存儲器的層次結(jié)構(gòu)‘

多層結(jié)構(gòu)的存儲器系統(tǒng)

存儲器的多層結(jié)構(gòu)兜粘。

存儲層次至少應(yīng)具有三級：最高層為 CPU 寄存器界赔，中間為主存蜕乡，最底層是輔存锅铅。還可以根據(jù)具體的功能分工細劃為寄存器、高速緩存羞迷、主存儲器界轩、磁盤緩存、固定磁盤衔瓮、可移動存儲介質(zhì)等 6 層浊猾。在存儲層次中越往上，存儲介質(zhì)的訪問速度越快热鞍，價格也越高葫慎，相對存儲容量也越小衔彻。

寄存器、高速緩存偷办、主存儲器和磁盤緩存均屬于操作系統(tǒng)存儲管理的管轄范疇艰额，掉電后它們存儲的信息不再存在。固定磁盤和可移動存儲介質(zhì)屬于設(shè)備管理的管轄范疇椒涯，它們存儲的信息將被長期保存柄沮。

可執(zhí)行存儲器。

寄存器和主存儲器又被稱為可執(zhí)行存儲器废岂。

主存儲器與寄存器

主存儲器祖搓。

主存儲器簡稱內(nèi)存或主存。由于主存儲器的訪問速度遠低于 CPU 執(zhí)行指令的速度湖苞，為緩和這一矛盾拯欧，在計算機系統(tǒng)中引入了寄存器和高速緩存。

寄存器财骨。

寄存器具有與處理機相同的速度镐作。主要用于存放處理機運行時的數(shù)據(jù)。如用寄存器存放操作數(shù)蚓再，或用作地址寄存器加快地址轉(zhuǎn)換速度等滑肉。

高速緩存和磁盤緩存

高速緩存。

高速緩存是介于寄存器和存儲器之間的存儲器摘仅，主要用于備份主存中較常用的數(shù)據(jù)靶庙。其容量遠大于寄存器，而比內(nèi)存約小兩到三個數(shù)量級左右娃属。

根據(jù)程序執(zhí)行的局部性原理(即程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律六荒，在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分)矾端，將主存中一些經(jīng)常訪問的信息存放在高速緩存中掏击。當 CPU 訪問一組特定信息時，首先檢查它是否在高速緩存中秩铆，在則直接取出使用砚亭，否則再從主存中讀取。

磁盤緩存殴玛。

由于目前磁盤的 I/O 速度遠低于對主存的訪問速度捅膘，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中滚粟，可減少訪問磁盤的次數(shù)寻仗。但磁盤緩存與高速緩存不同，它本身并不是一種實際存在的存儲介質(zhì)凡壤，而是利用主存中的部分存儲空間暫存從磁盤中讀出(或?qū)懭?的信息署尤。

程序的裝入和鏈接

用戶程序要在系統(tǒng)中運行耙替，必須先將它裝入內(nèi)存，然后再將其轉(zhuǎn)變?yōu)橐粋€可以執(zhí)行的程序曹体，通常都要經(jīng)過以下幾個步驟：

1）編譯俗扇，由編譯程序?qū)⒂脩粼创a編譯成若干個目標模塊。

2）鏈接混坞，由鏈接程序?qū)⒕幾g后形成的一組目標模塊狐援，以及它們所需要的庫函數(shù)鏈接在一起钢坦，形成一個完整的裝入模塊究孕。

3）裝入，由裝入程序?qū)⒀b入模塊裝入內(nèi)存爹凹。

程序的裝入

絕對裝入方式厨诸。

僅能運行單道程序時可以采用該種方式。裝入模塊被裝入內(nèi)存后禾酱，程序中的邏輯地址與實際內(nèi)存地址完全相同微酬。

可重定位裝入方式。

