軟件技術(shù)基礎(chǔ) (10)處理器管理1

第四章操作系統(tǒng)4.2處理器管理一、基本概念與術(shù)語

在多道程序系統(tǒng)中，處理器數(shù)小于程序數(shù)，于是處理器就在各程序間進(jìn)行切換，因此在一個處理器上要交叉運(yùn)行若干道程序。處理器管理就是要解決用戶遞交的作業(yè)何時調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各個作業(yè)程序間如何分配處理器，以達(dá)到各道程序能協(xié)調(diào)一致運(yùn)行，而系統(tǒng)資源又能得到最大程度的利用。

基本概念與術(shù)語

★作業(yè)和進(jìn)程

★特權(quán)指令、處理器狀態(tài)

★處理器管理1第四章操作系統(tǒng)4.2處理器管理★作業(yè)和進(jìn)程

⑴作業(yè)、作業(yè)步作業(yè)是用戶在一次算題過程中或一個事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所作工作的集合。一個作業(yè)由一系列的作業(yè)步組成。一個作業(yè)步運(yùn)行的結(jié)果產(chǎn)生下一個作業(yè)步所需的文件。例如一個C語言程序要經(jīng)歷編輯、編譯、連接、運(yùn)行四個作業(yè)步。2第四章操作系統(tǒng)4.2處理器管理⑵進(jìn)程和程序在多道程序系統(tǒng)中，多道程序并發(fā)運(yùn)行，為了競爭有限的資源，相互間存在依賴與制約關(guān)系，它們在系統(tǒng)中的狀態(tài)是不斷變化的，即時而運(yùn)行，時而停頓。因此引入新的概念---進(jìn)程。一旦操作系統(tǒng)接受了某用戶的作業(yè)，并把它調(diào)入內(nèi)存執(zhí)行，系統(tǒng)就為此作業(yè)創(chuàng)建一個或多個進(jìn)程。因此進(jìn)程可以看成是程序的一次執(zhí)行，即是在指定內(nèi)存區(qū)域中的一組指令序列的執(zhí)行過程。多個進(jìn)程可以并發(fā)進(jìn)行，并可能由于各種原因隨時中斷。

3第四章操作系統(tǒng)4.2處理器管理

從對進(jìn)程的描述來看，進(jìn)程既與程序有關(guān)，又與程序不同，它們的區(qū)別是：①進(jìn)程是程序的執(zhí)行，因此屬于動態(tài)的概念；而程序是一組指令的集合，屬于靜態(tài)的概念。②進(jìn)程既然是程序的執(zhí)行，因此它是有生命過程的，進(jìn)程有誕生（創(chuàng)建進(jìn)程）和死亡（撤消進(jìn)程），應(yīng)此進(jìn)程的存在是暫時的，而程序的存在是永久的。4第四章操作系統(tǒng)4.2處理器管理

★

特權(quán)指令、處理器狀態(tài) 每個處理器都有自己的指令系統(tǒng)，在多道程序環(huán)境中為了保證系統(tǒng)正常工作，將指令系統(tǒng)中的指令分為兩類：

1.特權(quán)指令：只能由操作系統(tǒng)使用。

2.非特權(quán)指令：供一般用戶使用。對應(yīng)兩種不同的指令，處理器有兩種執(zhí)行狀態(tài)。

◆管態(tài)：又稱主態(tài)、執(zhí)行狀態(tài),此時處理器執(zhí)行特權(quán)指令。

◆目態(tài)：又稱算態(tài)、題目狀態(tài)，此時處理器處于用戶執(zhí)行狀態(tài)。5第四章操作系統(tǒng)4.2處理器管理★

從Intel80386開始，出于安全性和穩(wěn)定性的考慮，該系列的CPU可以運(yùn)行于ring0（0級環(huán)）至ring3(3級環(huán))從高到低四個不同的權(quán)限級，對數(shù)據(jù)也提供相應(yīng)的四個保護(hù)級別。運(yùn)行于較低級別的代碼不能隨意調(diào)用高級別的代碼和訪問較高級別的數(shù)據(jù)，只有ring0層的代碼才可以對物理硬件直接進(jìn)行訪問。6第四章操作系統(tǒng)4.2處理器管理

★處理器管理

