05 - Process Scheduling

Problem 1: Scheduler Differences

Briefly describe the difference between the long-term scheduler and short-term (CPU) scheduler.

Instructor Solution

The long-term scheduler (or job scheduler) determines which programs are admitted into the system for processing. It selects processes from a “job pool” on the disk and loads them into memory, thereby controlling the degree of multiprogramming (the number of processes in memory).

The short-term scheduler (or CPU scheduler) is much faster and more frequent. It selects which process, from those already residing in memory and in the “ready” state, should be executed next by the CPU. Its primary goal is to optimize system performance based on criteria like throughput and latency.

Problem 2: Context Switch Events

List 4 events that might occur to cause the kernel to context switch from one user process to another.

Instructor Solution

A kernel will trigger a context switch from one user process to another when:

• I/O Completion: The I/O request of a process in Waiting (Blocked) state completes and the process moves from the Blocked state to the Ready state.
• I/O Request: A process makes an I/O request for a slow resource (like reading from a disk), causing it to move from a Running to a Blocked state.
• Time-Slice Expiration: In preemptive multitasking, the CPU scheduler decides the process has used its allotted time (quantum) and forces a switch.
• New Process Arrival: A new process with a higher priority arrives and the OS decides to stop the currently executing process and schedule the newly arrived process.
• Process Termination: The current process finishes its execution or crashes, requiring the kernel to select a new process to run.

Problem 3: Preemptive vs. Non-Preemptive Scheduling

What’s the difference between preemptive and non-preemptive scheduling? Briefly explain. Which one is more suitable for a timesharing system?

Instructor Solution

In non-preemptive scheduling, a process keeps the CPU until it either terminates or voluntarily switches to a waiting state (e.g., for I/O). The kernel cannot force it to stop. In preemptive scheduling, the kernel can interrupt a running process at any time to give the CPU to another process, usually based on a timer interrupt or the completion of an I/O request for process with a higher priority.

Preemptive scheduling is more suitable for a timesharing system. This is because timesharing requires the OS to rapidly cycle through multiple users/processes to ensure that everyone receives a responsive experience, which is only possible if the OS can force processes to yield the CPU after their time slice (quantum) expires.

Problem 4: Context Switch State Preservation

What state is saved on a context switch between threads of the same process?

Instructor Solution

When the kernel performs a context switch between threads of the same process, it must save the Thread Context, which consists of:

• Program Counter (PC): The memory address of the next instruction to execute.
• CPU Registers: The current state of general-purpose and floating-point registers.
• Stack Pointer (SP): The location of the thread’s private stack (containing local variables and function calls).

Crucially, because threads share the same address space, the kernel does not need to save or reload memory management information like page tables or the heap.

Problem 5: Round Robin Time Quantum

Selecting a proper time quantum is important in round robin scheduling. What happens if the quantum is too big? What happens if it is too small? Briefly explain.

Instructor Solution

In Round Robin scheduling, the time quantum determines the system’s balance between efficiency and responsiveness:

• If the quantum is too big: The algorithm behaves like First-Come, First-Served (FCFS). Long processes will monopolize the CPU, causing “convoy effects” where short, interactive tasks must wait a long time, leading to poor responsiveness in a multi-user or UI-driven system.
• If the quantum is too small: The system suffers from excessive overhead. Because the CPU spends a higher percentage of its time performing context switches (saving and loading process states) rather than executing actual instructions, the overall system throughput drops significantly.

Problem 6: Starvation in Scheduling

What’s starvation as it applies to process scheduling? In which scheduling discipline is it more likely to occur? Give an example.

Instructor Solution

Starvation occurs when a process is perpetually denied CPU time because higher-priority processes are constantly being scheduled ahead of it. The process remains in the “Ready” state indefinitely, even though it is technically capable of running. It is most likely to occur in Priority Scheduling (specifically Fixed-Priority) and Shortest Job First (SJF).

Example: In a system that always executes the shortest task first, a very long process might never run if new, short processes continue to arrive every few seconds. The long process “starves” while the CPU handles a never-ending stream of quick tasks or tasks with higher priority.

Problem 7: Round Robin for Batch Jobs

A friend of yours is to design an OS that would run batch jobs, and s/he decides to employ Round Robin Scheduling algorithm. Is your friend making a good choice. Why or why not?

Instructor Solution

