全面解讀操作系統(tǒng)中的內(nèi)存管理，你懂幾點(diǎn)？

轉(zhuǎn)自 | 程序喵大人

今天分享關(guān)于內(nèi)存的幾點(diǎn)內(nèi)容：

• 什么是物理內(nèi)存

• 使用物理內(nèi)存有什么缺點(diǎn)？

• 什么是虛擬內(nèi)存？

• 虛擬內(nèi)存如何映射到物理內(nèi)存

• 什么是分頁(yè)內(nèi)存管理？

• 什么是缺頁(yè)中斷？

• 頁(yè)面置換算法都有哪些？

• 什么是分段內(nèi)存管理？

01什么是物理內(nèi)存？

我們常說(shuō)的物理內(nèi)存大小就是指內(nèi)存條的大小，一般買(mǎi)電腦時(shí)都會(huì)看下內(nèi)存條是多大容量的，話說(shuō)如果內(nèi)存條大小是100G，那這100G就都能夠被使用嗎？不一定的，更多的還是要看CPU地址總線的位數(shù)，如果地址總線只有20位，那么它的尋址空間就是1MB，即使可以安裝100G的內(nèi)存條也沒(méi)有意義，也只能視物理內(nèi)存大小為1MB。

02使用物理內(nèi)存有什么缺點(diǎn)？

這種方式下每個(gè)程序都可以直接訪問(wèn)物理內(nèi)存，有兩種情況：

1.系統(tǒng)中只有一個(gè)進(jìn)程在運(yùn)行：如果用戶程序可以操作物理地址空間的任意地址，它們就很容易在不經(jīng)意間破壞了操作系統(tǒng)，使系統(tǒng)出現(xiàn)各種奇奇怪怪的問(wèn)題；

2.系統(tǒng)有多個(gè)進(jìn)程同時(shí)在運(yùn)行：如圖，理想情況下可以使進(jìn)程A和進(jìn)程B各占物理內(nèi)存的一邊，兩者互不干擾，但這只是理想情況下，誰(shuí)能確保程序沒(méi)有bug呢，進(jìn)程B在后臺(tái)正常運(yùn)行著，程序員在調(diào)試進(jìn)程A時(shí)有可能就會(huì)誤操作到進(jìn)程B正在使用的物理內(nèi)存，導(dǎo)致進(jìn)程B運(yùn)行出現(xiàn)異常，兩個(gè)程序操作了同一地址空間，第一個(gè)程序在某一地址空間寫(xiě)入某個(gè)值，第二個(gè)程序在同一地址又寫(xiě)入了不同值，這就會(huì)導(dǎo)致程序運(yùn)行出現(xiàn)問(wèn)題，所以直接使用物理內(nèi)存會(huì)使所有進(jìn)程的安全性得不到保證。

如何解決上述問(wèn)題？

可以考慮為存儲(chǔ)器創(chuàng)造新的抽象概念：地址空間，地址空間為程序創(chuàng)造了一種抽象的內(nèi)存，是進(jìn)程可用于尋址內(nèi)存的一套地址集合，同時(shí)每個(gè)進(jìn)程都有一套自己的地址空間，一個(gè)進(jìn)程的地址空間獨(dú)立于其它進(jìn)程的地址空間。

如何為程序創(chuàng)造獨(dú)立的地址空間？

最簡(jiǎn)單的辦法就是把每個(gè)進(jìn)程的地址空間分別映射到物理內(nèi)存的不同部分。這樣就可以保證不同進(jìn)程使用的是獨(dú)立的地址空間。

實(shí)現(xiàn)

給每個(gè)進(jìn)程提供一個(gè)基址A和界限B，進(jìn)程內(nèi)使用的空間為x，則對(duì)應(yīng)的物理地址為A + x，同時(shí)需要保證A + x < B，如果訪問(wèn)的地址超過(guò)的界限，需要產(chǎn)生錯(cuò)誤并中止訪問(wèn)。為了達(dá)到目的CPU配置了兩個(gè)特殊硬件寄存器：基址寄存器和界限寄存器，當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)，程序的起始物理地址和長(zhǎng)度會(huì)分別裝入到基址寄存器和界限寄存器里，進(jìn)程訪問(wèn)內(nèi)存，在每個(gè)內(nèi)存地址送到內(nèi)存之前，都會(huì)先加上基址寄存器的內(nèi)容。

缺點(diǎn)：每次訪問(wèn)內(nèi)存都需要進(jìn)行加法和比較運(yùn)算，比較運(yùn)算很快，但是加法運(yùn)算由于進(jìn)位傳遞事件的問(wèn)題，在沒(méi)有使用特殊電路的情況下會(huì)顯得很慢。

此外，每個(gè)進(jìn)程運(yùn)行都會(huì)占據(jù)一定的物理內(nèi)存，如果物理內(nèi)存足夠大到可以容納許多個(gè)進(jìn)程同時(shí)運(yùn)行還好，但現(xiàn)實(shí)中物理內(nèi)存的大小是有限的，可能會(huì)出現(xiàn)內(nèi)存不夠用的情況，怎么辦？

