Introduction

This simulator is capable of scheduling both real-time tasks and interactive tasks. The simulator is able to model the power consumption as well as the resulting temperature of the processor. The simulator allows for selecting the task scheduling algorithm as well as the frequency governor policy.

Task models

The simulator does not schedule real tasks, but uses a model of task behavior in terms of workload and power consumption. Let's look more closely at those models.

Real-Time tasks

Real-time tasks are modelled as an infinite sequence of jobs. Jobs are spawned at a regular interval. Each job is defined as a set amount of work, where every job of the same task can have the same or different (random) amount of work. Different random distributions can be used for the job's duration.

Interactive processes

Interactive tasks are modelled as a sequence of workloads and waiting times. The waiting times model the time spent by the task waiting for user input, network, or disk access, etc. The duration of waiting time, as well as the amount of work of each workload segmentis random, following an exponential distribution.

Model of the power consumption

The simulator models power consumption as the sum of static power and dynamic power. Static power has a fixed value and is consumed whenever the processor is turned on. Dynamic power depends on whichever task is running (if any) and the frequency it is running at. The simulator allows you to specify the task's power consumption relative to each other. For instance, task 0 has a power factor of 1.0, task 1 has a factor of 1.5, etc.

Model of processor temperature

The simulator provides a simple, first-order, model for processor temperature. It relies on the thermal resistance and thermal capacity of the processor, and its instantaneous power consumption.

Installation

The scheduler is a set of static libraries. To install, go to the src directory and run ./buildScript.sh. This will compile the libraries as well as an example use of the simulator.

to run the simulator, go to the simulator/ directory and run the command:

./bin/SchedulingSimulator configuration/configuration.conf

Using the simulator

My first simulation

As a first example, let's look at a very simple real-time scheduling problem. Let's consider two tasks. The first has a period of 15 and a worst-case execution time (WCET) of 5. The second task has a period of 20 and a WCET of 6. Both tasks are assumed to be deterministic, so that their execution time is always equal to their WCET. We want to schedule this taskset under rate-monotonic scheduling.

Let's take a look at the main function, in the file src/main.cpp:

#include <cassert>
#include <iostream>
#include <vector>
#include <utils/configuration.h>
#include <utils/programTime.h>
#include <scheduler/freqConstants.h>
#include <scheduler/schedulingSimulator.h>
#include <scheduler/schedulerConfiguration.h>
#include <scheduler/system.h>
#include <scheduler/process.h>
#include <scheduler/taskSetGenerator.h>
int main(int argc, char *argv[])
{
    Utils::ProgramTime::init();
    
    std::string defaultConfigName = "configuration/configuration.conf";
    std::string configName;
    configName = (argc == 2 ? argv[1]: defaultConfigName);
    
    std::shared_ptr<Scheduler::SchedulerConfiguration> conf = std::make_shared<Scheduler::SchedulerConfiguration>(configName);
    assert(conf != nullptr);
    Scheduler::SchedulingSimulator simulator(conf);
    simulator.seedRandomGenerator(123);
    
    simulator.createRealTimeTask(0.0, 15.0, 5.0*MINFREQ, 15.0);
    simulator.createRealTimeTask(0.0, 20.0, 6.0*MINFREQ, 20.0);
    simulator.turnOnProcessor(-0.0001);
    Scheduler::System::getInstance()->printProcessesReport();
    simulator.endSimulation(conf->getRunningTime());
    simulator.startScheduler();
    return 0;
}

The first step is to create a SchedulerConfiguration object, initialized from a configuration file. This allows you to specify many simulation parameters in a configuration file instead of havnig to hard-code them in C++. Then, we create a SchedulingSimulator object. This is the main object of the simulator. Next, we can create the tasks. The easiest way is via the createRealTimeTask with four arguments:

The time at which the task will first be ready
The period at which the task repeats itself
The amount of work to be done. Note that this is not a time duration. The simulator is capable of varying frequency, so the time taken to complete a task is not fixed. But for the moment, we will keep a constant frequency, the minimum frequency of the processor. Therefore, we can specify the amount of work corresponding to a given time duration by multiplying the duration by the processor frequency.
The deadline. Let's make this equal to the period of the task.

Next, we specify the time at which the processor should turn on. This value should be less than the starting time of the tasks.

Then, the function endSimulation() is used top specify at what time the simulation should end. In this case, we get the value from the configuration file.

Finally, we start the simulation.

Once the main file written, we can build the simulator (see above). We can now edit the configuration file, located in configuration/configuration.conf

[global]
reportsFolder = .
record = yes
[scheduler]
runningTime = 600
discipline = rmsDiscipline
governor = minGovernor
temperatureModel = simpleTemperatureModel
randomSeed = 1
distribution = none
logTemperature = yes
onlyLogTempAfterRatio = 0.0
thermalResistance = 2.0
thermalCapacitance = 20.0
logAging = no
[taskSet]
tasksetSource = compiled

The most important field is the kind of task scheduler to use. In this case, it is rate-monotonic scheduling (rmsScheduler).

