CCU_OS
重點
load
and store
需要是 atomic operationflag
and turn
被 assigned 的“順序“很重要 (不能被 compiler 優化,調整先後順序)例子
trival
-O3
correct
atomic_thread_fence(memory_order_seq_cst);
避免 instruction 被調整 atomic_store(&flag[0], 1)
&tomic_load(&flag[1])
spinlock 缺點 ,一個 task 持有 lock 但被 schedule out(time sharing
起他 task 會白白等這個 lock
mutex / semaphore = spinlock + sleep + wakeup
實作
需要進入 CS 時, 用 mutex/lock —— 上鎖/解鎖永遠是同一個 thread/process;
需要處理 signalling 時,用 semaphore —— 等待/通知通常是不同的 threads/processes;
(signaling 是 process/threads 之間要通知彼此 「某些條件已經改變」 的情境:例如 producer-consumer 類型的問題可用兩個 semaphore 來實作)
mutex 與 semaphore 的差別在於:
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 來達成這樣的作用。
哲學家問題解法
Limiting the number of diners in the table
sem_init(&room, 0, NUM_PHILOSOPHERS - 1)
不限制的話會卡死,沒有任何可以進入 C.S.
Simultaneously (low concurrency)
rand
來增加每一個哲學家可以用餐的信號量 eatPermission[i]
不同core擁有不同的cache,因此core可能看到「新舊不一」的值 (這個問題稱之為cache coherence problem)
cache line
Flush
把 Cache 內容寫回 Memory ,當 Cache 為 Write through ,不需要 Flush
Invalidate
把 Cache 內容直接丟掉不要
只保證某些指 atomic,傳統上有:test_n_set、swap
這二個指令都不斷的對記憶體寫入
atomic_compare_exchange_strong
schedule()
是觸發排程器,主動讓出 CPU 使用權atomic_store(&flag[0], 1)
使用了最強的記憶體模型
C11 memory order 定義
若多個 process 申請 lock 的時候,當第一個申請 lock 成功的 process 在釋放時,其他 process 即刻處於競爭的關係,因此會造成不公平 (可能會有某個 process 頻繁持有 lock)。
現在的 Linux 採用 Ticket lock 排隊機制,也就是說,誰先申請,誰就先得到 lock
無論是 spinlock 還是 semaphore,在同一時間僅能有一個 process 進入 critical section (CS)。對於有些情況,我們可區分讀寫操作,進而提出最佳化機制,讓 read 操作的 process 可以並行 (concurrent) 運作。對於 write 操作僅限於一個 process 進入 CS。這種同步機制就是 rwlock