Final Exam, with suggested answers

CSC 256/456, 5-4-1999

Please, read the following notes carefully before starting the exam:


  1. (10 points) What are the tradeoffs between semaphores and monitors as process synchronization constructs? Are they equivalent in terms of expressiveness?
    Semaphores are lower level constructs than monitors, in the sense that there is not much structure to the use of semaphores. The uses of P and V are usually scattered throughout programs (especially if the semaphores are not used simply for mutual exclusion), making it easy for the programmer to make mistakes. Monitors, in contrast, are more structured constructs that encapsulate the data, operations that can be applied to the data, and condition queues. Due to their higher level of abstraction, monitors provide for easier programming and fewer errors. An additional difference between monitors and semaphores is that semaphores can be implemented in a user-level library, while monitors are language constructs and thus require compiler support. In terms of expressiveness, the two constructs are equivalent in the sense that one can be implemented with the other.
  2. (15 points) Why is it useful for the operating system to maintain a pool of free page frames?
    A pool of page frames can improve the performance of the page replacement algorithm in several ways: a) it allows dirty pages to the written to disk in the background; b) it allows bursts of write traffic to be accommodated without much performance degradation; c) it allows new page frames to be made available without overhead; d) it can soften the impact of a poor page replacement algorithm by acting as a victim cache; and e) it allows better disk scheduling.
  3. (5 points) Describe the basic idea of copy-on-write and two different applications of this mechanism.
    The basic idea of copy-on-write is to allow two or more virtual pages with the same contents to share the same physical page frame. Copy-on-write can be used in to speed up virtual address space copying (such as performed by the Unix fork command) and to implement efficient message passing between processes on the same machine.
  4. (10 points) Explain what inverted page tables are and how they are used. Compare inverted page tables against traditional (linear) page tables.
    Inverted page tables devote space to only those pages that are actually resident in memory at any given time. Each entry of the table consists (at least) of a process identifier and a virtual page number. A virtual address is translated into a physical address by hashing the virtual page number into a hash table entry that contains the page frame number. The frame number and the offset are then put together to generate the physical address. Inverted page tables require less physical memory than linear page tables, since their size is proportional to the size of physical memory rather than virtual memory. However, with inverted page tables it is harder to map two different virtual pages to the same physical page frame.
  5. (10 points) Discuss the tradeoffs between bit map and linked list representations of free space in a file system.
    With bit maps it is easier to allocate disk sectors belonging to the same track or cylinder, thereby improving the transfer rate of the file system. Linked lists make it harder to implement this type of optimization. With bit maps, sector deallocation always takes time proportional to the number of sectors, while with linked lists deallocation can be implemented in constant time if files themselves are represented as linked lists of sectors. Regarding the amount of space these approaches consume, the bit map is more compact if a large number of sectors is free. However, it has been observed that disks are usually mostly full, often favoring the linked list.
  6. (20 points) Consider an operating system that uses capabilities for protection. What are the tradeoffs between keeping capabilities in the kernel and keeping (encrypted) capabilities in user space?
    Capabilities kept in user space rely on the randomness of the mechanism used to generate capabilities. If this mechanism can be cracked, protection is lost. Another problem with user-level capabilities is that it is not possible to control their dissemination, i.e. there is no way to prevent one user from giving a copy of its capabilities to another user. However, this ease of dissemination can also be seen as an advantage, as the kernel does not have to be involved in the dissemination. Capabilities kept in the kernel guarantee protection, but at the cost of kernel intervention whenever capabilities have to be passed around.
  7. (10 points) Describe the tradeoffs between fixed routing, virtual circuits, and dynamic routing in computer networks.
    In fixed routing, a path between the two nodes is specified in advance and does not change. In virtual circuit routing, a path between the nodes is fixed for the duration of one session. A session can be a file transfer, remote login, etc. In dynamic routing, a path between the nodes is only chosen when a message is sent. Usually, each router chooses the link with lowest use at a particular time. Fixed routing cannot adapt to link failures or load changes. Virtual circuits can adapt to failures and load changes between two different sessions involving the same two nodes. Dynamic routing can adapt to failures and load changes much more rapidly than the other techniques. Fixed routing and virtual circuits deliver messages in order, while dynamic routing does not necessarily.
  8. (20 points) In a distributed file system, what are the tradeoffs between caching files (or parts of files) locally and accessing files only via remote procedure calls (RPCs)? Under what circumstances should a distributed file system perform better with RPCs only? Under what circumstances is using local caching more efficient than using RPCs only?
    With caching, many file accesses can be serviced locally. This reduces server load and network traffic, while enhancing the potential for scalability. When all file accesses require RPCs to the server, there is a penalty in network traffic, server load, and performance. The total network overhead in transmitting big chunks of data (caching) is usually lower than a series of request/response operations (RPC). In addition, local caching is particularly efficient for access patterns with infrequent writes and when execution is carried out on machines with either local disks or large main memories. With frequent writes, local caching involves substantial overhead to overcome the cache coherence problem.
  9. (25 points) Given that network transfers are significantly faster than disk accesses, suggest one strategy for using the set of memories in a network of workstations to improve the performance of file system operations. How efficient is your strategy?
    One possibility here would be to implement system-wide caching of disk data, i.e. have all memories in the system be part of a large cooperative cache, where nodes with available memory would cache data read from disk on behalf of other nodes. Another option would be to use the set of memories in the system in page out operations. More specifically, a page out operation can send the page to another workstation's memory, as opposed to the disk. Both of these strategies should improve performance, given the gap between (modern) network and disk performance. The performance improvement obtained by the strategies may not be significant in certain cases, however. The gains achievable by the first strategy may be limited for systems with little available cache space. Both strategies should exhibit limited gains, if disk controllers include large disk caches.
  10. (25 points) False sharing occurs when two or more processors read and write non-overlapping sets of data that happen to be allocated on the same coherence unit. One major problem with page-based, software distributed shared-memory systems is false sharing. Describe one way in which the impact of false sharing can be alleviated in these systems. How efficient is your strategy?
    The standard way of alleviating the false sharing problem is to allow multiple concurrent writers to each page and use a relaxed consistency model. Multiple concurrent writers can be implemented with the twining and diffing mechanism, where on the first write to a clean page, an exact copy (twin) of the (unaltered) page is created. Later, when the exact modifications made to the page are required, a word-by-word comparison of the twin and the current version of the page (a diff) is performed. Relaxed consistency is used to delay invalidations substantially, until synchronization operations, for instance. This strategy is efficient in the sense that the impact of false sharing is alleviated by allowing concurrent writers to proceed without intervention and delaying invalidations. However, twining and diffing operations are very expensive. Other examples of approaches for alleviating false sharing are: padding of data structures to page boundaries, the use of sub-page coherence units, and the re-organization of data structures or computation partitions.

Last Change: 1 February 1999 / scott@cs.rochester.edu
Exam by Ricardo Bianchini.