計算機操作系統(tǒng)

1、計算機操作系統(tǒng)主講教師：曹建秋 賀清碧課程主要內(nèi)容課程主要內(nèi)容操作系統(tǒng)引論（1章）進程管理（2-3章）存儲管理（4章）設(shè)備管理（5章）文件管理（6章）操作系統(tǒng)接口（7章）系統(tǒng)安全性（9章）*分布式操作系統(tǒng)從進程的觀點研究操作系統(tǒng)n把OS看作是由若干個可獨立運行的程序和一個可對這些程序進行協(xié)調(diào)控制的核心（內(nèi)核）組成。這些運行的程序稱為進程，它是資源分配和獨立運行的基本單位，每一進程都完成某一特定任務(wù)，而OS的內(nèi)核則必須要控制和協(xié)調(diào)這些進程的運行，解決進程之間的通信，并從系統(tǒng)可并發(fā)工作為出發(fā)點，實現(xiàn)并發(fā)進程間通信，并解決由此帶來的共享資源的競爭問題。Process Management Proce

2、ss Management 進程管理進程管理-第第2 2章章n進程的基本概念與控制n進程的基本概念n進程控制n線程的基本概念nUNIX中進程的描述與控制n進程同步與通信n進程同步n經(jīng)典進程的同步問題n管程機制n進程通信nUNIX中進程的同步與通信n調(diào)度與死鎖（第3章）本章作業(yè)本章作業(yè)2.1 進程的基本概念n前趨圖n程序順序執(zhí)行n程序并發(fā)執(zhí)行n進程的描述進程的定義、特征進程的狀態(tài)（狀態(tài)、狀態(tài)轉(zhuǎn)換 及掛起狀態(tài)）進程控制塊PCBProcess Management進程管理-processes 進程 返回目錄一、前趨圖的定義3有向無循環(huán)圖,記DAG124567結(jié)點，可表一語句、程序段或進程前趨關(guān)系初始

3、結(jié)點終止結(jié)點前趨關(guān)系： P1 P2 ， P2 P5 ， P5 P7 P1 P3 ， P3 P5 P1 P4 ， P6 P7直接前趨直接后繼Eg1： 以下三條語句的前趨圖為： s1: a:=x+y s2: b:=a-5 s3: c:=b+1 Eg2: S1： a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 s1s2s3s1s2s3s4返回二、程序順序執(zhí)行二、程序順序執(zhí)行n程序執(zhí)行時，必須按照某種先后次序逐個執(zhí)行程序執(zhí)行時，必須按照某種先后次序逐個執(zhí)行nEg s1: a:=x+y s2: b:=a-5 s3: c:=b+1n程序順序執(zhí)行時有如下特征：n順序性n封閉性

4、n可再現(xiàn)性s1s2s3返回三、程序并發(fā)執(zhí)行在處理一批作業(yè)時，有的程序可實現(xiàn)并發(fā)執(zhí)行在處理一批作業(yè)時，有的程序可實現(xiàn)并發(fā)執(zhí)行n n S1： a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6I1I2I3I4C1C2C3C4P1P2P3P4s1s2s3s4三、程序并發(fā)執(zhí)行三、程序并發(fā)執(zhí)行n程序并發(fā)執(zhí)行時的特征n間斷性n失去封閉性n不可再現(xiàn)性n（補充）（補充）程序并發(fā)執(zhí)行的條件（Bernstein)()()()()()(211221 pWpWpWpRpWpR程序并發(fā)執(zhí)行條件例題程序并發(fā)執(zhí)行條件例題nEg S1： a:=x+2 S3: c:=a-b S2: b:=z+4 S

5、4: w:=c+1試?yán)肂ernstein條件證明： （1）s1與s2并發(fā)執(zhí)行；（2） s1與s3,s2與s3,s3與s4不能。解：各語句的讀、寫集分別為： R(S1)=x, W(S1)=a, R(S2)=z, W(S2)=b, R(S3)=a,b, W(S3)=c, R(S4)=c, W(S4)=w, 因為 R(S1) W(S2)=,R(S2) W(S1) = 且W(S1) W(S2) =所以由Bernstein條件，s1與s2并發(fā)執(zhí)行。 同理可證s1與s3,s2與s3,s3與s4不能（略）。 返回一、進程的定義、特征一、進程的定義、特征1、進程進程process的定義的定義 1）進程是程序

6、的一次執(zhí)行。 2）進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。 3）進程是程序在一個數(shù)據(jù)集合上的運行過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。注：進程與程序的主要區(qū)別注：進程與程序的主要區(qū)別Process Management進程管理-processes 進程 進程與程序的主要區(qū)別進程與程序的主要區(qū)別1）程序是指令的有序集合，其本身沒有任何運行的含義，它是一個靜態(tài)靜態(tài)的概念。而進程是程序在處理機上的一次執(zhí)行過程，它是一個動態(tài)動態(tài)概念。2）程序的存在是永久存在是永久的。而進程則是有生命期進程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。3）程序

7、僅是指令的有序集合指令的有序集合。而進程則由程序段、相關(guān)數(shù)據(jù)段程序段、相關(guān)數(shù)據(jù)段進程控制塊（進程控制塊（PCB）組成。4）進程與程序之間不是一一對應(yīng)進程與程序之間不是一一對應(yīng)。進程與程序的主要區(qū)別進程與程序的主要區(qū)別2、進程、進程process的基本特征的基本特征 （1）結(jié)構(gòu)特征結(jié)構(gòu)特征 為了描述和記錄進程的運動變化過程，并使之能正確運行，每個進程都應(yīng)配置了一個進程PCB。所以，從結(jié)構(gòu)上看，每個進程（進程實體）都是由程序段、相關(guān)數(shù)據(jù)段及進程控制塊（程序段、相關(guān)數(shù)據(jù)段及進程控制塊（PCB）組成。注：1.在早期UNIX版本中稱進程的三個組成部分為“進程映像” 2.區(qū)別進程實體和進程 （2）動態(tài)性動

