Computer Science 422 / 622 Test 2 Name ______________________ 1. Answer the following T or F: ___ a. All of the scheduling policies we discussed are equally appropriate for batch job, swap, and dispatch scheduling. ___ b. FIFO is a common policy for dispatch scheduling. ___ c. A process will typically be scheduled more often by the dispatch scheduler than the swap scheduler. 2. a. We identified 4 conditions that were necessary for a deadlock to exist. One of them was the existence of non-sharable (serially reusable) resources. Name the other three. 1 - 2 - 3 - b. We identified two mechanisms for deadlock prevention. Each worked by preventing one of the three conditions above from occuring. Name one of the deadlock prevention methods, identify the condition it prevents, and identify a resource class for which its use is reasonable. Method: Condition prevented (1 of above 3): Resource class: 3. Suppose a system contains three processes (1, 2, and 3) and four single unit resources (A, B, C, D). Suppose the following sequence of requests occurs Process 1 1 2 3 3 1 ----------------------------- Resource A B B D A C a. Draw the resource allocation directed graph using the notational conventions of the text. b. Is this system deadlocked?? Explain why or why not USING THE GRAPH as a basis for your reasoning. c. What additional information would be needed if you were to apply the bankers algorithm at each step to determine if an allocation were safe or not. 4. For the following outline of the deadlock detection algorithm circle the appropriate terms. a. Each step of the iteration start with the release of the resources of 1. all processes 2. all blocked processes 2. all unblocked processes b. The algorithm terminates after an iteration in which 1. A single resource is freed. 2. No resources are freed. 3. A process is unblocked. c. When the iteration terminates, the system is deadlocked if 1. there are no blocked processes 2. there are some blocked processes 3. all the original processes are blocked. 5. For each of the following functions related to memory managment answer H if it is purely a hardware function and O if it is performed by the OS. ____ a. Translating (seg, offset) form addresses to real memory addresses each time a process references memory. ____ b. Building a segment table for a newly created process. ____ c. Detecting that an address translation cannot be performed because the Invalid bit is set and generating an interrupt. ____ d. Setting the Invalid bit. ____ e. Keeping track of how many seconds since a page has been referenced by periodically testing and resetting the Referenced bit. ____ f. Setting the referenced bit each time a page or segment is referenced. ____ g. Choosing a page or segment to write out to disk when a memory shortage occurs. 6. a. What is the primary motivation for using schemes such as hierarchical page tables and base/bounds page table address registers. b. What performance penalty is associated with the use of each of the above schemes when compared with a single "full sized" table. Hierarchical: Base/Bounds: 7. Suppose a hierarchical paging system uses 36 bit virtual addresses. Suppose 12 bits each are used for offset into a page, page table index, and page directory index. a. How large is a page. b. How many entries are there in a page table. c. How much virtual memory can be accessed through a single page directory entry. 8. Choose the best answer. a. Best fit, first fit, and worst fit are examples of memory managment policies commonly classified as 1. Replacement 3. Fetch 2. Placement 4. Paging b. Placement policies are most signficant in: 1. Real memory systems. 3. Systems using both segmentation and paging. 2. Paged memory systems. c. LRU, FIFO, and OPT are examples of memory managment policies commonly classified as 1. Replacement 3. Fetch 2. Placement 4. Demand 9. a. How does the use of base/bounds addressing (don't confuse with base/bounds page table management in question 6.a.) help solve the problem of fragmentation in real memory systems using variable partitions. b. What additional benefits does the use of segmentation provide with respect to fragmentation in real memory systems using variable partitions. c. Identify one other advantage of the use of segmentation in real memory systems that is unrelated to the fragmentation issue. 9. Consider the following sets of ESD and RLD data SYM TYPE ID ADDR LENGTH SYM TYPE ID ADDR LENGTH ABC ER 0001 | MNO SD 0001 0000 0068 DEF ER 0002 | DEF LD 0002 002C IKJ SD 0003 0000 004C | ABC LD 0003 0014 XYZ LD 0004 0034 | XYZ ER 0004 | POSID RELID ADDR | POSID RELID ADDR 03 01 0010 | 01 01 0040 03 02 002C | 01 01 0044 03 03 0038 | 01 04 004C 03 01 004C | a. At what relative address within the left module (IKJ) are the relocatable references to symbols defined WITHIN IKJ. b. At what relative address within the first module was the reference to DEF located and what value did the assembler put there? rel addr = value = c. Suppose the modules are to be linked together. Construct the global external symbol table (GEST) and the local external symbol array (LESA) for module MNO G E S T L E S A Symbol - Value Id - Value | | | | | | | | | | | | | | | | | | | d. When the linked program is loaded by the program loader, how many relocation fixups will the program loader perform. 10. Choose the best answer: a. A GEST entry is constructed during 1. Pass 1 2. Pass 2 3. Neither pass. b. A GEST entry is constructed when 1. An RLD record is processed 3. An LD type ESD record is processed. 2. An ER type ESD record is processed c. LESA tables are constructed during. 1. Pass 1 2. Pass 2 3. Neither pass.