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

How unit 3 is examined

Covers how the OS allocates main memory (partitioning, swapping, paging, segmentation), how large programs run (overlay, dynamic linking and loading, virtual memory) and the page-replacement numericals. Marks sit in page replacement, segmentation, dynamic linking and loading, and virtual memory.

Different Memory Management Techniques – Partitioning

Not asked since 2022

Definition. Partitioning divides main memory into blocks, and each process is loaded into one contiguous partition.

Key points.

In fixed (static) partitioning the partition sizes are set at boot time, so a process must fit in a partition at least as large as itself.
Fixed partitioning causes internal fragmentation, which is the unused space inside a partition when the process is smaller than the partition.
In variable (dynamic) partitioning a partition is created exactly as large as the arriving process, so there is no internal fragmentation.
Variable partitioning causes external fragmentation, where free holes are scattered and no single hole fits a new process; compaction can join the holes.
Hole selection uses first fit (first hole big enough), best fit (smallest hole big enough) or worst fit (largest hole).

Swapping

Definition. Swapping temporarily moves a process from main memory to a backing store (disk) and brings it back later, so that more processes can be run than fit in memory.

Key points.

Moving a process out is called roll out and bringing it back is roll in; a lower-priority process is rolled out so a higher-priority one can be loaded.
The backing store must be a fast disk large enough to hold copies of all memory images.
Most of the swap time is transfer time, which is proportional to the amount of memory swapped.
A process waiting for I/O should not be swapped out unless the I/O uses OS buffers, otherwise the data would arrive in the wrong process.

Segmentation

Definition. Segmentation is a memory management scheme in which a program is divided into variable-sized logical units called segments (main, function, stack, data), and each segment is placed anywhere in memory.

Key points.

A logical address is a pair $(s, d)$, where $s$ is the segment number and $d$ is the offset inside the segment.
The segment table has one entry per segment, holding its base (starting physical address) and limit (length).
The segment number indexes the segment table; the segment table base register (STBR) locates the table and the segment table length register (STLR) gives the number of segments.
The hardware compares the offset $d$ with the limit; if $d \ge$ limit, an addressing-error trap goes to the OS.
If the offset is legal, the physical address is base plus offset.
Segmentation matches the user's view of a program, allows sharing and protection per segment, and has no internal fragmentation.
Its drawback is external fragmentation, because segments are of unequal size.

Formula. Physical address $= \text{base}[s] + d$ if $d < \text{limit}[s]$, else trap.

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 517 252" width="517" height="252" role="img" aria-label="Segmentation hardware. CPU sends (s, d); ST = segment table (base, limit); Cmp = check d < limit; Mem = physical memory; Trap = addressing error."><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="ah4" 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="ahh4" 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(#ah4)"/><path class="e" d="M231,40 L320,40" marker-end="url(#ah4)"/><path class="e" d="M360,40 L449,40" marker-end="url(#ah4)"/><path class="e" d="M341,59 L341,184" marker-end="url(#ah4)"/><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="253" y="31" width="47.1" height="18" rx="9"/><text class="t" x="276.5" y="40" dy=".35em" text-anchor="middle">limit</text></g><g class="wl"><rect x="378.4" y="31" width="54.3" height="18" rx="9"/><text class="t" x="405.5" y="40" dy=".35em" text-anchor="middle">base+d</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">d>=limit</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="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">Cmp</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">Mem</text><rect class="n" x="316" y="197" width="50" height="30" rx="15"/><text class="t" x="341" y="212" dy=".35em" text-anchor="middle">Trap</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Segmentation hardware. CPU sends (s, d); ST = segment table (base, limit); Cmp = check d < limit; Mem = physical memory; Trap = addressing error.</figcaption></figure>

Example. Segment table (Jun 2024): seg 0 (base 219, limit 600), seg 1 (2300, 14), seg 2 (90, 100), seg 3 (1327, 580), seg 4 (1952, 96). The first digit is the segment and the rest is the offset.

Logical	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, illegal
3400	3, 400	400 < 580	1327 + 400 = 1727

649, 2310, trap (illegal), 1727.

Answer frame. Open by defining segmentation and the segment table; draw the hardware figure with s, d, the table, the limit comparison and base + d; then develop points 1-5 in order, and add points 6-7; close with the advantage of logical division and the drawback of external fragmentation. For the numerical, write the formula, split each address into s and d, compare with the limit, and mark illegal ones as trap.

