第二章進程管理132進程（Process）進程間通信進程調(diào)度4線程（Thread）2.1進程(Process)2.1.1Whyprocesses?為了提高計算機系統(tǒng)中各種資源的利用率，現(xiàn)代操作系統(tǒng)廣泛采用多道程序技術（multi-programming），使多個程序同時在系統(tǒng)中存在并運行。multi-programmingWhyprocesses?(Cont.)在多道程序系統(tǒng)中，各個程序之間是并發(fā)執(zhí)行的，共享系統(tǒng)資源。CPU需要在各個運行的程序之間來回地切換，這樣的話，要想描述這些多道的并發(fā)活動過程就變得很困難。計算機程序的執(zhí)行過程Bus指令的表示操作碼操作數(shù)或地址addr1,r2,r30110100011010111addr1r2r3CPU中央處理器：CentralProcessingUnit計算機的大腦功能：執(zhí)行指令需求功能部件指令存在哪？做什么？控制單元怎么做？執(zhí)行單元速度不匹配？寄存器組控制單元（ControlUnit）能夠正確并且自動地連續(xù)執(zhí)行指令能正確并分步完成每一條指令的功能

讀取指令→分析指令→控制執(zhí)行響應并處理中斷程序計數(shù)器(ProgramCounter)指令寄存器(Ins.Register)自動地連續(xù)執(zhí)行指令正確完成每條指令

讀取指令、分析指令、

控制執(zhí)行

執(zhí)行單元（ExecutionUnit）CPU的“計算器”分為不同的功能部件，包括算術邏輯單元（ALU，+-*/）、移位器、乘法器、除法器、分支單元等來自控制單元的信號選擇不同的功能部件指令執(zhí)行周期x86CPURegistersGeneral-purposeregistersSegmentregistersEFLAGSregisterEIP(InstructionPointerregister)EAXEBXECXEDXEBPESIEDIESP310015CSDSSSESFSGSAXBXCXDX16-bit32-bitDISIBPSPALAHBLCLDLBHCHDH8715MOVAX,0040MOVDS,AXTEST[0314],24JNZ579BPOPAX...程序1POPDSMOVDX,000EMOVAH,09INT21MOVAX,4C01...程序2為此，操作系統(tǒng)設計者提出了進程的概念。硬件只有一份，如何使這兩個程序同時運行？Aprocess＝aprograminexecution一個進程應該包括：程序的代碼；程序的數(shù)據(jù)；

CPU寄存器的值，如PC，用來指示下一條將運行

的指令、通用寄存器等；

堆、棧；一組系統(tǒng)資源（如地址空間、打開的文件）總之，進程包含了正在運行的一個程序的所有

狀態(tài)信息。2.1.2什么是進程？只允許在一端插入和刪除。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點：后進先出(LIFO)棧的主要操作進棧Push出棧Pop棧(Stack)a1a3bottomtoptopa2toptop棧的用途用于暫存功能，在程序運行時保存運行上下文信息在函數(shù)調(diào)用發(fā)生時，保存被調(diào)用函數(shù)的局部變量和形參棧在哪里？平時編程時為何沒這么做？intTimes2(intvalue);voidmain(){intnumber;printf(“請輸入一個整數(shù)：”);scanf(“%d”,&number);printf(“該數(shù)的兩倍是：%d”,Times2(number));}intTimes2(intvalue){return(2*value);}mainnumber3intTimes2(intvalue);

voidmain()

{

intnumber;

printf(“請輸入一個整數(shù)：”);

scanf(“%d”,&number);

printf(“該數(shù)的兩倍是：%d”,Times2(number));

}intTimes2(intvalue)

{

return(2*value);

}mainnumber3Times2valueTimes2也得到一個棧幀,

它的參數(shù)看成局部變量intTimes2(intvalue);

voidmain()

{

intnumber;

printf(“請輸入一個整數(shù)：”);

scanf(“%d”,&number);

printf(“該數(shù)的兩倍是：%d”,Times2(number));

}intTimes2(intvalue)

{

return(2*value);

}mainnumber3Times2value“值傳遞”,把實參的值

傳給形參。3intTimes2(intvalue);

voidmain()

{

intnumber;

printf(“請輸入一個整數(shù)：”);

scanf(“%d”,&number);

printf(“該數(shù)的兩倍是：%d”,Times2(number));

}intTimes2(intvalue)

{

return(2*value);

}mainnumber36Times2函數(shù)的返回值被

放在函數(shù)的調(diào)用位置上，

然后，分配給Times2函

