Assignment-9-Anderson.txt

Brian Anderson
Assignment 9 - Com S 352
April 4, 2012

[NOTE --> PLEASE USED A FIXED WIDTH FONT TO READ THIS DOCUMENT]


1. (25pts) Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order 
   from low-end to high-end of user memory space), how would the first-fit, best- fit, and 
   worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in the arriving order)?

Assumption:
- The five partitions are non-contiguous
- First & worst fit restarts at the beginning (top) 
  with each new allocation attempt

  +--- The label of the memory partition (for use below)
  |                                     
  |                   First Fit          Best Fit          Worst Fit
  |                   =========          ========          =========
  v                                         
+-----------+       +-----------+      +-----------+      +-----------+ 
| a) 100KB  |       |(free)100KB|      |(free)100KB|      |(free)100KB| 
+-----------+       +-----------+      +-----------+      +-----------+ 
    .....               .....              .....              .....     
+-----------+       +-----------+      +-----------+      +-----------+ 
| b) 500KB  |       ||  212KB  ||      ||  417KB  ||      ||  417KB  ||       
|           |       + - - - - - +      ||         ||      ||         || 
|           |       ||  112KB  ||      ||         ||      ||         || 
|           |       + - - - - - +      + - - - - - +      + - - - - - + 
|           |       |(free)176KB|      |(free) 83KB|      |(free) 83KB|
+-----------+       +-----------+      +-----------+      +-----------+ 
    .....               .....              .....              .....     
+-----------+       +-----------+      +-----------+      +-----------+ 
| c) 200KB  |       |   200KB   |      ||  112KB  ||      |   200KB   |       
|           |       |  (free)   |      + - - - - - +      |  (free)   | 
+-----------+       +-----------+      +-----------+      +-----------+ 
    .....               .....              .....              .....     
+-----------+       +-----------+      +-----------+      +-----------+ 
| d) 300KB  |       |   300KB   |      ||  212KB  ||      |   300KB   |       
|           |       |  (free)   |      + - - - - - +      |  (free)   | 
|           |       |           |      |(free) 88KB|      |           | 
+-----------+       +-----------+      +-----------+      +-----------+ 
    .....               .....              .....              .....
+-----------+       +-----------+      +-----------+      +-----------+
| e) 600KB  |       ||  417KB  ||      ||  426KB  ||      ||  212KB  ||       
|           |       ||         ||      ||         ||      ||         ||
|           |       ||         ||      ||         ||      + - - - - - +
|           |       ||         ||      ||         ||      ||  112KB  ||
|           |       + - - - - - +      + - - - - - +      + - - - - - +
|           |       |   183KB   |      |   174KB   |      |   276KB   |
|           |       |   (free)  |      |   (free)  |      |   (free)  |
+-----------+       +-----------+      +-----------+      +-----------+


----------------------+---------------------------+--------------------
First fit:            | Best Fit:                 | Worst Fit:
----------------------+---------------------------+--------------------
(Allocate the         | Allocate the smallest     |(Allocate the 
  first hole          | hole that is big enough)  |  largest hole)
----------------------+---------------------------+--------------------
212KB -> b            |  212KB -> d               |  212KB -> e
417KB -> e            |  417KB -> b               |  417KB -> b
112KB -> b (remainder)|  112KB -> c               |  112KB -> e (remainder)
426KB -> ?? no fit.   |  426KB -> e               |  426KB -> ?? no fit!
----------------------+---------------------------+--------------------


#########################################################################################
2. (25pts) Assuming a 4-KB page size, what are the page numbers and offsets 
   for the following address references (provided as decimal numbers):
   
    a. 2375, 
    b. 19366, 
    c. 30000, 
    d. 256, 
    e. 16385

Assumption:
 - (max) Physical/logical Address Space = 32,768 because part c has the highest address 30,000, 
   which would fit in an addressible space of this size. This would require a 15 bit address size. 
 - A Physical/logical address of 32,786 would have 'm' = 15 (2^15) => 32,768

Page size: 2^n = 4KB = 4,096 bytes
             n = 12

Page count = 8, bits required: 3, 0 indexed: 0-7

  Page Number    Page Offset
    +---------+---------------+
    | 3 bits  |    12 bits    |
    +---------+---------------+
       (m-n)          n

