【正文】 程序A先開始做，程序B后開始運(yùn)行。答：畫出兩道程序并發(fā)執(zhí)行圖如下：處理器輸入機(jī)打印機(jī)程序A程序BA計(jì)算B計(jì)算計(jì)算計(jì)算時(shí)間(ms)0 50 100 150 180 200 250 300打印計(jì)算打印輸入計(jì)算A打印A打印B輸入A計(jì)算B計(jì)算一(1) 兩道程序運(yùn)行期間，CPU存在空閑等待，時(shí)間為100至150ms之間(見圖中有色部分)。ABCC11＝30msC21=60msC31=20ms∣∣∣I12＝40msI22=30msI32=40ms∣∣∣C13＝10msC23=10msC33=20ms試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。2） 調(diào)度執(zhí)行時(shí)間1ms，多道運(yùn)行方式（搶占式）：時(shí)間 0 303132 71727374 8485 105107 127 136137 147 177178 198 單位1msI/O I12 I22 I32 CPU C11 C21 C13 C21 C31 C23 C33 OS 調(diào)度執(zhí)行時(shí)間1ms，多道運(yùn)行方式（非搶占式）：時(shí)間 0 303132 7172 939495 105106 124125127129 139 168169 189 單位1msI/O I12 I22 I32 CPU C11 C21 C21 C13 C31 C31 C23 C33 OS 4 在單CPU和兩臺(tái)I/O(I1,I2)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。(3)I/O設(shè)備利用率。(3) 設(shè)備I1空閑時(shí)間段為：20ms至40ms，90ms至100ms，故I1的利用率為(11030)/110=%。試求：(1)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2) CPU空閑時(shí)間段為：60ms至70ms，80ms至90ms。6 若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運(yùn)行。CPU利用率為(19080)/190=%(1) 單道運(yùn)行時(shí)間關(guān)系圖I/OCPU時(shí)間(ms)AAAB C0 20 40 50 60 80 100 120 140 BBCCB多道總運(yùn)行時(shí)間為140ms。程序B為220ms。在順序環(huán)境下先執(zhí)行A，再執(zhí)行B，求出總的CPU利用率為多少?答：程序A執(zhí)行了40秒，其中CPU用了25秒。9 在某計(jì)算機(jī)系統(tǒng)中，時(shí)鐘中斷處理程序每次執(zhí)行的時(shí)間為2ms（包括進(jìn)程切換開銷）。CH2 應(yīng)用題參考答案1 下列指令中哪些只能在核心態(tài)運(yùn)行? (1) 讀時(shí)鐘日期；（2）訪管指令；（3）設(shè)時(shí)鐘日期；（4）加載PSW；（5）置特殊寄存器；(6) 改變存儲(chǔ)器映象圖；(7) 啟動(dòng)I/O指令。同樣原因一個(gè)進(jìn)程等待CPU足夠久時(shí)，由于它是“最近使用處理器較少的進(jìn)程”，就能被優(yōu)先調(diào)度，故不會(huì)饑餓。(2)、(4)為同步問題。答：采用短作業(yè)優(yōu)先算法調(diào)度時(shí)，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T1=a+(a+b)+(a+b+c)=3a+2b+c ①若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序?yàn)椋篔JJ3。試找出一種作業(yè)調(diào)度算法，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。7 假定執(zhí)行表中所列作業(yè)，作業(yè)號(hào)即為到達(dá)順序，依次在時(shí)刻0按次序5進(jìn)入單處理器系統(tǒng)。一次進(jìn)程切換的系統(tǒng)開銷時(shí)間為S。對(duì)于1）時(shí)間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法(按到達(dá)次序C、D、B、E、A)，在忽略進(jìn)程切換時(shí)間的前提下，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。若不考慮系統(tǒng)切換開銷，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。應(yīng)該如何賦予它們占有處理器的優(yōu)先級(jí)使得系統(tǒng)效率較高？答：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長(zhǎng)時(shí)間霸占處理器。答：該計(jì)算機(jī)有一個(gè)專用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB的指針。(時(shí)間以十進(jìn)制表示)作業(yè) 提交時(shí)間(時(shí)) 估計(jì)運(yùn)行時(shí)間(小時(shí)) 開始執(zhí)行時(shí)間(時(shí)) 1 2 3 4 答： FCFS SJF HRRF作業(yè) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn)時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間1 2 3 4 平均周 T= T= T=轉(zhuǎn)時(shí)間=帶權(quán)平均 W= W= W=周轉(zhuǎn)時(shí)間=16 Kleinrock提出一種動(dòng)態(tài)優(yōu)先權(quán)算法：進(jìn)程在就緒隊(duì)列等待時(shí)，其優(yōu)先權(quán)以速率α變化； 當(dāng)進(jìn)程在處理器上運(yùn)行，時(shí)其優(yōu)先權(quán)以速率β變化。(2) 是后進(jìn)先出算法。(2)計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。18 有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊(duì)列等待。(4) 10:50，作業(yè)B運(yùn)行結(jié)束，作業(yè)D到達(dá)，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進(jìn)入就緒隊(duì)列。(7) 12:20，作業(yè)D運(yùn)行結(jié)束。19 某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。 (2)全部作業(yè)運(yùn)行結(jié)束的時(shí)間9:30。20 某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機(jī)5臺(tái)。(2) SJF算法選中作業(yè)執(zhí)行的次序?yàn)椋篈、B、D、E和C。答：1） var B : array[0,k1] of item 。rptr : integer := 0 。begin L1: read a message into x 。 V(smanage) 。begin L2: P(smanage) 。 B[mptr] := x。process writer 。 V(sread) 。coend2） var A, B : array [0,k1] of item 。sget2 : semaphore := 0 。get2 : integer := 0 。 A[put1] := x 。end 。 get1 :=(get1+1) mod k。 B[put2] := x 。 end 。 get2 :=(get2+1) mod k。end 。當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為1；最多可能有n1個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為(n1)也就是n+1。試問PP2并發(fā)執(zhí)行后，x、y、z的值各為多少？P1： P2：begin begin y:=1。 V(S1)。 P(S2)。P1： P2：begin begin y:=1。 ⑥ V(S1)。 ⑦ P(S2)。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦時(shí)，可以得到x=10，y=4。4 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列出一個(gè)表目，包括座號(hào)、姓名，讀者離開時(shí)要注銷登記信息；假如閱覽室共有100個(gè)座位。 name:string。i:integer。 P(mutex)。P(mutex)。 離開閱覽室。試寫出兩進(jìn)程P1和P2能并發(fā)正確執(zhí)行的程序。S2:=0。 endprocess P2 begin repeat P(S2)。售票員的活動(dòng)：關(guān)車門；售票；開車門。應(yīng)設(shè)置兩個(gè)信號(hào)量：ss2；s1表示是否允許司機(jī)啟動(dòng)汽車(其初值為0)；s2表示是否允許售票員開門(其初值為0)。}coenddriver ( ) begin while(1) { P(s1) 啟動(dòng)車輛； 正常行車； 到站停車； V(s2)。8 (1)兩個(gè)并發(fā)進(jìn)程并發(fā)執(zhí)行，其中，A、B、C、D、E是原語，試給出可能的并發(fā)執(zhí)行路徑。 k:=0。答：(1) 共有10種交錯(cuò)執(zhí)行的路徑：A、B、C、D、E；A、B、D、E、C；A、B、D、C、E；A、D、B、E、C；A、D、B、C、E；A、D、E、B、C；D、A、B、E、C；D、A、B、C、E；D、A、E、B、C；D、E、A、B、C。 ② k:=0。2) 語句并發(fā)執(zhí)行有以下情況： ①、②、③、④，這時(shí)的打印值為：47 ③、④、①、②，這時(shí)的打印值為：23 ①、③、②、④，這時(shí)的打印值為：46 ①、③、④、②，這時(shí)的打印值為：46 ③、①、②、④，這時(shí)的打印值為：23 ③、①、④、②，這時(shí)的打印值為：23由于進(jìn)程P1和P2并發(fā)執(zhí)行，共享了變量K，故產(chǎn)生了‘結(jié)果不唯一’。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙和第三個(gè)有自己的火柴。答：(1)用信號(hào)量和P、V操作。S1:=S2:=S3:=0。 取兩樣香煙原料放桌上，由flagi標(biāo)記。flag3 then V(S2)。 取原料。 untile false。 V(S)。 取原料。 untile false。由題中所給條件可知： max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))m+n如果在這個(gè)系統(tǒng)中發(fā)生了死鎖，那么一方面m個(gè)資源應(yīng)該全部分配出去， alloc(1)+ ┅+alloc(n)=m另一方面所有進(jìn)程將陷入無限等待狀態(tài)。(5) 不可以分配。14 把死鎖檢測(cè)算法用于下面的數(shù)據(jù)，并請(qǐng)問： Available=(1，0，2，0)110 0011 2310 0Need=1 00 02 11 0301 1010 0111 1Allocation=0 11 00 00 0 (1) 此時(shí)系統(tǒng)此時(shí)處于安全狀態(tài)嗎？(2) 若第二個(gè)進(jìn)程提出資源請(qǐng)求request2(0，0，1，0)，系統(tǒng)能分配資源給它嗎？(3) 若第五個(gè)進(jìn)程提出資源請(qǐng)求request5(0，0，1，0)，系統(tǒng)能分配資源給它嗎？答：(1)此時(shí)可以找出進(jìn)程安全序列：P4，P1，P5，P2，P3。15 某系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被PPP3和P4進(jìn)程共享，且已知這4個(gè)進(jìn)程均按以下順序使用設(shè)備： →申請(qǐng)R1→申請(qǐng)R2→申請(qǐng)R1→釋放R1→釋放R2→釋放R1(1) 系統(tǒng)運(yùn)行中可能產(chǎn)生死鎖嗎？為什么？(2) 若可能的話，請(qǐng)舉出一種情況，并畫出表示該死鎖狀態(tài)的進(jìn)程—資源圖。當(dāng)三個(gè)進(jìn)程執(zhí)行完申請(qǐng)資源R2后，系統(tǒng)還剩1個(gè)R2資源。答：當(dāng)兩個(gè)進(jìn)程都執(zhí)行完第一步(都占用R1) 時(shí)，系統(tǒng)進(jìn)入不安全狀態(tài)。這時(shí)己形成死鎖。答：(1)用信號(hào)量和P、V操作。mutex:semaphore。 /* 盤子里允許