【正文】 在執(zhí)行過程中就出現(xiàn)了相互制約的新關(guān)系，程序的執(zhí)行出現(xiàn)“走走停?！钡男聽顟B(tài)。因此，盡管進(jìn)程是動態(tài)概念，是程序的執(zhí)行過程，但是，在多個進(jìn)程并行執(zhí)行時，仍然只有一個進(jìn)程占據(jù)處理機(jī)執(zhí)行，而其他并發(fā)進(jìn)程則處于就緒或等待狀態(tài)。 直接制約是由并發(fā)進(jìn)程相互共享對方的私有資源所引起的；間接制約是由競爭共有資源而引起的。（1分）P,V操作原語有如下定義。② 資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。綜合題1如下圖所示的工作模型中，有三個進(jìn)程p0,p1,p2和三個緩沖區(qū)B0,B1,B2. 進(jìn)程之間借助于相鄰緩沖區(qū)進(jìn)行消息傳遞：每個進(jìn)程每次從緩沖區(qū)中取一條消息，經(jīng)加工處理后送入另一個緩沖區(qū)中，三個緩沖區(qū)分別可存放3,2,2個消息。B1S1=2。過程add_buf(type,numb)和take_buf(type,numb)分別用來把緩沖區(qū)numb插入type隊列和從type隊列中取出緩沖區(qū)numb。如果廳內(nèi)不足100人則允許進(jìn)入，進(jìn)入后購票，購票后退出。 mutex:=1。每當(dāng)有讀者進(jìn)入閱覽室時，為了正確地登記，各讀者應(yīng)互斥使用(1’)。請給出兩個方向的人順利過河的同步算法。 //申請過河 V(S1)。請用P,V操作設(shè)計一個同步算法，實(shí)現(xiàn)用戶查詢與訂票功能。　　COBEGIN　PROCESS　PI(I=1，2，……)　　　　　　　 begin　　　　　　　　進(jìn)入售票廳； 購票； 　　　　　　　　　　　退出；　　　　　　　 end　　　COEND(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。 y = 12。3死鎖防止要求進(jìn)程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進(jìn)入死鎖狀態(tài)。 互斥條件——某個資源在一段時間內(nèi)只能由一個進(jìn)程占有，不能同時被兩個及其以上的進(jìn)程占有。即系統(tǒng)中的進(jìn)程處于安全序列中。在T0時刻系統(tǒng)狀態(tài)如表39所試。若出現(xiàn)以下資源分配情況： 進(jìn)程 資源最大請求 已分配資源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2系統(tǒng)剩余資源數(shù)量為(3,2,2)。它們使用資源的次序和數(shù)量如下圖所示。系統(tǒng)還剩2個。 進(jìn)程 最大需求量 當(dāng)前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0(1) 進(jìn)程p4當(dāng)前請求25個資源；(2) 之后p4又提出35個資源的請求。由于系統(tǒng)存在一個進(jìn)程完成的安全序列P1\P3\P4\P2\P5(2’)，故系統(tǒng)狀態(tài)是安全的(2’)。2周轉(zhuǎn)時間是指從作業(yè)進(jìn)入系統(tǒng)開始，到作業(yè)退出系統(tǒng)所經(jīng)歷的時間。這種調(diào)度方式系統(tǒng)開銷大，但系統(tǒng)能及時響應(yīng)請求。而進(jìn)程是已提交完畢的程序所執(zhí)行過程的描述，是資源分配的基本單位。像UNIX這樣的分時系統(tǒng)中，則沒有作業(yè)概念。 5作業(yè)調(diào)度與進(jìn)程調(diào)度之間有什么差別？二者間如何協(xié)調(diào)工作？答：作業(yè)調(diào)度與進(jìn)程調(diào)度之間的差別主要是：作業(yè)調(diào)度是宏觀調(diào)度，它所選擇的作業(yè)只是具有獲得處理機(jī)的資格，但尚未占有處理機(jī)，不能立即在其上實(shí)際運(yùn)行；而進(jìn)程調(diào)度是微觀調(diào)度，動態(tài)地把處理機(jī)實(shí)際地分配給所選擇的進(jìn)程，使之真正活動起來。 ①用一個執(zhí)行時間圖描述使用非搶占式優(yōu)先級算法時各自執(zhí)行這些作業(yè)的情況： ②對于該算法，各個作業(yè)的周轉(zhuǎn)時間是多少?平均周轉(zhuǎn)時間是多少？③對于該算法，各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少？平均帶權(quán)周轉(zhuǎn)時間是多少？解：⑴ 非搶占式優(yōu)先級 J1 J4 J3 J5 J20 10 11 13 18 19(3’) ⑵和⑶ 非搶占式優(yōu)先級 (`7’=1’*7)JOB ts tr te T WJ1 0 10 10 10 1J2 1 1 19 18 18J3 2 2 13 11 J4 3 1 11 8 J5 4 5 18 14 2在一個有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先級調(diào)度算法，進(jìn)程調(diào)度采用搶占式優(yōu)先級調(diào)度算法。 (5’) 下面對x的取值進(jìn)行討論：(`5’=1’*5) 當(dāng)0x=3時，作業(yè)的運(yùn)行順序應(yīng)為E(x),C(3),D(5),B(6),A(9)。3邏輯地址空間由程序中邏輯地址組成的地址范圍叫做邏輯地址空間。10碎片在分區(qū)法中，內(nèi)存出現(xiàn)許多容量太小、無法被利用的小分區(qū)稱作“碎片”。即如果一個進(jìn)程沒有一定數(shù)量的內(nèi)存塊，它很快就發(fā)生缺頁。20快表又叫“聯(lián)想存儲器”。23實(shí)存實(shí)存是指計算機(jī)配置的物理存儲器，它直接向cpu提供程序和數(shù)據(jù)。內(nèi)部碎片出現(xiàn)在一個分區(qū)的內(nèi)部（即被浪費(fèi)的空間），如固定分區(qū)法會產(chǎn)生內(nèi)部碎片 。離散分配——不必占用連續(xù)的內(nèi)存空間,而是”見縫插針”。 ③分頁的作業(yè)地址空間是一維的，分段的作業(yè)的地址空間是二維的。9請求分頁技術(shù)的基本思想是什么？它與簡單分頁技術(shù)之間有何根本區(qū)別？答：請求分頁技術(shù)的基本思想是：當(dāng)一個進(jìn)程的部分頁面在內(nèi)存時就可調(diào)度它運(yùn)行；在運(yùn)行過程中若用到的頁面尚未在內(nèi)存，則把它們動態(tài)換入內(nèi)存。 利用工作集模型可防止抖動，也可以進(jìn)行頁面置換。綜合題1考慮下面頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 當(dāng)內(nèi)存塊數(shù)量分別為3時，試問LRU,FIFO,OPT三種置換算法的缺頁次數(shù)各是多少？（注意，所有內(nèi)存最初都是空的，凡第1次用到的頁面都產(chǎn)生一次缺頁）答：LRU1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6 3 3 3 3 3 6 6 6 6 3 3 3 3 3 3 3 3 3 (2’)FIFO1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3 (2’)OPT1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 6 (2’)內(nèi)存塊數(shù) 置換算法 FIFO LRU OPT3 16 15 11 (3’)2考慮下面存儲訪問序列，該程序大小為460字：10，11，104，170，73，309，185，245，246，434，458，364 設(shè)頁面大小是100字，請給出該訪問序列的頁面走向。(3’)系統(tǒng)為運(yùn)行進(jìn)程分配4個主存塊，采用LRU算法，因此可以列表給出進(jìn)程的缺頁情況： 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 0 2 1 7 6 0 8 8 4 3 2 0 0 2 1 7 6 0 0 8 4 3 3 F F F F F F F F F S F F F S (5’)由上表可見，被淘汰的頁依次為0，2，1，7，6，0，8，4。(3’)因此地址為8762的物理地址為14*512+58=7226。(3’)6有一虛擬存儲系統(tǒng)，采用先進(jìn)先出（FIFO）的頁面淘汰算法。若快表的命中率是85%，則有效存取時間為多少？若快表命中率為50%，那么有效存取時間為多少？解答：（1）分頁需要訪問2次，第一次訪問頁表，第二次執(zhí)行訪內(nèi)操作(2’)；分段需要訪問2次，第一次訪問段表，第二次執(zhí)行訪內(nèi)操作；段頁式需要訪問3次，第一次訪問段表，第二次訪問頁表，第三次執(zhí)行訪內(nèi)操作(2’)。某作業(yè)運(yùn)行中使用的操作數(shù)所在的頁號依次為：4，3，2，1，4，3，5，4，3，2，1，5。1） 寫出邏輯地址的格式2） 若不考慮訪問權(quán)限位，進(jìn)程的頁表有多少項？每項至少多少位？3） 如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)作怎樣的改？答：1）邏輯空間32頁，占5個二進(jìn)制位。假定某時刻用戶頁表中虛頁號和物理塊號對照表如下：虛頁號 0 2 5 17 20物理塊號 5 20 8 14 36求虛地址0A3CH、223CH分別對應(yīng)的物理地址。如果采用LRU算法，缺頁率是多少？如果采用最優(yōu)淘汰算法，其缺頁率又是多少？解: 該序列的頁面走向?yàn)椋?、0、3。整個系統(tǒng)的頁面替換非常頻繁，以致大部分機(jī)器時間都用在來回進(jìn)行的頁面調(diào)度上，只有一小部分時間用于進(jìn)程的實(shí)際運(yùn)算方面。 請求分頁技術(shù)是在簡單分頁技術(shù)基礎(chǔ)上發(fā)展起來的，兩者根本區(qū)別是：請求分頁提供虛擬存儲器，而簡單分頁系統(tǒng)并未提供虛擬存儲器。7在分頁系統(tǒng)中頁面大小由誰決定？頁表的作用是什么？如何將邏輯地址轉(zhuǎn)換成物理地址？答:在分頁系統(tǒng)中頁面大小由硬件決定。 5引入虛擬存儲器后，除了獲得主存“擴(kuò)充”的好處，還有什么好處？答：引入虛存后，程序的地址空間都是虛地址的集合，只有在程序運(yùn)行中通過硬件地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)的相應(yīng)軟件，才能將虛地址變換成主存的實(shí)地址，這將為主存的分配帶來更大的靈活性。3動態(tài)重定位分區(qū)管理方式中如何實(shí)現(xiàn)虛實(shí)地址映射？答：作業(yè)裝入內(nèi)存時，是將該用戶的程序和數(shù)據(jù)原封不動地裝入到內(nèi)存中 。簡答題1解釋固定分區(qū)法和動態(tài)分區(qū)法的基本原理。這樣使計算機(jī)的處理速度降低約一倍。由于所有這些頁面都正在使用，所以剛被淘汰出去的頁很快又被訪問，因而要把它重新調(diào)入。12可重定位地址當(dāng)含有它的程序被重定位時，將隨之被調(diào)整的一種地址。5重定位把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程叫做重定位。 當(dāng)5=x=6時，作業(yè)的運(yùn)行順序應(yīng)為C(3),D(5),E(x),B(6),A(9)。表49 作業(yè)列表作業(yè)名 到達(dá)時間 預(yù)估計時間（分鐘） 優(yōu)先數(shù)A 8:00 40 10B 8:20 30 5C 8:30 50 8D 8:50 20 12其中給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進(jìn)程的優(yōu)先數(shù)。 作業(yè)調(diào)度從外存的后背隊列中選擇一批作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進(jìn)程，這些進(jìn)程被送入就緒隊列。3高級調(diào)度與低級調(diào)度的主要功能是什么？為什么要引入中級調(diào)度？答:高級調(diào)度的主要功能是根據(jù)一定的算法,從輸入的一批作業(yè)中選出若干作業(yè),分配必要的資源,如內(nèi)存、外設(shè)等，為它建立相應(yīng)的用戶作業(yè)進(jìn)程和為其服務(wù)的系統(tǒng)進(jìn)程（如輸入/輸出進(jìn)程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等待進(jìn)程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后做善后處理工作。在用戶向計算機(jī)提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊列中等待執(zhí)行。這種調(diào)度方式實(shí)現(xiàn)簡單，系統(tǒng)開銷小，但系統(tǒng)性能不夠好。4作業(yè)調(diào)度作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。如果能找到一個安全序列，就可以真正進(jìn)行分配。將這15個資源可先分配給p3，p3達(dá)到最大請求，釋放60個；之后可以分配給其他任何進(jìn)程，系統(tǒng)中的進(jìn)程都能順利完成。P2申請2個，系統(tǒng)滿足它，p2接著運(yùn)行；p2完成，釋放資源，使系統(tǒng)資源變?yōu)?個。2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進(jìn)程完成序列。若找不到,可先求出進(jìn)程的剩余請求矩陣. 進(jìn)程 資源最大需求 已分配資源 剩余資源請求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 P2 9, 0, 2 3, 0, 2 6, 0, 0 P3 2, 2, 2 2, 1, 1 0, 1, 1 P4 4, 3, 3 0, 0, 2 4, 3, 1 系統(tǒng)剩余資源向量A=(3,2,2)，在進(jìn)程剩余資源請求矩陣中找，是否有一行，選進(jìn)程P1，滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源，并標(biāo)記它為完成使系統(tǒng)剩余資源向量A=(5,3,2).之后再重復(fù)上述過程，從而找到了一個進(jìn)城完成序列為：P1,P3,P4,P2,P0 (2’)。①T0時刻是否為安全狀態(tài)？若試，請給出安全序列。 若存在循環(huán)等待，設(shè)在環(huán)路上的一組進(jìn)程為{P0,P1,P2,…,Pn}，這里Pi等待進(jìn)程Pi+1占有資源Ri（下角標(biāo)取模運(yùn)算，從而，Pn等待p0占有的資源）。 不可搶占條件——一個進(jìn)程所占有的資源再用完之前，其他進(jìn)程不能強(qiáng)行奪走資源，只能由該進(jìn)程用完之后主動釋放。就是說，在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。進(jìn)程R負(fù)責(zé)從輸入設(shè)備上讀數(shù)據(jù)，每讀一個后把它存放在緩沖區(qū)buf的一個單元中；進(jìn)程C負(fù)責(zé)從緩沖區(qū)讀數(shù)據(jù)并進(jìn)行處理，之后將處理結(jié)果再送入緩沖區(qū)的一個單元中；進(jìn)程P負(fù)責(zé)從緩沖區(qū)讀進(jìn)程C處理的結(jié)果并打印?！?1’)　　意義：(`3’=1’*3)　　S0　S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)　　　S=0　表示售票廳中已有20名顧客(購票者)