在大型通用系統(tǒng)中，可能有數(shù)百個作業(yè)等待處理，處理器管理又稱處理器調(diào)度，就是解決如何從這些作業(yè)中挑選一些進(jìn)入主存運(yùn)行，又如何在主存各進(jìn)程間分配處理器。它一般分為兩級：作業(yè)調(diào)度：又稱高級調(diào)度或宏觀調(diào)度。它的主要功能是按照某種調(diào)度原則，選取某些作業(yè)進(jìn)入內(nèi)存，為它們分配必要的資源，建立相應(yīng)的進(jìn)程，并當(dāng)作業(yè)完成后做好一切善后工作。進(jìn)程調(diào)度：又稱低級調(diào)度或微觀調(diào)度。它的主要功能是按照某種調(diào)度原則，實(shí)現(xiàn)處理器在各進(jìn)程間的轉(zhuǎn)換。7第四章操作系統(tǒng)4.2處理器管理二、作業(yè)調(diào)度1.作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊 一個作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般要經(jīng)歷以下四種狀態(tài):提交收容執(zhí)行完成。提交收容完成去分配作業(yè)管理設(shè)備管理輔存執(zhí)行內(nèi)存作業(yè)的四種狀態(tài)8第四章操作系統(tǒng)4.2處理器管理提交收容完成去分配作業(yè)管理設(shè)備管理輔存執(zhí)行內(nèi)存作業(yè)的四種狀態(tài)提交狀態(tài)：用戶向機(jī)房提交作業(yè)或通過終端鍵盤將作業(yè)輸入，其作業(yè)所處的狀態(tài)為提交狀態(tài)。收容狀態(tài)：作業(yè)的全部信息已經(jīng)輸入外存等待運(yùn)行，又稱為后備狀態(tài)。9第四章操作系統(tǒng)4.2處理器管理提交收容完成去分配作業(yè)管理設(shè)備管理輔存執(zhí)行內(nèi)存作業(yè)的四種狀態(tài)執(zhí)行狀態(tài)：作業(yè)被作業(yè)調(diào)度程序選中進(jìn)入內(nèi)存，稱為執(zhí)行狀態(tài)。完成狀態(tài)：作業(yè)執(zhí)行完畢，釋放其占用的全部資源，準(zhǔn)備退出系統(tǒng)。10第四章操作系統(tǒng)4.2處理器管理為了管理和調(diào)度作業(yè)，系統(tǒng)為每個作業(yè)建立一個作業(yè)控制塊（JCB-JobControlBlock），是作業(yè)存在的標(biāo)志。它詳細(xì)記錄每個作業(yè)的有關(guān)信息。不同系統(tǒng)的JCB不完全相同，取決于系統(tǒng)對作業(yè)調(diào)度的要求。主要有：作業(yè)名：用戶作業(yè)的名稱。狀態(tài)：輸入/收容/執(zhí)行。優(yōu)先數(shù)：根據(jù)作業(yè)的重要程度，由系統(tǒng)或用戶確定。運(yùn)行時間：用戶根據(jù)經(jīng)驗(yàn)估計(jì)完成本作業(yè)所需時間。位置：本作業(yè)在外存中的起始地址。11第四章操作系統(tǒng)4.2處理器管理長度：作業(yè)的地址空間。外設(shè)申請：作業(yè)運(yùn)行時要求的外部設(shè)備。所有的JCB可按作業(yè)的優(yōu)先數(shù)大小或作業(yè)到達(dá)系統(tǒng)的時間順序構(gòu)成一個作業(yè)隊(duì)列，如下圖所示作業(yè)名現(xiàn)在狀態(tài)優(yōu)先數(shù)時間估計(jì)位置長度外設(shè)申請…指向下一個JCB指針JCB1作業(yè)控制塊與作業(yè)隊(duì)列JCB2JCBn12第四章操作系統(tǒng)4.2處理器管理2.作業(yè)調(diào)度的功能按照某種調(diào)度算法，從所有處于后備狀態(tài)的作業(yè)隊(duì)列中挑選作業(yè)進(jìn)入主存。調(diào)用存儲管理和設(shè)備管理程序，為被選中的作業(yè)分配內(nèi)存和外設(shè)，做好運(yùn)行前的準(zhǔn)備為選中的作業(yè)建立相應(yīng)的進(jìn)程。作業(yè)運(yùn)行完畢時回收該作業(yè)占用的資源，輸出必要的信息，撤消該作業(yè)的JCB與相應(yīng)的進(jìn)程。13第四章操作系統(tǒng)4.2處理器管理3.作業(yè)調(diào)度算法

調(diào)度算法的考慮因素很多，但這些因素應(yīng)和主觀上的目標(biāo)一致。通常調(diào)度算法應(yīng)達(dá)到的目標(biāo)為：運(yùn)行盡可能多的作業(yè)使處理器保持忙碌狀態(tài)使I/O設(shè)備得到充分利用對所有作業(yè)公平合理上述這些目標(biāo)往往存在沖突，要想同時滿足是不可能的，只能根據(jù)需要兼顧某些目標(biāo)。14第四章操作系統(tǒng)4.2處理器管理考慮的因素越多、算法就越復(fù)雜，從而增加系統(tǒng)的開銷，對資源的利用反而不利。因此，大多數(shù)操作系統(tǒng)往往采用比較簡單的調(diào)度算法。下面介紹幾種常用的作業(yè)調(diào)度算法：先來先服務(wù)算法：這是一種最簡單的調(diào)度算法。它按作業(yè)錄入的先后次序建成進(jìn)行調(diào)度。這種算法優(yōu)先考慮等待時間最長的作業(yè)，忽視它要求運(yùn)行時間的長短。效率低，對短作業(yè)不利，容易被大作業(yè)壟斷。短作業(yè)優(yōu)先調(diào)度算法：以每個作業(yè)JCB中提供的運(yùn)行時間為依據(jù)，總是選取運(yùn)行時間最短的作業(yè)。對短作業(yè)有利，但可能使長作業(yè)得不到運(yùn)行的機(jī)會。15第四章操作系統(tǒng)4.2處理器管理

響應(yīng)比高者優(yōu)先：是介于先來先服務(wù)和短作業(yè)優(yōu)先算法之間的一種折中算法。兼顧了運(yùn)行時間短和等待時間長的作業(yè)。

響應(yīng)比=作業(yè)響應(yīng)時間/估計(jì)運(yùn)行時間

=1+作業(yè)等待時間/作業(yè)估計(jì)運(yùn)行時間計(jì)算后備作業(yè)隊(duì)列中每個作業(yè)的響應(yīng)比，然后挑選響應(yīng)比最高的投入運(yùn)行。它實(shí)際上優(yōu)先考慮短作業(yè)，但也兼顧等待時間長的作業(yè)。16第四章操作系統(tǒng)4.2處理器管理