8、態(tài)性 進程的實質(zhì)是程序在處理機上的一次執(zhí)行過程程序在處理機上的一次執(zhí)行過程，因此是動態(tài)性的。所以動態(tài)性是進程的最基本的特征。同時動態(tài)性還表現(xiàn)在 進程則是有生命期進程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。Process Management進程管理-processes 進程 一、進程的定義、特征一、進程的定義、特征（3）并發(fā)性并發(fā)性 指多個進程實體同時存在于內(nèi)存中，能在一段時間內(nèi)同時運行。 引入進程的目的就是為了使進程能并發(fā)執(zhí)行，以提高資源利用率，所以并發(fā)性是進程的重要特征，也是OS的重要特征。（4）獨立性獨立性 指進程是一個能獨立運行的基本單位，也是系

9、統(tǒng)進行資源分配和調(diào)度的獨立單位。（5）異步性異步性 指進程以各自獨立的、不可預(yù)知的速度向前推進。返回二、二、 進程狀態(tài)進程狀態(tài) 為了刻畫了整個進程，可以將一個進程的生命周期劃分為一組狀態(tài)：1、進程的5種狀態(tài)（三種基本狀態(tài)三種基本狀態(tài)）nnew新建/創(chuàng)建:進程正在創(chuàng)建中的狀態(tài)nready就緒就緒: 進程已獲得了除處理機以外的所有資源，等待分配處理機執(zhí)行的等待狀態(tài)。nrunning運行/執(zhí)行執(zhí)行: 當(dāng)一個進程獲得必要的資源并正在處理機上執(zhí)行的狀態(tài)。nwaiting等待/阻塞阻塞: 正在執(zhí)行的進程由于發(fā)生某事件而暫時無法執(zhí)行下去，此時進程所處的狀態(tài)。nterminated終止/撤消/退出：進程執(zhí)行完

10、畢，釋放所占資源的狀態(tài)。Process Management進程管理-processes 進程 進程在運行期間并非固定處于某個狀態(tài)，而是不斷從一個狀態(tài)轉(zhuǎn)換到另一個狀態(tài)。n2 2、進程狀態(tài)轉(zhuǎn)換、進程狀態(tài)轉(zhuǎn)換3 3、進程的掛起狀態(tài)、進程的掛起狀態(tài) 在某些系統(tǒng)中，為了更好地管理和調(diào)度進程，引入了掛起狀態(tài)：n掛起狀態(tài)掛起狀態(tài)/靜止?fàn)顟B(tài)：靜止?fàn)顟B(tài)： 程序在運行期間，由于某種需要，往往要將進程程序在運行期間，由于某種需要，往往要將進程暫停執(zhí)行，使其靜止下來，以滿足其需要。這種靜止?fàn)顣和?zhí)行，使其靜止下來，以滿足其需要。這種靜止?fàn)顟B(tài)就稱為進程的掛起狀態(tài)。態(tài)就稱為進程的掛起狀態(tài)。引起掛起狀態(tài)的原因引起掛起狀態(tài)

11、的原因 終端用戶的需要終端用戶的需要：終端用戶在自己程序運行中發(fā)現(xiàn)問題要求使正在 執(zhí)行的進程暫停執(zhí)行而使進程處于掛起狀態(tài)。父進程的需要：父進程的需要：父進程為了考查和修改某個子進程，或者協(xié)調(diào)各子進 程間的活動，需要將該子進程掛起。操作系統(tǒng)的需要：操作系統(tǒng)的需要：操作系統(tǒng)為了檢查運行中的資源使用情況或進行記 帳，而將某些進程掛起。對換的需要：對換的需要：為了提高內(nèi)存的利用率，而將內(nèi)存中某些進程掛起，以 調(diào)進其它程序運行。負荷調(diào)節(jié)的需要：負荷調(diào)節(jié)的需要：由于工作負荷較重，而將一些不重要的進程掛起， 以保證系統(tǒng)能正常運行（實時操作系統(tǒng)） 返回控制進程的掛起與激活具有掛起狀態(tài)的進程狀態(tài)具有掛起狀態(tài)的進

12、程狀態(tài) 在引入掛起狀態(tài)后，就增加了掛起狀態(tài)（靜止?fàn)顟B(tài)）與非掛起狀態(tài)（活動狀態(tài)）間的轉(zhuǎn)換，如圖所示：活動就緒掛起就緒活動阻塞掛起阻塞執(zhí)行進程調(diào)度時間片用完掛起激活掛起掛起事件發(fā)生事件發(fā)生等待事件激活返回三、進程控制塊三、進程控制塊Process Control Block (PCB)Process Control Block (PCB)進程控制塊進程控制塊PCBPCB 是操作系統(tǒng)為了管理和控制進程的運行而為每一個進程定義的一個數(shù)據(jù)結(jié)構(gòu)，它記錄了系統(tǒng)管理進程所需的全部信息。系統(tǒng)根據(jù)PCB而感知進程的存在，PCB是進程存在的唯一標(biāo)志。1 1、進程控制塊、進程控制塊PCBPCB的作用的作用是OS對并發(fā)

13、執(zhí)行的進程進行控制和管理的根據(jù)。也是系統(tǒng)用來感知進程存在的根據(jù)，即PCB是進程存在的唯一標(biāo)志。Process Management進程管理-processes 進程 1、進程控制塊PCB的作用2、進程控制塊PCB中的信息3、進程控制塊PCB的組織方式2 2、進程控制塊、進程控制塊PCBPCB中的信息中的信息 根據(jù)操作系統(tǒng)的要求不同，PCB所包含信息有些不同，但通常包含以下信息：進程標(biāo)志符進程標(biāo)志符：由系統(tǒng)創(chuàng)建進程時分配給進程的唯一標(biāo)識號，通常為一整數(shù)，稱為進程號，用于區(qū)分不同的進程。其所屬用戶通常也為一整數(shù)，稱為用戶號。處理機狀態(tài)（斷點信息）處理機狀態(tài)（斷點信息）：即處理機中各種寄存器（通用寄