No, Round Robin is generally a poor choice for a pure batch system. Batch jobs are typically long-running, non-interactive tasks where the primary goal is maximum throughput and efficiency. Round Robin introduces frequent context-switching overhead and interrupts long-running processes unnecessarily. For batch processing, First-Come, First-Served (FCFS) or Shortest Job First (SJF) are better because they minimize overhead and complete individual jobs faster.

Problem 8: Ready to Waiting State Transition

Is it possible for a process to move from the Ready state to the Waiting (blocked) state? Why or why not? Briefly justify your answer.

Instructor Solution

No, a process cannot move directly from the Ready state to the Waiting (Blocked) state. Justification: A process only enters the Waiting state when it requests a resource (like an I/O operation) that isn’t immediately available. To make such a request, the process must execute a system call, which requires the CPU. Since a process in the Ready state is not currently executing on the CPU, it cannot perform the actions necessary to block itself. It must first be scheduled to the Running state.

Problem 9: Round-Robin Queue Placement

In Round-Robin scheduling, new processes are placed at the end of the queue, rather than at the beginning. Suggest a reason for this.

Instructor Solution

This design ensures Fairness and prevents Starvation. By placing new processes at the end of the queue, the system follows a First-In-First-Out (FIFO) logic that guarantees every process already in the “Ready” state gets its allotted time slice before a newcomer can “cut the line.” If new processes were placed at the beginning, a constant stream of incoming tasks could indefinitely postpone the execution of existing ones leading to starvation.

Problem 10: Round-Robin Process Bias

Explain why Round-Robin scheduling tends to favor CPU bound processes over I/O bound ones.

Instructor Solution

Round-Robin favors CPU-bound processes because they typically use their entire time quantum, allowing them to maximize their CPU occupancy and stay at the front of the scheduler’s mind once their turn returns. I/O-bound processes, conversely, often execute for only a fraction of their quantum before blocking for I/O. When they finish their I/O and return to the Ready queue, they are placed at the back of the line, effectively “losing” the remainder of their unused time. This results in I/O-bound processes getting significantly less total CPU time relative to their needs compared to CPU-heavy tasks.

Problem 11: CPU Scheduling Quanta

CPU scheduling quanta have remained about the same over the past 20 years, but processors are now over 1,000 times faster. Why has CPU scheduling quanta NOT changed?

Instructor Solution

The reason CPU scheduling quanta have remained largely unchanged (typically between 10ms and 100ms) despite processors becoming 1,000 times faster is that the quantum is determined by human perception, not processor speed. A quantum is designed to be short enough to create the illusion of concurrency for a human user—making the system feel “responsive”—but long enough so that the context switch overhead (the time spent saving/loading process states) remains a negligible fraction of the total execution time. While a modern CPU can execute many more instructions within that 100ms window than a CPU from 20 years ago, reducing the quantum further would:

1. Not improve the user experience, as humans cannot perceive sub-millisecond responsiveness.
2. Increase overhead, because the time required to perform a context switch (governed by memory and bus speeds) has not decreased as dramatically as raw CPU calculation speed.

Problem 12: Shortest Job First

Briefly explain how the shortest job first scheduling works.

Instructor Solution

Shortest Job First (SJF) scheduling selects the process with the smallest next CPU burst length from the Ready Queue to execute next. If two processes have the same burst length, First-Come, First-Served (FCFS) is typically used to break the tie. SJF is mathematically optimal for minimizing the average waiting time for a given set of processes because it moves short jobs to the front, clearing them out of the system quickly. There are two versions:

1. Non-preemptive: Once a process starts, it holds the CPU until it finishes its burst.
2. Preemptive (Shortest Remaining Time First): If a new process arrives with a shorter burst than the remaining time of the current process, the CPU is switched to the new process

Problem 13: Multi-level Feedback Queuing

Briefly explain multi-level feedback queuing scheduling algorithm.

Instructor Solution

Multilevel Feedback Queue (MLFQ) scheduling uses multiple queues with different priority levels to categorize processes based on their CPU-burst behavior. New processes enter the highest-priority queue and are granted a short time quantum. If a process uses its entire quantum (CPU-bound), it is demoted to a lower-priority queue with a longer quantum. If a process blocks for I/O (I/O-bound), it stays at or moves to a higher-priority queue. This dynamically separates interactive tasks from background batch jobs, optimizing both responsiveness and throughput.

Problem 14: Optimal Scheduling for Maximum Throughput

