自學(xué)考試操作系統(tǒng)名詞解釋總結(jié)

自學(xué)考試操作系統(tǒng)名詞解釋總結(jié)在學(xué)習(xí)這章之前，我們先來考慮這樣一個問題：為什么要進(jìn)行存儲器的管理？要回答這個問題，我們先回憶一下我們計(jì)算機(jī)使用的過程。計(jì)算機(jī)啟動到桌面→用戶啟動自己想要運(yùn)行的程序→開始使用此時我們來假想一下計(jì)算機(jī)內(nèi)存中的情況：內(nèi)存中此時至少有兩部分程序，一部分是操作系統(tǒng)的程序，一部分是用戶運(yùn)行的程序。而且為了提高計(jì)算機(jī)的使用效率，現(xiàn)在的計(jì)算機(jī)系統(tǒng)多采用多道程序的思想，也就是說計(jì)算機(jī)中一次裝入內(nèi)存的程序應(yīng)該有多道，再加上操作系統(tǒng)本身的程序，那么在計(jì)算機(jī)內(nèi)存中存在的程序應(yīng)該是多個。因此就出現(xiàn)了幾個問題值得我們思考：第一個問題：這么多程序在一塊內(nèi)存中，他們之間不相互影響嗎？萬一串了怎么辦？用戶程序互相影響也就罷了，但萬一影響到操作系統(tǒng)，那系統(tǒng)可就崩潰了！第二個問題：這些程序裝入內(nèi)存是怎樣裝入的？只是簡單的將要運(yùn)行的程序的源代碼復(fù)制到內(nèi)存就可以了嗎？第三個問題：多個程序在內(nèi)存中是怎樣存放的，是簡單的一個接一個嗎？第四個問題：萬一操作系統(tǒng)的程序和用戶要運(yùn)行的程序都比內(nèi)存空間大，那怎么辦，這些程序還能運(yùn)行嗎？我們會考慮這些問題，作為方便用戶管理計(jì)算機(jī)的操作系統(tǒng)更會考慮這些問題，因此操作系統(tǒng)必須具有很好的解決上述幾個問題的功能，即存儲器管理功能，這也正是要進(jìn)行存儲器管理的主要原因。下面我們來考慮一下前面幾個問題的解決方法：第一個問題：多個程序相互影響嗎？肯定影響，解決方法：存儲地址保護(hù)，即就是給每個程序劃分不同的內(nèi)存區(qū)域，如下圖所示以內(nèi)存地址為界，將內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)，用戶程序調(diào)入內(nèi)存時，操作系統(tǒng)肯定在用戶區(qū)中劃分空間，這樣首先保證用戶程序不會破壞系統(tǒng)程序而是系統(tǒng)崩潰；在用戶區(qū)中為不同的用戶程序分配空間時，進(jìn)行內(nèi)存地址的保護(hù)，以保證用戶程序之間不會相互干擾和破壞。這種保護(hù)包括：1、防止地址越界2、防止越權(quán)(對共享區(qū)有訪問權(quán))存儲保護(hù)的實(shí)現(xiàn)方法在CPU中設(shè)置一對下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址也可將一個寄存器作為基址寄存器，另一寄存器作為限長寄存器（指示存儲區(qū)長度）每當(dāng)CPU要訪問主存，硬件自動將被訪問的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界如果未越界，則按此地址訪問主存，否則將產(chǎn)生程序中斷——越界中斷（存儲保護(hù)中斷）上下界寄存器保護(hù)基址、限長寄存器保護(hù)說明：并不一定為每個進(jìn)程設(shè)置單獨(dú)的硬件設(shè)備，多個進(jìn)程公用一組設(shè)備即可。第二個問題：程序裝入內(nèi)存是簡單的源代碼復(fù)制嗎？肯定不是，將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序的步驟如下：編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存如下圖所示庫鏈接程序裝入模塊裝入程序…編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存提問：為什么不能將源程序直接復(fù)制到內(nèi)存呢？編譯、鏈接到底提供了什么？在計(jì)算機(jī)中執(zhí)行程序時，CPU是根據(jù)內(nèi)存的地址來尋找指令的，而我們編寫程序時，根本不會考慮地址的問題，因此編譯、鏈接的工作是為我們源程序的每條指令設(shè)置相應(yīng)的能在內(nèi)存中使用的地址，這種問題稱為地址的映射。為了更好的理解地址映射，我們引入幾個概念：物理地址：內(nèi)存的每個存儲單元都有一個編號，這種編號稱為內(nèi)存地址或稱為物理地址，絕對地址。要求用戶用內(nèi)存地址編程是非常困難的，尤其是在多道程序設(shè)計(jì)的環(huán)境中。因此用戶編程時一般將開始位置認(rèn)為0地址，其余指令的地址都是相對于首地址而言的。邏輯地址：用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址），由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）。我們把用戶程序裝入內(nèi)存時對有關(guān)指令的地址部分的修改定義為從程序地址到內(nèi)存地址的地址映射，或稱為地址重定位。地址映射的方式有兩種：1、靜態(tài)地址映射2、動態(tài)地址映射1、靜態(tài)地址映射程序被裝入內(nèi)存時由操作系統(tǒng)的連接裝入程序完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換，程序分配到那一塊內(nèi)存，根據(jù)這塊內(nèi)存的地址對程序中的所有地址進(jìn)行修改。假定程序裝入內(nèi)存的首地址為BR，裝入前程序的邏輯地址為VR，裝入后內(nèi)存地址為MR，則地址映射按下式進(jìn)行：MR=BR+VR。例如，程序裝入內(nèi)存的首地址為1000，則裝配程序就按MR=1000+VR對程序中所有地址部分進(jìn)行修改，修改后指令LoadA，200就變?yōu)長oadA，1200地址映射LoadA12003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BR=1000靜態(tài)地址映射的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：容易實(shí)現(xiàn)，不需要硬件的支持。缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；地址變換在裝入時一次完成，以后不再改變，一旦程序裝入后不能移動；程序裝入時必須一次全部裝入內(nèi)存。2、動態(tài)地址映射動態(tài)地址映射是指把裝入模塊裝入內(nèi)存時，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。裝入內(nèi)存后的所有地址都仍是相對地址。程序真正要執(zhí)行時，利用專門的硬件機(jī)構(gòu)來完成地址的映射。

