Operating System Concepts 作業系統原理 Chapter 3 行程觀念 (Process Concept)

Chapter 3 行程觀念 3.1 行程概念 3.2 行程排班 3.3 行程的操作 3.4 行程間通訊

3.1 行程概念 討論作業系統的一個問題就是該如何稱呼CPU所有的運作項目。 - 整批式(Batch)系統執行工作 (jobs)， - 分時系統有使用者程式(user programs)，(或稱為任務，task)。 在單一使用者系統 (如Microsoft Windows)使用者仍可同時執行數個程式:一個文書處理程式、網頁瀏覽器、email套件程式。就算使用者只能一次執行一個程式，作業系統仍須支援其內部一些工作，比方說是記憶體管理。從各方面看來，這些所有的事情都類似，所以稱之為行程(Process)。

3.1.1 行程 行程指的是正在執行的程式。行程不只是程式碼 (有時也稱為本文區，text section)而已。它還包含代表目前運作的程式計數器 (Program counter)數值和處理器的暫存器內容。 行程還包括存放暫用資料 (譬如:副程式的參數、返回位址，及暫時性變數)的行程堆疊 (stack)，以及包含整體變數的資料區間(data section)。行程也包含堆積 (heap)，堆積就是在行程執行期間動態配置的記憶體，行程記憶體結構如圖。

3.1.2 行程狀態 行程在執行時會改變其狀態。行程的狀態 (state)部份是指該行程目前的動作，每一個行程可能會處於以下數種狀態之一: 新產生 (new):該行程正在產生中。 執行 (running):指令正在執行。 等待(waiting):等待某件事件的發生(譬如輸出入完成或接收到一個信號)。 就緒 (ready):該行程正等待指定一個處理器。 結束 (terminated):該行程完成執行。