14、存器、PC、PSW等）的內(nèi)容進程調(diào)度進程調(diào)度：記錄了進程調(diào)度的相關(guān)信息（狀態(tài)、優(yōu)先級、事件等）。進程控制進程控制：記錄了系統(tǒng)對進程控制的信息（程序和數(shù)據(jù)的地址、同步機制、資源清單、鏈接指針）Process Management進程管理-processes 進程 3 3、進程控制塊、進程控制塊PCBPCB的組織方式的組織方式 在一個系統(tǒng)中，通常存在著許多進程，它們所處的狀態(tài)不同，為了方便進程的調(diào)度和管理，需要將各進程的PCB用適當(dāng)方法組織起來。目前常用的組織方式有：鏈接方式鏈接方式 圖示 把同一狀態(tài)的PCB鏈接成一個隊列，這樣就形成了就緒隊列、阻塞隊列等。索引方式索引方式 圖示 將同一狀態(tài)的進程

15、組織在一個索引表中，索引表的表項指向相應(yīng)的PCB ，不同狀態(tài)對應(yīng)不同的索引表。 Process Management進程管理-processes 進程 返回1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針按鏈接方式組織PCB按索引方式組織PCB1PCB90PCB89PCB77PCB6 PCB58PCB40PCB33PCB24PCB1執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索引表2.3 2.3 進程的控制進程的控制 進程控制是進程管理中最基本的功能，即對系統(tǒng)中所有的進程實施有效的管理，其功能包括進程的創(chuàng)建、撤

16、消、阻塞與喚醒等，這些功能一般是由操作系統(tǒng)的內(nèi)核來完成。補充：補充：OS OS 內(nèi)核：內(nèi)核：在現(xiàn)代OS中，常把一些功能模塊（與硬件緊密相關(guān)的、常用設(shè)備的驅(qū)動程序及運行頻率較高的）放在緊靠硬件的軟件層次中，加以特殊保護，同時把它們常駐內(nèi)存，以提高OS的運行效率，這部分功能模塊就稱OS的內(nèi)核。內(nèi)核是基于硬件的第一層軟件擴充，它為系統(tǒng)控制和管理進程提供了良好的環(huán)境。Process Management進程管理-processes 進程 補充：處理機的執(zhí)行狀態(tài)處理機的執(zhí)行狀態(tài) 為防止OS及其關(guān)鍵數(shù)據(jù)（如PCB等)不被用戶有意或無意破壞,通常將處理機的執(zhí)行狀態(tài)分為兩種Process Management

17、進程管理-processes 進程 一、進程創(chuàng)建一、進程創(chuàng)建 一個進程可以創(chuàng)建若干個新進程，新創(chuàng)建的進程又可以創(chuàng)建子進程，為了描述進程之間的創(chuàng)建關(guān)系，引入了進程圖（如下圖所示：） 1 1、進程圖、進程圖：又稱為進程樹或進程家族樹，是描述進程家族關(guān)系的一棵有向樹。Process Management進程管理-processes 進程 ABDECF父進程祖先進程子進程2 2、引起進程創(chuàng)建的事件、引起進程創(chuàng)建的事件 在多道程序環(huán)境中，只有進程才可以在系統(tǒng)中運行。為了使一個程序能運行，必須為它創(chuàng)建進程。導(dǎo)致進程創(chuàng)建的事件有： 用戶登錄：用戶登錄：在分時OS中，用戶在終端鍵入登錄命令后，如是合法用戶，則

18、系統(tǒng)為該終端創(chuàng)建一進程，并插入就緒隊列。 作業(yè)調(diào)度作業(yè)調(diào)度：在批處理OS中，當(dāng)按某算法調(diào)度一作業(yè)進內(nèi)存，系統(tǒng)為之分配必要資源，同時為該作業(yè)創(chuàng)建一進程，并插入就緒隊列。 提供服務(wù)：提供服務(wù)：在程序運行中，若用戶需某種服務(wù)，則系統(tǒng)創(chuàng)建一進程為用戶提供服務(wù)，并插入就緒隊列。 應(yīng)用請求應(yīng)用請求：在運行中，由于應(yīng)用進程本身的需求，自己創(chuàng)建一進程，并插入就緒隊列。3 3、進程的創(chuàng)建進程的創(chuàng)建 操作系統(tǒng)一旦發(fā)現(xiàn)了要求創(chuàng)建進程的事件后，便調(diào)用進程創(chuàng)建原語create()按以下過程創(chuàng)建一新進程：申請一個空閑的申請一個空閑的PCBPCB為新進程分配資源為新進程分配資源對對PCBPCB初始化初始化將將PCBPCB插

19、入就緒隊列插入就緒隊列返回一個進程標(biāo)識號返回一個進程標(biāo)識號 一個進程在完成其任務(wù)后，應(yīng)加以撤消，以便及時釋放其占有的各類資源。1 1、導(dǎo)致進程撤消的事件、導(dǎo)致進程撤消的事件u進程正常結(jié)束進程正常結(jié)束u進程異常結(jié)束進程異常結(jié)束u外界干預(yù)外界干預(yù) 如果系統(tǒng)中發(fā)生了要求撤消進程的事件，OS便調(diào)用撤消原語去撤消進程。2 2、撤消原語可采用、撤消原語可采用2 2種撤消策略：種撤消策略：u只撤消指定的進程只撤消指定的進程u撤消指定進程及其所有的子孫進程撤消指定進程及其所有的子孫進程 二、二、進程的撤消進程的撤消Process Management進程管理-processes 進程 3 3、進程撤消的過程、