Consider a set of “n” tasks with known burst times to be run on a uniprocessor machine. Which scheduling algorithm will result in the maximum throughput, i.e., minimum average turnaround time. Justify your answer.

Instructor Solution

The algorithm that results in the minimum average turnaround time (and thus high throughput) is Shortest Job First (SJF). Average turnaround time is minimized when the shortest tasks are completed first. By scheduling the smallest burst time at the earliest possible moment, we ensure that the waiting time for all subsequent processes is kept to a minimum. Mathematically, this moves the “waiting” cost of long jobs to the end of the schedule, preventing them from delaying a large number of smaller tasks.

Problem 15: SRTF and Starvation

True/False: Shortest Remaining Time First scheduling may cause starvation. Justify your answer.

Instructor Solution

True. Shortest Remaining Time First (SRTF) is the preemptive version of SJF. If a steady stream of new processes with very short burst times keeps arriving, a process with a long burst time will be constantly preempted or bypassed. It will remain in the Ready queue indefinitely, unable to finish its execution, which is the definition of starvation.

Problem 16: Preemptive Priority and Starvation

True/False: Preemptive Priority scheduling may cause starvation. Justify your answer.

Instructor Solution

True. In Preemptive Priority scheduling, the kernel always grants the CPU to the process with the highest priority. If the system is constantly flooded with high-priority tasks, a low-priority process will be repeatedly preempted or bypassed. It may sit in the Ready queue indefinitely, never receiving enough CPU time to complete.

Problem 17: Round Robin vs. FCFS Response Time

True/False: Round Robin scheduling is better than FCFS in terms of response time. Justify your answer.

Instructor Solution

True. Round Robin is designed specifically to improve response time by limiting how long any single process can hold the CPU. In FCFS, a short process can be stuck behind a very long one (the “convoy effect”), leading to long delays. Round Robin ensures that every process gets a turn within a fixed time window, providing much faster initial feedback to users.

Problem 18: FCFS Gantt Chart with 5 Processes

Consider the following 5 processes in a system.

Process	Arrival Time	Burst Time
P1	4	5
P2	6	4
P3	0	3
P4	6	2
P5	5	4

Draw a Gantt chart illustrating the execution of these processes using FCFS. Compute the average waiting time and average turnaround time. What’s the CPU utilization?

Instructor Solution

Gantt Chart:

	P3	Idle	P1	P5	P2	P4
0	3	4	9	13	17	19

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	4	5	9	5	0
P2	6	4	17	11	7
P3	0	3	3	3	0
P4	6	2	19	13	11
P5	5	4	13	8	4

Average Waiting Time = (0 + 7 + 0 + 11 + 4) / 5 = 4.4

Average Turnaround Time = (5 + 11 + 3 + 13 + 8) / 5 = 8

CPU Utilization =

Problem 19: FCFS with Overhead

Consider the following 6 processes in a system.

Process	Arrival Time	Burst Time
P1	0	3
P2	1	2
P3	2	1
P4	3	4
P5	4	5
P6	5	2

(a) Draw a Gantt chart illustrating the execution of these processes using FCFS. Compute the average waiting time and average turnaround time for each case.

Instructor Solution

Gantt Chart:

	P1	P2	P3	P4	P5	P6
0	3	5	6	10	15	17

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	3	3	3	0
P2	1	2	5	4	2
P3	2	1	6	4	3
P4	3	4	10	7	3
P5	4	5	15	11	6
P6	5	2	17	12	10

Average Waiting Time = (0 + 2 + 3 + 3 + 6 + 10) / 6 = 4

Average Turnaround Time = (3 + 4 + 4 + 7 + 11 + 12) / 6 = 6.83

(b) Now assume that there is 1 unit of overhead when scheduling a process. Compute the efficiency of the scheduling algorithm; that is, the percentage of time where the CPU is doing useful work as opposed to doing context switching.

Instructor Solution

With 1 unit of scheduling overhead between each process transition, there will be 5 units of scheduling overhead total (between P1→P2, P2→P3, P3→P4, P4→P5, P5→P6). Total time = 17 + 5 = 22.

CPU Efficiency = (17 / 22) × 100 = 77.27%

The CPU is doing useful work 77.27% of the time.

Problem 20: Preemptive SRTF with 4 Processes

Consider the following 4 processes in a system.

Process	Arrival Time	Burst Time
P1	0	12
P2	2	4
P3	3	6
P4	8	1

