Operating Systems

Comprehensive Question & Answer Guide

Units 1 & 2 | Detailed Answers with Diagrams & Examples

Q1. Different Types of Operating Systems (Detailed) + Multiprogramming vs
Multitasking

1. Batch Operating System

In a batch operating system, jobs with similar needs are grouped (batched) together and executed as a
group without user interaction during execution. Users submit jobs (via punch cards earlier) to an
operator, who sorts them into batches.
• Advantages: High throughput, efficient CPU use for repetitive tasks
• Disadvantages: No real-time interaction; if a job fails, the rest of the batch is affected
• Examples: IBM's early mainframe systems, payroll processing

2. Multiprogramming Operating System

Multiple programs are loaded into memory simultaneously. When one process waits for I/O, the CPU is
switched to another, maximizing CPU utilization and system throughput.
• Multiple jobs reside in memory at one time
• CPU never sits idle; it switches to a ready process when current one waits
• Job scheduling is used to decide which job runs next
• Improves throughput and reduces CPU idle time

3. Time-Sharing (Multitasking) Operating System

A logical extension of multiprogramming where CPU switches among jobs so rapidly (time slices /
quanta) that each user appears to have dedicated access. Allows multiple users to interact
concurrently.
• Each user gets a short CPU time quantum (e.g., 10-100 ms)
• Response time is kept under 1 second
• Each user has at least one process in memory
• Examples: UNIX, Linux, Windows

4. Real-Time Operating System (RTOS)

Provides a guaranteed response within strict time constraints. Used in safety-critical or time-sensitive
systems.
• Hard Real-Time: Strict deadline; missing it is catastrophic (e.g., airbag systems, pacemakers)
• Soft Real-Time: Deadlines are goals; occasional misses are acceptable (e.g., multimedia
streaming)
• Examples: VxWorks, FreeRTOS, QNX
5. Distributed Operating System
Manages a group of independent computers and makes them appear to the users as a single coherent
system. Resources and computation are distributed across the network.
• Provides resource sharing, load balancing, and fault tolerance
• Communication via message passing
• Examples: Amoeba, LOCUS

6. Network Operating System

Manages network resources and provides services such as file sharing, printer sharing, and user
management over a network. Each computer retains its own local OS.
• Common in corporate and office environments
• Examples: Novell NetWare, Windows Server

7. Mobile Operating System

Designed specifically for smartphones and tablets, supporting touch input, wireless connectivity, and
battery optimization.
• Supports apps through app stores, GPS, sensors, and camera
• Examples: Android (Linux-based), iOS (Unix-based)

8. Embedded Operating System

A specialized OS designed for embedded systems like washing machines, microwave ovens, and
routers. Typically very lightweight.
• Examples: Embedded Linux, Windows CE

Difference: Multiprogramming vs Multitasking OS

Aspect Multiprogramming OS Multitasking (Time-Sharing)

OS
Primary Goal Maximize CPU utilization Provide interactive response
to multiple users
CPU Switching Switches when process waits Switches on time quantum
for I/O expiry (preemptive)
User Interaction No direct user interaction Users interact in real-time
during execution
Response Time Not a primary concern Must be < 1 second
Switching Basis Event-driven (I/O wait) Time-driven (time slice)
Focus Throughput efficiency User responsiveness
Example Early IBM batch systems UNIX, Linux, Windows
Q2. Services and Functions of an Operating System

An operating system provides two broad categories of services: (A) Services for users and programs,
and (B) Services for efficient system operation.

A. Services for Users

1. User Interface (UI)

Provides a means for users to interact with the system:
• Command-Line Interface (CLI): Users type commands. Faster for experts (e.g., Unix shell,
CMD)
• Graphical User Interface (GUI): Icons, windows, menus. User-friendly (e.g., Windows, macOS)
• Batch Interface: Commands and directives entered into files for later execution

2. Program Execution
The OS loads a program into memory, runs it, and handles normal/abnormal termination. It manages
the process lifecycle completely.

3. I/O Operations
Provides access to I/O devices (keyboard, disk, network). User programs do not directly control
devices; the OS intermediates to ensure safety and efficiency.

4. File-System Manipulation
Programs need to create, read, write, delete files and directories. The OS provides file system
management including permission control and directory organization.

