先來(lái)先服務(wù)/先進(jìn)先出:優(yōu)點(diǎn):簡(jiǎn)單，易實(shí)現(xiàn)缺點(diǎn):

排在長(zhǎng)作業(yè)之后的短作業(yè)的等待時(shí)間長(zhǎng)，可能引起饑餓時(shí)間片輪轉(zhuǎn):優(yōu)點(diǎn):避免了先進(jìn)先出調(diào)度可能引起的饑餓，適于短作業(yè)較多的情況缺點(diǎn):不宜于長(zhǎng)度相同的作業(yè)調(diào)度；時(shí)間片的大小取決于作業(yè)集中作業(yè)的長(zhǎng)短，過(guò)大或過(guò)小的時(shí)間片會(huì)導(dǎo)致效率低下短作業(yè)優(yōu)先：ShortestJobFirst(SJF)/ShortestRemainingTimeFirst(SRTF):優(yōu)點(diǎn):平均等待時(shí)間最短

缺點(diǎn):公平性；難以預(yù)測(cè)（如作業(yè)長(zhǎng)度）優(yōu)先級(jí)調(diào)度:優(yōu)點(diǎn):靈活缺點(diǎn):公平性；另外靜態(tài)優(yōu)先級(jí)會(huì)導(dǎo)致饑餓小結(jié)如何判定調(diào)度算法的優(yōu)劣確定性建模排隊(duì)模型實(shí)現(xiàn)/仿真:(CPU、內(nèi)存、外存、I/O)資源不足=>調(diào)度何時(shí)需要添加資源：買(mǎi)電腦、網(wǎng)絡(luò)帶寬…Aninterestingimplicationofthiscurve:絕大多數(shù)調(diào)度算法在上述負(fù)載曲線(xiàn)的線(xiàn)性部分工作很好,反之則不然在拐點(diǎn)處添加資源？UtilizationResponsetime100%小結(jié)死鎖產(chǎn)生原因饑餓

vs.死鎖

不同之處？DeadlockStarvationbutnotviceversa三種處理方式（經(jīng)常組合使用）Prevention預(yù)防Avoidance避免Detection檢測(cè)把資源劃分為不同的等級(jí)對(duì)每一類(lèi)使用適當(dāng)?shù)募夹g(shù)來(lái)處理死鎖造成死鎖的四個(gè)原因互斥部分分配條件（保持-等待）不剝奪條件（不搶占）環(huán)路條件（循環(huán)等待）資源分配圖死鎖的預(yù)防死鎖的避免死鎖的檢測(cè)

銀行家算法進(jìn)程Aprocessisaprogram

in

executionAsaprocessexecutes,itchangesstateready,running,waiting,…AprocessisrepresentedbyitsPCBProcess

queuesreadyqueue,I/Orequestqueue,…Long-term(job)andshort-term(CPU)schedulingConcurrentprocessesIndependentprocessesCducer&consumer線(xiàn)程AthreadisaflowofcontrolwithinaprocessAmultithreadedprocesscontainsseveraldifferentflowsofcontrolwithinthesameaddressspaceUser-levelthreadsvisibletoprogrammer,unknowntokernelathreadlibraryinuserspaceKernelthreadssupportedandmanagedbythekernelThreemodelsmany-to-one,m:1one-to-one,1:1many-to-many,m:n(m>=n)CPU調(diào)度Scheduling-selectingaprocessfromthereadyqueueSchedulingalgorithmsfirst-come,firstserved(FCFS)shortestjobfirst(SJF)provablyoptimal,butdifficulttoknownextCPUburstgeneralpriorityschedulingstarvation,andaginground-robin(RR)fortime-sharing,interactivesystemproblem:howtoselectthetimequantum?multilevelqueuedifferentalgorithmsfordifferentclassesofprocessesmultilevelfeedbackqueueallowprocesstomovefromone(ready)queuetoanotherSolaris2,WindowsXP,Linux–preemptive,priority-basedscheduling進(jìn)程同步Shareddatamakemutualexclusionnecessarycriticalsection–apieceofcoderaceconditionSemaphoresmutualexclusionsynchronizationsemaphores’implementationsTheoreticalproblemsbounded-buffer,readers-writers,dining-philosophersalargeclassofconcurrency-controlproblems*high-levelconstructscriticalregions,monitorsequivalenttosemaphores死鎖DefinitionofdeadlockFournecessaryconditionsmutualexclusion,hold-and-wait,nopreemption,circularwaitPreventionbreakoneofthefourconditionsAvoidanceaprioriinformationaboutprocesses’resourceusageThebanker’salgorithm(safestate)Detection-and-recoveryterminatingprocesses,preemptingresources*Ignoretheproblem(e.g.Unix,Linux)內(nèi)存管理背景主存管理介紹連續(xù)存儲(chǔ)空間管理分頁(yè)式存儲(chǔ)管理分段式存儲(chǔ)管理虛擬存儲(chǔ)管理局部性原理：時(shí)間/空間局部性低端存儲(chǔ)的容量盡量大高端存儲(chǔ)的速度盡量快On-ChipCacheRegistersControlDatapathSecondaryStorage(Disk)ProcessorMainMemory(DRAM)SecondLevelCache(SRAM)1s10,000,000s(10sms)Speed(ns):10s-100s100s100sGsSize(bytes):Ks-MsMsTertiaryStorage(Tape)10,000,000,000s(10ssec)Ts內(nèi)存：由很大一組字/字節(jié)所組成，每個(gè)字/字節(jié)都有自己的地址輸入隊(duì)列—磁盤(pán)上等待進(jìn)入內(nèi)存并執(zhí)行的進(jìn)程的集合內(nèi)存共享時(shí)需要考慮的問(wèn)題進(jìn)程和內(nèi)核的工作狀態(tài)取決于存儲(chǔ)在內(nèi)存/寄存器中的相關(guān)數(shù)據(jù)不同的進(jìn)程/線(xiàn)程控制部分不能使用內(nèi)存的同一部分Physics:不同部分的數(shù)據(jù)不能使用內(nèi)存的同一地址有時(shí)不同線(xiàn)程的內(nèi)存資源會(huì)private化

