1第三章進(jìn)程管理3.1進(jìn)程概述3.2進(jìn)程控制塊3.3調(diào)度3.4UNIX系統(tǒng)的進(jìn)程調(diào)度3.5進(jìn)程控制3.6進(jìn)程的創(chuàng)建和圖像改換3.7線程

3.8Linux進(jìn)程管理23.1進(jìn)程概述程序的執(zhí)行有兩種方式：順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機(jī)系統(tǒng)；現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。3程序：是一個(gè)在時(shí)間上嚴(yán)格有序的指令集合。程序規(guī)定了完成某一任務(wù)時(shí)，計(jì)算機(jī)所需做的各種操作，以及這些操作的執(zhí)行時(shí)間。程序的順序執(zhí)行：具有獨(dú)立功能的程序獨(dú)占CPU直至得到最終結(jié)果的過程。程序4程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。

S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;56程序順序執(zhí)行時(shí)的特征（1）順序性：（執(zhí)行的順序性）由于內(nèi)存中每次只有一道程序，因此各個(gè)程序是按次序執(zhí)行的，即執(zhí)行完一個(gè)以后，再執(zhí)行下一個(gè)。（2）封閉性：獨(dú)占全部資源，計(jì)算機(jī)的狀態(tài)只由于該程序的控制邏輯所決定（3）可再現(xiàn)性：結(jié)果的再現(xiàn)性，初始條件相同則結(jié)果相同。7程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行8程序并發(fā)執(zhí)行時(shí)的特征

間斷(異步)性：執(zhí)行的順序性被打破，“走走停停”，一個(gè)程序可能走到中途停下來，失去原有的時(shí)序關(guān)系；失去封閉性：資源的獨(dú)占性被打破，共享資源，受其他程序的控制邏輯的影響。如：一個(gè)程序?qū)懙酱鎯ζ髦械臄?shù)據(jù)可能被另一個(gè)程序修改，失去原有的不變特征。失去可再現(xiàn)性：失去封閉性－>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。9不加控制的并發(fā)執(zhí)行所帶來的影響例：為了了解某單行道的交通流量，在路口安放一個(gè)監(jiān)視器，功能是有車通過該路段時(shí)，就向計(jì)算機(jī)發(fā)送一個(gè)信號。程序A功能：接收到監(jiān)視器信號時(shí)，就在計(jì)數(shù)單元COUNT上加1；程序B功能：每個(gè)半個(gè)小時(shí)，打印COUNT的值，然后清零。程序A：While(1){A1:收到監(jiān)視器信號；A2:COUNT=COUNT+1;}程序B：While(1){B1:延遲半小時(shí)；B2:打印COUNT的值;B3:COUNT=0;}(w)A1A2B1B2A1A2B3(r)A1A2B1A1A2B2B3103.1.1進(jìn)程的概念

程序本身完全是個(gè)靜態(tài)的概念（程序是完成某個(gè)功能的指令的集合），而系統(tǒng)及其中的各個(gè)程序?qū)嶋H上是處于不斷變化的狀態(tài)，程序的概念反映不了這種動態(tài)性；其次，程序概念也反映不了系統(tǒng)中的并行特性。綜上所述，靜態(tài)的程序概念已不敷使用，需要引用一個(gè)新的概念——“進(jìn)程”。11進(jìn)程的概念進(jìn)程是程序處于一個(gè)執(zhí)行環(huán)境中在一個(gè)數(shù)據(jù)集上的運(yùn)行過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)可并發(fā)執(zhí)行的獨(dú)立單位。12進(jìn)程的特征（1）動態(tài)性進(jìn)程的實(shí)質(zhì)是程序的一次執(zhí)行過程，因此，動態(tài)性是進(jìn)程的最基本特征。動態(tài)性還表現(xiàn)為：“它由創(chuàng)建而產(chǎn)生，由‘調(diào)度’而執(zhí)行，由撤消而消亡”。可見，進(jìn)程有一定的生命期，而程序只是一組有序指令的集合，并存放于某種介質(zhì)上，本身并無運(yùn)動的含義，因此是靜態(tài)的。（2）并發(fā)性這是指多個(gè)進(jìn)程能在一段時(shí)間內(nèi)同時(shí)運(yùn)行，并發(fā)性是進(jìn)程的重要特征。引入進(jìn)程的目的也正是為了使其程序能和其他進(jìn)程的程序并發(fā)執(zhí)行，而程序（沒有建立進(jìn)程）是不能并發(fā)執(zhí)行的（由于程序不反映執(zhí)行過程）。13進(jìn)程的特征（3）獨(dú)立性這是指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立調(diào)度的基本單位，凡未建立進(jìn)程的程序，都不能作為一個(gè)獨(dú)立的單位參加運(yùn)行。只有進(jìn)程有資格向系統(tǒng)提出申請資源并獲得系統(tǒng)提供的服務(wù)。（4）異步性這是指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程按異步方式運(yùn)行。（5）結(jié)構(gòu)性為使進(jìn)程能獨(dú)立運(yùn)行，應(yīng)為之配置一個(gè)稱為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)，簡稱PCB。14

進(jìn)程和程序的聯(lián)系與區(qū)別：（1）聯(lián)系。程序是構(gòu)成進(jìn)程的組成部分之一，一個(gè)進(jìn)程的運(yùn)行目標(biāo)是執(zhí)行它所對應(yīng)的程序，如果沒有程序，進(jìn)程就失去了其實(shí)際存在的意義。15

進(jìn)程和程序的聯(lián)系與區(qū)別：（2）區(qū)別。進(jìn)程是程序的一次動態(tài)執(zhí)行活動，而程序是進(jìn)程運(yùn)行的靜態(tài)描述文本。一個(gè)進(jìn)程可以執(zhí)行一個(gè)或多個(gè)程序，反之，同一程序也可被多個(gè)進(jìn)程同時(shí)執(zhí)行。程序是一種軟件資源，它可以長期保存，而進(jìn)程是一次執(zhí)行過程，它是暫時(shí)存在的、動態(tài)地產(chǎn)生和中止的。163.1.2進(jìn)程的組成進(jìn)程是在一個(gè)上下文的執(zhí)行環(huán)境中執(zhí)行的，這個(gè)執(zhí)行環(huán)境稱為進(jìn)程的映像，或稱圖像。它包括處理機(jī)中各通用寄存器的值、進(jìn)程的內(nèi)存映像、打開文件的狀態(tài)和進(jìn)程占用資源的信息等很多部分。進(jìn)程映像的關(guān)鍵部分是存儲器映像。進(jìn)程存儲器映像由以下幾部分組成：進(jìn)程控制塊、進(jìn)程執(zhí)行的程序（code）、進(jìn)程執(zhí)行時(shí)所用的數(shù)據(jù)、進(jìn)程執(zhí)行時(shí)使用的工作區(qū)17進(jìn)程的組成181.進(jìn)程控制塊進(jìn)程控制塊PCB（ProcessControlBlock）是系統(tǒng)用于查詢和控制進(jìn)程運(yùn)行的檔案，它描述進(jìn)程的特征，記載進(jìn)程的歷史，決定進(jìn)程的命運(yùn)。由于PCB較大，一些系統(tǒng)將其分割成兩部分：一部分是進(jìn)程基本控制塊，這部分記錄不管進(jìn)程是否在執(zhí)行，操作系統(tǒng)都需要訪問的進(jìn)程控制信息，因此，進(jìn)程基本控制塊要常駐內(nèi)存；另一部分是進(jìn)程擴(kuò)充控制塊，當(dāng)進(jìn)程不處于執(zhí)行狀態(tài)時(shí)，操作系統(tǒng)就不會訪問這部分信息，擴(kuò)充控制塊能對換到盤交換區(qū)中。192.共享正文段用高級語言編寫的程序一般是可重入的“純代碼”，也即是它可以被多個(gè)進(jìn)程并發(fā)地執(zhí)行的。共享正文段不限于包括程序，還可包括不可修改的常數(shù)。用戶用C語言所編的程序經(jīng)編譯后產(chǎn)生的代碼也是作為共享正文段裝入內(nèi)存的203.數(shù)據(jù)區(qū)進(jìn)程執(zhí)行時(shí)用到的數(shù)據(jù)，如C程序中的外部變量和靜態(tài)變量；如進(jìn)程執(zhí)行的程序?yàn)榉枪蚕沓绦颍ㄈ缬脜R編語言編寫，可以在執(zhí)行時(shí)修改執(zhí)行的代碼和其中夾帶的數(shù)據(jù)），則也可構(gòu)成數(shù)據(jù)區(qū)的一部分。214.工作區(qū)進(jìn)程在核心態(tài)運(yùn)行時(shí)的工作區(qū)為核心棧；在用戶態(tài)下運(yùn)行時(shí)的工作區(qū)為用戶棧；在調(diào)用核心的函數(shù)或用戶函數(shù)時(shí)，兩種棧分別用于傳遞參數(shù)、存放返回地址、保護(hù)現(xiàn)場以及為局部動態(tài)變量提供存儲空間。此外，核心棧還可用于保護(hù)中斷現(xiàn)場，用戶棧還用于向主程序（main函數(shù)）傳遞命令行參數(shù)等。223.1.3進(jìn)程的狀態(tài)及其變化進(jìn)程具有生存期，它有一個(gè)創(chuàng)建、活動及消亡的過程。進(jìn)程在其活動期間可以因外部和內(nèi)部的原因進(jìn)入“睡眠”階段?！八摺钡倪M(jìn)程會被“喚醒”而繼續(xù)先前的活動。為了完成一組特定的任務(wù)，進(jìn)程也可采用“克隆”技術(shù)，生成一個(gè)或多個(gè)子進(jìn)程，互相配合地工作。進(jìn)程在其整個(gè)生存期間可處于不同的狀態(tài)，有一些不同的特征 23就緒(Ready)狀態(tài)：一個(gè)進(jìn)程已經(jīng)具備運(yùn)行條件，但由于無CPU暫時(shí)不能運(yùn)行的狀態(tài)（當(dāng)調(diào)度給其CPU時(shí)，立即可以運(yùn)行)。“萬事俱備，只欠東風(fēng)”。位于“就緒隊(duì)列”中。2)執(zhí)行狀態(tài)(Running)：進(jìn)程占有了包括CPU在內(nèi)的全部資源，，并在CPU上運(yùn)行。3)阻塞狀態(tài)(Blocked)

