2.1 主存儲(chǔ)器

　　主存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)中的一個(gè)主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，CPU的控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)秕磷，數(shù)據(jù)能夠從主存儲(chǔ)器中讀取并將他們裝入到寄存器中齐苛，或者從寄存器存入到主存儲(chǔ)器引镊，CPU與外圍設(shè)備交換的信息一般也依托于主存儲(chǔ)器地址空間。但是指厌，主存儲(chǔ)器的訪問(wèn)速度遠(yuǎn)低于CPU執(zhí)行指令的速度刊愚，于是引入了寄存機(jī)和告訴緩沖。

　　2.2寄存器

　　寄存器訪問(wèn)速度最快踩验，能與CPU協(xié)調(diào)工作鸥诽，價(jià)格昂貴商玫，容量不大，寄存器用于加速存儲(chǔ)器的訪問(wèn)速度牡借，如用寄存器存放操作數(shù)拳昌，或用作地址寄存器加快地址轉(zhuǎn)換速度等。

　　2.3高速緩存

　　高速緩存容量大于或遠(yuǎn)大于寄存器钠龙，但小于內(nèi)存炬藤，訪問(wèn)速度高于主內(nèi)存器，根據(jù)程序局部性原理碴里，將主存中一些經(jīng)常訪問(wèn)的信息存放在高速緩存中沈矿，減少訪問(wèn)主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度咬腋。通常羹膳，進(jìn)程的程序和數(shù)據(jù)存放在主存，每當(dāng)使用時(shí)根竿，被臨時(shí)復(fù)制到高速緩存中陵像，當(dāng)CPU訪問(wèn)一組特定信息時(shí)，首先檢查它是否在高速緩存中犀填，如果已存在蠢壹，則直接取出使用，否則九巡，從主存中讀取信息图贸。有的計(jì)算機(jī)系統(tǒng)設(shè)置了兩級(jí)或多級(jí)高速緩存，一級(jí)緩存速度最高冕广，容量小疏日，二級(jí)緩存容量稍大，速度稍慢撒汉。

　　2.4磁盤(pán)緩存

　　磁盤(pán)的IO速度遠(yuǎn)低于對(duì)主存的訪問(wèn)速度沟优，因此將頻繁使用的一部分磁盤(pán)數(shù)據(jù)和信息暫時(shí)存放在磁盤(pán)緩存中，可減少訪問(wèn)磁盤(pán)的次數(shù)睬辐，磁盤(pán)緩存本身并不是一種實(shí)際存在的存儲(chǔ)介質(zhì)挠阁，它依托于固定磁盤(pán)，提供對(duì)主存儲(chǔ)器空間的擴(kuò)充溯饵，即利用主存中的存儲(chǔ)空間侵俗，來(lái)暫存從磁盤(pán)中讀出或?qū)懭氲男畔?/b>，主存可以看做是輔存的高速緩存丰刊，因?yàn)榘ィo存中的數(shù)據(jù)必須復(fù)制到主存方能使用，反之啄巧，數(shù)據(jù)也必須先存在主存中寻歧，才能輸出到輔存掌栅。

三、程序的裝入和鏈接

　　為了使程序能夠運(yùn)行码泛，必須先為之創(chuàng)建進(jìn)程猾封，而創(chuàng)建進(jìn)程的第一件事，就是將程序和數(shù)據(jù)裝入內(nèi)存噪珊，如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序忘衍，通常要經(jīng)過(guò)如下幾步，首先是編譯（由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊）卿城，其次是鏈接（由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及它們所需要的庫(kù)函數(shù)鏈接在一起铅搓，形成一個(gè)完整的裝入模塊）瑟押，最后是裝入（由裝入程序?qū)⒀b入模塊裝入內(nèi)存）。

　　3.1程序的裝入

　　在裝入一個(gè)模塊到內(nèi)存時(shí)星掰，有絕對(duì)裝入方式多望，可重定位裝入方式，動(dòng)態(tài)運(yùn)行時(shí)裝入方式氢烘。

　』惩怠①?絕對(duì)裝入方式，如果在編譯時(shí)知道程序駐留在內(nèi)存的什么位置播玖，那么椎工，編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼，絕對(duì)裝入方式按照裝入模塊中的地址蜀踏，將程序和數(shù)據(jù)裝入內(nèi)存维蒙，裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同果覆，故不需要對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改颅痊。

　　②?可重定位裝入方式局待，由于絕對(duì)裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置斑响，在多道程序環(huán)境下，編譯程序不可能事先知道所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存的何處钳榨，因此舰罚，絕對(duì)裝入方式只適用于單道程序環(huán)境，在多道程序環(huán)境下重绷，所得到的目標(biāo)模塊的起始地址通常都是以0開(kāi)始的沸停，程序中的其他地址也都是相對(duì)于起始地址計(jì)算的，此時(shí)應(yīng)采用可重定位裝入方式昭卓，根據(jù)內(nèi)存的當(dāng)前情況愤钾，將裝入模塊裝入到內(nèi)存的適當(dāng)位置瘟滨。該方式會(huì)使裝入模塊中的所有邏輯地址與實(shí)際裝入內(nèi)存的物理地址不同，需要對(duì)數(shù)據(jù)地址和指令地址進(jìn)行修改能颁，通常把再裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過(guò)程稱為重定位杂瘸，又因?yàn)?b>地址變換通常是在裝入時(shí)一次完成的，以后不再變化伙菊，故稱為靜態(tài)重定位败玉。

　　③?動(dòng)態(tài)運(yùn)行時(shí)裝入方式镜硕，可重定位裝入方式允許將裝入模塊裝入到內(nèi)存中任何允許的位置运翼，故可用多道程序環(huán)境，但這種方式并不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置兴枯，因?yàn)檠剩绦蛟趦?nèi)存中的移動(dòng)，意味著它的物理位置發(fā)生了變化财剖，這就必須對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改后方能運(yùn)行悠夯。然而，在運(yùn)行過(guò)程中它在內(nèi)存中的位置可能經(jīng)常要改變躺坟，此時(shí)就應(yīng)該采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式沦补。動(dòng)態(tài)運(yùn)行時(shí)的裝入程序在把裝入程序裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址咪橙，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行夕膀。因此，裝入內(nèi)存后的所有地址都仍是相對(duì)地址美侦，為了使地址轉(zhuǎn)換不影響指令的執(zhí)行速度店诗，需要重定位寄存器的支持。

　　3.2程序的鏈接

　　源程序經(jīng)過(guò)編譯后音榜，可得到一組目標(biāo)模塊庞瘸，再利用鏈接程序把這組目標(biāo)模塊鏈接，形成裝入模塊赠叼，根據(jù)鏈接時(shí)間的不同擦囊，可把鏈接分為靜態(tài)鏈接（在程序運(yùn)行之前，先將各目標(biāo)模塊及他們所需的庫(kù)函數(shù)嘴办，鏈接成一個(gè)完整的裝配模塊瞬场，以后不再拆開(kāi)）、裝入時(shí)動(dòng)態(tài)鏈接（將用戶源程序編譯后所得到的一組目標(biāo)模塊涧郊，在裝入內(nèi)存時(shí)贯被，采用邊裝入邊鏈接的鏈接方式）、運(yùn)行時(shí)動(dòng)態(tài)鏈接（對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要蓋模塊時(shí)彤灶，才對(duì)它進(jìn)行鏈接）看幼。

　　①?靜態(tài)鏈接幌陕，在將目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)诵姜，需要對(duì)相對(duì)地址進(jìn)行修改（由于編譯程序產(chǎn)生的所有目標(biāo)模塊中，使用的都是相對(duì)地址搏熄，其起始地址都為0棚唆，每個(gè)模塊中的地址都是相對(duì)于起始地址計(jì)算的）。也需要變換外部調(diào)用符號(hào)（將每個(gè)模塊中所用的外部調(diào)用符號(hào)都變換為相對(duì)地址）心例，這種先進(jìn)行鏈接所形成的一個(gè)完整的裝入模塊宵凌，又稱為可執(zhí)行文件，通常都不再拆開(kāi)它止后，要運(yùn)行時(shí)可直接將它裝入內(nèi)存摆寄，這種事先進(jìn)行鏈接，以后不再拆開(kāi)的鏈接方式坯门，稱為靜態(tài)鏈接方式。

　《喊恰②?裝入時(shí)動(dòng)態(tài)鏈接古戴，用戶源程序經(jīng)編譯后所得是目標(biāo)模塊，是在裝入內(nèi)存時(shí)邊裝入邊鏈接的窜管，即在裝入一個(gè)目標(biāo)模塊時(shí)租谈，若發(fā)生一個(gè)外部模塊調(diào)用事件量九，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存叉袍，裝入時(shí)動(dòng)態(tài)鏈接有如下優(yōu)點(diǎn)，便于修改和更新（各目標(biāo)模塊是分開(kāi)的存放的刽酱，所以要修改或更新各目標(biāo)模塊非常容易）喳逛，便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享（很容易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享）

　】美铩③?運(yùn)行時(shí)動(dòng)態(tài)鏈接润文，將某些模塊的鏈接推遲到程序執(zhí)行時(shí)才進(jìn)行鏈接，即在執(zhí)行過(guò)程中殿怜，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)典蝌，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上头谜，凡在執(zhí)行過(guò)程中未被調(diào)用到的模塊骏掀，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅加快程序的裝入過(guò)程，同時(shí)也節(jié)省了大量的內(nèi)存空間截驮。

