CIS 657 Exam 2 Version 2 (Monday, 10/13/95) 1. 4 page frames, 8 virtual pages. Find C and F vectors for distance string : _ _ _ _ _ 3 1 2 3 2 3 1 4 4 4 2 4 2 3 5 6 1 2 (_ stands for inf.) Count the number of occurences to get C vector and add up the C vector from last to first to get the F vector : C1-8,_ = < 3, 5, 4, 4, 1, 1, 0, 0, 5> F1-8 = <20,15,11, 7, 6, 5, 5, 5> (F4 = 7) 2. The average file size is 288K, each page table entry takes 4 bytes. Should we prefer 1K, 2K or 4K to minimize the total overhead caused by the page table + internal fragmentation? Important : The average file size is 288K does not mean the file sizes don't vary. 288K - 1 byte (biggest internal fragmentation) and 288K + 1 byte (1 byte internal fragmentation) may be equally likely. On average, p/2 of the last page is unused independent of the average file size. Let's compare the cases : Page number of page table File page Internal Total size entries needed for file table size fragmentation overhead 1K 288K / 1K = 288 1152 bytes 1K/2 = 512 bytes 1664 bytes 2K 288K / 2K = 144 576 bytes 2K/2 = 1024 bytes 1660 bytes 4K 288K / 4K = 72 288 bytes 4K/2 = 2048 bytes 2336 bytes The 2K page size is optimal. Note : Here, we compared (se/p + p/2) of page 123 for the three cases. If we instead use the formula that gives its minima : p = sqrt(2 x 288K x 4) = sqrt(2^3 x 288 x 2^10) = sqrt(9 x 2^18) ==> p = 3 x 2^9 = 1.5K (optimal page size is 1.5K !) This does not mean that the overhead is the same for 1K and 2K; we still have to compare those two cases. 3. The variables x, y and z are in pages 5, 11 and 2 of the data segment, respectively. Show the data segment page references for : x = y; read y, write it to x. References 11 and 5. if (x < z) 5 and 2, or, 2 and 5. x = z; (executed only if x < z) 2 and 5. return x; 5. Hence, if initially y < z, then we reference 11, 5, 5, 2, 2, 5, 5; otherwise we reference 11, 5, 5, 2, 5. 4. Disk block size is 1K = 1024 bytes. Block numbers take 4 bytes, the file attributes take 24 bytes. Max file size (in KBs) for a file that uses a single i-node without any indirect blocks? Max file size for single and double indirect blocks used but triple indirect block not used (rounded up to MBs)? +------------+ | attributes | 24 bytes +------------+ --+ +------------+ | + . . . | | +------------+ > 1000 bytes +------------+ single indirect | ==> 1000/4 = 250 block numbers +------------+ double indirect | +------------+ triple indirect --+ Three of them indirect ==> 247 left Using the 247 direct block numbers of the i-node, the maximum file size we can address will be 247 disk blocks. ===> max file size = 247 K. ---------------------- The single indirect block will be a disk block of 1024 bytes, all disk block numbers (1024 / 4 = 256 disk block numbers). The double indirect block will point to 256 disk blocks with 256 disk block numbers each. ===> max file size = 247 + 256 + 256 x 256 blocks ===> max file size = 503 K + 64 M = 64.5 MB (actually, 9K less than 64.5 MB) 5. A file system consistency check revealed missing blocks, duplicate used and duplicate free blocks. If we decide that the free block list is corrupted, how can we reconstruct it? If we can reconstruct it, why do we keep it at all? Can all the mentioned problems in the file system be solved by this method? If not, which ones remain? We can construct the free block list from scratch by going through all the blocks of all the files in all the directories to form the used block list, inverse of which will give us the free block list. We can reconstruct the free block list, but we keep it up to date all the time because the process above is too slow to repeat each time a block allocation is requested. The one problem mentioned in the question which can't be solved is the duplicate used block. This problem is handled in the book by forming two copies of the duplicate used block, but this is not a solution. Actually, no solution exists. A single disk block can not keep two blocks from two separate files at the same time. Data is lost, and there is no way to recover it. Book explains a method not to cure the cancer but remove the organ before the disease spreads elsewhere. 6. ? T F T T F F T F F a. Quick fit memory management generally runs faster than the first fit. TRUE if you consider the speed of finding a hole for a request, FALSE if you include the overhead of finding neighboring holes to merge. b. New small requests might decrease the external fragmentation even if there is no release of memory in the meantime. TRUE. External fragmentations get allocated by requests. c. Page table size is directly proportional to page size. FALSE. For the same virtual address space, they are inversely proportional. d. One instruction might cause two page faults. TRUE. Even with the simplest instruction. If the instruction is past the end of the page and it is reading a memory location, one page fault for code and one for data can occur. e. The FIFO page replacement algorithm removes the oldest page even if it is being used very frequently. TRUE. Of the food items, it could remove bread or salt from the supermarket shelves to make space for the new leather jacket flavored crayons. f. Belady's anomaly could happen in optimal page replacement algorithm. FALSE. Optimal page replacement algorithm is a stack algorithm; all the virtual pages kept for 4 page frame memory will also be kept for 5. g. Inverted page tables are not so common because they generally take more memory compared to the conventional page tables. FALSE. Inverted page tables take much less space in the memory. h. Multilevel page tables are more memory efficient. TRUE. That's what they are for. i. Any two consecutive holes of the same size are buddies in a buddy system. FALSE. Consider a 4M buddy system. Allocate 1M each for processes A, B, C and D. Now release B and C. You get : |** A **|---1M--|---1M--|** D **|. The 1M holes can't be merged because they are not buddies. j. The second chance page replacement algorithm might loop indefinitely. FALSE. It loops at most once through the list of pages.