This programming assignment 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).
- Fair share scheduling, which schedules tasks based on their user and assigns each user
the same time quantum for their tasks.
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.
Calculate the average turnaround time, and waiting time for each of the scheduling
algorithms.
Fair share scheduling description
The -share scheduling policy works as follow:
Several users may exist in the system and each user may own several processes.
In each scheduling cycle the scheduler distributes a predefined time quantum of CPU between different
users and processes.
At any scheduling cycle the scheduler distributes the time quantum equally between different users that
have at least one process ready for execution.
Furthermore, the scheduler distributes each user’s time share equally between processes that belong to
that user. when calculating the time to allocate , make sure to handle floating numbers.
The order which the processes will be scheduled in one cycle is not important, i.e. there is no priority on
users and processes.
For this scheduler, the second column of the input represents the user id instead of the priority.
Input
The schedule of tasks has the form [task name] [priority or user_id] [CPU burst], with the
following example format:
T1, 4, 20
T2, 2, 25
T3, 3, 25
T4, 3, 15
T5, 10, 10
Thus, task T1 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 with RR Scheduling 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. Example: Assume that at the beginning of a scheduling cycle, users A, B and C exist in the system. User A owns processes P1 and P2 ready for execution. User B owns process P3 ready for execution. User C does not have any ready process. Scheduler should distribute this cycle time quantum 50% to user A and 50% to user B. Therefore, P1 and P2 should receive 25% of quantum usage each, while P3 will receive 50% of quantum. This means that if fair-share scheduler has a quantum equal to 4 seconds. Then in this scheduling cycle P1 and P2 receives 1 second each, while P3 receives 2 seconds of CPU usage.
Output
The output of the program should have the following format.
[Scheduler name]
Will run name: [Task name]
Tid: [Task id]
Priority: [Task priority]
Burst: [Time that the task will run]
Average times: waiting [X], turnaround: [Y]
If the task finishes, print Task [Taskname] finished.
At the end of all tasks print the average waiting time, average turnaround time and response
time.
Example
Priority with RR scheduling
Will run Name: T8
Tid: 7
Priority: 10
Burst: 25
Task T8 finished.
Will run Name: T4
Tid: 3
Priority: 5
Burst: 15
Will run Name: T5
Tid: 4
Priority: 5
Burst: 20
Will run Name: T4
Tid: 3
Priority: 5
Burst: 5
Task T4 finished.
Average times: waiting [X], turnaround: [Y]
Implementation
A starting point for this project is available at
https://github.com/greggagne/osc10e/tree/master/ch5/project for both Java and C.
The Driver reads in the schedule of tasks, inserts each task into a linked list, and
invokes the process scheduler by calling the schedule() function. The schedule()
function executes each task according to the specified scheduling algorithm. Tasks selected
for execution on the CPU are determined by the pickNextTask() function and are executed by
invoking the run() function defined in CPU.
The program runs as follows
Java: java Driver fcfs schedule.txt
C: make fcfs and then ./fcfs schedule.txt
Refer to the README file for more details.
You don’t need to implement the Priority with RoundRobin scheduler, instead implement the
FairShare scheduling algorithm.
Hints:
- Familiarize yourself with the starting code before starting the assignment. Read the
documentation and understand the code that is already implemented.
- Implement the FCFS algorithm first. Compile and run the program with the different
inputs. When it works, start the implementation of other algorithms. One idea for work
division is: All members discuss the implementation strategy (i.e. data structures to use,
what are major considerations, etc.). Then each member can implement one algorithm,
assigning another member to revise the code and test it. All members participate in the
implementation of the fair share scheduler.
- Test with the input files given in the starting code.
Deliverables
You must submit the following:
- A zip file of your source code for your project
- A report (between 2 and 4 pages) detailing:
o A comparison of the scheduling algorithms considering your implementation,
their advantages and drawbacks and the average waiting and turnaround time.
You will demonstrate your work to the TA during lab sessions. Your code should run with new
input that follows the same format, regardless of the number of tasks or users.
