Operating Systems (CS-405) Unit 4 Notes - RGPV

How unit 4 is examined

This unit covers I/O methods (programmed, interrupt-driven, DMA, buffering, spooling) and concurrency: mutual exclusion, synchronization, semaphores and deadlocks; the marks sit in semaphores (dining philosophers), deadlocks (Coffman, Banker's, recovery), real vs virtual concurrency and synchronization.

Input / Output : Principles and Programming

Low weight

Definition. I/O programming is the way the CPU controls devices, using programmed I/O, interrupt-driven I/O or DMA, hidden behind a uniform device-independent interface.

Key points.

Programmed I/O makes the CPU poll the device status until it is ready, so the CPU is busy all the time.
Interrupt-driven I/O lets the CPU run other work and be interrupted by the device when it is ready.
DMA lets a controller move a whole block between device and memory without the CPU, which is interrupted only at the end.
The layers are user-level I/O software, device-independent OS software, device drivers, interrupt handlers and hardware.
A blocking interface suspends the calling process until the I/O completes, while a non-blocking interface returns at once with whatever is ready.

Asked: [7 marks] (Jun 2026) Explain I/O programming principles and I/O interfaces.

Input/Output Problems

Definition. I/O problems are the difficulties in handling devices: errors, wide speed differences and many device types.

Key points.

Transient errors such as a bad read are retried, while permanent errors such as a dead disk are reported to the user process.
The CPU is far faster than devices, which is solved by buffering, spooling and interrupts.
Devices differ in unit, code and speed, so drivers give one uniform view, and dedicated devices such as printers need spooling.

Asynchronous Operations

Definition. Asynchronous I/O is an operation where the process issues the request, continues running, and is told later by an interrupt, signal or callback that it has finished.

Key points.

The call is non-blocking, so CPU work and I/O overlap.
The process must check or be notified of completion, so control is more complex.
Concurrent I/O means several I/O operations are in progress at the same time on different devices.

Basis	Asynchronous I/O	Concurrent I/O
Meaning	Issuer does not wait for completion	Many I/O operations progress together
Overlap	CPU with I/O	I/O with I/O
Control	Completion signal or callback	Scheduling and locking of shared devices
Complexity	Callback handling	Synchronization of shared data
Performance	Better CPU use	Better throughput
Use	Network servers, GUI	Multi-disk servers, databases

Asked: [7 marks] (Jun 2026) Compare asynchronous and concurrent I/O operations.

Speed gap Format conversion

Definition. Buffering holds data in memory temporarily to smooth the speed gap between device and CPU, while spooling queues whole jobs on disk for a slow shared device such as a printer.

Key points.

Single buffering reads the next block while the current one is processed; double buffering alternates two buffers so device and CPU work fully in parallel; circular buffering uses many buffers in a ring.
Buffers also convert data size and format, for example bytes to blocks, between device and process.
Spooling stores print jobs on disk, and a spooler prints them one by one, so many processes share a non-shareable device.
Buffering works on one process's data in memory, whereas spooling works on complete jobs on disk and gives an illusion of a private device.
The buffer cache keeps recently used disk blocks in memory.
Buffer cache advantages: fewer disk accesses, faster repeated reads, delayed writes that combine updates, and one shared copy of a block for synchronization.
Buffer cache disadvantages: it uses memory, delayed writes can be lost on a crash, and it needs replacement and consistency management.

Answer frame. Define buffering and spooling; draw double buffering (device, two buffers, process); develop points 1-4; close with memory vs disk. Buffer cache: purpose, then points 5-7.

Asked: [7 marks] (May 2019) Discuss the advantages and disadvantages of the buffer cache? Asked: [7 marks] (Nov 2023) Explain the concept of buffering and spooling.

I/O Interfaces

Definition. An I/O interface is the hardware and software between the CPU and a device: the device controller, its registers and ports, and the device driver.

Key points.

The device controller converts between device signals and bus data, and holds status, command and data registers.
The CPU reaches registers by port-mapped or memory-mapped I/O.
The device driver is OS code that knows one controller and gives the kernel a uniform interface.
Interfaces may be blocking or non-blocking, and the CPU is signalled by polling or interrupt.

Programme Controlled I/O

Definition. In programmed (polled) I/O the CPU itself executes a loop that tests the device status register and transfers each data unit.

Key points.

The CPU issues the command, then loops until the ready bit is set (busy waiting).
Every byte passes through the CPU, so it is simple but wastes CPU time.
It suits fast devices and short transfers where polling is cheap.

Interrupt Driven I/O

Definition. In interrupt-driven I/O the CPU starts the transfer and continues other work, and the device raises an interrupt when it is ready.

Key points.

On the interrupt the CPU saves its state, runs the handler to move the data, then resumes.
It removes busy waiting, but each interrupt has a context-switch cost.
A single serial port sends characters rarely, so interrupts free the CPU between characters at little cost.
A front-end processor such as a terminal concentrator has many lines and a constant stream of data, so interrupts would arrive continuously and cost more than polling.
Polling therefore has lower overhead for high-frequency traffic, and interrupts for sparse events.

Asked: [7 marks] (Jun 2025) Why might a system use interrupt driven I/O to manage a single serial port but polling I/O to manage a front end processor, such as a terminal concentrator.

Concurrent I/O

Definition. Concurrent I/O is overlapping several I/O operations, usually using DMA so that a controller moves data directly between device and memory.

Key points.

The CPU gives the DMA controller the device, memory address and count.
The controller transfers the block using cycle stealing and interrupts the CPU only once at the end.
This lets the CPU compute while many devices transfer.

Real and Virtual Concurrency

Definition. Concurrency means several processes make progress in the same period; it is real when they run at the same instant on different CPUs, and virtual when one CPU interleaves them.

Key points.

Concurrent programming is writing a program as cooperating processes or threads whose execution overlaps in time.
Real concurrency is true parallelism, needing a multiprocessor with one process per CPU.
Virtual (pseudo) concurrency is created on one CPU by time-sharing and context switching, so processes only appear parallel.
Concurrency control is the set of mechanisms (locks, semaphores, monitors) that keep shared data consistent.
Both kinds create race conditions on shared data, so synchronization is needed.

Basis	Real concurrency	Virtual concurrency
Execution	Simultaneous	Interleaved
Hardware	Multiple CPUs	Single CPU
Mechanism	Parallel processors	Time-slicing, context switch
Overhead	Low switching	Context-switch cost
Speed-up	Real	None in total work
Example	Multicore server	Uniprocessor time-sharing

Answer frame. Open with the definition; draw two timelines (two CPUs at once vs one CPU alternating); give the table; close with the need for synchronization. For the 14-mark question give a few lines to each of a-d.

Asked: [4 marks] (Jun 2025, Jun 2023) Write short notes: Concurrent Programming. Explain concurrency controls? What are the differences between real and virtual concurrency? Asked: [14 marks] (Nov 2019) Explain the following term: a) Real and virtual concurrency b) Critical section c) Mutual exclusion d) I/O Interfaces

