Advanced Process Scheduling Exercises

Multi-CPU I/O + CPU Scheduling

In a computing environment, we have two Central Processing Units (CPUs) and five distinct processes. Each process arrives at the system at a unique, random time and undergoes the following sequence:

  1. First CPU Burst: Upon arrival, the process requires a first batch of processing time on a CPU.

  2. I/O Operation: After the first CPU burst, the process moves to perform an Input/Output (I/O) operation. This environment has infinite I/O resources, allowing multiple processes to perform I/O operations simultaneously without queuing.

  3. Second CPU Burst: Following the I/O operation, the process returns for a second burst of CPU time.

  4. Completion: After the second CPU burst, the process completes its execution and retires.

Since there are two CPUs available, there are two separate queues for CPU processing. The scheduling algorithm employed is the Shortest Remaining Time First (SRTF) algorithm. In this context, the "remaining time" is the sum of the times remaining from both the first and second CPU bursts combined.

Your task is to analyze this system and determine the following metrics for each process:

  • Response Time: The time from the arrival of the process until the first time it is scheduled.

  • Waiting Time: The total time a process spends in the ready queue (excluding the time spent in I/O operations).

  • Turnaround Time: The total time from the arrival of the process until its completion.

  • Completion Order: The sequence in which the processes complete their execution.

  • Gantt Charts: Visual representations showing how the two CPUs are utilized over time, including the allocation of processes to each CPU.

ProcessArrival Time (units)First Burst (units)I/O Time (units)Second Burst (units)
P128105
P21492
P39959
P44142
P5741110

Exploring Aging in Priority Preemptive Scheduling

This problem explores the concept of aging in a priority-based preemptive scheduling algorithm within a single CPU system. There are five processes, labeled P1 to P5, each with its own initial priority level. In this scheduling environment, the priority of a process is dynamic and is subject to change based on the time it spends in the ready queue.

The aging mechanism works as follows:

  • Every 5 units of time a process spends in the ready queue, its priority is increased by 1.

  • The priority value is inversely related to the actual priority: a lower numerical value indicates a higher scheduling priority.

  • The minimum possible priority value a process can have is 0, representing the highest priority level.

The CPU scheduling is done based on priority, with the preemptive approach being used. This means that if a process with a higher priority (lower numerical value) enters the ready queue, it preempts the currently running process.

Your task will be to determine the order of execution, waiting times, and turnaround times for each process, using the assigned initial priorities and burst times for the processes.

ProcessArrival Time (units)Initial PriorityBurst Time (units)
P10419
P27320
P33120
P44030
P56220

Break ties by looking at the remaining time. If two processes have the same priority, only preempt if the running process has a higher remaining time. If that is also the same, do not preempt.

Exploring Multi-Level Queue Scheduling with Priority Preemption

This problem investigates a multi-level queue scheduling scenario designed to demonstrate the intricacies and efficiency of different scheduling algorithms working in tandem within a single CPU system. The system consists of three distinct queues, each employing a different scheduling algorithm, and a priority-based mechanism to manage the CPU allocation among these queues.

The three queues and their respective scheduling algorithms are as follows:

  1. First Queue - Round Robin (RR):

    • This queue utilizes the Round Robin scheduling algorithm with a time quantum of 2 units.

    • Processes in this queue are given the highest priority (Priority 0).

  2. Second Queue - Shortest Remaining Time Next (SRTN):

    • This queue employs the Shortest Remaining Time Next algorithm, a preemptive version of the shortest job next.

    • Processes in this queue are assigned a medium priority (Priority 1).

  3. Third Queue - First Come First Serve (FCFS):

    • The third queue operates on the First Come First Serve scheduling principle.

    • Processes in this queue are given the lowest priority (Priority 2).

The CPU scheduling works on a priority preemptive basis across these queues:

  • At any given time, the CPU selects the process from the queue with the highest priority (lowest numerical value).

  • Within each queue, the respective scheduling algorithm (RR, SRTN, or FCFS) determines which process is selected.

  • Preemption occurs if a process from a higher-priority queue becomes ready while a process from a lower-priority queue is executing. In such a case, the lower-priority process is preempted in favor of the higher-priority one.

Round Robin (RR) queue:

ProcessArrival Time (units)Burst Time (units)
PQ11210
PQ12520
PQ132029

Shortest Remaining Time Next (SRTN) queue:

ProcessArrival Time (units)Burst Time (units)
PQ211020
PQ22510
PQ233429

First Come First Serve (FCFS) queue:

ProcessArrival Time (units)Burst Time (units)
PQ31729
PQ32217
PQ3359

Find the response time, waiting time, and turnaround of each process. Draw the Gantt chart for the CPU. Find the order of completion of the processes.