..1．2例題精選例1.1如何理解虛擬機的概念？解:一臺僅靠由硬件組成的計算機一般被稱為裸機,不易使用。操作系統(tǒng)為用戶使用計算機提供了許多服務,從而把一臺難于使用的裸機改造成了功能更強大、使用更方便的計算機系統(tǒng),這種計算機系統(tǒng)稱為虛擬機。所謂虛擬,是指把一個物理上的實體變?yōu)槿舾蓚€邏輯上的對應物。前者是實際存在的,而后者是虛的,只是用戶的一種感覺。在單CPU的計算機系統(tǒng)中能同時運行多道程序,好像每個程序都獨享一個CPU,這就是虛擬。在構造操作系統(tǒng)時,把操作系統(tǒng)分成若干層,每層完成特定的功能,從而形成一個虛擬機。下層的虛擬機為上層的虛擬機提供服務,這樣逐次擴充以完成操作系統(tǒng)的功能。討論"虛擬"的概念體現(xiàn)在操作系統(tǒng)的方方面面。例如,虛擬存儲器,使一臺只有4MB內存的計算機可以運行總容量遠遠超過4MB的程序；虛擬外設,能夠使多個用戶同時訪問該外設等。例1.2什么是多道程序設計,它的主要優(yōu)點是什么？解:所謂多道程序設計是指把一個以上的程序存放在內存中,并且同時處于運行狀態(tài),這些程序共享CPU和其他計算機資源。其主要優(yōu)點是：〔1CPU的利用率高：在單道程序環(huán)境下,程序獨占計算機資源,當程序等待I／O操作時CPU空閑,造成CPU資源的浪費。在多道程序環(huán)境下,多個程序共享計算機資源,當某個程序等待I／O操作時,CPU可以執(zhí)行其他程序,這大大地提高了CPU的利用率?！?設備利用率高：在多道程序環(huán)境下,內存和外設也由多個程序共享,無疑也會提高內存和外設的利用率。〔3系統(tǒng)吞吐量大：在多道程序環(huán)境下,資源的利用率大幅度提高,減少了程序的等待時間,提高了系統(tǒng)的吞吐量。討論多道程序在計算機中并發(fā)地運行是現(xiàn)代計算機系統(tǒng)的重要特征。早期的單道批處理系統(tǒng)與人工操作相比自動化程度大大提高,但系統(tǒng)中仍有較多的空閑資源,系統(tǒng)的性能較差。多遭批處理系統(tǒng)雖有很多優(yōu)點,但這種系統(tǒng)交互能力差,作業(yè)的平均周轉時間長。多道程序處理系統(tǒng)要解決的主要問題是,如何使多個程序合理、有序地共事處理機、內存、外設等資源。例1.3A,B兩個程序,程序A按順序使用CPU10S,使用設備甲5S,使用CPU5S,使用設備乙10S,最后使用CPU10S。程序B按順序使用設備甲10S,使用CPU10S,使用設備乙5S,使用CPU5S,使用設備乙10S?！埠雎哉{度程序執(zhí)行時間試問：〔1在順序環(huán)境下執(zhí)行程序A和程序B,CPU的利用率是多少？〔2在多道程序環(huán)境下,CPU的利用率是多少？解〔1程序A和程序B順序執(zhí)行時,程序A執(zhí)行完畢,程序B才開始執(zhí)行。兩個程序共耗時80S,其中占用CPU時間為40S,順序執(zhí)行時CPU的利用率為50％。〔2在多道程序環(huán)境下,兩個程序并發(fā)執(zhí)行,其執(zhí)行情況如圖所示?？梢钥闯?兩個程序共耗時45S,其中占用CPU時間為40S,故此時CPU的利用率為40/45=88.89％。討論<1>在單道程序環(huán)境下,程序順序執(zhí)行,CPU被一道程序獨占,即使CPU空閑,其他程序也不能使用,所以CPU的利用率低。〔2在多道程序環(huán)境下,若干個程序宏觀上同時執(zhí)行,微觀上交替執(zhí)行。當其中一個程序由于某種原因〔例如進行1／O操作而不能占用CPU時,其他程序就可以占用CPU,提高了CPU的利用率?！?在該例中,當程序A使用完設備甲時,由于CPU正被程序B占用,所以程序A必須等待一段時間〔如虛線所示。同理,當程序B第二次使用完CPU準備使用設備動時,由于此時設備乙正被程序A占用,所以程序B也必須等待一段時間〔如虛線所示,這時CPU將空閑〔如虛線所示。例1.4試述分時系統(tǒng)與實時系統(tǒng),并比較它們的區(qū)別。解:分時系統(tǒng)是指在一個系統(tǒng)中多個用戶分時地使用同一計算機。實時系統(tǒng)是指計算機及時響應外部事件的請求,在規(guī)定時限內完成對該事件的處理,并控制所有實時設備和實時任務協(xié)調一致地運行。實時系統(tǒng)與分時系統(tǒng)的主要區(qū)別有兩點。<1>分時系統(tǒng)的目標是提供一種通用性很強的系統(tǒng),有較強的交互能力,而實時系統(tǒng)則大都是具有特殊用途的專用系統(tǒng),交互能力略差；〔2分時系統(tǒng)對響應時間雖有要求,但一般來說,響應時間由人所能承受的等待時間來確定；而實時系統(tǒng)對響應時間要求更高,一般由控制系統(tǒng)或信息處理系統(tǒng)所能接受的延遲時間來決定。1．3習題填空題：當CPU執(zhí)行操作系統(tǒng)代碼時,稱處理機處于〔A執(zhí)行態(tài)〔B目態(tài)〔C管態(tài)〔D就緒態(tài)在下列性質中,不是分時系統(tǒng)的特征?！睞多路性〔B交互性〔C獨占性〔D成批性下列僅一條指令只能在管態(tài)下執(zhí)行。〔A讀取時鐘指令〔B訪管指令〔C屏蔽中斷指令〔D取數(shù)指令何謂管態(tài)〔系統(tǒng)態(tài)和目態(tài)〔用戶態(tài)？一般從哪幾方面對操作系統(tǒng)的性能進行評價？試說出幾種你所熟悉的操作系統(tǒng)名稱,并說明其特征。試列舉UNIX操作系統(tǒng)的特點。根據(jù)你使用計算機系統(tǒng)的經(jīng)驗,說明操作系統(tǒng)的作用。試說明批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)的主要特征。如何理解網(wǎng)絡操作系統(tǒng)的主要功能？A,B兩個程序,A按順序使用CPU10s,使用設備甲5s,使用CPU5s,使用設備乙10s,最后使用CPU10s;程序B按順序使用設備甲10s,使用CPU10s,使用設備乙5s,使用CPU5s,最后使用設備乙10s。請問：在順序執(zhí)行程序A和B時,CPU的利用率是多少？在多道程序環(huán)境下執(zhí)行時,CPU的利用率是多少？例題：考慮5個進程P1,P2,P3,P4,P5,見表2.1。規(guī)定進程的優(yōu)先數(shù)越小,優(yōu)先級越高。試描述在采用下述幾種調度算法時各個進程運行過程,并計算采用每種算法時的進程平均周轉時間。假設忽略進程的調度時間?！?先來先服務調度算法；〔2時間片輪轉調度算法〔時間片為1ns；進程創(chuàng)建時間運行時間優(yōu)先數(shù)進程創(chuàng)建時間運行時間優(yōu)先數(shù)P1033P2265P3441P4652P5824練習題單選題一個進程是?！睬迦A大學1996A由協(xié)處理機執(zhí)行的一個程序B一個獨立的程序+數(shù)據(jù)集CPCB結構與程序和數(shù)據(jù)的組合D一個獨立的程序并發(fā)進程之間。A彼此無關B必須同步C必須互斥D可能需要同步或互斥3、是進程調度算法。A時間片輪轉法B先來先服務C響應比高者優(yōu)先D均衡調度算法4、當時,進程從執(zhí)行扎轉變?yōu)榫途w狀態(tài)?！参鞅惫ご?999A進程被調度程序選中B時間片到C等待某一事件D等待的事件發(fā)生5、系統(tǒng)中有n〔n>2個進程,并且當前沒有執(zhí)行進程調度程序,則不可能發(fā)生。A有一個運行進程,沒有就緒進程,剩下的n-1個進程處于等待狀態(tài)B有一個運行進程和n-1個就緒進程,但沒有進程處于等待狀態(tài)C有一個運行進程和1個就緒進程,剩下的n-2個進程處于等待狀態(tài)D沒有運行進程但有2個就緒進程,剩下的n-2個進程處于等待狀態(tài)6、支持多道程序設計的操作系統(tǒng)在運行過程中,不斷地選擇新進程運行來實現(xiàn)CPU的共享,但其中不是引起操作系統(tǒng)選擇新進程的直接原因?！矎偷┐髮W1999A運行進程的時間片用完B運行進程出錯C運行進程要等待某一事件的發(fā)生D有新進程進入就緒狀態(tài)判斷題在剝奪式進程管理方式下,現(xiàn)運行進程的優(yōu)先級不低于系統(tǒng)中所有進程的優(yōu)先級。進程是一個獨立的運行單位,也是系統(tǒng)進行資源分配和調度的基本單位。程序的并發(fā)執(zhí)行是指同一時刻有兩個以上的程序,它們的指令在同一處理器上執(zhí)行。進程由進程控制塊和數(shù)據(jù)集以及對該數(shù)據(jù)集進行操作的程序段組成。并發(fā)是并行的不同表述,其原理相同。問答題操作系統(tǒng)中為什么要引入進程的概念？為了實現(xiàn)進程的并發(fā)運行,操作系統(tǒng)在進程管理方面應做那些工作？〔XX大學1997試比較進程與程序的區(qū)別。〔XX工業(yè)大學2000進程與線程的主要區(qū)別是什么？〔西北工大1999例:假設某系統(tǒng)中有4種資源〔R1,R2,R3,R4,在某時刻系統(tǒng)中共有5個進程。進程P1,P2,P3,P4,P5的最大資源需求數(shù)向量和此時已分配到的資源數(shù)向量分別為進程 當前已分配到資源 最大資源需求P1〔0,0,1,2 〔0,0,1,2p2 〔2,0,0,0 〔2,7,5,0P3 〔0,0,3,4 〔6,6,5,6P4 〔2,3,5,4 〔4,3,5,6P5 〔0,3,3,2 〔0,6,5,2系統(tǒng)中當前可用資源向量為〔2,1,0,0。問：〔1當前系統(tǒng)是否是安全的？〔2如果進程3已發(fā)出資源請求向量〔0,1,0,0,系統(tǒng)能否將資源分配給它？..解：〔1進程的最大資源需求數(shù)減去當前進程已獲得的資源數(shù)就是進程仍需的資源數(shù)。此時各個進程的仍需資源數(shù)向量為P1：〔0,0,0,0P2：〔0,7,5,0P3：〔6,6,2,2P4：〔2,0,0,2P5：〔0,3,2,0而系統(tǒng)的可用資源向量為〔2,1,0,0,這時存在如下進程執(zhí)行序列,可以使進程順利執(zhí)行完畢,所以該狀態(tài)是安全的。進程 可用資源數(shù)P1完成后：〔2,1,1,2P4完成后：〔4,4,6,6P5完成后：〔4,7,9,8P2完成后：〔6,7,9,8P3完成后：〔6,7,12,12..〔2在P3發(fā)出資源請求〔0,1,0,0后,假設系統(tǒng)把資源分配給P3,則各進程已分配資源數(shù)為P1：〔0,0,1,2P2：〔2,0,0,0P3：〔0,1,3,4P4：〔2,3,5,4P5：〔0,3,3,2這時系統(tǒng)可用資源數(shù)為〔2,0,0,0,各個進程仍需資源向量為P1：〔0,0,0,0P2：〔0,7,5,0P3：〔6,5,2,2P4：〔2,0,0,2P5：〔0,3,2,0..滿足資源需求的進程執(zhí)行序列為 進程可用資源數(shù)P1完成后：〔2,0,1,2P4完成后：〔4,3,6,6P5完成后：〔4,6,9,8此時可用資源已不能滿足P2或P3的需求,即此時系統(tǒng)狀態(tài)是不安全的,系統(tǒng)將拒絕資源請求。討論銀行家算法的關鍵是尋找一個進程的運行序列,如果系統(tǒng)按該序列調度進程運行,系統(tǒng)的可用資源就可以滿足它們的需求,這時資源分配是安全的；否則,若該進程序列不存在,則資源分配是不安全的,系統(tǒng)暫不進行資源分配。生產(chǎn)者和消費者問題1、有n個緩沖區(qū),一個生產(chǎn)者和一個消費者情況：main<>{intS=1;//可否進入緩沖區(qū)intfull=0;//產(chǎn)品數(shù)目intempty=n//可用緩沖區(qū)數(shù)intbuffer[n];intin=0;//指向下一個可放產(chǎn)品的緩沖區(qū)intout=0;//指向下一個可取產(chǎn)品的緩沖區(qū)producer<>;consumer<>;}producer<>{While<生產(chǎn)未結束>{produceaproductP<empty>;P<S>;Buffer[in]=product;in=<in+1>modn;V<S>;V<full>;}}consumer<>{While<消費未結束>{P<full>;P<S>;TakeaproductfromBuffer[out]Out=<out+1>modn;V<S>;V<empty>;}Consumetheproduct}2、m個生產(chǎn)者和k個消費者共享n個緩沖區(qū)的情況：main<>{intB[n];//緩沖區(qū)intp=r=0;//p表示生產(chǎn)者指針,r表示消費者指針intS=1;//可否進入緩沖區(qū)intfull=0;//產(chǎn)品數(shù)目intempty=n;//可用緩沖區(qū)數(shù)producer-i<i=1,2,…,m>;consumer-j<j=1,2,…,k>;}Producer-i<i=1,2,…,m>{while<producingdoesnotend>{produceaproductP<empty>;P<S>;B[p]=product;p=<p+1>modn;//每放入一個產(chǎn)品,位置指針后移一位V<S>;V<full>;}}Consumer-j<j=1,2,…,k>{while<continuetoconsume>{P<full>;P<S>;TakeaproductfromB[r]r=<r+1>modn;//從第一個開始,消費一個后,指向下一個V<S>;V<empty>;Consume}}讀者與寫者問題讀者與寫者有相同的優(yōu)先級的情況：main<>{intS=1;//讀者與寫者,寫者與寫者間的互斥,即可否修改文件intSr=1;//可否修改讀者個數(shù)intrc=0;//讀者個數(shù)reader<>;writer<>;}reader<>{While<讀過程未結束>{P<Sr>;if<rc==0>{P<S>;rc=rc+1;V<Sr>;readfileF}else{rc=rc+1;V<Sr>;readfileF}P<Sr>;rc=rc-1;if<rc==0>V<S>;V<Sr>;}}writer<>{While<寫過程未結束>{P<S>;WritefileFV<S>;}}2、寫者優(yōu)先問題：main<>{intS=1;//讀者與寫者,寫者與寫者間的互斥,即可否修改文件intSn=n;//最多有n個進程可以同時進行讀操作reader<>;writer<>}reader<i>{P<S>;P<Sn>;V<S>;ReadfileFV<Sn>;}writer<j>{P<S>WritefileFV<S>;}例題有一個閱覽室,讀者進入時必須先在一張登記表上進行登記。該表為每一座位列出一個表目,包括座號、姓名。讀者離開時要撤消登記信息。閱覽室有100個座位,試問：為描述讀者的動作,應編寫幾個程序？,應該設置幾個進程？進程和程序之間的關系如何？試用P、V操作描述這些進程之間的同步算法。若系統(tǒng)有某類資源m*n+1個,允許作業(yè)執(zhí)行過程中動態(tài)申請該類資源,但在該系統(tǒng)上運行的每一個作業(yè)對該類資源的占有量在任一時刻都不會超過m+1個。當作業(yè)申請資源時,只要資源尚未分配完,則總能滿足它的要求。但用限制系統(tǒng)中可同時執(zhí)行的作業(yè)個數(shù)來防止死鎖。你認為作業(yè)調度允許同時執(zhí)行的最大作業(yè)數(shù)應為多少？證明之。3、若系統(tǒng)有同類資源m個,被n個進程共享,試問：當m>n和m<n,每個進程最多可申請多少個這類資源而使系統(tǒng)一定不會發(fā)生死鎖？SFSFPaPbPc5、醫(yī)生給病人看病,需要化驗,于是醫(yī)生開出化驗單,病人到化驗室化驗,化驗結果送回醫(yī)生處供醫(yī)生診斷。醫(yī)生看病為一個進程,化驗室化驗為一個進程,二者需要交換信息,試用信號燈的P、V操作實現(xiàn)這兩個進程的同步關系。6、設有兩個優(yōu)先級相同的進程P1、P2如下：令信號量S1,S2的初值為0,試問P1、P2并發(fā)運行結束后X=?y=?z=?進程P1進程P2y=1;x=1;y=y+2;x=x+1;V<S1>;P<S1>;Z=y+1;x=x+y;P<S2>;V<S2>;Y=z+y;z=x+z;7、在一個盒子里,混裝了數(shù)量相等的圍棋白子和黑子?，F(xiàn)在要用自動分揀系統(tǒng)把白子和黑子分開。該系統(tǒng)設有兩個進程P1、P2,其中P1將揀白子,P2將揀黑子。規(guī)定每個進程每次只揀一子。當一進程正在揀子時,不允許另一進程去揀,當一進程揀了一子時,必須讓另一進程去揀。試寫出兩個并發(fā)進程能正確執(zhí)行的程序。8、桌上有一只盤子,每次只能放入一個水果。爸爸專向盤中放蘋果,媽媽專向盤中放橘子,一個女兒專等吃盤中的蘋果,一個兒子專等吃盤中的橘子。試用P、V操作寫出他們能同步的程序。例4．1某虛擬存儲器的用戶空間共有32個頁面,每頁1KB,主存16KB。試問：〔1邏輯地址的有效位是多少？

〔2物理地址需要多少位？

〔3假定某時刻系統(tǒng)為用戶的第0,1,2,3頁分別分配的物理塊號為5,10,4,7,試將虛地址0A5C和〔3當頁面為1KB時,虛地址0A5C該頁在內存的第4塊,即塊號為0100,因此0A5C討論分頁存儲管理的地址變換非常簡單,只要記住一點,由頁號查頁表得物理塊號,然后與頁內地址拼接成物理地址。例4．2某段式存儲管理中采用如表4．1所示的段表?！?給定段號和段內地址,說明段式管理中的地址變換過程。〔2計算［0,430］,［1．10］,［2,500〕,［3,400］,［4,20］,［5,100］的內存地址,其中方括號內的第一元素是段號,第二元素是段內地址?！?說明存取主存中的一條指令或數(shù)據(jù)至少要訪問幾次主存。解〔1為了實現(xiàn)從邏輯地址到物理地址的變換,在系統(tǒng)中需要設置段表寄存器,存放段表起站地址和段表長度TL。在進行地址變換時,系統(tǒng)將邏輯地址中的段號S與段表長度TL進行比較。若S＞TL,則表示段號太大,是訪問越界〔段號越界,產(chǎn)生越界中斷。若未越界,則根據(jù)段表的起始地址和段號,計算出該段對應段表項的位置,從中讀出該段在內存中的起始位置和段長SL,再檢查段內地址d是否超過該段的段長SL。若超過,即d＞SL,則同樣發(fā)出越界中斷信號〔段內地址越界；若未越界,則將該段的起始地址與段內地址d相加,即得要訪問的內存物理地址?！?［0,430］的物理地址是219＋430=649。［1,10］的物理地址是3330＋10=3340。因500＞100,所以［2,500］越界〔段內地址越界。［3,400］的物理地址是1237＋400=1637。［4,20］的物理地址是1952＋20=1972。因5＞4,所以［5,100］越界〔段號越界。〔3存取主存中的一條指令或數(shù)據(jù)至少要訪問2次主存。一次是訪問段表,另一次是訪問需要的指令或數(shù)據(jù)。討論在分段存儲管理的地址變換過程中,要點是由段號查段表得段起始地址,然后與段內地址相加得物理地址。但要注意,段地址是二維地址,段號和段內地址都有可能越界。例4．3分頁和分段有何區(qū)別？為什么說分段系統(tǒng)較之分頁系統(tǒng)更易于實現(xiàn)信息共享和保護？如何實現(xiàn)？解分頁和分段都采用離散分配方式,但兩者有顯著的差別?！?頁是信息的物理單位,分頁是系統(tǒng)的需要,是為了提高內存的利用率；段是信息的邏輯單位,目的在于更好地滿足用戶的需要?！?頁的大小固定,且由系統(tǒng)確定,一個系統(tǒng)只能有一種大小的頁面；段的長度不固定,決定于用戶的程序。〔3分頁的作業(yè)地址空間是一維的,單一的線性地址空間；分段的作業(yè)地址空間是二線的,一個地址包括段號和段內地址。在分頁和分段存儲管理系統(tǒng)中,多個作業(yè)并發(fā)運行,共享同一內存塊里的程序或數(shù)據(jù)是可行的。為了實現(xiàn)共享,必須在各共享者的段表或頁表中分別有指向共享內存塊的表目。對分段式系統(tǒng),被共享的程序或數(shù)據(jù)可作為單獨的一段。在物理上它是一段,在不同的進程中,可以對應不同的邏輯段,相對來說比較易于實現(xiàn)。對分頁管理,則要困難得多。首先,必須保證被共享的程序或數(shù)據(jù)占有整數(shù)塊,以便與非共享部分分開。其次,由于共享程序或數(shù)據(jù)被多個進程訪問,所以每個進程對共享程序或數(shù)據(jù)的訪問都應該是有限制條件的。因此,從共享和保護的實現(xiàn)上來看,須共享的程序段或數(shù)據(jù)段是一個邏輯單位,而分段存儲管理中被共享的程序或數(shù)據(jù)作為一個整體〔一段,實現(xiàn)共享和保護就要方便得多。分段系統(tǒng)的共事是通過兩個〔或多個進程的段表之相應表目都指向同一個物理段,并設置共享計數(shù)來實現(xiàn)的。每段設置訪問方式,就可以實現(xiàn)段的保護。討論分頁與分段的邏輯地址一個是一維,一個是二維,一定要加以區(qū)別。從共享與保護來講．分頁管理也可以實現(xiàn),但非常復雜,一般系統(tǒng)不易實現(xiàn)。例4．4在一個請求分頁系統(tǒng)中,假如一個作業(yè)的頁面走向為4,3,2,1,4,3,5,4,3,2,1,5。當分配給該作業(yè)的物理塊數(shù)M分別是3和4時,分別采用LRU和FIFO頁面替換算法,432143543215432143543215FIFO444111555LRU444111522233344422333444411222333122233335計算訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率；比較所得結果。缺頁次數(shù)=10次,缺頁率=〔10／12*100％=83％。通過以上缺頁次數(shù)和缺頁率的分析計算,可以看出,對于LRU算法,增加物理塊數(shù),可以減少缺頁次數(shù),降低缺頁率。而對FIFO算法,增加物理塊數(shù),不一定能減少缺頁次數(shù)。討論計算缺頁次數(shù)和缺頁率時,要注意初始時刻所有物理塊為空。調入頁面時,不需要頁面替換,但是需要引起缺頁中斷。例4．5什么是虛擬存儲器？在分頁存儲管理系統(tǒng)中如何實現(xiàn)虛擬存儲？解所謂虛擬存儲器是指僅把作業(yè)的一部分裝入內存便可運行作業(yè)的存儲管理系統(tǒng)。它具有請求調入功能和置換功能,能從邏輯上對內存容量進行擴充。請求分頁存儲管理系統(tǒng)是在分頁管理的基礎上實現(xiàn)的。頁表中除了有頁號、物理塊號兩項外,還需要狀態(tài)位、訪問字段、修改位、外存地址等信息。由于是部分調入內存,每當所要訪問的頁面不在內存時,便要產(chǎn)生缺頁中斷,請求操作系統(tǒng)將所缺頁調入內存。缺頁中斷的處理過程是保留CPU現(xiàn)場；從外存中找到所缺的頁面；若內存已滿,則選擇一頁換出,從外存讀入所缺的頁面,寫入內存,修改頁表。在進行地址變換時,若發(fā)現(xiàn)被訪問的頁不在內存,必須先通過缺頁中斷將所缺的頁面調入內存,并修改頁表。其余的過程與分頁管理類似。全過程如圖4．3所示。討論請求分頁存儲管理系統(tǒng)實現(xiàn)的重點,在于對地址變換過程和缺頁中斷處理過程的理解。例4．6類似于請求分頁存儲管理中的請求式調頁那樣,在請求分段存儲管理中也可以采用請求式調段策略。試提出一個合理的段替換算法,并說明在段替換過程中會出現(xiàn)哪些在負面替換過程中不出現(xiàn)的問題。解可以使用FIFO替換算法。它在內存中查找第一個滿足要求的段。為避免內部存儲碎片,可把該段的末被占用的部分并入空閑空間表中。若找不到滿足要求的段,則可以選擇兩個或多個連續(xù)的段來滿足要求。在段替換過程中,必須要考慮到段的大小變化,但在頁面替換中頁面的大小是固定的。討論關于請求分段存儲管理的段替換算法,考慮到段大小的不固定,可能需要替換若干個連續(xù)的段才能滿足要求,所以替換算法應力求簡單,FIFO算法成為首選。4．3習題4．1填空題：〔1存儲管理方案中,可采用覆蓋技術?！睞單一連續(xù)區(qū)存儲管理〔B可變分區(qū)存儲管理〔C段式存儲管理〔D段頁式存儲管理〔2對如圖4．4所示的內存分配情況〔其中,陰影部分表示已占用塊,空白部分表示空閑塊,若要申請一塊40KB的內存,對于最佳適應分配策略給出分配區(qū)域的首地址是?！睞110KB〔B190KB〔C330KB〔D410KB〔3在圖4.4所示中,若要申請一塊40KB的內存,使首地址最大的分配策略是?！睞首次適應分配策略〔B最佳適應分配策略〔C最壞適應分配策略〔D單一連續(xù)區(qū)分配策略〔4下列算法中會產(chǎn)生Belady異?，F(xiàn)象的是。〔A先進先出〔FIFO頁面替換算法〔B最近最久未使用〔LRU替換算法〔C最不經(jīng)常使用〔LFU頁面替換算法〔D最佳〔Optimal頁面替換算法4．2為什么要引入動態(tài)重定位？如何實現(xiàn)？4．3在動態(tài)分區(qū)管理中,有哪些分區(qū)分配算法？各有何優(yōu)缺點?4．4在采用首次適應算法的分區(qū)管理中,回收內存時可能出現(xiàn)哪幾種情況？應怎樣處理這些情況？4．5什么叫覆蓋？使用覆蓋技術有什么要求？4．6在系統(tǒng)中引入交換技術后帶來哪些好處？為實現(xiàn)交換,系統(tǒng)應具備哪些方面的功能？4．7對于一個利用快表且頁表存于內存的分頁系統(tǒng),假定CPU一次訪存時間為1.5us。訪問快表的時間可以忽略不計。試問：〔1如果85％的地址映射可以直接通過快表完成〔即快表命中率為85％那么進程完成一次內存讀寫的平均有效訪問時間是多少？〔2若快表的命中率只有50％,那么進程完成一次內存讀寫的平均有效訪問時間又是多少？〔3快表命中率對平均有效訪問時間有何影響？4．8什么叫動態(tài)裝入？動態(tài)裝入的優(yōu)點是什么？4．9為什么引入虛擬存儲概念？虛擬存儲器的容量由什么決定？受什么影響？4.10請指出下面哪些程序設計技術和數(shù)據(jù)結構適合于請求分頁存儲管理環(huán)境,哪些不適合請求式分頁存儲管理環(huán)境?！??！?雜湊符號表〔3順序查找〔4折半查找〔5純代碼〔6向量操作。4．11假定有一個請求分頁存儲管理系統(tǒng),測得各相關成分的利用率為：CPU利用率為20％；磁盤交換區(qū)為96.7％；其他I／0設備為50％。試問下面哪些措施將〔可能改進CPU的利用率？〔1增加一個更快速的CPU?！?增大磁盤交換區(qū)的容量。〔3增加多道程序的度數(shù)?！?減少多道程序的度數(shù)?！?增加其他更快速的I／0設備。4．12設有二維數(shù)組intA［1..100］［1..100］；其中數(shù)組元素A［1,1］存放在頁面大小為200的分頁存儲管理系統(tǒng)中的地址200處,數(shù)組按行存儲。使用該數(shù)組的一個較小的程序存放在第0頁中〔地址0～199,這樣將只會從第0頁取指令。假定現(xiàn)有三個頁面,第一個頁面存放程序,其余兩個頁面用于存放數(shù)據(jù),初始為空。試問：若使用LRU替換算法,下面的數(shù)組初始化循環(huán)將會產(chǎn)生多少次缺頁中斷？若每頁的頁面大小為100,數(shù)組初始化循環(huán)將會產(chǎn)生多少次缺頁中斷？并說明頁面大小對缺頁中斷次數(shù)的影響.for<j=1;j<=100;j++>for<k=1;k<=100;k++>A[j][k]=0;for<j=1;j<=100;j++>for<k=1;k<=100;k++>A[k][j]=0;4．13考慮下面的頁訪問串：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6假定有1,2,3,4,5,6,7個頁塊。試問：若應用下面的頁面替換算法,各會出現(xiàn)多少次缺頁中斷？注意,所給定的頁塊初始均為空,因此,首次訪問一頁時就會發(fā)生缺頁中斷?！?LRU替換算法。〔2FIFO替換算法。〔3Optima替換算法。4．14什么是局部性原理？什么是抖動？有什么辦法可以減少系統(tǒng)的抖動現(xiàn)象？4．15什么叫工作集？工作集模型的優(yōu)點是什么？例1：假定盤塊的大小為1KB,硬盤的大小為500MB,采用顯式鏈接分配方式時,其FAT需占用多少存儲空間？如果文件A占用硬盤的第11,12,16,14四個盤塊,試畫出文件A中各個盤塊間的鏈接情況及FAT的情況。例2：存放在某個磁盤上的文件系統(tǒng),采用混合索引分配方式,其FCB中共有13個地址項,第0~9個地址項為直接地址,第10個地址項為一次間接地址,第11個地址項為二次間接地址,第12個地址項為三次間接地址。如果每個盤塊的大小為512字節(jié),若盤塊號需要用3個字節(jié)來描述,而每個盤塊最多存放170個盤塊地址：〔1該文件系統(tǒng)允許文件的最大長度是多少？〔2將文件的字節(jié)偏移量5000,15000,150000轉換為物理塊號和塊內偏移量?！?假設某個文件的FCB已在內存,但其他信息均在外存,為了訪問該文件中某個位置的內容,最少需要幾次訪問磁盤,最多需要幾次訪問磁盤？答：〔1該文件系統(tǒng)允許文件的最大長度是多少？10+170+170x170+170x170x170=4,942,080盤塊4,942,080*512Byte=2,471,040KB〔2將文件的字節(jié)偏移量5000、15000、150000轉換為物理塊號和塊內偏移量。5000 =9x512+39215000=29x512+152150000=292x512+496〔3假設某個文件的設備目錄表項<FCB>已在內存中,其它信息在外存,為了訪問該文件的某個字節(jié),最少需要幾次訪問硬盤,最多需要幾次。最少一次〔直接地址,最多四次〔1：讀三重索引,2：讀二重索引,3：讀一重索引,4：讀內容例3：請分別解釋在連續(xù)分配方式,隱式鏈接分配方式,顯式鏈接分配方式和索引分配方式中如何將文件的字節(jié)偏移量3500轉換為物理塊號和塊內偏移量〔設盤塊大小為1KB,盤塊號需占4個字節(jié)。例1：假設兩個用戶共享一個文件系統(tǒng),用戶甲要用到文件A,B,C,D,E,用戶乙要用到文件A,D,E,F,已知用戶甲的文件A與用戶乙的文件A實際上不是同一個文件；用戶甲的文件C與用戶乙的文件F實際上是同一個文件；甲乙兩個用戶的文件E是同一個文件。試擬定一個文件組織方案,使得甲乙兩個用戶能共享該文件系統(tǒng)而不致造成混亂。例題：在某系統(tǒng)中,從磁盤將一塊數(shù)據(jù)輸入到緩沖區(qū)需要花費的時間為T,CPU對一塊數(shù)據(jù)進行處理的時間為C,將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)所花費的時間為M,那么在單緩沖和雙緩沖情況下,系統(tǒng)處理大量數(shù)據(jù)時,一塊數(shù)據(jù)的處理時間為多少？解：〔1在無緩沖的情況下,,其后CPU對這一塊