方法一：如果是因?yàn)槌绦蛱?，大到超過(guò)了內(nèi)存的容量，可以采用手動(dòng)覆蓋技術(shù)，只把需要的指令和數(shù)據(jù)保存在內(nèi)存中。

方法二：如果是因?yàn)槌绦蛱?，?dǎo)致超過(guò)了內(nèi)存的容量，可以采用自動(dòng)交換技術(shù)，把暫時(shí)不需要執(zhí)行的程序移動(dòng)到外存中。

覆蓋技術(shù)

把程序按照自身邏輯結(jié)構(gòu)，劃分成多個(gè)功能相互獨(dú)立的程序模塊，那些不會(huì)同時(shí)執(zhí)行的模塊可以共享到同一塊內(nèi)存區(qū)域，按時(shí)間順序來(lái)運(yùn)行：

將常用功能需要的代碼和數(shù)據(jù)常駐在內(nèi)存中；

將不常用的功能劃分成功能相互獨(dú)立的程序模塊，平時(shí)放到外存中，在需要的時(shí)候?qū)?duì)應(yīng)的模塊加載到內(nèi)存中；

那些沒(méi)有調(diào)用關(guān)系的模塊平時(shí)不需要裝入到內(nèi)存，它們可以共用一塊內(nèi)存區(qū)，需要時(shí)加載到內(nèi)存，不需要時(shí)換出到外存中；

如圖：

交換技術(shù)

多個(gè)程序同時(shí)運(yùn)行，可以將暫時(shí)不能運(yùn)行的程序送到外存，獲得更多的空閑內(nèi)存，操作系統(tǒng)將一個(gè)進(jìn)程的整個(gè)地址空間內(nèi)容換出到外存中，再將外存中某個(gè)進(jìn)程的整個(gè)地址空間信息換入到內(nèi)存中，換入換出內(nèi)容的大小是整個(gè)程序的地址空間。

交換技術(shù)在實(shí)現(xiàn)上有很多困難：

需要確定什么時(shí)候發(fā)生交換：簡(jiǎn)單的辦法是可以在內(nèi)存空間不夠用時(shí)換出一些程序；

交換區(qū)必須足夠大：多個(gè)程序運(yùn)行時(shí)，交換區(qū)（外存）必須足夠大，大到可以存放所有程序所需要的地址空間信息；

程序如何換入：一個(gè)程序被換出后又重新?lián)Q入，換入的內(nèi)存位置可能不會(huì)和上一次程序所在的內(nèi)存位置相同，這就需要?jiǎng)討B(tài)地址映射機(jī)制。

覆蓋技術(shù)和交換技術(shù)的比較

覆蓋只能發(fā)生在那些相互之間沒(méi)有調(diào)用關(guān)系的程序模塊之間，因此程序員必須給出程序內(nèi)的各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。

交換技術(shù)是以在內(nèi)存中的程序大小為單位來(lái)進(jìn)行的，它不需要程序員給出各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。

通俗來(lái)說(shuō)：覆蓋發(fā)生在程序的內(nèi)部，交換發(fā)生在程序與程序之間。

但是這兩種技術(shù)都有缺點(diǎn)：

覆蓋技術(shù)：需要程序員自己把整個(gè)程序劃分為若干個(gè)小的功能模塊，并確定各個(gè)模塊之間的覆蓋關(guān)系，增加了程序員的負(fù)擔(dān)，很少有程序員擅長(zhǎng)這種技術(shù)；

交換技術(shù)：以進(jìn)程作為交換的單位，需要把進(jìn)程的整個(gè)地址空間都換進(jìn)換出，增加了處理器的開(kāi)銷，還需要足夠大的外存。

那有沒(méi)有更好的解決上述問(wèn)題的方法呢？答案是虛擬內(nèi)存技術(shù)。

03什么是虛擬內(nèi)存？

虛擬內(nèi)存，那就是虛擬出來(lái)的內(nèi)存，它的基本思想就是確保每個(gè)程序擁有自己的地址空間，地址空間被分成多個(gè)塊，每一塊都有連續(xù)的地址空間，同時(shí)物理空間也分成多個(gè)塊，塊大小和虛擬地址空間的塊大小一致，操作系統(tǒng)會(huì)自動(dòng)將虛擬地址空間映射到物理地址空間，程序所關(guān)注的只是虛擬內(nèi)存，請(qǐng)求的也是虛擬內(nèi)存，其實(shí)真正使用的是物理內(nèi)存。

虛擬內(nèi)存技術(shù)有覆蓋技術(shù)的功能，但它不是把程序的所有內(nèi)容都放在內(nèi)存中，因而能夠運(yùn)行比當(dāng)前的空閑內(nèi)存空間還要大的程序。它比覆蓋技術(shù)做的更好，整個(gè)過(guò)程由操作系統(tǒng)自動(dòng)來(lái)完成，無(wú)需程序員的干涉；