：也稱等待態(tài)、睡眠態(tài)、封鎖態(tài)、掛起態(tài)等。指進(jìn)程因等待某種事件的發(fā)生而暫時(shí)不能運(yùn)行的狀態(tài)（即使CPU空閑，該進(jìn)程也不可運(yùn)行）。處于阻塞態(tài)的進(jìn)程位于阻塞隊(duì)列中。 24運(yùn)行Running就緒Ready阻塞Blocked

DispatchTimeoutEventWaitEventOccurs基本狀態(tài)間的轉(zhuǎn)換25

在實(shí)際的操作系統(tǒng)中，為了管理和調(diào)度的便利，還將進(jìn)程的狀態(tài)進(jìn)一步細(xì)分，例如，UNIX系統(tǒng)V定義了10種進(jìn)程的狀態(tài)：#defineSSLEEP1

睡眠狀態(tài)#defineSWAIT2

等待狀態(tài)，該狀態(tài)已被廢棄#defineSRUN3

執(zhí)行狀態(tài)或就緒狀態(tài)#defineSIDL4

創(chuàng)建子進(jìn)程狀態(tài)#defineSZOMB5

等待善后處理狀態(tài)#defineSSTOP6

進(jìn)程處于被跟蹤的暫停狀態(tài)#defineSXBRK7

因數(shù)據(jù)段擴(kuò)展時(shí)未滿足的換出狀態(tài)#defineSXSTK8

因棧段擴(kuò)展時(shí)未滿足的換出狀態(tài)#defineSXFRK9

創(chuàng)建子進(jìn)程時(shí)內(nèi)存不夠，父進(jìn)程鎖定在內(nèi)存的狀態(tài)#defineSXTXT10

因正文段擴(kuò)展未滿足而被換出的狀態(tài)26掛起狀態(tài)

引入掛起狀態(tài)的原因終端用戶的請求。：當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)問題，希望暫時(shí)使自己的程序靜止下來。亦即，使正在執(zhí)行的進(jìn)程暫停執(zhí)行；若此進(jìn)程正處于就緒狀態(tài)，則暫不接受調(diào)度。這種靜止?fàn)顟B(tài)稱為掛起狀態(tài)。(2)父進(jìn)程請求。(3)負(fù)荷調(diào)節(jié)的需要。(4)操作系統(tǒng)的需要。27被掛起進(jìn)程的特征能立即執(zhí)行，除非首先激活它。被掛起進(jìn)程可能是等待某事件的阻塞進(jìn)程，其阻塞條件獨(dú)立于掛起條件，即使阻塞事件發(fā)生，該進(jìn)程也不能執(zhí)行。能實(shí)施掛起操作的進(jìn)程包括：進(jìn)程自身、進(jìn)程的父進(jìn)程和操作系統(tǒng)。只有實(shí)施掛起操作的進(jìn)程才能激活被掛起進(jìn)程。282)進(jìn)程狀態(tài)的轉(zhuǎn)換在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱為靜止?fàn)顟B(tài)）到非掛起狀態(tài)（又稱為活動狀態(tài)）的轉(zhuǎn)換；或者相反?？捎幸幌聨追N情況：(1)活動就緒→靜止就緒。(2)活動阻塞→靜止阻塞。(3)靜止就緒→活動就緒。(4)靜止阻塞→活動阻塞。29具有掛起狀態(tài)的進(jìn)程狀態(tài)圖303.2進(jìn)程控制塊為了掌握進(jìn)程的運(yùn)行狀況和便于管理和控制進(jìn)程的運(yùn)行，操作系統(tǒng)為每一個(gè)進(jìn)程設(shè)置了一個(gè)數(shù)據(jù)結(jié)構(gòu)——進(jìn)程控制塊（PCB）。進(jìn)程控制塊是進(jìn)程的控制結(jié)構(gòu)，包含了進(jìn)程的描述信息、控制信息和資源信息以及現(xiàn)場保護(hù)區(qū)。311.進(jìn)程控制塊的作用進(jìn)程控制塊是由OS維護(hù)的用來記錄進(jìn)程相關(guān)信息和管理進(jìn)程設(shè)置的一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)。進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。PCB是進(jìn)程動態(tài)特性的集中反映。系統(tǒng)通過PCB感知進(jìn)程的存在，通過PCB中所包含的各項(xiàng)變量的變化，掌握進(jìn)程的狀態(tài)以達(dá)到控制進(jìn)程活動的目的；32PCB隨進(jìn)程的創(chuàng)建而填寫，隨進(jìn)程的撤消而釋放；系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志進(jìn)程與PCB是一一對應(yīng)的PCB結(jié)構(gòu)常駐內(nèi)存；系統(tǒng)將所有PCB組織成若干個(gè)隊(duì)列，存放在操作系統(tǒng)中專門開辟的PCB區(qū)內(nèi)。332.進(jìn)程控制塊中的信息1)進(jìn)程標(biāo)識符進(jìn)程標(biāo)識符用于惟一地標(biāo)識一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識符：

(1)內(nèi)部標(biāo)識符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識符，它通常是一個(gè)進(jìn)程的序號。設(shè)置內(nèi)部標(biāo)識符主要是為了方便系統(tǒng)使用。

(2)外部標(biāo)識符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進(jìn)程)在訪問該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系，還應(yīng)設(shè)置父進(jìn)程標(biāo)識及子進(jìn)程標(biāo)識。此外，還可設(shè)置用戶標(biāo)識，以指示擁有該進(jìn)程的用戶。342)處理機(jī)狀態(tài)

處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。

①通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問的，用于暫存信息，在大多數(shù)處理機(jī)中，有8~32個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過100個(gè)；②指令計(jì)數(shù)器，其中存放了要訪問的下一條指令的地址；③程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等；

④用戶棧指針，指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。353)進(jìn)程調(diào)度信息在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的信息，包括：

①進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和對換時(shí)的依據(jù)；②進(jìn)程優(yōu)先級，用于描述進(jìn)程使用處理機(jī)的優(yōu)先級別的一個(gè)整數(shù)，優(yōu)先級高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)；③進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等；④事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。364)進(jìn)程控制信息

①程序和數(shù)據(jù)的地址，是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；②進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號量等，它們可能全部或部分地放在PCB中；

③資源清單，是一張列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單；④鏈接指針，它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址。37PCB的存放有些系統(tǒng)將進(jìn)程控制塊分成兩個(gè)部分：一部分是進(jìn)程無論處于什么狀態(tài)，系統(tǒng)都可能要查詢和處理的PCB成員，這部分就要常駐內(nèi)存；另一部分是進(jìn)程不在執(zhí)行時(shí)系統(tǒng)就不需要訪問的PCB成員，在內(nèi)存緊張時(shí)可以將它們換到盤交換區(qū)，以為其他進(jìn)程騰出寶貴的內(nèi)存空間。在UNIX中，常駐內(nèi)存的進(jìn)程PCB部分是proc結(jié)構(gòu)；在UNIX中，非常駐內(nèi)存的PCB部分是進(jìn)程擴(kuò)充控制塊user結(jié)構(gòu)；383.進(jìn)程控制塊的組織方式早期的UNIX系統(tǒng)將進(jìn)程的proc結(jié)構(gòu)組成一個(gè)順序存放的線性表，系統(tǒng)中可以存在的最大進(jìn)程數(shù)受表的大小的限制（如50個(gè)）。當(dāng)要對處于某種狀態(tài)的進(jìn)程控制或調(diào)度時(shí)，就要掃描整個(gè)proc表，這大大地降低了系統(tǒng)的效率。系統(tǒng)V用鏈?zhǔn)椒绞浇M織PCB隊(duì)列，不同狀態(tài)的進(jìn)程鏈接成就緒隊(duì)列、阻塞隊(duì)列等不同的隊(duì)列。為了便于系統(tǒng)的調(diào)度和控制，對于就緒狀態(tài)進(jìn)程，還可以將其分成優(yōu)先級不同的幾個(gè)就緒隊(duì)列。對于阻塞進(jìn)程，可根據(jù)原因不同，組成若干個(gè)隊(duì)列。39403.3調(diào)度3.3.1調(diào)度概述1.高級調(diào)度(HighScheduling)