最簡單的動態(tài)地址映射硬件機(jī)構(gòu)是重定位寄存器。在地址重定位機(jī)構(gòu)中，有一個基地址寄存器BR和一個程序地址寄存器VR，一個內(nèi)存地址寄存器MR。03456......LOADA200......0100200300.........LOADA2003456110012001300200VR+1000BR動態(tài)地址映射的具體過程程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過程中，若要訪問內(nèi)存，將訪問的邏輯地址送入VR中。地址轉(zhuǎn)換機(jī)構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入MR中，作為實(shí)際訪問的地址。動態(tài)地址映射的地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行的過程中完成的，而靜態(tài)地址映射的地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行之前集中一次完成的。動態(tài)地址映射的優(yōu)點(diǎn)1、程序占用的內(nèi)存空間是動態(tài)可變的，當(dāng)程序從某個存儲區(qū)移到另一個區(qū)域時，只需要修改相應(yīng)的寄存器BR的內(nèi)容即可。2、一個程序不一定要求占用一個連續(xù)的內(nèi)存空間。3、可以部分地裝入程序運(yùn)行。4、便于多個進(jìn)程共享同一個程序的代碼。動態(tài)地址映射的缺點(diǎn)1、需要硬件的支持。2、實(shí)現(xiàn)存儲管理的軟件算法較為復(fù)雜第三個問題：多個程序在內(nèi)存中是怎樣存放的，是簡單的一個接一個嗎？這種內(nèi)存的分配方案不是不行，只是，這種分配方案效率太低，因此，內(nèi)存的分配方案有很多種，常見的有：1、連續(xù)分配方案2、基本分頁存儲管理3、基本分段存儲管理4、段頁式存儲管理第四個問題：萬一操作系統(tǒng)的程序和用戶要運(yùn)行的程序都比內(nèi)存空間大，那怎么辦，這些程序還能運(yùn)行嗎？程序肯定能夠運(yùn)行，現(xiàn)實(shí)中，由于程序員編程時不會受到限制，想寫多長就可以寫多長，但內(nèi)存空間是由硬件來決定的，計(jì)算機(jī)一旦裝好，內(nèi)存的空間不會再變，因此執(zhí)行的程序空間比內(nèi)存空間大的情況很多。為了解決這一問題，人們利用了虛擬存儲器的思想，利用覆蓋和交換技術(shù)在邏輯上對內(nèi)存進(jìn)行了擴(kuò)充?？偨Y(jié)存儲器管理的主要功能有:1、存儲保護(hù)2、地址重定位(地址映射)3、主存分配與回收4、主存擴(kuò)充(虛擬內(nèi)存)存儲器管理的主要目的是：合理安全的使用內(nèi)存，同時提高內(nèi)存空間的利用率4.2連續(xù)分配方式連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。分類：單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配動態(tài)重定位分區(qū)分配4.2.1單一連續(xù)分配最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常放在內(nèi)存低址部分，用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。而用戶區(qū)每次只裝入一個作業(yè)程序，直到該作業(yè)程序完成，才會調(diào)其它的作業(yè)程序進(jìn)入內(nèi)存。4.2.2固定分區(qū)分配將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)，這樣把用戶空間劃分為幾個分區(qū)，便允許有幾道作業(yè)并發(fā)執(zhí)行。當(dāng)有一空閑分區(qū)時，便可以再從外存的后備作業(yè)隊(duì)列中，選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時，可再從后備作業(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。說明：這種分配方法注意兩個問題：1.劃分分區(qū)的方法(1)分區(qū)大小相等：缺乏靈活性，用于一臺計(jì)算機(jī)控制多個相同對象的場合(2)分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)，可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。2.內(nèi)存分配的方法為便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)。已分配1281284已分配64643已分配32322已分配20121狀態(tài)起址(K)大小(K)分區(qū)號分區(qū)說明表作業(yè)C作業(yè)B作業(yè)A操作系統(tǒng)20K32K64K128K256K存儲空間分配情況4.2.3動態(tài)分區(qū)分配動態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動態(tài)地為之分配內(nèi)存空間,使分區(qū)的大小剛好與作業(yè)的大小相等。這種存儲管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問題。是一種較為實(shí)用的存儲管理方法。為實(shí)現(xiàn)動態(tài)分區(qū)過程，一般系統(tǒng)中需要建立兩個表：1、分區(qū)表2、可用空間表固定分區(qū)分配很容易產(chǎn)生作業(yè)與作業(yè)之間的零頭問題，引入動態(tài)分區(qū)思想。區(qū)號分區(qū)長度起始地址進(jìn)程號執(zhí)行時間120K30K1511223K50K4403316K73K2062412K89K12341、分區(qū)表用來記錄已經(jīng)分配了的分區(qū)情況2、空閑分區(qū)表：記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括分區(qū)序號、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。隨著時間的推移，也會出現(xiàn)不連續(xù)的可用空間，而且時間變，可用空間也會發(fā)生變化，所以也要對可用空間情況做一個記錄序號可用空間長度可用空間起始地址115K50K232K80K346K125K為了更好的管理空閑分區(qū)，將它們串接為一個空閑分區(qū)鏈空閑分區(qū)鏈：在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針，在分區(qū)末尾重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目。如下圖所示：引出一個問題：當(dāng)一個新作業(yè)申請裝入內(nèi)存時，需要從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)，若有若干個空閑分區(qū)都滿足條件，那應(yīng)該選擇那一個空閑分區(qū)呢？因此出現(xiàn)了幾種選擇算法：(1)首次適應(yīng)算法FF(2)循環(huán)首次適應(yīng)算法(3)最佳適應(yīng)算法(4)最壞適應(yīng)算法(1)首次適應(yīng)算法FFFF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從頭到尾不存在滿足要求的分區(qū)，則分配失敗。優(yōu)點(diǎn)：優(yōu)先利用內(nèi)存低址部分的內(nèi)存空間缺點(diǎn)：低址部分不斷劃分，產(chǎn)生小碎片；每次查找從低址部分開始，增加了查找的開銷要求:空閑區(qū)表或空閑區(qū)鏈按地址從低到高排列.(2)循環(huán)首次適應(yīng)算法在分配內(nèi)存空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)算法，需要：設(shè)置一起始查尋指針采用循環(huán)查找方式優(yōu)點(diǎn)：使內(nèi)存空閑分區(qū)分布均勻，減少查找的開銷缺點(diǎn)：缺乏大的空閑分區(qū)要求:空閑區(qū)表或空閑區(qū)鏈按地址從低到高排列.(3)最佳適應(yīng)算法所謂“最佳”是指每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。缺點(diǎn)：產(chǎn)生許多難以利用的小空閑區(qū)要求:空閑分區(qū)表或空閑分區(qū)鏈按其容量從小到大排列。(4)最壞(差)適應(yīng)算法所謂“最壞”是指每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最大的空閑分區(qū)分配給作業(yè)。缺點(diǎn)：大的空閑區(qū)不容易保留。要求:空閑分區(qū)表或空閑分區(qū)鏈按其容量從大到小排列。例：分區(qū)存儲管理算法采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中按地址順序依次有五個大小依次為15k、28k、10k、226k和110k的空閑區(qū)。現(xiàn)有五個作業(yè)Ja、Jb、Jc、Jd和Je，它們各需要內(nèi)存10k、15k、102k、26k和180k。問：⑴如果采用最先適應(yīng)分配算法，能將這五個作業(yè)按Ja~Je的次序全部裝入內(nèi)存嗎？⑵用什么分配算法裝入這5個作業(yè)可使內(nèi)存的利用率最高？110k226k10k28k15k解：(1)按最先適應(yīng)分配算法，不能將這五個作業(yè)按Ja-Je的次序全部裝入內(nèi)存。因?yàn)閮?nèi)存中前兩個原先的空閑分區(qū)能依次裝入Ja(10k)和Jb(15k)，第3個10KB的空閑區(qū)和剛剛劃分出來的兩個大小分別為5KB和13KB的空閑區(qū)均無法分配，第4個空閑區(qū)可以分2次裝入作業(yè)Jc(102k)和Jd(26k)，則作業(yè)Je(180k)無法裝入內(nèi)存。(2)用最佳適應(yīng)分配算法裝入這5個作業(yè)，可使內(nèi)存的利用率最高。此時，原先的5個空閑區(qū)依次裝入了5個作業(yè)，它們是：Jb(15k)，Jd(26k)，Ja(10k)，Je(180k)和Jc(102k)。三種分配算法的比較1、從搜索速度上看：最先適應(yīng)算法具有最佳性能。盡管最佳適應(yīng)算法或最壞適應(yīng)算法看上去能很快地找到一個最適合的或最大的空閑區(qū)，但后兩種算法都要求首先把不同大小的空閑區(qū)按其大小進(jìn)行排隊(duì)，這實(shí)際上是對所有空閑區(qū)進(jìn)行一次搜索。2、從釋放速度來看：最先適應(yīng)算法也是最佳的。因?yàn)槭褂米钕冗m應(yīng)算法回收某一空閑區(qū)時，無論被釋放區(qū)是否與空閑區(qū)相鄰，都不用改變該區(qū)在可用表或自由鏈中的位置，只需修改其大小或起始地址。3、上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對具體作業(yè)序列來分析。動態(tài)分區(qū)剛開始時，沒有存儲零頭，但隨著時間的推移，也會出現(xiàn)零頭的問題。例如：有三個存儲零頭是5k、8k、12k，有一個20k的作業(yè)，每個存儲零頭都不能滿足作業(yè)要求，但總的存儲空間是滿足的。因此要提高存儲空間的使用效率，主要是解決存儲零頭的問題，那如何解決存儲零頭問題呢？兩種方法：1、程序的浮動：將幾個空閑空間合并。2、多重分區(qū)：將一個作業(yè)撕開，分散的裝入到幾個分區(qū)中。動態(tài)分區(qū)總結(jié)4.2.4可重定位分區(qū)分配1.動態(tài)重定位的引入在連續(xù)分配方式中，必須把系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。如果在系統(tǒng)中只有若干個小分區(qū)，即使它們的容量總和大于要裝入的程序，但由于這些分區(qū)不相鄰，所以無法將程序裝入內(nèi)存。解決方法：將內(nèi)存中的所有作業(yè)進(jìn)行移動，使它們?nèi)苦徑?，這樣可把原來分散的小分區(qū)拼接成大分區(qū)，這種方法稱為“拼接”或“緊湊”。缺點(diǎn)：用戶程序在內(nèi)存中的地址發(fā)生變化，必須重定位，開銷大，移動時機(jī)不好定。20KB

