操作系統(tǒng)第二章進程管理

§2.1進程概念§2.2進程控制§2.3進程同步§2.4經(jīng)典進程的同步問題§2.5進程通信§2.6線程第二章進程管理

重點和難點：進程的定義和特征進程的同步和互斥用信號量機制解決進程同步、互斥問題2.1進程的概念2.1.1程序的順序執(zhí)行1.程序的順序執(zhí)行

在計算機系統(tǒng)中只有一個程序運行時，這個程序獨占系統(tǒng)中所有資源，其執(zhí)行不受外界影響。通常一個程序可分成若干個程序段，它們必須按照某種先后次序執(zhí)行，僅當前一操作執(zhí)行后，才能執(zhí)行后繼操作。例如：進行計算。I:輸入操作C:計算操作P:打印操作。在進行計算時，總是先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后將結果打印出來。I1C1P1P2I2C2

程序的順序執(zhí)行

2.語句的順序執(zhí)行對于一個程序段中的多條語句來說，也有一個執(zhí)行順序的問題。如果對于下述三條語句的程序段：S1：a:＝x＋yS2：b:＝a－5S3：c:＝b＋1(其中S2必須在a被賦值以后才能執(zhí)行；同樣S3也只能在b被賦值以后才能執(zhí)行)3.

程序順序執(zhí)行時的特征（1）

順序性

處理機的操作，嚴格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在上一操作結束之后開始。（2）

封閉性封閉環(huán)境下運行，程序獨占全機資源只有當前運行程序才能改變資源狀態(tài)程序執(zhí)行結果不受外界因素的影響（3）

可再現(xiàn)性

只要程序執(zhí)行時的環(huán)境和初始條件都相同，不論它是從頭到尾的不停頓的執(zhí)行，還是“走走停停”地執(zhí)行，都將獲得相同的結果。程序順序執(zhí)行時的特性，將為程序員檢測和校正程序的錯誤，帶來極大的方便。.

多道程序系統(tǒng)中，程序執(zhí)行環(huán)境的變化

計算機能夠同時處理多個具有獨立功能的程序（如批處理系統(tǒng)，分時系統(tǒng)、實時系統(tǒng)、網(wǎng)絡與分布式系統(tǒng)）。這樣的執(zhí)行環(huán)境具有三個特點：獨立性：邏輯上獨立；隨機性：程序和數(shù)據(jù)輸入與執(zhí)行開始時間都是隨機的資源共享:

硬件資源：CPU、輸入輸出設備，存儲器軟件資源：各種例行程序、各種共享的數(shù)據(jù)2.1.3程序的并發(fā)執(zhí)行1.并發(fā)環(huán)境：

在一定時間內(nèi)物理機器上有兩個或兩個以上的程序同處于開始運行但尚未結束的狀態(tài)，并且次序不是事先確定的。2.程序的并發(fā)執(zhí)行

一組邏輯上相互獨立的程序或程序段在執(zhí)行過程中，其執(zhí)行時間在客觀上相互重疊，即一個程序段的執(zhí)行尚未結束，另一個程序段的執(zhí)行已經(jīng)開始的執(zhí)行方式。I1I2I4I3C1C2C3P1C4P4P3P2圖2-2程序并發(fā)執(zhí)行時的前趨圖在對一批程序進行處理時，可以并發(fā)執(zhí)行。

例如，輸入、計算、打印三個程序?qū)σ慌鳂I(yè)進行處理時，存在以下的前趨關系：

Ii→Ci

，Ii→Ii＋1

，Ci→Pi，

Ci→Ci+1，Pi→Pi+1

對一個作業(yè)的輸入計算和打印三個操作，必須順序執(zhí)行，但并不存在Pi→

Ii＋1。

Ii＋1和Ci及Pi－1是可以并發(fā)執(zhí)行的。例：下述四條語句的程序段畫出前趨圖S1：

a：＝x+2S2：

b：＝y(tǒng)＋4S3：

c：＝a＋bS4：

d：＝c＋6S1S2S4S33.程序并發(fā)執(zhí)行的特征：

