CIS 657 (and CIS 400) FINAL EXAM -------------------------------- Date : 12/13/1995 Time : 2 hours. Open book, open notes. Everyone is to do the following six problems. Graduate students only (CIS 657 students) are to do problem number 7. 1. (10 points) Consider a two-dimensional array of size 100 by 100. Each element of A takes one memory word. The array is stored by rows (so the elements of the first row of A are stored first, followed by the elements of the second row, and so on). The first element of A is stored at address 200. Addresses 0 through 199 contain the code that uses array A. The computer has three page frames, and uses LRU algorithm for page replacement. For each of the following two loops, how many page faults are generated? Assume that page frame 1 has the code in it permanently, and the other two page frames are initially empty. One page is 2000 words. a. for j = 1 to 100 do for i = 1 to 100 do A[i,j] = 0; b. for i = 1 to 100 do for j = 1 to 100 do A[i,j] = 0; 2 (10 points) Consider a disk scheduler, which accepts requests from the CPU to read or write blocks from a disk. Requests are continually arriving. All the disk-scheduling disciplines, except First-Come-First-Served, are not truly fair (starvation may occur). a. Explain why this assertion is true. b. Describe a scheme to ensure fairness. c. Explain why fairness is an important goal in a time-sharing system. 3. (10 points) A system has 4 plotters and 5 CD ROM drives. Three processes, A, B, and C each have a maximum requirement of two plotters and three CD ROM drives. At a given time, A is only holding two CD ROM drives, B is holding one plotter and one CD ROM drive, and C is only holding two plotters. Currently, the system is in a safe state. Which of the following requests can be granted to keep the system in a safe state? a. A requests a plotter. b. C requests a CD ROM drive. c. B requests a plotter. d. B requests two CD ROM drives. Consider each request separately (not in succession). What can you say about C requesting another plotter? 4. (10 points) Consider a distributed system with two sites, A and B. Can A distinguish between the following : a. B goes down. b. The link between A and B goes down. c. B is extremely overloaded and the response time is 100 times longer than normal. What implication does your answer have for recovery in distributed systems? 5. (10 points) There are three processes, A, B, and C, competing for single resources of three types, X, Y, and Z. We are given a resource graph that contains illegal connections : ,--> C ----> Z / | | / | / | V / ,---- X <---- B <--' / | /^\ | | | V V / A ----> Y ----' Remove the illegal connections from the graph. If you have a choice to remove either of two connections, try to avoid deadlock. After the removal of the illegal connections, is there deadlock according to the graph? 6. (10 points) Correct the clocks according to Lamport's algorithm. Process 0 Process 1 Process 2 0 0 0 6 10 15 12 -----\ ,----- 20 30 18 <-----'\----> 30 ,---- 45 24 40 <------' 60 30 ,----- 50 75 36 <-----' 60 90 7. (10 points) GRADUATE STUDENTS ONLY : If the communication primitives in a client-server system are nonblocking, then a call to send will complete before the message has actually been sent. To reduce the overhead, some systems do not copy the data to the kernel, but transmit it directly from user space. For such a system, devise two ways in which the sender can be told that the transmission has been completed and the buffer can be reused.