20、進程撤消的過程Process Management進程管理-processes 進程 在運行？在運行？NYNY由標(biāo)識符在由標(biāo)識符在PCBPCB集中找集中找PCBPCB并讀狀態(tài)并讀狀態(tài)歸還占有資源歸還占有資源從所在隊列從所在隊列( (索引表索引表) )撤消撤消PCBPCB中止運行重置調(diào)度標(biāo)志中止運行重置調(diào)度標(biāo)志終止所有子孫進程終止所有子孫進程有子孫進程？有子孫進程？ 當(dāng)一個進程期待的事件尙未出現(xiàn)時，該進程調(diào)用阻塞原語block()（功能：將進程由執(zhí)行狀態(tài)轉(zhuǎn)為阻塞狀態(tài)）將自己阻塞起來。對于處于阻塞狀態(tài)的進程，當(dāng)該進程期待的事件出現(xiàn)時，由其它相關(guān)進程調(diào)用喚醒原語wakeup()（功能：將進程由阻塞狀

21、態(tài)變?yōu)榫途w狀態(tài)）將阻塞的進程喚醒，使其進入就緒狀態(tài)。1、引起進程阻塞和喚醒的事件、引起進程阻塞和喚醒的事件請求系統(tǒng)服務(wù)請求系統(tǒng)服務(wù)啟動某種操作啟動某種操作新數(shù)據(jù)尚未到達新數(shù)據(jù)尚未到達無新工作可做無新工作可做三、進程的阻塞與喚醒三、進程的阻塞與喚醒Process Management進程管理-processes 進程 停止執(zhí)行停止執(zhí)行修改修改PCBPCB中的狀態(tài)中的狀態(tài)（執(zhí)行（執(zhí)行- -阻塞）阻塞）插入到相應(yīng)的阻塞隊列插入到相應(yīng)的阻塞隊列另調(diào)度一就緒進程，切換另調(diào)度一就緒進程，切換CPUCPU（保留阻塞進程的（保留阻塞進程的CPUCPU狀態(tài)）狀態(tài)）將阻塞進程移出阻塞隊列將阻塞進程移出阻塞隊列插入

22、到就緒隊列插入到就緒隊列另調(diào)度一就緒進程，切換另調(diào)度一就緒進程，切換CPUCPU（保留阻塞進程的（保留阻塞進程的CPUCPU狀態(tài)）狀態(tài)）修改修改PCBPCB中的狀態(tài)中的狀態(tài)（阻塞（阻塞- -就緒）就緒）2、進程的阻塞過程、進程的阻塞過程3、進程的喚醒過程、進程的喚醒過程 當(dāng)引起進程掛起的事件發(fā)生時，系統(tǒng)就將利用掛起原語suspend()將指定進程或處于阻塞狀態(tài)的進程掛起。當(dāng)發(fā)生激活進程的事件時，系統(tǒng)就將利用激活原語active()將指定進程激活。1、引起進程的掛起與激活的事件引起進程的掛起與激活的事件四、進程的掛起與激活四、進程的掛起與激活Process Management進程管理-proc

23、esses 進程 2、進程的掛起過程、進程的掛起過程檢查該進程狀態(tài)檢查該進程狀態(tài)修改修改PCBPCB中的狀態(tài)中的狀態(tài)* *（活動（活動- -靜止）靜止）復(fù)制復(fù)制PCBPCB至指定內(nèi)存區(qū)域至指定內(nèi)存區(qū)域運行？運行？另調(diào)度另調(diào)度一就緒進程一就緒進程3、進程的激活過程、進程的激活過程NY將掛起進程從外存調(diào)入內(nèi)存將掛起進程從外存調(diào)入內(nèi)存決定是否需重新調(diào)度決定是否需重新調(diào)度修改修改PCBPCB中的狀態(tài)中的狀態(tài)* *（靜止（靜止- -活動）活動）活動就緒？活動就緒？返回目錄* *2.7 2.7 線程線程 線程是近年來操作系統(tǒng)領(lǐng)域出現(xiàn)的一個非常重要的技術(shù)，其引入進一步提高了程序并發(fā)執(zhí)行的程度，從而進一步提高

24、了資源的利用率和系統(tǒng)的吞吐量。 線程的基本概念 線程間的同步和通信 內(nèi)核支持線程和用戶級線程 線程控制Process Management進程管理-processes 進程 一、線程的基本概念一、線程的基本概念進程間CPU的切換/上下文切換Process Management進程管理-processes 進程 Process Management進程管理-threads 線程 二、線程的分類二、線程的分類三、三、Solaris OS 中的線程中的線程qSolaris 2：是UNIX的一種版本,92年以前僅支持傳統(tǒng)的單線程的重型進程,現(xiàn)在已發(fā)展為可支持用戶級、內(nèi)核/核心級線程,對稱多處理器和實時

25、調(diào)度的OS。用戶級線程用戶級線程輕型進程輕型進程內(nèi)核級線程內(nèi)核級線程進程進程內(nèi)核內(nèi)核返回目錄* *2.8 UNIX2.8 UNIX中進程的描述與控制中進程的描述與控制P323P323n進程的描述進程的描述n進程的數(shù)據(jù)結(jié)構(gòu)進程的數(shù)據(jù)結(jié)構(gòu)n進程的狀態(tài)及其轉(zhuǎn)換進程的狀態(tài)及其轉(zhuǎn)換n進程映像進程映像進程的數(shù)據(jù)結(jié)構(gòu)進程的數(shù)據(jù)結(jié)構(gòu) UNIX系統(tǒng)V中，一個進程由程序區(qū)、數(shù)據(jù)區(qū)、棧區(qū)、共享存儲區(qū)等若干區(qū)組成，同時設(shè)置PCB，PCB分為以下四部分：n進程表進程表：記錄了進程的狀態(tài)及有關(guān)控制信息等。nU U區(qū)：區(qū)：存放進程表項的一些擴充信息n進程區(qū)表進程區(qū)表：記錄了進程每個區(qū)的起始虛地址及指向系統(tǒng)區(qū)表中對應(yīng)區(qū)表項的

