Algorithm
// 暴力解法
func maxArea1(height []int) (result int) {
i := 0
result = 0
for i < len(height) {
k := i + 1
for k < len(height) {
current := (k - i) * min(height[i], height[k])
if current > result {
result = current
}
k++
}
i++
}
return
}
func min(a int, b int) (result int) {
if a < b {
return a
}
return b
}
// 官方雙指針解法
func maxArea2(height []int) (result int) {
left := 0
right := len(height) - 1
result = 0
for left < right {
current := (right - left) * min(height[left], height[right])
if current > result {
result = current
}
if height[left] < height[right] {
left += 1
continue
}
if height[left] >= height[right] {
right -= 1
continue
}
}
return
}
Review
10 Common Software Architectural Patterns in a nutshell
文章介紹了一些常用的設(shè)計模式的優(yōu)缺點和使用場景间狂。
TIP
這周開發(fā)過程涉及到狀態(tài)機相關(guān)需求，所以了解了fsm相關(guān)概念火架。并使用Go開源fsm庫完成了業(yè)務(wù)需求鉴象。
Share
繼續(xù)學(xué)習(xí)“操作系統(tǒng)32講”
L23 段頁結(jié)合的實際內(nèi)存管理
虛擬內(nèi)存
用戶角度只能看到分段的虛擬內(nèi)存，硬件角度虛擬地址映射的是物理內(nèi)存的頁號何鸡。操作系統(tǒng)負責(zé)虛擬地址到物理地址的轉(zhuǎn)換（ 重定位也就是地址翻譯）纺弊。
- 首先根據(jù)段號+偏移（CS：IP）去段表）找到對應(yīng)的虛擬地址。CS對應(yīng)段號骡男，IP對應(yīng)偏移量淆游。比如CS：IP為1：30，段號找到基址為0x4800，再加上偏移量得到虛擬地址犹菱。
段號 基址 長度 保護
0 0x4000 0x0800 R
1 0x4800 0x1400 R/W
2 0xF000 0x1000 R/W
3 0x0000 0x3000 R
- 根據(jù)步驟1得到的虛擬地址拾稳，然后去頁表里面查詢得到物理地址。步驟1腊脱、2實際都是由MMU自動完成访得。
操作系統(tǒng)在fork一個進程過程如何實現(xiàn)內(nèi)存分配和虛實地址映射
- 從虛擬內(nèi)存中分配一段內(nèi)存段給新的進程，然后分配對應(yīng)段表陕凹。這里講的是比較簡單的內(nèi)存分割算法（根據(jù)進程ID遞增分配內(nèi)存塊）
// 這個函數(shù)講的就是fork進程的時候悍抑，把父進程的內(nèi)存信息copy一份到子進程
int copy_mem(int nr,task_struct *p){ // p就是被fork的進程的pcb
unsigned long new_data_base;
new_data_base = nr * 0x4000000; // 64M*nr nr代表第幾個進程，32位操作系統(tǒng)每個進程的內(nèi)存空間是64M nr*64就是偏移量
set_base(p->ldt[1],new_data_base); // 設(shè)置基地址杜耙，這里可能是數(shù)據(jù)段搜骡。并且建立段表
set_base(p->ldt[2],new_data_base); // 設(shè)置基地址，這里可能是代碼段佑女。并且建立段表
}
- 分配物理內(nèi)存记靡，建立頁表。這里因為和父進程共用內(nèi)存珊豹，所以不需要分配新的物理內(nèi)存簸呈，直接建立頁表就可以。
32位操作系統(tǒng)的多級頁表：
10bits 10bits 12bits
頁目錄號 頁號 offset（頁內(nèi)偏移）
分配物理內(nèi)存
int copy_mem(int nr,task_struct *p){
unsigned long old_data_base;
old_data_base = get_base(current->ldt[2]);
copy_page_tables(old_data_base, new_data_base, data_limit);
}
// 建立子進程的頁表
int copy_page_tables(unsigned long from, unsigned long to, long size){
from_dir = (unsigned long *)((from >> 20) & 0xffc); // 頁內(nèi)偏移為12bits 頁號為10bits店茶，先右移22位得到頁目錄號 每個頁目錄號對應(yīng)的頁號為4字節(jié) 所以需要向左偏移2位 最終就是向右偏移20位
to_dir = (unsigned long *)((to >> 20) & 0xffc);
size = (unsigned long *)(size + 0x3ffffff) >> 22; // 有多個頁目錄章節(jié)
for(; size-->0;from_dir++, to_dir++){ // 建立新的頁目錄章節(jié)的具體頁號內(nèi)容映射
from_page_table = (0xffffff000 & *from_dir);
to_page_table = get_free_page(); // 去物理內(nèi)存中申請新的內(nèi)存分配給新的頁號
*to_dir = ((unsigned long) to_page_table) | 7;
}
for(;nr-->0;from_page_table++,to_page_table++){ // 拷貝父進程的頁號內(nèi)容到子進程
this_page = *from_page_table; // from_page_table是父進程的內(nèi)存指針蜕便，*from_page_table就是指針指向的內(nèi)容
this_page &= ~2; // 父子進程共用內(nèi)存，所以需要設(shè)置為只讀
*to_page_table = this_page; // 父進程內(nèi)容給子進程
*from_page_table = this_page; // 內(nèi)存塊修改成只讀贩幻，所以需要給父進程也重新賦值一下
this_page -= LOW_MEM;
this_page >>= 12;
mem_map[this_page]++;
}
}
L24 內(nèi)存換入-請求調(diào)頁
為什么需要內(nèi)存換入
32位操作系統(tǒng)在用戶角度來看轿腺，4G的虛擬內(nèi)存都是可以隨意使用的。但是實際的物理內(nèi)存可能就只有1G或者3G丛楚，為了較小的物理內(nèi)存能夠支撐4G的虛擬內(nèi)存族壳，就引入了內(nèi)存換入。
用戶程序趣些、數(shù)據(jù)在沒有使用的時候存儲在磁盤上仿荆，在需要用到的時候?qū)⑿枰臄?shù)據(jù)寫入到內(nèi)存上，這就是內(nèi)存換入坏平。
如何實現(xiàn)內(nèi)存換入
- CS：IP查找段表之后拢操，得到虛擬地址。
- MMU拿虛擬地址去查找頁表的時候舶替，如果頁表上找不到對應(yīng)的頁框號這時候會觸發(fā)一個缺頁中斷（page fault）令境。
- 中斷處理程序處理缺頁中斷的時候，先去磁盤找到對應(yīng)數(shù)據(jù)顾瞪，然后會去內(nèi)存中g(shù)et_free_page找到一個空白的內(nèi)存段并將磁盤中的數(shù)據(jù)寫入到free_page中舔庶。
- 中斷處理完成之后抛蚁，繼續(xù)完成剩下程序邏輯。整個內(nèi)存換入完成惕橙。
L25 內(nèi)存換出
內(nèi)存換出常用算法
- FIFO：先入先出算法 會產(chǎn)生較多的缺頁次數(shù)
- MIN算法：選最遠將使用的頁淘汰瞧甩。這個是最優(yōu)算法，但是無法預(yù)測未來哪些頁會被訪問吕漂。
- LRU（least recent used）：最近最長一段時間沒有使用的頁進行淘汰亲配。最近不常用的頁表尘应，一般來說未來也不會被經(jīng)常使用所以可以優(yōu)先進行淘汰惶凝。這個也符合計算機的局部性現(xiàn)象。
LFU算法的實現(xiàn)
- 使用頁碼棧來實現(xiàn)犬钢，最準(zhǔn)確苍鲜。但是每次地址訪問都需要修改棧，實現(xiàn)代價太大玷犹。
- 將頁組織成循環(huán)隊列混滔，給每個頁加一個引用位（reference bit）。時間輪（clock）算法
- 每次訪問一頁時歹颓，硬件MMU自動設(shè)置引用位為1
- 選擇淘汰頁：觸發(fā)缺頁中斷的時候遍歷循環(huán)隊列并掃描引用位坯屿，如果引用位是1的時候清0并繼續(xù)掃描；如果引用位是0的話巍扛，就選擇該頁進行淘汰领跛。 SCR算法（second chance replacement）。
- clock算法的改進
- 缺頁中斷觸發(fā)幾率很小撤奸，同時MMU每次訪問頁表的時候都會自動把引用位置為1吠昭。這樣就會導(dǎo)致很大概率下缺頁中斷處理過程，時間輪上的所有引用位都為1胧瓜，這時候就會導(dǎo)致每次淘汰的都是最先來的頁矢棚。最終退化成FIFO。
- 解決方案：引入一個掃描指針府喳。掃描指針不斷地定時輪訓(xùn)循環(huán)隊列并把引用位置為0蒲肋。掃描指針移動速度比淘汰指針快，這樣子實現(xiàn)定時清除引用位钝满。從而防止clock算法退化成FIFO兜粘。
