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

How unit 3 is examined

Covers processes, schedulers, scheduling algorithms, threads, memory management and virtual memory; the marks are in page replacement numericals, paging/segmentation, process states with PCB, and scheduling algorithms.

Process Concept

<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">High weight</span>

Definition. <mark>A process is a program in execution: an active entity with its own code, data, stack, heap, registers and a Process Control Block (PCB), whereas a program is a passive file on disk.</mark>

Diagram. PCB, drawn as one box of fields from top to bottom:

PCB field	Content
Process ID	unique number
Process state	new, ready, running, waiting, terminated
Program counter	address of next instruction
CPU registers	accumulator, index, stack pointer
CPU scheduling info	priority, queue pointers
Memory management info	base/limit, page or segment tables
Accounting info	CPU time used, time limits
I/O status info	open files, allotted devices

Key points.

A process in memory has code, data (globals), heap (dynamic memory) and stack (calls and locals).
The PCB is the process descriptor: the OS creates one per process and it is the only record from which the process can be resumed.
The PCB is used in process management, scheduling and context switching: on a switch the OS saves the running process's PC and registers in its PCB and loads those of the next.
The PID identifies the process, and the state field tells the scheduler whether it is ready, running or waiting.
Scheduling and memory information let the scheduler pick the next process and the memory manager locate its pages, and accounting and I/O status record CPU time and files held for release on exit.
A thread is a unit of execution inside a process that shares its address space; a process may have several.

Answer frame. Open with the process definition; draw the PCB box and the state diagram; develop points 1-3, then fields (4-5) with usefulness; close with "the PCB makes context switching possible".

Asked: [14 marks] (May 2019, Nov 2019) What is a PCB? Where used? Contents; process and thread. Asked: [7 marks] (May 2019) Explain a process with its components. Asked: [7 marks] (Jun 2020, Jun 2023) Define process states. Draw the diagram of PCB. Asked: [7 marks] (Jun 2023) Define process states. Draw the diagram of PCB.

Scheduling Concepts

Definition. <mark>CPU scheduling is selecting one process from the ready queue to run on the CPU, and it is either preemptive or non-preemptive.</mark>

Key points.

In non-preemptive scheduling a process keeps the CPU until it terminates or waits for I/O (FCFS, non-preemptive SJF).
In preemptive scheduling the CPU can be taken away on a time-slice end or a higher-priority arrival (RR, SRTF, preemptive priority).
Criteria: maximise CPU utilization and throughput; minimise turnaround, waiting and response time.
$TAT = CT - AT$ and $WT = TAT - BT$.

Types of Schedulers

Definition. <mark>Scheduling is deciding which process gets the CPU or memory next, and three schedulers work at different levels: long-term (job), short-term (CPU) and medium-term (swapping).</mark>

Key points.

The long-term scheduler loads jobs from the disk job pool into memory, so it controls the degree of multiprogramming and should mix I/O-bound and CPU-bound jobs.
The short-term scheduler picks a ready process and dispatches it, so it runs every few milliseconds and must be very fast.
The medium-term scheduler swaps processes out of memory and back in later, reducing multiprogramming when memory is short.

Basis	Long-term	Short-term	Medium-term
Frequency	Lowest	Highest	Medium
Moves	New to ready	Ready to running	Memory to disk and back
Controls	Multiprogramming degree	Which process runs	Memory load

Answer frame. Define scheduling; two lines per scheduler; close with the table.

Asked: [7 marks] (May 2019, Jun 2023) What is scheduling? Explain short, medium, long term scheduler. Asked: [7 marks] (Jun 2023) Differences among short, medium and long term scheduling.

Process State Diagram

