CIS 657 (and CIS 400) FINAL EXAM (12/13/1995) QUESTIONS AND ANSWERS Note: This file may contain statements objectionable to some (few). Please don't read any further if you have Compulsive Objection Syndrome (aka "NO"). ------------------------- have a nice Christmas break -- Kanat --- <:):< --- I have prepared very long answers. For the students who only want to check the correctness of their answers, I have compiled a summary : 1. code+A (10,200 words) takes 6 pages, one permanently in the memory. The rest is read row by row in (b) causing 5 page faults, and column by column (reading from each row, hence each of six pages, for each column) in (a) causing 100x5 = 500 page faults. 2. (a) SSF might forget the two ends while satisfying requests at the middle, elevator can get stuck on a single cylinder's requests. (b) Get a group of requests. Satisfy them. Then get the next group. (c) Response time suffers. Critical processes get forgotten. 3. Grant only (c) and (d). C WILL NOT request another plotter. 4. A can't distinguish. This means, keep on checking B suspecting that (b) or (c) might have happened, after doing normal recovery assuming B is down. 5. Remove C-->B and X-->Y and either one of { X-->A , X-->C }. There is deadlock in either case. 6. Process 0 : 18, 24, 30, 36 become 21, 27, 33, 57. Process 1 : 40, 50, 60 become 46, 56, 66. 7. User defined interrupt, kernel poll function (procedure) called by user, kernel blocking wait-till-sent procedure called by user, a semaphore, an ACK reply from the receiver are a few of the options. --------------------------- LONG ANSWERS --------------------------- ********* ** 1 ** ********* 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; ANS : Array A starts at address 200, and it has 100x100 = 10,000 words. It is stored by rows; each row is 100 words. Then, the code and the array take 10,200 words, which is contained in six pages (2000 words each). First page : 200 words code + 1800 words (18 rows) of array A Second page, third page, fourth page, fifth page : 20 rows of A, each. Sixth page : 2 rows (200 words) of A. The first page is permanently in the memory together with the code. There are two page frames which are free, and we use LRU algorithm to page in and out the remaining five pages of the array. (a) The code in (a) accesses array A column by column. For each column, each row is accessed. The elements of any single column j is spread to six pages : A[1,j] - A[18,j] is in the first page ... A[99,j] and A[100,j] is in the sixth page The elements of the first page won't cause any page faults. The remaining five will cause a page fault each. For the next column, we will again have the same happening all over again, because the two page frames will be keeping the fifth and sixth pages which will have to be paged out for the second and third pages to be paged in. 5 page faults for each column x 100 columns = 500 page faults. (b) This code accesses array A row by row. The first 18 rows won't cause any page faults. After that, rows 19, 39, 59, 79 and 99 will each cause a page fault. 5 page faults. ********* ** 2 ** ********* 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. ANS : In the book, fairness is defined for CPU time sharing and a good general definition of starvation in resource sharing is given at the end of chapter 6. Fairness is not "whoever comes first gets the resource first". If fairness could be defined as such, only FCFS would be fair by definition. Fairness is how equally the users share the resource. (a) We have two other disk-scheduling algorithms : Shortest-seek-first and elevator algorithm. In the case of busy shortest seek first, cylinder requests of : 1, 45, 46, 44, 100, 46, 50, 40, 48, 1, 42, 51, 44, 48, 47, . . . would keep the head very busy at the middle cylinders, and the lower (1) and higher (100) ends might starve. The important thing to note here is that reading from disk is very slow compared to the calculations and memory reading/writing that each process has to do. If we satisfy the requests around the center much faster than usual, the requesting processes might each do another round of calculations and come back requesting another disk read or write around the same cylinder before the head gets a chance to service the cylinders far away. Hence, we have to delay some easy-to-serve requests sometimes and keep those processes blocked a little longer to serve the ones less remembered. The elevator algorithm does a better job (on being fair) than SSF. It can only get unfair if requests keep coming for the same cylinder : 1, 45, 45, 45, 45, 100, 50, 45, 45, 45, 45, 1, 45, 45, 45, . . . If the requests are read requests, we can get away using a cache. Not so if they are write requests. For example, think of a process which keeps a running counter on disk. If we have a few of these processes running in parallel and using the same cylinder on disk to keep the counter, the head will be held on a single cylinder and no request from any other cylinder can be granted. "But," you might say, "there is no way the disk scheduler can catch up with such a stream of disk requests, anyway. Everyone is doomed to starve, whatever algorithm is used." Not true. If we don't satisfy the counter processes so fast, they will not request the next disk write so soon. We have a limited number of processes, hence a limited number of maximum possible disk requests. The only problem is that where most processes go back to their work after the granting of their request, some of them never get satisfied, no matter how much you grant their requests. I would like to note that the situation that will cause starvation in elevator algorithm seems much less likely compared to the situation that will cause starvation in SSF. (b) An algorithm that takes requests in groups of 10 (or any other size) and services them in any manner before serving the next group, will be fair. Because no request will have to wait indefinitely (they won't starve). Another method is combining FCFS with the faster unfair algorithm : The algorithm can keep a counter that is incremented on granting each request. Each coming request will be timestamped. If the oldest request is too old (compare the counter with the timestamps), then forget SSF, elevator, or whatever algorithm you were using and start using FCFS. This can be viewed as emergency operation mode. FCFS won't run very fast compared to your usual algorithm, but in this method we keep time in terms of number of granted requests, so eventually we will be able to get out of FCFS and get back to our usual algorithm. (c) Starvation is caused by continuous stream of requests from others. If the system is not overcrowded, it will eventually end, and the user can continue. But in a time-sharing system, starvation that continues for as long as a few seconds may already be taking too long. This is because a time-sharing system usually has users running interactive tasks. In the case of using an editor, for example, no user wants to wait for a few seconds after each letter. Another problem is that a high priority kernel process might starve, and cause many other processes to starve consequently. ********* ** 3 ** ********* 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? ANS : Similar to fig. 6-10 : Resource 1 : plotter Processes : A, B, C Resource 2 : CD ROM Assigned : Still Needed : +---+---+---+ +---+---+---+ | A | 0 | 2 | | A | 2 | 1 | +---+---+---+ +---+---+---+ | B | 1 | 1 | | B | 1 | 2 | +---+---+---+ +---+---+---+ | C | 2 | 0 | | C | 0 | 3 | +---+---+---+ +---+---+---+ E = (4, 5) P = (3, 3) A = (1, 2) As we can see from above, available resources can barely satisfy process B. It can not satisfy A or C fully. Thus, the Banker's algorithm will show that requests coming from A and C leave the system in an unsafe state where the requests coming from B leave it safe. Hence, (a) and (b) can't be granted, where (c) and (d) can be granted. "What can you say about C requesting another plotter?" It WILL NOT request another plotter. The question clearly states that C needs a maximum of two plotters, and it is already holding two plotters. Even if we understood the question as "C declared a maximum need of 2 plotters and is now going beyond its limit", we can't consider such a request. Because if the declarations of maximum requirements are not observed, then we can't trust any conclusion the Banker's algorithm reaches. "Maximum requirement" and "still needed" tables would both be wrong, and we might already be in an unsafe state without knowing it. Some students tried to solve the problem using single resource Banker's algorithm. When we look at plotters by themselves, it seems that C needs no more, and it can finish and release its two plotters. But C also needs three CD ROM drives to finish, and might not release the plotters before it gets the CD ROM drives. You can not use single resource Banker's algorithm on a multiple resource problem. ********* ** 4 ** ********* 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? ANS : This question caused misunderstanding for many students. We have to look at the question from the viewpoint of designing a distributed OS, and trying to find the source of the problem, so as to solve it properly. The problem is that B didn't reply A within timeout. Is the cause (a), (b), or (c)? Can we find which one is the problem? My answer to this problem is "no" considering messages to be the only way to detect the problem. The implication is that after assuming B dead, and doing recovery accordingly, it might make sense to check B every now and then. For example, the recovery for client A - server B case will quite possibly include A requesting the same service from another server, which might be distant or slow compared to B. If B was temporarily busy as in (c), A can return to requesting services from B once B has lower load. Your answer might be different, and if you have adequately explained the context within which you considered the problem, your answer is correct, too, even if it is the reverse of my answer. I want to note that I understood (c) as "the kernel of B is so busy, B can't even return an ACK within normal time". A way to detect case (c) is to make A wait 100 times longer than usual. This answer, although I accepted as a correct answer, is merely theoretical, and totally impractical. The question doesn't say 1000 times or 10000 times, because 100 times longer is already way too long. A service that takes 45 seconds will not have a timeout of 75 minutes!!! An ACK that normally takes one second will not be waited for, for 100 seconds! (Would you ask your friend a question on the phone and wait for two minutes before you hear anything? I wouldn't. I would either "resend" my "message", or ask : "Are you alive?") ********* ** 5 ** ********* 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? ANS : The C-->B is illegal because a process can't hold a process, and X-->Y is illegal because a resource can't request a resource. Also, the single resource X seems to be held by both A and C at the same time. We have to remove one of the links X-->A and X-->C. According to the question, we should remove the link that avoids deadlock, if there is any. We get : C ---> Z C ---> Z /^\ | | | V V X <--- B X <--- B /^\ | /^\ | V | A ---> Y A ---> Y if we remove X-->A if we remove X-->C there is the B-X-C-Z loop there is the B-X-A-Y loop Both have a loop each, hence there is deadlock after the removal of the illegal connections. ********* ** 6 ** ********* 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 ANS : Process 0 Process 1 Process 2 0 0 0 6 10 15 12 -----\ ,----- 20 30 21 <-----'\----> 30 ,---- 45 27 46 <------' 60 33 ,----- 56 75 57 <-----' 66 90 Pi below denotes process i; clock i is the clock of process i. Message Correction P0 to P1 : 12-->30 No correction needed. Arrival time is bigger than the sending time. P1 to P0 : 20-->18 Increment clock0 by 3 ticks. becomes 20-->21 (changes all the clock0 values hereafter) P2 to P1 : 45-->40 Increment clock1 by 6 ticks. becomes 45-->46 P1 to P0 : 56-->39 Increment clock0 by 18 ticks. becomes 56-->57 ********* ** 7 ** ********* 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. ANS : According to the convention in the book, the user should be able to use the buffer after the message is sent by the kernel. There are a few ways to make the user know that the buffer is free : The user and the kernel can communicate through a semaphore. The kernel is one of the readers of the readers and writers to the buffer. The user can read from, but can't write to the buffer while the kernel is reading from it. The kernel can call a user defined interrupt after sending the message. This interrupt can, for example, deallocate the buffer space. The least the kernel can do is to supply a poll function that the user can call to find out whether or not the kernel is done yet. Or a wait-till-sent procedure (separate from nonblocking send procedure) can be supplied to change the mode to "blocking send". This procedure will not block at all if the message was already sent before the call. According to the alternative convention mentioned at the end of page 411, the buffer should be kept until an ACK (or REP) is sent back. If TA (try again) is sent back, the sender should resend the message (hence the buffer is still needed). In this case, the ACK (or REP) message to the process will notify the end of sending. Book mentions threads as a method cleaner than interrupts. The thread mentioned is not one that sends the message but one that does the cleanup after the message is sent by the kernel. --------------------------------------------------------------------------