數(shù)的堆棧區(qū)域被釋放。swap(intx,inty){inttemp;temp=x;x=y;y=temp;}main(){

inta,b;a=4;b=7;swap(a,b);printf("%d,%d\n",a,b);}輸出結(jié)果：4，7內(nèi)存中的一塊空間，用于動態(tài)分配；在C語言中，通過malloc來申請動態(tài)內(nèi)存空間，通過free來釋放；使用不當可能導致內(nèi)存泄漏。堆(Heap)Aprocess＝aprograminexecution一個進程應該包括：程序的代碼；程序的數(shù)據(jù)；

CPU寄存器的值，如PC，用來指示下一條將運行

的指令、通用寄存器等；堆、棧；一組系統(tǒng)資源（如地址空間、打開的文件）總之，進程包含了正在運行的一個程序的所有

狀態(tài)信息。AprogramisCstatementsorcommands

靜態(tài)的；Aprocessisprogram+runningcontext

動態(tài)的.main()

{…..}A()

{…..}

PROGRAMmain()

{…..}A()

{…..}

PROCESSheap

StackAMainRegisters,PCProcess≠Program舉例有一個計算機科學家，有一天女兒過生日，想親手給女兒做一個生日蛋糕。所以他就找了一本有關做蛋糕的食譜，買了一些原料，面粉、雞蛋、糖、香料等，然后邊看邊學邊做。

食譜＝算法；原料＝數(shù)據(jù)；這時小兒子哭著跑進來，說手被蜜蜂蟄了。教授只好把蛋糕先放在一邊。他在食譜上做了個標記，把狀態(tài)信息記錄了起來。然后又去找了一本醫(yī)療手冊，查到了相關的內(nèi)容，按照上面的指令一步步地執(zhí)行。當傷口處理完之后，又回到廚房繼續(xù)做蛋糕。

CPU從一個進程（做蛋糕）切換到另一個進程（醫(yī)療

救護）。科學家＝；進程＝；CPU做蛋糕動態(tài)性：程序的運行狀態(tài)在變，PC、寄存器、

堆和棧等；獨立性：是一個獨立的實體，是計算機系統(tǒng)資

源的使用單位。每個進程在一個“虛擬

計算機”上運行，每個進程都有“自己”

的PC和內(nèi)部狀態(tài)，運行時獨立于其他

的進程（虛擬PC和物理PC）；并發(fā)性：從宏觀上看各進程是同時獨立運行的2.1.3

進程的特性四個進程在并發(fā)地運行（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）如何實現(xiàn)邏輯PC？引起進程創(chuàng)建的三個主要事件：系統(tǒng)初始化時；在一個正在運行的進程當中，執(zhí)行了

創(chuàng)建進程的系統(tǒng)調(diào)用；用戶請求創(chuàng)建一個新進程。2.1.4

進程的創(chuàng)建從技術上來說，只有一種創(chuàng)建進程的方法，即在一個已經(jīng)存在的進程（用戶進程或系統(tǒng)進程）當中，通過系統(tǒng)調(diào)用來創(chuàng)建一個新的進程。Unix：fork函數(shù)；Windows：CreateProcess函數(shù);進程的三種基本狀態(tài)：進程在生命結(jié)束前處于且僅處于三種基本狀態(tài)之一，不同系統(tǒng)設置的進程狀態(tài)數(shù)目不同。2.1.5

進程的狀態(tài)運行狀態(tài)（Running）：進程占有CPU，并在CPU上運行。處于此狀態(tài)的進程數(shù)目小于等于CPU的數(shù)目。就緒狀態(tài)（Ready）：進程已經(jīng)具備運行條件，但由于CPU忙暫時不能運行，只要分得CPU即可執(zhí)行；阻塞狀態(tài)（Blocked）：指進程因等待某種事件的發(fā)生而暫時不能運行的狀態(tài)（如I/O操作或進程同步）,此時，即使CPU空閑，該進程也不能運行。修理自行車…（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”，下同）進程的狀態(tài)及其轉(zhuǎn)換進程正常運行(未阻塞)時處于什么狀態(tài)此PPT程序處于什么狀態(tài)？是否有其他的狀態(tài)轉(zhuǎn)換？進程轉(zhuǎn)換運行-->阻塞等待I/O的結(jié)果等待某一進程提供輸入運行-->就緒運行進程用完了時間片運行進程被中斷，因為一高優(yōu)先級進程處于就緒狀態(tài)就緒-->運行調(diào)度程序選擇一個新的進程運行阻塞-->就緒當所等待的事件發(fā)生時問題：如果你要設計一個OS，怎么