0

os

作業(yè)1作業(yè)3作業(yè)4

52KB116KB166KB256KB1主存20KB

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存180KB

02.動態(tài)重定位的實(shí)現(xiàn)在動態(tài)運(yùn)行時裝入的方式時，將相對地址轉(zhuǎn)換為物理地址的工作在程序指令真正要執(zhí)行時才進(jìn)行。地址轉(zhuǎn)換需要重定位寄存器的支持。程序執(zhí)行時訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而成。地址變換過程是在程序執(zhí)行過程期間，隨著對每條指令的訪問自動進(jìn)行的，稱為動態(tài)重定位。movr1,[500]123movr1,[500]123010050059901000256k-1作業(yè)地址空間存儲空間重定位寄存器1100150016005001000相對地址+擴(kuò)充內(nèi)存的兩種方法---交換與覆蓋覆蓋技術(shù)：把程序劃分為若干個功能上相對獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域覆蓋舉例：子程序A(8k)子程序B(10k)子程序M(20k)子程序N(25k)子程序X(15k)主程序(30k)程序總共需要108k內(nèi)存空間，但在執(zhí)行的過程中A、B；X、M、N進(jìn)程不會同時執(zhí)行，因此它們有65k的內(nèi)存空間就夠用了。覆蓋技術(shù)的實(shí)現(xiàn)：把程序劃分為若干個功能上相對獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域，即就是一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間。交換技術(shù)：是指當(dāng)內(nèi)存空間緊張時，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動態(tài)調(diào)度，多用于分時系統(tǒng)中。交換技術(shù)實(shí)現(xiàn)的基本依據(jù)：程序的局部性原理。局部性原理：指程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。還可以表現(xiàn)為：時間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)（一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行）空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)。（若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用)局部性原理的具體體現(xiàn)1、程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令。2、過程調(diào)用的嵌套深度一般不超過5，因此執(zhí)行的范圍不超過這組嵌套的過程。3、程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。4、程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。交換技術(shù)與覆蓋技術(shù)共同點(diǎn)：進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換交換技術(shù)與覆蓋技術(shù)不同點(diǎn)：與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)；而且，交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。此外，覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。4.3頁式存儲管理方式連續(xù)分配方式會形成“碎片”，雖然可以通過“緊湊”解決，但開銷大。根據(jù)多重分區(qū)的思想，如果允許將一個進(jìn)程直接分散地裝入許多不相鄰的分區(qū)中，則無需“緊湊”，由此產(chǎn)生離散分配方式。分頁技術(shù)是由曼徹斯特大學(xué)提出，并于1960年前后在Atlas計(jì)算機(jī)上實(shí)現(xiàn)。這種技術(shù)對操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響。4.3.1頁面與頁表1.幾個基本概念頁面：將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片稱為頁或頁面，并為各頁加以編號，從0開始。物理塊:把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為塊或頁架。頁式管理的基本思想：在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程的若干個頁分別裝入到多個可以不相鄰的物理塊中。頁內(nèi)碎片：進(jìn)程的最后一頁經(jīng)常裝不滿而形成“頁內(nèi)碎片”。...0塊1塊2塊3塊4塊5塊6塊0頁1頁2頁3頁4頁作業(yè)的地址空間頁框（物理塊）內(nèi)存1、頁面大小的確定頁面大小應(yīng)適中，必須是2的冪，通常是512B8KB。2、頁號、頁內(nèi)地址的計(jì)算

