scheduled processes. For example, the Completely Fair Scheduler (CFS) is a process
scheduler for the 2.6.23 (October 2007) release of the Linux kernel. Schedulers like the
CFS keep track of time (in nanoseconds) a process has executed on processor, called
vruntime. In this assignment, we will implement and analysis CFS types of schedulers
that keep track of vruntime of a process. Processes that has got a small amount of
time are boosted to the front of the runqueue to get the processor, those who got bigger
amount of time are thwarted [1]. When the scheduler is invoked to run a new process: the
process with the lowest vruntime from the runqueue is chosen, and sent for execution,
then
1
2
. If the process simply completes execution, it is removed from the runqueue
. Otherwise, if it is interrupted for a reason, it is reinserted into the runqueue based
on its new vruntime. If there are multiple processes has the same vruntime, they
follow a First-In-First-Out (FIFO) ordered.
This type of schedulers commonly require efficient data structure implementation of
the runqueue to schedule new process, delete process, track process information and high-
performance code to generate the schedules. Despite the name, the runqueue need not be
implemented in the traditional way, e.g., as an array. In this assignment, we defines the
runqueue as an abstract data type similar to a PriorityQueue and consider the following
two representations:
•
•
The Sequential Representation
The Tree Representation
We will implement both representations for the runqueue and evaluate how well they
perform when representing some given runqueues and compute the average speed of
various operations.
4
Tasks
The assignment is broken up into a number of tasks, to help you progressively complete
the project.
4
.1 Task A: Implement the runqueue representations and its op-
erations (8 marks)
In this task, you will implement the runqueue using linear and tree representations,
respectively. Each representation will be implemented by various data structures. Each
element of the runqueue represents a process to be scheduled, containing a process label,
and its vruntime.
4
.1.1 Data Structure Details
In this assignment, each element of the runqueue (i.e., process) will be represented with
an abstract data type Proc that consists of the following information: