Skip to content

MY OS Notes

Jump to bottom
Madhab Sharma edited this page Dec 12, 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.

Deadlock Avodiance

  1. Banker's Algorithm: The Core Principle

    • The Banker's Algorithm ensures that the system never enters an unsafe state.
    • Safe State: A state where it is possible for the system to allocate resources to each process (up to its maximum need) in some order and still avoid a deadlock. This order is called a safe sequence.
    • Unsafe State: A state that is not safe. While an unsafe state doesn't guarantee a deadlock, the system cannot guarantee that a deadlock will not occur from that state.

    Priority Inversion

    • Priority Inversion is a condition where a higher-priority task is indirectly forced to wait for a lower-priority task to release a resource, thereby violating the principles of priority-based scheduling.

    • read more

Memory Management

Memory Layout of a Process

  • Porcess is a live and running program that is loaded into the mem and has unique Process Identifier (PID).
  • It remain running until it exits normally, or due to following signals
    • SIGTERM: termination signal, allows process to clean up. Maskable
    • SIGINT : interrupt singal sent using Ctrl + c. Maskable
    • SIGKILL: kill singal doesn't let process to clean up. non Maskable
  • Static memory layout: layout of the executable file added by the compiler itself.
    • size cmd can be used to see the static layout of an executable
    fat12$ size fat12
text    data     bss     dec     hex filename
3299     648    8256   12203    2fab fat12
  • Dynamic memory layout: layout that comes at runtime while the process is being loaded.
  • Static memory Layout:
    • BSS Segment:
      • Stands for Block started by symbol.
      • This segements holds uninitializd global vars or global vars set to zero.
    • DATA Segment:
      • This segment holds initialized global vars set to a non-zero value.
    • Note: 
      func () {
   static int i;        // this will be present in BSS segment
   static int j = 1;    // this will be present in DATA segment
}
    • Text Segment:
      • Contains all the machine-level instructions of a program.
  • Dynamic memory Layout:
    • It is the runtime memory layout of a process and it exits as long as process is running.
    • Loader takes care of executing, it spawns a new process and create the initial mem layout.
    • It copies static layout from the executable file.
    • More than that two new segment will also be added [stack and Heap].
    • Stack segement is the default memory region where we allocatd variable from.
      • it is a limited region in terms of size and cannot hold big objects in it.
      • It grows downwards
    • Heap segment is a bigger and adjustable region of memory
      • Can hold big objects and huge arrays.
      • Working with heap segment requires its own APIs like calloc and malloc and free.
  • To read the memory map of a process: see this example 
    command-line arguments and environment variables
------------------------------------------------
STACK
...
...
HEAP
------------------------------------------------
DATA
------------------------------------------------
BSS
------------------------------------------------
TEXT
  • How OS knows where stack stops?
    • It pre-allocates a fixed stack region + guard page.
    • Touch guard → crash.
  • How OS knows where heap stops?
    • Heap can grow only via syscalls (brk/mmap).
    • OS rejects growth if the region would overlap reserved memory.
    • No overlap can occur accidentally.
  • Do stack and heap meet?
    • Not in modern systems.
    • They have separated reserved address regions with large gaps between them.
  • Why buffer overflow works even though the OS has guard pages?
    • Guard pages detect stack region overflow (stack pointer moving out of bounds)
    • Buffer overflow exploits are inside already allocated stack pages
  • Modern protections (why exploitation is harder today)
    • Stack canaries: Small secret value placed before return address. If overflow overwrites it → program aborts.
    • ASLR (Address Space Layout Randomization): Makes it difficult to predict where stack/heap/code is located.
    • NX / DEP (non-executable stack) : Prevents executing shellcode placed on stack.
    • PIE binaries: Makes code addresses unpredictable.
  • Still, vulnerabilities exist because attackers use:
    • ROP (Return-Oriented Programming)
    • Bypassing canaries with partial overwrites
    • Leaking addresses to bypass ASLR

Clone this wiki locally