自學(xué)考試操作系統(tǒng)概論串講筆記-資料下載頁(yè)

　　

【正文】 關(guān)臨界區(qū)、及其管理的原則 5.（補(bǔ)充）信號(hào)量的定義及其物理意義 重點(diǎn)： 本章考試分值約為30分，是本書(shū)的重點(diǎn)內(nèi)容。出題形式多以單選題、多選題、填空題、簡(jiǎn)答題、綜合應(yīng)用題為主。? 知識(shí)網(wǎng)絡(luò)圖? 串講內(nèi)容一、 進(jìn)程的并發(fā)性1. 進(jìn)程的順序性進(jìn)程的順序性是指進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，即按照程序規(guī)定的操作順序，只有在前一個(gè)操作結(jié)束后才能開(kāi)始后繼操作。當(dāng)一個(gè)進(jìn)程獨(dú)占處理器順序執(zhí)行時(shí)，具有兩個(gè)特性：封閉性和可再現(xiàn)性。2. 進(jìn)程的并發(fā)性在多道程序設(shè)計(jì)的系統(tǒng)中，若干個(gè)作業(yè)可以同時(shí)執(zhí)行，而每一個(gè)作業(yè)又需要有多個(gè)進(jìn)程協(xié)作完成。因此，系統(tǒng)中會(huì)同時(shí)存在著許多進(jìn)程，在單處理器的情況下，這些進(jìn)程流地占用處理器，即一個(gè)進(jìn)程的工作沒(méi)有全部完成之前，另一個(gè)進(jìn)程就可開(kāi)始工作，我們說(shuō)這些可同時(shí)執(zhí)行的進(jìn)程具有并發(fā)性，并且把可同時(shí)執(zhí)行的進(jìn)程稱(chēng)為“并發(fā)進(jìn)程”。并發(fā)進(jìn)程相互間可能無(wú)關(guān)，也可能相互間有交往。進(jìn)程并發(fā)執(zhí)行時(shí)，執(zhí)行結(jié)果與其執(zhí)行的相對(duì)速度有關(guān)，進(jìn)程的并發(fā)執(zhí)行會(huì)破壞“封閉性”和“可再現(xiàn)性”。二、與時(shí)間有關(guān)的錯(cuò)誤造成與時(shí)間有關(guān)的錯(cuò)誤的原因是什么？（概念）答：一個(gè)進(jìn)程運(yùn)行時(shí)，經(jīng)常會(huì)由于自身或外界的原因而被中斷，切斷點(diǎn)是不固定的。一個(gè)進(jìn)程被中斷后，哪個(gè)進(jìn)程可以運(yùn)行，被中斷的進(jìn)程什么時(shí)候再去占用處理器，這是與進(jìn)程調(diào)度策略。所以，進(jìn)程執(zhí)行的相對(duì)速度不能由進(jìn)程自己來(lái)控制，于是，就可能導(dǎo)致兵法進(jìn)程在共享資源時(shí)出現(xiàn)錯(cuò)誤。進(jìn)程的執(zhí)行次序?qū)Y(jié)果是有影響的，關(guān)鍵是它們涉及到共享變量，若交叉訪問(wèn)了共享變量，導(dǎo)致共享變量的值不同，造成計(jì)數(shù)值不正確的因素是與進(jìn)程被打斷的時(shí)間和能占用處理器的時(shí)間有關(guān)。三、臨界區(qū)與PV操作（重點(diǎn)）我們把并發(fā)進(jìn)程中與共享變量有關(guān)的程序段稱(chēng)為臨界區(qū)。相關(guān)臨界區(qū)是指并發(fā)進(jìn)程中涉及到相同變量的那些臨界區(qū)。：（1）一次最多一個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)；（2）任何一個(gè)進(jìn)入臨界區(qū)的進(jìn)程必須在有限的時(shí)間內(nèi)退出臨界區(qū)；（3）有進(jìn)程退出臨界區(qū)時(shí)應(yīng)讓一個(gè)等待進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入它的臨界區(qū)執(zhí)行。3.（重點(diǎn)）PV操作PV操作是定義在信號(hào)量S的兩個(gè)操作——P操作和V操作組成。這兩個(gè)操作是兩個(gè)不可中斷的過(guò)程，它們?cè)谄帘沃袛嗟那闆r下繼續(xù)執(zhí)行。把不可中斷的過(guò)程稱(chēng)作原語(yǔ)。因此，P操作和V操作也可稱(chēng)為P操作原語(yǔ)V操作原語(yǔ)，簡(jiǎn)稱(chēng)PV操作。P操作：（1）S：=S1（2）若S≥0，則調(diào)用P操作的進(jìn)程繼續(xù)運(yùn)行 若S＜0，則調(diào)用P操作的進(jìn)程被置成等待態(tài)V操作：（1）S：=S+1（2）若S＞0，則調(diào)用V操作的過(guò)程繼續(xù)運(yùn)行 若S≤0，則調(diào)用V操作的進(jìn)程繼續(xù)運(yùn)行，并且從等待態(tài)中調(diào)用一個(gè)進(jìn)程置成就緒態(tài)。（Semaphore）的定義是表示資源的實(shí)體，是一個(gè)與隊(duì)列有關(guān)的整形變量，其值僅能用P、V操作改變。：（1）當(dāng)S＞0時(shí)，S表示可以使用的資源數(shù)，或者表示可使用資源的進(jìn)程數(shù)；（2）當(dāng)S=0時(shí)，S表示無(wú)資源可用，或者表示不允許進(jìn)程再進(jìn)入它的臨界區(qū)；（3）當(dāng)S＜0時(shí)，︱S︱表示等待使用資源的進(jìn)程數(shù)或者表示等待進(jìn)入臨界區(qū)的進(jìn)程數(shù)。更多優(yōu)質(zhì)自考資料盡在百度貼吧自考樂(lè)園俱樂(lè)部（）歡迎?加入...歡迎?交流...止不住的驚喜等著你.........四、進(jìn)程的互斥與同步（重點(diǎn)）進(jìn)程的互斥是指當(dāng)有若干個(gè)進(jìn)程都要使用某一共享資源時(shí)，任何時(shí)刻最多只允許一個(gè)進(jìn)程去使用該資源，其他要使用它的進(jìn)程必須等待，直到該資源的占用者釋放了該資源。進(jìn)程Pi（i=1，2，…，n）互斥的一般形式為： begin S:semaphore； S:=1； …cobegin … Process Pi begin …P(S)；臨界區(qū)；V(S)；…end；…coend；end；（注意）（1）P、V操作一定僅挨臨界區(qū) （2）P、V操作一定要成對(duì)使用。有P操作，必定有V操作與之對(duì)應(yīng)。當(dāng)程序有多個(gè)分支時(shí)，必須考慮它們的成對(duì)性。【例1】：若有一條小河,河上有一座橋,現(xiàn)在河?xùn)|、河西都有人過(guò)橋，若把每個(gè)過(guò)橋者看作一個(gè)進(jìn)程，為保證安全，請(qǐng)用P、V操作進(jìn)行管理。begin S:semaphore； S:=1；cobegin process P(E→W)i(i=1,2,…) begin P(S)； 過(guò)橋 V(S)； end； process P(W→E)j(j=1,2,…) begin P(S)； 過(guò)橋 V(S)； end；coend；end；【例2】：若有3個(gè)進(jìn)程共享同一臨界區(qū)，最多允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，則信號(hào)量的初值為1，信號(hào)量可能的變化范圍為1，0，1，2?！纠?】：多個(gè)讀者與多個(gè)寫(xiě)者的問(wèn)題分析：S：=1作用:用于讀寫(xiě)互斥,寫(xiě)寫(xiě)互斥 Sr:=1 作用:用于變量rc的互斥修改 rc:=0 作用:用于記錄讀者個(gè)數(shù)begin S,Sr:semaphore； rc:integer； S:= Sr:=1； rc:=0cobegin process readeri(i=1,2,…) begin P(Sr)； rc:=rc+1 if rc=1 then P(S) V(Sr)； read file F P(Sr)； rc:=rc1 if rc=0 then V(S) V(Sr)； end； process writerj(j=1,2,…) begin P(S)； writer file F V(S)； end；coend；end；進(jìn)程的同步是指在并發(fā)進(jìn)程之間存在一種制約關(guān)系，一個(gè)進(jìn)程的執(zhí)行依賴(lài)另一個(gè)進(jìn)程的消息，當(dāng)一個(gè)進(jìn)程沒(méi)有得到另一個(gè)進(jìn)程的消息時(shí)應(yīng)等待，直到消息到達(dá)才被喚醒。3. 同步機(jī)制（1） 如何利用信號(hào)量PV操作實(shí)現(xiàn)進(jìn)程的同步？答：PV操作不僅是實(shí)現(xiàn)進(jìn)程互斥的有效工具，而且還是一個(gè)簡(jiǎn)單又方便的同步工具。用一個(gè)信號(hào)量與一個(gè)消息聯(lián)系起來(lái)，當(dāng)信號(hào)量的值為0時(shí)，表示所期望的尚未產(chǎn)生，當(dāng)信號(hào)量的值為大于0時(shí)，表示所期望的消息已經(jīng)存在。（2）實(shí)現(xiàn)進(jìn)程時(shí)應(yīng)注意在用PV操作實(shí)現(xiàn)同步時(shí)，一定要根據(jù)具體的問(wèn)題來(lái)定義信號(hào)量和調(diào)用P操作或V操作。一個(gè)信號(hào)量與一個(gè)消息聯(lián)系在一起。當(dāng)有多個(gè)消息時(shí)必須定義多個(gè)信號(hào)量。測(cè)試不同的消息是否到達(dá)或發(fā)送不同消息時(shí)，應(yīng)對(duì)不同的信號(hào)量調(diào)用P操作或V操作?！纠?】：一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者共享一個(gè)緩沖器SP：表示是否可以把物品存入緩沖區(qū)，SP：=1SG：表示緩沖器中是否存有物品SG：=1begin Buffer：integer； SP，SG:semaphore； SP:= 1；SG:=0；cobegin process producer begin L1：producer a product；/生產(chǎn)一件物品/ P(SP)； Buffer：=product；/將生產(chǎn)的物品存入緩沖器/ V(SG)； go to L1。 end； process consumer begin L2:P(SG)； take a product；/從緩沖器中取出一件物品/ V(SP)； consume；/消費(fèi)取出的物品/ go to L2。 end；coend；end；【例2】：若有三個(gè)進(jìn)程R，M，P，它們共享一個(gè)緩沖區(qū)，R負(fù)責(zé)從輸入設(shè)備上讀信息到緩沖區(qū)，M對(duì)緩沖區(qū)中的記錄進(jìn)行加，P把加工后的記錄打印輸出，讀入的記錄經(jīng)加工打印輸出后，緩沖區(qū)才可放下一條記錄，試用P、V操作編寫(xiě)正確的程序去管理（緩沖區(qū)中只能存放一條記錄）S1：是否可以把記錄讀入緩沖區(qū)，S1：=1S2：是否可以加工記錄，S2：=1S3：是否可以把加工后的記錄打印輸出，S3：=1begin S1，S2 ，S3，:semaphore； S1:= 1；S2:= S3:=0；cobegin process R begin L1：從輸入設(shè)備上讀記錄 P(S1)； 把記錄存入緩沖區(qū) V(S2)； go to L1。 end； process M begin L2:P(S2)； 加工緩沖區(qū)記錄 V(S3)； go to L2。 end；process P begin L3:P(S3)； 打印加工后的記錄 V(S1)； go to L3。 end；coend；end；【例1】：討論m個(gè)生產(chǎn)者和r個(gè)消費(fèi)者怎樣共享容量為n的緩沖器。SP：是否可以向緩沖器中放產(chǎn)品，SP：=nSG：是否可以從緩沖器中取產(chǎn)品，SG：=0S1：表示m個(gè)生產(chǎn)者互斥的向緩沖器中放產(chǎn)品，S1：=1S2：表示r個(gè)消費(fèi)者互斥的向緩沖器中取產(chǎn)品，S2：=1k：指示生產(chǎn)者存放產(chǎn)品的位置，k：=1t：指示消費(fèi)者取產(chǎn)品的位置，t：=1begin B：array[0..（n1）]of integer： k，t:integer；S1，S2，SP，SG:semaphore； k:=0；t:=0；S1:=1；S2:=1；SP:=n；SG:=0；cobegin process producer i(i=1,2,…，m) begin L1：produce a product； P(SP)； P(S1)； B[k]:=product； k:=(k+1) mod n； V(S1)； V(SG)； go to L1 end； process consumer j(j=1,2,…，r) begin L2: P(SG)； P(S2)； take a product from B [t]； t:=(t+1) mod n； V(S2)； V(SP)； go to L2 end；coend；end；五、進(jìn)程通信通過(guò)專(zhuān)門(mén)的通信機(jī)制實(shí)現(xiàn)進(jìn)程間交換大量信息的通信方式稱(chēng)為進(jìn)程通信。：發(fā)送者名、信息（或信息存放的地址和長(zhǎng)度）、等/不等回信、回信存放地址。信箱說(shuō)明可存信件數(shù)已有信件數(shù)可存信件的指針取信件信件1信件2…用信箱實(shí)現(xiàn)進(jìn)程間互通信息的通信機(jī)制要有兩個(gè)通信原語(yǔ)，它們是發(fā)送（send）原語(yǔ)和接收（receive）原語(yǔ)。（1） send（N，M）功能：把信件M送到指定的信箱N(xiāo)中。實(shí)現(xiàn)要求：查指定信箱N(xiāo)。若信箱未滿(mǎn)，則按“可存信件的指針”把信件M存入信箱且釋放“等信件”者；若信箱已滿(mǎn)，則把發(fā)送信件進(jìn)程置為“等信箱”狀態(tài)。（2） receive（N，Z）功能：從指定信箱N(xiāo)取出一封信，存到指定的地址Z中。實(shí)現(xiàn)要求：查指定信箱N(xiāo)。若信箱中有信，則取出一封信存于Z中，且釋放“等信箱”者；若信箱中無(wú)信，則把接收信件進(jìn)程置為“等信件”狀態(tài)。六、死鎖（重點(diǎn)）若系統(tǒng)中存在一組進(jìn)程（兩個(gè)或多個(gè)進(jìn)程），它們中的每一個(gè)進(jìn)程都占用了某種資源而又都在等待該組進(jìn)程中另一個(gè)進(jìn)程所占用的資源，這種等待永遠(yuǎn)不能結(jié)束，則說(shuō)系統(tǒng)出現(xiàn)了死鎖，或說(shuō)這組進(jìn)程處于死鎖狀態(tài)。形成死鎖的起因是系統(tǒng)提供的資源數(shù)比進(jìn)程要求的資源數(shù)少，或者是若干個(gè)進(jìn)程要求的資源總數(shù)大于系統(tǒng)能提供的資源數(shù)。這時(shí)，進(jìn)程間就會(huì)出現(xiàn)競(jìng)爭(zhēng)資源的現(xiàn)象，對(duì)進(jìn)程競(jìng)爭(zhēng)的資源如果管理或分配不當(dāng)，就會(huì)引起死鎖。死鎖的出現(xiàn)與資源分配策略和并發(fā)執(zhí)行的速度有關(guān)。當(dāng)所有進(jìn)程都處于等待狀態(tài)，一定會(huì)發(fā)生死鎖。若系統(tǒng)有某類(lèi)資源m個(gè)，被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程都要求k個(gè)資源（k≤m），當(dāng)m＜nk時(shí)，即資源數(shù)小于進(jìn)程所要求資源的總數(shù)時(shí)，如果分配不當(dāng)，就可能引起死鎖。2.（ 重點(diǎn)）同類(lèi)資源數(shù)m，每個(gè)進(jìn)程最多申請(qǐng)的資源數(shù)為x，系統(tǒng)中進(jìn)程數(shù)為n。當(dāng)n（x1）+1≤m 成立，一定不死鎖?！纠浚喝裟诚到y(tǒng)中有5個(gè)同類(lèi)資源，被3個(gè)進(jìn)程共享，每個(gè)進(jìn)程最多申請(qǐng)幾個(gè)資源時(shí)，系統(tǒng)一定不會(huì)發(fā)生死鎖？解：資源的按輪分配法： P1 P2 P3第一輪：1 1 1第二輪：1 1 等待所以，最多申請(qǐng)2個(gè)資源。（1）互斥地使用資源（2）占有且等待資源（3）非搶奪式分配（4）循環(huán)等待資源？ 答：（1）硬件故障，軟件設(shè)計(jì)的錯(cuò)誤引起的死鎖； （2）申請(qǐng)不存在的資源或申請(qǐng)資源數(shù)超過(guò)系統(tǒng)擁有的資源數(shù)引起死鎖。死鎖的防止是指當(dāng)采用某種資源分配策略后，使系統(tǒng)一定不會(huì)出現(xiàn)死鎖。：（1）靜態(tài)分配資源。靜態(tài)分配資源是指進(jìn)程必須在開(kāi)始執(zhí)行前就申請(qǐng)它所要的全部資源，僅當(dāng)系統(tǒng)能滿(mǎn)足進(jìn)程的資源申請(qǐng)要求且把資源分配給進(jìn)程后，該進(jìn)程才開(kāi)始執(zhí)行，實(shí)現(xiàn)起來(lái)簡(jiǎn)單，但卻降低了資源的利用率。這種分配策略破壞了四個(gè)必要條件中的占有且等待資源和循環(huán)等待資源兩個(gè)條件不成立，從而防止了死鎖的發(fā)生。（2）按序分配資源。按序分配資源是指對(duì)系統(tǒng)中每一個(gè)資源給出一個(gè)編號(hào)。規(guī)定任何一個(gè)進(jìn)程申請(qǐng)兩個(gè)以上資源時(shí)，總是先申請(qǐng)編號(hào)小的資源，再申請(qǐng)編號(hào)大的資源。這種分配策略破壞了四個(gè)必要條件中的循環(huán)等待資源的條件。（3）剝奪式分配資源。剝奪式分