虛擬內(nèi)存技術(shù)有交換技術(shù)的功能，能夠?qū)崿F(xiàn)進(jìn)程在內(nèi)存和外存之間的交換，因而獲得更多的空閑內(nèi)存空間。它比交換技術(shù)做的更好，它只對(duì)進(jìn)程的部分內(nèi)容在內(nèi)存和外存之間進(jìn)行交換。

虛擬內(nèi)存技術(shù)的具體實(shí)現(xiàn)：

虛擬內(nèi)存技術(shù)一般是在頁(yè)式管理（下面介紹）的基礎(chǔ)上實(shí)現(xiàn)

在裝入程序時(shí)，不必將其全部裝入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的部分頁(yè)面裝入到內(nèi)存，就可讓程序開(kāi)始執(zhí)行；

在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁(yè)）。則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)面調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序；

另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)面調(diào)出保存在外存上，從而騰出更多空閑空間存放將要裝入的程序以及將要調(diào)入的頁(yè)面。

虛擬內(nèi)存技術(shù)的特點(diǎn) ：

大的用戶空間：通過(guò)把物理內(nèi)存與外存相結(jié)合，提供給用戶的虛擬內(nèi)存空間通常大于實(shí)際的物理內(nèi)存，即實(shí)現(xiàn)了兩者的分離。如32位的虛擬地址理論上可以訪問(wèn)4GB，而可能計(jì)算機(jī)上僅有256M的物理內(nèi)存，但硬盤(pán)容量大于4GB；

部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的；

連續(xù)性：程序可以使用一系列相鄰連續(xù)的虛擬地址來(lái)映射物理內(nèi)存中不連續(xù)的大內(nèi)存緩沖區(qū)；

安全性：不同進(jìn)程使用的虛擬地址彼此隔離。一個(gè)進(jìn)程中的代碼無(wú)法更改正在由另一進(jìn)程或操作系統(tǒng)使用的物理內(nèi)存。

04虛擬內(nèi)存如何映射到物理內(nèi)存？
如圖，CPU里有一個(gè)內(nèi)存管理單元（Memory Management Unit），簡(jiǎn)稱MMU，虛擬內(nèi)存不是直接送到內(nèi)存總線，而是先給到MMU，由MMU來(lái)把虛擬地址映射到物理地址，程序只需要管理虛擬內(nèi)存就好，映射的邏輯自然有其它模塊自動(dòng)處理。

操作系統(tǒng)如何表示的內(nèi)存被占用還是空閑？

05分頁(yè)內(nèi)存管理

將虛擬地址空間分成若干個(gè)塊，每個(gè)塊都有固定的大小，物理地址空間也被劃分成若干個(gè)塊，每個(gè)塊也都有固定的大小，物理地址空間的塊和虛擬地址空間的塊大小相等，虛擬地址空間這些塊就被稱為頁(yè)面，物理地址空間這些塊被稱為幀。

關(guān)于分頁(yè)這里有個(gè)問(wèn)題，頁(yè)面的大小是多少合適呢？頁(yè)面太大容易產(chǎn)生空間浪費(fèi)，程序假如只使用了1個(gè)字節(jié)卻被分配了10M的頁(yè)面，這豈不是極大的浪費(fèi)，頁(yè)面太小會(huì)導(dǎo)致頁(yè)表（下面介紹）占用空間過(guò)大，所以頁(yè)面需要折中選擇合適的大小，目前大多數(shù)系統(tǒng)都使用4KB作為頁(yè)的大小。

上面關(guān)于虛擬內(nèi)存如何映射到物理內(nèi)存程序喵只介紹了MMU，但是MMU是如何工作的還沒(méi)有介紹，MMU通過(guò)頁(yè)表這個(gè)工具將虛擬地址轉(zhuǎn)換為物理地址。32位的虛擬地址分成兩部分（虛擬頁(yè)號(hào)和偏移量），MMU通過(guò)頁(yè)表找到了虛擬頁(yè)號(hào)對(duì)應(yīng)的物理頁(yè)號(hào)，物理頁(yè)號(hào)+偏移量就是實(shí)際的物理地址。

具體如圖：

圖只表示了頁(yè)表的大體功能，頁(yè)表的結(jié)構(gòu)其實(shí)還很復(fù)雜，下面會(huì)具體介紹。

頁(yè)表的目的就是虛擬頁(yè)面映射為物理內(nèi)存的頁(yè)框，頁(yè)表可以理解為一個(gè)數(shù)學(xué)函數(shù)，函數(shù)的輸入是虛擬頁(yè)號(hào)，函數(shù)的輸出是物理頁(yè)號(hào)，通過(guò)這個(gè)函數(shù)可以把虛擬頁(yè)面映射到物理頁(yè)號(hào)，從而確定物理地址。不同機(jī)器的頁(yè)表結(jié)構(gòu)不同，通常頁(yè)表的結(jié)構(gòu)如下：

