Computer Science 422/622 Test 2 - Nov 17, 1999 Name________________________ 1. One of the issues in the implementation of message passing was "copying". The message passing system that we implemented in assignment 3 is best classified as: a. Zero copy b. Single copy 3 x c. Double copy d. Triple copy 2. Suppose a single copy message passing scheme is being used. The use of "rendezvous" synchronization (as opposed to non-blocking writes): x a. Eliminates the b. Causes the buffer recycling "buffer-recycling" problem problem 3 c. Has no effect on the buffer d. Slightly reduces the magnitude recycling problem. of the buffer recycling problem. 3. In client / server message passing system we discussed in class the mailbox used for the SERVER to send status to the CLIENT is: a. The same as the one used x b. A private box owned by the by the client to send a client. 3 service request. c. A "community reply box" d. None of the above.. servers are not owned by the server allowed to respond to clients. 4. For each of the following resource types which deadlock prevention mechanism did we say was most appropriate _3_ a. Files and I/O devices 1. Hierarchical allocation 6 _2_ b. Real memory 2. Preemption _1_ c. Internal OS locks 3. Simultaneous allocation 4. Unconstrained sharing 5. In the deadlock detection algorithm resources the resources of process k were released if: a. Requested[k][j] <= avail[j] x b. Requested[k][j] <= avail[j] for some j. for all j. 3 c. Requested[k][j] - Alloc[k][j] c. Requested[k][j] - Alloc[k][j] <= avail[j] for some j <= avail[j] for all j 6. 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. c. Claims[j][i] <= avail[i] x d. Claims[j][i] <= avail[i] for some i. for all i. 7. At the start of the deadlock detection algorithm if EVERY ROW of the requested table has exactly 1 non-zero entry a. The system is definitely x b. The system is definitely 3 not deadlocked. deadlocked. c. The system might or might not contain a deadlock. 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 3 1 2 4 3 4 2 1 --------------------------------------- Resource B A C D C B B D Which request (if any) is the first one to cause a deadlock in this chain of requests. (Identify the request as (PID, RID) for example (3, B)). 3 (2, B) 9. 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 D Process 1 1 2 4 3 1 4 3 1 1 1 1 0 <-- Original ----------------------------------- MAX Resource A B C C D C A A 2 0 0 1 1 Claims 3 1 1 0 1 4 1 1 1 0 Which (if any) will be the first one denied by the bankers algorithm: Identify the request as (PID, RID). 3 (3,D) 10. 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. The Banker's algorithm and a process must be blocked. 3. Anytime a resource is requested regardless of whether or not it can be granted. 11. When base/limit registers are used they must be reloaded x a. Each time a new task is b. Each time a partition is reassigned dispatched. but not at each dispatch. 3 c. Each time a process references memory. 12. The partition management policy that has been accused of creating small unusable free blocks is: x a. Best Fit. b. Worst fit. 3 c. First Fit. d. Last fit. 13. Which of the memory allocation policies that we discussed always allocates from the largest free block of memory. a. First Fit. b. Last fit. 3 c. Best Fit. x d. Worst fit. 14. First fit is equivalent to best fit when the free partition list is sorted.. a. by starting address from b. by starting address from low to high high to low 3 x c. by size from low to high d. by size from high to low 15. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 000482 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 0006AE 5820???? L R2, X ;Load X into R2. : : : : 000980 00000000 X DW 0 ;Define word variable x ; with init value 0 000A84 ???? 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? 2 3 b. What value will be inserted at relative location 484 (the first batch of ????'s) by the assembler. 2 980 c. Suppose the program is loaded into real memory at start address A800. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 AC84 AEB0 B284 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. 2 B180 16. For each of the following functions answer O, L, H, A depending upon whether the function is performed by the O/S, by the Language Translator, by hardware without OS intervention, or by the application itself. _O_ 1. Build the segment tables used to translate addresses when a new process is created and a program loaded into memory. _L_ 2. Create the relocation tables used in load time relocation. _H_ 3. Translate a (segment, offset) address to real memory address. 6 _H_ 4. Test each real memory address to see if its outside the bounds of the segment being accessed. _O_ 5. Test the allocated bit after a page fault to determine whether a legitmate page fault or a protection error has occured. _O_ 6. Zero the present bit when a page is stolen. 17. 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. 3 x 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. 18. In the Pseudo-LRU algorithm that we discussed, the OS periodically tests every reference bit of every page. It adds one to the page's UIC a. only if the reference x b. only if the reference bit bit was 1 was 0 3 c. only if the UIC was 0 d. only if the UIC was non zero. 19. In conducting the reference bit tests the OS a. leaves all reference bits b. sets them all to 1 in whatever state it finds 3 them x 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. 20. Suppose page size is 1024 bytes. Give (in hex) the page number and offset associated with the virtual address: 0xabcde Page number - 2AF 4 Offset - DE 21. The maximum value of |W(n, h)| (the size of the working set of a process at reference "n" with window "h" can be no larger than: a. n b. h 3 c. the total number of pages x d. No larger that ANY owned by the process of the above. 22. Consider the following reference string: Ref # 1 2 3 4 5 6 7 8 9 10 Page 33 44 32 44 31 31 32 31 32 44 3 What is W(8, 4)? {31, 32} 23. Suppose it is determined that a processor executes 20,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 15,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 3 1/2 second 24. Associate each of the following page stealing algorithms with the appropriate description: _4__ a. OPT 1. Steal the page that has been referenced most often. 6 _5__ b. LRU 2. Steal the page that has been allocated the longest time. _2__ c. FIFO 3. Steal the page with the smallest number of total references 4. Steal the page that will be next referenced most distant in the future 5. Steal the page that was last referenced most distant in the past.