【正文】 執(zhí)行期間，任務(wù)3又先后到達(dá)。圖39是將該算法用于非搶占調(diào)度方式之例。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的先后排序。答：根據(jù)任務(wù)的開(kāi)始截止時(shí)間確定的任務(wù)優(yōu)先級(jí)調(diào)度算法。而非搶占式算法又分為非搶占式輪轉(zhuǎn)和優(yōu)先調(diào)度算法；搶占式調(diào)度算法又分為基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)和立即搶占式優(yōu)先權(quán)調(diào)度算法。若處理機(jī)的處理能力不夠強(qiáng)，有可能因?yàn)樘幚頇C(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)得不到及時(shí)處理，導(dǎo)致發(fā)生難以預(yù)料的后果。所以，多級(jí)反饋隊(duì)列調(diào)度算法能滿足多用戶需求。對(duì)于稍長(zhǎng)作業(yè)，通常只需在第二和第三隊(duì)列各執(zhí)行一時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。13．為什么說(shuō)多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各方面用戶的需求？答：（1）終端型作業(yè)用戶提交的作業(yè)大多屬于較小的交互型作業(yè)，系統(tǒng)只要使這些作業(yè)在第一隊(duì)列規(guī)定的時(shí)間片內(nèi)完成，終端作業(yè)用戶就會(huì)感到滿足。一般應(yīng)考慮三個(gè)因素：系統(tǒng)對(duì)相應(yīng)時(shí)間的要求、就緒隊(duì)列中進(jìn)程的數(shù)目和系統(tǒng)的處理能力。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．在選擇調(diào)度方式和調(diào)度算法時(shí)，應(yīng)遵循的準(zhǔn)則是什么？答：（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ō)明書(shū)。引入中級(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)存。當(dāng)PTDA中的TCB 用完，而進(jìn)程又有新線程時(shí)，只要所創(chuàng)建的線程數(shù)目未超過(guò)系統(tǒng)允許值，系統(tǒng)可在為之分配新的TCB；在撤銷一個(gè)線程時(shí)，也應(yīng)回收線程的所有資源和TCB。答：系統(tǒng)在創(chuàng)建新進(jìn)程時(shí)，分配一個(gè)任務(wù)數(shù)據(jù)區(qū)PTDA，其中包括若干個(gè)線程控制塊TCB空間。內(nèi)核控制線程或輕型進(jìn)程LWP可通過(guò)系統(tǒng)調(diào)用獲得內(nèi)核提供服務(wù)，利用LWP進(jìn)程作為中間系統(tǒng)。答：用戶級(jí)線程是在用戶空間中的實(shí)現(xiàn)的，運(yùn)行在“運(yùn)行時(shí)系統(tǒng)”與“內(nèi)核控制線程”的中間系統(tǒng)上。在內(nèi)核空間里還為每個(gè)內(nèi)核支持線程設(shè)置了線程控制塊，內(nèi)核根據(jù)該控制塊感知某線程的存在并實(shí)施控制。（2）內(nèi)核支持線程：在內(nèi)核支持下運(yùn)行的線程。這種線程的創(chuàng)建、撤銷、線程間的同步與通信等功能，都無(wú)需利用系統(tǒng)調(diào)用實(shí)現(xiàn)。其數(shù)據(jù)結(jié)構(gòu)是存放在受保護(hù)的系統(tǒng)存儲(chǔ)區(qū)中，由OS為它分配空間并進(jìn)行管理。（2）公用信號(hào)量。40．用于實(shí)現(xiàn)線程同步的私用信號(hào)量和公用信號(hào)量之間有何差別？答：（1）私用信號(hào)量。39. 為了在多線程O(píng)S中實(shí)現(xiàn)進(jìn)程之間的同步與通信，通常提供了哪幾種同步機(jī)制？答：同步功能可以控制程序流并訪問(wèn)共享數(shù)據(jù)，從而并發(fā)執(zhí)行多個(gè)線程。（4）系統(tǒng)開(kāi)銷。（3）擁有資源。（2）并發(fā)性。答：（1）調(diào)度性。37．試說(shuō)明線程具有哪些屬性？答：（1)輕型實(shí)體（2）獨(dú)立調(diào)度和分派的基本單位（3）可并發(fā)執(zhí)行（4）共享進(jìn)程資源。36．為什么要在OS 中引入線程？答：在操作系統(tǒng)中引入線程，則是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，使OS具有更好的并發(fā)性，提高CPU的利用率。34．當(dāng)前有哪幾種高級(jí)通信機(jī)制？答：共享存儲(chǔ)器系統(tǒng)、消息傳遞系統(tǒng)以及管道通信系統(tǒng)。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)量集寫(xiě)出讀者一寫(xiě)者問(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ò)程。當(dāng)一個(gè)進(jìn)程調(diào)用了管程，在管程中時(shí)被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進(jìn)程不釋放管程，則其它進(jìn)程無(wú)法進(jìn)入管程，被迫長(zhǎng)時(shí)間地等待。until false。signal(empty)。endpute:beginrepeat……wait(full)。signal(full)。wait(empty)。endb. Var empty, full: semaphore:=1, 0。pute data in nextc。signal(mutex)。wait(mutex)。until false。signal(mutex)。wait(mutex)。gather:beginrepeat……gather data in nextp。28．在測(cè)量控制系統(tǒng)中的數(shù)據(jù)采集任務(wù)，把所采集的數(shù)據(jù)送一單緩沖區(qū)；計(jì)算任務(wù)從該單?！璗hink?！璖ignal(chopstick[i])。Wait(. chopstick[(i+1) mod 5])。end27．試?yán)糜涗浶托盘?hào)量寫(xiě)出一個(gè)不會(huì)出現(xiàn)死鎖的哲學(xué)家進(jìn)餐問(wèn)題的算法.答：Var chopstick:array[0,…,4] of semaphore。consumer item in nextc。out:=out+1。wait(empty)。until false。signal(mutex)。buffer(in):=nextp。wait(mutex)。endcritical sectionunlock(W)。if(W1) then block(W, L)unlock(W): W:=W1。unlock(W): W:=0。試寫(xiě)出開(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。22．試寫(xiě)出相應(yīng)的程序來(lái)描述圖217所示的前驅(qū)圖。利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程描述如下：Var mutex: semaphore:=1；beginparbeginprocess 1: beginrepeatwait(mutex)；critical sectionsignal(mutex)；remainder sectionuntil false；endprocess 2: beginrepeatwait(mutex)；critical sectionsignal(mutex)；remainder sectionuntil false；endparend這樣，每個(gè)欲訪問(wèn)該臨界資源的進(jìn)程在進(jìn)入臨界區(qū)之前，都要先對(duì)mutex 執(zhí)行wait 操作，若該資源此刻未被訪問(wèn)，本次wait 操作必然成功，進(jìn)程便可進(jìn)入自己的臨界區(qū)，這時(shí)若再有其他進(jìn)程也欲進(jìn)入自己的臨界區(qū)，此時(shí)由于對(duì)mutex 執(zhí)行wait操作定會(huì)失敗，因而該進(jìn)程阻塞，從而保證了該臨界資源能被互斥訪問(wèn)。21．如何利用信號(hào)量機(jī)制來(lái)實(shí)現(xiàn)多個(gè)進(jìn)程對(duì)臨界資源的互斥訪問(wèn)？并舉例說(shuō)明之?！?，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，因此應(yīng)調(diào)用wakeup 原語(yǔ)，鏈表中的第一個(gè)等待進(jìn)程喚醒。執(zhí)行一次wait 操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，使系統(tǒng)中可供分配的該類資源減少一個(gè)，因此描:=；0時(shí)，表示該類資源已分配完畢，進(jìn)程應(yīng)調(diào)用block原語(yǔ)自我阻塞，放棄處理機(jī)。19. 試從物理概念上說(shuō)明記錄型信號(hào)量wait 和signal。17．為什么進(jìn)程在進(jìn)入臨界區(qū)之前應(yīng)先執(zhí)行“進(jìn)入?yún)^(qū)”代碼？而在退出前又要執(zhí)行“退出區(qū)”代碼？答：為了實(shí)現(xiàn)多個(gè)進(jìn)程對(duì)臨界資源的互斥訪問(wèn)，必須在臨界區(qū)前面增加一段用于檢查欲訪問(wèn)的臨界資源是否正被訪問(wèn)的代碼，如果未被訪問(wèn)，該進(jìn)程便可進(jìn)入臨界區(qū)對(duì)資源進(jìn)行訪問(wèn)，并設(shè)置正被訪問(wèn)標(biāo)志，如果正被訪問(wèn)，則本進(jìn)程不能進(jìn)入臨界區(qū)，實(shí)現(xiàn)這一功能的代碼為進(jìn)入?yún)^(qū)代碼；在退出臨界區(qū)后，必須執(zhí)行退出區(qū)代碼，用于恢復(fù)未被訪問(wèn)標(biāo)志，使其它進(jìn)程能再訪問(wèn)此臨界資源。舉例：有輸入進(jìn)程A 通過(guò)單緩沖向進(jìn)程B 提供數(shù)據(jù)。舉例：有兩進(jìn)程A 和B，如果A 提出打印請(qǐng)求，系統(tǒng)已把唯一的一臺(tái)打印機(jī)分配給了進(jìn)程B，則進(jìn)程A 只能阻塞；一旦B 釋放打印機(jī)，A 才由阻塞改為就