操作系統(tǒng)習(xí)題課-2

1、操作系統(tǒng)習(xí)題第2章 處理機(jī)管理【例15】 進(jìn)程P0和P1的共享變量定義及初值為boolean flag2;int turn=0;flag0=FALSE; flag1=FALSE;若進(jìn)程P0和P1訪問(wèn)臨界資源的類C代碼實(shí)現(xiàn)如下：/ 進(jìn)程P0 / 進(jìn)程P1void P0() void P1() while(TRUE) while(TRUE) flag0=TRUE; flag1=TRUE; turn=1; turn=0; while(flag1&(turn=1); while(flag0&(turn=0); 臨界區(qū); 臨界區(qū); flag0=FALSE; flag1=FALSE; 第2章 處理機(jī)管理則

2、并發(fā)執(zhí)行進(jìn)程P0和P1時(shí)產(chǎn)生的情況是A.不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn)“饑餓”現(xiàn)象B.不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn)“饑餓”現(xiàn)象C.能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會(huì)出現(xiàn)“饑餓”現(xiàn)象D.能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會(huì)出現(xiàn)“饑餓”現(xiàn)象解答：D第2章 處理機(jī)管理【例16】某銀行提供 1 個(gè)服務(wù)窗口和 10 個(gè)供顧客等待的座位。顧客到達(dá)銀行時(shí)，若有空座位，則到取號(hào)機(jī)上領(lǐng)取一個(gè)號(hào)，等待叫號(hào)。取號(hào)機(jī)每次僅允許一位顧客使用。當(dāng)營(yíng)業(yè)員空閑時(shí)，通過(guò)叫號(hào)選取一位顧客，并為其服務(wù)。顧客和營(yíng)業(yè)員的活動(dòng)過(guò)程描述如下：請(qǐng)?zhí)砑颖匾男盘?hào)量和 P、V操作，實(shí)現(xiàn)上述過(guò)程中的互斥與同步。要求寫(xiě)出完整的過(guò)程，說(shuō)明信號(hào)量的含義

3、并賦初值。第2章 處理機(jī)管理cobegin process 顧客i 從取號(hào)機(jī)獲得一個(gè)號(hào)； 等待叫號(hào) 獲得服務(wù)； coendprocess 營(yíng)業(yè)員 while (TRUE) 叫號(hào) 為顧客服務(wù)； semaphore mutex = 1;/互斥使用取號(hào)機(jī)semaphore empty = 10;/空座位的數(shù)量 semaphore full = 0;/已占座位的數(shù)量 semaphore service = 1;/服務(wù)窗口 第2章 處理機(jī)管理cobegin process 顧客i P(empty); P(mutex); 從取號(hào)機(jī)獲得一個(gè)號(hào)； V(mutex); V(full); P(service);/

4、等待叫號(hào) 獲得服務(wù)； coendprocess 營(yíng)業(yè)員 while (TRUE) P(full); V(empty); V(service);/叫號(hào) 為顧客服務(wù)； 第2章 處理機(jī)管理【例17】某寺廟中有若干個(gè)老和尚和小和尚，并有一個(gè)水缸能儲(chǔ)存10桶水，小和尚每天從寺廟的水井中打水入缸供老和尚飲用。寺廟中有3個(gè)水桶，小和尚從井中打水時(shí)每次只能使用1個(gè)水桶，老和尚從缸中取水時(shí)每次也只能取1桶。試給出從井中打水和從缸中取水的算法描述。第2章 處理機(jī)管理 設(shè)信號(hào)量empty表示水缸還能容納幾桶水，初值為10；信號(hào)量full表示水缸中還有幾桶水可用，初值為0；設(shè)信號(hào)量S表示可用水桶數(shù)目，初值為3；信號(hào)量

5、mutex1表示從井中打水者互斥使用水井，初值為1；mutext2表示從缸中取水者互斥使用水缸，初值為1。8第2章 處理機(jī)管理cobegin從井中打水：從缸中取水：beginbegin:L1: P(empty); L2: P(full);P(S); P(S);P(mutext1); P(mutext2);井中打水從缸中取水；V(mutext1); V(mutext2);P(mutext2);V(empty);倒水入缸V(S);V(mutex2);goto L2;V(full);endV(S);goto L1;endcoend9第2章 處理機(jī)管理【例21】某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，有K個(gè)進(jìn)程競(jìng)

