Operating Systems • CS 438

Test 5, 11 December 2014


This test has six questions, all of which should be answered. The test runs the entire class period, starting at 7:25 and ending at 9:15. When you finish the test, you may leave.

Always justify answers unless the question explicitly states it’s not necessary. Some questions require reasonable assumptions in order to be answered. In such cases the answer should clearly state the assumptions made.
  1. Determine as precisely as possible the word or phrase being defined by the following:

    • Manipulating process state to change the system’s multiprogramming level.

    • Devices having access times proportional to the distance between successive I-O operations.

    • A dedicated, special-purpose CPU that off-loads I-O from the main CPU.

    • Self-propelled malware.

    • A particular technique or method for performing or achieving anp objective.

    • A data structure with two operations: signal() and wait().


    • Manipulating process state to change the system’s multiprogramming level:
    Medium-term scheduling

    • Devices having access times proportional to the distance between successive I-O operations:
    Sequential-access devices

    • A dedicated, special-purpose CPU that off-loads I-O from the main CPU:
    An I-O channel.

    • Self-propelled malware:
    Worms

    • A particular technique or method for performing or achieving an objective:
    A method (as opposed to a policy), or a tactic (as opposed to a strategy).

    • A data structure with two operations: signal() and wait():
    A semaphore.

  2. True or false: a system cannot deadlock if each shared resource is manged by a monitor. Justify your answer, either by proving the absence of deadlock or by describing a deadlock example.


    False. Monitors provide, among other things, mutual exclusion, but mutual exclusion isn’t that helpful in avoiding deadlock. For example, if two processes want camera and printer resources, both managed by a monitor, there is nothing particular about the monitor that can prevent both processes from getting into the usual allocation deadlock (one process gets the camera, the other gets the printer, then they deadlock waiting for the other resource).

  3. A colleague of yours believes that it is possible to use clever virtual-address manipulations to devise a multi-level page table that requires less total space than is required by the equivalent single-level page table. You, of course, recognize the foolishness of your colleague’s belief (under an important assumption which should be part of your answer). Describe the demonstration or proof do you show your colleague to illustrate the folly.


    In essence, every bit in a virtual address has to be translated into physical address, and some part of the page table has to handle that bit. If your colleague’s page table is smaller than the associated virtual address space, then there is (at best) ambiguity about the mapping of the virtual address space not covered. This assumes the page sizes are the same in either case because the offset bits are non-virtual and don’t need to be translated.

  4. Your poor, benighted colleague has developed a file system that assigns a bit map per file to keep track of disk blocks allocated to the file. Surprisingly, your colleague’s file system works, but has the odd property that eventually attempts to extend the file with more data fail even though there are plenty of free disk blocks available. Your colleague, puzzled, comes to you for an explanation. What do you say?


    The problem is your colleague’s file metadata format forces a quasi-sequential allocation policy on file blocks. A bit map has enough information to indicate which blocks are part of a file, but not enough information to indicate the order of those blocks in the file. The file system is forced to assume that the next block in the file is associated with the next true bit after the current one in the bit map. As a consequence, once bit i in the bit map is used to mark a file block, it is not possible to use any bits before i for later file blocks. If there are no free blocks after the most recently allocated block, the file can’t be extended even though there may be free blocks before the most recently allocated one.

  5. Recognizing and exploiting locality in various forms is an important part of designing and running operating systems. Explain the advantage gained by recognizing and exploiting locality. Give at least two examples.

    But locality is not a property to be exploited without wisdom. Describe problems that may occur when locality is exploited unwisely.


    Spatial locality suggests that if a process reads disk block i, then the process is likely to want to read successor disk blocks too, and they should be read in at the same time i is. Temporal locality suggests that if a process accesses disk block i, the process is likely to access i again soon, and it would helpful to cache the block for easier access.

    Generally, locality is a heuristic, which means it may be wrong on occasion. When locality goes wrong it does extra work to no good effect, which increases overhead. If a process is accessing a disk at random, then reading successor blocks isn’t useful. Locality can also increase the complexity with which the system works. Caching recently accessed objects for easier access raises problems like managing finite cache space and maintaining consistency between the cached object and the original.

  6. Explain how capabilities can be used to let a browser download files to the browser user’s directory but keep the browser from reading the files in the download directory.


    The agent using the browser can pass a suitably restricted copy of the agent’s capabilities to the browser for the download. The restrictions limit the objects that can be effected by the capability (the download directly) and the operations performed on those objects (create and write, but not read or delete). The interesting question is how the agent would revoke the browser’s capability once the file’s been downloaded.


This page last modified on 2014 December 15.