操作系統(tǒng)-進程管理習(xí)題.pptVIP

進程管理習(xí)題課,重點：用P、V原語實現(xiàn)同步與互斥,本章小結(jié),進程是系統(tǒng)分配資源的基本單位,是一個具有獨立功能的程序段對某個數(shù)據(jù)集的一次執(zhí)行活動。 為什么要引入進程的概念是由操作系統(tǒng)的資源有限性和處理上的并行性以及系統(tǒng)用戶的執(zhí)行起始時間的隨機性所決定的。 進程具有動態(tài)性、并發(fā)性等特點。 進程動態(tài)特性的是進程狀態(tài)的變化。進程要經(jīng)歷創(chuàng)建、等待資源、就緒準(zhǔn)備執(zhí)行,以及執(zhí)行和執(zhí)行后釋放資源消亡等幾個過程和狀態(tài)。進程的狀態(tài)轉(zhuǎn)換要由不同的原語執(zhí)行完成。,本章小結(jié),P78,進程的并發(fā)特性反映在進程對資源的競爭以及由資源競爭所引起的對進程執(zhí)行速度的制約。這種制約可分為直接制約和間接制約。 直接制約是被制約進程和制約進程之間,存在著使用對方資源的需求,只有制約進程執(zhí)行后,被制約進程才能繼續(xù)往前推進。具有固定的執(zhí)行順序 間接制約是被制約進程共享某個一次只能供一個進程使用的系統(tǒng)資源,只有得到該資源的進程才能繼續(xù)往前推進,其他進程在獲得資源進程執(zhí)行期間不允許交叉執(zhí)行。沒有固定的執(zhí)行順序。 操作實現(xiàn)：間接制約可利用加鎖法和P,V原語操作實現(xiàn)。直接制約既可用P,V原語實現(xiàn),也可用其他互相傳遞信號的方式實現(xiàn)。,進程上下文：一個進程的靜態(tài)描述是處理機的一個執(zhí)行環(huán)境,被稱為進程上下文。進程上下文由以下部分組成：PCB(進程控制塊)、正文段和數(shù)據(jù)段以及各種寄存器和堆棧中的值。寄存器中主要存放將要執(zhí)行指令的邏輯地址,執(zhí)行模式以及執(zhí)行指令時所要用到的各種調(diào)用和返回參數(shù)等。而堆棧中則存放CPU現(xiàn)場保護信息、各種資源控制管理信息等。 進程通信：進程間通信又可分為傳送控制信號的低級通信和大量傳送數(shù)據(jù)的高級通信。 通信方式來看,又可分為主從式、會話式、消息與郵箱方式、以及共享虛存方式。,本章小結(jié)(續(xù)),P79,常用的死鎖排除方法是檢測與恢復(fù)方法。 造成死鎖：無論是互相通信的進程或是共享某些不同類型資源的進程,都可能因通信順序不當(dāng)或資源分配順序不當(dāng)而造成死鎖。 死鎖是一種因各并發(fā)進程等待資源而永久不能向前推進的系統(tǒng)狀態(tài)。 排除死鎖的方法是預(yù)防、回避、檢測與恢復(fù)三種。 線程是進程內(nèi)的一段程序的基本調(diào)度單位。線程可分為用戶級線程和系統(tǒng)級線程。用戶級線程的管理全部由線程庫完成,與操作系統(tǒng)內(nèi)核無關(guān)。 線程組成由寄存器、堆棧以及程序計數(shù)器等組成,同一進程的線程共享該進程的進程空間和其他所有資源。線程主要用于多機系統(tǒng)以及網(wǎng)絡(luò)系統(tǒng)的操作系統(tǒng)中。,本章小結(jié)(續(xù)),P79,第一題,一、用P、V操作描述前趨關(guān)系。P1、P2、P3、P4、P5、P6為一組合作進程，其前趨圖如圖所示，試用P、V操作描述這6個進程的同步。,第二題,二、生產(chǎn)者-消費者問題 它描述了一組生產(chǎn)者向一組消費者提供產(chǎn)品，它們共享一個有界緩沖區(qū)，生產(chǎn)者向其中投放產(chǎn)品，消費者從中取得產(chǎn)品。生產(chǎn)者-消費者問題是許多相互合作進程的一種抽象。 我們把一個長度為n的有界緩沖區(qū)(n0)與一群生產(chǎn)者進程P、P、Pm和一群消費者進程C、C、Ck聯(lián)系起來，如圖所示。提取物品。,第二題（續(xù)）,假定這些生產(chǎn)者和消費者是互相等效的。只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩沖區(qū)未空，消費者便可以從緩沖區(qū)中取走物品并消耗它。生產(chǎn)者和消費者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也禁止消費者從空的緩沖區(qū)中,第三題（選擇）,三、在操作系統(tǒng)中，進程是一個具有一定獨立功能的程序在某個數(shù)據(jù)集上的一次 。 A等待活動 B運行活動 C單獨操作 D關(guān)聯(lián)操作 答：B,第四題（選擇）,四、多道程序環(huán)境下，操作系統(tǒng)分配資源以為基本單位。 A程序 B指令 C進程 D作業(yè) 答：C,第五題（選擇）,五、對于兩個并發(fā)進程，設(shè)互斥信號量為mutex，若mutex=O，則。 A.表示沒有進程進入臨界區(qū) B.表示有一個進程進入臨界區(qū) C.表示有一個進程進入臨界區(qū)，另一個進程等待進入 D.表示有兩個進程進入臨界區(qū) 答：B,第六題（選擇）,六、兩個進程合作完成一個任務(wù)。在并發(fā)執(zhí)行中，一個進程要等待其合作伙伴發(fā)來消息，或者建立某個條件后再向前執(zhí)行，這種制約性合作關(guān)系被稱為進程的。 A.同步 B互斥 C. 調(diào)度 D執(zhí)行 答：A,第七題（選擇）,七、為了進行進程協(xié)調(diào)，進程之間應(yīng)當(dāng)具有一定的聯(lián)系，這種聯(lián)系通常采用進程間交換數(shù)據(jù)的方式進行，這種方式稱為。 A.進程互斥 B進程同步 C .進程制約 D進程通信 答：D,第八題,八、在測量控制系統(tǒng)中，數(shù)據(jù)采集任務(wù)把所采集的數(shù)據(jù)送入一單緩沖區(qū);計算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進行計算。試寫出利用信號量機制實現(xiàn)兩者共享單緩沖區(qū)的同步算法。,分析,分析及相關(guān)知識 在本題中采集任務(wù)與計算任務(wù)共用一個單緩沖區(qū)當(dāng)采集 任務(wù)采集到一個數(shù)據(jù)后，只有當(dāng)緩沖區(qū)為空時才能將數(shù)據(jù)送入緩沖區(qū)中存放，否則應(yīng)等待緩沖區(qū)騰空;當(dāng)緩沖區(qū)中有數(shù)據(jù)時，計算任務(wù)才能從緩沖區(qū)中取出數(shù)據(jù)進行計算，否則也應(yīng)等待。,答案,int Se=l; int Sf=0; main() cobegin get(); compute(); coend get() while (采集工作未完成) 采集一個數(shù)據(jù)： p(Se); 將數(shù)據(jù)送入緩沖區(qū)中; v(Sf); ,compute() while(計算工作未完成) p(Sf); 從緩沖區(qū)中取出數(shù)據(jù); v(Se); 進行數(shù)據(jù)計算; ,第九題,九、下圖給出了四個進程合作完成某一任務(wù)的前趨圖，試說明這四個進程間的同步關(guān)系，并用P、V操作描述它。,第十題,十、桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次只能放一只水果供吃者取用，請用P、V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。P37,分析,分析及相關(guān)知識 在本題中，爸爸、兒子、女兒共用一個盤子，且盤中一次只能放一個水果當(dāng)盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待;若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。 本題實際上是生產(chǎn)者消費者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產(chǎn)品。,答案,int S=1; int Sa=0； int So=0； main( ) cobegin father(); son(); daughter()： coend father() while (1) p(S); 將水果放入盤中; if(放入的是桔子) v(So)： else v(Sa); ,son( ) while(1) p(So); 從盤中取出桔子; v(S); 吃桔子; daughter() while(1) p(Sa); 從盤中取出蘋果; v(S); 吃蘋果; ,十一題,十一、(華中理工大學(xué)1999年試題)設(shè)公共汽車上，司機和售票員的活動分別是：p41 司機的活動： 啟動車輛： 正常行車; 到站停車; 售票員的活動： 關(guān)車門; 售票： 開車門; 在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系?用信號量和P、 V操作實現(xiàn)它們的同步。,分析,在汽車行駛過程中，司機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后， 向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開車門讓乘客上下車。因此司機啟動車輛的動作必須與售票員關(guān)車門的動作取得同步;售票員開車門的動作也必須與司機停車取得同步。,答案,int s1=0; int s2=0; driver() while(1) p(s1); 啟動車輛; 正常行車; 到站停車; v(s2); ,busman() while(1) 關(guān)車門; v(s1); 售票; p(s2); 開車門; 上下乘客; ,十二題,十二、設(shè)有一個發(fā)送者進程和一個接收者進程，其流程圖如圖所示。s是用于實現(xiàn)進程同步的信號量，mutex是用于實現(xiàn)進程互斥的信號量。試問流程圖中的A、B、C、D四框中應(yīng)填寫什么?假定緩沖區(qū)有無限多個，s和mutex的初值應(yīng)為多少? p42,分析,分析及相關(guān)知識發(fā)送者進程與接收者進程之間的同步關(guān)系是：發(fā)送者進程生成的信息送入消息鏈中，接收者進程從消息鏈中接收信息;由于發(fā)送者進程產(chǎn)生一個消息并鏈入消息鏈后用V操作增加消息計數(shù)并喚醒接收者進程，這表示發(fā)送者進程和接收者進程是通過信號量s實現(xiàn)同步的，因此接收者進程應(yīng)該在取信息之前先使用一個P操作來查看消息鏈上是否有消息，若無消息則阻塞自己;另外，發(fā)送者和接收者對消息鏈的訪問應(yīng)使用信號量進行互斥，即在訪問前使用P操作，在訪問后使用V操作。,答案,A框 P(mutex) B框 V(mutex) C框 P(s) D框 P(mutex) 開始時，消息鏈上沒有可供接收的信息，所以s的初值為0;互斥信號量mutex的初值應(yīng)為1。,十三題,十三、(北京大學(xué)1990年試題)p46 寫出P、V操作的定義。 有三個進程PA、PB和PC合作解決文件打印問題： PA將文件記錄從磁盤讀入主存 的緩沖區(qū)1，每執(zhí)行一次讀一個記錄; PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個記錄； PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個記錄。緩沖區(qū)的大小等于一個記錄大小。請用P、V操作來保證文件的正確打印。,分析,分析及相關(guān)知識 信號量是一個確定的二元組(s，q)，其中s是一個具有非負初值的整型變量，q是一個與s相關(guān)聯(lián)的初始狀態(tài)為空的隊列整型變量s表示系統(tǒng)中某類資源的數(shù)目，當(dāng)其值大于0時，表示系統(tǒng)中當(dāng)前可用資源的數(shù)目; 當(dāng)其值小于0時，其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù)目除信號量的初值外，信號量的值僅能由P操作和V操作改變。,答案,P操作記為P(S)，其中S為一信號量，它執(zhí)行時主要完成下述動作： S=S-1 若S0，則進程繼續(xù)運行。 若S0，則進程繼續(xù)執(zhí)行。 若S0，則從信號量等待隊列中移出隊首進程，使其變?yōu)榫途w狀態(tài)。,十四題,十四、設(shè)有8個程序progl、prog2、prog8。它們在并發(fā)系統(tǒng)中執(zhí)行時有如圖所示的制約關(guān)系，試用P、V操作實現(xiàn)這些程序間的同步。P48,分析,由圖表明開始時，progl及prog2先執(zhí)行。 當(dāng)progl和prog2都執(zhí)行完后，prog3、prog4、prog5才可以開始執(zhí)行。 prog3完成后，prog6才能開始執(zhí)行。 prog5完成后，prog7 才能開始執(zhí)行。 prog6、prog4、prog7都結(jié)束后，prog8才可以開始執(zhí)行。 為了確保這一執(zhí)行順序，設(shè)7個同步信號量f1、f7分別表示程序progl、prog7是否執(zhí)行完，其初值均為0。,十五題,十五、(北京大學(xué)1991年試題)有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求： (1)每次只能存入一種產(chǎn)品(A或B); (2)-N(A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量)M。 其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。,分析,分析及相關(guān)知識 本題給出的第一個條件是臨界資源的訪問控制，可用一個互斥信號量解決該問題。第二個條件可以分解為： -NA產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量 A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量M 也就是說，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個以上,分析,在本題中，我們可以設(shè)置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和B產(chǎn)品不入庫的情況下，還可以允 許sa個A產(chǎn)品入庫;sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和 A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。 初始時，sa為M一1，sb為N一1，當(dāng)往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1;當(dāng)往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。,十六題,十六、(南開大學(xué)1997年試題)在南開大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行車通過，但其中有一個小的安全島M(同時允許兩輛自行車停留)，可供兩輛自行車已從兩端進入小路情況下錯車使用，如圖所示。試設(shè)計一個算法使來往的自行車均可順利通過。,分析,由于小路中間的安全島M僅允許兩輛自行車停留，本應(yīng)該作為臨界資源而設(shè)置信號量， 但仔細分析可以發(fā)現(xiàn)：在任何時刻進入小路的自行車最多不會超過兩輛(南開和天大方向各一輛)，因此，無需為安全島M設(shè)置信號量。在路口S處，南開出發(fā)的若干自行車應(yīng)進行進入小路權(quán)的爭奪，以決定誰能夠進入小路SK段，為此，設(shè)置信號量S(初值為1)來控制南 開路口資源的爭奪。同理，設(shè)置信號量T(初值為1)來控制天大路口資源的爭奪。此外，小路SK段僅允許一輛自行車通過，所以設(shè)置信號量SK(初值為1)來進行控制，而對于LT 段則設(shè)置信號量LT(初值為1)進行控制。,答案,totian( ) /*從南開大學(xué)去天津大學(xué)* P(S)；/*與其他南開方向的爭奪路口S使用權(quán)* P(SK)； /*同對面來的爭奪SK路段的使用權(quán)* 通過SK路段； 進入安全島M； V(SK)； /*一旦進入安全島M便可釋放SK* P(LT)； /*同對面來的爭奪LT路段* 通過LT路段： V(LT)； *已通過LT路段釋放路段LT* V(S) /*已經(jīng)通過小路，允許在路口S等待的自行車爭奪再次進入S的 使用權(quán)* ,十七題,十七、(中國科學(xué)院軟件研究所1995年試題)多個進程共享一個文件，其中只讀文件的稱為讀者，只寫文件的稱為寫者。讀者可以同時讀，但寫者只能獨立寫。請