前趨圖和程序執行

1、前趨圖

所謂前趨圖（PG），是指一個有向無環圖，可記為DAG，用于描述進程之間執行的先后順序，具體見書上P35。

沒有前趨的結點稱為初始結點，沒有后繼的結點稱為終止結點，每個結點都有一個重量，代表當前結點的程序量或程序的執行時間。

注：有循環則非前趨圖

2、程序順序執行

程序由若干程序段組成，在執行時，需要按照某種先后次序順序執行，僅當前一段程序完成時，才運行后一段程序。

特征：1.順序性 處理機嚴格按照順序執行。2.封閉性 程序在封閉環境下運行，除了本程序以外不受任何外界因素影響。3.可再現性 只要環境與初始條件相同，無論怎么執行，得到的結果均相同。

3、程序并發執行

為解決系統資源利用率低的問題，引入了并發執行，不存在前趨關系的程序之間才可以并發執行。

特征：1.間斷性 并發執行時，由于共享系統資源，以及為完成同一項任務而相互合作，導致這些程序之間形成了相互制約的關系。因此并發程序具有”執行-暫停-執行“這種間斷性的活動規律。2.失去封閉性 資源共享，不再封閉 3.不可再現性 由于失去了封閉性，導致了失去了可再現性（調用同一資源并改變其信息的情形，先后順序不同結果不同）

進程的描述

1、進程的定義與特征

—1、定義

進程控制塊（PCB）：為保證并發執行的每個程序（含數據）都能獨立的運行，配備了進程控制塊，描述了描述信息、調度信息、資源管理與處理機狀態。

進程實體：由程序段、相關的數據段與PCB三部分組成。

進程是進程實體的運行過程，是系統資源分配和調度的一個獨立單位。

—2、特征

動態性：進程由創建而產生、調度而執行、撤銷而消亡，而程序則是靜態的，不具備活動的含義。

并發性：多個進程存在于內存中并在同一時間段內同時執行。

獨立性：進程是一個能夠獨立運行、獲得資源和接收調度的基本單位。

異步性：進程按異步方式運行。

2、進程的基本狀態及轉換

—1、程序的三種基本狀態

就緒態：已準備好運行。

執行態：已獲得CPU，正在執行。

阻塞態：由于發生某些事件無法繼續執行的狀態，執行收到阻塞。此時將處理機分配給另一個進程，受阻進程處于暫停狀態。

—2、三種狀態的轉換

圖片見課本

—3、創建狀態與終止狀態

創建狀態：創建需要申請空白PCB，寫入控制和管理進程的信息-分配運行時資源-轉入就緒狀態插入就緒隊列。若此時進程資源無法被滿足，則不能被調度運行，此狀態稱為創建狀態。

終止狀態：終止需要將PCB清空，并將空間返還給系統。若進程自然結束或被其他原因終結，將進入終止狀態，此后不能再執行，但在系統中保留記錄。

圖片見課本

3、掛起操作和進程狀態的轉換

操作于某個進程時，進程將掛起，此時進程處于靜止狀態。

4、進程管理中的數據結構-PCB

—1、作用

作為獨立運行基本單位的標志

能實現間斷性運行方式

提供進程管理者所需要的信息

提供進程調度所需要的信息

實現與其他進程的同步與通信

—2、PCB中的信息

進程標識符：唯一的標識一個進程，通常有內部標識符（系統提供，唯一數字標識符）和外部標識符（創建者提供，由字符組成）兩種。

處理機狀態：也稱為處理機上下文，由各種寄存器內容組成，包括了通用寄存器、指令計數器（下一條指令地址）、程序狀態字PSW（狀態信息、條件碼、執行方式、中斷屏蔽標志等）、用戶棧指針（存放過程與系統調用參數及調用地址）。進程被切換時，狀態信息應被保存在PCB中，以便重新執行時能從斷點繼續執行。

程序調度信息：包含進程狀態、優先級、調度所需要的其他信息以及事件（阻塞原因）。

進程控制信息：包含程序和數據的地址（以便再次執行時能夠找到程序和數據）、進程同步和通信機制、資源清單（執行所需的全部資源）、鏈接指針（下一個PCB的首地址）。

—3、組織方式

線性方式：系統所有的PCB都在一張線性表中。

鏈接方式：按照優先級PCB鏈接為一個隊列。

索引方式：根據進程狀態，建立索引表。

進程控制

1、操作系統內核

與硬件聯系緊密的模塊、驅動程序及調用頻率高的模塊，將他們常駐內存，稱為OS內核。

通常將處理機分為兩種狀態：

系統態：又稱管態、內核態，權限高。

