Consider the following set of processes, with the length of the CPU-burst time giving in milliseconds:
Process Burst Time Priority ------------------------------- p_0 10 3 p_1 1 1 p_2 2 3 p_3 1 4 p_4 5 2The processes are assumed to have arrived in the order p_0, p_1, p_2, p_3, p_4, all at time 0.
- Draw four Gantt charts illustrating the execution of these processes using FCFS, SJN, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.
- What is the turnaround time of each process for each of the scheduling algorithms in part a?
- What is the waiting time of each process for each of the scheduling algorithms in part a?
- Which of the schedules in part a results in the minimal average waiting time (over all processes)?
Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at rate alpha; when it is running, its priority changes at a rate beta. All processes are given a priority of 0 when they enter the ready queue. The parameters alpha and beta can be set to give many different algorithms.
- What is the algorithm that results from beta > alpha > 0?
- What is the algorithm that results from alpha < beta < 0?
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 algorithms for each queue, the criteria used to move processes between queues, and so on.
These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all time slices, and so on). One set of algorithms may include another (for example, the FCFS algorithm is the RR algorithm with an infinite time quantum). What (if any) relation holds between the following pairs of sets of algorithms?
- Priority and SJN
- Multilevel feedback queues and FCFS
- Priority and FCFS
- RR and SJN
Consider the exponential average method of predicting future CPU bursts based on past history (pp. 131-132 of your text). For each of the process burst patterns shown in the attached figures:
- graph the predicted burst values for alpha close to zero and alpha close to 1.
- indicate what values of alpha (close to 0, close to 1) would best predict the behavior of that process.
- discuss your general conclusions about choosing the value of alpha.
Warning: The bulk of this problem is understanding what is called for. You should spend a lot of time dissecting the problem. The solution itself is not long. You might see this problem on the midterm.
You are to write high level pseudo-code for a short term scheduler / process scheduler which implements a round robin scheduling algorithm with time quantum TAU. This means that each process is scheduled to run for at most TAU units of time.
- Your code must cover the cases described below.
- You must use certain data structures and procedures that are pre-defined for you.
- Your scheduler must take care of moving processes among the process states ready, running, and blocked by moving them among the corresponding queues. You need not handle movement from new or to halted (zombie) states.
- You must decide how to handle the situation in which a process
has not used up its time quantum, but is interrupted because
I/O has finished.
- Here is the structure for your solution:
scheduler() { /* I am a Round Robin Scheduler */ if (called by a process that is finished) { /* current process is done */} else { if (called by I/O routines) { /* current process requests I/O */ } else { if (called by the I/O interrupt handler) { /* I/O done for process IO_DONE_PID */ } else { if (called by the timer interrupt handler) { /* current process has used up it's time quantum */ } }
- Here are the pre-defined data structures and procedures:
Running_Process - global variable which contains the PCB for the current running process. IO_Done_PID - global variable which contains the process id PID of the process whose I/O just completed. PCB - a structure for the process control block. It contains the following fields: PID - process ID Next_PCB - link to the next PCB in the queue PC - current program counter value for this process Other - you can define other fields if you need them Ready_Queue - linked list of PCBs of processes waiting for the CPU. Wait_Queue - linked list of PCBs of processes waiting for I/O to complete.
Append(pcb, queue) - appends pcb to tail of queue. Head(queue) - removes the first PCB in queue and returns it; if queue is empty it returns NIL. Select(queue,pid) - searches queue for the first process PCB whose PID matches pid. Context_Switch(pcb,TAU) - set the interval timer clock to TAU and start executing the process whose PCB is specified. NOTE: Context_Switch never returns. The PC (Program Counter) is loaded with the PC value stored in pcb->PC which causes the fetch/execute cycle to start where that process left off. You can define any other procedures or data structures you need, but these should be sufficient. If you end up defining too many more, you may lose points for an overly complex solution. - Miscellaneous Notes:
- When writing your pseudo-code solution, do not worry about details such as syntax, variable declarations, pointers, etc.
- Comment your pseudo-code with English sentences.
- Write a few sentences that describe how your scheduler handles the situation described above in which a process that has not used up its time quantum is interrupted by I/O. Write a sentence about the fairness of your approach.