又稱為作業(yè)調(diào)度或長程調(diào)度，用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。因此有時(shí)也把作業(yè)調(diào)度稱為接納調(diào)度。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。

1)接納多少個(gè)作業(yè)，取決于多道程序度。

2)接納哪些作業(yè)，取決于調(diào)度算法412.中級調(diào)度(Intermediate-LevelScheduling)又稱中程調(diào)度，它決定處于交換區(qū)中的就緒進(jìn)程中哪一個(gè)可以調(diào)入內(nèi)存，以便直接參與對CPU的競爭。在內(nèi)存資源緊張時(shí)，為了將進(jìn)程調(diào)入內(nèi)存，必須將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程調(diào)至交換區(qū)，以便為調(diào)入進(jìn)程騰出空間。這相當(dāng)于使處于內(nèi)存中的進(jìn)程和處于盤交換區(qū)中的進(jìn)程交換了位置，故中級調(diào)度又稱為“對換調(diào)度”。中級調(diào)度是為了緩解內(nèi)存資源的緊張狀態(tài)，在多道程序范疇內(nèi)實(shí)現(xiàn)進(jìn)程動態(tài)覆蓋和進(jìn)程級的虛擬存儲器技術(shù)。一個(gè)進(jìn)程在其運(yùn)行期間可能需要經(jīng)過多次中級調(diào)度。423.低級調(diào)度(LowLevelScheduling)（進(jìn)程調(diào)度或短程調(diào)度）

它決定駐在內(nèi)存中的哪一個(gè)就緒進(jìn)程可以占用CPU，使其獲得實(shí)實(shí)在在的執(zhí)行權(quán)力，故低級調(diào)度又可稱處理機(jī)調(diào)度或分派調(diào)度。低級調(diào)度執(zhí)行頻度很高，調(diào)度算法也比較復(fù)雜，是操作系統(tǒng)中最活躍、最重要的調(diào)度程序，對系統(tǒng)的性能影響也最大。43443.3.2進(jìn)程調(diào)度策略進(jìn)程調(diào)度策略是指在什么情況下用什么方式，在內(nèi)存中的就緒進(jìn)程之間進(jìn)行切換和分配處理機(jī)。進(jìn)程切換的方式有兩種：一種是不可剝奪（或不可搶占）方式，即一個(gè)進(jìn)程在獲得處理機(jī)后，除非因運(yùn)行結(jié)束或進(jìn)入了阻塞狀態(tài)等原因自己放棄處理機(jī)，否則就可以一直運(yùn)行下去，不會被其他進(jìn)程搶占處理機(jī)；另一種是可剝奪方式，即在某些條件下系統(tǒng)可以強(qiáng)制剝奪正在運(yùn)行中進(jìn)程使用處理機(jī)的權(quán)利，將其分配給系統(tǒng)中另一個(gè)合適的就緒進(jìn)程45

在設(shè)計(jì)一個(gè)調(diào)度算法時(shí)，應(yīng)考慮以下的因素。①針對不同的系統(tǒng)應(yīng)當(dāng)考慮不同的設(shè)計(jì)目標(biāo)。如對于批處理系統(tǒng)應(yīng)當(dāng)以提高計(jì)算機(jī)系統(tǒng)的運(yùn)行效率、取得最大的作業(yè)吞吐量和減少作業(yè)平均周轉(zhuǎn)時(shí)間為主要目標(biāo)；對于交互式分時(shí)系統(tǒng)，應(yīng)當(dāng)以能及時(shí)響應(yīng)用戶的請求為主要目標(biāo)；對于實(shí)時(shí)系統(tǒng)，應(yīng)當(dāng)能對緊急事件做出及時(shí)處理和安全可靠為頭等重要的考慮因素。②調(diào)度算法應(yīng)能充分使用系統(tǒng)中各種類型的資源，使多個(gè)設(shè)備能并行地工作46③應(yīng)當(dāng)既能在某一原則下公平地對待系統(tǒng)中的各個(gè)進(jìn)程，使它們能均衡地使用處理機(jī)，也能考慮不同類型進(jìn)程具有不同的優(yōu)先權(quán)利，在一定程度下滿足用戶對優(yōu)先級的要求，但也不能造成某些低優(yōu)先權(quán)的進(jìn)程可能無限期地推遲任務(wù)完成的時(shí)間。④合理的系統(tǒng)開銷473.3.3進(jìn)程調(diào)度算法

在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度；但也有些調(diào)度算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。481.先來先服務(wù)調(diào)度算法（FCFS-FirstComeFirstServe

）

按照作業(yè)進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動等待時(shí)間最長的作業(yè)。優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、公平缺點(diǎn)：沒考慮資源利用率和作業(yè)的特殊性，對短作業(yè)不公平。49先來先服務(wù)調(diào)度算法帶權(quán)周轉(zhuǎn)時(shí)間＝周轉(zhuǎn)時(shí)間/請求服務(wù)時(shí)間50短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法

短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。5152SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)：

(1)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。

(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時(shí)處理。

(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。53

2.時(shí)間片輪轉(zhuǎn)法在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。54時(shí)間片輪轉(zhuǎn)法比較適合于交互式的分時(shí)系統(tǒng)，對于用戶輸入的每一條命令，系統(tǒng)能保證在一個(gè)不太長的時(shí)間內(nèi)對此做出響應(yīng)。時(shí)間片輪轉(zhuǎn)法是剝奪式調(diào)度算法，因此系統(tǒng)需要花費(fèi)額外開銷用于各個(gè)就緒進(jìn)程間的切換。系統(tǒng)的效率與時(shí)間片大小的設(shè)置有關(guān)。如時(shí)間片設(shè)置過大，系統(tǒng)與用戶間的交互性就差，會招致用戶的埋怨；如時(shí)間片設(shè)置太小，進(jìn)程間切換過分頻繁，系統(tǒng)開銷就增大。55為了適應(yīng)不同進(jìn)程的運(yùn)行特點(diǎn)，在系統(tǒng)中可設(shè)置時(shí)間片大小不同的n個(gè)隊(duì)列，如時(shí)間片長度可分為10ms、50ms和200ms等。調(diào)度程序可將運(yùn)行時(shí)間短、交互性強(qiáng)或I/O繁忙的進(jìn)程安排在時(shí)間片小的隊(duì)列，這樣可以提高系統(tǒng)的響應(yīng)速度和減少周轉(zhuǎn)時(shí)間而對于需要連續(xù)占用處理機(jī)的進(jìn)程可安排在時(shí)間片長的隊(duì)列中，這樣可減少進(jìn)程切換的開銷。一個(gè)進(jìn)程處于哪一個(gè)時(shí)間片的隊(duì)列，可以在運(yùn)行時(shí)根據(jù)它的先前運(yùn)行狀況加以調(diào)整。563.優(yōu)先級調(diào)度算法

為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)（FPF）調(diào)度算法。當(dāng)把該算法用于作業(yè)調(diào)度時(shí)，系統(tǒng)將從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)，裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。57

對于優(yōu)先權(quán)調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)、還是動態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。

1)靜態(tài)優(yōu)先權(quán)

靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。58確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下幾個(gè)方面：①系統(tǒng)進(jìn)程執(zhí)行和完成的是系統(tǒng)功能，應(yīng)當(dāng)賦予它們比用戶進(jìn)程高的優(yōu)先級。②短作業(yè)的進(jìn)程可以賦予較高的優(yōu)先級，這樣可減少作業(yè)的平均等待時(shí)間，提高系統(tǒng)的吞吐量。③I/O繁忙的進(jìn)程只要求較短的處理機(jī)時(shí)間，讓該類進(jìn)程優(yōu)先獲得CPU。④根據(jù)用戶作業(yè)的申請，系統(tǒng)可以分配一些進(jìn)程較高的優(yōu)先級，一般這意味著要提高收費(fèi)標(biāo)準(zhǔn)。靜態(tài)優(yōu)先權(quán)法也很適合于實(shí)時(shí)系統(tǒng)，因?yàn)樵趯?shí)時(shí)系統(tǒng)中計(jì)算機(jī)所處理的所有事件是預(yù)知的，故其優(yōu)先級可根據(jù)事件的緊迫程度事先設(shè)定592)動態(tài)優(yōu)先權(quán)

動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先權(quán)以速率a提高。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。604.多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。優(yōu)點(diǎn)：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動態(tài)調(diào)節(jié)614.多級反饋隊(duì)列調(diào)度算法

