計(jì)算機(jī)操作系統(tǒng)_3_進(jìn)程管理_3.ppt

1、計(jì)算機(jī)操作系統(tǒng),計(jì)算機(jī)科學(xué)與技術(shù)系 趙緒營(yíng),主 要 內(nèi) 容,引論 操作系統(tǒng)用戶界面 進(jìn)程管理 處理機(jī)調(diào)度 存儲(chǔ)管理 文件系統(tǒng) 設(shè)備管理,第3章 進(jìn)程管理,3.1 進(jìn)程的概念 3.2 進(jìn)程的描述 3.3 進(jìn)程狀態(tài)及其轉(zhuǎn)換 3.4 進(jìn)程控制 3.5 進(jìn)程互斥 3.6 進(jìn)程同步 3.7 進(jìn)程通信 3.8 死鎖問題 3.9 線程的概念 3.10 線程分類與執(zhí)行,3.5 進(jìn) 程 互 斥 3.5.1 資源共享所引起的制約 進(jìn)程的并發(fā)執(zhí)行：用戶隨機(jī)性和提高資源利用率的結(jié)果，資源的競(jìng)爭(zhēng)與共享制約所導(dǎo)致。 1. 臨界區(qū) 賦值語(yǔ)句：X=X+1；,匯編語(yǔ)言： LOAD A，X（A：累加器） ADDI A，1 STO

2、RE A，X 為了保證程序執(zhí)行最終結(jié)果的正確性，必須對(duì)并發(fā)執(zhí)行的各進(jìn)程進(jìn)行制約，以控制它們的執(zhí)行速度和對(duì)資源的競(jìng)爭(zhēng)。 進(jìn)程中兩相鄰語(yǔ)句可并發(fā)執(zhí)行的三個(gè)條件？,設(shè)有兩個(gè)計(jì)算進(jìn)程A，B共享內(nèi)存S。 S分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)。 數(shù)據(jù)區(qū)被劃分大小相等的塊， 系統(tǒng)區(qū)主要是堆棧，其中存放那些空數(shù)據(jù)塊的地址。,圖3.10 多進(jìn)程共享內(nèi)存棧區(qū)示例,取出空數(shù)據(jù)塊從堆棧最頂部 釋放數(shù)據(jù)塊的地址放入堆棧頂部 過程getspace ：取空數(shù)據(jù)塊過程 過程release(ad)：釋放一個(gè)地址為ad的數(shù)據(jù)塊,getspace: begin local g gstack top toptop-1 end

3、 release(ad):begin top top+1 stack top ad end,設(shè)時(shí)刻t0時(shí)，top=h0，可能按以下順序執(zhí)行： 首先 release(ad)的第一句執(zhí)行， t0：top top+1 top=h0+1； 接著getspace 執(zhí)行，得： t1：g stack top g=stack h0+1； t2：top top-1 top=h0；,再是 release(ad)的第二句執(zhí)行，得： t3：stack top ad stack h0 ad； 結(jié)果：調(diào)用getspace的進(jìn)程取到的是h0+1中的一個(gè)未定義值，而調(diào)用release(ad)的進(jìn)程把所釋放的空塊地址ad重復(fù)放

4、入了h0中。 正確性保證：把getspace和release(ad)抽象為兩個(gè)各以一個(gè)動(dòng)作完成的順序執(zhí)行單位,臨界區(qū)：不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界部分（critical section ）或臨界區(qū)（critical region）。 臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。 臨界區(qū)不可能用增加硬件的方法來解決。 臨界區(qū)也可以被稱為訪問公用數(shù)據(jù)的那段程序。,2. 間接制約 把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。以公用數(shù)據(jù)棧劃分的臨界區(qū)集合 getspace,release。 把這些集合稱為類（class）。 對(duì)類給定一個(gè)唯一的

5、標(biāo)識(shí)名，系統(tǒng)就會(huì)容易地區(qū)分它們。,2. 間接制約 用下列標(biāo)準(zhǔn)形式來描述臨界區(qū)： when類名do臨界區(qū)od 設(shè)類 getspace，release 的類名為sp，則getspace和release(ad)可重新描述為： getspace: when sp do getspcestack top toptop-1 od release(ad): when sp do top top+1 stack top ad od,由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡(jiǎn)稱間接制約。 “間接”二字主要是指各并發(fā)進(jìn)程的速度受公

