Paging 1y4f3l

Paging • • • • • • •

permits the physical address space of a process to be noncontiguous whole process in main memory, but does not have to be contiguous split physical memory into fixed-sized blocks called frames split logical memory into blocks of same size called pages last page of process may not occupy an entire frame (i.e., some internal fragmentation) frame and page size are an efficiency issue; page size is between 512 bytes and 16 MB depending on the computer architecture paging increases context switch time, but overhead of page table decreases as page size increases logical address is a pair: (page number p, page offset d) which indexes into page table (which resides in the PCB). page table contains the base address of each frame in physical memory p must be in range of the pages d must be less than the page size physical address = frame_number * page_size + offset For instance, (2, 325). Does paging increase the context switch overhead? and if so, why? Overhead of page table decreases as the page size increases. Use s if page table small (< 256 entries). However, on most contemporary computers page table might be very large (> 1 million entries). Keep it in main memory and have 1 point to it, but that approach increases the context switch time. Solution: cache (translation look-aside-buffer or TLB) example: memory access = 100 ns cache search = 20 ns hit ratio = 80%

effective access time of hit = 120 ns effective access time of miss = 220 ns (0.8)(20+100) + (0.2)(20+100+100) = 0.8*120 + 0.2*220 = 96 + 44 = 140 ns 40% slowdown when compared to no paging. How does performance improve with a 98% hit ratio?

Page Table Structure Structure of the page table • • • •

main idea: page the page table itself hierarchical paging (applicable in 64-bit systems?) hashed page tables inverted page tables o decreases amount of memory required to store page table, but o increases what? o what about shared memory?

Segmentation • • • • • • • • • •

paging separates (and even blurs) the 's view of memory from physical memory segmentation is a memory management scheme which s the view of memory compiler automatically constructs segments reflecting the input program loader assigns these segments segment numbers logical address is: (segment name/num, offset) segmentation table: an array of (seg base, seg limit) pairs (2,53) → (4300+53) = 4353 eliminates internal fragmentation external fragmentation possible segmentation fault

Memory Management Techniques: a Summary • • • • • • •

single contiguous overlays fixed (static) partitions relocation (dynamic) partitions paging segmentation paged segmentation

• •

demand paging segmentation with demand paging

Intel Pentium uses pure segmentation (or segmentation with paging).

Memory Management Summary • •

goal: high degree of multiprogramming (most efficient use of memory). why? with a fixed memory size, how can we increase the degree of multiprogramming? six main ways all under the umbrella of packing as many processes as possible into main memory o dynamic loading o dynamic linking o swapping o sharing code o compaction o virtual memory

• • • •

memory management schemes range from simple single- approaches to complex multiprogramming schemes such paged segmentation most important factor is the hardware? why? a simple base or base/limit pair is sufficient for single and multiple partition schemes, but paging/segmentation require mapping tables as the memory management scheme becomes more complex, the time required to translate from a logical to physical address increases; page table o s o TLB o main memory

•

• •

to maximize memory use, we must reduce memory waste or fragmentation o fixed-size partitions (and paging to a small extent) suffer from internal fragmentation o variable-sized partitions and segmentation suffer from external fragmentation OS must also provide protection so that processes do not access data outside of their region in memory swapping: now part of the ready queue can exist in second memory; allows more processes to run than can be fit into main memory