優(yōu)先數(shù)調(diào)度算法：選取優(yōu)先數(shù)最高作業(yè)首先運(yùn)行.優(yōu)先數(shù)的確定可由用戶指定，也可根據(jù)作業(yè)運(yùn)行時間的長短和對資源要求的多少來規(guī)定。如：每當(dāng)作業(yè)調(diào)度程序挑選作業(yè)時，要遍訪后備隊(duì)列，為每個作業(yè)算出一個優(yōu)先數(shù)，然后根據(jù)優(yōu)先數(shù)大小挑選作業(yè)。17第四章操作系統(tǒng)4.2處理器管理例題1：在多道操作系統(tǒng)控制下，作業(yè)反復(fù)運(yùn)行多次，它的運(yùn)行時間都相同嗎？例題2：現(xiàn)有2道作業(yè)同時執(zhí)行，一道以計(jì)算為主，另一道以輸入輸出為主，怎樣賦予作業(yè)進(jìn)程占有處理器的優(yōu)先級，使作業(yè)作業(yè)的平均周轉(zhuǎn)周期最短？作業(yè)周轉(zhuǎn)時間=作業(yè)完成時刻–作業(yè)遞交時刻

=作業(yè)運(yùn)行時間+作業(yè)等待時間18第四章操作系統(tǒng)4.2處理器管理例題3：有5個批處理作業(yè)(A,B,C,D,E)幾乎同時到達(dá)一個計(jì)算中心，估計(jì)運(yùn)行的時間分別為2,4,6,8,10分鐘，它們的優(yōu)先數(shù)分別為1,2,3,4,5。對下面的每種調(diào)度算法，分別計(jì)算作業(yè)的平均周轉(zhuǎn)時間。(1)最高優(yōu)先級優(yōu)先(2)時間片輪轉(zhuǎn)（時間片為2分鐘）(3)FIFO（作業(yè)到達(dá)的順序?yàn)镃,D,B,E,A）(4)短作業(yè)優(yōu)先19第四章操作系統(tǒng)4.2處理器管理作業(yè)執(zhí)行次序優(yōu)先數(shù)運(yùn)行時間等待時間周轉(zhuǎn)時間E510010D481018C361824B242428A122830作業(yè)平均周轉(zhuǎn)時間T=22(分鐘)(a)優(yōu)先級調(diào)度算法20第四章操作系統(tǒng)4.2處理器管理作業(yè)運(yùn)行時間等待時間周轉(zhuǎn)時間A202B4812C61420D81826E102030作業(yè)平均周轉(zhuǎn)時間T=18(分鐘)(b)時間片輪轉(zhuǎn)法調(diào)度21第四章操作系統(tǒng)4.2處理器管理作業(yè)執(zhí)行次序運(yùn)行時間等待時間周轉(zhuǎn)時間C606D8614B41418E101828A22830作業(yè)平均周轉(zhuǎn)時間T=19.2(分鐘)(c)先來先服務(wù)法調(diào)度22第四章操作系統(tǒng)4.2處理器管理作業(yè)執(zhí)行次序運(yùn)行時間等待時間周轉(zhuǎn)時間E202D426C6612B81220A102030作業(yè)平均周轉(zhuǎn)時間T=14(分鐘)(d)短作業(yè)優(yōu)先法調(diào)度23第四章操作系統(tǒng)4.2處理器管理三、進(jìn)程調(diào)度當(dāng)作業(yè)管理程序?qū)⒃谟脩糇鳂I(yè)調(diào)入內(nèi)存后，作業(yè)即以進(jìn)程形式出現(xiàn)。進(jìn)程數(shù)目總是大于CPU數(shù)目。各進(jìn)程必將為爭奪CPU而競爭，得到CPU的運(yùn)行，得不到的只有等待。在內(nèi)存中的多個進(jìn)程具有不同的狀態(tài)，他們隨著系統(tǒng)運(yùn)行而不斷改變。進(jìn)程調(diào)度的任務(wù)就是控制、協(xié)調(diào)各進(jìn)程對CPU的競爭，按照一定的調(diào)度算法，使某一就緒進(jìn)程得到CPU，轉(zhuǎn)換成運(yùn)行狀態(tài)。

進(jìn)程是系統(tǒng)并發(fā)活動的體現(xiàn)。用動態(tài)的觀點(diǎn)看，操作系統(tǒng)是進(jìn)程的動態(tài)和并發(fā)執(zhí)行。進(jìn)程并發(fā)執(zhí)行：在一定時間內(nèi)系統(tǒng)內(nèi)2個或2個以上的進(jìn)程同時處于開始運(yùn)行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的。24第四章操作系統(tǒng)4.2處理器管理1.進(jìn)程的定義進(jìn)程有很多各式各樣的定義，如：

程序在處理機(jī)上的運(yùn)行進(jìn)程是這樣的計(jì)算部分，它可以與別的進(jìn)程并行運(yùn)行在自身的虛擬地址空間運(yùn)行的一個單獨(dú)的程序.一個具有一定獨(dú)立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運(yùn)行活動進(jìn)程既和程序有關(guān)，又與程序不同25第四章操作系統(tǒng)4.2處理器管理原來程序的概念已經(jīng)難以刻畫和反映系統(tǒng)中的情況※

程序概念反映不了動態(tài)性，系統(tǒng)中的程序?qū)嶋H上是處于不斷變化的狀態(tài)※

程序反映不了系統(tǒng)中的并行特性(運(yùn)行于不同的集合上，將屬于不同的進(jìn)程)進(jìn)程的特征：①動態(tài)性：進(jìn)程是程序的執(zhí)行，進(jìn)程有生命過程，是短暫的②并發(fā)性：多個進(jìn)程可同存于內(nèi)存中，能在一段時間內(nèi)同時