樣來實現(xiàn)其中的進程機制？思考2分鐘的時間！程序＝數(shù)據(jù)結(jié)構(gòu)＋算法描述進程的數(shù)據(jù)結(jié)構(gòu)：進程控制塊（ProcessControlBlock，PCB）。

系統(tǒng)為每個進程都維護了一個PCB，用來保存與該進程有關的各種狀態(tài)信息。體檢…PCB中的主要內(nèi)容邏輯寄存器應該用什么數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)PCB？structtask_struct{...volatilelongstate;pid_tpid;unsignedlonglongtimestamp;unsignedlongrt_priority;structmm_struct*mm,*active_mm;...};Linux的進程控制塊進程的創(chuàng)建：為該進程生成一個PCB；進程的終止：回收它的PCB；進程的組織管理：通過對PCB的組織管理來實現(xiàn)；系統(tǒng)用PCB來描述進程的基本情況以及運行變化的過程，PCB是進程存在的唯一標志。PCB存放在哪？進程的狀態(tài)轉(zhuǎn)換：……？intmain(){while(1){fork();}}（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）兩個進程的狀態(tài)轉(zhuǎn)換運行

|就緒運行

|阻塞阻塞

|就緒就緒

|運行單核CPU的進程運行內(nèi)核運行切換到進程P1陷入到內(nèi)核切換到另一個（或同一個）進程陷入到內(nèi)核...P1KP2KP2KKP1P1OS內(nèi)核P2P3用戶模式內(nèi)核模式TimeP1P2P3Kernelsystemcall(userI/O)interrupt(I/Odone)interruptexceptioninterrupt(timer)waitingreadyreadyreadyreadyreadywaitingOSProcessManagementSubsystem由操作系統(tǒng)來維護一組隊列，用來表示系統(tǒng)當中所有進程的當前狀態(tài)；不同的狀態(tài)分別用不同的隊列來表示（運行隊列、就緒隊列、各種類型的阻塞隊列）；每個進程的PCB都根據(jù)它的狀態(tài)加入到相應的隊列當中，當一個進程的狀態(tài)發(fā)生變化時，它的PCB從一個狀態(tài)隊列中脫離出來，加入到另外一個隊列。2.1.6

狀態(tài)隊列就緒隊列和各種I/O設備隊列（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）如何實現(xiàn)隊列？自從60年代提出進程概念以來，在操作系統(tǒng)中一直都是以進程作為獨立運行的基本單位，直到80年代中期，人們又提出了更小的能獨立運行的基本單位線程。2.2線程(Thread)【案例】編寫一個MP3播放軟件。核心功能模塊有三個：（1）從MP3音頻文件當中讀取數(shù)據(jù)；（2）對數(shù)據(jù)進行解壓縮；（3）把解壓縮后的音頻數(shù)據(jù)播放出來。2.2.1why線程？main()