5. Communications
Processes communicate either on the same computer or across a network. The OS supports:
• Shared Memory: Processes read/write a common memory region
• Message Passing: OS transfers packets of information between processes

6. Error Detection
The OS must detect and handle errors in CPU, memory hardware, I/O devices, and user programs. It
takes appropriate action to ensure consistent operation (e.g., halting a failing process).

B. Services for Efficient System Operation

7. Resource Allocation
When multiple processes run concurrently, the OS allocates resources (CPU cycles, memory, I/O
devices, files) fairly and efficiently. Allocation algorithms vary by resource type.

8. Accounting
The OS tracks which users use how much of which resources. Used for billing, system tuning, and
audit trails.

9. Protection and Security

• Protection: Controls access of processes or users to system resources
• Security: Defends against unauthorized external/internal access, viruses, and denial-of-service
attacks
• Uses User IDs, Group IDs, privilege levels, and authentication mechanisms

How Services Differ from Functions

Services (User-Facing) Functions (Internal System)

UI, Program Execution, I/O Ops Process Scheduling, Memory Management
File System Access Disk Space Management, File Allocation
Communication between processes Synchronization primitives, IPC mechanisms
Error reporting to users Hardware interrupt handling, error logging
Security for users/resources Privilege mode management, kernel protection
In essence: Services are the visible offerings the OS provides to users and programs; Functions are the
internal mechanisms the OS uses to deliver those services and maintain itself.
Q3. Major Operating System Structures with Diagrams

1. Simple / Monolithic Structure (e.g., MS-DOS)

The earliest OS design. All functionality is in a single layer without clear separation of concerns. The
OS and user programs share the same address space.
• No clear boundaries between user and kernel code
• Easy to implement, but hard to maintain and extend
• A bug anywhere can crash the whole system

MS-DOS Layered Structure (Diagram):

┌─────────────────────────────────────┐
│ Application Programs │
├─────────────────────────────────────┤
│ Resident System Programs │
├─────────────────────────────────────┤
│ MS-DOS Device Drivers │
├─────────────────────────────────────┤
│ ROM BIOS │
└─────────────────────────────────────┘

2. Layered Approach
The OS is divided into N layers. Layer 0 is hardware; Layer N is the user interface. Each layer uses
only services from the layer directly below it.
• Advantages: Modularity, easier debugging (one layer at a time)
• Disadvantages: Performance overhead from multiple layer traversals; difficult to define layer
boundaries

Layered OS Structure (Diagram):

│ Layer N : User Interface │
│ Layer N-1: I/O Management │
│ Layer N-2: Inter-process Communication │
│ Layer 2 : Memory Management │
│ Layer 1 : CPU Scheduling │
│ Layer 0 : Hardware │

3. UNIX / Traditional Monolithic Kernel

UNIX has two separable parts: system programs and the kernel. The kernel provides all OS services
(file system, CPU scheduling, memory management, etc.) in one large block below the system-call
interface.

Traditional UNIX Structure (Diagram):

┌───────────────────────────────────────┐
│ Users / Application Programs │
├───────────────────────────────────────┤
│ Shells / Compilers / Libraries │
 ├───────────────────────────────────────┤
│ System Call Interface │
├─────────────────┬─────────────────────┤
│ File Subsystem │ Process Control │
│ (File Mgmt,I/O) │ (Sched, Mem, IPC) │
├─────────────────┴─────────────────────┤
│ Hardware (CPU, Memory, I/O) │
└───────────────────────────────────────┘

4. Microkernel Structure
Moves as much functionality as possible out of the kernel into user space. The microkernel handles
only the most essential functions: basic inter-process communication, minimal memory management,
and basic scheduling.
• User-space servers handle file system, device drivers, network, etc.
• Communication via message passing
• Benefits: More reliable, secure, easier to port and extend
• Drawback: Performance overhead due to user-kernel space communication
• Examples: Mach, QNX, MINIX

Microkernel Structure (Diagram):

┌────────────────────────────────────────────┐
│ User Mode │
│ [File Server] [Device Driver] [Net Server]│
├────────────────────────────────────────────┤
│ Kernel Mode │
│ [Basic IPC] [Memory Mgmt] [CPU Sched] │
├────────────────────────────────────────────┤
│ Hardware │
└────────────────────────────────────────────┘