Asked: [7 marks] (Nov 2023) What is Segmentation? Explain virtual to physical address mapping in a segmented system with the help of a diagram. Asked: [7 marks] (Jun 2024) Consider the following segment table. What are the physical addresses for the logical addresses i) 0430 ii) 110 iii) 2500 iv) 3400? Pitfall: Adding the offset without first checking it against the limit; an offset beyond the limit is a trap, not an address.

Paging

Definition. Paging divides logical memory into fixed-size pages and physical memory into frames of the same size, so a process can be loaded into any free frames without needing contiguous memory.

Key points.

A logical address is split into page number $p$ and page offset $d$; the page table maps $p$ to a frame number $f$, and the physical address is $f \times \text{page size} + d$.
Paging removes external fragmentation, but the last page of a process may be partly empty, which gives internal fragmentation.
Each process has its own page table, held in memory and located by the page table base register (PTBR).
A Translation Lookaside Buffer (TLB), a small associative cache of page-table entries, avoids the extra memory access for the table.
Effective access time is $\text{EAT} = h \cdot (t_{tlb} + m) + (1-h)(t_{tlb} + 2m)$, where $h$ is the hit ratio and $m$ is the memory access time.

Paged Segmentation

Definition. Paged segmentation divides a program into segments and then divides each segment into fixed-size pages, combining the logical view of segmentation with the frame allocation of paging.

Key points.

The logical address is (segment, page, offset); each segment has its own page table, and the segment table entry points to that page table.
Only the last page of each segment wastes space, so external fragmentation is removed.
Sharing and protection stay at segment level, while allocation is at frame level.
It needs two table lookups per reference, so it is slower unless a TLB is used (as in MULTICS and Intel x86).

Comparison of these techniques

Definition. Paging uses equal fixed-size pages and is invisible to the user, while segmentation uses unequal logical segments and is visible to the user.

Key points.

Paging divides memory into fixed-size frames, so it has no external fragmentation, but the last page gives internal fragmentation.
Segmentation uses variable-sized segments, so it has no internal fragmentation, but external fragmentation appears as segments come and go.
Internal fragmentation is wasted space inside an allocated block; external fragmentation is free space that exists but is split into holes too small to use.
Paging uses a page table (page to frame); segmentation uses a segment table (base and limit) and segment descriptors.
Segmentation follows the logical structure of the program, so sharing and protection are natural; paging ignores that structure.

Basis	Paging	Segmentation
Unit size	Fixed	Variable
Seen by user	No	Yes
Table	Page table	Segment table (base, limit)
External fragmentation	None	Yes
Internal fragmentation	Yes (last page)	None
Sharing and protection	Harder	Easy, per segment

Answer frame. Open by defining paging (pages, frames, page table) and segmentation (segments, descriptors); draw the comparison table; explain internal versus external fragmentation; close by saying paging removes external fragmentation and segmentation aids logical division.

Asked: [7 marks] (Jun 2023) Explain paging and segmentation. How are they helpful in removing fragmentation?

Techniques for supporting the execution of large programs: Overlay

Definition. Overlay is a technique in which only the instructions and data needed at a given time are kept in memory, and a later part of the program is loaded over the space of a part no longer needed.

Key points.

It lets a program larger than the available memory run, by dividing it into a root (always resident) and overlay segments that share the same area.
A two-pass assembler is the classic example: pass 1 and pass 2 are never needed together, so they occupy the same area in turn.
The programmer designs the overlay structure and an overlay driver loads the parts, which is complex and hard to maintain.
Virtual memory has largely replaced overlays because it does the same job automatically.

Dynamic Linking and Loading

Definition. Dynamic loading loads a routine into memory only when it is first called, and dynamic linking postpones the linking of library routines until run time.

Key points.

Overlay keeps only the currently needed part of a program in memory and replaces it with the next part when required, so a program larger than memory can run; the programmer defines the overlay structure.
In static linking the linker copies all library routines into the executable before run time, so every program carries its own copy of the library.
In dynamic linking the executable contains only a stub for each library call; at run time the stub finds the library routine, loads it if absent, and replaces itself with the routine's address.
A dynamically linked library (DLL or shared object) has one copy in memory shared by all processes, which saves memory and disk space.
Library updates or bug fixes reach every program without relinking, but the OS must check that a process may use a shared routine.
In dynamic loading the main program is loaded first, and a routine stays on disk in relocatable form until it is called; the loader then loads it and updates the address table.
Dynamic loading never loads unused routines (such as error handlers), so memory use is smaller and start-up is faster.
Neither needs special OS support for the programmer, but both give better memory utilisation and support large programs.

