進(jìn)程管理概要課件

1、進(jìn)程管理概要課件進(jìn)程管理概要課件第二章 進(jìn)程管理教學(xué)目的：本課為描述程序并發(fā)執(zhí)行引入進(jìn)程的概念，描述進(jìn)程的特征、狀態(tài)、狀態(tài)的轉(zhuǎn)換、進(jìn)程控制塊等基本概念。描述控制進(jìn)程狀態(tài)轉(zhuǎn)換的OS內(nèi)核和進(jìn)程控制原語(yǔ)的功能。并發(fā)性是OS最重要的特征，進(jìn)程是OS最基本最重要的概念，進(jìn)程管理是OS的重點(diǎn)和難點(diǎn)。在進(jìn)程的控制的基礎(chǔ)上這課引入進(jìn)程同步和進(jìn)程同步機(jī)制的概念，它對(duì)并發(fā)執(zhí)行進(jìn)程的推進(jìn)序列加以限制以保證互斥使用臨界資源或協(xié)同完成任務(wù)，解決程序并發(fā)執(zhí)行時(shí)帶來(lái)結(jié)果不可再現(xiàn)問(wèn)題。這課介紹了用軟件、硬件、信號(hào)量機(jī)制、AND型信號(hào)量集、一般信號(hào)量集、管程等各種解決進(jìn)程互斥同步問(wèn)題的方法，重點(diǎn)介紹了信號(hào)量機(jī)制的概念和用信號(hào)量

2、機(jī)制解決進(jìn)程互斥同步問(wèn)題的方法 2第二章 進(jìn)程管理教學(xué)目的：4教學(xué)要求：熟悉進(jìn)程引入的必要性；熟練掌握進(jìn)程的定義和特征，熟練掌握進(jìn)程的三個(gè)基本狀態(tài)和狀態(tài)的轉(zhuǎn)換，熟練掌握進(jìn)程存在的唯一實(shí)體-進(jìn)程控制塊，熟悉進(jìn)程上下文。熟悉內(nèi)核的功能，掌握增加“掛起”、 “激活”操作的五個(gè)狀態(tài)圖和狀態(tài)的轉(zhuǎn)換，熟悉創(chuàng)建、撤消、阻塞、喚醒、掛起和激活進(jìn)程控制原語(yǔ)的功能，一般了解線程的概念。3教學(xué)要求：熟悉進(jìn)程引入的必要性；熟練掌握進(jìn)程的定義和特征，熟熟悉進(jìn)程間制約關(guān)系，掌握臨界資源和臨界區(qū)概念，掌握進(jìn)程同步和進(jìn)程同步機(jī)制，熟悉利用軟件方法和硬件技術(shù)解決進(jìn)程同步機(jī)制。熟練掌握信號(hào)量和P、V操作的概念、定義和實(shí)質(zhì)，熟練掌

3、握利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥和同步，熟悉用信號(hào)量描述前趨關(guān)系。掌握利用信號(hào)量解生產(chǎn)者-消費(fèi)者問(wèn)題、熟悉利用信號(hào)量解讀者-寫(xiě)者問(wèn)題等經(jīng)典同步問(wèn)題，掌握進(jìn)程同步分析方法。了解用AND型信號(hào)集機(jī)制、一般信號(hào)集機(jī)制和管程解經(jīng)典同步問(wèn)題。熟悉進(jìn)程通訊的概念和共享存儲(chǔ)器系統(tǒng)、消息傳送系統(tǒng)、管道通信系統(tǒng)三類(lèi)高級(jí)通訊機(jī)制，掌握消息緩沖隊(duì)列通信機(jī)制。 4熟悉進(jìn)程間制約關(guān)系，掌握臨界資源和臨界區(qū)概念，掌握進(jìn)程同步和進(jìn)程的的基本概念程序順序執(zhí)行與特征程序并發(fā)執(zhí)行與特征進(jìn)程的引入進(jìn)程狀態(tài)及其轉(zhuǎn)換進(jìn)程控制塊PCB進(jìn)程上下文進(jìn)程控制進(jìn)程創(chuàng)建進(jìn)程終止進(jìn)程阻塞與喚醒進(jìn)程的掛起與激活進(jìn)程的互斥與同步軟件方法硬件方法信號(hào)量方法管程方

4、法進(jìn)程通信共享存儲(chǔ)器消息傳遞管道通信線程5進(jìn)程的的基本概念進(jìn)程的互斥與同步7（一）進(jìn)程的的基本概念（1） 程序順序執(zhí)行與特征一個(gè)較大的程序通常都由若干個(gè)程序段組成，程序在執(zhí)行時(shí)，各程序段必須按照先后次序逐個(gè)執(zhí)行。程序各程序段先后執(zhí)行次序關(guān)系可用前趨圖表示。前趨圖是一個(gè)有向無(wú)循環(huán)圖，圖由結(jié)點(diǎn)和結(jié)點(diǎn)間有向邊組成，結(jié)點(diǎn)代表各程序段操作，而結(jié)點(diǎn)間的有向邊表示兩程序段操作之間存在的前趨關(guān)系（“-”）。兩程序段Pi和Pj的前趨關(guān)系表示成Pi-Pj，Pi是Pj的前趨，Pj是Pi的后繼。 P1C1I1 I2C2P26（一）進(jìn)程的的基本概念（1） 程序順序執(zhí)行與特征 P1C1I程序順序執(zhí)行與特征程序順序執(zhí)行特征

5、： 順序性：程序各程序段嚴(yán)格按照規(guī)定的順序執(zhí)行。 封閉性：程序執(zhí)行時(shí)機(jī)內(nèi)各資源只受該程序控制而改變，執(zhí)行結(jié)果不受外界因素影響。 可再現(xiàn)性：只要程序執(zhí)行環(huán)境和初始條件相同，程序多次執(zhí)行，可獲得相同結(jié)果。7程序順序執(zhí)行與特征程序順序執(zhí)行特征：9（2）程序并發(fā)執(zhí)行與特征 在計(jì)算機(jī)系統(tǒng)支持并行操作時(shí)，如采用多道程序設(shè)計(jì)技術(shù)，則內(nèi)存中多道程序處于并發(fā)執(zhí)行狀態(tài)。如上述有三個(gè)程序段的作業(yè)類(lèi)，雖然每個(gè)作業(yè)有前趨關(guān)系的各程序段不能在系統(tǒng)CPU和輸入輸出各部件并行執(zhí)行，但一個(gè)作業(yè)沒(méi)有前趨關(guān)系的程序段或不同作業(yè)的程序段可以分別在CPU和各輸入輸出部件上并行執(zhí)行。8（2）程序并發(fā)執(zhí)行與特征 在計(jì)算機(jī)系統(tǒng)支持并行操作程

6、序并發(fā)執(zhí)行與特征 四個(gè)上述三個(gè)程序段類(lèi)的作業(yè)并發(fā)執(zhí)行的前趨圖如下圖所示:C3I1I2I3I4C1C2C4P1P2P3P49程序并發(fā)執(zhí)行與特征 四個(gè)上述三個(gè)程序段類(lèi)的作業(yè)并發(fā)執(zhí)行的前程序并發(fā)執(zhí)行與特征程序并發(fā)執(zhí)行特征：間斷性：程序在并發(fā)執(zhí)行時(shí)，由于它們共享資源或?yàn)橥瓿赏豁?xiàng)任務(wù)而相互合作，使在并發(fā)程序之間形成了相互制約的關(guān)系。相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行-暫仃-執(zhí)行”這種間斷性活動(dòng)規(guī)律。失去封閉性：程序在并發(fā)執(zhí)行時(shí)，是多個(gè)程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個(gè)程序來(lái)改變，致使程序的執(zhí)行已失去了封閉性。10程序并發(fā)執(zhí)行與特征程序并發(fā)執(zhí)行特征：12程序并發(fā)執(zhí)行與特征不可再現(xiàn)性：程序

7、在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也將導(dǎo)致失去結(jié)果的可再現(xiàn)性。即程序經(jīng)過(guò)多次執(zhí)行，雖然其各次的環(huán)境和初始條件相同，但得到的結(jié)果卻各不相同。例1：觀察者/報(bào)告者11程序并發(fā)執(zhí)行與特征不可再現(xiàn)性：程序在并發(fā)執(zhí)行時(shí)，由于失去了封程序并發(fā)執(zhí)行與特征觀察者： 報(bào)告者：begin begin repeat repeat wait a car go through deley a time N=N+1； Print N ； N=0 ； until untilend end初始N=n時(shí)不同執(zhí)行序列： N=N+1； Print N； Print N ； Print N ； N=0 ； N=N+1 ； N=0 ；