5. Modular / Loadable Kernel Modules (LKM)

Most modern OS (Linux, Solaris) use loadable kernel modules. The kernel has a core set of
components; additional services are loaded as modules at boot or runtime.
• Each module is independent and communicates over known interfaces
• More flexible than layers; modules can call each other freely
• Similar to microkernel but runs in kernel space (better performance)

6. Virtual Machine Structure

Treats hardware and the OS kernel as hardware. A virtual machine monitor (VMM or hypervisor)
provides each guest OS with a virtual copy of the physical machine.
• Allows multiple OSes to run on the same physical hardware
• Complete isolation between VMs
• Examples: VMware, VirtualBox, KVM, Xen
 Structure Key Idea Advantage Disadvantage
Simple/MS-DOS All in one layer Easy to implement Not secure,
unmaintainable
Layered N distinct layers Modularity, debugging Performance
overhead
UNIX Monolithic Large kernel Fast, efficient Hard to maintain
Microkernel Minimal kernel + user Reliable, portable Slow IPC overhead
services
Modular LKM Core + loadable Flexible, efficient Bugs in modules
modules crash kernel
Virtual Machine Virtualize hardware Isolation, portability Overhead
Q4. System Calls: Definition + Five Process-Related System Calls

Definition of System Call

A system call is a programmatic interface (API) through which a user-mode program requests a service
from the operating system kernel. Since user programs run in user mode (restricted), they cannot
directly access hardware or OS data structures. System calls provide a controlled entry point into the
kernel.
System calls are typically written in C or C++. Programs access them through high-level APIs:
• POSIX API (Linux/Unix systems)
• Win32 API (Windows systems)
• Java API (JVM-based programs)

Mechanism:
When a system call is made, the CPU switches from user mode to kernel mode (via a trap/interrupt),
executes the requested service, then returns to user mode. A system call number indexes into a
system call table that maps to the kernel function.

Five Process-Related System Calls

1. fork()
Creates a new child process by duplicating the calling (parent) process.
• The child gets a copy of the parent's address space (code, data, stack)
• Returns 0 to child, child's PID to parent, -1 on error
• Child and parent execute concurrently after fork()

Example (C Code):
pid_t pid = fork();
if (pid == 0) { /* Child process */ }
else { /* Parent process */ }

2. exec()
Replaces the current process's memory image with a new program. Often called after fork() to load a
different program into the child process.
• exec() family includes: execl(), execv(), execle(), execve(), execlp(), execvp()
• Does not return on success; the process's code, data, heap, and stack are replaced
• PID remains the same after exec()

Example (C Code):
execlp("/bin/ls", "ls", NULL); // Replace process with 'ls' command
3. wait() / waitpid()
Causes the parent process to suspend execution until one of its child processes terminates. Used to
collect the exit status of child processes and prevent zombie processes.
• wait(NULL) waits for any child to finish
• waitpid(pid, status, options) waits for a specific child
• Returns the PID of the terminated child

Example (C Code):
int status;
pid_t child = wait(&status); // Parent waits

4. exit()
Terminates the calling process and returns an exit status to the parent. The OS reclaims all resources
(memory, file descriptors) allocated to the process.
• exit(0) typically means success; non-zero means error
• Triggers cleanup of atexit() registered functions and flushes stdio buffers
• Parent receives the exit status via wait()

Example (C Code):
exit(0); // Normal termination
exit(1); // Abnormal termination

5. getpid() / getppid()
Returns the Process ID (PID) of the calling process or its parent's PID (PPID). PIDs are used by the OS
to uniquely identify and manage processes.
• getpid(): Returns current process's PID
• getppid(): Returns parent process's PID
• Useful in fork() logic to distinguish parent and child

Example (C Code):
pid_t my_pid = getpid();
pid_t parent_pid = getppid();

System Call Purpose Returns

fork() Create a new child process 0 (child), PID (parent), -1
(error)
exec() Replace process image with new program Does not return on success
wait() Parent waits for child to terminate PID of terminated child
exit() Terminate calling process Exit status to parent via
 System Call Purpose Returns
