首頁

# Process Concept

# Program vs Process vs Threads

  • Program (Passive entity)
    被動、儲存於 disk 中等待被執行的程式碼
  • Process (Active entity)
    主動、正在記憶體裡面執行的程式。包含：
    • Code Segment (text section)
    • Data Section (global variables)
    • Stack (暫時的 local variables 和 functions)
    • Heap (動態分配的 variables 或 classes)
    • Current Activity (program counter、register contents)
    • 其他相關的資源 (OS resources, e.g. open file handlers)
  • Threads
    • lightweight process
      • 跟 Process 長的一樣，有些 Threads 可以共用 Memory 空間
      • 以 CPU 來說 thread 是執行的最基本單位
    • 同一個 Process 底下的 Threads 共用
      • Code Section
      • Data Section
      • OS resources
    • 每個 Thread 有自己的
      • Thread ID
      • Program Counter
      • Register Set
      • Stack

    因此，在寫 Multi-Thread 的時候可以用 Global Variables (Data Section) 來做溝通

# Process States

  • New：行程新產生
    • Program 載入到 Memory，並初始化記憶體狀態 (Code Section、Data Section…)
    • 決定要分配多少給 Process
  • Ready：排班中，等待 CPU
    • 有一個 Queue 管理這些 Process
    • 等待被執行的階段會被放到佇列當中等 CPU 排程
  • Running：在 Ready 中被選到執行的 Process
    • 有時候會直接回到 Ready State，一段時間 (timer) 就會 interrupt (hardware signal)
  • Waiting：等待某事發生，例如等待使用者輸入完成。亦稱 「阻塞」（blocked）
    • 在做 IO 的時候不需要 CPU 參與，等到完成後會回到 Ready state
    • 也有一個 Queue 來儲存
  • Terminated：完成執行
    • 釋放所有分配給這 Process 的資源

# Process Control Block（PCB）

定義：OS 要管理每個 Process，會在 kernel memory 中替每個 process 各自準備一個 block 紀錄 process 之所有相關的資訊

  • PCB 中的 pointer 是 process 串聯 queue 的，該個 pointer 會指到下個 process 的 PCB
  • 把 Process 放進 Queue 其實是個抽象的概念，實際上是放進 PCB
  • PCB 裡面包含
    • Process No. (ID)：是唯一的
    • Process State：有 「ready」、「running」、「wait」…
    • Program Counter（PC）
    • CPU Registers：accumulator, psw, stack top…
    • CPU Scheduling Information：優先權值、process arrival time (FIFO)
    • Memory-Management Information：隨作業系統記憶體管理方式不同記錄不同的資訊
      如：Base/limit register, page table 或 segememt table
    • I/O Status Information：Process 已發出多少 I/O-request？完成狀態如何？目前占用哪些 I/O 資源？
    • Accounting Information：Process 已使用多少 CPU time？還剩多少資源？系統管理員依據此資訊用以調校效能

# Context Switch

  • 藉由 Interrupt，把原來的 Process 替換成另一個 Process
    • 會把舊 Process 的資料存到 PCB 裡，把新 Process 的資料 Load 到 PCB 裡
  • Context Switch Time
    • 為 Overhead
    • 這期間兩個 Process 都在 Idle，為了 Time-Sharing 這是無法避免的
    • 基於
      • Memory Speed
      • Register 數量
      • 用特殊的 Instruction，像是某個 Instruction 可以一次 Load 所有 Register
    • Hardware Support：CPU 包含很多 Sets of Registers，一次去記很多程式的 狀態，在 Context Switch 得時候就不用寫到 Memory
    • 根據硬體資源和指令而做調整

# Process Scheduling

# Process Scheduling Queues

process 在不同的 queue 做切換（在 state 的切換）

  • Job queue（New state） – set of all processes in the system
  • Ready queue（Ready State） – set of all processes 在主記憶體等待執行
  • Device queue（Wait State） – set of processes 等待 I/O

# Schedulers

  • Long-term scheduler / Job scheduler [new → ready]
    • 從 job queue 中挑選合適的 jobs，並將之載入到記憶體內準備執行
    • 通常適用於 Batch System (大型機房)，但不適用於 Time-Sharing System
    • 可調控 Multiprogramming Degree
    • 可調合 CPU-Bound 與 I/O Bound processes 之混合比例
    • 執行頻率最低
  • Short-term scheduler [ready → running]
    • 從 Ready Queue 挑選高優先度的 Process，使之獲得 CPU 控制權執行
    • Batch System 和 Time-Sharing 均需要
    • 執行頻率最高
  • Medium-term scheduler [running → ready/wait]
    • 當記憶體空間不足，且又有其它 Process 欲進入記憶體執行，此時該 Scheduler 必須
      • 挑選某些 Process Swap Out 到磁碟中以空出記憶體空間
      • 待記憶體有足夠空間再將其 swap in 記憶體中繼續執行
    • 通常用在 Time Sharing System。
    • 減少 Multiprogramming Degree
    • 可調合 I/O Bound 與 CPU Bound 的比例

# Operations on Processes

# Tree of Processes


parent process 會建立 children processes，children processes 又可以成為 parent processes 建立其他 processes 而形成樹狀結構
Each process has a unique PID, Some special PIDs :

  • 0 : scheduler
  • 1 : init
  • 2 : pageout