(protection)DRAM>?+BaseLimitCPUVirtualAddressPhysicalAddressError!存儲(chǔ)管理的功能地址變換：將程序地址空間中使用的邏輯地址變換成主存中的地址的過(guò)程，又稱(chēng)地址重定位。地址變換的功能就是要建立虛實(shí)地址的對(duì)應(yīng)關(guān)系。主存分配：按照一定的算法把某一空閑的主存區(qū)分配給作業(yè)或進(jìn)程。存儲(chǔ)保護(hù)：保證用戶(hù)程序(或進(jìn)程映象)在各自的存儲(chǔ)區(qū)域內(nèi)操作，互不干擾。虛擬存儲(chǔ)：使用戶(hù)程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制，即使在用戶(hù)程序比實(shí)際主存容量還要大的情況下，程序也能正確運(yùn)行。地址變換邏輯地址（虛擬地址）－用戶(hù)編程序時(shí)所用的地址（或稱(chēng)程序地址、虛地址），基本單位可與內(nèi)存的基本單位相同，也可以不相同邏輯地址空間－由程序所生成的所有邏輯地址的集合；可以是一維線(xiàn)性空間，也可以是多維空間物理地址－把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱(chēng)為內(nèi)存地址，即內(nèi)存單元所用的地址物理地址空間－與邏輯地址相對(duì)應(yīng)的內(nèi)存中所有物理地址的集合，一維的線(xiàn)性空間用戶(hù)程序看不見(jiàn)真正的物理地址。用戶(hù)只生成邏輯地址，且認(rèn)為進(jìn)程的地址空間為0到max。物理地址范圍從R+0到R+max，R為基地址地址變換－將程序地址空間中使用的邏輯地址變換成內(nèi)存中的物理地址的過(guò)程。由內(nèi)存管理單元（MMU）來(lái)完成。內(nèi)存保護(hù)內(nèi)存保護(hù)：保護(hù)操作系統(tǒng)不受用戶(hù)進(jìn)程影響，保護(hù)用戶(hù)進(jìn)程不受其它用戶(hù)進(jìn)程影響。措施：上下界保護(hù)：下界寄存器存放程序裝入內(nèi)存后的開(kāi)始地址（首址）。上界寄存器存放程序裝入內(nèi)存后的末地址物理地址基址、限長(zhǎng)寄存器保護(hù)：基址寄存器存放程序裝入內(nèi)存后的起始地址。限長(zhǎng)寄存器存放程序裝入內(nèi)存后的最大長(zhǎng)度邏輯地址對(duì)于合法的訪(fǎng)問(wèn)地址，這兩者的效率是相同的，對(duì)不合法的訪(fǎng)問(wèn)地址來(lái)說(shuō)，上下界存儲(chǔ)保護(hù)浪費(fèi)的CPU時(shí)間相對(duì)來(lái)說(shuō)要多些。例子Prog1虛擬地址空間1Prog2虛擬地址空間

2CodeDataHeapStackCodeDataHeapStackData2Stack1Heap1OSheap&StacksCode1Stack2Data1Heap2Code2OScodeOSdata變換

1變換

2物理地址空間例子：指令和數(shù)據(jù)地址變換Couldweplacedata1,start,and/orcheckitatdifferentaddresses?YesWhen?Compiletime/Loadtime/ExecutiontimeRelated:whichphysicalmemorylocationsholdparticularinstructionsordata?data1: dw 32 … start: lw r1,0(data1)

jal

checkitloop: addir1,r1,-1

bnz

loop …checkit:… 0x300 00000020… …0x900 8C2000C00x904 0C0003400x908 2021FFFF0x90C 1420FFFF…0xD00 …編譯時(shí)確定地址變換關(guān)系

:如果內(nèi)存位置已知，可生成絕對(duì)代碼；如果開(kāi)始位置改變，需要重新編譯代碼。加載時(shí)(靜態(tài)地址變換):如果存儲(chǔ)位置在編譯時(shí)不知道，則必須生成可重定位代碼。執(zhí)行時(shí)(動(dòng)態(tài)地址變換)

：如果進(jìn)程在執(zhí)行時(shí)可以在內(nèi)存中移動(dòng)，則地址綁定要延遲到運(yùn)行時(shí)。需要硬件對(duì)動(dòng)態(tài)地址變換的支持，例如基址和限長(zhǎng)寄存器基址寄存器這時(shí)稱(chēng)為重定位寄存器。用戶(hù)進(jìn)程所生成的地址在送交內(nèi)存之前，都將加上重定位寄存器的值。

進(jìn)程在執(zhí)行時(shí)，會(huì)訪(fǎng)問(wèn)內(nèi)存中的指令和數(shù)據(jù)。將指令和數(shù)據(jù)捆綁到內(nèi)存地址可以在以下步驟的任何一步中執(zhí)行。使用重定位寄存器的動(dòng)態(tài)重定位地址變換方式編程或編譯時(shí)確定地址變換關(guān)系：編程時(shí)確定虛－實(shí)地址的關(guān)系是指在用機(jī)器指令編程時(shí)，程序員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中是不能做任何移動(dòng)的，否則就會(huì)出錯(cuò)。靜態(tài)地址變換：靜態(tài)地址變換是在程序裝入內(nèi)存時(shí)完成從邏輯地址到物理地址的轉(zhuǎn)換的。在一些早期的系統(tǒng)中都有一個(gè)裝入程序（加載程序），它負(fù)責(zé)將用戶(hù)程序裝入系統(tǒng)，并將用戶(hù)程序中使用的訪(fǎng)問(wèn)內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址。優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，不要硬件的支持。缺點(diǎn)：程序一旦裝入內(nèi)存，移動(dòng)就比較困難，有時(shí)間上的浪費(fèi)。在程序裝入內(nèi)存時(shí)要將所有訪(fǎng)問(wèn)內(nèi)存的地址轉(zhuǎn)換動(dòng)態(tài)地址變換：地址變換是在程序執(zhí)行時(shí)由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。動(dòng)態(tài)地址變換是由硬件執(zhí)行時(shí)完成的，程序中不執(zhí)行的程序就不做地址變換的工作，這樣節(jié)省了CPU的時(shí)間。系統(tǒng)中設(shè)置了重定位寄存器。重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來(lái)設(shè)置，比較靈活。實(shí)現(xiàn)動(dòng)態(tài)地址變換必須有硬件的支持，并有一定的執(zhí)行時(shí)間延遲?，F(xiàn)代計(jì)算機(jī)系統(tǒng)中都采用動(dòng)態(tài)地址變換技術(shù)。動(dòng)態(tài)加載一個(gè)子程序只有在調(diào)用時(shí)才被加載。更好的內(nèi)存空間利用率；不用的子程序不會(huì)被裝入內(nèi)存。當(dāng)需要大量的代碼來(lái)處理不經(jīng)常發(fā)生的事情時(shí)是非常有用的。不需要操作系統(tǒng)的特別支持，通過(guò)程序設(shè)計(jì)實(shí)現(xiàn)。動(dòng)態(tài)鏈接鏈接被推遲到執(zhí)行時(shí)期二進(jìn)制映像中對(duì)每個(gè)庫(kù)程序的引用都有一個(gè)存根。

