1. The following is a semaphore solution to the readers-writers problem:

    semaphore mutex = 1

    semaphore wrt = 1  

    int variable: readcount = 0

   0 Reader: P(mutex)
   1          readcount = readcount + 1
   2          if readcount == 1 then P(wrt)
   3        V(mutex)
   4          <read database>
   5        P(mutex)
   6          readcount = readcount – 1
   7          if readcount == 0 then V(wrt)
   8        V(mutex)

   
   9 Writer: P(wrt)
   10         <write database>
   11        V(wrt)

   Assuming the following situations:

   1)      If there are no writers and you have first Reader executing code at line #2 and a second Reader shows up, explain what will happen to the second Reader.

   2)      If you have one Writer accessing the database at line #10 and a Reader shows up, explain what will happen to the reader.

        3)      If you have 5 Readers reading the database at line #4, and a Writer shows up, what will happen to the Writer?  When will the Writer access the database?

        4)      The above solution can cause a starvation problem.  Point out how this situation is possible.

2. Round robin schedulers normally maintain a list of all runnable processes, with each process occurring exactly once in the list. What would happen if a process occurred twice in the list? Can you think of any reason for allowing this?
3. Most round robin schedulers use a fixed size quantum. Give an argument in favor of a small quantum. Now give an argument in favor of a large quantum.
4. Define the difference between preemptive and nonpreemptive scheduling. State why strict nonpreemptive scheduling is unlikely to be used in a computer center.
5. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

   

   The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

   a. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF,a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.

   b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

   c. What is the waiting time of each process for each of the scheduling algorithms in part a?

   d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

    
6. Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made.

   

   a. What is the average turnaround time for these processes with the FCFS scheduling algorithm?

   b. What is the average turnaround time for these processes with the SJF scheduling algorithm?

   c. The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling.

    

7. Is it possible to have a deadlock involving only one single process? Explain your answer.
8. Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.
9. Consider the following allocation state table:

1. Is the system in a safe state?    
2. Can a request(1,0,2) for P1 granted?  
3. Next, can request for (3,3,0) by P4 be granted?
4. Lastly, can request for (0,2,0) by P0 be granted?

10. In distributed systems, why is there a need for a unique timestamp?

11. To ensure mutual exclusion in distributed systems, there are two approaches: centralized and fully distributed?  Which approach you prefer and why?

12. What is a disadvantage of using total resource ordering for deadlock prevention in distributed systems?

13. To prevent starvation in preventing deadlock by breaking wait-for cycle, which scheme you prefer: wound-wait or wait-die? Justify your answer.

14. What is the bully algorithm is used for in distributed system?  How does it work?

15. Bully algorithm can have considerable overhead in exchanging messages.  The Ring algorithm minimizes this overhead.  Explain how.

16. What is a disadvantage of Ring algorithm over Bully algorithm?