./1．若程序A和B單獨執(zhí)行時分別需要1小時和1.5小時,其中CPU工作時間分別為18分鐘和27分鐘。若采用多道程序設(shè)計方法,讓A和B并行工作,假定CPU利用率達到50％,另加15分鐘系統(tǒng)開銷,請問系統(tǒng)效率能提高多少?解：在多道系統(tǒng)中,程序A和B共用的CPU時間為：<18十27>／50％＝90分鐘系統(tǒng)效率提高＝<A和B單獨執(zhí)行的時間總和－多道方式下總時間>／A和B單獨執(zhí)行的時間總和,即<<60十90>－<90十15>>／<60十90>＝45／150＝30％1.假定在單CPU條件下有下列要執(zhí)行的作業(yè)：作業(yè)運行時間優(yōu)先級1102243330作業(yè)到來的時間是按作業(yè)編號順序進行的<即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位>。<1>用一個執(zhí)行時間圖描述在采用非搶占式優(yōu)先級算法時執(zhí)行這些作業(yè)的情況。<2>對于上述算法,各個作業(yè)的周轉(zhuǎn)時間是多少?平均周轉(zhuǎn)時間是多少?<3>對于上述算法,各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少?平均帶權(quán)周轉(zhuǎn)時間是多少?解：<1>非搶占式優(yōu)先級算法作業(yè)的執(zhí)行情況如下：作業(yè)到達時間運行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間101010101.021417164.032313113.7平均周轉(zhuǎn)時間12.3平均帶權(quán)周轉(zhuǎn)時間2.92．若在后備作業(yè)隊列中等待運行的同時有三個作業(yè)1、2、3,已知它們各自的運行時間為a、b、c,且滿足關(guān)系a＜b＜c,試證明采用短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時間。證明：由于短作業(yè)優(yōu)先調(diào)度算法總是在后備作業(yè)隊列中選擇運行時間最短的作業(yè)作為調(diào)度對象,因此對短作業(yè)優(yōu)先調(diào)度算法而言,這三個作業(yè)的總周轉(zhuǎn)時間為T1=a+<a+b>+<a+b+c>=3a+2b+c……<1>若不按短作業(yè)優(yōu)先調(diào)度算法來調(diào)度這三個作業(yè),不失一般性,假定調(diào)度順序為2、l、3,則其周轉(zhuǎn)時間為T2=b+<b+a>+<b+a+c>=3b+2a+c……<2>由<1>、<2>兩式可得：T2-T1=b-a>0由此可見,短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時間。3．設(shè)有4道作業(yè),它們的提交時間及執(zhí)行時間如下：試計算在單道程序環(huán)境下,采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,并指出它們的調(diào)度順序。<時間單位：小時,以十進制進行計算。>解：若采用先來先服務(wù)調(diào)度算法,則其調(diào)度順序為1、2、3、4。平均周轉(zhuǎn)時間T=<2.0十2.8十3.1十3.3>/4＝2.8平均帶權(quán)周轉(zhuǎn)時間W=<1十2.8十6.2十11>／4=5.25若采用短作業(yè)優(yōu)先調(diào)度算法,則其調(diào)度順序為1、4、3、2平均周轉(zhuǎn)時間為T=<2.0+1.8+2.4+3.6>/4=2.45平均帶權(quán)周轉(zhuǎn)時間W=<1十6十4.8十3.6>/4=3.854．假設(shè)有四個作業(yè),它們的提交、運行時間如下表所示。若采用高響應(yīng)比優(yōu)先調(diào)度算法,試問平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間為多少？<時間單位小時,以十進制進行計算。>解：根據(jù)響應(yīng)比的定義每次調(diào)度前計算出各作業(yè)的響應(yīng)比,得到四個作業(yè)的調(diào)度次序為：作業(yè)1、作業(yè)3、作業(yè)2、作業(yè)4。平均周轉(zhuǎn)時間為T=<2.0十2.3十1.6十2.O>/4=1.975平均帶權(quán)周轉(zhuǎn)時間W=<1十4.6十16十5>/4=6.655．有一個具有兩道作業(yè)的批處理系統(tǒng),作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法,進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。在下表所示的作業(yè)序列,作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù),且優(yōu)先數(shù)越小優(yōu)先級越高。<1>列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間<2>計算平均周轉(zhuǎn)時間。分析:在本題中,每個作業(yè)的運行將經(jīng)歷兩級調(diào)度：作業(yè)調(diào)度和進程調(diào)度。作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法,進程調(diào)度采用基于優(yōu)先數(shù)的搶占式調(diào)度算法,高優(yōu)先級的進程可以搶占系統(tǒng)處理機。只有當作業(yè)調(diào)度程序?qū)⒆鳂I(yè)裝入內(nèi)存后,方能參與進程調(diào)度。本題中的批處理系統(tǒng)是兩道作業(yè)系統(tǒng),因此每次只能有兩道作業(yè)進入系統(tǒng)內(nèi)存。本題中的作業(yè)和進程推進順序如下：10：00時,A作業(yè)到達。因系統(tǒng)的后備作業(yè)隊列中沒有其他作業(yè),進程就緒隊列中也沒有進程,故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)A調(diào)入內(nèi)存并將它排在就緒隊列上,進程調(diào)度程序調(diào)度它運行。10：20時,B作業(yè)到達。因系統(tǒng)的后備作業(yè)隊列中沒有其他作業(yè),故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)B調(diào)入內(nèi)存并將它排在就緒隊列上。而作業(yè)B的優(yōu)先級高于作業(yè)A的優(yōu)先級,進程調(diào)度程序停止作業(yè)A的運行,將作業(yè)A放入就緒隊列,調(diào)度作業(yè)B運行。此時,系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運行,作業(yè)A已運行20分鐘,還需運行20分鐘才能完成。10：30時,C作業(yè)到達。因系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運行,故作業(yè)C只能在后備作業(yè)隊列中等待作業(yè)調(diào)度。此時,作業(yè)B已運行了10分針并將繼續(xù)運行,還需運行20分鐘才能完成,作業(yè)A已等待10分針并將繼續(xù)等待、還需運行20分鐘才能完成。10：50時,B作業(yè)運行30分鐘結(jié)束運行,D作業(yè)到達。因系統(tǒng)中只有作業(yè)A在內(nèi)存中運行,作業(yè)后備隊列中有C、D兩道作業(yè),按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略,作業(yè)D被作業(yè)調(diào)度程序選中,裝入內(nèi)存運行,作業(yè)C仍在后備作業(yè)隊列中等待作業(yè)調(diào)度。在內(nèi)存中,作業(yè)A的優(yōu)先級高于作業(yè)D,進程調(diào)度程序調(diào)度作業(yè)A運行,作業(yè)D在就緒隊列中等待進程調(diào)度。此時,作業(yè)A已運行了20分鐘,在就緒隊列中等待了30分鐘,還需運行20分鐘才能完成；作業(yè)C已在后備隊列中等待了20分鐘并將繼續(xù)等待．11：10時,A作業(yè)運行40分針結(jié)束運行。因系統(tǒng)中只有作業(yè)D在內(nèi)存中運行,作業(yè)后備隊列中只有作業(yè)C在等待,作業(yè)調(diào)度程序?qū)⒆鳂I(yè)C裝入內(nèi)存運行。因作業(yè)C的優(yōu)先級高于作業(yè)D,進程調(diào)度程序調(diào)度作業(yè)C運行,作業(yè)D仍在就緒隊列中等待進程調(diào)度。此時作業(yè)D已在就緒隊列中等待了20分鐘并將繼續(xù)等待。12：00時,C作業(yè)運行50分針結(jié)束運行。因系統(tǒng)中只有作業(yè)D在內(nèi)存,進程調(diào)度程序調(diào)度作業(yè)D運行。12：20時,D作業(yè)運行20分鐘結(jié)束運行。解：<1>由上述分析可得出所有作業(yè)的進入內(nèi)存時間和結(jié)束時間：〔2各作業(yè)執(zhí)行時的周轉(zhuǎn)時間為：作業(yè)A：70分鐘作業(yè)B：30分鐘作業(yè)c：90分鐘作業(yè)D：90分鐘作業(yè)的平均周轉(zhuǎn)時間為：<70十30十90十90>／4＝70分鐘。6.已知3個批處理作業(yè)中：第一個作業(yè)10.00時到達,需要執(zhí)行2小時；第二個作業(yè)在10.1時到達,需要執(zhí)行1小時；第三個作業(yè)在10.5小時到達,需要執(zhí)行0.5小時。如果分別采用如下的表1和表2所示的兩種作業(yè)調(diào)度算法。計算各調(diào)度算法下的作業(yè)平均周轉(zhuǎn)時間：<2>這兩種調(diào)度算法各可能是什么作業(yè)調(diào)度算法?表1調(diào)度算法1表2調(diào)度算法2解：<1>采用調(diào)度算法1的作業(yè)運行情況如下表3所示：表3采用調(diào)度算法1的作業(yè)運行情況表采用調(diào)度算法2的作業(yè)運行情況如下表4所示：表4采用調(diào)度算法2的作業(yè)運行情況表調(diào)度算法1是按照作業(yè)到達的先后次序執(zhí)行的,所以它是先來先服務(wù)調(diào)度算法。調(diào)度算法2滿足短作業(yè)優(yōu)先的調(diào)度原則,所以它屬于短作業(yè)優(yōu)先調(diào)度算法。此外,從響應(yīng)比高者優(yōu)先調(diào)度算法來看,當作業(yè)1在12.0完成時,作業(yè)2和作業(yè)3的響應(yīng)比如下：作業(yè)2的響應(yīng)比＝1+1.9/1＝2.9,作業(yè)3的響應(yīng)比＝1+1.5/0.5＝4也即,調(diào)度算法2也可能是響應(yīng)比高者優(yōu)先調(diào)度算法。7．有三個進程P1,P2和P3并發(fā)工作。進程P1需用資源S3和S1；進程P2需用資源S1和S2；進程P3需用資源S2和S3?；卮穑?lt;1>若對資源分配不加限制,會發(fā)生什么情況?為什么?<2>為保證進程正確工作,應(yīng)采用怎樣的資源分配策略?為什么?答：<1>可能會發(fā)生死鎖例如：進程P1,P2和P3分別獲得資源S3,S1和S2后再繼續(xù)申請資源時都要等待,這是循環(huán)等待。<或進程在等待新源時均不釋放已占資源><2>可有幾種答案：A．采用靜態(tài)分配由于執(zhí)行前已獲得所需的全部資源,故不會出現(xiàn)占有資源又等待別的資源的現(xiàn)象<或不會出現(xiàn)循環(huán)等待資源現(xiàn)象>。或B.采用按序分配不會出現(xiàn)循環(huán)等待資源現(xiàn)象?；駽.采用銀行家算法因為在分配時,保證了系統(tǒng)處于安全狀態(tài)。8．設(shè)系統(tǒng)有三種類型的資源,數(shù)量為<4,2,2>,系統(tǒng)中有進程A,B,C按如下順序請求資源：進程A申請<3,2,1>進程B申請<1,0,1>進程A申請<0,1,0>進程C申請<2,0,0>請你給出一種防止死鎖的資源剝奪分配策略,完成上述請求序列,并列出資源分配過程,指明哪些進程需要等待,哪些資源被剝奪。解：①分配策略為：當進程Pi申請ri類資源時,檢查ri中有無可分配的資源,有則分配給Pi；否則將Pi占有的資源全部釋放而進入等待狀態(tài)。<Pi等待原占有的所有資源和新申請的資源>②資源分配過程：剩余資源進程A：<3,2,1><1,0,1>進程B：<1,0,1><0,0,0>

