Computer Science 422/622 Test 2 - Dec 4, 2000 Name________________________ 1. We looked at a possible solution of the following form: writer() reader() { { wait(wsem); wait(wsem); -- write -- -- read -- signal(wsem); signal(wsem); 3 } } What is the major problem with this solution? Doesn't permit multiple readers to read concurrently 2. Suppose the reader exit code for the reader priority solution is written as: wait(rmutex); rcount -= 1; signal(rmutex); if (rcount == 0) signal(wsem); The location of the signal(rmutex) is: a. Correct as it stands and moving b. Incorrect as it stands and it to just after signal(wsem) needs to be moved to just B would break the code. after signal(wsem); c. Works fine in either place 3. In a message passing system, the buffer recycling problem a. goes away whenever single b. can't be eliminated in or double copy is used single copy but never occurs D in double copy c. can be eliminated in single d. never occurs in double copy and double copy... but only and can be eliminated in via rendezvous synchronization single copy via rendezvous sync. 4. In the following list of allocation requests circle the first request that causes a deadlock Proc 2 4 1 1 4 3 3 ------------------------- No deadlock Res B C A B A D C 5. In the deadlock detection algorithm a process j is blocked if and only if: a. Requested[j][i] > 0 for b. Requested[j][i] > 0 for B all i some i c. Requested[j][i] == 0 d. Requested[j][i] = 0 for some for all i. i 6. A system may contain a deadlock: a. even if all entries in the b. If a least one row in the requested table are 0. requested table has at least D one non-zero entry c. If at least one row has d. If at least two rows have at all non-zero entries least on non-zero entry 7. Which of the following is invariant: a. avail[i] b. avail[i] + sum (alloc[i][j]) B j c. avail[i] + sum(req[i][j]) d. avail[i] - sum (alloc[i][j]) j j 8. 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. 9. 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 10. Each relocation fixup requires adding to each address reference in a program. a. The length of the program b. The relative address of each location referenced. C c. The address at which the program is loaded. 11. Relocation fixups are performed. a. By the application process b. By the the linker when the in its own initialization executable a.out file is created. C code. c. By the OS when the program is read into memory. 12. 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, 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. 8 _L_ 2. Create the relocation tables used in load time relocation. _H_ 3. Translate a (segment, offset) address to real memory address. _O_ 4. Test the allocated bit after a page fault to determine whether a legitmate page fault or a protection error has occured. 13. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 00024C 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 0004AE 5820???? L R2, Y ;Load Y into R2. : : : : 000504 00000000 X DW 0 ;Define word variable x ; with init value 0 000508 ???? 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 the second batch of ????'s by the assembler. 2 0x508 c. Suppose the program is loaded into real memory at start address 4800. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 3 4A4E 4CB0 4D08 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 4D08 14. 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. D d. Paging significantly reduces d. None of the above the complexity of the load time relocation problem. 15. 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. 16. 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. 17. Suppose page size is 1024 bytes. Give (in hex) the page number and offset associated with the virtual address: 0x34567 Page number - D1 4 Offset - 167 18. The maximum value of |W(n, h)| (the size of the working set of a process at reference "n" with window "h" can be no larger than: a. n b. h D c. the total number of pages d. No larger that ANY owned by the process of the above. 19. Consider the following reference string: Ref # 1 2 3 4 5 6 7 8 9 10 11 Page # 33 44 32 44 31 31 32 31 31 44 a. What is |W(9, 5)| 2 2 b. What (if any) page number at reference 11 would make |W(11, 4)| < | W(10, 4) | 2 31, 44 c. What (if any) page number at reference 11 would make |W(11, 4)| > | W(10, 4) | 2 none 20. Suppose it is determined that a processor executes 30,000,000 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/3 second 21. Associate each of the following page stealing algorithms with the appropriate description: __4_ a. OPT 1. Steal the page that has been referenced most often. 6 __5_ b. LRU 2. Steal the page that is not in the working set of any process __2_ c. WS 3. Steal the page with the smallest number of total references 4. Steal the page that will be next referenced most distant in the future 5. Steal the page that was last referenced most distant in the past. 22. In the model discussed in class, page frame descriptors moved among the AFL, PFL, RL, and WL lists under control of the Page Stealer, Page Reader, Page Fault Int Handler, and Page Writer. For each of the following transitions identify the responsible process: (PFL = Pageable frame list (available for stealing)) (AFL = available frame list (available for reassignment)) RL = read list (assigned and awaiting read completion). WL = Write list (assigned and awaiting writeback.) _4_ a. RL to PFL 1. Page stealer _3_ b. AFL to PFL 2. Page writer 5 _2_ c. WL to AFL 3. Page fault int handler _1_ d. PFL to WL 4. Page reader _1_ e. PFL to AFL 5. None of the above (The transistion does not occur.) 23. Suppose a hierarchical paging system uses 32 bit virtual addresses. Suppose 9 bits each are used for offset into a page, 10 for a page index, and 13 for a page directory index. a. How large is a page. 2 ^ 9 b. How many entries are there in a page table. 2 ^ 10 8 c. How much virtual memory can be accessed through a single page directory entry. 2 ^ 9 x 2 ^ 10 = 2 ^ 19 d. Suppose virtual address 0x123ABCDE is referenced. What is the value of the offset within the target page. DE 24. Suppose a computer system uses 4096 byte pages and virtual address with the value 0x001b67 is generated. What physical address will this address be generated if the page table shown is used: 0x12b 0x345 0x12a 3 234b67 0x006 0x1eb 0x1ac 0x234 PTBR -> 0x005 25. Suppose a computer system uses 8192 byte sized pages. The number of bits representing the OFFSET within a page is: a. 14 b. 12 D c. 10 d. None of the above 26. Identify the appropriate description for the use of the allocated (A) and present (P) bits. _4__ a. A = 0 P = 0 1. This setting should NEVER happen _1__ b. A = 0 P = 1 2. A page owned by an app has been stolen 8 by the OS _2__ c. A = 1 P = 0 3. The page is allocated to an application and attempts to access it will succeed. _3__ d. A = 1 P = 1 4. The page is not allocated to an application and the app will "segfault" if it attempts to access the page.