存根是小的代碼片，用來(lái)定位合適的保留在內(nèi)存中的庫(kù)程序。存根用子程序地址來(lái)替換自己，并開(kāi)始執(zhí)行子程序。動(dòng)態(tài)鏈接需要操作系統(tǒng)的幫助。操作系統(tǒng)需要檢查子程序是否在進(jìn)程的內(nèi)存空間，或是允許多個(gè)進(jìn)程訪(fǎng)問(wèn)同一內(nèi)存地址。動(dòng)態(tài)地址變換動(dòng)態(tài)地址變換技術(shù)的優(yōu)點(diǎn)：（1）具有給一個(gè)用戶(hù)程序任意分配內(nèi)存區(qū)的能力；（2）可實(shí)現(xiàn)虛擬存儲(chǔ)；（3）具有重新分配的能力；（4）對(duì)于一個(gè)用戶(hù)程序，可以分配到多個(gè)不同的存儲(chǔ)區(qū)。連續(xù)內(nèi)存分配主存通常被分為兩部分用于駐留操作系統(tǒng)：為操作系統(tǒng)保留的部分，通常用中斷向量保存在內(nèi)存低端。用于用戶(hù)進(jìn)程：保存在內(nèi)存高端。每個(gè)程序（作業(yè)）占據(jù)主存中連續(xù)的空間，按管理方式的不同分為：?jiǎn)斡脩?hù)連續(xù)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理采用連續(xù)內(nèi)存分配時(shí)，每個(gè)進(jìn)程位于一個(gè)連續(xù)的內(nèi)存區(qū)域動(dòng)態(tài)定位靜態(tài)定位基址和限長(zhǎng)寄存器的硬件支持連續(xù)存儲(chǔ)空間管理單用戶(hù)連續(xù)存儲(chǔ)管理又稱(chēng)單分區(qū)模式，適用于單用戶(hù)情況，任何時(shí)刻主存儲(chǔ)器中最多只有一道程序主存空間劃分為系統(tǒng)區(qū)和用戶(hù)區(qū)地址轉(zhuǎn)換與存儲(chǔ)保護(hù)：地址轉(zhuǎn)換：物理地址=界限地址+邏輯地址多采用靜態(tài)重定位，采用柵欄寄存器進(jìn)行存儲(chǔ)保護(hù)動(dòng)態(tài)重定位，采用定位寄存器進(jìn)行存儲(chǔ)保護(hù)單用戶(hù)連續(xù)存儲(chǔ)管理的缺點(diǎn)：同單道程序的缺點(diǎn)，系統(tǒng)利用率低連續(xù)存儲(chǔ)空間管理固定分區(qū)存儲(chǔ)管理又稱(chēng)定長(zhǎng)分區(qū)或靜態(tài)分區(qū)模式，是滿(mǎn)足多道程序設(shè)計(jì)需要的最簡(jiǎn)單的存儲(chǔ)管理技術(shù)基本思想：給進(jìn)入主存的用戶(hù)作業(yè)劃分一塊連續(xù)存儲(chǔ)區(qū)域，把作業(yè)裝入該連續(xù)存儲(chǔ)區(qū)域，若有多個(gè)作業(yè)裝入主存，則它們可并發(fā)執(zhí)行。實(shí)現(xiàn)：系統(tǒng)啟動(dòng)時(shí)，系統(tǒng)操作員根據(jù)作業(yè)情況靜態(tài)地把可分配的主存儲(chǔ)器空間（用戶(hù)空間）分割成若干個(gè)連續(xù)的區(qū)域，每個(gè)區(qū)域的位置固定，大小可相同也可不同，每個(gè)分區(qū)在任何時(shí)刻最多只裝入一道程序執(zhí)行連續(xù)存儲(chǔ)空間管理固定分區(qū)存儲(chǔ)管理示例OS(8K)用戶(hù)分區(qū)1(16K)用戶(hù)分區(qū)2(16K)用戶(hù)分區(qū)3(32K)分區(qū)號(hào)起始地址長(zhǎng)度占用標(biāo)志18K16K0224K16K0340K32K主存分配表Job1(20K)0Job1連續(xù)存儲(chǔ)空間管理固定分區(qū)存儲(chǔ)管理地址轉(zhuǎn)換與存儲(chǔ)保護(hù)靜態(tài)定位方式，地址轉(zhuǎn)換時(shí)檢查其絕對(duì)地址是否落在為其分配的用戶(hù)分區(qū)？動(dòng)態(tài)定位方式，專(zhuān)門(mén)設(shè)置一對(duì)地址寄存器（上限/下限寄存器），硬件地址轉(zhuǎn)換機(jī)構(gòu)對(duì)相應(yīng)的地址進(jìn)行比較。作業(yè)調(diào)度策略每個(gè)等待作業(yè)被選中時(shí)，排到一個(gè)能夠裝入它的最小分區(qū)的等待隊(duì)列，該調(diào)度方式可能導(dǎo)致分區(qū)使用不均勻所有作業(yè)排成一個(gè)隊(duì)列，當(dāng)調(diào)度其中一個(gè)進(jìn)入分區(qū)運(yùn)行時(shí)，選擇可容納它的最小可用分區(qū)連續(xù)存儲(chǔ)空間管理固定分區(qū)存儲(chǔ)管理比較適合已知程序（作業(yè)）大小和出現(xiàn)頻率的情形缺點(diǎn)：實(shí)際系統(tǒng)運(yùn)行時(shí)，往往無(wú)法預(yù)知分區(qū)大?。ㄌ?，等同于“單用戶(hù)分區(qū)模式”）主存空間利用率仍然較低無(wú)法適應(yīng)動(dòng)態(tài)擴(kuò)充主存分區(qū)數(shù)目預(yù)先確定，限制了多道運(yùn)行程序的數(shù)量可變分區(qū)內(nèi)存分配根據(jù)一組空閑分區(qū)來(lái)分配大小為n的請(qǐng)求，常用方法有：首次適應(yīng)(firstfit)最佳適應(yīng)(bestfit)最壞適應(yīng)(worstfit)下次適應(yīng)(nextfit)快速適應(yīng)(quickfit)在存儲(chǔ)速度和存儲(chǔ)資源的利用上，首次適應(yīng)和最佳適應(yīng)要比最差適應(yīng)好?？勺兎謪^(qū)存儲(chǔ)管理又稱(chēng)變長(zhǎng)分區(qū)模式基本思想：按作業(yè)的大小劃分分區(qū)，但劃分的時(shí)間、大小和位置均動(dòng)態(tài)確定，系統(tǒng)在作業(yè)裝入主存執(zhí)行之前并不建立分區(qū)。通用數(shù)據(jù)結(jié)構(gòu)（1）已分配區(qū)表（2）未分配區(qū)表。首次適應(yīng)算法：1.