運(yùn)行③獨(dú)立性：獨(dú)立運(yùn)行的基本單位，獨(dú)立獲得資源和調(diào)度的基

本單位完成某個功能的指令的集合26第四章操作系統(tǒng)4.2處理器管理④異步性：各進(jìn)程按各自獨(dú)立的不可預(yù)知的速度向前推進(jìn)進(jìn)程的組成包括程序和數(shù)據(jù)，以及進(jìn)程控制塊。一個程序可對應(yīng)多個進(jìn)程，

一個進(jìn)程可包含多個程序(調(diào)用其他程序，共同組成一個”運(yùn)行的活動”)2.進(jìn)程的狀態(tài)轉(zhuǎn)換進(jìn)程有三種基本狀態(tài)：就緒、運(yùn)行、阻塞

進(jìn)程在生命消亡前處于且僅處于三種基本狀態(tài)之一，并且在單處理器系統(tǒng)中，任何時刻只有一個進(jìn)程處于運(yùn)行狀態(tài)，其他進(jìn)程分別處于就緒和阻塞狀態(tài)。

不同操作系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同27第四章操作系統(tǒng)4.2處理器管理（1）就緒狀態(tài)：進(jìn)程已具備各種必要的資源，只等待獲得CPU。(得到CPU即可運(yùn)行)（2）運(yùn)行狀態(tài)：系統(tǒng)根據(jù)調(diào)度算法，將CPU分配給某一個就緒進(jìn)程使之運(yùn)行，該進(jìn)程就處于運(yùn)行狀態(tài)。當(dāng)運(yùn)行的進(jìn)程由于分配的CPU時間已到或是由于I/O要求，則必須交出CPU就轉(zhuǎn)入就緒或阻塞狀態(tài)。（3）阻塞(等待)狀態(tài)：進(jìn)程在運(yùn)行中由于要等待I/O設(shè)備或發(fā)生其它錯誤時，就轉(zhuǎn)入阻塞狀態(tài)。待到阻塞原因消除后，重新回到就緒狀態(tài)。(即使CPU空閑，它也不能運(yùn)行)進(jìn)程的三種基本狀態(tài)：28進(jìn)程各狀態(tài)之間轉(zhuǎn)換的示意圖狀態(tài)變化：就緒狀態(tài)－>運(yùn)行狀態(tài)運(yùn)行狀態(tài)－>就緒狀態(tài)運(yùn)行狀態(tài)－>阻塞狀態(tài)阻塞狀態(tài)－>就緒狀態(tài)等待－>運(yùn)行就緒－>等待不具有下列轉(zhuǎn)換：29第四章操作系統(tǒng)4.2處理器管理引起進(jìn)程狀態(tài)轉(zhuǎn)換的原因：1)CPU調(diào)度：從就緒隊(duì)列中調(diào)度一個進(jìn)程到CPU上運(yùn)行，該進(jìn)程就從就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)；與此同時，原運(yùn)行進(jìn)程從運(yùn)行狀態(tài)變?yōu)榫途w狀態(tài)2)進(jìn)程在運(yùn)行過程中需要等待某一事件，如等待分配某一資源，等待IO操作完成等。這時進(jìn)程主動推出CPU，并使自己處于阻塞狀態(tài)3)進(jìn)程所等待的事件發(fā)生了變化，如I/O完成了，進(jìn)程就解除阻塞狀態(tài)，變?yōu)榫途w狀態(tài)4)任何一個指定時刻必須且只能處于一種狀態(tài)。30五狀態(tài)進(jìn)程模型

新狀態(tài):

一個進(jìn)程剛剛建立，但尚未將其送入就緒隊(duì)列時的狀態(tài)；

終止?fàn)顟B(tài)：一個進(jìn)程已經(jīng)正?；虍惓＝Y(jié)束，OS已將它從就緒隊(duì)列移

出，但尚未撤銷。31第四章操作系統(tǒng)4.2處理器管理3.進(jìn)程控制塊(PCB)為了刻畫進(jìn)程的動態(tài)變化，通常把進(jìn)程表示為由程序段、私有數(shù)據(jù)塊和進(jìn)程控制塊組成。程序部分描述進(jìn)程本身所要完成的功能，而“私有數(shù)據(jù)塊”是接受程序規(guī)定操作的一組存儲單元的內(nèi)容，是操作的對象。為了描述一個進(jìn)程和其它進(jìn)程以及系統(tǒng)資源的關(guān)系，以及一個進(jìn)程在各個不同時期所處的狀態(tài)，采用了一個與進(jìn)程相聯(lián)系的數(shù)據(jù)塊，稱為進(jìn)程控制塊（PCB）。系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志進(jìn)程與PCB是一一對應(yīng)的32第四章操作系統(tǒng)4.2處理器管理PCB中的內(nèi)容：進(jìn)程描述信息：

?進(jìn)程標(biāo)識符(processID)，唯一，通常是一個整數(shù)

?進(jìn)程名，通?；诳蓤?zhí)行文件名（不唯一）

?用戶標(biāo)識符(userID)；進(jìn)程組關(guān)系進(jìn)程控制信息：?當(dāng)前狀態(tài)

?優(yōu)先級(priority)

?代碼執(zhí)行入口地址

?程序的外存地址

?運(yùn)行統(tǒng)計(jì)信息（執(zhí)行時間、頁面調(diào)度）33第四章操作系統(tǒng)4.2處理器管理?進(jìn)程的隊(duì)列指針?進(jìn)程的消息隊(duì)列指針?biāo)鶕碛械馁Y源和使用情況：?虛擬地址空間的現(xiàn)狀?打開文件列表CPU現(xiàn)場保護(hù)信息：?寄存器值（通用、程序計(jì)數(shù)器PC、狀態(tài)PSW，地址包括棧指針）?指向賦予該進(jìn)程的段/頁表的指針34第四章操作系統(tǒng)4.2處理器管理PCB表的組織方式：1)