3.1.3 行程控制表 每一個行程在作業系統之中都對應著一個行程控制表 (Process control block (PCB)或稱任務控制表 (task control block)，如圖。 行程控制表 (PCB)記載所代表的行程之相關資訊，包括: 行程狀態:可以是new、ready、running、waiting或halted等。 程式計數器:指明該行程接著要執行的指令位址。

CPU暫存器:其數量和類別，完全因電腦架構而異。包括累加器 (accumulator)、索引暫存器 (index register)、堆疊指標 (stack pointer)以及一般用途暫存器 (general-purpose register)等，還有一些狀況代碼 (condition code)。當中斷發生時，這些狀態資訊以及程式執行計數器必須儲存起來，以便稍後利用這些儲存的資訊，使程式能於中斷之後順利地繼續執行。 CPU排班法則相關資訊:包括行程的優先順序 (Priority)、排班佇列 (scheduling queue)的指標以及其它的排班參數。 記憶體管理資訊:這些資訊包括如基底暫存器(base register)和限制 暫存器(limit register)，分頁表(Page table)值的資訊所使用的記 憶系統區段表(segment table)。 帳號資訊:包括了CPU和實際時間的使用數量、時限、帳號工作或行程 號碼。 輸入/輸出狀態資訊:包括配置給行程的輸入/輸出裝置，包括開啟檔案 的串列 等等。

3.2 行程排班(Process Scheduler) 多元程式規劃系統(Multiprogramming)的主要目的，是隨時有一個行程在執行，藉以提高CPU的使用率。分時系統(Time Sharing)的目的是將CPU在不同行程之間不斷地轉換，以便讓使用者可以在自己的行程執行時與它交談。 為了達到這個目的，行程排班程式(Scheduler)為CPU上執行程式選擇一個可用的行程(可能由一組可用行程)。 單一處理器系統，不可能有一個以上的行程同時執行。如果有多個行程，其它的都必須在旁邊等待一直到CPU有空，才可能重新排列。

3.2.1 排班佇列(Scheduling Queues) 行程進入系統時，是放在工作佇列(Job Queue)之中，此佇列是由系統中所有的行程所組成。位於主記憶體中且就緒等待執行的行程是保存在一個所謂就緒佇列 (Ready Queue)的串列。這個佇列一般都是用鏈接串列的方式儲存。在就緒佇列前端保存著指向這個串列的第一個和最後一個PCB的指標。

一個新的行程最初是置於就緒佇列中。就一直在就緒佇列中等待，直到選來執行。一旦這個行程配置CPU並且進行執行，則會有若干事件之一可能發生: ．行程可發出I/0要求，然後置於一個I/0佇列中。 ．行程可產生出一個新的子行程並等待後者的結束。 ．行程可強行地移離CPU(如用中斷的結果一樣)，然後放回就緒佇列中。

3.2.2 排班程式(Schedulers) 作業系統必須按排班次序從這些佇列選取行程。行程的選取將由適當的排班程式 (Scheduler)來執行。 Batch系統 - Long-term Scheduler (Job Scheduler) 從Spooled (行程池)中選出 行程並且將它們載入記憶體內以便執行。 Short-term Scheduler (or CPU Scheduler) 從記憶體中選出一個已 經準備就緒的行程，並且將CPU分配給它。 分時系統(Time Sharing)，可能會採用一種額外的、間接方式來排班。 中程排班程式 (Medium-term Scheduler)背後的最主要觀念就是有時可以將行程從記憶體中有效地移開(並且從對CPU的競爭中移開)、並減低多元程式規劃的程度(Multiprogramming)。

3.2.3 內容轉換(Context Switch) 當中斷(Interrupt)發生時，系統先暫停Process，爾後再恢復Process。做法是將目前在CPU上執行行程(Process)的內容 (Context)先儲存起來，以便作業完成時，可以還原Process之內容。 轉換 CPU至另一項行程時必須將舊行程的狀態儲存(State Save)起來，然後再載入新行程的儲存狀態(還原狀態：State Restore)。這項任務稱為內容轉換(Context Switch)。

3.3 行程的操作 (Operations on Processes) 系統中的各個行程可以並行(Concurrently)地執行，而且也要能動態地產生或刪除。作業系統必須提供行程產生和結束的功能。

3.3.1 行程的產生(Process Creation) 一個行程的執行期間，可以利用產生行程的系統呼叫來產生數個新的行程。原先的行程就叫做父行程 (Parent Process)，而新的行程則叫做子行程(Children Process)。每一個新產生的行程可以再產生其它的行程，這可以形成一幅行程樹 (Tree of Processes)。

fork()產生Sub-Process or Child Process函數 ls指令: 顯示檔案目錄

3.3.2 行程的結束(Process Termination) 一個行程在執行完最後一個敘述(Statement)，以及使用系統呼叫 exit() 要求作業系統將自己刪除時結束。這個行程的所有資源 (包括實體記憶體、虛擬記憶體、開啟檔案，以及輸入輸出緩衝區) 都由作業系統收回。 一個父行程可以基於若干理由將子行程中止︰ 子行程已經使用超過配置的資源數量。 指派給子行程的工作已經不再需要。 父行程結束，而作業系統不允許子行程在父行程結束之後繼續執行。

3.4 行程間通訊(Interprocess Communication) 在OS中同時執行的行程分為獨立行程(Independent)及合作(Cooperating Process)行程。 合作行程(Cooperating Process) 資訊共享(Information Sharing): 數個使用者可能對相同的一項資訊(例如，公用檔案)有興 趣，因此須提供一個環境允許使用者能同時使用這些資源。 加速運算(Computation Speedup): 如果希望某一特定工作執行快一點，則可以分成一些子工作， 每一個子工作都可以和其它子工作平行地執行。 模組化(Modularity): 以模組的方式來建立系統，把系統功能分配到數個行 程。 方便性(Convenience):即使是單一使用者也可能同時執行數項工作。 合作行程間通訊有二個基本模式︰ 共用記憶體及訊息傳遞。 Send M訊息 Receive M訊息

Producer-Consumer Problem 3.4.1共用記憶體系統(Shared-Memory Systems) 為了闡述合作行程的觀念，讓我們來看「生產者-消費者」的問題。生產者(Producer)行程產生資訊，消費者(Consumer)行程消耗掉這些資訊。 Producer-Consumer Problem Paradigm for cooperating processes, producer process produces information that is consumed by a consumer process unbounded-buffer places no practical limit on the size of the buffer bounded-buffer assumes that there is a fixed buffer size

Bounded-Buffer – Shared-Memory Solution Shared data #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; Solution is correct, but can only use BUFFER_SIZE-1 elements

Bounded-Buffer – Producer while (true) { /* Produce an item */ while (((in = (in + 1) % BUFFER_SIZE count) == out) ; /* do nothing -- no free buffers */ buffer[in] = item; in = (in + 1) % BUFFER_SIZE; } X in指向buffer中的下一個空位 out指向buffer中的下一個填滿資料位置 當in=out時, 表示buffer是空的 Bounded Buffer – Consumer while (true) { while (in == out) ; // do nothing -- nothing to consume // remove an item from the buffer item = buffer[out]; out = (out + 1) % BUFFER SIZE; return item; }

3.4.2 訊息傳遞系統(Message-Passing Systems) 訊息傳遞提供行程互相溝通和彼此同步而不需要共享相同的位址空間。 訊息傳遞設施提供至少兩種操作：send(訊息) 和 receive(訊息)。 如果兩個行程 P 與 Q 要互相聯繫，則它們必須互相傳送與接收訊息。為了使它們可這樣做，因此在它們間必須存在一個通訊鏈(Communication Link)。 通訊鏈操作方法(send/receive): - 直接或間接聯繫(Direct or Indirect Communication) - 同步或非同步聯繫(Synchronous or Asynchronous Communication) - 自動或明確的緩衝作用(Automatic or Explicit Buffering)

3.4.2.1 命名(Naming) 直接聯繫 (Direct Communication)方法中，每一個要傳送或接收訊息的行程必須先確定聯繫接收者或傳送者的名稱。在這個體系之中，send 與 receive的基本運算定義如下: send (P, message)傳送一個訊息(message)至行程P。 receive (Q, message)自行程Q接收一個訊息(message)。 間接式聯繫(Indirect Communication)之中，需藉著信箱(mailbox，也叫作埠，port)來傳送與接收訊息。這種 send 與 receive 的基本運算之定義如下: send (A, message) 將訊息 (message)傳送至信箱A。 receive (A, message) 自信箱A接收一個訊息 (message)。

3.4.2.2 同步化(Synchronization) 訊息傳遞可以是等待(Blocking)或非等待(Nonblocking)，也稱為同步 (Synchronous)和非同步 (Asynchronous)。 等待傳送 (Blocking Send):傳送行程等待著，直到接收行程或信箱接收訊息。 非等待傳送 (Nonblocking Send):傳送行程送出訊息及重新操作。 等待接收 (Blocking Receive):接收者等待，直到有效訊息出現。 非等待接收 (Nonblocking Receive):接收者收到有效訊息或無效資料。

3.4.2.3 緩衝器(Buffering) 不論是直接或間接連繫，經由通訊行程交換的訊息是放在一個暫時的佇列(Temporary Queue)。基本上，有三種製作這種佇列的方式︰ 零容量 (Zero Capacity)︰佇列的最長長度為 0，因此鏈(Link)中將不含有任何等候的訊息。 有限的容量 (Bounded Capacity)︰佇列具有有限長度 n；因此最多有 n 個訊息存於其中。 無限制的容量 (Unbounded Capacity)︰佇列具有無限長度的潛力；因此任何訊息能在佇列中等候，傳送者從不阻塞，而且傳送者也不需等候。