Definitions

Process: An active execution of a program running on an Operating System.

Thread: The smallest sequence of manageable programmed instructions.

Scheduler: A software component of an operating system, that decides what process, thread, or task should run next on the CPU.

Context Switch: A mechanism used by operating systems to save a current state of a running process or thread, then loads a state of another process or thread.

Throughput: The actual data rate that is transmitted or processed within a specific time frame. Often expressed in bits per second.

Latency: The time delay between initiation of an action and receiving a corresponding response. Often measured in milliseconds.

CPU Scheduling uses a ready queue, in that processes are served from. This is an important function of CPU's as they can only handle a single task at a time, and there tends to be multiple running tasks at any given time that need to be processed. This also ensures whenever the CPU is idle, the Operating System has at least a single process available in the ready queue.

The internal mechanisms of the Scheduler ensure all processes are handled appropriately based upon the underlying algorithm to ensure maximum throughput and minimal latency between tasks. Optimal performance from these algorithms aim to keep the CPU busy at all times.

There are two main types of scheduling methods, preemptive scheduling and non-preemptive scheduling. Preemptive scheduling is when a process switches from a running state to a ready state or from a waiting state to a ready state, where non-preemptive scheduling is used when a process terminates, or when a process switches from a running state to waiting state and only reassigns when that process is complete. With preemptive scheduling the scheduler may decide depending on the algorithm in use, to use context switching and stop a current process, before switching to the next process in the queue. The scheduler tends to operate at the thread level treating each thread as an independently scheduled unit within a process.

How it Works

First Come First Served is a Scheduling Algorithm that works as it is defined, when a process arrives into the ready queue, it is served in the order it comes in, until completion. Due to it being non-preemptive, the order does not utilize Preemptive Context Switching, and instead initializes, and runs, a single process, until completion.

Advantages

First Come First Served, is simple to implement, it's an easier to design and understand scheduling algorithm and has minimal overhead. It simply runs the processes in the order they arrive, due to this it has what could be considered a fair execution order, as processes are handled in a first-in first-out condition. Thanks to this, every process should eventually execute, with predictable behavior. Allowing for easier analysis of performance conditions.

Disadvantages

Disadvantages to First Come First Served are wait time, response time, and poor handling of urgency. As each process is treated equally regardless of priority, length, interaction requirements, or deadlines. The wait time, and response times, end up being linear. With Process A and Process B arriving at the same time, in a case where Process A has a wait time of 0ms, due to it arriving first, but a completion time of 20ms, leading to Process B, having a wait time of 20ms, in addition to it's completion time. These times can become unnecessarily large, leading to sluggish systems with high latency.

Convoy Effect

In alignment with disadvantages, the Convoy Effect is known to be the biggest weakness of First Come First Served Scheduling as a long running process at the front of the queue ensures all shorter processes are required to wait. In the example of Process A having a completion time of 20ms assume Process B has a completion time of 10ms, and a third, Process C with a completion time of 5ms, if Process A arrives before B then C, the total time to execute Process C will be 35ms. Process C having to wait until Process B and Process A execute fully, despite needing the least amount of processing time on the CPU.

Exercise

Mathematically if we pick 5 Processes, with random execution times by rolling a d20 dice, and multiplying by 10 to ensure we have substantial data. We can chart the processes in a quick exercise. With the expression Process => Completion Time from Arrival.

With Non-Preemptive SJF Scheduling, the scheduler or scheduling algorithm looks at all available processes, and picks the one with the shortest burst time. After the process runs until completion, the next shortest burst time process is selected. In the case multiple processes have the same burst time, they are scheduled using FCFS Scheduling.

The advantages to Shortest Job First Scheduling are in relation to the minimal wait times provided by this algorithm. As well as being simple and easy to implement (minus not knowing burst times in advance). It's an optimal algorithm for minimizing wait times, and is useful for batch processing.

In the case of Preemptive Shortest Job First Scheduling, longer processes may never get CPU time in the case shorter processes keep arriving in the queue, while this can be mitigated by using priority or aging, in a Non-Preemptive SJF Schedule CPU Starvation is still possible as well, however is more apparent in Preemptive SJF. Additionally, burst times are often unknown in advance, so estimation is required.

Exercise

For the example, we'll be looking at Non-Preemptive Shortest Job First Scheduling in order to compare it against First Come First Serve Scheduling. Using the same processes, after we'll compare the two. As before Process => Completion Time from Arrival.

With first come first serve, we can see regardless of the burst time, the process arrives and is executed in the order received. Without priorities we can't determine if it's successfully executing urgent processes in a timely manner, but the same goes for shortest job first. The main difference here is the optimization that processes with a short burst time are executed first, without having an extensive wait time.

For that, we can see this reflect in Exercise 3 from both Day 2 and Day 3, for P1: 20ms, P2: 10ms, P3: 160ms, P4: 80ms, P5: 80ms. For first come first serve, P4 and P5 have a wait time of 190ms for P4, and 270ms for P5. Where shortest job first has a wait time of 30ms for P4, and 110ms for P5. These exercises both focused on arrival order, and execution time, without priority, or context switching. However they also highlight the foundations of CPU Scheduling and the Algorithms in use.

