OS

15 August 2025 14:29

Operating-
[Link]

Page 1
Page 2
Page 3
Page 4
Page 5
 preemptive

Cpu is taken away from

expire, After the

Page 6
Page 7
Spooling (Simultaneous Peripheral Operations On-Line) in OS means storing data temporarily in a buffer (usually on disk) so that \
the CPU and I/O devices can work independently at their own speeds.
Example: In printer spooling, multiple print jobs are stored in a queue (spool) and the printer prints them one by one,
while the CPU continues working.
It improves CPU utilization, allows multiprocessing, and manages slow I/O devices efficiently.

Page 8
Page 9
Page 10
Page 11
Page 12
Page 13
The Degree of Multiprogramming in an operating system refers to the number of processes loaded into main memory (RAM) and actively
being managed by the CPU at a given time.
Detailed Explanation
1. Definition
○ It is the number of processes that are ready to execute (in main memory) at the same time.
○ It is not the total number of processes in the system (some might be on disk or suspended).
2. Purpose
○ To improve CPU utilization: When one process waits for I/O, another can use the CPU.
○ To reduce idle CPU time.
3. Example
○ If your OS has 4 processes in main memory at the same time, the degree of multiprogramming is 4.
4. Control
○ Controlled by a Long-Term Scheduler (also called Admission Scheduler).
○ If the degree is too high → risk of thrashing (excessive swapping between RAM and disk).
○ If too low → CPU underu liza on.
5. Formula (conceptual, not exact calculation)
Degree of Multiprogramming = Number of processes in memory
1. CPU Scheduling — Overview
• Definition:
CPU scheduling is the process of deciding which process in the ready queue gets the CPU next.
• Goal:
Maximize CPU utilization, throughput, and responsiveness while minimizing waiting time, turnaround time, and response time.

Page 14
2. Types of Scheduling
Scheduling can happen at different levels in an OS:
A. Long-Term Scheduling
• What it does:
Controls the degree of multiprogramming (how many processes are in main memory).
• Function:
Decides which processes are admitted into the system for processing.
• Characteristics:
○ Runs infrequently (seconds or minutes apart).
○ Balances I/O-bound and CPU-bound processes.
○ Implemented by Long-Term Scheduler (Admission Scheduler).
• Impact:
Too many processes → memory thrashing.
Too few processes → CPU idle.

B. Medium-Term Scheduling
• What it does:
Temporarily removes (suspends) some processes from memory and later resumes them.
• Function:
Optimizes the mix of I/O-bound and CPU-bound processes, controls multiprogramming level dynamically.
• Characteristics:
○ Improves performance by suspending low-priority or waiting processes.
○ Used in time-sharing systems to free up CPU for active processes.
○ Implemented by Medium-Term Scheduler.

C. Short-Term Scheduling
• What it does:
Decides which ready process will run next on the CPU.
• Function:
Selects from ready queue and dispatches to CPU.
• Characteristics:
○ Runs very frequently (milliseconds).
○ Has the most direct impact on system performance.
○ Implemented by Short-Term Scheduler (CPU Scheduler).

Summary Table of Schedulers

Feature Long-Term Scheduler Medium-Term Scheduler Short-Term Scheduler
Frequency Low Medium High
Decision Which process enters system Which process to suspend/resume Which process gets CPU next
Goal Control multiprogramming Optimize process mix Maximize CPU efficiency
Speed Slow Medium Fast (milliseconds)
Impact Degree of multiprogramming CPU/I-O balance CPU utilization, responsiveness
CPU Scheduling Criteria – Definitions and Formulas
1. Burst Time (BT)
The total time a process requires the CPU for execution (excluding I/O time).
Also called CPU Execution Time.
Example: If a process needs 12 ms of CPU processing, its BT is 12 ms.
2. Arrival Time (AT)
The time at which a process enters the ready queue.
Example: If a process arrives at 3 ms, AT = 3 ms.
3. Completion Time (CT)
The time at which a process finishes its execution.
Example: If a process finishes at 20 ms, CT = 20 ms.
4. Turnaround Time (TAT)
Total time taken from the process’s arrival to its completion.
Formula:
TAT = CT - AT

Example: CT = 20 ms, AT = 3 ms → TAT = 17 ms.

5. Waiting Time (WT)
Total time a process spends waiting in the ready queue.
Formula:
WT = TAT - BT

Page 15
 WT = TAT - BT

Example: TAT = 17 ms, BT = 12 ms → WT = 5 ms.

6. Response Time (RT)
Time from the process’s arrival until the first time it gets CPU.
Formula:
RT = (Time of first CPU allocation) - AT

Example: First CPU allocation at 8 ms, AT = 3 ms → RT = 5 ms.

7. Throughput
Number of processes completed per unit time.
Formula:
Throughput = Number of processes completed / Total time taken

Example: 5 processes completed in 50 ms → Throughput = 0.1 processes/ms.

8. CPU Utilization
Percentage of time CPU is actively executing processes.
Formula:
CPU Utilization = (CPU Busy Time / Total Time) × 100

Example: CPU busy for 45 ms in a 50 ms interval → U liza on = 90%.

9. Average Turnaround Time (Average TAT)
Formula:
Average TAT = (Sum of all TAT values) / Number of processes
10. Average Waiting Time (Average WT)
Formula:
Average WT = (Sum of all WT values) / Number of processes
11. Average Response Time (Average RT)
Formula:
Average RT = (Sum of all RT values) / Number of processes
y.

First Come First Serve (FCFS) Scheduling – OS Notes

Definition:
• FCFS is the simplest CPU scheduling algorithm.
• The process that arrives first in the ready queue is executed first.
• It works like a queue (FIFO – First In First Out).

Characteristics:
1. Non-preemptive – once a process starts execution, it cannot be stopped until it finishes.
2. Basis of Scheduling – Process arrival time.
3. Fairness – Each process gets CPU in the order of arrival.
4. Implementation – Managed with a simple FIFO queue.

Example:
Suppose 3 processes arrive as follows:
Process Arrival Time (AT) Burst Time (BT)
P1 0 5
P2 1 3
P3 2 8
Step 1 – Arrange in order of arrival
Already ordered: P1 → P2 → P3
Step 2 – Calculate Completion Time (CT)
• P1: CT = 0 + 5 = 5
• P2: CT = 5 + 3 = 8
• P3: CT = 8 + 8 = 16
Step 3 – Calculate TAT & WT
Process AT BT CT TAT = CT-AT WT = TAT-BT
P1 0 5 5 5 0
P2 1 3 8 7 4
P3 2 8 16 14 6
Averages:
• Avg TAT = (5+7+14) / 3 = 8.67
• Avg WT = (0+4+6) / 3 = 3.33