用戶態：又稱目態，權限低，只能執行規定的指令，訪問指定的寄存器和存儲區。

—1、支撐功能

中斷處理：是內核最基本的功能，操作系統賴以活動的基礎。

時鐘管理：是內核的一項基本功能。

原語操作：所謂原語，就是由若干條指令構成，用于完成一定功能的一個過程。它與一般過程的區別在于他們是“原子操作”，也就是說，一個操作要么全做，要么不做，是一個不可分割的基本單位，不能被中斷。原子操作在系統態下執行，常駐內存。

—2、資源管理功能

進程管理：通常放在內核當中，提高OS性能。

存儲器管理：同樣放在內核中。

設備管理：大部分放在內核當中。

2、進程的創建

—1、進程的層次結構

在OS中，允許一個進程（父進程）創建另一個進程（子進程），由此形成了一個進程的層次結構。父子進程之間存在資源的繼承與歸還。

注：在$windows$中，進程不具備層次結構概念，所有進程地位相同，而是通過可傳遞的句柄，來實現控制與被控制的關系。

—2、進程圖

用于描述進程關系的一棵有向樹。

—3、引起進程創建的事件

用戶登錄、作業調度、提供服務、應用請求

前三者都是通過系統內核為用戶創建一個新進程，而應用請求是由用戶進程自己創建新進程。

—4、進程的創建

OS調用$Create$?創建原語按照如下步驟創建新進程：

申請空白PCB、為新進程分配運行所需的，包括邏輯與物理的資源、初始化PCB（標識信息、處理機狀態信息、處理機控制信息），若就緒隊列能夠接納新進程，便插入就緒隊列。

3、進程的終止

—1、引起終止的事件

正常結束：執行完成。

異常結束：發生了諸如越界錯誤、保護錯誤、非法指令、特權指令錯誤、TLE、等待超時、運算錯誤、I/O錯誤等異常后終止。

外界干預：進程因外界請求終止運行。

—2、進程的終止過程

OS調用終止原語，執行如下操作：

根據被終止進程的標識符，檢索出該進程的PCB，讀出狀態。

若正處于執行，應立即終止執行，并置調度標志為真，表示應重新調度。

若還有子進程，將子進程也終止。

全部資源歸還父進程或系統。

將PCB從隊列中移除，等待其他程序搜集信息。

4、進程的阻塞與喚醒

—1、引起阻塞和喚醒的事件

向系統請求共享資源失敗

等待某種操作完成

新數據尚未到達

等待新任務的到達

—2、進程阻塞過程

進程通過調用$Block$?阻塞原語將自己阻塞，執行如下操作：

進程立即停止執行，PCB中“執行”改為”阻塞“，并插入阻塞隊列，最后轉調度程序重新調度，將處理機分配給另一就緒進程。

—3、進程喚醒過程

被阻塞時期待的事情發生后，有關進程調用$Wakeup$喚醒原語，將PCB從阻塞隊列中移入就緒隊列中。

5、進程的掛起與激活

掛起原語$Suspend$，激活原語$Active$。

進程同步

1、進程同步的基本概念

—1、兩種形式的制約關系

間接相互制約關系：進程并發執行時，由于共享系統資源，導致這些并發執行的進程形成相互制約的關系。對于臨界資源，必須保證只能互斥訪問，因此這些進程形成了所謂間接制約的關系。對于這類資源，必須由系統統一分配，用戶要使用之前，必須現申請，而不允許用戶進程直接使用。

直接相互制約關系：多個進程為了完成同一個任務而相互合作，形成了直接制約關系。

—2、臨界資源

一次只允許一個進程訪問的資源。消費者生產者問題是一個著名的進程同步問題。大致描述了：為了使生產者與消費者并發執行，在兩者之間加入了有$n$個緩沖區的緩沖池，生產者放入，消費者拿出，兩進程以異步方式運行，但必須保持同步，不能從空緩沖區取，也不能向滿緩沖區放。

—3、臨界區

每個進程中訪問臨界資源的那段代碼稱為臨界區。保證各進程互斥進入自己的臨界區，即可實現對臨界資源的互斥訪問。

—4、同步機制的規則

空閑讓進、忙則等待、有限等待（保證在有限的時間內進入自己的臨界區，避免”死等“狀態）、讓權等待（若不能進入臨界區，立即釋放，避免”忙等“）

2、硬件同步機制

計算機提供硬件指令，解決互斥問題。初始鎖為開，進入的進程要先對鎖進行測試，若未開則等待，若已開則立即鎖上。測試與關鎖必須連續，防止多個進程同時檢測到打開。

—1、關中斷