8、N=N+1 ； N=0 ；結(jié)果各不相同: 打印n+1，N=0； 打印n，N=1； 打印n，N=0；與執(zhí)行速度有關(guān)12程序并發(fā)執(zhí)行與特征觀察者： 例2 與時(shí)間有關(guān)的錯(cuò)誤：一飛機(jī)訂票系統(tǒng)，兩個(gè)終端，執(zhí)行T1、T2進(jìn)程T1 : T2:. .Read(x); Read(x);if x=1 then if x=1 then x:=x-1; x:=x-1;write(x); write(x);. .程序并發(fā)執(zhí)行與特征中斷13例2 與時(shí)間有關(guān)的錯(cuò)誤：一飛機(jī)訂票系統(tǒng)，兩個(gè)終端，執(zhí)行T1例3銀行的聯(lián)網(wǎng)儲(chǔ)蓄業(yè)務(wù)允許儲(chǔ)戶(hù)同時(shí)用儲(chǔ)蓄卡和存折對(duì)同一帳戶(hù)進(jìn)行存取款操作，如果某儲(chǔ)戶(hù)同時(shí)（ATM，柜臺(tái)）辦理兩筆存款業(yè)務(wù)（10

9、00，2000）從系統(tǒng)的角度看，有兩個(gè)進(jìn)程將同時(shí)對(duì)儲(chǔ)戶(hù)余額等數(shù)據(jù)進(jìn)行修改。如果兩個(gè)進(jìn)程將同時(shí)對(duì)儲(chǔ)戶(hù)余額等數(shù)據(jù)進(jìn)行修改。如果兩個(gè)進(jìn)程同時(shí)讀出原余額（假設(shè)為5000），兩個(gè)進(jìn)程分別將最新余額修改為6000和700014例316分析及措施最后，儲(chǔ)戶(hù)余額可能為6000，或7000，顯然都不正確。原因：兩個(gè)進(jìn)程同時(shí)修改同一數(shù)據(jù)，而沒(méi)有進(jìn)行有效控制。正確方法：如果有多個(gè)進(jìn)程需要同時(shí)修改某一數(shù)據(jù)，系統(tǒng)必須控制，一次僅允許一個(gè)進(jìn)程完成讀數(shù)據(jù)，并修改數(shù)據(jù)兩件事以后，才允許別的進(jìn)程對(duì)同一數(shù)據(jù)的讀和修改操作。15分析及措施17通過(guò)上述例子可見(jiàn)，采用多道程序并發(fā) 設(shè)計(jì)技術(shù)的操作系統(tǒng)對(duì)諸進(jìn)程的并發(fā)控制是非常重要和必須的

10、。16通過(guò)上述例子可見(jiàn)，采用多道程序并發(fā) 設(shè)計(jì)技術(shù)的操作系統(tǒng)對(duì)諸進(jìn)（3）進(jìn)程的引入 由于程序在并發(fā)執(zhí)行時(shí)，各次執(zhí)行的結(jié)果不同，所以用“程序”這個(gè)概念已無(wú)法描述程序的并發(fā)執(zhí)行，所以必須引入新的概念-進(jìn)程來(lái)描述程序的并發(fā)執(zhí)行。進(jìn)程這一術(shù)語(yǔ)最早由麻省理工學(xué)院著名的操作系統(tǒng)MULTICS中提出。 進(jìn)程定義：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。17（3）進(jìn)程的引入 由于程序在并發(fā)執(zhí)行時(shí)，各次執(zhí)行的結(jié)果不同進(jìn)程的引入進(jìn)程的特征:結(jié)構(gòu)特征：從結(jié)構(gòu)上，進(jìn)程實(shí)體由程序段、數(shù)據(jù)段和進(jìn)程控制塊三部分組成，UNIX中稱(chēng)為“進(jìn)程映象”。進(jìn)程描述進(jìn)程控制塊PCB程序段數(shù)據(jù)結(jié)構(gòu)集18進(jìn)程的

11、引入進(jìn)程的特征:進(jìn)程描述進(jìn)程控制塊PCB程序段數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)性：動(dòng)態(tài)性是進(jìn)程的最基本特征，它是程序執(zhí)行過(guò)程，它是有一定的生命期。它由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行，因得不到資源而暫仃，并由撤消而死亡。而程序是靜態(tài)的，它是存放在介質(zhì)上一組有序指令的集合，無(wú)運(yùn)動(dòng)的含義。并發(fā)性：并發(fā)性是進(jìn)程的重要特征，同時(shí)也是OS的重要特征。并發(fā)性指多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)執(zhí)行。而程序是不能并發(fā)執(zhí)行。19動(dòng)態(tài)性：動(dòng)態(tài)性是進(jìn)程的最基本特征，它是程序執(zhí)行過(guò)程，它是有一進(jìn)程的引入獨(dú)立性：進(jìn)程是一個(gè)能獨(dú)立執(zhí)行的基本單位，即是一個(gè)獨(dú)立獲得資源和獨(dú)立調(diào)度的單位，而程序不作為獨(dú)立單位參加執(zhí)行。異步性：進(jìn)程按各自獨(dú)立的

12、不可預(yù)知的速度向前推進(jìn)，即進(jìn)程按異步方式進(jìn)行，正是這一特征，將導(dǎo)致程序執(zhí)行的不可再現(xiàn)性，因此OS必須采用某種措施來(lái)限制各進(jìn)程推進(jìn)序列以保證各程序間正常協(xié)調(diào)執(zhí)行。20進(jìn)程的引入22程序與進(jìn)程的區(qū)別與聯(lián)系進(jìn)程是程序的一次執(zhí)行，是一個(gè)動(dòng)態(tài)的概念，程序是完成某個(gè)特定功能的指令的有序序列，是一個(gè)靜態(tài)的概念 一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，同一程序也可能由多個(gè)進(jìn)程同時(shí)執(zhí)行進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，程序則不是 程序可以作為一種軟件資源長(zhǎng)期保存，而進(jìn)程是程序的一次執(zhí)行過(guò)程，它是臨時(shí)的，有生命期的 21程序與進(jìn)程的區(qū)別與聯(lián)系進(jìn)程是程序的一次執(zhí)行，是一個(gè)動(dòng)態(tài)的概念（4）進(jìn)程狀態(tài)及其轉(zhuǎn)換1. 進(jìn)程

13、的三個(gè)基本狀態(tài)執(zhí)行態(tài)（Running）：當(dāng)一個(gè)進(jìn)程在處理機(jī)上執(zhí)行時(shí)，則稱(chēng)該進(jìn)程處于執(zhí)行狀態(tài)。就緒態(tài)（Ready）：一個(gè)進(jìn)程獲得了除處理機(jī)外的一切所需資源，一旦得到處理機(jī)即可執(zhí)行，則稱(chēng)此進(jìn)程處于就緒狀態(tài)。阻塞態(tài)（Blocked）：（又稱(chēng)掛起狀態(tài)、等待狀態(tài)）：一個(gè)進(jìn)程正在等待某一事件發(fā)生（例如請(qǐng)求IO而等待IO完成等）而暫時(shí)仃止執(zhí)行，這時(shí)即使把處理機(jī)分配給進(jìn)程也無(wú)法執(zhí)行，故稱(chēng)該進(jìn)程處于阻塞狀態(tài)。22（4）進(jìn)程狀態(tài)及其轉(zhuǎn)換1. 進(jìn)程的三個(gè)基本狀態(tài)24執(zhí)行就緒阻塞進(jìn)程的狀態(tài)及其轉(zhuǎn)換調(diào)度時(shí)間片完I/O請(qǐng)求I/O完成進(jìn)程狀態(tài)及其轉(zhuǎn)換23執(zhí)行就緒阻塞進(jìn)程的狀態(tài)及其轉(zhuǎn)換調(diào)度時(shí)間片完I/O請(qǐng)求I/O完進(jìn)程狀態(tài)及

14、其轉(zhuǎn)換 三個(gè)基本狀態(tài)之間可能轉(zhuǎn)換和轉(zhuǎn)換原因如下：就緒態(tài)執(zhí)行態(tài)：當(dāng)處理機(jī)空閑時(shí)，進(jìn)程調(diào)度程序必將處理機(jī)分配給一個(gè)處于就緒態(tài)的進(jìn)程 ，該進(jìn)程便由就緒態(tài)轉(zhuǎn)換為執(zhí)行態(tài)。執(zhí)行態(tài)阻塞態(tài)：處于執(zhí)行態(tài)的進(jìn)程在執(zhí)行過(guò)程中需要等待某一事件發(fā)生后（例如因IO請(qǐng)求等待IO完成后），才能繼續(xù)執(zhí)行，則該進(jìn)程放棄處理機(jī)，從執(zhí)行態(tài)轉(zhuǎn)換為阻塞態(tài)。24進(jìn)程狀態(tài)及其轉(zhuǎn)換 26進(jìn)程狀態(tài)及其轉(zhuǎn)換阻塞態(tài)就緒態(tài)：處于阻塞態(tài)的進(jìn)程，若其等待的事件已經(jīng)發(fā)生，于是進(jìn)程由阻塞態(tài)轉(zhuǎn)換為就緒態(tài)。執(zhí)行態(tài)就緒態(tài)：處于執(zhí)行狀態(tài)的進(jìn)程在其執(zhí)行過(guò)程中，因分給它的處理機(jī)時(shí)間片已用完，而不得不讓出（被搶占）處理機(jī)，于是進(jìn)程由執(zhí)行態(tài)轉(zhuǎn)換為就緒態(tài)。 而阻塞態(tài)執(zhí)行態(tài)和就