采用可重定位裝入方式颤陶，根據(jù)內(nèi)存的當前情況颗管，將裝入模塊裝入到內(nèi)存的適當位置。值得注意的是滓走，在采用可重定位裝入程序?qū)⒀b入模塊裝入內(nèi)存后垦江，會使裝入模塊中的所有邏輯地址與實際裝入內(nèi)存的物理地址不同。通常是把在裝入時對目標程序中指令和數(shù)據(jù)地址的修改過程稱為重定位搅方。又因為地址變換通常是在裝入時一次完成的比吭，以后不再改變，故稱為靜態(tài)重定位姨涡。

動態(tài)運行時裝入方式衩藤。

動態(tài)運行時的裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址涛漂，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行赏表。因此，裝入內(nèi)存后的所有地址都仍是相對地址匈仗。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度瓢剿，這種方式需要一個重定位寄存器的支持。

程序的鏈接

靜態(tài)鏈接方式锚沸。

在程序運行之前跋选，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊哗蜈，以后不再拆開前标。在將這幾個目標模塊裝配成一個裝入模塊時坠韩，須解決以下兩個問題：

1）對相對地址進行修改。這是因為在由編譯程序所產(chǎn)生的所有目標模塊中炼列，使用的都是相對地址只搁，其起始地址都為 0，每個模塊中的地址都是相對于起始地址計算的俭尖。

2）變換外部調(diào)用符號氢惋。將每個模塊中所用的外部調(diào)用符號也都變換為相對地址。

這種先進行鏈接所形成的一個完整的裝入模塊稽犁，又稱為可執(zhí)行文件焰望。

裝入時動態(tài)鏈接。

指用戶源程序經(jīng)編譯后所得的目標模塊已亥，在裝入內(nèi)存時采用邊裝入邊鏈接的鏈接方式熊赖。這樣便于裝入前修改和更新，以及實現(xiàn)對目標模塊的共享虑椎。

運行時動態(tài)鏈接震鹉。

將對某些模塊的鏈接推遲到程序執(zhí)行時才進行鏈接，亦即捆姜，在執(zhí)行過程中传趾，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由 OS 去找到該模塊并將之裝入內(nèi)存泥技，把它鏈接到調(diào)用者模塊上浆兰。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上零抬，這樣不僅可加快程序的裝入過程镊讼，而且可節(jié)省大量的內(nèi)存空間。

連續(xù)分配存儲管理方式

為了能將用戶程序裝入內(nèi)存平夜，必須為它分配一定大小的內(nèi)存空間蝶棋。

單一連續(xù)分配

只能用于單道程序環(huán)境下，整個內(nèi)存的用戶空間由一個程序獨占忽妒。

固定分區(qū)分配

將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域玩裙，在每個分區(qū)中只裝入一道作業(yè)。

劃分分區(qū)的方法段直。

分區(qū)大小相等吃溅、分區(qū)大小不等。

內(nèi)存分配鸯檬。

通常將分區(qū)按大小進行排隊决侈，并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址喧务、大小及狀態(tài)(是否已分配)赖歌。當有一用戶程序要裝入時枉圃，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的庐冯、尚未分配的分區(qū)孽亲，將之分配給該程序，然后將該表項中的狀態(tài)置為“已分配”展父。

動態(tài)分區(qū)分配

又稱可變分區(qū)分配返劲。

動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)。

常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：

空閑分區(qū)表栖茉，表目：分區(qū)號篮绿、分區(qū)大小、分區(qū)始址衡载、狀態(tài)搔耕。

空閑分區(qū)鏈隙袁，在每個分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息痰娱，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針菩收，以及前后都重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目梨睁。通過前、后向鏈接指針娜饵，可將所有的空閑分區(qū)鏈接成一個雙向鏈坡贺。

動態(tài)分區(qū)分配算法。

順序式搜索算法箱舞、索引式搜索算法遍坟。

分區(qū)分配操作。

1）分配內(nèi)存：