Mutual Exclusion

Definition. Mutual exclusion means that when one process is executing in its critical section, no other process may execute in its own critical section on the same shared resource.

Key points.

Example: two processes update a shared counter or use one printer, and without exclusion their updates interleave and give wrong results.
A correct solution needs mutual exclusion, progress and bounded waiting.
Software solutions are Peterson's and Dekker's algorithms with flag and turn variables.
Hardware solutions are disabling interrupts and atomic instructions such as test-and-set and swap.
OS solutions are semaphores, monitors and locks.

Asked: [7 marks] (Jun 2023) Explain mutual exclusion with suitable example.

Synchronization

Definition. Synchronization is the coordination of concurrent processes so that they access shared data in a controlled order and give consistent results.

Key points.

Without it, a race condition arises when the outcome depends on the order of interleaved accesses.
It has two aims: mutual exclusion on shared data, and ordering of events (one process waits for another).
Tools are locks, semaphores, monitors and message passing.
Busy waiting means a process repeatedly tests a condition in a loop (a spinlock) and wastes CPU cycles.
The other kind is blocking (sleep) waiting, where the process is put in a wait queue and woken by signal, using no CPU.
Busy waiting cannot be avoided altogether: the lock itself needs an atomic test, and on a multiprocessor a short spin is cheaper than a context switch, so it is kept for very short critical sections.
A monitor is a module whose procedures run one process at a time; condition variables provide wait and signal inside it.
Readers-writers: many readers may read together, but a writer needs exclusive access.

