Synchronization:
Critical section:
entry section: Request permission to enter its critical section.
接在critical section之後的: exit section
接在exit section之後的: remainder section
critical section problem的三要素:
mutual exclusion: 同時間只能有一個process在critical section
progress: 只有不是在remainder section的process能一起決定誰要進入critical section，而這個選擇can not be postponed indefinitely
bounded waiting: 當有process made a request之後，能夠進入critical section的process數量有限
nonpreemptive kernel不需擔心race conditions
SMP: symmetric multiprocessing
在single-processor中，如果nonpreemptive的話，就可以讓critical section中的指令不會執行到一半被中斷，如此就不必擔心race condition。但在multi-processor中，這樣做會讓效能大幅降低，因為message passing會送到所有processors，delay進入critical section？
test_and_set和compare_and_swap?
test_and_set在講義上好像沒有多做解釋
第一個使用compare_and_swap()的process會將lock設成1並進入critical section
課本figure6.4和6.5，並不滿足progress requirement和bounded-waiting requirement，後者似乎很好理解，因為在某個process發出request之後她是有可能無限等待的，但前者我並不瞭解？
6.7: 回頭再看
mutex = mutual exclusion
mutex lock是OS設計者通常用來處理critical section的工具。當要進入critical section之前會acquire lock，當出來之後會release lock。這種mutex lock稱作spinlock，因為當有process在critical section中時，其他process只能在原地繞圈圈busy waiting。但是其優點是當有process等待的時候不需要context switch(為什麼?)，所以如果lock很快就會解鎖，spinlock也是好選擇。
Semaphore: 一個integer
binary semaphore基本上和mutex lock是一樣的
為了避免busy waiting的發生，應該要讓等待的process block itself，使其回到waiting state。而semaphore會負責通知其當可以執行(有signal()發生時)。
方法就是將semaphore定義為一個包含integer和一個process list的struct。
當wait發生時，如果value--之後小於0就block。如果signal()發生就使value++並且如果value>0就wakeup list中排首位的process。
process control block...是什麼?
semephore的wait()和signal()當然也要是atomic的。但是，沒辦法在multiprocessor environment中disable interrupts，所以必須要確保同一個semaphore的wait()和signal()不能同時被兩個process呼叫。
priority inversion(倒置)可能發生在有兩種以上priority的系統。可以透過priority-inheritance protocol來解決：當process正在使用high priority process所需要的資源的時候，他的priority也會暫時變高。
使用semaphore來解決bounded-buffer problem，和reader-writer problem。
在reader-writer problem(6.7.2)中，rw_mutex最多只會有一個process位於queue中。有些系統可能會將其generalized為reader-writer lock。如果process只希望讀取，則他request the lock in read mode。一次最多只能有一個process acquire the lock for writing。
在Dining-Philosophers Problem中，只用semaphore可能還是會造成deadlock(見figure 6.14)。而在6.1處理的counter中，用semaphore可能還是會有潛在的問題，例如：
如果signal和wait倒置的話，可能會同時有多個critical sections執行，violating the mutual-exclusion requirement。或是某個process不小心用wait代替了signal，或忽略了其中一者，都有可能造成dead lock或mutual exclusion violating。
而為了解決這些問題，就提出了high-level language construct: monitor。
6.8.2即是使用monitor解決哲學家晚餐問題，但還是有可能starve！
課本上寫了用semaphore實作monitor和condition的方法，但我看不懂！Exercise可能會有幫助。
Definition: Adaptive Mutex是在Solaris系統上的一種mutex。
6.9待補
6.10.1
Hardware transactional memory(HTM)是使用硬體的方式去實現transactional memory。它利用了cache hierarchies和cache coherency protocols的技術。
cache coherency指的是cache之間的一致性，不同的硬體同時存取同一個memory時，它們之間各自的cache其資料可能會不一致，需要特別處理。
活學活用！
Critical section:
entry section: Request permission to enter its critical section.
接在critical section之後的: exit section
接在exit section之後的: remainder section
critical section problem的三要素:
mutual exclusion: 同時間只能有一個process在critical section
progress: 只有不是在remainder section的process能一起決定誰要進入critical section，而這個選擇can not be postponed indefinitely
bounded waiting: 當有process made a request之後，能夠進入critical section的process數量有限
nonpreemptive kernel不需擔心race conditions
SMP: symmetric multiprocessing
在single-processor中，如果nonpreemptive的話，就可以讓critical section中的指令不會執行到一半被中斷，如此就不必擔心race condition。但在multi-processor中，這樣做會讓效能大幅降低，因為message passing會送到所有processors，delay進入critical section？
test_and_set和compare_and_swap?
test_and_set在講義上好像沒有多做解釋
第一個使用compare_and_swap()的process會將lock設成1並進入critical section
課本figure6.4和6.5，並不滿足progress requirement和bounded-waiting requirement，後者似乎很好理解，因為在某個process發出request之後她是有可能無限等待的，但前者我並不瞭解？
6.7: 回頭再看
mutex = mutual exclusion
mutex lock是OS設計者通常用來處理critical section的工具。當要進入critical section之前會acquire lock，當出來之後會release lock。這種mutex lock稱作spinlock，因為當有process在critical section中時，其他process只能在原地繞圈圈busy waiting。但是其優點是當有process等待的時候不需要context switch(為什麼?)，所以如果lock很快就會解鎖，spinlock也是好選擇。
Semaphore: 一個integer
binary semaphore基本上和mutex lock是一樣的
為了避免busy waiting的發生，應該要讓等待的process block itself，使其回到waiting state。而semaphore會負責通知其當可以執行(有signal()發生時)。
方法就是將semaphore定義為一個包含integer和一個process list的struct。
當wait發生時，如果value--之後小於0就block。如果signal()發生就使value++並且如果value>0就wakeup list中排首位的process。
process control block...是什麼?
semephore的wait()和signal()當然也要是atomic的。但是，沒辦法在multiprocessor environment中disable interrupts，所以必須要確保同一個semaphore的wait()和signal()不能同時被兩個process呼叫。
priority inversion(倒置)可能發生在有兩種以上priority的系統。可以透過priority-inheritance protocol來解決：當process正在使用high priority process所需要的資源的時候，他的priority也會暫時變高。
使用semaphore來解決bounded-buffer problem，和reader-writer problem。
在reader-writer problem(6.7.2)中，rw_mutex最多只會有一個process位於queue中。有些系統可能會將其generalized為reader-writer lock。如果process只希望讀取，則他request the lock in read mode。一次最多只能有一個process acquire the lock for writing。
在Dining-Philosophers Problem中，只用semaphore可能還是會造成deadlock(見figure 6.14)。而在6.1處理的counter中，用semaphore可能還是會有潛在的問題，例如：
如果signal和wait倒置的話，可能會同時有多個critical sections執行，violating the mutual-exclusion requirement。或是某個process不小心用wait代替了signal，或忽略了其中一者，都有可能造成dead lock或mutual exclusion violating。
而為了解決這些問題，就提出了high-level language construct: monitor。
6.8.2即是使用monitor解決哲學家晚餐問題，但還是有可能starve！
課本上寫了用semaphore實作monitor和condition的方法，但我看不懂！Exercise可能會有幫助。
Definition: Adaptive Mutex是在Solaris系統上的一種mutex。
6.9待補
6.10.1
Hardware transactional memory(HTM)是使用硬體的方式去實現transactional memory。它利用了cache hierarchies和cache coherency protocols的技術。
cache coherency指的是cache之間的一致性，不同的硬體同時存取同一個memory時，它們之間各自的cache其資料可能會不一致，需要特別處理。
活學活用！
留言
張貼留言