頁(yè)框號(hào)：最主要的一項(xiàng)，頁(yè)表最主要的目的就是找到物理頁(yè)號(hào)；

有效位：1表示有效，表示該表項(xiàng)是有效的，如果為0，表示該表項(xiàng)對(duì)應(yīng)的虛擬頁(yè)面現(xiàn)在不在內(nèi)存中，訪問(wèn)該頁(yè)面會(huì)引起缺頁(yè)中斷，缺頁(yè)中斷后會(huì)去物理空間找到一個(gè)可用的頁(yè)框填回到頁(yè)表中；

保護(hù)位：表示一個(gè)頁(yè)允許什么類型的訪問(wèn)，可讀可寫(xiě)還是可執(zhí)行；

修改位：該位反應(yīng)了頁(yè)面的狀態(tài)，在操作系統(tǒng)重新分配頁(yè)框時(shí)有用，在寫(xiě)入一頁(yè)時(shí)由硬件自動(dòng)設(shè)置該位，重新分配頁(yè)框時(shí)，如果一個(gè)頁(yè)面已經(jīng)被修改過(guò)，則必須把它這個(gè)臟頁(yè)寫(xiě)回磁盤(pán)，如果沒(méi)有被修改過(guò)，表示該頁(yè)是干凈的，它在磁盤(pán)上的副本依然是有效的，直接丟棄該頁(yè)面即可。

訪問(wèn)位：該位主要用于幫助操作系統(tǒng)在發(fā)生缺頁(yè)中斷時(shí)選擇要被淘汰的頁(yè)面，不再使用的頁(yè)面顯然比正在使用的頁(yè)面更適合被淘汰，該位在頁(yè)面置換算法中發(fā)揮重要作用。

高速緩存禁止位：該位用于禁止該頁(yè)面被高速緩存。

如何加快地址映射速度？

每次訪問(wèn)內(nèi)存都需要進(jìn)行虛擬地址到物理地址的映射，每次映射都需要訪問(wèn)一次頁(yè)表，所有的指令執(zhí)行都必須通過(guò)內(nèi)存，很多指令也需要訪問(wèn)內(nèi)存中的操作數(shù)，因此每條指令執(zhí)行基本都會(huì)進(jìn)行多次頁(yè)表查詢，為了程序運(yùn)行速度，指令必須要在很短的時(shí)間內(nèi)執(zhí)行完成，而頁(yè)表查詢映射不能成為指令執(zhí)行的瓶頸，所以需要提高頁(yè)表查詢映射的速度。

如何才能提高速度呢？可以為頁(yè)表提供一個(gè)緩存，通過(guò)緩存進(jìn)行映射比通過(guò)頁(yè)表映射速度更快，這個(gè)緩存是一個(gè)小型的硬件設(shè)備，叫快表（TLB），MMU每次進(jìn)行虛擬地址轉(zhuǎn)換時(shí)，首先去TLB中查找，找到了有效的物理頁(yè)框則直接返回，如果沒(méi)有找到則進(jìn)行正常的頁(yè)表訪問(wèn)，頁(yè)表中找到后則更新TLB，從TLB中淘汰一個(gè)表項(xiàng)，然后用新找到的表項(xiàng)替代它，這樣下次相同的頁(yè)面過(guò)來(lái)時(shí)可以直接命中TLB找到對(duì)應(yīng)的物理地址，速度更快，不需要繼續(xù)去訪問(wèn)頁(yè)表。

這里之所以認(rèn)為T(mén)LB能提高速度主要依靠程序局部性原理，程序局部性原理是指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)間，所執(zhí)行的指令地址和要訪問(wèn)的數(shù)據(jù)通常都局限在一塊區(qū)域內(nèi)，這里可分為時(shí)間局部性和空間局部性：

時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)間內(nèi)；

空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的幾個(gè)數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。

通過(guò)TLB可以加快虛擬地址到物理地址的轉(zhuǎn)換速度，還有個(gè)問(wèn)題，現(xiàn)在都是64位操作系統(tǒng)啦，有很大的虛擬地址空間，虛擬地址空間大那對(duì)應(yīng)的頁(yè)表也會(huì)非常大，又加上多個(gè)進(jìn)程多個(gè)頁(yè)表，那計(jì)算機(jī)的大部分空間就都被拿去存放頁(yè)表，有沒(méi)有更好的辦法解決頁(yè)表大的問(wèn)題呢？答案是多級(jí)頁(yè)表。

tips：頁(yè)表為什么大？32位環(huán)境下，虛擬地址空間有4GB，一個(gè)頁(yè)大小是4KB，那么整個(gè)頁(yè)表就需要100萬(wàn)頁(yè)，而每個(gè)頁(yè)表項(xiàng)需要4個(gè)字節(jié)，那整個(gè)頁(yè)表就需要4MB的內(nèi)存空間，又因?yàn)槊總€(gè)進(jìn)程都有一個(gè)自己的頁(yè)表，多個(gè)進(jìn)程情況下，這簡(jiǎn)直就是災(zāi)難。