15、緒態(tài)阻塞態(tài)這二種狀態(tài)轉(zhuǎn)換不可能發(fā)生。25進(jìn)程狀態(tài)及其轉(zhuǎn)換阻塞態(tài)就緒態(tài)：處于阻塞態(tài)的進(jìn)程，若其等備菜完成開(kāi)炒炒另一個(gè)菜時(shí)落選沒(méi)有醬油買(mǎi)來(lái)醬油就緒炒菜阻塞炒菜的三態(tài)模型26備菜完成開(kāi)炒炒另一個(gè)菜時(shí)落選沒(méi)有醬油買(mǎi)來(lái)醬油就緒炒菜阻塞炒菜系統(tǒng)中各進(jìn)程狀態(tài)的分布和管理處于執(zhí)行態(tài)進(jìn)程:如系統(tǒng)有一個(gè)處理機(jī)，則在任何一時(shí)刻，最多只有一個(gè)進(jìn)程處于執(zhí)行態(tài)。處于就緒態(tài)進(jìn)程:一般處于就緒態(tài)的進(jìn)程按照一定的算法（如先來(lái)的進(jìn)程排在前面，或采用優(yōu)先權(quán)高的進(jìn)程排在前面）排成一個(gè)就緒隊(duì)列。處于阻塞態(tài)進(jìn)程:處于阻塞態(tài)的進(jìn)程排在阻塞隊(duì)列中。由于等待事件原因不同，阻塞隊(duì)列也按事件分成幾個(gè)隊(duì)列。27系統(tǒng)中各進(jìn)程狀態(tài)的分布和管理處于執(zhí)行態(tài)

16、進(jìn)程:如系統(tǒng)有一個(gè)處理例例：一個(gè)只有一個(gè)處理機(jī)的系統(tǒng)中，OS的進(jìn)程有執(zhí)行、就緒、阻塞三個(gè)基本狀態(tài)。假如某時(shí)刻該系統(tǒng)中有10個(gè)進(jìn)程并發(fā)執(zhí)行，在略去調(diào)度程序所占用時(shí)間情況下試問(wèn)：這時(shí)刻系統(tǒng)中處于執(zhí)行態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？這時(shí)刻系統(tǒng)中處于就緒態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？這時(shí)刻系統(tǒng)中處于阻塞態(tài)的進(jìn)程數(shù)最多有幾個(gè)？最少有幾個(gè)？28例例：一個(gè)只有一個(gè)處理機(jī)的系統(tǒng)中，OS的進(jìn)程有執(zhí)行、就緒、阻解解：因?yàn)橄到y(tǒng)中只有一個(gè)處理機(jī)，所以某時(shí)刻處于執(zhí)行態(tài)的進(jìn)程數(shù)最多只有一個(gè)。而最少可能為0，此時(shí)其它10個(gè)進(jìn)程一定全部排在各阻塞隊(duì)列中，在就緒隊(duì)列中沒(méi)有進(jìn)程。而某時(shí)刻處于就緒態(tài)的進(jìn)程數(shù)最多只有9個(gè)，不可

17、能出現(xiàn)10個(gè)情況，因?yàn)橐坏〤PU有空，調(diào)度程序馬上調(diào)度，當(dāng)然這是在略去調(diào)度程序調(diào)度時(shí)間時(shí)考慮。處于阻塞態(tài)的進(jìn)程數(shù)最少是0個(gè)。29解解：因?yàn)橄到y(tǒng)中只有一個(gè)處理機(jī)，所以某時(shí)刻處于執(zhí)行態(tài)的進(jìn)程數(shù)4。系統(tǒng)中各進(jìn)程狀態(tài)轉(zhuǎn)換影響執(zhí)行 阻塞就緒執(zhí)行 阻塞就緒 A進(jìn)程 B進(jìn)程 C進(jìn)程 D進(jìn)程執(zhí)行 執(zhí)行 阻塞就緒阻塞就緒進(jìn)程狀態(tài)及其轉(zhuǎn)換304。系統(tǒng)中各進(jìn)程狀態(tài)轉(zhuǎn)換影響執(zhí)行 阻塞就緒執(zhí)行 阻塞就緒進(jìn)程狀態(tài)及其轉(zhuǎn)換 在一個(gè)多道程序設(shè)計(jì)的系統(tǒng)中，各進(jìn)程狀態(tài)轉(zhuǎn)換會(huì)互相影響。例如系統(tǒng)中一個(gè)執(zhí)行態(tài)的進(jìn)程A發(fā)生I/O請(qǐng)求后要等待I/O完成，它的狀態(tài)也由執(zhí)行態(tài)轉(zhuǎn)換為阻塞態(tài)，此時(shí)進(jìn)程調(diào)度程序就會(huì)按照一定的算法，在就緒隊(duì)列中選一個(gè)

18、進(jìn)程B，將處理機(jī)分給它，該B進(jìn)程的狀態(tài)也由就緒態(tài)轉(zhuǎn)換為執(zhí)行態(tài)。如一個(gè)進(jìn)程C等待的事件完成，則它的狀態(tài)由阻塞態(tài)轉(zhuǎn)換為就緒態(tài)，它也從阻塞隊(duì)列中抽出插入就緒隊(duì)列中。如進(jìn)程 C從阻塞態(tài)轉(zhuǎn)換為就緒態(tài)時(shí)，有一個(gè)進(jìn)程D在CPU上執(zhí)行。而系統(tǒng)采用搶占式調(diào)度算法，進(jìn)程C的優(yōu)先級(jí)又高于正在CPU上執(zhí)行的進(jìn)程D的優(yōu)先級(jí)，則要發(fā)行搶占調(diào)度。即接下去的操作時(shí)由進(jìn)程調(diào)度程序?qū)⒄趫?zhí)行的進(jìn)程D由執(zhí)行態(tài)轉(zhuǎn)換為就緒態(tài)，插入就緒隊(duì)列。31進(jìn)程狀態(tài)及其轉(zhuǎn)換 在一個(gè)多道程序設(shè)計(jì)的系統(tǒng)中，各進(jìn)程狀 除此之外，在實(shí)際的系統(tǒng)中，將進(jìn)程的狀態(tài)進(jìn)一步細(xì)分為五個(gè)狀態(tài)，除了上述三個(gè)狀態(tài)之外，增加了創(chuàng)建和退出兩個(gè)狀態(tài)。新建狀態(tài)（New)：進(jìn)程還在創(chuàng)

19、建過(guò)程中，還不能運(yùn)行。這時(shí)，操作系統(tǒng)要建立PCB、建立資源表、分配資源、建立地址空間表。終止?fàn)顟B(tài)（Exit)：進(jìn)程運(yùn)行結(jié)束，系統(tǒng)回收所占用資源。2、五態(tài)模型32 除此之外，在實(shí)際的系統(tǒng)中，將進(jìn)程的狀態(tài)進(jìn)一步細(xì)分為五五態(tài)模型創(chuàng)建新建提交就緒調(diào)度執(zhí)行釋放終止等待事件阻塞事件出現(xiàn)落選33五態(tài)模型創(chuàng)建新建提交就緒調(diào)度執(zhí)行釋放終止等待事件阻塞事件出現(xiàn)問(wèn)題：多個(gè)進(jìn)程競(jìng)爭(zhēng)系統(tǒng)資源內(nèi)存資源緊張無(wú)就緒進(jìn)程，處理機(jī)空閑：I/O的速度比處理機(jī)的速度慢的多，可能出現(xiàn)所有進(jìn)程阻塞等待I/O34問(wèn)題：多個(gè)進(jìn)程競(jìng)爭(zhēng)系統(tǒng)資源內(nèi)存資源緊張36解決辦法 把某些進(jìn)程掛起（suspend），對(duì)換到磁盤(pán)鏡像區(qū)中，暫時(shí)不參與進(jìn)程調(diào)度，起

20、到平滑系統(tǒng)操作負(fù)荷的目的。35解決辦法 把某些進(jìn)程掛起（suspend），對(duì)換到磁盤(pán)鏡像3、七態(tài)模型進(jìn)程增加了兩個(gè)新?tīng)顟B(tài)：掛起就緒態(tài)（ready suspend）表明進(jìn)程具備運(yùn)行條件但目前在二級(jí)存儲(chǔ)器中，當(dāng)它被對(duì)換到主存才能被調(diào)度執(zhí)行。掛起等待態(tài)（blocked suspend） 表明進(jìn)程正在等待某一個(gè)事件且在二級(jí)存儲(chǔ)器中。363、七態(tài)模型進(jìn)程增加了兩個(gè)新?tīng)顟B(tài)：38掛起原因引入原因終端用戶(hù)請(qǐng)求父進(jìn)程請(qǐng)求（考察、修改、協(xié)調(diào)）負(fù)荷調(diào)節(jié)需要操作系統(tǒng)需要（監(jiān)察資源使用情況或記賬）37掛起原因引入原因39掛起等待事件結(jié)束出現(xiàn)等待事件解除掛起掛起落選選中運(yùn)行態(tài)就緒態(tài)等待事件結(jié)束終止態(tài)新建態(tài)掛起就緒態(tài)解除掛