若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P=INT[A/L]

頁內(nèi)地址d=[A]MODL例1：系統(tǒng)頁面大小為1KB，設(shè)A=2170B，計(jì)算頁號P和頁內(nèi)地址。解：P=INT

(2170/1024)=2d=2170mod1024=122頁式管理中的幾個注意問題：3.頁式存儲下內(nèi)存地址結(jié)構(gòu)位移量W頁號P3112110假設(shè)：內(nèi)存地址長度為32，且系統(tǒng)為每個頁面劃分大小為4K，則內(nèi)存地址的含義如下：地址長度共32位:011位為位移量(頁內(nèi)地址)，即每頁的大小為4KB1231位為頁號，地址空間最多允許有1M頁例如：設(shè)內(nèi)存地址線共14位，后10位表征頁的大小,前4位為頁號,則內(nèi)存的分頁情況如圖所示0000000100100011010001010110011110001001101010111100110111101111每頁大小為1K,16K的內(nèi)存分了16個頁架4.頁表的含義和地址映射中的計(jì)算在分頁系統(tǒng)中，允許進(jìn)程的每一頁離散地存儲在內(nèi)存的任一存儲塊中，為方便查找，系統(tǒng)為每一進(jìn)程建立一張頁面映像表，簡稱頁表。頁表記錄了一個進(jìn)程的各個頁對應(yīng)的頁架號，有了頁表就可以實(shí)現(xiàn)從頁號到物理塊號的地址映射。在頁表表項(xiàng)中常設(shè)置一存取控制字段，對存儲塊內(nèi)容加以保護(hù)。頁號塊號其它05存儲保護(hù)信息165…213…頁表常包含的幾個表項(xiàng)：頁號：登記程序地址空間的頁號。塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號其它：登記與存儲信息保護(hù)有關(guān)的信息如下表就是一個頁表例2：一個進(jìn)程具有有0、1、2三個頁面，對應(yīng)的頁架號為4、5、9。若系統(tǒng)頁面大小為1KB，指令load22480的邏輯地址為1200，則該指令和指令中操作數(shù)的物理地址是多少？解：1200/1024=商1余176說明該指令在第1頁中且頁內(nèi)地址為176因此，指令的物理地址=1024*5+176=52962480/1024=商2余432說明該操作數(shù)在第2頁中且頁內(nèi)地址為432因此，操作數(shù)的物理地址=1024*9+432=9648總結(jié)頁式存儲管理的過程，可得到如下結(jié)論：1、CPU每存取一個數(shù)據(jù)時，都需要進(jìn)行兩次訪問內(nèi)存。2、第一次訪問內(nèi)存：找到頁表，查找相應(yīng)指定頁的物理塊號，將塊號與頁內(nèi)偏移量拼接形成物理地址。3、第二次訪問內(nèi)存：從第一次所得地址中獲得所需數(shù)據(jù)，或向此地址中寫入數(shù)據(jù)。其過程如下圖所示：頁表長度頁表始址頁表寄存器頁內(nèi)地址頁號(3)邏輯地址L物理地址b1塊號頁號0124>+

越界中斷頁表3第一步第二步第三步第四步在上述過程中，還有兩個問題需要我們考慮：1、存儲器利用率提高了，但處理器處理速度降低了。2、現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232-264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如：一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB，則頁表中頁表項(xiàng)就有1兆（220）個之多。假設(shè)每個頁表項(xiàng)占用4個字節(jié)，僅僅其頁表就要占用4MB的內(nèi)存空間，而且還要求是連續(xù)的。第一個問題的解決方法：具有快表的地址變換機(jī)構(gòu)，即就是在系統(tǒng)中增設(shè)一個具有并行查尋能力的特殊高速緩沖寄存器，稱為“聯(lián)想寄存器”或“快表”。因?yàn)榭毂淼乃俣仁莾?nèi)存速度的數(shù)倍或數(shù)十倍，那么相對于內(nèi)存速度，訪問頁表的時間可以忽略不計(jì)。也就是說頁地址變換不會造成進(jìn)程運(yùn)行速度下降多少。其示意圖如下：頁表長度頁表始址頁表寄存器頁內(nèi)地址頁號(3)邏輯地址Ldb物理地址>+越界中斷b1塊號頁號頁表具有快表的分頁系統(tǒng)的地址變換機(jī)構(gòu)：b塊號頁號快表輸入寄存器第二個問題的解決方法：

