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

時間：2020-12-22 08:50:57

關(guān)鍵字：內(nèi)存嵌入式

手機看文章

掃描二維碼
隨時隨地手機看文章

[導(dǎo)讀]什么是物理內(nèi)存？使用物理內(nèi)存有什么缺點？什么是虛擬內(nèi)存？虛擬內(nèi)存如何映射到物理內(nèi)存？

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

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

什么是物理內(nèi)存
使用物理內(nèi)存有什么缺點？
什么是虛擬內(nèi)存？
虛擬內(nèi)存如何映射到物理內(nèi)存
什么是分頁內(nèi)存管理？
什么是缺頁中斷？
頁面置換算法都有哪些？
什么是分段內(nèi)存管理？

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

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

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

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

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

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

如何解決上述問題？

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

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

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

實現(xiàn)

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

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

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

方法一：如果是因為程序太大，大到超過了內(nèi)存的容量，可以采用手動覆蓋技術(shù)，只把需要的指令和數(shù)據(jù)保存在內(nèi)存中。

方法二：如果是因為程序太多，導(dǎo)致超過了內(nèi)存的容量，可以采用自動交換技術(shù)，把暫時不需要執(zhí)行的程序移動到外存中。

覆蓋技術(shù)

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

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

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

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

如圖：

交換技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體如圖：

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

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

頁框號：最主要的一項，頁表最主要的目的就是找到物理頁號；

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

保護位：表示一個頁允許什么類型的訪問，可讀可寫還是可執(zhí)行；

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

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

高速緩存禁止位：該位用于禁止該頁面被高速緩存。

如何加快地址映射速度？

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

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

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

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

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

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

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

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

32位的虛擬地址空間下：每個頁面4KB，且每條頁表項占4B：

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

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

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

每個進程都有4GB的虛擬地址空間，而顯然對于大多數(shù)程序來說，其使用到的空間遠未達到4GB，何必去映射不可能用到的空間呢？

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

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

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

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

06 什么是缺頁中斷？

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

缺頁中斷的處理過程如下：

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

07頁面置換算法都有哪些？

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

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

先進先出算法：最先進入的頁面最先被淘汰，這種算法很簡單，就不過多介紹啦。

最近最久未使用算法：傳說中的LUR算法，當發(fā)生缺頁中斷時，選擇最近最久沒有使用過的頁面淘汰，該算法會給每個頁面一個字段，用于記錄自上次訪問以來所經(jīng)歷的時間T，當需要淘汰一個頁面時，選擇已有頁面中T值最大的頁面進行淘汰。

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

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

時鐘頁面置換算法

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

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

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

工作集頁面置換算法

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

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

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

W(t, s)表示在當前時刻t之前的s時間段中所有訪問頁面所組成的集合

不同時間下的工作集會有所變化，如圖：

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

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

局部性區(qū)域的位置改變時(進程前一項事情做完去做下一項事情時) 工作集快速擴張和快速收縮過渡到下一個穩(wěn)定值

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

第0次訪問e：缺頁，裝入e
第1次訪問d：缺頁，裝入d
第2次訪問a：缺頁，裝入a
第3次訪問c：缺頁，裝入c
第4次訪問c：命中，時間窗口【1-4】，淘汰e
第5次訪問d：命中，時間窗口【2-5】
第6次訪問b：缺頁，時間窗口【3-6】，淘汰a，裝入b
第7次訪問c：命中，時間窗口【4-7】
第8次訪問e：缺頁，時間窗口【5-8】，裝入e
第9次訪問c：命中，時間窗口【6-9】，淘汰d，裝入c
第10次訪問e：命中，時間窗口【7-10】，淘汰b
第11次訪問a：缺頁，時間窗口【8-11】，裝入a
第12次訪問d：缺頁，時間窗口【9-12】，裝入d

工作集時鐘頁面置換算法

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

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

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

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

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

參考資料

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

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

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

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

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

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