26、指針。n系統(tǒng)區(qū)表：系統(tǒng)區(qū)表：記錄了各區(qū)的類型、狀態(tài)及在物理存儲器中的地址信息等，以實現(xiàn)對區(qū)的管理。U區(qū)進程表a b c本進程區(qū)表系統(tǒng)區(qū)表abc進程的數(shù)據(jù)結(jié)構(gòu)進程的狀態(tài)及轉(zhuǎn)換進程的狀態(tài)及轉(zhuǎn)換 UNIX系統(tǒng)中，進程的狀態(tài)(9種)及轉(zhuǎn)換如圖圖10-410-4所示所示。n進程的九種狀態(tài)進程的九種狀態(tài)n核心態(tài)執(zhí)行核心態(tài)執(zhí)行n用戶態(tài)執(zhí)行用戶態(tài)執(zhí)行n內(nèi)存中就緒內(nèi)存中就緒n被剝奪狀態(tài)被剝奪狀態(tài)n就緒且換出就緒且換出n內(nèi)存中睡眠內(nèi)存中睡眠n睡眠且換出睡眠且換出n創(chuàng)建狀態(tài)創(chuàng)建狀態(tài)n僵死狀態(tài)僵死狀態(tài)85系統(tǒng)調(diào)用中斷返回用戶態(tài)執(zhí)行返回用戶態(tài)4962137搶占核心態(tài)執(zhí)行僵死睡眠內(nèi)存中睡眠睡眠且換出換出喚醒內(nèi)存中就緒調(diào)度

27、換出 換入喚醒就緒且換出內(nèi)存不足內(nèi)存足創(chuàng)建fork被搶占進程的映像進程的映像 UNIX系統(tǒng)中，進程是進程映像的執(zhí)行過程，進程映像由三部分組成:n用戶級上、下文用戶級上、下文 主要是用戶程序，在系統(tǒng)中分為正文區(qū)、數(shù)據(jù)區(qū)、棧區(qū)和主要是用戶程序，在系統(tǒng)中分為正文區(qū)、數(shù)據(jù)區(qū)、棧區(qū)和共享數(shù)據(jù)區(qū)。共享數(shù)據(jù)區(qū)。n寄存器上、下文寄存器上、下文 由由CPUCPU中一些寄存器的內(nèi)容所構(gòu)成。中一些寄存器的內(nèi)容所構(gòu)成。n系統(tǒng)級上、下文系統(tǒng)級上、下文 分靜態(tài)（只有一個，大小不變）和動態(tài)兩部分（大小可分靜態(tài)（只有一個，大小不變）和動態(tài)兩部分（大小可變）。變）。進程的控制進程的控制系統(tǒng)調(diào)用系統(tǒng)調(diào)用 unix系統(tǒng)向用戶提供了

28、一組系統(tǒng)調(diào)用，用戶可利用這些系統(tǒng)調(diào)用來實現(xiàn)對進程的控制。nfork()fork()創(chuàng)建一新進程（創(chuàng)建一新進程（0 0進程由系統(tǒng)引導(dǎo)時建）進程由系統(tǒng)引導(dǎo)時建）nExec()Exec()改變進程的原有代碼改變進程的原有代碼nExit()Exit()實現(xiàn)進程的自我終止實現(xiàn)進程的自我終止nWait()Wait()掛起進程，等待子進程終止掛起進程，等待子進程終止nGetpid()Getpid()獲取進程標(biāo)識符獲取進程標(biāo)識符nNice()Nice()改變進程的優(yōu)先級改變進程的優(yōu)先級返回目錄 2.3 2.3 進程同步進程同步n進程同步進程同步是指對多個相關(guān)進程在執(zhí)行次序上進行協(xié)調(diào)，它的目的是使系統(tǒng)中諸進程之

29、間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性；或系統(tǒng)中諸進程之間在邏輯上的相互制約的關(guān)系（直接的-同步；間接的互斥）。n用來實現(xiàn)同步的機制稱為同步機制。如：信號量機制；管程機制。 2.3 2.3 進程同步進程同步進程同步的基本概念進程同步的基本概念 兩種形式的制約關(guān)系兩種形式的制約關(guān)系 臨界資源、臨界區(qū)臨界資源、臨界區(qū) 同步機制應(yīng)遵循的規(guī)則同步機制應(yīng)遵循的規(guī)則信號量機制信號量機制 整型信號量整型信號量 記錄型信號量記錄型信號量 ANDAND型信號量集、一般信號量集型信號量集、一般信號量集信號量的應(yīng)用信號量的應(yīng)用 信號量實現(xiàn)進程互斥信號量實現(xiàn)進程互斥 信號量描述進程間的前趨關(guān)系信號

30、量描述進程間的前趨關(guān)系返回目錄一、進程同步的基本概念一、進程同步的基本概念1 1、兩種形式的制約關(guān)系、兩種形式的制約關(guān)系系統(tǒng)中諸進程之間在邏輯上存在著兩種制約關(guān)系：n直接制約關(guān)系（進程同步）直接制約關(guān)系（進程同步）：即為完成同一個任務(wù)的諸進程間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。 n間接制約關(guān)系（進程互斥）間接制約關(guān)系（進程互斥） ：是進程共享獨占型資源而必須互斥執(zhí)行的間接制約關(guān)系。n同步與互斥比較同步與互斥比較2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)n一次只允許一個進程使用的資源稱為臨界資源一次只允許一個進程使用的資源稱為臨界資源，如打印機，繪圖機；變量，數(shù)