(1)應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級。第一個(gè)隊(duì)列的優(yōu)先級最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長一倍。6263(2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個(gè)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。64(3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?~(i-1)隊(duì)列均空時(shí)，才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1~(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。65特點(diǎn)短進(jìn)程優(yōu)先處理。因此運(yùn)行時(shí)間短的進(jìn)程在經(jīng)過前面幾個(gè)隊(duì)列之后便已經(jīng)執(zhí)行完，而這些隊(duì)列中的進(jìn)程被優(yōu)先調(diào)度。設(shè)備資源利用率高。因?yàn)榕c設(shè)備打交道的進(jìn)程可能經(jīng)常會由于下面原因而進(jìn)入等待狀態(tài)：所申請的資源被占用，啟動了I/O傳輸。當(dāng)?shù)却录l(fā)生時(shí)，它將進(jìn)入第一級就緒隊(duì)列，盡快獲得處理機(jī)并使用資源。系統(tǒng)開銷小.因?yàn)檫\(yùn)行時(shí)間長的進(jìn)程最后進(jìn)入低優(yōu)先級的隊(duì)列，這些隊(duì)列的時(shí)間片較長，因而進(jìn)程的調(diào)度頻率較低。但是，如果高優(yōu)先級的隊(duì)列一直不為空，則低優(yōu)先級隊(duì)列的進(jìn)程可能長時(shí)間得不到運(yùn)行機(jī)會，可能會發(fā)生“餓死”現(xiàn)象。因此，允許采用某種原則將低優(yōu)先級隊(duì)列的進(jìn)程移到高優(yōu)先級隊(duì)列中665.實(shí)時(shí)調(diào)度策略在實(shí)時(shí)系統(tǒng)中，計(jì)算機(jī)必須響應(yīng)和控制的事件可分為周期事件和非周期事件；系統(tǒng)可能需要處理多種周期事件流。計(jì)算機(jī)能不能及時(shí)處理所有的事件，取決于事件的到達(dá)周期和需要處理的時(shí)間。例如，對于m個(gè)周期事件，如事件i的到達(dá)周期為Pi，所需CPU的處理時(shí)間為Ci秒，那么只有當(dāng)滿足：

∑Ci/Pi≤1(i=1,…,m)

時(shí)才是可以調(diào)度的。67

假如系統(tǒng)中有6個(gè)實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間為10ms，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：68實(shí)時(shí)調(diào)度算法也可分為靜態(tài)算法和動態(tài)算法。前者是在系統(tǒng)開始運(yùn)行之前就決定了的，而后者是在運(yùn)行期間才做出調(diào)度決定。下面討論幾種動態(tài)實(shí)時(shí)調(diào)度算法。①速率單調(diào)算法（RateMonotonicAlgorithm），該算法分配給各個(gè)進(jìn)程的優(yōu)先級正比于要處理觸發(fā)事件的發(fā)生頻率。如每隔20ms運(yùn)行一次的進(jìn)程優(yōu)先級為50，每隔100ms運(yùn)行一次的進(jìn)程的優(yōu)先級為10。運(yùn)行時(shí)調(diào)度程序總是運(yùn)行優(yōu)先級最高的就緒進(jìn)程，如需要，就搶占當(dāng)前運(yùn)行進(jìn)程的處理機(jī)。69②最早截止時(shí)間優(yōu)先算法（EarliestDeadlineFirst），是廣泛使用的調(diào)度算法。當(dāng)檢測到一個(gè)事件時(shí)，對應(yīng)的處理進(jìn)程就加入就緒進(jìn)程表中，該表以截止時(shí)間排序，調(diào)度程序總是使表中最早截止時(shí)間的那個(gè)進(jìn)程獲得運(yùn)行權(quán)。也就是說，使處理最緊迫事件的進(jìn)程優(yōu)先占用處理機(jī)。70③最小松弛時(shí)間優(yōu)先（LeastLaxity）算法，該算法先要計(jì)算每一個(gè)進(jìn)程的寬余（或稱松弛）時(shí)間，如果一個(gè)進(jìn)程需要運(yùn)行200ms，并且必須在250ms內(nèi)結(jié)束，它的松弛時(shí)間就是50ms。此算法選擇最小寬余時(shí)間的進(jìn)程，使其占用處理機(jī)，換句話說，該算法使處理最不能拖延的事件的進(jìn)程優(yōu)先占用處理機(jī)。假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。71723.4UNIX系統(tǒng)的進(jìn)程調(diào)度3.4.1進(jìn)程的切換調(diào)度算法1.UNIX的切換調(diào)度策略

UNIX系統(tǒng)的切換調(diào)度采用動態(tài)優(yōu)先權(quán)算法，其主要工作是在一個(gè)適當(dāng)?shù)臅r(shí)機(jī)，選擇一個(gè)優(yōu)先權(quán)最高，也即優(yōu)先數(shù)p_pri最小的就緒進(jìn)程，使其占用處理機(jī)。73UNIX系統(tǒng)中的每一個(gè)進(jìn)程在其運(yùn)行期間可以處于兩種狀態(tài)，即用戶態(tài)和核心態(tài)。系統(tǒng)對在用戶態(tài)下運(yùn)行的進(jìn)程，可以根據(jù)優(yōu)先數(shù)的大小，對它們進(jìn)行切換調(diào)度。對在核心態(tài)下運(yùn)行的進(jìn)程，除非它們完成了所要執(zhí)行的操作系統(tǒng)功能，即將返回用戶態(tài)下運(yùn)行，或它們因?yàn)槟承┰颍ㄈ缟暾堎Y源得不到滿足）而進(jìn)入睡眠狀態(tài)，或?yàn)榱送降男枰栽笗和?zhí)行，否則是不會對它們進(jìn)行切換調(diào)度的，也即UNIX核心從本質(zhì)上來說，是不可重入的742.優(yōu)先數(shù)的計(jì)算與運(yùn)行狀態(tài)相對應(yīng)，UNIX對進(jìn)程優(yōu)先數(shù)的處理也有兩種方法。對用戶態(tài)的進(jìn)程，內(nèi)核程序在適當(dāng)時(shí)機(jī)用下列公式計(jì)算進(jìn)程的優(yōu)先數(shù)：

p_pri=p_cpu/2+p_nice+PUSER+NZEROp_cpu是進(jìn)程占用處理機(jī)的量度，內(nèi)核程序在每次時(shí)鐘中斷（每秒50次或100次）中，使當(dāng)前執(zhí)行進(jìn)程的p_cpu加1，但最多加到80；每一秒鐘使所有就緒狀態(tài)的進(jìn)程的p_cpu衰減一半，即p_cpu=p_cpu/2。75p_nice是用戶可以通過系統(tǒng)調(diào)用nice（intpriority）設(shè)置的進(jìn)程優(yōu)先數(shù)偏置值。用戶可設(shè)置的偏置值范圍為0~20（有的系統(tǒng)為0~39），只有超級用戶能將p_nice置成負(fù)值，以提高進(jìn)程的優(yōu)先權(quán)。PUSER和NZERO是兩個(gè)常量，用于分界不同類型的優(yōu)先數(shù)763.優(yōu)先數(shù)的設(shè)置正在核心態(tài)運(yùn)行的進(jìn)程，其優(yōu)先數(shù)對調(diào)度是不起作用的，因?yàn)樗粫粡?qiáng)迫剝奪占用處理機(jī)的權(quán)利。只有當(dāng)它因等待系統(tǒng)資源等原因進(jìn)入睡眠狀態(tài)時(shí)，系統(tǒng)才根據(jù)等待事件的輕重緩急程度分配給其一個(gè)相應(yīng)的優(yōu)先數(shù)。只有當(dāng)它被喚醒之后，才以設(shè)置的優(yōu)先數(shù)參與競爭處理機(jī)，并在核心態(tài)下繼續(xù)運(yùn)行下去。77核心態(tài)進(jìn)程根據(jù)被設(shè)置優(yōu)先數(shù)的大小，可分為可中斷和不可中斷兩類優(yōu)先級。若進(jìn)程在可中斷的優(yōu)先級上睡眠，當(dāng)一個(gè)軟中斷信號（軟中斷的概念將在下一章敘述）到達(dá)時(shí)，它就被喚醒，進(jìn)入就緒隊(duì)列，以便執(zhí)行軟中斷處理程序。若進(jìn)程在不可中斷的優(yōu)先級上睡眠，它在收到軟中斷信號后，繼續(xù)睡眠，以保證它能優(yōu)先處理所等待的事件78PSWP（0）對換進(jìn)程（即中級調(diào)度0號進(jìn)程）睡眠的優(yōu)先數(shù)PINOD（10）等待磁盤I/O、管道；申請空閑磁盤塊，空閑I節(jié)點(diǎn)PRIBIO（20）等待緩沖區(qū)NI_PRILEV（25）有關(guān)網(wǎng)絡(luò)機(jī)制的睡眠NZERO（25）可中斷和不可中斷的分界常數(shù)PMSG（27）因等待消息而睡眠TTIPRI（28）

等待TTY輸入TTOPRI（29）

等待TTY輸出PWAIT（30）

等待子進(jìn)程終止PSLEP（39）

因系統(tǒng)調(diào)用pause，sleep而入睡PUSER（60）

核心態(tài)與用戶態(tài)優(yōu)先級的分界常數(shù)若干用戶態(tài)進(jìn)程優(yōu)先級

由計(jì)算而得到的優(yōu)先數(shù)PIDLE（127）

計(jì)算機(jī)空轉(zhuǎn)的最低優(yōu)先級794.進(jìn)程切換調(diào)度的時(shí)機(jī)