wait()
getpid() Get process ID of calling process Integer PID
Q5. Process State Transition Diagram and Explanation

Five Process States

A process passes through several states during its lifetime:
• New: The process is being created
• Ready: The process is waiting to be assigned to a CPU (in memory, ready to execute)
• Running: Instructions are being executed on the CPU
• Waiting (Blocked): The process is waiting for an event (I/O completion, signal)
• Terminated: The process has finished execution

Process State Transition Diagram:

Admitted
┌─────┐ ─────────────────────► ┌───────┐
│ NEW │ │ READY │
└─────┘ └───┬───┘
Scheduler│ ▲ Interrupt /
Dispatch │ │ I/O Complete
▼ │
┌──────────┐ ┌──────────────────┐
│ WAITING │ ◄──────── │ RUNNING │
│(BLOCKED) │ I/O Req. │ (On CPU) │
└──────────┘ └────────┬─────────┘
│ Exit
▼
┌────────────┐
│ TERMINATED │
└────────────┘

Explanation of Transitions

Transition From → To Cause

Admitted New → Ready Process is created and loaded into memory;
admitted to ready queue
Dispatch (Schedule) Ready → Running CPU scheduler selects this process and assigns
CPU to it
Interrupt / Time Running → Ready Timer interrupt fires (time slice over) or higher-
Quantum Expiry priority process arrives; process preempted
I/O Request / Wait Running → Waiting Process requests I/O or waits for an event (e.g.,
disk read); cannot continue until event occurs
I/O Completion Waiting → Ready The awaited event (I/O) completes; process
moves back to ready queue
Exit / Terminate Running → Terminated Process finishes execution or is killed; OS
reclaims resources
Note: A process can only run from the Running state. It cannot go directly from Waiting to Running; it
must pass through Ready first.
Q6. Short-Term, Medium-Term, and Long-Term Scheduling

1. Long-Term Scheduler (Job Scheduler)

Selects which processes from the job pool (on disk) should be brought into main memory (ready
queue). It controls the degree of multiprogramming.
• Invocation frequency: Infrequently (seconds to minutes)
• Can afford to be slow and take time making decisions
• Controls the mix of I/O-bound and CPU-bound processes for balance
• Goal: Maximize CPU utilization by maintaining the right degree of multiprogramming

2. Short-Term Scheduler (CPU Scheduler)

Selects which process from the ready queue should be executed next by the CPU. This is the most
frequently invoked scheduler.
• Invocation frequency: Very frequently (every few milliseconds)
• Must be very fast to minimize overhead (dispatch latency)
• Uses scheduling algorithms: FCFS, SJF, Priority, Round-Robin
• Goal: Maximize CPU efficiency and minimize waiting time

3. Medium-Term Scheduler (Swapper)

Temporarily removes (swaps out) processes from memory to disk to reduce the degree of
multiprogramming, and reintroduces them later (swap in). Introduced to handle memory pressure.
• Invocation frequency: Moderate (between short and long term)
• Improves process mix and frees memory during congestion
• Key concept: Swapping - moving a process to/from disk to free/restore memory
• Goal: Manage memory efficiently during high load

Aspect Long-Term Short-Term Medium-Term

Also Known As Job Scheduler CPU Scheduler Swapper
Selects From Job pool (disk) Ready queue Swapped-out
processes
Selects For Main memory (ready CPU execution Memory (swap in)
queue)
Invocation Frequency Infrequent (min/sec) Very frequent (ms) Moderate
Speed Required Can be slow Must be fast Moderate
Controls Degree of CPU allocation Memory load
multiprogramming
Present in all OS? Not always (batch Always Time-sharing OS
Aspect Long-Term Short-Term Medium-Term
OS)
Q7. CPU Scheduling Algorithms with Solved Problems

Key Metrics
• CPU Utilization: Percentage of time CPU is busy
• Throughput: Number of processes completed per unit time
• Turnaround Time: Total time from submission to completion (waiting + execution + I/O)
• Waiting Time: Time spent in the ready queue waiting for CPU
• Response Time: Time from submission to first response

1. First-Come, First-Served (FCFS)

Processes are executed in the order they arrive (FIFO queue). Non-preemptive.