6、有資源制約，而不是進(jìn)程間直接制約的意思。,在一組并發(fā)執(zhí)行進(jìn)程中，除了因?yàn)楦?jìng)爭(zhēng)公有資源而引起的間接制約帶來進(jìn)程之間互斥之外，還存在有因?yàn)椴l(fā)進(jìn)程互相共享對(duì)方的私有資源所引起的直接制約。 直接制約將使得各并發(fā)進(jìn)程同步執(zhí)行。,受間接制約的類中各程序段在執(zhí)行順序上是任意的。 對(duì)于每一類，系統(tǒng)應(yīng)有相應(yīng)的分配和釋放相應(yīng)公有資源的管理辦法，以制約并發(fā)進(jìn)程。這就是互斥。,3. 什么是互斥 互斥定義：一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。 不允許兩個(gè)以上并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū) 原因：共享某一公有資源,并發(fā)進(jìn)程互斥執(zhí)行準(zhǔn)則： (1) 不能假設(shè)各并發(fā)進(jìn)程的

7、相對(duì)執(zhí)行速度。即各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。 (2) 并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其他進(jìn)程進(jìn)入臨界區(qū)。 (3) 并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。,(4) 并發(fā)進(jìn)程中的某個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。 準(zhǔn)則(1)，(2)，(3)是保證各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)和使用公有資源的權(quán)利，且保證每一時(shí)刻至多只有一個(gè)進(jìn)程在臨界區(qū)。 準(zhǔn)則(4)則是并發(fā)進(jìn)程不發(fā)生死鎖的重要保證。否則，由于某個(gè)并發(fā)進(jìn)程長(zhǎng)期占有臨界區(qū)，其他進(jìn)程則因?yàn)椴?/p>

8、能進(jìn)入臨界區(qū)而進(jìn)入互相等待狀態(tài)。,3.5.2 互斥的加鎖實(shí)現(xiàn) 怎樣實(shí)現(xiàn)并發(fā)進(jìn)程的互斥： 臨界區(qū)中的各個(gè)過程按不同的時(shí)間排列調(diào)用-不可行 對(duì)臨界區(qū)加鎖-可行,設(shè)臨界區(qū)的類名為。設(shè)鎖定位 key 表示該鎖定位屬于類名為的臨界區(qū)。 加鎖后的臨界區(qū)程序描述如下： lock(key ) 臨 界 區(qū) unlock(key ) 設(shè)key=1時(shí)表示類名為的臨界區(qū)可用，key=0時(shí)表示類名為的臨界區(qū)不可用。則，unlock(key )只用一條語(yǔ)句即可實(shí)現(xiàn)。即： key 1,lock(key )必須滿足key =0時(shí)，不允許任何進(jìn)程進(jìn)入臨界區(qū)，而key =1時(shí)僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)的準(zhǔn)則。 一種簡(jiǎn)便的實(shí)現(xiàn)方法是

9、： lock (x)=begin local v repeat vx untilv=1 x0 end,這種實(shí)現(xiàn)方法不能保證并發(fā)進(jìn)程互斥執(zhí)行所要求的準(zhǔn)則(3)。 因?yàn)楫?dāng)同時(shí)有幾個(gè)進(jìn)程調(diào)用lock(key )時(shí)，在x0語(yǔ)句執(zhí)行之前，可能已有兩個(gè)以上的多個(gè)進(jìn)程由于key =1而進(jìn)入臨界區(qū)。 為解決這個(gè)問題有些機(jī)器在硬件中設(shè)置了“測(cè)試與設(shè)置指令，保證第一步和第二步執(zhí)行不可分離。 注意：在系統(tǒng)實(shí)現(xiàn)時(shí)鎖定位key 總是設(shè)置在公有資源所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。,3.5.3 信號(hào)量和，原語(yǔ) 1. 信號(hào)量（semaphore） 加鎖的方法可以實(shí)現(xiàn)進(jìn)程之間的互斥 影響系統(tǒng)的執(zhí)行效率 在某些情況下出現(xiàn)不公平現(xiàn)象,進(jìn)程P

10、A和PB反復(fù)使用臨界區(qū)的情況： PA A：lock(key) unlock(key) Goto A PB B：lock(key ) unlock(key ) Goto B,設(shè)進(jìn)程A已通過lock(key )過程而進(jìn)入臨界區(qū)。 進(jìn)程PB將處于永久饑餓狀態(tài)（starvation）。只有在進(jìn)程PA執(zhí)行完unlock(key)過程之后、執(zhí)行Goto A語(yǔ)句之前的瞬間發(fā)生進(jìn)程調(diào)度，使進(jìn)程PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，進(jìn)程PB才有可能得到執(zhí)行。這種可能性非常小。,產(chǎn)生不公平現(xiàn)象的原因 一個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠進(jìn)程自己調(diào)用lock過程去測(cè)試相應(yīng)的鎖定位。 每個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠自己的測(cè)試判斷。沒有獲

