操作系統(tǒng)（第3版）第2章用戶接口和作業(yè)管理第2章用戶接口和作業(yè)管理2.1概述

2.2命令接口

2.3系統(tǒng)調(diào)用

2.4作業(yè)管理2.1概述作業(yè)的基本概念概念－作業(yè)通常是指用戶在一次計(jì)算過程中或者一次事物處理過程中要求計(jì)算機(jī)系統(tǒng)所作的工作的集合－任何一個(gè)作業(yè)都要經(jīng)過若干加工步驟才能得到結(jié)果，作業(yè)的每一個(gè)加工步驟稱為一個(gè)作業(yè)步－一次有一批作業(yè)進(jìn)入系統(tǒng)，并在操作系統(tǒng)控制下，一個(gè)接一個(gè)地進(jìn)行處理，稱之為作業(yè)流－作業(yè)的兩種基本類型：批處理作業(yè)、交互式作業(yè)用戶接口－命令接口－程序接口－圖形接口2.2命令接口聯(lián)機(jī)命令接口命令的格式和分類

-一般格式為：命令名參數(shù)，參數(shù)，…，參數(shù)

-操作控制命令類型有：系統(tǒng)訪問命令，文件、目錄管理命令，編輯修改命令，編譯、連接和執(zhí)行命令，詢問命令，操作員專用命令

-命令的接收和解釋執(zhí)行

-交互式系統(tǒng)主要包括：一組聯(lián)機(jī)命令，終端處理程序，命令解釋程序2.2命令接口

終端處理程序配置在終端上的終端處理程序主要用于實(shí)現(xiàn)人機(jī)交互，具有以下功能：－接收用戶從終端上輸入的字符－字符緩沖管理－回送顯示－屏幕編輯－特殊字符處理命令解釋程序－主要功能：對用戶輸入的命令進(jìn)行解釋，并轉(zhuǎn)入相應(yīng)的命令處理程序去執(zhí)行－對命令的處理方法：由命令解釋程序直接處理或由子進(jìn)程代為處理2.2命令接口脫機(jī)命令接口

作業(yè)控制語言是對用戶作業(yè)的進(jìn)行組織和管理的各種控制命令的集合

作業(yè)控制說明書是用戶用于描述批處理作業(yè)處理過程控制意圖的一種特殊程序

作業(yè)控制說明書主要包括內(nèi)容：作業(yè)的基本描述、作業(yè)控制描述和資源要求描述

作業(yè)的組成：程序、數(shù)據(jù)和作業(yè)控制說明書2.3系統(tǒng)調(diào)用

系統(tǒng)調(diào)用是操作系統(tǒng)提供給編程人員的唯一接口系統(tǒng)調(diào)用的概念由操作系統(tǒng)提供，用戶程序可以調(diào)用的包含特權(quán)指令的子程序稱為“系統(tǒng)功能調(diào)用”程序，或簡稱為“系統(tǒng)調(diào)用”。系統(tǒng)調(diào)用分類文件操作類、進(jìn)程控制類、資源申請類、進(jìn)程通信類、信息維護(hù)類系統(tǒng)調(diào)用與一般過程調(diào)用的區(qū)別

系統(tǒng)調(diào)用通過非特權(quán)指令——訪管指令調(diào)用2.3系統(tǒng)調(diào)用

系統(tǒng)調(diào)用與一般過程調(diào)用的區(qū)別：

*通過軟中斷進(jìn)入

一般的過程調(diào)用可直接由調(diào)用過程轉(zhuǎn)向被調(diào)用過程；系統(tǒng)調(diào)用通常都是通過軟中斷機(jī)制轉(zhuǎn)向相應(yīng)的命令處理程序*運(yùn)行在不同的處理器狀態(tài)一般的過程調(diào)用，其調(diào)用程序和被調(diào)用程序都運(yùn)行在相同的處理器狀態(tài)；系統(tǒng)調(diào)用調(diào)用程序運(yùn)行在目態(tài)，而被調(diào)用程序則運(yùn)行在管態(tài)

*處理器狀態(tài)的轉(zhuǎn)換一般的過程調(diào)用不涉及系統(tǒng)狀態(tài)的轉(zhuǎn)換；系統(tǒng)調(diào)用需要系統(tǒng)狀態(tài)轉(zhuǎn)換2.3系統(tǒng)調(diào)用*返回問題

一般的過程調(diào)用在被調(diào)用過程執(zhí)行完后，將返回到調(diào)用過程繼續(xù)執(zhí)行；系統(tǒng)調(diào)用不一定返回原調(diào)用過程

*嵌套調(diào)用像一般過程一樣，系統(tǒng)調(diào)用也允許嵌套調(diào)用，但對嵌套調(diào)用的深度都有一定的限制2.3系統(tǒng)調(diào)用系統(tǒng)調(diào)用的處理過程基本概念－在系統(tǒng)中為控制系統(tǒng)調(diào)用服務(wù)的機(jī)構(gòu)稱為陷入或異常處理機(jī)構(gòu)－由于系統(tǒng)調(diào)用引起處理機(jī)中斷的指令稱為陷入或異常指令（或稱訪管指令）－每個(gè)系統(tǒng)調(diào)用都對應(yīng)一個(gè)事先給定的功能號－為了實(shí)現(xiàn)系統(tǒng)調(diào)用，系統(tǒng)設(shè)計(jì)人員還必須為實(shí)現(xiàn)各種系統(tǒng)調(diào)用功能的子程序編寫入口地址表，每個(gè)入口地址都與相應(yīng)的系統(tǒng)程序名對應(yīng)起來2.3系統(tǒng)調(diào)用

系統(tǒng)調(diào)用的執(zhí)行過程大體上分成以下三步－設(shè)置系統(tǒng)調(diào)用號和參數(shù)－系統(tǒng)調(diào)用命令的一般性處理－系統(tǒng)調(diào)用命令處理程序做具體處理2.4作業(yè)管理

批處理作業(yè)的管理作業(yè)控制塊和作業(yè)表作業(yè)控制塊批處理作業(yè)存在的標(biāo)志，其中保存了系統(tǒng)對于作業(yè)進(jìn)行管理所需要的全部信息，它們被保存于磁盤區(qū)域中作業(yè)控制塊中包括的內(nèi)容－作業(yè)本身的內(nèi)容，如作業(yè)的名字、程序作者名字、創(chuàng)建時(shí)間等

2.4作業(yè)管理

－為實(shí)現(xiàn)作業(yè)調(diào)度所而的信息，如作業(yè)本身的優(yōu)先數(shù)、現(xiàn)在所處的狀態(tài)處理機(jī)的時(shí)間等－作業(yè)使用的資源要求，如作業(yè)所需內(nèi)存的大小、打印機(jī)、磁帶機(jī)等－系統(tǒng)指示單元，如該作業(yè)所在外存中的起址和長度等信息2.4作業(yè)管理作業(yè)標(biāo)知用戶名稱用戶帳號調(diào)度信息資源需求作業(yè)狀態(tài)作業(yè)類別輸入井地址輸出井地址進(jìn)入系統(tǒng)時(shí)間開始處理時(shí)間作業(yè)完成時(shí)間作業(yè)退出時(shí)間資源使用情況2.4作業(yè)管理

作業(yè)表每個(gè)作業(yè)有一個(gè)作業(yè)控制塊，所有作業(yè)的作業(yè)控制塊構(gòu)成一個(gè)表，稱為作業(yè)表作業(yè)表存放在外存固定區(qū)域中，其長度是固定的，這就限制了系統(tǒng)所能同時(shí)容納的作業(yè)數(shù)量作業(yè)的建立一個(gè)作業(yè)的建立過程包括兩個(gè)子過程：—個(gè)是JCB的建立，一個(gè)是作業(yè)的輸入建立作業(yè)的作業(yè)控制塊就是申請分得和填寫一張空白的JCB表的過程2.4作業(yè)管理作業(yè)的輸入常用的作業(yè)的輸入方式有三種：－脫機(jī)輸入方式－SPOOLING系統(tǒng)的輸入方式－直接耦合方式批處理作業(yè)的調(diào)度－作業(yè)調(diào)度操作系統(tǒng)根據(jù)允許并行工作的道數(shù)和一定的算法從等待的作業(yè)（后備作業(yè)）中選取若干作業(yè)裝入內(nèi)存儲器，使它們可以去獲得處理器運(yùn)行－作業(yè)調(diào)度程序完成作業(yè)調(diào)度工作的程序2.4作業(yè)管理