Page 16
• Avg WT = (0+4+6) / 3 = 3.33

Gantt Chart:
| P1 | P2 | P3 |
0 5 8 16

Advantages:
• Simple to implement.
• Fair: processes are served in the order they arrive.
• No starvation.
Disadvantages:
• Convoy Effect: Short processes may wait for long processes to finish.
• Poor average waiting time if burst times vary a lot.

Use Cases:
• Best for batch systems where execution time is predictable and processes are not interactive.

Shortest Job First (SJF) Scheduling – OS Notes

Definition:
• SJF is a scheduling algorithm where the process with the shortest burst time (execution time) is selected first.
• It can be preemptive or non-preemptive.
○ Non-preemptive SJF: Once a process starts, it runs till completion.
○ Preemptive SJF (also called Shortest Remaining Time First, SRTF): If a new process arrives with a shorter burst time than the
remaining time of the current process, CPU is preempted.

Characteristics:
1. Based on burst time (BT), not arrival order.
2. Optimal algorithm – gives minimum average waiting time if all processes are known in advance.
3. Implementation needs knowledge of burst times (can be predicted using exponential averaging in real systems).

For preemptive SJF, scheduling decisions happen at each process arrival.

Example 1 – Non-Preemptive SJF:

Process AT BT
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Step 1 – Sort by arrival, then pick shortest BT available at each step.
• At time 0 → P1 only → run P1.
• At time 2 → P2 arrives but P1 s ll running.
• At time 4 → P3 arrives (shortest BT among ready processes → P3 executes).
• Next shortest is P2, then P4.
Execution Order: P1 → P3 → P2 → P4
Step 2 – Calculate CT, TAT, WT
Process AT BT CT TAT=CT-AT WT=TAT-BT
P1 0 7 7 7 0
P2 2 4 12 10 6
P3 4 1 8 4 3
P4 5 4 16 11 7
Averages:
• Avg TAT = (7+10+4+11)/4 = 8.0
• Avg WT = (0+6+3+7)/4 = 4.0
Gantt Chart (Non-preemptive):
| P1 | P3 | P2 | P4 |
0 7 8 12 16

Example 2 – Preemptive SJF (SRTF):

Process AT BT
P1 0 8
P2 1 4
P3 2 2

Page 17
 P3 2 2
P4 3 1
Execution:
• At 0 → P1 starts (BT=8).
• At 1 → P2 arrives (BT=4 < remaining 7) → preempt P1, run P2.
• At 2 → P3 arrives (BT=2 < remaining 3) → preempt P2, run P3.
• At 3 → P4 arrives (BT=1 < remaining 1 of P3? No, equal → con nue P3).
• P3 finishes, then P4, then P2, then P1.
Order: P1 → P2 → P3 → P4 → P2 → P1
Result: Gives smaller average waiting time than non-preemptive.
When BT for two process=- same follow fcfs

Advantages:
• Minimum average waiting time (optimal).
• Good for batch jobs where execution times are predictable.
Disadvantages:
• Needs knowledge of burst time (not realistic always).
• Response time is poor.
• May cause starvation – longer processes may never execute if short ones keep arriving.
• Preemptive SJF has higher overhead due to frequent context switching.

Use Cases:
• Suitable for batch processing systems where job lengths are known.

How to find no of Context switching

Count all the lines of gant chart-2;

Priority Scheduling – OS Notes

Definition:
• In priority scheduling, each process is assigned a priority number.
• The CPU is allocated to the process with the highest priority.
• Can be:
○ Non-preemptive: Once a process starts, it cannot be stopped until completion.
○ Preemptive: If a new process arrives with a higher priority, it preempts the currently running process.

Characteristics:
1. Scheduling is based on priority (not arrival or burst time).
2. Priority may be internally defined (based on resource needs, memory usage, etc.) or externally defined (business importance, user
requirement).
3. Processes with the same priority are scheduled using FCFS.

Important Terms:
• Priority number: Lower number = higher priority (or vice-versa, depends on system convention).
• AT, BT, CT, TAT, WT are calculated as usual.

Example – Non-Preemptive Priority Scheduling:

Process AT BT Priority
P1 0 5 2
P2 1 3 1
P3 2 8 4
P4 3 6 3
Execution:
• At time 0 → only P1 → runs.
• At time 1 → P2 arrives (higher priority than P1), but non-preemp ve → wait ll P1 finishes.
• After P1, among P2, P3, P4 → P2 has highest priority → run P2.
• Then P4, then P3.
Order: P1 → P2 → P4 → P3
CT, TAT, WT Table:
Process AT BT Priority CT TAT=CT-AT WT=TAT-BT
P1 0 5 2 5 5 0
P2 1 3 1 8 7 4
P4 3 6 3 14 11 5
P3 2 8 4 22 20 12

Page 18
Averages:
• Avg TAT = (5+7+11+20)/4 = 10.75
• Avg WT = (0+4+5+12)/4 = 5.25
Gantt Chart:
| P1 | P2 | P4 | P3 |
0 5 8 14 22

Example – Preemptive Priority Scheduling:

• If P2 (priority 1) arrived while P1 was executing at time 1, it would preempt P1 immediately.
• Execution Order would change: P1 → P2 → …

Advantages:
• Flexible (can give priority to important processes).
• Useful in real-time systems.
Disadvantages:
• Starvation (indefinite blocking): Low-priority processes may never execute if high-priority processes keep coming.
• Can be solved with Aging → gradually increase the priority of wai ng processes.
• New Priority=Old Priority+(Waiting Time×α)

Use Cases:
• Real-time OS (where urgent tasks must execute first).
• Systems where different types of jobs (interactive vs background) exist.

Round Robin (RR) Scheduling – OS Notes

Definition:
• Round Robin is a preemptive CPU scheduling algorithm.
• Each process gets the CPU for a fixed time slice/quantum (q).
• If a process doesn’t finish in that time, it is preempted and placed at the end of the ready queue.

Characteristics:
1. Preemptive version of FCFS.
2. Time Quantum (q): Decides efficiency.
○ If q is too large → works like FCFS.
○ If q is too small → more context switches, high overhead.
3. Fair → every process gets an equal share of CPU in cyclic order.
4. Best suited for time-sharing systems.
5. Best avg response time
6. Ready queue is circular queue
7. Context switching is used.

Remaining Time (RT): Burst time left after partial execution.