31、據(jù)等，諸進程間采取互斥方式式實現(xiàn)對這種臨界資源的共享，從而實現(xiàn)并行程序的封閉性。例例：有兩個進程A和B，它們共享一個變量x，且兩個進程按以下方式對變量X進行訪問和修改: 其中R1和R2為處理機中的兩個寄存器。A與B均對X+1，即X+2。若按另一順序?qū)ψ兞窟M行修改：結(jié)果x只加了1.A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B: R2=R2+1; X=R2;A: R1=X; R1=R1+1; X=R1;B: R2=X; R2=R2+1; X=R2;（1 1）變量）變量X X必必需按臨界資源需按臨界資源處理。處理。（2 2）每個進程）每個進程中訪問臨界資中訪問臨界資源的那段代

32、碼源的那段代碼稱為臨界區(qū)稱為臨界區(qū)2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū) 為了保證臨界資源的正確使用，可以把臨界資源的訪問過程臨界資源的訪問過程分成以下幾部分： 進入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)v進入?yún)^(qū)增加在臨界區(qū)前面的一段代碼，用于檢查欲訪問的臨界資源此刻是否被訪問。v退出區(qū)增加在臨界區(qū)后面的一段代碼，用于將臨界資源的訪問標(biāo)志恢復(fù)為未被訪問標(biāo)志。v剩余區(qū)進程中除了進入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其余代碼。2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū) 要進入臨界區(qū)的若干進程必須滿足要進入臨界區(qū)的若干進程必須滿足：（1）一次只允許一個進程進入臨界區(qū)（2）任何時候，處于臨界區(qū)的進程不得多于一個（3）進入臨界