6、爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值A(chǔ). 2B. 3C. 4D. 5解答：C第2章 處理機(jī)管理【例22】在下列解決死鎖的辦法中，屬于死鎖預(yù)防策略的是A. 化簡(jiǎn)進(jìn)程的資源分配圖B. 銀行家算法C.資源的有序分配法D.死鎖檢測(cè)法解答：C第2章 處理機(jī)管理【例23】為避免產(chǎn)生死鎖，銀行家算法破壞了A.互斥條件B.部分分配條件C.不可搶占條件D.循環(huán)等待條件解答：D第2章 處理機(jī)管理【例24】若有同類資源10個(gè)，進(jìn)程P1、P2和P3需要該類資源的最大數(shù)量分別為8，6，7。它們使用資源的次序和數(shù)量如下：(1) 試給出采用銀行家算法分配資源時(shí)，進(jìn)行第5次分配后各進(jìn)程的狀態(tài)及

7、各進(jìn)程占用資源情況。(2) 在以后的申請(qǐng)中，哪次的申請(qǐng)可以得到最先滿足？給出一個(gè)進(jìn)程完成序列。次序進(jìn)程申請(qǐng)量1P132P223P344P125P226P137P338P22第2章 處理機(jī)管理 P1申請(qǐng)3個(gè)，滿足，系統(tǒng)還剩7個(gè)。 P2申請(qǐng)2個(gè)，滿足（因?yàn)橄到y(tǒng)的7個(gè)可以使P2運(yùn)行完），系統(tǒng)還剩5個(gè)。 P3申請(qǐng)4個(gè)，因?yàn)槿魸M足它的請(qǐng)求，可能使以后的任何進(jìn)程都不能運(yùn)行完，故P3等待。 P1申請(qǐng)2個(gè)，滿足（系統(tǒng)還剩5個(gè)可以滿足P1的最大請(qǐng)求），系統(tǒng)還剩3個(gè)。 P2申請(qǐng)2個(gè)，不能滿足，等待；此時(shí)系統(tǒng)的分配情況如下：P1分配5個(gè)后正在運(yùn)行，P2分配2個(gè)后等待分配2個(gè)，P3等待分配4個(gè)，系統(tǒng)還剩3個(gè)。P1接著

8、運(yùn)行14第2章 處理機(jī)管理 P1申請(qǐng)3個(gè)可以滿足。P1運(yùn)行完成后，釋放資源，使系統(tǒng)的資源數(shù)量變?yōu)?個(gè)。首先將P3喚醒，滿足它的4個(gè)資源，系統(tǒng)還剩4個(gè)，可以繼續(xù)喚醒P2，滿足它的2個(gè)請(qǐng)求。系統(tǒng)還剩2個(gè)。 P3申請(qǐng)3個(gè)，不能滿足，等待。 P2申請(qǐng)2個(gè)，系統(tǒng)滿足它，P2接著運(yùn)行，P2完成，釋放資源，使系統(tǒng)資源變?yōu)?個(gè)。系統(tǒng)喚醒P3，滿足它的資源請(qǐng)求，最終P3完成，釋放資源，使資源數(shù)量恢復(fù)為10個(gè)。找到的進(jìn)程完成序列為P1,P2,P3。15第3章 存儲(chǔ)器管理【例25】分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是A. 界地址保護(hù)B. 程序代碼保護(hù)C. 數(shù)據(jù)保護(hù)D. 棧保護(hù) 解答：A16第3章 存儲(chǔ)器管理【例26