①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：②只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時再調(diào)入。也就是說，頁表在內(nèi)存中也使用離散分裝和換進(jìn)換出的思想，以減小頁表所占內(nèi)存空間和小空間、大頁表的問題。頁表能夠分散裝入和換進(jìn)換出，一個整的頁表是很難做到的，因此引入兩級頁表和多級頁表的思想。兩級頁表：將頁表也進(jìn)行分頁，離散地將各個頁面分別存放在不同的物理塊中，同時為離散分裝的頁表再建立一張額外的頁表，稱為外層頁表，其每個頁表項(xiàng)記錄了頁表頁面的物理塊號。其示意圖如下：………012345671141151468內(nèi)存空間…641第0頁頁表012…1023115114第1頁頁表012…10231468第n頁頁表012…1023174210781011012n外部頁表兩級分頁結(jié)構(gòu)例如：一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB，則頁表中頁表項(xiàng)就有1兆（220）個之多。假設(shè)每個頁表項(xiàng)占用4個字節(jié)，僅僅其頁表就要占用4MB的內(nèi)存空間，但若采用二級頁表，頁表所占空間總數(shù)沒有變化，不過這些空間可以分為若干個小的空間，放在不連續(xù)的內(nèi)存塊中。而且當(dāng)時不用的一些小空間可暫時不調(diào)入內(nèi)存，從而使頁表所占內(nèi)存大大減小。為實(shí)現(xiàn)實(shí)現(xiàn)上述所說，在地址變換機(jī)構(gòu)中需設(shè)一外層頁表寄存器，用于存放外層頁表的始址，并利用邏輯地址中的外層頁號，作為外層頁表的索引，從中找到指定頁表分頁的始址，再利用p2作為指定頁表分頁的索引，找到指定的頁表項(xiàng)，其中即含有該頁在內(nèi)存的物理塊號，用該塊號和頁內(nèi)地址d即可構(gòu)成訪問的內(nèi)存物理地址，其示意圖如下：外部頁表寄存器外部頁表頁表db物理地址++dP2P1邏輯地址外部頁號外部頁內(nèi)地址頁內(nèi)地址具有兩級頁表的地址變換機(jī)構(gòu)：通過前面的學(xué)習(xí)，我們了解到兩級頁表的確可以解決頁表占連續(xù)內(nèi)存的問題，但同時也引入了一個新的問題，那就是兩級頁表系統(tǒng)中，CPU每存取一個數(shù)據(jù)時，都需要進(jìn)行三次訪問內(nèi)存，使得處理機(jī)的效率下降，因此前面我們所說的兩個問題都要解決，就要處理好這兩個問題之間的取舍關(guān)系。多級頁表對于32位的機(jī)器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項(xiàng)，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。對于64位的計(jì)算機(jī)，如果要求它能支持2６４(=1844744TB)規(guī)模的物理存儲空間，則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無此必要。頁式存儲管理分為兩種方式：基本分頁存儲管理：也叫實(shí)分頁式存儲管理或靜態(tài)頁式存儲管理，它是指只有作業(yè)或進(jìn)程將涉及到的所有頁面全部裝入內(nèi)存后，才會執(zhí)行。請求分頁存儲管理：也叫虛擬頁式存儲管理或動態(tài)頁式存儲管理，它是指作業(yè)或進(jìn)程執(zhí)行之前不是將作業(yè)或進(jìn)程涉及到的所有頁面全部裝入內(nèi)存，而是只裝入一部分，其它部分在執(zhí)行的過程中需要了再動態(tài)裝入。基本分頁存儲管理方式，它要求作業(yè)執(zhí)行前，必須將作業(yè)或進(jìn)程涉及到的所有頁面全部裝入內(nèi)存。這樣就有了一些限制。例如，當(dāng)內(nèi)存能提供的所有頁架的個數(shù)小于作業(yè)的頁面數(shù)時，則這個作業(yè)將永遠(yuǎn)不能執(zhí)行。而請求分頁存儲管理方式可以動態(tài)的裝入作業(yè)，不會產(chǎn)生這樣的問題。因此在現(xiàn)在的計(jì)算機(jī)系統(tǒng)中多采用請求分頁存儲管理方式來管理內(nèi)存。但請求分頁存儲管理方式同樣存在問題：1、把作業(yè)的那一部分裝入內(nèi)存比較合適？2、什么時候進(jìn)行頁面的換進(jìn)換出？3、若內(nèi)存中沒有空閑空間時，換進(jìn)換出應(yīng)換掉那一個頁面？解決問題：1、把作業(yè)的那一部分裝入內(nèi)存比較合適？當(dāng)然應(yīng)該將馬上要運(yùn)行的頁面先裝入內(nèi)存，其它的可先放在外存中等待換進(jìn)換出。2、什么時候進(jìn)行頁面的換進(jìn)換出？兩種策略：①請求調(diào)入策略：即執(zhí)行時缺少頁了，就中斷調(diào)入。②預(yù)調(diào)入策略：將外存中的頁提前計(jì)算一個時間順序，按此順序進(jìn)行調(diào)入。3、若內(nèi)存中沒有空閑空間時，換進(jìn)換出應(yīng)換掉那一個頁面？三種算法：①先進(jìn)先出頁面置換算法（FIFO）②最近最久未使用置換算法（LRU）③理想淘汰置換算法（OPTIMAL）為了說明這三種算法，我們先來看一個例題：例：設(shè)某作業(yè)占有7個頁面，如果在主存中只允許裝入4個工作頁面，作業(yè)運(yùn)行時，實(shí)際訪問頁面的順序是1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。試用FIFO、LRU與OPTIMAL頁面調(diào)度算法，列出各自的頁面淘汰順序和缺頁中斷次數(shù)123647321475652111111444444455555222227777777666633333322222222246666611111111缺**********解：（1）fifo頁面調(diào)度算法如上表所示，缺頁的順序?yàn)椋?236472156缺頁的次數(shù)：10次123647321475652111111444411116666222227777444442233333333377777146666222255555缺**************（2）lru頁面調(diào)度算法如上表所示，缺頁的順序?yàn)椋?2364721475621缺頁的次數(shù)：14次（2）OPTIMAL頁面調(diào)度算法123647321475652111111111111111111222222222222222233333333444666646477777755555缺*********如上表所示，缺頁的順序?yàn)椋?23647456缺頁的次數(shù)：9次總結(jié)請求分頁存儲管理方式：1、基本思想：在基本分頁（實(shí)分頁）的基礎(chǔ)上增加虛擬存儲功能。