21、起掛起掛起等待態(tài)等待態(tài)提交提交七狀態(tài)進(jìn)程狀態(tài)及其轉(zhuǎn)換如果當(dāng)前不存在就緒進(jìn)程，那么至少有一個(gè)等待態(tài)進(jìn)程將被對(duì)換出去成為掛起等待態(tài)；操作系統(tǒng)根據(jù)當(dāng)前資源狀況和性能要求，可以決定把等待態(tài)進(jìn)程對(duì)換出去成為掛起等待態(tài) 引起進(jìn)程等待的事件發(fā)生之后，相應(yīng)的掛起等待態(tài)進(jìn)程將轉(zhuǎn)換為掛起就緒態(tài) 當(dāng)內(nèi)存中沒(méi)有就緒態(tài)進(jìn)程，或者掛起就緒態(tài)進(jìn)程具有比就緒態(tài)進(jìn)程更高的優(yōu)先級(jí)，系統(tǒng)將把掛起就緒態(tài)進(jìn)程轉(zhuǎn)換成就緒態(tài)。 操作系統(tǒng)根據(jù)當(dāng)前資源狀況和性能要求，也可以決定把就緒態(tài)進(jìn)程對(duì)換出去成為掛起就緒態(tài) 當(dāng)一個(gè)進(jìn)程等待一個(gè)事件時(shí)，原則上不需要把它調(diào)入內(nèi)存。但是在下面一種情況下，這一狀態(tài)變化是可能的。當(dāng)一個(gè)進(jìn)程退出后，主存已經(jīng)有了一大塊

22、自由空間，而某個(gè)掛起等待態(tài)進(jìn)程具有較高的優(yōu)先級(jí)并且操作系統(tǒng)已經(jīng)得知導(dǎo)致它阻塞的事件即將結(jié)束，此時(shí)便發(fā)生了這一狀態(tài)變化 掛起當(dāng)一個(gè)具有較高優(yōu)先級(jí)的掛起等待態(tài)進(jìn)程的等待事件結(jié)束后，它需要搶占CPU，而此時(shí)主存空間不夠，從而可能導(dǎo)致正在運(yùn)行的進(jìn)程轉(zhuǎn)化為掛起就緒態(tài)。另外處于運(yùn)行態(tài)的進(jìn)程也可以自己掛起自己 提交考慮到系統(tǒng)當(dāng)前資源狀況和性能要求，可以決定新建的進(jìn)程將被對(duì)換出去成為掛起就緒態(tài) 38掛起等待事件結(jié)束出現(xiàn)等待事件解除掛起掛起落選選中運(yùn)行態(tài)就緒態(tài)七狀態(tài)進(jìn)程狀態(tài)及其轉(zhuǎn)換活動(dòng)就緒 靜止就緒活動(dòng)阻塞 靜止阻塞靜止就緒 活動(dòng)就緒靜止阻塞 活動(dòng)阻塞39七狀態(tài)進(jìn)程狀態(tài)及其轉(zhuǎn)換活動(dòng)就緒 靜止就緒41（5）進(jìn)程控

23、制模塊PCB 1進(jìn)程控制塊的作用進(jìn)程存在的唯一實(shí)體 由于進(jìn)程控制塊中記錄進(jìn)程存在和特性信息；PCB與進(jìn)程同生死，創(chuàng)建一個(gè)進(jìn)程就是為其建立一個(gè)PCB，當(dāng)進(jìn)程被撤消時(shí)，系統(tǒng)就回收它的PCB；OS對(duì)進(jìn)程的控制要是根據(jù)PCB來(lái)進(jìn)行，對(duì)進(jìn)程管理也通過(guò)對(duì)PCB管理來(lái)實(shí)現(xiàn)，所以進(jìn)程控制塊是進(jìn)程存在的唯一實(shí)體。 PCB常駐內(nèi)存，系統(tǒng)將所有的PCB組織成若干個(gè)鏈表（或隊(duì)列），存放在操作系統(tǒng)中專(zhuān)門(mén)開(kāi)辟的PCB區(qū)內(nèi)。40（5）進(jìn)程控制模塊PCB 1進(jìn)程控制塊的作用進(jìn)程存在的唯進(jìn)程控制塊包含四類(lèi)信息標(biāo)識(shí)信息現(xiàn)場(chǎng)信息調(diào)度信息控制信息41進(jìn)程控制塊包含四類(lèi)信息標(biāo)識(shí)信息43標(biāo)識(shí)信息 用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程，分由用戶(hù)使用的外

24、部標(biāo)識(shí)符和被系統(tǒng)使用的內(nèi)部標(biāo)識(shí)號(hào)。 常用的標(biāo)識(shí)信息有數(shù)字標(biāo)識(shí)符、進(jìn)程標(biāo)識(shí)符、父進(jìn)程的標(biāo)識(shí)符、用戶(hù)進(jìn)程名、用戶(hù)組名等。 “我是誰(shuí)”進(jìn)程控制模塊（PCB）42標(biāo)識(shí)信息 用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程，分由用戶(hù)使用的外部標(biāo)現(xiàn)場(chǎng)信息（處理機(jī)狀態(tài)） 保留進(jìn)程運(yùn)行時(shí)存放在處理器現(xiàn)場(chǎng)中的各種信息，進(jìn)程讓出處理器時(shí)必須把處理器現(xiàn)場(chǎng)信息保存到PCB中，當(dāng)該進(jìn)程重新恢復(fù)運(yùn)行時(shí)也應(yīng)恢復(fù)處理器現(xiàn)場(chǎng)。 現(xiàn)場(chǎng)信息包括通用寄存器內(nèi)容、控制寄存器內(nèi)容、指令計(jì)數(shù)器、程序狀態(tài)字、用戶(hù)堆棧指針、系統(tǒng)堆棧指針等。 “我周?chē)鞘裁矗以诟墒裁础边M(jìn)程控制模塊（PCB）43現(xiàn)場(chǎng)信息（處理機(jī)狀態(tài)） 保留進(jìn)程運(yùn)行時(shí)存放在處理器現(xiàn)場(chǎng)中進(jìn)程調(diào)度信息 包括

25、進(jìn)程狀態(tài)（running、ready、blacked）、隊(duì)列指針（就緒、阻塞隊(duì)列），調(diào)度參數(shù)：進(jìn)程優(yōu)先級(jí)、進(jìn)程已執(zhí)行時(shí)間和已等待時(shí)間、等待事件和等待原因等。進(jìn)程控制模塊（PCB）44進(jìn)程調(diào)度信息進(jìn)程控制模塊（PCB）46進(jìn)程控制模塊（PCB）進(jìn)程控制信息 它包括程序和數(shù)據(jù)的地址、保證進(jìn)程正常執(zhí)行的同步和通信機(jī)制，如消息隊(duì)列指針、信號(hào)量等互斥和同步機(jī)制等、 IO資源清單、鏈接指針（本進(jìn)程pcb所在對(duì)列的下一個(gè)進(jìn)程的pcb的首地址）。45進(jìn)程控制模塊（PCB）進(jìn)程控制信息47 UNIX的PCB由Proc和user兩個(gè)結(jié)構(gòu)組成，proc常駐主存的系統(tǒng)區(qū)，是PCB中最基本和常用信息，而user可根據(jù)需

26、要換進(jìn)換出。進(jìn)程控制模塊（PCB）46 UNIX的PCB由Proc和user兩個(gè)結(jié)構(gòu)組成進(jìn)程控制模塊（PCB）3、進(jìn)程控制塊的組織方式 在一個(gè)系統(tǒng)中，通?？蓳碛袛?shù)十個(gè)、數(shù)百個(gè)乃至數(shù)千個(gè)PCB。為了能對(duì)它們加以有效的管理，應(yīng)該用適當(dāng)?shù)姆绞綄⑦@些PCB組織起來(lái)。目前常用的組織方式有以下兩種：鏈接方式索引方式47進(jìn)程控制模塊（PCB）3、進(jìn)程控制塊的組織方式49進(jìn)程控制模塊（PCB）48進(jìn)程控制模塊（PCB）50進(jìn)程控制模塊（PCB）49進(jìn)程控制模塊（PCB）51進(jìn)程控制模塊（PCB）PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索引表50進(jìn)程控制

