Computer Science 422/622 Test 2 - Nov 25, 1996 Name________________________ (All multiple guess questions were 3 pts -- total point value = 112) 1. a. We identified 4 conditions that were NECESSARY for a deadlock to exist. One of them was the existence 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 - Hold + Wait 6 2 - No preemption 3 - Cycle (or Knot or Circular Chain) in the process/resource allocation graph b. For each of the following deadlock prevention mechanisms identify the deadlock condition prevented and a resource class for which its use is appropriate. Hierarchical alloction of resources: Condition prevented: Cycle in the allocation graph 4 Resource class: Internal OS locks Preemption of resources - Condition prevented: No preemption of resources 4 Resource class: Memory or processor (any resource whose state can be transparently restored) 2. In the deadlock detection algorithm the resources of process j were released if b a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] for some i. for all i. c. Requested[j][i] >= avail[i] d. Requested[j][i] >= avail[i] for some i. for all i. 3. When the resources of process j were released what was added to avail[i]? a a. Allocated[j][i] b. Requested[j][i] c. Allocated[j][i] + d. Allocated[j][i] - Requested[j][i] Requested[j][i] 4. The system was free of deadlock at the end of the procedure if b a. At least one process was b. All processes were not blocked. not blocked (= marked). (were marked) c. All processes were blocked (=unmarked) . 5. In the deadlock avoidance (banker's) algorithm process j was marked and had its resources released if b a. Claims[j][i] <= allocated[i] b. Claims[j][i] <= available[i] for for all i. all i. c.(Claims[j][i] + requested[j][i]) d.(Claims[j][i] + requested[j][i]) <= allocated[i] <= available[i] for all i. for all i. 6. At the end of the Banker's alogorithm, it was safe to grant the request if: b a. At least one process was b. All processes were not blocked. not blocked (= marked). (were marked) c. All processes were blocked (=unmarked) . 7. Identify the appropriate time to run the deadlock detection algorithm and the bankers (deadlock avoidance) algorithm. 4 _2__ a. Deadlock detection 1. When a resource can be granted. 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. 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 2 1 4 3 2 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. 4 4-A 9. Suppose a system contains four processes (1, 2, 3, and 4) and four single unit resources (A, B, C, D). Suppose the following sequence of requests occurs A B C D Process 1 2 1 4 3 2 4 3 1 1 1 0 0 <-- Original ----------------------------------- MAX Resource A B B C D C A A 2 0 1 1 0 Claims 3 1 0 0 1 4 1 0 1 0 Which will be the first one denied by the bankers algorithm: 4 4-C 10. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 00048C 5010???????? ST R1, X ;Store R1 in variable X. : : : : : : : : : 000638 5820???????? L R2, X ;Load X into R2. : : : : 00074C 00000000 X DW 0 ;Define word variable x ; with init value 0 000850 ???????? 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 48C (the first batch of ????????'s) by the assembler. 3 74C c. Suppose the program is loaded into real memory at start address 1A000. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 1A48E 1A63A 1A850 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 1A74C 11. For each of the following functions answer O, L, or H depending upon whether the function is performed by the O/S, by the Compiler/Linker or performed by the hardware in hardware without OS intervention. _o_ 1. Build the segment tables actually used to translate addresses _l_ 2. Create the relocation tables in the a.out file. 16 _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 prsent bit when an address is translated. _o_ 8. Test and reset the reference bits and update the UIC's. 12. 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. c 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. 13. Identify an advantage of the use of demand segmentation over paging: - Finer grained protection 3 - Improved support for controlled sharing - Eliminates need for load time relocation 14. The partition management policy that has been accused of creating small unusable free blocks is: a. First Fit. c. Last fit. b b. Best Fit. d. Worst fit. 15. Which of the memory allocation policies that we discussed always allocates from the largest free block of memory. a. First Fit. c. Last fit. d b. Best Fit. d. Worst fit. 16. 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 17. The one combination of the allocated and present bits that should never occur is: a. Not allocated and b. Allocated and not present. not present. c c. Not allocated and d. Present and present. allocated. 18. The combination of the allocated and present bits that indicates that a process has made a memory protection violation is: a. Not allocated and b. Allocated and not present. not present. a c. Not allocated and d. Present and present. allocated. 19. If a computer system uses 512 byte sized pages, and a process references address: 0x567def The offset in hex is: 2 0x1ef The page number in hex is: 2 0x2b3e 20. Suppose a computer system uses 2048 byte pages and a virtual address with the value 0x001667 is generated. What physical address will this address be generated if the page table shown is used: 0x007 0x00a 0x006 3 E67 0x00b 0x001 0x234 PTBR -> 0x005 21. Suppose it is determined that a processor executes 10,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 12,000,000 references is selected. What is the appropriate time unit for use in computing working set sizes. 3 12,000,000 / (10,000,000) * 1.5 = 4/5 Suppose the virtual address 0x47E342b2 is to be translated by an Intel processor. 22. The part of the address NOT translated by the hardware is: a. 0xAB2 c. 0x47e b b. 0x2B2 d. None of the above 23. The index into the page TABLE is: a. 0xE32 b. 0x32A d c. 0x232 d. None of the above 24. Now suppose a hypothetical processor uses 36 bit virtual addresses with the bits partitioned as follows: 11 bits = offset into page, 12 bits = page table index, 13 bits = page directory index. a. The amount of memory that can be accessed through a single page table is: 3 2^ 23 b. If page table entries are 4 bytes each, how many bytes are required for a complete page table. There was some confusion here..induced by me.. on the meaning of complete page table. Thus full credit was given for answers describing either an Intel style page table or a single linear table mapping the entire address space. 3 Intel style 4 * 2^12 Full 4 * 2^12 * 2^13 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 Computer Science 422/622 Test 2 - Apr 13, 1995 Name________________________ The first two questions refer to the FIFO implementation of message passing that we discussed in class: 1. The mailbox write procedure should check for 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. 2. The mailbox read procedure should check for a. Blocked writers before checking b. Messages available in the buffer for messages available in the before checking for blocked buffer. writers. c. It doesn't matter because blocked writers and buffered messages are mutually exclusive. 3. 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 b. Read the mailbox c. Open the mailbox. d. Close the mailbox. 4. a. We identified 4 conditions that were necessary for a deadlock to exist. One of them was the use of non preemptable allocation. Name the other tree. 1 - 2 - 3 - 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: Resource class: Hierarchical allocation - Condition prevented: Resource class: 5. In the deadlock detection algorithm a process was blocked if and only if it had (assume available resources are never withheld in the allocation procedure). a. A positive entry in the b. A positive entry in the requested allocated matrix. matrix. c. Positive entries in both d. A positive entry in either requested allocated and requested or allocated. 6. In the deadlock detection algorithm resources were the resources of a process were released if a. Requested[i] <= avail[i] b. Requested[i] <= avail[i] for some i. for all i. c. Requested[i] >= avail[i] d. Requested[i] >= avail[i] for some i. for all i. 7. The system was free of deadlock at the end of the procedure if a. At least one process was b. All processes were not blocked. not blocked (= marked). c. All processes were blocked (=unmarked) . 8. In the deadlock avoidance algorithm a process was marked and had its resources released if a. Claims[i] <= allocated[i] 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] 9. 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 --------------------------- Resource A B B C D C A Which (if any processes are deadlocked)? 10. 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 b. Which (if any) of the allocation requests would have been the first one denied if the bankers algorithm were in use. 11. 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. 12. 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. 13. 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. 14. 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 15. 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. 16. 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. c. The use of informal and d. All of the above. dynamically created pointers. 17. 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 page 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 when a page is stolen. ____ 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. 18. Suppose a hierarchical paging system uses 36 bit virtual addresses. Suppose 10 bits are used for offset into a page, 14 bits as page table index, and 12 bits as page directory index. a. How large is a page. b. How many entries are there in a page table. c. How much virtual memory can be accessed through a single page directory entry. d. How large would a single linear page table that mapped the entire virtual address space be if entries were 4 bytes each. 19. Both the base and limit page table descriptor registers and hierarchichal table techniques are designed to eliminate the requirement for immense page table space requirements. a. What is the principal advantage of a base / limit technique over hierarchical tables. b. What is the principal advantage of hierarchical tables over base /limit. 20. Suppose it is determined that a processor executes 12,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 20,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 21. 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 22. 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: Computer Science 422/622 Test 2 - 16 Apr - Name ___________________ 1. Identify three approaches for deadlock PREVENTION along with examples of the resources for which the technique is a good choice. Technique Resource ---------------------------------------------------------- | 1 | | ---------------------------------------------------------- | 2 | | ----------------------------------------------------------- | 3 | | 2. 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. 3. a. Using the deadlock detection graph shown on the board fill the following table: Process ID | Holds Resource(s) | Waiting on Resource(s) ------------------------------------------------------- | | ------------------------------------------------------- | | ------------------------------------------------------- | | ------------------------------------------------------- | | ------------------------------------------------------- b. Give the ID of any deadlocked processes. 4. 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 A B C D Process 1 1 2 3 3 1 1 1 1 1 1 <-- Original ----------------------------- MAX Resource A B B D A C 2 1 Claims 3 1 1 a. Is this system deadlocked?? b. Which (if any) of the allocation requests would have been the first one denied if the bankers algorithm were in use. 5. 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 a. How many relocation table entries will be generated by the above code sequence? b. What value will be inserted at relative location 486 (the first batch of ????????'s) by the assembler. c. Suppose the program is loaded into real memory at start address 8000. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 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. 7. a. How (if at all) would the use of base / bounds addressing simplify the load time relocation process considered in question 5.. b. Why is it useful to be able to dynamically relocate a program that has been in execution for some time. c. Why is dynamic relocation generally not possible in systems that employ real memory addresses. d. Is dynamic relocation possible with base/bounds addressing if so describe how to do it. If not state why not. 8. For each of the following actions answer O, A, or H depending upon whether the function is performed by the O/S, in application code, performed by the hardware in hardware without OS intervention. ___ 1. Build segment tables. ___ 2. Translate (segment, offset) address to real memory address. ___ 3. Test each memory access to see if its outside the bounds of the segment being accessed. ___ 4. Set the allocated bit when a page is assigned. ___ 5. Set the invalid bit when a page is stolen. ___ 6. Test the invalid bit when an address is translated. 9. Suppose a paging system uses 24 bit virtual addresses a single linear page table and each page is 512 bytes in size. a. How many entries would a page table contain? b. How many bits of an address are translated by the address translation hardware. 10. Suppose a hierarchical paging system uses 36 bit virtual addresses. Suppose 11 bits are used for offset into a page, 12 bits as page table index, and 13 bits as page directory index. a. How large is a page. b. How many entries are there in a page table. c. How much virtual memory can be accessed through a single page directory entry. 11. Match the settings of the Present and Allocated page table bits with the correct description: ___ a. Not Present, Not Allocated 1. Should never occur. ___ b. Not Present, Allocated 2. Memory protection violation ___ c. Present, Not Allocated 3. Successful access to memory ___ d. Present, Allocated 4. Page fault. 12. a. 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: b. We also described an approach to approximating working set replacement that was time based rather than reference count based. Suppose it is determined that a processor executes 6,000,000 instructions per second and that each instruction AVERAGES 1.5 memory references. Suppose a working set window size of 12,000,000 references is selected. In order to determine the approximate working set how long should the OS let the process run before testing the reference bits of the pages owned by the process? 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