Homework 1, Due Date: Oct 6th (Section 0201); Oct 7th (Section 0101 and Section 0301), IN CLASS (Within 5 minutes of class start time)

Assigned: 30 Sep. 2003
Note: Handin a typewritten or handwritten (should be legible to be eligible for grading) homework.

Answer the following questions. Note that the problem numbers refer to OSC, 6th Ed, XP Update Edition. The text of the questions are repeated below.

1. Problem 3.7 : What is the purpose of system calls?
   
2. Compare the layered and the micro-kernel approaches to system design - describe the relative advantages and disadvantages of each scheme.
   
3. Problem 4.5 What are the benefits and the determents of each of the following? Consider both the systems and programmers levels.
   1. Direct and Indirect Communication
   2. Symmetric and asymmetric communication
   3. Automatic and explicit buffering
   4. Send by copy and send by reference
   5. Fixed-size and variable-sized messages.
   
   
4. Problem 5.3 What are the two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?
   
5. Problem 5.7 Assume an operating system maps user-level threads to the kernel using the many-to-many model where the mapping is done through LWPs. Furthermore, the system allows the developers to create real-time threads. Is it necessary to bound a real-time thread to an LWP? Explain.
   
6. Problem 6.3 Consider the following set of processes, with the length of the CPU-Burst time given in milliseconds

   		Process         Burst 	  Time Priority
   
   		P1  		10 		 3
   		P2  		1   		 1
   		P3  		2 		 3
   		P4  		1  		 4
   		P5 		5  		 2
   
   

   
   The process are assumed to have arrived in the order P1,P2, P3, P4, P5, all at time 0.
   1. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a non-preemptive priority (a smaller priority number implies a higher priority), and RR (quantum=1) scheduling.
   2. What is the turnaround time of each process for each scheduling algorithm in part a?
   3. What is the waiting time of each process for each of the scheduling algorithms in part a?
   4. Which of the schedules in part a result in the minimal average waiting time (over all process)?
   
   
7. Problem 6.8 Many CPU-scheduling algorithms are parameterized. For example, the RR algorithm requires a parameter to indicate the time slice. Multilevel feedback queues require parameters to define the number of queues, the scheduling algorithm for each queue , the criteria used to move processes between each queues, and so on. These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all time sclies, and so on).One set of algorithms may include another (for example, the FCFS is the RR algorithm with an infinite time quantum). What (if any) relation holds between the following pairs of sets of algorithms?
   1. Priority and SJF
   2. Multilevel feedback queues and FCFS
   3. Priority and FCFS
   4. RR and SJF
   
   
8. Problem 7.4 The first known correct software solution to critical section problem for two process was developed by Dekker. The two processes, P0 and P1, share the following variables:

                 Boolean flag [2];   /* initially False */
                Int turn;
   

   
   The structure of process Pi (i = =0 or 1), with Pj (j= =0 or 1) being the other process, is

                            Do
        				{
   
   				   	Flag[i] = true;
   					
   					While (flag [j])
   					{
   					   if (turn = = j)
   					   {
   						flag [i] = false;
   						while ( turn = = j);
   						flag [i] = true;
   					    }
   					}
   
   
   					Critical Section
   
          
   					Turn = j;
   
   					Flag [i] = false;
   
   
   
   					Remainder section
   
   				}  While (1)
   
   
   

   
   Prove that the algorithm satisfies all the three requirements for the critical section problem.