Using time quantum, as a variable in the algorithm, RR cycles through processes in the ready queue until each process is completed. In the simplest process possible, if we use q for time quantum like so, q = 5, then if P1 with a burst time of 20ms, and P2 with a burst time of 45ms, would cycle in the CPU for the respective slice per time quantum, so P1 would run for 4 slices, until completion, and time P2 would run for 9 slices, until completion.

With RR the advantages compound against FCFS, and SJF Scheduling. With this algorithm starvation is unlikely, CPU allocation is consistent for each process, response times in interactive systems decrease. Optimization at this level becomes more dependent on the algorithm and use case, with the time quantum determining the utilization of each process, rather than the burst time of each process.

Adjacent to the advantage of optimization due to time quantums, the disadvantage also appears here. With performance relaying on having an optimal time quantum. As excessive context switching can reduce efficiency of the algorithm. This also may have a greater average turn around time compared to SJF.

Exercise

For this exercise, we'll give 3 example with differing time quantums. One for q = 4, one for q = 6, and one for q = 10. To ensure we have good data to compare, we'll continue using the process sets from previous examples.

Here we can see structural differences in averages and wait times against the process set. Vastly different from the first two algorithms. Where the processes were ran as they entered the ready queue, or where the shortest job times ran first. With Round Robin we can see each process is treated fairly and routed in and out of the ready queue. Increasing overall times comparatively to non-preemptive scheduling.

While this may be more favorable and optimal for interactive systems where multiple tasks are being completed at once, and it limits disadvantages experienced with previous algorithms. It introduces overhead due to increased use of context switching, which can increase turnaround times and reduce efficiency if the quantum time is too small.

Definitions

Aging: The process of gradually increasing the priority of processes that have waited in the ready queue for long time periods.

With Priority Scheduling, there are two ways it can operate, Preemptively, with newly arrived higher-priority processes interrupting the running process, or Non-Preemptive, where processes run until completion.

Priority can also be assigned statically, or dynamically. With static assignment being assigned once, and never changing. Or dynamic assignment, where the scheduler may increase or decrease priorities based on wait time, CPU usage, I/O Bandwidth, or existing system policies.

Advantages exist for both Preemptive, and Non-Preemptive Priority, as well as Static, and Dynamic use cases.

For Preemptive Static Priority Scheduling, execution of Critical/Urgent Tasks have fast response time, and predictable behavior. Meaning Systems are easier to monitor and test on. This is more suited for Real-Time Systems where time is of the essence.

For Preemptive Dynamic Priority Scheduling, the advantages shift to reducing CPU Starvation, adaptive priorities to adjust to System Conditions, and a favorable environment for Multi-User conditions.

With Non-Preemptive Static Priority Scheduling, these advantages take the form of lower overhead, simple implementation, and predictable execution behaviors. All being beneficial for stable system behaviors.

For Non-Preemptive Dynamic Priority Scheduling,There is a focus on lower overhead, reduced starvation, improved throughput, and adaptability to variable workloads. Allowing for a predictable system with multiple options available for work cases.

Disadvantages also exist for both Preemptive, and Non-Preemptive Priority, as well as Static, and Dynamic use cases.

With Preemptive Static Priority Scheduling, disadvantages begin with starvation, higher overhead due to context switching, and increased complexity. If higher priority processes keep arriving, lower priority processes may never execute, even with aging this becomes problematic due to priority inversion where a low priority process can keep resources locked until completion due to a greater age.

For Preemptive Dynamic Priority Scheduling, the behavior becoming unpredictable but adaptable, it's complexity increases due to continuously adapting conditions, higher overhead, and a need for fine tuning become apparent here. Processes may oscillate between higher and lower priorities if all variables are not adjusted for optimal performance.

With Non-Preemptive Static Priority, disadvantages remain with starvation, response time and wait time become apparent with higher priority or urgent tasks. As a lower priority process may begin running and be unable to shift, or dynamically shift the priority of a more urgent task. This leads to inefficient utilization due to longer running processes blocking important tasks.

Lastly Non-Preemptive Dynamic Priority Scheduling, disadvantages here exist with complexity, and overhead. Where adjustment needs to be fine tuned, or starvation and delays will become apparent.

Exercise

For this exercise, we'll continue to use the process sets from Exercises A, B, and C. Focusing on Non-Preemptive Static Priority. We'll include priority, and a comparison table will be shown to identify key differences in the previous scheduling algorithms.

Here we can see that Non-Preemptive Static Priority Scheduling appears consistent for average wait time, turnaround time, and completion time with Round Robin. The difference here consists in the execution order, without context switching, the processes run until completion, and their execution order is known. Leading to consistent, predictable results.

Based on the exercise sets, Shortest Job First appears to have the most effecient performance. Reducing average wait time compared to the other algorithms. Although this is a case where burst times are known. Meaning it would not reflect real world data on an actual Operating System.

With First Come First Serve showing a middle ground between wait time, and tunaround time for each process. We can also see in our gantt chart the effects of Convoying, with longer processes restricting the execution of shorter process.

Round Robin and Priority Scheduling showed a decrease in efficiency within our data sets, in order to achieve responsiveness and fairness. This highlights that the efficiency of Shortest Job First, may not be reliable for real systems where responsiveness and fairness are needed improvements.