MY OS Notes

Process Synchronisation

IPC - Inter process communication

• File in mem -> Pipes
• Shared mem for communications

Inter -> comm betn two entity
Intra -> comm withing same entity (func calls)

Problems due to lack of synchronisation

1. Inconsistency (incorrectness)
2. Loss of Data
3. Deadlock

Type of synchronisation

1. Competition: Two process compete for accessing a shared resource
   • Leads to deadlock and incosistency
2. Cooperation : Execution of one task effects the other .eg producer consumer problem

Necessary condition for synchronisation Problem

1. Critical section : accessing shared resource
2. Race Condition : concurrent access of processes to a critical section
   • Final result of output depends on the order in which they finish their update.
3. Preemption : A task can be preemted by other.

Synchronisation Mechanism

Has two major parts

1. Entry Section
2. Exit Section : its job is to notify other about CS availability

ENTRY -> CS -> EXIT

Requirement for Synchronisation Mechanism

1. Mutual Exclusion
   • Definition: If one process $P_i$ is executing in its critical section, then no other process is allowed to be executing in its critical section.
   • Significance: This is the most crucial requirement, ensuring that shared resources (data structures, files, etc.) are accessed by only one process at a time, preventing race conditions and maintaining data integrity.
2. Progress
   • Definition: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision of which will enter the critical section next.
   • This selection cannot be postponed indefinitely.
   • Significance: This prevents deadlock. It ensures that if the critical section is free, a waiting process can eventually enter it, and the system does not unnecessarily halt or wait.
3. Bounded Wating
   • Definition: There exists a limit (a bound) on the number of times that other processes are allowed to enter their critical sections after a process $P_i$ has made a request to enter its critical section and before that request is granted.
   • Significance: This prevents starvation. It guarantees that a process won't wait forever to enter the critical section while other processes repeatedly enter and exit it.

A synchronisation mechanism that satisfies all three is considered a correct solution to the critical section problem.

• Mutual Exclusion $\rightarrow$ Safety (ensures nothing bad happens - data integrity is preserved).
• Progress and Bounded Waiting $\rightarrow$ Liveness (ensures something good eventually happens - processes can make progress).

Busy Waiting

• Simple Locks
• TSL (Test and Set Lock)
• XCHG / SWAP
• Strict Alternation
• Peterson's Solution

1. Simple Locks
   • Busy Wait
   • No mutual exclusion

   lock = 0; // vacant
   lock = 1; // taken
   
   while (!lock); // Entry section
   lock = 1;
   
   lock = 0;     // Exit section

test:
(1)        push    rbp
(2)        mov     rbp, rsp
(3)        nop
.L2:
(4)        mov     eax, DWORD PTR lock[rip]
(5)        test    eax, eax
(6)        je      .L2
(7)        mov     DWORD PTR lock[rip], 1
// CS (critical section)

• T1 : 1,2,3,4| T2: 1,2,3,4,5,6,7,CS | T1: 5,6,7,CS
• When to use ?
  • Only in theoretical examples, as they fail Mutual Exclusion due to race conditions (unless atomic).

1. TSL (Test Set Lock, atomic operations)
   • Gurantees Mutual exclusion
   • Gurantees Progress
   • BW not gurateed.

(1) TSL LOCK, R0
(2) CMP R0, #0
(3) JNZ 1
(4) CS

• T1: 1| T2: 1, 2, 3, CS, 1, 2, 3 | T2: 2, 3, 4
• Hardware support has to be present
• Not architectural neutral
• when to use ?
  • Multiprocessor Systems: When the critical section is very short. The overhead of a context switch would be greater than the time spent busy waiting.

3. Strict Alternation
   • No Progres
   • Gurantess MEX
   • Gurantess B.W

• Every process waiting to endter CS has to check turn value, if not then wait.

// Task 0
while (trun != 0);
<CS>
turn 1;


//Task 2
while (turn != 1)
<CS>
turn 0;

• Where to use ?
  • Purely theoretical/pedagogical, as it fails the Progress requirement.