Computer Science 422/622 Test 2 - Nov 25, 1996 Name________________________ (All multiple guess questions were 3 pts -- total point value = 112) 1. a. We identified 4 conditions that were NECESSARY for a deadlock to exist. One of them was the existence of serially reusable resources Name the other three. (NOTE WELL: This question IS asking for the conditions NECESSARY for deadlock. It is NOT asking the (related) question of how to PREVENT deadlock. Please make sure that YOU answer the question I asked!) 1 - Hold + Wait 6 2 - No preemption 3 - Cycle (or Knot or Circular Chain) in the process/resource allocation graph b. For each of the following deadlock prevention mechanisms identify the deadlock condition prevented and a resource class for which its use is appropriate. Hierarchical alloction of resources: Condition prevented: Cycle in the allocation graph 4 Resource class: Internal OS locks Preemption of resources - Condition prevented: No preemption of resources 4 Resource class: Memory or processor (any resource whose state can be transparently restored) 2. In the deadlock detection algorithm the resources of process j were released if b a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] for some i. for all i. c. Requested[j][i] >= avail[i] d. Requested[j][i] >= avail[i] for some i. for all i. 3. When the resources of process j were released what was added to avail[i]? a a. Allocated[j][i] b. Requested[j][i] c. Allocated[j][i] + d. Allocated[j][i] - Requested[j][i] Requested[j][i] 4. The system was free of deadlock at the end of the procedure if b a. At least one process was b. All processes were not blocked. not blocked (= marked). (were marked) c. All processes were blocked (=unmarked) . 5. In the deadlock avoidance (banker's) algorithm process j was marked and had its resources released if b a. Claims[j][i] <= allocated[i] b. Claims[j][i] <= available[i] for for all i. all i. c.(Claims[j][i] + requested[j][i]) d.(Claims[j][i] + requested[j][i]) <= allocated[i] <= available[i] for all i. for all i. 6. At the end of the Banker's alogorithm, it was safe to grant the request if: b a. At least one process was b. All processes were not blocked. not blocked (= marked). (were marked) c. All processes were blocked (=unmarked) . 7. Identify the appropriate time to run the deadlock detection algorithm and the bankers (deadlock avoidance) algorithm. 4 _2__ a. Deadlock detection 1. When a resource can be granted. 2. When a resource can't be granted _1__ b. Banker's algorithm and a process must be blocked. 3. Anytime a resource is requested regardless of whether or not it can be granted. 8. Suppose a system contains four processes (1, 2, 3, 4 ) and four single unit resources (A, B, C, D). Suppose the following sequence of requests occurs Process 1 2 1 4 3 2 4 3 ----------------------------------- Resource A B B C D C A A Which request (if any) is the first one to cause a deadlock in this chain of requests. 4 4-A 9. Suppose a system contains four processes (1, 2, 3, and 4) and four single unit resources (A, B, C, D). Suppose the following sequence of requests occurs A B C D Process 1 2 1 4 3 2 4 3 1 1 1 0 0 <-- Original ----------------------------------- MAX Resource A B B C D C A A 2 0 1 1 0 Claims 3 1 0 0 1 4 1 0 1 0 Which will be the first one denied by the bankers algorithm: 4 4-C 10. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 00048C 5010???????? ST R1, X ;Store R1 in variable X. : : : : : : : : : 000638 5820???????? L R2, X ;Load X into R2. : : : : 00074C 00000000 X DW 0 ;Define word variable x ; with init value 0 000850 ???????? Y DW A(X) ;Define word variable y ; holding ADDRESS of x a. How many relocation table entries will be generated by the above code sequence? 3 3 b. What value will be inserted at relative location 48C (the first batch of ????????'s) by the assembler. 3 74C c. Suppose the program is loaded into real memory at start address 1A000. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 1A48E 1A63A 1A850 d. What will be the actual value of the operand of the L(oad) instruction (the 2nd batch of ???'s) at the time the program actually begins execution. 3 1A74C 11. For each of the following functions answer O, L, or H depending upon whether the function is performed by the O/S, by the Compiler/Linker or performed by the hardware in hardware without OS intervention. _o_ 1. Build the segment tables actually used to translate addresses _l_ 2. Create the relocation tables in the a.out file. 16 _h_ 3. Translate a (segment, offset) address to real memory address. _h_ 4. Test each real memory address to see if its outside the bounds of the segment being accessed. _o_ 5. Set the allocated bit when a page is assigned. _o_ 6. Zero the present bit when a page is stolen. _h_ 7. Test the prsent bit when an address is translated. _o_ 8. Test and reset the reference bits and update the UIC's. 12. The main advantage that paging has over segmentation is that: a. Paging makes controlled b. Paging provides a finer grained sharing easier. level of memory protection. c c. Paging's use of fixed rather d. Paging significantly reduces variable sized entities greatly the complexity of the load time simplifies the management of relocation problem. real and auxilliary (disk) storage. 13. Identify an advantage of the use of demand segmentation over paging: - Finer grained protection 3 - Improved support for controlled sharing - Eliminates need for load time relocation 14. The partition management policy that has been accused of creating small unusable free blocks is: a. First Fit. c. Last fit. b b. Best Fit. d. Worst fit. 15. Which of the memory allocation policies that we discussed always allocates from the largest free block of memory. a. First Fit. c. Last fit. d b. Best Fit. d. Worst fit. 16. Recombining free blocks in a variable partition system is necessary a. Only during a partition b. Only when a partition is freed. allocation. b c. Both a. and b. d. Only when a process terminates 17. The one combination of the allocated and present bits that should never occur is: a. Not allocated and b. Allocated and not present. not present. c c. Not allocated and d. Present and present. allocated. 18. The combination of the allocated and present bits that indicates that a process has made a memory protection violation is: a. Not allocated and b. Allocated and not present. not present. a c. Not allocated and d. Present and present. allocated. 19. If a computer system uses 512 byte sized pages, and a process references address: 0x567def The offset in hex is: 2 0x1ef The page number in hex is: 2 0x2b3e 20. Suppose a computer system uses 2048 byte pages and a virtual address with the value 0x001667 is generated. What physical address will this address be generated if the page table shown is used: 0x007 0x00a 0x006 3 E67 0x00b 0x001 0x234 PTBR -> 0x005 21. Suppose it is determined that a processor executes 10,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 12,000,000 references is selected. What is the appropriate time unit for use in computing working set sizes. 3 12,000,000 / (10,000,000) * 1.5 = 4/5 Suppose the virtual address 0x47E342b2 is to be translated by an Intel processor. 22. The part of the address NOT translated by the hardware is: a. 0xAB2 c. 0x47e b b. 0x2B2 d. None of the above 23. The index into the page TABLE is: a. 0xE32 b. 0x32A d c. 0x232 d. None of the above 24. Now suppose a hypothetical processor uses 36 bit virtual addresses with the bits partitioned as follows: 11 bits = offset into page, 12 bits = page table index, 13 bits = page directory index. a. The amount of memory that can be accessed through a single page table is: 3 2^ 23 b. If page table entries are 4 bytes each, how many bytes are required for a complete page table. There was some confusion here..induced by me.. on the meaning of complete page table. Thus full credit was given for answers describing either an Intel style page table or a single linear table mapping the entire address space. 3 Intel style 4 * 2^12 Full 4 * 2^12 * 2^13