a. 3275 =>  (binary) 110011001011
                     000110011001011  (zero padded to 15 bits)
    Page:   (binary) 000 ->          (decimal) 0 [the first page]
    Offset: (binary) 110011001011 -> (decimal) 3,275

b. 19366 => (binary) 100101110100110
    Page:   (binary) 100 ->          (decimal) 4
    Offset: (binary) 101110100110 -> (decimal) 2,982
                     000000100000000
c. 30000 => (binary) 111010100110000
    Page:   (binary) 111 ->          (decimal) 7
    Offset: (binary) 010100110000 -> (decimal) 1,328
    
d. 256 =>   (binary) 000000100000000 (zero padded to 15 bit)
    Page:   (binary) 000 ->          (decimal) 0 
    Offset: (binary) 000100000000 -> (decimal) 256

e. 16385 => (binary) 100000000000001
    Page:   (binary) 100 ->          (decimal) 4
    Offset: (binary) 000000000001 -> (decimal) 1
    
    
#########################################################################################
3. (20pts) Consider a logical address space of 8 pages with 
      2,048 bytes per page, mapped onto a physical memory of 16 frames.

2^n = 2048 ==> n = 11 (page size)

           +--+--+--+--+--+--+--+--+
Logical -> | 0| 1| 2| 3| 4| 5| 6| 7|
(pages)    +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Physical-> | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
(frames)   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
          
a. How many bits are required in the logical address? 
   How many for page number and how many for page offset?

8 pages * 2048 bytes = 16,384 bytes total logical memory
16,384 = 2^14 ==> 14 bits

8 pages can be accessed with 3 bits (2^3 = 8) 
2048 bytes per page can be access with 11 bits.

Page Number    Page Offset
  +---------+---------------+
  | 3 bits  |    11 bits    |
  +---------+---------------+
   
b. How many bits are required in the physical address? 
   How many for frame number and how many for page offset?
   
16 frames * 2048 bytes per frame = 32,768 bytes total physical memory
32,768 = 2^15 ==> 15 bits

16 pages can be accessed with 4 bits (2^4 = 4) 
2048 bytes per page can be access with 11 bits.

Frame Number   Frame Offset
  +----------+---------------+
  | 4 bits   |    11 bits    |
  +----------+---------------+


#########################################################################################
4. (30pts) Consider a paging system with the page table stored in memory. 
   A memory reference takes 160 nanoseconds, we add a TLB, and 80 percent 
   of all page-table references are found in the TLBs, what is the effective 
   memory reference time? 
   
   (Assume that finding a page-table entry in the  TLBs takes zero time, 
   if the entry is there.)
  
TLB = Translation look-aside Buffer
      A special, small, fast-lookup hardware cache of page to frame references.

EAT = Effective (Memory) Access Time
      The average access time it takes to read a value from main memory,
      It is called average because it factors in the different paths to get
      a value from main memory. In this case, we can get the page to frame
      reference in 0ns 80% of the time.


      // in TLB           // Not in TLB
EAT = .8 * (0 + 160ns) + (1-.8) * (0 + 160ns + 160ns)
    = 128ns + 64ns
    = 192ns

Explained: 80% of the time the page number is found in the TLB (hardware)
---------- and then requires just one more memory access time to read
           the main memory.
           ... but 20% of the time, it the page to frame number reference 
           is not in the TLB, this requires 160ns to read the page to frame
           reference from main memory, then another 160ns to read the contents
           of the addressed value from memory.

192ns is the EAT.

With first fit, the 112KB process (line 57) can fit in segment b, right?

You put far too much work into this. Also, Markdown meet Brian, Brian meet Markdown. =]

@jdavis

I love markdown, When I used to take notes in class I would use mark down.
I use it daily for my real (work) tasks.

but... I like to submit my answers in raw ascii :)

...also gist's don't notify of comments :/ argh.

thanks @tylertreat-wf, I fixed it.

@banderson623 Excellent. I just fixed mine. Thanks!

Yeah, Great Work!
But I like to mention a point
Page no and offset can be find simply by:-
page no. = address/page_size
page_offset = address%page_size
No need to convert to binary :)