Consider a two-level paging system for a 64-bit memory
 space.  The 26 high-order bits represent the outer
 page number (p1); the middle 24 bits represent the
 second-level page number (p2); the remaining bits
 represent the offset.

 (a) What is the total logical memory space?

 (b) How many top-level pages are there?

 (c) How many second-level pages are there?

 (d) What is the page size?

 (e) What does logical memory address 888,777,666,555
    map to?

 (f) If a process requires 400,000,000,000 bytes of mem,
    how many outer pages and second-level pages will
    it require?

    How many bytes are wasted due to internal frag.?



     64
 (a) 2   = 18,446,744,073,709,551,616

     26
 (b) 2   = 67,108,864

     24
 (c) 2   = 16,777,216 per top-level page

     14
 (d) 2   = 16,384

 (e) 11|001110111011110100011011|10111111111011

 (f) 400000000000 / 16384 = 24,414,063 (round up)

    24,414,063 / 16,777,216 = 2 (round up)


    Internal fragmentation: 8192


 Primary differences between segmentation and paging:
 (a) segments of a process differ in size
 (b) segment sizes are typically larger than page sizes
 (c) fewer segments per process


 Segment#    Memory requirement
 0           48K
 1           100K
 2           150K
 3           30K
 4           56K

 Segment#    Start addr (base)       Segment size (limit)
 0           10000                   48K
 1  (SQRT)   20000                   100K
 2           80000                   150K
 3           50000                   30K
 4           60000                   56K

 Advantages:
 (a) no internal fragmentation
 (b) easy to share segments
 (c) less overhead (fewer table entries than paging)
 (d) perhaps better application of principle of locality

 Disadvantage:
 (a) external frag requiring compaction



 Paging memory scheme
-----------------------------
Page size considerations:
-- small page size reduces internal fragmentation
----> best case: 0 wasted bytes
----> worst case: K - 1 wasted bytes where K is the page size
----> increase the number of pages, overhead, etc.
----> swap from disk becomes inefficient
-- too many page faults


 contiguous and noncontiguous memory allocation schemes
 are inherently wasteful because they load the entire
 process into memory




 Principle of locality ... and thrashing
 -- thrashing: insufficient frame allocation
 -- typically the number of frames allocated to a process
    is less than the size of the current locality

 Fetch policy (when to fetch a page from disk):
 -- demand paging
 -- pre-paging

 Algorithms for swapping out (replacing) frame(s):
 -- FIFO; Least Recently Used; Least Frequently Used