Operating Systems (AD-405) Unit 2 Notes - RGPV

How unit 2 is examined

Processes, states, scheduling, threads, IPC, synchronization with semaphores and monitors, and deadlocks; the marks sit in CPU scheduling, semaphores, synchronization and deadlock prevention.

Concept of a process

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A process is a program in execution; it is an active entity with a program counter, registers, stack and data, whereas a program is a passive file on disk.

Key points.

The Process Control Block (PCB) is the kernel record of a process, and the OS saves and restores it on every context switch.
The PCB holds process ID, process state, program counter, CPU registers, CPU-scheduling information, memory-management information, accounting information and I/O status.
Process states are New, Ready, Running, Waiting and Terminated.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 1121 134" width="1121" height="134" role="img" aria-label="Fields of a Process Control Block"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="548.5" y1="39" x2="63" y2="103"/><line class="e" x1="548.5" y1="39" x2="189" y2="103"/><line class="e" x1="548.5" y1="39" x2="334.5" y2="103"/><line class="e" x1="548.5" y1="39" x2="480" y2="103"/><line class="e" x1="548.5" y1="39" x2="625.5" y2="103"/><line class="e" x1="548.5" y1="39" x2="763" y2="103"/><line class="e" x1="548.5" y1="39" x2="900.5" y2="103"/><line class="e" x1="548.5" y1="39" x2="1034" y2="103"/><circle class="n" cx="548.5" cy="39" r="17"/><text class="t" x="548.5" y="39" dy=".35em" text-anchor="middle">PCB</text><rect class="n" x="14" y="88" width="98" height="30" rx="8"/><text class="t" x="63" y="103" dy=".35em" text-anchor="middle">Process ID</text><rect class="n" x="128" y="88" width="122" height="30" rx="8"/><text class="t" x="189" y="103" dy=".35em" text-anchor="middle">Process state</text><rect class="n" x="266" y="88" width="137" height="30" rx="8"/><text class="t" x="334.5" y="103" dy=".35em" text-anchor="middle">Program counter</text><rect class="n" x="419" y="88" width="122" height="30" rx="8"/><text class="t" x="480" y="103" dy=".35em" text-anchor="middle">CPU registers</text><rect class="n" x="557" y="88" width="137" height="30" rx="8"/><text class="t" x="625.5" y="103" dy=".35em" text-anchor="middle">Scheduling info</text><rect class="n" x="710" y="88" width="106" height="30" rx="8"/><text class="t" x="763" y="103" dy=".35em" text-anchor="middle">Memory info</text><rect class="n" x="832" y="88" width="137" height="30" rx="8"/><text class="t" x="900.5" y="103" dy=".35em" text-anchor="middle">Accounting info</text><rect class="n" x="985" y="88" width="98" height="30" rx="8"/><text class="t" x="1034" y="103" dy=".35em" text-anchor="middle">I/O status</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Fields of a Process Control Block</figcaption></figure>

Asked: [7 marks] (Jun 2023) Define process states. Draw the diagram of PCB.

Process State Diagram

Definition. Process state is the current activity of a process; it changes as the process is admitted, scheduled, blocked and finished.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 596 252" width="596" height="252" role="img" aria-label="Five-state model. N New, R Ready, Run Running, W Waiting, T Terminated"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah3)"/><path class="e" d="M229.8,46.6 Q298,72 364.3,47.3" marker-end="url(#ah3)"/><path class="e" d="M366.2,33.4 Q298,8 231.7,32.7" marker-end="url(#ah3)"/><path class="e" d="M403,40 L535,40" marker-end="url(#ah3)"/><path class="e" d="M375.5,57 L307.4,193.2" marker-end="url(#ah3)"/><path class="e" d="M289.5,195 L221.4,58.8" marker-end="url(#ah3)"/><g class="wl"><rect x="102.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">admit</text></g><g class="wl"><rect x="263.2" y="50.5" width="68.7" height="18" rx="9"/><text class="t" x="297.5" y="59.5" dy=".35em" text-anchor="middle">dispatch</text></g><g class="wl"><rect x="260.5" y="11.5" width="75.9" height="18" rx="9"/><text class="t" x="298.5" y="20.5" dy=".35em" text-anchor="middle">interrupt</text></g><g class="wl"><rect x="449.6" y="31" width="40.8" height="18" rx="9"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">exit</text></g><g class="wl"><rect x="320.6" y="117" width="40.8" height="18" rx="9"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">wait</text></g><g class="wl"><rect x="227.9" y="117" width="54.3" height="18" rx="9"/><text class="t" x="255" y="126" dy=".35em" text-anchor="middle">signal</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">N</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">Run</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">W</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Five-state model. N New, R Ready, Run Running, W Waiting, T Terminated</figcaption></figure>