Basis	Static linking	Dynamic linking
Linking time	Before execution	At run time
Library copy	In every executable	One shared copy
Executable size	Large	Small (stub only)
Library update	Needs relinking	Automatic

Answer frame. Open by defining overlay (points 1), then dynamic linking and loading; draw the static versus dynamic linking table; develop points 2-5 for linking and 6-7 for loading; close by saying both keep only needed code in memory, saving memory and aiding memory management.

Asked: [7 marks] (Jun 2024, Jun 2026) What is Overlay? How to dynamic linking and loading perform in memory management?

Virtual Memory – Concept

Definition. Virtual memory is a technique that lets a process execute although only part of it is in main memory, by using disk as an extension of RAM, so the logical address space can be far larger than physical memory.

Key points.

Programs seldom use all their code at once (error routines, unused tables), so only the needed pages are kept in memory.
It is usually implemented by demand paging, where a page is brought in only when it is referenced.
More processes fit in memory at once, so CPU utilisation and throughput rise.
Programmers are freed from memory size limits, and less I/O is needed to load or swap a process.
Its costs are the extra hardware and page tables, page-fault handling time, and thrashing if too few frames are given.

Non-contiguous allocation (Nov 2023).

Advantages: a process can use scattered free blocks, so external fragmentation is avoided or reduced and memory utilisation is high.
Advantages: it supports virtual memory, sharing of pages or segments, and easy growth of a process.
Disadvantages: page or segment tables use memory and need translation hardware, so each access is slower.
Disadvantages: paging gives internal fragmentation, segmentation gives external fragmentation, and management is more complex.
Contiguous allocation is simple and fast with no table, but wastes memory through fragmentation and cannot run a process larger than a hole.

Memory-mapped objects (Jun 2024). Mapping a file into the virtual address space (the mmap call) lets the process read and write the file as ordinary memory.

It simplifies I/O, because file access becomes normal loads and stores instead of read and write system calls.
Pages are loaded on demand, so only the parts of the file actually touched are read, which reduces memory use.
Several processes can map the same file and share the same physical pages, which gives fast sharing and communication.
It avoids copying data between kernel buffers and user memory, so access is faster.
Example: p = mmap(0, len, PROT_READ, MAP_SHARED, fd, 0); then p[i] reads byte $i$ of the file directly.

Answer frame. Open with the virtual memory definition and mention demand paging; draw a small figure of pages mapped between virtual memory, RAM and disk if time permits; develop points 1-5; close with "virtual memory makes memory look larger than it is". For Nov 2023, add the advantages and disadvantages list and contrast with contiguous allocation; for Jun 2024, define memory-mapped objects and give the four benefits with the mmap example.

Asked: [7 marks] (Nov 2023) Explain virtual memory in operating system. Discuss the advantages and disadvantages of non contiguous storage allocation. Asked: [7 marks] (Jun 2024) What are the benefits of mapping objects into virtual memory? Explain in detail.

Implementation by Demand Paging etc.

Definition. Demand paging loads a page into memory only when it is referenced; a reference to a page not in memory raises a page fault, and a page replacement algorithm chooses the victim when no frame is free.

Key points.

Each page-table entry has a valid/invalid bit; invalid means the page is not in memory, and access to it causes a page-fault trap.
On a page fault the OS finds the page on disk, gets a free frame (or picks a victim), reads the page in, updates the page table and restarts the instruction.
FIFO replaces the oldest page; it is simple but can show Belady's anomaly, where more frames give more faults.
Optimal (OPT) replaces the page whose next use is farthest in the future; it gives the fewest faults but cannot be implemented, and is used as a benchmark.
LRU replaces the page not used for the longest time; it is close to OPT, has no Belady's anomaly, and needs a counter or stack.
Page fault rate is measured as faults divided by references, and hits are references that find the page in a frame.

Formula. Effective access time $\text{EAT} = (1-p)\,m + p \cdot t_{fault}$, where $p$ is the page-fault rate and $m$ is the memory access time.

Example 1. Reference string 7 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, 3 frames. F is a fault, H a hit.

Ref	7	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
FIFO	F	F	F	F	F	H	F	F	H	F	F	H	F	F	F	H	F	H	F
LRU	F	F	F	F	F	H	F	F	F	F	H	H	F	H	F	H	F	H	H
OPT	F	F	F	F	F	H	F	H	H	F	H	H	F	H	H	H	F	H	H