四笑陈、連續(xù)分配方式

　　連續(xù)分配方式是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，可以將連續(xù)分配方式分為單一連續(xù)分配侧纯、固定分區(qū)分配新锈、動(dòng)態(tài)分區(qū)分配、動(dòng)態(tài)重定位分區(qū)分配眶熬。

　　4.1單一連續(xù)分配

　　這是一種最簡(jiǎn)單的存儲(chǔ)管理方式妹笆，但只能在單用戶、單任務(wù)的操作系統(tǒng)中娜氏，將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)拳缠，系統(tǒng)區(qū)供OS使用，通常放在內(nèi)存的低地址贸弥，用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間窟坐，提供給用戶使用。

　　4.2固定分區(qū)分配

　　固定分區(qū)分配是一種最簡(jiǎn)單的可運(yùn)行多道程序的存儲(chǔ)管理方式绵疲，將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域哲鸳，在每個(gè)分區(qū)只裝入一道作業(yè)，這樣盔憨，便允許多道作業(yè)并發(fā)執(zhí)行徙菠，當(dāng)有空閑分區(qū)時(shí)，便可以再?gòu)耐獯娴暮髠渥鳂I(yè)隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)郁岩，當(dāng)該作業(yè)結(jié)束時(shí)婿奔，又可再?gòu)暮髠渥鳂I(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。

　　對(duì)于內(nèi)存的用戶空間的劃分问慎，有如下兩種方法萍摊。

　　① 分區(qū)大小相等如叼，即所有的內(nèi)存分區(qū)大小相等冰木。缺點(diǎn)是缺乏靈活性，即當(dāng)程序太小時(shí)笼恰，會(huì)造成內(nèi)存資源的浪費(fèi)片酝，程序太大時(shí)，一個(gè)分區(qū)由不足以裝入該程序挖腰，只是該程序無(wú)法運(yùn)行雕沿。

　　② 分區(qū)大小不等猴仑，把內(nèi)存區(qū)劃分成含有多個(gè)較小的分區(qū)审轮、適量中等分配和少量大分區(qū)肥哎，這樣，便可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)疾渣。

　　為了便于內(nèi)存分配篡诽，將分區(qū)按大小進(jìn)行排隊(duì)，并為之簡(jiǎn)歷一張分區(qū)使用表榴捡，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址杈女、大小、狀態(tài)（是否已分配）吊圾，當(dāng)有一個(gè)程序需要裝入時(shí)达椰，由內(nèi)存分配程序檢索該表，從中找出一個(gè)能滿足要求的项乒，尚未分配的分區(qū)啰劲，將之分配給該程序，然后將該表項(xiàng)中的狀態(tài)設(shè)置為已分配檀何，若未找到大小足夠的分區(qū)蝇裤，則拒絕為該用戶分配內(nèi)存。

　　4.3動(dòng)態(tài)分區(qū)分配

　　動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要频鉴，動(dòng)態(tài)地為之分配內(nèi)存空間栓辜，在實(shí)現(xiàn)可變分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)垛孔、分區(qū)分配算法藕甩、分區(qū)的分配和回收等。

　∷蒲住①?分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)，為了實(shí)現(xiàn)分區(qū)分配悯姊，胸中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)羡藐，用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為分配提供依據(jù)悯许，常用的數(shù)據(jù)結(jié)構(gòu)有如下兩種形式：空閑分區(qū)表（在系統(tǒng)中設(shè)置一張空閑分區(qū)表仆嗦，用于記錄每個(gè)空閑分區(qū)的情況，每個(gè)空閑分區(qū)占一個(gè)表目先壕，表目中包括分區(qū)序號(hào)瘩扼、分區(qū)始址、分區(qū)大小等垃僚，在前面已有介紹）集绰、空閑分區(qū)鏈（為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分谆棺，設(shè)置一些用于控制分區(qū)分配的信息栽燕，以及用于鏈接各分區(qū)所用的向前指針；在分區(qū)尾部設(shè)置一向后指針，這樣碍岔，可以將空閑分區(qū)鏈接成一個(gè)雙向鏈）浴讯，為了檢索方便，在分區(qū)尾部重復(fù)設(shè)置狀態(tài)為和分區(qū)大小表目蔼啦，當(dāng)分區(qū)被分配出去以后榆纽，把狀態(tài)為從0改成1，此時(shí)前后指針都失去意義（已經(jīng)不再空閑鏈表中）捏肢。

　∧巫选②?分區(qū)分配算法，為把一個(gè)新作業(yè)裝入內(nèi)存猛计，需按照一定的分配算法唠摹，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)，目前常用一下五種分配算法

　　1.?首次適應(yīng)算法（First Fit）

　　以空閑分區(qū)鏈為例進(jìn)行說(shuō)明奉瘤，F(xiàn)F算法要求空閑分區(qū)鏈以地址遞增的次序鏈接勾拉，在分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找盗温，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止藕赞，然后再按照作業(yè)的大小，從該分區(qū)劃出一塊內(nèi)存空間分配給請(qǐng)求者卖局，余下的空閑分區(qū)仍留在空閑鏈中斧蜕，若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則此次內(nèi)存分配失敗砚偶，返回批销。該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)染坯，這給以后達(dá)到的大作業(yè)分配大的內(nèi)存空閑創(chuàng)造了條件均芽，缺點(diǎn)在與低地址空間不斷被劃分，會(huì)留下許多難以利用的单鹿、很小的空閑分區(qū)掀宋，而每次查找又都是從低地址部分開(kāi)始，這無(wú)疑會(huì)增加查找可用空閑分區(qū)的開(kāi)銷仲锄。

　　2.循環(huán)首次適應(yīng)算法（Next Fit）

由首次適應(yīng)算法演變而來(lái)劲妙，在未進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_(kāi)始查找儒喊，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找镣奋，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃分出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)怀愧。進(jìn)行空閑分區(qū)分配時(shí)唆途，會(huì)采用循環(huán)查找方式富雅，即如果最后一個(gè)（鏈尾）空閑分區(qū)的大小仍不能滿足要求，則返回第一個(gè)空閑分區(qū)肛搬。該算法能使內(nèi)存中的空閑分區(qū)分布得更加均勻没佑，從而減少了查找空閑分區(qū)時(shí)的開(kāi)銷，但是會(huì)缺乏大的空閑分區(qū)温赔。

　　3.最佳適應(yīng)算法（Best Fit）

該算法總是能把滿足要求蛤奢、又是最小的康縣分區(qū)分配給作業(yè)，避免大材小用陶贼，為了加速尋找啤贩，該算法要求把所有的空閑分區(qū)按其容量以從小到大的順序形成一個(gè)空閑分區(qū)鏈，這樣拜秧，第一次就能找到滿足要求的空閑區(qū)痹屹，必然是最佳的，孤立地看枉氮，最佳適應(yīng)算法似乎是最佳的志衍，然而宏觀上卻不一定，因?yàn)槊看畏峙浜笏懈钕聛?lái)的剩余部分總是最小的聊替，會(huì)留下很多難以使用的小空閑區(qū)楼肪。

　　4.快速適應(yīng)算法（Quick Fit）

該算法又稱為分類搜索法，是將空閑分區(qū)容量大小進(jìn)行分類惹悄，對(duì)于每一類具有相同容量的所有空閑分區(qū)春叫，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這些泣港，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表暂殖，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型当纱，并記錄了該類型空閑分區(qū)鏈表表頭的指針呛每。該算法的優(yōu)點(diǎn)是查找效率高，僅需根據(jù)進(jìn)程的長(zhǎng)度惫东，尋找到能容納它的最小空閑區(qū)鏈表莉给，并取下第一塊進(jìn)行分配即可毙石。該算法在進(jìn)行空閑分區(qū)分配時(shí)廉沮，不會(huì)對(duì)任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)徐矩，滿足對(duì)大空間的需求滞时，也不會(huì)產(chǎn)生內(nèi)存碎片。但是在分區(qū)歸還主存時(shí)算法復(fù)雜滤灯，系統(tǒng)開(kāi)銷大坪稽。

　÷妗③?分區(qū)分配操作，在動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理中窒百，主要的操作是分配內(nèi)存和回收內(nèi)存黍判。

　　1.分配內(nèi)存

　　系統(tǒng)利用某種分配算法，從空閑分區(qū)鏈（表）中找到所需大小的分區(qū)篙梢，其流程圖如下

　　說(shuō)明：size表示事先規(guī)定的不再切割的剩余分區(qū)的大小顷帖。空閑分區(qū)表示為m.size渤滞，請(qǐng)求分區(qū)的大小為u.size贬墩。

　　2.回收內(nèi)存