進(jìn)程自愿放棄處理機(jī)而引起的切換調(diào)度，屬于這一類的主要有以下幾種情況：—進(jìn)程完成了預(yù)定任務(wù)而進(jìn)入了SZOMB（等待善后處理）狀態(tài)；—進(jìn)程因等待某種資源進(jìn)入了睡眠狀態(tài)；—進(jìn)程因同步或互斥的需要，暫停執(zhí)行，放棄了處理機(jī)80

系統(tǒng)發(fā)現(xiàn)了可能更適合占用處理機(jī)的進(jìn)程，設(shè)置了強(qiáng)迫調(diào)度標(biāo)志runrun。屬于該類的主要情況有：—在喚醒睡眠進(jìn)程時(shí)，發(fā)現(xiàn)該進(jìn)程的優(yōu)先數(shù)小于現(xiàn)運(yùn)行進(jìn)程；—進(jìn)程由系統(tǒng)調(diào)用返回用戶態(tài)時(shí)，重新計(jì)算自己的優(yōu)先數(shù)，發(fā)現(xiàn)自己的優(yōu)先數(shù)上升了，要選擇可能更合適的進(jìn)程運(yùn)行；—在時(shí)鐘中斷程序中每一秒對所有優(yōu)先數(shù)大于（PUSER-NZERO）的進(jìn)程（一般原先在用戶態(tài)下運(yùn)行）重新計(jì)算優(yōu)先數(shù)，通常總要設(shè)置runrun標(biāo)志。在runrun標(biāo)志設(shè)置后，進(jìn)行強(qiáng)迫調(diào)度的具體時(shí)機(jī)是在中斷或陷入處理末尾。813.4.2切換調(diào)度程序

實(shí)施進(jìn)程切換調(diào)度的程序是swtch，其主要任務(wù)是：—保存現(xiàn)運(yùn)行進(jìn)程的現(xiàn)場信息；—在就緒隊(duì)列中選擇一個(gè)在內(nèi)存且優(yōu)先數(shù)p_pri最小的進(jìn)程，以使其占用處理機(jī)，如找不到這樣的進(jìn)程，計(jì)算機(jī)就空轉(zhuǎn)等待；—為新選中的進(jìn)程恢復(fù)現(xiàn)場823.4.3進(jìn)程的對換調(diào)度為了使更多的進(jìn)程能進(jìn)入系統(tǒng)，以使切換調(diào)度程序能選擇更合適的進(jìn)程占用處理機(jī)，以充分利用系統(tǒng)中的各種資源，UNIX在磁盤開辟一塊空間——進(jìn)程圖像的交換區(qū)，作為內(nèi)存的邏輯擴(kuò)充。UNIX系統(tǒng)中的0號進(jìn)程的主要任務(wù)就是按照換入換出算法在內(nèi)存和磁盤交換區(qū)之間傳輸進(jìn)程的圖像。83進(jìn)程圖像的換入算法是找在盤交換區(qū)的就緒進(jìn)程（SLOAD為0），按它們在外存駐留時(shí)間p_time從長到短的次序逐個(gè)將它們換入內(nèi)存，直至全部調(diào)入或內(nèi)存無足夠空閑區(qū)為止。有的系統(tǒng)在調(diào)入進(jìn)程的次序上除了考慮進(jìn)程在交換區(qū)駐留時(shí)間外，還要考慮進(jìn)程的大小和優(yōu)先數(shù)的因素；進(jìn)程優(yōu)先數(shù)小，尺寸小的也優(yōu)先換入內(nèi)存。進(jìn)程圖像的換入84進(jìn)程圖像的換出算法是首先將部分圖像已換出的進(jìn)程從內(nèi)存中完全換出，然后考慮處于睡眠或被跟蹤的進(jìn)程，最后是在內(nèi)存駐留時(shí)間最長的進(jìn)程，包括就緒狀態(tài)的進(jìn)程，但p_flag中包含SSYS或SLOCK位的進(jìn)程不能換出。進(jìn)程圖像的換出85習(xí)題1.若是在單批道處理系統(tǒng)中，已知進(jìn)入時(shí)間和所需計(jì)算的時(shí)間。忽略作業(yè)調(diào)度所花的時(shí)間。當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后就開始調(diào)度。

作業(yè)

進(jìn)入時(shí)間

所需計(jì)算時(shí)間

1

8：00

2小時(shí)

2

8：30

30分鐘

3

9：00

六分鐘

4

9：30

12分鐘（1）將分別采用先來先服務(wù)和短作業(yè)優(yōu)先的調(diào)度算法時(shí)，各個(gè)作業(yè)的開始時(shí)間，完成時(shí)間，周轉(zhuǎn)時(shí)間分別計(jì)算。

（2）分別求出在這兩種算法之下的平均周轉(zhuǎn)時(shí)間。86解答：（1）先來先服務(wù)調(diào)度算法：由于當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后就開始調(diào)度，所以作業(yè)1到達(dá)后，因?yàn)樽鳂I(yè)隊(duì)列中沒有其它作業(yè)，所有立刻得到調(diào)度了。作業(yè)進(jìn)入時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：002小時(shí)8：0010：002個(gè)小時(shí)28：3030分鐘10：0010：302個(gè)小時(shí)39：006分鐘10：3010：3696分鐘49：3012分鐘10：3610：4878分鐘平均周轉(zhuǎn)時(shí)間＝（120＋120＋96＋78）/4＝103.5分鐘87短作業(yè)優(yōu)先調(diào)度算法：作業(yè)進(jìn)入時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間18：002小時(shí)8：0010：00120分鐘28：3030分鐘10：1810：48138分鐘39：00六分鐘10：0010：0666分鐘49：3012分鐘10：0610：1848分鐘平均周轉(zhuǎn)時(shí)間＝（120＋138＋66＋48）/4＝93分鐘882.在一個(gè)兩道的批處理系統(tǒng)中，有六個(gè)作業(yè)進(jìn)入系統(tǒng)，他們的進(jìn)入時(shí)刻、估計(jì)運(yùn)行時(shí)間和優(yōu)先級如下表所示：作業(yè)號

進(jìn)入時(shí)刻

估計(jì)運(yùn)行時(shí)間

優(yōu)先級job1

8:00

90m

5job2

8:10

30m

6job3

8:30

20m

3job4

8:50

15m

8job5

9:20

10m

2job6

9:40

5m

4

系統(tǒng)采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)一旦被調(diào)度運(yùn)行就不再退出，但當(dāng)有新的作業(yè)投入運(yùn)行時(shí)，可以按照優(yōu)先級的進(jìn)行進(jìn)程調(diào)度。

（1）試給出各個(gè)作業(yè)的運(yùn)行時(shí)間序列。

（2）試計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間。89解答：兩道的批處理系統(tǒng)，說明內(nèi)存中只能同時(shí)存在兩個(gè)進(jìn)程；這個(gè)題目要考慮兩級調(diào)度，作業(yè)調(diào)度和進(jìn)程調(diào)度。作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法；進(jìn)程調(diào)度采用搶占式優(yōu)先級調(diào)度（假定優(yōu)先數(shù)越大優(yōu)先級越高）。8:00時(shí)刻：job1到達(dá)，立即被作業(yè)調(diào)度程序調(diào)入內(nèi)存，進(jìn)入內(nèi)存后立即被進(jìn)程調(diào)度程序調(diào)度開始運(yùn)行8:10時(shí)刻：job1運(yùn)行了10分鐘，剩余80分鐘，由于優(yōu)先級低于job2，被進(jìn)程調(diào)度程序調(diào)度處于就緒狀態(tài)。

job2到達(dá)，被作業(yè)調(diào)度程序調(diào)入內(nèi)存，由于優(yōu)先級高與正在運(yùn)行的job1，被進(jìn)程調(diào)度程序調(diào)度開始運(yùn)行。908:30時(shí)刻：job1在就緒隊(duì)列中等待了20分鐘，剩余80分鐘，繼續(xù)等待；

job2運(yùn)行了20分鐘，剩余10分鐘，繼續(xù)運(yùn)行；

job3到達(dá)，由于內(nèi)存中已有兩道作業(yè)，所以等待作業(yè)調(diào)度程序調(diào)度。8:40時(shí)刻：job1等待了30分鐘，剩余80分鐘，由于優(yōu)先級較高，被進(jìn)程調(diào)度程序調(diào)度到處理機(jī)上運(yùn)行；

job2運(yùn)行30分鐘，結(jié)束運(yùn)行；

job3在外存等待了10分鐘，被作業(yè)調(diào)度程序調(diào)入內(nèi)存，但因?yàn)閮?yōu)先級低于job1，暫時(shí)得不到進(jìn)程調(diào)度程序的調(diào)度，處于就緒狀態(tài)。918:50時(shí)刻：job1運(yùn)行了20分鐘，剩余70分鐘，繼續(xù)運(yùn)行；

job3在就緒隊(duì)列中等待了10分鐘，等待進(jìn)程調(diào)度程序調(diào)度；

job4到達(dá)，等待作業(yè)調(diào)度程序調(diào)度；9:20時(shí)刻：job1運(yùn)行了50分鐘，剩余40分鐘，繼續(xù)運(yùn)行；

job3在就緒隊(duì)列中等待了40分鐘，等待進(jìn)程調(diào)度程序調(diào)度；