如圖，以一個(gè)32位虛擬地址的二級(jí)頁(yè)表為例，將32位虛擬地址劃分為10位的PT1域，10位的PT2域，以及12位的offset域，當(dāng)一個(gè)虛擬地址被送入MMU時(shí)，MMU首先提取PT1域并把其值作為訪問(wèn)第一級(jí)頁(yè)表的索引，之后提取PT2域把把其值作為訪問(wèn)第二級(jí)頁(yè)表的索引，之后再根據(jù)offset找到對(duì)應(yīng)的頁(yè)框號(hào)。

32位的虛擬地址空間下：每個(gè)頁(yè)面4KB，且每條頁(yè)表項(xiàng)占4B：

一級(jí)頁(yè)表：進(jìn)程需要1M個(gè)頁(yè)表項(xiàng)（4GB / 4KB = 1M, 2^20個(gè)頁(yè)表項(xiàng)），即頁(yè)表（每個(gè)進(jìn)程都有一個(gè)頁(yè)表）占用4MB（1M * 4B = 4MB）的內(nèi)存空間。

二級(jí)頁(yè)表：一級(jí)頁(yè)表映射4MB（2^22）、二級(jí)頁(yè)表映射4KB，則需要1K個(gè)一級(jí)頁(yè)表項(xiàng)（4GB / 4MB = 1K, 2^10個(gè)一級(jí)頁(yè)表項(xiàng)）、每個(gè)一級(jí)頁(yè)表項(xiàng)對(duì)應(yīng)1K個(gè)二級(jí)頁(yè)表項(xiàng)（4MB / 4KB = 1K），這樣頁(yè)表占用4.004MB（1K * 4B + 1K * 1K * 4B = 4.004MB）的內(nèi)存空間。

二級(jí)頁(yè)表占用空間看著貌似變大了，為什么還說(shuō)多級(jí)頁(yè)表省內(nèi)存呢？

每個(gè)進(jìn)程都有4GB的虛擬地址空間，而顯然對(duì)于大多數(shù)程序來(lái)說(shuō)，其使用到的空間遠(yuǎn)未達(dá)到4GB，何必去映射不可能用到的空間呢？

也就是說(shuō)，一級(jí)頁(yè)表覆蓋了整個(gè)4GB虛擬地址空間，但如果某個(gè)一級(jí)頁(yè)表的頁(yè)表項(xiàng)沒(méi)有被用到，也就不需要?jiǎng)?chuàng)建這個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)的二級(jí)頁(yè)表了，即可以在需要時(shí)才創(chuàng)建二級(jí)頁(yè)表。做個(gè)簡(jiǎn)單的計(jì)算，假設(shè)只有20%的一級(jí)頁(yè)表項(xiàng)被用到了，那么頁(yè)表占用的內(nèi)存空間就只有0.804MB（1K*4B+0.2*1K*1K*4B=0.804MB），對(duì)比單級(jí)頁(yè)表的4M是不是一個(gè)巨大的節(jié)約？

那么為什么不分級(jí)的頁(yè)表就做不到這樣節(jié)約內(nèi)存呢？我們從頁(yè)表的性質(zhì)來(lái)看，保存在主存中的頁(yè)表承擔(dān)的職責(zé)是將虛擬地址翻譯成物理地址。假如虛擬地址在頁(yè)表中找不到對(duì)應(yīng)的頁(yè)表項(xiàng)，計(jì)算機(jī)系統(tǒng)就不能工作了。所以頁(yè)表一定要覆蓋全部虛擬地址空間，不分級(jí)的頁(yè)表就需要有1M個(gè)頁(yè)表項(xiàng)來(lái)映射，而二級(jí)頁(yè)表則最少只需要1K個(gè)頁(yè)表項(xiàng)（此時(shí)一級(jí)頁(yè)表覆蓋到了全部虛擬地址空間，二級(jí)頁(yè)表在需要時(shí)創(chuàng)建）。

二級(jí)頁(yè)表其實(shí)可以不在內(nèi)存中：其實(shí)這就像是把頁(yè)表當(dāng)成了頁(yè)面。當(dāng)需要用到某個(gè)頁(yè)面時(shí)，將此頁(yè)面從磁盤(pán)調(diào)入到內(nèi)存；當(dāng)內(nèi)存中頁(yè)面滿了時(shí)，將內(nèi)存中的頁(yè)面調(diào)出到磁盤(pán)，這是利用到了程序運(yùn)行的局部性原理。我們可以很自然發(fā)現(xiàn)，虛擬內(nèi)存地址存在著局部性，那么負(fù)責(zé)映射虛擬內(nèi)存地址的頁(yè)表項(xiàng)當(dāng)然也存在著局部性了！這樣我們?cè)賮?lái)看二級(jí)頁(yè)表，根據(jù)局部性原理，1024個(gè)第二級(jí)頁(yè)表中，只會(huì)有很少的一部分在某一時(shí)刻正在使用，我們豈不是可以把二級(jí)頁(yè)表都放在磁盤(pán)中，在需要時(shí)才調(diào)入到內(nèi)存？

