COMS W4118: Operating Systems I Fall 2000 Final Exam: December 20, 2000 DIRECTIONS This exam is closed book, calculator is permitted. You have 2 hours and 50 minutes to complete the exam. Complete the following five 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. Consider a demand-paging system in which processes are performing sequential data accesses with the following time-measured utilizations: CPU utilization 20% Paging disk 98% Other I/O devices 10% For each of the following, indicate yes or no to say whether or not it will (or is likely to) improve CPU utilization: a. Install a faster CPU b. Install a bigger paging disk. c. Increase the degree of multiprogramming. d. Decrease the degree of multiprogramming. e. Install more main memory. f. Install a faster hard disk. g. Install multiple controllers with multiple hard disks and stripe the data across the disks. h. Add prepaging to the page-fetch algorithms. i. Increase the page size. j. Increase the I/O bus speed. 2. Consider a system with 3 physical frames of memory that is given the following page memory reference sequence: 1, 3, 6, 7, 1, 3, 6, 7, 1, 3, 6, 7 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. LRU c. 2nd chance clock replacement d. Does an optimal page replacement algorithm exist that does not require future knowledge for cyclical memory reference sequences such as shown above? If so, give a general algorithm. If not, explain why. 3. A file is stored on a LOOK scheduled disk system. The disk is 1 MB in size and has disk blocks of size 1 KB. The file is stored in sequential order in 4 disk blocks: 20, 500, 10, and 900. The last disk access was to block 51 and the directory entry for the file is stored in block 50. The first disk block is numbered block 0. A single block disk cache is present. a. Suppose a linked disk allocation method is used. What is the total seek distance for reading the entire file from beginning to end? b. Suppose a FAT allocation method is used in which the FAT is stored at the beginning of the disk and each FAT entry is 2 bytes. What is the total seek distance for appending and storing data in disk block 600 at the end of the file? c. If a C-SCAN disk scheduler is used in part b, what is the total seek distance? d. Suppose an indexed disk allocation method is used and the index block contains 1 byte direct entries. If the index is stored in block 55, what is the total seek distance for reading the entire file from beginning to end? e. Suppose an indexed disk allocation method is used and the index block contains 1 byte direct entries. If the disk contains 100 files, what is the maximum size file possible (in bytes)? 4. Consider a system with a 32-bit logical address space, a two-level paging scheme, 4 byte page table entries, 1 KB pages, and a 4 entry TLB. The page-table base register access time is 0 ns, TLB access time is 10 ns and memory access time is 100 ns. a. How many address bits are needed for the page offset? b. How much memory in bytes is required to store the outer page table entirely in main memory? c. The CPU has just been context-switched to a new process whose page tables are entirely stored in main memory. If there is a one-to-one mapping between logical and physical addresses, what is the average effective access time for sequentially accessing the following set of logical addresses: 2, 3, 4, 5, 5, 2010, 2022, 2009? d. If the TLB contained only 1 entry and the page-table base register access time was 10 ns, what would be the average effective access time for part c? e. Suppose the outer page table is stored in main memory starting at frame 0 and the inner page tables are stored in memory sequentially immediately after the outer page table. If logical address 80386 translates to physical address 1073742338, what are the values stored in the corresponding outer page table entry and inner page table entry? 5. Suppose there are four processes (P1 - P4) with respective arrival times of 0, 10, 20, and 40, priorities 1, 2, 3, and 4, and job times of 30, 20, 50, and 20 ms. These processes are scheduled from a single run queue to run on a dual-processor machine. Assume the context switch overhead is zero unless otherwise stated. a. Suppose the context switch overhead is 1 ms. What is the average turnaround time for scheduling the four processes using the following preemptive schedulers: priority (highest- priority-first), round-robin, or shortest-job-first? For round-robin, assume a 20 ms time quantum. b. The Linux SCHED_OTHER scheduler preemptively schedules processes in order of highest goodness. You are given the following code snippets: create_process(p) { ... p->counter = p->priority; add_to_front_runqueue(p); ... } schedule() { ... c = 0; for (p = front_runqueue; p <= end_runqueue; p++) { if (p->counter > c) c = p->counter; next = p; } if (!c) { for (all processes p) { p->counter = p->priority + (p->counter / 2); } } run(next); ... } When a process runs, its counter is decremented at each 10 ms timer interrupt and checked to determine if the scheduler should select another process to execute: do_timer_interrupt(p) { ... p->counter--; if (p->counter < 0) schedule(); ... } Draw the Gantt chart that would result if the four processes are scheduled using the SCHED_OTHER scheduler with the priorities given above. Assume these priorities are the internal priorities stored by Linux in the task_struct of the respective processes. c. What is the average waiting time for the processes scheduled in part b?