job4在外存等待了30分鐘，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job5到達(dá)，等待作業(yè)調(diào)度程序調(diào)度；9:40時(shí)刻：job1運(yùn)行了70分鐘，剩余20分鐘，繼續(xù)運(yùn)行；

job3在就緒隊(duì)列中等待了60分鐘，繼續(xù)等待進(jìn)程調(diào)度程序調(diào)度；

job4在外存等待了50分鐘，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job5在外存等待了20分鐘，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job6到達(dá)，等待作業(yè)調(diào)度程序調(diào)度9210:00時(shí)刻：job1運(yùn)行了90分鐘，結(jié)束運(yùn)行；

job3在就緒隊(duì)列中等待了80分鐘，由于優(yōu)先級較低，繼續(xù)等待進(jìn)程調(diào)度程序調(diào)度；

job4在外存等待了70分鐘，由于估計(jì)運(yùn)行時(shí)間較長，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job5在外存等待了40分鐘，由于估計(jì)運(yùn)行時(shí)間較長，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job6在外存等待了20分鐘，由于估計(jì)運(yùn)行時(shí)間較短，被作業(yè)調(diào)度程序調(diào)入內(nèi)存；由于優(yōu)先級為4，高于已在內(nèi)存的job3，被進(jìn)程調(diào)度程序調(diào)度運(yùn)行。9310:05時(shí)刻：job6運(yùn)行了5分鐘，結(jié)束運(yùn)行。

job3在就緒隊(duì)列中等待了85分鐘，由于優(yōu)先級較高，被進(jìn)程調(diào)度程序調(diào)度運(yùn)行；

job4在外存等待了75分鐘，由于估計(jì)運(yùn)行時(shí)間較長，繼續(xù)等待作業(yè)調(diào)度程序調(diào)度；

job5在外存等待了45分鐘，由于估計(jì)運(yùn)行時(shí)間比job4短，被作業(yè)調(diào)度程序調(diào)入內(nèi)存；由于優(yōu)先級低于job3，所以不被進(jìn)程調(diào)度程序調(diào)度，在就緒隊(duì)列中等待；

9410:25時(shí)刻：job3運(yùn)行了20分鐘，結(jié)束運(yùn)行；

job4在外存等待了95分鐘，被作業(yè)調(diào)度程序調(diào)入內(nèi)存，由于優(yōu)先級高于job5，被進(jìn)程調(diào)度程序調(diào)度運(yùn)行；

job5在就緒隊(duì)列中等待了20分鐘，由于優(yōu)先級低于job4，所以不被進(jìn)程調(diào)度程序調(diào)度，仍在就緒隊(duì)列中等待；10:40時(shí)刻：job4運(yùn)行了15分鐘，結(jié)束運(yùn)行；

job5在就緒隊(duì)列中等待了35分鐘，被進(jìn)程調(diào)度程序調(diào)度運(yùn)行。10:50時(shí)刻：job5運(yùn)行了10分鐘，結(jié)束運(yùn)行。953、一單道批處理系統(tǒng)中,有如下五個(gè)作業(yè),并采用FCFS，SJF調(diào)度算法,試計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。(單位:小時(shí))作業(yè)提交時(shí)間運(yùn)行時(shí)間

１7．002．5２8．002.5３9．00149．000．50510．001．096答：FCFS作業(yè)提交時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

１7．002．59：302.51２8．002.512：0041.6３9．00113.004449．000．5013.304.59510．001．014.304.54.5平均周轉(zhuǎn)時(shí)間＝3.9；平均帶權(quán)周轉(zhuǎn)時(shí)間＝4.0297答：SJF作業(yè)提交時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

１7．002．59：302.51２8．002.514：306.52.6３9．00111：002249．000．5010：0012510．001．012：0022平均周轉(zhuǎn)時(shí)間＝2.8；平均帶權(quán)周轉(zhuǎn)時(shí)間＝1.92983.5進(jìn)程的控制一個(gè)進(jìn)程可能由于某種原因進(jìn)入掛起、阻塞或睡眠狀態(tài)。常見的原因有以下幾種。①請求系統(tǒng)服務(wù)或請求分配資源時(shí)得不到滿足，進(jìn)程暫時(shí)不能繼續(xù)執(zhí)行下去。②同步等待I/O的完成。③進(jìn)程間互相配合共同完成一個(gè)任務(wù)時(shí)。④在利用消息實(shí)現(xiàn)進(jìn)程間控制時(shí)，一進(jìn)程在等待某一進(jìn)程發(fā)消息時(shí)，也進(jìn)入了阻塞狀態(tài)。⑤進(jìn)程將自己掛起或進(jìn)程將自己某個(gè)子進(jìn)程掛起。3.5.1進(jìn)程的掛起993.5.2UNIX系統(tǒng)中的進(jìn)程睡眠和喚醒1.進(jìn)程睡眠在UNIX中，阻塞狀態(tài)稱為睡眠狀態(tài)。核心中，進(jìn)程通過調(diào)用sleep程序自愿地進(jìn)入睡眠狀態(tài)。其調(diào)用形式是：sleep(caddr_tchan,intdisp);參數(shù)chan是睡眠原因，它實(shí)際上是與睡眠事件相關(guān)的變量或數(shù)據(jù)結(jié)構(gòu)的地址。如系統(tǒng)用一個(gè)標(biāo)志變量event的值表示一個(gè)事件是否發(fā)生，那么等待該事件的睡眠原因就是該變量的地址&event。100如一個(gè)進(jìn)程因等待系統(tǒng)分配給它一個(gè)緩沖區(qū)或等待需緩沖的I/O完成，那么其睡眠原因的值就是相應(yīng)的緩沖區(qū)起始地址。變量disp的低7位是根據(jù)睡眠原因的緩急程度對睡眠進(jìn)程設(shè)置的優(yōu)先數(shù)，該優(yōu)先數(shù)是在進(jìn)程被喚醒后參與競爭處理機(jī)時(shí)起作用的。第8位為捕獲軟中斷的PCATCH標(biāo)志。當(dāng)該標(biāo)志置位時(shí)，若進(jìn)程收到軟中斷信號，則恢復(fù)進(jìn)程的運(yùn)行狀態(tài)，以執(zhí)行信號處理程序進(jìn)程睡眠101進(jìn)程睡眠UNIX系統(tǒng)V按睡眠原因chan將睡眠進(jìn)程排列到NHSQUE(64)個(gè)睡眠等待隊(duì)列：struct

proc*hsque[NHSQUE]當(dāng)正在將一個(gè)進(jìn)程排到睡眠隊(duì)列中時(shí)，核心要提高處理機(jī)的優(yōu)先級來屏蔽所有的中斷，以免在操作隊(duì)列指針時(shí)因中斷而引起混亂。核心還要將進(jìn)程proc結(jié)構(gòu)中的p_stat改為睡眠狀態(tài)，在p_wchan中記錄相應(yīng)的睡眠原因。1022.定時(shí)睡眠sleep（chan，disp）是內(nèi)核函數(shù)，用戶是不能直接調(diào)用的。UNIX向用戶另外提供了一個(gè)系統(tǒng)調(diào)用：sleep(seconds)