monitor RW {
  int readers = 0; bool writing = false;
  condition okRead, okWrite;
  startRead()  { if (writing) okRead.wait(); readers++; okRead.signal(); }
  endRead()    { readers--; if (readers == 0) okWrite.signal(); }
  startWrite() { if (writing || readers > 0) okWrite.wait(); writing = true; }
  endWrite()   { writing = false;
                 if (okRead.queue) okRead.signal(); else okWrite.signal(); }
}

The chained okRead.signal() admits all waiting readers, and endWrite prefers them, which limits starvation of readers.

Answer frame. Reader-writer: state the problem, give the monitor, explain each procedure, close with starvation. Busy waiting: define it, name blocking wait, argue it cannot be removed completely. Short note: definition, race condition, tools, conclusion.

Asked: [7 marks] (Jun 2023) Discuss Reader-Writers solution using Monitors. Asked: [7 marks] (Jun 2024) What is the meaning of the term busy waiting? What another kind of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer. Asked: [14 marks] (Jun 2024) Write short notes on following (any two): a) Synchronization b) Paging c) System Calls

Inter- Process Communication

Definition. IPC is the mechanism by which cooperating processes exchange data and signals, by shared memory or by message passing using send and receive.

Key points.

In indirect message passing, messages go to a mailbox and a process does receive(A) to take one.
A blocking receive suspends the caller until a message arrives.
Sequence for P: receive(A, m1); receive(B, m2); works because P needs both messages anyway.
If P must react to whichever comes first, a fixed order can block on A while B's message waits, so use non-blocking receives in a polling loop or a receive-from-any (select) on both mailboxes.
Sender blocking with a full mailbox can add deadlock, so buffered mailboxes are preferred.

Asked: [7 marks] (Jun 2025) Suppose a process P wants to wait for two messages, one from mailbox A and one from mailbox B. What sequence of send and receive should it execute.

Critical Section Problem

Definition. A critical section is the code segment in which a process accesses shared data; the critical section problem is to design a protocol so that no two processes are in their critical sections at the same time.

Key points.

Each process has the structure: entry section, critical section, exit section, remainder section.
Mutual exclusion: if one process is in its critical section, no other may be.
Progress: if no process is in the critical section, only processes wanting to enter decide who goes next, and the choice cannot be postponed forever.
Bounded waiting: a limit exists on how many times others enter before a waiting process gets in, so no starvation.
Example: two processes doing count++ and count-- on a shared variable can leave a wrong value without a protocol.
Solutions are Peterson's algorithm, hardware atomic instructions and semaphores.

Answer frame. Define both terms; write the four-part loop; list the three requirements; close with the semaphore solution.

Asked: [7 marks] (May 2019, Jun 2020) Briefly explain the following: i) Mutual exclusion ii) Critical section problem

Solution to Critical Section Problem : Semaphores – Binary and Counting Semaphores, WAIT & SIGNAL Operations and their implementation

Definition. A semaphore is an integer variable, accessed only through the atomic operations wait (P) and signal (V), used for mutual exclusion and synchronization.

Key points.

Importance: it gives mutual exclusion without busy waiting in the OS and orders events between processes.
Binary semaphore takes only 0 or 1 and works as a mutex lock, for example mutex = 1 around a critical section.
Counting semaphore has an unbounded non-negative range and counts free units of a resource, for example a pool of 3 printers with initial value 3.
wait(S) decrements S and blocks the caller if the result is negative; signal(S) increments S and wakes one blocked process.
Implementation: each semaphore has an integer and a queue of waiting processes; both operations execute atomically (interrupts disabled or an atomic instruction on a single CPU).
Uses: mutual exclusion (wait(mutex) ... signal(mutex)) and synchronization (P2 waits on a semaphore initialised to 0 until P1 signals it).