Example:
Process Burst Time Arrival Time
P1 24 ms 0
P2 3 ms 0
P3 3 ms 0

Gantt Chart: P1(0-24) | P2(24-27) | P3(27-30)

Waiting Times: P1=0, P2=24, P3=27 | Average Waiting Time = (0+24+27)/3 = 17 ms
• Advantage: Simple, easy to implement
• Disadvantage: Convoy effect; long processes delay short ones

2. Shortest Job First (SJF)

Assigns CPU to process with smallest next CPU burst. Optimal for minimum average waiting time. Can
be preemptive (SRTF) or non-preemptive.

Example (Non-preemptive SJF):

Process Burst Time
P1 6 ms
P2 8 ms
P3 7 ms
P4 3 ms

Gantt Chart: P4(0-3) | P1(3-9) | P3(9-16) | P2(16-24)

Waiting Times: P1=3, P2=16, P3=9, P4=0 | Average = (3+16+9+0)/4 = 7 ms
• Advantage: Minimum average waiting time; provably optimal
• Disadvantage: Cannot know future CPU burst lengths; may cause starvation of long processes

3. Priority Scheduling
Each process has a priority. CPU is assigned to the highest-priority process. Ties broken by FCFS. Can
be preemptive or non-preemptive.

Example:
Process Burst Time Priority
P1 10 ms 3
P2 1 ms 1 (highest)
P3 2 ms 4
P4 1 ms 5 (lowest)
P5 5 ms 2

Gantt Chart: P2(0-1) | P5(1-6) | P1(6-16) | P3(16-18) | P4(18-19)

Waiting Times: P1=6, P2=0, P3=16, P4=18, P5=1 | Average = 41/5 = 8.2 ms
• Problem: Starvation - low-priority processes may never run
• Solution: Aging - gradually increase priority of waiting processes

4. Round-Robin (RR)
Designed for time-sharing. Each process gets a fixed time quantum (e.g., 4 ms). After its quantum, it's
preempted and placed at the end of the ready queue. Preemptive.

Example (Time Quantum = 4 ms):

Process Burst Time
P1 24 ms
P2 3 ms
P3 3 ms

Gantt Chart: P1(0-4) | P2(4-7) | P3(7-10) | P1(10-14) | P1(14-18) | P1(18-22) | P1(22-26) | P1(26-30)
Waiting Times: P1=6, P2=4, P3=7 | Average = 17/3 = 5.66 ms
• Advantage: Fair; no starvation; good for time-sharing
• Disadvantage: Higher average turnaround time; quantum size critical
5. Multilevel Queue Scheduling
Ready queue is split into multiple queues by process type (system, interactive, batch, student). Each
queue has its own algorithm. Processes are permanently assigned to a queue.
• Foreground (interactive) queue: RR scheduling
• Background (batch) queue: FCFS scheduling
• Each queue has priority; starvation possible for lower queues

6. Multilevel Feedback Queue

Extends multilevel queue by allowing processes to move between queues based on CPU usage. Long
processes move to lower-priority queues; short/I/O-bound stay high.
• A new process enters Queue 0 (highest priority, quantum=8 ms)
• If not done, moves to Queue 1 (quantum=16 ms)
• If still not done, moves to Queue 2 (FCFS)
Q8. Threading Models: Diagrams, Advantages, and Disadvantages

Background: User vs Kernel Threads

• User-Level Threads: Managed by a user-space thread library; OS is unaware of them
• Kernel-Level Threads: Managed by the OS kernel; OS schedules them

1. Many-to-One Model
Many user-level threads are mapped to a single kernel thread. Thread management is done in user
space.

Diagram:
User Space: [T1] [T2] [T3] [T4]
\ | | /
Kernel Space: [K1]

Advantages Disadvantages
Efficient thread management in user space If one thread blocks on I/O, all threads block
No kernel involvement for context switch Cannot run threads in parallel on multicore
Portable across OS Limited scalability
Examples: Solaris Green Threads, GNU Portable Threads

2. One-to-One Model
Each user-level thread maps to exactly one kernel thread. The kernel schedules each thread
independently.

Diagram:
User Space: [T1] [T2] [T3]
| | |
Kernel Space: [K1] [K2] [K3]