首次適應(yīng)算法是按空閑區(qū)首址升序的（即空閑區(qū)表是按空閑區(qū)首址從小到大）方法執(zhí)行的。分配時(shí)從表首開(kāi)始，以請(qǐng)求內(nèi)存的大小逐個(gè)與空閑區(qū)進(jìn)行比較，找到第一個(gè)滿(mǎn)足要求的空閑為止；若大于請(qǐng)求區(qū)，就將該空閑區(qū)的一部分分配給請(qǐng)求者，然后，修改空閑區(qū)的大小和首址。2.修改空閑區(qū)有兩種方法：從空閑區(qū)頭開(kāi)始；從空閑區(qū)尾開(kāi)始。例如，空閑區(qū)大小50KB，首址156KB，申請(qǐng)34KB。3.這種算法的實(shí)質(zhì)是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被切削成小的區(qū)，其目的是保證在已有大的作業(yè)的到來(lái)有足夠大的空閑區(qū)來(lái)滿(mǎn)足請(qǐng)求者。4.回收時(shí)，首先考察釋放區(qū)是否與系統(tǒng)中的某個(gè)空閑區(qū)相鄰，若相鄰則合并成一個(gè)空閑區(qū)，否則，將釋放區(qū)作為一個(gè)空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當(dāng)?shù)奈恢?。最佳適應(yīng)算法：1.最佳適應(yīng)算法是將申請(qǐng)者放入與其大小最接近的空閑區(qū)中。切割后的空閑區(qū)最小，若系統(tǒng)中有與申請(qǐng)區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請(qǐng)者。（首次適應(yīng)法則不一定）。2.最佳適應(yīng)算法的空閑區(qū)表按空閑區(qū)大小升序方法組織。3.分配時(shí)，按申請(qǐng)的大小逐個(gè)與空閑區(qū)大小進(jìn)行比較，找到一個(gè)滿(mǎn)足要求的空閑區(qū)，就說(shuō)明它是最適合的（即最佳的）。4.這種算法最大的缺點(diǎn)是分割后的空閑區(qū)將會(huì)很小，直至無(wú)法使用，而造成浪費(fèi)。最壞適應(yīng)算法：1.為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問(wèn)題。2.最壞適應(yīng)算法的空閑區(qū)表是按空閑區(qū)大小降序的方法組織的（從大到小的順序）。3.分配時(shí)總是取表中的第一個(gè)表目，若不能滿(mǎn)足申請(qǐng)者的要求，則表示系統(tǒng)中無(wú)滿(mǎn)足要求的空閑區(qū)，分配失??；否則，將從該空閑區(qū)中分配給申請(qǐng)者，然后修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當(dāng)位置。連續(xù)存儲(chǔ)空間管理可變分區(qū)存儲(chǔ)管理實(shí)現(xiàn)地址轉(zhuǎn)換和存儲(chǔ)保護(hù)設(shè)置兩個(gè)專(zhuān)門(mén)的寄存器基址寄存器，存放分區(qū)的起始地址限長(zhǎng)寄存器，存放分區(qū)的長(zhǎng)度移動(dòng)技術(shù)將分散的空閑區(qū)匯集成一個(gè)較大的空閑區(qū)，以利于大作業(yè)的執(zhí)行連續(xù)分區(qū)管理方式存在的問(wèn)題每個(gè)程序總是要求占用連續(xù)的存儲(chǔ)空間，經(jīng)過(guò)一段時(shí)間的運(yùn)行將會(huì)產(chǎn)生許多碎片（不連續(xù)的容量較小的分區(qū)），為接納新的作業(yè)往往需要通過(guò)移動(dòng)已有的主存內(nèi)容來(lái)產(chǎn)生容量較大的分區(qū)。移動(dòng)技術(shù)實(shí)現(xiàn)復(fù)雜，并不可避免地導(dǎo)致管理開(kāi)銷(xiāo)增大碎片問(wèn)題碎片：在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中，會(huì)形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶(hù)（程序）利用而浪費(fèi)。造成這樣問(wèn)題的主要原因是用戶(hù)程序裝入內(nèi)存時(shí)是整體裝入的外部碎片

–當(dāng)整個(gè)內(nèi)存空間可以滿(mǎn)足一個(gè)請(qǐng)求，但它不是連續(xù)的。內(nèi)部碎片–分配的內(nèi)存可能比申請(qǐng)的內(nèi)存大一點(diǎn)，這兩者之間的數(shù)字之差。通過(guò)移動(dòng)技術(shù)來(lái)減少外部碎片移動(dòng)內(nèi)存內(nèi)容，把一些小的空閑內(nèi)存結(jié)合成一個(gè)大的塊。只有在執(zhí)行時(shí)期進(jìn)行動(dòng)態(tài)重定位(relocation)，才有可能進(jìn)行移動(dòng)傳統(tǒng)內(nèi)存管理技術(shù)分區(qū)技術(shù)覆蓋技術(shù)將大程序劃分為一系列的覆蓋，每個(gè)覆蓋是一個(gè)相對(duì)獨(dú)立的程序單位，把程序執(zhí)行時(shí)不需要同時(shí)裝入內(nèi)存的覆蓋構(gòu)成一組，稱(chēng)為覆蓋段。一個(gè)覆蓋段內(nèi)的覆蓋共享同一存儲(chǔ)區(qū)域，該區(qū)域成為覆蓋區(qū)，其大小由對(duì)應(yīng)的覆蓋段內(nèi)最大的覆蓋決定。交換技術(shù)把暫時(shí)不用的某個(gè)程序及數(shù)據(jù)的一部分或全部從內(nèi)存移到外存中去，或把指定的程序或數(shù)據(jù)從外存讀到相應(yīng)的內(nèi)存中，并將控制權(quán)轉(zhuǎn)給該程序的一種內(nèi)存擴(kuò)充技術(shù)。分頁(yè)式存儲(chǔ)管理基本原理：允許作業(yè)存放在若干個(gè)不相鄰的分區(qū)中，既可免去移動(dòng)內(nèi)存信息而產(chǎn)生的工作量，又可充分利用主存空間，盡量減少主存碎片。程序地址空間分成大小相等的頁(yè)面，同時(shí)把內(nèi)存也分成與頁(yè)面大小相等的塊，當(dāng)一個(gè)用戶(hù)程序裝入內(nèi)存時(shí)，以頁(yè)面為單位進(jìn)行分配。頁(yè)面的大小是為2n。分頁(yè)式存儲(chǔ)管理基本概念：幀：主存空間按物理地址分成多個(gè)大小相等區(qū)，每個(gè)區(qū)稱(chēng)為塊(幀)（又稱(chēng)frame）頁(yè)：程序（作業(yè)）按邏輯地址分成多個(gè)大小相等的區(qū)，每個(gè)區(qū)稱(chēng)為一個(gè)頁(yè)面(page)，大小與幀大小相等虛地址（邏輯地址）：頁(yè)號(hào)和頁(yè)偏移pd頁(yè)碼頁(yè)偏移分頁(yè)式存儲(chǔ)管理基本概念頁(yè)表、作業(yè)表和地址轉(zhuǎn)換頁(yè)表塊號(hào)1(20)塊號(hào)2(21)塊號(hào)3(51)…第0頁(yè)第1頁(yè)第2頁(yè)…作業(yè)名Job1…頁(yè)表始址0頁(yè)表長(zhǎng)度3……作業(yè)表物理地址=幀號(hào)（塊號(hào)）*塊長(zhǎng)+單元號(hào)邏輯地址=頁(yè)號(hào)*頁(yè)長(zhǎng)+單元號(hào)查找頁(yè)表分頁(yè)式存儲(chǔ)管理允許進(jìn)程的物理地址空間可以是不連續(xù)的物理內(nèi)存分成大小固定的塊，稱(chēng)為幀(Frame)邏輯內(nèi)存也分位同樣固定大小的塊，叫做頁(yè)(Page)頁(yè)、幀大小由硬件來(lái)決定，通常為2的冪建立一個(gè)頁(yè)表，把邏輯地址轉(zhuǎn)換為物理地址頁(yè)表是頁(yè)式存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)：它包括用戶(hù)程序空間的頁(yè)面與內(nèi)存塊的對(duì)應(yīng)關(guān)系、頁(yè)面的存儲(chǔ)保護(hù)和存取控制方面的信息。在實(shí)際的系統(tǒng)中，為了節(jié)省存儲(chǔ)空間，在頁(yè)表中可以省去頁(yè)號(hào)這個(gè)表目。動(dòng)態(tài)重定位：讓程序的指令執(zhí)行時(shí)動(dòng)態(tài)地進(jìn)行地址變換，給每個(gè)頁(yè)面設(shè)立重定位寄存器，重定位寄存器的集合便稱(chēng)頁(yè)表。頁(yè)表是操作系統(tǒng)為每個(gè)用戶(hù)作業(yè)建立的，用來(lái)記錄程序頁(yè)面和主存對(duì)應(yīng)頁(yè)框的對(duì)照表。分頁(yè)式存儲(chǔ)管理為解決頁(yè)表規(guī)模過(guò)大占用內(nèi)存空間的問(wèn)題多級(jí)頁(yè)表頁(yè)表可以部分存放在內(nèi)存中例，二級(jí)頁(yè)表系統(tǒng)中，一次按邏輯地址的主存訪(fǎng)問(wèn)需要訪(fǎng)問(wèn)三次主存：一次訪(fǎng)問(wèn)頁(yè)目錄、一次訪(fǎng)問(wèn)頁(yè)表、一次訪(fǎng)問(wèn)具體的數(shù)據(jù)現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。兩級(jí)頁(yè)表一個(gè)邏輯地址(32位系統(tǒng)，頁(yè)大小

4K)被分為

