Try   HackMD

參考資料


  • Cooperating process 合作流程
    • Affect or be affected by other processes executing in the system
      (影響系統中執行的其他進程或受其影響)
    • Cooperating processes can either
      • directly share a logical address space
      • be allowed to share data only through shared memory
      • message passing
  • Concurrent access to shared data may result in data inconsistency
    (並發存取共享資料可能會導致資料不一致)

Background

  • Producer-consumer problem
    • Solution
      • Producer process
        ​​​​​​while (true) {
        ​​​​​​    /* produce an item in next_produced */
        
        ​​​​​​    while (count == BUFFER_SIZE)  // buffer 滿了,等到有空間為止
        ​​​​​​        ; /* do nothing */
        
        ​​​​​​    buffer[in] = next_produced;
        ​​​​​​    in = (in + 1) % BUFFER_SIZE;
        ​​​​​​    count++;
        ​​​​​​}
        
      • Consumer process
        ​​​​​​while (true) {
        ​​​​​​    while (count == 0)
        ​​​​​​        ; /* do nothing */
        
        ​​​​​​    next_consumed = buffer[out];
        ​​​​​​    out = (out + 1) % BUFFER_SIZE;
        ​​​​​​    count--;
        
        ​​​​​​    /* consume the item in next_consumed */
        ​​​​​​}
        
  • This solution are correct separately, they may not function correctly when executed concurrently
  • A shared variable
    • Counter (counter is in memory)
      • Counter++
        ​​​​​​register1 = counter
        ​​​​​​register1 = register1 + 1
        ​​​​​​counter = register1
        
      • Counter--
        ​​​​​​register2 = counter
        ​​​​​​register2 = register2 - 1
        ​​​​​​counter = register2
        
  • Assume the initial value of the counter is 5
    • T0: producer execute register1 = counter {register1 = 5}
    • T1: producer execute register1 = register1 + 1 {register1 = 6}
    • T2: consumer execute register2 = counter {register2 = 5}
    • T3: consumer execute register2 = register2 - 1 {register2 = 4}
    • T4: producer execute counter = register1 {counter = 6}
    • T5: consumer execute counter = register2 {counter = 4}
  • Race condition
    • Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place
    • 當多個 processes 同時存取及操作 share data 時,最終的值取決於最後一個完成執行的 process (最後一個 instruction),這個現象稱為 race condition
    • 通常將可能產生 race condition 的區域稱作 critical section
    • 多個 process 共享同個資源 & Context Switch
    • 因為 process 的執行順序不同,而造成結果不同
  • Process synchronization and coordination among cooperating processes

The Critical Section Problem

  • Critical section(簡稱 CS)
  • The critical section problem
    • Design a protocol that the processes can use
      ​​​​while (True) {
      ​​​​    entry section
      ​​​​        critical section
      ​​​​    exit section
      ​​​​        remainder section
      ​​​​}
      
    • Entry section
      • 進入 critical section 時, 要先問能不能進入
    • Critical section
      • 會用到共同 buffer 的地方
    • Exit section
      • 離開 critical section
    • Remainder section
      • 剩下的程式碼
  • A solution to the critical section problem must satisfy three requirements
    • Mutual exclusion 相互排斥
      • 避免兩個 process 拿到同一個 pid。
      • 當一個 process 在執行他的 critical section 時,其他 process 都無法進入自己的 critical section
    • Progress
      • 如果沒有 process 在執行 critical section, 且有 process 想要執行 critical section, 則必須讓此 process 去執行 critical section
    • Bounded waiting
      • 限制等待次數,避免無止盡的等待。
      • 不會永遠都是同一個 process 在執行他的 critical section 也可以說一個 process 不會被無限插隊
        Image Not Showing Possible Reasons
        • The image was uploaded to a note which you don't have access to
        • The note which the image was originally uploaded to has been deleted
        Learn More →
  • Two general approaches are used to handle critical sections in OS
    • Preemptive kernels
      • 能有效率地換 process,執行起來會更好
    • Non-preemptive kernels
      • 一個一個跑,不會互相起衝突

