操作系統(tǒng)例題匯總

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

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

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