:一個(gè)20位的頁(yè)號(hào)一個(gè)12位的偏移對(duì)頁(yè)表進(jìn)行再分頁(yè)，頁(yè)號(hào)分解為:一個(gè)10位的頁(yè)號(hào)一個(gè)10位的偏移因此，一個(gè)邏輯地址表示如下

:

p1

是用來(lái)訪(fǎng)問(wèn)外部頁(yè)表的索引,p2

是外部頁(yè)表的頁(yè)偏移頁(yè)號(hào)頁(yè)偏移pip2d101012兩級(jí)32位分頁(yè)結(jié)構(gòu)的地址轉(zhuǎn)換機(jī)制圖4-14兩級(jí)頁(yè)表結(jié)構(gòu)地址變換結(jié)構(gòu)1.虛地址（邏輯地址、程序地址）以十六進(jìn)制、八進(jìn)制、二進(jìn)制的形式給出將虛地址轉(zhuǎn)換成二進(jìn)制的數(shù)；按頁(yè)的大小分離出頁(yè)號(hào)和位移量（低位部分是位移量，高位部分是頁(yè)號(hào)）；將位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)頁(yè)裝入內(nèi)存的塊號(hào)，并將塊號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。內(nèi)存地址＝塊號(hào)×頁(yè)大?。灰屏俊?、虛地址以十進(jìn)制數(shù)給出頁(yè)號(hào)＝虛地址％頁(yè)大小位移量＝虛地址mod頁(yè)大小以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)頁(yè)裝入內(nèi)存的塊號(hào)內(nèi)存地址＝塊號(hào)×頁(yè)大小＋位移量虛地址變換例1：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將邏輯地址0AFEH，1ADDH轉(zhuǎn)換成物理地址。邏輯地址0AFEH0000101011111110P＝1d＝01011111110物理地址＝0100101011111110＝4AFEH虛地址1ADDH0001101011011101P＝3d＝01011011101物理地址＝0010101011011101＝2ADDH例2：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將邏輯地址7145，3412轉(zhuǎn)換成物理地址。邏輯地址3412P＝3412％2048＝1d＝3412mod2048

＝1364MR=9*2048+1364=19796邏輯地址3412的物理地址是：19796邏輯地址7145P＝7145％2048＝3d＝7145mod2048

＝1001MR=5*2048+1001=11241邏輯地址7145的物理地址是：11241分頁(yè)中的碎片沒(méi)有外部碎片有內(nèi)部碎片最壞情況下，一個(gè)需要n頁(yè)再加1B的進(jìn)程，需要n+1個(gè)幀，幾乎有一個(gè)幀的碎片頁(yè)表的實(shí)現(xiàn)頁(yè)表放在放在內(nèi)存中，用頁(yè)表基址寄存器指向頁(yè)表（table

baseregister，PTBR)頁(yè)表限長(zhǎng)寄存器表明頁(yè)表的長(zhǎng)度（tablelengthregister

，PRLR）每一次的數(shù)據(jù)/指令存取需要兩次內(nèi)存訪(fǎng)問(wèn)，一次是訪(fǎng)問(wèn)頁(yè)表，一次是訪(fǎng)問(wèn)數(shù)據(jù)）通過(guò)一個(gè)相聯(lián)存儲(chǔ)器associativememory或translationlook-asidebuffers(TLBs)，可以解決兩次存取的問(wèn)題，加速頁(yè)表查找分頁(yè)式存儲(chǔ)管理相聯(lián)存儲(chǔ)器和快表通常頁(yè)表存放在主存中，因此按邏輯地址訪(fǎng)問(wèn)某個(gè)主存地址內(nèi)容時(shí)，需要涉及二次主存訪(fǎng)問(wèn)，效率較低相聯(lián)存儲(chǔ)器，一個(gè)專(zhuān)用的高速緩沖存儲(chǔ)器，用于存放最近被訪(fǎng)問(wèn)的部分頁(yè)表，是分頁(yè)式存儲(chǔ)管理的重要組成部分?？毂?，存放在相聯(lián)存儲(chǔ)器中的部分頁(yè)表內(nèi)容頁(yè)號(hào)塊號(hào)（幀號(hào)）特征位…相聯(lián)存儲(chǔ)器相聯(lián)存儲(chǔ)器–并行搜索

Addresstranslation(A′,A′′)如果頁(yè)號(hào)A′在相聯(lián)寄存器內(nèi),得到對(duì)應(yīng)的幀號(hào)否則查找內(nèi)存中的頁(yè)表來(lái)得到幀號(hào)Page#Frame#帶TLB的分頁(yè)硬件基于TLB的有效內(nèi)存訪(fǎng)問(wèn)時(shí)間相聯(lián)存儲(chǔ)器的查找需要時(shí)間：訪(fǎng)問(wèn)內(nèi)存一次需要時(shí)間：t命中率–在相聯(lián)存儲(chǔ)器中找到頁(yè)號(hào)的概率，概率與相聯(lián)存儲(chǔ)器的大小有關(guān)。命中率=有效訪(fǎng)問(wèn)時(shí)間（EffectiveAccessTime，EAT）

EAT=(t+)+(2t+)(1–)

存儲(chǔ)保護(hù)內(nèi)存保護(hù)由與每個(gè)幀相關(guān)聯(lián)的保護(hù)位來(lái)實(shí)現(xiàn)的，可定義讀寫(xiě)權(quán)限有效-無(wú)效位附在頁(yè)表的每個(gè)表項(xiàng)中:“有效”表明相關(guān)的頁(yè)屬于進(jìn)程的邏輯地址空間，并且是一個(gè)valid的頁(yè)?！盁o(wú)效”表明頁(yè)不在進(jìn)程的邏輯地址空間中，或valid但在外存中。共享頁(yè)共享代碼一段只讀（可重入）代碼副本可由進(jìn)程共享。共享代碼出現(xiàn)在進(jìn)程的邏輯地址空間的相同位置。如：文本編輯器，窗口系統(tǒng)等私有代碼和數(shù)據(jù)每個(gè)進(jìn)程保留代碼和數(shù)據(jù)的私有副本。私有代碼和數(shù)據(jù)的頁(yè)可以出現(xiàn)在邏輯地址空間的任何地方。在分頁(yè)環(huán)境下的代碼共享代碼:150KB數(shù)據(jù):50KB進(jìn)程數(shù):40非共享:40*200