系統(tǒng)應(yīng)利用某種分配算法晴股，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)愿伴。設(shè)請求的分區(qū)大小為 u.size，表中每個空閑分區(qū)的大小可表示為 m.size电湘。若 m.size-u.size≤size(size 是事先規(guī)定的不再切割的剩余分區(qū)的大小)隔节，說明多余部分太小，可不再切割寂呛，將整個分區(qū)分配給請求者怎诫；否則(即多余部分超過 size)，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去贷痪，余下的部分仍留在空閑分區(qū)鏈(表)中幻妓。然后，將分配區(qū)的首址返回給調(diào)用者劫拢。

2）回收內(nèi)存：

當進程運行完畢釋放內(nèi)存時肉津，系統(tǒng)根據(jù)回收區(qū)的首址胖缤，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四種情況之一：

①回收區(qū)與插入點的前一個空閑分區(qū)相鄰接阀圾，此時應(yīng)將回收區(qū)與插入點的前一分區(qū)合并哪廓。

②回收分區(qū)與插入點的后一空閑分區(qū)相鄰接，此時也可將兩分區(qū)合并初烘。

③回收區(qū)同時與插入點的前涡真、后兩個分區(qū)鄰接，此時將三個分區(qū)合并肾筐。

④回收區(qū)既不與前一個鄰接哆料，又不與后一個鄰接，這時應(yīng)為回收區(qū)單獨建立一新表項吗铐，填寫回收區(qū)的首址和大小东亦，并根據(jù)其首址插入到空閑鏈中的適當位置。

基于順序搜索的動態(tài)分區(qū)分配算法

順序搜索唬渗，是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)典阵，去尋找一個其大小能滿足要求的分區(qū)。

碎片：內(nèi)存空間不斷被劃分镊逝，會留下許多難以利用的壮啊、很小的空閑分區(qū)。

首次適應(yīng)算法撑蒜。

要求空閑分區(qū)鏈以地址遞增的次序鏈接歹啼。在分配內(nèi)存時，從鏈首開始順序查找座菠，直至找到一個大小能滿足要求的空閑分區(qū)為止狸眼，缺點是低址部分會不斷被劃分，形成碎片浴滴。

循環(huán)首次適應(yīng)算法拓萌。

在為進程分配內(nèi)存空間時，不再是每次都從鏈首開始查找巡莹，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找司志。實現(xiàn)可通過設(shè)置一起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)降宅，并采用循環(huán)查找方式骂远。缺點缺乏大的空閑分區(qū)。

最佳適應(yīng)算法腰根。

總是把能滿足要求激才、又是最小的空閑分區(qū)分配給作業(yè)，為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈瘸恼。缺點產(chǎn)生許多碎片劣挫。

最壞適應(yīng)算法。

在掃描整個空閑分區(qū)表或鏈表時东帅，總是挑選一個最大的空閑區(qū)压固，分割一部分空間給作業(yè)使用。要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈靠闭，查找時只要看第一個分區(qū)能否滿足作業(yè)要求即可帐我。缺點缺乏大的空閑分區(qū)。

基于索引搜索的動態(tài)分區(qū)分配算法

快速適應(yīng)算法愧膀。

又稱為分類搜索法拦键。是將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)檩淋，單獨設(shè)立一個空閑分區(qū)鏈表芬为，同時在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一種空閑分區(qū)類型蟀悦，并記錄了該類型空閑分區(qū)鏈表表頭的指針媚朦。

該算法僅需要根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表熬芜，并取下第一塊進行分配即可莲镣。在分配過程中，不會對任何分區(qū)產(chǎn)生分割涎拉。

伙伴系統(tǒng)。

規(guī)定的圆，無論已分配分區(qū)或空閑分區(qū)鼓拧，其大小均為 2 的 k 次冪（k 為整數(shù)，l≤k≤m）越妈。通常 2^m是整個可分配內(nèi)存的大小季俩。

對于每一類具有相同大小的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)雙向鏈表梅掠。