Draw a Gantt chart illustrating the execution of these processes using preemptive shortest remaining time first algorithm. Compute the average waiting time and average turnaround time.

Instructor Solution

Gantt Chart:

	P1	P2	P3	P1	P3
0	2	6	8	17	23

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	12	17	17	5
P2	2	4	6	4	0
P3	3	6	23	20	14
P4	8	1	9	1	0

Average Waiting Time = (5 + 0 + 14 + 0) / 4 = 4.75

Average Turnaround Time = (17 + 4 + 20 + 1) / 4 = 10.5

Problem 21: Preemptive SRTF with Different Arrivals

Consider the following 4 processes in a system.

Process	Arrival Time	Burst Time
P1	0	10
P2	3	6
P3	7	1
P4	8	3

Draw a Gantt chart illustrating the execution of these processes using preemptive shortest remaining time first algorithm. Compute the average waiting time and average turnaround time.

Instructor Solution

Gantt Chart:

	P1	P2	P3	P2	P4	P1
0	3	3	7 8	3 1	0 14	1 20

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	10	20	20	10
P2	3	6	10	7	1
P3	7	1	8	1	0
P4	8	3	14	6	3

Average Waiting Time = (10+1+0+3) / 4 = 3.5

Average Turnaround Time = (20+7+1+6) / 4 = 8.5

Problem 22: Priority Scheduling Non-preemptive vs. Preemptive

Consider the following 5 processes in a system. Assume that lower values indicate higher priority.

Process	Arrival Time	Burst Time	Priority
P1	0	11	2
P2	5	28	0
P3	12	2	3
P4	2	10	1
P5	9	16	4

(a) Draw the Gantt chart if we employ non-preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround
P1	0	11	11	11
P2	5	28	39	34
P3	12	2	49	37
P4	2	10	51	49
P5	9	16	67	58

(b) Draw the Gantt chart if we employ preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround
P1	0	11	49	49
P2	5	28	33	27
P3	12	2	51	39
P4	2	10	40	38
P5	9	16	67	58

Problem 23: Priority Scheduling with Higher Priority Values

Consider the following 5 processes in a system. Assume that higher values indicate higher priority.

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

(a) Draw the Gantt chart if we employ non-preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround
P1	0	4	4	4
P2	1	3	15	14
P3	2	1	12	10
P4	3	5	9	6
P5	4	2	11	7

(b) Draw the Gantt chart if we employ preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround
P1	0	4	15	15
P2	1	3	12	11
P3	2	1	3	1
P4	3	5	8	5
P5	4	2	10	6

Problem 24: Round Robin with Quantum 2

Consider the following 5 processes in a system.

Process	Arrival Time	Burst Time
P1	0	5
P2	1	3
P3	2	1
P4	3	2
P5	4	3

Draw a Gantt chart illustrating the execution of these processes using round robin scheduling with a quantum of 2. Compute the average waiting time and average turnaround time. Note: At any given time, a newly arriving process is put to the back of the ready queue before the executing process is preempted. That is, the preempted process is always the last process in the ready queue.

Instructor Solution

Gantt Chart:

	P1	P2	P3	P1	P4	P5	P2	P1	P5
0	2	2	4	5	7	9	1	1	1

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	5	13	13	8
P2	1	3	12	11	8
P3	2	1	5	3	2
P4	3	2	9	6	4
P5	4	3	14	10	7

Average Waiting Time = (8+8+2+4+7) / 5 = 5.8

Average Turnaround Time = (13+11+3+6+10) / 5 = 8.6

Problem 25: FCFS vs. Round Robin

Consider the following 3 processes in a system.

Process	Arrival Time	Burst Time
P1	0	5
P2	1	7
P3	3	4

Draw a Gantt chart illustrating the execution of these processes using FCFS and round robin scheduling with a quantum of 2. Compute the average waiting time and average turnaround time.

(a) FCFS

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	5	5	5	0
P2	1	7	12	11	4
P3	3	4	16	13	9

Average Waiting Time = (0+4+9) / 3 = 4.33

Average Turnaround Time = (5+11+13) / 3 = 9.66

(b) Round Robin with quantum of 2

Instructor Solution

Process Metrics:

Process	Arrival Time	Burst Time	Finish Time	Turnaround	Waiting Time
P1	0	5	11	11	6
P2	1	7	16	15	8
P3	3	4	13	10	6

Average Waiting Time = (6+8+6) / 3 = 6.66

