Midterm

22C:116, Spring 1995

1. Background: Recall the first study question. Our hypothetical system has one virtual address map per process, and any number of processes may share any particular page.

   Consider the option of lazy map update. In this case, when a page is moved from disk to main memory, only the map of the process that actually caused the page-fault is updated. Other processes may have map entries that still point to the page on disk. This is particularly beneficial if some map pages containg references to the same page aren't in main memory. When a system employs lazy map update, it is possible that reference to some page will cause a page fault trap even though that page is in main memory.

   By comparison prompt map update requires that all map entries that reference a particular page to be updated immediately when that page is moved.

   Part A: As defined here, lazy map update applies only when pages are moved from disk to main memory. Why can't lazy update be used when pages are moved from main memory to disk?

   Part B: Outline the operation of a page-fault handler that employs lazy map update when pages are brought from disk to main memory while still ensuring that shared pages are correctly implemented from the user's viewpoint. Focus on bringing new pages into memory and on the differences between this modified handler and a handler which does prompt update.

2. Background: Recall that semaphores are typically implemented as a counter plus a linked list of blocked processes. If the counter is nonzero, no processes are blocked. If the counter is zero, there may be some number of waiting processes in the list. The linked list of processes is implemented using link fields reserved for this purpose in each process control block.

   Recall that a binary semaphore is one where the counter may never take on values other than zero or one. When a binary semaphore is used for mutual exclusion, a critical section is entered with P(sem) and exited with V(sem).

   Part A: What information is missing from the implementation of semaphores suggested above that would be needed to detect deadlocks in a resource centered system that used binary semaphores for mutual exclusion.

   Part B: Assuming that the missing information you identified in part A is added to the semaphore and process data structures, what deadlock detection algorithm is applicable, when should the algorithm be initiated, and what would you suggest it do when it detects a deadlock?

3. Background: Recall the first study question. Our hypothetical system has one virtual address map per process, and any number of processes may share any particular page. When a process opens a file, the pages of that file are inserted into the address space of that process. The right to open a file is controlled by an access control list attached to that file.

   Part A: What protection model does this system implement? For the purpose of this part, focus only on processes and the pages they currently share, and pay no attention to how pages come to be shared.

   Part B: Does the complete system implement some specific protection model? Please take into account the file directory structure, the rights to open files, and the rights to access pages of files already opened. If yes, what model and why? If no, why not?

4. Background: Recall the second study question. Our hypothetical system includes processes that may lock records in a database before inspecting and updating them. A transaction proceeds by locking the requisite records, one at a time, then inspecting and updating them, as needed, and then unlocking them, one at a time.

   Part A: Outline, in graph theoretic terms, the structure of a deadlock detection algorithm applicable to this system.

   Part B: Suppose that the complete set of database records needed for a transaction can be determined before any of them are locked. There is a simple deadlock avoidance algorithm that applies in this case. Explain it.