Example:
Process AT BT
P1 0 5
P2 1 4
P3 2 2
Time Quantum (q) = 2
Step-by-Step Execution:
• At 0 → P1 runs for 2 units → remaining BT = 3
• At 2 → P2 arrives → run P2 for 2 units → remaining BT = 2
• At 4 → P3 arrives → run P3 for 2 units → finishes
• Back to P1 (remaining 3) → run 2 units → remaining 1
• Next P2 (remaining 2) → run 2 units → finishes
• Finally P1 (remaining 1) → run 1 unit → finishes
Execution Order (Gantt Chart):
| P1 | P2 | P3 | P1 | P2 | P1 |
0 2 4 6 8 10 11
CT, TAT, WT Table:
Process AT BT CT TAT=CT-AT WT=TAT-BT
P1 0 5 11 11 6
P2 1 4 10 9 5
P3 2 2 6 4 2
Averages:
Page 19
Averages:
• Avg TAT = (11+9+4)/3 = 8.0
• Avg WT = (6+5+2)/3 = 4.33
After a certain time quantum RR=FCFS
Advantages:
• Fair → no starva on.
• Good for time-sharing & interactive systems.
• Simple to implement.
Disadvantages:
• Performance depends heavily on time quantum (q).
• High context switching overhead if q is too small. As time quantum is inversely proportional tp context switching
• Larger average waiting time compared to SJF. Means starvation

Use Cases:
• Interactive systems (user processes, servers, multitasking).
• Time-sharing OS like UNIX.
🔹 Multilevel Queue (MLQ) Scheduling
Definition:
• Ready queue is divided into multiple separate queues based on process type/priority.
• Each queue has its own scheduling algorithm.
• A fixed priority is given to each queue → processes in higher priority queues are executed first.

Structure Example:
• Queue 1 (Highest priority): System processes → Scheduled by RR (q=10 ms).
• Queue 2: Interactive processes → Scheduled by RR (q=20 ms).
• Queue 3: Batch processes → Scheduled by FCFS.
Diagram (Text Form):
[ Queue 1: System ] → RR
[ Queue 2: Interac ve ] → RR
[ Queue 3: Batch ] → FCFS

Characteristics:
1. Rigid – once a process is assigned to a queue, it stays there permanently.
2. Each queue can have its own algorithm.
3. Queues scheduled based on fixed priority.

Advantages:
• Simple to implement.
• Useful for systems with clear process categories (foreground vs background).
Disadvantages:
• Rigid – process can’t move between queues.
• Starvation possible → low-priority queues may never execute.

🔹 Multilevel Feedback Queue (MLFQ) Scheduling

Definition:
• Extension of MLQ → allows a process to move between queues based on its behavior and requirements.
• Designed to improve fairness and responsiveness.
• Increase the prioritty of low priority process,

Rules (commonly used):

1. New processes enter the highest priority queue.
2. If a process uses its entire time quantum without finishing → it is moved to a lower priority queue.
3. If a process yields before time quantum expires → stays in the same or moves higher (depending on implementa on).
4. Lower queues usually have larger time quantums.

Structure Example (3 Queues):

• Q1: Highest priority, RR (q=8 ms)
• Q2: Medium priority, RR (q=16 ms)
• Q3: Lowest priority, FCFS
Diagram (Text Form):
[ Q1: High Priority ] → RR (q=8)
[ Q2: Medium Priority ] → RR (q=16)
[ Q3: Low Priority ] → FCFS

Page 20
Characteristics:
• Dynamic – processes can move up or down queues.
• Prevents starvation by eventually pushing all processes to lower FCFS queue.
• More complex to implement than MLQ.

Advantages:
• More flexible than MLQ.
• Adapts to process behavior.
• Good for general-purpose time-sharing systems.
Disadvantages:
• Complex to tune (time quantum, number of queues, promotion/demotion rules).
• Higher overhead due to frequent queue adjustments.

🔹 Key Differences: MLQ vs MLFQ

Feature Multilevel Queue (MLQ) Multilevel Feedback Queue (MLFQ)
Queue movement No (process fixed in one queue) Yes (process can move between queues)
Flexibility Rigid Flexible, adaptive
Starvation Possible (low-priority ignored) Avoided with feedback mechanism
Complexity Simple implementation More complex to implement
Use Cases Systems with well-defined process types (system vs batch) General-purpose OS, interactive & batch mix

🔹 Threads in OS
Definition:
• A thread is the smallest unit of CPU execution.
• Single sequence stream within a process
• A process can have multiple threads that share the same address space, code, and resources, but run independently.
• Sometimes called lightweight process (LWP).

🔹 Process vs Thread
Feature Process Thread
System call req No System call
Definition Independent program in execution Smallest execution unit inside a process
Memory Has its own memory (PCB, address space) Shares memory of process (code, data, files) as treated as single task for os
Overhead Heavyweight (more overhead) Lightweight (less overhead)
Communication Inter-process Communication (IPC) needed Easier (shared memory within process)
Switching Slower (context switch between processes) Faster (context switch between threads)

🔹 Types of Threads
1. User Threads (UT):
○ Managed at user level (not kernel).
○ Created by application
○ No use of kernel
○ Has own program counter, register set and data files
○ Faster to create & manage.
○ Thread switching is fast.
○ OS not aware → if one thread blocks or it causes page fault , the whole process blocks.
2. Kernel Threads (KT):
○ Managed by OS kernel.
○ Slower (more overhead).
○ Efficient
Thread control Block- overhead
Page 21
 ○ Thread control Block- overhead
○ It does not block entire process.
○ OS schedules threads individually → be er CPU u liza on.
3. Hybrid (User + Kernel):
○ Many user threads mapped to fewer kernel threads (M: N model).
○ Tries to combine advantages of both.

🔹 Thread Models
1. Many-to-One:
○ Many user threads mapped to one kernel thread.
○ Simple but one blocked thread blocks all.
2. One-to-One:
○ Each user thread maps to a kernel thread.
○ True concurrency, but high overhead.
3. Many-to-Many:
○ Many user threads mapped to many kernel threads.
○ Flexible, balanced model.
○ Blocking system call does not block the entire process.

🔹 Benefits of Threads
1. Responsiveness: One thread blocked doesn’t block entire process.
2. Resource Sharing: Threads share memory & resources.
3. Economy: Cheaper to create/manage than processes.
4. Scalability: Efficient use of multiprocessor systems.

🔹 Problems with Threads

• Synchronization issues → mul ple threads accessing shared data may cause race condi ons.
• Deadlock if threads wait indefinitely on each other.
• Difficulty in debugging due to concurrency.

🔹 Example Use Cases

• Web servers (each client handled by a thread).
• Word processors (typing thread, spell-check thread, auto-save thread).
• Multimedia applications (video rendering + audio playback).
• Operating system kernel tasks.
• Concurrency means executing multiple tasks in overlapping time periods.
• It does not always mean parallelism. Even on a single CPU, tasks can be concurrent (via context switching).
• Goal: maximize CPU utilization and responsiveness.
• Concurrency- many to many> one to one> many to one