=8000共享:

40*50+150

=2150分段式存儲(chǔ)管理為提高主存空間的利用率，存儲(chǔ)管理方式固定分區(qū)→動(dòng)態(tài)分區(qū)→分頁(yè)方式為滿(mǎn)足程序設(shè)計(jì)和開(kāi)發(fā)的要求（為模塊為單位的裝配、共享和保護(hù)），出現(xiàn)了分段式存儲(chǔ)管理一個(gè)程序是一些段的集合，一個(gè)段是一個(gè)邏輯單位，如：主函數(shù)過(guò)程，函數(shù)，方法，對(duì)象局部變量，全局變量堆棧符號(hào)表，數(shù)組用戶(hù)對(duì)一個(gè)程序的認(rèn)知分段式存儲(chǔ)管理基本概念邏輯地址：段號(hào)和段內(nèi)地址段表、作業(yè)表始址長(zhǎng)度100k8k256k16k段表第0段……第1段作業(yè)名Job1…段表始址0段表長(zhǎng)度2……作業(yè)表分段式存儲(chǔ)管理實(shí)現(xiàn)：可基于可變分區(qū)存儲(chǔ)管理的原理，以段為單位進(jìn)行主存分配段共享：通過(guò)不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)。分段的例子1324邏輯地址空間1423物理內(nèi)存分頁(yè)和分段的主要區(qū)別頁(yè)是信息的物理單位，分頁(yè)是由于系統(tǒng)管理的需要，減少外部碎片，提高內(nèi)存利用率。段則是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息，是為了能更好地滿(mǎn)足用戶(hù)的需要。(2)頁(yè)的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁(yè)面；而段的長(zhǎng)度卻不固定，決定于用戶(hù)所編寫(xiě)的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分。(3)分頁(yè)的作業(yè)地址空間是一維的，即單一的線(xiàn)性地址空間；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。Intel30386AddressTranslationLinuxonIntel80x86UsesminimalsegmentationtokeepmemorymanagementimplementationmoreportableUses6segments:KernelcodeKerneldataUsercode(sharedbyalluserprocesses,usinglogicaladdresses)Userdata(likewiseshared)Task-state(per-processhardwarecontext)LDTUses2protectionlevels:KernelmodeUsermode小結(jié)比較不同內(nèi)存管理策略（連續(xù)分配、分頁(yè)、分段）時(shí)，考慮以下方面硬件支持寄存器,頁(yè)表,段表性能快速寄存器、頁(yè)表、TLB碎片固定分區(qū)，內(nèi)部碎片多個(gè)分區(qū)、分段，外部碎片小結(jié)重定位緊縮，在內(nèi)存中移動(dòng)程序要求在執(zhí)行時(shí)邏輯地址能動(dòng)態(tài)重定位共享要求分頁(yè)或分段保護(hù)頁(yè)、段表中的保護(hù)位基址、限長(zhǎng)寄存器虛擬內(nèi)存背景虛擬內(nèi)存：事實(shí)數(shù)組、鏈表和表通常分配了比實(shí)際所需要更多的內(nèi)存。程序的某些選項(xiàng)或特點(diǎn)可能很少使用。即使需要完整程序，也并不是在某時(shí)刻同時(shí)需要優(yōu)點(diǎn)保存部分程序在內(nèi)存中，可運(yùn)行一個(gè)比物理內(nèi)存大的多的程序邏輯地址空間能夠比物理地址空間大可以有更多程序同時(shí)運(yùn)行允許若干個(gè)進(jìn)程共享地址空間進(jìn)程創(chuàng)建高效實(shí)現(xiàn)請(qǐng)求分頁(yè)存儲(chǔ)管理(Demandpaging)請(qǐng)求分段存儲(chǔ)管理(Demandsegmentation)請(qǐng)求段頁(yè)式存儲(chǔ)管理局部性原理：

(1)時(shí)間局部性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪(fǎng)問(wèn)過(guò)，則不久以后該數(shù)據(jù)可能再次被訪(fǎng)問(wèn)。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。

(2)空間局部性。一旦程序訪(fǎng)問(wèn)了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪(fǎng)問(wèn)，即程序在一段時(shí)間內(nèi)所訪(fǎng)問(wèn)的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。虛擬存儲(chǔ)管理虛擬存儲(chǔ)器實(shí)現(xiàn)的理論基礎(chǔ)作業(yè)為什么能夠部分裝入和部分對(duì)換？作業(yè)信息（程序）的局部性，使得在作業(yè)信息不完全裝入主存的情況下能夠保證其正確運(yùn)行空間局部性，一段時(shí)間內(nèi)，僅訪(fǎng)問(wèn)程序代碼和數(shù)據(jù)的一小部分時(shí)間局部性，最近訪(fǎng)問(wèn)過(guò)的程序代碼和數(shù)據(jù)，很快又被訪(fǎng)問(wèn)的可能性很大虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理與對(duì)換技術(shù)的區(qū)別虛擬存儲(chǔ)管理以頁(yè)或段為單位處理進(jìn)程所需主存容量大于當(dāng)前系統(tǒng)空閑量時(shí)仍能運(yùn)行對(duì)換技術(shù)（中級(jí)調(diào)度，掛起和解除掛起）以進(jìn)程為單位處理進(jìn)程所需主存容量大于當(dāng)前系統(tǒng)空閑量時(shí)，無(wú)法解除掛起示意圖虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理技術(shù)的擴(kuò)展，是一種常用的分頁(yè)式虛擬存儲(chǔ)管理技術(shù)基本原理：將作業(yè)信息被分為多個(gè)頁(yè)面，其副本存放在輔助存儲(chǔ)器中。當(dāng)作業(yè)被調(diào)度運(yùn)行時(shí)，僅裝入需要立即訪(fǎng)問(wèn)和使用的頁(yè)面，在執(zhí)行過(guò)程中如果需要訪(fǎng)問(wèn)的頁(yè)面不在主存中，則將其動(dòng)態(tài)裝入。虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理頁(yè)表的擴(kuò)展頁(yè)號(hào)駐留標(biāo)志頁(yè)框號(hào)輔存地址其他標(biāo)志…1…………0……………………1表示在主存中，0表示不在主存中其他標(biāo)志：缺頁(yè)標(biāo)志、臟頁(yè)標(biāo)志、訪(fǎng)問(wèn)標(biāo)志、鎖定標(biāo)志、淘汰標(biāo)志等虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理硬件支撐操作系統(tǒng)的存儲(chǔ)管理需要依靠低層硬件的支撐來(lái)完成，該硬件稱(chēng)為主存管理單元MMU。MMU的主要功能，完成邏輯地址到物理地址的轉(zhuǎn)換，并在轉(zhuǎn)換過(guò)程中產(chǎn)生相應(yīng)的硬件中斷（缺頁(yè)中斷、越界中斷）MMU的主要組成：頁(yè)表基址寄存器快表TLB請(qǐng)求分頁(yè)式存儲(chǔ)管理需要調(diào)頁(yè)的時(shí)候才把它換入內(nèi)存.需要很少的I/O需要很少的內(nèi)存響應(yīng)快多用戶(hù)需要頁(yè)面調(diào)度時(shí)查閱此頁(yè)的引用無(wú)效引用中止不在內(nèi)存將其調(diào)入內(nèi)存缺頁(yè)中斷找一個(gè)空閑幀將需要的頁(yè)調(diào)入空閑幀重置頁(yè)表，有效位為1重啟指令虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理硬件支撐MMU的工作流程分解邏輯地址（頁(yè)號(hào)，頁(yè)內(nèi)地址）查詢(xún)快表（高速緩存）查詢(xún)頁(yè)表（主存）轉(zhuǎn)換成物理地址（頁(yè)號(hào)→頁(yè)框號(hào)）命中不命中命中不命中產(chǎn)生缺頁(yè)中斷裝入快表PageReplacement基本步驟Findthelocationofthedesiredpageondisk