我們考慮極端情況，只有一級(jí)頁(yè)表在內(nèi)存中，二級(jí)頁(yè)表僅有一個(gè)在內(nèi)存中，其余全在磁盤(pán)中（雖然這樣效率非常低），則此時(shí)頁(yè)表占用了8KB（1K*4B+1*1K*4B=8KB），對(duì)比上一步的0.804MB，占用空間又縮小了好多倍?。ㄟ@里參考的下面知乎鏈接中大佬的回答）

06 什么是缺頁(yè)中斷？

缺頁(yè)中斷就是要訪問(wèn)的頁(yè)不在主存中，需要操作系統(tǒng)將頁(yè)調(diào)入主存后再進(jìn)行訪問(wèn)，此時(shí)會(huì)暫時(shí)停止指令的執(zhí)行，產(chǎn)生一個(gè)頁(yè)不存在的異常，對(duì)應(yīng)的異常處理程序就會(huì)從選擇一頁(yè)調(diào)入到內(nèi)存，調(diào)入內(nèi)存后之前的異常指令就可以繼續(xù)執(zhí)行。

缺頁(yè)中斷的處理過(guò)程如下：

1. 如果內(nèi)存中有空閑的物理頁(yè)面，則分配一物理頁(yè)幀r，然后轉(zhuǎn)第4步，否則轉(zhuǎn)第2步；
2. 選擇某種頁(yè)面置換算法，選擇一個(gè)將被替換的物理頁(yè)幀r，它所對(duì)應(yīng)的邏輯頁(yè)為q，如果該頁(yè)在內(nèi)存期間被修改過(guò)，則需把它寫(xiě)回到外存；
3. 將q所對(duì)應(yīng)的頁(yè)表項(xiàng)進(jìn)行修改，把駐留位置0；
4. 將需要訪問(wèn)的頁(yè)p裝入到物理頁(yè)面r中；
5. 修改p所對(duì)應(yīng)的頁(yè)表項(xiàng)的內(nèi)容，把駐留位置1，把物理頁(yè)幀號(hào)置為x；
6. 重新運(yùn)行被中斷的指令。
   

07頁(yè)面置換算法都有哪些？

當(dāng)缺頁(yè)中斷發(fā)生時(shí)，需要調(diào)入新的頁(yè)面到內(nèi)存中，而內(nèi)存已滿時(shí)，選擇內(nèi)存中哪個(gè)物理頁(yè)面被置換是個(gè)學(xué)問(wèn)，由此引入了多種頁(yè)面置換算法，致力于盡可能減少頁(yè)面的換入換出次數(shù)（缺頁(yè)中斷次數(shù)）。盡量把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面換出，通常在程序局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)來(lái)進(jìn)行預(yù)測(cè)。

最優(yōu)頁(yè)面置換算法：當(dāng)一個(gè)缺頁(yè)中斷發(fā)生時(shí)，對(duì)于保存在內(nèi)存當(dāng)中的每一個(gè)邏輯頁(yè)面，計(jì)算在它的下一次訪問(wèn)之前，還需等待多長(zhǎng)時(shí)間，從中選擇等待時(shí)間最長(zhǎng)的那個(gè)，作為被置換的頁(yè)面。注意這只是一種理想情況，在實(shí)際系統(tǒng)中是無(wú)法實(shí)現(xiàn)的，因?yàn)椴僮飨到y(tǒng)不可能預(yù)測(cè)未來(lái)，不知道每一個(gè)頁(yè)面要等待多長(zhǎng)時(shí)間以后才會(huì)再次被訪問(wèn)。該算法可用作其它算法的性能評(píng)價(jià)的依據(jù)（在一個(gè)模擬器上運(yùn)行某個(gè)程序，并記錄每一次的頁(yè)面訪問(wèn)情況，在第二遍運(yùn)行時(shí)即可使用最優(yōu)算法）。

先進(jìn)先出算法：最先進(jìn)入的頁(yè)面最先被淘汰，這種算法很簡(jiǎn)單，就不過(guò)多介紹啦。

最近最久未使用算法：傳說(shuō)中的LUR算法，當(dāng)發(fā)生缺頁(yè)中斷時(shí)，選擇最近最久沒(méi)有使用過(guò)的頁(yè)面淘汰，該算法會(huì)給每個(gè)頁(yè)面一個(gè)字段，用于記錄自上次訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間T，當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，選擇已有頁(yè)面中T值最大的頁(yè)面進(jìn)行淘汰。

