This are very quick solutions I came up with. I do not guarantee they are correct, but they should be close. If you find possible errors, feel free to post to the newsgroup. Question 1: Here are the possible sequences: (x,y) a,f,b,c,d,e,g,h,i,j = (0,2) a,f,g,h,i,j,b,c,d,e = (2,3) f,a,b,c,d,e,g,h,i,j = (2,0) f,a,g,h,i,j,b,c,d,e = (2,1) a,b,c,d,e,f,g,h,i,j = (4,0) note, you can have cases like: f,g,h,i,a,j,b,c,d,e but they turn out to be redundant (the x,y pair has already been shown) Question 2: FIFO Time 0 5 10 15 20 #1 ********** = done at 5 #2 ****** = done at 8 #3 ************ = done at 14 #4 *** = done at 15.5 average run time = 5 + 7 + 12 + 12.5 = 36.5 /4 = 9 RR assuming that when a task is done, it is put at the end of the ready queue also, when a process arrives, it is put at the end of the queue, and in fact, is put after the one that is running during the time slot it arrived in. ok, I think this is right, but it might be off by a little.. it's hard to keep track of all this info.. Time 0 5 10 15 20 #1 *** * * * * * * * = done at 12.5 #2 * * * * * * = done at 10.5 #3 * * * * * * ****** = done at 15.5 #4 * * * = done at 9 average run time = (12.5 + 9.5 + 13.5 + 6)/4 = 10.4 STCF Time 0 5 10 15 20 #1 ********** = done at 5 #2 ****** = done at 9.5 #3 ************ = done at 15.5 #4 *** = done at 6.5 average run time = (5 + 8.5 + 13.5 + 3.5)/4 = 7.6 SRTCF Time 0 5 10 15 20 #1 ** ******** = done at 9.5 #2 ****** = done at 4 #3 ************ = done at 15.5 #4 *** = done at 5.5 average run time = (9.5 + 3 + 13.5 + 2.5)/4 = 7.1 SET Time 0 5 10 15 20 #1 ** * * * * * * * * = done at 14 #2 ** * * * * = done at 10 #3 ** * * * * * * * *** = done at 15.5 #4 ** * = done at 6 average run time = (14 + 9 + 13.5 + 6 )/4 = 10.6 Question 3: A program is merely a series of instructions.. A process is a program being run... it has a state (where it is currently executing, what the values of the memory locations are, and so on) Question 4: Total X currently held by all: 9 Total Y currently held by all: 15 Let's see how we could order the threads to proceed There is 1 unit of X left and 5 units of Y. We could schedule thread 3 since it will at most request 0 X and 4 Y. We could also schedule thread 4, since it will at most request 1 X and 0 Y. ==> we schedule thread 3, and we keep doing so until thread 3 is done. Now Total X held is 4 (thread 3 gave 5 back when it was done and Total Y held is 13 We could schedule thread 2 since it will at most request 6 X and 1 Y. We could also schedule thread 4 since it will at most request 1 X and 0 Y. ==> we schedule thread 2, and have it finish. Now Total X held is 4, and Total Y held is 7 We could schedule thread 4 since it will at most request 1 X and 0 Y. ==> we schedule thread 4. Now, the only thread left is thread 1, and we can have it run until completion. Therefore, therefore deadlock is not inevitable, since we have determined an ordering to run the processes ( 3, 2, 4, 1) which does not lead to deadlock. Question 5: Deadlock occurs when a set of threads cannot possibly make any further progress unless some external force is applied. This happens when each thread is blocked, trying to acquire some resource that another thread is currently holding (and that thread, in turn, is blocked because it is waiting for another resource held by a different thread). There will be a circular chain between which threads are trying to acquire which resources, and which threads own which resources. This occures when thread A holds lock 1, but is trying to acquire lock 2. Also, thread B holds lock 2, and is trying to acquire lock 1. Priority inversion occurs when a lower priority thread seems to be getting more CPU time than a higher priority thread. This happens because the higher priority thread is trying to acquire a resource which is currently held by a third, even lower priority, thread. Thread starvation occurs when a thread does not seem to be getting any CPU time for an indefinite amount of time. Note, thread starvation can cease without any intervention from the OS. An example is when we have one lower priority thread to run, but higher priority threads are constantly arriving. We will always process the higher ones, but since they are continuously arriving, we never get a chance to give CPU time to the lower priority thread Question 6: No, you cannot. The biggest reason why you cannot is that the table no longer points to all the locations we need to change. This is because the program, while it was executing, save pointers to the data structures or functions in new variables. Since these pointers are dependent where the data structures and functions are placed in the memory, they should be changed if the loader moves the entire program. However, since these variables are being created after the program begins, they are not included in the table used by the loader, and they will not be changed. For example, say we have the following: void sorter(char *) { } void main() { functionptr sortRoutine = sorter; /* save a pointer to the sorter function */ sorter(); (*sortRoutine)(); } because of how the program was compiled, the loader knows to change the address used by the first call to sorter in main. However, it does not know that the variable sortRoutine has kept a copy of where sorter is in memory. If sorter is moved, then sortRoutine will be invalid. Question 7: A. To give readers priority over the writers you simply have to always give readers the chance to run before any new writer do. This is done by signaling the okToRead condition variable when the writer is done working instead of signalling okToWrite (Readers will only queue up when a writer is working, so that's the only place we have to worry about getting them unqueued) Simply, we change the following code in Writer if (WW > 0) okToWrite->Signal(&lock) else if (WR > 0) okToRead->Broadcast(&lock) to this code: if (WR > 0) okToRead->Broadcast(&lock) else if (WW > 0) okToWrite->Signal(&lock) We also have to change code in the Reader code.. The condition in the while loop should be changed from ((AW + WW) > 0) to (AW > 0). B. It has no effect. On a lightly loaded system, we will have the case where readers and writers will come in one at a time, with a lot of time in between them. Our change only dictates what will happen when there are a lot of readers or writers waiting. Since this will not happen in the lightly loaded case, our change will not effect its behaviour. C. Writers will starve. When we have a ton of readers coming in while writers are waiting, the readers will always be run first. Therefore, the writers have to wait longer, and in essence, starve. D. If this is a banking system, then readers correspond to people who are just checking their balance (simply reading the information), where as the writers are the ones depositing or withdrawing money (writing new info to the database). So, people checking their balances will be processed very quickly, while people making deposits or withdrawals will take a long time.