Key points.

New: the process is being created; the long-term scheduler admits it to the ready queue.
Ready: the process has everything except the CPU and waits in the ready queue.
Running: the short-term scheduler dispatches one ready process to the CPU.
Running to Ready happens on interrupt, when the time slice expires or a higher-priority process arrives.
Running to Waiting happens when the process requests I/O or an event; it returns to Ready when the I/O completes.
Terminated: the process has finished and the OS reclaims its resources.
A suspended state (swapped out by the medium-term scheduler) is added in the seven-state model.

Program	Process
Passive, a file on disk	Active, a program in execution
Exists until deleted	Exists for its execution time
Needs only disk space	Needs CPU, memory and I/O
No PCB	Has a PCB
One program can give many processes	Each process belongs to one program

Answer frame. Open with the definition of process state; draw the diagram with the six transition labels; explain the transitions in the order admit, dispatch, interrupt, wait, signal, exit; close with the role of the schedulers. For "process vs program" add the table.

Asked: [7 marks] (Nov 2023, Jun 2025, Jun 2026) What is process state? Explain state transition diagram. How is a process different from a program? Describe the process transition diagram in detail.

Process based kernel

Definition. A process-based kernel runs OS services as separate processes, as in a microkernel, instead of one large monolithic kernel.

A microkernel keeps only scheduling, IPC and basic memory management in kernel mode.
File system and drivers run as user processes, so one failing service does not crash the OS, but message passing makes it slower than a monolithic kernel.

Dual mode of process execution

Definition. Dual mode means the CPU runs in user mode or kernel mode, selected by a mode bit (1 user, 0 kernel).

Privileged instructions such as I/O and memory management run only in kernel mode.
A system call or interrupt switches to kernel mode, and returning switches back to user mode.
This protects the OS from faulty user programs.

CPU scheduling algorithms

Definition. CPU scheduling selects which ready process gets the CPU next, so that utilization and throughput rise while waiting and response time fall.

Key points.

Criteria: CPU utilization, throughput, turnaround time (finish minus arrival), waiting time (turnaround minus burst) and response time.
FCFS serves in arrival order and is non-preemptive; it is simple and fair but a long job makes short ones wait (convoy effect).
SJF picks the shortest burst and gives the minimum average waiting time, but long jobs may starve.
SRTF is preemptive SJF: a newly arrived shorter job preempts the running one; it gives low waiting time but needs burst prediction and has high overhead.
Round Robin gives each process a time quantum in turn; it gives good response time, and a very large quantum degenerates to FCFS.
Priority scheduling runs the highest priority first and can starve low priorities; aging raises the priority of long-waiting processes.

Example. P1(arr 0, burst 8), P2(1,4), P3(2,9), P4(3,5).

Algorithm	Waiting times P1, P2, P3, P4	Average
FCFS (order P1,P2,P3,P4)	0, 7, 10, 18	35/4 = 8.75
SRTF (order P1,P2,P4,P1,P3)	9, 0, 15, 2	26/4 = 6.5

Compare FCFS and SRTF.

Point	FCFS	SRTF
Preemption	Non-preemptive	Preemptive
Average waiting	High	Lowest
Starvation	None	Long jobs starve
Convoy effect	Yes	No
Overhead	Very low	High, needs burst estimate

Schedulers.

Scheduler	Long-term (job)	Medium-term (swapping)	Short-term (CPU)
Function	Admits jobs from pool to memory	Swaps processes out and in	Picks next ready process for CPU
Frequency	Rare	Occasional	Very often (milliseconds)
Controls	Degree of multiprogramming	Memory load	CPU allocation

Starvation (Jun 2024). Yes, a system can detect it by monitoring each ready process's waiting time or age against a threshold. The remedy is aging: raise the priority of a process step by step as it waits, so it eventually runs.

RR with PCB pointers (Jun 2025). (i) Two pointers to one process give it two turns per cycle, so it gets double the CPU share, like a higher priority. (ii) Advantage: priority can be implemented cheaply, favouring important or CPU-bound jobs. Drawback: other processes get less CPU and may starve, and the queue must stay consistent when the process ends or blocks.

Answer frame. Open by defining CPU scheduling and the criteria; for FCFS vs SRTF give one line of working each, then the comparison table and the numerical; for schedulers draw the table only; for starvation open with the definition, then detection, then aging; close with the best-fit algorithm.

