Home CS439

CS439: Principles of Computer Systems

Homework 6, Part 1

Due in Section on Friday, March 11, 2016

Part 1 of the homeworks must be completed before section and brought to section. Please refer to the homework turnin instructions.

  1. In a 32-bit machine we subdivide the virtual address into 4 segments as follows:
    8 bit
    We use a 3-level page table, such that the first 10-bits are for the first level and so on.
    1. What is the page size in such a system?
    2. What is the size of a page table for a process that has 256K of memory starting at address 0?

  2. In class, we discussed that paging may increase internal fragmentation. What is internal fragmentation? What steps could you take to reduce it?
  3. Consider a paging system with 16 pages and a page size of 256 bytes. The system has 1024 bytes of physical memory.
    1. How many bits are in a physical address?
    2. How many bits represent the page number?
    3. How many bits are in the complete virtual address?
    4. What size are the page frames?
  4. Sam P. Hacker is a Head Guru in a software company known for operating systems with very sorry quality. Hacker suggested a trick to reduce the pressure on the swap space. Instead of swapping out pages that belong to code texts into the swap area, the operating system could just take away the memory frames. If the code page is needed later, it could be paged directly from its binary file. Hacker's argument is that the operating system will save time by not storing the code page into the swap space, and will save space in the swap area. The code text exists on disk anyway, and could be fetched from there. Would you approve of this design? Why or why not?

  5. Belady's anomaly: Intuitively, it seems that the more frames the memory has, the fewer page faults a program will get. Surprisingly enough, this is not always true. Belady (1969) discovered an example in which FIFO page replacement causes more faults with four page frames than with three. This strange situation has become known as Belady's anomaly. To illustrate, a program with five virtual pages numbered from 0 to 4 references its pages in the order:
    0 1 2 3 0 1 4 0 1 2 3 4
    1. Using FIFO replacement and assuming demand paging, compute the number of page faults with 3 frames. Repeat for 4 frames.
    2. Compute the number of page faults under LRU, the clock algorithm, and the optimal algorithm. What do you notice?