33、區(qū)的進程要在有限的時間內(nèi)退出（4）如果不能進入自己的臨界區(qū)，則應(yīng)讓出處理機資源解決臨界區(qū)（互斥）問題的幾類方法：解決臨界區(qū)（互斥）問題的幾類方法：（1）軟件方法（2）硬件方法（3）P-V操作進入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)同步機制3 3、同步機制應(yīng)遵循的規(guī)則、同步機制應(yīng)遵循的規(guī)則q 有空讓進有空讓進( (空閑讓進）空閑讓進）: :當(dāng)無進程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進入臨界區(qū)的進程立即進入自己的臨界區(qū)，以有效地利用臨界資源。q 互斥（忙則等待）互斥（忙則等待）: :當(dāng)已有進程進入臨界區(qū)時，表明臨界資源正在被訪問，因而其他試圖進入臨界區(qū)的進程必須等待，以保證對臨界資源的互斥訪問

34、q 有限等待有限等待: :對要求訪問臨界資源的進程，應(yīng)保證在有限時間內(nèi)能進入自己的臨界區(qū)，以免陷入“死等”狀態(tài).q 讓權(quán)等待讓權(quán)等待: :當(dāng)進程不能進入自己的臨界區(qū)時，應(yīng)立即釋放處理機，以免進程陷入“忙等”。返回二、信號量機制解決臨界區(qū)（互斥）問題的幾類方法解決臨界區(qū)（互斥）問題的幾類方法n* *軟件方法軟件方法RepeatRepeat flagi:=true;turn:=j;flagi:=true;turn:=j; while(flagi and turn=j) while(flagi and turn=j) do no_op; do no_op; critical section crit

35、ical section flagi:=false;flagi:=false; remainder section remainder sectionUntil falseUntil false遵循遵循“忙則等待忙則等待”；“有空讓進有空讓進”，但難但難度和局限性較大。度和局限性較大。u硬件方法硬件方法 用硬件方法來解決臨界區(qū)問題，用硬件方法來解決臨界區(qū)問題，即定義一些特殊指令，如即定義一些特殊指令，如TEST TEST 、SETSET、SWAPSWAP等指令，有效地實現(xiàn)了等指令，有效地實現(xiàn)了進程互斥，但不滿足進程互斥，但不滿足“讓權(quán)等待讓權(quán)等待”。有效解決同步問題的方法有效解決同步問題的方法

36、信號機制信號機制為臨界資源加鎖的方法二、信號量機制n信號量機制是荷蘭科學(xué)家E.W.Dijkstra在1965年提出的一種同步機制，也稱為P、V操作。由最初的整型信號量發(fā)展為記錄型信號量，進而發(fā)展為信號量集。n整型信號量整型信號量n記錄型信號量記錄型信號量n信號量集（信號量集（AND信號量集、一般信號量集）信號量集、一般信號量集）1 1、整型信號量、整型信號量n整型信號量整型信號量非負整數(shù)，除了初始化外，只能通過兩個原子操作waitwait和signalsignal（P P，V V）來訪問。nwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： whil

37、e Swhile S 0 do no-op0 do no-op 測試有無可用資源 S:=S-1; S:=S-1; 可用資源數(shù)減一個單位 signal(S): S:=S+1;signal(S): S:=S+1; 主要問題主要問題：只要S S 0 0， waitwait操作就不斷地測試（盲等），因而，未做到“讓權(quán)等待”。 2 2、記錄型信號量、記錄型信號量n基本思想基本思想 1、設(shè)置一個代表資源數(shù)目的整型變量valuevalue（資源信號量） 2、設(shè)置一鏈表L L用于鏈接所有等待的進程記錄型信號量的數(shù)據(jù)結(jié)構(gòu)記錄型信號量的數(shù)據(jù)結(jié)構(gòu) Type semaphore=record value:intege

38、r; L: list of process; endwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： S.value:=S.value-1; S.value:=S.value-1; if S.value0 then block(S.L);if S.value0），一群生產(chǎn)者進程），一群生產(chǎn)者進程p1,p2,，pm，一群消費者進程，一群消費者進程c1,c2,，cm，如圖所示。假定生產(chǎn)者和消費，如圖所示。假定生產(chǎn)者和消費者是相互等效，只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，者是相互等效，只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩

39、沖區(qū)未空，消費者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。類似地，只要緩沖區(qū)未空，消費者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。生產(chǎn)者和消費者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也生產(chǎn)者和消費者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也禁止消費者從空的緩沖區(qū)提取產(chǎn)品。禁止消費者從空的緩沖區(qū)提取產(chǎn)品。 P1P2pmc1c2cmn設(shè)置兩個同步信號量及一互斥信號量設(shè)置兩個同步信號量及一互斥信號量empty：說明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的大小說明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的大小n n。Full： 說明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為說明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為0

40、.0.Mutex: 說明該有界緩沖區(qū)是一臨界資源，必須互斥使用，說明該有界緩沖區(qū)是一臨界資源，必須互斥使用， 其初值為其初值為1 1。 “ “生產(chǎn)者生產(chǎn)者消費者消費者”問題的解決問題的解決n“生產(chǎn)者生產(chǎn)者消費者消費者”問題的同步算法描述問題的同步算法描述 semaphore full=0; /*表示滿緩沖區(qū)的數(shù)目表示滿緩沖區(qū)的數(shù)目*/ semaphore empty=n; /*表示空緩沖區(qū)的數(shù)目表示空緩沖區(qū)的數(shù)目*/ semaphore mutex=1; /*表示對緩沖區(qū)進程操作的互斥信號量表示對緩沖區(qū)進程操作的互斥信號量*/Main() cobegin producer(); consume

41、r(); coend “ “生產(chǎn)者生產(chǎn)者消費者消費者”問題的解決問題的解決 while(true) while(true) 生產(chǎn)一個產(chǎn)品生產(chǎn)一個產(chǎn)品; ; p(empty); p(empty); P(mutex); P(mutex); 將一個產(chǎn)品送入緩沖區(qū)；將一個產(chǎn)品送入緩沖區(qū)； V(mutex);V(mutex); V(full); V(full); Producer() while(true) while(true) p(full); p(full); P(mutex); P(mutex); 從緩沖區(qū)取走一個產(chǎn)品從緩沖區(qū)取走一個產(chǎn)品; ; V(mutex); V(mutex); V(emp

42、ty); V(empty); 消費一個產(chǎn)品；消費一個產(chǎn)品； consumer()“生產(chǎn)者生產(chǎn)者- -消費者消費者”問題中應(yīng)注意問題中應(yīng)注意1. 互斥信號量的P,V操作在每一程序中必須成對出現(xiàn).2. 資源信號量(full,empty)也必須成對出現(xiàn),但可分別處于不同的程序中.3. 多個P操作順序不能顛倒.4. 先執(zhí)行資源信號量的P操作,再執(zhí)行互斥信號量的P操作,否則可能引起進程死鎖.5. 它是一個同步問題： （1）消費者想要取產(chǎn)品，有界緩沖區(qū)中至少有一個單元是滿的。 （2）生產(chǎn)者想要放產(chǎn)品，有界緩沖區(qū)中至少有一個是空的。6. 它是一互斥問題 有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進程和各消費者進程

43、必須互斥執(zhí)行。返回2 2、“哲學(xué)家進餐哲學(xué)家進餐”問題問題n問題描述：問題描述： 有五個哲學(xué)家，他們的生活方式是交替地進行思考和進餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個碗和五支筷子，平時一個哲學(xué)家進行思考，饑餓時便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時才能進餐。進餐畢，放下筷子又繼續(xù)思考。n哲學(xué)家進餐問題可看作是并發(fā)進程并發(fā)執(zhí)行時，處理共享資源的一個有代表性的問題。n semaphore stick5=1,1,1,1,1; /*分別表示分別表示5支筷子支筷子*/ Main() cobegin philosopher(0); philosopher(1); ph

44、ilosopher(2); philosopher(3); philosopher(4); coend 哲學(xué)家進餐問題的解決哲學(xué)家進餐問題的解決 while(true) while(true) 思考思考; ; p(sticki); p(sticki); P(stick(i+1)%5); P(stick(i+1)%5); 進餐；進餐； V(sticki);V(sticki); V(stick(i+1)%5); V(stick(i+1)%5); 第第i個哲學(xué)家的活動算法個哲學(xué)家的活動算法philosopher(int i)返回說明：說明：1、此算法可以保證不會有相保證不會有相鄰的兩位哲學(xué)家同時進餐

45、鄰的兩位哲學(xué)家同時進餐。2、若五位哲學(xué)家同時饑餓而各自拿起了左邊的筷子，這使五個信號量stick均為0，當(dāng)他們試圖去拿起右邊的筷子時，都將因無筷子而無限期地等待下去，即可能會引起死鎖可能會引起死鎖。3 3、“讀者讀者寫者寫者”問題問題n問題描述：問題描述： 一個數(shù)據(jù)對象（數(shù)據(jù)文件或記錄）可被多個進程共享。其中，reader進程要求讀，writer 進程要求寫或修改。允許多個reader進程同時讀共享數(shù)據(jù)，但絕不允許一個writer進程與其它的reader進程或writer進程同時訪問，即writer進程必須與其它進程互斥訪問共享對象。n“讀者讀者寫者寫者”問題的同步算法描述問題的同步算法描述

46、設(shè)置一個共享變量和兩個信號量：設(shè)置一個共享變量和兩個信號量：共享變量Readcount：記錄當(dāng)前正在讀數(shù)據(jù)集的讀進程數(shù)目， 初值為0。讀互斥信號量Rmutex ：表示讀進程互斥地訪問共享變量 readcount，初值為1.寫互斥信號量wmutex：表示寫進程與其它進程（讀、寫） 互斥地訪問數(shù)據(jù)集，初值為1. “ “讀者讀者寫者寫者”問題的解決問題的解決n“讀者讀者寫者寫者”問題的同步算法描述問題的同步算法描述 semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main() cobegin reader(); writer(); c

47、oend “ “讀者讀者寫者寫者”問題的解決問題的解決 while(true) while(true) p(rmutex); p(rmutex); if(readcount= =0) p(wmutex); if(readcount= =0) p(wmutex);/ /* *第一位讀者阻止寫者第一位讀者阻止寫者* */ / readcount+; readcount+; V(rmutex); V(rmutex); 讀數(shù)據(jù)集；讀數(shù)據(jù)集； p(rmutex); p(rmutex); readcount-; readcount-; if(readcount= =0) v(wmutex); if(rea

48、dcount= =0) v(wmutex);/ /* *第末位讀者允許寫者進第末位讀者允許寫者進* */ / V(rmutex); V(rmutex); reader()修改修改readcount修改修改readcount while(true) p(wmutex); /*阻止其它進程（讀、寫）進阻止其它進程（讀、寫）進/ 寫數(shù)據(jù)集；寫數(shù)據(jù)集； V(wmutex); /*允許其它進程（讀、寫）進允許其它進程（讀、寫）進/writer()返回2.5 管程機制n信號量機制實現(xiàn)進程同步的問題信號量機制實現(xiàn)進程同步的問題 用信號量機制實現(xiàn)進程間的同步和互斥，即方便又有效。但存在以下兩個問題：v 每個訪

49、問臨界資源每個訪問臨界資源的進程都必須自備同步操作（的進程都必須自備同步操作（P P、V V操作）操作），這使大量的同步操作分散在各個進程中，給系統(tǒng)的管理帶來麻煩。給系統(tǒng)的管理帶來麻煩。v會因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖會因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖。n解決方法解決方法-管程（管程（Monitors)Monitors) Dijkstra于1971年提出，為每個共享資源設(shè)立一個“秘書”來管理對它的訪問。一切來訪者都要通過秘書，而秘書每次僅允許一個來訪者（進程）來訪問共享資源。這樣既便于系統(tǒng)管理共享資源，又能保證進程的互斥訪問和同步。1973年，Hanson和Hoare又把“秘書”概念發(fā)展為

50、管程概念。 一、管程的基本概念基本思想基本思想 把訪問某種臨界資源的所有進程的同步操作都集中起來，構(gòu)成一個所謂的“秘書秘書”進程（管程）進程（管程），凡是訪問臨界資源的進程，都需要報告 “秘書”，由秘書來實現(xiàn)諸進程的同步。管程的定義管程的定義 一個數(shù)據(jù)結(jié)構(gòu)一個數(shù)據(jù)結(jié)構(gòu)和在該數(shù)據(jù)結(jié)構(gòu)上能被并發(fā)進程所執(zhí)行的一組操作一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。如下圖所示。一、管程的基本概念條件變量條件變量 在管程機制中，當(dāng)某進程通過管程請求臨界資源未能滿足時，管程便調(diào)用wait原語使該進程等待，但等待的原因可能有多個，為了加以區(qū)別，在P，V操作前，引入條件變量加以說明。 （1 1）條件變量的定義

51、格式）條件變量的定義格式 Var x,y: condition （2 2）對條件變量執(zhí)行的兩種操作）對條件變量執(zhí)行的兩種操作nWait操作 如x.wait用來將執(zhí)行進程掛到與條件變量x相應(yīng)的 等待隊列上。nSignal操作 如x.signal用來喚醒與條件變量x相應(yīng)的等待隊列 上的一個進程。 二、用管程機制解決生產(chǎn)者二、用管程機制解決生產(chǎn)者消費者問題消費者問題1、建立Producer-consumer(PC)管程 Type producer-consumer=monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull

52、,notempty:condition; put(item); get(item); begin in:=out:=0; /* 初始化代碼*/ count:=0; end管程中的兩個條件變量：管程中的兩個條件變量： (1) notfull 當(dāng)緩沖區(qū)中不全滿，該變量為真。 (2)notempty 當(dāng)緩沖區(qū)中不全空，該變量為真。二、用管程機制解決生產(chǎn)者二、用管程機制解決生產(chǎn)者消費者問題消費者問題1、建立Producer-consumer(PC)管程n put(item)過程 生產(chǎn)者利用此過程將自已的消息放到緩沖池中，若發(fā)現(xiàn)緩沖已滿（count n),則等待。nGet(item)過程 消費者利用此過

53、程將緩沖池中的消息取走，若發(fā)現(xiàn)緩沖已空（count 0),則等待。 put(item) put(item)Procedure entry put(item) begin if count n then full.wait; buffer(in):=nextp; in:=(in+1) mod n; count:=count+1; if empty.queue then empty.signal; end get(item) get(item)Procedure entry get(item) begin if count 0 then empty.wait; nextc:=buffer(out)

