Assignment 3

PDF (117 KB) SolutionPDF (159 KB)

HTML versions of documents are provided for quick reference only.
Do not print the HTML documentsdownload and print the PDF versions instead.

Due:

8:30 AM, Wednesday, July 21, 1999.

Weight:

8% of your course grade.

Preliminaries

As with all assignments in this course, a small part of the assessment for this assignment reflects how your work is presented. Your work must be easy to read. This means:

• Your work must be clear, succinct, grammatically correct, and correctly spelled.
• Your work must be laid out sensibly. In text, lines should be short enough to be readable (i.e., don't fill the entire width of the page with text-appropriate use of margins and other blank space on a page can dramatically improve the readability of your work).
• Unless there is a compelling reason to do otherwise, all pages should be on letter-size paper, with content in the portrait orientation. Pages should be held together with a single staple in the top lefthand corner.
• Avoid unnecessary embellishment-you should not use presentation folders.

Most students find it easier to create their answers to assignments using a word processor or equivalent program. Although you may handwrite your answers, it is much easier to check and correct grammar and spelling on a computer screen than on a handwritten page. If you choose to handwrite your answers, they must be neat, tidy, and legible.

The late policy for all assignments is as follows: 10% penalty for being one day late, 20% penalty for being two days late. Assignments may be handed in early. No assignments will be accepted more than two days late. The late period begins immediately after the beginning of class on the due date (i.e., handing in your work at 9 AM on the Wednesday it is due counts as one day late).

This assignment may be refined or clarified in class or e-mail.

Written Exercises

1. Explain how sharing memory over a network (as you have done with Mneme) is similar to sharing files over a network. Briefly discuss the similarities and differences.
2. Your original implementation of Mneme allocates pages of memory to one process at a time, making the acquisition of a page by a process akin to the acquisition of a mutex lock. However, it is possible to adopt a strategy for page acquisition akin to the readers/writers problem. In fact, it is possible to go beyond traditional readers/writers solutions (which disallow reads while one process is writing) and develop a solution that allows readers to continue to read "stale" data until the current writer has written new data.
   1. Explain how such a scheme would work by describing the flow of requests and data between clients and the shared-page server.
   2. Explain why this kind of solution to the readers/writers problem is not usually possible.
3. What is meant by the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answers.
4. Explain the difference between logical and physical addresses.
5. Explain the difference between internal and external fragmentation.
6. Why are page sizes always powers of two?
7. What complications arise if an operating system that manages memory using segmentation allows processes to increase the size of their segments?
8. On the road, four-way stops are (theoretically) prone to deadlock. Traffic circles (aka roundabouts) are an alternative to four-way stops. In a traffic circle, all vehicles reach their destinations by driving around the traffic circle in a counterclockwise direction. Vehicles wanting to enter the circle must yield to vehicles already driving around the circle (i.e., vehicles on their left). An example of a traffic circle is shown on the right.
   1. Are four-way stops prone to starvation?
   2. Are traffic circles prone to deadlock?
   3. Are traffic circles prone to starvation?
   4. Give an additional traffic rule that could be used to prevent deadlock at four-way stops.

   In each case, explain your answer.

9. Some paging hardware does not support the "referenced bit" needed by various page-replacement algorithms. Explain how the protection bits in the page table can be used to emulate a referenced bit.
10. When calculating the hash function for an inverted page table, we include the process ID as well as the page number. Why?
11. This question is about the similarities and differences between page replacement with page buffering (FPB) and the Clock page-replacement algorithm. Both methods usually provide a fair approximation of LRU page replacement.

    In the questions below, assume a uniprocessor machine where the page fault routine will not be interrupted to run another process. State any additional assumptions you make.

    1. Explain how these algorithms have strong similarities.
    2. Consider the situation where every frame is in active use, all frames are clean, and there is a heavy demand for frames (i.e., the system is thrashing).
       1. Does the Clock algorithm degenerate to another (non-LRU) policy (such as FIFO or RAND) under these circumstances? If so, state which policy it becomes and why.
       2. Does the FPB algorithm degenerate to another (non-LRU) policy (such as FIFO or RAND) under these circumstances? If so, state which policy it becomes and why.
    3. Consider the situation where every frame is is accessed only occasionally, averaging once every ten seconds, and page replacement is very rare, averaging once a day.
       1. Does the Clock algorithm degenerate to another (non-LRU) policy (such as FIFO or RAND) under these circumstances? If so, state which policy it becomes and why.
       2. Does the FPB algorithm degenerate to another (non-LRU) policy (such as FIFO or RAND) under these circumstances? If so, state which policy it becomes and why.
    4. Which algorithm provides a better approximation of the LRU policy? Why?
12. Devise a question suitable for use in an examination on operating systems. State the question and give a model answer. Your question should:
    • Require about five to seven minutes for an average student to read, consider, and answer.
    • Require the application of operating systems knowledgenot be a simple matter of factual recall.
    • Have a straightforward answer that can be assessed quickly.
    • Be original (not found in your textbook or very similar to a question suggested by your friends).

    Your score for this question will be based both on your question and your answer. You may not receive full credit if your question is too easy or too hard.

    (If your question is a good one, I may adapt it for use on either a sample final exam given out to students, or on the actual final. You may have an advantage over your fellow students if you have to answer your own question on the final exam, so you have a special incentive to produce a good question.)