當需要為進程分配一個長度為 n 的存儲空間時酌住，首先計算一個 i 值，使 2^(i-1) < n ≤ 2^i阎抒，然后在空閑分區(qū)大小為 2^i 的空閑分區(qū)鏈表中查找酪我。若找到則直接分配。否則且叁，則在分區(qū)大小為 2^(i+1) 的空閑分區(qū)鏈表中尋找都哭。若存在 2^(i+1) 的一個空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴欺矫，其中的一個分區(qū)用于分配纱新，而把另一個加入分區(qū)大小為 2^i 的空閑分區(qū)鏈表中。若仍然找不到穆趴，依次類推去尋找更高1次冪的分區(qū)脸爱。

與一次分配可能要進行多次分割一樣，一次回收也可能要進行多次合并未妹，如回收大小為 2^i的空閑分區(qū)時阅羹，若事先已存在回收塊所對應(yīng)的2^i伙伴塊的空閑分區(qū)時，則應(yīng)將其與伙伴分區(qū)合并為大小為2^(i+1)的空閑分區(qū)教寂，若事先已存在新合并空閑塊對應(yīng)的2^(i+1)伙伴塊的空閑分區(qū)時捏鱼，依次類推合并。

對于一個大小為2^k酪耕，地址為x的內(nèi)存塊导梆，其伙伴塊的地址則用buddy k (x)表示，其通式為：

if(x MOD 2^(k+1) == 0) {

buddy k (x) = x + 2^k;

}

else if(x MOD 2^(k+1) == 2^k) {

buddy k (x) = x - 2^k;

}

哈希算法迂烁。

構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表看尼，該表的每一個表項記錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針。

動態(tài)可重定位分區(qū)分配

緊湊盟步。

在連續(xù)分配方式中藏斩，必須把一個系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。當一臺計算機運行了一段時間后却盘，它的內(nèi)存空間將會被分割成許多小的分區(qū)狰域，而缺乏大的空閑分區(qū)。

通過移動內(nèi)存中作業(yè)的位置黄橘，以把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法兆览，稱為“拼接”或“緊湊”。由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化塞关。為此抬探，在每次“緊湊”后，都必須對移動了的程序或數(shù)據(jù)進行重定位帆赢。

動態(tài)重定位小压。

在動態(tài)運行時裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址都仍然是相對(邏輯)地址椰于，將相對地址轉(zhuǎn)換為物理地址的工作怠益，被推遲到程序指令要真正執(zhí)行時進行。

地址變換過程是在程序執(zhí)行期間廉羔，隨著對每條指令或數(shù)據(jù)的訪問借助重定位寄存器自動進行的溉痢，故稱為動態(tài)重定位僻造。當系統(tǒng)對內(nèi)存進行了“緊湊”而使若干程序從內(nèi)存的某處移至另一處時，不需對程序做任何修改孩饼，只要用該程序在內(nèi)存的新起始地址髓削，去置換原來的起始地址即可。

動態(tài)重定位分區(qū)分配算法镀娶。

動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同立膛，差別僅在于：在這種分配算法中，增加了緊湊的功能梯码。

對換

多道程序環(huán)境下的對換技術(shù)

對換的引入宝泵。

所謂“對換”，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)調(diào)出到外存上轩娶，以便騰出足夠的內(nèi)存空間俊柔，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存题篷。

對換的類型捉捅。

1）整體對換撒蟀。

處理機中級調(diào)度實際上就是存儲器的對換功能。其目的用于解決內(nèi)存緊張問題许溅。由于中級調(diào)度是以進程為單位的瓤鼻，故又稱之為“進程對換”或“整體對換”。

2）頁面(分段)對換贤重。

以進程的一個“頁面”或“分段”為單位進行的茬祷，分別稱為“頁面對換”、“分段對換”并蝗，又統(tǒng)稱為“部分對換”祭犯。

在此，我們只介紹進程對換借卧，而分頁或分段對換將放在虛擬存儲器中介紹盹憎。

對換空間的管理

對對換空間管理的主要目標。

在具有對換功能的 OS 中铐刘，通常把外存分為文件區(qū)和對換區(qū)。

1）對文件區(qū)管理的主要目標影晓。

是提高文件存儲空間的利用率镰吵，為此，對文件區(qū)采取離散分配方式挂签。

