『操作系统』 进程的描述与控制 Part 1 前驱图与程序执行
文章目錄
- 2.1 前趨圖和程序執行
- 2.1.1 程序的順序執行及其特征
- 1. 程序的順序執行
- 2.程序順序執行時的特征
- 2.1.2 前趨圖
- 2.1.3 程序的并發執行及其特征
- 1. 程序的并發執行
- 2. 程序并發執行時的特征
- 3.程序并發執行的描述
- 4.采用并發程序設計的目的
- 練習題
- 2.2 進程的描述
- 1. 進程（ Process ）的定義
- 2. 進程的特征
- 3. 進程與程序的區別
- 練習題
- 4、進程的基本狀態-三態模型
- 練習題
- 5、五態模型
- 6、七態模型
- 練習題
- 7、進程控制塊
- 練習題
- 練習題
- 練習題
- 2.3 進程控制
- 2.3.1 進程創建
- 1. 進程圖
- 2.引起創建進程的事件
- 練習題
- 3.進程的創建過程
- 2.3.2 進程終止
- 1. 引起進程終止的事件
- 2.3.3 進程的阻塞與喚醒
- 1. 引起進程阻塞的事件
- 2.進程阻塞過程
- 3.進程喚醒過程
- 2.3.4 進程掛起/激活
- 1.進程的掛起
- 2.進程激活
- 練習題
2.1 前趨圖和程序執行
2.1.1 程序的順序執行及其特征
1. 程序的順序執行
一個程序由若干個程序段組成，而這些程序段的執行必須是順序的，這種程序執行的方式就稱為程序的順序執行。
2.程序順序執行時的特征
(1) 順序性
處理機的操作嚴格按照程序所規定的順序執行。
(2) 封閉性
程序一旦開始執行，其計算結果不受外界因素的影響。
(3) 可再現性
程序執行的結果與它的執行速度無關(即與時間無關)，而只與初始條件有關
2.1.2 前趨圖
前驅圖是一個 DAG，其用于描述進程間執行的先后次序，圖中的每個結點用于表示一個進程或一個程序段，結點間的有向邊表示兩個結點間存在的偏序關系(前趨關系)。進程間的前趨關系用 → 來表示，若進程 Pi 和 Pj 間存在前趨關系，可表示為 (Pi,Pj)∈→，即：Pi→Pj，表示 Pj 在執行前
Pi 必須完成。
在前驅圖中，將沒有前驅的結點稱為初始結點，將沒有后繼的結點稱為終止結點，此外，每個結點還具有一個價值，用于表示該結點所含有的進程的執行時間
- 結點 ： 描述一個程序段或進程，或一條語句。
- 有向邊： 結點之間的前趨關系“->”
- Pi->Pj ：Pi 必須在 Pj 開始之前完成，則 Pi是Pj的直接前趨，Pj是Pi的直接后繼
- 初始結點: 沒有前趨的結點
- 終止結點: 沒有后繼的結點
- 重量: 結點的程序量或執行時間
前趨圖中絕對不能出現循環
2.1.3 程序的并發執行及其特征
1. 程序的順序執行
一個應用程序由若干程序段組成，每一程序段完成特定的功能，他們在執行時，都要按照某種先后次序執行，僅當前一程序段執行完后，再運行后一程序段，這種執行過程被稱為程序的順序執行。程序順序執行時，具有以下三個特征：
順序性：處理機的操作嚴格按程序規定順序執行
封閉性：程序一旦開始執行，其計算結果不受外界因素影響
可再現性：程序執行只要初始條件一樣，不論如何停頓，重復執行多少次結果都一樣
2. 程序的并發執行
例：在系統中有n個作業，每個作業都有三個處理步驟，輸入數據、處理、輸出，即Ii,Ci,Pi (i=1,2,3,…,n)。
這些作業在系統中執行時是對時間的偏序，有些操作必須在其它操作之前執行，這是有序的，但有些操作是可以同時執行的。
3. 程序并發執行時的特征
(1) 間斷性
在多道程序設計的環境下，程序是并發執行的，由于它們共享系統資源，以及為完成同一項任務而相互合作，致使在這些并發執行的程序之間形成了相互制約的關系。
相互制約導致并發程序具有“執行-暫停-執行”這種間斷性的活動規律。
(2) 失去封閉性
程序在并發執行時，多道程序共享系統的資源，因而這些資源的狀態由多道程序來改變，程序運行失去封閉性。一程序的運行受到其他程序的影響。
(3) 不可再現性
程序在并發執行時，失去封閉性導致其失去可再現性。
(4) 程序與計算不再一一對應
程序并發執行時失去程序的封閉性和可再現性的主要原因是什么？
解答： 并發運行的程序相互制約
4.程序并發執行的描述
- 若干個程序段同時在系統中運行，這些程序的執行在時間上是重迭的；
- 一個程序段的執行尚未結束，另一個程序段的執行已經開始；
- 即使這種重迭是很小的，也稱這幾個程序段是并發執行的。
描述
cobegin
S1;S2;S3;…;SN
coend;
其中Si(i=1,2,3,…,n)表示n個語句（程序段），這n個語句用cobegin和coend括起來表示這n個語句是可以并發執行的。
co是concurrent的頭兩個字符。 這是Dijkstra提出的。
5.采用并發程序設計的目的
- 充分發揮硬件的并行性，消除處理器和I/O 設備的互等現象，提高系統效率。
- 并發程序設計是多道程序設計的基礎，多道程序的實質就是把并發程序設計引入到單處理器的系統中。
練習題
1.[2017考研真題 28]與單道系統相比，多道程序系統的優點是（D）
Ⅰ．CPU利用率高
Ⅱ．系統開銷小
Ⅲ．系統吞吐率大
Ⅳ．I/O設備利用率高
A．僅 Ⅰ、Ⅲ
B．僅 Ⅰ、Ⅳ
C．僅 Ⅱ、Ⅳ
D．僅 Ⅰ、Ⅲ 、Ⅳ
2.2 進程的描述
在多道程序設計的環境下，為了描述程序在計算機系統內的執行情況，必須引人新的概念——進程。
1. 進程（ Process ）的定義
進程是一個可并發執行的程序在其數據集上的一次運行過程，是操作系統進行資源分配的單位,進程表示資源的占用和所要做的工作。
各種不同的進程定義
- 行為的一個規則叫做程序，程序在處理機上執行時所發生的活動稱為進程（Dijkstra)。
- 進程是這樣的計算部分，它是可以和其它計算并行的一個計算。(Donovan)
- 進程（有時稱為任務）是一個程序與其數據一道通過處理機的執行所發生的活動。（Alan.C. Shaw)
- 進程是執行中的程序。（Ken Thompson and Dennis Ritchie )
進程的定義：可并發執行的程序在一個數據集合上的一次執行過程。
進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。
2. 進程的特征
動態性、并發性、獨立性、異步性、結構性
(1)動態性——進程是程序在處理機上的一次執行過程。具有生命期。
(2)并發性——多個進程實體同存于內存中，在一段時間內同時運行。以提高資源利用率。
(3) 獨立性——進程實體是一個能獨立運行、獨立分配資源和獨立接受調度的基本單位，而程序則不是。
(4) 異步性——進程按各自獨立的、不可預知的速度向前推進。
(5) 結構性——進程控制塊(PCB)+程序段+相關的數據段=進程實體。
3. 進程與程序的區別
- 進程是動態的，程序是靜態的
- 進程是暫時的，程序是永久的
- 進程與程序的組成不同：
程序是指令的有序集合；
進程包括程序、數據和進程控制塊(即進程狀態信息） - 進程與程序的對應關系：
無一一對應關系(一個進程可順序執行多個程序;一個程序可由多個進程共用）
練習題
操作系統引入進程后，不能（C）
A．提高資源的利用率
B．正確描述程序的執行情況
C．提高用戶編程能力
D．允許一個程序同時被多個用戶調用
進程的類型
（1）系統進程：執行操作系統核心代碼的進程。系統進程起著資源管理和控制的作用。
（2）用戶進程：執行用戶程序的進程。
（3）計算進程，I/O進程。
（4）前臺進程，后臺進程。
4、進程的基本狀態-三態模型
- 運行態（running）：進程占有處理器正在運行。
- 就緒態（ready）：進程具備運行條件，等待系統分配處理器以便運行。
- 等待態（wait）：又稱為阻塞（blocked）態或睡眠（sleep）態，進程不具備運行條件，正在等待某個事件的完成。
不同系統設置的進程狀態數目不同
三態轉換圖
正經圖來了
引起進程狀態轉換的具體原因
- 運行態→等待態：等待使用資源或某事件發生；
- 等待態→就緒態：資源得到滿足或事件發生；
- 運行態→就緒態：運行時間片到；出現有更高優先權進程。
- 就緒態→運行態：CPU空閑時選擇一個就緒進程。
練習題
1.[2015考研題 25] 下列選項中會導致進程從執行態變為就緒態的事件是（D）
A．執行P(wait)操作
B．申請內存失敗
C．啟動I/O 設備
D．被高優先級進程搶占
2.[2014考研題 26] 一個進程的讀磁盤操作完成后，操作系統針對該進程必做的是（A）
A．修改進程狀態為就緒態
B．降低進程優先級
C．給進程分配用戶內存空間
D．增加進程時間片大小
5、五態模型
五態模型在三態模型的基礎上引進了新建態和終止態。
- 新建態—對應進程剛被創建的狀態。為一個新進程創建必要的管理信息，它并沒有被提交，而是在等待操作系統完成創建進程的必要操作。
- 終止態—進程的終止狀態。首先，等待操作系統進行善后，然后，退出主存。進入終止態的進程不再執行，但依然臨時保留在系統中等待善后。一旦其他進程完成了對終止態進程的信息抽取之后，系統將刪除該進程。
進程狀態轉換的具體原因
- NULL→新建態：創建一個子進程。
- 新建態→就緒態：系統完成了進程創建操作，且當前系統的性能和內存的容量均允許。
- 運行態→終止態：一個進程到達自然結束點，或出現了無法克服的錯誤，或被操作系統所終結，或被其他有終止權的進程所終結。
- 終止態→NULL：完成善后操作。
- 就緒態→終止態：某些操作系統允許父進程終結子進程。
- 等待態→終止態：某些操作系統允許父進程終結子進程。
6、七態模型
(1)為什么要有“掛起”狀態?
由于進程的不斷創建，系統資源已不能滿足進程運行的要求，就必須把某些進程掛起（suspend），對換到磁盤鏡像區中，暫時不參與進程調度，起到平滑系統負載的目的。
(2)引起掛起狀態的原因
- 終端用戶的需要：終端用戶在自己程序運行中發現問題要求使正在執行的進程暫停執行而使進程處于掛起狀態。
- 父進程的需要：父進程為了考查和修改某個子進程，或者協調各子進程間的活動，需要將該子進程掛起。
- 操作系統的需要：操作系統為了檢查運行中的資源使用情況或進行記帳，而將某些進程掛起。
- 對換的需要：為了提高內存的利用率，而將內存中某些進程掛起，以調進其它程序運行。
- 負荷調節的需要：由于工作負荷較重，而將一些不重要的進程掛起，以保證系統能正常運行（實時操作系統） 。
(3)進程增加的兩個新狀態
- 掛起就緒態（ready suspend）：表明進程具備運行條件但目前在輔助存儲器中，當它被對換到主存才能被調度執行。
- 掛起等待態（blocked suspend）：表明進程正在等待某一個事件且在輔助存儲器中。
(4)引起進程狀態轉換的具體原因
- 等待態→掛起等待態：系統根據當前資源狀況和性能要求，決定將一個等待態進程對換出去成為掛起等待態；
- 就緒態→掛起就緒態：系統根據當前資源狀況和性能要求，決定把就緒態進程對換出去成為掛起就緒態。
- 掛起等待態→掛起就緒態：引起進程等待的事件發生之后，相應的掛起等待態進程將轉換為掛起就緒態。
- 掛起等待態→等待態：當一個進程等待一個事件時，原則上不需要把它調入內存。但是，當其它進程退出后，主存已經有了足夠的自由空間，而某個掛起等待態進程具有較高的優先級并且操作系統已經得知導致它阻塞的事件即將結束，便可能發生這一狀態變化。
- 掛起就緒態→就緒態：內存中沒有就緒態進程，或掛起就緒態進程具有比就緒態進程更高的優先級，將把掛起就緒態進程轉換成就緒態。
- 運行態→掛起就緒態：當一個高優先級等待進程的等待事件結束后，它將搶占CPU，而此時主存不夠，從而可能導致正在運行的進程轉化為掛起就緒態。運行態的進程也可以自己掛起自己。
- 新建態→掛起就緒態：根據系統當前資源狀況和性能要求，可以將新建進程對換出去成為掛起就緒態。
掛起的進程將不參與低級調度直到它們被對換進主存。
(5)掛起進程具有如下特征
- 該進程不能立即被執行。
- 掛起進程可能會等待事件，但所等待事件是獨立于掛起條件的，事件結束并不能導致進程具備執行條件。
- 進程進入掛起狀態是由于操作系統、父進程或進程本身阻止它的運行。
- 結束進程掛起狀態的命令只能通過操作系統或父進程發出。
練習題
針對分時系統，進程的三種狀態之間有幾種可能的轉換關系？
在單處理機的分時系統中，分配給進程P的時間片用完后，系統進行切換，結果調度到的仍然是進程P。有可能出現上述情形嗎？如果可能請說明理由。
解答：
有可能出現上述情況。
- 例如,若在進程P時間片用完后，被迫回到就緒隊列時，就緒隊列為空，這樣進程P就是就緒隊列中惟一的一個進程，于是調度程序選中的進程必是進程P；
- 又如在按優先級調度的系統中，就緒隊列按進程優先級排列，在進程P時間片用完之后回到就緒隊列時，若其優先級高于當前就緒隊列中的其他進程程，則它將排在就緒隊列之首，從而再次被調度程序選中并投入運行。
7、進程控制塊
進程控制塊中的信息
1)進程標識符信息 ：每個進程都必須有一個唯一的標識符
- 內部標識符：便于系統使用
- 外部標識符：便于用戶使用
2)處理機狀態信息(現場信息)
處理機狀態信息主要由處理機的各種寄存器中的內容組成。處理機運行時的信息存放在寄存器中，當被中斷時這些信息要存放在PCB中。
- 通用寄存器
- 指令計數器
- 程序狀態字PSW
- 用戶棧指針
- 指向該進程頁表的指針
3)進程調度信息
- 進程優先級
- 進程調度所需的其他信息（執行時間等）
- 事件
- 進程狀態
4)進程控制信息
- 程序和數據的地址
- 進程同步和通信機制
- 資源清單（打開文件表等）
- 鏈接指針
練習題
1.“程序狀態字寄存器內容”屬于進程控制塊的?
A、標識信息
B、控制信息
C、現場信息
D、調度信息
2.進程控制塊中的現場信息是在（D）保存的。
A、創建進程時
B、處理器執行指令時
C、中斷源申請中斷時
D、中斷處理程序處理中斷前
進程組織方式
1）線性方式:
2）索引方式
CPU模式和進程類型
進程的兩大類：
系統進程：運行在內核模式，執行操作系統代碼；
用戶進程：運行在用戶模式，執行用戶程序代碼。
練習題
1.判斷：操作系統通過PCB來控制和管理進程，用戶進程也可以對PCB中的信息進行讀寫操作。
答案： 錯誤
2.在一個單處理機系統中，若有10個用戶進程，則處于“運行”、“阻塞”、“就緒”狀態的進程數量最小和最大值分別可能是多少？
答案：
運行態：最少0個，最多1個；
阻塞態：最少0個，最多10個；
就緒態：最少0個，最多9個。
3.某系統的進程狀態變遷如圖所示（設該系統的進程調度方式為可剝奪方式）
1）說明進程發生變遷1、3、5的原因；
2）當發生一個變遷時可能引起另一個變遷的發生，則這兩個變遷稱為因果變遷。下述因果變遷是否會發生，如果有可能的話，會在什么情況下發生？ (a) 3→5 (b) 3→2 ? 2→1 (d) 4→1 (e) 4→5
3）根據狀態變遷圖說明該系統的調度策略和調度效果。
答案：
1）系統中當前運行著的進程因中止、結束或等待某個I/O事件而退出運行，并且此時高優先就緒隊列中沒有等待進程，發生變遷1；
當運行著的進程發出I/O請求，需要等待I/O事件完成才能繼續進行，發生變遷3；
當有高優先級進程進入就緒隊列，并且運行著的進程是低優先級進程時，高優先級進程會搶占CPU，發生變遷5。
2）
(a) 3→5 是因果變遷；
(b) 3→2 不是；
? 2→1 是；
(d) 4→1 不是；
(e) 4→5 是。
3）此系統采用根據進程優先級分別設置高優先就緒隊列和低優先就緒隊列：
高優先進程運行100ms 后就降為低優先就緒隊列，以使短進程優先完成；
對低優先就緒隊列中的進程采用時間片輪轉法（時間片程度為500ms），確保每個進程都有運行機會；
同時，對于進行了I/O操作的進程賦予一個高優先級，保證對外界事件可以盡快響應。
4.程序并發執行時失去封閉性和可再現性的主要原因是：
答案： 運行程序的相互制約
5.處于等待狀態的進程也希望占有處理機
答案： 錯
6.簡述進程控制塊的作用。
答案：
- 進程控制塊是進程存在的唯一標志；
- 是操作系統對進程進行控制和管理的依據；
- 記錄進程的各種屬性，描述進程的動態變化過程；
- 與進程一一對應。
練習題
1.系統中有N(N>2)個進程,并且當前沒有執行進程調度程序,則(D)不可能發生.
A.有一個運行進程,沒有就緒進程,還有N-1個進程處于等待狀態
B.有一個運行進程, N-1個就緒進程, 沒有進程處于等待狀態
C.有一個運行進程和一個就緒進程,還有N-2個進程處于等待狀態
D.沒有運行進程,但有兩個就緒進程,還有N-2個進程處于等待狀態
2.在進程管理中，當?時，進程從阻塞狀態變為就緒狀態。
A.進程被進程調度程序選中
B.等待某一事件
C.等待的事件發生
D. 時間片用完
3.分配到必要的資源并獲得處理機時的進程狀態是(B)。
A.就緒狀態
B.執行狀態
C.阻塞狀態
D.撤消狀態
4．進程的三個基本狀態在一定條件下可以相互轉化，進程由就緒狀態變為運行狀態的條件是(D)。
A.時間片用完
B.等待某事件發生
C.等待的某事件已發生
D.被進程調度程序選中
5．進程的三個基本狀態在一定條件下可以相互轉化，進程由運行狀態變為阻塞狀態的條件是(B)。
A.時間片用完
B.等待某事件發生
C.等待的某事件已發生
D.被進程調度程序選中
6．下列的進程狀態變化中，?變化是不可能發生的。
A．運行→就緒
B．就緒→運行
C．等待→運行
D．等待→就緒
7．一個運行的進程用完了分配給它的時間片后，它的狀態變為(A)。
A.就緒
B.等待
C.運行
D.由用戶自己確定
8．操作系統通過(B)對進程進行管理。
A. JCB
B. PCB
C. DCT
D. CHCT
9．一個進程被喚醒意味著(D)。
A. 該進程重新占有了CPU
B. 它的優先權變為最大
C. 其PCB移至等待隊列隊首
D. 進程變為就緒狀態
10．多道程序環境下，操作系統分配資源以?為基本單位。
A. 程序
B. 指令
C. 進程
D. 作業
2.3 進程控制
- 進程控制是進程管理中最基本的功能
用于創建和撤銷進程；
控制進程狀態的轉換； - 進程控制是操作系統的內核通過原語來實現的
進程的創建與終止
進程的阻塞與喚醒
進程的掛起與激活
原語(primitive)：由若干條指令構成的“原子操作(atomic operation)”過程，作為一個整體而不可分割－－要么全都完成，要么全都不做。許多系統調用就是原語。
特征:“不可中斷性”。
實現方法：屏蔽中斷。
2.3.1 進程創建
1. 進程圖
- 描述進程的家族關系的有向樹.
- 進程Pi創建了進程Pj，則Pi是Pj的父進程， Pj是Pi的子進程，用一條由進程Pi指向進程Pj的有向邊來描述。
- 創建父進程的進程為祖先進程，由此形成進程樹，樹根為進程家族的祖先。
計算機系統的啟動過程- BIOS啟動（POST加電自檢，讀取MBR）
- 系統引導（bootloder）
- 啟動內核
- 初始化系統
2.引起創建進程的事件
- 用戶登錄
- 作業調度
- 提供服務
- 應用請求
練習題
1.[2009年考研題 24]下列選項中，導致創建新進程的操作是（C）
I 用戶登陸成功
II 設備分配
III 啟動程序執行
A、僅I和II
B、僅II和III
C、僅I和III
D、I、II、III
3.進程的創建過程
操作系統發現有創建新進程的事件后，調用進程創建原語(CreateProcess/Fork)創建新進程。
創建過程：
(1)申請空白PCB
(2)為新進程分配資源
(3)初始化PCB
(4)將新進程插入就緒隊列
父進程創建子進程與主程序調用子程序有何不同？
- 父進程創建子進程后，父進程與子進程同時執行；
- 主程序調用子程序，主程序暫停在調用點，子程序開始執行，直到子程序執行完畢返回，主程序開始執行。
2.3.2 進程終止
1. 引起進程終止的事件
越界錯誤、保護錯、非法指令、特權指令錯、運行超時
- 操作員或操作系統干預
- 父進程請求
- 父進程終止
進程的終止過程
(1) 根據被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態。
(2) 若被終止進程正處于執行狀態，應立即終止該進程的執行，置調度標志為真，用于指示該進程被終止后應重新進行進程調度。
(3) 若該進程有子孫進程，應將其所有子孫進程予以終止，以防他們成為不可控的進程。
(4) 將被終止進程所擁有的全部資源，或歸還其父進程，或歸還系統。
(5) 將被終止進程的PCB從所在隊列或鏈表中移出，掛入空白PCB隊列。
2.3.3 進程的阻塞與喚醒
(block與wakeup原語)
1. 引起進程阻塞的事件
2.進程阻塞過程
- 調用阻塞原語阻塞自己，終止該進程的執行，將PCB中的狀態改為阻塞，并加入到阻塞隊列中；
- 然后轉進程調度，將處理機分配給另一進程，并進行進程切換以及處理機狀態的保護與重新設置。
3.進程喚醒過程
- 阻塞進程等待的事件發生，有關進程調用喚醒原語把等待該事件的進程喚醒。
- 把阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的現行狀態改為就緒，將PCB插入到就緒隊列中。
- 阻塞原語與喚醒原語作用相反，成對使用
2.3.4 進程掛起/激活
(suspend/active)
1.進程的掛起
當出現引起進程掛起的事件時，系統利用掛起原語將指定進程掛起。
- 檢查被掛起進程的狀態；
- 若處于活動就緒，則改為靜止就緒；
- 若處于活動阻塞，則改為靜止阻塞；
- 將該進程PCB復制到內存指定區域；
- 若掛起的進程正在執行，則重新進行進程調度。
2.進程激活
- 當發生激活進程的事件時，系統利用激活原語將指定進程激活。
- 激活原語先將進程從外存調入內存，檢查該進程的狀態;
若處于靜止就緒，則改為活動就緒;
若處于靜止阻塞，則改為活動阻塞;
若采用搶占調度策略，則新進程進入就緒隊列時，檢查是否要重新進行進程調度。
練習題
1.只作用于一個進程一次的原語是（A）
A.創立
B.解掛
C.阻塞
D.掛起
2.給出用于進程控制的四種常見的原語 創建原語 、 撤消原語 、 阻塞原語 、 喚醒原語 。
3.操作系統對進程的管理和控制主要是通過控制原語實現的。
錯誤： 對
4.原語的執行是屏蔽中斷的。
錯誤： 對
總結
以上是生活随笔為你收集整理的『操作系统』 进程的描述与控制 Part 1 前驱图与程序执行的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 海外服务器如何加速
- 下一篇： win10登录选项不见了怎么办 win1