進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入幾個或零個頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面2、頁表結(jié)構(gòu)：同基本分頁管理方式一樣，為了將用戶程序地址空間中的邏輯地址變換為內(nèi)存空間中具體內(nèi)存塊的物理地址。在請求分頁系統(tǒng)中也需要頁表。只不過頁表的結(jié)構(gòu)發(fā)生了變化，其具體結(jié)構(gòu)如下：頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存。(2)訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的

次數(shù)，或記錄本頁最近已有多長時間未被訪問。(3)修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。

問題：考慮為什么要有這一項(xiàng)？(4)外存地址：用于指出該頁在外存上的地址。其中：3、系統(tǒng)中應(yīng)該有缺頁中斷機(jī)構(gòu)在請求分頁系統(tǒng)中，每當(dāng)要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。此時應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）如果內(nèi)存中有空閑塊，則分配一個塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目若此時內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）問題：缺頁中斷同一般中斷的區(qū)別？相同點(diǎn)：缺頁中斷作為中斷，同樣需要經(jīng)歷諸如保護(hù)CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理、恢復(fù)CPU環(huán)境等幾個步驟。不同點(diǎn)：缺頁中斷是一種特殊的中斷，與一般中斷有明顯區(qū)別：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。4、系統(tǒng)中的地址變換機(jī)構(gòu)有所改進(jìn)請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)，是在基本分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)虛擬存儲器而增加了某些功能而形成的。如：能夠產(chǎn)生和處理缺頁中斷，以及具有從內(nèi)存中換出一頁的功能等等。其過程如下圖所示：5、系統(tǒng)為進(jìn)程分配內(nèi)存時，內(nèi)存的分配策略和分配算法，主要涉及三個問題：（1）最小物理塊數(shù)的確定（2）物理塊的分配策略（3）物理塊的分配算法（1）最小物理塊數(shù)的確定最小物理塊數(shù)，是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最小物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。對于某些簡單機(jī)器，若是單地址指令且采用直接尋址方式，最小物理塊數(shù)應(yīng)為2，如果該機(jī)器允許間接尋址，則至少要求3個物理塊。對于某些功能較強(qiáng)的機(jī)器，指令長度可能是兩個或兩個以上字節(jié)，至少要為進(jìn)程分配6個物理塊。（2）物理塊的分配策略在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，也可以采取兩種策略，即全局置換和局部置換。于是可以組合出三種適合的策略。Ⅰ、固定分配局部置換基于進(jìn)程的類型，或根據(jù)程序員、程序管理員的建議，為每個進(jìn)程分配一定數(shù)目的物理塊，在整個運(yùn)行期間不再改變。采用該策略時，如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁，只能從該進(jìn)程在內(nèi)存中的n個頁面中選出一頁換出，然后再調(diào)入一頁。Ⅱ、可變分配全局置換在采用這種策略時，先為系統(tǒng)中的每個進(jìn)程分配一定數(shù)目的物理塊，而OS自身也保持一個空閑的物理塊隊(duì)列。如果某進(jìn)程發(fā)生缺頁時，由系統(tǒng)從空閑的物理塊隊(duì)列中，取出一個物理塊分配給該進(jìn)程，并將欲調(diào)入的頁裝入其中。Ⅲ、可變分配局部置換基于進(jìn)程的類型，或根據(jù)程序員的要求，為每個進(jìn)程分配一定數(shù)目的物理塊，如果某進(jìn)程發(fā)生缺頁時，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，不會影響其他進(jìn)程執(zhí)行。如果進(jìn)程在運(yùn)行中頻繁發(fā)生缺頁中斷，則系統(tǒng)再為進(jìn)程分配若干物理塊；如果進(jìn)程在運(yùn)行中缺頁率特別低，則適當(dāng)減少分配給該進(jìn)程的物理塊。（3）物理塊分配算法在采用固定分配策略時，如何將系統(tǒng)中可供分配的物理塊分配給各個進(jìn)程，可采用以下幾種算法：(1)平均分配算法將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(jìn)程。缺點(diǎn)：未考慮各進(jìn)程本身的大小。(2)按比例分配算法根據(jù)進(jìn)程的大小按比例分配物理塊。假設(shè)系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi，將有：注意：b應(yīng)該取整，而且必須大于最小物理塊數(shù)。(3)考慮優(yōu)先權(quán)的分配算法以上兩種算法可以完成物理塊的分配，但沒有考慮到各個作業(yè)的輕重緩急程度。在實(shí)際應(yīng)用中，為了照顧重要的、急迫的作業(yè)盡快完成，應(yīng)為它分配較多的內(nèi)存空間。方法：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。6、請求分頁存儲管理方式中頁面大小的確定頁面太大：頁的碎片多，缺頁的機(jī)率提高頁面太小：頁表占用的內(nèi)存空間會增大頁面大小如何確定呢？我們來看一個例題。例：設(shè)內(nèi)存大小為M，作業(yè)的平均尺寸為J，一個頁表項(xiàng)占一個單位，問最佳的頁面尺寸P應(yīng)該為多少？解：最佳頁面尺寸也就是空間浪費(fèi)最小的尺寸。在這我們認(rèn)為所有作業(yè)的平均頁內(nèi)碎片的大小為P/2則系統(tǒng)中浪費(fèi)空間的函數(shù)為：把它看作是P的函數(shù)，因此有我們希望Y越小越好，則計(jì)算得：即：7、調(diào)頁策略1.何時調(diào)入頁面1）預(yù)調(diào)頁策略采用以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計(jì)在不久之后便會被訪問的頁面，預(yù)先調(diào)入內(nèi)存。目前預(yù)調(diào)頁的成功率僅為50%,主要用于進(jìn)程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào)入哪些頁。2）請求調(diào)頁策略當(dāng)程序在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由OS將其所需要的頁面調(diào)入內(nèi)存。優(yōu)點(diǎn)：由請求調(diào)頁策略所確定調(diào)入的頁，一定會被訪問；請求調(diào)頁策略比較容易實(shí)現(xiàn)。缺點(diǎn)：每次僅調(diào)入一頁，需花費(fèi)較大的系統(tǒng)開銷，增加了磁盤I/O的啟動頻率2.從何處調(diào)入頁面在請求分頁系統(tǒng)中的外存分為文件區(qū)和對換區(qū)。每當(dāng)發(fā)生缺頁時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成三種情況：系統(tǒng)擁有足夠的對換區(qū)空間：可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。系統(tǒng)缺少足夠的對換區(qū)空間：凡不會被修改的文件，直接從文件區(qū)調(diào)入；換出時不用換，再調(diào)入時仍從文件區(qū)調(diào)入。可能被修改的部分，換出時需調(diào)到對換區(qū)，換入時從對換區(qū)調(diào)入。3.頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。主要過程如下：1、缺頁中斷2、查找頁表，找到該頁在外存的物理塊3、調(diào)入并修改頁表4、如果內(nèi)存已滿，按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出5、再把做缺的頁面調(diào)入內(nèi)存，修改頁表中的相應(yīng)表項(xiàng)8、頁面置換算法概念：在進(jìn)程運(yùn)行過程中，若其訪問的頁面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時，需從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換區(qū)。但應(yīng)將哪個頁面調(diào)出，需根據(jù)一定的算法來確定。把選擇換出頁面的算法稱為頁面置換算法，其好壞直接影響系統(tǒng)的性能。一個好的置換算法應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不會再訪問的頁面換出，或者把那些在較長時間內(nèi)不會再訪問的頁面換出。常見的幾種頁面置換算法最佳置換算法（Optimal)先進(jìn)先出頁面置換算法（FIFO）最近最久未使用置換算法（LRU）簡單Clock置換算法（最近未用算法NRU）改進(jìn)型Clock置換算法最少使用置換算法（LFU)頁面緩沖算法1.最佳置換算法其所選擇的被淘汰頁面，將是以后永不再用的，或者是在最長(未來)時間內(nèi)不再被訪問的頁面。優(yōu)點(diǎn)：保證獲得最低的缺頁率缺點(diǎn)：無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面，哪個在未來最長時間內(nèi)不再被訪問。算法無法實(shí)現(xiàn)，但可評價其他算法2.先進(jìn)先出置換算法算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。算法實(shí)現(xiàn)簡單，只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針(替換指針)，使它總是指向最老的頁面。算法與進(jìn)程的實(shí)際運(yùn)行規(guī)律不相適應(yīng)，因?yàn)檫M(jìn)程中的某些頁面經(jīng)常被訪問，但先進(jìn)先出置換算法不能保證這些頁面不被淘汰。先進(jìn)先出置換算法最直觀，但其性能較差，故應(yīng)用極少。3、

