The usage of some notation or terms may vary slightly across the computer science community; here we use the following definitions for this homework. TArrival(i) = Time when process i request for service arrives TResponse(i)= Delay between request for service and start of process i Turnaround(i) = Delay between request for service and completion of service for process i TExecution (i) = Time needed to perform computation for the process i Toverhead (i) = Time needed to dispatch or stop the process task by the scheduler, usually ignored Other processing Execution Time Overhead Process Response Time Turnaround Time Time Average waiting time = Sum of all non-execution time divided by the number of processes Throughput = Number of processes completed per unit of time Processor utilisation = Percentage of time that the processor is not idle Recall that the seven states model below is an extension to the five states model: New Suspended Ready Ready Running Blocked Suspended Blocked Further, recall that there are three levels of scheduling. List the level of scheduling of every applicable transition. For example, from New to Suspended Ready is the task of long-term Scheduling. How do we evaluate and compare the performance of the scheduling algorithms/policies? You may choose a utility or (expected utility), usually a quantified evaluation of the system (such as the average waiting time) as the major target for your study. Now, work out the expression for Average Waiting Time given the Turnaround(i), TExecution (i) of all processes and the number of processes. Assuming 0 overhead for now and considering the general scheduling algorithms: FCFS (First Come First Served), SPN (Shortest Process Next), RR (Round Robin) with quantum = 3, SRT (Shortest Remaining Time First); for the following process set: Process ID A B 0 2 3 Tantal 4 TExecution 7 3 1 10 5 Draw a diagram that explicitly illustrates the process that is running at each time step. Work out the average waiting time (AWT) for each scheduling algorithm, and determine the best and worst algorithms for this particular case. You can assume the oldest process has the highest priority if necessary. Notice that two algorithms perform exactly the same scheduling in question 3. Consider the following case for these two algorithms only, and repeat the analysis you have done for question 3 (still using the zero overhead assumption). Process ID TArrival TExecution A B 1 3 D E 10 5 Now you should consider overheads for all context switching. Assume an overhead of one time step, which is an exaggeration of reality of course (but it serves our purposes). Repeat question 3 for RR only (FCFS is done for you below); also work out the AWT for both RR and FCFS. How does the quantum of RR affect its AWT? Figure 3 Example FCFS To stress the problem of fairness, we define a new utility U-the sum of all squared consecutive waiting times: For example, if a process starts at 0, is blocked at 2, resumes at 4 and finishes at 5 then the U for the process is (4-2)=5. Explain why smaller U means better fairness; compare the FCFS and RR in question 1, which is a better algorithm in terms of having smaller U? Make sure to show the details of your work. Think of another kind of measure or utility that can be used to evaluate the fairness. Is it possible to define a utility that estimates both the fairness and the throughput at the same time? Now, repeat question 3 for the feedback algorithm. Use the following configuration: a. Two RR queues with quantum = 2 b. New processes join the queue with highest priority c. Each time a process is pre-empted, it will be downgraded and join the end of the next lower priority queue (except the lowest queue) d. Scheduler always dispatches the first process in the highest queue that is not empty Also work out the AWT and U. Comment on this policy: is it a good, poor, or moderately balanced approach? How would you change the configuration to improve the performance