COMS W4118: Operating Systems I Fall, 1999 Final Exam: December 22, 1999 DIRECTIONS This exam is closed book, calculator is permitted. You have 2 hours and 50 minutes to complete the exam. Complete the following six questions. The questions are all of equal weight. The order of the questions is random, so the difficulty may vary from question to question. Don't get stuck by insisting on doing them in exact order; as long as your answers are clearly labeled with the problem numbers, they can appear in any order in your exam book. Make sure you write your name and email address on the front cover of your exam book. You need not write a novel in order to get full credit. To avoid this problem, all explanations should be 20 words or less. Explanations in excess of 20 words will receive zero credit. Use diagrams when possible or necessary. 1. Suppose that a disk drive has 300 cylinders, numbered 0 to 299. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 15. The queue of pending requests, in FIFO order, is 86, 147, 291, 18, 95, 151, 12, 175, 30 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms? a. FCFS b. SSTF c. SCAN d. LOOK e. C-SCAN 2. Suppose that you have file system consisting only of inodes and data blocks. Each inode contains 10 entries, each of which is 4 bytes in size. a. Assuming that all entries in an inode point directly to data blocks and data blocks are 4096 bytes in size, what is the maximum file size allowed by this file system? b. Suppose that inodes now contain 10 entries, of which 7 point to direct blocks, 2 point to single indirect blocks, and 1 points to a double indirect block. Data blocks and indirect blocks are both 1024 bytes in size, and indirect block entries are each 4 bytes in size. What is the maximum file size allowed by this file system? c. Suppose that you have the same file system configuration as in part b and you are given a 100 MB disk on which the file system is stored. Assuming that the disk is formatted with a single inode table with 1024 entries, what is the maximum sized file that can be stored on this disk? d. Suppose that instead of inodes, a file allocation table is used, and each entry in the file allocation table is 4 bytes in size. Given a 100 MB disk on which the file system is stored and data blocks of size 1024 bytes, what is the maximum sized file that can be stored on this disk? e. What disadvantage is there, if any, to using a file allocation table instead of the inode organization used with the ext2 file system in Linux? 3. Suppose there are four processes, P1, P2, P3, and P4, with respective arrival times of 1 ms, 3 ms, 4 ms, and 5 ms, and processing requirements of 4 ms each. The processes are assigned priorities 1, 2, 3, and 4, respectively, with a higher number being higher priority. The processes are scheduled preemptively and scheduling overheads are considered negligible. a. What is the average completion time for these processes if the processes are scheduled using first come first serve? b. What is the average completion time for these processes if the processes are scheduled using round-robin scheduling, assuming a time quantum of 2 ms? Assume that processes are initially queued in FIFO order. c. Suppose each process needs to grab a spin lock A at the beginning of its execution and releases the lock at the end of its execution. What is the average completion time for these processes if the processes are scheduled using round-robin scheduling, assuming a time quantum of 2 ms? Assume that processes are initially queued in FIFO order. d. Suppose each process needs to grab a spin lock A at the beginning of its execution and releases the lock at the end of its execution. What is the average completion time for these processes if the processes are scheduled using priority scheduling? e. Suppose each process needs to grab a blocking semaphore A at the beginning of its execution and releases the lock at the end of its execution. What is the average completion time for these processes if the processes are scheduled using priority scheduling? Assume that FIFO queues are used for the semaphores. 4. Consider a system with 3 physical frames of memory that is given the following page memory reference sequence: 1, 2, 3, 4, 1, 2, 3, 4, 3, 2, 1, 3, 1, 3, 2 What is the number of page faults that would occur for each of the following page replacement algorithms? a. An optimal page replacement algorithm b. MRU c. LRU d. What can you say about the types of memory reference sequences when LRU does not work well? e. How can you combine LRU and MRU in a page replacement algorithm that results in fewer page faults than either MRU or LRU alone for the above memory reference sequence? 5. Consider a system with 64 MB of physical memory, 32-bit physical addresses, 32-bit virtual addresses, and 4 KB physical page frames. a. Using a single-level paging scheme, what is the maximum number of page table entries for this system? b. Using a two-level paging scheme with a 1024-entry outer-page table, what would be the page offset of the page of the page table accessed for the virtual address 00110000000100001110001000011100? c. Suppose a TLB is used with the two-level paging scheme described in part b, and the TLB has a 90% hit rate. If the TLB access time is 10 ns and memory access time is 100 ns, what is the effective memory access time of the system? d. If an inverted page table is used to translate virtual addresses to physical addresses, how large would it need to be? e. What disadvantage is there, if any, in using an inverted page table versus per process page tables? 6. Answer the following questions true or false: a. An operating system can be viewed as a "resource allocator" to control various I/O devices and user programs. b. The following instructions must be protected to ensure that a computer system operates correctly: change to monitor mode, read from monitor memory, write into monitor memory, and turn off timer interrupts. c. I/O instructions and turning interrupts on are not generally considered to be privileged instructions. d. Deadlock can be prevented in the dining philosophers problem by simply reducing the number of philosophers that are allowed to eat at the same time by one. e. On a uniprocessor system, the critical section problem can be solved simply by disabling interrupts while a shared variable is being modified. f. A thread is generally more lightweight than a process because threads have their own virtual address spaces while processes may have shared address spaces. g. A priority scheduler can be used to implement any other kind of scheduler, given an appropriate choice of priorities and the ability to change those priorities at any time. h. When using a text editor in UNIX, the characters that are typed are processed by the text editor application without any operating system activity other than processor scheduling. i. While LRU page replacement is more complicated that FIFO page replacement, LRU is generally used because it performs at least as well as FIFO for all possible memory reference strings. j. A deadlock cannot arise for a set of processes unless there is a circular wait condition.