Unit 8 Self-Check Quiz

Question

Question 1

List the levels of the memory hierarchy from fastest to slowest, and give a typical access time and size for each.

Answer 1

Registers (hundreds of bytes, sub-nanosecond), L1 cache (32–64 KB, ~1 ns), L2 cache (256 KB – 1 MB, ~3 ns), L3 cache (8–64 MB, ~10 ns), main memory (gigabytes, ~100 ns), solid-state storage (terabytes, ~100 μs), magnetic disk (terabytes, ~10 ms), and archival storage (minutes to hours). Each level is larger and slower than the one above it, and the hierarchy works because of locality: the small fast levels keep the working set, and the large slow levels hold everything else.

Answer 2

Temporal locality: a location accessed recently is likely to be accessed again soon. Example: the loop counter in a tight loop; the same data structure used repeatedly. Spatial locality: a location near one that was just accessed is likely to be accessed soon. Example: the next element of an array; the next instruction after the current one; the fields of a struct. Caches exploit both: a cache line brings in a block of adjacent bytes (spatial) and keeps it around for a while (temporal). Programs that violate locality — pointer chasing through a linked list scattered in memory, or a column-major traversal of a large row-major array — run much slower than their access count would suggest.

Answer 3

Compile time. The compiler emits absolute addresses. Advantage: no translation overhead at load or run time. Disadvantage: the program must be loaded at a known address, and it cannot be moved once running. Load time. The compiler emits relocatable addresses; the loader fixes them up when the program is loaded. Advantage: the program can be loaded wherever there is room. Disadvantage: it cannot be moved after loading. Execution time. The compiler emits relocatable addresses; the MMU translates them on every access. Advantage: the process can be moved during execution, which makes paging, swapping, and dynamic memory allocation possible. This is the model used by all modern general-purpose systems.

Answer 4

The MMU (memory-management unit) is the hardware that translates every logical address issued by the CPU into a physical address. Its exact form depends on the memory-management scheme: in a simple base-and-limit scheme it adds a base register to the logical address and checks the result against a limit register; in a paging scheme it splits the address into page and offset, looks up the page table, and constructs the physical address; in a segmented scheme it indexes the segment table. The relocation register (or base register) holds the starting physical address of the currently running process. It is changed on every context switch, so the same logical address in two processes maps to two different physical addresses.

Answer 5

Dynamic loading is a technique in which a routine is loaded into memory only when it is first called. The program does not need the routine at startup, and the routine is loaded on demand (typically by the program itself, using a loader routine). Dynamic linking is a technique in which the linking of a library routine to the program is postponed until run time. The executable contains a stub for each library routine; when the stub is first called, it invokes the dynamic linker, which loads the library (if not already loaded) and patches the stub to point at the routine. The main practical difference: dynamic loading is chosen by the programmer for a routine that may not be needed; dynamic linking is chosen by the build system for all shared libraries, saving disk space and memory when several programs use the same library.

Answer 6

The data section contains initialised global and static variables — those with a non-zero initial value at program start. The BSS section contains uninitialised global and static variables, and variables initialised to zero. The difference is that the BSS occupies no space in the executable file: the loader simply zeroes the corresponding memory when the program is loaded. For a program that declares large global arrays without initialising them, the BSS can be much larger than the data section, and the executable remains small. This is why size reports the BSS separately.

Answer 7

First-fit: scan the free list from the beginning and take the first hole large enough. Fastest, because it can stop at the first fit. Tends to leave small holes near the start of memory. Best-fit: scan the entire free list and take the smallest hole large enough. Produces the smallest leftover at each allocation, but the small leftovers accumulate as unusable external fragmentation. Worst-fit: scan the entire free list and take the largest hole. Produces the largest leftover, which is more likely to be useful for a future allocation, but tends to fragment large holes quickly. Empirically, first-fit and best-fit are comparable in utilisation; first-fit is faster. Worst-fit is generally the worst of the three.

Answer 8

First-fit: the first hole ≥ 250 KB. The 100 KB hole is too small; the 500 KB hole is the first fit. Chosen: 500 KB. Best-fit: the smallest hole ≥ 250 KB. The holes ≥ 250 KB are 500, 300, and 600. The smallest is 300. Chosen: 300 KB. Worst-fit: the largest hole. That is 600 KB. Chosen: 600 KB. After the allocation: first-fit leaves a 250 KB hole; best-fit leaves a 50 KB hole; worst-fit leaves a 350 KB hole. The 50 KB leftover is likely to be unusable for future requests, illustrating why best-fit can produce poor utilisation.

Answer 9