9、】能解決主存碎片問(wèn)題的存儲(chǔ)器管理方案是A.可變式分區(qū)B.分頁(yè)管理C.分段管理D.都可以解答：B17第3章 存儲(chǔ)器管理【例27】不會(huì)產(chǎn)生內(nèi)部碎片存儲(chǔ)器管理的方案是A.分頁(yè)B.分段C.固定分區(qū)D.段頁(yè)式解答：B18第3章 存儲(chǔ)器管理【例28】在主存管理諸模式中，(1)主存利用率最高的模式是（ ）；(2)便于動(dòng)態(tài)擴(kuò)充存儲(chǔ)空間的模式是（ ）；(3)主存利用率最高且實(shí)現(xiàn)保護(hù)和共享更容易的模式是（ ）。A.分區(qū)管理B.分頁(yè)管理C.分段管理D.段頁(yè)式管理解答： (1)B (2)C (3)D19第3章 存儲(chǔ)器管理【例29】某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55Mb（初始為空），采用最佳適配（Best

10、 fit）算法，分配和釋放的順序?yàn)椋悍峙?5Mb，分配30Mb，釋放15Mb，分配8Mb，分配6Mb，此時(shí)主存中最大空閑分區(qū)的大小是A.7MbB.9MbC.10MbD.15Mb解答：B20第3章 存儲(chǔ)器管理【例30】一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長(zhǎng)度為32位，其中段號(hào)占8位，則最大段長(zhǎng)是A.2的8次方字節(jié)B.2的16次方字節(jié)C.2的24次方字節(jié)D.2的32次方字節(jié)解答：C21第3章 存儲(chǔ)器管理【例31】請(qǐng)求分頁(yè)管理系統(tǒng)中，假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下表所示：頁(yè)面大小為4KB，一次內(nèi)存的訪問(wèn)時(shí)間是100ns，一次快表（TLB）的訪問(wèn)時(shí)間是10ns，處理一次缺頁(yè)的平均時(shí)間為108ns（已含更新TLB和頁(yè)

11、表的時(shí)間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。22頁(yè)號(hào)頁(yè)框（Page Frame）號(hào)有效位（存在位）0101H11-02254H1第3章 存儲(chǔ)器管理假設(shè)TLB初始為空；地址轉(zhuǎn)換時(shí)先訪問(wèn)TLB，若TLB未命中，再訪問(wèn)頁(yè)表（忽略訪問(wèn)頁(yè)表之后的TLB更新時(shí)間）；有效位為0表示頁(yè)面不在內(nèi)存，產(chǎn)生缺頁(yè)中斷，缺頁(yè)中斷處理后，返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問(wèn)序列2362H、1565H、25A5H，請(qǐng)問(wèn)：(1) 依次訪問(wèn)上述三個(gè)虛地址，各需要多少時(shí)間？給出計(jì)算過(guò)程。 (2) 基于上述訪問(wèn)序列，虛地址1565H的物理地址是多少？請(qǐng)說(shuō)明理由。23第3章

12、存儲(chǔ)器管理(1)頁(yè)面大小為4KB，即212，則得到頁(yè)內(nèi)位移占虛地址的低12位，頁(yè)號(hào)占剩余高位。可得3個(gè)虛地址的頁(yè)號(hào)P如下:2362H：P=2，訪問(wèn)快表10ns，因初始為空，訪問(wèn)頁(yè)表100ns得到頁(yè)框號(hào)，合成物理地址后訪問(wèn)主存100ns，共計(jì)10ns+100ns+100ns=210ns。 1565H：P=1，訪問(wèn)快表10ns，落空，訪問(wèn)頁(yè)表100ns落空，進(jìn)行缺頁(yè)中斷處理108ns，合成物理地址后訪問(wèn)主存100ns，共計(jì)10ns+100ns+108ns+100ns108ns。 24第3章 存儲(chǔ)器管理25A5H：P=2，訪問(wèn)快表，因第一次訪問(wèn)已將該頁(yè)號(hào)放入快表，因此花費(fèi)10ns便可合成物理地址，訪

13、問(wèn)主存100ns，共計(jì)10ns+100ns=110ns。(2)當(dāng)訪問(wèn)虛地址1565H時(shí)，產(chǎn)生缺頁(yè)中斷，合法駐留集為2，必須從頁(yè)表中淘汰一個(gè)頁(yè)面，根據(jù)題目的置換算法，應(yīng)淘汰0號(hào)頁(yè)面，因此1565H的對(duì)應(yīng)頁(yè)框號(hào)為101H。由此可得1565H的物理地址為101565H。25第3章 存儲(chǔ)器管理【例32】設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進(jìn)程最多需要6頁(yè)（Page）數(shù)據(jù)存儲(chǔ)空間，頁(yè)的大小為1KB。操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個(gè)頁(yè)框（Page Frame）。26頁(yè)號(hào)頁(yè)框號(hào)裝入時(shí)刻訪問(wèn)位071301142301222001391601第3章 存儲(chǔ)器管理當(dāng)該