當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址妄呕，從空閑區(qū)鏈（表）中找到相應(yīng)的插入點(diǎn)陶舞，此時(shí)會(huì)出現(xiàn)如下四種情況之一：回收分區(qū)與插入點(diǎn)的前一個(gè)空閑區(qū)F1相鄰接，此時(shí)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并绪励，不必為回收區(qū)分配新表項(xiàng)肿孵，只需要修改前一分區(qū)F1的大小。回收分區(qū)與插入點(diǎn)的后以空閑分區(qū)F2相鄰接优炬，此時(shí)將兩分區(qū)合并颁井，形成新的空閑分區(qū)，用回收區(qū)的首址作為新空閑區(qū)的首址蠢护，大小為兩者之和雅宾。回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接葵硕，此時(shí)將三個(gè)分區(qū)合并眉抬，使用F1的表項(xiàng)和F1的首址，取消F2的表項(xiàng)懈凹，大小為三者之和蜀变。回收區(qū)既不與F1鄰接，也不與F2鄰接介评，這時(shí)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)库北，填寫(xiě)回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置们陆。

　　4.4伙伴系統(tǒng)

　　伙伴系統(tǒng)規(guī)定寒瓦，無(wú)論已分配分區(qū)還是空閑分區(qū)，其大小均為2的k次冪坪仇，k為整數(shù)杂腰，1<=

k <= m，其中椅文，2^1表示分配的最小分區(qū)的大小喂很，2^m表示分配的最大分區(qū)的大小惜颇，通常2^m是整個(gè)可分配內(nèi)存的大小。假設(shè)系統(tǒng)開(kāi)始時(shí)的初始容量為2^m個(gè)字少辣，由于不斷切分凌摄，可能會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類漓帅，對(duì)于每一類具有相同大小的所有空閑分區(qū)望伦，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣煎殷，不同大小的空閑分區(qū)形成了k個(gè)空閑分區(qū)鏈表屯伞。

　　當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)i值豪直，使2^i-1 <

n <= 2^i劣摇，然后，在空閑分區(qū)大小為2^i的空閑分區(qū)鏈表中查找弓乙，若找到末融，即把該空閑分區(qū)分配給進(jìn)程，否則暇韧，表明2^i的空閑分區(qū)已經(jīng)耗盡勾习，在大小為2^i+1的空閑分區(qū)鏈表中查找，若存在懈玻，則將該空閑分區(qū)分為兩個(gè)大小為2^i的分區(qū)巧婶，一個(gè)用于分配，一個(gè)加入到大小為2^i的空閑分區(qū)鏈表中涂乌，若還是不存在艺栈，則繼續(xù)在大小為2^i+2的空閑分區(qū)鏈表中查找，若存在湾盒，則將空閑分區(qū)進(jìn)行兩次分割湿右，一次分割為兩個(gè)大小為2^i+1的空閑分區(qū)，一個(gè)加入到大小為2^i+1的空閑分區(qū)鏈表中罚勾，另外一個(gè)繼續(xù)進(jìn)行分割毅人，分成兩個(gè)大小2^i的空閑塊，一個(gè)用于分配尖殃，另外一個(gè)加入到大小為2^i的空閑分區(qū)鏈表中丈莺，以此類推。在最壞的情況下分衫，可能需要對(duì)2^k的空閑分區(qū)進(jìn)行k此分割才能得到所需分區(qū)场刑。

　　當(dāng)回收空閑分區(qū)時(shí)般此，也需要經(jīng)過(guò)多次合并蚪战，如回收大小為2^i的空閑分區(qū)時(shí)牵现，若事先已經(jīng)存在2^i的空閑分區(qū)，則應(yīng)將其與伙伴分區(qū)合并為一個(gè)大小為2^i+1的空閑分區(qū)邀桑，若事先已存在2^i+1的空閑分區(qū)瞎疼，則再次進(jìn)行合并，合并為2^i+2的分區(qū)壁畸，以此類推贼急。

　　4.5可重定位分區(qū)分配

在連續(xù)分配方式中，必須把一個(gè)系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間捏萍，若果在系統(tǒng)中只有若干個(gè)小的分區(qū)太抓，即使他們?nèi)萘靠偤痛笥谝b入的程序，但由于這些分區(qū)不相鄰接令杈，也無(wú)法把該程序裝入內(nèi)存走敌。若想裝入，則將內(nèi)存中的所有作業(yè)進(jìn)行移動(dòng)逗噩，使他們?nèi)肯噜徑拥衾觯@樣，即可把原來(lái)分散的多個(gè)小分區(qū)拼接成一個(gè)大分區(qū)异雁，這時(shí)捶障，就可以把作業(yè)裝入該區(qū)。經(jīng)過(guò)緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化纲刀，此時(shí)若不對(duì)程序和數(shù)據(jù)的地址加以修改（變換）项炼，則程序必將無(wú)法執(zhí)行，為此示绊，在每次緊湊之后芥挣，都必須對(duì)移動(dòng)了的數(shù)據(jù)和程序進(jìn)行重定向。

　　在動(dòng)態(tài)運(yùn)行時(shí)裝入的方式中耻台，作業(yè)裝入內(nèi)存后的所有地址都仍然是相對(duì)地址空免，將相對(duì)地址轉(zhuǎn)化為物理地址的工作，退推遲到程序指令要真正執(zhí)行時(shí)進(jìn)行盆耽。為了是地址變換不影響指令的執(zhí)行速度蹋砚，在系統(tǒng)中增設(shè)了一個(gè)重定位寄存器，用它來(lái)存放程序（數(shù)據(jù)）在內(nèi)存中的起始地址摄杂。在程序執(zhí)行時(shí)坝咐，真正訪問(wèn)的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的。該動(dòng)作是隨著對(duì)每條指令或數(shù)據(jù)的訪問(wèn)自動(dòng)進(jìn)行的析恢，故稱為動(dòng)態(tài)重定位墨坚，當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了緊湊而使若干程序在內(nèi)存中移動(dòng)時(shí)，不需要對(duì)程序做任何修改映挂，只要用該程序在內(nèi)存的新起始地址去置換原來(lái)的起始地址即可泽篮。

動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本上相同盗尸，差別僅在于：在這種分配算法中，增加了緊湊功能帽撑，通常泼各，在找不到足夠大的空閑分區(qū)來(lái)滿足用戶需求時(shí)進(jìn)行緊湊。

　　4.6對(duì)換

　　在多道程序環(huán)境下亏拉，一方面扣蜻，在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占用了大量的內(nèi)存空間及塘，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞而迫使CPU停止下來(lái)等待的情況莽使，另一方面，卻有很多作業(yè)在外存上等待笙僚，因無(wú)內(nèi)存而無(wú)法進(jìn)入內(nèi)存運(yùn)行的情況吮旅，這是對(duì)系統(tǒng)資源的浪費(fèi)，為了解決這個(gè)問(wèn)題味咳，增設(shè)了對(duì)換設(shè)施庇勃，對(duì)換是把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間槽驶，再把已具備運(yùn)行條件的進(jìn)程或者進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存责嚷。對(duì)換是提高內(nèi)存利用率的有效措施。如果對(duì)換的單位是進(jìn)程掂铐，便稱為整體對(duì)換或進(jìn)程對(duì)換罕拂，為了實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須實(shí)現(xiàn)對(duì)換空間的管理全陨、進(jìn)程的換出爆班、進(jìn)程的換入。

　∪枰獭①?對(duì)換空間的管理柿菩，在具有對(duì)換功能的OS中，通常把外存分為文件區(qū)和對(duì)換區(qū)雨涛，前者用于存放文件枢舶，后者用于存放從內(nèi)存換出的進(jìn)程。由于文件通常是較長(zhǎng)久的駐留在外存上替久，文件區(qū)的管理主要目標(biāo)是提高存儲(chǔ)空間的利用率凉泄，采取離散分配方式，進(jìn)程通常在對(duì)換區(qū)中駐留的時(shí)間較短暫蚯根，對(duì)換操作較頻繁后众，故對(duì)對(duì)換空間管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度，采取的是連續(xù)分配的方式，較少考慮外存中的碎片問(wèn)題蒂誉。

　〗淘濉②?進(jìn)程的換出，每當(dāng)進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間拗盒，但又無(wú)足夠的內(nèi)存空間情況時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出锥债，首先陡蝇，系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)磁盤(pán)哮肚，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤(pán)的對(duì)換區(qū)上登夫，若傳送過(guò)程沒(méi)有錯(cuò)誤，則可回收該進(jìn)程所占用的內(nèi)存空間允趟，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改恼策。

　　③?進(jìn)程的換入眨层，系統(tǒng)定時(shí)地查看所有進(jìn)程的狀態(tài)蹭秋，從中找出就緒狀態(tài)但已換出的進(jìn)程侈沪，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入狮斗，直至無(wú)換入的進(jìn)程或無(wú)可換出的進(jìn)程為止。

五弧蝇、基本分頁(yè)存儲(chǔ)管理方式

　　連續(xù)分配方式會(huì)形成很多碎片碳褒，為之進(jìn)行緊湊操作的開(kāi)銷非常大，如果允許一個(gè)進(jìn)程直接分散地裝入到許多不相鄰接的分區(qū)中看疗，則無(wú)須進(jìn)行緊湊操作沙峻，基于這一思想產(chǎn)生了離散分配方式，如果離散分配的基本單位是頁(yè)两芳，則稱為分頁(yè)存儲(chǔ)管理方式摔寨，若為段，則為分段存儲(chǔ)管理方式怖辆。

　　5.1頁(yè)面與頁(yè)表

