1、練習題（四）I問答題試說明進程的互斥和同步兩個概念，并說明它們之間的異同。答：進程互斥是解決進程間競爭關系（間接制約關系）的手段。它是 指一組并發(fā)進程中的一個或多個程序段，因共享同一臨界資源時，任 何時刻不允許兩個以上共享該資源的并發(fā)進程同時進入臨界區(qū)。進程同步指的是兩個或多個進程為了合作完成同一個任務，在執(zhí)行速 度或某些確定的時序點上必須相互協(xié)調，即一個進程的執(zhí)行依賴于另 一個進程一其合作伙伴的消息，當一個進程到達了某一確定點而沒有 得到合作伙伴發(fā)來的“已完成某些操作”的消息時必須等待，直到該消 息到達被喚醒后，才能繼續(xù)向前推進。進程同步與互斥相似之處是：進程的互斥實際上是進程同步的一種特

2、殊情況，即逐次使用互斥共享資源，也是對進程使用資源次序上的一 種協(xié)調。進程的互斥和同步統(tǒng)稱為進程同步。進程同步與互斥的差別是：進程互斥是進程間共享資源的使用權，這 種競爭沒有固定的必然聯(lián)系，哪個進程競爭到資源的使用權，該資源 就歸那個進程使用，直到它不再需要使用時才歸還資源；而進程同步 則涉及共享資源的并發(fā)進程間有一種必然的聯(lián)系，當進程必須同步 時，即使無進程在使用共享資源時，那么尚未得到同步消息的進程也 不能去使用該資源。進程之間存在哪幾種相互制約關系？各是什么原因引起的？請說 明下列活動分別屬于哪種制約關系？（1）若干同學去圖書館借書；（2）兩隊舉行籃球比賽；（3）流水線生產(chǎn)的各道工序；（

3、4）商品生產(chǎn)和社會消費。答：進程之間存在直接制約關系（進程間的同步）和間接制約關系（進 程間的互斥）。直接制約關系是指兩個或多個進程為了合作完成同一 個任務，間接制約關系是指兩個或多個進程為了競爭臨界資源。（1）屬于互斥關系（2）屬于互斥關系（3）屬于同步關系（4）屬于同步關系什么是臨界區(qū)和臨界資源？對臨界區(qū)管理的基本原則是什么？答：把一次只允許一個進程使用的資源稱為臨界資源。把每個進程中 訪問臨界資源的那段代碼從概念上分離出來，將其稱為臨界區(qū)。即臨 界區(qū)是指對臨界資源實施操作的程序代碼段。對臨界區(qū)管理的原則是：互斥。如果某個進程在臨界區(qū)內執(zhí)行，則其它進程不能進入臨界區(qū)。有空讓進。如果沒有進程

4、在其臨界區(qū)內執(zhí)行，則選擇一進程（如有） 進入臨界區(qū)。有限等待。當有若干個進程同時要求進入臨界區(qū)時，應在有限時間內 使一個進程進入。什么是信號量？在信號量S上作P、V操作時，S的值發(fā)生變化, 當S0、S=0、S0時，其值表示系統(tǒng)中當前可用的某類資源數(shù)量；當s=o時，表示系統(tǒng)中當前已無某類資源可用；當s0時，其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù) 量或登記排列在該信號量s隊列之中等待的進程個數(shù)。請說明P、V操作的定義和作用？為什么它們均為不可分割的原 語操作？答：定義：設S為一個記錄型數(shù)據(jù)結構，其中一個分量為整型量value ,另一個 分量為信號量隊列queue, value通常是一個具

5、有非負初值的整型變 量，queue是一個初始狀態(tài)為空的進程隊列。信號量S的初值可定義 為0, 1或其它正整數(shù)，在系統(tǒng)初始化時確定。記錄型信號量和P操作和V操作可表示成如下的數(shù)據(jù)結構和不可中 斷的過程：void P(semaphore S)/* P 操作定義 */S. value/*把信號量值減1 */if (S.value 0)add this process to S.queue;block();void V(semaphore S)(/* V 操作定義 */S.value + +; /*把信號量值加1 */if (S.valuebuffer2-bufferlV(emptyl)V(empty

6、2)V(fiilll)P(empty2)-buffer2V(fiill2)考慮一個共有150個存儲單元的系統(tǒng)，如下分配給三個進程,Pl最 大需求70,己占有25； P2最大需求60,己占有40； P3最大需求 60,己占有45o使用銀行家算法，以確定下面的任何一個請求是否 安全。（1）P4進程到達，P4最大需求60,最初請求25個。（2）P4進程到達，P4最大需求60,最初請求35。如果安全，找 出安全序列；如果不安全，給出結果分配情況。答： 由于系統(tǒng)目前還有150-25-40-45=40個存儲單元，P4進程到 達，把25個存儲單元分給它。這時系統(tǒng)還余15個單元，可把15個 單元分給P3,它執(zhí)

7、行完后會釋放60個單元。于是可供P1 （還要45 個單元）、P2（20個單元）和P4（還要35個單元）任何一個執(zhí)行。安全序 列有6個序列，分別為：P3, Pl, P2, P4 ;P3, Pl, P4, P2 ; P3, P2, Pl, P4 ;P3, P2, P4, Pl ;P3, P4, Pl, P2 ; P3, P4, P2, P1 ;（2）P4進程到達，P4最大需求60,最初請求35。如果把35個單元分 給P4,系統(tǒng)還余5個單元，不再能滿足任一個進程的需求，系統(tǒng)進 入不安全狀態(tài)。某一游覽勝地，有一天然隧道，隧道內只允許一人通過。為使雙 方游人都有機會，規(guī)定當同一方向經(jīng)過一人后就交替地改變

8、方向，讓 另一方游人通過，要想進入隧道的人在隧道口排隊等待，試用信號量 與P、V操作編寫游人到達隧道口，通過隧道并從另一端離開隧道口的程序。答：設隧道一邊的信號量為S1和隧道另一邊的信號量為S2,它們的 初值分別為：Sl=l； S2=0；隧道另邊隧道邊P(S1)過隧道V(S2)P(S2) 過隧道V(S1)有Pl、P2、P3三個進程共享一個表格F, P1對F只讀不寫，P2 對F只寫不讀，P3對F先讀后寫。進程可同時讀F,但有進程寫時, 其它進程不能讀和寫。用信號量和P、V操作編寫三進程能正確工作 的程序。答：有Pl、P2、P3三個進程共享一個表格F, P1對F只讀不寫，P2對F 只寫不讀，P3對F先讀后寫。進程可同時讀F,但有進程寫時，其 他進程不能讀和寫。用信號量和P、V操作。s