2.1進程的基本概念2.2進程管理2.3進程調度2.4進程間的同步與互斥2.5進程通訊2.6死鎖第二章進程管理2.1進程的基本概念程序的順序執(zhí)行和并發(fā)執(zhí)行順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機系統(tǒng)；

現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。順序執(zhí)行的特征順序性

封閉性

可再現(xiàn)性

例：程序段

read(disk,&a,4);/*從磁盤讀a*/read(tape,&b,4);/*從帶讀b*/c=a+b;

printf(“c=%f\n”,c);程序的順序執(zhí)行

是一個有向無環(huán)圖，圖中每個結點表示一個語句、一段程序或一個進程1.前驅圖有向邊<Vi,Vj>表示Vj僅在

Vi執(zhí)行完后才能開始執(zhí)行

S1S3S7S6S4S2S5S2S1S3前驅圖有回路的前驅圖程序并行性表示類Pascal的并行語句。COBEGINs1；s2；…；snCOENDCOBEGIN/COEND相當于一個括號，表示其中的所有語句s1,s2,…sn可并行執(zhí)行。2.并行語言并發(fā)執(zhí)行的條件（Bernstein條件）程序P(i)針對變量的讀集R(i)和寫集W(i)條件：任意兩個程序P(i)和P(j)，同時滿足：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;1966年，由Bernstein給出并發(fā)執(zhí)行的條件。前兩條保證一個程序的兩次讀之間數(shù)據(jù)不變化；最后一條保證寫的結果不丟掉。例：s1:read(disk,&a,4);/*從磁盤讀a*/s2:read(tape,&b,4);/*從帶讀b*/s3:

c=a+b;R(s1)=W(s1)={a}s1和s2可并發(fā)，s2和s3不可并發(fā)多道程序系統(tǒng)：資源共享；程序的并發(fā)運行例：intN=0;/*全局變量*/

cobegin

progamA{while(1){…..N++;…..}}progamB{while(1){…..

printf(“N=%d\n”,N);N=0;…..}}coend并發(fā)執(zhí)行的特征間斷(異步)性：“運行－暫停－運行”；并發(fā)程序之間依賴相互、相互制約不可再現(xiàn)性并發(fā)程序與它的執(zhí)行過程并非一一對應進程(PROCESS)的概念一個具有一定獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程。是系統(tǒng)進行資源分配和調度的一個獨立單位進程的定義是并發(fā)程序的一次執(zhí)行過程，它由一個動作序列組成，每個動作是在某數(shù)據(jù)集上執(zhí)行一段程序，整個活動的結果是提供一種系統(tǒng)或用戶功能。動態(tài)性：產(chǎn)生、執(zhí)行、暫停、消亡。有一個生存期獨立性：是系統(tǒng)進行資源分配和調度的獨立單位，是能獨立運行的基本單位并發(fā)性：程序在建立進程后并發(fā)運行進程的特征

進程＝程序＋數(shù)據(jù)＋PCB(進程控制塊，processcontrolblock)進程是動態(tài)的，程序是靜態(tài)的進程是暫時的，程序的永久的進程與程序的組成不同進程與程序的區(qū)別進程與程序的聯(lián)系通過多次執(zhí)行，一個程序可對應多個進程；通過調用關系，一個進程可包括多個程序。運行狀態(tài)：進程分配到必要的資源，在CPU上執(zhí)行時的狀態(tài)就緒狀態(tài)：進程分配到必要的資源，還沒獲得在CPU上執(zhí)行的狀態(tài)阻塞狀態(tài)（等待狀態(tài)）：進程的執(zhí)行由于本身不具備運行條件而受到阻塞，處于暫停狀態(tài)進程的狀態(tài)2.2進程管理三種基本調度狀態(tài)RunningReadyBlocked等待事件

(系統(tǒng)服務請求，如請求I/O))被調度或分派時間片用完事件發(fā)生掛起：強迫進程釋放分配到的資源，將進程調出到外存活動：未被掛起的就緒和阻塞狀態(tài)稱為活動就緒和活動阻塞靜止：被掛起的就緒和阻塞狀態(tài)稱為靜止就緒和靜止阻塞進程的狀態(tài)細分的進程調度狀態(tài)ReadyaRunningBlockedaBlockedsReadyswakeup(喚醒)事件發(fā)生掛起suspend時間片完被調度schoduler解掛

active掛起

suspend解掛

active掛起

suspend等待事件

sleep事件發(fā)生wakeup(喚醒)圖：具有掛起功能的進程狀態(tài)變化進程的狀態(tài)轉換：三狀態(tài)進程模型程序：描述進程要完成的功能數(shù)據(jù)集合：包含程序運行所需的數(shù)據(jù)和工作區(qū)進程控制塊（PCB）：包含進程的描述信息和控制信息，是進程動態(tài)特性的反映進程的物理結構程序和數(shù)據(jù)集合是進程的實體進程控制塊是進程存在的唯一標志進程控制塊（PCB,processcontrolblock)進程控制塊是由OS維護的用來記錄進程相關信息的一塊內存。進程標識符：進程標識符(processID)（內部標識符）：唯一，通常是一個整數(shù)；進程名（外部標識符）：不唯一，由字母數(shù)字組成；位置信息：指出進程的程序和數(shù)據(jù)在內存和外存中的物理位置現(xiàn)場信息：寄存器值（通用、程序計數(shù)器PC、狀態(tài)PSW，地址包括棧指針）狀態(tài)信息：進程現(xiàn)行狀態(tài)進程優(yōu)先級：進程使用CPU的優(yōu)先級別資源清單：已分配到的資源等同步與互斥機構進程通訊機制隊列指針家族聯(lián)系資源占用信息：虛擬地址空間的現(xiàn)狀、打開文件列表進程控制塊的內容順序表：將所有PCB連續(xù)存放在內存。要經(jīng)常掃描整個表索引表：同一狀態(tài)的PCB建立一個index表（由index指向PCB），多個狀態(tài)對應多個不同的index表各狀態(tài)形成不同的索引表：就緒索引表、阻塞索引表鏈表：同一狀態(tài)的進程的PCB成一鏈表，多個狀態(tài)對應多個不同的鏈表各狀態(tài)的形成不同的鏈表：就緒鏈表、阻塞鏈表PCB的組織方式進程控制進程控制的功能完成進程狀態(tài)的轉換。原語(primitive)：由若干條指令構成的“原子操作(atomicoperation)”過程，作為一個整體而不可分割－－要么全都完成，要么全都不做。許多系統(tǒng)調用就是原語。2.3進程調度作業(yè)狀態(tài)及其轉換提交狀態(tài)后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤的專用區(qū)（后備作業(yè)區(qū)）中，等待運行執(zhí)行狀態(tài)：被作業(yè)調度程序選中，分配了必要資源，建立了PCB，進入進程的就緒狀態(tài)，等待運行完成狀態(tài)：作業(yè)完成任務，釋放資源調度的層次作業(yè)調度（高級調度）：選擇作業(yè)，調入內存，分配資源建立進程，將PCB插入就緒進程隊列進程調度（低級調度）：將CPU分配給進程，進行進程間切換，運行被調度進程中級調度：進程映象在內存和盤交換區(qū)間的對換操作。防止死鎖。作業(yè)從提交到完成，要經(jīng)歷三級調度進程調度算法非剝奪搶占方式：一旦進程占用CPU就一直運行，直到終止或阻塞剝奪搶占方式：系統(tǒng)強行剝奪已分配給現(xiàn)運行進程的CPU，使其進入就緒進程隊列按占用處理器的方式，進程調度有兩種方式：進程調度方式設計目標：目標不同，系統(tǒng)的要求不同CPU利用率：吞吐量：系統(tǒng)在單位時間內完成的作業(yè)數(shù)目周轉時間：從作業(yè)提交到完成的時間間隔等待時間：進程在就緒進程隊列中的等待時間，通常用來衡量調度程序的性能響應時間：從向系統(tǒng)發(fā)出請求到系統(tǒng)首次開始響應的時間間隔資源利用率：最大限度地使各種資源并行操作合理的系統(tǒng)開銷調度算法性能標準按先進先出組織就緒狀態(tài)的進程隊列總是把CPU分配給就緒狀態(tài)的進程隊列的隊首進程最簡單的進程調度算法屬于非剝奪搶占方式進程調度算法先來先服務算法（FCFS）例：進程P1,P2,P3，它們的CPU運行時間為3，3，24個單位時間FCFS特點：僅考慮作業(yè)提交時間，未考慮系統(tǒng)資源使用率（1）P3,P1,P2順序進入就緒進程隊列，幾乎同時到達平均周轉時間=(24+27+30)/3=27（2）P1,P2,P3順序進入就緒進程隊列，幾乎同時到達平均周轉時間=(3+6+30)/3=13要求就緒狀態(tài)的進程隊列中每個進程有下一個CPU運行期的時間值把CPU分配給就緒狀態(tài)的進程隊列中下一個CPU運行期最短的進程短者優(yōu)先的原則進程調度算法短CPU運行期優(yōu)先算法（SCBF）優(yōu)點：等待時間最小，系統(tǒng)吞吐量高缺點：已知進程的CPU運行時間，很難實現(xiàn)例：進程P1,P2,P3,P4，它們的CPU運行時間為6，3，8，7個單位時間，P3,P1,P2,P4順序進入就緒進程隊列，幾乎同時到達

FCFS算法：平均周轉時間=(8+14+17+24)/4=15.75SCBF算法：平均周轉時間=(3+9+16+24)/4=13系統(tǒng)自動按一定原則為每個進程規(guī)定一個調度優(yōu)先權把CPU分配給就緒狀態(tài)的進程隊列具有最高優(yōu)先權的進程常用的調度算法進程調度算法優(yōu)先權調度算法確定優(yōu)先權的方法：靜態(tài)優(yōu)先權法動態(tài)優(yōu)先權法進程創(chuàng)建時確定其優(yōu)先權，運行期間不改變按進程類型確定按作業(yè)要求的資源類型和數(shù)量確定按作業(yè)提交的時間順序確定按用戶類型和要求確定靜態(tài)優(yōu)先權法優(yōu)點：簡單易實現(xiàn)，系統(tǒng)開銷小缺點：未能反映進程的動態(tài)性進程創(chuàng)建時賦一個優(yōu)先權初值，運行期間動態(tài)調整其權值動態(tài)優(yōu)先權法特點：防止一個進程壟斷或長期等待CPU時間片輪轉算法簡單輪轉法就緒狀態(tài)的所有進程按FCFS組成隊列首先CPU分給隊首的進程，規(guī)定一個時間片就緒隊列中的所有進程輪流使用CPUT=NqN就緒隊列中進程數(shù)，T為系統(tǒng)響應時間，時間片為q多隊列輪轉法常用雙就緒狀態(tài)進程隊列輪轉法首先對前臺就緒進程隊列以時間片輪轉法調度，當前臺就緒進程隊列為空時，才對后臺就緒進程隊列按FCFS算法調度按調度級別設置多個就緒進程隊列按級別劃分時間片各級就緒進程隊列按FIFO組織，F(xiàn)CFS調度最后一級按循環(huán)輪轉方式組織調度多級反饋隊列調度算法2.4進程間的同步與互斥臨界資源進程間的制約關系間接制約：進行競爭－－獨占分配到的部分或全部共享資源，“互斥”直接制約：進行協(xié)作－－等待來自其他進程的信息，“同步”系統(tǒng)中一次僅允許一個進程使用的一類資源。打印機，卡片輸入機，磁帶機、共享變量等。互斥：多個進程不能同時使用同一個資源；死鎖：多個進程互不相讓，都得不到足夠的資源；饑餓：一個進程一直得不到資源（其他進程可能輪流占用資源）共享變量的修改沖突例：民航售票系統(tǒng)，n個售票處

/*ProcessPi,i=1,2,...,n*/…../*按訂票要求找到共享數(shù)據(jù)x[k]*//*x[k]存放某月某日某次航班的現(xiàn)有票數(shù)*/R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}else

顯示“票已售完”；臨界區(qū)臨界區(qū)的訪問過程臨界區(qū)：訪問臨界資源的程序段。同類臨界區(qū)：對同一臨界資源進行操作的程序段。臨界區(qū)(criticalsection)：進程中訪問臨界資源的一段代碼。進入?yún)^(qū)(entrysection)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。退出區(qū)(exitsection)剩余區(qū)(remaindersection)：代碼中的其余部分。空閑則入：其他進程均不處于臨界區(qū)；忙則等待：已有進程處于其臨界區(qū)；有限等待：等待進入臨界區(qū)的進程不能"死等"；讓權等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉換到阻塞狀態(tài)）互斥應遵循的準則有兩個進程Pi,Pj，其中的Pi設立一個公用整型變量turn：描述允許進入臨界區(qū)的進程標識進程互斥的軟件方法算法1：單標志互斥算法缺點：強制輪流進入臨界區(qū)，沒有考慮進程的實際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；設立一個標志數(shù)組flag[]：描述進程是否要求進入臨界區(qū)或已在臨界區(qū)，初值均為FALSEturn=j;描述可進入的進程（同時修改標志時）在進入?yún)^(qū)先修改、后檢查、后修改者等待算法2：雙標志

intflag[2]={0,0};

intturn=0;/*進程pi的結構*/while(1){

flag[i]=1;

while(flag[j]){

if(turn==j){

flag[i]=0;

while(turn==j);

flag[i]=1;}

/*進入臨界區(qū)*/criticalsection/*退出臨界區(qū)]*/turn=j;

flag[i]=0;

remaindersection}每一類臨界資源設置一把鎖lock。lock表示資源的兩種狀態(tài)：TRUE表示正被占用（鎖關狀態(tài)）；FALSE表示空閑（鎖開狀態(tài)）進程互斥的鎖操作方法加鎖操作開鎖操作執(zhí)行臨界區(qū)程序不能實現(xiàn)所有的同類臨界區(qū)互斥；臨界區(qū)太長時，降低了中斷響應速度；擴大了互斥范圍；加鎖時CPU不斷測試，處于忙等待。優(yōu)點：簡單、可靠鎖操作方法用開、關中斷實現(xiàn)鎖操作關中斷開中斷執(zhí)行臨界區(qū)程序缺點：信號量表示臨界資源的實體，是一個數(shù)據(jù)結構，其值僅能由P、V操作來改變。信號量(semaphore)阻塞等待信號量數(shù)據(jù)結構：typedef

struct{

intvalue;/*信號量的值*/PCB*ptr_of_semque;}semaphore;

PCB:進程控制塊的數(shù)據(jù)類型

ptr_of_semque：指向等待使用該信號量的進程隊列的隊首Value:指定一個非負整數(shù)值，表示空閑資源總數(shù)－－若為非負值表示當前的空閑資源數(shù)，若為負值其絕對值表示當前等待臨界區(qū)的進程數(shù)ptr_of_semque：初值為空信號量初始化：P原語wait(s)externPCB*curproc;voidp(s)semaphore*s;{s->value--;

if(s->value<0){

Insert(curproc,s->ptr_of_semque);

Block(curproc);}}V原語通常喚醒進程等待隊列中的頭一個進程V原語signal(s)voidV(s)semaphore*s;{PCB*pcb_ptr;s->value++;

if(s->value<=0){

pcb_ptr=Remove(s->prt_of_semque);

Wakeup(pcb_ptr);/*進程狀態(tài)置為活動就緒*/}}為臨界資源設置一個互斥信號量mutex(MUTualExclusion)，其初值為1；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語，P、V原語不能次序錯誤、重復或遺漏利用信號量實現(xiàn)互斥信號量實現(xiàn)互斥模型：

semaphoremutex={1,NULL};

cobegin

programpi{while(1){

P(&mutex)；

criticalsectionforpi;/*進程pi臨界區(qū)*/

V(&mutex)；

remaindersectionforpi;}}

coend解決共享變量的修改沖突例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobegin

programpi{………

P(&mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

V(&mutex)；

輸出一張機票；

}

else{

V(&mutex)；

顯示“票已售完”；

}}coend

設置一個同步信號量proceed1，其初值為0利用信號量實現(xiàn)同步

semaphoreproceed1={0,NULL};

cobegin

進程p1………P(&proceed1)；

………

進程p2………V(&proceed1)；

……….

coend

例：一輛公共汽車上，司機和售票員進程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};

cobegin

programdrive{while(1){driving;/*正常行車*/stopping;

V(&conductor_sem)；/*喚醒開門*/

P(&drive_sem)；/*等待關門*/startacar;}}

programconductor{while(1){selltickets;/*售票*/

P(&conductor_sem)；/*等待停車*/openthedoor;closethedoor;

V(&drive_sem)；/*喚醒司機開車*/}}coend

1.生產(chǎn)者－消費者問題(theproducer-consumerproblem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。經(jīng)典應用示例采用信號量機制：full是"滿"數(shù)目，初值為0，empty是"空"數(shù)目，初值為N。full+empty=Nmutex用于訪問緩沖區(qū)時的互斥，初值是1每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥――否則可能死鎖(為什么？)

＃defineN100

＃defineMAXLEN80

typedef

struct{

intnum;chararray[MAXLEN];}Message;semaphoremutex={1,NULL};semaphoreempty={N,NULL};

semaphorefull={0,NULL};Messagebuffers[N];

int

p_index=0,c_index=0;

cobegin

programproduceri{Messagep_puf;while(1){produceamessageinp_buf;算法：

P(&empty)；

P(&mutex)；

memcpy((char*)&buffers[p_index],(char*)&p_buf,sizeof(Message));

p_index=(p_index+1)%N;

V(&mutex)；

V(&full)；}}programconsumerj{Messagec_buf;while(1){

P(&full)；

P(&mutex)；

memcpy((char*)&c_buf,(char*)&buffers[c_index],sizeof(Message));

c_index=(c_index+1)%N;

V(&mutex)；

V(&empty)；

consumethemessageinc_buf;}}coend

2.讀者－寫者問題(thereaders-writersproblem)問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個“讀－寫”互斥，“寫－寫”互斥，"讀－讀"允許采用信號量機制：rwmutex表示"允許寫"，初值是1。公共變量Readcount表示“正在讀”的進程數(shù)，初值是0；rmutex表示讀者對Readcount的互斥操作，初值是1。

semaphorerwmutex={1,NULL},rmutex

={1,NULL};

int

readcount=0;

cobegin

programreaderi{

P(&rmutex)；

readcount++;

if(readcount==1)

P(&rwmutex)；

V(&rmutex)；

readdata;

P(&rmutex)；

readcount--;

if(readcount==0)

V(&rwmutex)；

V(&rmutex)；}算法：programwriterj{

P(&rwmutex)；

writeorupdatedata;

V(&rwmutex)；}coend

寫者長期阻塞寫者優(yōu)先算法：cobegin

programreaderi{

P(&rwmutex)；

P(&rsem)；

V(&rwmutex)；

readdata;

V(&rsem)；}programwriterj{

inti;

P(&rwmutex)；

for(i=1;i<=10;i++)

P(&rsem)；

writeorupdatedata;for(i=1;i<=10;i++)V(&rsem)；

V(&rmutex)；}coend

semaphorerwmutex={1,NULL},rsem={10,NULL};低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進程互斥和同步所采用的信號量和管程機制。優(yōu)點是速度快。缺點是：傳送信息量小、效率低編程復雜高級通信：能夠傳送任意數(shù)量的數(shù)據(jù)，包括三類：消息緩沖、管道、共享存儲區(qū)。2.5進程間通信進程間通信的類型直接通信和間接通信直接通信：信息直接傳遞給接收方，如管道。在發(fā)送時，指定接收方的地址或標識，也可以指定多個接收方或廣播式地址；在接收時，允許接收來自任意發(fā)送方的消息，并在讀出消息的同時獲取發(fā)送方的地址。間接通信：借助于收發(fā)雙方進程之外的共享數(shù)據(jù)結構作為通信中轉，如消息隊列。管道：用于連接一個讀進程和一個寫進程，以實現(xiàn)它們之間通信的共享文件（pipe文件）常用于命令行所指定的輸入輸出重定向和管道命令。在使用管道前要建立相應的管道，然后才可使用。管道(pipe)通訊無名管道：用于父子進程或子進程間通信有名管道：用于父進程間通信（又稱FIFO通信）例：MSDOS命令

DIR|MORE進程間數(shù)據(jù)交換以消息為單位應用系統(tǒng)使用系統(tǒng)提供的一組通信原語來實現(xiàn)通信消息的發(fā)送不需要接收方準備好，隨時可發(fā)送。消息(message)緩沖通訊諸進程通過共享存儲區(qū)中的數(shù)據(jù)的讀或寫來實現(xiàn)通信應用程序實現(xiàn)對共享存儲區(qū)訪問的互斥與同步是進程間通信最有效的機制相當于內存，可以任意讀寫和使用任意數(shù)據(jù)結構，需要進程互斥和同步的輔助來確保數(shù)據(jù)一致性共享存儲區(qū)(sharedmemory)2.6死鎖(DEADLOCK)死鎖：當一個進程提出使用某資源的請求后，使系統(tǒng)中的一些進程處于無休止的阻塞狀