多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行由于資源有限，多道程序的并發(fā)執(zhí)行總是伴隨著資源的共享與競爭，制約了各道程序的執(zhí)行速度。在某道程序段中，包含著一部分可以同時執(zhí)行或順序顛倒執(zhí)行的代碼例如：read（a）；

read（b）；既可以同時執(zhí)行，也可以顛倒次序執(zhí)行，同時執(zhí)行不會改變順序程序所具有的邏輯性質(zhì)，可采用并發(fā)執(zhí)行來充分利用資源。間斷性、失去封閉性、不可再現(xiàn)性間斷性程序在并發(fā)執(zhí)行時，由于它們共享資源或為完成某一項任務而合作，致使在并發(fā)程序之間存在相互制約的關系。(I、C、P是三個相互合作的程序，當計算程序完成Ci－1的計算后，如果輸入程序I尚未完成對Ii的處理，則計算程序無法進行Ci處理，致使計算程序暫停運行。)失去封閉性程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。

不可再現(xiàn)性

程序在并發(fā)執(zhí)行時，由于失去了封閉性，也導致失去了可再現(xiàn)性。

例如：有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時都要做N:＝N+1操作；程序B每執(zhí)行一次時，都要做print（N）操作，然后再將N置成“0”，程序A和B以不同的速度運行。（假定某時刻變量N的值為n）

程序并發(fā)執(zhí)行不可再現(xiàn)性舉例分析共享初值為n的變量N的兩程序段A、BA:N:=N+1B:Print(N);N:=0（1）N:＝N＋1在print（N）和N:＝0之前，此時得到的N值分別為n＋1，n＋1，0（2）N:＝N＋1在print（N）和N:＝0之后，此時得到的N值分別為

n，0，1（3）N:＝N＋1在

print（N）和N:＝0之間，此時得到的N值分別為

n，n＋1，04.程序并發(fā)執(zhí)行的條件程序并發(fā)執(zhí)行過程可以描述為：

S0CobeginP1；P2；……PnCoendSn1966年，Bernstein提出了相鄰語句S1S2可以并發(fā)執(zhí)行的條件。

如果并發(fā)執(zhí)行的各程序段中語句或指令滿足Bernstein的三個條件，則認為并發(fā)執(zhí)行不會對執(zhí)行結果的封閉性和可再現(xiàn)性產(chǎn)生影響。

將程序中任一語句Si劃分為兩個變量的集合R（Si）＝{a1,a2,……am}是語句Si在執(zhí)行其間必須對其進行讀的變量，稱為讀集；W（Si）＝{b1，b2，……bn}是語句Si在執(zhí)行其間必須對其進行修改的變量，稱為寫集；如果對于語句S1和S2，有

①

R(S1)∩W(S2)＝{Φ}②W(S1)∩R(S2)＝{Φ}③W(S1)∩W(S2)＝{Φ}同時成立即：R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)＝{Φ},則語句S1和S2是可以并發(fā)執(zhí)行的。？操作系統(tǒng)中許多任務不滿足Bernstein條件，它們不能并發(fā)執(zhí)行嗎？怎么辦？例：若有兩條語句Ci＝a－b和Wi＝c＋1，判斷它們是否可以并發(fā)執(zhí)行？解：它們的“讀集”和“寫集”分別為

R（C：＝a－b）＝{a，b}

R（W：＝c＋1）＝{c}W（C：＝a－b）＝{c}W（W：＝c＋1）＝{w}R（C：＝a－b）∩W（Wi：＝c＋1）={Φ}R（W：＝c＋1）∩W（C：＝a－b）={c}所以：兩條語句不能并發(fā)執(zhí)行。進程的引入并發(fā)、共享及多道程序環(huán)境基于程序的概念已不能完整、有效地描述并發(fā)程序在內(nèi)存中的運行狀態(tài)必須建立并發(fā)程序的新的描述和控制機制基于程序段、數(shù)據(jù)段和進程控制塊而引入進程的概念以對應程序的運行過程進程控制塊存放了進程標識符、進程運行的當前狀態(tài)、程序和數(shù)據(jù)的地址以及關于該程序運行時的CPU環(huán)境信息2.1.4進程的特征與狀態(tài)1)結構特征：程序段、相關的數(shù)據(jù)段、PCB構成了進程實體。2)動態(tài)性：進程是進程實體的一次執(zhí)行過程。3)并發(fā)性：多個進程實體，同存于內(nèi)存中，能在一段時間內(nèi)同時運行。4)獨立性：獨立運行和資源調(diào)度的基本單位。5)異步性：各自獨立的、以不可預知的速度向前推進。1.進程的特征和定義：進程有許多各式各樣的定義，其中較典型的進程定義是：（1）進程是程序的一次執(zhí)行。（2）進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。（3）進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位?！?/p>