Asked: [7 marks] (Nov 2023) Compare FCFS and SRTF, highlighting strengths and limitations of each. Asked: [7 marks] (Jun 2023) Describe the differences among short term, medium term and long term scheduling. Asked: [7 marks] (Jun 2024) Can a system detect that some of its processes are starving? If yes, how; if no, how can it deal with starvation? Asked: [7 marks] (Jun 2025) In an RR variant whose ready queue holds PCB pointers: (i) effect of two pointers to the same process; (ii) major advantages and drawback.

Deterministic modeling

Definition. Deterministic modeling evaluates scheduling algorithms by taking a fixed workload and computing each algorithm's performance on exactly that input.

Example: compute average waiting time for FCFS, SJF and RR on the same burst list and pick the smallest.
It is simple and exact but valid only for the given workload.

System calls for Process Management

Definition. These are the calls through which a program asks the kernel to create, run and end processes.

fork() creates a child copy; it returns 0 in the child and the child's PID in the parent.
exec() replaces the process image with a new program.
wait() makes the parent wait until a child ends; exit() terminates the process.

Concept of Threads: User level and Kernel level Threads

Definition. A thread is a lightweight unit of CPU execution inside a process; threads of one process share code, data and open files but each has its own stack, registers and program counter.

Key points.

User-level threads are managed by a library without kernel help, so switching is fast, but one blocking call blocks the whole process.
Kernel-level threads are managed by the OS, so they run in parallel on multiple CPUs and one blocking thread does not block the others, but switching is slower.
Creating a thread needs only a stack, registers and a Thread Control Block; creating a process needs a new address space, PCB and page tables.
The Thread Control Block (TCB) stores thread ID, state, program counter, registers, stack pointer, priority and a pointer to the parent process's PCB.
Per-thread data (TCB fields, stack) is private; per-process data (code, heap, files, address space) is shared.

Point	Thread	Process
Weight	Lightweight	Heavyweight
Memory	Shares address space	Own address space
Creation and switch	Fast	Slow
Communication	Shared memory, easy	Needs IPC
Crash effect	Can kill whole process	Isolated

Answer frame. Open with the definition of thread; draw nothing, give the table; then the resources needed at creation; for TCB list the fields and contrast with PCB; close with multithreading (one process, many threads) vs multiprocessing (many CPUs).

Asked: [7 marks] (Nov 2023) Explain Thread Control Block. Asked: [7 marks] (Jun 2023, Jun 2024) What is the difference between threads and process? What resources are used when a thread is created, and how do they differ from those for a process?

Process Management in UNIX and Windows

Definition. UNIX creates processes with fork() and exec(); Windows creates them with CreateProcess().

UNIX keeps a process table and forms a tree with init as the root.
Windows CreateProcess() builds the child and loads its program in one call, and Windows schedules threads, not processes.

Inter Process Communication: Real and Virtual Concurrency

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

Key points.

Concurrent programming means writing programs whose processes or threads execute in overlapping time, which raises the need for synchronization.
Real concurrency is true parallel execution on several CPUs; virtual (pseudo) concurrency is interleaving of processes on one CPU by fast switching.
Concurrency control (locks, semaphores, monitors) keeps shared data consistent, since unsynchronized interleaving causes race conditions.
In message passing, processes use send(dest, msg) and receive(src, msg) through a mailbox, and receive may block until a message arrives.
To wait for messages from mailboxes A and B in any arrival order, P should not block on A before B; it uses a receive-from-either or non-blocking receive.

Point	Real concurrency	Virtual concurrency
Hardware	Multiple CPUs	Single CPU
Execution	Truly simultaneous	Interleaved
Example	Multiprocessor server	Time-sharing on one core

Answer frame. For concurrency, open with the definition, then real vs virtual table, then race condition and control. For mailboxes, write: receive(A, m1); receive(B, m2) only if both messages are certain to come; otherwise loop with non-blocking receive on A then on B until both arrive, which avoids blocking forever on one.

Asked: [4 marks] (Jun 2023, Jun 2025) Write short notes: Concurrent Programming. Explain concurrency controls; differences between real and virtual concurrency. Asked: [7 marks] (Jun 2025) 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?

Mutual Exclusion

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

Key points.

Example: two processes updating a shared counter or using one printer; without exclusion their interleaved updates corrupt the result.
A solution must give mutual exclusion, progress and bounded waiting.
Software solutions are Peterson's algorithm; hardware solutions are Test-and-Set and disabling interrupts.

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