Peterson's Solution

  • Peterson’s solution is restricted to two processes that alternate execution between their critical section and remainder section
    (僅限兩個 processes 的時候)

    The structure of process

    Pi in Peterson's solution:

    ​​while (true) {
    ​​    // entry section
    ​​    flag[i] = true;  // 代表我想進入 critical section
    ​​    turn = j;   // 但我把執行權讓給 j
    ​​    
    ​​    // 如果 j 也想執行 -> j 執行 critical section
    ​​    // 如果 j 不想執行 -> i 執行 critical section
    ​​    while (flag[j] && turn == j);
    
    ​​    critical_section();
    ​​    
    ​​    // exit section
    ​​    flag[i] = false;  // 代表我不想進入 critical section 了
    ​​                      // 因為已經執行完了
    ​​  
    ​​    remainder_section();
    ​​}
    
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →
  • The two processes share two variables:
    ​​int turn;   // turn=i,就代表是 i 進入 Critical Section
    ​​boolean flag[2];   // flag 是用來記錄,process 是否「想」進入 Critical Section
    
  • Prove
    • Mutual exclusion: turn 不可能同時為 0 或 1,因此不可能同時進入 critical section
    • Progress
      • 若 P1 尚未準備好 > flag[1] = false > P0 可以進入
      • 若兩者都準備好 > flag[0] = flag[1] = true
        • 若 turn = 0 則 P0 進入,否則 P1 進入
      • 以上兩種狀況,process 都可以順利進入 critical section
    • Bounded-waiting
      • 若 P1 離開 critical section > flag[1] = false > P0 可以進入
      • 若 P1 離開 critical section 後,繼續執行 while loop > flag[1] = true > turn = 0 (覆寫 P0 原先的 turn = 1) > P0 可以進入
      • 以上兩種狀況, P1 進入後接著進去的一定是 P0,符合 bounded waiting 的要求

Hardware Support for Synchronization

考點:哪三個方法及各自的做法(可能是程式碼填空)

  • Three hardware support for synchronization
    • Memory barriers
    • Hardware instruction
    • Atomic variables

Memory Barriers

  • Memory model
    • Strongly ordered
      • 某個 processor 修改了記憶體,其他 processor 能立即看到變更
      • 效率會降低
    • Weakly ordered
      • 某個 processor 修改了記憶體,其他 processor 不一定能立即看到變更
  • Memory barriers (Memory fences)
    • 執行 memory barrier 時,系統會確保在執行任何讀取或寫入前完成之前的讀取或寫入工作。
    • memory barrier 之前的所有 write operation 都要寫入記憶體,memory barrier 之後的 read operation 都可以獲得同步屏障之前的結果。
  • Exmaple: 確保 thread 1 輸出是 100
    • Thread 1
      ​​​​while (!flag)
      ​​​​    memory barrier();
      ​​​​print x;
      
    • Thread 2
      ​​​​x = 100;
      ​​​​    memory barrier();
      ​​​​flag = true;
      

Hardware Instructions

  • Many modern computer systems provide special hardware instructions that allow us either to test and modify the content of a word or swap the contents of two words atomically (one uninterruptable unit)

test_and_set()

The definition of the atomic test_and_set() instruction.

/* return the old value of lock, and set lock to true */
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;

    return rv;
}

Mutual-exclusion implementation with test_and_set().

do {
    while (test_and_set(&lock)) // obtain lock
        ; /* do nothing */

        critical_section();

    lock = false; // release lock

        remainder_section();
} while (true);

compare_and_swap()

The definition of the atomic compare_and_swap() instruction.

/* return the old value of lock, if lock == expected, set lock to new value */
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;

    if (*value == expected)
      *value = new_value;

    return temp;
}

Mutual exclusion with the compare_and_swap() instruction.

while (true) {
    while (compare_and_swap(&lock, 0, 1) != 0)
        ; /* do nothing */

    critical_section();

    lock = 0;

    remainder_section();
}

Bounded-waiting mutual exclusion with compare_and_swap().

while (true) { waiting[i] = true; key = 1; while (waiting[i] && key == 1) key = compare_and_swap(&lock, 0, 1); waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = 0; else waiting[j] = false; /* remainder section */ }
line 2: 表示 i 想進入 critical section,現在在 waiting 等
line 3: set key to 1
line 4: 當我在 waiting 且 key = 1 的時候
line 5: 只有 waiting = false 且 key = 0 的人才可以進入 critical section
    - 如果 lock = 0,表示沒有人在 critical section,
      那麼把 key 設成 0 並且取得 lock (lock = 1)
    - 如果 lock = 1,表示有人在 critical section,
      那我就必須繼續等,直到取得 lock
line 6: waiting = false (準備進入 critical section)
line 7: critical section
line 8: 找到 i 的下一個人 j
line 9: 找到下一個在 waiting 的 j (只有 waiting[j] = true 才會脫離迴圈)
line 10: 如果 waiting[j] = false 就繼續找下一個 j,直到找到下一個想進入 
         critical section 的人 (還沒執行過 critical section 的人)
line 11: 如果 i = j,表示大家都執行過 critical section 了
line 12: 將 lock 解開
line 13: 如果 i != j,表示還有人沒進去過 critical section
line 14: waiting[j] = false 讓 j 停止 waiting,進入 critical section

==>

Prove bounded waiting: 
當一個 process 離開 critical section 的時候,他會依序掃描 waiting 那個陣列去找到
下一個 waiting = true 的人 (想進入 critical section 但還沒進去過的),讓他變
成下一個進入 critical section 的人,所以所有 process 最多只需要等待 n - 1 輪就
可以進入 critical section,符合 bounded waiting #

The increment() function is implemented using CAS instruction:

increment(&sequence);

