行程與上下文切換 (Processes & Context Switches)

Overview Table

8.2 行程 (Processes) — 抽象的本質 (p.768)

例外 (exceptions) 是 OS kernel 得以提供 process 概念的基本建構元件。行程是計算機科學中最深刻、最成功的想法之一。它給程式三重錯覺:

• 程式好像是系統中唯一正在執行的程式
• 好像獨占 processor 與 memory
• 指令好像一條接一條、不被中斷地執行

經典定義:process 是「執行中程式的一個實例」。每個程式都在某個行程的 context(上下文) 中執行。Context = 程式正確執行所需的狀態,包括:

• 存於記憶體的 code 與 data、stack
• 通用暫存器 (general-purpose registers) 內容、program counter (PC)
• 環境變數 (environment variables)、已開啟的檔案描述子集合 (open file descriptors)

每當使用者在 shell 輸入可執行檔名稱,shell 就建立一個新行程,並在其 context 中執行該可執行檔;應用程式自己也能建立新行程來執行自身或其他程式的程式碼。

行程提供給應用程式的兩個關鍵抽象:

1. 獨立的邏輯控制流 (independent logical control flow) → 獨占 processor 的錯覺
2. 私有位址空間 (private address space) → 獨占記憶體系統的錯覺

8.2.1 邏輯控制流 (Logical Control Flow) (p.768-769)

用除錯器單步執行程式時,觀察到的一連串 PC 值——全部落在自己程式的可執行檔或動態連結的 shared objects 中——這個 PC 值序列就是邏輯控制流 (logical flow)。

時間  Process A    Process B    Process C     ← Figure 8.12
 |       |
 |       |  (A 執行一段, 被 preempt)
 |                    |
 |                    |  (B 執行到結束)
 |                                 |
 |                                 |  (C 執行一段)
 |       |
 |       |  (A 恢復, 執行到結束)
 |                                 |
 v                                 |  (C 執行到結束)
        單一實體控制流被切分成三條邏輯流,彼此交錯 (interleaved)

• Processor 的單一實體控制流被切分為多條邏輯流,每個行程一條
• 各行程輪流 (take turns) 使用 processor:執行一段後被 preempted(暫時懸置),換其他行程執行
• 對行程內的程式而言,唯一能察覺不獨占 CPU 的證據:精確量測會發現 CPU 在某些指令之間週期性停頓 (stall)
• 但每次停頓後恢復執行時,程式的記憶體內容與暫存器完全不變 → 錯覺得以維持

8.2.2 並行流 (Concurrent Flows) (p.769-770)

邏輯流有多種形式:exception handlers、processes、signal handlers、threads、Java processes 都是邏輯流。

並行 (concurrent) 的精確定義:流 X 與 Y 互為 concurrent 若且唯若

X 在 Y 開始之後、Y 結束之前開始;或 Y 在 X 開始之後、X 結束之前開始

亦即兩流的執行在時間上重疊 (overlap in time)。以 Figure 8.12 為例:A 與 B 並行、A 與 C 並行;B 與 C 不並行(B 的最後一條指令在 C 的第一條指令之前執行完)。

8.2.3 私有位址空間 (Private Address Space) (p.770-771)

在 n-bit 位址的機器上,address space 是 $2^n$ 個可能位址的集合:$0,1,\dots ,2^n-1$。行程給每個程式自己私有的位址空間——「私有」意指空間中某位址對應的記憶體位元組,一般而言不能被其他行程讀寫。

各行程位址空間內容不同,但組織結構相同。x86-64 Linux 行程的位址空間佈局(Figure 8.13):

 2^48-1 ┌────────────────────────────────┐
        │   Kernel virtual memory        │ ← user code 不可見
        │   (code, data, heap, stack)    │   (memory invisible to user code)
        ├────────────────────────────────┤
        │   User stack                   │ ← %rsp (stack pointer)
        │   (run time 時建立, 向下長)     │
        ├──────────── ↓ ─────────────────┤
        │                                │
        ├──────────── ─ ─────────────────┤
        │   Memory-mapped region         │
        │   for shared libraries         │
        ├──────────── ─ ─────────────────┤
        │                                │
        ├──────────── ↑ ─────────────────┤ ← brk
        │   Run-time heap                │
        │   (由 malloc 建立, 向上長)      │
        ├────────────────────────────────┤
        │   Read/write segment           │ ┐
        │   (.data, .bss)                │ │ 從可執行檔
        ├────────────────────────────────┤ │ 載入
        │   Read-only code segment       │ │ (loaded from the
        │   (.init, .text, .rodata)      │ ┘  executable file)
0x400000├────────────────────────────────┤
        │          (未使用)               │
      0 └────────────────────────────────┘

• 下半部保留給 user program:code、data、heap、stack 四段;code segment 固定始於 0x400000
• 上半部保留給 kernel(OS 常駐記憶體的部分):kernel 代表行程執行指令時(如 system call)所用的 code、data、stack

8.2.4 使用者模式與核心模式 (User and Kernel Modes) (p.770-772)

