軟件技術基礎 (10)處理器管理1

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

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

基本概念與術語

★作業(yè)和進程

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

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

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

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

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

★

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

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

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

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

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

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

★處理器管理

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

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

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

響應比=作業(yè)響應時間/估計運行時間

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

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

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

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

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

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

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

運行③獨立性：獨立運行的基本單位，獨立獲得資源和調度的基

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

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

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

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

新狀態(tài):

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

終止狀態(tài)：一個進程已經正?；虍惓＝Y束，OS已將它從就緒隊列移

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

?進程標識符(processID)，唯一，通常是一個整數(shù)

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

?用戶標識符(userID)；進程組關系進程控制信息：?當前狀態(tài)

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

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

?程序的外存地址

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

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

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

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

在linux中每一個進程都由structtask_struct

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

...pid_tpid;

進程IDvolatilelong

state;

進程狀態(tài)unsignedlong

policy;

調度策略(FIFO,roundrobin...)int

prio;

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

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

進程屬主的用戶ID號。PID

進程ID號。

PPID父進程的ID號。

C

進程最近使用CPU的估算。

STIME

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

TTY

該進程建立時所對應的終端,“?”表示該進程不占用終端。

TIME

報告進程累計使用的CPU時間。CMD

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

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

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

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

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

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

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

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

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

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

2．并發(fā)性

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

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

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

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

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

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

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

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

有空讓進：當無進程在臨界區(qū)，任何有權使用臨界資源的進程可進入

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

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

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

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

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

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

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

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

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

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

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

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

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