Design Con 2015

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

Paulo Baltarejo Sousa and Luis Lino Ferreira, Polytechnic Institute of Porto

July 28, 2010

Paulo Baltarejo Sousa and Luis Lino Ferreira, Polytechnic Institute of PortoJuly 28, 2010

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 http://kernel.org/ 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 https://moodle.isep.ipp.pt/mod/resource/view.php?id=34521 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 error file 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

Conclusions
The Linux modular scheduling framework came with Linux 2.6.23 kernel version. This framework became the implementation of the new scheduling policies for Linux easier than the previous one.

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

In this document, we have presented in a depth description all steps required to implement a new scheduling policy. For that, we have modified the Linux 2.6.24 kernel version in order to support real-time tasks 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.

Resources:
1. Source code for the SCHED CASIO Linux Scheduler

References:
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 multicore processors 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.)

Loading comments...

Parts Search Datasheets.com

KNOWLEDGE CENTER