作業(yè)調(diào)度的基本概念選取調(diào)度算法應(yīng)考慮的主要因素公平性、均衡使用資源、吞吐率、平衡系統(tǒng)和用戶要求作業(yè)調(diào)度性能衡量的指標(biāo)

-CPU利用率

-吞吐量

-周轉(zhuǎn)時(shí)間:假定作業(yè)i進(jìn)入“輸入井”的時(shí)間為Si，若它被選中執(zhí)行，得到計(jì)算結(jié)果的時(shí)間為Ei，它的周轉(zhuǎn)時(shí)間定義為

Ti=Ei-Si-平均周轉(zhuǎn)時(shí)間：所有作業(yè)的周轉(zhuǎn)時(shí)間的平均值。假定作業(yè)i的周轉(zhuǎn)時(shí)間定義為Ti，平均周轉(zhuǎn)時(shí)間定義為2.4作業(yè)管理

-帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間為作業(yè)的周轉(zhuǎn)時(shí)間與作業(yè)的運(yùn)行時(shí)間之比。作業(yè)調(diào)度算法先來先服務(wù)算法

算法：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選

優(yōu)點(diǎn)：算法容易實(shí)現(xiàn)缺點(diǎn)：效率不高、不利于短作業(yè)2.4作業(yè)管理

最短作業(yè)優(yōu)先算法

算法：總是選取計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行

優(yōu)點(diǎn)：算法容易實(shí)現(xiàn)，縮短了平均周轉(zhuǎn)時(shí)間，提高了系統(tǒng)的吞吐能力

缺點(diǎn)：忽視了作業(yè)等待時(shí)間，計(jì)算時(shí)間靠用戶估計(jì)2.4作業(yè)管理

響應(yīng)比最高者優(yōu)先算法

算法：響應(yīng)比=（等待時(shí)間+計(jì)算時(shí)間）/計(jì)算時(shí)間，作業(yè)調(diào)度時(shí)總是選取響應(yīng)比高的作業(yè)投入運(yùn)行

優(yōu)點(diǎn)：既照顧了短作業(yè)，考慮了系統(tǒng)的吞吐量，又考慮了不使長作業(yè)長時(shí)間等待

缺點(diǎn)：響應(yīng)比所用計(jì)算時(shí)間仍是用戶的估計(jì)時(shí)間2.4作業(yè)管理優(yōu)先數(shù)調(diào)度算法

算法：每次總是選擇優(yōu)先數(shù)高的作業(yè)

優(yōu)先數(shù)的確定：一種是用戶自己提出；一種是由系統(tǒng)綜合考慮有關(guān)因素來確定分類調(diào)度算法

算法：根據(jù)系統(tǒng)運(yùn)行情況和作業(yè)屬性將作業(yè)分類，作業(yè)調(diào)度時(shí)輪流從這些不同的作業(yè)類中挑選作業(yè)

目標(biāo)：力求均衡地利用各種系統(tǒng)資源，發(fā)揮資源的使用效率，又力求使用戶滿意2.4作業(yè)管理

作業(yè)調(diào)度與處理器調(diào)度的關(guān)系進(jìn)入計(jì)算機(jī)系統(tǒng)的作業(yè)只有經(jīng)過兩級調(diào)度后才能占用處理器。第一級是作業(yè)調(diào)度，使作業(yè)進(jìn)入內(nèi)存儲器；第二級是處理器調(diào)度，使作業(yè)進(jìn)程占用處理器。

作業(yè)的執(zhí)行一個(gè)批處理作業(yè)被作業(yè)調(diào)度選中后，操作系統(tǒng)按用戶提交的作業(yè)控制說明書控制作業(yè)的執(zhí)行，一個(gè)作業(yè)往往要分幾個(gè)作業(yè)步執(zhí)行。2.4作業(yè)管理

作業(yè)的終止與撤銷作業(yè)的終止

正常終止、非正常終止撤銷作業(yè)的過程－報(bào)告用戶作業(yè)是正常終止還是非正常終止－回收發(fā)給該進(jìn)程的資源，包括外設(shè)、內(nèi)存空間，進(jìn)程運(yùn)行時(shí)打開的文件等－釋放該作業(yè)JCB

－將此作業(yè)注銷2.4作業(yè)管理

作業(yè)的狀態(tài)－提交狀態(tài)作業(yè)還未進(jìn)入算機(jī)系統(tǒng)內(nèi)之前，用戶正在向系統(tǒng)提交作業(yè)時(shí)所處的狀態(tài)－后備狀態(tài)作業(yè)的提交完成后，作業(yè)便處于后備狀態(tài)－運(yùn)行狀態(tài)作業(yè)被選中，分配資源，調(diào)入內(nèi)存，創(chuàng)建進(jìn)程－完成狀態(tài)當(dāng)作業(yè)運(yùn)行結(jié)束或異常終止時(shí)，作業(yè)進(jìn)入完成狀態(tài)第3章進(jìn)程與進(jìn)程管理操作系統(tǒng)（第3版）第3章進(jìn)程與進(jìn)程管理3.1進(jìn)程的引入3.2進(jìn)程3.3進(jìn)程調(diào)度3.4線程的基本概念3.5Linux的進(jìn)程與進(jìn)程管理3.1進(jìn)程的引入前趨圖的定義

前趨圖（ProcedenceGraph）是一個(gè)有向無循環(huán)圖（DAG）。圖中的每個(gè)結(jié)點(diǎn)可用于表示一條語句、一個(gè)程序段或進(jìn)程；結(jié)點(diǎn)間的有向邊則表示在兩結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“→”，→={(Pi，Pj)|Pi必須在Pj開始前完成}。

3.1進(jìn)程的引入程序順序執(zhí)行定義程序在執(zhí)行時(shí)，必須按照某種先后次序逐個(gè)執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作程序順序執(zhí)行的特征

－程序執(zhí)行的順序性處理機(jī)的操作嚴(yán)格按程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后才能執(zhí)行后繼操作

3.1進(jìn)程的引入

－程序執(zhí)行的封閉性

程序一旦開始運(yùn)行，其執(zhí)行結(jié)果不受外界因素的影響

－程序執(zhí)行結(jié)果的確定性

程序執(zhí)行的結(jié)果與它的執(zhí)行速度、時(shí)間無關(guān)

－程序結(jié)果的可再現(xiàn)性程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序多次重復(fù)執(zhí)行時(shí)，都將獲得相同的結(jié)果

3.1進(jìn)程的引入程序并發(fā)執(zhí)行定義在上圖中的輸入程序、計(jì)算程序和打印程序三者之間，存在著Ii→Ci→Pi這樣的前趨關(guān)系，以致對一個(gè)作業(yè)的輸入、計(jì)算和打印三個(gè)操作必須順序執(zhí)行，但并不存在Pi→Ii+1關(guān)系，因而在對一批程序進(jìn)行處理時(shí)，可使它們并發(fā)執(zhí)行。3.1進(jìn)程的引入

程序并發(fā)執(zhí)行特征

－程序執(zhí)行的間斷性

程序執(zhí)行的相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行—暫停執(zhí)行—執(zhí)行”這種間斷性的活動規(guī)律

－程序執(zhí)行失去封閉性

因多個(gè)程序共享系統(tǒng)中的資源，所以某程序在執(zhí)行時(shí)必然會受到其他程序的影響

3.1進(jìn)程的引入

－程序執(zhí)行結(jié)果的不可再現(xiàn)性

由于失去了封閉性，也將導(dǎo)致失去其可再現(xiàn)性

－資源共享系統(tǒng)中的硬件資源和軟件資源不再被單個(gè)用戶或程序獨(dú)占，而為多個(gè)用戶或作業(yè)共同使用

－程序和計(jì)算不再一一對應(yīng)

程序和計(jì)算是兩個(gè)不同的概念，在程序并發(fā)執(zhí)行中一個(gè)共享程序可對應(yīng)多個(gè)“計(jì)算”，程序與“計(jì)算”已不再一一對應(yīng)

3.1進(jìn)程的引入多道程序設(shè)計(jì)定義在采用多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，允許多個(gè)程序同時(shí)進(jìn)入一個(gè)計(jì)算機(jī)系統(tǒng)的內(nèi)存儲器并運(yùn)行，這種讓多個(gè)程序同時(shí)進(jìn)入計(jì)算機(jī)計(jì)算的方法稱為多道程序設(shè)計(jì)。

目的提高處理器的效率，從而提高整個(gè)系統(tǒng)的效率必須解決的問題－存儲保護(hù)與程序浮動－處理器的管理和調(diào)度－系統(tǒng)資源的管理和調(diào)度3.2進(jìn)程

引入進(jìn)程的原因

為了使程序在多道程序環(huán)境下能夠并發(fā)執(zhí)行，并對并發(fā)執(zhí)行的程序加以控制和描述，引入進(jìn)程的概念

程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成了一個(gè)進(jìn)程的實(shí)體

進(jìn)程的概念進(jìn)程的定義

進(jìn)程是具有獨(dú)立功能的可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位?；蛘哒f，“進(jìn)程”是進(jìn)程實(shí)體的運(yùn)行過程。3.2進(jìn)程

程序與進(jìn)程的區(qū)別與聯(lián)系區(qū)別:進(jìn)程是程序的一次執(zhí)行，是一個(gè)動態(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ú)立單位，程序則不是程序可以作為一種軟件資源長期保存，而進(jìn)程是程序的一次執(zhí)行過程，它是臨時(shí)的，有生命期的進(jìn)程是具有結(jié)構(gòu)的聯(lián)系:進(jìn)程是程序的運(yùn)行3.2進(jìn)程

進(jìn)程的特征

動態(tài)性：進(jìn)程的基本特性。進(jìn)程是進(jìn)程實(shí)體的執(zhí)行過程；

并發(fā)性:進(jìn)程的主要特征。多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行；獨(dú)立性：進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。

異步性：進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)；或者說，進(jìn)程按異步方式運(yùn)行。

結(jié)構(gòu)特征：從結(jié)構(gòu)上看，進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分組成，有人把這三部分統(tǒng)稱為“進(jìn)程映像”。3.2進(jìn)程進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)

就緒狀態(tài)

當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源后，只要能再獲得處理機(jī)便可立即執(zhí)行，這時(shí)的狀態(tài)稱為就緒狀態(tài)

執(zhí)行狀態(tài)

指進(jìn)程已獲得處理機(jī)，其程序正在執(zhí)行

阻塞狀態(tài)

進(jìn)程因發(fā)生某種事件（如I/O請求、申請緩沖空間等）而暫停執(zhí)行時(shí)的狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，故稱這種狀態(tài)為阻塞狀態(tài)，有時(shí)也稱為“等待”狀態(tài)或“睡眠”狀態(tài)。思考:剛剛創(chuàng)建的進(jìn)程應(yīng)該處于哪種狀態(tài)?3.2進(jìn)程進(jìn)程狀態(tài)的轉(zhuǎn)換

－就緒→執(zhí)行狀態(tài)

處于就緒狀態(tài)的進(jìn)程，當(dāng)進(jìn)程調(diào)度為之分配了處理機(jī)后－執(zhí)行→阻塞狀態(tài)

正在執(zhí)行的進(jìn)程因發(fā)生某種事件而無法執(zhí)行－執(zhí)行→就緒狀態(tài)

正在執(zhí)行的進(jìn)程如因時(shí)間片用完或一個(gè)優(yōu)先權(quán)高的進(jìn)程到來而被暫停執(zhí)行－阻塞→就緒狀態(tài)

處于阻塞狀態(tài)的進(jìn)程，其等待的事件已經(jīng)發(fā)生

思考:其他狀態(tài)轉(zhuǎn)換可以存在嗎?3.2進(jìn)程3.2進(jìn)程進(jìn)程的掛起狀態(tài)掛起狀態(tài)的引入

－終端用戶的需要

當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問題時(shí)，往往希望暫時(shí)使自己的進(jìn)程靜止下來。－父進(jìn)程的需要

父進(jìn)程常常希望考察和修改子進(jìn)程或者當(dāng)要協(xié)調(diào)各子進(jìn)程間的活動－操作系統(tǒng)的需要

操作系統(tǒng)有時(shí)需要掛起某些進(jìn)程，檢查運(yùn)行中資源的使用情況及進(jìn)行記賬，以便改善系統(tǒng)運(yùn)行的性能。3.2進(jìn)程

－對換的需要

為了緩解內(nèi)存緊張的情況，即將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程換至輔存上，使進(jìn)程又處于一種有別于阻塞狀態(tài)的新狀態(tài)。

－負(fù)荷調(diào)節(jié)的需要進(jìn)程狀態(tài)的轉(zhuǎn)換

在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱靜止?fàn)顟B(tài)）到非掛起狀態(tài)（又稱活動狀態(tài)）的轉(zhuǎn)換－活動就緒→靜止就緒

－活動阻塞→靜止阻塞

－靜止就緒→活動就緒

－靜止阻塞→活動阻塞3.2進(jìn)程進(jìn)程控制塊PCB

進(jìn)程控制塊的作用－進(jìn)程控制塊記錄進(jìn)程信息－操作系統(tǒng)是根據(jù)進(jìn)程控制塊PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的－PCB是進(jìn)程存在的唯一標(biāo)志

思考:進(jìn)程控制塊應(yīng)該存放在何處?需要存放在磁盤中嗎?

進(jìn)程控制塊中的信息－進(jìn)程標(biāo)識符信息

進(jìn)程標(biāo)識符用于唯一地標(biāo)識一個(gè)進(jìn)程，通常有外部標(biāo)識符和內(nèi)部標(biāo)識符3.2進(jìn)程①外部標(biāo)識符。由創(chuàng)建者提供，通常由字母、數(shù)字所組成，往往是由用戶（進(jìn)程）在訪問該進(jìn)程時(shí)使用。②內(nèi)部標(biāo)識符。這是為了方便系統(tǒng)使用而設(shè)置的。在所有操作系統(tǒng)中都為每一個(gè)進(jìn)程賦予一個(gè)惟一的整數(shù)作為內(nèi)部標(biāo)識符，它通常就是一個(gè)進(jìn)程的序號。－處理機(jī)狀態(tài)信息

處理機(jī)狀態(tài)信息主要是由處理機(jī)各種寄存器中的內(nèi)容所組成：通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字PSW、用戶棧指針。－進(jìn)程調(diào)度信息存放了一些與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的信息：進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級、進(jìn)程調(diào)度所需的其他信息、事件。3.2進(jìn)程

－進(jìn)程控制信息程序和數(shù)據(jù)的地址、進(jìn)程同步和通信機(jī)制、資源清單、鏈接指針。

PCB的組織方式

-鏈接方式把具有相同狀態(tài)的PCB鏈接成一個(gè)隊(duì)列，這樣可形成就緒隊(duì)列、若干個(gè)阻塞隊(duì)列和空隊(duì)列等

-索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表思考:你認(rèn)為圖中缺少什么內(nèi)容嗎?3.2進(jìn)程進(jìn)程控制

進(jìn)程控制的主要任務(wù)是創(chuàng)建和撤消進(jìn)程以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換，進(jìn)程控制一般由操作系統(tǒng)的內(nèi)核來實(shí)現(xiàn)。操作系統(tǒng)內(nèi)核通常是運(yùn)行在系統(tǒng)態(tài)的。操作系統(tǒng)內(nèi)核定義通常，將一些與硬件緊密相關(guān)的模塊諸如中斷處理程序、各種常用設(shè)備的驅(qū)動程序以及運(yùn)行頻率較高的模塊都安排在緊靠硬件的軟件層次中并使它們常駐內(nèi)存，以便提高操作系統(tǒng)的運(yùn)行效率，并對它們加以特殊的保護(hù)，把這一部分稱為操作系統(tǒng)的內(nèi)核

3.2進(jìn)程

操作系統(tǒng)內(nèi)核的功能

中斷處理：中斷處理功能在操作系統(tǒng)中，既是內(nèi)核的最基本功能，也是整個(gè)操作系統(tǒng)賴以活動的基礎(chǔ)，即操作系統(tǒng)的重要活動最終都將依賴于中斷。進(jìn)程管理：進(jìn)程創(chuàng)建、撤消、進(jìn)程狀態(tài)的轉(zhuǎn)換、進(jìn)程調(diào)度等。

資源管理中的基本操作：包括對時(shí)鐘、I/O設(shè)備和文件系統(tǒng)進(jìn)行控制和管理的基本操作。

原子操作所謂原子操作是指：一個(gè)操作中的所有動作，要么全做，要么全不做。換言之，原子操作是一個(gè)不可分割的操作內(nèi)核在執(zhí)行上述操作時(shí)，往往是通過執(zhí)行各種原語操作來實(shí)現(xiàn)的。3.2進(jìn)程

進(jìn)程的創(chuàng)建進(jìn)程圖－進(jìn)程圖是用于描述進(jìn)程家族關(guān)系的有向樹－子進(jìn)程可以繼承父進(jìn)程所擁有的資源，當(dāng)子進(jìn)程撤銷時(shí)，應(yīng)將從父進(jìn)程那里獲得的資源歸還給父進(jìn)程；在撤銷父進(jìn)程時(shí)，也必須同時(shí)撤銷其所有的子進(jìn)程引起創(chuàng)建進(jìn)程的事件－用戶登錄－作業(yè)調(diào)度－提供服務(wù)－應(yīng)用請求3.2進(jìn)程

進(jìn)程的創(chuàng)建過程調(diào)用進(jìn)程創(chuàng)建原語create()創(chuàng)建進(jìn)程－申請空白PCB

－為新進(jìn)程分配資源－初始化進(jìn)程控制塊－將新進(jìn)程插入就緒隊(duì)列思考:前兩步驟是否可以顛倒順序?3.2進(jìn)程

進(jìn)程的終止引起進(jìn)程終止的事件

-正常結(jié)束

-異常結(jié)束

-外界干預(yù)進(jìn)程的終止過程調(diào)用進(jìn)程終止原語destroy()終止進(jìn)程－根據(jù)被終止進(jìn)程的標(biāo)識符從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)－若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行并設(shè)置調(diào)度標(biāo)志為真

3.2進(jìn)程

－若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止－將該進(jìn)程所擁有的全部資源，或者歸還其父進(jìn)程或者歸還給系統(tǒng)－釋放進(jìn)程的PCB

進(jìn)程的阻塞與喚醒引起進(jìn)程阻塞和喚醒的事件

-請求系統(tǒng)服務(wù)

-啟動某種操作

-新數(shù)據(jù)尚未到達(dá)

-無新工作可作3.2進(jìn)程

進(jìn)程阻塞過程進(jìn)程便通過調(diào)用阻塞原語block（）把自己阻塞－立即停止當(dāng)前進(jìn)程的執(zhí)行－把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”，并把它插入到阻塞隊(duì)列

思考:是否轉(zhuǎn)向進(jìn)程調(diào)度?

進(jìn)程喚醒過程調(diào)用喚醒原語wakeup()將等待該事件的進(jìn)程喚醒－把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出－將其PCB中的現(xiàn)行狀態(tài)由“阻塞”改為“就緒”－然后再將該進(jìn)程插入到就緒隊(duì)列中3.2進(jìn)程

進(jìn)程的掛起與激活進(jìn)程的掛起過程當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，系統(tǒng)就利用掛起原語suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起－檢查被掛起進(jìn)程的狀態(tài)，若正處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進(jìn)程，則將其改為靜止阻塞－進(jìn)程保存于外存對換區(qū)－如被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)度3.2進(jìn)程進(jìn)程的激活過程

當(dāng)發(fā)生激活進(jìn)程的事件時(shí)系統(tǒng)將利用激活原語active()將指定進(jìn)程激活－將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)：若是靜止就緒，便將其改為活動就緒；若為靜止阻塞，便將其改為活動阻塞－假如采用的是搶占調(diào)度策略，檢查是否要進(jìn)行重新調(diào)度3.3進(jìn)程調(diào)度調(diào)度的基本概念高級、中級和低級調(diào)度一個(gè)作業(yè)從提交開始直到完成，往往要經(jīng)歷三級調(diào)度：

高級調(diào)度又稱為作業(yè)調(diào)度，它決定將哪些在外存上處于后備狀態(tài)的作業(yè)調(diào)入主機(jī)內(nèi)存，準(zhǔn)備執(zhí)行

低級調(diào)度又稱為進(jìn)程調(diào)度。它決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，并實(shí)際執(zhí)行將處理機(jī)分配給該進(jìn)程的操作在有的系統(tǒng)中，可能增加一中級調(diào)度，主要作用是在內(nèi)存和外存對換區(qū)之間進(jìn)行進(jìn)程對換，以解決內(nèi)存緊張問題3.3進(jìn)程調(diào)度

進(jìn)程調(diào)度的功能進(jìn)程調(diào)度就是系統(tǒng)按照某種算法把CPU動態(tài)地分配給某一就緒進(jìn)程。進(jìn)程調(diào)度工作是通過進(jìn)程調(diào)度程序來完成的。進(jìn)程調(diào)度程序的主要功能：－選擇進(jìn)程占有CPU

－進(jìn)行進(jìn)程上下文的切換3.3進(jìn)程調(diào)度調(diào)度方式

非剝奪方式分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件（如提出I/O請求）而阻塞時(shí)才把處理機(jī)分配給另一進(jìn)程－優(yōu)點(diǎn)：簡單，系統(tǒng)開銷小，－缺點(diǎn)：貌似公正,可能導(dǎo)致系統(tǒng)性能的惡化剝奪方式該方式規(guī)定，當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程剝奪原則：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則3.3進(jìn)程調(diào)度進(jìn)程調(diào)度算法先進(jìn)先出（FIFO）算法－算法：把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程－優(yōu)點(diǎn)：易于實(shí)現(xiàn)－缺點(diǎn)：表面上公平，服務(wù)質(zhì)量不佳、對短進(jìn)程不利

思考:算法實(shí)現(xiàn)最短CPU運(yùn)行期優(yōu)先調(diào)度算法－算法：從就緒隊(duì)列中選出“下一個(gè)CPU執(zhí)行期”最短的進(jìn)程，為之分配處理機(jī)使之執(zhí)行－優(yōu)點(diǎn)：可獲得較好的調(diào)度性能－缺點(diǎn)：進(jìn)程的CPU執(zhí)行期難以準(zhǔn)確得到、對長進(jìn)程不利3.3進(jìn)程調(diào)度最高響應(yīng)比優(yōu)先調(diào)度算法－算法：響應(yīng)比=（等待時(shí)間+要求的服務(wù)時(shí)間）/要求的服務(wù)時(shí)間，每次選取響應(yīng)比最高的進(jìn)程調(diào)度－優(yōu)點(diǎn)：所以對短進(jìn)程有利，并且考慮了等待時(shí)間－缺點(diǎn)：計(jì)算響應(yīng)比有一定的系統(tǒng)開銷優(yōu)先級調(diào)度算法－算法：將CPU分配給就緒隊(duì)列中優(yōu)先級最高的進(jìn)程

－靜態(tài)優(yōu)先級在進(jìn)程創(chuàng)建時(shí)確立，確定后運(yùn)行期間保持不變。確立依據(jù)有：進(jìn)程的類型、進(jìn)程對資源的需求、用戶申請的優(yōu)先級優(yōu)點(diǎn)：簡單缺點(diǎn)：不能動態(tài)反映進(jìn)程特點(diǎn)，系統(tǒng)調(diào)度性能差3.3進(jìn)程調(diào)度

－動態(tài)優(yōu)先級

進(jìn)程在開始創(chuàng)建時(shí)，根據(jù)某種原則確定一個(gè)優(yōu)先級后，隨著進(jìn)程執(zhí)行時(shí)間的變化，其優(yōu)先級不斷地進(jìn)行動態(tài)調(diào)整確定依據(jù)：根據(jù)進(jìn)程占有的CPU時(shí)間的長短來決定，占有時(shí)間越長優(yōu)先級越低；根據(jù)進(jìn)程等待CPU的時(shí)間來決定，時(shí)間越長優(yōu)先級越高3.3進(jìn)程調(diào)度

時(shí)間片輪轉(zhuǎn)調(diào)度算法

算法：通常用在分時(shí)系統(tǒng)，它輪流地調(diào)度系統(tǒng)中所有就緒進(jìn)程，使就緒進(jìn)程依次獲得一個(gè)時(shí)間片的運(yùn)行時(shí)間時(shí)間片長短確定遵循原則既要保證系統(tǒng)各個(gè)用戶進(jìn)程及時(shí)地得到響應(yīng)，又不要由于時(shí)間片太短而增加調(diào)度的開銷，降低系統(tǒng)的效率3.3進(jìn)程調(diào)度

進(jìn)程依次執(zhí)行時(shí)可能發(fā)生的三種情況

－進(jìn)程未用完一個(gè)時(shí)間片便結(jié)束，這時(shí)系統(tǒng)應(yīng)提前進(jìn)行調(diào)度－進(jìn)程在執(zhí)行過程中提出I/O請求而阻塞，系統(tǒng)應(yīng)將它放入相應(yīng)的阻塞隊(duì)列并引起調(diào)度－進(jìn)程用完一個(gè)時(shí)間片后尚未完成。系統(tǒng)應(yīng)將它重新放到就緒隊(duì)列的末尾，等待下次執(zhí)行

3.3進(jìn)程調(diào)度

3.3進(jìn)程調(diào)度

前后臺調(diào)度算法－算法：該方法用在批處理和分時(shí)相結(jié)合的系統(tǒng)中。將分時(shí)用戶作業(yè)放在前臺，把批處理作業(yè)放在后臺。系統(tǒng)對前臺作業(yè)按照時(shí)間片輪轉(zhuǎn)法進(jìn)行調(diào)度，僅當(dāng)前臺無作業(yè)時(shí)，才把處理機(jī)分配給后臺作業(yè)的進(jìn)程。后臺進(jìn)程通常按先來先服務(wù)方式運(yùn)行－優(yōu)點(diǎn)：使分時(shí)用戶進(jìn)程得到及時(shí)響應(yīng)，又提高了系統(tǒng)資源的利用率

3.3進(jìn)程調(diào)度

多級反饋隊(duì)列輪轉(zhuǎn)算法－系統(tǒng)設(shè)置多個(gè)不同優(yōu)先級的就緒隊(duì)列，每次調(diào)度總是先調(diào)度優(yōu)先級高的隊(duì)列，僅當(dāng)該隊(duì)列空時(shí)，才調(diào)度次高優(yōu)先級隊(duì)列。－通常剛創(chuàng)建的進(jìn)程和因請求I/O未用完時(shí)間片的進(jìn)程排在最高優(yōu)先級隊(duì)列，在這個(gè)隊(duì)列中運(yùn)行2-3個(gè)時(shí)間片未完成的進(jìn)程排列下一個(gè)較低優(yōu)先級隊(duì)列。－不論什么時(shí)候，只要較高優(yōu)先級隊(duì)列有進(jìn)程進(jìn)入，立即轉(zhuǎn)進(jìn)程調(diào)度，及時(shí)調(diào)度較高優(yōu)先級隊(duì)列進(jìn)程。－優(yōu)點(diǎn)：能較好地滿足各類作業(yè)的用戶要求，既能使分時(shí)用戶作業(yè)得到滿意的響應(yīng)，又能使批處理用戶的作業(yè)獲得較合理的周轉(zhuǎn)時(shí)間3.3進(jìn)程調(diào)度3.3進(jìn)程調(diào)度進(jìn)程調(diào)度的時(shí)機(jī)和過程進(jìn)程調(diào)度的時(shí)機(jī)－正在執(zhí)行的進(jìn)程運(yùn)行完畢

－正在執(zhí)行的進(jìn)程調(diào)用阻塞原語將自己阻塞起來進(jìn)入等待狀態(tài)－在采用搶占式優(yōu)先級調(diào)度時(shí)，有優(yōu)先級高于正在運(yùn)行進(jìn)程的進(jìn)程進(jìn)入就緒隊(duì)列－在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完－CPU方式是可剝奪時(shí)，就緒隊(duì)列中的某個(gè)進(jìn)程優(yōu)先級變得高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級3.3進(jìn)程調(diào)度

進(jìn)程調(diào)度的過程

－進(jìn)程調(diào)度所依賴的數(shù)據(jù)結(jié)構(gòu)通常是調(diào)度隊(duì)列，由于調(diào)度的原因不同，在單處理器系統(tǒng)中設(shè)置了多種等待隊(duì)列－只有就緒隊(duì)列中的進(jìn)程能夠獲得處理器而最終運(yùn)行，其他隊(duì)列中的進(jìn)程從隊(duì)列中出來后，必須進(jìn)入就緒隊(duì)列才能分配處理器－隊(duì)列數(shù)據(jù)結(jié)構(gòu)的建立結(jié)構(gòu)與調(diào)度算法密切相關(guān)－進(jìn)程調(diào)度算法只是決定哪一個(gè)進(jìn)程將獲得處理機(jī)，而將處理機(jī)分配給該進(jìn)程的具體操作是由分派程序完成的

3.3進(jìn)程調(diào)度voiddispatcher()

{

if(RQ==0)

if(EP==0)

idler();

elsecontinue;

enqueue(RQ,i);

if(EP==0)

gotoL;

j=EP;

if(i.priority>j.priority)

{

stop(j);

j.status=ready;

j.sdata=EPdata;

enqueue(RQ,j);

L:dequeue(RQ,i)’

i.status=executing;

EP=i;

}

else

continue;

}

例：

3.4線程線程的引入在操作系統(tǒng)中引入進(jìn)程的目的是為了使多個(gè)程序并發(fā)執(zhí)行以改善資源利用率及提高系統(tǒng)的吞吐量；在操作系統(tǒng)中再引入線程，則是為了減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使操作系統(tǒng)具有更好的并發(fā)性

3.4線程線程的定義和屬性線程的定義在引入線程的操作系統(tǒng)中，線程是進(jìn)程的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。線程自己基本上不擁有系統(tǒng)資源，只擁有一點(diǎn)在運(yùn)行中必不可少的資源，但它可與同屬一個(gè)進(jìn)程的其他線程共享進(jìn)程所擁有的全部資源。一個(gè)線程可以創(chuàng)建和撤銷另一個(gè)線程；同一進(jìn)程中的多個(gè)線程之間可以并發(fā)執(zhí)行3.4線程

線程的屬性線程的狀態(tài)由于線程之間的相互制約，致使線程在運(yùn)行中也呈現(xiàn)出間斷性。相應(yīng)地，線程也同樣有就緒、阻塞和執(zhí)行三種基本狀態(tài)線程的屬性－每個(gè)線程有一個(gè)惟一的標(biāo)識符和一張線程描述表，線程描述表記錄了線程執(zhí)行的寄存器和棧等現(xiàn)場狀態(tài)－不同的線程可以執(zhí)行相同的程序3.4線程

－同一進(jìn)程中的各個(gè)線程共享該進(jìn)程的內(nèi)存地址空間－線程是處理器的獨(dú)立調(diào)度單位，多個(gè)線程是可以并發(fā)執(zhí)行的－一個(gè)線程被創(chuàng)建后便開始了它的生命周期，直至終止，線程在生命周期內(nèi)會經(jīng)歷等待狀態(tài)、就緒態(tài)和運(yùn)行態(tài)等各種狀態(tài)變化3.4線程

引入線程的好處

－創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少（結(jié)束亦如此）－兩個(gè)線程的切換花費(fèi)時(shí)間少－由于同一進(jìn)程內(nèi)的線程共享內(nèi)存和文件，線程之間相互通信無須調(diào)用內(nèi)核，故不需要額外的通信機(jī)制，使通信更簡便，信息傳送速度也快－線程能獨(dú)立執(zhí)行，能充分利用和發(fā)揮處理器與外圍設(shè)備并行工作能力3.4線程線程與進(jìn)程的比較

線程具有許多傳統(tǒng)進(jìn)程所具有的特征，故又稱為輕型進(jìn)程（Light-WeightProcess）或進(jìn)程元；而把傳統(tǒng)的進(jìn)程稱為重型進(jìn)程（Heavy-WeightProcess）調(diào)度在引入線程的操作系統(tǒng)中，線程是調(diào)度和分派的基本單位；在同一進(jìn)程中，線程的切換不會引起進(jìn)程切換；在由一個(gè)進(jìn)程中的線程切換到另一進(jìn)程中的線程時(shí)，將會引起進(jìn)程切換并發(fā)性在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間亦可并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量

3.4線程

擁有資源不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)，進(jìn)程都是擁有資源的一個(gè)獨(dú)立單位，它可以擁有自己的資源。一般地說，線程自己不擁有系統(tǒng)資源（也有一點(diǎn)必不可少的資源），但它可以訪問其隸屬進(jìn)程的資源系統(tǒng)開銷創(chuàng)建、撤銷以至于切換進(jìn)程時(shí)付出的系統(tǒng)開銷顯著大于創(chuàng)建、撤銷、切換線程時(shí)的系統(tǒng)開銷

3.4線程線程的實(shí)現(xiàn)機(jī)制用戶級線程僅存在于用戶級中，對于這種線程的創(chuàng)建、撤銷和切換，都不利用系統(tǒng)調(diào)用來實(shí)現(xiàn)，因而這種線程與內(nèi)核無關(guān)。相應(yīng)地，內(nèi)核也并不知道有用戶級線程的存在內(nèi)核支持線程依賴于內(nèi)核，它們的創(chuàng)建、撤銷和切換都由內(nèi)核實(shí)現(xiàn)。在內(nèi)核中保留了一張線程控制塊，內(nèi)核根據(jù)該控制塊而感知該線程的存在并對線程進(jìn)行控制

3.4線程

用戶級線程和內(nèi)核支持線程的比較

－線程的調(diào)度與切換速度

用戶級線程的調(diào)度切換速度高于內(nèi)核支持線程的速度－系統(tǒng)調(diào)用

用戶級線程的系統(tǒng)調(diào)用將看作整個(gè)進(jìn)程的行為，該進(jìn)程將被阻塞；內(nèi)核支持線程的系統(tǒng)調(diào)用看作該線程的行為，僅僅阻塞該線程－線程執(zhí)行時(shí)間

對于只設(shè)置了用戶級線程的系統(tǒng)，調(diào)度是以進(jìn)程為單位進(jìn)行的；設(shè)置的內(nèi)核支持線程的系統(tǒng)，其調(diào)度是以線程為單位進(jìn)行的

第4章進(jìn)程同步與通信操作系統(tǒng)（第3版）第4章進(jìn)程同步與通信4.1進(jìn)程間的相互作用4.2進(jìn)程通信4.3死鎖4.4Linux進(jìn)程間通信4.1進(jìn)程間的相互作用進(jìn)程間的聯(lián)系

－資源共享關(guān)系－相互合作關(guān)系臨界資源

-一種多個(gè)進(jìn)程訪問的資源。

-屬性：訪問臨界資源的進(jìn)程必須互斥得訪問它，也就是說，同一時(shí)刻只允許一個(gè)進(jìn)程訪問的資源叫臨界資源

思考:下面兩個(gè)進(jìn)程并發(fā)是否能正確執(zhí)行?4.1進(jìn)程間的相互作用voidProducer(){while(1){…produceaniteminnextp;while(counter==n)no-op;buffer[in]=nextp;in=(in+1)modn;counter++;}}register1=counter;resister1++;counter=register1;voidConsumer(){while(1){while(counter==0)no-op;nextc=buffer[out];out=(out+1)modn;counter--;consumetheiteminnextc;…}}register2=counter;resister1--;counter=register2;4.1進(jìn)程間的相互作用

臨界區(qū)不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對它進(jìn)行訪問。我們把在每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)（criticalsection）同步機(jī)制應(yīng)遵循的準(zhǔn)則

-空閑讓進(jìn)

-忙則等待

-有限等待

-讓權(quán)等待4.1進(jìn)程間的相互作用利用軟件方法解決進(jìn)程互斥問題算法1

設(shè)置一個(gè)公用整型變量turn，用于指示被允許進(jìn)入臨界區(qū)的進(jìn)程的編號.

算法描述如下：

P1while(1){…while(turn!=1)no-op;criticalsectionturn=2;…}不能保證實(shí)現(xiàn)“空閑讓進(jìn)”的準(zhǔn)則P2while(1){…while(turn!=2)no-op;criticalsectionturn=1;…}

算法2

設(shè)置一個(gè)數(shù)組，使其中每個(gè)元素的初值為0，表示所有進(jìn)程都未進(jìn)入臨界區(qū)，在每一個(gè)進(jìn)程訪問臨界資源之前，先去查看一下臨界資源是否正被訪問。若正被訪問，該進(jìn)程需等待；否則進(jìn)入自己的臨界區(qū)算法描述如下：intflag[2]={0,0};…P0：

while(1){…while(flag[1])no-op;flag[0]=1;criticalsectionflag[0]=0;…}4.1進(jìn)程間的相互作用違背了“忙則等待”的準(zhǔn)則和“有限等待”P1：

while(1){…while(flag[0])no-op;flag[1]=1;criticalsectionflag[1]=0;…}

算法3

使要進(jìn)入臨界區(qū)的進(jìn)程先設(shè)置其要求進(jìn)入的標(biāo)志，然后，再去查看其他進(jìn)程的標(biāo)志,算法描述如下：intflag[2]={0,0};…P0：

while(1){…flag[0]=1;while(flag[1])no-op;criticalsectionflag[0]=0;…}4.1進(jìn)程間的相互作用違背了“空閑讓進(jìn)”P1：

while(1){…flag[1]=1;while(flag[0])no-op;criticalsectionflag[1]=0;…}

算法4

為每個(gè)進(jìn)程設(shè)置了相應(yīng)的標(biāo)志為flag[]；還設(shè)置了一個(gè)turn變量，用于指示允許進(jìn)入臨界區(qū)的進(jìn)程編號,算法描述如下：

intflag[2]={0,0};…P0：

while(1){…flag[0]=1;turn=2；

while(flag[1]&&turn==2)no-op;criticalsectionflag[0]=0;…}4.1進(jìn)程間的相互作用P1：

while(1){…flag[1]=1;turn=1；

while(flag[0]&&turn==1)no-op;criticalsectionflag[1]=0;…}

保證了“忙則等待”，又實(shí)現(xiàn)了“空閑讓進(jìn)”4.1進(jìn)程間的相互作用利用硬件方法解決進(jìn)程互斥問題利用Test-and-Set指令實(shí)現(xiàn)互斥

Test-and-Set指令為：

intTS(staticintlock){intTS=lock;lock=1;return(TS);}4.1進(jìn)程間的相互作用用TS指令實(shí)現(xiàn)進(jìn)程互斥的循環(huán)描述為：