void increment(atomic_int *v) {
    int temp;
    
    do {
        temp = *v;
    } while (temp != compare_and_swap(v, temp, temp + 1));
    // 因為 v 會一直等於 temp,所以 v 會一直被設定成 temp + 1,就可以達成 increment
}
  • Satisfy all the critical section requirements

Atomic Variables

  • Atomic variables can be used in to ensure mutual exclusion in situations where there may be a data race on a single variable while it is being updated.

Mutex Locks

  • OS designers build software tools to solve the critical section problem
  • mutex lock
    ​​acquire() {
    ​​    while (!available)
    ​​        ; /* busy wait */
    ​​    available = false;
    ​​}
    ​​
    ​​release() {
    ​​    available = true;
    ​​}
    ​​
    ​​while (true) {
    ​​    acquire_lock();
    ​​        critical_section();
    ​​    release_lock();
    ​​        remainder_section();
    ​​}
    
  • Disadvantage
    • Busy waiting

Semaphores

  • 號誌 (程式設計) - Wiki
  • A semaphore S is an integer variable that is accessed only through two standard atomic operations.
    • wait()
      • P
      • To test
      • semaphores - 1
    • signal()
      • V
      • To increment
      • semaphores + 1
  • All modifications to the integer value of the semaphore in the wait() and signal() operations must be executed atomically.
    • When one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value

Semaphore Usage

  • Binary semaphore
    • Range only between 0 and 1
    • Mutex lock
  • Counting semaphore
    • Range over an unrestricted domain
    • The semaphore is initialized to the number of resources available
    • To use a resource
      • wait()
        • decrementing
    • To release a resource
      • signal()
        • incrementing

  • Assume that
    P1
    and
    P2
    that wants the statement
    S1
    to happen before the statement
    S2
    • In process
      P1
      :
      ​​​​S1;
      ​​​​signal(synch);
      
    • In process
      P2
      :
      ​​​​wait(synch);
      ​​​​S2;
      
    • 因為 P2 必須等待 synch 被 P1 釋放,所以 S1 一定會比 S2 先執行。

Semaphore Implementation

  • Busy waiting problem
  • The block operation places a process into a waiting queue associated with the semaphore
    • Waiting state
  • Change the process from the waiting state to the ready state
    • wakeup()

Monitors

  • Errors may occur when semaphores are used (next page)
    • High-level synchronization constructs
      • The monitor type

  • Violating the mutual exclusion requirement
    ​​signal(mutex);
    ​​    ...
    ​​  critical section
    ​​    ...
    ​​wait(mutex);
    
  • A deadlock will occur
    ​​wait(mutex);
    ​​    ...
    ​​  critical section
    ​​    ...
    ​​wait(mutex);
    
  • Violating the mutual exclusion requirement; or a deadlock will occur
    • A process omits the wait(mutex), or the signal(mutex), or both.

Monitor Usage

  • Abstract Data Type (ADT)
    • Encapsulates data with a set of functions to operate on that data that are independent of any specific implementation of the ADT
  • Pseudocode syntax of a monitor:
    ​​monitor monitor_name
    ​​{
    ​​    /* shared variable declarations */
    
    ​​    function P1 (...) {
    ​​        ...
    ​​    }
    
    ​​    function P2 (...) {
    ​​        ...
    ​​    }
    
    ​​        .
    ​​        .
    ​​        .
    ​​    function Pn (...) {
    ​​        ...
    ​​    }
    
    ​​    initialization code ( ...) {
    ​​        ...
    ​​    }
    ​​}
    

image


  • A programmer who needs to write a tailor-made synchronization scheme can define one or more variables of type condition.
  • Condition variables
    image
    • Condition x, y
    • The operation x.wait() means that the process invoking this operation is suspended until another process invokes x.signal()
    • The operation x.signal() resumes exactly one suspended process

Implementing a Monitor Using Semaphores

  • Mutual exclusion within a monitor is ensured

Resuming Processese within a Monitor

  • Process resumption order within a monitor
    • Solution 1: FCFS
    • Solution 2: Conditional wait
      • x.wait(c)
        • c: priority number
monitor ResourceAllocator {
    boolean busy;
    condition x;
  
    void acquire(int time) {
        if (busy) x.wait(time);
        busy = true;
    }
  
    void release() {
        busy = false;
        x.signal();
    }
  
    initialization_code() {
        busy = false;
    }	
}

Liveness

Deadlock

  • Deadlocked
    • Two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes

Priority Inversion

  • Priority inversion
    • When a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process (or a chain of lower-priority processes)
      • Kernel data are protected with a lock
  • Priority-inheritance protocol
    • All processes that are accessing resources needed by a higher-priority process inherit the higher priority until they are finished with the resources.
    • When they are finished, their priorities revert to their original values.

Evaluation

  • CAS (compare-and-swap)-based approaches
    • optimistic
  • Mutual exclusion locking
    • pessimistic
CAS protection Traditional synchronization
Uncontended Faster
Moderate contention Faster