Advantages Disadvantages
True parallelism on multicore processors Creating many threads creates many kernel
threads (overhead)
One thread blocking does not block others System may limit the number of kernel threads
Better concurrency support More expensive context switching
Examples: Linux, Windows NT/XP/2000
3. Many-to-Many Model
Many user-level threads are multiplexed onto an equal or smaller number of kernel threads. The OS
creates as many kernel threads as needed.

Diagram:
User Space: [T1] [T2] [T3] [T4] [T5]
\ | \ / | /
Kernel Space: [K1] [K2] [K3]

Advantages Disadvantages
Combines benefits of both models Complex to implement
Can create as many user threads as needed Requires kernel-user coordination (scheduler
activations)
Threads can run in parallel Debugging is harder
Examples: Solaris (prior to v9), Windows with ThreadFiber

4. Two-Level Model
Similar to Many-to-Many, but also allows a specific user thread to be bound to a specific kernel thread
(one-to-one binding when needed). Provides flexibility.
• Can use M:M for most threads and 1:1 for real-time or critical threads
• Examples: IRIX, HP-UX, Tru64 UNIX, Solaris 8 and earlier

Model Mapping Parallelism Blocking Complexity

Many-to-One N:1 No All block if one blocks Low
One-to-One 1:1 Yes Independent Medium
Many-to-Many N:M Yes Independent High
Two-Level N:M + 1:1 Yes Independent Very High
Q9. Inter-Process Communication (IPC) Mechanisms

Inter-Process Communication (IPC) refers to mechanisms that allow processes to communicate and
synchronize with each other. Two fundamental models exist:
• Shared Memory: A region of memory shared between processes
• Message Passing: Processes communicate by sending/receiving messages

1. Shared Memory
A shared memory region is created in the address space accessible to multiple cooperating processes.
Processes read and write to this common area directly.

Block Diagram:
┌───────────┐ ┌──────────────────┐ ┌───────────┐
│ Process A │ ───► │ SHARED MEMORY │ ◄─── │ Process B │
│(Producer) │ │ (Common Buffer) │ │(Consumer) │
└───────────┘ └──────────────────┘ └───────────┘

• Advantage: Fastest IPC method (no kernel involvement after setup)

• Disadvantage: Requires explicit synchronization; risk of race conditions
• System Calls: shmget(), shmat(), shmdt(), shmctl() on UNIX

2. Message Passing
Processes communicate by sending and receiving messages through the OS. No shared variable
needed. Useful in distributed systems.

Block Diagram:
┌───────────┐ send(msg) ┌─────────────┐ recv(msg) ┌───────────┐
│ Process A │ ──────────────► │ Message │ ─────────────► │ Process B │
└───────────┘ │ Queue/Link │ └───────────┘
└─────────────┘

• Direct Communication: Sender explicitly names recipient (send(P, msg))

• Indirect Communication: Messages sent through mailboxes/ports (send(mailbox, msg))
• Synchronous (Blocking): Sender waits until receiver gets message
• Asynchronous (Non-blocking): Sender continues; message buffered

3. Pipes
A pipe is a unidirectional communication channel between two related processes (typically parent and
child). Data is written at one end and read from the other.

Block Diagram:
 ┌───────────┐ write(fd[1]) ┌──────────┐ read(fd[0]) ┌───────────┐
│ Process A │ ──────────────► │ PIPE │ ─────────────► │ Process B │
└───────────┘ └──────────┘ └───────────┘

• Ordinary (Anonymous) Pipes: Between parent and child; unidirectional

• Named Pipes (FIFOs): Independent processes can communicate; bidirectional
• System Calls: pipe(), read(), write(), close()

4. Sockets
A socket is an endpoint for communication. Two sockets (one at each end of the connection) form a
socket pair. Used for both local (Unix domain sockets) and network communication (TCP/IP).

Block Diagram:
┌─────────┐ Socket Pair ┌─────────┐
│ Host A │ ◄────────────────► │ Host B │
│IP:Port A│ Network/Local │IP:Port B│
└─────────┘ └─────────┘

• Supports both connection-oriented (TCP) and connectionless (UDP) communication

• Most common for distributed/network applications

