Implementing a new real-time scheduling policy for Linux: Part 3 -

Implementing a new real-time scheduling policy for Linux: Part 3


Described in the third part in this series is the logging system used by SCLS. The logging system is based on a file entry in the /proc directory called casio_event. Therefore, to get the information from this file we can use the cat command and redirect the output to a file, for instance, typing in a terminal the following command:

bash$ cat /proc/casio events > event

Each CASIO tasks related event is stored using a tuple {action, timestamp, message}. We assume four actions: CASIO_ENQUEUE, CASIO_DEQUEUE, CASIO_CONTEXT_SWITCH and CASIO_MSG. CASIO_ENQUEUE, CASIO_DEQUEUE and CASIO_CONTEXT_SWITCH are related to the enqueue, dequeue and context switch of a task. CASIO_MSG is used for debug purpose.

The timestamp field refers to the instant time at which the action happened and msg is a string used to write the message. Listing 17 below shows the data structures and functions implemented for the logging system and are defined in the /kernel_source- code/include/linux/sched.h file.

Listing 17. Data structures and functions for system log

The system log information is stored on the vector struct casio_event casio_event, which is managed as a circular queue. The fields lines and cursor are used to manage the information, namely the insertion and remotion of that information.

In order to get this information using an user space program like cat command, the /proc /casio_event file is created. For that purpose, we created a structure with all information required for the /proc file, including pointers to any functions in the /kernel source-code/ fs/proc/proc_misc.c (Listing 18 below ). Then, void __init proc_misc_init registers the structure within the kernel.

Listing 18. Creating the /proc/casio_event file

Next, is described which events are registered and where we have to write the code to catch those events. The first step is to initialize the data structures related to logging system. This must be done in the sched_init function. Listing 19 below shows the invocation of init_casio_event_log by the sched_init function to initialize the data fields of the logging system.

Listing 19. sched_init function calling the init_casio event log

The enqueue and the dequeue events are registered in the enqueue_task_casio (Listing 8 earlier) and dequeue_task_casio (Listing 9 earlier) functions.

Another important event is the context switch, that is, when a task that is running on a processor is replaced by other. The context_switch function is the interface to the architecture-specific methods that perform a low-level context switch.

This function is invoked in the schedule function, which is the main scheduler core function. schedule function is invoked directly at many points in the kernel to allocate the processor to a different process.

Therefore, the place to register the context switch event is within the schedule function. The context switch registration is shown in the Listing 20 below .

The variable prev is a pointer to the task that is being replaced by the other task pointed by next variable. Note that, the next variable catchs the return of the pick_next_task function that calls the pick_next_task of each scheduling class, starting by the highest priority (in this case by the casio_sched_class) and returning when it found a task. Note that, it will always find a task. In the worst case returns the pointer to the swapper process, the idle task.

Listing 20. schedule function

Assuming the task set presented in the Table 1 below , shown Listing 21 below shows part of the output generated by the SCLS.

Table 1. Task set.

As mentioned before, each CASIO tasks related event is stored using a tuple {action, timestamp, message}.

Listing 21. Output file

Concerning to the actions: 1 means enqueueing; 2 dequeueing, 3 context swicthing and 4 debugging. The time unit is nanoseconds and specifies the time instant when the event occurred.

The message format for enqueueing and for dequeueing actions is as follows: between parenthesis and separated by colon is: CASIO identifier (casio_id); kernel Linux process identifier (pid) and the last one is the absolute deadline of the CASIO task.

The message format for the context switching is: the casio_id and pid of the process that is being replaced is coming next to the word prey and following the word next it is specified the casio_id and pid of the selected process to be executed by processor. Note that, when one of them it is not a CASIO task the casio_id field appears equal to -1.

Looking for the first lines of Listing 21, we can check the scheduling algorithm behaviour. In the first line, it is shown the enqueue of the CASIO task 4. According to the scheduling algorithm if there is one CASIO task in the system and the currently executing it is not a CASIO task then, it must be preempted.

The context switch appears in the second line, where task with pid equal to 0 is replaced by CASIO task with casio_id equal to 4. In the third line appears another CASIO task with casio_id equal to 3.

As its absolute deadline is earlier than the task that is running (CASIO task with casio-id equal to 4) then, this CASIO task must be preempted. The context switch appears in the fourth line.

CASIO Tasks Implementation
As previously referred the system call sched_setscheduler allows changing the scheduling policy of a process and setting scheduling parameters (using the struct sched-param data structure).

Listing 22 below shows the basic CASIO task code. As one can see, sched_setscheduler has three parameters, the first is the pid of the process. If pid is equal to 0, the scheduler of the calling process will be set.

The second argument is the policy and the last one is used to set the parameters. However, the invocation of this system call must be performed by a process with root permissions.

Note that, according to the EDF scheduling algorithm, the deadline is a fundamental item. Then, it must be set through the deadline field of the struct sched_param data structure and using nanosecond time unit. casio-id field is used to set CASIO task identifier. Note that there is the need to include the sched.h header file.

Listing 22. CASIO task code

Tools and source code for this project
To complement the source code supplied with this series of articles, following are some directions on how to set up your system in order to be able to compile the kernel as well as the way to get the patch file of the SCLS.

Tree directories. The structure of directories used by the authors to implement the SCLS is as follows: In the $HOME we have created two directories: scheduler_dev and scheduler . The scheduler_dev was used to develop the SCLS. In the other hand, scheduler was used to compile the kernel source code.

Software required . Before you configure kernel make sure you have the minimum software versions for a kernel build:

Getting the required Linux kernel source code .   Visit and download the linux-2.6.24.tar.bz2 source code, which represents 2.6.24 kernel version and follow these directions:

 1) Use wget command to download kernel source code:

2) Type the following command:

3) Change the linux-2.6.24 directory name to linux-2.6.24-casio:

4) Create a config file from the current system configuration:

5) Change the EXTRAVERSION variable in the Makefile to differentiate this kernel version from others present in your system (Listing 23 below ).

Listing 23. kernel Makefile

6) Download the SCHED_CASIO.patch patch file from the to the scheduler_dev directory.

7) Apply the SCHED_CASIO patch. (Note that, at this moment the work directory is linux-2.6.24-casio ):

Compiling the kernel . Assuming that the currently work directory is the $HOME directory Listing 24 below shows a script file with a sequence of commands to compile the kernel.

Listing 24. Compile script

First, we save the modules. Next, we remove any directory from scheduler directory, then we copy all source code to the scheduler directory. Therefore, the path of the source code to be compiled is in the /$HOME/scheduler/linux-2.6.24-casio directory. We change the directory and select different options according to the needs.

Finally, the kernel compilation starts and if everything goes well a compressed kernel image is created, otherwise you can check the errors in the errorfile created in the /$HOME directory.Install the compiled kernel version generated by the previous step. For that, in the /$HOME/scheduler directory type:

To finish this process the system must be rebooted:

A new kernel image will boot in your system (Figure 3 below ).

Figure 3. System rebooting

The Linux modular scheduling framework came with Linux 2.6.23 kernelversion. This framework became the implementation of the new schedulingpolicies for Linux easier than the previous one.

However, in the literature we did not find documents that explain howto implement a new scheduling policy for Linux. Usually, generalpurpose documentation where all parts of the Linux are deeply explainedcan be found. The other way is hacking the Linux kernel source code.

In this document, we have presented in a depth description allsteps required to implement a new scheduling policy. For that, we havemodified the Linux 2.6.24 kernel version in order to support real-timetasks scheduled according to the EDF scheduling algorithm.

This is a simple implementation of that scheduling algorithm. However,advanced issues, like interruptions, timers and multiprocessor systems,just to mention some, are out of the scope of this article

To read Part 1 , go to:Scheduling in real-time Systems.
To read Part 2 , go to: Building a new scheduling policy module.

1. Source code for the SCHED CASIO Linux Scheduler

1. A. Kumar. Multiprocessing with the completely fair scheduler. Technical report, IBM, 2008.
2. D. Bovet and M. Cesati. Understanding The Linux Kernel. O Reilly & Associates Inc, 2005.
3. Wolfgang Mauerer. ProfessionalLinux Kernel Architecture. Wiley Publishing, Inc., 2008.
4. C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46-61, 1973.
5. John A. Stankovic. Misconceptions about real-time computing: A serious problem for next-generation systems. Computer, 21(10):10-19, 1988.
6. Arezou Mohammadi and Selim G. Akl. Technical report no. 2005-499 scheduling algorithms for real-time systems. 2005.
7. C. L. Liu. Scheduling algorithms for hard-real-time multiprogramming of a single processor. JPL Space Programs Summary, II(1):37-60, 1969.

(Paulo Baltarejo is a researcher on scheduling algorithms for multicoreprocessors at CISTER Research Group and also a Professor at the Polytechnic Institute of Porto in Portugal.

Luis Lino Ferreira is a researcher on QoS Architectures and algorithms for mobile distributed systems at CISTER Research Group and Professor at the Polytechnic Institute of Porto.)

5 thoughts on “Implementing a new real-time scheduling policy for Linux: Part 3

  1. “I have been struggling with implementing my own scheduler for a few weeks now. I figured out most of what you discussed in this article, however I was unable to connect all of the dots in order to create a polished product. I really appreciate you writi

    Log in to Reply
  2. “I need to write a scheduler as well, and I've been slamming my head to the wall and reached the same conclusion as you have regarding this post. By now, have you had any solid results? Can you share a success story or point me somewhere I can find what I

    Log in to Reply
  3. “Hey Luis thanks for this tutorial. Like what TamilS054 said, there is a problem with the patch link. It's not broken though, it asks a username and pass to a private Moodle page. Can you help please? Thanks”

    Log in to Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.