Experiment 14 – Processes

Use micro:bian processes to perform multiple tasks concurrently.

Files

x14-processes:
valentine.c	Hearts and primes combined
Makefile	Build script
x14.geany	Geany project file

Programs in this part of the book use the micro:bian operating system as a basis. The source files that make up micro:bian and its standard device drivers are not replicated in each experiment directory, but exist as one shared copy in a top-level directory named microbian. Here is a list of them:

microbian:
microbian.c	Operating system kernel
microbian.h	Header file for clients
mpx-m0.s or mpx-m4.s	Context switching for V1 or V2
serial.c	Device driver for UART
timer.c	Device driver for timer
i2c.c	Device driver for I2C bus
radio.c	Device driver for 2.4 GHz radio
display.c	Device driver for LED display
hardware.h	Addresses of device registers
lib.c, lib.h	Library containing implementation of printf
startup.c	Start-up code
hardware.h	Addresses of device registers
device.ld	Linker script describing memory layout
Makefile	Build script

Not all these components of micro:bian are used in every experiment, and this one uses the components microbian.c (the heart of the operating system) and the device drivers serial.c and timer.c, but not the other components. The files startup.c, lib.c, lib.h, hardware.h and device.ld are identical with those used in earlier parts of the book. Using make to build any of the programs in this part of the book will check that the operating system has been built, and will include the operating system binary microbian.a in the final linking stage for the program. The linker uses this archive file to include just the operating system components that are actually used in each experiment.

Demonstration

Compile and upload the program valentine.hex, and connect to it with minicom. You will see that the program outputs a list of primes on the serial port, and that simultaneously it shows a beating heart pattern on the LEDs. Think of it as an electronic valentines card for your favourite mathematician!

Activity

As explained in the Background section below, the program contains two independent processes, one looking after the animated display and another that searches for prime numbers. Try changing one or both of these processes, and check that the program still works as expected.

• Change the animation so that each cycle takes two seconds rather than one, or so that the small heart pattern flashes three times instead of twice.
• Change the process that looks for primes so that it tests only the numbers 7, 13, 19, 25, ... that leave a remainder of 1 when divided by 6.

Background

The program as written consists of two processes, heart and primes, that appear to run independently of each other. The crucial difference between these processes and the similar-looking programs we wrote earlier is that when these processes pause for some reason, they do so not by entering a fruitless loop, waiting for a time when they can make progress, but instead by notifying the operating system, which is able to suspend them for a while and let the other process run until they are ready to proceed.

The heart process runs this code (or slightly different code on V2):

/* show -- display three rows of a picture n times */
void show(const unsigned *img, int n)
{
    while (n-- > 0) {
        /* Takes 15msec per iteration */
        for (int p = 0; p < 3; p++) {
            GPIO.OUT = img[p];
            timer_delay(5);
        }
    }
}

/* heart_task -- show beating heart */
void heart_task(int n)
{
    GPIO.DIRSET = 0xfff0;

    /* Set row pins to high-drive mode to increase brightness */
    gpio_drive(ROW1, GPIO_DRIVE_S0H1);
    gpio_drive(ROW2, GPIO_DRIVE_S0H1);
    gpio_drive(ROW3, GPIO_DRIVE_S0H1);

    /* priority(P_HIGH); */

    while (1) {
        show(heart, 70);
        show(small, 10);
        show(heart, 10);
        show(small, 10);
    }
}

This is like the animation code from before, but uses a subroutine timer_delay to introduce delays between one setting for the LEDs and the next.

The primes process runs this code:

/* prime_task -- print primes on the serial port */
void prime_task(int arg)
{
    int n = 2, count = 0;

    while (1) {
        if (prime(n)) {
            count++;
            printf("prime(%d) = %d\n", count, n);
        }
        n++;
    }
}

Notice that neither the heart nor the primes process is written in a way that depends on the existence of the other one. The difference is in the way two subroutines are implemented: the subroutine timer_delay that is explicitly called by heart, and the subroutine putchar that is implicitly called via printf when the primes process wants to produce some output. Each of these is implemented in a way that does not involve a wait loop. It is the operating system that shares the processor between the two processes, running each one when it is ready to make progress. The micro:bit has only a single processor, and cannot really run more than one process at a time, but the operating system arranges to switch between the processes in such a way that both appear to make steady progress.

As you will see, the subroutine call to timer_delay() that suspends the heart process appears in the subroutine show(), and though we cannot see it, the call to putchar that sometimes causes the primes process to pause is buried somewhere inside printf. The operating system is able to deal with processes that must pause somewhere inside multiple subroutine calls just as well as it deals with processes that pause in their 'main program'. In short, the operating system gives each process its own subroutine stack. Contrast this with programs that have a main program and a number of interrupt handlers, where there is only one stack.