5. Signals
Signals are software interrupts sent to a process to notify it of an event (e.g., SIGKILL, SIGTERM,
SIGSEGV). The process handles the signal via a signal handler.
• Asynchronous: Can arrive at any time
• Predefined signal set (kill -l lists all)
• Used for inter-process notification (e.g., parent notifying child)

IPC Mechanism Communication Type Best For

Shared Memory Direct, fast High-speed local IPC between related
processes
Message Passing Structured, indirect Distributed systems, loose coupling
Pipes Unidirectional stream Parent-child process communication
Named Pipes (FIFO) Bidirectional stream Unrelated processes on same machine
Sockets Bidirectional, networked Network communication, client-server
Signals Asynchronous notification Event notification, process control
Q10. Critical Section Problem + Producer-Consumer Solution with Semaphores

Critical Section Problem

When multiple processes access shared data concurrently, a race condition can occur - the outcome
depends on the order of execution. A critical section is a segment of code where a process accesses
shared resources (variables, files, data structures).

Requirements for a valid critical-section solution:

• Mutual Exclusion: Only one process can be in its critical section at a time
• Progress: If no process is in the critical section, processes wanting to enter should not be
indefinitely postponed
• Bounded Waiting: There must be a limit on the number of times other processes enter their
critical sections after a process has requested entry

Semaphores
A semaphore is a synchronization tool. It is an integer variable S accessed only through two atomic
operations:
• wait(S) [also called P(S) or down(S)]: Decrements S. If S <= 0, the process blocks
• signal(S) [also called V(S) or up(S)]: Increments S. May wake a blocked process

Types of Semaphores:
• Binary Semaphore (Mutex): Value is 0 or 1. Used for mutual exclusion
• Counting Semaphore: Can take any non-negative value. Used for resource counting

Producer-Consumer Problem (Bounded Buffer)

The Producer-Consumer problem involves two processes sharing a fixed-size buffer:
• Producer: Generates data items and places them in the buffer
• Consumer: Removes items from the buffer for processing

Constraints:
• Producer must not produce into a full buffer
• Consumer must not consume from an empty buffer
• Only one process should access the buffer at a time (mutual exclusion)

Semaphore-Based Solution
Three semaphores are used:
• mutex (binary): Initialized to 1 - ensures mutual exclusion on the buffer
 • empty (counting): Initialized to N (buffer size) - counts empty slots
• full (counting): Initialized to 0 - counts filled slots

Producer Process Code:

// Semaphores: mutex=1, empty=N, full=0
// Buffer size = N

Producer() {
while (true) {
produce_item(item); // Create a new item

wait(empty); // Decrement empty count

// Block if no empty slot
wait(mutex); // Enter critical section

add_item_to_buffer(item); // Place item in buffer

signal(mutex); // Leave critical section

signal(full); // Increment full count
}
}

Consumer Process Code:

Consumer() {
while (true) {
wait(full); // Decrement full count
// Block if no item available
wait(mutex); // Enter critical section

item = remove_item_from_buffer(); // Get item

signal(mutex); // Leave critical section

signal(empty); // Increment empty count

consume_item(item); // Process the item

}
}

How the Solution Works

Trace for Buffer of Size N=2:
Step Action empty full mutex Buffer
Initial Setup 2 0 1 [ ][ ]
Producer wait(empty) → empty=1, wait(mutex) 1 0 0 [ ][ ]
→ mutex=0
 Step Action empty full mutex Buffer
Producer add item A, signal(mutex)→1, 1 1 1 [A][ ]
signal(full)→1
Consumer wait(full)→0, wait(mutex)→0 1 0 0 [A][ ]
Consumer remove A, signal(mutex)→1, 2 0 1 [ ][ ]
signal(empty)→2

Critical Section Verification

• Mutual Exclusion: Guaranteed by mutex semaphore - only one process in buffer at a time
• Progress: Processes blocked only when buffer is full or empty - valid conditions
• Bounded Waiting: Semaphore queues ensure bounded waiting; no starvation

This semaphore-based solution is elegant, correct, and widely used in OS implementations for
producer-consumer style problems including disk I/O buffers, print spoolers, and network packet
queues.

--- End of Operating Systems Q&A Document ---