Computer Science 422/622 Test 2 - Apr 13 2004 Name________________________ 1. 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) 2. Does the following graph represent a deadlock? NO - There is a cycle but no knot 3 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 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 5. 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 6. 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 7. 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 one non-zero entry 8. A system must contain a deadlock: a. If every row in the requested b. If a least one row in the table has a non-zero entry. requested table has at least A 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 9. When the resources of process j were released what was added to avail[i]? a. Allocated[j][i] + b. Allocated[j][i] - C Requested[j][i] Requested[j][i] c. Allocated[j][i] d. Requested[j][i] 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. 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. 12. 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. 13. First fit is equivalent to worst fit when the free partition list is sorted.. a. by starting address from b. by starting address from D low to high high to low c. by size from low to high d. by size from high to low 14. 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. 15. When base/bounds addressing is being used, relocation fixups are required: a. Only when the "a.out" is b. Whenever the program is moved D initially loaded into memory after executing for a while.. c. Both a. and b. d. Neither a. nor b. 16. When base/bounds addressing is being used the base/bounds registers must be loaded: a. Only at the time the system b. Each time a new process is C is booted. created. c. Each time a new process is d. Each time an instruction dispatched. is executed 17. 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 18. The purpose of the "auxilliary" or shadow bitmap discussed in class and used in the assignment was to: a. identify allocated blocks b. identify the first block of an allocated area D c. identify free blocks d. identify the last block of an allocated area 19. Answer the following H, O, or L depending upon whether the specified function is the responsibility of the Hardware, the OS, or the Language Translator. _O_ a. Constructing the memory resident segment table that is actually used to map (seg, offset) form addresses to real memory addresses. _H_ b. Detecting that a memory access being performed is inconsistent with the attributes of the target segment and generating a 8 seg-fault interrupt if such is not the case. _L_ c. Assigning specific elements (data structures or code procedures) of a program to specific segments. _H_ d. Mapping application generated addresses of the form (segment, offset) to real memory addresses. 20. 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, Y ;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 by the assembler at relative location 446 (the first batch of ????'s) 2 A84 c. Suppose the program is loaded into real memory at start address 1C00. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 1C00 + 446 3 1C00 + 6D0 1C00 + A84 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 1C00 + 980 21. Suppose a process executes: p = malloc(256 * 1024) a. Page table entries are b. Real memory is assigned created for the space to the virtual pages A c. Both (a) and (b). d. Neither (a) nor (b) 22. Suppose the process then executes: memset(p, 0, 256 * 1024); a. Page table entries are b. Real memory is assigned B created for the space to the virtual pages c. Both (a) and (b). d. Neither (a) nor (b) 23. 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. 24. 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. 25. Suppose page size is 2048 bytes. Give (in hex) the page number and offset associated with the virtual address: 0x56789 Page number - AC 4 Offset - 789 26. 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 3 What pages are in W(10, 5)? 44 32 31 27. In the above example the relationship of |W(11, 6)| to |W(10, 6)| is (circle ALL that could conceivably be correct. x a. |W(11, 6)| > |W(10, 6)| b. |W(11, 6)| < |W(10, 6)| 3 x c. |W(11, 6)| == |W(10, 6)| 28. Suppose it is determined that a processor executes 40,000,000 instructions per second and instructions AVERAGE 1.5 references per instruction to memmory. Suppose a working set window size of 60,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 60 3 -------------- = 1 second 40 * 1.5 29. The best 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 30. Associate each of the following page stealing algorithms with the appropriate description: __2_ a. FIFO 1. Steal the page that has been referenced most often. 9 __5_ b. OPT 2. Steal the page that has been allocated the longest time. __4_ c. LRU 3. Steal the page with the smallest number of total references 4. Steal the page that was last referenced most distant in the past. 5. Steal the page that will be next referenced most distant in the future 31. 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.) 32. Suppose a hierarchical paging system uses 32 bit virtual addresses. Suppose 10 bits each are used for offset into a page, 11 for a page index, and 11 for a page directory index. a. How large is a page. 2 2^10 bytes b. How many entries are there in a page table. 2 2^ 11 entries c. How much virtual memory can be accessed through a single page directory entry. 2 2^21 bytes d. Suppose virtual address 0xABC12345 is referenced. What is the value of the page <> index. 2 0x48 e. How many entries would a single linear page table used to map all of virtual memory require? 2 2^22 entries 33. For each of the standard segmentation/paging flag bits identify how the are used during normal operation of the system: __D_ 1. Allocated a. Set by the hardware and periodically tested and reset by the O/S. 9 __B_ 2. Present 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