intseconds；該系統(tǒng)調(diào)用的功能是使調(diào)用進(jìn)程定時(shí)睡眠seconds秒，可用于進(jìn)程間的同步和定時(shí)處理事務(wù)1033.進(jìn)程的喚醒當(dāng)引起進(jìn)程阻塞的原因消除后，核心就可將阻塞進(jìn)程喚醒。喚醒的方法是根據(jù)睡眠原因先算出對應(yīng)的阻塞隊(duì)列。由于不同的原因可能掛在同一個(gè)隊(duì)列中，因此在喚醒因某一原因進(jìn)入睡眠的進(jìn)程時(shí)，在對應(yīng)的hash隊(duì)列中還要核查睡眠原因。但由于采用了數(shù)量眾多的hash隊(duì)列，每個(gè)隊(duì)列的長度一般都非常短，故大大減少了搜索的時(shí)間。104由于可能有多個(gè)進(jìn)程因同一原因而阻塞，一般的算法是核心將這些進(jìn)程全部喚醒。喚醒一個(gè)進(jìn)程并不意味著該進(jìn)程馬上可以占用處理機(jī)，而是僅將它排到就緒隊(duì)列中，使其有被調(diào)度的資格。因此，由于同一原因而喚醒的進(jìn)程將先競爭處理機(jī)，從而才可獲得有關(guān)的資源。如其中有一個(gè)獲得等待的資源后，其他競爭相同資源的進(jìn)程一旦獲得處理機(jī)，還得再轉(zhuǎn)入阻塞狀態(tài)。105喚醒函數(shù)UNIX核心的喚醒函數(shù)是wakeup(chan)，該函數(shù)的主要工作是首先提高處理機(jī)的優(yōu)先級，以防止函數(shù)的執(zhí)行被中斷，然后在睡眠隊(duì)列hsqueue[NHSQUE]中查找所有p_wchan等于參數(shù)chan的進(jìn)程，將找到進(jìn)程的p_stat置為SRUN（就緒狀態(tài)），消除原睡眠原因（p_wchan置為0），將喚醒的進(jìn)程送入就緒隊(duì)列中。1063.5.3進(jìn)程的終止和等待終止1.進(jìn)程的終止在UNIX中，一個(gè)進(jìn)程在完成了任務(wù)后，可用系統(tǒng)調(diào)用exit（intstatus）終止自己。status左移8位后作為傳送給父進(jìn)程的參數(shù)。進(jìn)程調(diào)用exit時(shí)，關(guān)閉所有的打開文件，釋放共享正文段、本進(jìn)程的數(shù)據(jù)段、用戶棧和核心棧的存儲空間，暫時(shí)保留proc結(jié)構(gòu)和盤交換區(qū)的user結(jié)構(gòu)副本，使進(jìn)程的狀態(tài)改為SZOMB狀態(tài)。1073.5.3進(jìn)程的終止和等待終止進(jìn)程終止時(shí)如有父進(jìn)程因等待子進(jìn)程的終止而處于睡眠狀態(tài)，就喚醒父進(jìn)程，最后調(diào)用swtch程序重新調(diào)度。父進(jìn)程被調(diào)度占用處理機(jī)時(shí)，在對進(jìn)入SZOMB的子進(jìn)程作善后處理后，釋放該子進(jìn)程的一切資源，使其生命期最后被終止。1082．父進(jìn)程等待子進(jìn)程終止創(chuàng)建子進(jìn)程的父進(jìn)程可以通過系統(tǒng)調(diào)用pid=wait(&status)等待它的一個(gè)子進(jìn)程終止。通過返回值pid，可獲得終止進(jìn)程的進(jìn)程標(biāo)識數(shù)。status的高位部分為子進(jìn)程傳給父進(jìn)程的參數(shù)，status的低8位部分為核心設(shè)置的系統(tǒng)調(diào)用狀態(tài)碼。如父進(jìn)程在調(diào)用wait時(shí)，子進(jìn)程已先期終止了，那么對子進(jìn)程作善后處理后，立即返回。1093.6進(jìn)程的創(chuàng)建和圖像改換3.6.1進(jìn)程的創(chuàng)建1.進(jìn)程創(chuàng)建的目的①在批處理系統(tǒng)中，當(dāng)部分作業(yè)已經(jīng)運(yùn)行完畢，退出了系統(tǒng)，操作系統(tǒng)準(zhǔn)備運(yùn)行下一個(gè)批作業(yè)時(shí)，它要?jiǎng)?chuàng)建一個(gè)進(jìn)程，讀入作業(yè)控制命令，以輸入作業(yè)和控制作業(yè)的運(yùn)行。②分時(shí)系統(tǒng)中的用戶在終端上登錄時(shí)，操作系統(tǒng)需要?jiǎng)?chuàng)建一個(gè)進(jìn)程，為用戶建立交互命令的環(huán)境，接收、分析并執(zhí)行用戶輸入的命令。110③在執(zhí)行批處理命令時(shí)，系統(tǒng)要產(chǎn)生一個(gè)進(jìn)程分析并處理批命令，對于批處理文件中的每一條命令，也要?jiǎng)?chuàng)造一個(gè)子進(jìn)程來執(zhí)行該命令。④當(dāng)用戶程序需要獲得系統(tǒng)服務(wù)時(shí)，操作系統(tǒng)要?jiǎng)?chuàng)建一個(gè)新進(jìn)程，代表用戶程序的利益，完成一種系統(tǒng)的功能。⑤用戶程序?yàn)榱瞬l(fā)執(zhí)行的需要，可以在運(yùn)行時(shí)創(chuàng)建一系列的進(jìn)程，各實(shí)現(xiàn)一個(gè)功能，并互相合作，完成總?cè)蝿?wù)。1112.創(chuàng)建進(jìn)程的主要步驟①為新進(jìn)程分配惟一的進(jìn)程標(biāo)識數(shù)。接著為新進(jìn)程分配進(jìn)程控制塊的空間，在進(jìn)程表中加入新項(xiàng)。②為新進(jìn)程分配進(jìn)程各部分映像所需的內(nèi)存空間，因此操作系統(tǒng)必須知道新進(jìn)程的程序、數(shù)據(jù)和用戶棧的大小。系統(tǒng)也能根據(jù)進(jìn)程的類型為之分配默認(rèn)的值，或在作業(yè)遞交時(shí)根據(jù)用戶的要求來分配。如果一個(gè)進(jìn)程由另一進(jìn)程產(chǎn)生，父進(jìn)程會將創(chuàng)建子進(jìn)程所需的存儲要求傳送給操作系統(tǒng)。如新進(jìn)程共享已存在內(nèi)存空間，就建立適當(dāng)?shù)逆溄有畔ⅰ?12③初始化進(jìn)程控制塊，如進(jìn)程標(biāo)識數(shù)、父進(jìn)程標(biāo)識數(shù)、程序計(jì)數(shù)器、系統(tǒng)棧指針、進(jìn)程的狀態(tài)等，根據(jù)進(jìn)程的性質(zhì)或默認(rèn)值初始化進(jìn)程的控制信息。進(jìn)程的運(yùn)行狀態(tài)一般初始化為就緒狀態(tài)或就緒掛起。除非進(jìn)程顯式申請較高的優(yōu)先級，否則優(yōu)先級設(shè)置為較低的級別。④子進(jìn)程復(fù)制父進(jìn)程擴(kuò)充控制塊。這意味著子進(jìn)程將共享父進(jìn)程的全部打開文件、信號處理方式等。子進(jìn)程復(fù)制了父進(jìn)程的數(shù)據(jù)區(qū)、核心棧和用戶棧，這意味著父子進(jìn)程程序執(zhí)行的當(dāng)前位置、狀態(tài)、數(shù)據(jù)區(qū)、變量的當(dāng)前值都是相同的。但隨著父、子進(jìn)程的各自獨(dú)立執(zhí)行，子進(jìn)程的映像將會與父進(jìn)程有明顯的差異。113如何使父子進(jìn)程完成不同的任務(wù)？由上可知，當(dāng)一個(gè)子進(jìn)程剛創(chuàng)建完成，它與父進(jìn)程共享執(zhí)行代碼，且起始執(zhí)行位置相同，數(shù)據(jù)區(qū)與棧段也相同。UNIX采用了在調(diào)用創(chuàng)建子進(jìn)程的系統(tǒng)調(diào)用后，使父子進(jìn)程具有不同的返回值，這樣就可以采用判斷語句，使父子進(jìn)程可以執(zhí)行不同的程序段，以便完成不同的任務(wù)。在執(zhí)行系統(tǒng)調(diào)用fork后，父進(jìn)程得到的返回值是所創(chuàng)建子進(jìn)程的標(biāo)識數(shù)，而子進(jìn)程的返回值為0。114main(){ intpid; printf("Beforefork\n"); while((pid=fork())==-1); if(pid){ printf("Itisparentprocess:PID=%d\n",getpid()); printf"Producedchild’sPID=%d\n",pid); }else printf("Itischildprocess:PID=%d\n",getpid()); printf("Itisparentorchildprocess:PID=%d\n",getpid());}1153.6.2進(jìn)程圖像的改換fork雖然能產(chǎn)生子進(jìn)程，將一個(gè)進(jìn)程變成了兩個(gè)，使它們能執(zhí)行不同的程序段和完成不同的功能，形成了多進(jìn)程并發(fā)運(yùn)行的必要條件，但這兩個(gè)進(jìn)程的圖像基本相同。對子進(jìn)程來說，fork之前的圖像已由父進(jìn)程執(zhí)行過了，子進(jìn)程是不會再從頭開始執(zhí)行的，因而這部分圖像的存在對子進(jìn)程是毫無意義的；fork之后父進(jìn)程所執(zhí)行的圖像部分的存在對子進(jìn)程來說也是一個(gè)浪費(fèi)。父進(jìn)程也有相似的問題。116UNIX為了配合fork，還提供了進(jìn)程圖像改換的exec系列的系統(tǒng)調(diào)用。exec的調(diào)用進(jìn)程用一個(gè)可執(zhí)行文件中的程序和數(shù)據(jù)取代當(dāng)前正在運(yùn)行的程序和數(shù)據(jù)，從而使主調(diào)進(jìn)程的圖像改換成新的圖像。盡管新執(zhí)行的程序與原進(jìn)程的執(zhí)行程序完全不同，但該調(diào)用并不形成新進(jìn)程，因?yàn)樵M(jìn)程的proc結(jié)構(gòu)和user結(jié)構(gòu)并不改換，其進(jìn)程標(biāo)識數(shù)p_pid與主調(diào)進(jìn)程相同，與父進(jìn)程的關(guān)系也沒有改變。進(jìn)程圖像的改換（exec）1173.7線程

本節(jié)討論一些與進(jìn)程管理有關(guān)的新概念，這些概念出現(xiàn)在一些現(xiàn)代的操作系統(tǒng)中。

如更深入地思考一下，可以發(fā)現(xiàn)進(jìn)程實(shí)際上包括了兩種不同的獨(dú)立概念：

一是與資源的所有權(quán)有關(guān)，

二是與執(zhí)行有關(guān)。

這種區(qū)別已經(jīng)導(dǎo)致了操作系統(tǒng)結(jié)構(gòu)的發(fā)展，出現(xiàn)了線程這種形式的結(jié)構(gòu)單元。

