Reading Assignment

• Operating Systems Concepts: Chapters 8 and 9.

Lecture Slides

• Memory Management

Homework Assignment

Due Date: 4/28/08


• Briefly discuss the benefits and drawbacks of each of the following address binding schemes: Compile Time, Load Time, Run Time.
• Consider a virtual memory system using paging and a single level page table for address binding. Assume that the system is byte addressable, has 15 bit logical addresses, 12 bit physical addresses, and 128 byte pages. Assume that the page table for the current process holds the following values:

  Entry	Frame	Valid
  0	10010	V
  1	01001	V
  2	11100	I
  3	00101	V
  ...	...	...
  52	10110	I
  53	00000	V
  54	10110	V
  ...	...	...

  Answer each of the following questions with regard to the above system:
  • How many entries would the page table for this system have?
  • What is the maximum amount of physical memory that this system could have?
  • Give the physical address, in binary, corresponding to each of the following logical addresses assuming that the page table is as shown below. Indicate any address translations that would result in page faults.
    • 000000000000000
    • 000000101010101
    • 001101010011101
  • Give a logical address that would translate into a physical address located in page frame 22.
• Consider the following compressed page reference string:
  1,4,5,4,3,7,2,1,4,1,4,5,3,4,5
  Assuming this process has been allocated 3 page frames, show the contents of its page frames following each reference using the optimal page replacement scheme. Also assume that all of the frames are initially empty.
• Consider the following page reference string:
  1,1,1,1,3,3,5,3,5,3,5,6,6,6,2,3,4,5,4,3,2
  • If a working set frame allocation scheme is being used with a window size of 4, how many frames would be allocated to this process at each of the times indicated in bold?
  • Give a page reference string that would cause thrashing if the working set frame allocation scheme from part a were used in combination with least recently used page replacement.
• Consider a machine based on the load-and-store architecture that uses a virtual memory system with a two level page table. The first level page table for every process is always held in main memory, while the second level page table is managed by the virtual memory system (i.e. entries are loaded only when referenced and are removed from memory according to the page replacement algorithm). Every time an address translation results in a page fault, that page fault is handled and the address translation is restarted from the beginning. Also assume the following about this system: it takes 5ms to read a page from the disk, and it takes 100ns to access main memory.

  Answer each of the following questions with respect to this system:

  • What is the maximum number of page faults that could be generated during the fetching and execution of a single instruction on this machine? Briefly explain your answer.
  • Give an expression for the effective memory access time for this system under the following assumptions:
    • 0.2% of all address translations result in a page fault when trying to access the second level page table.
    • 0.3% of all address translations that do not result in a page fault when accessing the second level page table do result in a page fault when accessing the required physical memory frame.
    • Whenever a page from the second level page table is evicted from memory, all pages it refers to are also evicted.

Acknowledgment: this content is essentially identical to that developed by Professor Grant Braught for the Spring 2006 Operating Systems course, and I'm grateful for his permission to use it.