操作系統(tǒng)-進程管理

第2章進程管理,共69頁,共69頁,第2頁,在操作系統(tǒng)中，最核心的概念是進程，其他所有的內(nèi)容都是圍繞著進程展開的。,共69頁,第3頁,本章主要內(nèi)容,進程的引入和概念進程的描述：PCB、狀態(tài)、進程的控制：創(chuàng)建、撤消、阻塞、喚醒處理機調(diào)度：分配CPU給某一進程線程的引入,共69頁,第4頁,2.1進程的引入及其概念,1.程序的順序執(zhí)行簡單，但資源利用率低2.程序的并行執(zhí)行復雜，但資源利用率高,1.程序的順序執(zhí)行,一次只運行一道程序。如，單道批處理系統(tǒng)。封閉性：程序在運行時獨占全機資源，因此，這些資源的狀態(tài)只由一個程序決定和改變，不受外界因素影響?？稍佻F(xiàn)性：只要初始條件相同，無論程序連續(xù)運行，還是斷斷續(xù)續(xù)地運行，程序的執(zhí)行結(jié)果不變。,共69頁,第5頁,共69頁,第6頁,2.程序的并行執(zhí)行,并行執(zhí)行：計算機同時運行多個程序，即多個程序在CPU上交叉運行。以資源共享為條件，提高資源利用率。增強計算機系統(tǒng)的處理能力。,共69頁,第7頁,例作業(yè)i的輸入、計算和輸出操作分別用Ii、Ci、Pi表示。多個作業(yè)的并行執(zhí)行如下圖所示。,共69頁,第8頁,程序并行執(zhí)行的特征：(1,2,3),(1)失去了程序的封閉性和可再現(xiàn)性在并行執(zhí)行時，多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行環(huán)境失去了封閉性，也將導致運行結(jié)果失去了可再現(xiàn)性。,共69頁,第9頁,因共享資源或協(xié)調(diào)完成同一任務而引起的。,例typea.c|more這條命令就需要管道符號兩邊的程序相互協(xié)作。這是一種直接制約關系。,例并行執(zhí)行的程序A和B共享一臺打印機。A和B之間就產(chǎn)生了間接制約關系。,(2)并行執(zhí)行的程序間產(chǎn)生了相互制約關系,共69頁,第10頁,程序是完成特定功能的指令序列，是靜態(tài)的CPU執(zhí)行的活動是一個動態(tài)概念，是程序的執(zhí)行過程。,(3)程序與CPU執(zhí)行的活動之間不再一一對應,例一個編譯程序多個編譯活動：分時系統(tǒng)中，多個用戶都調(diào)用C編譯器對自己的源程序進行編譯。實際系統(tǒng)只保留一個編譯程序，而CPU正在為多個用戶進行編譯。,共69頁,第11頁,進程的概念,為了描述系統(tǒng)中各“并發(fā)活動”，而引入了“進程”。進程（process）又叫做任務（task）進程是程序的一次執(zhí)行過程進程是程序在一個數(shù)據(jù)集合上順序執(zhí)行時發(fā)生的活動,共69頁,第12頁,進程具有的特性,動態(tài)性。進程是程序的一次執(zhí)行過程，是臨時的，有生命期的。獨立性。進程是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。并發(fā)性。多個進程可在處理機上交替執(zhí)行。結(jié)構(gòu)性。系統(tǒng)為每個進程建立一個進程控制塊。,共69頁,第13頁,進程和程序,進程是動態(tài)的，程序是靜態(tài)的。程序是有序代碼的集合，進程是程序的執(zhí)行，沒有程序就沒有進程。通常，進程不可以在計算機之間遷移，而程序可以復制。進程是暫時的，程序是永久的。進程包括程序、數(shù)據(jù)和進程控制塊。通過多次執(zhí)行，一個程序可對應多個進程；通過調(diào)用關系，一個進程可包括多個程序。進程可創(chuàng)建其他進程，而程序不能形成新的程序。,共69頁,第14頁,2.2進程的描述,PCB是進程存在的唯一標識通常，一個進程的信息包括：至少一個可執(zhí)行程序一個獨立的地址空間一個執(zhí)行棧區(qū)（子程序調(diào)用，系統(tǒng)調(diào)用，進程切換）打開的文件、申請使用的I/O設備等,進程控制塊(PCB,processcontrolblock)進程描述符(processdescriptor),共57頁,第15頁,進程地址空間,內(nèi)核代碼可以訪問當前進程的整個4GB地址空間,共69頁,第16頁,PCB中的基本信息,進程標識數(shù)：用于唯一地標識一個進程，通常是一個整數(shù)。外部標識符，由用戶使用。如：send進程、print進程等。進程的狀態(tài)、調(diào)度、存儲器管理信息：是調(diào)度進程所必需的信息，包括進程狀態(tài)、優(yōu)先級、程序在主存地址、在外存的地址等。進程使用的資源信息：分配給進程的I/O設備、正在打開的文件等。,共69頁,第17頁,CPU現(xiàn)場保護區(qū)：保存進程運行的現(xiàn)場信息。包括：程序計數(shù)器(PC)、程序狀態(tài)字、通用寄存器、堆棧指針等。記帳信息：包括使用CPU時間量、帳號等。進程之間的家族關系：類UNIX系統(tǒng)，進程之間存在著家族關系，父/子進程。Windows進程之間不具有父子關系。進程的鏈接指針：鏈接相同狀態(tài)的進程。,共69頁,第18頁,Unix：structproc;Linux：structtask_struct;P146Windows執(zhí)行體進程塊（EPROCESS）P284,內(nèi)核實現(xiàn)線程調(diào)度，調(diào)度信息在KTHREAD結(jié)構(gòu)中,實例,共69頁,第19頁,進程的狀態(tài),進程在其生命期內(nèi)一直處在一個狀態(tài)不斷變化的過程中。為了刻畫這一變化過程，操作系統(tǒng)把進程狀態(tài)分成若干種，并約定各種狀態(tài)之間的轉(zhuǎn)換條件。狀態(tài)信息記錄在進程的PCB結(jié)構(gòu)中。,共69頁,第20頁,(1)運行態(tài)(running)：進程正在CPU上運行。單CPU系統(tǒng)一次只有一個運行進程；多CPU系統(tǒng)可能有多個運行進程。(2)阻塞態(tài)(blocked)：又稱等待態(tài)。當進程因等待某個條件發(fā)生而不能運行時所處的狀態(tài)。等待I/O完成，等待一個消息(3)就緒態(tài)(ready)：已獲得除CPU之外的全部資源，只要再獲得CPU，就可執(zhí)行。,共69頁,第21頁,運行態(tài),就緒態(tài),阻塞態(tài),被搶先,進程調(diào)度,等待事件,事件完成,進程的三個基本狀態(tài)及其轉(zhuǎn)換,共69頁,第22頁,運行態(tài)-阻塞態(tài)：是由運行進程自己主動改變的。例一個正在運行的進程啟動了某一I/O設備后，使自己由運行態(tài)變?yōu)樽枞麘B(tài)，等待該I/O設備傳輸完成。阻塞態(tài)-就緒態(tài)：是由外界事件引起的。例當I/O設備傳輸完成時，請求中斷，由I/O中斷處理程序把因等待這一I/O完成而阻塞的進程變?yōu)榫途w態(tài)。,由進程狀態(tài)轉(zhuǎn)換圖可以看出,共69頁,第23頁,運行態(tài)-就緒態(tài)：處于運行態(tài)的進程被剝奪CPU。例（1）采用時間片輪轉(zhuǎn)法調(diào)度：當前進程用完時間片，由運行態(tài)變?yōu)榫途w態(tài)。（2）采用優(yōu)先級調(diào)度：若有更高優(yōu)先級的進程變?yōu)榫途w態(tài)，當前進程被剝奪CPU，由運行態(tài)變?yōu)榫途w態(tài)。就緒態(tài)-運行態(tài)：被進程調(diào)度程序選中。,共69頁,第24頁,(4)創(chuàng)建態(tài)：剛剛建立，未進就緒隊列。(5)終止態(tài)：已正常結(jié)束或故障中斷，但尚未撤消。暫留在系統(tǒng)中，方便其它進程去收集該進程的有關信息。,創(chuàng)建態(tài)就緒態(tài)：操作系統(tǒng)準備好再接納一個進程時，把一個進程從創(chuàng)建態(tài)變?yōu)榫途w態(tài)。為了確保系統(tǒng)的性能，大多數(shù)系統(tǒng)都限制創(chuàng)建的進程數(shù)量。,共69頁,第25頁,圖2.3進程的五種狀態(tài),共69頁,第26頁,進程的組織,（1）線性表：把所有進程的PCB存放在一個數(shù)組中，系統(tǒng)通過數(shù)組下標訪問每個PCB。,共69頁,第27頁,（2）鏈接表：把具有相同狀態(tài)的PCB組成一個隊列。處于就緒態(tài)的進程可按照某種策略排成多個就緒隊列。處于阻塞態(tài)的進程又可以根據(jù)阻塞的原因不同組織成多個阻塞隊列。如，等待磁盤I/O隊列，等待磁帶I/O隊列等。,共69頁,第28頁,共69頁,第29頁,2.3進程控制,進程控制：是指系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程，以及完成進程各狀態(tài)之間的轉(zhuǎn)換。進程控制是由操作系統(tǒng)內(nèi)核實現(xiàn)的。是屬于原語一級的操作，不能被中斷。,共69頁,第30頁,(1)創(chuàng)建進程的時機批處理系統(tǒng)中，會為每個提交的作業(yè)創(chuàng)建一個進程。分時系統(tǒng)中，系統(tǒng)會為每個登錄用戶創(chuàng)建一個終端進程。交互式系統(tǒng)中，鍵入一個命令或點擊一個圖標都會開始一個新進程。,創(chuàng)建原語,共69頁,第31頁,在UNIX和Windows系統(tǒng)中，用戶可以同時打開多個窗口，每個窗口都對應一個進程。UNIX的系統(tǒng)調(diào)用fork()會創(chuàng)建一個與調(diào)用進程具有相同副本的進程，子進程通過execve()系統(tǒng)調(diào)用會運行一個新的程序。Windows中的Win32函數(shù)調(diào)用CreateProcess()創(chuàng)建新進程，運行新程序。,共69頁,第32頁,(2)創(chuàng)建原語的功能,掃描進程表，找到一個空閑的PCB。為新進程的程序、數(shù)據(jù)、用戶棧分配內(nèi)存初始化PCB。把調(diào)用者提供的參數(shù)（進程名、進程優(yōu)先級、實體所在主存的起始地址、所需的資源清單、記帳信息及進程家族關系等）填入PCB中。將新進程插入就緒隊列。,共69頁,第33頁,進程執(zhí)行完或因故障不能繼續(xù)運行。功能：在PCB集合中尋找要撤銷的進程；若有子進程，也須終止，以防成為不可控的；將其占用的系統(tǒng)資源歸還系統(tǒng)；撤銷其PCB。,（UNIX中用exit();Windows用ExitProcess()）,撤消原語,共69頁,第34頁,在運行過程中進程期待某一事件發(fā)生時，自己執(zhí)行阻塞原語，由運行態(tài)變?yōu)樽枞麘B(tài)。（等待鍵盤輸入；等待磁盤數(shù)據(jù)傳輸完成；等待其它進程發(fā)送一個信息）功能：中斷CPU；將其運行現(xiàn)場信息保存在PCB中；置狀態(tài)為阻塞態(tài)，插入相應事件的阻塞隊列中；轉(zhuǎn)進程調(diào)度。,阻塞原語,共69頁,第35頁,喚醒原語,若進程等待的事件是I/O完成。I/O完成后，CPU響應中斷，在中斷處理中，將等待I/O完成而阻塞的進程喚醒，并置為就緒態(tài)。若等待某進程發(fā)信息。由發(fā)送進程調(diào)用喚醒原語把等待者喚醒，置為就緒態(tài)。插入就緒隊列。,共69頁,第36頁,UNIX阻塞/喚醒,Sleep()將在指定時間內(nèi)阻塞本進程Pause()阻塞本進程以等待信號。Wait()阻塞本進程以等待子進程的結(jié)束。Kill()向指定進程或進程組發(fā)送信號。Wakeup(),共69頁,第37頁,實時系統(tǒng)，根據(jù)實時現(xiàn)場的需要，會將正在執(zhí)行的或沒有執(zhí)行的進程掛起一段時間。被掛起的進程由活動狀態(tài)變?yōu)殪o止狀態(tài)（靜止就緒、靜止阻塞）。分時系統(tǒng)，把進程從內(nèi)存換到外存，進程就處于靜止狀態(tài)，不被調(diào)度。,掛起原語,共69頁,第38頁,解掛原語,當掛起進程的原因被解除時，系統(tǒng)調(diào)用解掛原語將指定的進程解掛，使其由靜止狀態(tài)變?yōu)榛顒訝顟B(tài)。當被解掛的進程變?yōu)榛顒泳途w時，通常立即轉(zhuǎn)進程調(diào)度。,共69頁,第39頁,2.4處理機調(diào)度,進程數(shù)大于處理機數(shù)。多進程競爭處理機。進程調(diào)度就是為進程分配處理機。系統(tǒng)運行性能在很大程度上取決于調(diào)度。吞吐量大小、周轉(zhuǎn)時間長短、響應及時性。,共69頁,第40頁,處理機的調(diào)度級別,作業(yè)調(diào)度：高級調(diào)度。多道批處理系統(tǒng)。多個用戶作業(yè)以成批的形式提交到外存，形成后備作業(yè)隊列。被作業(yè)調(diào)度選中進內(nèi)存，就處于運行態(tài)。進程調(diào)度：低級調(diào)度。交換調(diào)度：中級調(diào)度。將主存就緒或主存阻塞等暫不具備運行條件的進程換出到外存交換區(qū)；或?qū)⑼獯娼粨Q區(qū)中的已具備運行條件的進程換入主存。交換調(diào)度可以控制進程對主存的使用。,共69頁,第41頁,(1)記錄系統(tǒng)中各進程的執(zhí)行狀況管理進程控制塊，將進程的狀態(tài)變化及資源需求情況及時地記錄到PCB中。(2)選擇就緒進程占有CPU(3)進行進程上下文的切換將正在執(zhí)行進程的上下文保存在該進程的PCB中，將剛選中進程的運行現(xiàn)場恢復起來，以便執(zhí)行。,進程調(diào)度的功能,共69頁,第42頁,進程上下文,用戶級上下文：進程的程序和數(shù)據(jù)，用戶棧。寄存器級上下文：是CPU的現(xiàn)場信息，包括程序計數(shù)器、PSW、棧指針、用來保存變量和臨時結(jié)果的通用寄存器的值等。系統(tǒng)級上下文：包括進程的PCB、核心棧等,進程的運行環(huán)境和物理實體,共69頁,第43頁,棧記錄進程的執(zhí)行歷程。棧幀中存放有關的輸入?yún)?shù)、局部變量、過程調(diào)用之后的返回地址、沒有保存在寄存器中的臨時變量。通常，每個進程會調(diào)用不同的過程，從而有一個各自不同的執(zhí)行歷程。,共69頁,第44頁,非搶先方式(非剝奪方式)某一進程占用CPU,直到運行完或不能運行為止，其間不被剝奪。用在批處理系統(tǒng)。主要優(yōu)點：簡單、系統(tǒng)開銷小。搶先方式(剝奪方式)允許調(diào)度程序基于某種策略（優(yōu)先級、時間片等）剝奪現(xiàn)行進程的CPU給其它進程。用在分時系統(tǒng)、實時系統(tǒng)。,進程調(diào)度的方式,共69頁,第45頁,（1）現(xiàn)行進程完成或錯誤終止；（2）提出I/O請求，等待I/O完成時；（3）在分時系統(tǒng)，按照時間片輪轉(zhuǎn)，分給進程的時間片用完時；（4）優(yōu)先級調(diào)度，有更高優(yōu)先級進程就緒；（5）進程執(zhí)行了某種原語操作，如阻塞原語和喚醒原語，都可能引起進程調(diào)度。,進程調(diào)度的時機,共69頁,第46頁,（1）先來先服務(FCFS)（2）最短作業(yè)優(yōu)先(SJF)（3）響應比高者優(yōu)先(HRN)（4）優(yōu)先級調(diào)度法（5）輪轉(zhuǎn)法(RoundRobin)（6）多級反饋隊列輪轉(zhuǎn)法,進程調(diào)度算法,共69頁,第47頁,（1）先來先服務(FCFS)：簡單，節(jié)省機器時間。缺點：容易被大作業(yè)壟斷，使得平均周轉(zhuǎn)時間延長。例幾乎同時到達的三個作業(yè)j1、j2、j3。j1運行2小時，j2和j3只需1分鐘。三個作業(yè)的平均周轉(zhuǎn)時間為2個小時多。增長了短作業(yè)的周轉(zhuǎn)時間。（系統(tǒng)先運行j1，j2和j3要等2個小時。j1完成之后，j2和j3再分別運行1分鐘。）,共69頁,第48頁,（2）最短作業(yè)優(yōu)先(SJF)：選取運行時間最短的作業(yè)運行。對短作業(yè)有利，作業(yè)的平均周轉(zhuǎn)時間最佳。若系統(tǒng)不斷進入短作業(yè)，長作業(yè)就沒有機會運行，出現(xiàn)饑餓現(xiàn)象。,共69頁,第49頁,（3）響應比高者優(yōu)先(HRN)Rp=(作業(yè)等待時間+作業(yè)估計運行時間)/作業(yè)估計運行時間=1+作業(yè)等待時間/作業(yè)估計運行時間特點：結(jié)合了先來先服務、短作業(yè)優(yōu)先的方法。優(yōu)先運行短作業(yè)和等待時間足夠長的長作業(yè)。缺點：算法比較復雜。,共69頁,第50頁,（4）優(yōu)先級調(diào)度法將CPU分配給就緒隊列中優(yōu)先級最高的進程靜態(tài)優(yōu)先級：在進程創(chuàng)建時確定的，運行時保持不變。通常賦予系統(tǒng)進程較高優(yōu)先級；申請資源量少的賦予較高優(yōu)先級?？赡軐е碌蛢?yōu)先級的長進程沒有機會運行。動態(tài)優(yōu)先級：原優(yōu)先級可隨進程的推進而改變。根據(jù)進程占用CPU時間的長短或等待CPU時間的長短動態(tài)調(diào)整。,共69頁,第51頁,（5）輪轉(zhuǎn)法(RoundRobin)用在分時系統(tǒng)，輪流調(diào)度所有就緒進程。利用一個定時時鐘，使之定時地發(fā)出中斷。時鐘中斷處理程序在設置新的時鐘常量后，立即轉(zhuǎn)入進程調(diào)度程序。時間片長短的確定原則：既要保證系統(tǒng)各個用戶進程及時地得到響應，又不要因時間片太短而增加調(diào)度的開銷，降低效率。,共69頁,第52頁,（6）多級反饋隊列輪轉(zhuǎn)法因就緒原因不同，系統(tǒng)通常設置多個就緒隊列。多個就緒隊列可采用前后臺運行。前臺隊列采用RR調(diào)度；后臺采用FCFS。高優(yōu)先級進程的時間片較短，低則較長。剛創(chuàng)建的進程和因請求I/O而未用完時間片的進程排在高優(yōu)先級隊列。運行23個時間片還未完成的進程降級。,共69頁,第53頁,（時間片：s1s2sn),共69頁,第54頁,實時系統(tǒng)的調(diào)度算法,時鐘驅(qū)動法：各任務的調(diào)度在系統(tǒng)運行前就確定了，調(diào)度程序依次調(diào)度任務執(zhí)行。加權輪轉(zhuǎn)法：進程的權就是分配給它的一小部分處理機時間。輪轉(zhuǎn)時，不同的進程可以獲得不同的處理機時間。廣泛用在高速開關網(wǎng)的實時控制中。,共69頁,第55頁,進程在邏輯上表示OS要做的一個作業(yè)，線程表示組成該作業(yè)的許多可能的子任務。線程是進程中的一個可執(zhí)行實體。以進程為單位分配資源，以線程為單位調(diào)度執(zhí)行。,2.5線程的引入,共69頁,第56頁,多線程字處理：一個線程與用戶交互另一個線程在后臺進行格式化處理。一旦在某一頁中的語句被刪除掉，交互線程就立即通知格式化線程對整本書重新進行處理。同時，交互線程繼續(xù)監(jiān)控鍵盤和鼠標。第三個線程可以做磁盤備份。,共69頁,第57頁,分派線程(dispatcher)從網(wǎng)絡讀入請求，之后選一個工作線程提交請求，當該工作線程阻塞在磁盤操作上時，分派線程可另選一個工作線程運行。,共69頁,第58頁,進程地址空間,進程控制塊,線程控制塊,堆棧,寄存器組,線程控制塊,堆棧,寄存器組,線程控制塊,堆棧,寄存器組,程序段,數(shù)據(jù)段,打開文件,線程1,線程2,線程3,共69頁,第59頁,一個線程的組成,有一個唯一的標識符表示處理機狀態(tài)和運行現(xiàn)場的一組寄存器兩個堆棧，分別用于用戶態(tài)和核心態(tài)調(diào)用時進行參數(shù)傳遞一個獨立的程序計數(shù)器關聯(lián)的進程和線程指針,共69頁,第60頁,進程擁有一個獨立的地址空間，用來存放若干代碼段和數(shù)據(jù)段。若干打開文件，以及至少一個線程。一個進程內(nèi)的多線程共享該進程的所有資源，線程自己擁有很少資源。,線程與進程的比較,（1）擁有的資源,進程調(diào)度需進行進程上下文的切換，開銷大。同一進程內(nèi)的線程切換，僅把線程擁有的一小部分資源變換了即可，效率高。同一進程內(nèi)的線程切換比進程切換快得多。不同進程的線程切換,（2）調(diào)度,共69頁,第61頁,（3）并發(fā)性引入線程后，使得系統(tǒng)的并發(fā)執(zhí)行程度更高。進程之間、進程內(nèi)的多線程之間可并發(fā)執(zhí)行。（4）安全性同一進程的多線程共享進程的所有資源，一個線程可以改變另一個線程的數(shù)據(jù)，共享數(shù)據(jù)方便。多進程實現(xiàn)，安全性好。,共69頁,第62頁,系統(tǒng)對線程的支持,1）用戶級線程有關線程的所有管理工作都由用戶程序通過調(diào)用用戶態(tài)運行的線程庫完成。