進程C：<2,0,0><1,2,1>進程A：<0,1,0><不滿足><3,2,1>,A的所有資源被剝奪,A處于等待,C,B完成之后,A可完成。9．某系統(tǒng)中有10臺打印機,有三個進程P1,P2,P3分別需要8臺,7臺和4臺。若P1,P2,P3已申請到4臺,2臺和2臺。試問：按銀行家算法能安全分配嗎？請說明分配過程。答：系統(tǒng)能為進程P3分配二臺打印機。因為盡管此時10臺打印機已分配給進程P14臺,P22臺和P34臺,全部分配完,但P3已分配到所需要的全部4臺打印機,它不會對打印機再提出申請,所以它能順利運行下去,能釋放占用的4臺打印機,使進程P1,P2均可能獲得乘余的要求4臺和5臺,按銀行家算法是安全的。10．在生產(chǎn)者—消費者問題中,如果對調(diào)生產(chǎn)者進程中的兩個P操作和兩個V操作,則可能發(fā)生什么情況?解：如果對調(diào)生產(chǎn)者進程中的兩個P操作和兩個v操作,則生產(chǎn)者—消費者問題的同步描述為：intfull=0;intempty=n;intmutex=1;main<>{cobeginproducer<>;consumer<>;coend}producer<>{while<生產(chǎn)未完成>{生產(chǎn)一個產(chǎn)品；p<mutex>;p<empty>;送一個產(chǎn)品到有界緩沖區(qū)；v<full>;v<mutex>;}}consumer<>{while<還要繼續(xù)消費>{p<full>;p<mutex>;從有界緩沖區(qū)中取產(chǎn)品；v<mutex>;v<empty>;消費一個產(chǎn)品；}}由于V操作是釋放資源,因此對調(diào)V操作的次序無關(guān)緊要。而對調(diào)P操作的次序則可能導(dǎo)致死鎖。這是因為對調(diào)P操作后,有可能出現(xiàn)這樣一種特殊情況：在某一時刻緩沖區(qū)中己裝滿了產(chǎn)品且緩沖區(qū)中無進程工作<這時信號量full的值為n,信號量empty的值為0,信號量mutex的值為1>,若系統(tǒng)此時調(diào)度生產(chǎn)者進程運行,生產(chǎn)者進程又生產(chǎn)了一個產(chǎn)品,它執(zhí)行P<mutex>并順利進入臨界區(qū)<這時mutex值為0>,隨后它執(zhí)行p<empty>時因沒有空閑緩沖單元而受阻等待,等待消費者進程進入緩沖區(qū)取走產(chǎn)品以釋放出緩沖單元；消費者進程執(zhí)行p<full>后再執(zhí)行p<mutex>時,因緩沖區(qū)被生產(chǎn)者進程占據(jù)而無法進入。這樣就形成了生產(chǎn)者進程在占有臨界資源的情況下,等待消費者進程取走產(chǎn)品,而消費者進程又無法進入臨界區(qū)取走產(chǎn)品的僵局,此時兩進程陷入死鎖。11．n個進程共享某種資源R,該資源共有m個可分配單位,每個進程一次一個地申請或釋放資源單位。假設(shè)每個進程對該資源的最大需求量均小于m,且各進程最大需求量之和小于m十n,試證明在這個系統(tǒng)中不可能發(fā)生死鎖。解：設(shè)max<i>表示第i個進程的最大資源需求量,need<i>表示第i個進程還需要的資源量,alloc<i>表示第i個進程己分配的資源量。由題中所給條件可知：max<1>+max<2>+…＋max<n>=<need<1>+…+need<n>>+<alloc<1>+…+alloc<n>><m+n如果在這個系統(tǒng)中發(fā)生了死鎖,那么一方面m個資源應(yīng)該全部分配出去,即alloc<1>+…+alloc<n>=m另一方面所有進程將陷入無限等待狀態(tài)。由上述兩式可得：need<1>+…+need<n><n上式表示死鎖發(fā)生后,n個進程還需要的資源量之和小于n,這意味著此刻至少存在一個進程i,need<i>＝0,即它己獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源,那么它就能執(zhí)行完成并釋放它占有的資源,這與前面的假設(shè)矛盾,從而證明在這個系統(tǒng)中不可能發(fā)生死鎖。12．在銀行家算法中,若出現(xiàn)下述資源分配情況：試問：<1>該狀態(tài)是否安全?<2>如果進程P2提出請求Request2<1,2,2,2>后,系統(tǒng)能否將資源分配給它?解：<1>利用銀行家算法對此時刻的資源分配情況進行分析,可得此時刻的安全性分析情況：從上述分析中可以看出,此時存在一個安全序列{P0,P3,P4,P1,P2},故該狀態(tài)是安全的。<2>P2提出請求Request2<1,2,2,2>,按銀行家算法進行檢查：Request2<1,2,2,2>≤Need2<2,3,5,6>Request2<1,2,2,2>≤Available<1,6,2,2>試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu),資源分配情況如下：再利用安全性算法檢查系統(tǒng)是否安全,可用資源Available<0,4,0,0>己不能滿足任何進程的需要,故系統(tǒng)進入不安全狀態(tài),此時系統(tǒng)不能將資源分配給P2。13．有相同類型的5個資源被4個進程所共享,且每個進程最多需要2個這樣的資源就可以運行完畢。試問該系統(tǒng)是否會由于對這種資源的競爭而產(chǎn)生死鎖。答：該系統(tǒng)不會由于對這種資源的競爭而產(chǎn)生死鎖。因為在最壞情況下,每個進程都需要2個這樣的資源,且每個進程都已申請到了1個資源,那么系統(tǒng)中還剩下1個可用資源。無論系統(tǒng)為了滿足哪個進程的資源申請而將資源分配給該進程,都會因為該進程已獲得了它所需要的全部資源而確保它運行完畢,從而可將它占有的2個資源歸還給系統(tǒng),這就保證了其余三個進程能順利運行。由此可知,該系統(tǒng)不會由于對這種資源的競爭而產(chǎn)生死鎖。14．考慮下列資源分配策略：對資源的申請和釋放可以在任何時候進行。如果一個進程提出資源請求時得不到滿足,若此時無由于等待資源而被阻塞的進程,則自己就被阻塞；若此時已有等待資源而被阻塞的進程,則檢查所有由于等待資源而被阻塞的進程。如果它們有申請進程所需要的資源,則將這些資源取出分配給申請進程。例如,考慮一個有3類資源的系統(tǒng),系統(tǒng)所有可用資源為<4,2,2>,進程A申請<2,2,1>,可滿足；進程B申請<1,0,1>,可滿足；若A再申請<0,0,1>,則被阻塞。此時,若C請求<2,0,0>,它可以分到剩余資源<1,0,0>,并從A已分到的資源中獲得一個資源,于是進程A的分配向量變成<1,2,1>而需求向量變成<1,0,1>。①這種分配策略會導(dǎo)致死鎖嗎?如果會,請舉一個例子；如果不會,請說明產(chǎn)生死鎖的哪一個必要條件不成立。②這種分配方式會導(dǎo)致某些進程的無限等待嗎?為什么?解：①本題所給的資源分配策略不會產(chǎn)生死鎖。因為本題給出的分配策略規(guī)定若一進程的資源得不到滿足,則檢查所有由于等待資源而被阻塞的進程,如果它們有申請進程所需要的資源,則將這些資源取出分配給申請進程。從而破壞了產(chǎn)生死鎖必要條件中的不剝奪條件,這樣系統(tǒng)就不會產(chǎn)生死鎖。②這種方法會導(dǎo)致某些進程無限期的等待。因為被阻塞進程的資源可以被剝奪,所以被阻塞進程所擁有的資源數(shù)量在其被喚醒之前只可能減少。若系統(tǒng)中不斷出現(xiàn)其他進程申請資源,這些進程申請的資源與被阻塞進程申請或擁有的資源類型相同且不被阻塞,則系統(tǒng)無法保證被阻塞進程一定能獲得所需要的全部資源。例如,本題中的進程A申請<2,2,1>后再申請<0,0,1>被阻塞。此后,進程C又剝奪了進程A的一個資源,使得進程A擁有的資源變?yōu)?lt;1,2,1>,其需求向量為<1,0,1>。之后,若再創(chuàng)建的進程總是只申請第1和第3類資源,總是占有系統(tǒng)所剩下的第1和第3類資源的全部且不阻塞,那么進程A將會無限期地等待。15．一臺計算機有8臺磁帶機。它們由N個進程競爭使用,每個進程可能需要3臺磁帶機。請問N為多少時,系統(tǒng)沒有死鎖危險,并說明原因。解：當N為1,2,3時,系統(tǒng)沒有產(chǎn)生死鎖的危險。因為,當系統(tǒng)中只有1個進程時,它最多需要3臺磁帶機,而系統(tǒng)有8臺磁帶機,其資源數(shù)目足夠系統(tǒng)內(nèi)的1個進程使用,因此絕不可能發(fā)生死鎖：當系統(tǒng)中有2個進程時,最多需要6臺磁帶機,而系統(tǒng)有8臺磁帶機,其資源數(shù)目也足夠系統(tǒng)內(nèi)的2個進程使用,因此也不可能發(fā)生死鎖；當系統(tǒng)中有3個進程時,在最壞情況下,每個進程都需要3個這樣的資源,且假定每個進程都已申請到了2個資源,那么系統(tǒng)中還剩下2個可用資源,無論系統(tǒng)為了滿足哪個進程的資源申請而將資源分配給該進程,都會因為該進程已獲得了它所需要的全部資源而確保它運行完畢,從而可將它占有的3個資源歸還給系統(tǒng),這就保證了其余進程能順利運行完畢。由此可知,當N為1,2,3時,該系統(tǒng)不會由于對這種資源的競爭而產(chǎn)生死鎖。16．假設(shè)就緒隊列中有10個進程,系統(tǒng)將時間片設(shè)為200ms,CPU進行進程切換要花費10ms,試問系統(tǒng)開銷所占的比率約為多少?解：因就緒隊列中有10個進程,它們以時間片輪轉(zhuǎn)的方式使用CPU,時間片長度為200ms。當一個時間片用完時．調(diào)度進程將當前運行進程設(shè)置為就緒狀態(tài)并放入就緒隊列尾,再從就緒隊列隊首選擇進程投入運行,這一過程<進程切換>要花費時間l0ms。因此系統(tǒng)開銷所占比率為：10/<200+10>=4.8%17.如果P、V操作設(shè)計不當,則有可能產(chǎn)生死鎖。假如系統(tǒng)中有輸入機和打印機兩類資源各一臺,有兩個進程P1和P2都要求使用輸入機和打印機。我們可以利用P、V操作來實現(xiàn)互斥：定義s1、s2分別為代表輸入機和打印機能否被使用的信號量,初值均為1,并且按如下方法請求使用和歸還資源：ProcessP1beginP<s1>；使用輸入機；P<s2>；使用打印機；V<s2>；V<s1>；End;ProcessP2BeginP<s2>；使用打印機；P<s1>；使用輸入機；V<s2>；V<s1>；End；結(jié)合死鎖產(chǎn)生的必要條件,分析此種方法是否會造成死鎖,若不會,給出理由；若會產(chǎn)生死鎖,則修改上面程序,使P1、P2兩進程能夠互斥的使用資源,并且能夠順利完成。解：此種方法可能會出現(xiàn)P1得到輸入機而P2得到打印機,雙方在不釋放已有資源的情況下,又去申請新的資源,從而造成死鎖?？梢圆捎脼橘Y源編號的方法,讓進程按序申請資源,來避免死鎖。程序可修改如下：ProcessP2BeginP<s2>；使用輸入機；P<s1>；使用打印機；V<s2>；V<s1>；End；18．假定某計算機系統(tǒng)有R1和R2兩類可再使用資源<其中R1有兩個單位,R2有一個單位>．它們被進程P1和P2所共享,且已知兩個進程均以申請R1申請R2申請R1釋放R1釋放R2釋放R所示的順序使用兩類資源。試求出系統(tǒng)運行過程中可能到達的死鎖點．并畫出死鎖點的資源分配圖<或稱進程一資源圖>。解：該題答案不惟一。從已知條件可知,P1、P2兩進程都是各自按順序申請系統(tǒng)中所有資源,并在全部得到滿足之后才會依次釋放；由此可得,只要讓Pl、P2分別占有其中某個資源,即不把全部資源都交給一個進程,則會發(fā)生死鎖。進程一資源圖如下：19．某系統(tǒng)有R1、R2和R3共3種資源．在T0時刻P1、P2、P3和P4這4個進程對資源的占用和需求情況見下表,此刻系統(tǒng)的可用資源向量為<2,1,2>,問題：<1>將系統(tǒng)中各種資源總數(shù)和此刻各進程對各資源的需求數(shù)目用向量或矩陣表示出來；<2>如果此時P1和P2均發(fā)出資源請求向量Request<1,0,1>,為了保持系統(tǒng)安全性,應(yīng)該如何分配資源給這兩個進程?說明你所采用策略的原因；<3>如果<2>中兩個請求立刻得到滿足后,系統(tǒng)此刻是否處于死鎖狀態(tài)?解：〔1系統(tǒng)資源總數(shù)為<9,3,6>。各進程對資源需求矩陣為：222202103420<2>采用銀行家算法進行計算得：系統(tǒng)不可以將資源分配給進程P1,雖然剩余資源還可以滿足進程P1現(xiàn)在的需求,但是一旦分配給進程P1后,就找不到一個安全執(zhí)行的序列保證各個進程能夠正常運行下去。因此進程P1進入等待狀態(tài)。系統(tǒng)可以滿足P2的請求,因為分配完成后,至少還可以找到一個安全序列,如<P2P1P3P4>,使各進程可以運行至結(jié)束。<3>系統(tǒng)滿足進程P1和P2的請求后,沒有立即進入死鎖狀態(tài),因為此時所有進程還處于運行狀態(tài),沒有被阻塞；只有等到進程繼續(xù)申請資源井因得不到滿足而全部進人阻塞狀態(tài),死鎖才真正發(fā)生了。1．在一個請求分頁存儲管理系統(tǒng)中,一個作業(yè)的頁面走向為4、3、2、1、4、3、5、4、3、2、1、5,當分配給該作業(yè)的物理塊數(shù)分別為3、4時,試計算采用下述頁面淘汰算法時的缺頁次數(shù)<假設(shè)開始執(zhí)行時主存中沒有頁面>,并比較所得結(jié)果。<1>最佳置換法<OPT><2>先進先出法<FIFO>解：<1>根據(jù)所給頁面走向,使用最佳頁面置換算法時,頁面置換情況如下：<略>物理塊為3時,缺頁次數(shù)為7；物理塊為4時,缺頁次數(shù)為6。由上述結(jié)果可以看出,增加分配給作業(yè)的內(nèi)存塊數(shù)可以降低缺頁次數(shù)。<2>根據(jù)所給頁面走向,使用先進先出頁面置換算法時,頁面置換情況如下：〔略物理塊為3時,缺頁次數(shù)為9；物理塊為4時,缺頁次數(shù)為10。由上述結(jié)果可以看出,對先進先出算法而言,增加分配給作業(yè)的內(nèi)存塊數(shù)反而出現(xiàn)缺頁次數(shù)增加的異?，F(xiàn)象。2．某采用頁式存儲管理的系統(tǒng),接收了一個共7頁的作業(yè),作業(yè)執(zhí)行時依次訪問的頁為：1、2、3、4、2、1、5、6、2、1、2、3、7。當內(nèi)存塊數(shù)量為4時,請分別用先進先出<FIFO>調(diào)度算法和最近最少使用<LRU>調(diào)度算法,計算作業(yè)執(zhí)行過程中會產(chǎn)生多少次缺頁中斷?寫出依次產(chǎn)生缺頁中斷后應(yīng)淘汰的頁。<所有內(nèi)存開始時都是空的,凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計算過程>答：采用先進先出<FIFO>調(diào)度算法,共產(chǎn)生10次缺頁中斷,依次淘汰的頁是1、2、3、4、5、6,〔頁面調(diào)度過程略；采用最近最少使用<LRU>調(diào)度算法,共產(chǎn)生8次缺頁中斷,依次淘汰的頁是3、4、5、6,〔頁面調(diào)度過程略。3．在一個多道程序系統(tǒng)中,設(shè)用戶空間為200K,主存空間管理采用最先適應(yīng)分配算法,并采用先來先服務(wù)算法管理作業(yè)。今有如下所示的作業(yè)序列,請列出各個作業(yè)開始執(zhí)行時間、完成時間和周轉(zhuǎn)時間?！沧⒁猓汉雎韵到y(tǒng)開銷,時間用10進制。作為名進入輸入井時間需計算時間主存需求量JOB18.0時1小時20KJOB28.2時0.6小時60KJOB38.4時0.5小時25KJOB48.6時1小時20K答：作業(yè)開始時間完成時間周轉(zhuǎn)時間JOB1891JOB299.61.4JOB39.610.11.7JOB410.111.12.54．設(shè)某作業(yè)的程序部分占一頁,A是該作業(yè)的一個100×100的數(shù)組,在虛空間中按行主秩序存放〔即按如下順序存放：A〔1,1,A〔1,2,…A〔l,100,A〔2,1,…A〔2,100…A〔100,1…A〔100,100,頁面大小為100個字,駐留集為2個頁幀。若采用LRU替換算法,則下列兩種對A進行初始化的程序段引起的缺頁中斷次數(shù)各是多少？并說明原因。<aforj:=1to100dofori:＝1to100doA〔i,j:=0<bfori:=1to100doforj:＝1to100doA〔i,j:=0答：由于程序占1頁,故放入一個頁幀中。只發(fā)生1次缺頁中斷。<a>種情況是按A〔1,1、A〔2,l…A〔100,1A〔1,2,A〔2,2…,A〔100,2,A〔1,100、A〔2,100…A〔100,100次序初始化,而數(shù)組的存放為A〔1,1,A〔1,2…A〔1,100…………1頁A〔2,1,A〔2,2…A〔2,100…………2頁………A〔100,1A〔100,2…A〔100,100……100頁故對數(shù)組中每個元素初始化時,均要發(fā)生缺頁中斷,共發(fā)生100×100次再加上程序加載所發(fā)生的一次,共計10001次缺頁中斷?！瞓種情況是按：A〔1,1、A〔1,2…A〔1,100,A〔2,1,A〔2,2…,A〔2,100………A〔100,1A〔100,2…A〔100,100次序進行初始化,則每初始化一頁發(fā)一次缺頁中斷,所以共101次。5．在一個采用頁式虛擬存儲管理的系統(tǒng)中,有一用戶作業(yè),它依次要訪問的字地址序列是：115,228,120,88,446,102,321,432,260,167,若該作業(yè)的第0頁已經(jīng)裝入主存,現(xiàn)分配給該作業(yè)的主存共300字,頁的大小為100字,請回答下列問題：按〔1FIFO調(diào)度算法〔2LRU調(diào)度算法將產(chǎn)生多少次缺頁中斷,缺頁中斷率為多少,依次淘汰的頁號是什么。答：〔1按FIFO調(diào)度算法將產(chǎn)生5次缺頁中斷；依次淘汰的頁號為：0,1,2；缺頁中斷率為：5/10=50%?！?按LRU調(diào)度算法將產(chǎn)生6次缺頁中斷；依次淘汰的頁號為：2,0,1,3；缺頁中斷率為：6/10=60%。6．己知頁面走向為1、2、1、3、1、2、4、2、1、3、4,且開始執(zhí)行時主存中沒有頁面。若只給該作業(yè)分配2個物理塊,當采用FIFO頁面淘汰算法時缺頁率為多少?假定現(xiàn)有一種淘汰算法,該算法淘汰頁面的策略為當需要淘汰頁面時,就把剛使用過的頁面作為淘汰對象,試問就相同的頁面走向,其缺頁率又為多少?解：根據(jù)所給的頁面走向,采用FIFO置換算法的頁面置換情況如下：從上述頁面置換中可以看出：頁面引用次數(shù)為11次,缺頁次數(shù)為9次,所以缺頁率為9/11。若采用后一種置換算法：其頁面置換情況如下：從上述頁面置換圖可以看出：頁面引用次數(shù)為11次,缺頁次數(shù)為8次,所以缺頁率為8/11。7．在一個請求分頁系統(tǒng)中,假定系統(tǒng)分配給一個作業(yè)的物理塊數(shù)為3,并且此作業(yè)的頁面走向為2、3、2、1、5、2、4、5、3、2、5、2。試用FIFO和LRU兩種算法分別計算出程序訪問過程中所發(fā)生的缺頁次數(shù)。解：在本題中,分配給作業(yè)的物理塊數(shù)為3。根據(jù)所給頁面走向,使用FIFO算法時,頁面置換情況如下：缺頁次數(shù)為9。根據(jù)所給頁面走向,使用LRU算法時,頁面置換情況如下：缺頁次數(shù)為7。8．有一頁式系統(tǒng),其頁表存放在主存中,<1>如果對主存的一次存取需要1.5微秒,試問實現(xiàn)一次頁面訪問的存取時間是多少?<2>如果系統(tǒng)加有快表,平均命中率為85％,當頁表項在快表中時,其查找時間忽略為0,試問此時的存取時間為多少?解：若頁表存放在主存中,則要實現(xiàn)一次頁面訪問需兩次訪問主存,一次是訪問頁表,確定所存取頁面的物理地址,第二次才根據(jù)該地址存取頁面數(shù)據(jù)。<1>由于頁表存放在主存,因此CPU必須兩次訪問主存才能獲得所需數(shù)據(jù),所以實現(xiàn)一次頁面訪問的存取時間是1.5×2＝3微秒<2>在系統(tǒng)增加了快表后,在快表中找到頁表項的概率為85％,所以實現(xiàn)一次頁面訪問的存取時間為0.85×1.5十<1—0.85>×2×1.5＝1.725微秒9．在一個段式存儲管理系統(tǒng)中,段表內(nèi)容如下：試求下述邏輯地址對應(yīng)的物理地址是什么？解：<1>由于第0段的內(nèi)存始址為210,段長為500,故邏輯地址[O,430]是合法地址。邏輯地址[0,430]對應(yīng)的物理地址為210十430＝640。<2>由于第1段的內(nèi)存始址為2350,段長為20,故邏輯地址[1,10]是合法地址。邏輯地址[1,10]對應(yīng)的物理地址為2350+10=2360。<3>由于第2段起始地址為100,段長為90,所給邏輯地址[2,500]非法。<4>由于第3段的內(nèi)存始址為1350,段長為590,故邏輯地址[3,400]是合法地址。邏輯地址[3,400]對應(yīng)的物理地址為1350十400＝1750。<5>由于第4段的內(nèi)存始址為1938,段長為95,所給邏輯地址[4,l12]非法。<6>由于系統(tǒng)中不存在第5段,所給邏輯地址[5,32]非法。10．在某系統(tǒng)中,采用固定分區(qū)分配管理方式,內(nèi)存分區(qū)<單位字節(jié)>情況如圖a所示?，F(xiàn)有大小為lK、9K、33K、121K的多個作業(yè)要求進入內(nèi)存,試畫出它們進入內(nèi)存后的空間分配俏況,并說明主存浪費有多大?解：從圖a可以看出,該系統(tǒng)中共有四個分區(qū),第一分區(qū)的大小為8k,第二分區(qū)的大小為32K,第三分區(qū)的大小為120K,第四分區(qū)的大小為332K。作業(yè)進入系統(tǒng)后的內(nèi)存分配情況,如圖b所示<每個分區(qū)中未被利用的那部分空間用陰影表示>：〔圖a某系統(tǒng)內(nèi)存分配情況〔圖b作業(yè)進入系統(tǒng)后的分配情況從圖b可以看出,作業(yè)進入系統(tǒng)后,第一分區(qū)剩余空間為7K,第二分區(qū)剩余空間為23K,第三分區(qū)剩余空間為87K,第四分區(qū)剩余空間為211K。主存空間浪費328K。11．下表給出了某系統(tǒng)中的空閑分區(qū)表,系統(tǒng)采用可變式分區(qū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：96k、20K、200k。若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列,試問哪一種算法可以滿足該作業(yè)序列的請求,為什么?空閑分區(qū)表：解：若采用最佳適應(yīng)算法,在申請96K存儲區(qū)時,選中的是5號分區(qū),5號分區(qū)大小與申請空間大小一致,應(yīng)從空閑分區(qū)表中刪去該表項；接著申請20K時,選中1號分區(qū),分配后l號分區(qū)還剩下12K；最后申請200K,選中4號分區(qū),分配后剩下18K。顯然采用最佳適應(yīng)算法進行內(nèi)存分配,可以滿足該作業(yè)序列的需求。為作業(yè)序列分配了內(nèi)存空間后,空閑分區(qū)表如表a所示。若采用首次適應(yīng)算法,在申請96K存儲區(qū)時,選中的是4號分區(qū),進行分配后4號分區(qū)還剩下122K；接著申請20K,選中1號分區(qū),分配后剩下12K；最后申請200K,現(xiàn)有的五個分區(qū)都無法滿足要求,該作業(yè)等待。顯然采用首次適應(yīng)算法進行內(nèi)存分配,無法滿足該作業(yè)序列的需求。這時的空閱分區(qū)表如表b所示。<分配后的空閑分區(qū)表a><分配后的空閑分區(qū)表b>12．在某個采用頁式存儲管理的系統(tǒng)中,現(xiàn)有J1,J2,J3共3個作業(yè)同駐主存。其中J2有4個頁面,被分別裝入到主存的第3,4,6,8塊中。假定頁面和存儲塊的大小均為1024字節(jié),主存容量為10K字節(jié)。<1>寫出J2的頁面映像表；<2>當J2在CPU上運行時,執(zhí)行到其地址空間第500號處遇到一條傳指令MOV2100,3100請用地址變換圖計算出MOV指令中兩個操作數(shù)的物理地址。解：該題已知條件很多,但實質(zhì)還是給出邏輯地址,要求轉(zhuǎn)換成物理地址。首先得出頁表項如圖1所示,頁面大小為1024字節(jié),可得頁內(nèi)位移為10位。邏輯地址2100頁號為2,頁內(nèi)位移52；3100頁號為3．頁內(nèi)位移28。轉(zhuǎn)換過程如圖2所示?！矆D1〔圖213．假設(shè)有一臺計算機,它有1M內(nèi)存,操作系統(tǒng)占用200K,每個用戶進程也占用200K,用戶進程等待I/O的時間為80％,若增加lM內(nèi)存,則CPU的利用率將提高多少?答：由題目所給條件可知,當前IM內(nèi)存可支持4個用戶進程,由于每個用戶進程等待I/O的時間為80％,故CPU的利用率為：1一<80％>4＝1一<0．8>4＝59％若增加1M內(nèi)存,則系統(tǒng)中可同時運行9個進程,則CPU的利用率為I一<0.8>9＝87％故增加1M內(nèi)存使CPU的利用串提高了87％÷59％＝147％147％一100％＝47％所以增加1M內(nèi)存使CPU的利用率提高了47％的利用率。1．若干個等待訪問磁盤者依次要訪問的柱面為20,44,40,4,80,12,76,假設(shè)每移動一個柱面需要3毫秒時間,移動臂當前位于40號柱面,請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間?！?先來先服務(wù)算法；〔2最短尋找時間優(yōu)先算法。解：〔13毫秒×292=876毫秒〔23毫秒×120=360毫秒〔注：各算法使移動臂的移動次序和移動的柱面數(shù)如下：〔140→20→44→40→4→80→12→76〔20〔24〔4〔36〔76〔68〔64共移動292柱面〔240→44→20→12→4→76→80〔4〔24〔8〔8〔72〔4共移動120柱面2．有如下請求磁盤服務(wù)的隊列,要訪問的磁道分別是98、183、37、122、14、124、65、67?，F(xiàn)在磁頭在53道上,若按最短尋道時間優(yōu)先法,磁頭的移動道數(shù)是多少?解：最短尋道時間優(yōu)先法總是讓查找時間最短的那個請求先執(zhí)行,而不考慮請求訪問者到來的先后時間。即靠近當前移動臂位置的請求訪問者將優(yōu)先執(zhí)行。當前磁頭在53道上則總的移動道為：12＋2＋30＋23＋84＋24＋2＋59＝2363．若磁頭的當前位置為100磁道,磁頭正向磁道號增加方向移動。現(xiàn)有一磁盤讀寫請求隊列：23,376,205,132,19,61,190,398,29,4,18,40。若采用先來先服務(wù)、最短尋道時間優(yōu)先和掃描算法,試計算出平均尋道長度各為多少?解：<1>采用先來先服務(wù)磁盤調(diào)度算法,進行調(diào)度的情況為：〔從100磁道開始移動磁道數(shù)總數(shù)為1596,平均尋道長度為133。<2>采用最短尋道時間優(yōu)先磁盤調(diào)度算法,進行調(diào)度的情況為〔從100磁道開始移動磁道總數(shù)為700,平均尋道長度為58.3?！?采用掃描算法,進行調(diào)度的情況為：〔從100磁道開始,磁頭向磁道號增加方向移動移動磁道總數(shù)為692,平均尋道長度為57.7。4．假定在某磁盤上移動臂剛從58號柱上完成任務(wù),目前正在96號柱面上讀信息,并有下列請求序列等待訪問磁盤：175,52,157,36,159,106,108,72<1>請分別使用先來先服務(wù)調(diào)度算法、最短尋找時間優(yōu)先算法、電梯調(diào)度算法,排出實際處理上述請求的次序。<2>計算<1>中三種算法下移動臂需要移動的距離。解：<1>使用先來先服務(wù)調(diào)度算法,按照訪問者的失后次序進行訪問,處理次序依次為：96,175,52,157,36,159,106,108,72。使用最短