14、進(jìn)程執(zhí)行到時(shí)刻260時(shí)，要訪問(wèn)邏輯地址為17CAH的數(shù)據(jù)，請(qǐng)回答下列問(wèn)題：(1).該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)是多少？(2).若采用先進(jìn)先出（FIFO）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過(guò)程。(3).若采用時(shí)鐘（CLOCK）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過(guò)程。（設(shè)搜索下一頁(yè)的指針沿順時(shí)針?lè)较蛞苿?dòng)，且當(dāng)前指向2號(hào)頁(yè)框，示意圖如下。）27第3章 存儲(chǔ)器管理17CAH=(0001 0111 1100 1010)2(1)由于頁(yè)大小為1KB=210B，所以頁(yè)內(nèi)偏移地址為10位；邏輯地址空間為64KB=26KB，共有64頁(yè)，由前6位表示，所以邏輯地址17CAH的頁(yè)號(hào)為(

15、000101)2，即5。(2)若采用FIFO置換算法，則被置換出的頁(yè)所在頁(yè)框?yàn)?，因此對(duì)應(yīng)的物理地址為(0001 1111 1100 1010)2，即1FCAH。(3)若采用CLOCK置換算法，且當(dāng)前指針指向2號(hào)頁(yè)框，則第一次循環(huán)時(shí)，訪問(wèn)位都被置為0；在第二次循環(huán)時(shí)，將選擇置換的頁(yè)面所在頁(yè)框?yàn)?，所以對(duì)應(yīng)的物理地址為(0000 1011 1100 1010)2，即0BCAH。28第3章 存儲(chǔ)器管理【例33】某系統(tǒng)采用頁(yè)式（Paging）存儲(chǔ)管理策略，擁有邏輯空間32頁(yè)，每頁(yè)2KB；擁有物理空間1MB。(1)寫(xiě)出邏輯地址的格式。(2)若不考慮訪問(wèn)權(quán)限位，進(jìn)程的頁(yè)表有多少項(xiàng)（Entry）？每項(xiàng)至少

16、多少位（bit）？(3)如果物理空間減少一半，頁(yè)表結(jié)構(gòu)應(yīng)做怎樣的改變？29第3章 存儲(chǔ)器管理(1)邏輯地址16位長(zhǎng)。其中5位存放頁(yè)碼，11位存放頁(yè)內(nèi)地址。(2)進(jìn)程的頁(yè)表有32項(xiàng)，每項(xiàng)的位數(shù)由主存的分塊個(gè)數(shù)決定。若不考慮訪問(wèn)權(quán)限位，那么，每個(gè)頁(yè)表項(xiàng)至少有9位(1MB的主存空間可劃分為1MB/2KB=29塊數(shù)，用9個(gè)二進(jìn)制位表示)。(3)如果物理空間減少一半，主存物理地址結(jié)構(gòu)就減少一位。頁(yè)表結(jié)構(gòu)也相應(yīng)減少一位。30第3章 存儲(chǔ)器管理【例34】有一個(gè)虛存系統(tǒng)，按行存儲(chǔ)矩陣的元素。一進(jìn)程要為矩陣進(jìn)行清零操作。系統(tǒng)為該進(jìn)程分配物理主存共3塊。系統(tǒng)用其中一塊存放程序，且已經(jīng)調(diào)入，其余兩塊空閑。按需調(diào)入矩陣數(shù)據(jù)。若進(jìn)程按如下兩種方式進(jìn)行編程： var A: arrayl.100，1.100 of integer; 程序A: 程序B: for i=1 to 100 do for j=1 to 100 do for j=1 to 100 do for i=1 to 100 do Ai,j = 0; Ai,j = 0;31第3章 存儲(chǔ)器管理 若每