！比較進程和程序的區(qū)別：答：（1）進程是一個動態(tài)的概念，進程的實質(zhì)是程序的一次執(zhí)行過程，動態(tài)性是進程的基本特征，同時進程是有一定的生命期的；而程序只是一組有序指令的集合，本身并無運動的含義，是靜態(tài)的。（2）并發(fā)性。并發(fā)性是進程的重要特征，引入進程的目的正是為了使其程序和其它程序并發(fā)執(zhí)行；而程序(沒有建立進程)是不能并發(fā)執(zhí)行的。（3）獨立性。是指進程是一個能獨立運行、獨立分配資源和獨立調(diào)度的基本單位；凡未建立進程的程序，都不能作為一個獨立的單位參加運行。（4）不同的進程可以包含同一個程序，同一個程序在執(zhí)行中也可以產(chǎn)生多個進程。實例：一位有一手好廚藝的計算機科學家正在為他的兒子烘制生日蛋糕。計算機科學家------處理機(CPU)；做蛋糕的食譜------程序（即用適當形式描述的算法）；做蛋糕的原料（如面粉，雞蛋，糖）------輸入數(shù)據(jù)；進程：廚師閱讀食譜，取來各種原料以及烘制蛋糕等一系列動作的總和?，F(xiàn)假設科學家的兒子跑進來，說被蜜蜂蟄了；科學家就記錄下他照著食譜做到哪兒了------保存進程當前狀態(tài)；然后拿出一本急救手冊（醫(yī)療救治進程的程序），按照其中的指示處理蟄傷------CPU進行進程切換（做蛋糕~實施醫(yī)療救治）；蟄傷處理完畢后，科學家又回來做蛋糕，從他離開時的那一步繼續(xù)做下去。關鍵思想：一個進程是某種類型的一個活動，它有程序、輸入、輸出以及狀態(tài)。單個處理機可以被若干個進程共享，它使用某種調(diào)度算法決定何時停止一個進程的工作，并轉(zhuǎn)而為另一個進程提供服務。

答：在單道程序設計環(huán)境下，CPU被一道程序獨占，CPU嚴格按該程序的指令順序來執(zhí)行，單道程序具有順序性，封閉性和可重現(xiàn)性。單道程序有許多局限性，于是出現(xiàn)了多道程序，在多道程序環(huán)境中，有若干個程序同時運行，其具有許多新的特征，如并發(fā)性，動態(tài)性以及相互制約性等，這時程序的概念已經(jīng)不能描述上述這些特征，并發(fā)程序的特征必須用新的概念來描述，所以引進了進程的概念。在操作系統(tǒng)中為什么要引進進程這個概念?它會產(chǎn)生什么影響? 2.進程的三種基本狀態(tài)1．就緒狀態(tài)（Ready）

當進程已經(jīng)分配到除CPU以外的所有必要的資源后，只要能再獲得處理機，就可以立即執(zhí)行。這時進程的狀態(tài)稱為就緒狀態(tài)。2．執(zhí)行狀態(tài)（Running）（運行狀態(tài)）

指進程已獲得處理機，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只能有一個進程處于執(zhí)行狀態(tài)。（在多處理機中，可能有多個進程處于執(zhí)行狀態(tài)）3．阻塞狀態(tài)（Block）（等待狀態(tài)）進程因為發(fā)生某個事件而暫停執(zhí)行時的狀態(tài)（如：請求I/O、申請緩沖空間等），也就是說，進程受到阻塞，所以稱這種暫停狀態(tài)為阻塞狀態(tài)，有時也稱“等待”狀態(tài)或“睡眠”狀態(tài)。