Synchronization

Definition. Synchronization is the coordination of cooperating processes so that shared data is accessed in a controlled order and stays consistent.

Key points.

Without it, a race condition occurs: the result depends on the order in which processes run.
Busy waiting is repeatedly testing a condition in a loop, which wastes CPU cycles (a spinlock).
The other kind is blocking (sleep-wait): the process joins a wait queue and is woken later, using no CPU.
Busy waiting cannot be avoided altogether: a lock inside the kernel itself, a very short critical section or a multiprocessor spinlock is cheaper than a context switch.
A monitor is a language construct with shared data and procedures where only one process is active at a time, plus condition variables with wait() and signal().
Reader-Writers problem: many readers may read together, but a writer needs exclusive access.

monitor RW {
  int readers = 0; bool writing = false; condition okR, okW;
  StartRead()  { if (writing) okR.wait(); readers++; okR.signal(); }
  EndRead()    { if (--readers == 0) okW.signal(); }
  StartWrite() { if (writing || readers > 0) okW.wait(); writing = true; }
  EndWrite()   { writing = false; if (!okR.empty()) okR.signal(); else okW.signal(); }
}

The signal in EndWrite prefers waiting readers, and the chained okR.signal() in StartRead lets all waiting readers in, so neither side is starved for ever.

Answer frame. For Reader-Writers open with the problem definition, then monitor definition, then the code and how waiting is handled; for busy waiting define it, name blocking as the alternative, then say it cannot be fully avoided with the reason; for the short note, define, list mechanisms (semaphore, monitor) and close on the OS role.

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

Critical Section Problem

Definition. The critical section is the code that accesses shared data; the problem is to design an entry and exit protocol so only one process is inside at a time.

A solution needs mutual exclusion, progress and bounded waiting.
Peterson's algorithm for two processes uses flag[i] and turn.

Solution to Critical Section Problem: Semaphores

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

Step 1: wait(S): while (S <= 0) ; then S = S - 1
Step 2: signal(S): S = S + 1

Key points.

Semaphores matter because they give mutual exclusion and ordering without busy-wait hacks and work for any number of processes.
A binary semaphore takes only 0 or 1 and acts as a lock; example: mutex initialized to 1 guarding a shared counter.
A counting semaphore has an unrestricted value and counts available resources; example: 3 identical printers, so the value starts at 3.
Implementation without busy waiting keeps a waiting queue: wait blocks the process if the value goes negative, and signal wakes one.
Dining philosophers: five philosophers share five chopsticks, and each needs two to eat.

semaphore chop[5] = {1,1,1,1,1}, room = 4;
philosopher(i) { while (1) {
  wait(room); wait(chop[i]); wait(chop[(i+1)%5]);
  eat();
  signal(chop[i]); signal(chop[(i+1)%5]); signal(room);
  think(); } }

Simple wait on left then right chopstick can deadlock if all pick up left together; allowing at most four philosophers into the room (semaphore room) prevents this, and FIFO queues on the semaphores avoid starvation.

Answer frame. For philosophers state the problem, define chop[] and the limiting semaphore, give the code, and close with deadlock and starvation. For binary and counting, open with why semaphores are needed, define wait and signal, then each type with its example.

Asked: [7 marks] (Nov 2023, Jun 2025) Write a semaphore solution for the dining philosophers problem. Define a semaphore for it. Asked: [7 marks] (Jun 2024, Jun 2026) Why is a semaphore important in OS? Explain binary and counting semaphores with suitable example.

Deadlocks: Deadlock Problems

Definition. A deadlock is a state in which every process in a set waits for a resource held by another process in the set, so none can proceed.

It is drawn with a resource allocation graph; a cycle means deadlock for single-instance resources.

Characterization

Definition. Deadlock can occur only if four conditions hold together.

Mutual exclusion: a resource is held by one process at a time.
Hold and wait: a process holds resources while waiting for others.
No preemption: resources cannot be forcibly taken.
Circular wait: a closed chain of processes each waits for the next one's resource.

Prevention

Definition. Deadlock prevention ensures that at least one of the four necessary conditions can never hold, so deadlock cannot occur.

Key points.

Mutual exclusion cannot be removed for non-sharable resources, but sharable ones such as read-only files need no lock.
Hold and wait is broken by requiring a process to request all resources at once, or to release all before requesting more.
No preemption is broken by taking resources away from a waiting process when a request cannot be met.
Circular wait is broken by numbering resource types and requiring requests in increasing order.
The cost of prevention is low resource utilization and possible starvation.

