Critical Section
n個processes(處理程序)組成系統，每個process都有一個code的片段來處理共用變數，稱為Critical Section(臨界區間)。
當一個process在使用critical section時，則其他process是不允許在此運作。
主要設計
要設計一個各process透過申請才能使用critical section，來達到一次只有一個process才能使用critical section。
達成3種條件, 解決Critical Section
- Mutual Exclusion
- Progress
- Bounded Waiting
Mutual Exclusion
一次只能有一個Process進入Critical Section。
Progress
- 不需進入Critical Section的Process不會去影響其他需要進入Critical Section的Process
- 決定要不要進入Critical Section的時間有限(為了防止Deadlock)。
Bounded Waiting
當一個process提出申請要進入critical section，是不能無限等待進入(一直等待會造成starvation)，解決方法是若有n個process提出要進入critical section，那其中的process最多等(n-1)個結束後，必須要進入critical section。
Peterson's Solution
兩個process需要進入critical section
A classic software-based solution to the critical-section.
Requires the two processes to share two data:
int turn; // 禮讓給另一個process
boolean flag[2]; // ex. flag[0]=1;代表process 0需要進入c.s.
參數:
- 有兩process i 和 process j。
- turn: 整數, 存放誰要busy waiting。
- flag[i]: boolean array, 詢問i是否想進critical section。
int turn;
boolean flag[2];
do {
flag[i] = TRUE;
turn = j; // 這讓j進去loop(busy waiting)
while(flag[j] && turn==j); // busy waiting
/* Critical Section */
flag[i] = FALSE; // process i已經做完critical section部分
/* Remainder Section */
}while(TRUE);
Hardware's way solution
- TestAndSet
- Swap
使用TestAndSet和Swap缺點
- 只有kernel mode能使用
- 花費時間
- muti-processor會失效, single-processor(busy waiting)
- 會有starvation
個別指出缺點(uniprocessor & multiprocessor)
Uniprocessor
- Interrupt disabling
- 只能用在kernel space
- 增加interrupt latency
- Spin lock(TestAndSet, Swap)
Multiprocessor
- Interrupt disabling
- 全部processes interrupt disabling花費太高了
- 如果參與的process在不同的processor，則無法使用。
- Spin lock
Semaphore(hardware)
Semaphore不需要busy waiting，而是使用waiting queue。