Contiguous Memory Allocation
---------------------------------------

First-fit:

 Job#   Memory requested
 J1     100K
 J2     200K
 J3     300K    <=== STILL BLOCKED
 J4     100K

 Mem loc   Mem size   Status   Job size   Internal Fragm
 A          300K      J1       100K       200K
 B          150K      J4       100K        50K
 C          500K      J2       200K       300K
 D          200K      Free
TOTALS ==> 1150K                          550K



 Best-fit:

 Job#   Memory requested
 J1     100K
 J2     200K
 J3     300K
 J4     100K


 Mem loc   Mem size   Status   Job size   Internal Fragm
 B          150K      J1       100K        50K
 D          200K      J2       200K         0K
 A          300K      J3       300K         0K
 C          500K      J4       100K       400K
TOTALS ==> 1150K                          450K






                   -----------------------
   Ready Queue:         P1  P3  P2  P4  P5
                   -----------------------

                   -----------------------
     I/O Queue:                     P7  P8
                   -----------------------


            Which process should we swap out?
                                                P7


           frame#
     0 ==>  0000  00
     4 ==>  0001  00
     8 ==>  0010  00
    12 ==>  0011  00
    16 ==>  0100  00
    20 ==>  0101  00
    24 ==>  0110  00
    28 ==>  0111  00



 Using a non-contiguous allocation, a logical address
 is represented using 32 bits.  Of these bits, the
 high-order 18 bits represent the page number.

 (a) What is the total logical memory space?

 (b) How many pages are there?

 (c) What is the page size?

 (d) How would logical address 1,234,567 be mapped to
     a physical memory address?

 (e) If a process requires 437,554,122 bytes of memory,
     how many pages would be required?

     How many bytes are wasted due to internal frag.?



 Without using a TLB, if a single memory access
 takes 200ns, how long does a paged memory access take?

    400ns  =  200ns + 200ns


 With a TLB, if a single memory access takes 200ns,
 a "TLB hit" takes 20ns, and the TLB hit ratio is 75%,
  what is the effective memory-access time?

    265ns

    0.75 * 20ns  +  0.25 * 200ns  +  200ns

       15ns      +       50ns     +  200ns



    20ns   +   0.25 * 200ns       +  200ns

    20ns   +       50ns           +  200ns   =  270ns




 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 offest.

 (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.?







      32
 (a) 2

      18
 (b) 2

      14
 (c) 2   = 16384


 (d) logical memory address: 1,234,567

    convert to binary:
             |
      1001011|01011010000111
             |
      page #    page offest

 1+2+8+64 = 75      1+2+4+128+512+1024+4096


  e.g. page table maps page#75 to frame#20

                       |
physical addr: 00010100|01011010000111
                       |

               frame#      offset


 (e) Required bytes: 437,554,122

                    14
      page size is 2    = 16384

     437,554,122/16384 = 26707 pages
                         (rounded up)

 to determine internal fragmentation:

    26706 * 16384 = 437,551,104 bytes

     437,554,122 - 437,551,104 = 3018

      16384 - 3018 = 13366 bytes wasted