索引方式：有著相同狀態(tài)的進(jìn)程的PCB組織在一個表格中，就緒/運(yùn)行/等待進(jìn)程表，系統(tǒng)中有一些固定單元分別指出各表的起始地址;35第四章操作系統(tǒng)4.2處理器管理2)

隊(duì)列方式：把具有相同狀態(tài)的所有進(jìn)程的PCB按優(yōu)先數(shù)排成一個或多個(每個優(yōu)先級一個)隊(duì)列采集隊(duì)列形式時，每個進(jìn)程的PCB中要增加一個鏈指針的表目項(xiàng)，以指向隊(duì)列的下一個進(jìn)程的PCB地址36第四章操作系統(tǒng)4.2處理器管理PCB的主要作用：記錄進(jìn)程的有關(guān)信息標(biāo)識信息，狀態(tài)信息，調(diào)度信息，通訊信息，已占用資源信息標(biāo)志進(jìn)程的存在

操作系統(tǒng)根據(jù)系統(tǒng)中是否存在進(jìn)程的PCB來知道該進(jìn)程存在與否，PCB是進(jìn)程存在的具體物理標(biāo)志和體現(xiàn)，是進(jìn)程調(diào)度的主要數(shù)據(jù)基。37第四章操作系統(tǒng)4.2處理器管理OS根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程，進(jìn)行控制和管理?調(diào)度前，要從各進(jìn)程的PCB中知道現(xiàn)行的狀態(tài)及優(yōu)先級；?調(diào)度時，根據(jù)PCB中保存的CPU狀態(tài)信息恢復(fù)現(xiàn)場，并根據(jù)指令和數(shù)據(jù)的內(nèi)存地址，找到程序和數(shù)據(jù)；?進(jìn)程執(zhí)行過程中，當(dāng)需要與其他進(jìn)程同步、通信時，也需要訪問PCB?當(dāng)進(jìn)程因某種原因暫停執(zhí)行時，需要保存CPU環(huán)境38第四章操作系統(tǒng)Linux中的PCB

在linux中每一個進(jìn)程都由structtask_struct

數(shù)據(jù)結(jié)構(gòu)來定義，這就是通常所說的PCB，它相當(dāng)大。/usr/src/linux-2.4/include/linux/sched.h

...pid_tpid;

進(jìn)程IDvolatilelong

state;

進(jìn)程狀態(tài)unsignedlong

policy;

調(diào)度策略(FIFO,roundrobin...)int

prio;

進(jìn)程優(yōu)先級structthread_structthread;CPU寄存器狀態(tài)信息structtask_struct*next_task,*prev_task;

構(gòu)成一循環(huán)的雙向鏈表，通過它可以遍歷執(zhí)行所有的現(xiàn)存進(jìn)程。...有關(guān)詳細(xì)，參考UnderstandingLinuxKernel--byrtsys.pdf39第四章操作系統(tǒng)Linux中進(jìn)程信息察看UID

進(jìn)程屬主的用戶ID號。PID

進(jìn)程ID號。

PPID父進(jìn)程的ID號。

C

進(jìn)程最近使用CPU的估算。

STIME

進(jìn)程開始時間,以“小時:分:秒”的形式給出。

TTY

該進(jìn)程建立時所對應(yīng)的終端,“?”表示該進(jìn)程不占用終端。

TIME

報(bào)告進(jìn)程累計(jì)使用的CPU時間。CMD

是command(命令)的縮寫，往往表示進(jìn)程所對應(yīng)的命令名。40第四章操作系統(tǒng)4.2處理器管理P0P1P2P4P5P6P3P7進(jìn)程控制對系統(tǒng)中全部進(jìn)程實(shí)施有效的管理，即它應(yīng)具有創(chuàng)建進(jìn)程、撤消進(jìn)程、改變進(jìn)程狀態(tài)的功能。進(jìn)程控制一般有原語來實(shí)現(xiàn)在樹型結(jié)構(gòu)系統(tǒng)中，一個進(jìn)程能夠創(chuàng)建一個或多個進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程。這樣就形成了一個進(jìn)程家族。如下圖所示。41第四章操作系統(tǒng)4.2處理器管理原語是機(jī)器指令的延伸，由若干條機(jī)器指令構(gòu)成，用以完成某一特定功能的程序段。它與一般過程的區(qū)別在于：它們是屬于“原子操作

atomicopertation”，即一個操作中的所有動作，要么全做，要么全不做。原語在執(zhí)行期間是不允許被中斷的。常用的進(jìn)程控制原語?創(chuàng)建原語?終止原語?阻塞原語、喚醒原語42第四章操作系統(tǒng)4.2處理器管理創(chuàng)建進(jìn)程原語1）申請空白PCB：為新進(jìn)程分配唯一的標(biāo)識符，并從PCB集合中索取一空白的PCB2）為新進(jìn)程分配資源，如內(nèi)存3）初始化進(jìn)程控制塊：

a)初始化標(biāo)識符信息：將系統(tǒng)分配的標(biāo)識符、父進(jìn)程標(biāo)識符填入新的PCB；

b)初始化處理器狀態(tài)信息：使程序計(jì)數(shù)器指向程序入口地址，棧指針指向棧頂

c)初始化處理器控制信息：設(shè)置進(jìn)程狀態(tài)和優(yōu)先級4）設(shè)置對應(yīng)的鏈接，如把新進(jìn)程加到就緒隊(duì)列的鏈表中43第四章操作系統(tǒng)4.2處理器管理終止進(jìn)程原語1)根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的