11、得執(zhí)行機(jī)會(huì)的進(jìn)程無(wú)法判斷。 而獲得了測(cè)試機(jī)會(huì)的進(jìn)程又因需要測(cè)試而損失一定的CPU 時(shí)間。,教室設(shè)置管理員的例子。既減少了學(xué)生多次來去教室檢查門是否被打開的時(shí)間，又減少了因?yàn)閷W(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。 在操作系統(tǒng)中，這個(gè)管理員就是信號(hào)量。信號(hào)量管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實(shí)體。,信號(hào)量（semaphore） 信號(hào)量管理臨界區(qū)的公有資源 荷蘭科學(xué)家E.W.Dijkstra提出 信號(hào)量sem是一整數(shù) Sem=0：可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù) Sem0 ：正在等待使用臨界區(qū)的進(jìn)程數(shù),信號(hào)量（semaphore） 如何建立一個(gè)信號(hào)量 說明所建信號(hào)量所代表的意義 賦初值 用于互斥的信號(hào)量

12、sem的初值應(yīng)該大于零 建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)指向等待使用該臨界區(qū)的進(jìn)程,2. ，原語(yǔ) 信號(hào)量的數(shù)值僅能由，原語(yǔ)操作改變 類名為的臨界區(qū)可以描述為 When do (sem)臨界區(qū)(sem) od Sem：信號(hào)量 一次原語(yǔ)操作使得信號(hào)量sem減1 一次原語(yǔ)操作將使得信號(hào)量sem加1,原語(yǔ)操作的主要?jiǎng)幼鳎?(1) sem減 1； (2) 若sem-1 =0 ，P原語(yǔ)返回進(jìn)程繼續(xù)執(zhí)行； (3) 若sem-10，進(jìn)程阻塞并轉(zhuǎn)進(jìn)程調(diào)度。 原語(yǔ)操作的功能框圖如圖所示,原語(yǔ)操作功能 原語(yǔ)操作功能,原語(yǔ)的操作主要?jiǎng)幼鳎?(1) sem加1； (2) 若sem+1 0 ，進(jìn)程繼續(xù)執(zhí)行； (3) 若sem+1 =0

13、，喚醒一等待進(jìn)程再返回或轉(zhuǎn)進(jìn)程調(diào)度 原語(yǔ)操作的功能框圖如圖所示,3.5.4 用信號(hào)量和，原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥 設(shè)sem是用于互斥的信號(hào)量 初值為1表示沒有并發(fā)進(jìn)程使用該臨界區(qū) 臨界區(qū)置于(sem)和(sem)之間實(shí)現(xiàn)互斥,用信號(hào)量實(shí)現(xiàn)并發(fā)進(jìn)程PA，PB互斥： 1) 設(shè) sem為互斥信號(hào)量，其取值范圍為(1,0,-1) sem=1：進(jìn)程PA和PB都未進(jìn)入臨界區(qū) sem=0：進(jìn)程PA或PB已進(jìn)入臨界區(qū) sem=-1：一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū),2) 描述： PA： (sem) (sem)： ： ： PB： (sem) (sem) ： ：,1,P(sem),0,P(sem),0,P

14、(sem),0,PA,-1,P(sem),P(sem),PA,PB,0,V(sem),P(sem),PA,PB,1,V(sem),PB,3.6 進(jìn) 程 同 步 3.6.1 同步的概念 并發(fā)進(jìn)程對(duì)公有資源的競(jìng)爭(zhēng)引起間接制約 其他制約關(guān)系影響執(zhí)行速度的例子： 計(jì)算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū)Buf 計(jì)算進(jìn)程把計(jì)算結(jié)果放入 Buf中 打印進(jìn)程則打印 Buf中的數(shù)據(jù) 不采取制約措施，兩個(gè)進(jìn)程的執(zhí)行起始時(shí)間和執(zhí)行速度都是彼此獨(dú)立的,PC： : A:local Buf Repeat Buf Buf UntilBuf=空 計(jì)算 得到計(jì)算結(jié)果 Buf 計(jì)算結(jié)果 GotoA,PP:： : B:local P

