Exercise Sheet for Tutorial 6

Before the tutorial session, try your best to solve problems below and be prepared to discuss them at the tutorial session.

  1. (important) Explain the difference between logical and physical addresses.
  2. Why are page sizes always powers of 2?
  3. What is the effect of allowing two entries in a page table to point to the same frame? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on one page have on the other page?
  4. Consider a logical address space of 64 pages of 1,024 words each, mapped onto a physical memory of 32 frames.
    • How many bits are there in the logical address?
    • How many bits are there in the physical address?
  5. Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 115 KB, 500 KB, 358 KB, 200 KB, and 375 KB (in order)?
  6. Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers):
    • 3085
    • 42095
    • 215201
    • 650000
    • 2000001
  7. The BTV operating system has a 21-bit virtual address, yet on certain embedded devices, it has only a 16-bit physical address. It also has a 2-KB page size. How many entries are there in each of the following?
    • A conventional, single-level page table
    • An inverted page table What is the maximum amount of physical memory in the BTV operating system?
  8. (important) Explain the difference between internal and external fragmentation.
  9. Most systems allow a program to allocate more memory to its address space during execution. Allocation of data in the heap segments of programs is an example of such allocated memory. What is required to support dynamic memory allocation in the following schemes?
    • Contiguous memory allocation
    • Paging
  10. Explain why mobile operating systems such as iOS and Android do not support swapping.
  1. (important) Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs.
  2. Assume that you have a process with m frames (initially all empty). The reference string has length p, and n distinct page numbers occur in it.
    • How many page faults are there at least? (for any page replacement algorithm)
    • How many page faults are there at most? (for any page replacement algorithm)
  3. Rank the following page-replacement algorithms on a from “bad” to “good” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not.
    • LRU replacement
    • FIFO replacement
    • Optimal replacement

  4. Consider the page table for a system with 12-bit virtual and physical addresses and 256-byte pages, all addresses given in hexadecimal.

    Page Table

    The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last). A dash for a page frame indicates that the page is not in memory. Convert the following virtual addresses to their equivalent physical addresses

    • 9EF
    • 111
    • 700
    • 0FF
  5. Describe the connection between locality of reference (similar addresses being referenced closely in time) and page faults.
  6. Consider the two-dimensional array A: int A[][] = new int[100][100]; where A[0][0] is at location 200 in a paged memory system with pages that store 200 times the size of an int. A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0. For three page frames, how many page faults are generated by the following array-initialization loops? Use LRU replacement, and assume that page frame 1 contains the program code and the other two are initially empty.
    • Option 1:
     for (int j = 0; j < 100; j++)
   for (int i = 0; i < 100; i++)
       A[i][j] = 0;
    • Option 2:
     for (int i = 0; i < 100; i++)
   for (int j = 0; j < 100; j++)
       A[i][j] = 0;
  7. (important) Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.
    • LRU replacement
    • FIFO replacement
    • Optimal replacement
  8. You have devised a new page-replacement algorithm that you think may be optimal. In some contorted test cases, Belady’s anomaly occurs. Is the new algorithm optimal? Explain your answer.
  9. Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four (four processes run at the same time). The system was recently measured to determine utilization of the CPU and the paging disk. Three alternative results are shown below. For each case, what is happening? Can the degree of multiprogramming be increased to increase the CPU utilization? Is the paging helping?
    • CPU utilization 13 percent; disk utilization 97 percent
    • CPU utilization 87 percent; disk utilization 3 percent
    • CPU utilization 13 percent; disk utilization 3 percent
  10. We have an operating system for a machine that uses base and limit registers, but we have modified the machine to provide a page table. Can the page table be set up to simulate base and limit registers? How can it be, or why can it not be?

In class

Discuss the exercises prepared at home