27、模塊（PCB）PCB1PCB2PCB3PCB4PCB5153（6） 進(jìn)程上下文 進(jìn)程是由程序、數(shù)據(jù)和進(jìn)程控制塊組成。進(jìn)程上下文實(shí)際上是執(zhí)行活動(dòng)全過(guò)程的靜態(tài)描述。具體說(shuō)，進(jìn)程上下文包括系統(tǒng)中與執(zhí)行該進(jìn)程有關(guān)的各種寄存器（例如：通用寄存器、程序計(jì)數(shù)器PC、程序狀態(tài)寄存器PS等）的值，程序段在經(jīng)編譯之后形成的機(jī)器指令代碼集（或稱(chēng)正文段）、數(shù)據(jù)集及各種堆棧值和PCB結(jié)構(gòu)，如下圖所示。 P C B 各種控制表指針 各種寄存器正文集數(shù)據(jù)集棧區(qū)52（6） 進(jìn)程上下文 進(jìn)程是由程序、數(shù)據(jù)和進(jìn)程控制塊組成。進(jìn)所謂原語(yǔ)，是由若干條指令所組成的個(gè)指令序列用來(lái)實(shí)現(xiàn)某個(gè)特定的操作功能。這個(gè)指令序列的執(zhí)行是連續(xù)的，具有不

28、可分割性在執(zhí)行時(shí)也不可間斷，直至該指令序列執(zhí)行結(jié)束。 原語(yǔ)是操作系統(tǒng)核心(由一組程序模塊所組成的、完成操作系統(tǒng)中基本功能)的一個(gè)組成部分。原語(yǔ)必須在管態(tài)下執(zhí)行，并且常駐內(nèi)存。 （二）進(jìn)程控制(Process Control )原語(yǔ)53所謂原語(yǔ)，是由若干條指令所組成的個(gè)指令序列用來(lái)實(shí)現(xiàn)某個(gè)原語(yǔ) 原語(yǔ)是一種特殊的廣義指令，它的功能是由系統(tǒng)通過(guò)一段不可分割的指令操作來(lái)完成，它又稱(chēng)原子操作，原語(yǔ)在核心態(tài)下完成。進(jìn)程控制操作（創(chuàng)建、撤消、阻塞）大都為原語(yǔ)操作。54原語(yǔ) 原語(yǔ)是一種特殊的廣義指令，它的功能是由系統(tǒng)通procedure block begin i:=EP; stop (i); i.statu

29、s:=“blockeda”; i.sdata:=WQ (r); insert (WQ (r), i); scheduler end 55procedure block57核心態(tài)和用戶(hù)態(tài) Intel公司的80386及更高級(jí)的CPU可以提供程序代碼4層不同等級(jí)的權(quán)力，包括有Ring0-3。Ring0擁有最高的運(yùn)行優(yōu)先權(quán)，它訪問(wèn)所有系統(tǒng)內(nèi)存和所有的CPU指令，而Ring1-3訪問(wèn)權(quán)限受到不同限制。Windows 98/NT為了與基于RISC的結(jié)構(gòu)上兼容只使用兩個(gè)特權(quán)級(jí)別：Ring0和Ring3 為了防止用戶(hù)應(yīng)用程序訪問(wèn)或更改重要的操作系統(tǒng)數(shù)據(jù)，Windows98/NT、UNIX使用兩種處理器訪問(wèn)模式

30、：核心態(tài)和用戶(hù)態(tài)。操作系統(tǒng)代碼在核心態(tài)下執(zhí)行，即在X86處理器Ring0執(zhí)行，它有著最高的特權(quán)。而用戶(hù)應(yīng)用程序代碼在用戶(hù)態(tài)下執(zhí)行，即在X86處理器Ring3中執(zhí)行。56核心態(tài)和用戶(hù)態(tài) Intel公司的803用戶(hù)應(yīng)用程序（在Windows98/NT中以用戶(hù)線程方式出現(xiàn)）運(yùn)行用戶(hù)程序一般代碼時(shí)，它是在用戶(hù)態(tài)下執(zhí)行。但當(dāng)程序要調(diào)用系統(tǒng)服務(wù)，例如要調(diào)用OS中負(fù)責(zé)從磁盤(pán)文件中讀取數(shù)據(jù)的NT執(zhí)行體例程時(shí)，它就要通過(guò)一條專(zhuān)門(mén)的指令(系統(tǒng)調(diào)用)來(lái)完成從用戶(hù)態(tài)切換到核心態(tài)，OS根據(jù)該指令及有關(guān)參數(shù)，執(zhí)行用戶(hù)的請(qǐng)求服務(wù)。在服務(wù)完成后將處理器模式切換回用戶(hù)態(tài)，并將控制返回用戶(hù)線程。因此用戶(hù)線程有時(shí)在核心態(tài)下執(zhí)行，在

31、核心態(tài)下執(zhí)行的是調(diào)用操作系統(tǒng)有關(guān)功能模塊的代碼。 57用戶(hù)應(yīng)用程序（在Windows98/NT中以用戶(hù)線程方式出現(xiàn)進(jìn)程切換與模式切換 模式切換不同于進(jìn)程切換，它并不引起進(jìn)程狀態(tài)的變化，在大多數(shù)操作系統(tǒng)中，它也不一定引起進(jìn)程的切換，在完成了中斷調(diào)用之后，完全可以再通過(guò)一次逆向的模式切換來(lái)繼續(xù)執(zhí)行用戶(hù)進(jìn)程。 58進(jìn)程切換與模式切換 模式切換不同于進(jìn)程切換，它5961進(jìn)程切換的步驟如下： 保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息。 修改被中斷進(jìn)程的進(jìn)程控制塊的有關(guān)信息，如進(jìn)程狀態(tài)等。 把被中斷進(jìn)程的進(jìn)程控制塊加入有關(guān)隊(duì)列。 選擇下一個(gè)占有處理器運(yùn)行的進(jìn)程。 修改被選中進(jìn)程的進(jìn)程控制塊的有關(guān)信息。 根據(jù)被選中進(jìn)

32、程設(shè)置操作系統(tǒng)用到的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)信息。 根據(jù)被選中進(jìn)程恢復(fù)處理器現(xiàn)場(chǎng)。60進(jìn)程切換的步驟如下：62模式切換的步驟如下： 保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息。 根據(jù)中斷號(hào)置程序計(jì)數(shù)器。 把用戶(hù)狀態(tài)切換到內(nèi)核狀態(tài)，以便執(zhí)行中斷處理程序。61模式切換的步驟如下：63有效合理地使用模式切換和進(jìn)程切換有利于操作系統(tǒng)效率的提高。為此，大多數(shù)現(xiàn)代操作系統(tǒng)存在兩個(gè)名詞：系統(tǒng)進(jìn)程（線程）和用戶(hù)進(jìn)程（線程）。它們并不是指兩個(gè)具體的進(jìn)程實(shí)體，而是指一個(gè)進(jìn)程的兩個(gè)側(cè)面，系統(tǒng)進(jìn)程是在核心態(tài)下執(zhí)行操作系統(tǒng)代碼的進(jìn)程，用戶(hù)進(jìn)程在用戶(hù)態(tài)下執(zhí)行用戶(hù)程序的進(jìn)程。用戶(hù)進(jìn)程因中斷和系統(tǒng)調(diào)用進(jìn)入內(nèi)核態(tài)，系統(tǒng)進(jìn)程就開(kāi)始執(zhí)行，這兩個(gè)進(jìn)程

33、(用戶(hù)進(jìn)程和系統(tǒng)進(jìn)程)使用同一個(gè)PCB，所以實(shí)質(zhì)上是一個(gè)進(jìn)程實(shí)體。但是這兩個(gè)進(jìn)程所執(zhí)行的程序不同，映射到不同物理地址空間、使用不同堆棧。一個(gè)系統(tǒng)進(jìn)程的地址空間中包含所有的系統(tǒng)核心程序和各進(jìn)程的進(jìn)程數(shù)據(jù)區(qū)，所以，各進(jìn)程的系統(tǒng)進(jìn)程除數(shù)據(jù)區(qū)不同外，其余部分全相同，但各進(jìn)程的用戶(hù)進(jìn)程部分則各不相同。 62有效合理地使用模式切換和進(jìn)程切換有利于操作系統(tǒng)效率的提高。為 63 65思考PCB和進(jìn)程的代碼數(shù)據(jù)放在一起嗎？系統(tǒng)態(tài)和用戶(hù)態(tài)系統(tǒng)空間和用戶(hù)空間系統(tǒng)調(diào)用和普通調(diào)用的區(qū)別？系統(tǒng)調(diào)用會(huì)引起從用戶(hù)態(tài)進(jìn)入核心態(tài)64思考PCB和進(jìn)程的代碼數(shù)據(jù)放在一起嗎？661、進(jìn)程的創(chuàng)建 引起進(jìn)程創(chuàng)建的事件在終端上交互式的登錄（