分頁(yè)存儲(chǔ)管理是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片祷肯，稱為頁(yè)面或頁(yè)，并為各頁(yè)進(jìn)行編號(hào)疗隶，從0開(kāi)始佑笋。相應(yīng)地，把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊斑鼻，稱為（物理）塊或者頁(yè)框蒋纬，也同樣為它們編號(hào)，如0#塊，1#塊等蜀备。在未進(jìn)程分配內(nèi)存時(shí)关摇，以塊為單位將進(jìn)程的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的物理塊中，由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成不可利用的碎片碾阁，稱之為頁(yè)內(nèi)碎片输虱。

　　在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中，頁(yè)面若太大脂凶，一方面可以是內(nèi)存碎片減少宪睹，有利于提供內(nèi)存利用率，但是蚕钦，每一個(gè)進(jìn)程占用的頁(yè)面較多亭病，導(dǎo)致頁(yè)表過(guò)長(zhǎng)，占用太多內(nèi)存嘶居，會(huì)降低頁(yè)面換進(jìn)換出的效率罪帖。頁(yè)面若太大，可減少頁(yè)表的長(zhǎng)度邮屁，提供頁(yè)面換進(jìn)換出的速度整袁，但是，內(nèi)存碎片會(huì)增大佑吝，所以葬项，也頁(yè)面大小應(yīng)適中，通常為512B~8K

　　分頁(yè)地址中的地址結(jié)構(gòu)如下

　　說(shuō)明：前一部分為頁(yè)號(hào)P迹蛤，后一部分為位移量W（或稱為頁(yè)內(nèi)地址）民珍，總共32位，其中0~11位為頁(yè)內(nèi)地址盗飒，每頁(yè)大小4KB嚷量，12~31位為頁(yè)號(hào)，地址空間最多允許1M頁(yè)逆趣。

為了能夠保證在內(nèi)存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊蝶溶，系統(tǒng)為每個(gè)進(jìn)程建立了一張頁(yè)面映射表，簡(jiǎn)稱為頁(yè)表宣渗。頁(yè)表項(xiàng)紀(jì)錄了相應(yīng)頁(yè)在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)抖所，在配置了頁(yè)表后，進(jìn)程執(zhí)行時(shí)痕囱，通過(guò)查找該表田轧，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)，頁(yè)表實(shí)現(xiàn)了從頁(yè)號(hào)到物理塊號(hào)的地址映像鞍恢。

　　即使在簡(jiǎn)單的分頁(yè)系統(tǒng)中傻粘，也常在頁(yè)表的表項(xiàng)中設(shè)置一存取控制字段每窖，用于對(duì)該存儲(chǔ)塊中的內(nèi)存加以保護(hù)，當(dāng)存取控制字段僅有一位時(shí)弦悉，可用來(lái)規(guī)定該存儲(chǔ)塊中的內(nèi)存時(shí)允許讀/寫(xiě)窒典，還是只讀；若存取控制字段為二位稽莉，則可規(guī)定為讀/寫(xiě)瀑志、只讀、只執(zhí)行等存取方式污秆。

　　5.2地址變換機(jī)構(gòu)

為了能夠?qū)⒂脩舻刂房臻g中的邏輯地址變換為內(nèi)存空間中的物理地址劈猪，在系統(tǒng)中必須設(shè)置地址變換機(jī)構(gòu)，該機(jī)構(gòu)的基本任務(wù)是實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換混狠，由于頁(yè)內(nèi)地址與物里塊內(nèi)的地址一一對(duì)應(yīng)岸霹，無(wú)須再進(jìn)行轉(zhuǎn)換疾层，因此将饺，地址變換機(jī)構(gòu)的任務(wù)實(shí)際上只是將邏輯地址中的頁(yè)號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。又因?yàn)轫?yè)面映射表的的作用就是用于實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的變換痛黎，因此予弧，地址變換任務(wù)是借助頁(yè)表來(lái)完成的。

頁(yè)表的功能可以由一組專門的寄存器來(lái)實(shí)現(xiàn)湖饱，一個(gè)頁(yè)表項(xiàng)用一個(gè)寄存器掖蛤，由于寄存器具有較高的訪問(wèn)速度，因而有利于提高地址變換的速度井厌，但成本較高蚓庭，且頁(yè)表項(xiàng)一般會(huì)很多，都使用寄存器實(shí)現(xiàn)不太現(xiàn)實(shí)仅仆，因此器赞，頁(yè)表大多駐留在內(nèi)存。在系統(tǒng)中只設(shè)置一個(gè)頁(yè)表寄存器PTR(Page-Table Register)墓拜，用于存放頁(yè)表在內(nèi)存的始址和頁(yè)表的長(zhǎng)度港柜，平時(shí)，進(jìn)程執(zhí)行時(shí)咳榜，頁(yè)表的始址和頁(yè)表長(zhǎng)度存放在本進(jìn)程的PCB中夏醉，當(dāng)調(diào)度程序調(diào)度到某進(jìn)程時(shí)，將這兩個(gè)數(shù)據(jù)裝入頁(yè)表寄存器涌韩，因此畔柔，在單處理機(jī)環(huán)境下，雖然系統(tǒng)中可以運(yùn)行多個(gè)進(jìn)程臣樱，但只需要一個(gè)頁(yè)表寄存器释树。

　　當(dāng)進(jìn)程要訪問(wèn)某個(gè)邏輯地址中的數(shù)據(jù)時(shí)肠槽，分頁(yè)地址變換機(jī)構(gòu)會(huì)自動(dòng)地將有效地址（相對(duì)地址）分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，再以頁(yè)號(hào)為索引去檢索頁(yè)表奢啥，查找操作由硬件執(zhí)行秸仙，在執(zhí)行檢索前，先將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較桩盲，若頁(yè)號(hào)大于或等于頁(yè)表長(zhǎng)度寂纪，則表示本次訪問(wèn)的地址超越了進(jìn)程的地址空間，這一錯(cuò)誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生一個(gè)地址越界中斷赌结。若未出現(xiàn)錯(cuò)誤捞蛋，則將頁(yè)表始址加上頁(yè)號(hào)與頁(yè)表項(xiàng)長(zhǎng)度的乘積，便得到該表項(xiàng)在頁(yè)表中的位置柬姚，于是可從中得到該頁(yè)的物理塊號(hào)拟杉，將之裝入物理地址寄存器，與此同時(shí)量承，再將有效地址寄存器中的頁(yè)內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中搬设，這樣，便完成了邏輯地址到物理地址的轉(zhuǎn)換撕捍。

上述操作中拿穴，每次存取一個(gè)數(shù)據(jù)時(shí)，都會(huì)訪問(wèn)內(nèi)存兩次忧风，第一次是訪問(wèn)內(nèi)存中的頁(yè)表默色，從中找到指定頁(yè)的物理塊號(hào)，再將塊號(hào)與頁(yè)內(nèi)偏移量W拼接狮腿，以形成物理地址腿宰，第二次訪問(wèn)時(shí)，才是從第一次所得的地址中獲得所需數(shù)據(jù)缘厢，因此吃度，這種方式會(huì)使計(jì)算機(jī)的處理速度降低一半，為了提高地址變換速度昧绣，可以在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查詢能力的特殊高速緩沖寄存器规肴，又稱為聯(lián)想寄存器或快表，用以存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)夜畴。

　　此時(shí)的變換過(guò)程如下拖刃，在CPU給出有效地址后（邏輯地址），由地址變換機(jī)構(gòu)自動(dòng)的將頁(yè)號(hào)P送入高速緩沖寄存器贪绘，并將此頁(yè)號(hào)與高速緩存中的所有頁(yè)號(hào)進(jìn)行比較兑牡，若其中有與之相匹配的頁(yè)號(hào)，便表示所要訪問(wèn)的頁(yè)表項(xiàng)在快表中税灌，于是均函，可以直接從快表中讀出該頁(yè)所對(duì)應(yīng)的物理塊號(hào)亿虽，并送到物理地址寄存器中，如在快表中沒(méi)有找到苞也，則還需要再訪問(wèn)內(nèi)存中的頁(yè)表洛勉，找到后，把從頁(yè)表項(xiàng)讀出的物理塊好送入地址寄存器如迟，同時(shí)收毫，再將此頁(yè)表項(xiàng)存入快表的寄一個(gè)寄存器單元，即修改快表殷勘，如果快表已滿此再，則OS需要找到一個(gè)老的且已被認(rèn)為不再需要的頁(yè)表項(xiàng)，將它換出玲销。

　　5.3 兩級(jí)和多級(jí)頁(yè)表

　　現(xiàn)代計(jì)算機(jī)系統(tǒng)中输拇，可以支持非常大的邏輯地址空間（2^32~2^64），這樣贤斜，頁(yè)表就變得非常大策吠，要占用非常大的內(nèi)存空間，如蠢古，具有32位邏輯地址空間的分頁(yè)系統(tǒng)奴曙，規(guī)定頁(yè)面大小為4KB别凹，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1M(2^20)個(gè)草讶，又因?yàn)槊總€(gè)頁(yè)表項(xiàng)占用一個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅頁(yè)表就要占用1MB的內(nèi)存空間炉菲，而且要求連續(xù)堕战，這顯然是不現(xiàn)實(shí)的，可以通過(guò)如下兩個(gè)方法解決該問(wèn)題拍霜。

　≈龆① 采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題。

