Computer Science 422/622 Test 2 - Apr 10, 1992 Name________________________ 1. In a system using mailboxes it is typical for the creator of a mailbox to be the only process allowed to: a. Write to the mailbox b. Read the mailbox c. Open the mailbox. d. Close the mailbox. 2. When using mailboxes and dummy messages to simulate the operation of countinng semaphores. It is desirable to have: a. Readers block if the box b. Readers block if the box is is empty and writers block empty but writers continue after the if no reader is waiting for message is copied to the mailbox. a message. c. Writers block if no reader d. Both readers and writers continue is waiting for a message regardless of whether there is a but readers continue if no message available or a blocked reader. message is in the box. 3. Answer the following T or F depending upon whether or not the condition could arise in a correctly functioning message passing system that uses fixed length messages. ___ a. A mailbox could have both blocked readers and blocked writers ___ b. A mailbox could have blocked readers and available buffer space. ___ c. A mailbox could have blocked writers and available buffer space. 4. A mailbox READ procedure in a FIFO message passing system should consume: a. Messages in the buffer before b. Messages from blocked writers messages from blocked writers. before messages in the buffer. c. It doesn't matter because blocked writers and buffered messages are mutually exclusive. 5. If interrupts are disabled during mailbox processing, then a mailbox semaphore or lock is NECESSARY a. Only on a single CPU system b. Only on a multiple CPU system. c. On both single on multi d. Not at all. CPU systems. 6. Match the deadlock prevention strategy with the resource type for which it is most applicable. ___ 1. Hierarchical allocation a. Memory ___ 2. Use of preemption b. Application processes ___ 3. Simultaneous allocation c. Files / devices of all required resources d. Internal OS locks 7. Four conditions were described as necessary for a deadlock to occur. Each of the three strategies described in the last question defeats one of the four conditions.. What is the 4th condition? 8. For the following outline of the deadlock detection algorithm circle the appropriate terms. a. Each step of the iteration start with the release of the resources of 1. all processes 2. all blocked processes 3. all unblocked processes b. The algorithm terminates after an iteration in which 1. A single resource is freed. 2. No resources are freed. 3. A process is unblocked. c. When the iteration terminates, the system is deadlocked if 1. there are no blocked processes 2. there are some blocked processes 3. all the original processes are blocked. 9. Suppose a system contains three processes (1, 2, and 3) and four single unit resources (A, B, C, D). Suppose the following sequence of requests occurs Process 1 1 2 3 3 1 ----------------------------- Resource A B B D A C a. Draw the resource allocation directed graph using the notational conventions of the text. b. Is this system deadlocked?? Explain why or why not USING THE GRAPH as a basis for your reasoning. c. What additional information would be needed if you were to apply the bankers algorithm at each step to determine if an allocation were safe or not. 10. When base/limit registers are used they must be reloaded a. Each time a new task is b. Each time a partition is reassigned dispatched. but not at each dispatch. c. Each time a process references memory. 11. The use of a single/pair of base/ limit registers when compared to physical memory addressing: a. Makes both relocation and 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. 12. Wasted memory WITHIN a partition is typically a more significant problem in: a. Variable (dynamic) partition b. Fixed partition systems systems. c. Equally bad in both systems. d. Cannot occur in either system. 13. Fragmentation of free (unallocated) memory is a major problem in a. All fixed partition b. Fixed partition systems not systems. supporting dynamic relocation c. All variable partition d. Variable partition systems not systems supporting dynamic relocation e. b and d 14. Load time relocation fixups are: a. More likely to be required b. More likely to be required in in base/limit systems than systems using physical addresses in physical memory addressing than base limit addresses. systems. c. not used at all in either base/limit or physical memory systems. 15. The name of the memory placement (FIT) scheme that always allocates from the largest block of free memory is: 16. For each of the following functions related to memory managment answer H if it is purely a hardware function and O if it is performed by the OS. ____ a. Translating (seg, offset) form addresses to real memory addresses each time a process references memory. ____ b. Building a segment table for a newly created process. ____ c. Detecting that an address translation cannot be performed because the Invalid bit is set and generating an interrupt. ____ d. Setting the Invalid bit. ____ e. Keeping track of how many seconds since a page has been referenced by periodically testing and resetting the Referenced bit. ____ f. Setting the referenced bit each time a page or segment is referenced. ____ g. Choosing a page or segment to write out to disk when a memory shortage occurs. 17. Suppose a hierarchical paging system uses 24 bit virtual addresses. Suppose 10 bits each are used for offset into a page, and 7 bits each for page table index, and page directory index. a. How large is a page. b. How many entries are there in a single page table. c. How much virtual memory can be accessed through a single page directory entry. d. Suppose the virtual address 0x789abc is referenced: Give the value of the offset, page table index, and page directory index in hex. Offset = Table NDX = Directory NDX = 18. Match the settings of the resident and allocated bits with the appropriate description. ___ 1. Protection violation a. Resident and Allocated ___ 2. Reference to a page that b. Not resident and allocated must be read back into memory. c. Resident and not allocated d. Not resident and not allocated