Findafreeframe:

-Ifthereisafreeframe,useit

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe

Readthedesiredpageintothe(newly)freeframe.Updatethepageandframetables.

Restart[continue]theprocess缺頁(yè)當(dāng)需要調(diào)頁(yè)但沒(méi)有空閑幀時(shí)？

Swapping:

把內(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)存。數(shù)據(jù)結(jié)構(gòu)：其形式與內(nèi)存的動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)，即對(duì)換區(qū)的首址及其大小，它們的單位是盤(pán)塊號(hào)和盤(pán)塊數(shù)。Swapping可有效提高內(nèi)存利用率。

虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理需要解決的主要問(wèn)題主存和輔存的統(tǒng)一管理問(wèn)題邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題部分裝入和部分對(duì)換問(wèn)題虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理頁(yè)面裝入策略，何時(shí)將一個(gè)頁(yè)面裝入主存？請(qǐng)頁(yè)式調(diào)入，缺頁(yè)中斷驅(qū)動(dòng)，一次調(diào)入一頁(yè)預(yù)調(diào)式調(diào)入，按某種預(yù)測(cè)算法動(dòng)態(tài)預(yù)測(cè)并調(diào)入若干頁(yè)面）消除策略，何時(shí)將修改過(guò)的頁(yè)面寫(xiě)回輔存？請(qǐng)頁(yè)式清除，僅當(dāng)一頁(yè)被選中進(jìn)行替換時(shí)，該頁(yè)內(nèi)容已修改則寫(xiě)回輔存。（清除與替換成對(duì)）預(yù)約式清除，內(nèi)容被修改頁(yè)面成批寫(xiě)回輔存，寫(xiě)回操作在該頁(yè)面被替換前，而非替換時(shí)。例子：請(qǐng)求分頁(yè)性能缺頁(yè)概率

0p1.0p=0無(wú)缺頁(yè)p=1,全部缺頁(yè)

有效訪(fǎng)問(wèn)時(shí)間（EffectiveAccessTime，EAT) EAT=(1–p)x內(nèi)存訪(fǎng)問(wèn)時(shí)間

+p(頁(yè)錯(cuò)誤開(kāi)銷(xiāo)

+換出開(kāi)銷(xiāo)

+換入開(kāi)銷(xiāo)

+重啟開(kāi)銷(xiāo))“換出開(kāi)銷(xiāo)”=“換入開(kāi)銷(xiāo)”x“probablityithasbeenchanged”內(nèi)存訪(fǎng)問(wèn)時(shí)間=1usec

內(nèi)存中50%被選為參與調(diào)頁(yè)的頁(yè)已被修改，調(diào)頁(yè)時(shí)需換出

頁(yè)替換時(shí)間=10,000usec EAT=(1–p)x1usec+p(1+0.50)10000usec =1+14999xp(inusec)如果缺頁(yè)率為p=0.1%(0.001),then EAT=16usec(16倍于內(nèi)存訪(fǎng)問(wèn)時(shí)間)[WhywilladdingmorememoryspeedupyourPC?]例子：請(qǐng)求分頁(yè)性能DemandPagingExample有效訪(fǎng)問(wèn)時(shí)間

=HitRatexHitTime+MissRatexMissTime示例內(nèi)存訪(fǎng)問(wèn)時(shí)間=200nanoseconds缺頁(yè)時(shí)的頁(yè)替換時(shí)間

=8milliseconds缺頁(yè)率

p有效訪(fǎng)問(wèn)時(shí)間=(1–p)x200ns+px8ms =(1–p)x200ns+px8,000,000ns=200ns+px7,999,800ns如果缺頁(yè)率為0.1%,有效訪(fǎng)問(wèn)時(shí)間=8.2μs:訪(fǎng)問(wèn)速度比內(nèi)存訪(fǎng)問(wèn)速度慢40倍!如果要求訪(fǎng)問(wèn)速度比內(nèi)存慢10%?200nsx1.1<EATp<2.5x10-6即缺頁(yè)率為1/400000!請(qǐng)求分頁(yè)式存儲(chǔ)管理為實(shí)現(xiàn)請(qǐng)求分頁(yè)式存儲(chǔ)管理須解決兩個(gè)問(wèn)題幀分配算法:

給每個(gè)進(jìn)程分配多少幀頁(yè)替換算法:

怎樣選擇要替換的幀主要包括：主存和輔存的統(tǒng)一管理，邏輯地址到物理地址的轉(zhuǎn)換，部分裝入和部分對(duì)換問(wèn)題磁盤(pán)

I/O非常費(fèi)時(shí)，為提高系統(tǒng)性能－>降低缺頁(yè)率虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理影響缺頁(yè)中斷率的因素：頁(yè)面替換算法主存頁(yè)框數(shù)頁(yè)面大小程序特性虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理幀分配策略固定分配，在一個(gè)進(jìn)程的生命周期中，分配給它的幀數(shù)固定。平均分配、按比例分配、優(yōu)先權(quán)分配可變分配，在一個(gè)進(jìn)程的生命周期中，當(dāng)進(jìn)程缺頁(yè)次數(shù)較多時(shí)，分配給它較多的幀，反之，則分配給較少的幀。頁(yè)面替換策略局部替換策略，通常與固定分配結(jié)合使用全局替換策略，通常與可變分配結(jié)合使用幀分配算法

平均分配算法這是將系統(tǒng)中所有可供分配的幀，平均分配給各個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有100個(gè)幀，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)幀。這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁(yè)，只分配給它20個(gè)幀，這樣，它必然會(huì)有很高的缺頁(yè)率；而另一個(gè)進(jìn)程只有10頁(yè)，卻有10個(gè)幀閑置未用。按比例分配算法這是根據(jù)進(jìn)程的大小按比例分配幀的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁(yè)數(shù)為Si，則系統(tǒng)中各進(jìn)程頁(yè)數(shù)的總和為：又假定系統(tǒng)中可用的幀總數(shù)為m，則每個(gè)進(jìn)程所能分到的幀數(shù)為bi，將有：b應(yīng)該取整，它必須大于系統(tǒng)最小幀數(shù)?？紤]優(yōu)先權(quán)的分配算法在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有幀分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來(lái)為各進(jìn)程分配其幀的。理想的缺頁(yè)與幀數(shù)關(guān)系圖給定一串內(nèi)存引用序列:

