Computer Science 422/622 Test 2 - Apr 17, 1997 Name________________________ 1. A mailbox read procedure should check for a. Blocked writers before removing b. Blocked writers after removing 3 a message from the bufffer. a message from the buffer. b c. It doesn't matter because blocked writers and buffered messages are mutually exclusive. 2. For each of the following resource types which deadlock prevention mechanism did we say was most appropriate a - Files and I/O devices - Simultaneous alloc of all resources 6 b - Real memory Preemption c - Internal O/S locks Hierarchical allocation 3. In the deadlock detection algorithm process j was marked and had its resources released if 3 a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] for some i. for all i. b c. Claims[j][i] <= avail[i] d. Claims[j][i] <= avail[i] for some i. for all i. 4. In the deadlock avoidance algorithm process j was marked and had its resources released if a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] 3 for some i. for all i. d c. Claims[j][i] <= avail[i] d. Claims[j][i] <= avail[i] for some i. for all i. 5. At the end of the deadlock detection algorithm a. How does one determine if there is a deadlock? 2 If any unmarked processes remain at the end of the algorithm, there is a deadlock. b. How does one determine which processes are involved in the deadlock? 2 The unmarked processes are involved. 6. 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 1 2 4 3 1 4 --------------------------- Resource A B D C D C A 4 Which (if any) processes are deadlocked? 1 and 4 7. Suppose a system contains three processes (1, 2, and 3) and three single unit resources (A, B, C, D). Suppose the following sequence of requests occurs A B C Process 1 2 3 1 2 3 1 1 1 <-- Original ----------------------------- MAX Resource A B C B C A 2 1 1 Claims 4 3 1 1 b. Which (if any) of the allocation requests would have been the first one denied if the bankers algorithm were in use. 3 - C 8. Identify the appropriate time to run the deadlock detection algorithm and the bankers (deadlock avoidance) algorithm. _2__ a. Deadlock detection 1. When a resource can be granted. 4 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. 9. When comparing real memory based systems that use fixed partitions with those that use variable sized partitions wasted memory WITHIN a partition is typically a more significant problem in: 3 a. Variable (dynamic) partition b. Fixed partition systems b systems. c. Equally bad in both systems. d. Cannot occur in either system. 10. The use of a single/pair of base/ limit registers when compared to physical memory addressing: 3 a. Makes both relocation and b. Makes relocation much easier but controlled sharing much doesn't do much for controlled easier. sharing. b c. Makes neither relocation or controlled sharing much easier. 11. The programming "feature" that makes dynamic program relocation generally impossible in a real memory system is: a. The use of structures b. The use of any pointer that 3 is statically initialized at compile time. c c. The use of informal and d. Any one of the above is sufficient dynamically created pointers. to prevent dynamic relocation. 12. The partition management policy that has been accused of creating small unusable free blocks is: 3 a. First Fit. c. Last fit. b b. Best Fit. d. Worst fit. 13. Which of the memory allocation policies that we discussed always allocates from the largest free block of memory. 3 a. First Fit. c. Last fit. d b. Best Fit. d. Worst fit. 14. Recombining free blocks in a variable partition system is necessary a. Only during a partition b. Only when a partition is freed. 3 allocation. b c. Both a. and b. d. Only when a process terminates 15. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 000240 5010???????? ST R1, X ;Store R1 in variable X. : : : : : : : : : 00044E 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 242 (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 1a242 1a450 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 16. The main advantage that paging has over segmentation is that: a. Paging makes controlled b. Paging provides a finer grained 3 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. 17. 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. _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. 9 _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 present bit when an address is translated. _o_ 8. Test and reset the reference bits and update the UIC's. _h_ 9. Set the reference bit each time a page is referenced. 18. Suppose a hierarchical paging system uses 30 bit virtual addresses. Suppose 9 bits are used for offset into a page, 10 bits as page table index, and 11 bits as page directory index. a. How large is a page. 3 2 ^ 9 b. How many entries are there in a page table. 3 2 ^ 10 c. How much virtual memory can be accessed through a single page DIRECTORY entry. 3 2 ^ 19 d. How large would a single linear page table that mapped the entire virtual address space be if entries were 4 bytes each. 3 4 * 2 ^ 21 19. Suppose it is determined that a processor executes 24,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 20,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 3 20 / (1.5 * 24) = 20/36 = 5 / 9 20. Match the settings of the resident and allocated bits with the appropriate description. _d_ 1. Protection violation a. Present and Allocated 6 _b_ 2. Reference to a page that b. Not Present and allocated must be read back into memory. c. Present and not allocated _c_ 3. Bug in O/S d. Not Present and not allocated 21. In the Pseudo-LRU algorithm that we discussed, when the OS periodically tested every reference bit, it would add one the the page's UIC 3 a. only if the reference b. only if the reference bit bit was 1 was 0 b c. only if the UIC was 0 d. only if the UIC was non zero. 22. In conducting the reference bit tests the OS 3 a. leaves all reference bits b. sets them all to 1 in whatever state it finds c them c. sets them all to 0 d. sets to zero only those associated with pages whose UIC was 0 at the start of the test.