【正文】 微觀調度，動態(tài)地把處理機實際地分配給所選擇的進程，使之真正活動起來。 進程只有在得到CPU之后才能真正活動起來，所有就緒進程經由進程調度才能獲得CPU的控制權。 為了使內存中同時存放的進程數目不至于太多，有時需要把某些進程從內存移到外存上，以減少多道程序的數目，為此設立了中級調度. 4處理機調度一般分為哪三級？其中哪一級調度必不可少？為什么？答：處理機調度一般可分為高級調度（作業(yè)調度）、中級調度和低級調度（進程調度） 。3高級調度與低級調度的主要功能是什么？為什么要引入中級調度？答:高級調度的主要功能是根據一定的算法,從輸入的一批作業(yè)中選出若干作業(yè),分配必要的資源,如內存、外設等，為它建立相應的用戶作業(yè)進程和為其服務的系統進程（如輸入/輸出進程），最后把它們的程序和數據調入內存，等待進程調度程序對其執(zhí)行調度，并在作業(yè)完成后做善后處理工作。像UNIX這樣的分時系統中，則沒有作業(yè)概念。且必須至少由一個進城組成，但反過來不成立。任一進程，只要它被創(chuàng)建，總有相應的部分存在內存中。在用戶向計算機提交作業(yè)之后，系統將它放入外存中的作業(yè)等待隊列中等待執(zhí)行。而進程是已提交完畢的程序所執(zhí)行過程的描述，是資源分配的基本單位。作業(yè)是用戶需要計算機完成某項任務，而要求計算機所做工作的集合。 程序和數據完成用戶所要求的業(yè)務處理工作，作業(yè)說明書則體現用戶的控制意圖。這種調度方式實現簡單，系統開銷小，但系統性能不夠好。這種調度方式系統開銷大，但系統能及時響應請求。引入交換調度的目的是為了解決主存緊張和提高主存的利用效率。實際上，進程調度完成一臺物理的cpu轉變成多臺虛擬（或邏輯）的cpu的工作。4作業(yè)調度作業(yè)調度的主要任務是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉換。2周轉時間是指從作業(yè)進入系統開始，到作業(yè)退出系統所經歷的時間。(3’)(3) 系統初始配置的各類資源分別為(3 ,9 , 12 , 12 )。由此可見，仍然可以找到一個與(1)相同的安全序列。如果能找到一個安全序列，就可以真正進行分配。由于系統存在一個進程完成的安全序列P1\P3\P4\P2\P5(2’)，故系統狀態(tài)是安全的(2’)。（1） 用銀行家算法試判斷系統當前狀態(tài)是否安全？（2） 當進程p3提出對資源r3的剩余請求時，能否滿足她？（3） 系統初始配置的各類資源分別為多少？ ， .解答：系統剩余資源向量 A=(1, 2, 3, 0) 。(2’)5系統中有五個進程，分別為p1\p2\p3\p4\p5，四類資源分別為r1\r2\r3\r4。將這15個資源可先分配給p3，p3達到最大請求，釋放60個；之后可以分配給其他任何進程，系統中的進程都能順利完成。 進程 最大需求量 當前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0(1) 進程p4當前請求25個資源；(2) 之后p4又提出35個資源的請求。在某時刻系統中的進程已獲得的資源和最大請求資源如下所示，請用銀行家算法分別判斷完成下列請求時，系統是否安全？若安全，請給出進程的完成序列。找到的進程完成序列為p1,p2,p3。P2申請2個，系統滿足它，p2接著運行；p2完成，釋放資源，使系統資源變?yōu)?個。系統還剩2個。P1運行完成后，釋放資源，使系統的資源數量變?yōu)?個。此時系統的分配情況如下：p1分配5個后正在運行，p2分配2個后等待分配2個，p3等待分配4個，系統還剩3個。2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。它們使用資源的次序和數量如下圖所示。故可以滿足它的請求。2）p1:資源請求Request(1,0,2)時，由1）可知，可以立即滿足它，使得A=(2,2,0),P1的分配向量為(3,1,2)，其剩余向量變?yōu)?0,1,0). (2’)p4:資源請求Request(3,3,0)時，由于系統剩余資源向量A=(2,2,0)，顯然不能滿足它的請求，因為系統剩余資源向量A小于P4的請求 (2’)p0:資源請求Request(0,1,0)時，由于系統剩余資源向量A=(2,2,0)，若滿足它的請求，使得系統剩余資源向量A=(2,1,0)。若找不到,可先求出進程的剩余請求矩陣. 進程 資源最大需求 已分配資源 剩余資源請求 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 系統剩余資源向量A=(3,2,2)，在進程剩余資源請求矩陣中找，是否有一行，選進程P1，滿足它的全部資源請求，它在有限時間內能釋放全部資源，并標記它為完成使系統剩余資源向量A=(5,3,2).之后再重復上述過程，從而找到了一個進城完成序列為：P1,P3,P4,P2,P0 (2’)。若出現以下資源分配情況： 進程 資源最大請求 已分配資源 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系統剩余資源數量為(3,2,2)。如果分配的話，則系統剩余的資源向量為（0，1，2），這時無法找到一個安全序列。 (2’)③可以分配。①T0時刻是否為安全狀態(tài)？若試，請給出安全序列。在T0時刻系統狀態(tài)如表39所試。 餓死：在系統中，由于系統采用的資源分配算法不當，雖然每個資源占有者都在有限時間內釋放它所占的資源，但仍然使一些進程永遠得不到資源的一種錯誤現象。于是就有： F(R0)F(R1)…F(Rn)F(R0) 由傳遞性得到： F(R0)F(R0) 顯然，這是不可能的，因而，上述假設不成立，表明不會出現循環(huán)等待條件。 若存在循環(huán)等待，設在環(huán)路上的一組進程為{P0,P1,P2,…,Pn}，這里Pi等待進程Pi+1占有資源Ri（下角標取模運算，從而，Pn等待p0占有的資源）。即系統中的進程處于安全序列中。 4死鎖預防的基本思想是什么?死鎖避免的基本思想是什么?答:死鎖預防的基本思想是:要求進程申請資源是遵循某種協議,從而打破產生思索的四個必要條件中的一個或幾個,保證系統不會進入死鎖狀態(tài). 死鎖避免的基本思想是:對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查,在資源分配過程中若預測有發(fā)生死鎖的可能性,. 5什么是死鎖的安全序列?何謂系統是安全的？答：進程的安全序列{P1,P2,…,PN}是這樣組成的：若對于每個進程Pi（1=I=n），它需要的附加資源可以被系統中當前可用資源加上所有進程Pj（ji）當前占有資源之和所滿足，則{ P1,P2,…,PN }為一個安全序列。 3什么是死鎖？解決死鎖的方法一般有那幾種?答: 死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。 不可搶占條件——一個進程所占有的資源再用完之前，其他進程不能強行奪走資源，只能由該進程用完之后主動釋放。 互斥條件——某個資源在一段時間內只能由一個進程占有，不能同時被兩個及其以上的進程占有。死鎖發(fā)生的四個基本條件有互斥條件、請求保持條件（占有且等待條件）、非剝奪條件（不可搶占條件）和環(huán)路條件（循環(huán)等待條件） 。5安全序列針對當前分配狀態(tài)來說，系統至少能夠按照某種次序為每個進程分配資源（直至最大需求），并且使他們依次成功地運行完畢，這種進程序列{p1,p2,…,pn}就是安全序列。就是說，在資源分配過程中若預測有發(fā)生死鎖的可能性，則加以避免。3死鎖防止要求進程申請資源時遵循某種協議，從而打破產生死鎖的四個必要條件中的一個或幾個，保證系統不會進入死鎖狀態(tài)。(4’)算法描述如下：(`6’=2’*3) 進程R 進程C 進程P L1: L2: L3:P(S0) P(S1) P(S2)P(mux) P(mux) P(mux)讀一個數據 從緩沖區(qū)中取一個 從緩沖區(qū)中讀 送緩沖區(qū) 數據處理后放回去 輸出數據V(mux) V(mux) V(mux)V(S1) V(S2) V(S0) 打印gotoL1: gotoL2: gotoL3:名詞解釋1死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。解答：解決同步問題需設一個互斥信號量mux，用于控制三個進程互斥使用緩沖區(qū)，初值為1；再設三個同步信號量，用于控制對緩沖區(qū)的空閑數量和不同數據個數的記錄。進程R負責從輸入設備上讀數據，每讀一個后把它存放在緩沖區(qū)buf的一個單元中；進程C負責從緩沖區(qū)讀數據并進行處理，之后將處理結果再送入緩沖區(qū)的一個單元中；進程P負責從緩沖區(qū)讀進程C處理的結果并打印。 y = 12。令信號s1, s2的初值為0，已知z=2，試問p1, p2并發(fā)運行結束后x=? y=? z=? 進程p1 進程p2 y := 1 x := 1 y := y+2 x := x+1 v(s1) p(s1) z := y+1 x := x+y p(s2) v(s2) y := z+y z := x+z 解答：（分析過程略 2’）從結果來看，兩個進程無論誰先誰后，結果都是一樣的。解答：semaphore mutex1=0,mutex2=0?！?1’)　　意義：(`3’=1’*3)　　S0　S的值表示可繼續(xù)進入售票廳的人數　　　S=0　表示售票廳中已有20名顧客(購票者)　　　S0　|S|的值為等待進入售票廳的人數　　(2)上空格為P(S) (2’) ；下空格為V(S)　(2’)　(3)S的最大值為20 (1’ )；S的最小值為20－n　(1’ )9在公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開門關門，當售票員關好車門后，駕駛員才能開車行使?！　OBEGIN　PROCESS　PI(I=1，2，……)　　　　　　　 begin　　　　　　　　進入售票廳； 購票； 　　　　　　　　　　　退出；　　　　　　　 end　　　COEND(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。若把一個購票者看作一個進程，請回答下列問題：　　(1)用PV操作管理這些并發(fā)進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。(2’)變量說明：(`2’)計數變量rc——正在運行的查詢者進程數目，初值為0.信號量Sw——控制訂票者進程的活動，初值為1.Src——互斥使用rc變量，初值為1.S——當訂票者到達時封鎖后續(xù)的讀進程，初值為1.讀者進程 P(S)P(Src)rc=rc+1if (rc==1) P(Sw)V(Src)V(S) (2’)查詢庫當中的信息P(Src)rc=rc1。利用信號量機制保證其正常執(zhí)行。請用P,V操作設計一個同步算法，實現用戶查詢與訂票功能。 (3’)end. 7在一個飛機訂票系統中，多個用戶共享一個數據庫。 If R==0 V(S)。 P(S1)。 //申請過河 V(S1)。 end //同方向過河的人站滿橋墩時,重新申請計數 R=R+1。 //為同時過河,申請對計數器計數 If RN begin V(S1)。用S1信號量保護計數器，其初值為1，R的初值為0；互斥使用橋的信號量用S表示，其初值為1。請給出兩個方向的人順利過河的同步算法。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退?？梢姡粋€程序可對應多個讀者。下面用兩個過程描述對表格應執(zhí)行的動作： 登記過程：(`2’) 擦除過程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登記項擦除 找到一個登記項登記 V(mutex) V(mutex) V(empty) end end 為了正確地描述讀者的動作，可以將讀者看成進程。每當有讀者進入閱覽室時，為了正確地登記，各讀者應互斥使用(1’)。解：為了描述閱覽室，用一個登記表來記錄其使用情況。該表表目設有座位號和讀者姓名；離開時再將其登記項擦除。(4’)住宿登記及注銷過程的算法描述如下： 住宿登記：(`3’) begin p(empty) //檢查有無床位