第二次機(jī)會(huì)頁(yè)面置換算法：先進(jìn)先出算法的升級(jí)版，只是在先進(jìn)先出算法的基礎(chǔ)上做了一點(diǎn)點(diǎn)改動(dòng)，因?yàn)橄冗M(jìn)先出算法可能會(huì)把經(jīng)常使用的頁(yè)面置換出去，該方法會(huì)給這些頁(yè)面多一次機(jī)會(huì)，給頁(yè)面設(shè)置一個(gè)修改位R，每次淘汰最老頁(yè)面時(shí)，檢查最老頁(yè)面的R位，如果R位是0，那么代表這個(gè)頁(yè)面又老又沒(méi)有被二次使用過(guò)，直接淘汰，如果這個(gè)頁(yè)面的R位是1，表示該頁(yè)面被二次訪問(wèn)過(guò)，將R位置0，并且把該頁(yè)面放到鏈表的尾端，像該頁(yè)面是最新進(jìn)來(lái)的一樣，然后繼續(xù)按這種方法淘汰最老的頁(yè)面。

時(shí)鐘頁(yè)面置換算法：第二次機(jī)會(huì)頁(yè)面算法的升級(jí)版，盡管二次機(jī)會(huì)頁(yè)面算法是比較合理的算法，但它需要在鏈表中經(jīng)常移動(dòng)頁(yè)面，效率比較低，時(shí)鐘頁(yè)面置換算法如圖，該算法把所有的頁(yè)面都保存在一個(gè)類似時(shí)鐘的環(huán)形鏈表中，一個(gè)表針指向最老的頁(yè)面，當(dāng)發(fā)生缺頁(yè)中斷時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的R位是0就淘汰該頁(yè)面，并且把新的頁(yè)面插入這個(gè)位置，然后表針移動(dòng)到下一個(gè)位置，如果R位是1就將R位置0并把表針移動(dòng)到下一個(gè)位置，重復(fù)這個(gè)過(guò)程直到找到一個(gè)R位是0的頁(yè)面然后淘汰。

時(shí)鐘頁(yè)面置換算法

最不常用算法：當(dāng)發(fā)生缺頁(yè)中斷時(shí)，選擇訪問(wèn)次數(shù)最少的那個(gè)頁(yè)面去淘汰。該算法可以給每個(gè)頁(yè)面設(shè)置一個(gè)計(jì)數(shù)器，被訪問(wèn)時(shí)，該頁(yè)面的訪問(wèn)計(jì)數(shù)器+1，在需要淘汰時(shí)，選擇計(jì)數(shù)器值最小的那個(gè)頁(yè)面。

這里有個(gè)問(wèn)題：一個(gè)頁(yè)面如果在開(kāi)始的時(shí)候訪問(wèn)次數(shù)很多，但之后就再也不用了，那它可能永遠(yuǎn)都不會(huì)淘汰，但它又確實(shí)需要被淘汰，怎么辦呢？可以定期把減少各個(gè)頁(yè)面計(jì)數(shù)器的值，常見(jiàn)的方法是定期將頁(yè)面計(jì)數(shù)器右移一位。

tips：最不常用算法（LFU）和最近最久未使用算法（LRU）的區(qū)別：LRU考察的是最久未訪問(wèn)，時(shí)間越短越好，而LFU考察的是訪問(wèn)的次數(shù)或頻度，訪問(wèn)次數(shù)越多越好。

工作集頁(yè)面置換算法

介紹該算法時(shí)首先介紹下什么是工作集。

工作集是指一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合，可以用二元函數(shù)W(t, s)表示：

t表示當(dāng)前的執(zhí)行時(shí)刻）s表示工作集窗口，表示一個(gè)固定的時(shí)間段

W(t, s)表示在當(dāng)前時(shí)刻t之前的s時(shí)間段中所有訪問(wèn)頁(yè)面所組成的集合

不同時(shí)間下的工作集會(huì)有所變化，如圖：

進(jìn)程開(kāi)始執(zhí)行后隨著訪問(wèn)新頁(yè)面逐步建立較穩(wěn)定的工作集

當(dāng)內(nèi)存訪問(wèn)的局部性區(qū)域的位置大致穩(wěn)定時(shí)(只訪問(wèn)那幾個(gè)頁(yè)面 沒(méi)有大的改變時(shí)) 工作集大小也大致穩(wěn)定

局部性區(qū)域的位置改變時(shí)(進(jìn)程前一項(xiàng)事情做完 去做下一項(xiàng)事情時(shí)) 工作集快速擴(kuò)張和快速收縮過(guò)渡到下一個(gè)穩(wěn)定值

工作集置換算法主要就是換出不在工作集中的頁(yè)面，示例如圖：

• 第0次訪問(wèn)e：缺頁(yè)，裝入e

• 第1次訪問(wèn)d：缺頁(yè)，裝入d