wait(S):   Step 1: S.value--
           Step 2: if S.value < 0, add process to S.queue and block()
signal(S): Step 1: S.value++
           Step 2: if S.value <= 0, remove a process P from S.queue and wakeup(P)

Dining philosophers. Five philosophers sit at a round table with five chopsticks, one between each pair; a philosopher eats only with both neighbours' chopsticks. Taking the left chopstick first for all five gives deadlock, so at most four are admitted to the table with a counting semaphore.

semaphore chopstick[5] = {1,1,1,1,1};   // one per chopstick
semaphore room = 4;                     // at most 4 seated
philosopher(i) {
  while (1) {
    think();
    wait(room);
    wait(chopstick[i]); wait(chopstick[(i+1)%5]);
    eat();
    signal(chopstick[(i+1)%5]); signal(chopstick[i]);
    signal(room);
  }
}

With at most four philosophers competing for five chopsticks, one of them always gets two, so there is no deadlock; FIFO semaphore queues avoid starvation.

Answer frame. Semaphore questions: definition, wait/signal code, binary vs counting (range, use, example). Philosophers: state the problem, draw the round table with five chopsticks, give the code, close with why deadlock cannot occur.

Asked: [7 marks] (Nov 2019) What is Binary and Counting semaphores? Asked: [7 marks] (May 2019, Nov 2023) Write a semaphore solution for dining philosopher's problem? Asked: [7 marks] (Jun 2020) What do you mean by Semaphore? Explain its uses and its implementation. Asked: [7 marks] (Nov 2023, Jun 2025) Write a semaphore solution for dining philosopher's problem. Define a semaphore for dining philosopher's problem. Asked: [7 marks] (Jun 2024, Jun 2026) Why Semaphore is important in OS? Explain Binary and counting semaphores with suitable example. Explain synchronization using binary and counting semaphores with WAIT operations.

Deadlocks: Deadlock Problems, Characterization, Prevention, Avoidance, Recovery

Definition. A deadlock is a situation in which a set of processes is blocked forever, each holding a resource and waiting for a resource held by another process in the set.

Key points.

Coffman conditions, all four needed together: mutual exclusion (a resource is used by one process at a time); hold and wait (a process holds one resource while waiting for more); no preemption (a resource is released only voluntarily); circular wait (a cycle of processes each waits for the next).
Prevention breaks one condition: allow sharing where possible, make a process request all resources at once, preempt resources, or impose a resource ordering so no cycle can form.
Avoidance keeps the system in a safe state using advance maximum claims; the Banker's algorithm grants a request only if a safe sequence remains.
Detection uses a resource-allocation graph or wait-for graph cycle for single-instance resources, and a Banker-like algorithm for multiple instances.
Recovery by process termination: abort all deadlocked processes, or abort one at a time until the cycle breaks, choosing by priority, cost, run time and resources held.
Recovery by resource preemption: pick a victim, roll it back to a safe state, and avoid starving the same process repeatedly.

Formula. Need = Max - Allocation. Safety algorithm: find a process with Need $\le$ Work; add its Allocation to Work; repeat; safe if all finish. For $n$ processes each needing $m$ units of $R$ resources, deadlock-free if $n(m-1)+1 \le R$.

