這是我在簡(jiǎn)書上的第一篇文章熙揍。最近在自學(xué)操作系統(tǒng)职祷，然后發(fā)現(xiàn)網(wǎng)上很少有對(duì)內(nèi)存規(guī)劃這一塊進(jìn)行的比較直接簡(jiǎn)單完整的介紹。我想根據(jù)自己的理解寫一些東西届囚，作為記錄有梆，也可以和別人分享。其中自然會(huì)有許多理解上的錯(cuò)誤意系，希望能得到指證泥耀。
從而說起呢？我想自己意淫下蛔添。
想象下痰催，一開始的電腦是很簡(jiǎn)陋的兜辞。也就是只有幾十幾百KB的內(nèi)存。所以這個(gè)內(nèi)存就是程序所能用的空間的最大值夸溶。但是那時(shí)候程序也是很小的逸吵，所以夠用。后來科技發(fā)展了缝裁，程序員寫出了更加復(fù)雜的程序扫皱，這個(gè)時(shí)候，內(nèi)存不夠用了捷绑。于是問題就來了韩脑。
該怎么解決這個(gè)問題呢？
虛擬內(nèi)存粹污。
例子1扰才，看電影的時(shí)候，有時(shí)候一部電影得5G朝上厕怜，那么我們開始看的時(shí)候衩匣，有必要把后面時(shí)間段的視頻也載入內(nèi)存嗎？明顯沒必要粥航。所以我們把現(xiàn)在需要的一個(gè)時(shí)間段（working set）的數(shù)據(jù)載入內(nèi)存琅捏，然后不停地那新的視頻數(shù)據(jù)來代替舊的數(shù)據(jù)，這樣就大大節(jié)約了內(nèi)存递雀。
例子2柄延，玩魔獸世界的時(shí)候，不可能一下子把32G的游戲全部載入內(nèi)存缀程。就是根據(jù)你在哪兒搜吧，把相關(guān)信息載入內(nèi)存，然后你不停的去新的地點(diǎn)杨凑，他就不停的載入新的數(shù)據(jù)來替換掉舊的數(shù)據(jù)滤奈。
對(duì)于一臺(tái)內(nèi)存為256M的32bit x86主機(jī)來說，它的虛擬地址空間范圍是0~0xFFFFFFFF（4G）撩满，而物理地址空間范圍是0x000000000~0x0FFFFFFF（256M）
這就是虛擬內(nèi)存蜒程。把內(nèi)存的東西暫時(shí)存到硬盤里。需要的時(shí)候再取出來伺帘。
這就涉及到兩個(gè)問題昭躺。
1.放在硬盤的數(shù)據(jù)，如果內(nèi)存里的進(jìn)程需要了伪嫁，怎么找回來领炫？
2.硬盤的速度是內(nèi)存的幾百分之一，很慢张咳，如何設(shè)計(jì)系統(tǒng)才可以更好地提升計(jì)算機(jī)的效率帝洪。
問題二就可以分為兩個(gè)小問題似舵，
a.程序進(jìn)入內(nèi)存時(shí)，該給進(jìn)程配置多少頁
b.如果進(jìn)程需要新的頁碟狞，而分給他的空間已經(jīng)滿了啄枕，會(huì)用新頁代替舊頁，該選擇哪個(gè)代替（page replacement）
首先看第一個(gè)問題族沃∑底＃科學(xué)家發(fā)明了一種叫做MMU（Memory Management Unit）的硬件。他可以實(shí)現(xiàn)虛擬地址和物理地址之間的映射脆淹。
過去的時(shí)候常空，沒有MMU，程序員寫程序盖溺，編譯器翻譯時(shí)漓糙，會(huì)把相關(guān)地址直接翻譯成物理地址，然后直接映射到內(nèi)存的相應(yīng)區(qū)域『嬷觯現(xiàn)在有了MMU就不一樣了昆禽。編譯器可以把相關(guān)地址翻譯成邏輯地址，然后再由MMU轉(zhuǎn)換成相應(yīng)的物理地址蝇庭。這么做有什么好處呢醉鳖？
如果沒有MMU，首先是肯定不能使用虛擬內(nèi)存這個(gè)思想哮内。其次是盗棵，因?yàn)闆]有這么一個(gè)地址映射器，編譯器翻譯出來的地址就是物理地址北发，這樣為了確保程序運(yùn)行纹因，程序的數(shù)據(jù)段啊，代碼段啊琳拨，堆棧啊瞭恰，必須放在一塊連續(xù)的物理內(nèi)存里，這樣之后編譯器才能比較容易實(shí)現(xiàn)定位从绘。因?yàn)闂Ｖ羔樇氖瑁瑤羔槪謹(jǐn)?shù)據(jù)指針的地址都是存放在寄存器里面的僵井，寄存器通過加一減一這樣的簡(jiǎn)單操作來選擇下面的數(shù)據(jù)。所以所有數(shù)據(jù)必須放在一塊連續(xù)的內(nèi)存里驳棱，否則很可能通過指針就很難找到對(duì)應(yīng)數(shù)據(jù)了批什。
如果有了MMU，那么就不一樣了社搅。我只要保證邏輯地址是連續(xù)的就行了驻债。把剛剛的那些問題重復(fù)在這個(gè)有MMU的環(huán)境下乳规，那些問題就不再是問題了。邏輯地址連續(xù)合呐，那么我的棧指針暮的，幀指針，全局指針加一減一可以毫無問題的定位到相應(yīng)的邏輯地址淌实。而這些邏輯地址發(fā)到MMU里面冻辩，MMU把他們映射到不同的物理地址上，這樣仍然可以找到所需的數(shù)據(jù)拆祈。所以恨闪，有了MMU，邏輯地址是連續(xù)的放坏，進(jìn)程在物理空間上的映像卻再也不連續(xù)了咙咽。這有好處的，不連續(xù)的內(nèi)存映像可以減少內(nèi)存空洞（hole,內(nèi)部的淤年，外部的）的出現(xiàn)钧敞。這個(gè)原因具體自己查吧。
那么有了MMU之后麸粮，科學(xué)家又想出了一種軟件機(jī)制溉苛，分頁，（Page）豹休。即把邏輯地址分頁炊昆，分成一頁一頁的小內(nèi)存。然后再把物理內(nèi)存分幀威根，（Frame）凤巨，F(xiàn)rame大小和Page相等，Page是邏輯地址上的基本單位洛搀，F(xiàn)rame是物理地址上的基本單位敢茁，兩者通過MMU形成映射關(guān)系。
然后就必須要有頁表（Page Table）了留美。頁表記錄了邏輯地址上的一頁對(duì)應(yīng)了物理地址上的一幀彰檬。一般是把邏輯地址輸入進(jìn)MMU，同時(shí)給MMU載入頁表（這個(gè)過程下面會(huì)具體說）谎砾，然后MMU輸出相對(duì)應(yīng)的物理地址逢倍，從而實(shí)現(xiàn)定位，或者說景图，映射窍荧。
那么氏淑，這樣一個(gè)具體過程是怎么樣的呢稍走？我談下自己的理解绸狐。
假設(shè)我們下載了一個(gè)程序。然后它會(huì)存在硬盤里。雙擊啟動(dòng)它，程序被激活，變成了進(jìn)程贮尖，會(huì)向操作系統(tǒng)申請(qǐng)內(nèi)存，進(jìn)入等待隊(duì)列趁怔。然后OS通過算法湿硝，根據(jù)該進(jìn)程的頁（Page），從free pool里面分配一定數(shù)目的幀（Free Frame）痕钢。這就會(huì)涉及到問題二的a图柏，之后談。
然后通過導(dǎo)入的頁和其對(duì)應(yīng)的幀生成頁表任连，指向該頁表的指針儲(chǔ)存到該進(jìn)程的PCB（Process Control Block）里面蚤吹。這時(shí)候進(jìn)程變成就緒狀態(tài)，等待CPU随抠。CPU處理后裁着，執(zhí)行又一條instruction，如果需要新的頁拱她，而分配給進(jìn)程的空間已經(jīng)滿了二驰，這時(shí)候就會(huì)涉及到問題二的b，需要那新頁取代一些舊頁秉沼，算法之后談桶雀。進(jìn)程進(jìn)入等待隊(duì)列。
頁表的每一項(xiàng)邏輯地址都會(huì)有幾個(gè)狀態(tài)標(biāo)記位唬复。如矗积，reference flag(1 被引用過 0 未被引用過)，modified flag(1 被修改過 0 為被修改過)敞咧， value bit（1 在內(nèi)存里 0 無效頁或者在硬盤里） 還有一個(gè)標(biāo)志位用來標(biāo)志該頁在內(nèi)存還是在硬盤里棘捣。
當(dāng)上述情況發(fā)生時(shí)，OS會(huì)看該頁是否在內(nèi)存里休建。如果在乍恐，那沒事了，直接通過邏輯地址和MMU定位到相應(yīng)的物理地址上测砂。如果在硬盤里茵烈，會(huì)觸發(fā)一個(gè)中斷，page fault砌些，然后OS會(huì)去硬盤里調(diào)出相關(guān)的頁（同時(shí)將其value bit 設(shè)置為1）瞧毙，然后踢掉內(nèi)存里相關(guān)的頁，將其value bit設(shè)置為0（還有種情況是進(jìn)程空間未滿寄症，那就不用踢了宙彪，這里不討論了），拿新頁代替有巧。如果被代替的頁被修改過（modified flag = 1）,那么它得再次回寫到硬盤里（backing store）释漆，如果未被修改過，那么直接把對(duì)應(yīng)的frame放回free pool里面篮迎。下次直接覆蓋里面的內(nèi)容即可男图。然后當(dāng)頁條件滿足時(shí)，CPU會(huì) restart the instruction甜橱，重新跑一下剛剛那條指令逊笆。
當(dāng)然這里也有一個(gè)知識(shí)點(diǎn)，如果剛巧這個(gè)frame之后沒被用掉岂傲，然后那個(gè)頁又進(jìn)內(nèi)存了难裆，那他可以直接找到該frame，也不需要從硬盤把數(shù)據(jù)復(fù)制到該內(nèi)存塊上了镊掖，因?yàn)橹暗倪€未被覆蓋乃戈。所以frame也有個(gè)標(biāo)志位叫做dirty bit用來表示上面這個(gè)信息。然后frame的信息（哪些在被用亩进，哪些已經(jīng)被污染過了症虑，哪些free）都保存在一個(gè)叫做frame table的數(shù)據(jù)結(jié)構(gòu)中，然后OS知道它的位置归薛。
感覺這就基本是OS-Memory Management的流程了谍憔。每個(gè)進(jìn)程都有一個(gè)頁表，存在內(nèi)存的不連續(xù)位置里主籍。指向該頁表的指針存在PCB里习贫。
需要調(diào)入新頁的時(shí)候，CPU會(huì)生成一個(gè)虛擬地址送給MMU崇猫，MMU生成頁表表項(xiàng)（PTE）地址沈条，并從高速緩沖/主存中得到頁表。然后把該頁表返回給MMU诅炉，MMU通過該頁表和虛擬地址構(gòu)造物理地址蜡歹，并把該物理地址傳送給高速緩沖/主存，請(qǐng)求數(shù)據(jù)涕烧。所以需要訪問兩次主存月而。
然后，現(xiàn)在的虛擬空間一般很大议纯，如果page size小的話父款，有時(shí)候用來儲(chǔ)存信息的頁表也過大。但是我們不想用一段連續(xù)的內(nèi)存來存儲(chǔ)它，一般就會(huì)對(duì)應(yīng)有三種解決方法憨攒。
1.采用分級(jí)的方法世杀，兩級(jí)頁表等等。
2.采用Hashed Page Tables,每個(gè)表項(xiàng)里用鏈表連接肝集。
3.采用反轉(zhuǎn)頁表瞻坝，Inverted Page Table (IPT)，采用物理內(nèi)存順序（塊號(hào)）排序杏瞻。用進(jìn)程標(biāo)識(shí)符和頁號(hào)來檢索該反向頁表所刀。即通過物理內(nèi)存來找對(duì)應(yīng)的進(jìn)程的頁號(hào)。這樣每次都得檢索一下整個(gè)反向頁表來找所需要的東西捞挥，費(fèi)時(shí)浮创，但是該反向頁表卻比頁表要小很多（這里我不知道為什么小很多。）
有了分頁技術(shù)砌函，也就出現(xiàn)了斩披，shared pages。共享內(nèi)存胸嘴。即不同的程序可以通過頁號(hào)指向相同的frame雏掠，以此共享該塊數(shù)據(jù)。然后通過修改該共享數(shù)據(jù)劣像，也可以實(shí)現(xiàn)進(jìn)程間的通信乡话。
自然，shared pages也便宜了申請(qǐng)子進(jìn)程的開銷耳奕。當(dāng)父進(jìn)程fork()出子進(jìn)程后绑青，有一個(gè)叫做copy-on-write的技術(shù)。一開始子進(jìn)程的頁和父進(jìn)程指向相同的內(nèi)存塊屋群。如果在子進(jìn)程中修改了某個(gè)內(nèi)存數(shù)據(jù)闸婴，OS會(huì)把該修改的信息拷貝到另外一個(gè)內(nèi)存地址里，原內(nèi)存不變芍躏，所以此時(shí)本來共享某內(nèi)存塊的頁邪乍，父進(jìn)程仍指向原來的內(nèi)存塊，而子進(jìn)程指向了新的內(nèi)存塊对竣。其他未被修改過的頁仍指向同一個(gè)內(nèi)存塊庇楞。這樣大大減少了申請(qǐng)子進(jìn)程的開銷，因?yàn)橐婚_始不需要為其分配過多的內(nèi)存否纬。
共享數(shù)據(jù)還有一個(gè)叫做 Memory-Mapped Files吕晌，即把磁盤里面的文件直接拷貝到進(jìn)程空間里，避免了之后頻繁從磁盤加載到內(nèi)存临燃，回寫等步驟睛驳，而且進(jìn)程間可以通過該內(nèi)存映射文件實(shí)現(xiàn)通信烙心。
第一個(gè)問題差不多談到這里吧，下面說說第二個(gè)問題乏沸。分配算法淫茵。
a.程序進(jìn)入內(nèi)存時(shí)，該給進(jìn)程配置多少頁
b.如果進(jìn)程需要新的頁屎蜓，而分給他的空間已經(jīng)滿了痘昌，會(huì)用新頁代替舊頁，該選擇哪個(gè)代替（page replacement）
a.分配時(shí)必須給進(jìn)程保證最少數(shù)目的頁 = 進(jìn)程中單條指令最多所需的頁數(shù)
如果分配的不好炬转，會(huì)出現(xiàn)thrash現(xiàn)象，即OS不斷地收到page fault中斷算灸，不斷地向硬盤demand paging扼劈。造成效率降低。所以一般會(huì)根據(jù)不同的系統(tǒng)有一個(gè)working set菲驴，他有初始值荐吵，之后不斷變化。在一個(gè)working-set里面統(tǒng)計(jì)所有進(jìn)程所需要的頁數(shù)赊瞬，如果他大于目前物理內(nèi)存還剩的空間先煎，那么就得按照replacement算法，選擇一個(gè)進(jìn)程巧涧，將其設(shè)為無效薯蝎，把它的frame全部freee掉，空出足夠的空間來應(yīng)對(duì)thrash谤绳。
b
Page-replacement Algorithm有好多種占锯。比如 FIFO,OPT(不可能實(shí)現(xiàn))，LRU等等缩筛，再次不多說了
當(dāng)然剛剛談的都是用戶空間消略，內(nèi)核空間是完全不一樣的。
首先內(nèi)核空間的數(shù)據(jù)結(jié)構(gòu)大小不同瞎抛，很多小于one-page size艺演，如果采用分頁，浪費(fèi)空間桐臊，而內(nèi)核空間寸土寸金胎撤。
其次，用戶空間的程序?qū)r(shí)間要求不高豪硅，但內(nèi)核對(duì)響應(yīng)時(shí)間有著嚴(yán)格的要求哩照，所以如果采用分頁太浪費(fèi)時(shí)間了，只能用連續(xù)空間來儲(chǔ)存懒浮。
因此有兩種分配算法飘弧。Buddy System 和 Slab Allocation识藤，具體自己查吧。
最后說個(gè)題目次伶，如果這道題理解了痴昧，那么基本對(duì)內(nèi)存規(guī)劃也理解了。
one system, page size: 128 words, 整型（int）size: 1word
代碼1冠王，
int i,j;
int[128][128]data;
for(j = 0;j < 128;j++)
? ?for(i = 0;i < 128;i++)
? ? ? ?data[i][j] = 0;
代碼2赶撰，
int i,j;
int[128][128]data;
for(i = 0;i < 128;i++)
for(j = 0;j < 128;j++)
data[i][j] = 0;
你覺得這兩種算法哪個(gè)效率更高？
后記：這是修改過的文章柱彻，我一開始發(fā)表的時(shí)候不知道為什么后面一大段全部沒了豪娜，這讓我對(duì)簡(jiǎn)書的印象大打折扣。本著做一件像一件事的原則哟楷，我又重新打了瘤载。
寫完這篇萬丈感覺印象又加深了，但是感覺文章順序不太好卖擅，可能也是自己沒有準(zhǔn)備提筆就寫的結(jié)果吧鸣奔。希望有人會(huì)看吧，更加希望有人可以一起交流學(xué)習(xí)惩阶。
下面我就打算開始學(xué)習(xí)File Systems挎狸。加油
后記：
第一次寫文章，現(xiàn)在重讀断楷，覺得寫的太差了锨匆。該突出的重點(diǎn)也沒有突出出來。有一塊甚至遺漏了脐嫂。就是translation look-aside buffer (TLB), 中文翻譯應(yīng)該就是快表统刮。
OS會(huì)先去檢索快表，如果沒有命中账千，再根據(jù)頁號(hào)去內(nèi)存請(qǐng)求數(shù)據(jù)侥蒙。請(qǐng)求的數(shù)據(jù)先導(dǎo)入cache，然后更新快表匀奏，最后將所需要的數(shù)據(jù)送入CPU鞭衩。
快表是一個(gè)鍵值對(duì)，page-frame娃善。他之所以快是因?yàn)榭毂肀旧砭驮赾ache里面论衍，和他相關(guān)的數(shù)據(jù)也全部都在cache里面。然后CPU需要什么聚磺，就檢索快表坯台，找到了直接送入CPU。
真正的優(yōu)勢(shì)在于瘫寝，cache運(yùn)行比內(nèi)存快蜒蕾，而且距離CPU的物理距離近稠炬。
今天上課聽老師說馮諾依曼結(jié)構(gòu)的瓶頸就在于內(nèi)存和CPU的物理距離過大，現(xiàn)在CPU和內(nèi)存的速度越做越快咪啡，但是他們之間的距離卻無法改變首启，而傳輸數(shù)據(jù)的速率-光速也無法改變。所以我們得把計(jì)算機(jī)經(jīng)常用到的東西導(dǎo)入cache撤摸，避免計(jì)算機(jī)去內(nèi)存要東西毅桃，更不應(yīng)該讓計(jì)算機(jī)去硬盤要東西。
說到了cache准夷，我今天也查了下钥飞，加深了理解。cache和buffer有啥區(qū)別呢冕象？
1代承、Buffer（緩沖區(qū)）是系統(tǒng)兩端處理速度平衡（從長(zhǎng)時(shí)間尺度上看）時(shí)使用的。它的引入是為了減小短期內(nèi)突發(fā)I/O的影響渐扮，起到流量整形的作用。比如生產(chǎn)者——消費(fèi)者問題掖棉，他們產(chǎn)生和消耗資源的速度大體接近墓律，加一個(gè)buffer可以抵消掉資源剛產(chǎn)生/消耗時(shí)的突然變化。
2幔亥、Cache（緩存）則是系統(tǒng)兩端處理速度不匹配時(shí)的一種折衷策略耻讽。因?yàn)镃PU和memory之間的速度差異越來越大，所以人們充分利用數(shù)據(jù)的局部性（locality）特征帕棉，通過使用存儲(chǔ)系統(tǒng)分級(jí)（memory hierarchy）的策略來減小這種差異帶來的影響针肥。
3、假定以后存儲(chǔ)器訪問變得跟CPU做計(jì)算一樣快香伴，cache就可以消失慰枕，但是buffer依然存在。比如從網(wǎng)絡(luò)上下載東西即纲，瞬時(shí)速率可能會(huì)有較大變化具帮，但從長(zhǎng)期來看卻是穩(wěn)定的，這樣就能通過引入一個(gè)buffer使得OS接收數(shù)據(jù)的速率更穩(wěn)定低斋，進(jìn)一步減少對(duì)磁盤的傷害蜂厅。
4、TLB（Translation Lookaside Buffer膊畴，翻譯后備緩沖器）名字起錯(cuò)了掘猿，其實(shí)它是一個(gè)cache.
該段摘錄自 知乎 的一個(gè)匿名網(wǎng)友，寫的挺好的唇跨。我覺的buffer就是一個(gè)編程上的概念稠通，讓我們解決速率突然暴增的問題衬衬。不只是計(jì)算機(jī)，通信系統(tǒng)采记，銀行佣耐，日常生活其實(shí)都有buffer的思想。而cache就是一個(gè)硬件設(shè)備唧龄。
最后再談一個(gè)問題兼砖，之前的文章沒有說清楚。
邏輯地址既棺，虛擬地址讽挟，線性地址，物理地址之間的關(guān)系是什么丸冕？
我覺得我們?cè)诰幾g器上寫的代碼耽梅，編譯器翻譯出來的最初版本是邏輯地址。然后通過一個(gè) segmentation unit胖烛，將其分段眼姐。因?yàn)樵蹅兊拇a里面有，有代碼段佩番，數(shù)據(jù)段众旗，棧，堆趟畏，還有一些庫函數(shù)贡歧，系統(tǒng)文件等，我們需要將其分段赋秀，即把一個(gè)程序分成各個(gè)不同的部分利朵。這時(shí)候程序就變成了一個(gè)整體，有猎莲，系統(tǒng)空間绍弟，代碼段，數(shù)據(jù)段益眉，堆棧等晌柬。這時(shí)候的地址就是虛擬地址，又稱為線性地址郭脂。（虛擬地址 = 線性地址）年碘， 然后在經(jīng)過MMU就可以得到物理地址了。
送幾個(gè)截圖加深印象展鸡。
還有一篇?jiǎng)倓偪吹降奈恼掠煨疲唧w地講述了cache運(yùn)行的機(jī)理和硬件上的構(gòu)造。有興趣可以看下莹弊。我是看懂了涤久，但是很快會(huì)忘掉涡尘，其實(shí)有個(gè)大體的印象就可以了。其中有句話我思考了下响迂，他說考抄，每個(gè)進(jìn)程都認(rèn)為自己有4G的內(nèi)存空間。為什么蔗彤。因?yàn)槊總€(gè)進(jìn)程的虛擬空間都有4G川梅。虛擬空間是分頁的，你可以把程序?qū)懗?G（此說法不太嚴(yán)謹(jǐn)然遏，畢竟還有操作系統(tǒng)得占空間）贫途，然后會(huì)給你分頁的。你也可以寫成4M待侵，然后沒用的空間首先就不會(huì)給你分頁丢早。畢竟是虛擬地址。所以不會(huì)有多大影響秧倾。
鏈接如下：
http://www.cnblogs.com/pengdonglin137/p/3362274.html