LRU置換算法的描述算法根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當(dāng)需淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。LRU置換算法雖然較好，但如何能具體實(shí)現(xiàn)這個算法呢？最容易想到，也最簡單的方法：計(jì)時法。給頁表中的每一頁增加一個域，專門用來存放計(jì)時標(biāo)志，用來記錄該頁面自上次被訪問以來所經(jīng)歷的時間。頁面每被訪問一次，計(jì)時清0。要裝入新頁時，從內(nèi)存的頁面中選出時間最長的一頁，調(diào)出，同時把各頁的計(jì)時標(biāo)志全部清0，重新開始計(jì)時。計(jì)時法可以稍作改變，成為計(jì)數(shù)法：頁面被訪問，計(jì)數(shù)標(biāo)志清0，其余所有內(nèi)存頁面計(jì)數(shù)器加1；要裝入新頁時，選出計(jì)數(shù)最大的一頁調(diào)出，同時所有計(jì)數(shù)器清0。這兩種方法確實(shí)很簡單，但運(yùn)行效率卻不盡如人意。每個時刻，或是每調(diào)用一個頁面，就需要對內(nèi)存中所有頁面的訪問情況進(jìn)行記錄和更新，麻煩且開銷相當(dāng)大。另一種實(shí)現(xiàn)的方法：鏈表法。操作系統(tǒng)為每個進(jìn)程維護(hù)一條鏈表，鏈表的每個結(jié)點(diǎn)記錄一張頁面的地址。調(diào)用一次頁面，則把該頁面的結(jié)點(diǎn)從鏈中取出，放到鏈尾；要裝入新頁，則把鏈頭的頁面調(diào)出，同時生成調(diào)入頁面的結(jié)點(diǎn)，放到鏈尾。鏈表法可看作簡單計(jì)時/計(jì)數(shù)法的改良，維護(hù)一個鏈表，自然要比維護(hù)所有頁面標(biāo)志要簡單和輕松。可是，這并沒有在數(shù)量級上改變算法的時間復(fù)雜度，每調(diào)用一個頁面，都要在鏈表中搜尋對應(yīng)結(jié)點(diǎn)并放至鏈尾的工作量并不算小。前面幾種方法都是單純使用軟件實(shí)現(xiàn)的算法。我們知道，硬件的速度比軟件的速度要快的多，因此如果能有特殊的硬件幫忙，我們可以得到更有效率的算法。常用硬件的方法有兩種：1、寄存器2、棧1）寄存器為每個在內(nèi)存中的頁面配置一個移位寄存器，用來記錄某進(jìn)程在內(nèi)存中各頁的使用情況。移位寄存器表示為R=RnRn-1Rn-2…R2R1則：在一個有n個頁框的機(jī)器中，寄存器就構(gòu)成了一個n*n的矩陣，開始時所有位的初始值都是0。訪問到第k頁時，硬件把k行的位全設(shè)為1，之后再把k列的位置設(shè)為0。不難證明，在任意時候，二進(jìn)制值最小的行即為最久未使用的頁面，當(dāng)調(diào)換頁面時，將其調(diào)出。

例：一個作業(yè)的共有5個頁面，訪問次序?yàn)?、1、4、3、5，用寄存器法來驗(yàn)證每次置換時內(nèi)存中的最近最久未使用的頁面。000000000000000000000000011111000001111100000111110000011111111110000000000初始情況54321123452）棧利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。6444774700407740711471004701147012247021147012270126設(shè)一進(jìn)程訪問頁面的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6隨著進(jìn)程的訪問，棧中頁面號的變化情況：4、clock置換算法LRU算法是比較好的算法，但需要硬件的支持，因此實(shí)際中多采用LRU算法的近似算法。算法步驟：1、每頁增設(shè)一個訪問位,訪問過的頁面訪問位置12、將內(nèi)存中的頁鏈成一個循環(huán)隊(duì)列,查詢指針循環(huán)移動其過程圖如下：入口查尋指針前進(jìn)一步指向下一個表目訪問位=0?選擇該頁淘汰返回訪問位置0YF例題說明三種算法：5、改進(jìn)型Clock算法Clock算法加上置換代價(盡量選擇未修改過的頁面淘汰)每頁有訪問頁u和修改位mu=0m=0未用過,未修改過,最佳淘汰頁面u=0m=1未用過,但改過,不是最佳淘汰頁面u=1m=0最近用過,但未被修改,可能被再次使用u=1m=1最近用過,被修改過,可能被再次使用算法需要重復(fù)多次Clock算法從當(dāng)前位置找u=0,m=0的頁面,有則淘汰否則第二遍找u=0,m=1的頁面,同時將u置為0,有則淘汰否則第三遍找u=0,m=0的頁面,有則淘汰否則第四遍找u=0,m=1的頁面,(肯定會找到)6、其它置換算法1、最少使用置換算法(LFU)2、頁面緩沖算法(PBA)