　§艚取② 只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存越驻，其余頁(yè)表項(xiàng)仍駐留在磁盤(pán)上，需要時(shí)再調(diào)入道偷。

　　對(duì)于要求連續(xù)的內(nèi)存空間來(lái)存放頁(yè)表的問(wèn)題缀旁，可利用將頁(yè)表進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)面分別存放在不同的物理塊中的辦法來(lái)解決勺鸦，同樣的并巍，也要為離散分配在頁(yè)表再建立一張頁(yè)表，稱為外層頁(yè)表换途。在每個(gè)頁(yè)表項(xiàng)中記錄了頁(yè)表頁(yè)面的物理塊號(hào)懊渡，以32位邏輯地址空間為例進(jìn)行說(shuō)明刽射。

　　說(shuō)明：外層頁(yè)號(hào)P1為10位，可以表示1024個(gè)物理塊剃执，外層頁(yè)表中的外層也內(nèi)地址P2為10位誓禁，可以表示1024個(gè)物理塊，頁(yè)內(nèi)地址為12位肾档，表示頁(yè)面大小為4K现横。

　　說(shuō)明：在頁(yè)表的每一個(gè)表項(xiàng)中存放的是進(jìn)程的某頁(yè)在內(nèi)存中的物理塊號(hào)，如第0頁(yè)的0頁(yè)存放1#物理塊阁最，第1頁(yè)存放4#物理塊戒祠，而在外層頁(yè)表的每個(gè)頁(yè)表項(xiàng)中，所存放的是某頁(yè)表分頁(yè)的首址速种，如第0頁(yè)頁(yè)表存放在1011#物理塊中姜盈，第1頁(yè)頁(yè)表存放在1078#物理塊中。

　　為了實(shí)現(xiàn)地址變換配阵，在地址變換機(jī)構(gòu)中需要增設(shè)一個(gè)外層頁(yè)表寄存器馏颂，用于存放外層頁(yè)表的始址，并利用邏輯地址中的外層頁(yè)號(hào)棋傍，作為外層頁(yè)表的索引救拉，從中找到指定頁(yè)表分頁(yè)的始址，在利用P2作為指定頁(yè)表分頁(yè)的索引瘫拣，找到指定的頁(yè)表項(xiàng)亿絮，其中即含有該頁(yè)在內(nèi)存的物理塊號(hào)，用該塊號(hào)和頁(yè)內(nèi)地址d即可構(gòu)成訪問(wèn)的內(nèi)存物理地址麸拄。

　　將頁(yè)表施行離散分配的方法派昧，雖然解決了對(duì)大頁(yè)表無(wú)需大片存儲(chǔ)空間的問(wèn)題，但是并未解決用較少的內(nèi)存空間去存放大頁(yè)表的問(wèn)題拢切，換言之蒂萎，只用離散分配空間的辦法并未減少頁(yè)表所占用的內(nèi)存空間，解決辦法是把當(dāng)前需要的一批頁(yè)表項(xiàng)調(diào)入內(nèi)存淮椰，以后再根據(jù)需要陸續(xù)調(diào)入五慈。在采用兩級(jí)頁(yè)表結(jié)構(gòu)的情況下，對(duì)于正在運(yùn)行的進(jìn)程主穗，必須將其外層頁(yè)表調(diào)入內(nèi)存泻拦，而對(duì)頁(yè)表則只需要調(diào)入一頁(yè)或者幾頁(yè)，為了表征某頁(yè)的頁(yè)表是否已經(jīng)調(diào)入內(nèi)存黔牵，還應(yīng)在外層頁(yè)表項(xiàng)中增設(shè)一個(gè)狀態(tài)位S聪轿，其值若為0，表示該頁(yè)表分頁(yè)尚未調(diào)入內(nèi)存猾浦，否則陆错，說(shuō)明已經(jīng)在內(nèi)存灯抛，進(jìn)程運(yùn)行時(shí)，地址變換機(jī)構(gòu)根據(jù)邏輯地址P1音瓷，去查找外層頁(yè)表对嚼，若所找到的頁(yè)表項(xiàng)中的狀態(tài)位為0，則產(chǎn)生一中斷信號(hào)绳慎，請(qǐng)求OS將該頁(yè)表分頁(yè)調(diào)入內(nèi)存纵竖。

　　對(duì)于64位的機(jī)器而言，采用兩級(jí)頁(yè)表已經(jīng)不太合適杏愤，如果頁(yè)面大小仍采用4KB靡砌，那么剩下52位，若還是按照物理塊的大猩郝ァ（2^12位）來(lái)劃分頁(yè)表通殃，每個(gè)頁(yè)表項(xiàng)4B，故一頁(yè)中可存放2^10個(gè)頁(yè)表項(xiàng)厕宗，則將余下的42位用于外層頁(yè)號(hào)画舌，此時(shí)，外層頁(yè)表中可能有4096G個(gè)頁(yè)表項(xiàng)已慢，要占用16384GB的連續(xù)內(nèi)存空間曲聂，顯然是不行的。必須采用多級(jí)頁(yè)表佑惠，即將外層頁(yè)表再進(jìn)行分頁(yè)朋腋。若計(jì)算機(jī)的虛擬地址空間大小為2^64，頁(yè)面大小為4KB兢仰，頁(yè)表項(xiàng)為4B乍丈，則最少頁(yè)表的級(jí)數(shù)為6級(jí)剂碴，首先總的頁(yè)面?zhèn)€數(shù)為2^52（64

- 12）把将，其次，每個(gè)物理塊能裝入的頁(yè)表項(xiàng)為4KB/4B = 2^10個(gè)忆矛，10

* 6 > 52察蹲，即最少需要6級(jí)。

六催训、基本分段存儲(chǔ)管理方式

?　　從固定分區(qū)到動(dòng)態(tài)分區(qū)分配洽议，再到分頁(yè)存儲(chǔ)管理方式，其主要?jiǎng)恿樘岣邇?nèi)存利用率漫拭，引入分段存儲(chǔ)管理的目的在于滿足用戶在編程和使用上多方面的要求亚兄。如

　　① 方便編程采驻，用戶可以把自己的作業(yè)按照邏輯關(guān)系劃分為若干段审胚，每個(gè)段都是從0開(kāi)始編址匈勋，并有自己的名字和長(zhǎng)度。

　∩胚丁② 信息共享洽洁，在實(shí)現(xiàn)對(duì)程序和數(shù)據(jù)的共享時(shí)，是以信息的邏輯單位為基礎(chǔ)的菲嘴，比如共享某個(gè)函數(shù)饿自。

　　③ 信息保護(hù)龄坪，信息保護(hù)同樣是對(duì)信息的邏輯單位進(jìn)行保護(hù)昭雌。

　　④ 動(dòng)態(tài)增長(zhǎng)健田，在實(shí)際應(yīng)用中城豁，數(shù)據(jù)段在使用過(guò)程中往往會(huì)不斷增長(zhǎng)，而實(shí)現(xiàn)無(wú)法確切知道數(shù)據(jù)段會(huì)增長(zhǎng)到多大抄课，分段可以較好的解決這個(gè)問(wèn)題唱星。

　　⑤ 動(dòng)態(tài)鏈接跟磨，再運(yùn)行時(shí)间聊，先將主程序所對(duì)應(yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行，當(dāng)運(yùn)行過(guò)程中有需要調(diào)用某段時(shí)抵拘，才將該段調(diào)入內(nèi)存并進(jìn)行鏈接哎榴。

　　6.1分段系統(tǒng)的基本原理

　　在分段管理中，作業(yè)的地址空間被劃分為若干個(gè)段僵蛛，每個(gè)段定義了一組邏輯信息尚蝌，如有主程序段MAIN，子程序段X充尉，數(shù)據(jù)段D及棧段S飘言，每個(gè)段都有自己的名字，每個(gè)段從0開(kāi)始編址驼侠，并采用一段連續(xù)的地址空間姿鸿，段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定，因而各段長(zhǎng)度不等倒源，整個(gè)作業(yè)的地址空間由于是分成多個(gè)段苛预，因而是二維的，即其邏輯地址由段號(hào)和段內(nèi)地址構(gòu)成笋熬。

　　說(shuō)明：一個(gè)作業(yè)允許最長(zhǎng)有64K個(gè)段热某，每個(gè)段的最大長(zhǎng)度為64KB。

在分段式存儲(chǔ)管理系統(tǒng)中，為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)昔馋，而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)芜繁，為了使程序正常運(yùn)行，能夠物理內(nèi)存中找出每個(gè)邏輯段所對(duì)應(yīng)的位置绒极，應(yīng)該為每個(gè)進(jìn)程建立一張段映射表骏令，稱為段表，每個(gè)段在表中有一個(gè)表項(xiàng)垄提，其中記錄了該段在內(nèi)存中的起始地址和段的長(zhǎng)度榔袋。段表可以存放在一組寄存器中，這樣有利于提高地址轉(zhuǎn)換速度铡俐，但通常將段表放在內(nèi)存中凰兑。段表用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。