2）對對換區(qū)管理的主要目標疤祭。

對換操作較頻繁。故是提高進程換入和換出的速度饵婆。為此勺馆，采取的是連續(xù)分配方式，較少考慮外存中的碎片問題。

對換空間空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)草穆。

與動態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)相似灌灾，即空閑分區(qū)表或空閑分區(qū)鏈。在每個表目中包含兩項：對換區(qū)的首址及其大小悲柱，分表用盤塊號和盤塊數(shù)表示锋喜。

對換空間的分配與回收。

與動態(tài)分區(qū)分配方式中內(nèi)存分配與回收方法雷同豌鸡。

進程的換出與換入

進程的換出嘿般。

換出過程：

1）選擇被換出的進程。首先選擇處于阻塞或睡眠狀態(tài)的進程涯冠，如果有多個炉奴，則選擇優(yōu)先級最低的進程。在有的系統(tǒng)除了考慮優(yōu)先級蛇更，還需考慮進程在內(nèi)存的駐留時間瞻赶。如果系統(tǒng)中已無阻塞進程且內(nèi)存仍不足時，則選擇優(yōu)先級最低的就緒進程換出械荷。

2）進程換出過程共耍。只能換出非共享的程序和數(shù)據(jù)段，對于共享的只要還有進程需要吨瞎，就不能換出痹兜。在進行換出時，①需要申請對換空間颤诀。②若申請成功字旭，就啟動磁盤，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上崖叫。③若傳送成功遗淳，便可回收該進程所占的內(nèi)存空間，并對該進程的PCB和內(nèi)存分配表等進行相應(yīng)的修改心傀，若還有可換出進程屈暗，則繼續(xù)換出，直至內(nèi)存中再無阻塞進程為止脂男。

進程的換入养叛。

定時執(zhí)行換入操作。找出“就緒”狀態(tài)但已換出的進程宰翅，將其中換出時間最久的進程作為換入進程弃甥，為它申請內(nèi)存。若申請成功則調(diào)入汁讼，若失敗則需先將內(nèi)存中的某些進程換出淆攻，再將進程換入阔墩。直到外存中再無“就緒且換出”狀態(tài)的進程為止，或者已無足夠的內(nèi)存來換入進程時瓶珊，對換進程停止換入啸箫。

基本分頁存儲管理方式

比較連續(xù)分配方式：

作業(yè)邏輯地址空間有M大，就需要向內(nèi)存申請一個M大的連續(xù)區(qū)域艰毒。

分頁的目的是更細粒度的處理空間筐高，減少粗放管理的浪費或開銷問題。

離散分配內(nèi)存：

作業(yè)規(guī)定大小劃分成小份丑瞧；內(nèi)存也按同樣大小劃分成小份

作業(yè)的任一小份可分散放入內(nèi)存任意未使用的小份

分頁方式下柑土，內(nèi)存的使用率高，浪費少绊汹。但不是絕對沒有碎片（進程的最后一頁不總是能占滿一個物理塊）

1）頁面的概念

內(nèi)存劃分成多個小單元稽屏，每個單元K大小，稱（物理）塊西乖。作業(yè)也按K單位大小劃分成片狐榔，稱為頁面。

① 物理劃分塊的大小 = 邏輯劃分的頁的大小

②頁面大小要適中获雕。

太大薄腻，（最后一頁）內(nèi)碎片增大，類似連續(xù)分配的問題届案。 ?

太小的話庵楷，頁面碎片總空間雖然小，提高了利用率楣颠，但每個進程的頁面數(shù)量較多尽纽，頁表過長，反而又增加了空間使用童漩。

2）頁表的概念

為了找到被離散分配到內(nèi)存中的作業(yè)弄贿，記錄每個作業(yè)各頁映射到哪個物理塊，形成的頁面映射表矫膨，簡稱頁表差凹。

每個作業(yè)有自己的頁表

頁表的作用：

?? ??? ?頁號到物理塊號的地址映射

要找到作業(yè)A

?? ??關(guān)鍵是找到頁表（PCB）

