Scheduling Algorithms

This project involves implementing several different process scheduling algorithms. The scheduler will be assigned a predefined set of tasks and will schedule the tasks based on the selected scheduling algorithm. Each task is assigned a priority and CPU burst. The following scheduling algorithms will be implemented:

$$ First$-$come, first$-$served $($FCFS$),$ which schedules tasks in the order in which they request the CPU.

$$ Shortest$-$job$-$first $($SJF$),$ which schedules tasks in order of the length of the tasks' next CPU burst.

$$ Priority scheduling, which schedules tasks based on priority.

$$ Round$-$robin $($RR$)$ scheduling, where each task is run for a time quantum $($or for the remainder of its CPU burst$).$

$$ Priority with round$-$robin, which schedules tasks in order of priority and uses round$-$robin scheduling for tasks with equal priority.

Priorities range from $1$ to $10,$ where a higher numeric value indicates a higher relative priority. For round$-$robin scheduling, the length of a time quantum is $10$ milliseconds.

Implementation

The implementation of this project may be completed in either C or Java, and program files supporting both of these languages are provided in the source code download for the text. These supporting files read in the schedule of tasks, insert the tasks into a list, and invoke the scheduler.

The schedule of tasks has the form $[$task name$][$priority$][$CPU burst$],$ with the following example format:

T$1,4,20$

T$2,2,25$

T$3,3,25$

T$4,3,15$

T$5,10,10$

Thus, task T$1$ has priority $4$ and a CPU burst of $20$ milliseconds, and so forth. It is assumed that all tasks arrive at the same time, so your scheduler algorithms do not have to support higher$-$priority processes preempting processes with lower priorities. In addition, tasks do not have to be placed into a queue or list in any particular order.

There are a few different strategies for organizing the list of tasks, as first presented in Section CPU scheduler. One approach is to place all tasks in a single unordered list, where the strategy for task selection depends on the scheduling algorithm. For example, SJF scheduling would search the list to find the task with the shortest next CPU burst. Alternatively, a list could be ordered according to scheduling criteria $($that is$,$ by priority$).$ One other strategy involves having a separate queue for each unique priority, as shown in Figure $5\mathrm{.}3\mathrm{.}4.$ These approaches are briefly discussed in Section Multilevel feedback queue scheduling. It is also worth highlighting that we are using the terms list and queue somewhat interchangeably. However, a queue has very specific FIFO functionality, whereas a list does not have such strict insertion and deletion requirements. You are likely to find the functionality of a general list to be more suitable when completing this project.

Each program should be able to read a text file of tasks, run the corresponding scheduling algorithm and print out the average turnaround and waiting time, for example,$$

$./$fcfs schedule.txt

It is assumed that all tasks arrive at the same time $0,$ and in the order according to the list in the input text file. An example input file $$schedule$.$txt$$ is provided for testing your programs. The results of your implementation should match the "example$\_$out.txt$"$ for the example input file. But your program should work for any valid list of tasks following the same format and will be graded using a different input file. $$Your program should print out the turn$-$around and waiting time of each task, and the average turn$-$around time and average waiting time, for example:

T$1$ turn$-$around time $=20$

T$2$ turn$-$around time $=45,$ waiting time $=20$

T$3$ turn$-$around time $=70,$ waiting time $=45$

T$4$ turn$-$around time $=85,$ waiting time $=70$

T$5$ turn$-$around time $=105,$ waiting time $=85$

T$6$ turn$-$around time $=115,$ waiting time $=105$

T$7$ turn$-$around time $=145,$ waiting time $=115$

T$8$ turn$-$around time $=170,$ waiting time $=145$

Average turn$-$around time $=94\mathrm{.}375,$ Average waiting time $=73\mathrm{.}125$

Further challenges

Two additional challenges are presented for this project:

$1.$ Each task provided to the scheduler is assigned a unique task $($tid$).$ If a scheduler is running in an SMP environment where each CPU is separately running its own scheduler, there is a possible race condition on the variable that is used to assign task identifiers. Fix this race condition using an atomic integer.

On Linux and Mac os x systems, the $\_\_$sync$\_$fetch$\_$and$\_$add$()$ function can be used to atomically increment an integer value. As an example, the following code sample atomically increments value by $1$:

int value $=0$;

$\_\_$sync$\_$fetch$\_$and$\_$add$($&value,$1)$;

$2.$ Calculate the average turnaround time, waiting time, and response time for each of the scheduling algorithms.