Process Synchronization
• Definition:
Process synchronization is a mechanism to ensure that when multiple processes execute concurrently, their execution is coordinated so
that shared resources are accessed in a safe and consistent manner.
○ Prevents race conditions (when outcome depends on the order of execution).
○ Ensures data consistency in a multi-process system.

Types of Processes in Synchronization

1. Cooperating Processes
○ Processes that can affect or be affected by other processes.
○ They share data (directly or indirectly) and resources.
○ They need synchronization to avoid inconsistencies.
○ Examples:
 Two processes updating a shared variable or file.
 Producer–Consumer problem (Producer adds data, Consumer removes data from buffer).
2. Independent Processes
○ Processes that do not share data or resources with other processes.
Their execution is deterministic and does not affect other processes.
Page 22
 ○ Their execution is deterministic and does not affect other processes.
○ They do not require synchronization.
○ Examples:
 Text editor and music player running at the same time.
 Running two independent programs like a calculator and a photo viewer

Interprocess Communication (IPC)

• Definition:
IPC is the mechanism that allows processes to exchange data and information with each other, either within the same system or across
different systems.
Since processes run independently, IPC is needed to enable coordination and communication.

Two Types of Processes (w.r.t IPC)

1. Independent Process
○ Cannot affect or be affected by the execution of other processes.
○ Does not share data with any other process.
○ Example: A text editor and a music player running separately.
2. Cooperating Process
○ Affects or can be affected by other processes.
○ Shares data directly or indirectly with other processes.
○ Example: A compiler and assembler, or producer-consumer processes.

Reasons for IPC

1. Data sharing – Multiple applications share common data (e.g., database).
2. Computation speed-up – Divide tasks among multiple processes.
3. Modularity – Break a large system into smaller cooperating processes.
4. Convenience – Users can perform multiple tasks at once (chat + file transfer).

Methods of IPC
1. Shared Memory
○ A region of memory is shared between cooperating processes.
○ Fast, as processes directly read/write to memory.
○ Needs synchronization (semaphores/monitors).
○ Example: Producer-Consumer problem using a buffer.
○ Kernel is not involved.
2. Message Passing
○ Processes communicate by sending/receiving messages through the OS.
○ Slower than shared memory (more overhead).
○ Easier for distributed systems.
○ Example: Client-server communication.
○ Kernel is involved.
○ Message Passing Operations:
 send(message) → send info to another process.
 receive(message) → receive info from another process.

Direct vs Indirect Communication

1. Direct
○ Processes must name each other explicitly.
○ send(P, msg) → send msg to process P.
○ receive(Q, msg) → receive msg from process Q.
2. Indirect
○ Uses mailboxes/ports.
○ send(A, msg) → send msg to mailbox A.
○ receive(A, msg) → receive msg from mailbox A.

Synchronous vs Asynchronous Communication

• Synchronous (blocking): Sender waits until receiver receives the message.
• Asynchronous (non-blocking): Sender continues without waiting.

Examples of IPC in Real Life

• Pipes (Linux: |) – connect output of one process to input of another.
• Message Queues – used for ordered communication.
• Sockets – used for client-server communication over a network.
• Shared Memory + Semaphores – used in multiprogramming OS.

Page 23
🔹 Race Condition
Definition:
• A race condition occurs when multiple processes/threads access shared data concurrently, and the final outcome depends on the order
of execution.
Example:
Two threads updating a shared variable x = 5:
• Thread 1: x = x + 1
• Thread 2: x = x * 2
• If Thread 1 runs first → result = 12
• If Thread 2 runs first → result = 10
👉 Output is inconsistent → this is a race condition.
Cause: Lack of synchronization while accessing shared resources.

🔹 Critical Section
Definition:
• The part of the program where a process accesses shared resources (variables, files, databases, etc.) is called the Critical Section.
• Only one process should be allowed in the critical section at a time.

🔹 Critical Section Problem

Goal: Design a protocol (synchronization mechanism) that ensures processes execute critical sections safely without causing race conditions.
Requirements (3 conditions for a correct solution):
1. Mutual Exclusion:
○ Only one process can enter the critical section at a time.
2. Progress:
○ If no process is in the critical section, then one of the waiting processes must be allowed to enter.
○ No indefinite waiting.
3. Bounded Waiting (Fairness):
○ A process must not wait indefinitely to enter.
○ There should be a limit on how many times other processes can enter before it gets a chance.
4. No Assumption related to hardware speed
5. 1,2 primary condi 3 4 secondary

🔹 Solutions to Critical Section Problem

1. Software Solutions (Algorithmic):
○ Peterson’s Algorithm (classic 2-process solution).
○ Bakery Algorithm.
2. Hardware Solutions:
○ Test-and-Set (TSL instruction).
○ Compare-and-Swap.
3. Synchronization Mechanisms:
○ Semaphores (counting & binary).
○ Mutex Locks.
○ Monitors (high-level construct).

🔹 Semaphores
Definition:
• A semaphore is a synchronization primitive (a special integer variable) used to control access to shared resources by multiple
processes/threads.
• Proposed by Edsger Dijkstra (1965).
• Used to handle mutual exclusion.
🔹 Types of Semaphores
1. Binary Semaphore (Mutex Lock):
○ Value = 0 or 1.
○ Works like a simple lock → either resource is free (1) One means entry is allowed or taken (0 means not allowed)
○ Used for mutual exclusion.
2. Counting Semaphore:
○ Value ≥ 0 (integer). From - infintiy to + infinity
○ Used to manage access to multiple instances of a resource.
○ Example: Printer pool with 3 printers → ini al semaphore = 3.

🔹 Operations on Semaphore
Two atomic operations (can’t be interrupted):
1. Wait (P operation / down): used in entry section

Page 24
1. Wait (P operation / down): used in entry section
wait(S):
while S <= 0:
// busy wait (or block)
S=S-1
○ If S > 0 → decrement and proceed.
○ If S = 0 → process waits un l resource is free. No process are nin suspend list
○ If S<0 --> this no of process are on suspend list
2. Signal (V operation / up/ post/ release): exit section
signal(S):
S=S+1
○ Increments the semaphore value.
○ Wakes up a waiting process if any.

🔹 Problems with Semaphores

1. Busy Waiting (Spinlock):
○ Wastes CPU cycles while continuously checking.
○ Solution → use blocking instead of busy waiting.
2. Deadlock:
○ If processes wait for each other indefinitely.
○ Example: Process A locks resource1 and waits for resource2, while Process B locks resource2 and waits for resource1.
3. Starvation:
○ Some processes may wait indefinitely if scheduling is unfair.

