RTEMS: Adding a new scheduler

In this post I describe how to add a new scheduler implementation to the RTEMS open-source real-time operating system. The scheduler I use as an example is an earliest deadline first (EDF) scheduler which applies the EDF algorithm to schedule periodic tasks and a FIFO policy for non-periodic tasks.  This post demonstrates how to use my modular scheduling framework to extend the scheduling capabilities of RTEMS.

Architectural simulators

As a researcher in the areas of operating systems, compilers, and computer architecture, I spend a lot of time dealing with simulators.  An inordinate amount of time.  Much of this time is spent figuring out how well a given simulator provides:

1. Useful timing measurements (cycle-accurate)
2. Support for fully functional OSs (full-system)
3. Auxiliary features for specific experiments
4. Support for useful hardware platforms and instruction sets
5. Openness to modifying microarchitectural features
6. Availability of technical support

In my current work, I'm interested in actively developed simulators that support cycle-accurate full-system simulation with a detailed memory hierarchy on out-of-order uniprocessor or multicore RISC architecture models with the SPARC, MIPS, or ARM instruction sets that supports extending the pipeline and instruction set.  The rest of this article discussed my efforts in finding simulators to meet my needs.

Interrupt Handling with MMU Hardware on an MMU-less OS

This post describes some work that I have just recently gotten to a point that it seems to be correct.  It was a long-running project that started around May 2010.

RTEMS Modular Task Scheduler

As I mentioned in my last post, this past summer I participated in the Google Summer of Code by working on the RTEMS project. I have hopefully ironed out the last few small details that prevented the basic infrastructure that I developed from being accepted into the RTEMS code base. In this post I describe the design of the new scheduler, and also comment on some of the problems that I faced when merging the work. At the end of the post is a list of remaining work for this project.

Pre-existing RTEMS Scheduler

New Modular Scheduler
  Scheduler Control Structure
  Ready Queue Encapsulation
  Per-Thread Metadata
  Scheduler Operations Table
  Configuring the Scheduler

Merging the New Scheduler
  Short-circuit Evaluation
  PowerPC overheads

Open Issues
Improper Encapsulation
Interrupt Service Routine (ISR) Latency
Documentation
Configuration
New Technologies

Retroactive Introduction to my GSOC project

I've been busy this summer, between my GSOC project, my academic progress, and life in general. I thought I should catalog some of the work that I've done for the GSOC 2010. I have previously talked about my work to port RTEMS to SPARC V9. Well, I had a GSOC project accepted for the RTEMS project which I have been working on this summer. The remainder of this blog post is excerpted from my project proposal and describes what I have been doing lately. The full project proposal can be read online at: http://code.google.com/p/rtems-sched/wiki/ModularSuperCoreSchedulerProject.

My project is to refactor the RTEMS task scheduler to make it more modular. The current RTEMS scheduler is tightly coupled with the thread management code. This tight coupling prevents easy implementation and testing of alternate scheduling mechanisms. Refactoring the scheduler into a new SuperCore Scheduler Manager enables RTEMS developers (namely, me) to explore new scheduling mechanisms.

After finishing my project, the RTEMS scheduler internal data structures will be encapsulated in a module that provides a protected interface such that none of the thread management code directly touches scheduling data.

Perhaps the most important outcome of my project will be enabling exploration of scheduling for symmetric multiprocessing (SMP) and multicore platforms. An SMP system is a closely-coupled system with multiple CPU chips interconnected with main memory; a multicore system is even more tightly coupled, with multiple CPUs interconnected on a single chip. Although RTEMS currently supports multiprocessing systems, the support is designed for coarse-grained systems. Each processing element (core) runs a separate RTEMS application and executive, and communication is routed through a portion of shared memory. Scheduling decisions are made locally at each core, and tasks are not able to migrate between cores.

Although my project will not provide SMP support, the goal of refactoring the scheduler is to facilitate implementing an SMP scheduler, so care will be taken to make sure the interface does not enforce any policies that might deter an SMP scheduler. By supporting global scheduling decisions and task migration, RTEMS will be able to balance a processing load across multiple CPUs. Further, unifying the executive across all the cores in the system allows RTEMS to make smarter decisions and to reduce the effort of end users in deploying SMP and multicore configurations.

Understanding Energy and Power

Lately I've been looking at power as an evaluation metric for my research. Power consumption has always been an important design concern in embedded and resource constrained devices. Recently, power has also become important in desktop and server computing environments at the chip-level and at the rack-level respectively.

Energy and power are related, and the two are so often used synonymously that confusing them is quite easy.

Power, typically measured in (kilo)watts, is a rate of production or consumption of energy. The watt unit is an expression of coulombs per second, where a coulomb is a unit of electric charge. So power is the rate of change of electric charge over a period of time. Energy is typically measured in (kilo)watt-hours, which is what shows up on your "power" bill. So you pay for the total amount of energy consumed during the period of your bill, which is actually power integrated over that interval.

A common analogy to help understand the relationship between power and energy is that power is to a flow of water as energy is to a pool of water. The flow can be very slow, dripping even, but can fill a pool given enough time; or the flow can be very fast and fill a pool even quicker. The amount of water in the pool is analogous to energy, and the rate of the flow is analogous to power.

I find it is also helpful to consider the physical equations.

To understand power and energy, think back to middle or high school and recall Ohm's law, I = V / R (equivalently V = I * R), where I is current, V is voltage, and R is resistance. Current is the movement of electric particles, measured in amperes. Voltage is the force required to drive a current between two points, measured in volts. Resistance is opposition to current, measured in ohms. Note that current and voltage are only non-zero if there is a mismatch in the electrical potential between two connected points, and that bad things happen as resistance approaches zero.

Ohm's law is about as far as most people recall (if even that far!), and we haven't yet reached energy or power. We can get some interesting equations by substituting Ohm's law into Joule's first law after some massaging, P = I^2 * R = V * I = V^2 / R, where P is the power dissipated by a resistor. Power dissipation is a more accurate term for the notion of power consumption, although the two can be used interchangeably to mean the conversion of power into some other form of transfer of energy, for example heat or sound. The power dissipation of the resistive elements of a circuit is equivalent to the instantaneous power applied to the circuit in order to generate current through it. By considering a current applied from time 0 to t to a circuit with resistance R, the electric energy created by the current passing through the resistive elements of the circuit during that time interval is E = P * t.

The moral of the story is that power is the rate of transfer of electrical charge, and that energy is an accumulation of electrical charge.

Building and Booting RTEMS sparc64

I've put together a package at http://code.google.com/p/rtemssparc64/downloads/list called buildsparc64.tgz that contains a directory structure with scripts to help build the niagara and usiii BSPs.

There is a README with some simple instructions. After extracting the archive, you'll need to create a link in the build-sparc64 directory to the RTEMS sources on your machine (that contain the sparc64 CPU model and BSPs). Assuming you have the sparc64-rtems4.11 tools installed, you will then be able to build the niagara or usiii BSPs. Then there are scripts in the boot subdirectory to help build a bootable ISO image for either BSP. The scripts are set up to only build and package some of the RTEMS sample applications. Note that only Niagara has been run on open source simulators so far. I have run both BSPs on the Simics simulator, and you can contact me privately for more information.

Once you successfully build the image.iso file, you can follow the instructions at my previous post about the M5 simulator to run the BSP. Simply make a link from the built image.iso file to the /dist/m5/system/disks/image.iso file, and make the changes I mention to the M5 configuration files.