進程狀態(tài)間的轉(zhuǎn)換①就緒→執(zhí)行：調(diào)度②執(zhí)行→阻塞：等待某個事件發(fā)生而睡眠③阻塞→就緒：因等待的事件發(fā)生而喚醒④執(zhí)行→就緒：時間片用完接收進程就緒隊列1就緒隊列2...就緒隊列n超時事件1發(fā)生事件2發(fā)生等待事件1等事件2...處理機終止進程事件m發(fā)生等事件m引入掛起狀態(tài)的原因

終端用戶的請求（用戶調(diào)試程序）。(2)父進程請求。(3)負荷調(diào)節(jié)的需要（實時系統(tǒng)中）。(4)操作系統(tǒng)的需要。3.掛起狀態(tài)2)進程狀態(tài)的轉(zhuǎn)換(1)活動就緒→靜止就緒。(2)活動阻塞→靜止阻塞。(3)靜止就緒→活動就緒。(4)靜止阻塞→活動阻塞。

4.創(chuàng)建狀態(tài)和終止狀態(tài)

1）創(chuàng)建狀態(tài)：此時的進程已擁有了自己的PCB，但進程自身還未進入主存，即創(chuàng)建工作尚未完成，進程還不能被調(diào)度運行。

創(chuàng)建進程第一步為一個新進程創(chuàng)建PCB，并填寫必要的管理信息；第二步把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中。

2）終止狀態(tài)：當一個進程已經(jīng)正常結束或異常結束，OS已經(jīng)將它從就緒隊列中移出，但還沒有將它撤消時的狀態(tài)。終止進程第一步等待操作系統(tǒng)進行善后處理；第二步將其PCB清零，并將PCB空間返還系統(tǒng)。2.1.5進程控制塊？

1.進程控制塊的作用

進程控制塊是進程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結構，PCB中記錄了操作系統(tǒng)所需要的，用于描述進程情況及控制進程運行所需的全部信息。

作用：使一個在多道程序環(huán)境下不能獨立運行的程序（含數(shù)據(jù)），成為一個能獨立運行的基本單位。

2.進程控制塊中的信息(1)

進程標識符內(nèi)部標識符：惟一的數(shù)字標識符，設置內(nèi)部標識符主要是為了方便系統(tǒng)使用。外部標識符：它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶（進程）在訪問該進程時使用。父進程標識子進程標識(2)處理機狀態(tài)

當一個正在執(zhí)行的進程被中斷時，這一時刻處理機的狀態(tài)信息必須保存在PCB中，以便該進程恢復執(zhí)行時能從斷點處繼續(xù)。處理機狀態(tài)信息存放在下列寄存器中，當進程被中斷時這組寄存器中的信息被系統(tǒng)保存到PCB中。①通用寄存器

②指令計數(shù)器

③程序狀態(tài)字PSW

④用戶棧指針(3)進程調(diào)度信息

在PCB中還存放一些與進程調(diào)度和進程對換有關的信息，包括：①進程狀態(tài)；②進程優(yōu)先級；③進程調(diào)度所需的其它信息，它們與所采用的進程調(diào)度算法有關；④事件，是指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。(4)進程控制信息

進程控制信息包括：①程序和數(shù)據(jù)的地址；②進程同步和通信機制，指實現(xiàn)進程同步和進程通信時必需的機制；③資源清單；④鏈接指針。2.進程控制塊的組織方式1）鏈接方式：把具有同一狀態(tài)的PCB，用其中的鏈接字鏈接成一個隊列。2）索引方式：系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表。2.2進程控制

進程控制是進程管理中最基本的功能。它用于創(chuàng)建一個新進程，終止一個已完成的進程，或終止一個因出現(xiàn)某事件而使其無法運行下去的進程，還可負責進程運行中的狀態(tài)轉(zhuǎn)換。

進程控制一般是由OS的內(nèi)核中的原語來實現(xiàn)的。

原語是由若干條指令組成的，用于完成一定功能的一個過程。它是一個不可分割的單位，在執(zhí)行過程中不允許中斷。原子操作在系統(tǒng)態(tài)（管態(tài)）下執(zhí)行，常駐內(nèi)存。