為了實(shí)現(xiàn)從進(jìn)程的邏輯地址到物理地址的變換功能审丘，在系統(tǒng)中設(shè)置了段表寄存器吏够，用于存放段表始址和段表TL，在進(jìn)行地址變換時(shí)滩报，系統(tǒng)將邏輯地址中的段號(hào)與段表長(zhǎng)度TL進(jìn)行比較锅知，若S>TL，表示段號(hào)太大脓钾，訪問(wèn)越界售睹，產(chǎn)生越界中斷信號(hào)，若未越界可训，則根據(jù)段表的始址和該段的段號(hào)昌妹，計(jì)算該段對(duì)應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存中的起始地址握截，然后飞崖，再檢查段內(nèi)地址d是否超過(guò)該段的段長(zhǎng)SL，若超過(guò)谨胞，同樣發(fā)出越界中斷信號(hào)固歪，若為越界，則將該段的基址與段內(nèi)地址d相加畜眨，即得到要訪問(wèn)的內(nèi)存物理地址昼牛。

　　每次訪問(wèn)一個(gè)數(shù)據(jù)時(shí)（需給出段號(hào)和段內(nèi)地址），也需要訪問(wèn)兩次內(nèi)存康聂，第一次根據(jù)段號(hào)獲得基址，第二次根據(jù)基址與段內(nèi)地址之和訪問(wèn)真實(shí)數(shù)據(jù)的物理地址胞四。這降低了計(jì)算機(jī)的速率恬汁，也可以增設(shè)一個(gè)聯(lián)想存儲(chǔ)器，用來(lái)保存最近常用的段表項(xiàng)辜伟，用來(lái)加速存取數(shù)據(jù)的時(shí)間氓侧。

可以看到脊另，分頁(yè)與分段存在很大的相似性，如都采用離散分配方式约巷，都需要通過(guò)地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換偎痛，但兩者的主要區(qū)別如下。

　《览伞① 頁(yè)是信息的物理單位踩麦，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭氓癌，提高內(nèi)存的利用率谓谦，或者說(shuō)，分頁(yè)僅僅是由于系統(tǒng)管理的需要而不是用戶的需要贪婉，段則是信息的邏輯單位反粥，它含有一組意義相對(duì)完整的信息，分段的目的是為了能更好地滿足用戶的需要疲迂。

　〔哦佟② 頁(yè)的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分尤蒿，是由機(jī)器硬件實(shí)現(xiàn)的娜膘，一個(gè)系統(tǒng)中，只存在一種大小的頁(yè)面优质，段的長(zhǎng)度則不固定竣贪，決定于用戶所編寫(xiě)的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)巩螃，根據(jù)信息的性質(zhì)來(lái)劃分演怎。

　　③ 分頁(yè)的作業(yè)的地址空間是一維的避乏，即單一的線性的地址空間爷耀，程序員只利用一個(gè)記憶符即可表示一個(gè)地址，而分段的作業(yè)地址空間是二維的拍皮，程序員在標(biāo)識(shí)一個(gè)地址是歹叮，需要給出段名和段內(nèi)地址。

　　6.2段頁(yè)式存儲(chǔ)管理方式

　　分頁(yè)系統(tǒng)能夠有效的提高內(nèi)存利用率（但是會(huì)存在頁(yè)內(nèi)碎片）铆帽，分段系統(tǒng)則能夠很好地滿足用戶需要咆耿。若能將兩種方式結(jié)合起來(lái)，既具有分段系統(tǒng)的便于實(shí)現(xiàn)爹橱、分段可共享萨螺、易于保護(hù)、可動(dòng)態(tài)鏈接等優(yōu)點(diǎn)，又能像分頁(yè)系統(tǒng)那樣很好地解決內(nèi)存的外部碎片問(wèn)題慰技，基于此椭盏，提出了段頁(yè)式系統(tǒng)。

　　段頁(yè)式系統(tǒng)先將用戶程序分成若干個(gè)段吻商，再把段分為若干個(gè)頁(yè)掏颊，并為每一個(gè)段賦予一個(gè)段名。段頁(yè)式系統(tǒng)中艾帐，地址結(jié)構(gòu)由段號(hào)乌叶、段內(nèi)頁(yè)號(hào)冈涧、頁(yè)內(nèi)地址三部分構(gòu)成湘换。

　　在段頁(yè)式系統(tǒng)中亲善，為了便于實(shí)現(xiàn)地址轉(zhuǎn)換张足，須配置一個(gè)段表寄存器骤星，其中存放段表始址和段表長(zhǎng)TL流强，進(jìn)行地址變換時(shí)脑慧，首先利用段號(hào)S抡驼，將它與段表長(zhǎng)TL進(jìn)行比較阳藻，若S<TL晰奖，表示未越界，于是利用段表始址和段號(hào)來(lái)求出該段所對(duì)應(yīng)的段表項(xiàng)在段表中的位置腥泥，從中得到該段的頁(yè)表始址匾南，并利用邏輯地址中的段內(nèi)頁(yè)號(hào)P來(lái)獲得對(duì)應(yīng)頁(yè)的頁(yè)表項(xiàng)位置，從中讀出該頁(yè)所在的物理塊號(hào)b蛔外，再利用b和頁(yè)內(nèi)地址構(gòu)成物理地址蛆楞。

在段頁(yè)式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)夹厌，需要訪問(wèn)內(nèi)存三次豹爹，第一次訪問(wèn)時(shí)訪問(wèn)內(nèi)存中的段表，從中取得頁(yè)表始址矛纹，第二次訪問(wèn)是訪問(wèn)內(nèi)存中的頁(yè)表臂聋，從中取出該頁(yè)所在的物理塊號(hào)，并將該塊號(hào)與頁(yè)內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址或南，第三次訪問(wèn)才是真正的從第二次訪問(wèn)所得的地址中孩等，取出指令或數(shù)據(jù)。同樣采够，也可以增設(shè)高速緩沖寄存器用于加快訪問(wèn)速度肄方。

七、虛擬存儲(chǔ)器的基本概念

　　前面所介紹的存儲(chǔ)器管理方式都有一個(gè)共同的特點(diǎn)吁恍，即他們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行扒秸，于是播演，出現(xiàn)了下面兩種情況

　〖酵摺① 有的作業(yè)很大伴奥，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存翼闽，致使該作業(yè)無(wú)法運(yùn)行拾徙。

　　② 做大量作業(yè)要求運(yùn)行感局，但由于內(nèi)存容量不足以容納所有這些作業(yè)尼啡，只能將少數(shù)作業(yè)裝入內(nèi)存讓他們先運(yùn)行，而將其他大量作業(yè)留在外存上等待询微。

　　為了解決上述問(wèn)題崖瞭，可以增加物理內(nèi)存，但是其不太現(xiàn)實(shí)撑毛，另外是從邏輯上擴(kuò)充內(nèi)存容量书聚。

　　基于程序的局部性原理（時(shí)間局限性和空閑局限性），程序在運(yùn)行之前藻雌，沒(méi)有必要全部裝入內(nèi)存雌续，僅需將那些當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行。其余部分暫留在磁盤(pán)上胯杭，程序運(yùn)行時(shí)驯杜，如果它所要訪問(wèn)的頁(yè)（段）已經(jīng)調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去做个，但如果程序所要訪問(wèn)的頁(yè)（段）尚未調(diào)入內(nèi)存（缺頁(yè)或缺段）鸽心，此時(shí)程序應(yīng)利用OS的請(qǐng)求調(diào)頁(yè)（段）功能，將它們調(diào)入內(nèi)存居暖，以使進(jìn)程繼續(xù)執(zhí)行下去顽频。如果此時(shí)內(nèi)存已滿，無(wú)法再裝入新的頁(yè)（段）膝但，則還需利用頁(yè)（段）的置換功能冲九，將內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)至磁盤(pán)上，再將要訪問(wèn)的頁(yè)（段）調(diào)入內(nèi)存跟束，使程序繼續(xù)執(zhí)行莺奸。這樣，可以使很大的用戶程序在較小的內(nèi)存空間中運(yùn)行冀宴。從用戶的調(diào)入看灭贷，該系統(tǒng)具有很大的內(nèi)存容量，但是略贮，用戶看到的大容量只是一種感覺(jué)甚疟，這種存儲(chǔ)器被稱為虛擬存儲(chǔ)器仗岖。所謂虛擬存儲(chǔ)器，是指具有請(qǐng)求調(diào)入功能和置換功能览妖，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)轧拄，其邏輯容量由內(nèi)存容量和外存容量之和決定，其運(yùn)行速度接近內(nèi)存讽膏，成本接近外存檩电。

　　7.1虛擬存儲(chǔ)器的實(shí)現(xiàn)方法

在虛擬存儲(chǔ)器中，允許將一個(gè)作業(yè)分多次調(diào)入內(nèi)存府树，其建立在離散分配的存儲(chǔ)管理方式上俐末。