1,4,1,6,1,6,1,6,1,6,1如果有三幀:3次缺頁(yè)如果只有一幀:11次缺頁(yè)頁(yè)替換算法FIFO最優(yōu)頁(yè)替換隨機(jī)替換LRU其他如何評(píng)價(jià)頁(yè)面替換算法應(yīng)盡量避免“抖動(dòng)”現(xiàn)象的出現(xiàn)衡量指標(biāo)——缺頁(yè)率f：受頁(yè)替換算法、主存幀數(shù)、頁(yè)大小、程序等影響FIFO頁(yè)替換FIFO算法:可以創(chuàng)建一個(gè)FIFO隊(duì)列來(lái)管理內(nèi)存中的所有頁(yè)調(diào)入頁(yè)時(shí)，將它加到隊(duì)列的尾部當(dāng)必須替換一頁(yè)時(shí)，將選擇最舊的頁(yè)總共15次缺頁(yè)最優(yōu)頁(yè)替換算法被替換的頁(yè)是未來(lái)最長(zhǎng)時(shí)間不被使用的頁(yè)很難實(shí)現(xiàn)，因?yàn)樾枰磥?lái)的知識(shí)4幀的例子

1,2,3,4,1,2,5,1,2,3,4,5

最優(yōu)頁(yè)替換的作用：用來(lái)衡量其他算法的性能12346pagefaults45最優(yōu)頁(yè)替換total9pagefaults隨機(jī)頁(yè)替換算法被替換的頁(yè)是隨機(jī)選擇的頁(yè)TLB采用的一種應(yīng)用方式，硬件結(jié)構(gòu)簡(jiǎn)單性能難以預(yù)測(cè)，實(shí)時(shí)性難以保證LeastRecentlyUsed（LRU）頁(yè)替換LRU替換算法為每個(gè)頁(yè)記錄該頁(yè)最后的使用時(shí)間當(dāng)必須進(jìn)行頁(yè)替換時(shí)，LRU選擇最近最長(zhǎng)未被使用的頁(yè)。LRU頁(yè)替換棧實(shí)現(xiàn)在一個(gè)雙鏈表中保留一個(gè)記錄頁(yè)數(shù)目的棧最近被訪(fǎng)問(wèn)的頁(yè)

:移到棧頂最壞情況下需要改變6個(gè)指針無(wú)需查找，棧底部即是要找的頁(yè)P(yáng)age6Page7Page1Page2HeadTail(LRU)3frames,4頁(yè),andfollowingreferencestream:ABCABDADBCBFIFO:7次缺頁(yè).WhenreferencingD,replacingAisbadchoice,sinceneedAagainrightawayExample:FIFOCBADCBABCBDADBACBA321Ref:Page:考慮以下序列:ABCABDADBCB最優(yōu)頁(yè)替換:缺頁(yè):5次WherewillDbebroughtin?Lookforpagenotreferencedfarthestinfuture.WhatwillLRUdo?SamedecisionsasMINhere,butwon’talwaysbetrue!Example:最優(yōu)頁(yè)替換CDCBABCBDADBACBA321Ref:Page:考慮以下序列:ABCDABCDABCDLRU(sameasFIFOhere):Everyreferenceisapagefault!在該例中最優(yōu)頁(yè)替換性能好很多:DLRU性能可能差？CBADCBADCBACBADCBADCBAD321Ref:Page:BCDCBACBADCBADCBAD321Ref:Page:Addingmemory=>降低缺頁(yè)率?YesforLRUandMINNotnecessarilyforFIFO!(Belady’sanomaly)Afteraddingmemory:WithFIFO,contentscanbecompletelydifferentIncontrast,withLRUorMIN,contentsofmemorywithXpagesareasubsetofcontentswithX+1PageDCEBADCBADCBA EBADCBAE321Ref:Page:CD4EDBAECBADCBAEBADCBAE321Ref:Page:First-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)

4frames

FIFOReplacement–Belady’sAnomalymoreframes(can)morepagefaults(butnotgenerally)1231234125349pagefaults1231235124510pagefaults443存在Belady

異常的FIFO替換缺頁(yè)曲線(xiàn)圖Belady異常引用串:1,2,3,4,1,2,5,1,2,3,4,53幀4幀

FIFO替換算法–Belady異常期望:增加幀數(shù)降低缺頁(yè)率？1231234125349pagefaults1231235124510pagefaults443LRU頁(yè)替換內(nèi)存引用序列:1,2,3,4,1,2,5,1,2,3,4,5

計(jì)數(shù)器的實(shí)現(xiàn)每一個(gè)頁(yè)表項(xiàng)有一個(gè)計(jì)數(shù)器，每次頁(yè)通過(guò)這個(gè)表項(xiàng)被訪(fǎng)問(wèn)，把記錄拷貝到計(jì)數(shù)器中當(dāng)一個(gè)頁(yè)需要改變是，查看計(jì)數(shù)器來(lái)覺(jué)得改變哪一個(gè)頁(yè)0123544358pagefaultsLRU頁(yè)替換計(jì)數(shù)器實(shí)現(xiàn)每個(gè)頁(yè)表項(xiàng)都關(guān)聯(lián)一個(gè)使用時(shí)間域需要一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器，對(duì)每次內(nèi)存引用，計(jì)數(shù)器都會(huì)增加。每次內(nèi)存引用時(shí)，時(shí)鐘寄存器的內(nèi)容都會(huì)復(fù)制到相應(yīng)頁(yè)表項(xiàng)的使用時(shí)間域內(nèi)進(jìn)行頁(yè)替換時(shí)，選擇具有最小時(shí)間（或者計(jì)數(shù)器值）的頁(yè)問(wèn)題需要搜索頁(yè)表每次內(nèi)存訪(fǎng)問(wèn)都需要寫(xiě)頁(yè)表項(xiàng)的使用時(shí)間域上下文切換時(shí)需要維護(hù)頁(yè)表需要考慮時(shí)鐘溢出LRU頁(yè)替換棧實(shí)現(xiàn)在一個(gè)雙鏈表中保留一個(gè)記錄頁(yè)數(shù)目的棧最近被訪(fǎng)問(wèn)的頁(yè)

:移到棧頂最壞情況下需要改變6個(gè)指針無(wú)需查找，棧底部即是要找的頁(yè)理想實(shí)現(xiàn)方式:每次訪(fǎng)問(wèn)記錄Timestamp將頁(yè)按訪(fǎng)問(wèn)時(shí)間排序?qū)崿F(xiàn)過(guò)于復(fù)雜，tooexpensivePage6Page7Page1Page2HeadTail(LRU)LRU近似頁(yè)替換Referencebit每個(gè)頁(yè)都與一位相關(guān)聯(lián)，稱(chēng)為Referencebit,初始值位0當(dāng)頁(yè)被訪(fǎng)問(wèn)時(shí)，將該頁(yè)的Referencebit設(shè)為1替換Referencebit為0的第一個(gè)頁(yè)。缺點(diǎn)：時(shí)間順序未知一些通過(guò)Referencebit位實(shí)現(xiàn)的LRU近似頁(yè)替換算法時(shí)鐘算法Arrangephysicalpagesincirclewithsi