ECS 150: Practice Final Spring Quarter 2002 1. A program has a 32-bit virtual address space and a 4K page. The computer offers a 24-bit physical address space. How many entries are in each page table? 4K page -> 2^12 bytes per page -> 12-bit offset 32 bits - 12 bits = 20 bits for page numbers -> 2^20 pages There is 1 entry for each page, so 2^20 entries. How many frames are in main memory? 24 bits - 12 bits (offset) = 12 bits for frame numbers -> 2^12 frames Another program (on a different computer) has a 48-bit virtual address space, and 14 bits are used in each address for the page offset. The computer offers a 32-bit physical address space. In each page table entry, how many bits are needed for the frame number? Sorry! This question was a little too easy. 32 bits - 14 bits = 18 bits for frame number How many bits are in the page number portion of each virtual address? 48 bits - 14 bits = 34 bits for the page number (2^34 pages? That's a big program!) Next, consider the following virtual memory (by paging) system: * page size is 2K (2048) bytes * number of page table entries is 32 * number of page frames is 16 How many bits are there in each virtual address? page size of 2K -> 2^11 bytes -> 11-bit offset 32 page table entries -> 32 pages -> 2^5 pages -> 5 bits for page numbers. Thus, 11+5 = 16 bits in virtual addresses. How many bits are there in each physical address? 16 frames = 2^4 frames -> 4 bits for frame #. Thus, 11+4 = 15 bits in physical addresses. 2. Nondeterministic Output Consider the following program. sem s1 = 0; cobegin /* code for process P1 */ int j; for (j = 0; j < 4; j++) { if (j == 1 or j == 2) { V(s1); } printf("P1\n"); } // /* code for process P2 */ P(s1); printf("P2\n"); P(s1); printf("P2\n"); coend Below, please write two possible output sequences for this program. Note that both processes start at the same time. Many sequences are possible. But P1 must call V once before P2 prints "P2" for the 1st time. So P1 must print "P1" at least once before P2 ever prints "P2". Similarly, P1 must print "P1" at least twice before P2 prints the second "P2". But, notice that P1 has no P operations, and never has to block and wait for P2 to release it. So, in an extreme case, if the scheduler let P1 run 1st, and gave it a very long quantum, it could finish its whole For Loop, and print P1 4 times before P2 printed anything. 3. Consider Fig 5-14 on page 421. List each step that the OS must take to fetch the *first* disk block for "/usr/ast/mbox/". 1. Get the root inode from disk. (Note that the OS always knows the root inode #.) 2. Get the DBA for "/" . 3. Get that block from disk. 4. Get inode # for "usr". Result: 6 5. Get inode 6 from disk. 6. Get DBA for "usr" . Result: 132 7. Get "usr" (block 132) from disk. 8. Get inode # for "ast." Result: 26 9. Get inode 26 from disk. 10. Get DBA for "ast". Result: 406 11. Get "ast" (block 406) from disk. 12. Get inode # for mbox . Result: 60 13. Get inode 60 from disk. (Note: figure doesn't show this.) 14. Get DBA for 1st block of "mbox". 15. Get that block from disk. 4. Consider a 1-Gigabyte (1024^3 bytes) disk with a Minix file system. * How many 1K blocks are on the disk? 1048576 1024^3 bytes * (1 block/1024 bytes) = 1048576 blocks * If we assume an average file size of 4K when the disk is full, how many inodes are needed? (Note: for this calculation, pretend that the whole disk will be used for files. Thus, *temporarily* ignore the fact that some disk space will be needed for the inodes themselves, etc.) (1024^3 bytes) / (4K bytes) = 262144 Thus, a full disk will have 262144 files (if the ave. size is indeed 4K), and 262144 inodes are needed. Please note: I should have asked the following question, too: * How many blocks are needed for these inodes? (Note: each inode is 64 bytes, so there are 16 inodes per block.) (262144 inodes) * (1 block/16 inodes) = 16384 blocks * How many blocks are needed for the inode bit map? There is one bit in the inode bit map for every inode. (Each bit just indicates whether or not the corresponding inode is being used.) 262144 bits * (1 byte/8 bits) = 32768 bytes 32768 bytes * (1 block/1024 bytes) = 32 blocks for the inode bit map. (Note: if the number of inodes is *not* a multiple of 8192, then part of the last block in the inode bit map will be wasted. That's OK, though.) But here the # of inodes is a multiple of 8192. * Assume: * the boot block occupies 1 block; * the super block occupies 1 block. * Given all of the above, how many blocks can be used as data blocks? Let N = # of data blocks. For each data block, there is 1 bit in the "Data Block Bit Map". There are 8192 bits in every block, so: Let N/8192 = # of blocks in the Data Block Bit Map * Summary: total # of blocks on disk: 1048576 bytes boot block: 1 block super block: 1 block inodes: 16384 blocks inode bit map: 32 blocks data blocks: N blocks data block bit map: N/8192 blocks Thus, we have this equation: 1 + 1 + 16384 + 32 + N + N/8192 = 1048576 N (1 + 1/8192) = 1032158 N = 1032032.0195 We drop the fraction, and have N = 1032032. So we can have 1032032 data blocks. Data block bit map has N/8192 blocks: 125.98 blocks Here we have to go up to the next integer, so size of data block bit map is 126 blocks. Interesting note: 1032032/1048576 = 98.42 % So we are using over 98% of the disk for file storage, and less than 2% for "overhead" like inodes, etc. But this note still applies: (Note: here we are ignoring "single-indirect blocks" and "double-indirect" blocks. Just assume that later we will "steal" from the supply of data blocks if we need these indirect blocks.) 7. (10 points) Consider a paging system with 4 page frames and 8 pages. The page frames are initially empty. Assume the pages are accessed by a program in this order: 7 5 2 4 3 6 2 6 5 1 7 1 4 3 5 2 Assume the "Optimal" page replacement algorithm is used. page referenced: page fault? y/n result: pages in memory ---------------- --------------- ----------------------- 7 y 7 5 y 7 5 2 y 7 5 2 4 y 7 5 2 4 3 y 7 5 2 3 6 y 7 5 2 6 2 n 7 5 2 6 6 n 7 5 2 6 5 n 7 5 2 6 1 y 7 5 2 1 Please repeat this exercise, except now assume there are only 2 frames. ---------------- --------------- ----------------------- 7 y 7 5 y 7 5 2 y 2 5 4 y 2 4 3 y 2 3 6 y 2 6 2 n 2 6 6 n 2 6 5 y 2 5 1 y 1 5 6. Now please try the same problem, except use the "Second Chance" algorithm, and complete the table for all 16 references. (Below, when an R bit changes to 1, I've put an R above the page number). page referenced: page fault? y/n list: pages in memory ---------------- --------------- ----------------------- 7 y 7 5 y 7 5 2 y 7 5 2 4 y 7 5 2 4 3 y 5 2 4 3 6 y 2 4 3 6 R 2 n 2 4 3 6 R R 6 n 2 4 3 6 R 5 y 3 6 2 5 R 1 y 6 2 5 1 7 y 5 1 6 7 R 1 n 5 1 6 7 R 4 y 1 6 7 4 3 y 7 4 1 3 5 y 4 1 3 5 2 y 1 3 5 2 * * * * *