進入鎖測試之前關閉中斷，直到鎖測試完成并上鎖之后才打開，如此，進程在進入臨界區執行期間，計算機系統不會響應中斷，不會引發調度，也不會發生進程或線程的切換，保證了測試與關鎖的連續性和完整性。

但是關中斷有許多缺點：濫用關中斷可能導致嚴重后果、關中斷時間長影響系統效率、不適合多CPU系統。

—2、利用$Test?and?Set$指令實現互斥

測試并建立的指令，不可分割，即為一條原語。

—3、利用$Swap$指令實現互斥

對換指令，為臨界資源設置全局布爾變量，但易忙等，不符合讓權等待原則。

3、信號量機制

荷蘭科學家迪杰斯特拉提出的信號量機制是一種卓有成效的進程同步機制。

—1、整型信號量

最初由迪杰斯特拉將整型信號量定義為一個用于標識資源數目的整型量S，除了初始化，僅能通過兩個標準的原子操作$wait(S)$和$signal(S)$來訪問，這兩個操作被稱為P、V操作，描述如下：

wait(S){while(S<=0);//查看、等待臨界資源由空閑S--; } signal(S){//釋放臨界資源S++; }

—2、記錄型信號量

整型信號量中的$wait$操作，只要信號量$S<=0$?就會不斷測試，容易忙等。因此除了表示資源數目的$value$以外，還需要一個進程鏈表指針$list$，用于鏈接上述所有等待進程。

代碼描述為：

typedef struct{int value;struct process_control_block *list; }sem; wait(sem *S){S->value--;if(S-value<0)block(S->list);//若滿，則放入等待鏈表 } signal(sem *S){S->value++;if(S->value<=0)wakeup(S->list);//若仍有等待，則喚醒第一個等待進程 }

經典進程的同步問題

1、生產者-消費者問題

此問題若不考慮互斥與同步問題，易造成$Counter$的不定性。本小節將利用信號量機制來解決生產者-消費者問題。

—1、記錄型信號量

假定在緩沖池中有n個緩沖區，這時可利用互斥信號量$mutex$實現諸多進程對緩沖池的互斥作用，利用信號量$empty$與$full$分別表示空緩沖區和滿緩沖區的數量。代碼描述如下：

int in = 0, out = 0; item buffer[n]; sem mutex = 1, empty = n, full = 0; void producer(){do{producer an item nextp;...wait(empty);//查詢是否有空緩沖區，若有則占用wait(mutex);//查詢互斥信號量，若無互斥占用則占用buffer[in]=nextp;in=(in+1)%n;signal(nutex);//釋放時先更改mutexsignal(full);//隨后釋放緩沖區}while(TRUE); } void consumer(){do{wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n;signal(mutex);signal(empty);consumer the item in nextc;...}while(TRUE); } void main(){cobeginproducer();consumer();coend; }

2、哲學家進餐問題

五個哲學家在圓桌上坐，每兩人之間有一根筷子，共五根，饑餓時試圖取得其左右的筷子，拿到一雙筷子即可進餐。

筷子都為臨界資源，一段時間僅可供一位哲學家使用。代碼描述如下：

sem cho[5] = { 1, 1, 1, 1, 1}; do{wait(cho[i]),wait(cho[(i+1)%5]);//eatsignal(cho[i]),signal(cho[(i+1)%5]);//think }while(TRUE);

那么若所有哲學家同時拿起同一側的筷子，則死鎖。

于是有如下解決方案：1. 至多四名哲學家拿起同一側的筷子。 2.僅僅左右均可用時拿起筷子。 3.奇數偶數號哲學家拿筷子順序相反。

3、讀者-寫者問題

寫操作必須單獨進行，讀操作可以與其他讀操作一起進行

線程的基本概念

1、線程的引入

目的：為了減少程序在并發執行時所付的時空開銷（創建進程時分配資源，建立PCB、撤銷進程時回收資源與撤銷PCB、進程切換時保留、更改處理機環境），使OS具有更好的并發性。

線程作為調度和分派的基本單位，即并不把作為調度和分派的基本單位也同時作為擁有資源的單位。

2、線程與進程的比較

—1、調度的基本單位

引入線程后，把線程當作調度和分派的基本單位，線程切換時，僅需要保存和設置少量寄存器內容，切換代價小。

—2、并發性

引入線程后，不僅進程可以并發，同一個或不同進程的多個線程同樣也能并發執行，使得OS有更好的并發性，提高系統資源利用率和吞吐量。

—3、擁有資源

進程擁有資源，但線程并不擁有系統資源，而僅保留一點必不可少的、能保證獨立運行的資源。同時允許多個線程共享擁有的資源，可以訪問進程擁有的資源。

—4、獨立性

同一進程的不同線程之間的獨立性要小于不同進程之間的獨立性，因為防止進程被彼此干擾破壞，每個進程都獨立擁有地址空間和其他資源。而同一進程的不同線程則是為了提高并發性以及相互合作而創建的，共享內存地址空間和資源。

—5、系統開銷

進程開銷明顯大于線程。

—6、支持多處理機系統

傳統進程只能在同一個處理機上運行，而線程可在多個處理機上運行。

習題與答案

4、程序并發執行時為什么會失去封閉性和可再現性？ P38

因為并發執行的程序共享系統資源，失去了封閉性，又因為失去了封閉性，調用同一資源先后順序不同可能造成結果不同，失去了可再現性。

5、在操作系統中為什么要引入進程的概念？他會產生什么樣的影響？ P39

多道程序環境下，并發執行的程序失去了封閉性和可再現性，因此通常的程序時不能夠并發執行的，否則程序的運行就失去了意義。為了程序能夠并發執行，并且能夠對程序加以描述和控制，引入了進程的概念。進程的加入使之能夠并發執行，且更便于描述與控制，使系統資源利用率更高，吞吐量更大。

7、試說明PCB的作用具體體現在哪幾個方面？為什么說PCB是進程存在的唯一標志？ P44

PCB的作用主要體現在如下幾個方面：1.能作為獨立運行的標志。 2.能實現間斷性運行方式。 3.提供進程管理所需要的信息。 4.能提供進程調度所需要的信息。 5.實現與其他進程的同步和通信。 PCB的信息中中含有進程標識符，進程標識符用于唯一地標識一個進程，因此PCB是進程存在的唯一標志。

8、PCB提供了進程管理和進程調度所需要的哪些信息？ P45

進程管理：程序和數據的地址、進程同步和通信機制、資源清單、鏈接指針。

進程調度 ：進程狀態、進程優先級、進程調度所需要的其他信息、事件。

11、試說明進程在三個狀態之間轉換的典型原因。 P40

就緒->執行：進程調度

執行->阻塞：I/O請求

阻塞->就緒：I/O完成

執行->就緒：時間片完

12、為什么要引入掛起狀態？該狀態有哪些性質？ P41

基于系統和用戶的如下需要：終端用戶的需要、父進程請求、負荷調節的需要、操作系統的需要。處于掛起狀態的進程不能接受處理機調度。

13、在進程切換時，所要保存的處理機狀態信息有哪些？ P45

通用寄存器、指令計數器、程序狀態字PSW、用戶棧指針。

14、試說明引起進程創建的主要事件。 P49

用戶登錄、作業調度、提供服務與應用請求。

15、試說明引起進程被撤銷的主要事件。 P50

程序執行完畢正常結束、程序發生異常結束、因外界請求干預結束。

16、在創建一個進程時所要完成的主要工作是？ P49

申請空白PCB，為新進程分配資源，初始化PCB，若就緒隊列能夠接納新進程，將新進程插入就緒隊列。

17、在撤銷一個進程時所要完成的主要工作是？ P50

根據進程標識符，檢索PCB，讀出進程狀態，若處于執行狀態，立即終止，修改調度標志為真表示應重新調度，若還有子進程，將子進程也終止，將所有資源歸還給父進程或系統，移除該進程的PCB。

18、試說明引起進程阻塞或被喚醒的主要事件是什么？ P50

阻塞：向系統請求共享資源失敗、等待某種操作完成、新數據尚未到達、等待新任務的到達。

喚醒：阻塞時期待的事件完成。

19、為什么要在OS中引入線程？ P81

進程在操作時的時空開銷太大，且在多處理機系統上的，進程只能運行在一個處理機上。引入線程，可以使系統擁有更高的資源利用率與吞吐量。

21、試從調度性、并發性、擁有資源及系統開銷方面對線程與進程比較。 P81

調度性：傳統OS中，進程作為調度的基本單位，每次調度時開銷較大。而引入線程后，線程是調度的基本單位，線程切換時僅需保存和設置少量寄存器內容，切換代價遠小于進程。

并發性：引入線程的OS中，不僅進程可以并發，同一個進程的所有線程也可以并發執行，同樣，不同進程中的線程也可以并發執行。

擁有資源：進程是系統擁有資源的一個基本單位，而線程并不擁有系統資源，而是僅有一點必不可少，保證獨立運行的資源。

系統開銷：創建撤銷進程時，系統要為之分配回收PCB和其他資源。而線程的開銷遠小于進程。

總結

以上是生活随笔為你收集整理的操作系统第二章-进程的描述与控制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。