How to Create a Custom Scheduling Plugin in LITMUS^RT

A brief guide to creating a new scheduling plugin in LITMUS^RT (based on version 2012.2.)

As an example, we are going to implement a simple semi-partitioned EDF scheduler that migrates jobs among CPUs in a round-robin fashion every 500us of execution. While this is not an overly practical scheduler, it's a good example because it allows to demonstrate how to implement migrations, per-processor state, and custom scheduling timers.

Prerequisites

• A testing environment (i.e., KVM/Qemu or Bochs).
• Strong C programming skills.
• Ideally, some exposure to OS kernel development.

General Guidelines

Work in a checked-out git repository. Do not use the tarball from the web page. This will make keeping track of your edits and incorporating upstream changes much easier.

Commit early, commit often. Make many small commits a you go along. You can clean them up later using git rebase.

Do not commit to the master branch. This will make incorporating upstream changes much easier.

Follow the kernel coding standard defined in Documentation/CodingStyle, even when writing “throw away” code.

Step 0: Checkout and Compile the Kernel

First, obtain a copy of the LITMUSRT kernel.

$ git clone http://www.litmus-rt.org/src/litmus-rt.git
Cloning into litmus-rt...                                                                                                                                                                                       
$ cd litmus-rt/                                                                                                                                                               
$ ls
COPYING  Documentation  Kconfig      Makefile  REPORTING-BUGS  block   drivers   fs       init  kernel  litmus  net      scripts   sound  usr
CREDITS  Kbuild         MAINTAINERS  README    arch            crypto  firmware  include  ipc   lib     mm      samples  security  tools  virt

Next, obtain a working kernel configuration. For this tutorial, we are going to use the default KVM configuration.

$ wget http://www.litmus-rt.org/releases/2012.2/x86_64-config                                                                                                       
[...]
2012-08-13 14:22:25 (13.7 MB/s) - "x86_64-config" saved [52837/52837]
$ cp x86_64-config .config

Compile the kernel. On x86, the kernel build target is bzImage. Note that we do not compile modules for the default KVM configuration because all necessary drivers are statically compiled into the kernel image.

$ make -j16 bzImage
[...]
  CC      arch/x86/boot/compressed/cmdline.o
  CC      arch/x86/boot/compressed/early_serial_console.o
  OBJCOPY arch/x86/boot/compressed/vmlinux.bin
  HOSTCC  arch/x86/boot/compressed/mkpiggy
  GZIP    arch/x86/boot/compressed/vmlinux.bin.gz
  MKPIGGY arch/x86/boot/compressed/piggy.S
  AS      arch/x86/boot/compressed/piggy.o
  LD      arch/x86/boot/compressed/vmlinux
  ZOFFSET arch/x86/boot/zoffset.h
  OBJCOPY arch/x86/boot/vmlinux.bin
  AS      arch/x86/boot/header.o
  LD      arch/x86/boot/setup.elf
  OBJCOPY arch/x86/boot/setup.bin
  BUILD   arch/x86/boot/bzImage
Root device is (8, 1)
Setup is 14908 bytes (padded to 15360 bytes).
System is 3334 kB
CRC 3e3102d9
Kernel: arch/x86/boot/bzImage is ready  (#1)

Next, obtain a copy of liblitmus, the corresponding userspace library

$ git clone http://www.litmus-rt.org/src/liblitmus.git
Cloning into liblitmus...
$ cd liblitmus/
$ ls
INSTALL  Makefile  README  arch  bin  inc  include  setsched  showsched  src  tests

Finally, compile liblitmus. Note that this must occur after checking out the kernel since the liblitmus build system pulls some headers out of the kernel repository.

$ make
cp ../litmus-rt/include/litmus/rt_param.h include/litmus/rt_param.h
[...]
gcc -o runtests -m64  core_api.o fdso.o locks.o pcp.o runner.o   -L. -llitmus 

We are now ready to start hacking LITMUS^RT.

Step 1: Dummy File

Create a new file and add it to the build system.

1. Create the file litmus/sched_demo.c (all file names are relative to the kernel repository).

2. Edit the file litmus/Makefile to add sched_demo.o to the list named obj-y.

3. Compile the kernel to see if everything works.

Step 2: Dummy Plugin

Edit the file litmus/sched_demo.c to declare a dummy plugin (that implements no particular policy and that rejects all tasks).

Step 3: Define the Per-Processor State

In this step, we define the scheduler state on each processor.

Step 4: Augment the Per-Task State

Our scheduler needs to keep track of...

Step 5: Initialize the Scheduler Plugin

Step 6: Initialize new Tasks

Step 7: Enable Admission of Tasks

Step 8: Boot the Kernel in KVM

kvm -gdb tcp::3008 -smp 4 -hda /RTS/litmus-rt/work/kvm-images/bbb-litmus-rt.img -m 2000 -net nic,model=e1000 -net user -k en-us -kernel /home/bbb/ldev/litmus-rt/arch/x86/boot/bzImage -append console=ttyS0 ro root=/dev/hda1 no_timer_check  no_timer_check -nographic -redir tcp:2104::22

Step 9: Observe the Debugging TRACE() Log

Step 10: Trace Task Execution

Step 11: Visualize the Trace

Step 12: Record Scheduling Overheads

Step 13: Analyze Scheduling Overheads