External fragmentation is the situation in which there is enough total free memory to satisfy a request, but no single contiguous hole is large enough. It arises in contiguous allocation because allocation and release happen in arbitrary order, leaving free space scattered between allocated blocks. Compaction is the technique of moving all allocated blocks to one end of memory so that the free space is consolidated into a single large hole. It eliminates external fragmentation but is expensive (every byte must be moved) and it requires that processes can be relocated at run time — which means address binding must be done at execution time, with an MMU and a relocation register or page table. Compaction is rarely used in general-purpose systems because paging avoids external fragmentation entirely.

Answer 10

Internal fragmentation is the wasted space inside an allocated block: the block is larger than the request, and the difference is unusable. Example: a system that allocates memory in fixed-size pages of 4 KB. A process requests 100 bytes; it receives one 4 KB page, and the remaining 3996 bytes are wasted (they cannot be used by another process, because the page is allocated to this one). Internal fragmentation is inherent in any fixed-size allocation scheme — paging, block allocators, and slab allocators all have it. It is mitigated by choosing a small allocation unit, but small units increase the bookkeeping overhead and, in a paging system, the size of the page tables.

Answer 11

The second choice. Execution-time binding means the MMU translates every logical address on every access, so the physical location of the process can change without the process being aware — the MMU's base register or page table is simply updated. This is what makes paging, swapping, and dynamic memory allocation possible. The first, third, and fourth choices are incorrect: a stack is normal in any binding scheme; loading at a fixed address is a feature of compile-time binding; and shared libraries are a feature of the loader and dynamic linker, independent of the binding time.

Answer 12

A segment table entry contains: a base (the starting physical address of the segment), a limit (the length of the segment), and protection bits (read, write, execute). On a segmented access with logical address ⟨s, d⟩, the MMU:

Checks that s is a valid segment number.
Reads the segment table entry for s.
Checks that the offset d is less than the limit. If not, raises a trap (segmentation fault).
Checks that the access type (read, write, or execute) is permitted by the protection bits. If not, raises a trap (protection fault).
Computes the physical address as base + d.

The checks make segmentation a natural vehicle for protection: each segment has a clear set of access rights, and an out-of-bounds access is caught by the MMU without any software intervention.

Answer 13

Because segments are logical units, and different processes often need to share the same logical unit — for example, two processes running the same program share the code segment, or two processes using the same library share its code segment. In a segmented system, both processes' segment tables can point to the same physical segment, and the protection bits (read-only, executable) prevent either process from modifying it. In a contiguous allocation system, sharing is possible only if the two processes happen to have the shared code at the same physical address, which is difficult to arrange and fragile. Paging supports sharing at the page level, but the pages of a shared library must be mapped into each process's address space at the same virtual address (or the code must be position-independent), which is more complex than sharing a whole segment.

Answer 14

(a) ⟨0, 0x100⟩: offset 0x100 < limit 0x3000. Physical = 0x1000 + 0x100 = 0x1100. (b) ⟨1, 0x1200⟩: offset 0x1200 = 4608. Limit of segment 1 is 0x1000 = 4096. 4608 ≥ 4096, so the offset exceeds the limit. Trap (segmentation fault). (c) ⟨2, 0x1000⟩: offset 0x1000 = 4096. Limit of segment 2 is 0x2000 = 8192. 4096 < 8192. Physical = 0x5000 + 0x1000 = 0x6000.

Answer 15

A segmentation fault is raised when a process accesses an address that is not valid — outside the limits of any of its segments, or in violation of the protection bits of the segment it does belong to. It is a programming error: the process is not supposed to access that address at all, and the kernel's response is to deliver SIGSEGV, which by default terminates the process. A page fault is raised when a process accesses a valid virtual address whose page is not currently resident in physical memory. It is not an error: the kernel's page-fault handler loads the page (from disk or from the page cache), updates the page table, and restarts the faulting instruction. Page faults are a normal part of demand paging; a program may generate thousands of them without anything being wrong. The confusion arises because the kernel delivers SIGSEGV when a page fault cannot be resolved (the address is not valid), but the two events are distinct.

Answer 16

ASLR randomises the base addresses of the stack, heap, and shared libraries (and, on PIE binaries, the text segment) at each program launch. The program therefore cannot be compiled with absolute addresses for these regions — the addresses are not known until run time. Execution-time address binding (via the MMU and page tables) is what allows the kernel to place the regions at random base addresses and translate the program's logical addresses to the actual physical addresses. Without an MMU, the program's addresses would have to be fixed at link time, and ASLR would be impossible. ASLR is a security feature: it makes it harder for an attacker who has found a memory-corruption vulnerability to jump to a known address.

