INTRODUCTION TO OPERATING SYSTEMS MIDTERM #1 ANSWERS By : Kanat BOLAZAR (bolazar@top) Last Changed : 10/17/95 ********* ** 1 ** ********* In the ready queue shown below, the first job is RUNNING where all others are READY; they will all run in the order shown. New jobs are added to the end of the queue (last item). I ignored the incoming job while evaluating the context switch. You might not, and that's fine. I put job 4 behind job 2 in the queue when it came. You might reverse the order, and that's OK. But it is not OK to use no queue, and it is not OK to run the incoming jobs the instant they come. time Jobs context ready J1 J2 J3 J4 switch queue 0 2 0.5 J1 <- J2. 2.5 2 0.5 J2 <- J1. 5.0 2 0.75 J1 <- J2 <- J3. 7.75 2 0.75 J2 <- J3 <- J1. 10.5 2 1 J3 - J1 - J2 - J4. 13.5 2 1 J1 - J2 - J4 - J3. 16.5 2 1 J2 - J4 - J3 - J1. 19.5 2 1 J4 - J3 - J1 - J2. 22.5 2 1 J3 - J1 - J2 - J4. 25.5 2 2 2 2 4 one J1-J2-J4-J3 loop. 37.5 2. 1 J1 - J2 - J4 - J3. 40.5 2 0.75 J2 - J4 - J3. 43.25 1. 0.75 J4 - J3 - J2. 45.0 2 0.5 J3 - J2. 47.5 2 0.5 J2 - J3. 50.0 2. 0.5 J3 - J2. 52.5 2 0.25 J2. 54.75 1. (0.25) J2. The context switching before the last line, when there is a single job in the system, is quite useless. Let it be. arrival departure turnaround Job 1 0 39.5 39.5 Job 2 1 55.75 54.75 Job 3 5 52.0 47.0 Job 4 10 44.25 34.25 ------------------------------------------- total : 191.5 average : 37.875 units ********* ** 2 ** ********* a. If the priorities are set such that short jobs get high priority, and the longer jobs get lower priority, then the methods are equivalent. b. i. If we allow multiple queues to be as small as a single queue, then a single first-come first-served queue can be our multiple queue. (Equivalently, we can have other queues which are never used.) ii.Or we can have as many queues as maximum number of allowed processes to exist at any given time, with incoming jobs put to the lowest priority queue available, jobs shifted to higher priority queues whenever higher priority queues become empty, and with a single process in each queue at any given time. c. If all processes are given the same priority, then we get first-come first-served scheduling. d. They can't be made equivalent. Round Robin Multiple Queues Priority |(question) |(b) | +-------------+ | +-----------------+ | | |(c) |(a) First-in-first-out Shortest Job First ********* ** 3 ** ********* Many students had problem seeing how the algorithm uses busy waiting in : while flag[1-i] do no-op; I suggest they go back to the Strict Alternation and make sure they understand it (busy waiting is done the same way, but this algorithm - as a whole - is *not* strict alternation). Recall that the solution can not make any assumptions about the speeds or the number of CPU's (rule 2, page 35). It should work for any order of execution. The two processes can run in the following order (the value of i is used instead of i for clarity) : Process 0 Process 1 flag[0] := true; ---------> flag[1] := true; ------------> -----> while flag[1] do no-op; ---> while flag[0] do no-op; At this point, both flag[0] = flag[1] = true. If this is the sequence of execution, both processes will loop forever at this point. Hence ("no process should have to wait forever to enter its critical section", rule 4, p35) this is not a solution to the critical section problem. ********* ** 4 ** ********* If we change the state from EATING to THINKING after we do test for two neighbors, these tests will never change the neighbor states to EATING. We might as well omit tests. This means that if I get HUNGRY and am waiting for one or both of the forks, I will block, and stay blocked forever. My neighbors will not wake me up even after they finish EATING. They can THINK again and EAT again ignoring my starvation. On the other hand, if I always get HUNGRY when the two forks are available (my neighbors are THINKING), I can EAT. In the case of 3 philosophers, as well as in the case of 100 philosophers, as time goes on, more and more philosophers will get blocked at HUNGRY. It may be that no two neighbors ever need the forks at the same time; then none will block. It may be that one after the other blocks, resulting in a single philosopher awake : i : 1 2 3 4 ... | T T T T T : THINKING |t T H T T H : temporarily HUNGRY |i T E T T (not blocked at all) |m H* E T T E : EATING |e H* T H T | H* T E T H* : HUNGRY, blocked forever | H* H* E T V H* H* T H H* H* T E H* H* H* E . . . until all philosophers are blocked at H other than the last one. ********* ** 5 ** ********* Two-level scheduling is needed when memory is too small to hold all the ready processes. Some of them is put into memory, and a choice is made from that set. From time to time, the set of in-core processes is adjusted. This algorithm is easy to implement and reasonably efficient, certainly a lot better than say, round robin without regard to whether a process was in memory or not. ********* ** 6 ** ********* We need a mutex to assure atomicity. Both signal and wait have to be atomic, hence they both look like : down(mutex); ... /* the critical section */ up(mutex); ... /* we can only block here */ Whatever we do inside must take a short time, so that we allow others to do signal and wait as well. We can not do down(S) in the critical region of the wait. This would cause a deadlock, because up(S) will be done in the critical region of the signal, after down(mutex). We need to read the values of the semaphores inside the critical region, and the only way to do this is : "keep a variable for each semaphore, and increment it each time you do an UP, and decrement it each time you do a DOWN (that won't block)". Every now and then a wait(S,R) will block because one/both of the semaphores is/are 0. We need to go to sleep and be woken up by the procedure that will release the resource; the signal procedure. A queue must be used to keep the information about the blocked wait operation, and a semaphore for each process can be used to block and unblock. In this case, we don't really need semaphores for each resource S, R, etc (if wait and signal are the only operations on them). The code that follows uses ID# for the current running process' no. The triplet is a record (a struct). I have used a mixture of C, Pascal and some pseudocode (bad programming example, but the question didn't ask that you program fully, only that you "explain in detail"). The array of semaphores, one for each process (initialize to 0's) : semaphore Process[MAX_PROCESS_NO]; test(S,R,procno) : if (S > 0) and (R > 0) { S--; R--; up(Process[procno]); return 1; } else return 0; wait(S,R) : down(mutex); if not test(S,R,ID#) enqueue( ); up(mutex); down(Process[ID#]); signal(S,R) : down(mutex); S++; R++; Foreach in the queue : if test(Si,Ri,procno_i) remove from the queue; } up(mutex); A single signal(R,T) might wake up both a wait(S,R) and a wait(T,Q). Signal has to wake up all available candidates, one after another. ---------------------------------------------------------------- Please email me all typos/errors. Last changed : 10/17/95 Kanat BOLAZAR (bolazar@top)