15、ri Repeat Pri Buf UntilPri 空 打印 Buf中的數(shù)據(jù) 清除 Buf中的數(shù)據(jù) GotoB,假定進(jìn)程PC和PP對(duì)公用緩沖區(qū)Buf 已采取互斥措施 反復(fù)測(cè)試語(yǔ)句造成CPU時(shí)間的極大浪費(fèi) 原因：進(jìn)程PC和PP的執(zhí)行互相制約所引起的。PC的輸出結(jié)果是PP的執(zhí)行條件，反過來，PP的執(zhí)行結(jié)果也是PC的執(zhí)行條件。 這種現(xiàn)象在操作系統(tǒng)和用戶進(jìn)程中大量存在，不同于互斥的是執(zhí)行順序可以是任意的。,一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)進(jìn)程間的直接制約。 異步環(huán)境：各起始時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。,解決方法 直接制約的進(jìn)程互

16、相給對(duì)方進(jìn)程發(fā)送執(zhí)行條件已經(jīng)具備的信號(hào) 只要收到了制約進(jìn)程發(fā)來的信號(hào)便開始執(zhí)行 在未收到制約進(jìn)程發(fā)來的信號(hào)時(shí)便進(jìn)入等待狀態(tài) 被制約進(jìn)程省去對(duì)執(zhí)行條件的測(cè)試 方法最為簡(jiǎn)單和直觀,把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。 具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。,對(duì)一個(gè)消息或事件賦以唯一的消息名， 用過程 wait(消息名） 表示進(jìn)程等待合作進(jìn)程發(fā)來的消息 用過程 signal（消息名） 表示向合作進(jìn)程發(fā)送消息。 利用過程wait和signal描述上例中的同步關(guān)系：,(1

17、) 設(shè)消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。 (2) 初始化Bufempty=true，Buffull=false 。 (3) 描述： PC： A:wait(Bufempty) 計(jì)算 Buf 計(jì)算結(jié)果 Bufempty false signal(Buffull) GotoA,PP： B:wait(Buffull) 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) Buffull false signal(Bufempty) GotoB 過程wait的功能是等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行，而signal的功能則是向合作進(jìn)程發(fā)送合作進(jìn)程所需要的消息名，并將其值

18、置為true。,3.6.2 私用信號(hào)量 用信號(hào)量的方法實(shí)現(xiàn)進(jìn)程間的同步： 把各進(jìn)程之間發(fā)送的消息作為信號(hào)量看待，這里的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)。因此，稱該信號(hào)量為私用信號(hào)量（Private Semaphore）。 一個(gè)進(jìn)程Pi的私用信號(hào)量Semi是從制約進(jìn)程發(fā)送來的進(jìn)程Pi的執(zhí)行條件所需要的消息。 與私用信號(hào)量相對(duì)應(yīng)，稱互斥時(shí)使用的信號(hào)量為公用信號(hào)量。,3.6.3 用，原語(yǔ)操作實(shí)現(xiàn)同步 為各并發(fā)進(jìn)程設(shè)置私用信號(hào)量 為私用信號(hào)量賦初值 利用，原語(yǔ)和私用信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序 圖3.13 緩沖區(qū)隊(duì)列,例：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù) 發(fā)送進(jìn)程PA 和

19、接收進(jìn)程PB滿足如下條件： (1) 在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)； 2) PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的； 3) 由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。,進(jìn)程PA調(diào)用的過程deposit(data)和進(jìn)程PB調(diào)用的過程remove(data)必須同步執(zhí)行 過程 deposit(data)的執(zhí)行結(jié)果是過程remove(data)的執(zhí)行條件 當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時(shí)，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件。,描述發(fā)送過程deposit(data)和接收過程remove(data)：

20、（1) 設(shè)Bufempty為進(jìn)程PA的私用信號(hào)量，Buffull 為進(jìn)程PB的私用信號(hào)量； （2) 令Bufempty的初始值為n（n 為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)），Buffull 的初始值為0；,（3) 描述： PA: deposit(data): begin local x P(Bufempty)； 按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)； Buf(x) data Buf(x)置滿標(biāo)記 （Buffull） end,PB: remove(data): Begin local x （Buffull）； 按FIFO方式選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data Buf(x) Buf(x)置空標(biāo)記 （Bufempty） end,局部變量x用來指明緩沖區(qū)的區(qū)號(hào)，給Buf(x)置標(biāo)志位是為了便于區(qū)別和搜索空緩沖區(qū)及非空緩沖區(qū)。 需要考慮互斥,3.6.4 生產(chǎn)者-消費(fèi)者問題（producer-consumer problems） 把并發(fā)進(jìn)程的同步和互斥問題一般化，可以得到一個(gè)抽象的一般模型，即生產(chǎn)者-消費(fèi)者問題。 把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者，而把釋放同類資源的進(jìn)程稱為該資源