When executing the simulation with the -verbose option, a log is displayed:

 -0.000: Starting processor
  0.000:  Task  0:0: New job
    Scheduler invoked. Ready queue contains 0(15) 
    Currently running process number 0:0
  0.000:  Task  1:0: New job
    Scheduler invoked. Ready queue contains 1(20) 
  5.000:  Task  0:0: Task terminates
    Processor sleeping
    Scheduler invoked. Ready queue contains 1(20) 
    Currently running process number 1:0
 11.000:  Task  1:0: Task terminates
    Processor sleeping
    Scheduler invoked. Ready queue contains nothing
 15.000:  Task  0:1: New job
    Scheduler invoked. Ready queue contains 0(30) 
    Currently running process number 0:1
 20.000:  Task  1:1: New job
    Scheduler invoked. Ready queue contains 1(40) 
 20.000:  Task  0:1: Task terminates
    Processor sleeping
    Scheduler invoked. Ready queue contains 1(40) 
    Currently running process number 1:1
 26.000:  Task  1:1: Task terminates
    Processor sleeping
    Scheduler invoked. Ready queue contains nothing
 30.000:  Task  0:2: New job
    Scheduler invoked. Ready queue contains 0(45) 
    Currently running process number 0:2
 35.000:  Task  0:2: Task terminates
    Processor sleeping
    Scheduler invoked. Ready queue contains nothing
 40.000:  Task  1:2: New job
    Scheduler invoked. Ready queue contains 1(60) 
    Currently running process number 1:2

it contains the list of all events, along with the time at which they occured. For instance, both tasks spawn a new job at time 0.0. At time 5.0, task with pid 0 terminates. Whenever the task scheduler is invoked, the content of the ready queue is displayed. It comprises the pid of the task as well as its amount of work. It also prints the task currently being executed (or about to be).

taskset generation

programatically

The first way to specify the taskset to simulate is to directly write it in C++ code, as we did in the first example.

random

Another way to generate tasksets is to do it randomly. First, make sure to replace the createRealTimeTask lines in the main function with the following line:

simulator.initializeTaskSet();

To generate the taskset randomly, you will also need to set up the configuration file as follows: In the [taskSet] section, the tasksetSource entry should be set to random, and some values need to be specified:

[taskSet]
tasksetSource = random
utilization = 0.7
nbOfTasks = 3
seed = 1234
priorities = no
powerSpan = 1.0

the utilization field lets you specify the processor utilization of the task set. nbOfTasks is the number of tasks. The simulator will then generate a taskset where tasks have random periods and wcet. Some other fields are required. The seed is the seed of the random generator that generates the taskset. This allows you to generate a different taskset by changing the seed value. By setting the priorities field to yes, the tasks will each have a different priority. This characteristic is used by some scheduling algorithms. Finally, powerSpan lets you specify the span of instantaneous power consumption of the different tasks (more on that later).

XML

Tasksets can also be specified via a configuration file. This allows tasksets to be changed without having to recompile the simulator. Also, they provide a structured way to store or transfer taskset data.

An example of XML taskset is in the file xml/taskset.xml

Task execution time distribution

In our first example, we had deterministic tasks: their execution time was always equal to their WCET. It is possible to specify a random task duration, no matter what task generation process (programatically, random, xml) you use. In the [scheduler] section of the configuration file, specify the distribution of task duration in the 'distribution' field. The possible values are:

none the task duration is deterministic and equal to its WCET
deterministic same as none
uniform the task diration follows a uniform random variable. The duration will be anywhere between BCET and WCET.
bernoulli 'p' the task duration follows a Bernoulli distribution: it will be equal to WCET with probability 'p' and BCET with probability 1 - 'p'. 'p' needs to be a number between 0 and 1.

For programatically generated tasksets, the BCET is specified in the createRealTimeTask function as an optional parameter. See function Scheduler::SchedulingSimulator::createRealTimeTask()

For random-generated tasksets, random duration is not yet fully supported.

Scheduling disciplines

The simulator comes with several scheduling disciplines availables, and allows you to easily add additional algorithms.

The built-in scheduling disciplines are:

rmsDiscipline Rate monotonic scheduling
edfDiscipline Earliest deadline first
fixedPriorityDiscipline Fixed priority
fcfsDiscipline First come first serve
roundRobinDiscipline Round robin
rlDiscipline Reinforcement learning (more on that later)

To create a new scheduling algorithm, the following steps should be taken:

Create a new class for your discipline. Ideally, the files should be located in the folder src/scheduler/discipline and consist of a .h and a .cpp file.
Your class should have a public member variable named configKey, of type std::string. This is the unique name by which you will refer to your discipline in the discipline field of the [scheduler] section in the configuration file.
Your class should extend the SchedulingDiscipline interface. See definition in file src/scheduler/discipline/schedulingDiscipline.h.
Add your files to the src/scheduler/discipline/CMakeLists.txt file to include them in the build.
Edit the function SchedulerConfiguration::getDisciplineFromFile() in the file src/scheduler/schedulerConfiguration.cpp in order to allow your new discipline to be selected at the configuration file level. Just follow the logic of the other disciplines. You will also need to #include your header file in that file.

Now, after building the simulator, you should be able to use your new algorithm just like any other scheduling discipline of the simulator.

Let's focus a bit on the interface functions you will need to implement:

getName() This should return a name for your scheduling algorithm. It is mainly used for logging and reporting purposes.
preempts() Given an event, this function should return true if your algorithm is supposed to preempt the currently running task when that event occurs.
selectNextTask() This is the main function of your class. It should return which task of the ready queue should be run from this point on. It can also return nullptr to signify that the processor should be idle until the next event.

Reinforcement learning scheduling discipline

to be continued...

Reports

The simulator can save to file several reports, such as:

Deadline misses: The report will contain timestamp of each deadline, along with which task missed its deadline.
Temperature: The report will contain the temperature of the processor at the time of each scheduler invocation (along with its timestamp). Additionally, you can record temperature at a finer-grained interval by getting a special event to be triggered.
Aging