✅ In Short (Exam Answer):

• A semaphore is a synchronization tool with wait (P) and signal (V) operations.
• Binary semaphore → mutual exclusion.
• Counting semaphore → mul ple resources.
• Used to solve critical section problems, prevent race conditions, but can lead to deadlock/starvation if not designed properly.

Deadlock
A deadlock is a situation in which a set of processes are blocked because each process is holding a resource and waiting for another resource
held by some other process.
• In short: Circular waiting → No one proceeds → System stuck.

Necessary Conditions for Deadlock (Coffman’s Conditions)

For deadlock to occur, all these 4 conditions must hold simultaneously:
1. Mutual Exclusion → At least one resource must be held in a non-sharable mode. (Only one process can use at a time).
2. Hold and Wait → A process holding at least one resource is wai ng to acquire addi onal resources held by others.
3. No Preemption → A resource cannot be forcibly taken away from a process; it can only be released voluntarily.
4. Circular Wait → A set of processes {P1, P2, …, Pn} exist such that P1 waits for a resource held by P2, P2 waits for a resource held by P3, … Pn
waits for a resource held by P1.
⚡If any one of these conditions is prevented, deadlock cannot occur.

Methods of Handling Deadlock

1. Deadlock Prevention (Prevent at least one Coffman condition):

Page 25
1. Deadlock Prevention (Prevent at least one Coffman condition):
○ Mutual Exclusion: Not always possible (printers, etc.).
○ Hold & Wait: Require processes to request all resources at once.
○ No Preemption: Allow resource preemption.
○ Circular Wait: Impose an ordering of resources, and processes can only request resources in increasing order.
2. Deadlock Avoidance (Safe state check):
○ Uses Banker’s Algorithm.
○ Before allocating resources, check if system will remain in a safe state.
○ Safe state → At least one sequence of process execu on exists where all processes complete.
3. Deadlock Detection & Recovery:
○ Allow deadlock to occur, then detect using a Wait-for Graph (nodes = processes, edges = wait).
○ Recovery: Kill processes or preempt resources.
4. Ignore Deadlock:
○ Many OS (like UNIX, Windows) just ignore deadlock because handling is costly and rare.
Resource Allocation Graph (RAG / RG)
A Resource Allocation Graph is a directed graph used to represent the state of a system in terms of processes and resources. It is mainly used
for deadlock detection and prevention.

Components:
1. Processes (P1, P2, …, Pn) → represented as circles.
2. Resources (R1, R2, …, Rm) → represented as rectangles.
○ Each rectangle has small dots inside, representing instances of that resource.
3. Edges:
○ Request edge (Pi → Rj): Process Pi is requesting resource Rj.
○ Assignment edge (Rj → Pi): Resource Rj is assigned to process Pi.

Deadlock in RAG:
• If the graph has no cycle → No deadlock.
• If the graph has a cycle →
○ Single instance per resource: Cycle = Deadlock.
○ Multiple instances per resource: Cycle may or may not be a deadlock.

Example:
1. Process P1 requests R1
(P1 → R1 edge drawn).
2. R1 allocated to P2
(R1 → P2 edge drawn).
3. If P2 is waiting for R2, and R2 is allocated to P1 → A cycle is formed → Deadlock occurs.

For mininum no of resource allocation request not to have a deadlock follow the below method,

Page 26
Memory Management in OS
Memory management is the process of allocating and deallocating memory to processes efficiently so that CPU utilization is maximized and
response time is minimized.
Two Major Types:

1. Contiguous Memory Allocation

• Definition: Each process is allocated a single continuous block of memory.
• Requirement: The whole process must fit into a single block.
• Used in: Early operating systems.
Techniques:
1. Fixed Partitioning
○ Memory is divided into fixed-size partitions.
○ Size of partition may and maynot be same.
○ One process per partition.
○ Spanning is not allowed that is we cant store portion of processes in diff diff positions
○ Problem: Internal fragmentation (unused space inside allocated block).
 Limit in process size
 Degree of multiprogramming is lmtd,
2. Dynamic Partitioning
○ Memory divided dynamically depending on process size.
○ Uses allocation strategies:
 First Fit → Allocate the first hole big enough.
 Next fit- same as first fit but start searchingg always from last allocated hole using pointers
 Best Fit → Allocate the smallest hole big enough (may cause reduce fragmentation).
 Worst Fit → Allocate the largest hole (may leave usable space -> more frag).
○ Problem: External fragmentation (unused gaps between allocated blocks).

3. Compaction
○ Process of shifting processes to remove external fragmentation.
○ Undesirable as we need to stop running process also
○ Allocation and deallocation process is complex so bitmap and linked list is used.

2. Non-Contiguous Memory Allocation

• Definition: A process is allowed to occupy multiple non-contiguous blocks in memory.
• Advantage: Avoids external fragmentation, allows better utilization.
• Used in: Modern OS.
Techniques:
1. Paging
○ Memory divided into fixed-size blocks:
 Logical memory that is secondary memory → Pages.
Physical memory that is RAM→ Frames.
Page 27
  Physical memory that is RAM→ Frames.
 Page size = frame size
 Main memory is byte addressable.
 Size of process/ Page size = No of pages
○ OS maintains a page table mapping pages to frames.
○ Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory.
○ It allows a process’s logical address space to be non-contiguous, while mapping it onto physical memory.
○ Used to solve external frag but can cause internal frag
○ Managed by MMU
1. Address Translation
○ Logical Address = (page number, page offset)
○ Physical Address = (frame number, page offset)
○ CPU generates logical address → MMU (Memory Management Unit) translates to physical or absolute address using page table.
2. Important Components
○ Page Table: Keeps track of where each page of a process is stored in physical memory. Or main memory or ram
○ Each process has its own page table
○ No of entries in page table= no of pages in process
○ Page Number (p): Index into page table.
○ Page Offset (d): Displacement within the page.
○ The above two are wrt to logical address before mmu converted it to physical address, after that pages = frames so below are the
terms.
○ Frame Number (f): Index of physical memory frame.
○ Frame Offset(d) - Displacement
○ Page offset= frame offset

3.

