Skip to content

MY OS Notes

Jump to bottom
Madhab Sharma edited this page Dec 10, 2025 · 23 revisions

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).
image

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.
  1. 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.
  1. Peterson solution
    • Only for 2 tasks
    • Gurantees MEX
    • Gurantees Progress
    • Gurantess BW
  • Lock Variable + Strick Alteration
    • If no task(i) is intereset -> no concept of trun
    • if both are interested -> then turn comes in picture
    • any interested T(i) -> should change flag from F to T
    • if both interested, then make turn equal to their own id.
    • check whether if T(i) is last or first to update turn.
    • If first get insde CS, if last, then wait [FIFO order].
Process Pi​ (where j=1−i) Line No. CodeEntry 
Section1 flag[i] = true;2turn = j;3while (flag[j] && turn == j);Critical Section (CS)4// ... Critical Section Code ...Exit Section5flag[i] = false;
  • $$T_1: 1, 2 \ | \ T_2: 1, 2, 3(\text{Wait}) \ | \ T_1: 3(\text{Proceed}), 4, 5 \ | \ T_2: 3(\text{Proceed}), 4, 5$$
  • Theoretical, as it is complex and only works for two processes, but it correctly satisfies all three requirements (ME, Progress, Bounded Waiting).

Blocking Mecahanism

  • OS based
  • applicable to multiple process

Semaphores:

  • counting semaphore [-inf, +inf]
  • binary semaphore [0/1]
  • wait/down/p or singal/up/v
  1. Counting semaphores:
typedef struct {
   int value;      // no of sucessfull down
   queue Type L;   // list of PCB's of those process that gets blocked while performing "down" unsuccessfully
} CSEM;
  • case 1: if ++s -> -ve that implies : more than one blocked Tasks
  • case 2: if ++s -> 0 that implies: only 1 tasks is currently blocked
  • case 3: if ++s -> > 0 tha implies: no blocked process

  1. Binary semaphores (Mutex):

    • Only value 0/1
    • In counting sem one can know no of blocked tasks but not in BSem.
    • blocked Queue has process then value has to be zero.
    • if Critical section is in process value has to be zero.
    • but if value = 0, that doesn't mean its blocked.
    • to know about the blocked process queue has to be checked.
    • if 0 up is 0 then queue is not empty.
    • if 0 up is 1 when queue is empty.
    • Cases of BSEM
    1.
S = 1
 P(S)
S = 0
status -> sucess.

2.
S = 0
 V(S)
S = 0/1 // depends
status -> sucess

3. 
S = 0
 V(S)
S = 1
status -> sucess

4.
S = 0
 P(S)
S = 0
status -> blocked

5.
S = 1
 V(S)
 S = 1
status -> sucess
    • If blocked queue is LIFO, then startvation is possible and no BW is guarteed.
    • If blocked queue is FIFO, then all 3 (MEX, PRGRSS, BW) is guranteed.
    • LIFO also quarantess BW only if 2 tasks.
    1.
V(Mutex)
 CS     // no MEX
P(Mutex)

2.
P(Mutex)
 CS     // MEX but deadlock
P(Mutex)

eg. Deadlock
1. P(S)    P(T)
3. P(T)    P(S)
4. CS      CS
5. V(T)    V(S)
6. V(S)    V(T)

T1:1|T2:1|T1:2 W|T2:2W deadlock
    • If both the tasks process perform down operation in same order, deadlock prevented but not in reverse order.

    Concurency Problems

    Deadlock

    • starvation is long waiting
    • deadlock is infinite waiting
    • necessary condition for deadlock:
      • MEX
      • No-premption
      • HOLD and wait
      • Circular wait
    • resources may be single(CPU) or multiple (regs)
    • Min nof resources for no deadlock
      • max no resource even if provided will cause a deadlock + 1.
    • Max nof resource for deadlock
      • reduce 1 instance from all requesting process request.
    • for no deadlock $$\left( \sum_{i=1}^{n} xi \right) - n + 1$$
    • for deadlock hold one back.
    • in case if the system has resources of multi-instanace type, the presence of a cycle in ti is only a necessary condition for DL
    • For single instance presence of a cycle is both sufficent and Neccessary condition.
    • Strategies
      • DL ignorance (ostrich apporach)
      • DL prevention
      • DL avoidance [bankers algo]
      • DL detection and recovery [Doctor's algo]

    Deadlock Prvention

    1. Negate MEX
      • Make resourcess serable whenever possible.
      • Spooling: converting a dedicated resource into a sharable one.
      • Drawback: Not practical for all resources
    2. Negate Hold and Wait
      • Ensure that whenever a process request a resouce it does not hold any other resources.
      • Request all at once
      • Process must release all the resource befor making a fresh or new request
      • Drawbacks
        • Low Resource Utilization: Resources are allocated for the entire duration of the process even if they are only needed briefly, leading to long periods of idleness.
      • Starvation: A process that requires several popular resources may never get all of them simultaneously.
    3. Negate No Preemption

      • Allow resources to be preempted (taken away) from a process.

      • Forced Release on Wait: If a process is holding resources and requests another resource that cannot be immediately allocated, the system forces the process to release all the resources it currently holds. It then waits for all resources (old and new) to become available before restarting.

      • Preemption of Waiting Processes: If a resource is requested and is held by another process that is itself waiting for another resource, the system preempts the resource from the waiting process and gives it to the requesting process.

      • Drawbacks: Only practical for resources whose state can be easily saved and restored (e.g., CPU registers, memory). It is generally not feasible for physical devices like printers or tape drives.

    4. Negate Circular Wait
      • Impose a total linear ordering (ranking) on all resource types.
      • Resource Ordering: Assign a unique integer number to every resource type (e.g., Printer=1, Scanner=2, Disk Drive=3). A process must request resources in strictly increasing order of enumeration.
      • Never allow a process to request a lower numbered resouce than the last requested allocated.
      • Drawbacks: This constraint can be difficult to manage and may be inefficient if a process naturally needs resources in an order that violates the numbering scheme.

Clone this wiki locally