tags: CCU_OS

CH 05 Synchronous

解決 critical section 要滿足三個條件

• mutual exclusion
• progress
• bounded waiting

Spinlock / Peterson solution

• 重點

  • load and store 需要是 atomic operation
  • flag and turn 被 assigned 的“順序“很重要 (不能被 compiler 優化，調整先後順序)

• 例子

  • trival

    • flag -O3
      
      
      ​​​​​​​​​​​​0000000000001370 <p0>:
      ​​​​​​​​​​​​1370:	f3 0f 1e fa          	endbr64
      ​​​​​​​​​​​​1374:	53                   	push   %rbx
      ​​​​​​​​​​​​1375:	48 8d 3d 04 0d 00 00 	lea    0xd04(%rip),%rdi        # 2080 <_IO_stdin_used+0x80>
      ​​​​​​​​​​​​137c:	48 8d 1d d5 0c 00 00 	lea    0xcd5(%rip),%rbx        # 2058 <_IO_stdin_used+0x58>
      ​​​​​​​​​​​​1383:	e8 68 fd ff ff       	callq  10f0 <puts@plt>
      ​​​​​​​​​​​​1388:	83 3d cd 2c 00 00 01 	cmpl   $0x1,0x2ccd(%rip)        # 405c <flag1>
      ​​​​​​​​​​​​138f:	c7 05 bf 2c 00 00 01 	movl   $0x1,0x2cbf(%rip)        # 4058 <flag0>
      ​​​​​​​​​​​​1396:	00 00 00
      ​​​​​​​​​​​​1399:	c7 05 bd 2c 00 00 01 	movl   $0x1,0x2cbd(%rip)        # 4060 <turn>
      

    ​​​​​​​​void p0(void) {
    ​​​​​​​​    printf("p0: start\n");
    ​​​​​​​​    while (1) {
    ​​​​​​​​        flag0 = 1;
    ​​​​​​​​        turn = 1;
    ​​​​​​​​        while (flag1==1 && turn==1)
    ​​​​​​​​            ;   //waiting
    
    ​​​​​​​​        // -- critical section --
    ​​​​​​​​        cpu_p0 = sched_getcpu();
    ​​​​​​​​        in_cs++;
    
    ​​​​​​​​        if (in_cs == 2) 
    ​​​​​​​​            fprintf(stderr, "Both p0 and p1 are in critical section\n");
    
    ​​​​​​​​        p0_in_cs++;
    
    ​​​​​​​​        in_cs--;	
    ​​​​​​​​        // ----------------------
    
    ​​​​​​​​        flag0=0;
    ​​​​​​​​    }
    ​​​​​​​​}
    

  • correct

    • atomic_thread_fence(memory_order_seq_cst); 避免 instruction 被調整
    • atomic_store(&flag[0], 1) &tomic_load(&flag[1])
    ​​​​​​​​void p0(void) {
    ​​​​​​​​    printf("start p0\n");
    ​​​​​​​​    while (1) {
    
    ​​​​​​​​        atomic_store(&flag[0], 1);
    ​​​​​​​​        atomic_thread_fence(memory_order_seq_cst);
    ​​​​​​​​        atomic_store(&turn, 1);
    ​​​​​​​​        while (atomic_load(&flag[1]) && atomic_load(&turn)==1)
    ​​​​​​​​                ;   //waiting
    
    ​​​​​​​​        // -- critical section --
    ​​​​​​​​        cpu_p0 = sched_getcpu();
    
    ​​​​​​​​        in_cs++;	
    
    ​​​​​​​​        if (in_cs == 2) 
    ​​​​​​​​            fprintf(stderr, "p0及p1都在critical section\n");
    
    ​​​​​​​​        p0_in_cs++;	
    
    ​​​​​​​​        in_cs--;	
    ​​​​​​​​        // ----------------------
    ​​​​​​​​        atomic_store(&flag[0], 0);
    ​​​​​​​​    } 
    ​​​​​​​​}
    