2.2.1進程的創(chuàng)建1.進程圖

進程圖是用來描述進程家族關系的有向樹。ABCDMEIJHGFLK子進程可以繼承父進程的所有資源，當子進程被撤消時，應將從父進程那里獲得的資源歸還給父進程。撤消父進程時也必須同時撤消其所有的子進程。2.引起創(chuàng)建進程的事件(1)用戶登錄：在分時系統(tǒng)中，用戶在終端鍵入登錄命令后，若是合法用戶，系統(tǒng)建立一個進程，并插入就緒隊列。(2)作業(yè)調(diào)度：批處理系統(tǒng)中，作業(yè)調(diào)度程序調(diào)度到某個作業(yè)以后，就把這個作業(yè)裝入內(nèi)存，并分配必要的資源，立即為其創(chuàng)建進程，插入就緒隊列。(3)提供服務：運行中的用戶向系統(tǒng)提出請求后，系統(tǒng)專門建立一個進程為用戶服務。（打印請求）由操作系統(tǒng)核心（系統(tǒng)程序模塊）創(chuàng)建。(4)應用請求：在上述三種情況下，都是由系統(tǒng)內(nèi)核為之創(chuàng)建一新進程，基于應用進程的需要，可由它自己創(chuàng)建一個新進程，使新進程以并發(fā)運行方式完成特定任務。3.進程的創(chuàng)建（調(diào)用創(chuàng)建原語Create()）(1)申請空白的PCB。

為新進程分配唯一的數(shù)字標識符，并從PCB集合中索取一個空白的PCB。(2)為新進程分配資源。

為新進程的程序和數(shù)據(jù)以及用戶棧分配必要的內(nèi)存空間。(3)初始化進程控制塊。

①初始化標識符信息。將系統(tǒng)中分配的標識符、父進程標識符填入新PCB中。②初始化處理機狀態(tài)信息，使程序計數(shù)器指向程序的入口地址，棧指針指向棧頂。③初始化處理機控制信息，將進程的狀態(tài)設置為就緒狀態(tài)或靜止就緒狀態(tài)。(4)將新進程插入就緒隊列。創(chuàng)建原語流程圖入口查PCB鏈表有空PCB？PCB（I）入進程家族或進程鏈PCB(I)入就緒隊列將有關參數(shù)填入PCB（I）相應項取空表PCB(I)返回創(chuàng)建失敗無有1.引起進程終止的事件(1)正常結束：計算機系統(tǒng)中，都有一個表示進程已經(jīng)運行完成的指示。（批處理，Holt。分時系統(tǒng)中，LogsOff）(2)異常結束

越界錯誤、保護錯、特權指令錯、非法指令、運行超時、等待超時、算術運算錯、I/O故障(3)外界干預

操作員或操作系統(tǒng)干預父進程請求父進程終止2.2.2進程的終止2.進程的終止（調(diào)用終止原語Terminal()）(1)根據(jù)被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態(tài)。(2)若被終止進程處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，并設置調(diào)度標志為真（用于指示該進程被終止時應重新調(diào)度），然后再選擇一個進程，分配處理機給它。(3)如果該進程還有子孫進程，還應將它的所有子孫進程進行終止，以防它們成為不可控的。(4)將該進程所擁有的全部資源，或者歸還給它的父進程，或者歸還給系統(tǒng)。(5)將被終止進程（PCB）從所在隊列（或鏈表）中移出，等待其它程序來搜索信息。終止原語流程圖入口返回查進程鏈表或進程家族有此PCB嗎？該PCB有子進程嗎？釋放該進程所占有的資源釋放該PCB結構本身出錯處理有無有無引起創(chuàng)建/終止進程的事件用戶登錄分時系統(tǒng)中，驗證為合法的終端用戶登錄作業(yè)調(diào)度批處理系統(tǒng)中作業(yè)調(diào)度程序調(diào)度到某作業(yè)提供服務運行中的用戶程序提出某種請求應用請求基于應用進程的需要由其自身創(chuàng)建新進程正常結束批處理系統(tǒng)中Halt，分時系統(tǒng)中LogsOff異常結束越界錯誤、保護錯特權指令錯非法指令錯運行超時、等待超時算術運算錯、I/O故障外界干預操作員或操作系統(tǒng)干預父進程請求/終止2.2.3進程的阻塞與喚醒1.引起進程阻塞和喚醒的事件1)請求系統(tǒng)服務

