--- # System prepended metadata title: OS-Chap3 - Process_行程 tags: [作業系統 Operating System note, 110-1, '2021'] --- # OS-Chap3 - Process_行程 ###### tags: `作業系統 Operating System note`, `110-1`, `2021` ###### 參考資料 : [行程間的溝通](http://debussy.im.nuu.edu.tw/sjchen/OS/97Spring/Ch_7.pdf), [作業系統筆記](https://chentsungyu.github.io/2020/03/21/OS/%5BOS%5D%20%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E7%AD%86%E8%A8%98-Process/), [作業系統-Process](https://www.namepluto.com/%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-process/), [作業系統簡介(下)](http://enews.open2u.com.tw/~noupd/book_up/1746/8719.htm) # Contents [TOC] --- # Process Concept ## Process v.s. Program - Process = 行程。**正在執行中的程式。** - 主動。 - **一個 program** 在 **memory(記憶體)** 中執行。 - 帶有 program counter，用來指出下一個指令的位置。 - Program = 程式 - 被動。 - 以 binary 的方式儲存在 disk (硬碟)中。 :star2: **一個 program，可以是多個 processes** :star: ∵ 多個使用者再執行同個 program >>>>>>>>>>>>>>>>>>>>>>>>> ----- ## 一個 Process 包含的東西 ![](https://i.imgur.com/vkssW0B.png) - Code Segment(=Text Section) - 程式碼、PC、暫存器…。 - Data Section(資料區間) - 全域變數(Global Variables) > - uninitialize : BSS > - initialize : - Stack - 暫時性資料 - 方便使用後直接 pop 掉(結束) - ex. 區域變數(Local Variables) - ex. 函式的參數(Function parameters) - Heap - 動態配置記憶體(變數/類別class) - Current Activity - Program Counter(計數器) : 存放下個被執行 program 的 address - Processor register : 就是處理器的暫存器 ## Five state of Process ### Process STD → 行程狀態圖 >- Process State Transition Diagram - 描述 **Process 由開始到結束的生命週期 (Life-Cycle)**，而一個Process在此週期中會經歷數種狀態。 ![](https://i.imgur.com/MzJbwoC.png) - ### Transition : 1. new → ready - admitted : 引入/產生一個新的 program 到電腦執行。 > - OS 在此時會確認有沒有足夠的資源去 create process，也會檢查權限(Protection)，成功的話進入 Ready 2. ready → running - schedular dispatch : 從 memory 挑選一個 process 到 CPU 執行。 3. running → terminate :white_check_mark: - exit : process 完成他的 task/ job，就結束。 4. running → ready :heavy_check_mark: - 發生**短暫中止**時。 - interrupt/ 被高 priority process 插隊/ CPU Time Quantum 超過。 5. running → waiting (block) :white_check_mark: - 發生**較長時間的中止**時。 - wait for resource available - wait for I/O or event completion 6. waiting → ready :heavy_check_mark: - I/O or event completion :white_check_mark: 為 process **主動**放棄執行權 **non-preemptive** :heavy_check_mark: 為 process 被動放棄執行權 preemptive :exclamation: 若一個系統只有 process **主動** 放棄執行權，並重新進行排程時，此系統為 **non-preemptive** ，反之則稱為 preemptive :exclamation: > ref to chap 5 scheduling - ### State - new：產生新的 Process - 準備要將 Program load 到 memory，initial 各個 section - ready： - Process 競爭 CPU，在 queue 裡面等著被 OS schedule 後，被分配至CPU執行。 - 當 I/O 事件結束 or 執行期間(running)被Interrupt ， Process 都會回到ready狀態 - running：執行中的 Process - wating：當有其他事件(Event)發生時，(ex.週邊設備的I/O)，會進入暫時等待的狀態。 :heavy_exclamation_mark:Process此時雖然還在記憶體中，但不在Ready Queue - terminated：Process執行結束 - ### Queue > - 同下方 scheduling queue - Job Queue : 系統中的所有的 Process 形成的隊伍(list) - Ready Queue : 放在記憶體中多個 Process 形成的隊伍(list)，準備隨時可以被分配至 CPU 內執行(running) :heavy_check_mark: 同個時間，一次只可以有一個 process 在 running 中執行:heavy_check_mark: :heavy_check_mark: 同個時間，可以有多個 processes 在 ready 和 waiting 中執行:heavy_check_mark: #### 此 STD 是針對 CPU 這項資源，且 data 都在 Memory中。 ## Process management - ### PCB(Process Control Block)行程控制表 > = TCB(Task Control Block) - 存在 memory 中。 - 每個 process 都有各自的一個 PCB。 - **用來記錄該 process 在被 context switch 前的資訊。** ## PCB 包含以下資訊 ![](https://i.imgur.com/MDjLQGK.png) - Pointer : 連接下一個 PCB (?) - Process State (行程的狀態) - process 在哪一個狀態 - ex. ready, waiting, running - Process number = Process ID (Process identify) - Process counter - 指明該 process 下一個要執行的指令 address。 - 在尚未要被 context switch 前，只會存和 PCB 頭的相對位置。 - 當準備被 context switch 前，會將 PCB head 的位置加上目前的相對位置，再存回此。 - CPU register - CPU scheduling information - priorities : Process 的優先順序 - memory manegement - memory limit - 0x00~0xC0000000 : memory (可連接至上方 : Process 包含的東西/Current Activity/Process register 的圖片) - accounting infor. - 用掉多少 CPU 的時間 - 使用 CPU 的最大時間量 - I/O status infor.(list of open file) - 尚未完成的I/O Request還有哪些 - 還在 I/O Queue中排隊之Process的編號 #### :heavy_exclamation_mark: OS 為了管理Process 方便，會存一份 PCB 在 OS 所在之 Monitor Area 中。:heavy_exclamation_mark: ## Context Switch - 轉換 CPU 至另一個 process 時(p0→1)，必須將舊 process 的狀態存起來(存入PCB0)，再載入新 process (從PCB1)的 data 至 CPU - Context Switch 所花費的時間對系統而言是 **額外的浪費 (overhead)**。 - 因為在 switch 的過程中，系統所做的事是不具有生産力的工作。 - Context Switch 的速度 - 主要取決於 **硬體 (hardware)** 支援的程度。 >- #### Solution to decrease context switch burder > 1. 提供多套 Register Sets > - 毎個Process皆可有自已的Register Set (若Register數量夠多) > - 當需要做Context Switching時，**OS只要切換 Register Set 的指標**到新Process即可 > - 速度快(不會用到 memory 存取)、但不適用 register 數量少的系統 > ![](https://i.imgur.com/z6eLbf9.png) > 2. 用 thread 代替 process > - 毎個 Process 都有自己的 PDB(私有)，這些私有資訊會佔用 register。 > - **Threads之間彼此可以共享Memory Space** (ex. Code Section, Data Section, Open File) > - ∴ Context Switch 時**不須大量的 Memory Access** > 3. register 有限時 > - 當Register有限時，視哪一種類的Process切換較頻繁。 > - System Processes 與 User Processes 都有自已的Register Set > ∴當 User Process 與 System Process 之間 Context Switch 時，**OS只要改變Register Set的 pointer 即可**。 > ![](https://i.imgur.com/ipZg9L1.png) # Threads(線程) --- # Process Scheduling - Multiprogramming : CPU一直在running，達到最大效能 - Time sharing : 一直切換 CPU 執行的process，讓使用者覺得在互動 - processes 必須等到 CPU free 才能被重新排程 ## Scheduling Queue - process 在不同的 queue 做切換（在state的切換） - Job Queue（New state） - 在 disk 等待被抓入 ready 的所有行程 - Ready Queue（Ready State） - 在 memory 等待抓進去 running 的行程集合(process set) - Device Queue（Wait State） - 等待 I/O device 的行程集合(process set) ![](https://i.imgur.com/rUnJiDm.png) # Process Scheduling (行程的排程)--大排程 > 為了讓 CPU 發揮最大的效益，需 process scheduler 決定分配哪個 process 能使用CPU___猜。 ![](https://i.imgur.com/0izhrxL.png) ## Long-Term Scheduler - 亦稱 Job Scheduler - 從 job queue 挑選合適的 process ，能從 disk(磁碟) 排進 memory。(以控制 memory 內 process 的數量) ⇨ Control Multiprogramming Degree __(視CPU或Mem.的使用率高低而定) - 從 disk(磁碟) load 進 memory 的時間，相較於 memory 之間傳遞資料(Short-Term Scheduler) 所花費的時間長。 - ### disk → memory > - 執行頻率最低 > - 通常適用於Batch System，但不適用於Time-Sharing及Real-Time System。 > - 可調合CPU-Bound與I/O Bound之混合比例 (∵可視資源負荷決定載入Job與否)。 > UNIX/NT 沒有此 scheduler ## Short-Term Scheduler - 亦稱 CPU Scheduler - **Ready → Running** - 決定 memory 中的哪個 process 能排進 CPU running - 只作 memory 進入 CPU 的決定，花費的時間極短 - ### memory → CPU (?) > - 執行頻率最高 > - ∵毎個Process執行時狀況很多，如：不同情況的中斷…等。 > - 各種系統均需要 (Batch System, Time-Sharing, Real-Time System) > - ∵毎種系統都有CPU嘛。 > - 無法調整 Multiprogramming Degree 及 I/O Bound 與CPU Bound Job 之混合比例 ## Medium-Term Scheduler - **Virtual Memory** ???? - 保留long-term scheduler功能 - 採Swap(交換)的形式，將放在 memory(Ready Queue) 中的 Process 搬回 Disk(Job Queue) - Swapping - swap out : 從 memory 移除 process - swap in : 被 swap out 的process 再放回 memory - 目的 : 當記憶體內的行程太多，導致電腦的效能變差時，要將一些行程從 memory 移出，以減少行程搶用系統的 CPU ，以降低 multiprogramming process 的數量 (degree)。 - ### disk ↔ memory > - 執行頻率介於Long-Term與Short-Term之間 > - 用於 Time-Sharing System (Real Time, Batch不用) > - 可調控 Multiprogramming Degree > - 可調合I/O Bound與CPU Bound的比例 (當Long-Term Scheduler有誤判之時!! --- # Operation of Processes(Processes 的操作) ## Creation - parent process 創建 children processes(單個/多個)，形成 process tree。 - child process 和 parent process 的差異 - 每個 process 有 unique id - 第一個關聯性，child process 建立之後，所需的 resources 由誰提供： - share all : parent 和 child 可以看到一模一樣的 content - subset : 行程配部份資源給子行程 - ex. global variable 看得到，動態 variable 看不到 - shared none : 父子行程無共享資源 - 兩個看到的東西完全不一樣 :heavy_check_mark: resource 不是 parent process 提供，就是 OS 提供 - 第二個關聯性，Parent 生出 child proces 後，兩者的互動模式： 1. execute concurrently : 父子同時執行 process - 交給 OS Scheduling 決定 2. parent 等到 child 執行完(terminate) - = parent process 做了 fork 之後，就會進到 waiting queue 裡面 - 第三個關聯性，child process 的工作項目： - Old implementation : child 完全 copy parent( = duplicate) - Current implementation : Copy-on-write 的方式去儲存 ，run time,，修改值的時候再做分家 ### 相關的 system call - fork() - Memory space of fork() > - parent process 和 child process 有各自獨立的 memory space > ref. [fork()](https://burweisnote.blogspot.com/2017/09/fork.html) - execlp() - Load a new binary file into memory ，舊的 code 丟了 - ex. 在 web download 其他 file(ex.ppt, pdf ...)，下載完成後要開啟時，會連到其他file 做開啟的動作。(開啟後就不甘 web 的事 = 不甘 parent process 的事) - wait() - 通常是 concurrently 執行，所以可以透過 waiting 調整 - parents 會等待其中一個 child processes 執行完成 #### fork()、execlp() memory space 的 Example ![](https://i.imgur.com/EZwNu1i.png) ## Termination ### 相關的 system call - exit() - abort() - wait() # Important!!! ## Orphan(孤兒) && Zombie(殭屍) - parent 死了(terminate)，child 會變 orphan(孤兒)！ - parent 睡了(sleep)，child 事情做完會變 zombie(殭屍)！ --- # IPC(Inter-Process Communication) - 分為 independent 和 cooperating > - indepensent > - 不受其他 processes 的影響，或無法影響其他 processes 的執行。 > - 獨立的Process之間不會有任何共享資料。 > > - cooperating > - 會受到其他 processes 的影響，或影響其他 processes 的執行。 > - 故 Process 之間會有共享的資料，需要有進行資訊交換的管道。 > - processes 之間合作的理由 > 1. infor. sharing > 2. speedup computation > 3. Modularity > 以模組化的方式建構 system ，讓 system 分配它的功能到各個 processes。 > 4. Convenience > ex. 單一使用者同時做編輯、列印、編譯。 ## Model(常見作法) ![](https://i.imgur.com/MMmjFBo.png) ### Message passing - Process 間使用 kernel 中的 shared memory 產生連接通道(communication link#→message queue)溝通。 > (非藉助共享變數 shared variables) - 做 communication 的過程如下 → OS提供的東西 1. 建立 communication link → 會有 communication link 存在 processes 之間 2. 傳遞/交換信息(message) → send/receive messge 3. 傳輸完畢 → release link - :heavy_exclamation_mark: **若傳遞少 data 較沒效率** >#### 實作 Communication Link 的方式 >- Physical: - Shared memory - Hardware bus - Network >- Logical: - Direct or indirect - Synchronous or asynchronous - Automatic or explicit buffering #### 通訊(Communication)的方式 - #### direct (直接傳訊息) ![](https://i.imgur.com/3yRzEK6.png) - #### indirect (間接傳遞) ![](https://i.imgur.com/E03jZRO.png) | Direct | Indirect | |:---------------------------------------------------:|:--------------------------------------------------:| | 建立 link 用 send/receive 傳送訊息 | 訊息從 mailbox 裡直接接收(**只能共享mailbox**資料) | | 為自動建立 (established automatically) | 每個mailbox都有個獨特的ID(unique id) | | 一個Link剛好連接一對Process(One-to-One) | 一對process之間，可能存在多條Link | | 每個行程必須要明確地命名 | 要建立連結，只能是行程共享郵箱 | | Link 可以是 unidirectional，但通常是 bi-directional | Link 可能是 unidirectional 或 bi-directional | - 間接傳遞(indirect)的過程中，通訊的同步非常重要，分作兩種形式： - blocking - Blocking send：訊息傳遞出去，Process被Block阻擋，直到對方訊息收到才可再傳送。 - Blocking receive：不做任何動作，直到訊息送來，再回傳收到的資訊。 - non-blocking - Non-blocking send：不管對方有無收到訊息，持續發送訊息給對方。 - Non-blocking receive：接收者只接收有效訊息，或是沒有訊息。 ### Shared Memory - process 之間利用 shared memory 交換資訊、彼此溝通。(**非使用 kernel提供的 space**) - 使用記憶體位置(memory address)來存取 data - 利用 read/write 資料來完成資訊交換 - :heavy_exclamation_mark: OS只提供 shared memory space，行程間的 **sychronization** 則需要由 programmer(user) 負責，OS不提供額外的資源。 #### → producer會把資料放進buffer內(write) #### → consumer會去同一個buffer把資料取出來(read) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> --- | | Share Memory | Message Passing | | -------- |:----------------------------------------:| ---------------------------------------------------- | | 溝通方式 | 共享一部分的記憶體(透過共享變數存取資料) | Process 之間建立 Communication Link | | 共享性 | 共享變數所有 process 皆可存取 | process 間有專屬的 Link，不會隨意被其他 Process 共用 | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> --- ## Producer-Consumer Problem