CS 372 Operating Systems

Homework 3: Memory and Disks

Due: 11am Wed March 30, 2005
McKinley: in class
Witchel: in Taylor Homework Box

  1. (20 pts) Segmented Memory. Consider the following segmented memory state.
    Given the following memory state, requests, and algorithms show the state of memory after each request. If the current state cannot accommodate a request, perform process relocation (for a growing process) or compaction. For relocation, follow the specified algorithm. For compaction, first find (top down) a process with holes on both sides of it. If the two holes are sufficient to accommodate the new process, move up the middle process in the hole. Otherwise, compact all processes up until there is large enough hole to accommodate the request.

    • Process E starts and requests 300 memory units.
    • Process A requests 400 more memory units.
    • Process B exits.
    • Process F starts and requests 800 memory units.
    • Process C exits.
    • Process G starts and requests 900 memory units.

    1. (6 pts) Describe the contents of memory after each request using first fit (draw a picture or write the range of addresses for each process).

    2. (6 pts) Describe the contents of memory after each request using best fit.

    3. (6 pts) Describe the contents of memory after each request using worst fit.

    4. (2 pts) For this example, which is best?

  2. (5 pts) Paging. Consider a process with a logical address space of 4 pages of 1024 bytes per page, mapped onto a physical memory of 64 frames.

    1. (2 pts) How many bits are there in the logical address?

    2. (2 pts) How many bits are there in the physical address?

    3. (1 pts) Given the following page table map: page 0 is mapped to frame 3, page 1 is mapped to frame 14, page 2 to frame 6, and page 3 to frame 33, what is the physical address of page 2 byte 256?

  3. (5 pts) More Paging. Consider a paging system with the page table stored in memory.

    1. (2 pts) If a memory reference takes 60 nanoseconds, how long does a paged memory reference take?

    2. (3 pts) If we add associative registers (a TLB), what percent of page table references need to hit in the TLB to get an effective access time of 65 nanoseconds?

  4. (10 pts) TLBs. What is the advantage of a TLB that has an entry for every page frame? What is the advantage of a TLB smaller than the total number of frames? Which architectural design decisions determine this size?

  5. (10 pts) Sharing. Is data sharing easier in paged or segmented memory schemes? Why?

  6. (10 pts) Virtual Memory. When processes are allowed to grow larger than memory, page tables also grow very large. How could we organize page tables and TLB to keep access times as quick as possible for codes with good locality? For example, assume physical memory is 512K, each page is 1K, and a TLB of size 128. If we assume most processes are 256K or less, then we could allocate a fixed-size page table with 256 entries. Now in the unexpected case, where the page table grows larger than 256 entries, how should we organize it? What implications does your design have on average access time and on the maximum virtual memory size of a program?

  7. (20 pts) Page Replacement Algorithms. Consider the following page reference stream and 3 page frames:
    0 1 2 3 2 4 3 1 1 5 2 4 6 3 3 4 6 3 4 7
    For each algorithm, show the contents of the page frame after each reference, and then compute the total number of page faults, divided in to cold misses and other misses.
    1. MIN
    2. FIFO
    3. LRU
    4. Clock with one bit, where after 5 references, the OS sets all reference bits to 0. Show the clock bits states separately.
    5. For 4 page frames, what is the minimum number of misses possible in general, for this stream?

  8. (10 pts) Implications of Disk Access Time. Suppose an instruction takes 1 nanosecond to execute (on average), a page fault takes 20 microseconds of processor time, and it takes 300 microseconds of disk time to read or write a single page. Suppose that on average 1/3 of the pages are modified (and thus the OS needs to write them back). What is the average number of instructions between page faults that would cause the disk to be busy doing page transfers all the time? (Show your work.)

  9. (10 pts) File Sizes. Suppose a UNIX disk block will hold 2056 disk addresses. What is the maximum-sized file using only the direct pointers? Using double-indirection? Using triple-indirection?