{

while(TRUE）

{Read();

Decompress();

Play();

}}Read(){…}

Decompress(){…}Play(){…}單進程的實現(xiàn)方法問題：播放出來的聲音能

否連貫？各個函數(shù)之間不是

并發(fā)執(zhí)行，影響資

源的使用效率；I/OCPUyoutube的狀態(tài)欄在線視頻播放的進度

食堂的麻辣燙程序1

main()

{

while(TRUE）

{Read();

}}Read(){…}多進程的實現(xiàn)方法問題：進程之間如何通信，共享數(shù)據(jù)？程序3

main()

{

while(TRUE）

{Play();

}}Play(){…}程序2

main()

{

while(TRUE）

{Decompress();

}}Decompress(){…}怎么來解決這些問題？需要提出一種新的實體，滿足以下特性：（1）實體之間可以并發(fā)地執(zhí)行；（2）實體之間共享相同的地址空間；這種實體就是：線程（Thread）Thread：

Asequentialexecutionstreamwithin

aprocess;Athreadofexecution;

進程當中的一條執(zhí)行流程。2.2.2

什么是線程？從兩個方面來理解進程：從資源組合的角度：進程把一組相關的

資源組合起來，構(gòu)成了一個資源平臺

（環(huán)境），包括地址空間（代碼段、數(shù)據(jù)

段）、打開的文件等各種資源；從運行的角度：代碼在這個資源平臺上的

一條執(zhí)行流程（線程）。資源平臺線程進程＝線程＋資源平臺優(yōu)點：一個進程中可以同時存在多個線程；各個線程之間可以并發(fā)地執(zhí)行；各個線程之間可以共享地址空間。線程所需的資源

addr1,r2,r3subr2,r3,r10str2,0(r1)…線程獨享線程共享線程所需的資源（續(xù)）（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）why?棧中存放的是局部變量允許遞歸調(diào)用現(xiàn)代編程語言的重要特性A(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);A:tmp=2ret=C+1StackGrowthA:tmp=1ret=exitB:ret=A+2C:ret=B+1StackPointer線程執(zhí)行時的函數(shù)調(diào)用及棧線程與進程的比較進程是資源分配單位和操作系統(tǒng)保護單位，線程

是CPU調(diào)度單位；進程擁有一個完整的資源平臺，如代碼、數(shù)據(jù)和

堆，而線程只獨享必不可少的資源如寄存器和棧線程同樣具有就緒、阻塞和執(zhí)行三種基本狀態(tài)，

同樣具有狀態(tài)之間的轉(zhuǎn)換關系；線程能減少并發(fā)執(zhí)行的時間和空間開銷；線程＝輕量級進程（lightweightprocess）下列哪些內(nèi)容是存放在線程控制塊TCB中？A、CPU寄存器的值 B、頁表指針C、棧指針 D、就緒隊列 E、段表 F、線程優(yōu)先級G、打開文件表A、C、F在一個實際的工程項目中，軟件平臺采用的是某一種實時的嵌入式操作系統(tǒng)。該項目有兩個.c源文件，如下圖所示。這兩個.c文件實現(xiàn)的功能是：在文件1.c中，任務A循環(huán)地從SOCKET中接收數(shù)據(jù)；任務B每隔100ms向SOCKET發(fā)送響應消息，而定時功能是由文件2.c中的任務C來實現(xiàn)的。任務C和任務B之間通過同步信號量進行任務間的同步。問題：分析該操作系統(tǒng)當中的“任務”的概念，它相當于是我們通常所說的進程還是線程？為什么？2.2.3

一個例子intg_nSockId; //socket標識，全局變量semIdg_synSemId;//信號量標識，全局變量voidtestInit(void) //初始化函數(shù){

創(chuàng)建SOCKTE，建立連接；//g_nSockId被賦值

/*taskSpawn函數(shù)的功能：創(chuàng)建一個任務，它的參數(shù)為：“任務名”,“優(yōu)先級”,“棧大小”,“函數(shù)名”,“函數(shù)輸入?yún)?shù)”)；*//*創(chuàng)建任務A*/taskSpawn(“tTestTskA”,50,2000,testTskA,0,……..);/*創(chuàng)建任務B*/taskSpawn(“tTestTskB”,50,2000,testTskB,0,……..);}源文件1.cvoidtestTskA(void){char*pChRxBuf;pChRxBuf=malloc(100);while(1){recv(g_nSockId,pChRxBuf,…..);……}}voidtestTskB(void){charpChTxBuf[100]=“Sendmessagebackevery100ms”;while(1){semTake(g_synSemId);send(g_nSockId,pChTxBuf,…..);}}externsemIdg_synSemId;voidtest(void){

創(chuàng)建同步信號量，并初始為空；//即使用變量g_synSemId/*創(chuàng)建任務C*/taskSpawn(“tTestTskC”,50,2000,testTskC,0…….);}voidtestTskC(void){while(1){taskDelay(100);/*延時100ms，同時放出CPU資源*/semGive(g_synSemId);}}源文件2.c2.3

進程間通信與同步進程間通信（InterProcessCommunication，IPC）：進程之間的信息交流與協(xié)調(diào)。并發(fā)進程之間的兩種關系：相互獨立：進程之間沒有任何關聯(lián)關系，僅有CPU競爭關系；相互關聯(lián)：進程之間存在著某種關聯(lián)關系（直接或間接），需要相互通信。假設在一個雙核CPU上，需執(zhí)行如下代碼片段for(k=0;k<n;k++) a[k]=b[k]*c[k]+d[k]*e[k];替代方案:CreateProcess(fn,0,n/2);CreateProcess(fn,n/2,n);fn(l,m) for(k=l;k<m;k++) a[k]=b[k]*c[k]+d[k]*e[k];并行進程需要討論的問題：進程間如何通信呢，如何來相互傳遞信息呢？當兩個或多個進程在訪問共享資源時，如何確保它們不會相互妨礙——進程互斥問題；當進程之間存在著某種依存關系時，如何來調(diào)整它們運行的先后次序——進程同步問題。生活中的例子：教室座位、兩同學相約看電影上述問題是否也適用于線程？進程間通信方式低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息）高級通信：能夠傳送任意數(shù)量的數(shù)據(jù)如何實現(xiàn)？能否共享內(nèi)存單元（全局變量或共享緩沖區(qū)）？2.3.1

進程間通信方式P1P2OS低級通信：信號量（semaphore）信號（signal）高級通信：共享內(nèi)存（sharedmemory）、消息傳遞（messagepassing）、管道（pipe）進程互斥的產(chǎn)生原因進程宏觀上并發(fā)執(zhí)行，依靠時鐘中斷來實現(xiàn)微觀上輪流執(zhí)行；訪問共享資源。2.3.2

進程間互斥【例子】兩個進程，讀－修改－寫進程1 進程2tmp1=count; tmp2=count;

tmp1++;tmp2=tmp2+2;

count=tmp1;count=tmp2;

請問：如果在這些進程執(zhí)行之前，count變量的值為1，那么它最后的結(jié)果是多少？進程1 進程2tmp1=count;(=1)

interrupt...

tmp2=count;(=1)

tmp2=tmp2+2;(=3)

count=tmp2;(=3)

tmp1++;(=2)

count=tmp1;(=2)情形1情形2進程1 進程2tmp2=count;(=1)

interrupt...

tmp1=count;(=1)

tmp1++;(=2)

count=tmp1;(=2)

tmp2=tmp2+2;(=3)

count=tmp2;(=3)

情形3進程1 進程2tmp1=count;(=1)

tmp1++;(=2)

count=tmp1;(=2)

tmp2=count;(=2)

tmp2=tmp2+2;(=4)

count=tmp2;(=4)

演示...競爭狀態(tài)（racecondition）：兩個或多個進程對同一共享數(shù)據(jù)同時進行讀寫操作，而最后的結(jié)果是不可預測的，它取決于各個進程具體運行情況。解決之道：在同一時刻，只允許一個進程訪問該共享數(shù)據(jù)，即如果當前已有一個進程正在使用該數(shù)據(jù)，那么其他進程暫時不能訪問。這就是互斥的概念。上述例子有何問題？競爭狀態(tài)問題的抽象描述把一個進程在運行過程中所做的事情分為兩類：進程內(nèi)部的計算或其他的一些事情，肯定不會

導致競爭狀態(tài)的出現(xiàn)；對共享內(nèi)存或共享文件的訪問，可能會導致競

爭狀態(tài)的出現(xiàn)。我們把完成這類事情的那段程

序稱為“臨界區(qū)”，把需要互斥訪問的共享資

源稱為“臨界資源”。如果我們能設計出某種方法，使得任何兩個進程

都不會同時出現(xiàn)在臨界區(qū)中，就可以避免競爭狀

態(tài)的出現(xiàn)。實現(xiàn)互斥訪問的四個條件任何兩個進程都不能同時進入臨界區(qū)；不能事先假定CPU的個數(shù)和運行速度；當一個進程運行在它的臨界區(qū)外面時，

不能妨礙其他的進程進入臨界區(qū)；任何一個進程進入臨界區(qū)的要求應該在

有限時間內(nèi)得到滿足。如何實現(xiàn)進程之間的互斥訪問？問題描述：兩個進程，在各自臨界區(qū)中需要對某個共享資源進行訪問。非臨界區(qū)；…臨界區(qū)；…非臨界區(qū)；進程P1非臨界區(qū)；…臨界區(qū)；…非臨界區(qū)；進程P2

進程的切換是由中斷引發(fā)的，關閉中斷后，CPU不會被分配給其他進程，其他進程無法執(zhí)行；操作系統(tǒng)內(nèi)核經(jīng)常使用這種方法來更新內(nèi)部的數(shù)據(jù)結(jié)構(gòu)（變量、鏈表等）。當一個進程進入臨界區(qū)后，關閉所有的中斷；當

它退出臨界區(qū)時，再打開中斷。2.3.3

基于關閉中斷的互斥實現(xiàn)方法1.加鎖標志位法lock的初始值為0，當一個進程想進入臨界區(qū)時，

先查看lock的值，若為1，說明已有進程在臨界區(qū)

內(nèi)，只好循環(huán)等待。等它變成了0，才可進入。每個進程的操作類似。例如，圖書館借書。while(lock);lock=1;臨界區(qū)lock=0;共享變量缺點：可能出現(xiàn)針對lock的競爭狀態(tài)問題。2.3.4

基于繁忙等待的互斥實現(xiàn)方法2.強制輪流法while(turn!=0);臨界區(qū)turn=1;非臨界區(qū)while(turn!=1);臨界區(qū)turn=0;非臨界區(qū)process0process1共享變量基本思想：每個進程嚴格地按照輪流的順序來

進入臨界區(qū)。優(yōu)點：保證在任何時刻最多只有一個進程在臨界區(qū)缺點：違反了互斥訪問四條件中的第三個條件方法3.Peterson方法當一個進程想進入臨界區(qū)時，先調(diào)用enter_region

函數(shù)，判斷是否能安全進入，不能的話等待；當它

從臨界區(qū)退出后，需調(diào)用leave_region函數(shù)，允許其

它進程進入臨界區(qū)。兩個函數(shù)的參數(shù)均為進程號。enter_region(0);臨界區(qū)leave_region(0);非臨界區(qū)enter_region(1);臨界區(qū)leave_region(1);非臨界區(qū)process0process1#defineFALSE0#defineTRUE1#defineN2 //進程的個數(shù)intturn; //輪到誰？intinterested[N]; //興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess) //process=0或1{intother; //另外一個進程的進程號

other=1-process;interested[process]=TRUE; //表明本進程感興趣

turn=process; //設置標志位

while(turn==process&&interested[other]==TRUE);}

voidleave_region(intprocess){interested[process]=FALSE; //本進程已離開臨界區(qū)}Peterson算法解決了互斥訪問的問題，而且不會相互妨礙，可以完全正常地工作。演示...小結(jié)以上的各種方法，都是基于繁忙等待(busywaiting)的策略，都可歸納為一種形式：當一個進程想要進入它的臨界區(qū)時，首先檢查一下是否允許它進入，若允許，就直接進入了；若不允許，就在那里循環(huán)地等待，一直等到允許它進入（如何使用？）。缺點：1）浪費CPU時間；2）可能導致預料之外的結(jié)果（如：一個低優(yōu)先級進程位于臨界區(qū)中，這時有一個高優(yōu)先級的進程也試圖進入臨界區(qū)）一個低優(yōu)先級的進程正在臨界區(qū)中；另一個高優(yōu)先級的進程就緒了；調(diào)度器把CPU分配給高優(yōu)先級的進程；該進程也想進入臨界區(qū)；高優(yōu)先級進程將會循環(huán)等待，等待低優(yōu)先級進程退出臨界區(qū)；低優(yōu)先級進程無法獲得CPU，無法離開臨界區(qū)。怎么辦？解決之道：當一個進程無法進入臨界區(qū)時，應該被阻塞起來（sleep）；當一個進程離開臨界區(qū)時，需要去喚醒（wakeup）被阻塞的進程；克服了繁忙等待方法的兩個缺點（浪費CPU時間、可能死鎖）?，F(xiàn)有的進程互斥問題形式：兩個或多個進程都想進入各自的臨界區(qū)，但在任何時刻，只允許一個進程進入臨界區(qū)。新的進程互斥問題形式：兩個或多個進程都想進入各自的臨界區(qū)，但在任何時刻，只允許N個進程同時進入臨界區(qū)（N

1）。如何解決？1965年由著名的荷蘭計算機科學家Dijkstra提出，

其基本思路是用一種新的變量類型（semaphore）

來記錄當前可用資源的數(shù)量。semaphore的取值可正可負，正數(shù)表示當前空閑資源的數(shù)量，負數(shù)的絕對值表示正在等待進入臨界區(qū)的進程個數(shù)。信號量是由操作系統(tǒng)來維護的，用戶進程只能通

過初始化和兩個標準原語（P、V原語）來訪問。

初始化可指定一個非負整數(shù)，即空閑資源總數(shù)。2.3.5

信號量（Semaphore）

P、V原語包含有進程的阻塞和喚醒機制，因此

在進程等待進入臨界區(qū)時不會浪費CPU時間；P原語：申請一個空閑資源（把信號量減1），若成功，則退出；若失敗，則該進程被阻塞；V原語：釋放一個被占用的資源（把信號量加1），若發(fā)現(xiàn)有被阻塞的進程，則選擇一個喚醒之。Value=2Value=1Value=0Value=1Value=0Value=2信號量和P、V原語的實現(xiàn)信號量結(jié)構(gòu)體類型的定義typedefstruct

{intcount; //計數(shù)變量

structPCB*queue; //進程等待隊列

}semaphore;P原語：申請一個資源P(semaphoreS)

{--S.count; //表示申請一個資源;if(S.count<0) //表示沒有空閑資源;{

該進程進入等待隊列S.queue末尾;

阻塞該進程;

調(diào)用進程調(diào)度器；//OSSched()}

}

V原語：釋放一個資源V(semaphoreS)

{++S.count; //表示釋放一個資源;if(S.count<=0) //表示有進程被阻塞;{

從等待隊列S.queue中取出一個進程;

把該進程改為就緒狀態(tài)，插入就緒隊列

}

}WindowsCreateSemaphore（創(chuàng)建信號量）WaitForSingleObject（P操作）ReleaseSemaphore（V操作）

COS-IIosSemCreate（創(chuàng)建信號量）osSemPend（P操作）osSemPost（V操作）設與某資源相關聯(lián)的信號量初值為3，當前值為1，若M表示該資源的可用個數(shù)，N表示等待該資源的進程個數(shù)，則M，N分別是（）A、0，1B、1，0C、1，2D、2，0B利用信號量來實現(xiàn)進程互斥intcount; //共享變量（臨界資源）semaphoremutex；//互斥信號量，初始化為??非臨界區(qū)P(mutex);臨界區(qū)V(mutex);非臨界區(qū)P1非臨界區(qū)P(mutex);臨界區(qū)V(mutex);非臨界區(qū)P2非臨界區(qū)P(mutex);臨界區(qū)V(mutex);非臨界區(qū)P3演示...進程間的同步是指多個進程中發(fā)生的事件存在某種時序關系，因此在各個進程之間必須協(xié)同合作，相互配合，使各個進程按一定的速度執(zhí)行，以共同完成某一項任務。同步：合作。 互斥：競爭。只考慮基于信號量的同步問題。2.3.6

進程間同步如何實現(xiàn)A先執(zhí)行，然后B執(zhí)行？A；V(S);進程P1P(S);

B；進程P2配對先后S初始值為0….A(先)；….進程P1信號量S初始值為？？….B(后)；….進程P2【例子】共享緩沖區(qū)的合作進程的同步設有一個緩沖區(qū)buffer，大小為一個字節(jié)。Compute進程不斷產(chǎn)生字符，送buffer，Print進程從buffer中取出字符打印。如不加控制，會出現(xiàn)多種打印結(jié)果，這取決于這兩個進程運行的相對速度。在這眾多的打印結(jié)果中，只有Compute和Print進程的運行剛好匹配的一種是正確的，其它均為錯誤。while(計算未完成){

得到一個計算結(jié)果;

將數(shù)據(jù)送到緩沖區(qū)；}Computewhile(打印未完成){

從緩沖區(qū)中取一數(shù)據(jù)；

打印該數(shù)據(jù)；}PrintbufferComputePrint正確：CPCP錯誤：CCPP錯誤：CPPC“ABCD…”1.問題分析，弄清楚同步關系：要保證打印結(jié)果的正確，Compute和Print進程必須遵循以下同步規(guī)則：當Compute把數(shù)據(jù)送入buffer后，Print才能從

buffer中取，否則它必須等待（先存后?。划擯rint從buffer取走數(shù)據(jù)后，Compute才能將

新數(shù)據(jù)送buffer，否則也須等待（先取后存）computeprintcomputeprintcomputeprintt1t0t2t3t4t5t6討論一個信號量是否可行？semaphoreBufferNum；//緩沖區(qū)是否有空間，初值1semaphoreDataNum;//是否有數(shù)據(jù)需打印，初值02.設置信號量，說明含義、初值。3.寫出程序描述。while(計算未完成){

得到一個計算結(jié)果;P(BufferNum);

將數(shù)據(jù)送到緩沖區(qū)；

V(DataNum);}Computewhile(打印未完成){P(DataNum);

從緩沖區(qū)中取一數(shù)據(jù)；

V(BufferNum);

打印該數(shù)據(jù)；}Print生產(chǎn)者—消費者問題哲學家就餐問題讀者－寫者問題用信號量來解決，主要問題：如何選擇信號量，如何安排P、V原語的順序。2.3.7

經(jīng)典的IPC問題

生產(chǎn)者—消費者問題兩個進程（生產(chǎn)者和消費者）共享一個公有的、固定大小的緩沖區(qū)，生產(chǎn)者不斷地制造產(chǎn)品，并把它放入緩沖區(qū)，而消費者不斷地把產(chǎn)品取出來，并且使用它。要求這兩個進程相互協(xié)調(diào)，正確地完成各自的工作。12345678生產(chǎn)者生產(chǎn)—消費者問題消費方向生產(chǎn)方向消費者問題分析對于生產(chǎn)者進程：制造一個產(chǎn)品，當要送入緩沖區(qū)

時，要檢查緩沖區(qū)是否有空位，若是，才可將產(chǎn)品

送入緩沖區(qū)，并在必要時通知消費者；否則等待；對于消費者進程：當它去取產(chǎn)品時，先要檢查緩沖

區(qū)中是否有產(chǎn)品可取，若有，則取走一個，并在必

要時通知生產(chǎn)者；否則等待。這種相互等待，并互通信息就是典型的進程同步。同時，緩沖區(qū)是個臨界資源，因此，各個進程在

使用緩沖區(qū)的時候，還有一個互斥的問題。semaphoreBufferNum; //空閑的緩沖區(qū)個數(shù)，

//初值為NsemaphoreProductNum; //緩沖區(qū)當中的產(chǎn)品個

//數(shù)，初值為0semaphoreMutex; //用于互斥訪問的信號

//量，初值為1信號量的定義main()

{

cobegin

producer();

consumer();

coend

}voidproducer(void)

{

intitem;while(TRUE){

item=produce_item(); //制造一個產(chǎn)品

P(BufferNum); //是否有空閑緩沖區(qū)

P(Mutex); //進入臨界區(qū)

insert_item(item); //產(chǎn)品放入緩沖區(qū)

V(Mutex); //離開臨界區(qū)

V(ProductNum); //新增了一個產(chǎn)品

}}生產(chǎn)者進程while(計算未完成){

得到一個計算結(jié)果;P(BufferNum);

將數(shù)據(jù)送到緩沖區(qū)；

V(DataNum);}Computevoidconsumer(void)

{

intitem;while(TRUE){

P(ProductNum); //緩沖區(qū)中有無產(chǎn)品

P(Mutex); //進入臨界區(qū)

item=remove_item() //從緩沖區(qū)取產(chǎn)品

V(Mutex); //離開臨界區(qū)

V(BufferNum); //新增一個空閑緩沖區(qū)

consume_item(item); //使用該產(chǎn)品

}}消費者進程while(打印未完成){P(DataNum);

從緩沖區(qū)中取一數(shù)據(jù)；

V(BufferNum);

打印該數(shù)據(jù)；}PrintWhy互斥？voidproducer(void)

{

intitem;while(TRUE){

item=produce_item();

P(Mutex);

P(BufferNum);

insert_item(item);

V(Mutex);

V(ProductNum);

}}能否調(diào)整P操作的順序？voidconsumer(void)

{

intitem;while(TRUE){

P(ProductNum);

P(Mutex);

item=remove_item()

V(Mutex);

V(BufferNum);

consume_item(item);

}}在多道系統(tǒng)當中，往往有多個進程同時在內(nèi)存中

運行。在任何時刻，一個進程只可能是以下三種

狀態(tài)之一：運行狀態(tài)：該進程正在CPU上運行，每個CPU

上最多只能有一個進程在運行；就緒狀態(tài)：進程已經(jīng)就緒，隨時可以運行；阻塞狀態(tài)：如在某個信號量上被阻塞，等待I/O與此相對應，操作系統(tǒng)會維護相應的狀態(tài)隊列。2.4

進程調(diào)度就緒隊列和各種I/O設備隊列（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）選擇誰去運行？調(diào)度器（Scheduler）if(readyProcesses(PCBs)){ nextPCB=selectProcess(PCBs); run(nextPCB);}else{ run_idle_process();}1.要解決的問題WHEN：何時分配CPU—調(diào)度的時機WHAT：按什么原則分配CPU—調(diào)度算法HOW：如何分配CPU—進程的上下文切換2.4.1

關于調(diào)度的若干問題2.進程的行為進程的執(zhí)行過程：CPU執(zhí)行（CPUburst）和等待I/O操作（I/Oburst）交替進行。fpResult=fopen(szResult,"w");if(fpResult==NULL)printf(“can’topenfile");flag=0;while(1){ str1[0]=0; fgets(str1,MAX_LEN,fpOut); if(str1[0]==0) { str2[0]=0; fgets(str2,MAX_LEN,fpStd); if(str2[0]==0) { flag=1; break; } } ...

CPU繁忙（CPU-bound）的進程：大部分時間

處于運行和就緒狀態(tài)；

I/O繁忙（I/O-bound）的進程：大部分時間處

于阻塞狀態(tài)。CPU繁忙與I/O繁忙CPU繁忙I/O繁忙while(ch!=EOF){putchar(ch);ch=fgetc(fp);}WORD文字編輯器視頻播放軟件CPU繁忙還是I/O繁忙？電子海圖的顯示性能優(yōu)化海圖顯示主要有數(shù)據(jù)讀取和畫圖兩個主要步驟。數(shù)據(jù)讀取，顯然是屬于I/O操作，而海圖繪畫的主要過程是在內(nèi)存中進行，屬于CPU繁忙。讓這兩個步驟分別在兩個線程中進行，就能夠有效地利用CPU和外