What's the problem?

Computers and networks of computers often need to deal with more than one process at once. On an individual level, a user might be running Firefox, Outlook, Word, and Emacs on her laptop; on a group level, the students in a university's physics department might all submit simulations to the university's network. The system only has so many resources, and it must divide them among the processes. In many cases, the user (or administrator) gives each process a "share" to tell the system how much of the CPU quanta to devote to it; so Process 1 might have a share of 25%, Process 2 of 8%, etc.

The problem arises when all the processes' working sets will not fit in the available memory. If it's Process 2's turn to run, but Process 2's working set isn't in memory, it begins paging: pulling the pages it needs into memory. This can be a lengthy process, and while it happens, Process 2 isn't getting the share it needs: the time is being wasted. We need some way of managing processes' working sets while keeping the CPU active and balanced among the shares.

Enter RIRO

RIRO stands for Roll-In Roll-Out, and it's a way of dealing with the paging problem. Each process's working set is "rolled in" to memory just before that process runs; then after it's received its share, the working set is "rolled out" again, making room for the next process. These periods of rolling in and out overlap with the running time of the next and previous process, meaning that while a process accesses memory, no time is being wasted. (This also means that the memory must be at least large enough to hold two working sets at once.)

There are many algorithms for RIRO. Some look at the group of processes and calculate an ideal schedule of rolling in, rolling out, and running, in order to give each process its fair share in the shortest possible time. Others work on the fly, letting whichever process is farthest behind roll in next.

So far I've written simulators for four different implementations of RIRO. Two create pre-computed, optimal schedules-- Simple Linear scheduler and Start-End scheduler-- and two are heuristic schedulers-- In Order scheduler and Two Heap scheduler.

Simple Linear scheduling

A simple linear schedule runs each process one at a time, rolling out the previous process while the next one runs and rolling in the next process while the previous one runs.

Take a look at the Simple Linear algorithm to find out how to determine the optimal simple linear schedule.

Start-End scheduling

A start-end scheduler works like a simple linear scheduler in that it lists all possible schedules, then chooses the one with the lowest runtime; but rather than permutations of processes, it uses permutations of start (s) and end (e) events to create its schedules. So if your processes are P0, P1, and P2, a start-end schedule might be:

  • s1 s0 e1 s2 e0 e2

For an in-depth look at this kind of scheduling, check out the Start-End Algorithm that Xin and I developed.

In Order scheduling

An in-order scheduler is a simple, naive (read: stupid) heuristic algorithm that runs the processes in the order of their ID numbers. Each process is run for the length of time given by its share-- so if three processes have shares of 2, 8, and 50, they get run for 2, 8, and 50 units of time. If possible, the scheduler rolls out the last process and rolls in the next one while the current one is running; but if there's not room for that, the scheduler just lets the CPU sit idle while it's rolling the processes in and out.

Because it allows each process to run for the shortest possible amount of time while still remaining proportional to its share, the in-order scheduler reaches fairness very quickly. However, because it often requires blocks of idle time, it tends to have a longer total runtime than the Start-End or Simple Linear schedulers.

Two Heap scheduling

A two heap scheduler is a more intelligent heuristic algorithm that keeps two heaps, or priority queues, of processes: an active heap (processes that are rolled in and receiving quanta) and a passive heap (processes that are rolled out). The top processes of the two heaps are continuously swapped between the heaps.

For a more in-depth look at two heap scheduling, see the Two Heap Algorithm.

Results and Data

I've written a simulator that runs all four kinds of schedulers on the same sets of processes and plots the results, using three different formats:

  • CPU plots - plot how many CPU quanta each process has received, over time.
  • Share plots - plot what share of the CPU quanta given each process has received. There are three types of share plots: normal, which plot the share of quanta a process has received over the entire lifetime of the run; window, which plot shares over a sliding window of time (the window's size is approximately equal to the schedule length); and averaged, which calculate shares using exponential averaging. Horizontal lines show where each process's goal share is.
  • Integral plots - plot the absolute value of the difference between each process's current share and its goal share, over time. Labelled with the total area under all the process curves, which represents a kind of overall fairness for the schedule-- the smaller, the better.

This chart gives an overview of the runtimes and fairness of the three different schedulers (not the Two Heap scheduler).

Here are CPU and normal share plots for the various process sets:

Here are integral plots for some of the process sets:

Here are window share plots for some of the process sets:

Here are averaged share plots for some of the process sets:

Code

Here's all the code used to run the simulator and generate the plots. To run the simulator, do java Simulator; to generate plots, do ./grapher foo.proc n, where foo.proc is a process file and n is the amount of available memory.

My code:

Other authors' code (check comments for ownership):

My bash scripts: