Answers to Sample Final Exam

1. How does the working-set model relate process scheduling and memory management?
   Answer: The Working Set Principle says that all pages of the working set of a process must be resident for the process to run, and no page in a running process' working set can be removed from memory while the process is running. The memory manager and process schedulers must work together to ensure this principle is followed.

2. What is an access control matrix?
   Answer: An access control matrix is a structure that describes what rights processes have over files. The rows correspond to subjects (processes) and the columns correspond to subjects and objects (files). Each entry in the matrix contains the rights that the subject in the row has over the subject or object in the column.

3. What is the difference between deadlock and starvation?
   Answer: Deadlock occurs when two processes are blocked, waiting for the other to do something (like release resources). Starvation occurs when timing prevents one (or more) processes from acquiring a resource or performing some action.

4. Three procedures, A, B, and C, are to be linked together into one process and loaded into memory. The length of each procedure is 600 words. Consider the following memory management schemes:
   1. Paging: page size is 1000 words, page tables occupy 1 page each.
   2. Segmentation: segment table size is 1000 words.
   3. Paged segmentation: page size is 1000 words, page tables occupy 1 page each, segment table size is 1000 words.
   
   Assume that all procedures and all tables are in memory. For each of the three systems, what is the total occupied memory space (i.e., the space that cannot be used by another process)? This includes the space occupied by the procedures and the various tables, as well as space wasted due to the fixed page size.
   Answer:
   1. The page table is 1 page, and the three procedures make up a program that is 1800 words long, so it occupies 2 pages. Hence the total occupied memory is 3 pages or 3000 words.
   2. The segment table occupies 1000 words. Each of the procedures occupies a segment of 600 words. Hence the total memory occupied is 2800 words.
   3. Here, the segment table occupies 1000 words. Each procedure occupies 1 segment, and each segment contains 1 page. So each segment is 1000 words long. Each page table for the segment is 1000 words, so each segment and corresponding page table occupies 2000 words. Hence the program occupies 6000 words; adding in space for the segment table, the memory used is 7000 words.

5. Consider a system where free space is kept in a free space list.
   1. Suppose that the pointer to the free space list is lost. Can the system reconstruct the free space list?|
   2. Suggest a scheme to ensure that the pointer is never lost as a result of memory failure.
   
   Answer:
   1. Yes. Make a list consisting of all the blocks on the disk and then remove all the blocks already in use in existing files.
   2. One possible scheme is to keep the pointer on disk, replicated in several places. Then only a massive disk failure would cause it to be lost (in which case probably a lot of data is lost as well).