• spinlock 缺點 ，一個 task 持有 lock 但被 schedule out(time sharing
  起他 task 會白白等這個 lock

Semaphore

• mutex / semaphore = spinlock + sleep + wakeup

• 實作

wait (S)
{
    value--;
    if (value < 0) {
        // add this process to waiting queue
        block();
    }
}

signal (S)
{
    value++;
    if (value <= 0) {
        // remove a process P from the waiting queue
        wakeup(P);
    }
}

• Semaphore value 可以是
  • 「負的」，通常是多個task在等待，例如「-1、-2」代表有「一、二」個task在等待
  • 「零」，沒有task在等待。初始化時，通常為零
  • 「正的」，常用於「一種資源」最多可以服務「X」個task。例如：印表機共三台，因此最多3個task同時列印

Mutex

• 特色
  • 可以判斷是誰鎖住這個mutex（owner觀念）
  • 可能支援優先權繼承
  • 可以支援或者不支援「巢狀鎖定」
  • 可以支援「自適應鎖」

mutex / semaphore 差異

• 需要進入 CS 時， 用 mutex/lock —— 上鎖/解鎖永遠是同一個 thread/process;

• 需要處理 signalling 時，用 semaphore —— 等待/通知通常是不同的 threads/processes;
  (signaling 是 process/threads 之間要通知彼此 「某些條件已經改變」 的情境：例如 producer-consumer 類型的問題可用兩個 semaphore 來實作)

• mutex 與 semaphore 的差別在於：

  • process 使用 mutex 時，process 的運作是持有 mutex，執行 CS 來存取資源，然後釋放 mutex
    Mutex 就像是資源的一把鎖：解鈴還須繫鈴人
  • process 使用 semaphore 時，process 總是發出信號 (signal)，或者總是接收信號 (wait)，同一個 process 不會先後進行 signal 與 wait
    換言之，process 要不擔任 producer，要不充當 consumer 的角色，不能兩者都是。semaphore 是為了保護 process 的執行同步正確;

• Mutex, Semaphore, the difference, and Linux kernel

  • 30秒：最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開。另外，Mutex 只能讓一個 thread 進入 critical section，Semaphore 的話則可以設定要讓幾個 thread 進入。這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。

  • 60秒 (cont.)：舉例而言，Mutex 的兩個特性：一個是只能有持鎖人解鎖、一個是在釋放鎖之前不能退出的特性，讓 Mutex 叫常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候；Semaphore 也能透過 binary semaphore 做到類似的事情，卻沒有辦法避免 priority inversion 出現。

  • 120秒 (cont.)：而 Semaphore 更常是用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去，就可以使用 Semaphore 來達成這樣的作用。

利用 Semaphore 解決常見的問題

• 哲學家問題解法
  

  
  ​​​​#define NUM_PHILOSOPHERS 6
  ​​​​#define LEFT (i + NUM_PHILOSOPHERS - 1) % NUM_PHILOSOPHERS
  ​​​​#define RIGHT (i + 1) % NUM_PHILOSOPHERS
  ​​​​    
  ​​​​sem_t forks[NUM_PHILOSOPHERS]; 
  ​​​​sem_t room;
  ​​​​sem_init(&room, 0, NUM_PHILOSOPHERS - 1); // Limiting the number of diners in the table
  ​​​​    
  ​​​​void *philosopher(void *arg)
  ​​​​{
  ​​​​    int i = *((int *)arg);
  ​​​​    while (1) {
  ​​​​        sem_wait(&room);
  
  ​​​​        sem_wait(&forks[LEFT]);
  ​​​​        sem_wait(&forks[RIGHT]);
  
  ​​​​        eat_times[i]++;
  
  ​​​​        sem_post(&forks[LEFT]);
  ​​​​        sem_post(&forks[RIGHT]);
  
  ​​​​        sem_post(&room);
  ​​​​    }
  ​​​​}
  

  • Limiting the number of diners in the table

    • sem_init(&room, 0, NUM_PHILOSOPHERS - 1)

    • 不限制的話會卡死，沒有任何可以進入 C.S.

      ​​​​​​​​​​​​Number of each philosopher:
      ​​​​​​​​​​​​        p0: 1583
      ​​​​​​​​​​​​        p1: 447
      ​​​​​​​​​​​​        p2: 1329
      ​​​​​​​​​​​​        p3: 0
      ​​​​​​​​​​​​        p4: 942
      ​​​​​​​​​​​​        p5: 1
      ​​​​​​​​​​​​Number of each philosopher:
      ​​​​​​​​​​​​        p0: 1583
      ​​​​​​​​​​​​        p1: 447
      ​​​​​​​​​​​​        p2: 1329
      ​​​​​​​​​​​​        p3: 0
      ​​​​​​​​​​​​        p4: 942
      ​​​​​​​​​​​​        p5: 1
      ​​​​​​​​​​​​Number of each philosopher:
      ​​​​​​​​​​​​        p0: 1583
      ​​​​​​​​​​​​        p1: 447
      ​​​​​​​​​​​​        p2: 1329
      ​​​​​​​​​​​​        p3: 0
      ​​​​​​​​​​​​        p4: 942
      ​​​​​​​​​​​​        p5: 1
      

  • Simultaneously (low concurrency)

    • 透過 rand 來增加每一個哲學家可以用餐的信號量 eatPermission[i]
      一定程度的緩解 bounded waiting (避免某幾位持續拿到 resources)
    ​​​​​​​​+ sem_t eatPermission[NUM_PHILOSOPHERS];
    
    ​​​​​​​​void* philosopher(void* arg) {
    ​​​​​​​​    int i = *((int*)arg);
    ​​​​​​​​    while (1) {
    
    ​​​​​​​​+        sem_wait(&eatPermission[i]);
    
    ​​​​​​​​        sem_wait(&forks[i]);
    ​​​​​​​​        sem_wait(&forks[(i + 1) % NUM_PHILOSOPHERS]);
    
    ​​​​​​​​        eat_times[i]++;
    
    ​​​​​​​​        sem_post(&forks[i]);
    ​​​​​​​​        sem_post(&forks[(i + 1) % NUM_PHILOSOPHERS]);
    
    ​​​​​​​​        sem_post(&eatSet);
    ​​​​​​​​    }
    ​​​​​​​​}
    ​​​​​​​​
    ​​​​​​​​int main() {
    ​​​​​​​​+     while (1) {
    ​​​​​​​​+         sem_wait(&eatSet);
    ​​​​​​​​+         int philosopher_id = rand() % NUM_PHILOSOPHERS;
    ​​​​​​​​+         sem_post(&eatPermission[philosopher_id]);
    ​​​​​​​​+     }
    ​​​​​​​​}
    

Cache coherence

不同core擁有不同的cache，因此core可能看到「新舊不一」的值 (這個問題稱之為cache coherence problem)

• Snoop：空間成本較低，他是基於broadcast，無法實現點對點傳輸
• Dictionary：空間成本較高（要記住最新版本在哪邊），可以實現點對點傳輸

Cache info

• cache 操作

  • cache line

    • cache line 是 cpu cache 中的最小快取單位。
    • 主流的 CPU Cache 的 Cache Line 大小多為 64 Bytes

  • Flush
    把 Cache 內容寫回 Memory ,當 Cache 為 Write through ,不需要 Flush

  • Invalidate
    把 Cache 內容直接丟掉不要

atomic operation

• 只保證某些指 atomic，傳統上有：test_n_set、swap

  • X86為例：lock bts X, Y /Bit Test and Set/
  • X86為例：lock xchg EAX,mem /exchange/

• 這二個指令都不斷的對記憶體寫入

  • 對記憶體更新，即是不斷觸發 cache coherence，不斷廣播

int test_n_set (int *value) 
{
    		register tmp = value;
    		*value = 1;     /*對記憶體更新*/
    		return tmp;
}

void swap(int* a, int* b) {
    register tmp;
    tmp = *a;
    *a = *b;    	/*對記憶體更新*/
    *b = tmp;   	/*對記憶體更新*/
}

• 改進： atomic_compare_exchange_strong
  • write一定會觸發「cache coherence」。因為「值」改變了那麼需要讓各個cache的內容「一致」

bool atomic_compare_exchange_strong (volatile atomic_int* obj, 
      					int* expected, int desired );{
    if (obj == expected) {
        /*只有在obj == expected的時候，才會對全域變數obj進行寫入*/
        /*只有lock成功的時候，才會對全域變數obj進行寫入*/
        obj = desired; return true; 
    } else {
        expected = obj; return false; /*對obj只有讀取*/
    }
}

• C11 atomic

int atomic_exchange(atomic_int* obj, int desired) {
    register tmp = obj;
    obj = desired;  /*修改了全域變數*/
    return tmp;
}


/*global value*/
atomic_int lock = 0;
do {
    while (atomic_exchange(&lock, 1))
        ; /* do nothing */
    /* critical section */
    lock = 0;
    /* remainder section */
} while (true);

bool atomic_compare_exchange_strong (volatile atomic_int* obj, 
      					int* expected, int desired );{
    if (obj == expected) {
        /*只有在obj == expected的時候，才會對全域變數obj進行寫入*/
        /*只有lock成功的時候，才會對全域變數obj進行寫入*/
        obj = desired; return true; 
    } else {
        expected = obj; return false; /*對obj只有讀取*/
    }
}

void p1(void) {
    int expected;
    while (1) {
        while (!atomic_compare_exchange_strong(&current, &expected, 1)) {
            expected = 0;
        }
        //執行到這一步驟，表示 current == expected == 0，即拿到了lock
        //此時，current = myid
        //critical section
        in_cs++;
        p1_in_cs++;                
        //離開CS
        in_cs--;
        current = 0;
    }
}

Linux kernel 的 semaphore

• down(semaphore *sem)，如果count>0表示lock成功，程式進入CS。否則將呼叫這個函數的task串到wait_list（相當於waiting queue），然後呼叫schedule()
• up(semaphore *sem)，如果wait_list是空的，那麼count++，否則從wait_list找出最前面的task，將該task自wait_list移除，並呼叫wake_up_process將這個task放到適當的run-queue

struct semaphore {
    raw_spinlock_t		lock;
    unsigned int		count;
    struct list_head	wait_list;
};

• schedule() 是觸發排程器，主動讓出 CPU 使用權

void down(struct semaphore *sem) {
    struct semaphore_waiter waiter;
 
    if (sem->count > 0) {
        sem->count--; /* 1 */
        return;
    }
 
    waiter.task = current; /* 2 */
    list_add_tail(&waiter.list, &sem->wait_list); /* 2 */
    schedule(); /* 3 */
} 

• 如果 wait_list 沒有 process，那麼只需要增加 counter;
• 從 wait_list 開頭取出第一個 process，並從 linked list 上移除。然後就是喚醒該 process;

void up(struct semaphore *sem) {
    struct semaphore_waiter waiter;
 
    if (list_empty(&sem->wait_list)) {
        sem->count++; /* 1 */
        return;
    }
 
    waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list);
    list_del(&waiter->list); /* 2 */
    wake_up_process(waiter->task); /* 2 */
} 

