| title | date | lastmod |
|---|---|---|
Process Synchronization |
2022-11-08 |
2023-02-23 |
One method to solve the race condition is to divide processes into critical sections which are segments that shared data is accessed. One process must be writing.
Problem: design protocol to ensure that no 2 processes are executing their critical section at the same time.
We need to satisfy 3 properties:
- Mutual exclusion: if process is executing in critical section, no other process can be executing in its critical section at the same time.
*Why is mutual exclusion not enough?
- It can be achieved naively by preventing any process from entering critical section
- Progress: if no process is executing in its critical section and another process needs to enter their critical section, selection of this process to enter cannot be postponed indefinitely
- Bounded waiting: if a process needs to enter their critical section, all other processes are allowed to enter their own critical section only a bounded number of times
Following examples show how it is possible for 2 processes. For more processes, it becomes unfeasible
- P1 finish critical section and pass the turn over to P0
- P0 finish its critical section and pass the turn over to P1
- P1 runs in a long remainder section and never passes turn back to P0
- Context switch occurs, P0 needs to enter critical section but P1 is stuck running remainder for a long period
- Pi enters its critical section only if either flag[j] == false or turn == i. Also note that, if both processes can be executing in their critical sections at the same time, then flag[0] == flag[1] == true. These two observations imply that P0 and P1 could not have successfully executed their while statements at about the same time, since the value of turn can be either 0 or 1 but cannot be both. Hence, one of the processes—say, Pj —must have successfully executed the while statement, whereas Pi had to execute at least one additional statement (“turn == j”). However, at that time, flag[j] == true and turn == j, and this condition will persist as long as Pj is in its critical section; as a result, mutual exclusion is preserved. Progress:
- Pi can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag[j] == true and turn == j
- If Pj is not ready to enter the critical section, then flag[j] == false, and Pi can enter its critical section. If Pj has set flag[j] to true and is also executing in its while statement, then either turn == i or turn == j. If turn == i, then Pi will enter the critical section. If turn == j, then Pj will enter the critical section. Bounded Waiting:
- When
$P_i$ exits its critical section, flag[j] == false and$P_i$ is allowed to enter its critical section. Assume$P_j$ resets flag[j] == true, it will subsequently set turn == i. Since$P_i$ cannot change the turn value while in the loop, it is allowed to enter the critical section after at most 1 entry by$P_j$
Race condition is a result of context switches. We can prevent that in hardware to have atomic instructions.
- No context switches can occur while setting the lock value
- This means that whoever runs this instruction first will run first, no other process will be able to enter critical region
- If lock == true, someone is in the critical section: we are blocked
- If lock == false, we set lock to true and move into the critical section
Hardware has no memory of process trying to access the lock. P0 able to indefinitely take the lock without giving P1 a chance.
- A binary sempahore behaves similar to mutex locks.
- A counting semaphore is used to control access to a given resource consisting of a finite number of instances. It is initalised to the number of resources available.
Also known as a spinlock, where a thread trying to acquire a lock is caused to wait in a loop ("spin") while repeatedly checking if the lock is available.
Wait(S), no other processes can execute Signal(S) in order to allow P0 to continue. If we cannot context switch then there is no solution.
- Process is in the waiting state because the process cannot use the CPU (and following which enter its critical section) if another process is currently in its critical section
- Process woken up is changed to ready state but the CPU may not switch from the currently running process to this newly ready process depending on scheduling
Atomicity needed for these system calls:
One thread sends a signal to another thread to indicate something has happened
- Ensure a1 before b2
- Ensure b1 before a2
aArrived = Semaphore(0)
bArrived = Semaphore(0)
| Thread A | Thread B |
|---|---|
| statement a1 | statement b1 |
aArrived.signal() |
bArrived.signal() |
bArrived.wait() |
aArrived.wait() |
| statement a2 | statement b2 |
do
{
// wait until empty > 0 and then decrement 'empty'
wait(empty);
// acquire lock
wait(mutex);
/* perform the insert operation in a slot */
// release lock
signal(mutex);
// increment 'full'
signal(full);
}
while(TRUE)Consumer:
do
{
// wait until full > 0 and then decrement 'full'
wait(full);
// acquire the lock
wait(mutex);
/* perform the remove operation in a slot */
// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
}
while(TRUE);
- If each process executes the first
wait(chopstick)and context switches, every process only has 1 chopstick and is stuck in a deadlock Solutions:
wait(wrt);
//write
signal(wrt);It is possible that a reader R1 might have the lock, a writer W be waiting for the lock, and then a reader R2 requests access. It would be unfair for R2 to jump in immediately, ahead of W; if that happened often enough, W would starve. Instead, W should start as soon as possible. This is the motivation for the second readers–writers problem, in which the constraint is added that no writer, once added to the queue, shall be kept waiting longer than absolutely necessary. This is also called writers-preference.
int readcount, writecount; //(initial value = 0)
semaphore rmutex, wmutex, readTry, resource; //(initial value = 1)
//READER
reader() {
<ENTRY Section>
readTry.P(); //Indicate a reader is trying to enter
rmutex.P(); //lock entry section to avoid race condition with other readers
readcount++; //report yourself as a reader
if (readcount == 1) //checks if you are first reader
resource.P(); //if you are first reader, lock the resource
rmutex.V(); //release entry section for other readers
readTry.V(); //indicate you are done trying to access the resource
<CRITICAL Section>
//reading is performed
<EXIT Section>
rmutex.P(); //reserve exit section - avoids race condition with readers
readcount--; //indicate you're leaving
if (readcount == 0) //checks if you are last reader leaving
resource.V(); //if last, you must release the locked resource
rmutex.V(); //release exit section for other readers
}
//WRITER
writer() {
<ENTRY Section>
wmutex.P(); //reserve entry section for writers - avoids race conditions
writecount++; //report yourself as a writer entering
if (writecount == 1) //checks if you're first writer
readTry.P(); //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
wmutex.V(); //release entry section
resource.P(); //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
<CRITICAL Section>
//writing is performed
resource.V(); //release file
<EXIT Section>
wmutex.P(); //reserve exit section
writecount--; //indicate you're leaving
if (writecount == 0) //checks if you're the last writer
readTry.V(); //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
wmutex.V(); //release exit section
}
- Mutual exclusion
- Progression
- Bounded waiting b.
- Mx not satisfied:
- P1: turn = 0, while(flag and turn == 0) flag is false, critical section
- context switch
- P2: flag = true, while(turn == 1), critical section
- Progress is not satisfied. P1 can only run if flag = false but flag is only set to false after the critical section of P1.
a. False. If all instructions can complete in 1 cycle, there will not be instructions being executed halfway before context switch occurs. There are also other reasons for race condition, not only due to translation. If implementation using a temporary variable, a race condition can also occur. b. True. If no context switch can occur during critical section, only 1 process will be in its critical section at one time. c. False. Satisfies progress only means that 1 program will always be chosen to enter critical section. To satisfy bounded waiting, each program must have a chance to enter its critical section. A program where only 1 process always enter critical section while another is waiting indefinitely satisfies progress but not bounded waiting.
hmm not too sure abt this question idea:
- use a boolean lock value initialized to false as a shared variable, and a register boolean as a flag
- continuously try to swap
trueinto the lock - if register becomes false, we got the lock
- critical section
- set the lock to false
while(1){
register = true
while (register) {
swap(&lock, register)
} //entry section
critical section...
lock = false
remainder section...
}
Wait(S) runs before a single Signal(S). Each process is added to blocked queue until OS chooses to execute a critical region.
c. 2. There can be at most 2 processes holding S simultaneously as 2 processes are able to complete wait(S) (not blocked) before the block list starts to increase.
wait(A)
apple++
signal(A)
wait(O)
if (at least 2 oranges in basket){
oranges += 2
} else {
signal(O)
wait(A)
apple--
signal(A)
}
Wait(S){
while (TestAndSet(&lock));
S.value--
if (S.value < 0) {
S.L = append(S.L, process)
*lock = false
sleep(process)
} else {
*lock = false
}
}
Signal(S) {
while (TestAndSet(&lock));
S.value++
if (S.value <= 0) {
p = S.L[0]
*lock = false
//add to ready queue
} else {
*lock = false
}
}