34、合法則建立）為終端用戶(hù)建立一進(jìn)程作業(yè)調(diào)度。為被調(diào)度的作業(yè)建立進(jìn)程操作系統(tǒng)創(chuàng)建一個(gè)服務(wù)進(jìn)程。如要打印時(shí)建立打印進(jìn)程應(yīng)用請(qǐng)求由應(yīng)用程序建立多個(gè)進(jìn)程（二）進(jìn)程控制(Process Control )651、進(jìn)程的創(chuàng)建 引起進(jìn)程創(chuàng)建的事件（二）進(jìn)程控制(Proce進(jìn)程創(chuàng)建的過(guò)程 在主進(jìn)程表中增加一項(xiàng)，并從PCB池中取一個(gè)空白PCB。為新進(jìn)程所有成分分配地址空間。為新進(jìn)程分配資源，內(nèi)存空間及其它各種資源。查找輔助存儲(chǔ)器，找到進(jìn)程正文段并裝到正文區(qū)。初始化進(jìn)程控制塊，為新進(jìn)程分配唯一進(jìn)程標(biāo)識(shí)符，初始化PSW。把進(jìn)程加入某一就緒進(jìn)程隊(duì)列。通知操作系統(tǒng)的某些模塊，如記賬程序、性能監(jiān)控程序。進(jìn)程的創(chuàng)建 66進(jìn)程

35、創(chuàng)建的過(guò)程進(jìn)程的創(chuàng)建 682、進(jìn)程的終止引起進(jìn)程終止的事件正常結(jié)束 如Holt、logoff異常結(jié)束 如Protect error、overtime外界干預(yù)a.系統(tǒng)員kill進(jìn)程；b.父進(jìn)程終止；c.父進(jìn)程請(qǐng)求。672、進(jìn)程的終止引起進(jìn)程終止的事件69進(jìn)程終止的過(guò)程（1）檢查進(jìn)程狀態(tài)；（2）若為執(zhí)行態(tài)中止，且置調(diào)度標(biāo)志為真。（3）有無(wú)子孫需終止。（4）歸還資源給其父進(jìn)程或系統(tǒng)。（5）從PCB隊(duì)列中移出PCB,等待其他程序來(lái)搜集信息.68進(jìn)程終止的過(guò)程703、進(jìn)程的阻塞與喚醒引起進(jìn)程阻塞和喚醒的事件1.請(qǐng)求系統(tǒng)服務(wù)而得不到滿足時(shí)，如問(wèn)系統(tǒng)請(qǐng)求打印。2.啟動(dòng)某種操作而需同步時(shí)：如該操作和請(qǐng)求該操作

36、的進(jìn)程需同步運(yùn)行（即非異步操作）。3.新數(shù)據(jù)尚未到達(dá)：如進(jìn)程A寫(xiě)，進(jìn)程B讀，則A未寫(xiě)，完B不能讀。4.無(wú)新工作可做。693、進(jìn)程的阻塞與喚醒引起進(jìn)程阻塞和喚醒的事件71進(jìn)程阻塞過(guò)程：是進(jìn)程自身的一種主動(dòng)行為a.調(diào)block原語(yǔ)b.停止執(zhí)行，修改PCB入阻塞隊(duì)列（一個(gè)或多個(gè)），并轉(zhuǎn)調(diào)度。喚醒過(guò)程其它相關(guān)進(jìn)程完成。a.wakeup原語(yǔ)b.修改PCB，入就緒隊(duì)列可見(jiàn)，有block原語(yǔ)，在其它進(jìn)程中就應(yīng)有wakeup原語(yǔ)。70進(jìn)程阻塞過(guò)程：是進(jìn)程自身的一種主動(dòng)行為724、進(jìn)程的掛起與激活一、進(jìn)程的掛起過(guò)程由進(jìn)程自己或其父進(jìn)程調(diào)suspend原語(yǔ)完成，將該進(jìn)程PCB移到指定區(qū)域，注意狀態(tài)的改變，有可能要

37、重新調(diào)度。二、進(jìn)程的激活過(guò)程。active原語(yǔ)（如在外存，調(diào)入內(nèi)存，改變狀態(tài)，根據(jù)情況看是否調(diào)度，如搶先或非搶先）。阻塞、喚醒一般由OS實(shí)現(xiàn)，而掛起與激活可由用戶(hù)干預(yù)。714、進(jìn)程的掛起與激活一、進(jìn)程的掛起過(guò)程73討論 搶占式調(diào)度 假如采用搶占式調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，例如執(zhí)行喚醒原語(yǔ)，被喚醒進(jìn)程從活動(dòng)阻塞態(tài)轉(zhuǎn)為活動(dòng)就緒態(tài)時(shí)，或者執(zhí)行激活原語(yǔ)，被激活進(jìn)程從靜止就緒態(tài)轉(zhuǎn)為活動(dòng)就緒態(tài)時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度。即由調(diào)度程序?qū)⒓せ畹倪M(jìn)程（或喚醒的進(jìn)程）與當(dāng)前執(zhí)行進(jìn)程進(jìn)行優(yōu)先級(jí)比較，如果被激活的進(jìn)程的優(yōu)先級(jí)更高，則剝奪當(dāng)前進(jìn)程的執(zhí)行，把處理機(jī)分配給剛激活的進(jìn)程，否則就不必重新調(diào)度。

38、72討論 搶占式調(diào)度74（三）進(jìn)程同步(Synchronization of multiple processes)（1）進(jìn)程同步的基本概念1。進(jìn)程間制約關(guān)系 在多道程序環(huán)境下，系統(tǒng)中各進(jìn)程以不可預(yù)測(cè)的速度向前推進(jìn)，進(jìn)程的異步性會(huì)造成了結(jié)果的不可再現(xiàn)性。為防止這種現(xiàn)象，異步的進(jìn)程間推進(jìn)受到二種限制：73（三）進(jìn)程同步(Synchronization of mul資源共享關(guān)系（Cooperation Among Processes by Sharing）（間接相互制約） 多進(jìn)程共享資源相互合作關(guān)系 （Cooperation Among Processes by Communication）（直接

39、相互制約） 在某些進(jìn)程之間還存在合作關(guān)系，例如一個(gè)程序的輸入、計(jì)算、打印三個(gè)程序段作為三個(gè)進(jìn)程并發(fā)執(zhí)行，由于這三個(gè)進(jìn)程間存在著相互合作的關(guān)系，即先輸入再計(jì)算、最后再打印的關(guān)系，所以這三個(gè)進(jìn)程在并發(fā)執(zhí)行時(shí)推進(jìn)序列受到限制，要保證其合作關(guān)系正確，進(jìn)程間這種關(guān)系稱(chēng)為同步關(guān)系。 74資源共享關(guān)系（Cooperation Among Proce 并發(fā)進(jìn)程之間的競(jìng)爭(zhēng)關(guān)系 進(jìn)程的互斥 并發(fā)進(jìn)程之間的協(xié)作關(guān)系 進(jìn)程的同步進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作75 并發(fā)進(jìn)程之間的競(jìng)爭(zhēng)關(guān)系進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作77第一種是競(jìng)爭(zhēng)關(guān)系 系統(tǒng)中的多個(gè)進(jìn)程之間彼此無(wú)關(guān)，它們并不知道其它進(jìn)程的存在，并且也不受其它進(jìn)程的影響。但是，由于這些

40、進(jìn)程共用了一套計(jì)算機(jī)系統(tǒng)資源，因而，必然要出現(xiàn)多個(gè)進(jìn)程競(jìng)爭(zhēng)資源的問(wèn)題。進(jìn)程資源進(jìn)程競(jìng)爭(zhēng)關(guān)系（間接制約關(guān)系）76第一種是競(jìng)爭(zhēng)關(guān)系 系統(tǒng)中的多個(gè)進(jìn)程之間彼此無(wú)關(guān)，它們并不2、進(jìn)程之間競(jìng)爭(zhēng)資源面臨三個(gè)控制問(wèn)題： 互斥（ mutual exclusion ) 死鎖（ deadlock ) 饑餓（ starvation ) 多進(jìn)程共享資源，例如各進(jìn)程爭(zhēng)用一臺(tái)打印機(jī)，這時(shí)各進(jìn)程使用這臺(tái)打印機(jī)時(shí)有一定的限制。每次只允許一個(gè)進(jìn)程使用一段時(shí)間打印機(jī)，等該進(jìn)程使用完畢后再將打印機(jī)分配給其它進(jìn)程。這種使用原則稱(chēng)為互斥使用。772、進(jìn)程之間競(jìng)爭(zhēng)資源面臨三個(gè)控制問(wèn)題：79競(jìng)爭(zhēng)資源饑餓假設(shè)有3個(gè)進(jìn)程P1,P2 ,P3，每

41、個(gè)進(jìn)程都需要周期性的使用資源R如果當(dāng)前P1正在使用臨界資源R，P2和P3因?yàn)榈却齊而阻塞。當(dāng)P1退出臨界區(qū)時(shí)，P2立即進(jìn)入臨界區(qū)執(zhí)行，若P2還未退出臨界區(qū)時(shí)，P1又申請(qǐng)使用臨界資源R.假設(shè)P2退出臨界區(qū)后，系統(tǒng)將R分給了P1，然后，當(dāng)R空閑時(shí)，又將其分給P2，如此反復(fù)。 78競(jìng)爭(zhēng)資源饑餓80競(jìng)爭(zhēng)資源死鎖當(dāng)并發(fā)進(jìn)程競(jìng)爭(zhēng)使用同一資源時(shí)，它們之間就會(huì)發(fā)生沖突。如果操作系統(tǒng)將資源分配給其中的某一個(gè)進(jìn)程使用，另一個(gè)進(jìn)程就必須等待，直到申請(qǐng)的資源可用時(shí)，由操作系統(tǒng)分配給它。如果競(jìng)爭(zhēng)某資源的進(jìn)程太多，這些進(jìn)程還必須等待在一個(gè)隊(duì)列中，如就緒隊(duì)列，阻塞隊(duì)列等。一種極端的情況是，被阻塞進(jìn)程永久得不到申請(qǐng)的資源，而