PCB，從中讀出該進(jìn)程的狀態(tài)2)回收進(jìn)程所占的全部資源3)遞歸刪除其所有子進(jìn)程，以妨它們成為不可控4)刪除PCB5)若刪除的是正在運(yùn)行的進(jìn)程，則請求重新調(diào)度44第四章操作系統(tǒng)4.2處理器管理進(jìn)程的阻塞與喚醒阻塞：正在執(zhí)行的進(jìn)程，當(dāng)所期待的某一事件尚未出現(xiàn)時，該進(jìn)程便通過調(diào)用阻塞原語（block）將自己阻塞，并插入到具有相同事件的阻塞隊(duì)列。進(jìn)程阻塞是進(jìn)程的自身的一種主動行為。喚醒：當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時，如I/O操作完成，則由合作進(jìn)程調(diào)用喚醒原語（wakeup）將其喚醒。

處于阻塞狀態(tài)的進(jìn)程是絕不可能叫醒它自己的。45第四章操作系統(tǒng)4.2處理器管理5.線程的引入進(jìn)程的兩個基本屬性※進(jìn)程是一個可擁有資源的基本單位?！M(jìn)程同時又是一個可獨(dú)立調(diào)度和分派的基本單位。

進(jìn)程作為一個資源擁有者，在創(chuàng)建、撤消、切換中，系統(tǒng)必須為之付出較大時空開銷。1）創(chuàng)建進(jìn)程：系統(tǒng)在創(chuàng)建進(jìn)程時，必須為之分配其所必需的、除處理機(jī)以外的所有資源。如內(nèi)存空間、I/O設(shè)備以及建立相應(yīng)的PCB結(jié)構(gòu)46第四章操作系統(tǒng)4.2處理器管理2）撤消進(jìn)程。系統(tǒng)在撤消進(jìn)程時，又必須先對這些資源進(jìn)行回收操作，然后再撤消PCB結(jié)構(gòu)。3）進(jìn)程切換。在對進(jìn)程進(jìn)行切換時，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，為此需花費(fèi)不少處理機(jī)時間。

由此可見，由于在進(jìn)程的創(chuàng)建、撤銷、切換中，系統(tǒng)必須為之付出較大的時空開銷，導(dǎo)致了系統(tǒng)中進(jìn)程的數(shù)量不宜過多，進(jìn)程切換的頻率不宜過高，但這也就限制了并發(fā)程度的進(jìn)一步提高。47第四章操作系統(tǒng)4.2處理器管理

為解決此問題，人們想到將進(jìn)程的上述兩個屬性分開，即對作為調(diào)度和分派的基本單位，不同時作為獨(dú)立分配資源的單位；對擁有資源的單位，不對之進(jìn)行頻繁切換。線程因而產(chǎn)生?在引入線程的OS中，線程是進(jìn)程中的一個實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。?線程自己基本不擁有系統(tǒng)資源，只擁有少量必不可少的資源：程序計(jì)數(shù)器、一組寄存器、棧。48第四章操作系統(tǒng)4.2處理器管理?線程可與同屬一個進(jìn)程的其它線程共享進(jìn)程所擁有的全部資源。?一個線程可以創(chuàng)建和撤消另一個線程；同一進(jìn)程中的多個線程之間可以并發(fā)執(zhí)行。由于線程之間的相互制約，導(dǎo)致了線程在運(yùn)行過程中也呈現(xiàn)間斷性，相應(yīng)的，線程也同樣有就緒、阻塞、執(zhí)行三種基本狀態(tài)。49第四章操作系統(tǒng)4.2處理器管理線程與進(jìn)程的比較：1．調(diào)度?在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和獨(dú)立調(diào)度、分派的基本單位都是進(jìn)程。在引入線程的系統(tǒng)中，線程是調(diào)度和分派的基本單位，而進(jìn)程是擁有資源的基本單位。?在同一個進(jìn)程內(nèi)線程切換不會產(chǎn)生進(jìn)程切換，由一個進(jìn)程內(nèi)的線程切換到另一個進(jìn)程內(nèi)的線程時，將會引起進(jìn)程切換。

2．并發(fā)性

在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個進(jìn)程中的多個線程之間亦可并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。

50第四章操作系統(tǒng)4.2處理器管理3．擁有資源：不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)，進(jìn)程都是擁有資源的一個獨(dú)立單位，線程一般不擁有系統(tǒng)資源，但它可以訪問隸屬進(jìn)程的資源。即一個進(jìn)程的所有資源可供進(jìn)程內(nèi)的所有線程共享。4．系統(tǒng)開銷：進(jìn)程的創(chuàng)建和撤消的開銷要遠(yuǎn)大于線程創(chuàng)建和撤消的開銷，進(jìn)程切換時，當(dāng)前進(jìn)程的CPU環(huán)境要保存，新進(jìn)程的CPU環(huán)境要設(shè)置，線程切換時只須保存和設(shè)置少量寄存器，并不涉及存儲管理方面的操作，可見，進(jìn)程切換的開銷遠(yuǎn)大于線程切換的開銷。同一進(jìn)程內(nèi)的各線程由于它們擁有相同的地址空間，它們之間的同步和通信的實(shí)現(xiàn)也變得比較容易。51第四章操作系統(tǒng)4.2處理器管理6、進(jìn)程調(diào)度算法由于進(jìn)程數(shù)多于處理器，它們必然競爭處理器。進(jìn)程調(diào)度就是按一定策略，動態(tài)地把處理機(jī)分配給就緒隊(duì)列中的某個進(jìn)程。主要是協(xié)調(diào)進(jìn)程對CPU的爭奪使用。進(jìn)程調(diào)度與作業(yè)調(diào)度有相似之處，不過進(jìn)程調(diào)度僅負(fù)責(zé)CPU分配，而作業(yè)調(diào)度要負(fù)責(zé)CPU之外的資源。進(jìn)程調(diào)度算法有些和作業(yè)調(diào)度相似

