[[355925]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序喵大人」，作者程序喵大人 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序喵大人公眾號(hào)。

目錄

• 1. 什么是物理內(nèi)存
• 2. 使用物理內(nèi)存有什么缺點(diǎn)?
• 3. 什么是虛擬內(nèi)存?
• 4. 虛擬內(nèi)存如何映射到物理內(nèi)存
• 5. 什么是分頁內(nèi)存管理?
• 6. 什么是缺頁中斷?
• 7. 頁面置換算法都有哪些?
• 8. 什么是分段內(nèi)存管理?

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

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

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

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

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

2.系統(tǒng)有多個(gè)進(jìn)程同時(shí)在運(yùn)行：如圖，理想情況下可以使進(jìn)程A和進(jìn)程B各占物理內(nè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è)程序在某一地址空間寫入某個(gè)值，第二個(gè)程序在同一地址又寫入了不同值，這就會(huì)導(dǎo)致程序運(yùn)行出現(xiàn)問題，所以直接使用物理內(nèi)存會(huì)使所有進(jì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，如果訪問的地址超過的界限，需要產(chǎn)生錯(cuò)誤并中止訪問。為了達(dá)到目的CPU配置了兩個(gè)特殊硬件寄存器：基址寄存器和界限寄存器，當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)，程序的起始物理地址和長(zhǎng)度會(huì)分別裝入到基址寄存器和界限寄存器里，進(jìn)程訪問內(nèi)存，在每個(gè)內(nèi)存地址送到內(nèi)存之前，都會(huì)先加上基址寄存器的內(nèi)容。

缺點(diǎn)：每次訪問內(nèi)存都需要進(jìn)行加法和比較運(yùn)算，比較運(yùn)算很快，但是加法運(yùn)算由于進(jìn)位傳遞事件的問題，在沒有使用特殊電路的情況下會(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)槌绦蛱?，大到超過了內(nèi)存的容量，可以采用手動(dòng)覆蓋技術(shù)，只把需要的指令和數(shù)據(jù)保存在內(nèi)存中。

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

覆蓋技術(shù)

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

• 將常用功能需要的代碼和數(shù)據(jù)常駐在內(nèi)存中;
• 將不常用的功能劃分成功能相互獨(dú)立的程序模塊，平時(shí)放到外存中，在需要的時(shí)候?qū)?duì)應(yīng)的模塊加載到內(nè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ā)生在那些相互之間沒有調(diào)用關(guān)系的程序模塊之間，因此程序員必須給出程序內(nèi)的各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。
• 交換技術(shù)是以在內(nèi)存中的程序大小為單位來進(jìn)行的，它不需要程序員給出各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。

通俗來說：覆蓋發(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)換出，增加了處理器的開銷，還需要足夠大的外存。

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

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

虛擬內(nè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è)過程由操作系統(tǒng)自動(dòng)來完成，無需程序員的干涉;

虛擬內(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ù)一般是在頁式管理(下面介紹)的基礎(chǔ)上實(shí)現(xiàn)

• 在裝入程序時(shí)，不必將其全部裝入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的部分頁面裝入到內(nèi)存，就可讓程序開始執(zhí)行;
• 在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存(稱為缺頁)。則由處理器通知操作系統(tǒng)將相應(yīng)的頁面調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序;
• 另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁面調(diào)出保存在外存上，從而騰出更多空閑空間存放將要裝入的程序以及將要調(diào)入的頁面。

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

• 大的用戶空間：通過把物理內(nèi)存與外存相結(jié)合，提供給用戶的虛擬內(nèi)存空間通常大于實(shí)際的物理內(nèi)存，即實(shí)現(xiàn)了兩者的分離。如32位的虛擬地址理論上可以訪問4GB，而可能計(jì)算機(jī)上僅有256M的物理內(nèi)存，但硬盤容量大于4GB;
• 部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的;
• 連續(xù)性：程序可以使用一系列相鄰連續(xù)的虛擬地址來映射物理內(nèi)存中不連續(xù)的大內(nèi)存緩沖區(qū);
• 安全性：不同進(jìn)程使用的虛擬地址彼此隔離。一個(gè)進(jìn)程中的代碼無法更改正在由另一進(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來把虛擬地址映射到物理地址，程序只需要管理虛擬內(nèi)存就好，映射的邏輯自然有其它模塊自動(dòng)處理。

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

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

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

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

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

具體如圖：

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

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

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

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

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

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

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

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

如何加快地址映射速度?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

06 什么是缺頁中斷?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

工作集頁面置換算法

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

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

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

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

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

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

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

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

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

第0次訪問e：缺頁，裝入e

第1次訪問d：缺頁，裝入d

第2次訪問a：缺頁，裝入a

第3次訪問c：缺頁，裝入c

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

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

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

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

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

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

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

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

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

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

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

08什么是分段內(nèi)存管理?

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

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

關(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ǔ)頁面置換算法/

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

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

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