Computer Science 422/622 Test 2 - 24 Nov 1997 Name____________________ 1. 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. Sequential allocation 6 _2_ b. Real memory 2. Preemption _4_ c. Internal O/S locks 3. Simultaneous allocation 4. Hierarchical allocation 5. Fully shared resources 2. For client / server systems using message passing a a. Indirect naming is b. Direct naming is superior superior to direct naming. to indirect naming. 3 c. Both methods are d. Neither method is at all equally good. suitable. 3. In client / server message passing systems the mailbox used for the SERVER to send status to the CLIENT is: b a. The same as the one used b. A private box owned by the by the client to send a client. 3 service request. c. Neither a. or b. -- servers are not allowed to respond to clients. 4. One of the issues in the implementation of message passing was "copying". The message passing system that we implemented in assignment 4 is best classified as: c a. Zero copy b. Single copy 3 c. Double copy d. Triple copy 5. The "buffer recycling" problem in a message passing system a a. is worse with zero copy b. is worse with single or double than with single or double copy than with zero copy 3 copy c. is not related to the "copy" strategy used at all. 6. The synchronization method that is most typically used in message passing (and also makes it possible for mailboxes to easily emulate semaphores is): b a. Blocking reads and writes b. Blocking reads and non-blocking 3 writes c. Non-blocking reads and d. Non-blocking reads and blocking writes. non-blocking writes 7. In the deadlock detection algorithm resources the resources of process i were released if: d a. Requested[i][j] < avail[j] b. Requested[i][j] < avail[j] 3 for some j. for all j. c. Requested[i][j] <= avail[j] d. Requested[i][j] <= avail[j] for some j. for all j. 8. When the resources of process i were released what was added to avail[j]? c a. Allocated[i][j] + b. Allocated[i][j] - Requested[i][j] Requested[i][j] 3 c. Allocated[i][j] d. Requested[i][j] 9. In the deadlock avoidance (banker's) algorithm a process was marked and had its resources released if d a.(Claims[i] + requested[i]) b. (Claims[i] + requested[i]) <= allocated[i] <= available[i] 3 c. Claims[i] <= allocated[i] d. Claims[i] <= available[i] for for all i. all i. 10. 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 3 3 ----------------------------------- Resource A B C C D C A A Which request (if any) is the first one to cause a deadlock in this chain of requests. None 11. 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 1 <-- Original ----------------------------------- MAX Resource A B C C D C A A 2 1 1 1 1 Claims 3 3 1 1 1 1 4 1 1 1 1 Which will be the first one denied by the bankers algorithm: 2-C 12. When base/limit registers are used they must be reloaded a 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. 13. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 000484 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 000632 5820???? L R2, X ;Load X into R2. : : : : 000880 00000000 X DW 0 ;Define word variable x ; with init value 0 000884 ???? 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 486 (the first batch of ????'s) by the assembler. 2 880 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. 4 ac86 ae34 b084 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. b080 2 14. 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. 15. For each of the following functions answer O, L, H, A depending upon whether the function is performed by the O/S, by the Linker, by hardware without OS intervention, or by the application itself. _O_ 1. Build segment tables to translate addresses when a new process is 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. 16. Which of the memory allocation policies that we discussed always allocates from the largest free block of memory. d a. First Fit. c. Last fit. 3 b. Best Fit. d. Worst fit. 17. Recombining free blocks in a variable partition system is necessary b a. Only during a partition b. Only when a partition is freed. allocation. 3 c. Both a. and b. d. Only when a process terminates 18. The main advantage that paging has over segmentation is that: c a. Paging makes controlled b. Paging provides a finer grained sharing easier. level of memory protection. 3 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. 19. Suppose a paging system uses 32 bit virtual addresses a single linear page table and each page is 2048 bytes in size. a. How many entries does a page table mapping the entire virtual address space contain? 2 2^21 b. How many bits of an address are translated by the address translation hardware. 2 21 20. 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. 2^9 2 b. How many entries are there in a page table. 2^10 2 c. How much virtual memory can be accessed through a single page DIRECTORY entry. 2 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. 2 2^23 21. Suppose it is determined that a processor executes 20 million 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. 1/2 23. 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 b a. only if the reference 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. 24. In conducting the reference bit tests the OS c a. leaves all reference bits b. sets them all to 1 in whatever state it finds 3 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. 25. When a pseudo-LRU page replacement policy is in effect, global real memory overcommittment (==shortage) can be detected when: d a. When the min value of b. When the max value of all UIC's is large. all UIC's is large. 3 c. When the min value of d. When the max value of all UIC's is small. all UIC's is small.