Project ideas
Please come and talk to me about any of these projects, or about a project idea of your own along the same lines. The projects are quite open-ended, so they would suit either a third year or fourth year undergraduates or MSc students, with suitable adjustments to the length and depth.
micro:bian is a very small embedded operating system that is used in the first year course on Digital Systems. At present, it runs on the ARM-based microcontroller on the BBC micro:bit board, but it would be good to port it to other boards and other processors.
Unlike most other embedded operating systems, micro:bian provides process synchronization based on message passing, with interrutps converted into messages at the lowest level in the system. This encourages a style of programming where maximum advantage is made of concurrent processes, with minimum use of shared variables. The design is inspired by Andrew Tanenbaum's operating system Minix, an implementation of the Unix system call interface that uses message passing inside.
At present, micro:bian is specific to the BBC micro:bit. But plenty of other inexpensive ARM-based development boards exist, such as the Freescale FRDM-KL25Z and FRDM-K64F boards, and many other boards that are part of the MBED ecosystem.
The aim of these projects is to port micro:bian to one or more of these other boards, identifying and isolating the parts that are board-specific and providing multiple implementations of device driver processes so that micro:bian applications are as far as possible portable between boards. In addition, we would like to support a wider range of peripherals and communication methods, such as USB or Bluetooth: for complicated protocols like these, a good way forward would be to obtains an open-source software stack and modify it to work with micro:bian.
Microcontroller development boards are divided into what I call "one-chip" and "two-chip" boards. On a two-chip board like the micro:bit, there are two microcontrollers: one that we program, and another microcontroller with fixed firmware that looks after USB communication, and is able to program the first chip using its debugging interface. The second chip also acts as a serial-to-USB adapter for the serial port on the main chip. The micro:bit and the Freescale boards are like this.
On a one-chip board, there is no such second microcontroller, and the main chip contains bootloader firmware. These boards can be programmed over USB using the bootloader, or by using a separate debug probe (which probably contains an ARM-based microcontroller of its own). For a serial interface, you can either use a separate USB-to-serial adapter connected to the UART pins on the board, or include a USB driver in the firmware.
Other boards don't have the switches and lights of the micro:bit but some, including the FRDM boards, support Arduino-compatible add-on 'shield' boards, and we could easily make a shield that replicates the features of the micro:bit.
Porting micro:bian to new boards
Port micro:bian to an ARM-based microcontroller other than the Nordic chips and to boards other than the micro:bit. This implies adapting the micro:bian microkernel to the features of the other chip core, and writing device drivers for the peripherals, beginning with the serial port. For one-chip boards, it's probably best to begin by using an external USB-to-serial adapter.
Adding timeouts to micro:bian
For some of the tasks that follow, it will help to add a new form of the receive system call that provides a timeout. This does express something that can't be done with a timer process and ordinary receive. That's because it isn't possible to cancel an alarm call from the timer process without risk of deadlock: if the client process decides to cancel the alarm call at the same time the timer process decides to deliver it, then they are stuck in a deadly embrace, each refusing to receive a message the other is committed to sending. Moving the timeout into the kernel allows it to be cancelled automatically when the receive completes.
A suitable API will allow micro:bian to continue to function without a timer process, but allows a timer process to be installed and, via a special system call, to inform the kernel of the passage of time.
USB for micro:bian
Simple, portable libraries exist that implement USB communications on microcontrollers, and some of them claim to be adaptable to multiple real-time operating systems. Choose one of them and incorporate it into micro:bian, adapting the OS interface to fit in with the message-passing style of concurrency. For a feasibility study, it's not necessary to implement every kind of USB device – a simulated serial port is enough. For additional hints, https://github.com/Spivoxity/avr-usb has examples of simple USB devices implemented with bit-banging on ATtiny microcontrollers, using a freely available USB library.
Bluetooth for micro:bian
A module already exists that implements radio communication using a proprietary on-air protocol that is shared with the standard micro:bit firmware. Open source implementations of the Bluetooth Low Energy protocol also exist, for example as part of Apache MyNewt. Port one of these to work with micro:bian. [The Nordic proprietary softdevice or 'blob' is not likely to help us much with this, being oblivious to any operating system.]
SD card storage for micro:bian
The interface for SD cards is a variant of SPI, and they have a well-documented protocol. Implement a block storage service that uses this interface, and on top of it a file system, choosing either the MS-DOS disk format or the one used by Minix, either of which will allow the cards to be mounted on a Linux host. Open source implementations of the MS-DOS file system exist in the Arduino world as a guide.
Fast micro:bian context switch with floating point
At present, the context-switch code in micro:bian does not save and restore the floating point registers on chips that have them. That means client programs cannot use the floating point unit, or more accurately, that at most one thread can use it. ARM provide a method, documented [somewhere] that allows for lazy saving of the floating-point registers. At the least, the kernel should save the floating point state for a process only if it has used the floating point unit; but better than that, it's possible to exploit the hardware to save the floating point state only if some other process wants to use floating point. This makes for efficient treatment of interrupts: if the device driver process doesn't use floating point, then there is not need to save the floating point registers when control passes from a background process to the driver, or to restore them when control returns to the background process.
Multiprocessor micro:bian
The RP2040 chip on the Raspberry Pi Pico board has two Cortex-M0 cores. Make micro:bian run on the two cores symmetrically, using spinlocks to provide mutual exclusion for the kernel.
micro:bian under pthreads
Unix provides libraries that allow processes to consist of multiple threads in the same address space. For development, simulation and debugging, it is desirable to have an implementation of the micro:bian API on top of such a library, so that concurrent micro:bian programs can run on a host computer. There's a lab exercise for an ancient operating systems course that exploits this idea.
Handy links
- Concise documentation of the micro:bian API.
- A page about context switch for the Cortex-M3.
- Datasheet and reference manual for the FRDM-KL25Z.
- An app note about interrupt-driven I2C in Kinetis microcontrollers.
- The truth about timing for neopixels.
A fast portable grep
A classic paper by Ken Thompson describes a translation of regular expressions into nondeterministic finite automata, with the transition functions of the automota represented as dynamically generated machine code for the IBM 7090 computer. The aim of this project is to recreate Thompson's presentation using a more recent JIT framework called Thunder, yielding a fast implementation of the grep utility for pattern matching in files. Another page has more details and hints.
Better register allocation
The compiler we currently study in the last part of the Compilers course allocates registers greedily during the instruction selection phase. Even on the ARM, this can lead to unnecessary register-to-register moves, but a variant of the compiler for AMD64 suffers from the problem more severely.
The goal of this project is to implement a better register allocation scheme that operates as a separate pass after instruction selection. The pass will work from an explicit representation of the instruction sequence without assigned registers, and will be able to take into account move instructions marked in the instruction sequence, wherever possible assigning the same register to both the source and target of the move, so that the instruction itself can be eliminated.
Source material for the project can be found in the book, A retargetable C compiler by Fraser and Hanson, and in articles referenced in that book.