In fact, there are not two but four processes in the running program because there are device driver processes provided by the operating system that look after the serial port and a hardware timer. The function init(), which in previous experiments has been the 'main program' from which all activity stems, now has only the purpose of creating the processes that will do the real work.

void init(void)
{
    serial_init();
    timer_init();
    start("Heart", heart_task, 0, STACK);
    start("Prime", prime_task, 0, STACK);
}

The calls to serial_init() and timer_init() start up the two hidden driver processes, and two explicit calls to start() create the two processes specific to this program. For each process, we specify a function that is the code that the process will run, an integer argument (here 0) that is passed to the function, and an amount of stack space to give to the process (here, the standard allocation STACK, that is 1kB, enough for most simple processes).

The primes process is a client of the serial port driver process, because when the version of putchar that it calls via printf is implemented by sending a request to the serial driver process. Likewise, the heart process is a client of the timer driver, because the subroutine timer_delay that it calls is implemented by sending a request to the timer process and then waiting for a reply that comes only when the delay has expired. It is at the point where the heart process waits to receive a reply from the timer process that the operating system intervenes, suspending the process until the reply arrives, and running the primes process for a while instead.

Context

Although it shares CPU time between the processes in a program, micro:bian is unlike many other operating systems in not keeping account of how much time each process uses. It stops a process and gives the CPU to another one only when the process tries to send or receive a message, or (as we'll shortly see) when an interrupt happens. This is a simple scheme that does not depend on configuring a hardware timer, and it works well in applications where the machine must wake up to respond to events, but is otherwise idle for most of the time, so that there is plenty of CPU time to go round. It would work less well in a situation where there were multiple processes, each trying to use as much CPU time as it could get; then the operating system would need to share out the time fairly among them, or perhaps the users whose processes were running more slowly would start to complain.

Challenges

When the primes process is looking for primes among fairly small numbers, the program works well. The amount of CPU time taken by the primes process is limited by the speed at which it can print its output, leaving plenty of CPU time for the heart process to look after the display. (Actually, I've reduced the CPU time needed by the primes process compared with the earlier version of the program by replacing a naive division subroutine with a faster one from the C library, invoked implicitly through the operator n % k.)

Now try increasing the CPU demand for primes by starting the search for primes not at 2 but at 20,000,000. These larger numbers have bigger gaps between primes, and besides, determining whether a specific number is prime is likely to require many more divisions than with smaller numbers. If you build and upload the program with this change, you should see that the display now flickers a bit: the effect is subtle, but it is there. This is because, when the heart process is ready to update the display, the operating system may choose to run the primes process instead for a time, and the primes process will not give up the processor until the next prime is found. In reality, the hearts process is not likely to wait for more than a few milliseconds, as every timer interrupt gives the operating system a chance to switch to a different process, but nevertheless the disruption to the display is visible.

Next, try this: there is a comment in the heart process that contains a subroutine call priority(P_HIGH). Remove the comment markers around this call: this will ask the operating system to give the process a higher priority, so that it runs this process, rather than the primes process, whenever both are active. Building and uploading the program again should solve the problem with the flickering display. Sometimes it seems counter-intuitive that the process that wants less CPU time (the heart process needs to make just one change to the GPIO.OUT register before pausing again) should be given the higher priority. The right way to imagine things is to think of the express checkout in a supermarket: it is provided for people in a hurry who have only a small amount of shopping, and lets them get out of the shop quickly. It would not provide the same benefit to have a special, high-priority checkout for people with large amounts of shopping: then it, like all the other checkouts, would become swamped at busy times with heavily-laden trolleys, and customers in a hurry to pay for just a few things would have to wait with everybody else.

You can illustrate the difference by taking the call to priority out of the heart process and adding it to the primes process, somewhere in the preamble before the main loop begins. This will give the primes process a higher priority, while leaving the heart process with the default priority P_LOW. Building and uploading this version of the program reveals a very different effect. Try starting with n = 2,000,000 for a more striking result, then switch the high priority back the the hearts process.

Questions

Why can't one micro:bian processes start another?

In short, because that would be a complication that would add little that was useful. The memory allocation in micro:bian is deliberately simple, stack space for each process being nibbled away from one end of a single chunk of free space. That works well if a fixed number of processes are started when the program begins, but much less well if processes come and (by implication) go during the life of the system. If processes exit and restart, we will need to re-use the storage space of dead processes to find room for new ones; and unless we are prepared to move processes around, we then face the problem of fragmentation of storage – all too messy to contemplate. Given that the operating system is only going to support a fixed collection of processes, we may as well have those processes created as part of initialisation, before the scheduler takes control.

What is the file microbian.a?

The file microbian.a is an archive file containing, packed together, all the files of object code that make up the micro:bian operating system and device drivers. We have seen a similar file before, in the shape of the library libgcc.a that is provided with the Gnu C compiler and implicitly included whenever a C program is linked. When such a library is used as an input to the final linking stage in building a program, the linker will include just those parts that are needed by the program being built: for example, a program that calls serial_init() will need the archive member serial.o, but not necessarily other ones. Packing the components of micro:bian in an archive file like this saves the effort of keeping track of which parts of micro:bian are needed for each program.

How many processes can a program contain?

The operating system has a table of processes with room for a limited number of entries; in the default setup, there is room for 32 processes, including the device driver processes that are started by calling serial_init or timer_init, but that number can be increased by editing the file microbian.c and recompiling. More serious is the restriction that the stack space for all processes must fit in the limit RAM space of the micro:bit. A space of 1kB is reserved for the operating system's own stack, and the global variables and the stack space for all processes must fit in the remaining RAM space – 14kB on the V1 micro:bit, 120kB or so on V2.

Using the standard stack space STACK of 1kB for each process would severely limit the number of processes, at least on V1. But most processes use far less that 1kB unless subroutines are deeply nested. It's possible to find out from a process dump how much peak stack space has actually been used by each process, then trim the allocations accordingly.

How many different priority levels does micro:bian support?

For ordinary processes, there are two levels, P_HIGH and P_LOW, with P_LOW the default. Soon we will introduce processes that connect to interrupt sources, and the operating system gives them the special priority P_INTERRUPT, higher still than P_HIGH. One special process, the idle process, is always present: it runs only when there is nothing else to do, and has the lowest priority of all, P_IDLE. Having only a few different priority levels makes it faster to select the highest priority process to run. A potential source of confusion is that, like the (quite separate) priority levels assigned to interrupts, the highest priority level is associated with the smallest number, so actually P_INTERRUPT = 0, P_HIGH = 1, P_LOW = 2 and P_IDLE = 3.

Why is the stack space of a micro:bian process filled with the value 3735928559 when the process starts?

This helps with finding out how much stack space the process is actually using: when micro:bian prints a dump of the process table, it shows how much of the stack space of the process has been changed from this initial value, and we can assume that this is the total stack space that has been used, unless by some slim chance the last few words of the stack have been set to this magic value by the process itself. As to the choice of value, it appears in the micro:bian source code in hexadecimal notation, which makes it seem more significant.

Does micro:bian have a preemptive or non-preemptive scheduler?

With a preemptive scheduler, a process that is running can be suspended by the operating system at any time in order to run another process, whereas with a non-preemptive scheduler, processes are suspended only when they request it by calling an operating system function such as yield(). In this sense, micro:bian is preemptive, because an interrupt from the timer or another I/O device can result in a process being suspended and a higher-priority process taking over.

What micro:bian does not have is the idea that processes otherwise equal in priority should get an equal share of processor time. If no interrupts happen, a running process will continue to run until it uses the send() or receive() system calls to exchange a message with others. Although most of our programs will include the timer module that establishes a regular timer interrupt, this is not required for micro:bian to work. If interrupts do happen, then at each interrupt the currently running process (if any) is suspended, and joins at the back a queue of processes waiting to run. This has the effect of letting each process run in turn if it is ready to do so, but does nothing to ensure that processes get to run for equal periods of time. Despite the apparent lack of fairness, this scheme works well for programs where most processes spend most of their time waiting for events, and only one process (like the primes process in this experiment) needs a substantial amount of CPU time.

Does that mean micro:bian is a tickless system?

The word tickless usually refers to a system where, despite their being a scheduler that uses a timer interrupt to mete out slices of CPU time to each process, when all processes are idle, the timer interrupt can be stopped and the CPU can go to sleep, potentially saving energy. This can be very important in remote, battery-powered systems, which may need to last for months or years on a single charge, waking only when there is real work to do. micro:bian is not tickless in this sense, because it does not deal in time slices at all.

What happens in micro:bian when there are no processes that want to run?

There is always a process that is ready to run, with a priority lower than any genuine process. This idle process sits in an infinite loop, repeatedly calling the function pause(), a synonym for the wait-for-event instruction wfe that halts the processor in a low power mode until the next interrupt event. If the timer module is active, there is an interrupt every 5 ms, so the processor does not sleep for long.