Computer Science 422/622 Test 2 - Apr 19, 1996 Name________________________ 1. Consider the following solution to the readers and writers problem: 5 pts wait(rmutex); wait(wsem); if (rcount == 0) write(); wait(wsem); signal(wsem); rcount = rcount + 1; signal(rmutex); read(); a. The reader solution is incomplete. Complete it. wait(rmutex) if (rcount == 1) signal(wsem) rcount -= 1; signal(rmutex) b. Does this solution permit either readers or writers to starve? If so who? 3 pts Writers might starve The following questions refer to the FIFO implementation of message passing that we discussed in class: 2. A mailbox write procedure should check for 3 x a. Blocked readers before checking b. Available buffer space before for available buffer space. checking for blocked readers. c. It doesn't matter because blocked readers and available buffer space are mutually exclusive. 3. A mailbox read procedure should check for 3 a. Blocked writers before removing x b. Blocked writers after removing a message from the bufffer. a message from the buffer. c. It doesn't matter because blocked writers and buffered messages are mutually exclusive. 4. In a system using message passing it is typical for the creator of a mailbox to be the only process allowed to: a. Write to the mailbox x b. Read the mailbox c. Open the mailbox. d. Close the mailbox. 5. The synchronization method that is most typically used in message passing (and also makes it possible for mailboxes to easily emulate semaphores is): 3 a. Blocking reads and writes x b. Blocking reads and non-blocking writes c. Non-blocking reads and d. Non-blocking reads and blocking writes. non-blocking writes 6. a. We identified 4 conditions that were NECESSARY for a deadlock to exist. One of them was the use 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 - No preemption 6 2 - Hold and wait 3 - Circular chain of processes each waiting for a resource held by another. b. For each of the following deadlock prevention mechanisms identify the deadlock condition prevented and a resource class for which its use is appropriate. Simulataneous allocation of all resources: Condition prevented: Hold + wait 4 Resource class: Files, devices Hierarchical allocation - Condition prevented: Circular chain 4 Resource class: Internal OS locks 7. In the deadlock detection algorithm resources were the resources of process i were released if a. Requested[i][j] <= avail[j] x 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 a the resources of process i were released what was added to avail[j]? 3 x a. Allocated[i][j] b. Requested[i][j] c. Allocated[i][j] + d. Allocated[i][j] - Requested[i][j] Requested[i][j] 9. In the deadlock avoidance (banker's) algorithm a process was marked and had its resources released if 3 a. Claims[i] <= allocated[i] x b. Claims[i] <= available[i] for for all i. all i. c.(Claims[i] + requested[i]) d. (Claims[i] + requested[i]) <= allocated[i] <= available[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 ----------------------------------- 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. 3 4 - A 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 Process 1 2 3 1 2 1 1 1 1 <-- Original --------------------------- MAX Resource A B C B A 2 1 1 1 Claims 3 1 1 1 Which will be the first one denied by the bankers algorithm: 3 2 - B 12. 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. 13. The use of a single/pair of base/ limit registers when compared to physical memory addressing: 3 a. Makes both relocation and x b. Makes relocation much easier but controlled sharing much doesn't do much for controlled easier. sharing. c. Makes neither relocation or controlled sharing much easier. 14. 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? 3 3 b. What value will be inserted at relative location 486 (the first batch of ????????'s) by the assembler. 880 3 c. Suppose the program is loaded into real memory at start address C000. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 c486 c634 c884 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 c880 15. 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 is statically initialized at compile time. 3 c. The use of informal and d. All of the above contribute dynamically created pointers. equally. 16. Wasted memory WITHIN a partition is typically a more significant problem in: 3 a. Variable (dynamic) partition x b. Fixed partition systems systems. c. Equally bad in both systems. d. Cannot occur in either system. 17. The biggest advantage of segmentation over the use of a single pair of base bounds registers is that: a. It makes it much easier to b. It improves the capability move a program around for controlled sharing. in memory. c. Segmentation hardware is d. It significantly reduces simpler and cheaper to build the complexity of the load time relocation problem. 18. For each of the following functions answer O, L, or H depending upon whether the function is performed by the O/S, by the Linker, or performed by the hardware in hardware without OS intervention. _O_ 1. Build segment tables to translate addresses when a new program 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. _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 present bit when an address is translated. 19. 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. 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. 20. Suppose a paging system uses 24 bit virtual addresses a single linear page table and each page is 1024 bytes in size. a. How many entries does a page table mapping the entire virtual address space contain? 14 3 2 = 16K b. How many bits of an address are translated by the address translation hardware. 14 21. We described an approach to approximating LRU page replacement that involved having the OS "wake up" every second or so and act upon the reference bits of every real memory page. Describe the actions taken: OS maintains a counter called the UIC for each page frame OS wakes up and resets all reference bits to 0 If the bit was originally 0, OS adds one to the UIC for the page. If the bit was originally 1, the OS sets the UIC for the page to 0. ---------- OS tries to steal pages with high UIC's