　　①?請(qǐng)求分頁(yè)系統(tǒng)奄侠，在分頁(yè)系統(tǒng)的基礎(chǔ)上卓箫，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)，其允許只裝入少量頁(yè)面的程序（數(shù)據(jù)）垄潮，便啟動(dòng)運(yùn)行烹卒，以后，再通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能魂挂，陸續(xù)地把要運(yùn)行的頁(yè)面調(diào)入內(nèi)存甫题，同時(shí)把暫時(shí)不用的頁(yè)面換出到外存，置換是以頁(yè)面為單位涂召。其需要必要的硬件和軟件支持坠非。硬件有請(qǐng)求分頁(yè)的頁(yè)表機(jī)制（它是在純分頁(yè)的頁(yè)表機(jī)制上增加若干項(xiàng)而形成的，作為請(qǐng)求分頁(yè)的數(shù)據(jù)結(jié)構(gòu)）果正、缺頁(yè)中斷機(jī)構(gòu)（每當(dāng)用戶程序要訪問(wèn)的頁(yè)面尚未調(diào)入內(nèi)存時(shí)炎码，便產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺的頁(yè)調(diào)入內(nèi)存）秋泳、地址變換機(jī)構(gòu)（在純分頁(yè)的基礎(chǔ)上發(fā)展形成）潦闲。軟件有用于實(shí)現(xiàn)調(diào)頁(yè)的軟件和實(shí)現(xiàn)頁(yè)面置換的軟件。

　∑戎濉②?請(qǐng)求分段系統(tǒng)歉闰，在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段功能和分段置換功能所形成的段式虛擬存儲(chǔ)系統(tǒng)卓起。其允許只裝入少量段的用戶程序和數(shù)據(jù)和敬，即可啟動(dòng)運(yùn)行，以后再通過(guò)調(diào)段功能和段的置換功能將咱不運(yùn)行的段調(diào)出戏阅，同時(shí)調(diào)入即將運(yùn)行的段昼弟，置換是以段為單位。其需要必要的硬件和軟件支持奕筐，硬件有請(qǐng)求分段的段表機(jī)制（它是在純分頁(yè)的段表機(jī)制上增加若干項(xiàng)而形成的舱痘，作為請(qǐng)求分段的數(shù)據(jù)結(jié)構(gòu)）变骡、缺段中斷機(jī)構(gòu)（每當(dāng)用戶程序要訪問(wèn)的段尚未調(diào)入內(nèi)存時(shí)，便產(chǎn)生一缺段中斷芭逝，請(qǐng)求OS將所缺的段調(diào)入內(nèi)存）塌碌、地址變換機(jī)構(gòu)（在純分段的基礎(chǔ)上發(fā)展形成）。軟件有用于實(shí)現(xiàn)調(diào)頁(yè)的軟件和實(shí)現(xiàn)頁(yè)面置換的軟件铝耻。

?　　7.2虛擬存儲(chǔ)器的特征

　√艿① 多次性蹬刷，一個(gè)作業(yè)會(huì)被分成多次調(diào)入內(nèi)存運(yùn)行瓢捉，多次性是虛擬存儲(chǔ)器最重要的特征。

　“斐伞② 對(duì)換性泡态，允許在作業(yè)的運(yùn)行過(guò)程中進(jìn)行換進(jìn)、換出迂卢。換進(jìn)換出能夠有效地提高內(nèi)存利用率某弦。

　　③ 虛擬性而克，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量靶壮。

　　虛擬性是以多次性和對(duì)換性為基礎(chǔ)的，僅當(dāng)系統(tǒng)允許將作業(yè)分多次調(diào)入內(nèi)存员萍，并能夠?qū)?nèi)存中暫時(shí)不運(yùn)行的程序和數(shù)據(jù)換至磁盤(pán)上時(shí)腾降，才有可能實(shí)現(xiàn)虛擬存儲(chǔ)器，而多次性和對(duì)換性有必須建立在離散分配的基礎(chǔ)上碎绎。

八螃壤、請(qǐng)求分頁(yè)存儲(chǔ)管理方式

　　請(qǐng)求分頁(yè)是建立在分頁(yè)基礎(chǔ)上的，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能筋帖。

　　8.1請(qǐng)求分頁(yè)中的硬件支持

　〖榍纭①?頁(yè)表機(jī)制，其基本作用仍然是將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址日麸，由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存寄啼，還有一部分仍在盤(pán)上，故需要再頁(yè)表中再增加若干項(xiàng)代箭，供程序（數(shù)據(jù)）在換進(jìn)墩划、換出時(shí)參考，請(qǐng)求分頁(yè)系統(tǒng)中的頁(yè)表項(xiàng)如下

　　說(shuō)明：狀態(tài)位P梢卸，用于指示該頁(yè)是否已調(diào)入內(nèi)存走诞，供程序訪問(wèn)時(shí)參考；訪問(wèn)字段A蛤高，用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)蚣旱，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問(wèn)碑幅，供選擇換出頁(yè)面時(shí)參考；修改位M塞绿，表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)沟涨，由于內(nèi)存的每一頁(yè)在外存上保留有一個(gè)副本，因此异吻，若未被修改裹赴，則在置換時(shí)就不需要再將該頁(yè)寫(xiě)回到外存上，若被修改诀浪，則必須重寫(xiě)到外存上棋返，M位供置換頁(yè)面時(shí)參考；外存地址雷猪，指出該頁(yè)在外存上的地址睛竣，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考求摇。

　∩涔怠②?缺頁(yè)中斷機(jī)構(gòu)，當(dāng)要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)与境，產(chǎn)生一個(gè)缺頁(yè)中斷验夯，請(qǐng)求OS將缺的頁(yè)面調(diào)入內(nèi)存，缺頁(yè)作為中斷摔刁，也需要經(jīng)過(guò)保護(hù)CPU現(xiàn)場(chǎng)挥转、分析中斷原因、轉(zhuǎn)入中斷處理程序進(jìn)行處理簸搞、恢復(fù)CPU環(huán)境等扁位。但是，其與一般中斷相比有一些不同趁俊，主要在于：在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)（通常CPU都是在一條指令執(zhí)行完后域仇，才檢查是否有中斷請(qǐng)求到達(dá)，若有寺擂，則響應(yīng)暇务，否則，繼續(xù)執(zhí)行下一條指令怔软，然而垦细，缺頁(yè)中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問(wèn)的指令或數(shù)據(jù)不再內(nèi)存時(shí)所產(chǎn)生和處理的）挡逼，一條指令在執(zhí)行期間括改，可能產(chǎn)生多次缺頁(yè)中斷。

　〖铱病③?地址變換機(jī)構(gòu)嘱能，在分頁(yè)系統(tǒng)地址變換基礎(chǔ)上吝梅，為實(shí)現(xiàn)存儲(chǔ)器而增加的某些功能而形成。如產(chǎn)生和處理缺頁(yè)中斷惹骂，以及從內(nèi)存中換出一頁(yè)功能等苏携。

　　8.2內(nèi)存分配策略和分配算法

　　在為進(jìn)程分配內(nèi)存時(shí)，涉及到如下三個(gè)問(wèn)題：最小物理塊數(shù)的確定对粪、物理塊的分配策略右冻、物理塊的分配算法。

　≈谩①?最小物理塊數(shù)的確定纱扭，指能夠保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)，當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)小于此值時(shí)茫死，進(jìn)程將無(wú)法運(yùn)行跪但。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式峦萎、功能、尋址方式忆首。

　“啤②?物理塊的分配策略，在請(qǐng)求分頁(yè)系統(tǒng)中糙及，可采取兩種內(nèi)存分配策略详幽，固定和可變分配策略，在進(jìn)行置換時(shí)浸锨，也可采用全局置換和局部置換唇聘，可組合出如下三種適用的策略。固定分配局部置換（為每個(gè)進(jìn)程分配一定數(shù)目的物理塊柱搜，整個(gè)運(yùn)行期不再改變迟郎，如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存的n個(gè)頁(yè)面中選出一頁(yè)換出聪蘸，然后再調(diào)入一頁(yè)宪肖，以保證分配給該進(jìn)程的內(nèi)存空間不變，若開(kāi)始為進(jìn)程分配的物理塊數(shù)太少健爬，則會(huì)頻繁缺頁(yè)控乾，降低系統(tǒng)吞吐量，若太多娜遵，則使內(nèi)存中駐留的進(jìn)程數(shù)目減少蜕衡，進(jìn)而造成CPU空閑或其他資源空閑的情況），可變分配全局置換（先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理塊设拟，而OS自身也保持一個(gè)空閑物理塊隊(duì)列慨仿，當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)鸽扁，由系統(tǒng)從空閑物理塊隊(duì)列中取出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中镶骗，僅當(dāng)空閑物理隊(duì)列的物理塊用完時(shí)桶现，OS才能從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)鼎姊，這樣骡和，會(huì)是那個(gè)進(jìn)程的物理塊減少，進(jìn)而使缺頁(yè)率增加）相寇，可變分配局部置換（為每個(gè)進(jìn)程分配一定數(shù)目的物理塊慰于，當(dāng)進(jìn)程缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存中的頁(yè)面中選出一頁(yè)換出唤衫，這樣不會(huì)影響其他進(jìn)程的運(yùn)行婆赠，如果該進(jìn)程頻繁發(fā)生缺頁(yè)，則系統(tǒng)需要再為該進(jìn)程分配若干附加的物理塊佳励，直至該進(jìn)程的缺頁(yè)率減少到適當(dāng)程度為止休里，反之，若一個(gè)進(jìn)程正在運(yùn)行過(guò)程中的缺頁(yè)率特別低赃承，則此時(shí)可適當(dāng)減少分配給該進(jìn)程的物理塊數(shù)妙黍，但不應(yīng)該引起缺頁(yè)率明顯增加）。