4. Advantages of Paging
○ No external fragmentation (only internal fragmentation).
○ Efficient use of memory.
○ Easy process swapping.
○ Supports virtual memory.
5. Disadvantages of Paging
○ Overhead of maintaining page tables.
○ Internal fragmentation (last page may not fully use frame).
○ Slower memory access (extra lookup in page table).
○ Large processes → large page tables.
6. Types of Paging
○ Simple Paging: Single-level page table.
○ Multilevel Paging: Page table itself paged foreasy storage in RAM (reduces memory overhead).
○ Inverted Page Table: One entry per frame, not per page (saves space). That is it creates global page table for all the process. So not
of entries = no of frames.
○ Demand Paging: Load pages into memory only when needed (used in virtual memory).
7. Page Replacement Algorithms (for demand paging)
○ FIFO (First In First Out)
○ LRU (Least Recently Used)
○ Optimal Page Replacement
○ Clock Algorithm
8. Performance Factors
○ Hit Ratio = fraction of memory accesses found in TLB/cache.
○ Effective Access Time (EAT) =
EAT = (Hit Ratio × TLB Access Time) + (Miss Ratio × (TLB Time + Memory Time))
○ Solves external fragmentation, but may cause internal fragmentation.
2. Segmentation
Segmentation is a memory management technique in which a process is divided into different segments based on the logical divisions of a
program such as code, data, stack, heap, etc.
Unlike paging (which divides memory into fixed-size blocks), segmentation divides it into variable-sized blocks depending on the program’s
needs.
CPU has no idea of segmentation it is also done by MMU like paging

Key Features
Page 28
 Key Features
1. Logical Division – Program is divided into meaningful units (e.g., functions, arrays, objects).
2. Variable Size – Each segment can have a different size.
3. Segment Table – Maintains:
○ Segment Number (ID)
○ Base Address (starting address of segment in physical memory)
○ Limit (Length) (size of segment)
4. Addressing in Segmentation – A logical address has two parts:
○ Segment Number
○ Offset (Displacement within segment)
Then,
Physical Address = Base Address (from Segment Table) + Offset
5. Protection – Each segment can have protection bits (read/write/execute). Also called d bits which telll how to read… and until where.

Advantages
• Reflects programmer’s view of memory (logical grouping).
• Supports dynamic growth (stack, heap).
• Easier to apply protection and sharing (e.g., two processes sharing a code segment).

Disadvantages
• Leads to external fragmentation (since segments are variable size).
• Harder memory allocation compared to paging.

Comparison with Paging

Paging Segmentation
Fixed-size blocks Variable-size blocks
Programmer unaware Programmer aware (logical divisions)
Eliminates external fragmentation Suffers from external fragmentation
Internal fragmentation possible No internal fragmentation

👉 Example:
If a process has 3 segments:
• Segment 0 (Code) – 2 KB
• Segment 1 (Data) – 1.5 KB
• Segment 2 (Stack) – 1 KB
Segment table will map each segment’s base + limit, and logical address (segment no, offset) is translated accordingly.
3. Paged Segmentation (Hybrid)
○ Combines both paging + segmentation.
○ Each segment is divided into pages.

Thrashing in OS
Definition
Thrashing is a situation in virtual memory management where the system spends more time swapping pages between main memory and
disk (paging) than executing the actual process instructions.

Why does Thrashing occur?

1. High Degree of Multiprogramming
○ Too many processes are in memory, competing for limited frames.
2. Insufficient Frames
○ A process does not have the minimum number of frames it needs → frequent page faults.
3. Poor Page Replacement Policy
○ Bad decisions on which pages to swap increase page faults.

Symptoms of Thrashing
• CPU utilization decreases (because CPU is waiting for I/O due to page faults).
• High page fault rate.
• System becomes slow and unresponsive.

Example Flow
Page 29
Example Flow
1. Multiprogramming ↑
2. More processes → fewer frames per process
3. Page fault rate ↑↑
4. CPU utilization ↓
5. OS may try to increase multiprogramming (wrong decision)
6. Leads to vicious cycle → Thrashing

How to Control Thrashing?

1. Local Replacement Policy – Replace pages of the faulting process only, not from others.
2. Working Set Model – Allocate enough frames to cover the process’s current working set.
3. Page Fault Frequency (PFF) – Monitor page fault rate:
○ If too high → increase frames.
○ If too low → decrease frames.
4. Reduce Degree of Multiprogramming – Suspend some processes.
5. Increase memory size
Okay Sassy 🚀 let’s nail this. Here’s a clear & exam-ready note on Virtual Memory 👇

Virtual Memory in OS
Definition
Virtual memory is a memory management technique that provides an illusion of a large main memory to the user by combining hardware
(MMU), software (OS), and secondary storage (disk).
It allows programs to execute even if they are larger than the physical RAM available.

Key Concepts
1. Address Space
○ Logical (Virtual) Address Space: Generated by the CPU (seen by processes).
○ Physical Address Space: Actual location in main memory (RAM).
○ Virtual memory maps logical addresses to physical addresses using page tables.
2. Demand Paging
○ Only required pages of a program are loaded into RAM.
○ Rest are kept on the disk until needed.
○ Reduces memory usage.
3. Page Fault
○ Occurs when a program accesses a page not present in RAM.
○ OS fetches the page from secondary storage → loads it into RAM.
4. Thrashing
○ If too many page faults occur, the CPU spends more time swapping pages than executing instructions → severe performance drop.
5. Page Replacement Policies
○ Decide which page to remove from RAM when space is needed:
 FIFO (First-In-First-Out)
 LRU (Least Recently Used)
 Optimal Page Replacement

Effective Access Time (EAT)

Definition:
Effective Access Time (EAT) is the average time required to access a memory location, considering both:
1. TLB (Translation Lookaside Buffer) lookup, and
• TLB (Translation Lookaside Buffer) is a high-speed cache inside the MMU (Memory Management Unit).
• It stores recently used virtual-to-physical address translations (page table entries).
• Purpose: To avoid accessing the page table in main memory every time we need to translate an address.
2. Main memory access (with or without page fault).
It measures the performance of virtual memory systems where address translation and caching occur.

Important Terminologies
1. Memory Access Time (m)
○ Time required to access data from main memory.
○ Example: 100 ns.
2. TLB Access Time (t)
○ Time required to check the Translation Lookaside Buffer.
○ Example: 10 ns.
3. Hit Ratio (h)
○ Probability that the page number is found in the TLB.
○ Range: 0 ≤ h ≤ 1.
Example: h = 0.9 (i.e., 90% times address found in TLB).

Page 30
 ○ Example: h = 0.9 (i.e., 90% times address found in TLB).
4. Miss Ratio (1 – h)
○ Probability that the page number is not found in TLB.
5. Page Fault Rate (p)
○ Probability that the required page is not in memory.
○ Example: p = 0.001.
6. Page Fault Service Time (S)
○ Extra time needed to handle a page fault (fetch page from disk).
○ Disk access is very slow (in ms).

EAT Calculation
Case 1: Without Page Faults (only TLB and Memory)
EAT = (h × (t + m)) + ((1 – h) × (t + 2m))
Explanation:
• If TLB Hit → Need TLB lookup + 1 memory access → (t + m).
• If TLB Miss → Need TLB lookup + 2 memory accesses (page table + data) → (t + 2m).

