Computer Science 422/622 Test 2 - Nov 25 2002 Name________________________ 1. 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. 2. Consider the following lists of resource requests: Proc 2 4 1 1 4 3 2 3 ------------------------- Res B C A B A D C C a. Which is the first one to cause a process to block 2 (1, B) b. Which is the first one to cause a deadlock 2 (2, C) 3. 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 4. 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 5. In the deadlock avoidance algorithm process j was marked and had its resources released if a. Requested[j][i] <= avail[i] b. Requested[j][i] <= avail[i] D for some i. for all i. c. Claims[j][i] <= avail[i] d. Claims[j][i] <= avail[i] for some i. for all i. 6. Which of the following is invariant: a. avail[i] b. avail[i] + sum (alloc[i][j]) j B c. avail[i] + sum(req[i][j]) d. avail[i] - sum (alloc[i][j]) j j 7. Suppose a system contains two processes (1, 2) and two single unit resources (A, B) Suppose the following sequence of requests occurs A B Process 1 2 1 2 1 1 1 <-- Original ----------------------- MAX Resource A B B A 2 1 1 Claims Which (if any) will be the first one denied by the bankers algorithm: Identify the request as (PID, RID). (2, B) 8. Identify the appropriate time to run the deadlock detection algorithm and the bankers (deadlock avoidance) algorithm. _2__ a. Deadlock detection 1. When a resource can be granted. 4 2. When a resource can't be granted _1__ b. The Banker's algorithm and a process must be blocked. 3. Anytime a resource is requested regardless of whether or not it can be granted. 10. First fit is equivalent to best fit when the free partition list is sorted.. a. by starting address from b. by starting address from low to high high to low C c. by size from low to high d. by size from high to low 11. Each relocation fixup requires adding to each address reference in a program. a. The length of the program b. The relative address of each C location referenced. c. The address at which the program is loaded. 12. 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. 13. 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. 14. First fit is equivalent to worst fit when the free partition list is sorted.. a. by starting address from b. by starting address from low to high high to low D c. by size from low to high d. by size from high to low 15. Suppose 16 Mbytes (2^24 bytes) of memory are to be managed using the bitmap approach and memory is to be allocated in chunks of 128 bytes each. What is the required size of the bitmap in BYTES a. 16 KBytes b. 32 Kbytes A c. 64 KBytes d. None of the above 16. Which of the strategies for partition management is most vulnerable to being corrupted by a buggy application a. partition lists b. bitmap C c. tagged block d. None of them are at all vulnerable. 17. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 000444 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 0006CE 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 446 (the first batch of ????'s) by the assembler. 980 2 c. Suppose the program is loaded into real memory at start address AC00. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. B056 B2D0 B684 3 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 B580 18. 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. _L_ 1. Create the relocation tables used in load time relocation. _H_ 2. Translate a (segment, offset) address to real memory address. 8 _H_ 3. Test each real memory address to see if its outside the bounds of the segment being accessed. _O_ 4. Test the allocated bit after a page fault to determine whether a legitmate page fault or a protection error has occured. 19. 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 bit was 1 was 0 B c. only if the UIC was 0 d. only if the UIC was non zero. 20. In conducting the reference bit tests the OS a. leaves all reference bits b. sets them all to 1 in whatever state it finds them C 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. 21. Suppose page size is 2048 bytes. Give (in hex) the page number and offset associated with the virtual address: 0x45678 Page number - 8A 4 Offset - 678 22. 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. 23. Consider the following reference string: Ref # 1 2 3 4 5 6 7 8 9 10 Page 33 44 32 44 31 31 32 31 32 44 What is W(8, 5)? {44, 32, 31} 23. 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 90,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 90,000,000 ------------- = 2 secs 30,000,000 * 1.5 24. The proper measure of time for implementing time-based working set is: a. The process's USER mode b. The process's KERNEL mode CPU time (CPU time executing CPU time (CPU time spent in A application code) system calls) c. Real time 25. 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 has been allocated the longest time. _2__ c. FIFO 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. 26. 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.) _5_ a. RL to AFL 1. Page stealer _3_ b. AFL to PFL 2. Page writer 8 _2_ c. WL to AFL 3. Page fault int handler _1_ d. PFL to AFL 4. Page reader 5. None of the above (The transistion does not occur.) 27. Suppose a hierarchical paging system uses 32 bit virtual addresses. Suppose 9 bits each are used for offset into a page, 11 for a page index, and 12 for a page directory index. a. How large is a page. 2 512 b. How many entries are there in a page table. 2 2048 c. How much virtual memory can be accessed through a single page directory entry. 2 1MB d. Suppose virtual address 0x123ABCDE is referenced. What is the value of the page table index. 2 55E 28. For each of the standard segmentation/paging flag bits identify how the are used during normal operation of the system: __B_ 1. Present a. Set by the hardware and read by the O/S. 6 __D_ 2. Allocated b. Set by the O/S and read by the hardware __A_ 3. Referenced c. Set and read by the hardware but not used by the O/S d. Set and read by the O/S but not used by the hardware 29. 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 by the OS 8 __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.