第三篇4：進程管理

計算機系統(tǒng)平臺——

第4章操作系統(tǒng)的內(nèi)部實現(xiàn)機制王琳ise_wanglin@

已講的內(nèi)容第一篇：計算機操作平臺（操作系統(tǒng)）第二篇：計算機硬件平臺（計算機硬件組成、信息表示）問題：什么是操作系統(tǒng)?操作系統(tǒng)的作用是什么?部分操作系統(tǒng)部分操作系統(tǒng)操作系統(tǒng)的層次結(jié)構(gòu)操作系統(tǒng)抽象CPUMemdiskI/OOperatingSystemprocessaddressspacefile操作系統(tǒng)定義OSisacontrolprogramApieceofsystemsoftwareControlsexecutionofprogramstopreventerrorsandimproperuseofthecomputerExecuteuserprogramsandmakesolvinguserproblemseasierMakethecomputersystemconvenienttouseOSisaresourceallocatorAninterfacebetweenapplicationsandhardwareManagesallresourcesDecidesbetweenconflictingrequestsforefficientandfairresourceuseUsethecomputerhardwareinanefficientmannerNouniversallyaccepteddefinition操作系統(tǒng)定義(Cont.)?FunctionsofOSserviceproviderresourcemanagerextendedmachinevirtualmachine操作系統(tǒng)作為服務(wù)提供者ServiceproviderProvidestandardfacilitiesFilesystemStandardlibrariesGUIWindowsystemInterface……操作系統(tǒng)作為資源管理者ResponsibleformanagingresourcesFunctionssamewayasordinarycomputersoftwareItisaprogramthatisexecutedOperatingsystemrelinquishescontroloftheprocessor操作系統(tǒng)作為擴展機器Hardware+interruptsVirtualMemProcess+primitivesComm.PrmtvsFilesys.DevicesDirectoriesShellUserProcessesWebClientsApplicationClientsWebServerApplicationServer操作系統(tǒng)作為虛擬機器(a)Nonvirtualmachine(b)virtualmachineNon-virtualMachineVirtualMachine進程的管理進程概念的引入進程的狀態(tài)進程的調(diào)度進程間的通信線程進程概念的引入什么是程序？進程概念的引入什么是進程操作系統(tǒng)抽象概念里的程序運行操作系統(tǒng)的基本執(zhí)行單元進程是程序的運行（實體）程序=靜態(tài)文件(image)進程=程序執(zhí)行=程序+執(zhí)行狀態(tài).不同進程可以運行同一個程序的不同實例同一程序，不同進程多道程序系統(tǒng)下，多個執(zhí)行進程執(zhí)行至少要求以下資源:用以裝載程序代碼和數(shù)據(jù)的內(nèi)存空間支持執(zhí)行的一系列CPU寄存器從程序到進程用C語言編寫一個程序編譯器把程序轉(zhuǎn)化成指令集連接器生成可執(zhí)行文件(code+data)載入可執(zhí)行程序到內(nèi)存(makereadytorun)voidX(intb){if(b==1){…intmain(){inta=2;X(a);}CodeHeaderInitializeddataExecutableFileSourceCodeCompile+Link進程在內(nèi)存中的存在形式voidX(intb){if(b==1){…intmain(){inta=2;X(a);}WhatyouwroteWhatisinmemory.voidX(intb){if(b==1){…intmain(){inta=2;X(a);}Codemain;a=2X;b=2HeapStack進程的剖析CodeHeaderInitializeddataExecutableFileCodeInitializeddataHeapStackDLL’smappedsegmentsProcess’saddressspaceLoad進程控制塊CodeInitializeddataHeapStackDLL’smappedsegmentsProcess’saddressspacePCSPOtherRegistersPIDUIDSchedulingPriorityListofopenfiles…PCB操作系統(tǒng)用來存放進程有關(guān)的信息每個進程都有一個進程控制塊進程管理的任務(wù)進程的調(diào)度系統(tǒng)決定在某個時刻應(yīng)該執(zhí)行哪個進程(因為多道程序的存在)進程間資源的競爭與共享多個進程同時需要同一個資源（打印機）進程的同步與互斥任務(wù)多個進程訪問同一個數(shù)據(jù)（溫度測控與顯示）進程通信進程間通告狀態(tài)或者任務(wù)信息main{

intchildPID;S1;

childPID=fork();

if(childPID==0)<codeforchildprocess>

else{<codeforparentprocess>wait();

}

S2;

}Unixfork()產(chǎn)生進程實例（很多方式產(chǎn)生進程）Theexecutioncontextforthechildprocessisacopyoftheparent’scontextatthetimeofthecallfork()returnschildPIDinparent,and0inchildCodeDataStackCodeDataStackParentChildfork()childPID

=0childPID

=xxx進程的生命周期ProcessiscreatedatStartandtransitionstoReadywhenitbecomesrunnableReadyStart進程的生命周期ProcesstransitionsfromReadytoRunningwhenkernelschedulesitRunningReadyStart進程的生命周期ProcesstransitionsfromRunningtoWaitingwhenitisblocked,waitingforaneventtooccur(e.g.,waitingforanI/Otofinish)RunningReadyWaitingStart進程的生命周期ProcesstransitionsfromWaitingtoReadywhentheeventoccurs(e.g.,I/Ocompletion)RunningReadyWaitingStart進程的生命周期ProcesstransitionsfromRunningtoReadyonaninterruptandpre-emptiveschedulingRunningReadyWaitingStart進程的生命周期ProcesstransitionsfromRunningtoDoneonexit()RunningReadyWaitingStartDone進程的生命周期ProcessesarealwayseitherRunning,Ready(toexecute)orWaiting(foraneventtooccur)RunningReadyWaitingStartDone內(nèi)存進程的狀態(tài)基本狀態(tài)“執(zhí)行”、“就緒”、“阻塞”其他狀態(tài)掛起內(nèi)存不足、特殊階段性進程（計劃任務(wù)）內(nèi)存到外存（代碼除外）阻塞進程先掛起僵死進程信息依然存在等待能被信號喚起：淺睡眠不能被信號喚起：深睡眠掛起將暫不執(zhí)行的進程換出到外存，節(jié)省內(nèi)存空間“掛起就緒狀態(tài)”“掛起阻塞狀態(tài)”進程的七狀態(tài)圖內(nèi)存外存Linux的進程狀態(tài)圖就緒隊列（鏈表）structlist_head{ structlist_head*next,*prev;};structtask_struct{ …… structlist_headrun_list; ……}進程隊列實例回顧幾個問題操作系統(tǒng)通常包含哪四種子系統(tǒng)？進程和程序的區(qū)別？除了初始狀態(tài)與退出狀態(tài)，在五狀態(tài)模型中還包括哪幾種狀態(tài)？其狀態(tài)轉(zhuǎn)移關(guān)系是怎么樣的？考慮掛起的情況下，又可增加哪幾種狀態(tài)？新的狀態(tài)轉(zhuǎn)移關(guān)系是怎么樣的？進程的調(diào)度CPU的分配方式剝奪式（可中斷，間斷調(diào)用）當一個進程正在執(zhí)行，處于它的一個CPU周期期間，系統(tǒng)可基于某種原則，強行剝奪現(xiàn)行進程正占用的CPU，并把CPU分配給另一進程。非剝奪式（不可中斷，一直執(zhí)行）非剝奪式調(diào)度，也稱“非搶占式調(diào)度”。它的含義是：當一個進程獲得CPU后，除非它因某種原因阻塞或者運行完畢，系統(tǒng)不能從該進程奪走CPU控制權(quán)。即現(xiàn)行進程完成它的當前CPU周期后，系統(tǒng)才重新調(diào)度。周轉(zhuǎn)時間是從作業(yè)提交到作業(yè)完成的時間間隔。

平均周轉(zhuǎn)時間是指進程調(diào)度時,各個進程的周轉(zhuǎn)時間的平均值。等待時間是指一個作業(yè)從被提交到獲得資源來被處理的那段等待時間，也被稱為響應(yīng)時間。平均等待時間是指進程調(diào)度時,各個進程的等待時間的平均值。周轉(zhuǎn)時間與等待時間先來先服務(wù)策略該準則實質(zhì)對應(yīng)于FIFO隊列若進程終止或阻塞,則CPU被分配給隊列中的下一個進程例子—三個進程P1,P2,P3,執(zhí)行時間分別是12,3,3.作業(yè)抵達順序P1,P2,P3作業(yè)抵達順序P2,P3,P1該策略屬于哪種CPU的分配方式？短作業(yè)優(yōu)先策略短作業(yè)先執(zhí)行按照預(yù)估完成時間的順序進行排隊該策略屬于哪種CPU分配方式？可以是剝奪式，也可以是非剝奪式若是剝奪式的話:也稱做最短剩余時間優(yōu)先策略HeadTail短作業(yè)優(yōu)先法的性能進程

執(zhí)行時間

P1

15P2 4P3 3平均周轉(zhuǎn)時間：（22+7+3）/3=10.7平均等待時間：（7+3+0）/3=3.3若使用FCFS策略，進程到達的順序為

P1、P2、P3。平均周轉(zhuǎn)時間是多少？平均等待時間又是多少？平均周轉(zhuǎn)時間：（15+19+22）/3=18.7平均等待時間：（0+15+19）/3=11.3P3P2P103722時間最短剩余時間優(yōu)先策略的性能行程

CPU執(zhí)行時間

到達時間

P1 6

0 P2 3

1 P3 7

2P4 4

3 平均周轉(zhuǎn)時間是多少？平均等待時間又是多少？平均周轉(zhuǎn)時間：（13+3+18+5）/4=9.75平均等待時間：（7

+

0+11+1）/4=4.75P1P3P1P2P4時間

01481320時間片輪轉(zhuǎn)法采用被稱做時間片的離散單元來分配處理器在每個時間片的末期，進程狀態(tài)轉(zhuǎn)換為就緒狀態(tài)進程每(n–1)q個時間單元執(zhí)行一次該策略屬于哪種CPU分配方式？時間片輪轉(zhuǎn)法示例時間片為20，進程抵達順序與運行時間如下

P1 53

P2 8

P3 68

P4 24甘特圖等待時間P1=(68-20)+(112-88)=72 P2=(20-0)=20

P3=(28-0)+(88-48)+(125-108)=85

P4=(48-0)+(108-68)=88平均等待時間=(72+20+85+88)/4=66?P1P2P3P4P1P3P4P1P3P302028486888108112125145153優(yōu)先級法為每一個進程分配一個優(yōu)先級，并按照優(yōu)先級來調(diào)度進程 若將優(yōu)先級定義為作業(yè)的預(yù)計執(zhí)行時間,則變?yōu)榱硕套鳂I(yè)優(yōu)先缺點:進程饑餓低優(yōu)先級進程可能永遠不會被執(zhí)行！避免進程饑餓的方法：年齡增長 隨時間逐步增加進程的優(yōu)先級進程調(diào)度策略總結(jié)先來先服務(wù)就緒隊列：時間先后短作業(yè)（遇上復(fù)雜作業(yè)）短作業(yè)優(yōu)先短作業(yè)先服務(wù)長作業(yè)可能很久不被執(zhí)行時間片輪轉(zhuǎn)法時間片，輪流（剛獲得CPU資源，執(zhí)行I/O操作）為I/O就緒進程單設(shè)隊列優(yōu)先級法優(yōu)先級別（緊急情況優(yōu)先）進程饑餓（調(diào)整優(yōu)先級）進程切換開銷時間和空間上的系統(tǒng)開銷根據(jù)策略選擇進程需要時間和空間調(diào)度策略最后反映在實物上就是操作系統(tǒng)代碼時間的角度：這些代碼的執(zhí)行需要時間空間的角度：這些代碼以及用到的相應(yīng)數(shù)據(jù)結(jié)構(gòu)都要放在內(nèi)存中切換時保存和恢復(fù)進程的上下文（保護現(xiàn)場）需要保護的對象如程序計數(shù)器、狀態(tài)寄存器的內(nèi)容保存在哪進程控制塊或者與當前進程有關(guān)的一些內(nèi)存區(qū)域中進程上下文OperatingSystem“SystemSoftware”UserProgram1UserProgram2UserProgram2UserProgramn...Program1Program2OSI/ODevicek:read()k+1:startIO()endio{interruptmain{main{}read{}}schedule()Memorysave

stateschedule()restore

statesavestate上下文交換圖示進程的同步與互斥進程同步與互斥需求（操作系統(tǒng)協(xié)調(diào)）互斥：進程要求對資源的使用不受其他進程干擾（打印機硬件/數(shù)據(jù)資源）例子：照片編輯器和照片查看器都要打印機打印照片同步：協(xié)調(diào)進程的執(zhí)行順序 例子：一個進程負責收集溫度，另外一個進程負責顯示時間以及該時刻的溫度操作系統(tǒng)怎么支持進程互斥地訪問資源呢程序聲明互斥訪問的資源（硬件互斥資源操作系統(tǒng)聲明）使用互斥資源先申請資源未被使用，讓申請進程使用使用完資源，明確聲明，然后操作系統(tǒng)才會讓其他進程使用操作系統(tǒng)提供相關(guān)系統(tǒng)調(diào)用程序中訪問互斥資源的那段代碼：臨界區(qū)、或敏感區(qū)、或危險區(qū)互斥實現(xiàn)互斥鎖

加鎖和開鎖的操作由操作系統(tǒng)實現(xiàn)程序員在程序中使用系統(tǒng)調(diào)用，且需要很小心地使用這些功能操作系統(tǒng)實現(xiàn)檢測數(shù)據(jù)是否被鎖住加鎖的過程不能被打斷鎖抽象成一個變量，稱為互斥量?；コ饬康牟僮饔迷硬僮鲗崿F(xiàn)全部動作過程不會被打斷的操作互斥鎖的應(yīng)用 進程1： 進程2：

…

…

lock(w)； lock(w)； 執(zhí)行臨界段1； 執(zhí)行臨界段2；

unlock(w)； unlock(w)；進程的同步典型示例：生產(chǎn)者和消費者問題消費者產(chǎn)品數(shù)量大于1時,消費使產(chǎn)品數(shù)量減少、庫房（空）數(shù)量增加生產(chǎn)者庫房數(shù)量大于1時,放產(chǎn)品使產(chǎn)品的數(shù)量增加，庫房（空）的數(shù)量減少制約資源產(chǎn)品、庫房生產(chǎn)者/消費者問題簡化單向制約庫房無限大、產(chǎn)品數(shù)量消費者消費一個產(chǎn)品，數(shù)量減1減1后的產(chǎn)品數(shù)量不小于0表示還有產(chǎn)品，消費者就從庫房中取出產(chǎn)品小于0，表明沒有產(chǎn)品，消費者去排隊等待生產(chǎn)者/消費者問題簡化生產(chǎn)者生產(chǎn)一個產(chǎn)品，產(chǎn)品數(shù)量加1產(chǎn)品數(shù)量加1后，如果產(chǎn)品的數(shù)量還是小于0的，表示有消費者在等待，喚醒（V操作）。關(guān)鍵問題增/減數(shù)量、判斷、等待/喚醒所有步驟需要一次完成：原子操作同步的實現(xiàn)信號量對于需要同步訪問的資源，操作系統(tǒng)讓程序為它聲明一個信號量信號量是一個整數(shù)。值是資源的個數(shù)。操作系統(tǒng)提供兩種對信號量的操作P操作（荷蘭語：Passeren通過）V操作（荷蘭語：Vrijgeven釋放）同步的實現(xiàn)P操作對信號量的值減1判斷信號量是否小于等于0；如果不是，則調(diào)用P操作的進程繼續(xù)執(zhí)行否則，進程到這個信號量的等待隊列中去等待V操作對信號量加1判斷信號量是否大于0；如果是，則調(diào)用進程繼續(xù)執(zhí)行否則說明有進程在等待該信號量，通知等待進程以原語操作的形式實現(xiàn)（不可分割，不可中斷）

一般來說，信號量S>0時，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請求分配一個單位資源，因此S的值減1；當S<0時，表示已經(jīng)沒有可用資源，請求者必須等待別的進程釋放該類資源，它才能運行下去。而執(zhí)行一個V操作意味著釋放一個單位資源，因此S的值加1；若S<0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態(tài)的進程，使之運行下去。同步的實現(xiàn)buffer：=1；（緩沖區(qū)數(shù)量） data：=0；（數(shù)據(jù)數(shù)量）P計算： P打印：Repeat RepeatP(buffer)； P(data)；寫入數(shù)據(jù)； 輸出數(shù)據(jù)；

V(data)； V(buffer)；Untilfalse； Untilfalse；進程間的通信信號管道消息隊列共享內(nèi)存基于網(wǎng)絡(luò)連接的通信信號需求要傳遞的信息很少信號事先定義對應(yīng)每個信號進程有一個處理程序信號隊列每個進程有一個存放其他進程發(fā)給它、等待它處理的信號操作系統(tǒng)提供發(fā)送信號的接口函數(shù)把進程要發(fā)送的信號放到目標進程的信號隊列中進程在執(zhí)行過程中的特定時刻，檢查并處理自己的信號隊列如從系統(tǒng)空間返回到用戶空間之前發(fā)送信號時，必須指明發(fā)送目標進程的號碼一般用在具有親緣關(guān)系的進程之間管道需求大量信息上游的進程往管道中寫入數(shù)據(jù)，下游的一方從管道接收數(shù)據(jù)先進先出的單向通信雙向通信需要建立兩個管道操作系統(tǒng)提供建立管道的系統(tǒng)調(diào)用函數(shù)命名管道管道同步：操作系統(tǒng)負責管道的容量有限，管道滿時，發(fā)送進程睡眠等待以字節(jié)為單位：沒有格式的字節(jié)流“清明時節(jié)雨紛紛，路上行人欲斷魂，借問酒家何處有，牧童遙指杏花村?！薄扒迕鲿r節(jié)／雨／紛紛路上行人／欲斷魂／借問酒家何處／有牧童遙指／杏花村”消息隊列需求 保持數(shù)據(jù)邏輯邊界操作系統(tǒng)提供創(chuàng)建消息隊列的系統(tǒng)調(diào)用一個進程可以使用系統(tǒng)調(diào)用創(chuàng)建一個消息隊列任何進程都可以向該隊列中發(fā)送消息，也可以從隊列中接收消息操作系統(tǒng)負責同步若消息隊列已滿，則寫消息的進程排隊若取消息進程沒有找到需要的消息，讀等待隊列共享內(nèi)存速度最快的進程間通信方式管道和消息隊列都需要數(shù)據(jù)的復(fù)制發(fā)送進程把數(shù)據(jù)復(fù)制到管道或者隊列中接收進程把數(shù)據(jù)從管道或者隊列復(fù)制到自己的內(nèi)存區(qū)中操作系統(tǒng)提供系統(tǒng)調(diào)用讓一個進程創(chuàng)建一塊共享內(nèi)存區(qū)其他進程通過系統(tǒng)調(diào)用把這段內(nèi)存映射到自己的用戶地址空間中進程像正常的內(nèi)存訪問一樣讀寫共享內(nèi)存區(qū)間不涉及數(shù)據(jù)的復(fù)制沒有同步機制基于網(wǎng)絡(luò)連接的通信插口、也叫套接字（socket）不同計算機進程間通過插口機制通信需要通信的雙方首先要各自創(chuàng)建一個插口，插口聲明自己接收來自某端口地址的數(shù)據(jù)主機地址：通信地址端口號：人名進程通過插口把消息發(fā)送到網(wǎng)絡(luò)中消息中指明接收進程所在主機名、端口號網(wǎng)絡(luò)中的傳輸設(shè)備根據(jù)主機地址把消息傳遞給目的主機。操作系統(tǒng)按照消息中端口號找到聲明接收該信息的插口，并把數(shù)據(jù)復(fù)制到插口的緩沖區(qū)內(nèi)。目的進程從插口中接收到數(shù)據(jù)可用在同一臺計算機上的進程之間通信進程的缺點進程切換開銷大上下文切換：保存和恢復(fù)相關(guān)寄存器的內(nèi)容；與進程運行有關(guān)的這些數(shù)據(jù)都需要修改；進程控制塊中的各種隊列（如阻塞隊列、就緒隊列、通信隊列）；存儲管理有關(guān)的一些記錄信息；文件管理有關(guān)數(shù)據(jù)；進程的地址空間要轉(zhuǎn)換成新被指派運行的進程的地址空間涉及到讀寫內(nèi)存、需要花費很多時間 進程的個數(shù)很多、進程轉(zhuǎn)換又頻繁發(fā)生，那么系統(tǒng)的性能就會下降

怎樣減少開銷？為什么要切換這么多信息？切換處理機