42、死鎖。79競(jìng)爭(zhēng)資源死鎖當(dāng)并發(fā)進(jìn)程競(jìng)爭(zhēng)使用同一資源時(shí)，它們之間就會(huì)發(fā)生P1P2R1R280P1P2R1R282第二種是協(xié)作關(guān)系某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。比如：輸入進(jìn)程、加工處理、輸出進(jìn)程進(jìn)程進(jìn)程進(jìn)程的同步是解決進(jìn)程間協(xié)作關(guān)系(直接制約關(guān)系)的手段。81第二種是協(xié)作關(guān)系某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。83進(jìn)程同步指兩個(gè)以上進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的活動(dòng)。一個(gè)進(jìn)程的執(zhí)行依賴(lài)于協(xié)作進(jìn)程的消息或信號(hào)，當(dāng)一個(gè)進(jìn)程沒(méi)有得到來(lái)自于協(xié)作進(jìn)程的消息或信號(hào)時(shí)需等待，直到消息或信號(hào)到達(dá)才被喚醒。 82進(jìn)程同步指兩個(gè)以上進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的活動(dòng)。一個(gè)進(jìn)程進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即逐

43、次使用互斥共享資源，是對(duì)進(jìn)程使用資源次序上的一種協(xié)調(diào)。83進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即逐次使用互斥共享資源進(jìn)程競(jìng)爭(zhēng)資源首先必須解決“互斥”問(wèn)題。某些資源必須互斥使用。如打印機(jī)，共享變量等。這類(lèi)資源又稱(chēng)為臨界資源，訪臨界資源的那段代碼稱(chēng)為臨界區(qū)。任何時(shí)刻，只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，以此實(shí)現(xiàn)進(jìn)程對(duì)臨界資源的互斥訪問(wèn)。3、臨界資源和臨界區(qū)84進(jìn)程競(jìng)爭(zhēng)資源首先必須解決“互斥”問(wèn)題。某些資源必須互斥使用。臨界資源 象打印機(jī)這類(lèi)資源一次只允許一個(gè)進(jìn)程使用的資源稱(chēng)為臨界資源。屬于臨界資源有硬件打印機(jī)、磁帶機(jī)等，軟件有消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。當(dāng)然還有一類(lèi)象磁盤(pán)等資源，它允許進(jìn)程間共享，

44、即可交替使用，所以它稱(chēng)為共享資源，而臨界資源又稱(chēng)獨(dú)享資源。引起不可再現(xiàn)性是因?yàn)榕R界資源沒(méi)有互斥訪問(wèn)。85臨界資源87進(jìn)程同步的概念臨界區(qū)(critical sections) 多個(gè)進(jìn)程共享臨界資源時(shí)必須互斥使用，例如A和B兩個(gè)進(jìn)程都需要使用打印機(jī)，它們必須互斥使用。如果為了保證結(jié)果的正確性限制A、B二進(jìn)程推進(jìn)序列，規(guī)定進(jìn)程A執(zhí)行好再執(zhí)行進(jìn)程B，這樣的限制就顯得過(guò)死，因?yàn)樗巡荒鼙ＷC進(jìn)程A、B能并發(fā)執(zhí)行，所以必須把限制減少到最少，以盡可能支持并發(fā)執(zhí)行。為此把各進(jìn)程分解，把訪問(wèn)臨界資源的那段代碼（稱(chēng)為臨界區(qū)）與其它段代碼分割開(kāi)來(lái)，只對(duì)各種進(jìn)程進(jìn)入自己的臨界區(qū)加以限制，即各進(jìn)程互斥地進(jìn)入自己的臨界區(qū)

45、。 86進(jìn)程同步的概念臨界區(qū)(critical sections)8臨界區(qū)定義：進(jìn)程訪問(wèn)臨界資源的那段代碼。訪問(wèn)臨界資源的描述：進(jìn)入?yún)^(qū)：檢查有無(wú)進(jìn)程進(jìn)入臨界區(qū)：退出區(qū)：將訪問(wèn)標(biāo)志復(fù)位RepeatEntry sectionCritical sectionExit sectionUntil false87臨界區(qū)定義：進(jìn)程訪問(wèn)臨界資源的那段代碼。89進(jìn)程進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)阻塞隊(duì)列喚醒88進(jìn)程進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)阻塞隊(duì)列喚醒90互斥使用臨界資源當(dāng)進(jìn)程需要使用臨界資源時(shí)，通過(guò)獲得臨界區(qū)的使用權(quán)實(shí)現(xiàn)的。首先，在“進(jìn)入?yún)^(qū)”判斷是否可以進(jìn)入臨界區(qū)，如果可以進(jìn)入，則必須設(shè)置臨界區(qū)使用標(biāo)志，阻止其它后來(lái)的進(jìn)程進(jìn)入臨

46、界區(qū)。后來(lái)的進(jìn)程同過(guò)查看臨界區(qū)使用標(biāo)志，知道自己不能進(jìn)入臨界區(qū)，就進(jìn)入阻塞隊(duì)列，將自己阻塞。89互斥使用臨界資源當(dāng)進(jìn)程需要使用臨界資源時(shí)，通過(guò)獲得臨界區(qū)的使當(dāng)臨界區(qū)內(nèi)的進(jìn)程使用完畢，退出臨界區(qū)時(shí)，即在“退出區(qū)”修改臨界區(qū)使用標(biāo)志，并負(fù)責(zé)喚醒阻塞隊(duì)列中的一個(gè)進(jìn)程，讓其進(jìn)入臨界區(qū)。由于同一個(gè)臨界資源在多個(gè)共享它的進(jìn)程中將對(duì)應(yīng)多個(gè)臨界區(qū)，那么怎樣才能保證諸進(jìn)程間互斥地執(zhí)行臨界區(qū)呢？這就必須保證“臨界區(qū)使用標(biāo)志”是可被系統(tǒng)中所有進(jìn)程共享的全局變量，而且諸進(jìn)程對(duì)該標(biāo)志的修改操作必須互斥進(jìn)行。90當(dāng)臨界區(qū)內(nèi)的進(jìn)程使用完畢，退出臨界區(qū)時(shí)，即在“退出區(qū)”修改臨空閑讓進(jìn)。 當(dāng)無(wú)進(jìn)程進(jìn)入臨界區(qū)時(shí)，相應(yīng)的臨界資源處

47、于空閑狀態(tài)，因而允許一個(gè)請(qǐng) 求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)。忙則等待。 當(dāng)已有進(jìn)程進(jìn)入自己的臨界區(qū)時(shí)，即相應(yīng)的臨界資源正被訪問(wèn)，因而其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證進(jìn)程互斥地訪問(wèn)臨界資源。 臨界區(qū)使用原則也稱(chēng)為互斥條件91空閑讓進(jìn)。臨界區(qū)使用原則也稱(chēng)為互斥條件93有限等待。 對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證進(jìn)程能在有限時(shí)間進(jìn)入臨界區(qū)，以免陷入“饑餓”狀態(tài)。讓權(quán)等待。 當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。臨界區(qū)使用原則也稱(chēng)互斥條件92有限等待。臨界區(qū)使用原則也稱(chēng)互斥條件94（四）進(jìn)程互斥和同步方法軟件方法硬件指令方法信號(hào)量機(jī)制管程等消息傳遞方法93（

48、四）進(jìn)程互斥和同步方法軟件方法95軟件方法是指由進(jìn)程自己，通過(guò)執(zhí)行相應(yīng)的程序指令，實(shí)現(xiàn)與別的進(jìn)程的同步與互斥，無(wú)須專(zhuān)門(mén)的程序設(shè)計(jì)語(yǔ)言或操作系統(tǒng)的支持。實(shí)踐證明，該方法很難正確控制進(jìn)程間的同步與互斥，而且可能會(huì)大大地增加系統(tǒng)的額外開(kāi)銷(xiāo)，94軟件方法是指由進(jìn)程自己，通過(guò)執(zhí)行相應(yīng)的程序指令，實(shí)現(xiàn)與別的進(jìn)硬件方法為了解決軟件方法存在的不足，有人提出了硬件解決方法，通過(guò)屏蔽中斷或采用專(zhuān)門(mén)的機(jī)器指令控制同步與互斥。與軟件解決方法比較，這種方法減少了系統(tǒng)額外開(kāi)銷(xiāo)，但由于需要太強(qiáng)的硬件約束條件，以及可能導(dǎo)致進(jìn)程饑餓與死鎖現(xiàn)象，一直沒(méi)有成為通用的解決方法。95硬件方法為了解決軟件方法存在的不足，有人提出了硬件解