正在執(zhí)行的程序請求操作系統(tǒng)服務，但是由于某種原因操作系統(tǒng)沒有立即滿足該進程的要求，該進程只能轉(zhuǎn)變?yōu)樽枞麪顟B(tài)來等待。2)啟動某種操作

當進程啟動某種操作后，如果該進程必須在該操作完成之后才能繼續(xù)執(zhí)行，所有必須先使進程阻塞。3)新數(shù)據(jù)尚未到達4)無新工作可做

系統(tǒng)往往設置一些具有某特定功能的系統(tǒng)進程，每當這種進程完成任務以后便把自己阻塞起來等待新任務的到來。（發(fā)送進程）引起進程阻塞/喚醒的事件請求系統(tǒng)服務但不能立即滿足啟動某種操作且必須在該操作完成之后才能繼續(xù)執(zhí)行新數(shù)據(jù)尚未到達相互合作進程的一方需首先獲得另一進程數(shù)據(jù)才能繼續(xù)無新工作可做特定功能系統(tǒng)進程當完成任務且暫無任務系統(tǒng)服務滿足操作完成數(shù)據(jù)到達新任務出現(xiàn)2.進程阻塞過程

當有阻塞事件發(fā)生時，進程便調(diào)用阻塞原語block()把自己阻塞。進入block后，應先立即停止執(zhí)行，把進程控制塊中的執(zhí)行狀態(tài)改為阻塞狀態(tài)，并將PCB插入阻塞隊列。入口保存當前進程的CPU現(xiàn)場置該進程的狀態(tài)被阻塞進程入等待隊列轉(zhuǎn)進程調(diào)度阻塞原語流程圖注意：進程的阻塞是進程自身的一種主動行為。入口從等待隊列中摘下被喚醒進程將被喚醒進程置為就緒狀態(tài)將被喚醒進程送入就緒隊列轉(zhuǎn)進程調(diào)度返回3.進程喚醒過程

當阻塞進程所期待的事件出現(xiàn)時。則調(diào)用喚醒原語wakeup()，將等待事件的進程喚醒。喚醒原語執(zhí)行的過程是：首先把被阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的阻塞狀態(tài)改為就緒狀態(tài)，然后把該進程插入到就緒隊列中。喚醒原語流程圖Block()和wakeup()是一對作用剛好相反的原語。原語配對2.2.4進程的掛起與激活1.進程的掛起suspend()原語2.進程的激活active()原語引起掛起的事件，如用戶進程請求將自己掛起，或父進程請求將自己的某個子進程掛起。檢查被掛起進程的狀態(tài)活動就緒—靜止就緒活動阻塞—靜止阻塞執(zhí)行狀態(tài)—靜止就緒引起激活進程的事件，如父進程或用戶進程請求激活指定進程，若該進程駐留在外存而內(nèi)存已有足夠的空間時，則可將在外存上處于靜止就緒狀態(tài)的該進程換入內(nèi)存。1、某系統(tǒng)的進程狀態(tài)轉(zhuǎn)換圖如下圖所示，請說明：

（1）引起各種狀態(tài)轉(zhuǎn)換的典型事件有哪些？（2）當我們觀察系統(tǒng)中某些進程時，能夠看到某一進程產(chǎn)生的一次狀態(tài)轉(zhuǎn)換能引起另一進程做一次狀態(tài)轉(zhuǎn)換。在什么情況下，當一個進程發(fā)生轉(zhuǎn)換3時能立即引起另一個進程發(fā)生轉(zhuǎn)換1？（3）試說明是否會發(fā)生下述因果轉(zhuǎn)換：