Definition. <mark>Process state is the current activity of a process, and it moves between new, ready, running, waiting and terminated during its life.</mark>

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 596 252" width="596" height="252" role="img" aria-label="Five-state model. Rdy = Ready, Run = Running, Wt = Waiting (blocked), End = Terminated"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah18" 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="ahh18" 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(#ah18)"/><path class="e" d="M233,40 L363,40" marker-end="url(#ah18)" marker-start="url(#ah18)"/><path class="e" d="M375.5,57 L307.4,193.2" marker-end="url(#ah18)"/><path class="e" d="M289.5,195 L221.4,58.8" marker-end="url(#ah18)"/><path class="e" d="M403,40 L535,40" marker-end="url(#ah18)"/><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="235.8" y="31" width="124.5" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">dispatch/timeout</text></g><g class="wl"><rect x="306.7" y="117" width="68.7" height="18" rx="9"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">I/O-wait</text></g><g class="wl"><rect x="220.7" y="117" width="68.7" height="18" rx="9"/><text class="t" x="255" y="126" dy=".35em" text-anchor="middle">I/O-done</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><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">New</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Rdy</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">End</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">Wt</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Five-state model. Rdy = Ready, Run = Running, Wt = Waiting (blocked), End = Terminated</figcaption></figure>

Key points.

New: the process is being created, and the long-term scheduler admits it to the ready queue.
Ready: it has everything except the CPU; the short-term scheduler dispatches it to running.
Running: its instructions execute; only one process runs per CPU.
Running to ready happens on a timer interrupt or a higher-priority arrival; running to waiting on an I/O request, returning to ready when the I/O completes.
Terminated: the process has finished (exit) and the OS releases its resources. The seven-state model adds suspended states for swapped-out processes.
A program is a passive file; a process is a program in execution with state, PCB and resources.

Answer frame. Define process state; draw the diagram with transition labels; explain states, then transitions; close by naming the scheduler behind each move.

Asked: [7 marks] (Nov 2023, Jun 2025, Jun 2026) What is process state? Explain state transition diagram; process vs program; life cycle.

Scheduling Algorithms

Definition. <mark>A scheduling algorithm decides the order in which ready processes get the CPU, aiming to maximise CPU utilization and throughput and minimise turnaround, waiting and response time.</mark>

Formula. $TAT = CT - AT$, $WT = TAT - BT$, average $= \frac{\sum WT}{n}$.

Key points.

FCFS serves in arrival order; it is simple and non-preemptive, but short jobs wait behind a long one (convoy effect).
SJF picks the shortest burst; it gives the minimum average waiting time, but needs burst prediction and starves long jobs.
SRTF is preemptive SJF: a newly arrived shorter job preempts the running one, so waiting is lower than SJF but context switches are more.
Priority scheduling runs the highest-priority process first and can starve low-priority ones.
Round Robin gives each process a quantum $q$ in a circular queue; it is fair with good response time, but a huge $q$ becomes FCFS and a tiny $q$ wastes time on context switches.
Starvation is indefinite waiting; the system can detect it by monitoring waiting time in the ready queue, and cure it by aging: raising priority as waiting time grows.
FCFS and SJF are non-preemptive; SRTF, RR and preemptive priority are preemptive.

Example (Jun 2020). Arrivals P1..P5 = 0,1,2,3,4; bursts 3,5,2,5,5.

Algorithm	Gantt order (time)	Waits P1..P5	Average WT
FCFS	P1 0-3, P2 3-8, P3 8-10, P4 10-15, P5 15-20	0, 2, 6, 7, 11	26/5 = 5.2
SJF	P1 0-3, P3 3-5, P2 5-10, P4 10-15, P5 15-20	0, 4, 1, 7, 11	23/5 = 4.6
RR q=1	P1 P2 P1 P3 P2 P4 P1 P5 P3 P2 P4 P5 P2 P4 P5 P2 P4 P5 P4 P5	4, 10, 5, 11, 11	41/5 = 8.2

Average waiting time: FCFS 5.2, SJF 4.6, RR 8.2; SJF is best (RR: a new arrival joins the queue before the preempted process; $WT = CT - AT - BT$).

Duplicate pointers in RR. Two pointers to one PCB give that process two slices per cycle, like a higher priority. Advantage: important jobs finish sooner with no priority code. Drawbacks: others wait longer (unfair) and the OS must remove every copy when it ends.

Answer frame. Numerical: table, one Gantt bar per algorithm, waits, average, compare. Comparison: open with the criteria, table of preemption, starvation and overhead, close with RR for time-sharing.

Asked: [7 marks] (Jun 2020) Gantt charts, average waiting time: FCFS, SJF, RR (q = 1), P1-P5. Asked: [7 marks] (Nov 2023) Compare FCFS and SRTF: strengths and limitations. Asked: [7 marks] (Jun 2024) Can a system detect starving processes? How, or how to deal with it. Asked: [7 marks] (Jun 2025) RR with PCB pointers: two pointers to one process, advantages, drawbacks. Asked: [7 marks] (Jun 2026) Compare common CPU scheduling algorithms and their evaluation criteria.

Algorithms Evaluation

Definition. <mark>Algorithm evaluation selects a scheduling algorithm by measuring it against criteria such as CPU utilization, throughput, turnaround, waiting and response time.</mark>

Key points.

Deterministic modelling computes each algorithm's performance for one fixed workload, as in the Gantt examples; it is exact but only for that workload.
Queueing models use arrival and service distributions; Little's formula $n = \lambda \times W$ links queue length, arrival rate and waiting time.
Simulation runs a model with generated or trace data; implementation in a real OS is the most accurate and most expensive.

System calls for Process Management

Definition. <mark>Process management system calls are the interface through which a user program asks the kernel to create, run, wait for and end processes.</mark>

Key points.

fork() creates a child copy of the caller and returns 0 to the child and the child's PID to the parent.
exec() replaces the process image with a new program, wait() blocks the parent until a child ends, and exit() terminates a process with a status.
Each call is a trap that switches the CPU from user to kernel mode, so creation, synchronization and protection stay under OS control.

Asked: [7 marks] (Jun 2026) Discuss process management system calls and their importance.

Multiple Processor Scheduling

Definition. <mark>Multiple-processor scheduling assigns ready processes to several CPUs sharing memory, which is harder than single-CPU scheduling because load must be balanced.</mark>

Key points.

Asymmetric multiprocessing has one master CPU making all scheduling decisions; symmetric multiprocessing (SMP) lets each CPU schedule itself.
Load balancing keeps all CPUs busy by push migration (move work off a busy CPU) or pull migration (an idle CPU takes work).
Processor affinity keeps a process on one CPU to reuse its cache: soft affinity is a preference, hard affinity a guarantee.

Concept of Threads

Definition. <mark>A thread is a lightweight unit of CPU execution inside a process, with its own thread ID, program counter, registers and stack, sharing the process's code, data and open files.</mark>

Key points.

A multithreaded process has one address space but several execution paths, so one part can run while another waits.
Benefits: responsiveness, resource sharing, economy (cheaper to create and switch than processes) and use of multiple processors.
User threads are managed by a library without the kernel (fast, but one blocking call blocks the whole process); kernel threads are managed by the OS (can run on different CPUs, slower).
Creating a thread needs only a stack, registers, PC and a thread control block; creating a process needs a new address space, PCB, page tables and file table.
The Thread Control Block (TCB) stores per-thread data: thread ID, state, PC, registers, stack pointer, priority and a pointer to the parent PCB; code, data and files are per-process, in the PCB.

Basis	Process	Thread
Definition	Program in execution	Unit of execution within a process
Creation and switch cost	High	Low

Answer frame. Open with the definition; draw a process box with threads sharing code/data/files, each with own stack and registers; points 1-3, the table, then the TCB. For multiple processor scheduling add its points.

Asked: [7 marks] (Nov 2023) Explain Thread Control Block. Asked: [7 marks] (Jun 2023, Jun 2024) Threads vs process; resources for creating a thread vs a process. Asked: [7 marks] (Jun 2026) Explain threads and multiple processor scheduling.

Different Memory Management Techniques – Partitioning, Swapping, Segmentation, Paging, Paged Segmentation, Comparison of these techniques

Definition. <mark>Memory management allocates and protects main memory among processes using partitioning, swapping, paging, segmentation or paged segmentation, and translates logical addresses to physical ones.</mark>

Key points.

Partitioning is contiguous allocation: fixed partitions cause internal fragmentation (waste inside a block), variable ones external fragmentation (scattered holes), fixed by compaction.
Swapping moves a process to a backing store and back, so total process size can exceed RAM.
Paging divides logical memory into equal pages and physical memory into frames of the same size; a page table maps page to frame. It removes external fragmentation but leaves internal fragmentation in the last page.
Logical address = page number $p$ + offset $d$; physical = frame $\times$ page size + $d$.
Segmentation divides a program into variable-size logical segments (main, stack, functions); a segment table holds base and limit, with no internal but some external fragmentation.
Paged segmentation pages each segment, so each segment-table entry points to a page table, removing external fragmentation while keeping logical segments.

Segmentation translation. Logical address = (segment $s$, offset $d$). If $d <$ limit, physical = base + $d$, else trap.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="CPU gives (s, d); segment table ST returns base and limit; Chk tests d < limit; if yes base + d goes to memory, else trap"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah19" 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="ahh19" 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(#ah19)"/><path class="e" d="M231,40 L363,40" marker-end="url(#ah19)"/><path class="e" d="M59,40 L363,40" marker-end="url(#ah19)"/><path class="e" d="M403,40 L535,40" marker-end="url(#ah19)"/><g class="wl"><rect x="116.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">s</text></g><g class="wl"><rect x="256.9" y="31" width="82.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">base,limit</text></g><g class="wl"><rect x="202.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">d</text></g><g class="wl"><rect x="442.9" y="31" width="54.3" height="18" rx="9"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">base+d</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">CPU</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">ST</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">Chk</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">Mem</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CPU gives (s, d); segment table ST returns base and limit; Chk tests d < limit; if yes base + d goes to memory, else trap</figcaption></figure>

Example (Jun 2024). Segments (base, length): 0: 219, 600; 1: 2300, 14; 2: 90, 100; 3: 1327, 580; 4: 1952, 96.

Address	s, d	Check	Physical
0430	0, 430	430 < 600	219 + 430 = 649
110	1, 10	10 < 14	2300 + 10 = 2310
2500	2, 500	500 > 100	trap
3400	3, 400	400 < 580	1327 + 400 = 1727

Example (Nov 2019). 256 pages $= 2^8$, page size $2^{10}$, so logical address $= 8 + 10 =$ 18 bits.

Basis	Partitioning	Paging	Segmentation
Fragmentation	Internal (fixed) or external (variable)	Internal only	External only
Table	Base/limit	Page table	Segment table
User's view	Single block	Invisible	Visible

Answer frame. Segmentation: define, draw the diagram, explain the limit check, give the example. Compare: table, close with "paging removes external fragmentation, segmentation matches the user's view".

Asked: [14 marks] (Nov 2019) $2^{24}$ bytes physical memory, 256 logical pages, page size $2^{10}$: bits in logical address. Asked: [7 marks] (May 2019, Jun 2020) Compare paging and segmentation (with example). Asked: [7 marks] (Jun 2020, Nov 2023) Logical to physical address translation in segmentation, with example. Asked: [7 marks] (Nov 2023) What is segmentation? Explain address mapping with a diagram. Asked: [7 marks] (Jun 2023) Explain paging and segmentation; how they remove fragmentation. Asked: [7 marks] (Jun 2024) Segment table: physical addresses for 0430, 110, 2500, 3400. Asked: [7 marks] (Jun 2026) Compare partitioning, paging and segmentation.

Overlay, Dynamic Linking and Loading

Definition. <mark>Overlay, dynamic loading and dynamic linking let a program larger than its allotted memory run by keeping only the parts currently needed in memory.</mark>

Key points.

Overlay keeps in memory only the instructions and data needed at a time; later parts overwrite the space of finished parts.
Dynamic loading loads a routine only when first called, so unused routines are never loaded and memory is saved.
Static linking copies library routines into the executable; dynamic linking postpones linking to run time, with a small stub that finds the resident library routine or loads it.
Dynamic linking lets many processes share one library copy (DLLs), and updates need no relinking.
Dynamic loading needs no OS support; dynamic linking needs OS help.

Answer frame. Open with the large-program problem; define overlay, dynamic loading, dynamic linking; close that all save memory.

Asked: [7 marks] (Jun 2024, Jun 2026) What is overlay? Dynamic linking and loading; large-program issues.

Virtual Memory – Concept, Implementation by Demand Paging etc

Definition. <mark>Virtual memory lets a process run with only part of it in main memory, the rest on disk, so the logical address space can exceed physical memory.</mark>

Formula. $EAT = (1-p)\times ma + p\times T_{fault}$; for $ma = 200$ ns, $T_{fault} = 8$ ms, $p = 1/1000$: $EAT \approx$ 8200 ns.

Key points.

Advantages: programs larger than RAM run, more processes fit (higher multiprogramming and CPU use), and less I/O is needed.
Demand paging (lazy loading) brings a page in only when referenced; pure demand paging starts with none in memory.
A valid-invalid bit in each page-table entry shows whether the page is in memory; invalid causes a page-fault trap.
Fault handling: trap to OS; check the reference is legal; find a free frame; read the page from disk; update the page table; restart the instruction.
If no frame is free, a replacement algorithm picks a victim. The dirty bit shows whether the page changed; a clean victim is just overwritten, so one disk transfer replaces two.
FIFO replaces the oldest page (Belady's anomaly possible), LRU the least recently used, Optimal the page unused for longest in future (best, not implementable).
Thrashing is more paging than execution, so CPU utilization collapses. Causes: too few frames, too high multiprogramming, poor replacement. Cure: working set (frames for the current locality) or fewer processes.
Memory-mapped files (mmap) map a file into the address space, so file I/O becomes memory access and processes share pages.
Non-contiguous allocation avoids external fragmentation and enables virtual memory, at the cost of table overhead and complex hardware.

Example. Page faults:

String	Frames	FIFO	LRU	Optimal
1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5	4	12	12	10
7 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1	3	14	12	9
7 0 1 2 0 3 0 4 2 3 0 3	3	10	9	7

String 1 extended with 4 2, Optimal, gives 11. LRU beats FIFO on string 3 (9 against 10) because a recently used page is likely to be reused.

Answer frame. Numerical: state the rule, draw the frame table, mark each fault, end with the bold total. Definition: virtual memory, demand paging, fault steps, advantages. Thrashing: define, causes, cure.

Asked: [14 marks] (Nov 2019, Jun 2020, Nov 2023, Jun 2025) String 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, four frames: FIFO, LRU; and 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 3 frames: FIFO or LRU better. Asked: [14 marks] (May 2019) Short notes: Linux file system; page replacement; programmed I/O; demand paging. Asked: [7 marks] (May 2019, Jun 2020) Virtual memory and advantages; demand paging. Asked: [7 marks] (Jun 2020) What is thrashing? Its causes. Asked: [7 marks] (Jun 2020) Dirty bit for performance during page fault. Asked: [7 marks] (Nov 2023, Jun 2025) Faults of LRU, FIFO, Optimal: 7 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, 3 frames; Optimal: 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2, four frames. Asked: [7 marks] (Nov 2023) Virtual memory; advantages and disadvantages of non-contiguous allocation. Asked: [7 marks] (Jun 2024) Benefits of mapping objects into virtual memory. Asked: [7 marks] (Jun 2026) Paged segmentation and virtual memory with demand paging.

Last-minute revision

A process is a program in execution; the PCB holds PID, state, PC, registers, scheduling, memory, accounting and I/O info.
Five states: new, ready, running, waiting, terminated.
$WT = TAT - BT$, $TAT = CT - AT$; Jun 2020 averages: FCFS 5.2, SJF 4.6, RR (q=1) 8.2.
SJF gives minimum average waiting time; aging cures starvation; RR with a huge quantum becomes FCFS.
Threads share code, data and files but own stack, registers and PC.
Paging: internal fragmentation only; segmentation: external only; physical = base + offset if offset < limit, else trap.
Logical address bits = 8 + 10 = 18; Jun 2024 answers 649, 2310, trap, 1727.
Faults: 4 frames string 1: 12, 12, 10; 3 frames string 2: 14, 12, 9 (FIFO, LRU, Optimal).
$EAT = (1-p)\,ma + p\,T_{fault}$; a dirty bit saves the write-back of clean pages; thrashing is cured by the working set.

Memory hooks

Segment check: limit before base.
Paging = fixed pieces, internal waste; segmentation = logical pieces, external waste.
A thread owns Stack, Registers, PC; shares Code, Data, Files.

Coverage checklist

Process Concept: PCB, components, states.
Scheduling Concepts: no past question.
Types of Schedulers: three schedulers, differences.
Process State Diagram: states and transitions.
Scheduling Algorithms: Gantt, FCFS vs SRTF, starvation, RR pointers, comparison.
Algorithms Evaluation: no past question.
System calls for Process Management: fork, exec, wait, exit.
Multiple Processor Scheduling: with the Jun 2026 threads question.
Concept of Threads: TCB, thread vs process.
Different Memory Management Techniques – Partitioning, Swapping, Segmentation, Paging, Paged Segmentation, Comparison of these techniques: address bits, segment translation and table, comparisons.
Techniques for supporting the execution of large programs: Overlay, Dynamic Linking and Loading: overlay, linking, loading.
Virtual Memory – Concept, Implementation by Demand Paging etc: replacement numericals, demand paging, thrashing, dirty bit, mmap.