Project: a tiny robot operating system

Share the robot between three tasks with round robin, drive it through device drivers, and stop the patrol with an interrupt.

A10.9Operating systems, software and translatorsA level50 min

BugBot has several jobs to do at once: patrol the room, show its status on the LED, and play a tune, all while watching for walls. One processor has to do all of them. In this project you build the core of an operating system that makes that possible: a round-robin scheduler that shares the processor between tasks, device drivers that carry out each step, and an interrupt from the distance sensor that stops the patrol before it hits the wall.

The brief

Three tasks are each a list of steps. A step is a (command, value) pair: ("forward", cm), ("led", colour) or ("tone", hertz).

• The scheduler runs the tasks round robin, with a time slice of 2 steps: take the task at the front of the queue, run up to 2 of its steps, then put it at the back of the queue if it has steps left, or print <name> finished if it has none.
• Every step is carried out through a driver table, and printed as <name>: <command> <value>.
• After every step, whichever task ran it, the OS checks for the obstacle interrupt: if the patrol has not already been stopped and distance() is less than 25 cm, the handler prints interrupt: obstacle, plays 220 Hz for 0.2 seconds, stops the patrol task and prints patrol stopped. A stopped task gets no more steps, is never put back on the queue, and never prints finished.

Decompose it

tiny robot OS
├── drivers            {"forward": ..., "led": ..., "tone": ...}, one function per device
├── the ready queue    task names, front of the list runs next
├── the scheduler      take from the front, run a time slice, requeue or finish
└── the interrupt      checked after every step: obstacle -> stop the patrol

This is the same structure as a real operating system, shrunk down. The drivers are A10.2, the scheduler is A10.5, and the check after every step is the check at the end of every fetch-decode-execute cycle from A10.4.

Step 1: the drivers

Each driver takes one value and knows how to make its device do it. Nothing else in the program calls forward, led or tone directly.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def motor_driver(cm):
    forward(50, distance=cm)

def led_driver(colour):
    led(colour)

def piezo_driver(hz):
    tone(hz, 0.2)

drivers = {"forward": motor_driver, "led": led_driver, "tone": piezo_driver}

for command, value in [("led", "purple"), ("tone", 440), ("forward", 5)]:
    drivers[command](value)
    print(command, value, "done")

Run this in the simulator

Step 2: plan the trace before you code

A scheduler is easy to get subtly wrong, so work out by hand what should happen, then make the program match. The tasks are a patrol of four 10 cm drives towards a wall, three LED colours, and three notes. The robot starts 51 cm from the wall, so after each drive the sensor reads about 41, 31, 20 and 11 cm.

Notice two things. In slice 4 the interrupt ends the patrol's slice early, even though it had a step and a slot left. And in slices 5 and 6 the distance is still under 25 cm, but the interrupt must not fire again, because the patrol has already been stopped.

Step 3: the scheduler without the interrupt

Get round robin working first, with no interrupt. Keep each task's remaining steps in a dictionary, and the queue as a list of names:

jobs = {}
queue = []
for name, steps in tasks:
    jobs[name] = list(steps)
    queue.append(name)

while queue:
    name = queue.pop(0)
    ...

Without the interrupt, the patrol runs all four drives and hits the wall, so test this step on its own with the wall in mind, or temporarily make the patrol shorter.

Step 4: add the interrupt

Add the check after every step. It needs to remember whether the patrol has been stopped, to stop the patrol whichever task is running, and to make sure a stopped task is not put back on the queue.

Test plan

Task: a tiny robot OS

Build the operating system from the brief. The inputs are:

• tasks, a list of (name, steps) tuples in their starting queue order, where steps is a list of (command, value) pairs; command is "forward" (value: cm, a positive integer), "led" (value: a colour name) or "tone" (value: hertz, 100 to 10000);
• TIME_SLICE, the most steps a task runs before the next task starts (2);
• SAFE_CM, the interrupt threshold: the obstacle interrupt fires when distance() is less than this (25).

Write a drivers dictionary with a driver for each command: "forward" drives forward at speed 50, "led" sets the LED colour, and "tone" plays the note for 0.2 seconds. Run every step through drivers. Print exactly these lines, built from your variables: <name>: <command> <value> after each step, interrupt: obstacle and patrol stopped from the handler (with the 220 Hz, 0.2 second tone between them), and <name> finished when a task runs its last step. The wall is 51 cm ahead of the robot.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tasks = [
    ("patrol", [("forward", 10), ("forward", 10), ("forward", 10), ("forward", 10)]),
    ("lights", [("led", "blue"), ("led", "yellow"), ("led", "green")]),
    ("music", [("tone", 523), ("tone", 659), ("tone", 784)]),
]
TIME_SLICE = 2
SAFE_CM = 25

Challenges

1. Change TIME_SLICE to 1 and then to 4. Predict the order of the lines each time, then check. Does the slice change how close the patrol gets to the wall? Explain why.
2. Give each task a priority and replace round robin with a priority scheduler. Can a low-priority task starve?
3. Add a second interrupt, low battery, with a higher priority than the obstacle. What should happen if both are raised after the same step?