?? ??根據(jù)頁表找物理塊

若內(nèi)存和作業(yè)均按1K大小劃分塊或頁，一個4K大的作業(yè)可如下圖般分配：

①離散分配過程：

找空---空閑空間管理

放入---裝入與地址映射 （形成頁表）

記錄---頁表地址記入pcb

②如何運行一個作業(yè)?

連續(xù)方式下

? PCB記錄內(nèi)存首地址侧馅，根據(jù)該地址順序取指令執(zhí)行即可直奋。

離散方式下

? 頁表記錄作業(yè)的各頁分別占用了內(nèi)存的哪些塊； ?pcb則記錄頁表在內(nèi)存的地址——進程構(gòu)造時伴隨著構(gòu)造頁表施禾，該核心信息也要放在內(nèi)存中供訪問；

3）地址的處理

地址映射（地址計算）的過程：

若要執(zhí)行某作業(yè)的一條指令搁胆，其相對地址是24B （設(shè)10B一頁弥搞，頁表如右表）邮绿，其物理地址到底是多少呢？

分析其所在的頁和偏移得：2號頁（頁號從0開始） 攀例，偏移4B處是該條指令

查頁表找頁面對應(yīng)的塊（2號頁保存在6號物理塊）

找物理塊6船逮，向下偏移4B，找到要執(zhí)行的指令粤铭。取出執(zhí)行即可挖胃。

計算上就是求商（頁號）及取余（偏移量）的過程

任意一條指令的相對地址如何知道是第幾頁的第幾條指令？

邏輯地址空間分析 ?

設(shè)一分頁系統(tǒng)梆惯，頁面大小為8B（設(shè)8條指令） ?一個大小為 32B 的作業(yè)分配內(nèi)存

規(guī)律

作業(yè)相對地址在分頁下不同位置的數(shù)有一定的意義結(jié)構(gòu)：

?? ??? ??? ?頁號+頁內(nèi)地址（即頁內(nèi)偏移）

關(guān)鍵的計算是：根據(jù)系統(tǒng)頁面大小找到不同意義二進制位的分界線酱鸭。

從地址中分析出頁號后，地址映射只需要把頁號改為對應(yīng)物理塊號垛吗，偏移不變凹髓，即可找到內(nèi)存中實際位置。

注意：一作業(yè)所有指令在用戶地址空間是順序編址

計算口訣 ? ? ? ? ? ??

頁面大小決定偏移量（頁內(nèi)地址）的位數(shù) n怯屉；

作業(yè)大小?頁面數(shù)量

? ? ? ?頁表長度 a

? ? ? ?頁號的位數(shù) m（或總位數(shù)-頁內(nèi)位數(shù)）

內(nèi)存容量決定塊數(shù)蔚舀，塊數(shù)決定編址位數(shù)，即頁表項位數(shù) b锨络。

4）地址變換機構(gòu)

圍繞頁表進行工作赌躺，那么頁表數(shù)據(jù)放在哪？

寄存器羡儿。一個進程有n個頁礼患，頁表就需要記錄n項數(shù)據(jù)，需要n個寄存器失受。不現(xiàn)實讶泰。

內(nèi)存。只設(shè)置一個頁表寄存器PTR（page table register）記錄頁表在內(nèi)存中的首地址和頁表長度拂到，運行時快速定位頁表痪署。

地址變換過程：

分頁系統(tǒng)中，進程創(chuàng)建兄旬，放入內(nèi)存狼犯，構(gòu)建頁表，在PCB中記錄頁表存放在內(nèi)存的首地址及頁表長度领铐。

1.運行某進程A時悯森，將A進程PCB中的頁表信息寫入PTR中；

2.每執(zhí)行一條指令時绪撵，根據(jù)分頁計算原理瓢姻，得到指令頁號X和內(nèi)部偏移量Y；

3.CPU高速訪問PTR找到頁表在哪里音诈；

