Computer Science 422/622 Test 2 - Apr 16, 2003 Name________________________ 1. In the following list of allocation requests Proc 2 4 1 1 4 3 3 ------------------------- Res B C A B A D C a. Which (if any) is the first one to cause a process to block Proc = 1 2 Res = B b. Which (if any) is the first one to cause a deadlock Proc = None 2 Res = 2. 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 3. 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 4. In the deadlock detection algorithm 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 5. In the deadlock avoidance algorithm the resources of process i are released if a. Requested[i][j] <= avail[j] b. Requested[i][j] <= avail[j] d for some j. for all j. c. Claims[i][j] <= avail[j] d. Claims[i][j] <= avail[j] for some j. for all j. 6. In the classic two process two resource deadlock which of the following requests would be the first one denied by the deadlock avoidance algorithm: a. P0 for R0 b. P1 for R1 b c. P0 for R1 d. P1 for R0 7. In the deadlock avoidance algorithm which of the following is invariant a. Allocated[i][j] + b. Allocated[i][j] - Requested[i][j] Requested[i][j] c c. Allocated[i][j] + d. Allocated[i][j] - Claims[i][j] Claims[i][j] 8. The proper time to run the deadlock detection and the deadlock avoidance algorithm is: a. both should be run when b. both should be run when a a request can be granted a request can't be granted d c. detection when it can but d. detection when it can't avoidance when it can't but avoidance when it can. 9. 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 abnormally 10. In freeing a partition in a variable partition scheme of memory management, the number of elements in the free partition list remains unchanged.. a. only when no recombining b. only when the newly freed is possible. partition recombines with BOTH d the partition above it and below it c. Any time any recombining d. Only when the newly freed partition takes place. combines with either the partition above it XOR the partition below. 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. 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 13. Suppose 4 Mbytes (2^22 bytes) of memory are to be managed using the bitmap approach and memory is to be allocated in chunks of 512 bytes each. What is the required size of the bitmap in BYTES 2^22 / 2 ^ 9 / 2^3 = 2^ 10 = 1024 Bytes 14. In buddy system allocation suppose it is necessary to destroy a free block of size 2^12 to satisfy a request for 2^9 bytes. The number of NEW free blocks that will be created is a. 1 b. 2 c c. 3 d. 4 15. 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. 16. Suppose following program is to be loaded on a real memory system with variable partitions: Rel Loc Machine Code Assembler Code : : : : : : 00014C 5010???? ST R1, X ;Store R1 in variable X. : : : : : : : : : 0002A0 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? 3 3 b. What value will be inserted at the second batch of ????'s by the assembler. 3 508 c. Suppose the program is loaded into real memory at start address 3800. What is/are the real (NOT RELATIVE) address(es) of the location(s) that will be modified during the relocation process. 2 394e 3aa2 3d08 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. 3d08 2 17. 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 10 seg-fault interrupt. _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. _o_ e. Loading the STBR and STLR registers each time a new process is dispatched. 18. 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. 19. 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. 20. Suppose page size is 1024 bytes. Give (in hex) the page number and offset associated with the virtual address: 0x434567 Page number - 10d1 4 Offset - 167 21. 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. 22. 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 44 31 44 Please be careful to distinguish w(n, h) from |w(n, h)| a. What is W(9, 5) {31 32 44} b. What (if any) page number at reference 11 would make 6 |W(11, 4)| < | W(10, 4) | 31 or 44 c. What (if any) page number at reference 11 would make |W(11, 4)| > | W(10, 4) | none 23. Suppose it is determined that a processor executes 30,000,000 instructions per second and instructions AVERAGE 1.6 references per instruction to memmory. Suppose a working set window size of 12,000,000 references is selected. What is the appropriate time window in seconds for computing working set sizes. 12 / (30 * 1.6) = 1/4 sec 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 was last referenced most distant in the past. 6 _1__ 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 26. 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^10 b. How many entries are there in a page table. 2^ 11 8 c. How much virtual memory can be accessed through a single page directory entry. 2^21 d. Suppose virtual address 0x123ABCDE is referenced. What is the value of the page table index. 6af 27. 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 28. 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.