Average Turnaround Time = (11+15+10) / 3 = 12

Problem 26: Threading vs. Single Process

Consider the following function named “Work”, which performs I/O for 1 time unit and then performs computation for 1 time unit within a loop.

void Work(int numOfIterations){
  for (int i=0; i < numOfIterations; i++){
    DoIO();        // I/O takes 1 time unit
    Compute();     // Computation takes 1 time unit
  } //end-for
} //end-Work

main1(int argc, char *argv[]){
  Work(10); // Do the work in a single-threaded process
} //end-main

main2(int argc, char *argv[]){
  CreateThread(Work(5)); // Create a thread to run Work with numOfIterations = 5
  CreateThread(Work(5)); // Create a thread to run Work with numOfIterations = 5
  wait_until_both_threads_are_done();
} //end-main

(a) Assume that the OS does NOT support threads. So the programmer designs its main function to be single-threaded and codes main1() shown above. Assuming that this is the only process in the system and the machine has 1 CPU, how long does the program take to finish? Answer the same question when the machine has 2 CPUs.

Instructor Solution

Time	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
CPU		T1		T1		T1		T1		T1		T1		T1		T1		T1		T1
I/O	T1		T1		T1		T1		T1		T1		T1		T1		T1		T1

It takes 20 units of time for the process (T1) to finish executing. If we had 2 CPUs, T1 would still have taken 20 units of time because the second CPU would have to stay idle as there is only one thread to execute in the system.

(b) Assume now that the OS supports kernel-level threads. So the programmer designs its main function to be multi-threaded and codes main2() shown above. Assuming that this is the only process in the system and the machine has 1 CPU, how long does the program take to finish? Answer the same question when the machine has 2 CPUs. Assume that the threads can NOT perform I/O in parallel.

Instructor Solution

Time	1	2	3	4	5	6	7	8	9	10	11
CPU		T1	T2	T1	T2	T1	T2	T1	T2	T1	T2
I/O	T1	T2	T1	T2	T1	T2	T1	T2	T1	T2

T1 finishes at time 10 and T2 finishes at time 11. So, the program finishes at time 11.

If we have two CPUs, we can theoretically schedule both T1 and T2 in parallel, but because both T1 and T2 are using the same I/O device and I/O can NOT be performed in parallel, we will get the same schedule and the program will still finish at time 11. Notice that one the CPUs will still be idle as at any point in time, only one of the threads is ready to execute while the other is doing I/O.

Problem 27: Kernel Threads FCFS

Consider the following two threads T1 and T2 that belong to the same process P. Assume T1 is created first, followed by T2. Further assume that there is a single I/O device, which means that parallel I/O is NOT possible.

T1	T2
Compute(5)	Compute(3)
I/O(3)	I/O(6)
Compute(5)	Compute(1)
I/O(3)	I/O(5)
Compute(2)	Compute(4)

Assume that threads T1 and T2 are implemented as kernel threads. Draw the Gantt chart for First Come First Served (FCFS) scheduling. Compute the turnaround time for T1 and T2. Also compute the CPU utilization.

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
T1	0	19	19
T2	0	26	26

CPU Utilization:

Problem 28: Process CPU/I/O Scheduling

Two processes A and B execute the program given below. That is, each process performs computation for 3 units of time and performs I/O for 2 units of time within a loop.

main(int argc, char *argv[]){
  for (int i=0; i < 2; i++){
    Compute(); // Computation takes 3 time units
    DoIO();    // I/O takes 2 time units
  } //end-for
} //end-main

Assume that both processes are ready at time 0. Assume a single CPU and one I/O device. Assume that I/O can NOT be performed in parallel. Show the Gantt chart for the processes and compute the CPU utilization, and average turnaround time under:

(a) FIFO Scheduling algorithm.

Instructor Solution

Time	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
CPU	A	A	A	B	B	B	A	A	A	B	B	B
I/O				A	A		B	B		A	A		B	B

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
A	0	11	11
B	0	14	14

CPU Utilization: $\frac{12}{14} \times 100 = 85.71%

(b) Round-robin scheduling algorithm with a time quanta of 1 unit.

Instructor Solution

Time	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
CPU	A	B	A	B	A	B		A	A	B	A	B	B
I/O						A	A	B	B			A	A	B	B

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
A	0	13	13
B	0	15	15

CPU Utilization: $\frac{12}{15} \times 100 = 80%

Problem 29: Exploiting Scheduling Policies

Given a scheduling strategy, you can find a way to exploit the policy to your advantage and detriment other users. For each scheduling policy below, describe how you can exploit the scheduling policy to your advantage. For all cases, assume we are using a multi-level feedback queue that does round-robin scheduling within each priority level.

(a) Policy 1: Any job that uses an entire scheduling quantum is dropped to the next lowest priority level. The idea of this policy is to penalize compute-bound jobs.

Instructor Solution

The idea is to use the whole quanta except an epsilon time unit and call Yield() to give up the CPU. This way your priority will never decrease.

(b) Policy 2: Any process that performs an I/O operation during its scheduling quantum is moved up to the next highest priority level. The idea is to award I/O bound processes.

Instructor Solution

The idea is to make an I/O such as printing a char on the screen within a time quantum. This will increase your priority and you will be scheduled more often.

Problem 30: Priority Scheduling with 4 Processes

Consider the following 4 processes in a system. Assume that lower values indicate higher priority.

Process	Arrival Time	Burst Time	Priority
P1	0	5	4
P2	2	3	3
P3	4	5	2
P4	11	2	1

(a) Draw the Gantt chart if we employ non-preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	5	5
P2	2	13	11
P3	4	10	6
P4	11	15	4

(b) Draw the Gantt chart if we employ preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	15	15
P2	2	10	8
P3	4	9	5
P4	11	13	2

Problem 31: Priority Scheduling with 5 Processes

Consider the following 5 processes in a system. Assume that lower values indicate higher priority.

Process	Arrival Time	Burst Time	Priority
P1	0	6	4
P2	2	6	3
P3	4	3	2
P4	9	3	1
P5	13	3	5

(a) Draw the Gantt chart if we employ non-preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	6	6
P2	2	18	16
P3	4	9	5
P4	9	12	3
P5	13	21	8

(b) Draw the Gantt chart if we employ preemptive priority scheduling. Compute the turnaround time for each process.

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	18	18
P2	2	14	12
P3	4	7	3
P4	9	12	3
P5	13	21	8

Problem 32: Multiple Scheduling Algorithms Comparison

Consider the following 5 processes in a system.

Process	Arrival Time	Burst Time
P1	0	3
P2	1	5
P3	3	2
P4	9	5
P5	12	5

Draw 4 Gantt charts illustrating the execution of these processes using FCFS, SJF, and a RR (quantum=1) scheduling. Compute the average turnaround time for each case. Note: At any given time, a newly arriving process is put to the back of the ready queue before the executing process is preempted. That is, the preempted process is always the last process in the ready queue.

(a) FCFS

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	3	3
P2	1	8	7
P3	3	10	7
P4	9	15	6
P5	12	20	8

Average Turnaround Time = (3+7+7+6+8) / 5 = 6.2

(b) SJF

Instructor Solution

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	3	3
P2	1	10	9
P3	3	5	2
P4	9	15	6
P5	12	20	8

Average Turnaround Time = (3+9+2+6+8) / 5 = 5.6

(c) RR with quantum = 1

Instructor Solution

Time	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
CPU	P1	P2	P1	P2	P3	P1	P2	P3	P2	P4	P2	P4	P5	P4	P5	P4	P5	P4	P5	P5

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	6	6
P2	1	11	10
P3	3	8	5
P4	9	18	9
P5	12	20	8

Average Turnaround Time = (6+10+5+9+8) / 5 = 7.6

Problem 33: SJF, Priority, and RR Comparison

Consider the following set of processes with the given CPU burst times and priorities.

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

The processes have arrived in order from P1 to P5 all at time 0. Draw 4 Gantt charts illustrating the execution of these processes using SJF, priority (a smaller priority number implies a higher priority), and RR (quantum=1) scheduling. For each scheduling algorithm, compute the turnaround time and the waiting time for each process.

(a) SJF

Instructor Solution

Process Metrics:

Process	Burst Time	Finish Time	Turnaround	Waiting Time
P1	10	19	19	9
P2	1	1	1	0
P3	2	4	4	2
P4	1	2	2	1
P5	5	9	9	4

(b) Priority Scheduling

Instructor Solution

Process Metrics:

Process	Burst Time	Finish Time	Turnaround	Waiting Time
P1	10	16	16	6
P2	1	1	1	0
P3	2	18	18	16
P4	1	19	19	18
P5	5	6	6	1