Frames after the first faults are 7, 7 1, 7 1 2; then 0 replaces 7 in FIFO and LRU and 7 in OPT (7 is used last), and so on. Faults counted: FIFO 14, LRU 12, OPT 9.

FIFO = 14, LRU = 12, Optimal = 9 page faults.

Example 2. Optimal, 4 frames, string 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2. Faults occur at 1, 2, 3, 4 (fill), 5 (evict 2), 6 (evict 3), 7 (evict 1), 8 (evict 6), 9 (evict 4), 4 (evict 7), 2 (evict 5 or 9); all other references are hits.

Optimal = 11 page faults.

Answer frame. Open by stating the reference string, the frame count and the replacement rule of each algorithm; draw one table per algorithm showing the frames at each fault; count faults under each and compare (OPT < LRU < FIFO); close with the boxed totals and the note that OPT is only a benchmark.

Asked: [7 marks] (Nov 2023, Jun 2025) How many page faults does the LRU, FIFO and Optimal page replacement algorithm produce 7 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 assume frame size is 3? Also: page faults for optimal replacement with four frames for 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2. Pitfall: In LRU a hit must refresh the page's recency, and in OPT ties are broken freely; the count stays the same but forgetting the refresh changes the count.

Memory management in UNIX & Windows

Definition. UNIX uses swapping and demand paging with a page-replacement daemon, while Windows uses demand paging with a per-process virtual address space and a page file.

Key points.

Early UNIX used swapping of whole processes; modern UNIX uses demand paging with a two-handed clock (approximate LRU) algorithm run by the page daemon.
The UNIX kernel keeps a free-frame pool and starts replacing pages when the free count drops below a threshold.
Windows gives each process a private 4 GB (32-bit) virtual address space, split into user and system halves, and uses demand paging with clustering.
Windows keeps a page file on disk, a working set per process, and trims the working set when free memory is low.

Last-minute revision

Partitioning: fixed gives internal fragmentation, variable gives external fragmentation; compaction removes external.
Segmentation physical address = base + offset, valid only if offset < limit, else trap.
Jun 2024 segments: 0430 = 649, 110 = 2310, 2500 = trap, 3400 = 1727.
Paging: fixed pages and frames, no external fragmentation, page table maps page to frame; TLB caches entries.
Overlay keeps only the needed part in memory; dynamic linking uses a stub; dynamic loading loads on first call.
Virtual memory = partial process in RAM, disk as extension; implemented by demand paging.
Page fault = reference to a page not in memory (valid bit is 0).
FIFO oldest, LRU least recently used, OPT farthest next use.
For 7 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames: FIFO 14, LRU 12, OPT 9.
Optimal with 4 frames on 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2: 11 faults.
Belady's anomaly occurs in FIFO, never in LRU or OPT.

Memory hooks

Paging = Pages equal, Physical frames; Segmentation = Sections of unequal size.
Fixed partition = Fragment inside; Variable partition = Fragment outside.
FIFO First in, first out; LRU looks back; OPT looks forward.
Segment check: "d below limit, else trap".
Dynamic = "only when called".

Coverage checklist

Different Memory Management Techniques – Partitioning: covered, no past questions.
Swapping: covered, no past questions.
Segmentation: Nov 2023 diagram question, Jun 2024 segment-table numerical.
Paging: covered, no past questions.
Paged Segmentation: covered, no past questions.
Comparison of these techniques: Jun 2023 paging and segmentation with fragmentation.
Techniques for supporting the execution of large programs: Overlay: covered, overlay definition also in the Jun 2024 and Jun 2026 question.
Dynamic Linking and Loading: Jun 2024, Jun 2026 overlay and dynamic linking and loading.
Virtual Memory – Concept: Nov 2023 virtual memory and non-contiguous allocation, Jun 2024 memory-mapped objects.
Implementation by Demand Paging etc.: Nov 2023, Jun 2025 page-fault numericals (3 and 4 frames).
Memory management in UNIX & Windows: covered, no past questions.

Account

Operating Systems (AD-405) - Unit 3 Short Notes

How unit 3 is examined

Different Memory Management Techniques – Partitioning

Swapping

Segmentation

Paging

Paged Segmentation

Comparison of these techniques

Techniques for supporting the execution of large programs: Overlay

Dynamic Linking and Loading

Virtual Memory – Concept

Implementation by Demand Paging etc.

Memory management in UNIX & Windows

Last-minute revision

Memory hooks

Coverage checklist