要讓 process 抽象「密不透風 (airtight)」,processor 必須提供機制限制應用程式可執行的指令與可存取的位址空間範圍。實作方式:某個控制暫存器中的 mode bit。

User mode 被禁止的特權操作例:halt processor、改變 mode bit、發起 I/O 操作。User 程式必須改經 system call interface 間接存取 kernel 的 code 與 data。

模式轉換的唯一途徑是例外 (exception):

        user mode                          kernel mode
   ┌─────────────────┐   interrupt/fault/  ┌─────────────────┐
   │ application code│──trapping syscall──▶│ exception       │
   │ (初始即為 user)  │                     │ handler 執行     │
   │                 │◀───handler return───│ (in kernel mode)│
   └─────────────────┘   (改回 user mode)   └─────────────────┘

• 行程執行應用程式碼時一開始就在 user mode
• 發生例外(interrupt、fault、trapping system call)→ 控制轉入 exception handler 時,processor 把模式改為 kernel mode;handler 在 kernel mode 執行
• handler 返回應用程式碼時,processor 把模式改回 user mode
• 應用程式沒有任何辦法主動設定 mode bit(那本身就是特權指令)

/proc 檔案系統 (p.771-772):Linux 的巧妙機制,把許多 kernel 資料結構的內容匯出成一個文字檔階層,讓 user mode 行程可以讀取。例:

• /proc/cpuinfo → CPU 型別等一般系統屬性
• /proc/<process-id>/maps → 特定行程使用的記憶體段
• Linux 2.6 起新增 /sys 檔案系統,匯出關於系統匯流排 (buses) 與裝置的額外低階資訊

8.2.5 上下文切換 (Context Switches) (p.772-773)

OS kernel 用一種較高階的 ECF 形式——context switch——實作 multitasking;它建立在 08-Exceptional-Control-Flow/01-Exceptions 所述的低階例外機制之上。

Context(上下文):kernel 為每個行程維護的、重啟一個被 preempt 的行程所需的狀態,包含:

• 通用暫存器、浮點暫存器、program counter
• user's stack、status registers、kernel's stack
• kernel 資料結構:page table(刻畫位址空間)、process table(當前行程資訊)、file table(已開啟檔案資訊)

Scheduling(排程):kernel 在行程執行的某些時點,可決定 preempt 當前行程、重啟先前被 preempt 的行程;此決策由 kernel 中的 scheduler 程式碼處理。kernel 選定新行程 = 「scheduled 該行程」。之後以 context switch 機制轉移控制:

Context switch 三步驟:
  (1) 保存 (save)    當前行程的 context
  (2) 還原 (restore) 某個先前被 preempt 行程已保存的 context
  (3) 轉移 (pass)    控制權給這個新還原的行程

觸發時機(兩大類):

Figure 8.14 — context switch 的剖析(process A 執行 read):

時間          Process A                Process B
 |    ── user code (A) ──────
 |          read (trap)
 |    ── kernel code ────────┐  trap handler 發起磁碟 DMA、  ┐
 |                           │  設定磁碟完成後發 interrupt    │ context
 |                           └──────▶ ── user code (B) ──   ┘ switch
 |                                         |
 |    disk interrupt (資料已到記憶體)        |
 |                            ┌── kernel code ──────────    ┐ context
 |    ◀───────────────────────┘  (B 跑夠久了, 切回 A)        ┘ switch
 |    ── user code (A) ──────
 v      從 read 返回, 繼續執行 read 之後的下一條指令

流程細節 (p.772-773):

1. A 在 user mode 執行,呼叫 read trap 進 kernel;trap handler 向磁碟控制器請求 DMA 傳輸,並安排磁碟在傳輸完成後中斷 processor
2. 磁碟取資料需時很久(數十毫秒等級),kernel 不空等,執行 A→B 的 context switch
3. 切換前,kernel 是在 user mode 代表 A 執行;切換前半段,kernel 在 kernel mode 代表 A 執行;某個時點起改為(仍在 kernel mode)代表 B 執行;切換完成後,在 user mode 代表 B 執行
4. B 在 user mode 執行一段時間,直到磁碟發出 interrupt(資料已從磁碟送達記憶體);kernel 判定 B 跑夠久了,執行 B→A 的 context switch,把 A 的控制權還到 read 之後的那一條指令,A 繼續執行直到下一個例外

Exam/Test Patterns

Related Notes

• 08-Exceptional-Control-Flow/01-Exceptions — context switch 建立於其上的低階例外機制(interrupt/trap/fault/abort)
• 08-Exceptional-Control-Flow/03-Unix-Error-Handling — 緊接本節的 system call 錯誤處理(errno、strerror)
• 08-Exceptional-Control-Flow/04-Process-Control — fork/execve/waitpid 等操作行程的系統呼叫
• 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching — 私有位址空間背後的虛擬記憶體機制
• 09-Virtual-Memory/02-VM-Management-and-Protection — page table 如何實作位址空間的私有性與保護
• 12-Concurrent-Programming/01-Process-and-Event-Based-Concurrency — 以行程實作並行伺服器
• 01-Computer-Systems-Tour/03-OS-Abstractions-and-Networks — 第 1 章對 process/context switch 的初次概覽