Memory order

• atomic_store(&flag[0], 1) 使用了最強的記憶體模型

  • 限制了compiler的優化空
  • 限制了CPU的優化空間，CPU無法跨過這個「屏障」進行動態調整指令的執行順序（out-of-order execution）
  • 雖然大幅度的降低電腦效能，但在程式設計上相對簡單許多

• C11 memory order 定義

#include <stdatomic.h>
// 越上面越弱
typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

/*example*/
atomic_load_explicit( const volatile A* obj, memory_order order );
atomic_fetch_add_explicit( volatile A* obj, M arg, memory_order order );

ticket lock 解決 spinlock 可能不公平的機制

若多個 process 申請 lock 的時候，當第一個申請 lock 成功的 process 在釋放時，其他 process 即刻處於競爭的關係，因此會造成不公平 (可能會有某個 process 頻繁持有 lock)。
現在的 Linux 採用 Ticket lock 排隊機制，也就是說，誰先申請，誰就先得到 lock

struct ticketlock_t {
	volatile atomic_int next_ticket;	
	volatile int now_serving;			
} myTicketlock;

void ticketLock_acquire(volatile atomic_int* next_ticket,volatile int* now_serving){
    int my_ticket;
    my_ticket = atomic_fetch_add(next_ticket, 1);

    while(*now_serving != my_ticket)
        ;
}

void ticketLock_release(volatile int *now_serving) {
    ++*now_serving;
}

read-write lock (rwlock)

無論是 spinlock 還是 semaphore，在同一時間僅能有一個 process 進入 critical section (CS)。對於有些情況，我們可區分讀寫操作，進而提出最佳化機制，讓 read 操作的 process 可以並行 (concurrent) 運作。對於 write 操作僅限於一個 process 進入 CS。這種同步機制就是 rwlock

• 同一時間僅有一個 writer process 進入 CS;
• 在沒有 writer process 進入 CS 時，同時可有多個 reader process 進入 CS;
• reader process 和 writer process 不可以同時進入 CS;

+----+-------------------------------------------------+
| 31 | 30                                            0 |
+----+-------------------------------------------------+
  |                    |
  |                    +----> [0:30] Read Thread Counter
  +-------------------------> [31]  Write Thread Counter

• one bit for writer