【正文】 分配資源，并修改Available0，Allocation0和Need0向量，由此形成的資源變化情況如下圖所示： （3）P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0,1,0),系統(tǒng)按銀行家算法進(jìn)行檢查：① Requst0(0,1,0)=Need0(7,4,3)。銀行家算法各種資源數(shù)量分別為7，在T0時(shí)刻的資源分配如圖所示： （2）具體分析如下：①Requst0(0,1,0)=Need0(7,4,3)。答：（1）擯棄“請(qǐng)求和保持”條件，就是如果系統(tǒng)有足夠資源，便一次性把?103f絳枰乃?有資源分配給它；（2）擯棄“不剝奪”條件，就是已經(jīng)擁有資源的進(jìn)程，當(dāng)它提出新資源請(qǐng)求而不能立即滿足時(shí)，必須釋放它已保持的所有資源，待以后需要時(shí)再重新申請(qǐng)；（3）擯棄“環(huán)路等待”條件，就是將所有資源按類型排序標(biāo)號(hào)，所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按序號(hào)遞增的次序提出。19．在解決死鎖問(wèn)題的幾個(gè)方法中，哪種方法最易于實(shí)現(xiàn)？哪種方法使資源利用率最高？答：解決死鎖的四種方法即預(yù)防、避免、檢測(cè)和解除死鎖中，預(yù)防死鎖最容易實(shí)現(xiàn)；避免死鎖使資源的利用率最高。產(chǎn)生死鎖的原因?yàn)楦?jìng)爭(zhēng)資源和進(jìn)程間推進(jìn)順序非法。又如，另一任務(wù)在400 ms 時(shí)必須完成，它本身需要運(yùn)行 150 ms，則其松弛程度為 250 ms。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。 圖39 EDF算法用于非搶占調(diào)度的調(diào)度方式17．什么是最低松弛度優(yōu)先調(diào)度算法？舉例說(shuō)明之。由于任務(wù)3的開(kāi)始截止時(shí)間早于任務(wù)2，故系統(tǒng)在任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。該例中具有四個(gè)非周期任務(wù)，它們先后到達(dá)。舉例：非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)。截止時(shí)間越早則優(yōu)先級(jí)越高。16．什么是最早截止時(shí)間優(yōu)先調(diào)度算法？舉例說(shuō)明。15．按照調(diào)度方式可將實(shí)時(shí)調(diào)度算法分為哪幾種？答：可分為非搶占式和搶占式兩種算法。14．為什么在實(shí)時(shí)系統(tǒng)中，要求系統(tǒng)（尤其是CPU）具有較強(qiáng)的處理能力？答：實(shí)時(shí)系統(tǒng)中通常有著多個(gè)實(shí)時(shí)任務(wù)。（3）長(zhǎng)批處理作業(yè)，它將依次在第1，2，…，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長(zhǎng)期得不到處理。（2）短批處理作業(yè)用戶，開(kāi)始時(shí)像終端型作業(yè)一樣，如果在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片段即可完成，便可獲得與終端作業(yè)一樣的響應(yīng)時(shí)間。12．通過(guò)一個(gè)例子來(lái)說(shuō)明通常的優(yōu)先級(jí)調(diào)度算法不能適用于實(shí)時(shí)系統(tǒng)？答：實(shí)時(shí)系統(tǒng)的調(diào)度算法很多，主要是基于任務(wù)的開(kāi)始截止時(shí)間和任務(wù)緊急/松弛程度的任務(wù)優(yōu)先級(jí)調(diào)度算法，通常的優(yōu)先級(jí)調(diào)度算法不能滿足實(shí)時(shí)系統(tǒng)的調(diào)度實(shí)時(shí)性要求而不適用。11．在時(shí)間片輪轉(zhuǎn)法中，應(yīng)如何確定時(shí)間片的大小？答：時(shí)間片應(yīng)略大于一次典型的交互需要的時(shí)間。SPF算法每次調(diào)度都從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存中運(yùn)行。不同點(diǎn)：FCFS調(diào)度算法每次都從后備隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存、分配資源、創(chuàng)建進(jìn)程、插入到就緒隊(duì)列。10．試比較FCFS和SPF兩種進(jìn)程調(diào)度算法。動(dòng)態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先權(quán)，可以隨進(jìn)程推進(jìn)或隨其等待時(shí)間增加而改變的優(yōu)先級(jí)，可以獲得更好的調(diào)度性能。實(shí)時(shí)系統(tǒng)的調(diào)度算法：最早截止時(shí)間優(yōu)先即EDF、最低松弛度優(yōu)先即LLF算法。8．在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，各采用哪幾種進(jìn)程（作業(yè)）調(diào)度算法？答：批處理系統(tǒng)的調(diào)度算法：短作業(yè)優(yōu)先、優(yōu)先權(quán)、高響應(yīng)比優(yōu)先、多級(jí)反饋隊(duì)列調(diào)度算法。7．在選?103f竦鞫確絞膠偷鞫人惴ㄊ?，应遵循的浊v蚴鞘裁矗?答：（1）面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短、響應(yīng)時(shí)間快、截止時(shí)間的保證、優(yōu)先權(quán)準(zhǔn)則。答：（1）保存處理機(jī)的現(xiàn)場(chǎng)信息（2）按某種算法選取進(jìn)程（3）把處理機(jī)分配給進(jìn)程。最簡(jiǎn)單的是先來(lái)服務(wù)調(diào)度算法，較常用的是短作業(yè)優(yōu)先調(diào)度算法和基于作業(yè)優(yōu)先級(jí)的調(diào)度算法。JCB 包含的內(nèi)容通常有：1) 作業(yè)標(biāo)識(shí)2)用戶名稱3)用戶賬戶4)作業(yè)類型（CPU繁忙型、I/O 芳名型、批量型、終端型）5)作業(yè)狀態(tài)6)調(diào)度信息（優(yōu)先級(jí)、作業(yè)已運(yùn)行）7)資源要求8)進(jìn)入系統(tǒng)時(shí)間9) 開(kāi)始處理時(shí)間10) 作業(yè)完成時(shí)間11) 作業(yè)退出時(shí)間12) 資源使用情況等4．在作業(yè)調(diào)度中應(yīng)如何確定接納多少個(gè)作業(yè)和接納哪些作業(yè)？答:作業(yè)調(diào)度每次接納進(jìn)入內(nèi)存的作業(yè)數(shù)，取決于多道程序度。作業(yè)流是指若干個(gè)作業(yè)進(jìn)入系統(tǒng)后依次存放在外存上形成的輸入作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)程處理，于是形成了處理作業(yè)流。批處理系統(tǒng)中是以作業(yè)為基本單位從外存調(diào)入內(nèi)存。2．何謂作業(yè)、作業(yè)步和作業(yè)流？答：作業(yè)包含通常的程序和數(shù)據(jù)，還配有作業(yè)說(shuō)明書。引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。第三章第三章 處理機(jī)調(diào)度與死鎖1．高級(jí)調(diào)度與低級(jí)調(diào)度的主要任務(wù)是什么？為什么要引入中級(jí)調(diào)度？答：高級(jí)調(diào)度的主要任務(wù)是根據(jù)某種算法，把外存上處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存。創(chuàng)建一個(gè)線程分配一個(gè)TCB，有關(guān)信息寫入TCB，為之分配必要的資源。43．試說(shuō)明內(nèi)核支持線程的實(shí)現(xiàn)方法。運(yùn)行時(shí)系統(tǒng)用于管理和控制線程的函數(shù)的集合。42．試說(shuō)明用戶級(jí)線程的實(shí)現(xiàn)方法。無(wú)論是用戶進(jìn)程中的線程，還是系統(tǒng)線程中的線 程，其創(chuàng)建、撤銷和切換等都是依靠?jī)?nèi)核，在內(nèi)核空間中實(shí)現(xiàn)的。用戶級(jí)線程的切換通常發(fā)生在一個(gè)應(yīng)用進(jìn)程的諸多線程之間，同樣無(wú)需內(nèi)核支持。41．何謂用戶級(jí)線程和內(nèi)核支持線程？答：（1）用戶級(jí)線程：僅存在于用戶空間中的線程，無(wú)須內(nèi)核支持。公用信號(hào)量是為實(shí)現(xiàn)不同進(jìn)程間或不同進(jìn)程中各線程之間的同步而設(shè)置的。當(dāng)某線程需利用信號(hào)量實(shí)現(xiàn)同一進(jìn)程中各線程之間的同步時(shí)，可調(diào)用創(chuàng)建信號(hào)量的命令來(lái)創(chuàng)建一個(gè)私用信號(hào)量，其數(shù)據(jù)結(jié)構(gòu)存放在應(yīng)用程序的地址空間中。共有四種同步模型：互斥鎖、讀寫鎖、條件變量和信號(hào)。操作系統(tǒng)在創(chuàng)建、撤消和切換進(jìn)程時(shí)付出的開(kāi)銷顯著大于線程。進(jìn)程始終是擁有資源的基本單位，線程只擁有運(yùn)行時(shí)必不可少的資源，本身基本不擁有系統(tǒng)資源，但可以訪問(wèn)隸屬進(jìn)程的資源。進(jìn)程可以并發(fā)執(zhí)行，一個(gè)進(jìn)程的多個(gè)線程也可并發(fā)執(zhí)行。線程在OS 中作為調(diào)度和分派的基本單位，進(jìn)程只作為資源擁有的基本單位。38. 試從調(diào)度性，并發(fā)性，擁有資源及系統(tǒng)開(kāi)銷方面對(duì)進(jìn)程和線程進(jìn)行比較。進(jìn)程是分配資源的基本單位,而線程則是系統(tǒng)調(diào)度的基本單位。34．當(dāng)前有哪幾種高級(jí)通信機(jī)制？答：共享存儲(chǔ)器系統(tǒng)、消息傳遞系統(tǒng)以及管道通信系統(tǒng)?103f?35．消息隊(duì)列通信機(jī)制有哪幾方面的功能？答：（1）構(gòu)成消息（2）發(fā)送消息（3）接收梢息（4）互斥與同步。until falseendparendend33．試比較進(jìn)程間的低級(jí)與高級(jí)通信工具。perform write operation。until falseendwriter:beginrepeatSwait(mx,1,1?！璸erform read operation。beginparbeginreader:beginrepeatSwait(L,1,1)。解法：Var RN integer。endparendend32．什么是信號(hào)量集？試?yán)眯盘?hào)量集寫出讀者一寫者問(wèn)題的解法。consume the item in nextc。signal(empty)。out:=(out+1) mod n。 //k1,k2,...,kn 為執(zhí)行消費(fèi)者進(jìn)程除full 外其余的條件wait(mutex)。endconsumer: beginrepeatwait(full)。signal(s1,s2,s3,...,sn)。signal(mutex)。buffer(in):=nextp。wait(s1,s2,s3,...,sn)。beginparbeginproducer: beginrepeat…produce an item in nextp。buffer: array[0,...,n1] of item。答：為解決并行帶來(lái)的死鎖問(wèn)題，在wait 操作中引入AND 條件，其基本思想是將進(jìn)程在整個(gè)運(yùn)行過(guò)程中所需要的所有臨界資源，一次性地全部分配給進(jìn)程，用完后一次性釋放。until false。endconsumer: beginrepeat(item)。count:=0end在利用管程解決生產(chǎn)者一消費(fèi)者問(wèn)題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：producer: beginpepeatproduce an inem in nestp(item)。if then 。out:=(out+1)mod n。endprocedure entry get(item)beginif count=0 then not 。count:=count+1。buffer(in):=nextp。notfull，notempty:condition。PC 管程可描述如下：type producerconsumer =monitorVar in,out,count:integer。（2）get（item）過(guò)程。30．如何利用管程來(lái)解決生產(chǎn)者與消費(fèi)者問(wèn)題？答：首先建立一個(gè)管程，命名為ProclucerConsumer，包括兩個(gè)過(guò)程：（1）Put（item）過(guò)程。end29．畫圖說(shuō)明管程由哪幾部分組成，為什么要引入條件變量？答：管程由四部分組成：①管程的名稱；②局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說(shuō)明；③對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程；④對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語(yǔ)句； 當(dāng)一個(gè)進(jìn)程調(diào)用了管程，在管程中時(shí)被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進(jìn)程不釋放管程，則其它進(jìn)程無(wú)法進(jìn)入管程，被迫長(zhǎng)時(shí)間地等待。pute data in nextc。nextc:=buffer。until false。buffer:=nextp。gather:beginrepeat……gather data in nextp。until false。signal(empty)。nextc:=buffer。endpute:beginrepeat……wait(full)。signal(full)。buffer:=nextp。wait(empty)。答：a. Var mutex, empty, full: semaphore:=1, 1, 0。Until false。Signal(chopstick[(i+1) mod 5]) ?！?。所有信號(hào)量均被初始化為1，第i 位哲學(xué)家的活動(dòng)可描述為：RepeatWait(chopstick[i])。until false。/* signal(empty)。 /* 考慮循環(huán)，應(yīng)改為: out:=(out+1) mod n。 /* 應(yīng)為wait(full),而且還應(yīng)該在wait(mutex)的前面 */nextc:=buffer(out)。endconsumer:beginrepeatwait(mutex)。/* signal(full)。/* 緩沖池?cái)?shù)組游標(biāo)應(yīng)前移: in:=(in+1) mod n。wait(full)。end26．試修改下面生產(chǎn)者－消費(fèi)者問(wèn)題解法中的錯(cuò)誤:答： producer:beginrepeat…producer an item in nextp。critical sectionunlock(W)。if(W1) then block(W, L)unlock(W): W:=W1。unlock(W): W:=0。試寫出開(kāi)鎖和關(guān)鎖的原語(yǔ)，并利用他們實(shí)現(xiàn)互斥。若signal(mutex)和signal(full)互換位置后只是影響進(jìn)程對(duì)臨界資源的釋放次序，而不會(huì)引起系統(tǒng)死鎖，因此可以互換位置。24．在生產(chǎn)消費(fèi)者問(wèn)題中，如果將兩個(gè)wait 操作即wait(full)和wait(mutex)互換位置，或者將signal(mutex)與signal（full）互換位置，結(jié)果如何？答：將wait(full)和wait(mutex)互換位置后，可能引起死鎖。parendend23．在生產(chǎn)者消費(fèi)者問(wèn)題中，如果缺少了signal(full)或signal(empty),對(duì)執(zhí)行結(jié)果有何影響？答：如果缺少signal(full)，那么表明從第一個(gè)生產(chǎn)者進(jìn)程開(kāi)始就沒(méi)有改變信號(hào)量full 值，即使緩沖池產(chǎn)品已滿，但full 值還是0，這樣消費(fèi)者進(jìn)程執(zhí)行wait(full)時(shí)認(rèn)為緩沖池是空而取不到產(chǎn)品，消費(fèi)者進(jìn)程一直處于等待狀態(tài)。 S8。 wait(i)。begin wait(g)。 signal(j)。begin wait(f)。 signal(i)。begin wait(e)。 signal(h)。begin wait(d)。 signal(g)。begin wait(c)。 signal(f)。 S3。 end。 signal(c)。begin wait(a)。 signal(b)。beginparbeginbegin S1。parendend（b）Var a, b, c, d, e, f, g, h,i,j。 S7。 wait(g)。 end。 S6。 end。 S5。 end。 S4。 end。 S3。 end。 signal(c)。begin wait(a)。 signal(b)。beginparbeginbegin S1。 答：（a）Var a, b, c, d, e, f, g, h。當(dāng)訪問(wèn)臨界資源的進(jìn)程退出臨界區(qū)后，應(yīng)對(duì)mutex執(zhí)行signal 操作，釋放該臨界資源。答：為使多個(gè)進(jìn)程互斥訪