操作系統(tǒng)-進(jìn)程管理習(xí)題.ppt

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