Operating Systems · Unit 3
Memory ManagementA program can only run while it is in main memory, and memory is shared by many programs at once. Memory management decides where each program goes, keeps programs from touching each other's memory, and lets a program run even when only part of it fits. 1. Logical and physical addressesThe CPU produces logical addresses (also called virtual addresses), counted from the start of the program. The memory hardware works with physical addresses, the real locations in RAM. The memory management unit (MMU) translates one into the other while the program runs. ExampleWith a relocation (base) register of 14000, logical address 346 becomes physical address 14000 + 346 = 14346. A limit register stops the program from reaching beyond its own area.
Because translation happens at run time, the OS can move a program to a different place in memory simply by changing its base register. 2. Contiguous allocation and fragmentationIn contiguous allocation each process occupies one continuous block of memory. Free blocks are called holes. When a process arrives, the OS picks a hole using one of three rules:
Solved exampleHoles of 100 KB, 500 KB, 200 KB, 300 KB and 600 KB (in that order). Processes of 212 KB, 417 KB, 112 KB and 426 KB arrive in that order.
Here only best fit places all four processes. In first fit and worst fit, 426 KB must wait even though the total free memory is larger than 426 KB: it is split into holes that are each too small. Two kinds of fragmentationExternal fragmentation: enough free memory exists in total, but not in one piece. Internal fragmentation: a process is given slightly more memory than it asked for, and the unused part inside its block is wasted. Compaction (moving processes together) removes external fragmentation but takes time.
3. PagingPaging removes external fragmentation by letting a process's memory be scattered. Physical memory is divided into fixed-size frames, and a process's logical memory into pages of the same size. Any page can go into any free frame. A page table records which frame holds each page. FormulasPage number p = logical address ÷ page size (whole part)
Offset d = logical address mod page size Physical address = frame number × page size + d Solved examplePage size is 1 KB (1024 bytes) and page 2 is stored in frame 5. Translate logical address 3000.
Page sizes are powers of two so the split is just a split of bits. A 32-bit logical address with 4 KB (212 byte) pages uses 12 bits for the offset and 20 bits for the page number, so the page table can have 220 = 1,048,576 entries. The TLBThe page table lives in memory, so every access would need two memory reads: one for the table, one for the data. A translation look-aside buffer (TLB) is a small, fast cache of recent translations that avoids the extra read most of the time. Exam tipEffective access time (EAT) = hit ratio × (TLB time + memory time) + miss ratio × (TLB time + 2 × memory time). With an 80% hit ratio, a 20 ns TLB and 100 ns memory: EAT = 0.8 × 120 + 0.2 × 220 = 140 ns.
Paging has no external fragmentation, but the last page of a process is usually not full, so it can have a little internal fragmentation. 4. SegmentationSegmentation divides a program into parts that match the programmer's view: code, data, stack, and so on. Each segment has its own length. A logical address is a pair (segment number, offset), and a segment table stores each segment's base and limit. ExampleSegment 2 has base 4300 and limit 400. Address (2, 53) maps to 4300 + 53 = 4353. Address (2, 500) is refused with a trap, because 500 is beyond the limit of 400.
5. Virtual memory and demand pagingVirtual memory lets a program run when only part of it is in RAM. With demand paging, a page is loaded only when it is first used. If the program touches a page that is not in memory, a page fault occurs:
If processes have too few frames, they fault constantly and spend more time swapping pages than running. This collapse in performance is called thrashing. 6. Page replacement, solvedWhen memory is full, the OS must choose a page to remove:
Reference string 1, 3, 0, 3, 5, 6, 3 with 3 frames. Frames are shown after each reference; F marks a page fault.
FIFO removed page 3 just before it was needed again; LRU kept it because it had been used recently. Belady's anomalyWith FIFO, more frames can cause more faults. For the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO gives 9 faults with 3 frames but 10 faults with 4 frames. LRU and Optimal never show this anomaly.
7. Quick revision
8. Practice questionsQ1. With a page size of 2 KB, find the page number and offset of logical address 5000. Answer: 2 KB = 2048 bytes. Page number = 5000 ÷ 2048 = 2, offset = 5000 − 4096 = 904. Q2. A system has a 90% TLB hit ratio, a 20 ns TLB and 100 ns memory. Find the effective access time. Answer: 0.9 × 120 + 0.1 × 220 = 108 + 22 = 130 ns. Q3. Which kind of fragmentation can paging suffer from, and why? Answer: Internal fragmentation only, because the last page of a process is usually not completely filled. |