while(1){…while(TS(lock))dono-op;criticalsectionlock=0;…}

思考:如何保證臨界區(qū)管理的四個(gè)原則?

4.1進(jìn)程間的相互作用利用Swap指令實(shí)現(xiàn)進(jìn)程互斥

Swap指令稱為交換指令,描述為：

voidSwap(staticinta,b){inttemp;temp=a;a=b;b=temp;}4.1進(jìn)程間的相互作用利用Swap指令實(shí)現(xiàn)進(jìn)程互斥的循環(huán)可描述為：

while(1){…key=1;do{Swap(lock,key);}while(key);criticalsectionlock=0;…}

思考:如何保證臨界區(qū)管理的四個(gè)原則?4.1進(jìn)程間的相互作用

信號量機(jī)制

信號量機(jī)制是一種卓有成效的進(jìn)程同步工具記錄型信號量機(jī)制在信號量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還有一個(gè)進(jìn)程鏈表L，用于鏈接所有等待該信號量代表資源的進(jìn)程記錄型數(shù)據(jù)結(jié)構(gòu)描述

typedefstruct{intvalue;listofprocess*L;}semaphore;

4.1進(jìn)程間的相互作用對信號量的操作信號量除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作wait(s)和signal(s)來訪問。這兩個(gè)操作很長時(shí)間以來被稱為P、V操作。當(dāng)一個(gè)進(jìn)程在修改某信號量時(shí)，沒有其他進(jìn)程可以同時(shí)對該信號量進(jìn)行修改。4.1進(jìn)程間的相互作用

信號量的物理含義（假定信號量用S表示）如下：

-S.value>0時(shí)S.value表示可使用的資源數(shù)或表示可使用資源的進(jìn)程數(shù)；

-S.value=0時(shí)S.value表示無資源可供使用或表示不允許進(jìn)程得到該資源；

-S.value<0時(shí)S.value表示等待使用資源的進(jìn)程個(gè)數(shù)或表示等待該資源的進(jìn)程個(gè)數(shù)。4.1進(jìn)程間的相互作用wait操作

申請一個(gè)資源,得到繼續(xù),得不到阻塞，可描述為

if(s.value>0)s.value--;if(s.value<=0)s.value--;block(s.L);簡練為：s.value--;if(s.value<0)block(s.L);wait原語：voidwait(staticsemaphores){s.value--;if(s.value＜0)block(s.L);}4.1進(jìn)程間的相互作用signal操作

釋放一個(gè)資源，有進(jìn)程等待則喚醒一個(gè)，可描述為

if(s.value>=0)s.value++;if(s.value<0)s.value++;wakeup(s.L);簡練為：s.value++;if(s.value<=0)wakeup(s.L);singal原語

voidsignal(staticsemaphores){s.value++;if(s.value≤0)wackup(s.L);}4.1進(jìn)程間的相互作用利用信號量實(shí)現(xiàn)進(jìn)程互斥的過程描述為使多個(gè)進(jìn)程互斥地訪問某個(gè)臨界資源，只需為該資源設(shè)置一個(gè)信號量，并設(shè)其初始值為1，此時(shí)的信號量可以稱為“互斥信號量”。semaphoremutex=1;voidprocedure1(){while(1){…wait(mutex);criticalsectionsignal(mutex);…}}voidprocedure2(){while(1){…wait(mutex);criticalsectionsignal(mutex);…}}main(){cobegin{procedure1();procedure2();}}4.1進(jìn)程間的相互作用

利用信號量來描述程序或語句之間的前趨關(guān)系

－方法：一條邊一個(gè)信號量(信號量初值為0)；wait以該節(jié)點(diǎn)為終點(diǎn)所有邊的信號量，執(zhí)行該節(jié)點(diǎn)，signal以該節(jié)點(diǎn)為始點(diǎn)所有邊的信號量－例：有6個(gè)語句的前驅(qū)圖main(){semaphorea=b=c=d=e=f=g=0;cobegin{{S1;signal(a);signal(b);}{wait(a);S2;signal(c);signal(d);}{wait(b);S3;signal(e);}{wait(d);S4;signal(f);}{wait(c);S5;signal(g);}{wait(e);wait(f);wait(g);S6;}}}4.1進(jìn)程間的相互作用

信號量集機(jī)制

AND型信號量集機(jī)制假定現(xiàn)有兩個(gè)進(jìn)程P和Q，它們都要求訪問共享數(shù)據(jù)A和B。共享數(shù)據(jù)都應(yīng)作為臨界資源，為此，可為這兩個(gè)數(shù)據(jù)分別設(shè)置用于互斥的信號量Amutex和Bmutex，并令它們的初值為1，相應(yīng)地，在兩進(jìn)程中都要包含兩個(gè)對Amutex和Bmutex的操作，即processP:processQ:wait(Amutex);wait(Bmutex);wait(Bmutex);wait(Amutex);4.1進(jìn)程間的相互作用

若進(jìn)程P和Q按下述次序交替地執(zhí)行wait操作：

processP:wait(Amutex);于是Amutex==0processQ:wait(Bmutex);于是Bmutex==0processP:wait(Bmutex);于是Bmutex==-1，P阻塞。

processQ:wait(Amutex);于是Amutex==-1，Q阻塞。4.1進(jìn)程間的相互作用

對若干個(gè)臨界資源的分配采取原子操作方式，要么全部分配到進(jìn)程，要么一個(gè)也不分配

－Swait操作

Swait(S1,S2,…,Sn){if(S1≥1&&…&&Sn≥1)for(i=1;i<=n;i++)Si--;elsePlacetheprocessinthewaitingqueueassociatedwiththeSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperation.}4.1進(jìn)程間的相互作用

－Ssignal操作

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;i++)Si++;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.}

一般“信號量集”機(jī)制

一次分配多個(gè)某種資源，且當(dāng)該資源數(shù)量少于一定值時(shí)，不予分配。因此，在每次分配之前都必須測試該資源的數(shù)量是否大于測試值t

4.1進(jìn)程間的相互作用

－Swait操作

Swait(S1,t1,d1,S2,t2,d2,…,Sn,tn,dn){if(S1≥t1&&…&&Sn≥tn)for(i=1;i<=n;i++)Si=Si-di;

elsePlacetheprocessinthewaitingqueueassociatedwiththeSifoundwithSi＜ti,andsettheprogramcountofthisprocesstothebeginningofSwaitoperation.}4.1進(jìn)程間的相互作用

－Ssignal操作

Ssignal(S1,t1,d1,S2,t2,d2,…,Sn,tn,dn){for(i=1;i<=n;i++){Si=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.}}一般“信號量集”的幾種特殊情況

Swait(s,d,d)、Swait(s,1,1)、Swait(s,1,0)4.1進(jìn)程間的相互作用經(jīng)典進(jìn)程同步問題生產(chǎn)者-消費(fèi)者問題

有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將此產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在它們之間設(shè)置一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程可將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)取得一個(gè)產(chǎn)品消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步.

利用記錄型信號量解決生產(chǎn)者-消費(fèi)者問題

semaphoremutex=1,empty=n,full=0;itembuffer[n];intin=out=0;4.1進(jìn)程間的相互作用voidproducer(){while(1){…produceaniteminnextp;...wait(empty);wait(mutex);buffer[in]=nextp;in=(in+1)%n;signal(mutex);signal(full);}}voidconsumer(){while(1){...wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n;signal(mutex);signal(empty);...consumetheiteminnextc;…}}4.1進(jìn)程間的相互作用main(){cobegin{producer();consumer();}}生產(chǎn)者-消費(fèi)者問題另解semaphoremutex1=1,mutex2=1,empty=n,full=0;itembuffer[n];intin=out=0;main(){cobegin{producer();consumer();}}4.1進(jìn)程間的相互作用voidproducer(){while(1){…produceaniteminnextp;...wait(empty);wait(mutex1);buffer[in]=nextp;in=(in+1)%n;signal(mutex1);signal(full);}}voidconsumer(){while(1){...wait(full);wait(mutex2);nextc=buffer[out];out=(out+1)%n;signal(mutex2);signal(empty);...consumetheiteminnextc;…}}4.1進(jìn)程間的相互作用利用AND信號量解決生產(chǎn)者-消費(fèi)者問題semaphoremutex1=1,mutex2=1,empty=n,full=0;itembuffer[n];intin=out=0;voidproducer(){while(1){…produceaniteminnextp;...Swait(empty,mutex1);buffer[in]=nextp;in=(in+1)modn;Ssignal(mutex1,full);}}voidconsumer(){while(1){...Swait(full,mutex2);nextc=buffer[out];out=(out+1)modn;Ssignal(mutex2,empty);...consumetheiteminnextc;…}}main(){cobegin{producer();consumer();}}4.1進(jìn)程間的相互作用