# Process Creation

  • 工作類型：與父行程相同、不同
  • 資源分享的模式（父行程對子行程）：全部分享、部分分享、全部不分享
  • 執行方式：同時執行、等 child 終止才執行
  • 位址空間
    • Child 為 Parent 的複製
      • 與 Parent 相同：執行碼、counter
      • 與 Parent 不同：memory address
      • 透過 sharing variable 溝通
    • 將特定的 program 丟進 Child 的 code section 並重設 counter，讓 Child 變成完全不同狀態的 Process，透過 message passing 溝通

# UNIX/Linux Process Creation

Process 操作有關的 system calls：

  • fork ()： 用以建立 child process
    child process 與 parent 占用不同的記憶體，但最初 child 的 code section、data section 內容均自 parent copy
  • exit ()：用以終止 process
    • 釋放 process 所佔用的資源
    • 傳回結束狀態 (exit status) 給 parent process
  • exec ()：用以載入特定的 Binary code file 讓 process 執行，即 process 之 code section 為此 Binary code content
    • exec 有多種變體 (execl, execp, execv, etc.)，用來處理不同的參數傳遞方式
    • exec 不會產生新的行程，而是取代目前的行程
  • wait ()：父行程等待子行程結束
    • wait 會阻塞父行程，直到有一個子行程結束
    • wait 可以取得子行程的結束狀態 (exit status)

# Process Termination

  • 當最後一行指令結束或是 exit() ，所有的資源會被 deallocated by the OS
  • 父行程中斷（abort）子行程用 pid
    可能原因：子行程超用資源、被配給子行程的工作不被需要
  • 連帶終止，父行程結束子行程不能繼續執行

# Interprocess Communication（IPC）

# Independent process vs. Cooperating process

  • Independent process：不能（被）影響的行程
  • Cooperating process：能被影響且影響其他行程，且能與其他行程共用資料

# Communication Methods

# Shared memory

  • 介紹：兩個 Process 共享同一塊 memory，這樣他們就可以利用這塊 memory 溝通（也是需要透過 system call 先跟 OS 講
  • 需要仔細注意使用者的同步化
  • 優點：memory addr. access data，速度較快，因為不需要複製資料
  • 缺點：
    • Synchronization：需要額外的機制來確保兩個 Process 不會同時修改共享記憶體，導致資料不一致
    • Protection：需要確保只有授權的 Process 能存取共享記憶體，避免未授權存取

    Consumer & Producer Problem
    Sol.：允許至多 B-1 個資料在 array，否則無法決定 buffer 是空或是滿的

# Message passing

  • 介紹：簡單來講就是 memory copy，但不是直接複製過去的而是先到 kernel 繞了一圈
    例如說 Process A 要傳東西給 Process B
    1. Process A 把 message 複製到 kernel (OS 的 memory)
    2. Process B 從 kernel 複製 message 到自己的 memory
    3. Process B 讀取 message
  • 需要建一個 communication link，藉由 Send/Receive 交換資訊
  • 考量：
    • Protection：如果直接複製會越界，因此需要透過 system call 來處理
    • Synchronization：需要確保 Process B 在讀取 message 時，Process A 已經完成寫入
    • Efficiency：複製資料會有額外的時間和資源消耗
    • Reliability：透過 OS 進行傳輸，可以增加錯誤檢測和恢復的機制
  • 優點：不會有衝突，對於小資料有效率
  • 缺點：用 system call 實作，速度較慢

# communication link 的實作

  • physical：shared memory, HW bus, or network
  • logical：Direct or indirect communication、Blocking or non-blocking
    • Direct vs Indirect communication
      • Direct communication
        1. 明確講出對方名稱
        2. Send (P, message)、Receive (Q, message)
        3. Link 會自動建立，且一對一
      • Indirect communication
        1. 透過 mailbox (port) 溝通而不是直接寄到別人手上
        2. Send (A, message)、Receive (A, message)
        3. Link 不會自動建立，可以一對多或多對多
    • Synchronization
      • Blocking (synchronous) ：等到 func 全部執行完才 return
        • Send: sender 等到 message 被收到才繼續
        • Receive: receiver 等到 message 到才繼續
      • Non-blocking (asynchronous)：只會知道有做這件事但不會等到他完成之後才 return
        • Send: sender 發送完就繼續
        • Receive: receiver 若無 message 就繼續
    • Buffer
      • Zero-capacity link：send/receive 都是 blocking
      • Bounded-capacity link：有限 buffer，滿的話 sender 會被 block 住
      • Unbounded-capacity link：sender 永不會被 block 住
    • 收送同步化問題解決方法
      • link 的連結至多兩個 process
      • 一個時間內只允許一個 process 執行 receive 的動作
      • 系統隨意選單一個 receiver，sender 被通知是誰拿到

# Sockets

  • 透過 IP & Port 來 identify 使用者（port number 指 process）
  • 藉由 unstructured stream of bytes 來溝通 (low level)(傳訊息)
  • data 的 parsing 是依據 client/server application

# Remote Procedure Calls

  • 跨電腦 rpc，call function
  • 允許 client 呼叫 server 的 procedure
  • Stubs – client-side proxy for the actual procedure on the server

# Ref Notes

  • Kipper’s Note
  • Chang-Chia-Chi’s Note
  • 陳品媛的筆記
  • Mr. Opengate. OS - Ch4
  • ZYuC’s Note
  • WillyWangkaa’s Note
  • Mes’s Note