　∏破省③?物理塊分配算法拭嫁，可采用平均分配算法（將系統(tǒng)中所有可供分配的物理塊平均分配給各個(gè)進(jìn)程）、按比例分配（根據(jù)進(jìn)程的大小按比例分配物理塊）抓于、考慮優(yōu)先權(quán)的分配算法（將重要的做粤，緊迫的作業(yè)分配較多的內(nèi)存空間，可將系統(tǒng)的物理塊分成兩部分捉撮，一部分按比例分配給各進(jìn)程怕品，另一部分則根據(jù)進(jìn)程的優(yōu)先權(quán)適當(dāng)?shù)卦黾酉鄳?yīng)份額后，分配給進(jìn)程）

九呕缭、頁(yè)面置換算法

　　在進(jìn)程運(yùn)行過(guò)程中堵泽，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已五空閑空間時(shí)恢总，為了保證該進(jìn)程能正常運(yùn)行迎罗，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤(pán)的對(duì)換區(qū)中，但應(yīng)將哪個(gè)頁(yè)面調(diào)出片仿，必須根據(jù)一定的算法來(lái)確定纹安，通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法，置換算法的好壞厢岂，直接影響到系統(tǒng)的性能光督。一個(gè)好的頁(yè)面置換算法，應(yīng)該具有較低的頁(yè)面更換頻率塔粒。

　　9.1最佳置換算法

　　是一種理論上的算法结借，所選擇的被淘汰頁(yè)面將是以后用不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的卒茬，采用最佳置換算法船老，可以保證獲得最低的缺頁(yè)率，由于無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中圃酵，哪個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的柳畔，因而該算法無(wú)法實(shí)現(xiàn)，但可以以此評(píng)價(jià)其他算法郭赐。假設(shè)系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊薪韩，并考慮如下的頁(yè)面號(hào)引用串：7，0 捌锭，1俘陷， 2，0舀锨，3岭洲，0，4坎匿，2，3雷激，0替蔬，3，2屎暇，1承桥，2，0根悼，1凶异，7，0挤巡，1剩彬。在進(jìn)程運(yùn)行后的置換如下圖。

　　采用最佳置換算法發(fā)生了6次頁(yè)面置換矿卑。

　　9.2先進(jìn)先出頁(yè)面（FIFO）置換算法

　該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面喉恋，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰，該算法實(shí)現(xiàn)簡(jiǎn)單，只需要把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面轻黑，按照先后次序鏈接成一個(gè)隊(duì)列糊肤，并設(shè)置一個(gè)指針，稱為替換指針氓鄙，使之指向最老的頁(yè)面馆揉，但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中抖拦，有些頁(yè)面經(jīng)常被訪問(wèn)升酣，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。

　　使用FIFO算法時(shí)進(jìn)行了12次頁(yè)面置換蟋座。

　　9.3最近最久未使用（LRU）置換算法

　　該算法根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況來(lái)進(jìn)行決策拗踢，由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，LRU只能使用最近的過(guò)去代替最近的將來(lái)向臀，因此巢墅，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段券膀，用來(lái)記錄一個(gè)頁(yè)面自上次訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t君纫，當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的芹彬，即最近最久未使用的頁(yè)面予以淘汰蓄髓。

　　使用LRU算法時(shí)進(jìn)行了9次頁(yè)面置換。

　　9.4

Clock置換算法

　　為每一頁(yè)設(shè)置一位訪問(wèn)位舒帮，再將內(nèi)存中的所有頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列会喝，當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位置為1玩郊，置換算法在選擇一頁(yè)淘汰時(shí)肢执，只需要檢查頁(yè)的訪問(wèn)位，如果是0译红，就選擇該頁(yè)換出预茄；若為1，則重新置為0侦厚，暫不換出耻陕，給該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì)，再按照FIFO算法檢查下一頁(yè)面刨沦。當(dāng)檢查到隊(duì)列中的最后一個(gè)頁(yè)面時(shí)诗宣，若其訪問(wèn)位仍然是1，則再返回到隊(duì)首去檢查第一個(gè)頁(yè)面已卷，該算法只有一位訪問(wèn)位梧田，只能用它表示該頁(yè)是否已經(jīng)使用過(guò)淳蔼，而置換時(shí)是將未使用過(guò)的頁(yè)面置換出去，故又把該算法稱為最近未用算法NRU(Not

Recently Used)

　　在將一個(gè)頁(yè)面換出時(shí)裁眯，如果該頁(yè)已經(jīng)被修改過(guò)鹉梨，便需要將該頁(yè)重新寫(xiě)回到磁盤(pán)上，但如果沒(méi)有被修改過(guò)穿稳，則不必將它拷回磁盤(pán)存皂，在改進(jìn)的Clock算法中，增加了一個(gè)置換代價(jià)的因素逢艘，這樣旦袋，選擇頁(yè)面換出時(shí)，既要是未使用過(guò)的頁(yè)面它改，又是要未被修改過(guò)的頁(yè)面疤孕，把同時(shí)滿足這兩個(gè)條件的頁(yè)面作為首選淘汰頁(yè)面。由訪問(wèn)位A和修改位M可以組合如下四種類型的頁(yè)面

　⊙胪稀① （A

= 0, M = 0）祭阀，表示該頁(yè)最近既未被訪問(wèn)，又未被修改鲜戒，是最佳淘汰頁(yè)面专控。

　　② （A

= 0, M = 1）遏餐，表示該頁(yè)最近未被訪問(wèn)伦腐，但已被修改，并不是很好的淘汰頁(yè)面失都。

　“啬ⅰ③ （A

= 1, M = 0），表示該頁(yè)最近已被訪問(wèn)粹庞，但未被修改辩越，該頁(yè)可能被再次訪問(wèn)。

　⌒帕浮④ （A

= 1, M = 1），表示該頁(yè)最近已被訪問(wèn)且被修改趁啸，該頁(yè)可能再被訪問(wèn)强缘。

　　對(duì)于置換而言，執(zhí)行如下幾步不傅。

　÷玫唷① 從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列访娶，尋找A = 0 且 M = 0的第一類頁(yè)面商虐，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)，在第一次掃描期間不改變?cè)L問(wèn)位A。

　∶爻怠② 如果第一步失敗典勇，即查找一周后未遇到第一類頁(yè)面，則開(kāi)始第二輪掃描叮趴，尋找A = 0 且M = 1的第二類頁(yè)面割笙，將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間眯亦，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位置為0伤溉。

　　③ 如果第二步也失敗妻率，即未找到第二類頁(yè)面乱顾，則將指針?lè)祷氐介_(kāi)始位置，并將所有的訪問(wèn)位復(fù)為0宫静，然后重復(fù)第一步走净，如果仍然失敗，則重復(fù)第二步囊嘉，則一定能夠找到被淘汰的頁(yè)温技。

十、請(qǐng)求分段存儲(chǔ)管理方式

　　只需先調(diào)入若干個(gè)分段便可啟動(dòng)運(yùn)行扭粱，當(dāng)所訪問(wèn)的段不在內(nèi)存中時(shí)舵鳞，可請(qǐng)求OS將所缺的段調(diào)入內(nèi)存。也同樣需要硬件的支持琢蛤。

　　10.1請(qǐng)求分段中的硬件支持

　　為了快速完成請(qǐng)求分段功能蜓堕，需要支持的硬件有段表機(jī)制、缺段中斷機(jī)制博其、地址變換機(jī)構(gòu)套才。

　　①?段表機(jī)制慕淡，由于只有一部分段裝入內(nèi)存背伴，其余段仍留在外存上，需要再段表中增加若干項(xiàng)峰髓，以供程序調(diào)進(jìn)傻寂、調(diào)出時(shí)參考。

　　說(shuō)明：各字段意義如下存取方式（用于標(biāo)識(shí)本分段的存取屬性是只執(zhí)行携兵、只讀疾掰、還是允許讀/寫(xiě)），訪問(wèn)字段A（用于記錄該段被訪問(wèn)的頻繁程度）徐紧，修改位M（表示該頁(yè)在進(jìn)入內(nèi)存后是否已被修改過(guò)静檬，供置換時(shí)參考）炭懊，存在位P（表示本段是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考）拂檩，增補(bǔ)位（用于表示本段在運(yùn)行過(guò)程中是否做過(guò)動(dòng)態(tài)增長(zhǎng)）侮腹，外存始址（本段在外存中的起始地址，即起始盤(pán)塊號(hào)）广恢。

　】②?缺頁(yè)中斷機(jī)構(gòu)，進(jìn)程運(yùn)行時(shí)發(fā)現(xiàn)所需的段尚未調(diào)入內(nèi)存钉迷，便由缺段中斷機(jī)構(gòu)產(chǎn)生一個(gè)缺段中斷信號(hào)至非，進(jìn)入OS后由缺段中斷處理程序?qū)⑺枰亩握{(diào)入內(nèi)存。需要在一條指令的執(zhí)行期間糠聪，產(chǎn)生和處理中斷荒椭，以及一條指令執(zhí)行期間，可能會(huì)產(chǎn)生多次缺段中斷舰蟆。

③ 地址變換機(jī)構(gòu)趣惠，其在分段系統(tǒng)地址變換機(jī)構(gòu)基礎(chǔ)上形成，增加了缺段中斷的請(qǐng)求和處理功能身害。