2→13→24→14312執(zhí)行阻塞就緒1習題UNIX進程描述與控制UNIX進程控制用數(shù)據(jù)結構進程表項(processtable)：常用核心數(shù)據(jù)，常駐內(nèi)存。U區(qū)：User結構，存放用戶進程表項的一些擴充數(shù)據(jù)，非常駐內(nèi)存。系統(tǒng)區(qū)表：（系統(tǒng)把一個進程的虛地址空間劃分為若干個連續(xù)的區(qū)域：正文區(qū)、數(shù)據(jù)區(qū)、棧區(qū)等。）系統(tǒng)區(qū)表用來存放各個區(qū)在物理存儲器中的地址信息等。進程區(qū)表：存放各區(qū)的起始虛地址及指向系統(tǒng)區(qū)表中對應區(qū)表項的指針。同系統(tǒng)區(qū)表配合，可用于對區(qū)地址進行映射。（UNIX中，PCB被分為四部分：進程表項、U區(qū)、系統(tǒng)區(qū)表、進程區(qū)表）UNIX進程控制用數(shù)據(jù)結構進程表本進程區(qū)表內(nèi)存CODEDATASTACK正文區(qū)數(shù)據(jù)區(qū)棧區(qū)系統(tǒng)區(qū)表CODEDATASTACK進程U區(qū)UNIX進程狀態(tài)轉(zhuǎn)換圖fork用戶態(tài)執(zhí)行掛起就緒掛起阻塞內(nèi)存中就緒內(nèi)存中阻塞新狀態(tài)核心態(tài)執(zhí)行僵死狀態(tài)被搶占狀態(tài)exit內(nèi)存足內(nèi)存不足換出換入換出喚醒喚醒調(diào)度阻塞搶占系統(tǒng)調(diào)用中斷中斷返回中斷返回調(diào)度進程映像UNIX中，進程是進程映像的執(zhí)行過程，進程映像則是正在運行進程的實體用戶級上下文

主要成分為用戶程序用戶程序（正文區(qū)、數(shù)據(jù)區(qū)）、用戶棧區(qū)、共享存儲區(qū)寄存器上下文

（主要由CPU中的一些寄存器的內(nèi)容所組成）PC、PSR、棧指針、通用寄存器系統(tǒng)級上下文

