D-OS-Ch06b-Critical_Section_Problem

Critical-Section Problem

Introduction

Critical section 是會 access 或 update shared data 的程式區段。若一個 process 正在執行 critical section，其他會碰同一份 shared data 的 process 不應同時進入。

Critical-section problem 要設計一個 protocol，避免 race condition。

while (true) {
    entry section
    critical section
    exit section
    remainder section
}

• entry section：進入前取得許可
• critical section：操作 shared data
• exit section：離開後釋放許可
• remainder section：不需同步的部分

Requirements

Mutual Exclusion

若 $P_i$ 在 critical section，其他 process 不能同時在 critical section。

Progress

若沒有人在 critical section，且有人想進入，系統必須在有限時間內選出下一個進入者；不想進入的人不能阻擋決策。

Bounded Waiting

Process 提出 request 後，其他 process 插隊進入 critical section 的次數必須有上限，避免 starvation。

Kernel Critical Section

Kernel 也有 shared data structure，例如 process list、open file list、memory allocation metadata。

Nonpreemptive kernel 在 kernel mode 不會被 preempt，較不容易有 kernel race condition；preemptive kernel responsiveness 較好，也較適合 real-time，但在 SMP 上同步設計更難。