Computer Science 422/622 Test 2 - Apr 18 2001 Name________________________ (POINT values are 3 / question unless noted) Consider the following (correct) implementation of setlock: [0] CLI ;disable ints [1] RETRY: [2] CMPI LOCKVAL, 0 ;see if its 0 [3] JNZ RETRY ;if not, keep trying til it is. [4] TS LOCKVAL ;use the hardware to make sure. [5] JNZ RETRY ;start over if we got beat to the lock [6] RET 1. If statements [4] and [5] were removed which of the following BEST describes the result in a multiprocessor system. a. it would no longer work b. it would still work correctly A correctly. but it would be slower. c. it still work correctly and it would be faster. 2. If statements [4] and [5] were removed which of the following BEST describes the result in a single processor system: a. it would no longer work b. it would still work correctly correctly and but it would but it would be slower. C be faster. c. it still work correctly and it would be faster. 3. If interrupts are not disabled while attempting to acquire a test and set lock in a system that uses strict priority scheduling a. Processes may deadlock in b. Processes may deadlock single processor system in both single and multiple but not in an MP system. processor systems but the B likelihood of deadlock is greater on a single processor c. Processes may deadlock d. Processes may deadlock in in both single and multiple a multiple processor system processor systems but the but not in a single processor. likelihood of deadlock is greater on a multiprocessor 4. On a single processor system, a process finding the lock value already set to 1 when it reaches line [2] a. is normal and occurs b. implies that process is from time to time. stuck in an infinite loop C but other processes can run. c. implies that the system has crashed and must be rebooted. 5. On a multi-processor system, a process finding the lock value already set to 1 when it reaches line [2] a. is normal and occurs b. implies that process is from time to time. stuck in an infinite loop A but other processes can run. c. implies that the system has crashed and must be rebooted. Consider the following code segment from a producer/consumer problem: Producer Consumer wait(slot); wait(mutex); wait(mutex); wait(item); buffer[nxt_in] = new_item; consume = buffer[nxt_out]; nxt_in = (nxt_in + 1) % BUFSZ; nxt_out = (nxt_out + 1) % BUFSZ; signal(item); signal(slot); signal(mutex); signal(mutex); 6. The order of the waits in the above example correct in the a. producer b. consumer A c. both d. neither one 7. As written above, a deadlock might occur: a. Only when the buffer was b. Only when the buffer A empty. was full. c. Anytime regardless of the d. Never state of the buffer. 8. The deadlock could occur: a. Only if there were multiple b. Only if there were multiple consumers. producers D c. Only if there were multiple d. Even if there were a single producers AND consumers. producer and consumer. 9. Can changing the order of the signal statements lead to deadlock if the producers and consumers all use the same mutex semaphore. a. No, never b. Yes, definitely A c. Only when multiple producers or consumers exist. 10. If code were changed so that the consumers used "cmutex" and the producers used "pmutex" the deadlock could occur a. Only if there were multiple b. Even if there were a single C producers AND consumers. producer and consumer. c. Deadlock would no longer occur at all. Consider the following (partial) solution to the readers and writers problem: wait(rmutex); wait(wsem); rcount = rcount + 1; if (rcount == 1) write(); wait(wsem); signal(wsem); signal(rmutex); read(); 11. Suppose a writer is writing and 5 readers are queued to read. The readers will be distributed as follows: a. All will be blocked at b. All will be blocked at D wsem rmutex c. All but one will be d. All but one will be blocked blocked at wsem at rmutex. Suppose the reader code is completed as follows: [1] wait(rmutex); [2] rcount = rcount - 1; [3] if (rcount == 0) [4] signal(wsem); [5] signal(rmutex); 12. Which of the follow best describes the effect of moving statement [5] to between statements [2] and [3]. a. This has no effect on b. This could lead to simultaneous correctness reading and writing D c. This would correct an d. This could lead to a deadlock. error present in the solution shown above. 13. 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: a. Zero copy b. Single copy C c. Double copy d. Triple copy 14. Suppose a single copy message passing scheme is being used. The use of "rendezvous" synchronization (as opposed to non-blocking writes): a. Eliminates the b. Causes the buffer recycling A "buffer-recycling" problem problem c. Has no effect on the buffer d. Slightly reduces the magnitude recycling problem. of the buffer recycling problem. 15. 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 16. In the deadlock detection algorithm resources the resources of process k were released if: a. Requested[k][j] <= avail[j] b. Requested[k][j] <= avail[j] B for some j. for all j. c. Requested[k][j] - Alloc[k][j] c. Requested[k][j] - Alloc[k][j] <= avail[j] for some j <= avail[j] for all j 17. 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 3 3 2 1 4 3 4 --------------------------------------- (3,B) Resource B A C A C D B C Which request (if any) is the first one to cause a deadlock in this chain of requests. (Identify the request as (PID, RID) for example (1, B)). 18. 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. A c. Each time a process references memory. 19. 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. 20. 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. 21. First fit is equivalent to best fit when the free partition list is sorted.. a. by starting address from b. by starting address from C low to high high to low c. by size from low to high d. by size from high to low 22. In freeing a partition in a Variable Partition scheme of memory management, the number of elements in the FREE PARTITION LIST increases: a. Any time any recombining b. Never C takes place. c. only when no recombining d. only when the newly freed is possible. partition recombines with BOTH the partition above it and below it 23. 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. 24. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 000462 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 0006AC 5820???? L R2, X ;Load X into R2. : : : : 000980 00000000 X DW 0 ;Define word variable x : : ; with init value 0 000A84 ???? 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 464 (the first batch of ????'s) by the assembler. 980 2 c. Suppose the program is loaded into real memory at start address C400. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 C864 CAAE CE84 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. 2 CD80 25. For each of the following functions answer O, L, H, A depending upon whether the function is performed by the O/S, by the Language Translator/Linker, by hardware without OS intervention, or by the application itself. _O_ 1. Build the segment tables used to translate addresses when a new process is created and a program loaded into memory. _L_ 2. Create the relocation tables used in load time relocation. _H_ 3. Test the present bit of the associated page each time memory is accessed. 6 _O_ 4. Test the allocated bit after a page fault to determine whether a legitmate page fault or a protection error has occured. _O_ 5. Zero the present bit when a page is stolen. 26. Match the following descriptions with the correct settings of the P and A bits in a segmented/paged memory management system: _C__ 1. Segment has been stolen by OS and a. A = 0 P = 0 written out to disk b. A = 0 P = 1 6 _A__ 2. Segment was dynamically allocated but later freed by the process c. A = 1 P = 0 _B__ 3. Indicates a serious error in the d. A = 1 P = 1 OS 27. In the Pseudo-LRU algorithm that we discussed, the OS periodically tests every reference bit of every page. It adds one to 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. 28. 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. 29. A global memory shortage is indicated when: a. The smallest UIC value is b. The smallest and largest UIC near 0. values are close D c. The smallest UIC value is d. The largest UIC value is near 0 large 30. Suppose page size is 1024 bytes. Give (in hex) the page number and offset associated with the virtual address: 0xabcde Page number - 2AF Offset - DE 31. Suppose a computer system uses 4096 byte pages and virtual address with the value 0x00312C is generated. What physical address will this address be generated if the page table shown is used: 0x12b 0x345 0x12a 321C 0x006 0x003 0x001 0x234 PTBR -> 0x005 (Page Table Base Reg)