西安電子科技大學(xué)操作系統(tǒng)考試重點作業(yè)講解

1、.作業(yè)講解（24）.知識點n進程互斥和同步的控制 信號量機制 信號量是一種數(shù)據(jù)結(jié)構(gòu) 信號量的值與相應(yīng)資源的使用情況有關(guān) 信號量的值僅由P、V操作改變.知識點記錄型信號量n記錄型結(jié)構(gòu)，包括兩個數(shù)據(jù)項：type semaphore=record value:integer; L:list of process; end .知識點n假設(shè)定義了一個信號量SnS.value為資源信號量，其初值為某類資源的數(shù)目。 S.value=0，代表系統(tǒng)當(dāng)中可用資源的數(shù)目。 S.value0,其絕對值代表等待使用資源的進程個數(shù)。nS.L是一個阻塞隊列，進程無法申請到資源則進入此隊列。.知識點n定義對信號量的兩個原子操

2、作：定義對信號量的兩個原子操作：wait(s) 和signal（s） procedure wait(S) var S: semaphore; begin S.value: =S.value-1; if S.value0 then block(S.L) /進程阻塞，即進入S.L鏈表； end .知識點n定義對信號量的兩個原子操作：定義對信號量的兩個原子操作：wait(s) 和signal（s） procedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); /喚醒阻塞隊列首

3、進程, 將進程從 /S.L阻塞隊列中移出； end .第二章22、試寫出相應(yīng)的程序來描述圖2-17 所示的前趨圖。 P82 22(a) Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0, 0;beginparbeginbegin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c); signal(d); end;begin wait(b); S3; signal(e); end;begin wait(c); S4; signal(f); end;begin w

4、ait(d); S5; signal(g); end;begin wait(e); S6; signal(h); end;begin wait(f); wait(g); wait(h); S7; end;parendend.第二章n26. 參看教材參看教材P58-59.第二章n3、設(shè)公共汽車上有一個司機和一個售票員，其活動如圖、設(shè)公共汽車上有一個司機和一個售票員，其活動如圖3所示。所示。為了安全起見，顯然要求為了安全起見，顯然要求: (1)關(guān)車門后方能啟動車輛；關(guān)車門后方能啟動車輛；(2)到站停到站停車后方能開車門。亦即車后方能開車門。亦即“啟動車輛啟動車輛”這一活動應(yīng)當(dāng)在這一活動應(yīng)當(dāng)在“關(guān)車

5、門關(guān)車門”這一活動之后，這一活動之后，“開車門開車門”這一活動應(yīng)當(dāng)在這一活動應(yīng)當(dāng)在“到站停車到站停車”這一活這一活動之后。試用記錄型信號量實現(xiàn)司機與售票員之間的同步，并說動之后。試用記錄型信號量實現(xiàn)司機與售票員之間的同步，并說明各信號量的含義。明各信號量的含義。.n用記錄型信號量解決這一問題，需要定義兩個信號量：nStart：表示是否允許司機啟動車輛，初值為0；nOpen：表示是否允許售票員開車門，初值為0。semaphore start=0;semaphore open=0;售票員的活動:beginrepeat 關(guān)車門; Signal(start); 售票; Wait(open); 開車門;

6、until falseend司機的活動:beginrepeat Wait(start); 啟動車輛; 正常行車; 到站停車; Signal(open);until falseend.第二章n知識點 進程調(diào)度算法 避免死鎖銀行家算法.進程調(diào)度算法n先來先服務(wù)FCFSn短作業(yè)優(yōu)先調(diào)度算法n時間片輪轉(zhuǎn)調(diào)度算法n概念 周轉(zhuǎn)時間：指作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。 帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/系統(tǒng)為它提供服務(wù)的時間.第三章1、假定有如下作業(yè)：請用FCFS、SJF、RR(q=2）調(diào)度算法，分別計算周轉(zhuǎn)時間、平均周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間。.第三章FCF和SPF的計算結(jié)果如下.第

7、三章n時間片輪轉(zhuǎn)調(diào)度算法，執(zhí)行圖如下：進程名ABCDE平均到達時間01234服務(wù)時間64325RR完成時間1714151020周轉(zhuǎn)時2帶權(quán)周轉(zhuǎn)時間2.833.254.33.53.23.42BCA.銀行家算法n用于避免死鎖。n基本思想：當(dāng)有進程申請資源時，只有滿足此進程需要不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)才分配。n安全狀態(tài)： 是指系統(tǒng)能按某種進程順序，如,分別為這n個進程分配所需資源，直到滿足每個進程的最大需求，使每個進程都能順利完成，稱序列為安全序列。 若系統(tǒng)存在安全序列，則系統(tǒng)當(dāng)前為安全狀態(tài)。.銀行家算法描述n設(shè)Requesti是進程Pi的請求向量，如果Requestij

8、=K，表示進程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： n如果RequestijNeedi,j， 【請求小于需求請求小于需求】,便轉(zhuǎn)向步驟2；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。1.如果RequestijAvailablej【請求小于庫存請求小于庫存】,便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 .銀行家算法描述3. 系統(tǒng)試探著把資源分配給進程Pi【試分配試分配】，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： 【庫存庫存】 Available j :=Available j -Requestij; 【獲取獲取】 Allocationi,j:

9、=Allocationi,j+Requestij; 【需求需求】 Needi,j:=Needi,j-Requestij4. 系統(tǒng)執(zhí)行安全性算法安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。.第三章2 .在銀行家算法中，若出現(xiàn)下述資源分配情況：P115第22題Proceses AllocationNeed AvailableP0003200121622P110001750P213542356.第三章n1）該狀態(tài)是否安全？Proceses AllocationNeed

10、AvailableP0003200121622P110001750P213542356P303320652P400140656Proceses WorkNeed AllocationWork+AllocationFinishP01622001200321654trueP31654065203321986trueP11986175010002986trueP22986235613544340trueP44340065600143354true安全，因為存在安安全，因為存在安全序列全序列.第三章n2)2)若進程若進程P2P2提出請求提出請求Request(1,2,2,2)Request(1,2,2

11、,2)后，系統(tǒng)能否后，系統(tǒng)能否將資源分配給它將資源分配給它？n分配后系統(tǒng)資源情況如下：分配后系統(tǒng)資源情況如下：Proceses AllocationNeed AvailableP0003200120400P110001750P225762356P303320652P400140656此狀態(tài)不安此狀態(tài)不安全，因此不全，因此不能分配。能分配。.第四章n知識點 基本分頁式存儲管理地址映射過程 基本分段式存儲管理地址映射過程 頁面置換算法.頁表寄存器頁表始址頁表長度頁號頁內(nèi)地址邏輯地址L越界中斷1塊號b頁表頁號012物理地址3基本分頁式存儲管理地址映射過程.第四章1、在采用頁式存儲管理的系統(tǒng)中，擁有的

12、邏輯在采用頁式存儲管理的系統(tǒng)中，擁有的邏輯地址空間為地址空間為32頁，某作業(yè)頁，某作業(yè)J的邏輯地址空間為的邏輯地址空間為4頁（每頁頁（每頁2048字節(jié)），且已知該作業(yè)的頁面映字節(jié)），且已知該作業(yè)的頁面映像（即頁表）如下：像（即頁表）如下：n試借助地址變換圖求出有效邏輯地址試借助地址變換圖求出有效邏輯地址4865所對所對應(yīng)的物理地址。應(yīng)的物理地址。頁號頁號塊號塊號02142638.解答41836220塊號頁號011 0000 00010001000111頁表首址頁表首址+010物理地址為：物理地址為：13057.基本分段式存儲管理地址映射過程段地址變換由硬件地址變換機構(gòu)完成。段地址變換由硬件地址

13、變換機構(gòu)完成。控制寄存器段表始址段表長度2100段號S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址.第四章 作業(yè)33、對于下表所示的段表，請將邏輯地址（0，137），（1，4000），（4，230）轉(zhuǎn)換成物理地址。段號內(nèi)存始址段長050K10K160K3K270K5K3120K8K. 4 Cb+0 137比較比較5*1024 + 137段段表表04物理地址物理地址段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址b1375K比較比較段號內(nèi)存始址段長050K10K160K3K270K5K3

14、120K8K51337. 4 Cb+1 4000比較比較段段表表04地址越界地址越界段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址b40003K比較比較段號內(nèi)存始址段長050K10K160K3K270K5K3120K8K. 4 Cb4 23044段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址地址越界地址越界比較比較.頁面置換算法n在請求分頁式存儲管理中，當(dāng)發(fā)生缺頁中斷且無足夠的內(nèi)存空間時，需要置換已有的某些（個）頁面。.頁面置換算法分類n最佳頁面算法（OPT）n先進先出頁面置換算法（FIFO）n最近最久未使用頁面置換算法（LRU）n輪轉(zhuǎn)算法（

15、Clock）.第四章 作業(yè)2：P143頁 23題2、某程序在內(nèi)存中分配四個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按LRU、Clock、OPT算法分別計算缺頁次數(shù)假設(shè)開始時所有頁均不在內(nèi)存.LRU 4 3 2 1 4 3 5 4 3 2 1 5塊1塊2塊3塊4 x x x x x x x x共缺頁中斷8次LRU443432432143214321435143514351435243125312.Clock 4 3 2 1 4 3 5 4 3 2 1 5塊1塊2塊3塊4 x x x x x x x x x x共缺頁中斷10次Clock443432432143214321

16、532154215431543214321532.OPT 4 3 2 1 4 3 5 4 3 2 1 5塊1塊2塊3塊4 x x x x x x 共缺頁中斷6次OPT443432432143214321432543254325432513251325.第四章 作業(yè)44、某頁式虛擬存儲管理系統(tǒng)的物理空間共3K，頁面大小為1K，一進程按下列地址順序引用內(nèi)存單元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述數(shù)字均為十進制，而內(nèi)存中尚未裝入任何頁。請給出使用LRU算法時的缺頁次數(shù)。n解答：頁塊數(shù)為解答：頁塊數(shù)為3，頁號分別