OS為管理該進程所用的信息靜態(tài)部分：進程表項、U區(qū)、本進程區(qū)表、系統(tǒng)區(qū)表項、頁表動態(tài)部分：核心棧、若干層寄存器上下文進程控制fork系統(tǒng)調(diào)用創(chuàng)建新進程0號（對換）進程=>1號（始祖）進程exit系統(tǒng)調(diào)用實現(xiàn)進程自我終止exec系統(tǒng)調(diào)用改變進程原有代碼（更新用戶級上下文）wait系統(tǒng)調(diào)用阻塞主調(diào)進程并等待子進程終止進程調(diào)度與切換引起進程調(diào)度的原因時鐘中斷、核心態(tài)執(zhí)行返回、放棄處理機調(diào)用算法動態(tài)優(yōu)先數(shù)輪轉(zhuǎn)調(diào)度算法進程優(yōu)先級分類內(nèi)核優(yōu)先級（可/不可中斷）、用戶優(yōu)先級優(yōu)先數(shù)計算基本用戶優(yōu)先數(shù)、進程本次CPU使用時間進程切換三、Unix中的進程1、Unix系統(tǒng)進程創(chuàng)建機制引導程序核心程序創(chuàng)建0號程序0號進程創(chuàng)建1號進程init1號進程創(chuàng)建終端11號進程創(chuàng)建終端n1號進程創(chuàng)建終端2子進程……子進程子進程……子進程bootinitgetttygetttyshelllogin/etc/inittab/etc/rc/etc/rc.local/etc/passwd/etc/profile$HOME/.profile$HOME/.login讀取用戶注銷讀取讀取執(zhí)行讀取forkexecexecUNIX啟動及進程樹的形成系統(tǒng)管理員首先通過自舉把操作系統(tǒng)裝入內(nèi)存，并開始執(zhí)行它。自舉過程是由系統(tǒng)管理員按動某個特殊的按鈕來指示機器從它的微代碼裝入啟動程序的。UNIX系統(tǒng)的自舉過程是讀一個磁盤的引導塊（文件系統(tǒng)的第0塊），并將其裝入內(nèi)存，在核心裝入內(nèi)存后，系統(tǒng)開始執(zhí)行啟動過程start。啟動過程start首先初始化系統(tǒng)內(nèi)部數(shù)據(jù)結構。例如，構造空閑緩沖區(qū)、初始化區(qū)結構、頁表項等。然后，系統(tǒng)將根文件系統(tǒng)安裝到根“／”下，并建立系統(tǒng)調(diào)度進程的proc結構proc［0］，并使根“／”成為進程0的當前目錄。在創(chuàng)建和設置好進程0的環(huán)境之后，系統(tǒng)就作為進程0執(zhí)行并調(diào)用fork過程創(chuàng)建新進程1（這里的fork不是系統(tǒng)調(diào)用），也就是設置proc［1］的有關表項。進程1在系統(tǒng)中被稱為init進程。它是一個既可在核心態(tài)，又可在用戶態(tài)運行的進程，它的正文代碼由調(diào)用系統(tǒng)調(diào)用exec執(zhí)行程序“／etc／init”的代碼組成，進程1負責初始化所有新的用戶進程。進程1調(diào)用exec執(zhí)行“／etc／init”程序后，為每個終端生成一個子進程，然后等待用戶在終端上注冊。用戶在終端上輸入命令，每個命令都對應于一個可執(zhí)行文件。shell命令解釋程序解釋此命令，找到相應的可執(zhí)行命令文件，用系統(tǒng)調(diào)用fork()創(chuàng)建子進程，并由此子進程調(diào)用系統(tǒng)調(diào)用exec()執(zhí)行此命令文件；父進程也就是終端進程則處于等待狀態(tài)，子進程執(zhí)行文件結束后調(diào)用系統(tǒng)調(diào)用exit()自我終止。喚醒父進程做善后處理并轉(zhuǎn)而顯示提示符，準備接受下一條命令執(zhí)行。進程啟動及進程樹的形成過程如圖所示。圖進程樹的形成三、Unix中的進程0#進程由內(nèi)核程序創(chuàng)建，初始化時創(chuàng)建1#進程平時負責調(diào)度分配處理器管理中負責進程調(diào)度與交換

1#進程是所有用戶進程的祖先進程。是系統(tǒng)中的第一個真正的進程，它完成一些系統(tǒng)的初始化配置（如打開系統(tǒng)的控制盤以及安裝根文件系統(tǒng)），然后執(zhí)行系統(tǒng)初始化腳本,/etc/rc.d/rc.sysinit。使用/etc/inittab作為一個腳本來創(chuàng)建系統(tǒng)的新進程。三、Unix中的進程2、用戶進程創(chuàng)建結構用戶注冊csh用戶注銷cshshviccsorttarwclspasswd注意：用戶創(chuàng)建的進程樹以1#進程為根三、Unix中的進程3、Unix中的進程描述Proc結構系統(tǒng)棧用戶棧數(shù)據(jù)棧正文段User結構UNIX進程上下文劃分為：Proc結構和user結構:PCB用戶棧、核心棧正文段、數(shù)據(jù)段三、Unix中的進程4、Unix進程描述中的數(shù)據(jù)結構1).proc結構進程狀態(tài)進程用戶標識進程標識進程在存儲區(qū)中的位置和大小進程調(diào)度參數(shù)（優(yōu)先級）軟中斷信號項執(zhí)行時間及資源使用情況User結構起始址進程頁表指針被掛起事件描述2).user結構指向proc的指針當前系統(tǒng)調(diào)用（參數(shù)、返回值及錯誤碼）與用戶標識有關項（當前目錄、文件系統(tǒng)環(huán)境）輸入輸出項打開文件的描述符中斷及軟中斷參數(shù)錯誤信息進程各段長度（正文、數(shù)據(jù)和棧）文件權限屏蔽項交換數(shù)據(jù)項（包括進程在做上下文切換、現(xiàn)場保護時要保存的數(shù)據(jù)項）四、Unix進程調(diào)度與管理1、Unix進程狀態(tài)及其轉(zhuǎn)換進程調(diào)度的兩個關鍵問題：