52第四章操作系統(tǒng)4.2處理器管理(1)先來先服務(wù)調(diào)度算法在進(jìn)程調(diào)度中，采用FIFO算法調(diào)度時，每次從就緒隊(duì)列中，選擇一個最先進(jìn)入該隊(duì)列的進(jìn)程，把處理器分配給它，使之運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件阻塞時，才放棄CPU。屬于不可搶先策略。

目前已經(jīng)很少采用，但常被結(jié)合在其他調(diào)度策略中，如對于具有相同優(yōu)先級的進(jìn)程，可使用先來先服務(wù)的原則。53第四章操作系統(tǒng)4.2處理器管理(2)優(yōu)先級調(diào)度算法按進(jìn)程的優(yōu)先級大小來調(diào)度，使高優(yōu)先級進(jìn)程得到優(yōu)先處理，進(jìn)程的優(yōu)先級由系統(tǒng)按一定的原則賦給。在實(shí)際系統(tǒng)中，通常采用動態(tài)優(yōu)先數(shù)策略，即一個進(jìn)程的優(yōu)先級不是固定的，而是隨許多因素的變化而變化，如進(jìn)程的等待時間、已使用的處理器時間或其他資源的使用情況等。優(yōu)先級策略：①非搶占的優(yōu)先級調(diào)度法：一旦某個進(jìn)程在運(yùn)行，高優(yōu)先級進(jìn)程無法搶占。②可搶先優(yōu)先級調(diào)度算法：任何時刻都嚴(yán)格按照高優(yōu)先級進(jìn)程在處理器上運(yùn)行的原則進(jìn)行進(jìn)程的調(diào)度。高優(yōu)先級進(jìn)程可以搶先于低優(yōu)先級進(jìn)程。54第四章操作系統(tǒng)4.2處理器管理(3)時間片輪轉(zhuǎn)算法進(jìn)程就緒隊(duì)列按進(jìn)程到達(dá)的時間來排序，也就是按照先來先服務(wù)原則。但進(jìn)程每次只占有一個時間片，完了必須釋放重新排隊(duì)等待運(yùn)行。此算法對時間片大小的選擇十分重要，太大退化為先來先服務(wù)，太小增大系統(tǒng)開銷。選擇時要考慮下面幾個因素：1.系統(tǒng)對響應(yīng)時間的要求2.就緒隊(duì)列中進(jìn)程的數(shù)目3.系統(tǒng)的處理能力55第四章操作系統(tǒng)4.2處理器管理(4)多級反饋隊(duì)列調(diào)度算法：在輪轉(zhuǎn)法中，加入到就緒隊(duì)列的進(jìn)程有如下3種情況：1)分配它的時間片用完，但進(jìn)程還未完成，就回到就緒隊(duì)列的末尾等待下一次調(diào)度去繼續(xù)執(zhí)行；2)分配給該進(jìn)程的時間片未用完，只是等待IO或由于進(jìn)程的互斥與同步關(guān)系而被阻塞，當(dāng)阻塞解除后就回到就緒隊(duì)列；3)新創(chuàng)建的進(jìn)程進(jìn)入就緒隊(duì)列.如果對這些進(jìn)程區(qū)別對待，給予不同的優(yōu)先級和時間片，可提高系統(tǒng)資源的利用率。56第四章操作系統(tǒng)4.2處理器管理調(diào)度方法：可以將就緒隊(duì)列分為N級，每個就緒隊(duì)列分配給不同的時間片，優(yōu)先級高的為第一級隊(duì)列，時間片最小，隨著隊(duì)列級別的降低，時間片加大。各隊(duì)列按照先進(jìn)先出調(diào)度算法；當(dāng)一個新進(jìn)程就緒后進(jìn)入第一級隊(duì)列；如果進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列；57第四章操作系統(tǒng)4.2處理器管理當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒時，可以搶占CPU，被搶占進(jìn)程回到原來一級就緒隊(duì)列的末尾；當(dāng)?shù)谝患夑?duì)列空時，才去調(diào)度第二級隊(duì)列，依此類推；當(dāng)時間片到后，進(jìn)程放棄CPU，回到下一級隊(duì)列。多級反饋隊(duì)列調(diào)度與優(yōu)先級法在原理上的區(qū)別

一個進(jìn)程在它執(zhí)行結(jié)束之前，可能需要反復(fù)多次通過反饋循環(huán)執(zhí)行，而不是優(yōu)先級中的一次執(zhí)行。58第四章操作系統(tǒng)4.2處理器管理課本上的幾點(diǎn)說明：①照顧IO型進(jìn)程是宗旨，目的在于充分利用外設(shè)以及對用戶交互及時響應(yīng)；此外，第1級隊(duì)列的時間片應(yīng)大于大多數(shù)IO型進(jìn)程產(chǎn)生一個IO請求所需時間②CPU型會降低到低級別的隊(duì)列，但也得到了較大的時間片，從而減少了進(jìn)程間轉(zhuǎn)接的次數(shù)③有些CPU型進(jìn)程，偶爾產(chǎn)生一次IO請求，但完成后仍舊需要很長的處理器等待時間，為減少進(jìn)程的調(diào)度次數(shù)，就讓其回到原來所在隊(duì)列，而不是從高級隊(duì)列逐漸下降。59第四章操作系統(tǒng)4.2處理器管理7、多道程序并發(fā)運(yùn)行出現(xiàn)的問題進(jìn)程的同步與互斥

