This project is an attempt at improving the prioritization of scheduled processes within a system. It currently utilizes a Shortest-Job-First (SJF) approach, iterating through multiple queues that contain jobs of specific priorities. The goal is to improve system performance with execution of tasks of varying burst time and to avoid CPU starvation or long waiting times. This solution involves applying weight and age to processes to combat starvation.
Although SJF scheduling is often shown to be one of the quickest methods, starvation (or excessive wait times) can become an issue when combined with priority scheduling in CPU-bound systems. This is caused by two main sources, jobs of low-priority and jobs of long-length (A.S., P.B.G., G.G., 2013).
A simple method of fixing the starvation of lower-priority processes is to increase the priority of each process if not completed in a certain amount of time. This requires applying aging to each process. This entails processes being passed to the next highest priority queue when reaching a certain age. To implement this, each time a process is completed a method is called to loop over all remaining process and increment their age relative to the time passed (simulated as the bursts preceding it). Once a process passes a certain age threshold it is passed to the next queue.
Another prevalent issue when utilizing these scheduling methods is that processes requiring long CPU burst times are constantly overtaken by shorter processes within its fixed-priority queue. This means long processes are slow to be dealt with or are never completed. An elegant solution to this issue is adding weight to each process. This is known as weighted-shortest-job-first and is an adaptation of agile methodologies being applied to CPU scheduling. This would ideally be implemented using an algorithm that uses the processes burst and age. The calculation would result in processes that are over a certain weight being moved further up their respective priority queues as they age.
However, the limitations of java priority queues mean processes cannot simply change position within the queue. This would require removing, adding, and re-looping over each process in the queue every time any one processes weight passes the threshold. Instead, the weight is made equivalent to the processes burst. This keeps time-complexity to a minimum as adjustments are made during the queue’s initial formation. To implement this, the custom comparator used to order processes by burst level has an additional statement that places any process with a burst over a certain threshold higher in the queue.
As the original method of shortest-job-first is commonly cited as one of the most efficient scheduling algorithms, the solution chosen uses modifications of SJF instead of altering to a less efficient method where issues such as dispatch latency can become an issue. This meant the problems could be solved whilst retaining the efficiency of the SJF scheduling algorithm. As the quantity of processes and their data can vary significantly depending on the data imported, fields for altering all thresholds are provided in the UI.
Silberchatz, A., Galvin, P.B., and Gagne, G. - 2013. CPU Scheduling. University of Illinois Chicago. [ONLINE]. Available from: https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html. [28 March 2019]