? ? ? 為防止錯誤檢索幻碱，增加預(yù)先的判斷： ?計算得到的頁號是否大于頁表長度（即頁表項數(shù)） ?一個5頁的進程绎狭，頁面編號0-4，若地址計算出的頁號不在該范圍褥傍，一定產(chǎn)生了越界錯誤儡嘶。

4.查頁表數(shù)據(jù)，得到X實際對應(yīng)存放的物理塊恍风，完成地址映射計算蹦狂，最終在內(nèi)存找到該指令。

5）引入快表——針對訪問速度問題

問題：基本分頁機制下朋贬，一次指令需兩次內(nèi)存訪問凯楔，處理機速度降低1/2，分頁空間效率的提高以如此的速度為代價兄世，得不償失啼辣。

改進：減少第1步訪問內(nèi)存的時間。增設(shè)一個具有“并行查詢”能力的高速緩沖寄存器御滩，稱為“快表”鸥拧，也稱“聯(lián)想寄存器”（Associative memory），IBM系統(tǒng)稱為TLB（Translation Look aside Buffer）削解。

快表放什么富弦？： 正在執(zhí)行進程的頁表的數(shù)據(jù)項。

快表的寄存器單元數(shù)量是有限的氛驮，不能裝下一個進程的所有頁表項腕柜。雖不能完全避免兩次訪問內(nèi)存，但如果命中率a高還是能大幅度提高速度矫废。

設(shè)一次查找訪問快表時間為t' 盏缤，則 ?

EAT= a*t' + (1-a)(t'+t) ? ?+ ? ?t

?? ??? = 2t +t' -t*a

6）兩級、多級頁表蓖扑，反置頁表 ——針對大頁表占用內(nèi)存問題

?進程分頁離散存放唉铜，但頁表的數(shù)據(jù)是連續(xù)在存放內(nèi)存的。而頁表可能很大：

?? ??? ?現(xiàn)代操作系統(tǒng)支持非常大的邏輯地址空間的進程律杠。如32位系統(tǒng)潭流，可編址的最大代碼數(shù)為232，若頁面大小為4KB（4*210）柜去，則支持的最大進程頁表項數(shù)可達碼232/212=220灰嫉，有1M個，每個頁表項占1B（字節(jié)）嗓奢，則頁表大小就有1MB讼撒。

兩級頁表

將頁表分頁，并離散地將頁表的各個頁面分別存放在不同的物理塊中

為離散分配的頁表再建立一張頁表，稱為“外層頁表”椿肩，其每個表項記錄了頁表頁面所在的物理塊號瞻颂。

分段存儲管理方式

請求分段式的虛擬存儲器系統(tǒng)是基于分段基礎(chǔ)的，自然也具有分段管理系統(tǒng)的好處郑象；同時，同請求分頁管理方式一樣茬末，也需要擴展頁表項的字段厂榛，增加狀態(tài)位、修改位丽惭、存取方式击奶、訪問字段、外存地址和增補位责掏；最后一個字段是分段系統(tǒng)獨有的柜砾，用來標記該段是否發(fā)生過動態(tài)增長；

分段系統(tǒng)的特點就是便于信息的保護和共享换衬；而分段保護中包括越界檢查痰驱、存取控制檢查和環(huán)保護機構(gòu)；環(huán)保護機制是一種比較完善的保護機制瞳浦，在該機制中規(guī)定：低編號的環(huán)具有較高的優(yōu)先級担映。OS內(nèi)核處于0號環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務(wù)處于中間環(huán)叫潦；而一般程序則被安排到外環(huán)上蝇完；在環(huán)系統(tǒng)中，程序的訪問和調(diào)用遵守以下規(guī)則：一個程序只可以訪問駐留在相同環(huán)或者較低特權(quán)環(huán)（外環(huán)）中的數(shù)據(jù)和服務(wù)矗蕊；

至于地址轉(zhuǎn)換短蜕、內(nèi)存空間的分配和回收等與分段系統(tǒng)基本類似（增加了分段置換功能以實現(xiàn)虛擬存儲的需求），詳見存儲器管理之分段存儲管理方式傻咖；