（1）同步與互斥現(xiàn)象 “同步”是指系統(tǒng)中多個進(jìn)程中發(fā)生的事件存在某種時序上的關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個進(jìn)程運(yùn)行到某一點(diǎn)時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒狀態(tài)。例：司機(jī)與售票員的配合

60第四章操作系統(tǒng)4.2處理器管理司機(jī)售票員啟動車輛關(guān)車門行駛停車售票開車門售票員關(guān)門后司機(jī)才能啟動車輛，司機(jī)停車后售票員才能開門，司機(jī)和售票員的行動需要一定的協(xié)調(diào)。同樣，二個進(jìn)程之間有時也有這樣的依賴關(guān)系，必須要有一定的同步機(jī)制保證它們的執(zhí)行次序。61第四章操作系統(tǒng)4.2處理器管理“互斥”當(dāng)各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。例如：二個不同的進(jìn)程同時要求使用打印機(jī)，如果不加以控制，打印出的就是不同內(nèi)容的夾雜

又例如：有兩個進(jìn)程P1,P2都對公共變量count作加1操作P1:R1<－count;P2:R2<－count;P1:R1<－R1+1;count<－R1;P2:R2<－R2+1;count<－R2;Count中只增加162第四章操作系統(tǒng)4.2處理器管理同步互斥進(jìn)程－進(jìn)程進(jìn)程－資源－進(jìn)程時間次序上受到某種限制競爭某一物理資源時不允許進(jìn)程工作相互清楚對方的存在及其作用，交換信息不一定清楚其他進(jìn)程的情況往往指有幾個進(jìn)程共同完成一個任務(wù)往往指多個任務(wù)多個進(jìn)程間相互制約舉例：生產(chǎn)和消費(fèi)之間、發(fā)送和接收之間、作者和讀者之間舉例：交通十字路口、單軌火車的拔岔道63第四章操作系統(tǒng)4.2處理器管理臨界資源：一次只允許一個進(jìn)程使用的資源。臨界資源可能是硬件，也可能是軟件：變量，數(shù)據(jù)，表格，隊(duì)列等。臨界區(qū)：指一個程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)(共享資源)進(jìn)行操作。在進(jìn)程中涉及臨界資源的程序段叫臨界區(qū)。注：臨界區(qū)是對某一臨界資源而言的，對于不同臨界資源的臨界區(qū)，它們之間不存在互斥。如有程序段A、B是關(guān)于變量X的臨界區(qū)，而C、D是關(guān)于變量Y的臨界區(qū)，那么，A、B之間需要互斥執(zhí)行，C、D之間也要互斥執(zhí)行，而A與C、B與D之間不用互斥執(zhí)行。64第四章操作系統(tǒng)4.2處理器管理使用臨界區(qū)的時候必須遵循以下原則：

有空讓進(jìn)：當(dāng)無進(jìn)程在臨界區(qū)，任何有權(quán)使用臨界資源的進(jìn)程可進(jìn)入

等待：不允許二個及以上的進(jìn)程同時進(jìn)入臨界區(qū)

多中擇一：當(dāng)同時有多個進(jìn)程要求進(jìn)入臨界區(qū)時，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程等待65第四章操作系統(tǒng)4.2處理器管理2解決進(jìn)程同步與互斥的工具解決同步與互斥的工具有很多，可以由硬件或軟件實(shí)現(xiàn)。下面介紹一種用同步原語對某信號量進(jìn)行操作以實(shí)現(xiàn)同步與互斥的方法，通常稱為P-V操作。

?1965年，由荷蘭學(xué)者迪科斯徹(Dijkstra)提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)）?一種卓有成效的進(jìn)程同步機(jī)制

?最初提出的是二元信號量（互斥）推廣到一般信號量（多值）（同步）

?P、V操作是原語66第四章操作系統(tǒng)4.2處理器管理信號量(semaphore)是表示資源的物理實(shí)體，它只能被二個標(biāo)準(zhǔn)的同步原語(P、V操作)所訪問，操作系統(tǒng)利用它的狀態(tài)對進(jìn)程和資源進(jìn)行管理。P操作P(s)s←s-1if(s<0){

status(q)←”blocked”//將進(jìn)程q置為“阻塞”//

Insert(Q,q)}//將q插入阻塞隊(duì)列Q中//5.return67第四章操作系統(tǒng)4.2處理器管理P操作P(s)s←s-1if(s<0){

status(q)←”blocked”//將進(jìn)程q置為“阻塞”//

Insert(Q,q)}//將q插入阻塞隊(duì)列Q中//5.return當(dāng)s>0時信號燈數(shù)值表示該類資源的可用數(shù)，每執(zhí)行一次就意味著請求分配一個單位的該類資源給執(zhí)行P操作的進(jìn)程。因此描述為s=s-1.當(dāng)s<0表示已經(jīng)沒有此類資源可分配，因此請求資源的進(jìn)程被阻塞在相應(yīng)信號燈s的等待隊(duì)列。68第四章操作系統(tǒng)4.2處理器管理

V操作V(s)s←s+1if(s≤0){

remove(Q,R)//將R移出阻塞隊(duì)列

status(R)←”ready”//將R置為就緒

Insert(RL,R)}//將R插入就緒隊(duì)列RL中//6.returnV操作意味著進(jìn)程釋放一個單位的可用資源，故描述為s=s+1，若s≤0表示該信號燈等待隊(duì)列中有因請求該資源