Case 2: With Page Faults

EAT = (1 – p) × [ (h × (t + m)) + ((1 – h) × (t + 2m)) ] + (p × S)
Explanation:
• With probability (1 – p), no page fault → normal access (using TLB).
• With probability (p), page fault occurs → service me (S).

Example
Suppose:
• m = 100 ns
• t = 10 ns
• h = 0.9
• p = 0 (no page fault)
EAT = (0.9 × (10 + 100)) + (0.1 × (10 + 200))
EAT = (0.9 × 110) + (0.1 × 210)
EAT = 99 + 21
EAT = 120 ns

Advantages of Virtual Memory

• Program size > Physical RAM is possible.
• Better CPU utilization (multiple processes can run).
• Isolation & Protection: Each process has its own address space.

Disadvantages
• More page faults can cause slower performance.
• Thrashing in case of improper allocation.
• Requires extra hardware support (MMU).

Page Fault in Operating System (OS):

When a process tries to access a page (part of memory) that is not currently present in the main memory (RAM), a page fault occurs.
Steps in Page Fault Handling:
1. Process requests a page that is not in RAM.
2. Hardware traps to the OS → OS detects a page fault.
3. OS checks if the memory reference is valid:
○ If invalid → process is terminated (segmenta on fault).
○ If valid → OS must bring the required page from secondary storage (disk) into RAM.
4. If free frame is available → load the page into it.
5. If no free frame → OS uses a page replacement algorithm (e.g., FIFO, LRU) to evict an existing page.
6. Page table is updated.
7. Process restarts the instruction that caused the page fault.

Types of Page Faults:

1. Minor Page Fault (soft) → Page is not in memory but can be loaded quickly (e.g., in swap space).
2. Major Page Fault (hard) → Page is not in memory and must be fetched from disk (slow).
3. Invalid Page Fault → Process accesses an invalid memory address → leads to termina on.

Impact of Page Faults:

• Few page faults → system runs fine.
• Excessive page faults → Thrashing (CPU spends more time handling faults than executing processes).

Page 31
• Excessive page faults → Thrashing (CPU spends more time handling faults than executing processes).
Definition
• Roll-In Roll-Out is a swapping technique used in multiprogramming OS.
• Here, processes are moved between main memory (RAM) and backing store (disk/secondary storage) to make space for other processes.

Roll-In
• When a process is swapped out of main memory into secondary storage.
• Usually done when memory is full, or a higher-priority process needs to be loaded.
• Example: Process P1 is paused and copied from RAM → Disk.

Roll-Out
• When a process that was previously swapped out is brought back into main memory from secondary storage so it can continue execution.
• Example: P1 is needed again → Disk → RAM.

Use Case
• Used when there is memory shortage and multiple processes are competing for CPU.
• Allows the system to temporarily suspend some processes and later resume them.

Key Points
• It increases degree of multiprogramming but also increases overhead (because swapping takes time).
• Usually combined with scheduling (like priority scheduling).
• High-priority processes may roll out lower-priority ones.

Page Replacement
When a process tries to access a page that is not present in main memory (RAM), a page fault occurs.
If the memory (frames) is full, the operating system needs to replace one of the existing pages in memory with the new page from disk.
The decision of which page to replace is made by a Page Replacement Algorithm.

Key Terms:
1. Page Fault – When the required page is not in RAM.
2. Frame – A fixed-size block of physical memory.
3. Page – A fixed-size block of logical (virtual) memory.
4. Page Replacement Algorithm – Strategy to select which page should be replaced.

Objectives of Page Replacement:

• Minimize the number of page faults.
• Improve CPU utilization.
• Balance between speed (less replacement overhead) and fairness (not always evicting same process’s pages).

Common Page Replacement Algorithms:

1. FIFO (First-In, First-Out)
○ Oldest page (brought earliest into memory) is replaced first.
○ Easy to implement using a queue.
○ Problem: Belady’s Anomaly (increasing frames may increase page faults).

2. Optimal Page Replacement

Replace the page that will not be used for the longest time in future.
Page 32
 ○ Replace the page that will not be used for the longest time in future.
○ Gives minimum possible page faults.
○ Not practically implementable (requires future knowledge).
○ Used as a benchmark.

1. LRU (Least Recently Used)

○ Replace the page that was used least recently in the past.
○ Based on principle of locality (recently used pages are more likely to be used again).
○ Implementation using stack or counters.
○ More practical than Optimal.

2.

3. LFU (Least Frequently Used)

○ Replace the page with the least number of accesses.
○ Requires frequency count of accesses.
○ May not always work well (e.g., pages used heavily in past but not now may stay unnecessarily).
4. MRU (Most Recently Used)
○ Opposite of LRU: replaces the most recently used page.
○ Works well in certain scenarios where old pages are more likely to be used again.
5. Random Page Replacement
○ Replace a randomly chosen page.
○ Simple, but not efficient.

Performance Evaluation:
• Page Fault Rate = (Number of page faults) / (Total memory accesses).
• Lower page fault rate ⇒ Better performance.

Disk Architecture – OS Notes

1. Introduction
○ Disk is the secondary storage device widely used in computers.
Unlike main memory (volatile), disks are non-volatile and can permanently store data.

Page 33
 ○ Unlike main memory (volatile), disks are non-volatile and can permanently store data.
○ OS manages disk space and scheduling for efficient I/O operations.

1. Disk Structure
A magnetic disk has several components:
○ Platter: Circular disk made of magnetic material. Data is stored on the platter surface.
○ Track: Concentric circles on a platter surface.
○ Sector: Subdivision of a track (smallest unit of data storage, typically 512B or 4KB).
○ Cylinder: Set of tracks at the same position across all platters.
○ Head: Reads/writes data on a platter surface.
○ Arm: Holds the head and moves it across tracks.
○ Spindle: Rotates the platters at constant speed (e.g., 5400 rpm, 7200 rpm).

1. Disk Addressing
○ Data is accessed using CHS (Cylinder, Head, Sector) or more commonly Logical Block Addressing (LBA).
○ LBA treats the disk as a linear array of blocks (simplifies addressing).

1. Disk Performance Parameters

○ Seek Time: Time taken for the head to move to the required track.
○ Rotation time- time for one full rotation.
○ Rotational Latency: Time waiting for the required sector to rotate under the head. Half of rotation time.
○ Transfer Time: Time to actually read/write data from disk surface. Data to be transferred / transfer rate.
○ Controllers- software which controbl the components.
○ Disk Access Time = Seek Time + Rotational Latency + Transfer Time
○ Disk Bandwidth: Amount of data transferred per unit time.

