Midterm Preparation

22C:116, Spring 1995

1. Background: Consider a system with one virtual address space per process. At any instant, pages in the virtual address space may be unmapped or mapped to a sector of a file. Among the currently mapped pages, the sector in question may be currently in a page frame in main memory, or it may be on disk.

   Any process may open a file. The operation of opening a file maps some sectors of that file to consecutive pages of the processes virtual address space. Obviously, the open service must specify which sectors to map to what pages, but that is not relevant to this study problem. The important point is that two different processes may open the same file, and as a result, they may share some pages of their virtual address spaces.

   Memory address maps are large enough that not all pages of all maps may be held in main memory at one time. When the page replacement policy decides to replace the page in some frame, all map entries referencing that frame must be updated to reflect the fact that the page in that frame has been moved to disk.

   Think about the data structures needed to support clock page replacement on this system. When a page frame is replaced, how does the system find all map entries that reference that frame. When a page is brought in from disk, must all map entries referencing that page be updated? When a page is written back to disk, must all map entries referencing that page be updated at that time, even if those map entries are currently on disk?

   Think about the protection model applicable to the this system. What access rights would typically be associated with pages. What protection model applies? Is there any relationship between the protection that determines whether a process should be allowed to open a file and the protection model applying to pages currently mapped into the virtual address space of a process.

2. Background: Consider a database system where a number of interactive users share access to a database. Users interactively inspect and update records in the database. Updates may involve reading one or more pages and combining the values on those pages with new information to compute the contents of the pages that must be updated. Update operations therefore involve read-modify-write critical sections.

   The obvious implementation for this system is to attach a semaphore to each database record, with the rule that a user must lock all records involved prior to a read-modify-write update. In this case, all code involved in performing the updates would belong to the user processes.

   Think about the problem of avoiding or detecting deadlocks in this model. What deadlock detection model is applicable, if any? When a deadlock is detected, what action would be appropriate? If the set of records involved in an update does not depend on the contents of any of those records, does this simplify the problem?