(c) RR with quantum = 1

Instructor Solution

Process Metrics:

Process	Burst Time	Finish Time	Turnaround	Waiting Time
P1	10	19	19	9
P2	1	2	2	1
P3	2	7	7	5
P4	1	4	4	3
P5	5	14	14	9

Problem 34: CPU and I/O Scheduling with FCFS and RR

Consider the following set of processes with the given CPU, I/O burst times. The processes are assumed to have arrived in the order P1, P2, P3 all at time 0. Assume that the I/O operations can NOT be performed in parallel. That is, if a process is doing I/O, other processes must wait until the current process finishes its I/O operation. I/O scheduler uses FIFO scheduling.

P1	P2	P3
5 CPU	10 CPU	2 CPU
17 I/O	4 I/O	3 I/O
3 CPU	10 CPU	6 CPU

(a) Draw a Gantt chart illustrating the execution of these processes using FCFS. Compute the turnaround for each process, and the CPU utilization.

Instructor Solution

CPU Utilization:

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	25	25
P2	0	36	36
P3	0	42	42

(b) Draw a Gantt chart illustrating the execution of these processes using Round Robin Scheduling with a time quanta of 4. Compute the average waiting time and CPU utilization.

Instructor Solution

CPU Utilization:

Process Metrics:

Process	Arrival Time	Finish Time	Turnaround
P1	0	33	33
P2	0	44	44
P3	0	23	23

Problem 35: Multi-Algorithm Comparison with I/O

Consider the following set of processes with the given CPU, I/O burst times. The processes are assumed to have arrived in the order P1, P2, P3 all at time 0. Assume that the I/O operations can NOT be done in parallel. That is, if a process is doing I/O, other processes must wait until the current process finishes its I/O operation. I/O scheduler uses FIFO scheduling.

P1	P2	P3
2 CPU	4 CPU	4 CPU
3 I/O	3 I/O	3 I/O
1 CPU	2 CPU	2 CPU

(a) Draw a Gantt chart illustrating the execution of these processes using FCFS. Compute the average waiting time and CPU utilization.

Instructor Solution

CPU Utilization: 100%

(b) Draw a Gantt chart illustrating the execution of these processes using preemptive priority scheduling. Assume that P1 has the highest priority and P3 has the lowest priority. Compute the average turnaround time and CPU utilization.

Instructor Solution

CPU Utilization:

(c) Draw a Gantt chart illustrating the execution of these processes using Round Robin Scheduling with a time quanta of 2. Compute the average waiting time and CPU utilization.

Instructor Solution

CPU Utilization:

Problem 36: Priority and SRTF Scheduling

Consider the following set of processes with the given CPU, I/O burst times. The processes are assumed to have arrived in the order P1, P2, P3 all at time 0. Assume that P1 has the highest priority and P3 has the lowest priority. Assume that the I/O operations can NOT be done in parallel. That is, if a process is doing I/O, other processes must wait until the current process finishes its I/O operation. I/O scheduler uses FIFO scheduling.

P1	P2	P3
5 CPU	10 CPU	2 CPU
17 I/O	4 I/O	3 I/O
4 CPU	10 CPU	6 CPU

(a) Draw a Gantt chart illustrating the execution of these processes using Priority Scheduling without preemption. Compute the average waiting time and CPU utilization.

Instructor Solution

CPU Utilization:

(b) Draw a Gantt chart illustrating the execution of these processes using Shortest Job First with preemption, that is, Shortest Remaining Time First Scheduling. Compute the CPU utilization.

Instructor Solution

CPU Utilization:

Problem 37: SJF and Priority with Preemption

Consider the following set of processes with the given CPU, I/O burst times. The processes are assumed to have arrived in the order P1, P2, P3 all at time 0. Assume that P1 has the highest priority and P3 has the lowest priority. Assume that the I/O operations can NOT be done in parallel. That is, if a process is doing I/O, other processes must wait until the current process finishes its I/O operation. I/O scheduler uses FIFO scheduling.

P1	P2	P3
5 CPU	10 CPU	2 CPU
17 I/O	4 I/O	3 I/O
4 CPU	10 CPU	6 CPU

(a) Draw a Gantt chart illustrating the execution of these processes using Shortest Job First without preemption. Compute the average waiting time and CPU utilization.

(b) Draw a Gantt chart illustrating the execution of these processes using Priority Scheduling with preemption. Compute the average waiting time and CPU utilization.