Example (Jun 2020, Banker's). Available = (3,3,0).

Process	Allocation	Max	Need
P0	1 0 1	4 3 1	3 3 0
P1	1 1 2	2 1 4	1 0 2
P2	1 0 3	1 3 3	0 3 0
P3	2 0 0	5 4 1	3 4 1

Work = (3,3,0). P0: need 330 $\le$ 330, so Work = 431. P2: 030 $\le$ 431, Work = 534. P1: 102 $\le$ 534, Work = 646. P3: 341 $\le$ 646, Work = 846.

The system is in a safe state, with safe sequence $\langle$P0, P2, P1, P3$\rangle$; the Need matrix is as tabulated.

Example (Jun 2023, tape drives). Each process needs 2 of 6 drives, so the worst case gives each process 1 drive and holds $n$ drives; one process gets a second drive if $n(2-1)+1 \le 6$.

The system is deadlock free for $n \le 5$ (n = 1 to 5).

Answer frame. Coffman: define deadlock, explain the four conditions in a sentence each, add recovery if asked. Banker's: Need, trace, safe sequence. Prevention and avoidance note: definition, break-a-condition list, safe state, Banker's. Recovery: termination, then preemption, with selection criteria.

Asked: [14 marks] (Jun 2025) Write short notes on following. (any two) a) Deadlock prevention and avoidance b) Kernel architecture in Unix c) System calls Asked: [7 marks] (May 2019, Nov 2019) Describe necessary conditions for a deadlocks situation to arise. Define a deadlock? Write down the conditions responsible for deadlock? How can we recover from deadlock? Asked: [7 marks] (Jun 2020) Snapshot: Allocation ABC P0 101, P1 112, P2 103, P3 200; Max P0 431, P1 214, P2 133, P3 541; Available 330. Using Banker's Algorithm: i) Is the system in safe state ii) What is the matrix Need? Asked: [7 marks] (Nov 2023) Describe about how recovery from deadlock? Asked: [7 marks] (Jun 2023) What do you mean by deadlock prevention? A computer has six tape drive with a processes competing for them. Each process need two tape drives for which values of n the system is deadlock free.

Last-minute revision

Buffering smooths the speed gap in memory; spooling queues jobs on disk (printer).
Programmed I/O = polling; interrupt I/O frees the CPU; DMA moves blocks without the CPU.
Real concurrency = many CPUs at once; virtual = one CPU interleaving.
Critical section needs mutual exclusion, progress, bounded waiting.
Semaphore: integer with atomic wait (decrement, block if negative) and signal (increment, wake one).
Dining philosophers: chopstick[5]=1 and room=4.
Coffman: mutual exclusion, hold and wait, no preemption, circular wait.
Need = Max - Allocation; Jun 2020 safe sequence P0, P2, P1, P3.
Six tape drives, 2 each: deadlock-free for n at most 5.

Memory hooks

Coffman = "MHNC": Mutual, Hold, No-preempt, Circular.
Critical section rules = "MPB": Mutual exclusion, Progress, Bounded waiting.
P = wait (proberen, test), V = signal (verhogen, increment).
Philosophers: five chopsticks, four chairs, no deadlock.
Deadlock-free tape drives: $n(m-1)+1 \le R$.

Coverage checklist

Input / Output : Principles and Programming: Jun 2026.
Input/Output Problems: taught.
Asynchronous Operations: Jun 2026 comparison.
Speed gap Format conversion: May 2019, Nov 2023.
I/O Interfaces: taught; Nov 2019 part d, Jun 2026.
Programme Controlled I/O: taught.
Interrupt Driven I/O: Jun 2025.
Concurrent I/O: taught.
Real and Virtual Concurrency: Jun 2023, Jun 2025, Nov 2019.
Mutual Exclusion: Jun 2023.
Synchronization: Jun 2023, Jun 2024 (two).
Inter- Process Communication: Jun 2025.
Critical Section Problem: May 2019, Jun 2020.
Solution to Critical Section Problem : Semaphores – Binary and Counting Semaphores, WAIT & SIGNAL Operations and their implementation: Nov 2019, Jun 2020, Jun 2024, Jun 2026, May 2019, Nov 2023, Jun 2025.
Deadlocks: Deadlock Problems, Characterization, Prevention, Avoidance, Recovery: May 2019, Nov 2019, Jun 2020, Jun 2023, Nov 2023, Jun 2025.

Account

Operating Systems (CS-405) - Unit 4 Short Notes

How unit 4 is examined

Input / Output : Principles and Programming

Input/Output Problems

Asynchronous Operations

Speed gap Format conversion

I/O Interfaces

Programme Controlled I/O

Interrupt Driven I/O

Concurrent I/O

Real and Virtual Concurrency

Mutual Exclusion

Synchronization

Inter- Process Communication

Critical Section Problem

Solution to Critical Section Problem : Semaphores – Binary and Counting Semaphores, WAIT & SIGNAL Operations and their implementation

Deadlocks: Deadlock Problems, Characterization, Prevention, Avoidance, Recovery

Last-minute revision

Memory hooks

Coverage checklist