CS 537: Introduction to Operating Systems

Problem set 2

Due: Thursday, August 4, at the beginning of class. Work with your project groups; turn in only one solution per group.

Thanks for the memory management

  1. Suppose that your replacement policy (in a paged system) is to examine each page regularly and to discarding that page if it has not been used since the last examination. What would you gain and what would you lose by using this policy rather than or second-chance replacement?
  2. What is the copy-on-write feature and under what circumstances is it beneficial to use this feature? What is the hardware support required to implement this feature?
  3. We've talked about process schedulers for multiprocessor machines, but this question asks you to consider resource allocation for multiprocessor machines. Outline a design for an efficient and correct memory allocator for symmetric multiple processor (SMP) systems with uniform memory access. Your solution should address the following considerations: (0) you will want to exploit locality -- assume that the scheduler has a concept of affinity, (1) you will want to avoid contention on shared resources in order to increase concurrency, (2) tasks running on different processors should be able to share pages, and (3) you will want to avoid statically partitioning resources to increase utilization. If you read a paper or visit a website on multiprocessor memory allocators, be sure to cite it.

On a clear disk you can seek forever

  1. None of the disk-scheduling policies, except FCFS, is truly fair (starvation may occur). Explain why this assertion is true, explain why fairness is an important consideration in a multiprogrammed system, and describe one specific situation in which it might be desirable for an unfair scheduler.
  2. Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is

    86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

    Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?
    1. FCFS
    2. SSTF
    3. Elevator
    4. C-SCAN
  3. Requests are not usually uniformly distributed. For example, a cylinder containing the file system FAT or inodes can be expected to be accessed more frequently than a cylinder that only contains files. Suppose you know that 50 percent of the requests are for a small, fixed number of cylinders.
    1. Would any of the scheduling algorithms we've discussed be particularly good for this case? Explain your answer.
    2. Propose a disk-scheduling algorithm that gives even better performance by taking advantage of this “hot spot” on the disk.