• 第2次訪問(wèn)a：缺頁(yè)，裝入a

• 第3次訪問(wèn)c：缺頁(yè)，裝入c

• 第4次訪問(wèn)c：命中，時(shí)間窗口【1-4】，淘汰e

• 第5次訪問(wèn)d：命中，時(shí)間窗口【2-5】

• 第6次訪問(wèn)b：缺頁(yè)，時(shí)間窗口【3-6】，淘汰a，裝入b

• 第7次訪問(wèn)c：命中，時(shí)間窗口【4-7】

• 第8次訪問(wèn)e：缺頁(yè)，時(shí)間窗口【5-8】，裝入e

• 第9次訪問(wèn)c：命中，時(shí)間窗口【6-9】，淘汰d，裝入c

• 第10次訪問(wèn)e：命中，時(shí)間窗口【7-10】，淘汰b

• 第11次訪問(wèn)a：缺頁(yè)，時(shí)間窗口【8-11】，裝入a

• 第12次訪問(wèn)d：缺頁(yè)，時(shí)間窗口【9-12】，裝入d

工作集時(shí)鐘頁(yè)面置換算法

在工作集頁(yè)面置換算法中，當(dāng)缺頁(yè)中斷發(fā)生后，需要掃描整個(gè)頁(yè)表才能直到頁(yè)面的狀態(tài)，進(jìn)而才能確定被淘汰的是哪個(gè)頁(yè)面，因此比較耗時(shí)，所以引入了工作集時(shí)鐘頁(yè)面算法。與時(shí)鐘算法改進(jìn)了先進(jìn)先出算法類似，工作集頁(yè)面置換算法+時(shí)鐘算法=工作集時(shí)鐘頁(yè)面置換算法。避免了每次缺頁(yè)中斷都需要掃描整個(gè)頁(yè)表的開(kāi)銷。

0 8 什么是分段內(nèi)存管理？

關(guān)于分段內(nèi)存管理我們平時(shí)見(jiàn)的最多的應(yīng)該就是Linux可執(zhí)行程序的代碼段數(shù)據(jù)段之類的啦，要了解分段最好的方式就是了解它的歷史。分段起源于8086CPU，那時(shí)候程序訪問(wèn)內(nèi)存還是直接給出相應(yīng)單元的物理地址，為了方便多道程序并發(fā)執(zhí)行，需要支持對(duì)各個(gè)程序進(jìn)行重定位，如果不支持重定位，涉及到內(nèi)存訪問(wèn)的地方都需要將地址寫(xiě)死，進(jìn)而把某個(gè)程序加載到物理內(nèi)存的固定區(qū)間。通過(guò)分段機(jī)制，程序中只需要使用段的相對(duì)地址，然后更改段的基址，就方便對(duì)程序進(jìn)行重定位。而且8086CPU的地址線寬度是20位，可尋址范圍可以達(dá)到1MB，但是它們的寄存器都是16位，直接使用1個(gè)16位寄存器不可能訪存達(dá)到1MB，因此引入了段，引入了段寄存器，段寄存器左移4位+偏移量就可以生成20位的地址，從而達(dá)到1MB的尋址范圍。

以如今的科技水平，其實(shí)已經(jīng)不再需要這種段移位加偏移的方式來(lái)訪存，分段更多的是一種歷史包袱，沒(méi)有多大實(shí)際作用，而且我們經(jīng)常見(jiàn)到的可執(zhí)行程序中代碼段數(shù)據(jù)段這些更多是為了在邏輯上能夠更清晰有序的構(gòu)造程序的組織結(jié)構(gòu)。Linux實(shí)際上沒(méi)有使用分段而只使用了分頁(yè)管理，這樣會(huì)更加簡(jiǎn)單，現(xiàn)在的分段其實(shí)更多是為了使邏輯更加清晰。一個(gè)公司，為了方便管理都會(huì)劃分為好多個(gè)部門(mén)，這其實(shí)和分段邏輯相似，沒(méi)有什么物理意義但是邏輯更加清晰。

關(guān)于操作系統(tǒng)的內(nèi)存知識(shí)點(diǎn)就介紹到這里，希望對(duì)大家有所幫助！

參考資料

https://www.zhihu.com/question/50796850

https://www.zhihu.com/question/63375062

https://yuerer.com/操作系統(tǒng)之-虛擬存儲(chǔ)頁(yè)面置換算法/

《現(xiàn)代操作系統(tǒng)》

《B站清華操作系統(tǒng)教學(xué)視頻》

《B站哈工大操作系統(tǒng)教學(xué)視頻》

------------ END ------------

推薦閱讀：

精選匯總 | 專欄 | 目錄 | 搜索

精選匯總 | ARM、Cortex-M

精選匯總?| ST工具、下載編程工具

關(guān)注 微信公眾號(hào)『嵌入式專欄』，底部菜單查看更多內(nèi)容，回復(fù)“加群”按規(guī)則加入技術(shù)交流群。