Answer 17

Start: one hole of 1024 KB. Step 1: P1 takes the first 100 KB. Memory: [P1: 0–100][free: 100–1024] = 924 KB free. Step 2: P2 takes the next 200 KB. Memory: [P1: 0–100][P2: 100–300][free: 300–1024] = 724 KB free. Step 3: P3 takes the next 150 KB. Memory: [P1: 0–100][P2: 100–300][P3: 300–450][free: 450–1024] = 574 KB free. Step 4: P2 released. Memory: [P1: 0–100][free: 100–300][P3: 300–450][free: 450–1024]. Step 5: P4 (120 KB) takes the first fit, which is the 200 KB hole at 100–300. Memory: [P1: 0–100][P4: 100–220][free: 220–300][P3: 300–450][free: 450–1024]. Free holes: 80 KB at 220–300 and 574 KB at 450–1024. Total free = 654 KB, but the largest contiguous hole is 574 KB. A request for 600 KB would fail despite 654 KB being available — this is external fragmentation.

Answer 18

The text segment contains the executable machine instructions. It is read-only and executable, and it is usually shared between processes running the same program. The loader maps it directly from the executable file (or from the page cache), read-only. The data segment contains initialised global and static variables. It is read-write, and it is private to each process. The loader maps it from the executable file with copy-on-write semantics: initially the pages are shared with the file, but the first write to a page causes a private copy to be made. The BSS (uninitialised globals) is also part of the data segment, but it occupies no space in the executable file; the loader allocates zero-filled pages for it.

Answer 19

The relocation register is updated to the base address of the incoming process. This is necessary because each process has its own logical-to-physical mapping: the same logical address in two processes may correspond to two different physical addresses. In a base-and-limit system, the base register holds the starting physical address of the current process, and the MMU adds it to every logical address. On a context switch, the kernel saves the outgoing process's base (in its PCB) and loads the incoming process's base. In a paging system, the equivalent action is to load the new process's page-table base register (CR3 on x86). The cost of this update is small, but the indirect cost — TLB and cache pollution — is the main reason context switches are expensive.

Answer 20

Worst-fit's intention is good: by leaving the largest possible leftover, it hopes to keep large holes available for large future requests. In practice, worst-fit tends to fragment the largest holes quickly, so after a few allocations there are no large holes left at all. Empirical studies show that worst-fit produces worse utilisation and higher fragmentation than first-fit or best-fit, and it is slower because it must scan the entire free list to find the largest hole. The algorithm is a textbook example of a plausible idea that does not survive measurement.

Answer 21

A page is a fixed-size unit of physical memory (typically 4 KB) with no inherent meaning: the same page may hold code, data, or stack, and a single logical object may span many pages. A segment is a variable-size logical unit chosen by the programmer or compiler: a code segment, a data segment, a stack segment. Each has a clear purpose and a natural set of access rights. Advantage of paging: it eliminates external fragmentation and makes physical memory allocation trivial (any free frame can satisfy any page). Advantage of segmentation: it gives natural protection and sharing at the granularity of logical objects, without any additional bookkeeping.

Answer 22

4 KB pages mean 2¹² bytes per page, so the offset is 12 bits and the page number is 20 bits. The page table has 2²⁰ = 1,048,576 entries. At 4 bytes per entry, that is 4 MB per process. If a system has 100 processes, the page tables alone consume 400 MB. Worse, most of the table is unused: a typical process uses only a small fraction of its 4 GB virtual address space, but the single-level table must cover all of it. This is the motivation for multi-level page tables, which allocate only the parts of the table that correspond to used virtual pages.

Answer 23

The BSS section contains uninitialised global and static variables and those initialised to zero. Its purpose is to avoid storing large zero-initialised arrays in the executable file. The data section stores initialised variables with their values; each byte of the data section occupies a byte in the executable. The BSS does not: the loader simply allocates zero-filled pages for it at program start. A program with a 1 MB global array that is not explicitly initialised would have a 1 MB data section if it were placed in data, but a 0-byte BSS contribution. The separation is thus a form of compression in the executable file, and it makes the loader's job easier for large zero-initialised structures.

Answer 24

Paging decouples the virtual address space from the physical layout: any virtual page can be placed in any physical frame, so the system never suffers external fragmentation and never needs compaction. The cost — a page-table lookup on every access — is mitigated by the TLB, which makes the translation almost free for programs with locality, so the practical cost of paging is small compared to the flexibility it provides.

Unit 8 Self-Check Quiz

Multiple choice and short answer

Ready for the graded quiz?