1183.7.1進(jìn)程和線程在進(jìn)程的概述一節(jié)中談到進(jìn)程包含了下列兩個(gè)特征。①資源擁有單位：進(jìn)程的虛址空間用于駐留進(jìn)程的圖像，進(jìn)程可以分配到主存和控制其他的系統(tǒng)資源，如I/O通道、I/O設(shè)備和文件等。②調(diào)度單位：進(jìn)程是可以并發(fā)執(zhí)行的獨(dú)立單元，它具有各種狀態(tài)和調(diào)度優(yōu)先級，是操作系統(tǒng)進(jìn)行調(diào)度的一個(gè)實(shí)體。119

換言之，由于進(jìn)程是一個(gè)資源的擁有者，因而在創(chuàng)建、撤銷和切換中，系統(tǒng)必須為之付出較大的時(shí)空開銷。正因如此，在系統(tǒng)中所設(shè)置的進(jìn)程，其數(shù)目不宜過多，進(jìn)程切換的頻率也不宜過高，這也就限制了并發(fā)程度的進(jìn)一步提高。若能將進(jìn)程的上述兩個(gè)屬性分開，由操作系統(tǒng)分開處理，亦即對于作為調(diào)度和分派的基本單位，不同時(shí)作為擁有資源的單位，以做到“輕裝上陣”；而對于擁有資源的基本單位，又不對之進(jìn)行頻繁的切換。正是在這種思想的指導(dǎo)下，形成了線程概念。1203.7.2多線程多線程指的是操作系統(tǒng)支持在單個(gè)進(jìn)程中執(zhí)行多個(gè)線程的能力。121在多線程環(huán)境中，進(jìn)程被定義為保護(hù)單位和資源分配單位。在一個(gè)進(jìn)程內(nèi)部可以有一至多個(gè)線程，每一個(gè)線程具有如下特征：線程的執(zhí)行狀態(tài)（運(yùn)行、就緒等）；當(dāng)不處于執(zhí)行狀態(tài)時(shí)保存的線程上下文環(huán)境，可以把線程看成是進(jìn)程內(nèi)一個(gè)獨(dú)立的程序計(jì)數(shù)器的運(yùn)轉(zhuǎn)；一個(gè)執(zhí)行棧；存取所屬進(jìn)程內(nèi)的主存和其他資源，在本進(jìn)程的范圍內(nèi)與所有線程共享這些資源線程描述122123在單線程的進(jìn)程模式中（這里沒有明顯的線程概念），進(jìn)程的表示包括進(jìn)程控制塊、用戶地址空間（包括程序和數(shù)據(jù)）和進(jìn)程執(zhí)行時(shí)處理調(diào)用函數(shù)和從函數(shù)返回所用的用戶棧和核心棧。當(dāng)進(jìn)程執(zhí)行時(shí)，處理器中的寄存器由該進(jìn)程控制，當(dāng)進(jìn)程不處于執(zhí)行狀態(tài)時(shí)，這些寄存器的內(nèi)容就被保護(hù)在進(jìn)程控制塊中。在多線程的環(huán)境中，仍然有單個(gè)進(jìn)程控制塊和與進(jìn)程相關(guān)聯(lián)的用戶地址空間，但是每個(gè)線程有各自的用戶棧、核心棧和控制塊，在控制塊中包含有寄存器圖像、優(yōu)先級和其他與線程有關(guān)的狀態(tài)信息。124這樣，一個(gè)進(jìn)程中的所有線程共享進(jìn)程的狀態(tài)和資源，它們駐留在相同的地址空間和訪問相同的數(shù)據(jù)。如一個(gè)線程修改了存儲空間中的一項(xiàng)數(shù)據(jù)，其他線程訪問該數(shù)據(jù)項(xiàng)時(shí)獲得了改變了的結(jié)果。如一個(gè)線程以讀方式打開了一個(gè)文件，同一進(jìn)程中的其他線程也能從該文件中讀數(shù)據(jù)125線程的屬性

在多線程OS中，通常是在一個(gè)進(jìn)程中包括多個(gè)線程，每個(gè)線程都是作為利用CPU的基本單位，是花費(fèi)最小開銷的實(shí)體。線程具有下述屬性。(1)輕型實(shí)體。線程中的實(shí)體基本上不擁有系統(tǒng)資源，只是有一點(diǎn)必不可少的、能保證獨(dú)立運(yùn)行的資源，比如，在每個(gè)線程中都應(yīng)具有一個(gè)用于控制線程運(yùn)行的線程控制塊TCB、用于指示被執(zhí)行指令序列的程序計(jì)數(shù)器、保留局部變量、少數(shù)狀態(tài)參數(shù)和返回地址等的一組寄存器和堆棧。126線程的屬性(2)獨(dú)立調(diào)度和分派的基本單位。在多線程OS中，線程是能獨(dú)立運(yùn)行的基本單位，因而也是獨(dú)立調(diào)度和分派的基本單位。由于線程很“輕”，故線程的切換非常迅速且開銷小。(3)可并發(fā)執(zhí)行。在一個(gè)進(jìn)程中的多個(gè)線程之間，可以并發(fā)執(zhí)行，甚至允許在一個(gè)進(jìn)程中的所有線程都并發(fā)執(zhí)行；同樣，不同進(jìn)程中的線程也能并發(fā)執(zhí)行。(4)共享進(jìn)程資源。在同一進(jìn)程中的各個(gè)線程，都可以共享該進(jìn)程所擁有的資源。127線程的性質(zhì)（1）線程是進(jìn)程內(nèi)的一個(gè)相對獨(dú)立的可執(zhí)行單元。因此不妨把線程看作是應(yīng)用中的一個(gè)子任務(wù)的執(zhí)行。（2）線程是操作系統(tǒng)的基本調(diào)度單元，因此線程中應(yīng)包含有調(diào)度所需的必要信息。（3）由于線程是被調(diào)度的基本單元，而進(jìn)程不是調(diào)度的單元。所以每個(gè)進(jìn)程在創(chuàng)建時(shí)，至少需要同時(shí)為該進(jìn)程創(chuàng)建一個(gè)線程。（4）需要時(shí)，線程可以創(chuàng)建其它線程。128線程的性質(zhì)（5）進(jìn)程是被分給并擁有資源的基本單位，同一進(jìn)程內(nèi)的多個(gè)線程共享該進(jìn)程的資源。但線程并不擁有資源，只是使用它們。（6）由于共享資源（包括數(shù)據(jù)和文件），所以線程間需要通信和同步機(jī)制。（7）線程有生命期，在生命期中有狀態(tài)的變化。129采用線程機(jī)制的優(yōu)點(diǎn)對于多線程機(jī)制而言，一個(gè)進(jìn)程可以有多個(gè)線程，這些線程共享該進(jìn)程資源。這些線程駐留在相同的地址空間，共享數(shù)據(jù)和文件。如果一個(gè)線程修改了一個(gè)數(shù)據(jù)項(xiàng)，其它線程可以了解和使用此結(jié)果數(shù)據(jù)。一個(gè)線程打開并讀一個(gè)文件時(shí)，同一進(jìn)程中的其它線程也可以同時(shí)讀此文件?？偠灾@些線程運(yùn)行在同一進(jìn)程的相同的地址空間內(nèi)，這有以下優(yōu)點(diǎn)。130采用線程機(jī)制的優(yōu)點(diǎn)（1）首先用于創(chuàng)建和撤銷線程的開銷比創(chuàng)建和撤銷進(jìn)程的系統(tǒng)開銷（CPU時(shí)間）要少的多。（2）CPU在線程之間切換的開銷也遠(yuǎn)比進(jìn)程之間切換的開銷小。因?yàn)榍袚Q的線程都在同一地址空間內(nèi)，只需修改線程控制表或隊(duì)列，不涉及地址空間和其它工作。（3）線程機(jī)制也增加了通訊的有效性。如果是在進(jìn)程之間通信，往往要求內(nèi)核的參與，以提供通訊機(jī)制和保護(hù)機(jī)制。而線程間通信是在同一進(jìn)程的地址空間內(nèi)，共享主存和文件，所以非常簡單，無需內(nèi)核參與。（4）方便和簡化了用戶的程序結(jié)構(gòu)工作。131注意：調(diào)度和分派是基于線程的，因此涉及到執(zhí)行的大多數(shù)狀態(tài)信息是以線程級數(shù)據(jù)結(jié)構(gòu)維護(hù)的。可是，對于一些影響一個(gè)進(jìn)程中所有線程的動作，操作系統(tǒng)必須在進(jìn)程級管理。例如，掛起涉及到換出主存空間，由于進(jìn)程中所有的線程共享相同的地址空間，所有的線程必須同時(shí)進(jìn)入掛起狀態(tài)。同樣，進(jìn)程的終止也終止了該進(jìn)程中的所有線程。1323.7.3線程的狀態(tài)與功能1.線程的狀態(tài)與操作

線程在運(yùn)行時(shí)，也具有下述三種基本狀態(tài)：①執(zhí)行狀態(tài)，表示線程正獲得處理機(jī)而運(yùn)行；②就緒狀態(tài)，指線程已具備了各種執(zhí)行條件，一旦獲得CPU便可執(zhí)行的狀態(tài)；