OSNews

Stop the theory, show me it works

The above description gave a quick overview of how to write a scheduling policy with Bossa. In this section, we will test the round-robin scheduler. The complete implementation and some test programs can be found in the archive rr.tar.gz. Of course, for these programs to run correctly the first step is to boot and run a Bossa kernel.

1. Untar, compile, install and boot the Bossa kernel (Note: you have to use make install to install the kernel and the Bossa tools) or boot the Bossa CD
2. Untar the archive:

   ---

   $ tar zxf RR.tar.gz
   $ cd RR
   $ ls
   loop10.c  Proportion.bossa  RR30.bossa     testRR.sh
   loop30.c  RR10.bossa        setup_test.sh
   $
   

   ---

   RR10.bossa and RR30.bossa are two round-robin implementations. In RR10 the time_slice of each process is 10 while in RR30 it is 30.




scheduling tree

3. As root, launch the setup_test.sh script. This script compiles the two round-robin policies as Linux modules using the bossa_install tool included with the Bossa kernel. Then the script loads the policy modules in the kernel and configures the scheduling tree as shown by the diagram.

   ---

   $ ./setup_test.sh

   ---

4. Run the test script:

   ---

   $ ./testRR.sh

   ---

   The script runs three infinite loops in parallel, with each loop printing a different number. The source code can be found in loop10.c et loop30.c. When launched, the loop program attaches itself to the round-robin scheduler and then loops.

   ---

   We run three loops (1, 2, 3) in parallel. They are
   scheduled by the round-robin scheduler with time_slice=30.
   1111111111111111111122222222222222222233333333333333333311111111111111111122222
   2222222222222333333333333333333331111111111111111111122222222222222222233333333
   3333333333111111111111111111222222222222222222223333333333333333333311111111111
   11111112222222222222222223333333333333333331111111111111111112222
   
   The round robin scheduling effect can clearly be seen.
   
   We run three loops (1, 2, 3) in parallel. They are scheduled by the round-robin
   scheduler with time_slice=10.
   11111122222233333311111122222233333311111122222233333311111122222233333311111122
   22223333331111112222223333331111112222223333331111112222223333331111112222223333
   33111111222222333333111111222222333333111111222222333333111111222222333333111111
   22222233333311111122222233333311111122222233333311111122
   
   The round robin scheduling effect can clearly be seen.
   

   ---

   Indeed, this trace shows the behavior of a round robin scheduler.

Conclusion

In this article we have presented the Bossa framework for developing scheduling policies. You should now have an initial understanding of the development of scheduling policy and the advantages of using a domain-specific language. Bossa makes development easier, and most scheduling algorithms can be written with a few hundred lines of code.

Also, as Bossa simplifies the development and integration of schedulers in an operating system kernel, it can be used to teach scheduling to CS undergraduate students. By experimenting with scheduling policies using Bossa, students can learn in a practical way how a scheduler works.

About the author: Christophe Augier is a student in Computer Science at the Ecole des Mines de Nantes (France) where he is focusing on Operating Systems and Networking. For his master's thesis he is currently developing a dedicated language for writing network packet schedulers.

Many thanks to Julia Lawall and Gilles Muller for supporting me in the writing of this article.

References

¹ The Earliest-Deadline First scheduling policy:

• The Bossa version of the EDF policy: EDF.bossa
• A research paper introducing EDF:
  Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,
  C. L. Liu and James W. Layland
  Journal of the ACM (JACM)
  Volume 20, Issue 1 (January 1973)