Computer Science 422/622 Test 2 - Nov 23, 1998 Name________________________ 1. Answer T or F depending upon whether or not the sender must worry about when it is safe to reuse a message buffer (the "buffer recyling" problem). _F_ a. Non blocking sends with double copy 6 _T_ b. Non blocking sends with single copy _F_ c. Blocking sends with single copy 2. In client / server message passing systems the mailbox used for the SERVER to send status to the CLIENT is: 3 a. The same as the one used b. A private box owned by the by the client to send a client. b service request. c. Neither a. or b. -- servers are not allowed to respond to clients. 3. 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 4. Direct naming is most suitable for use by: a. Closely related cooperating b. Unrelated client/server a processes process c. Equally suitable for both 5. In the deadlock detection algorithm process j was marked and had its resources released if a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] for all i. for some i. a c. Claims[j][i] <= avail[i] d. Claims[j][i] <= avail[i] for all i. for some i. 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] d for some i. for all i. c. Claims[j][i] <= avail[i] d. Claims[j][i] <= avail[i] for some i. for all i. 7. At the end of the deadlock detection algorithm, a deadlock exists if: a. There is at least one b. There are no "unmarked" "unmarked" process. processes. a,c c. All processes are "unmarked" 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 1 2 1 4 3 4 2 --------------------------- Resource A B D D C D A A a. Which (if any) of the requests causes the system to deadlock -- identify a request by process and resource id: (e.g., (1, A)) 3 (2,A) b. Which (if any) is the first request that causes a process to become blocked. 3 (1,D) 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 Process 1 2 3 1 2 3 1 1 1 <-- Original ----------------------------- MAX Resource A B C B C A 2 1 1 Claims 3 1 1 a. Which (if any) of the allocation requests would have been the first one denied if the bankers algorithm were in use. 3 (2,B) 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. 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 a. Each time a process references b. Only when the system is rebooted. memory. c c. Each time a new task is d. Each time a partition is reassigned dispatched. but not at each dispatch. 12. The partition management policy that has been accused of creating small unusable free blocks is: a. Best Fit. b. Worst fit. a 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. d c. 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. 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 : : : : : : 000246 5010???????? ST R1, X ;Store R1 in variable X. : : : : : : : : : 00044E 5820???????? L R2, X ;Load X into R2. : : : : 000A4C 00000000 X DW 0 ;Define word variable x ; with init value 0 000C50 ???????? 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 248 (the first batch of ????????'s) by the assembler. 2 a4c c. Suppose the program is loaded into real memory at start address 2E000. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 2e248 2e450 2ec50 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 2 execution. 2ea4c 16. The "fatal flaw" in demand segmentation that caused it to lose out to demand paging was: a. Poor capacity for b. Poor memory protection controlled sharing capability c c. The difficulty in dealing d. All three were equally with variable size allocation important. of real memory and backing storage on disk 17. For each of the following functions answer A, O, L, or H depending upon whether the function is performed by the application itself, O/S, the Compiler/Linker, is performed in hardware without OS intervention: _L_ 1. Create the relocation tables in the a.out file. _H_ 2. Test each real memory address to see if its outside the bounds of the segment being accessed. 5 _O_ 3. Zero the present bit when a page is stolen. _H_ 4. Test the present bit when an address is translated. _O_ 5. Test the allocated bit after a page fault to determine whether a legitmate page fault or a protection error has occured. 18. Suppose a hierarchical paging system uses 32 bit virtual addresses. Suppose 10 bits are used for offset into a page, 12 bits as page table index, and 10 bits as page directory index. a. How large is a page. 2 2^10 b. How many entries are there in a page table. 2 2^12 c. How much virtual memory can be accessed through a single page DIRECTORY entry. 2 2^22 d. How large would a single linear page table that mapped the entire virtual address space be if entries were 4 bytes each. 2 2^24 19. Suppose a hierarchical paging system uses 32 bit virtual addresses. Suppose 10 bits are used for offset into a page, 10 bits as page table index, and 12 bits as page directory index. Suppose a virtual address of 0x1234abcd a. What is the offset into the page (in hex)? 2 3CD b. What is the page table index (in hex)? 2 12A c. What is the page directory index (in hex)? 2 123 20. Suppose it is determined that a processor executes 20,000,000 instructions per second and instructions AVERAGE 1.75 references per instruction to memmory. Suppose a working set window size of 10,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 3 2/7 SEC 21. The minimum value of |W(n, h)| (the size of the working set of a process at reference "n" with window "h" is: a. 1 b. n a c. h d. n + h 22. 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 d c. the total number of pages d. No larger that ANY owned by the process of the above. 23. Consider the following reference string: Ref # 1 2 3 4 5 6 7 8 9 10 Page 33 44 32 44 31 33 32 31 32 44 3 What is W(10, 4)? {44, 32, 31} 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. __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. 25. 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 a. only if the reference b. only if the reference bit b bit was 1 was 0 c. only if the UIC was 0 d. only if the UIC was non zero. 26. In conducting the reference bit tests the OS 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. 27. When a pseudo-LRU page replacement policy is in effect, global real memory overcommittment (==shortage) can be detected when: a. When the min value of b. When the max value of all UIC's is large. all UIC's is large. d c. When the min value of d. When the max value of all UIC's is small. all UIC's is small.