Formula. With $m$ resources of one type and $n$ processes each needing at most $k$, the system is deadlock free if $$m \ge n(k-1)+1$$

Example. Given $m=6$ tape drives, $k=2$ per process. Worst case each of $n$ processes holds 1 drive and waits for a second, using $n$ drives; deadlock is impossible when at least one spare drive exists. So $6 \ge n(2-1)+1$, i.e. $n \le 5$. Deadlock free for n = 1, 2, 3, 4, 5 (with n = 6 all six hold one and wait).

Answer frame. Open with the definition; list the four conditions, then the way to defeat each; for the numerical state the formula, substitute and end with the boxed n; for the short note add one line on avoidance (Banker's algorithm keeps the system in a safe state).

Asked: [7 marks] (Jun 2023) What do you mean by deadlock prevention? A computer has six tape drives with n processes competing; each needs two. For which values of n is the system deadlock free? Asked: [14 marks] (Jun 2025) Write short notes on (any two): a) Deadlock prevention and avoidance b) Kernel architecture in Unix c) System calls.

Avoidance

Definition. Deadlock avoidance grants a request only if the system stays in a safe state, using advance knowledge of maximum needs.

A state is safe if some order of running all processes to completion exists.
Banker's algorithm keeps Available, Max, Allocation and Need = Max - Allocation, and grants a request only if a safe sequence remains.

Recovery

Definition. Deadlock recovery breaks an existing deadlock after detection.

Key points.

Process termination: abort all deadlocked processes, or abort one at a time until the cycle breaks, which costs less work but needs repeated detection.
Resource preemption: take resources from some processes and give them to others, after choosing a victim and rolling it back to a safe state.
Victims are chosen by priority, work done so far, resources held and cost of restart; a process that is repeatedly chosen may starve.

Asked: [7 marks] (Nov 2023) Describe how recovery from deadlock is done.

IPC in UNIX and Windows

Definition. UNIX and Windows offer several IPC mechanisms.

UNIX has pipes, FIFOs, message queues, shared memory and semaphores.
Windows has anonymous and named pipes, mailslots and shared memory.

Last-minute revision

Process = program in execution; PCB stores its state, PC, registers, memory and I/O information.
Five states: New, Ready, Running, Waiting, Terminated; dispatch moves Ready to Running.
Waiting time = turnaround - burst; turnaround = finish - arrival.
SJF gives minimum average waiting; SRTF is its preemptive form.
Sample data: FCFS average wait 8.75, SRTF 6.5.
Aging cures starvation; long-term, medium-term and short-term schedulers differ in frequency.
User threads: fast but block together; kernel threads: parallel but slower.
Critical section needs mutual exclusion, progress, bounded waiting.
Semaphore: wait (P) decrements, signal (V) increments; binary 0/1, counting any integer.
Four deadlock conditions: mutual exclusion, hold and wait, no preemption, circular wait.
Deadlock free if $m \ge n(k-1)+1$; six drives, two each gives n up to 5.
Recovery: abort processes or preempt resources.

Memory hooks

Deadlock conditions: "MHNC" - Mutual, Hold, No-preemption, Circular.
Process states: "New Ready Run Wait End".
P = probeer (try/wait), V = verhoog (raise/signal).
Dining philosophers: keep one seat empty (4 of 5 in the room).
Real concurrency = many CPUs; virtual = one CPU taking turns.

Coverage checklist

Concept of a process: PCB, process states (Jun 2023).
Process State Diagram: state diagram, process vs program (Nov 2023, Jun 2025, Jun 2026).
Process based kernel: definition only.
Dual mode of process execution: definition only.
CPU scheduling algorithms: FCFS vs SRTF, schedulers, starvation, RR with PCB pointers.
deterministic modeling: definition only.
System calls for Process Management: definition only.
Concept of Threads: User level & Kernel level Threads: TCB, threads vs process.
Process Management in UNIX & Windows: definition only.
Inter Process Communication: Real and Virtual Concurrency: concurrent programming, real vs virtual, mailboxes.
Mutual Exclusion: explain with example.
Synchronization: Reader-Writers monitor, busy waiting, short note.
Critical Section Problem: definition only.
Solution to Critical Section Problem : Semaphores and their Operations and their implementation: dining philosophers, binary and counting semaphores.
Deadlocks: Deadlock Problems: definition only.
Characterization: four conditions.
Prevention: tape drives numerical, short note on prevention and avoidance.
Avoidance: safe state, Banker's algorithm.
Recovery: termination, preemption.
IPC in UNIX & Windows: definition only.