54、; out:=(out+1) mod n; count:=count-1; if full.queue then full.signal; end2 2、生產(chǎn)者、生產(chǎn)者消費者問題的解決消費者問題的解決Producer:begin repeat produce an item in nextp; PC.put(item); until false endConsumer:begin repeat PC.get(item); consume the item in nextc; until false end返回目錄 2.6 進程通信高級通信一、進程通信的類型一、進程通信的類型 進程通信是指進程之間的信息交換。根據(jù)所交換的信息量的多少分為： v低級通信低級通信 進程之間交換的信息量較少且效率低。如進程同步和互斥。v高級通信高級通信 進程之間交換的信息量較多且效率高。又分：共享存儲器系統(tǒng)共享存儲器系統(tǒng) 指進程之間通過對共享存儲區(qū)讀寫來交換數(shù)據(jù)。消息傳遞系統(tǒng)消息傳遞系統(tǒng) 指進程間的通信以消息為單位，程序員可通過通信原語 實現(xiàn)通信，按其實現(xiàn)方式不同可分為：直接通信方式直接通信方式 發(fā)送進程直接把消息發(fā)送給接收進程。間接通信方式間接通信方式 發(fā)送進程把消息發(fā)送到某個中間實體（信箱），接收進 程從中取得消息。管道通信系統(tǒng)管道通信系統(tǒng) 發(fā)送進程（寫進程）以字符流形式將大量數(shù)據(jù)送入管道（管道：