49、決方法，軟件解決方法有很多種，為了說(shuō)明設(shè)計(jì)并發(fā)程序時(shí)可能出現(xiàn)的典型錯(cuò)誤，下面以Dekker算法為例，分析如何設(shè)計(jì)并改進(jìn)一個(gè)互斥算法的過(guò)程96軟件解決方法有很多種，為了說(shuō)明設(shè)計(jì)并發(fā)程序時(shí)可能出現(xiàn)的典型錯(cuò)互斥與同步解決方法之一軟件方法初步設(shè)想為了控制兩個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)，可以讓兩個(gè)進(jìn)程輪流進(jìn)入臨界區(qū)。當(dāng)一個(gè)進(jìn)程正在臨界區(qū)執(zhí)行時(shí)，另一個(gè)進(jìn)程就不能進(jìn)入臨界區(qū)，而在臨界區(qū)外等待。程序?qū)崿F(xiàn)偽代碼如下：97互斥與同步解決方法之一軟件方法初步設(shè)想為了控制兩個(gè)進(jìn)程該算法設(shè)置一個(gè)公用整型變量turn,用于指示被允許進(jìn)入臨界區(qū)的進(jìn)程編號(hào)，即若turn=0,表示允許P0進(jìn)程進(jìn)入臨界區(qū)，若turn=1,表示允許P1進(jìn)

50、程進(jìn)入臨界區(qū)Var turn:0.1;/*共享的全局變量*/ P0While turn0 do nothing;Turn:=1;P1While turn1 do nothing;Turn:=0;98該算法設(shè)置一個(gè)公用整型變量turn,用于指示被允許進(jìn)入臨界區(qū)保證了互斥問(wèn)題1：“忙等”現(xiàn)象問(wèn)題2：進(jìn)程嚴(yán)格交替進(jìn)入臨界區(qū)，如果進(jìn)程需要多次使用臨界區(qū)，那么，使用臨界區(qū)頻率低的進(jìn)程嚴(yán)重制約著使用臨界區(qū)頻率高的進(jìn)程的執(zhí)行速度。違背了”空閑讓進(jìn) ”99保證了互斥101例如P0需要每10分鐘使用一次臨界區(qū)，P1需要每一分鐘使用一次臨界區(qū)假設(shè)trun 的初值為0，進(jìn)程p0正好先請(qǐng)求進(jìn)入臨界區(qū)，并成功進(jìn)入臨界區(qū)

51、執(zhí)行，這時(shí)，如果P1申請(qǐng)進(jìn)入臨界區(qū)，循環(huán)檢測(cè)turn=0,不可以進(jìn)入，只能“空”循環(huán)，等待。當(dāng)P0退出臨界區(qū)時(shí)，修改turn的值為1，P1循環(huán)檢測(cè)到turn=1時(shí)，就可以進(jìn)入臨界區(qū)執(zhí)行，退出臨界區(qū)時(shí)，修改 turn=0100例如P0需要每10分鐘使用一次臨界區(qū)，P1需要每一分鐘使用一例（續(xù)）根據(jù)假設(shè)，P1很快又需要進(jìn)入臨界區(qū)，但是P0卻只能在分鐘之后，按照turn 規(guī)定的順序，進(jìn)入臨界區(qū)執(zhí)行，退出時(shí)修改turn即，P1必須在臨界區(qū)空閑情況下，等待分鐘，才能使用臨界區(qū)，這不符合互斥原則，降低了系統(tǒng)性能。101例（續(xù)）根據(jù)假設(shè)，P1很快又需要進(jìn)入臨界區(qū)，但是P0卻只能在互斥與同步解決方法之一軟件方

52、法第一次改進(jìn)可以為臨界區(qū)設(shè)置一個(gè)狀態(tài)標(biāo)志，標(biāo)明臨界區(qū)是否可用，當(dāng)臨界區(qū)空閑時(shí)，任何一個(gè)進(jìn)程都能進(jìn)入，但此時(shí)必須修改臨界區(qū)標(biāo)志為“被占用”，別的進(jìn)程就不能進(jìn)入臨界區(qū)，當(dāng)臨界區(qū)使用完畢，必須修改該標(biāo)志為“空閑”這樣就不再使諸進(jìn)程嚴(yán)格交替使用臨界區(qū)，算法如下：102互斥與同步解決方法之一軟件方法第一次改進(jìn)可以為臨界區(qū)設(shè)103105分析：第一次改進(jìn)問(wèn)題“忙等”問(wèn)題2不能保證進(jìn)程互斥進(jìn)入臨界區(qū)。問(wèn)題出在檢查、修改有間隔，不能連續(xù)操作。104分析：第一次改進(jìn)問(wèn)題出在檢查、修改有間隔，不能連續(xù)操作。10互斥與同步解決方法之一軟件方法第二次改進(jìn)互斥算法的第一次改進(jìn)不能實(shí)現(xiàn)“互斥”因?yàn)?，進(jìn)程首先檢測(cè)臨界區(qū)狀態(tài)，

53、若“被占用”，則“忙等”，否則就直接進(jìn)入臨界區(qū)，從而，可能出現(xiàn)同時(shí)進(jìn)入臨界區(qū)的現(xiàn)象。能否讓進(jìn)程預(yù)先表明“希望進(jìn)入臨界區(qū)的態(tài)度”，然后，再檢測(cè)臨界區(qū)狀態(tài)，算法如下：105互斥與同步解決方法之一軟件方法第二次改進(jìn)互斥算法的第一106108分析：第二次改進(jìn)假設(shè)P0需要進(jìn)入臨界區(qū)，首先執(zhí)行flag0:=true,再執(zhí)行while flag1,若P1正在占用臨界區(qū)，則P0忙等；否則，P0進(jìn)入臨界區(qū)。但是，如果此時(shí)P1未占用臨界區(qū)，而與P0幾乎同時(shí)需要使用臨界區(qū)，則死鎖107分析：第二次改進(jìn)假設(shè)P0需要進(jìn)入臨界區(qū)，首先執(zhí)行flag0互斥算法的第二次改進(jìn)可能導(dǎo)致死鎖,因?yàn)镻0,P1”堅(jiān)持自己的權(quán)利,執(zhí)意進(jìn)入

54、臨界區(qū),且互不謙讓”.可以考慮,允許進(jìn)程即表明需要進(jìn)入臨界區(qū)的”態(tài)度”,又能互相”謙讓”.即首先表示自己需要使用臨界區(qū),再檢測(cè)臨界區(qū)的狀態(tài),若臨界區(qū)被占用,可以等一小段時(shí)間再申請(qǐng)互斥與同步解決方法之一軟件方法第三次改進(jìn)108互斥算法的第二次改進(jìn)可能導(dǎo)致死鎖,因?yàn)镻0,P1”堅(jiān)持自己的flag1,flag2:boolean;flag1 := false; /* P1不在其臨界區(qū)內(nèi) */flag2 := false; /* P2不在其臨界區(qū)內(nèi) */process P1 beginflag1 := true;while flag2 do begin flag1:=false; isside1:=tr

55、ue; end;臨界區(qū);flag1 := false; end;process P2 beginflag2 := true;while flag1 do begin flag2:=false; isside2:=true; end;臨界區(qū);flag2 := false; end;算法3和算法2類(lèi)似，它們的區(qū)別在于進(jìn)入?yún)^(qū)操作是先修改后檢查。這時(shí)標(biāo)志flagI表示進(jìn)程Pi想進(jìn)入臨界區(qū)，而不再表示進(jìn)程Pi在臨界區(qū)。109flag1,flag2:boolean;process P2flag1,flag2:boolean;flag1 := false; /* P1不在其臨界區(qū)內(nèi) */flag2 := f

56、alse; /* P2不在其臨界區(qū)內(nèi) */process P1 begin(1)flag1 := true;(3)while flag2 do begin (5) flag1:=false; (7) isside1:=true; end;臨界區(qū);flag1 := false; end;算法3和算法2類(lèi)似，它們的區(qū)別在于進(jìn)入?yún)^(qū)操作是先修改后檢查。這時(shí)標(biāo)志flagI表示進(jìn)程Pi想進(jìn)入臨界區(qū)，而不再表示進(jìn)程Pi在臨界區(qū)。process P2 begin(2)flag2 := true;(4)while flag1 do begin (6)flag2:=false; (8)isside2:=true; end;臨界區(qū);flag2 := false; end;110flag1,flag2:boolean;算法3和算法2類(lèi)似，分析-第三次改進(jìn)P0,P1的”謙讓”可能使它們都不能進(jìn)入臨界區(qū).這種現(xiàn)象不是死鎖,因?yàn)檫@種僵局不會(huì)是永久行為,某一時(shí)刻可能會(huì)自動(dòng)解除.但是,這種現(xiàn)象也是不希望出現(xiàn)的.111分析-第三次改進(jìn)P0,P1的”謙讓”可能使它們都不