1. Disk Scheduling Algorithms (to optimize performance)

○ FCFS (First Come First Serve) – simple, fair but not efficient.

○ SSTF (Shortest Seek Time First) – selects request closest to current head position.
○ SCAN (Elevator Algorithm) – head moves in one direction, services requests, then reverses.

Page 34
 ○ C-SCAN (Circular SCAN) – only services in one direction, provides uniform wait time.

○ LOOK and C-LOOK – optimized versions of SCAN and C-SCAN (stop at last request instead of end of disk).

1. Disk Management by OS
○ Disk formatting: Prepares disk into sectors and file system.
○ Boot block: Contains bootstrap loader.
○ Free space management: Keeps track of unused blocks.
○ File allocation methods:
 Contiguous
 Linked
 Indexed

1. RAID (Redundant Array of Independent Disks) – (optional, value addition)

○ Technique to improve reliability, performance using multiple disks.
○ RAID-0: Striping (performance, no redundancy).
○ RAID-1: Mirroring (data reliability).
○ RAID-5: Striping with parity (balance of performance + reliability).
File System in Operating System – Notes
1. Definition
• A File System is a method used by the operating system to store, organize, and manage data on storage devices like hard disks, SSDs, CDs,
etc.
• It defines how data is named, stored, accessed, updated, and managed.

2. Functions of a File System

• File Organization: Determines how files are stored on disk.
• Naming & Identification: Each file has a unique name (e.g., [Link]).
• Access Control: Ensures security, permissions (read/write/execute).
• Data Retrieval: Provides efficient access to data.
• Space Management: Keeps track of used/free disk space.
Page 35
• Space Management: Keeps track of used/free disk space.
• Metadata Management: Maintains info about files (size, type, creation date, etc.).

3. File Attributes (Metadata)

Stored in file control blocks (FCB) / inode:
• Name
• Type (text, binary, executable)
• Location (pointer to blocks)
• Size
• Protection (permissions)
• Timestamps (creation, modification, last access)

4. File Operations
• Create – make a new file.
• Open – load file into memory for use.
• Read/Write – access or modify contents.
• Seek – reposition file pointer.
• Delete – remove file.
• Close – release memory/resources after use.

5. Directory Structure
Directories = special files that hold metadata + list of files.
Types:
1. Single-level directory – one directory for all files (confusing in large systems).
2. Two-level directory – separate directory for each user.
3. Tree-structured directory – hierarchy like Windows Explorer.
4. Acyclic-graph directory – allows shared files via links.
5. General graph directory – includes cycles (requires garbage collection).

6. File Allocation Methods

How OS stores file blocks on disk:
1. Contiguous Allocation
○ Each file occupies a set of contiguous blocks.
○ Pros: Fast access (sequential + direct).
○ Cons: External fragmentation, resizing hard.
2. Linked Allocation
○ Each file is a linked list of disk blocks.
○ Pros: No external fragmentation, flexible large seek time.
○ Cons: Slow random access, pointer overhead.
3. Indexed Allocation
○ Each file has an index block containing pointers to its data blocks.
○ Pros: Supports direct access, no fragmentation. Best in 3
○ Cons: Index overhead for small files.

7. Free Space Management

OS keeps track of free blocks using:
• Bit Vector (bitmap of free/used blocks)
• Linked List (chain of free blocks)
• Grouping (store free block addresses in groups)
• Counting (track free blocks in continuous runs)

8. Types of File Systems

• FAT (File Allocation Table): Old, simple (used in Windows, USB drives).
• NTFS (New Technology File System): Windows, supports security, large files.
• ext2/ext3/ext4: Linux file systems.
• HFS+/APFS: macOS.
• ISO 9660: Optical disks (CD/DVD).

9. Mounting & Unmounting

• Mounting: Making a file system accessible at a directory point.
• Unmounting: Detaching it safely.

10. File Protection Mechanisms

• Access Control Lists (ACLs) – permissions (read, write, execute).
• Passwords – per-file or per-user.

Page 36
• Passwords – per-file or per-user.
• Encryption – protect file contents.
Here are detailed notes on Process Synchronization in Operating Systems (exam-oriented but clear enough for understanding):

Process Synchronization (OS Notes)

1. Introduction
• In a multiprogramming environment, multiple processes may execute concurrently and share system resources (CPU, memory, files, etc.).
• Process synchronization is the coordination of processes so that they can execute in a safe and consistent manner when sharing resources.
2. Race Condition
• Occurs when multiple processes access and manipulate shared data concurrently, and the final output depends on the execution order.
• Example: Two processes updating a shared variable x simultaneously → inconsistent result.
To avoid race condition → we need synchroniza on.
3. Critical Section Problem
• Critical Section (CS): A part of the program where shared resources are accessed.
• To ensure correctness, only one process should execute in CS at a time.
Structure of a process with CS:
do {
Entry Section // Request to enter CS
Critical Section // Access shared resource
Exit Section // Release CS
Remainder Section// Other code
} while (true);
4. Requirements for Critical Section Solution
A valid solution must satisfy:
1. Mutual Exclusion → Only one process at a me in CS.
2. Progress → If no process is in CS, decision of who enters next should not be delayed.
3. Bounded Waiting → Each process must get a chance within a bounded number of turns (no starva on).

5. Software Solutions
• Peterson’s Algorithm (for 2 processes).
• Dekker’s Algorithm.
• Both use variables (turn & flag) to ensure mutual exclusion.

6. Hardware Solutions

Page 37
6. Hardware Solutions
• Test-and-Set (TSL instruction) → atomic instruc on used for locks.
• Swap instruction → used in busy-wait locks.
Disadvantage: Leads to busy waiting (CPU wasted).

7. Synchronization Tools
1. Semaphores (Dijkstra):
○ Integer variable used for signaling.
○ Types: Counting Semaphore & Binary Semaphore (mutex).
○ Operations:
wait(S): while S <= 0; S--;
signal(S): S++;
○ Used for mutual exclusion and process coordination.
2. Mutex Locks:
○ Special kind of binary semaphore.
○ Provides mutual exclusion using acquire() and release().
○ Example: Used in thread libraries.
3. Monitors:
○ High-level synchronization construct.
○ Allows only one process inside monitor at a time.
○ Uses condition variables (wait, signal) for coordination.

8. Classical Synchronization Problems

1. Bounded Buffer (Producer–Consumer Problem).
2. Dining Philosophers Problem.
3. Readers–Writers Problem.
4. Sleeping Barber Problem.
These are used to illustrate semaphore and monitor solutions.

9. Deadlock vs Synchronization
• Deadlock: Processes wait forever (circular waiting).
• Synchronization: Controlled access, prevents race conditions.>

Page 38