CS2106 #5 Sychronization

• Interleaving of busy waiting could be solved by disabling interrupts and enabling back after the resource is released.

issue:

• if there is a issue in the critical section, then the OS cannot interrupt to force quit the problem.
• Cannot Ctrl + C.
• If there multiple CPUs, then disabling interrupt doesn't stop the other CPU from interrupting.
• The OS doesn't allow programs to randomly disable interrupt to prevent malicious program.

• Mutual exclusion is guaranteed: Turn cannot be 0 and 1 at the same time.

issue:

• Independence is not guaranteed:
  • If P0 is not run, then P1 cannot run because Turn is still 0.
  • This vio.ates Independence rule, because a process that is not in the critical section is blocking the other process from entering the critical section.
    
• Mutual exclusion is guaranteed, because if P0 is 1, then P1 cannot enter.

issue:

• deadlock, because if both processes want, then none of them can get in.
  • There is no progress, because progress means if one process does not enter the critical section, then any one of other processes must be able to enter the critical section.

• Peterson's algorithm

Disadvantage:

• Wasting CPU cycles, should be blocked to give other processes the chance to run.
• Needs to be abstracted, because too complicated.
• There could be other situations than mutual exclusions for synchronizations.
  
• Can have multiple different implementations, because only higher level abstractions are provided.

• Wait() decrements the capacity (s), just like how during COVID time the person standing at the gate of IKEA was counting the number of people in the building until it reaches the maximum capacity.
• Signal() increments the capacity (s), which then allows other processes from acquiring the resource. This is different in real life, because in real life it is FCFS, but any process in the queue can obtain the resource.

• Semaphore contains the integer and the list of processes.
• Signal never blocks, because we can always increment.

• P3 signal(S) wakes up any blocked process (P2 in this case), increments the integer, then P2 decrements again and proceeds.

• Invariant: always holds true

• Binary semaphore is enough to implement general semaphore.

1. P1 Wait(S) (S -> 0)
2. P2 Wait(S) (blocked)
3. P1 finish, Signal(S), (S -> 1)
4. P2 wakes up, Wait(S), (S -> 0), Signal(S) (S -> 1)

• To ensure mutual exclusion, the number of processes in the critical section should not exceed 1.
• Scurrent + Ncs = 1, and Scurrent >= 0. Thus, Ncs should be less than or equal to 1.

• Starvation does not happen under the assumption that there is a fair scheduling.

• If the Wait(P) and Wait(Q) are in the same order in both of them, then the deadlock is resolved.

• shared variable by chefs and students: table for foods.
  • students should come after the chefs put the foods on the table.

• count represents the number of foods on the table
• in points to the next place in the buffer where the item should be put in.
• out points to the next place in the buffer where the item should be taken out of.
• %K exists so that it is wrapped around.

• The problem without while loops is that there is an unnecessary entering of critical section just to fail the count < K test (when there is no room on the table) or count > 0 test (when there is no food on the table).
  • To fix this, we add two more boolean values canProduce and canConsume to reduce unnecessary critical section entering.
• If there is nothing in the buffer, then canConsume is false, and if there is no room in the buffer, canProduce is false.

issue:

• busy looping is not great, because it is wasting CPU cycle.

• 3 semaphores, mutex, not full, and not empty.
  • not full is used by producer to check if it is not full - if full, then producer is blocked.
  • not empty is used by consumer to check if the buffer is empty - if empty, consumer is blocked.
• when a producer signals !empty, then the consumer wakes up from waiting and consumes.
  • The consumer then signals !full, which, when the producer was blocked since the buffer was full, causes the producer to wake up.
    
• No two writers can write at the same time. Only one writer at a time.
• Readers can read at the same time, but cannot read when there is a writer modifying the data structure.

• roomEmpty semaphore is used so that the reader recognizes there is a writer in the room.
• wait(roomEmpty) is called for the first nReader, because if the first reader sees the room being empty, all the other readers can follow the first reader and read data.

issue:

• nReader is a shared variable but is not protected, so race condition can happen.
• other readers can still enter the room while the first readers is blocked.

• Solution is using mutex.
• Other readers cannot increment nReader if nReader == 1, because it is protected by mutex.
  • Which means that the room should be empty for other readers to read as well.

• Philosophers think, then get hungry,
• They need to use chopsticks on both sides to eat.

• If every philospher start eating and pick up chopsticks around the same time, then no one can start eating, causing deadlock.

• Fixing attempt: If a philospher cannot eat, then he puts down his left chopstick.
  • However, if everyone puts down at the same time again, this would not work.

• use mutex so that a philospher is guaranteed to eat.

issue:

• only one philosopher can eat at a time, when there clearly can be two philosophers who can eat at the same time, considering the number of chopsticks.
  (efficiency problem)

• state[N] : state of each philosopher
• i: ith philosopher
• s[N]: if s[i] == 1, then it is safe to eat, but if s[i] == 0, then it is not
  
• wait(s[i]) is blocked when it is not safe to eat, meaning that the person on the left or right or both are eating.
• wait(s[i]) is outside the mutex, because if it is inside and blocked, then no one can pick up their chopsticks.
• when it is safe to eat, s[i] becomes 1 by signaling, and the philosopher can Eat().

• Tell people on the left and right that it is safe to eat now.