讀者-寫者問題

只要求讀的進(jìn)程稱為“reader進(jìn)程”，其他進(jìn)程稱為“writer進(jìn)程”。允許多個(gè)reader進(jìn)程同時(shí)讀一個(gè)共享對象,但決不允許一個(gè)writer進(jìn)程和其他reader進(jìn)程或writer進(jìn)程同時(shí)訪問共享對象所謂讀者-寫者問題（TheReader-WriterProblem）是只保證一個(gè)writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題

4.1進(jìn)程間的相互作用利用記錄型信號量解決讀者-寫著問題readcount：正在讀的讀者數(shù)量分析：

-當(dāng)無讀者讀（readcount==0），判斷能否讀（臨界區(qū)信號量wmutex）；當(dāng)有讀者在讀（readcount>0)直接讀；

-讀者離開臨界區(qū)時(shí)，若還有讀者在讀，則直接離開，若是最后一個(gè)讀者，則喚醒等在臨界區(qū)外的一寫者

-讀者進(jìn)入臨界區(qū)和離開臨界區(qū)的代碼本身也是臨界區(qū)，不能并發(fā)，用信號量rmutex進(jìn)行管理

-在讀者等待進(jìn)入臨界區(qū)（mutmex）時(shí)，只有第一個(gè)讀者等在mtumex信號量上，其余等待在rmutex信號量上；

-寫者直接判斷能否進(jìn)入臨界區(qū)（臨界區(qū)信號量wmutex）

-寫者離開，喚醒一寫者或讀者；若喚醒的是讀者，該讀者離開rmutex的臨界區(qū)，相繼喚醒等待在rumtex上的讀者。4.1進(jìn)程間的相互作用利用記錄型信號量解決讀者-寫著問題semaphorermutex=wmutex=1;intreadcount=0;voidreader(inti){while(1){...

wait(rmutex);

if(readcount==0)wait(wmutex);readcount++;signal(rmutex);performreadoperation;wait(rmutex);

readcount--;if(readcount==0)signal(wmutex);

signal(rmutex);...}}voidwriter(intj){while(1){...

wait(wmutex);performwriteoperation;

signal(wmutex);...}}main(){cobegin{reader(1);…reader(n);writer(1);...writer(m);}}

4.1進(jìn)程間的相互作用

利用信號量集機(jī)制解決讀者-寫者問題這里的讀者-寫者問題與前面的略有不同，它增加了一條限制，即最多只允許RN個(gè)讀者同時(shí)讀。#defineRN…semaphoreL=RN,mx=1;voidreader(inti){while(1){...Swait(L,1,1,mx,1,0);

performreadoperation;Ssignal(L,1);...}}voidwriter(){while(1)

{...

Swait(mx,1,1,L,RN,0);

performwriteoperation;Ssignal(mx,1);...}}main(){cobegin{reader(1);...reader(n);writer(1);...writer(m);}}4.1進(jìn)程間的相互作用

哲學(xué)家進(jìn)餐問題

有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們共用一張圓桌，分別坐在周圍的五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子繼續(xù)思考。4.1進(jìn)程間的相互作用

解決辦法：①至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐，最終總會釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐。②僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)才允許他拿起筷子進(jìn)餐。③規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿他右邊的筷子；而偶數(shù)號哲學(xué)家則相反。4.1進(jìn)程間的相互作用

利用記錄型信號量解決哲學(xué)家進(jìn)餐問題

semaphorechopstick[5]={1,1,1,1,1};voidprocess(inti){while(1){wait(chopstick[i]);wait(chopstick[(i+1)mod5]);...eat;...signal(chopstick[i]);signal(chopstick[(i+1)mod5]);...think;}}4.1進(jìn)程間的相互作用

利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題semaphorechopstick[5]={1,1,1,1,1};voidprocess(inti){while(1){Swait(chopstick[(i+1)mod5],chopstick[i]);...eat;Ssignal(chopstick[(i+1...)mod5],chopstick[i]);...think;}}main(){cobegin{process(0);process(1);process(2);process(3);process(4);}}4.1進(jìn)程間的相互作用嗜睡的理發(fā)師問題

一個(gè)理發(fā)店由一個(gè)有N張沙發(fā)的等候室和一個(gè)放有一張理發(fā)椅的理發(fā)室組成。沒有顧客要理發(fā)時(shí)，理發(fā)師便去睡覺。當(dāng)一個(gè)顧客走進(jìn)理發(fā)店時(shí)，如果等候室的所有沙發(fā)都已經(jīng)占用，便離開理發(fā)店；否則，如果理發(fā)師正在為其他顧客理發(fā)，則該顧客就找一張空沙發(fā)坐下等待。如果理發(fā)師因無顧客正在睡覺，則由新到的顧客喚醒理發(fā)師為其理發(fā)。－解決辦法：分析顧客進(jìn)程和理發(fā)師進(jìn)程并發(fā)具體情況如下：（1）只有在理發(fā)椅空閑時(shí)，顧客才能做到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客便必須等待；只有當(dāng)理發(fā)椅上有顧客時(shí)，理發(fā)師才可以開始理發(fā)，否則他也必須等待；可通過信號量customers和barbers來控制；（2）設(shè)置一個(gè)整型變量waiting來對理發(fā)店中等待在沙發(fā)上的的顧客進(jìn)行計(jì)數(shù)（最大為沙發(fā)的數(shù)量N），該變量將被多個(gè)顧客進(jìn)程互斥地訪問并修改，可通過一個(gè)互斥信號量mutext來實(shí)現(xiàn)。4.1進(jìn)程間的相互作用semaphoreCustomers,babers,mutex;Customers=0;barbers=0;waiting=0;mutex=1;voidbarber(){while(1){wait(customers);wait(mutex);waiting=waiting-1;signal(barbers)；signal(mutex);Cut_hair();}}voidCustomer(inti){wait(mutex);if(waiting<N){ waiting=waiting+1;signal(customers);signal(mutex);wait(barbers);haveahaircut;}elsesignal(mutex);leave;}4.1進(jìn)程間的相互作用

管程機(jī)制管程的引入

為了解決信號量大量的同步操作分散，不利于管理；而且還會因同步操作的使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖，所以引入一種新的同步工具——管程信號量操作錯誤

錯誤1：將wait(s)與signal(s)顛倒

signal(mutex);criticalsectionwait(mutex);

錯誤2：將程序中的signal(mutex)誤寫為wait(mutex)wait(mutex);criticalsectionwait(mutex);4.1進(jìn)程間的相互作用

錯誤3：在程序中遺漏了wait(mutex)操作，將會使多個(gè)進(jìn)程同時(shí)活躍在臨界區(qū)；而如果遺漏了signal(mutex)操作，則將會使其他進(jìn)程無法在進(jìn)入臨界區(qū)。

管程的基本概念管程的定義

一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù).4.1進(jìn)程間的相互作用

管程的組成

由定義可知，管程由三部分組成－局部于管程的共享變量說明－對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程－對局部于管程的數(shù)據(jù)設(shè)置初值的語句管程的語法

monitormonitor-name{variabledeclarationsentryp1(...){...}entryp2(...){...}...entrypn(...){...}{initializationcode}}4.1進(jìn)程間的相互作用