最后，我們再來考慮一個問題，分配的頁架數(shù)越多，作業(yè)執(zhí)行的速度是不是越快呢？例：假設(shè)進(jìn)程P共有5頁，程序訪問內(nèi)存的順序?yàn)?，2，3，4，1，2，5，1，2，3，4，5。當(dāng)分配到的頁架數(shù)是3和4時，利用FIFO算法求出其缺頁次數(shù)？12341251234511114445555552

222111113333

3332222244缺*******

**

解：頁架數(shù)為三時，其缺頁情況如下：頁面數(shù)＝3缺頁次數(shù)＝9缺頁率＝75％

12341251234511111115555442

222222111153

33333322224

444444333缺****

******頁架數(shù)為四時，其缺頁情況如下：頁面數(shù)＝4

缺頁次數(shù)＝10缺頁率=83.3％

Belady現(xiàn)象

是指在使用FIFO算法進(jìn)行內(nèi)存頁面置換時，在未給進(jìn)程或作業(yè)分配足它所要求的全部頁面的情況下，有時出現(xiàn)的分配的頁面數(shù)增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象。

到此我們對分頁存儲管理方式有了一個全面的了解，分頁管理方式的主要思路就是將一個作業(yè)分為大小相同的若干個頁，然后將它們離散的分裝在內(nèi)存中的頁架上。頁式管理方式很好的解決了碎片的問題，但同時也存在著一個這樣的問題：那就是一個作業(yè)能不能隨意的分開呢？如果要分的地方偏偏不能分怎么辦？因此我們提出了段式存儲管理的思想。我們知道，一個大的程序可以分解為若干個小的功能完整的子函數(shù)（程序）段，對于整個作業(yè)來說，一個子函數(shù)段在邏輯上是完整的，是可分的。因此我們采用動態(tài)分區(qū)的方式將一個作業(yè)的子函數(shù)段離散的分裝在內(nèi)存中，就不會出現(xiàn)剛在我們在分頁管理中分頁時考慮的能不能分的問題。這種將大的作業(yè)按照子函數(shù)段離散分裝在內(nèi)存中的思想就是段式存儲的思想。主程序main函數(shù)庫sin棧stack動態(tài)數(shù)組array變量集data程序員眼中的一個程序一個程序由若干部分(段)組成，每個段有各自的特點(diǎn)、用途!通常在操作系統(tǒng)中還用段號代替段名。0213因此分段管理中每一條指令的地址其實(shí)都是一個二維地址，橫向找到段，從向找到段內(nèi)偏移地址。分段管理方式中各段裝入內(nèi)存的情況如下：01230213總結(jié)段式存儲管理的基本原理1.用戶程序的劃分在分段存儲管理方式中，作業(yè)地址空間被劃分為若干個段，每個段定義了一組邏輯信息，都有自己的名字（稱為段名），通常還用段號代替段名。每段從0開始編址，并采用一段連續(xù)地址空間。段長由邏輯信息組的長度決定。一個段的邏輯地址由段號(段名)和段內(nèi)地址所組成。2.內(nèi)存劃分內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定3.內(nèi)存分配分段式存儲管理的實(shí)現(xiàn)是基于動態(tài)分區(qū)存儲管理的原理。系統(tǒng)為每個分段分配一個連續(xù)的分區(qū)，而進(jìn)程中的各個段可以離散地裝入內(nèi)存中不同的分區(qū)中。段式存儲管理中的數(shù)據(jù)結(jié)構(gòu)--段表在段式存儲管理中，為使操作系統(tǒng)清楚了解內(nèi)存分配情況，須在系統(tǒng)中為每個進(jìn)程建立一張段映射表，簡稱“段表”。每個段在表中占有一個表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址(段基址)和段的長度。有了段表就可以實(shí)現(xiàn)從邏輯地址到內(nèi)存物理地址的映射。0213一個進(jìn)程需要記錄多個基址…基址長度保護(hù)段號180K150KR0360K60KR/W170K110KR/W2460K40KR3進(jìn)程段表01230K70K180K330K360K420K460K500K系統(tǒng)區(qū)段表長度段表始址段表寄存器物理地址>+越界中斷分段系統(tǒng)的地址變換機(jī)構(gòu)1002段號S位移量W段表92002008K5004K6006K1K段長基址段號0123+82928K82928692主存通過上圖我們可以看出分段管理方式與分頁管理方式有著同樣的問題，那就是：段式存儲管理中，因?yàn)榇嬖诙伪恚瑫r段表存放在內(nèi)存中，所以分段管理方式中每訪問一個數(shù)據(jù)，也需兩次訪問內(nèi)存，降低了計(jì)算機(jī)的速率。解決方法：設(shè)置聯(lián)想寄存器（快表），用于保存最近常用的段表項(xiàng)。這樣,比起沒有地址變換的常規(guī)存儲器的存取速度來僅慢約10%～15%.分頁和分段的主要區(qū)別相似點(diǎn)：采用離散分配方式，通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換不同點(diǎn)：頁是信息的物理單位，分頁是為了滿足系統(tǒng)的需要,可以提高內(nèi)存的利用率，但可能破壞程序的邏輯關(guān)系；段是信息的邏輯單位，含有一組意義相對完整的信息，分段是為了滿足用戶的需要。頁的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁號和頁內(nèi)地址，由機(jī)器硬件實(shí)現(xiàn)；段的長度不固定，取決于用戶程序，編譯程序?qū)υ闯绦蚓幾g時根據(jù)信息的性質(zhì)劃分。分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二