Assignment 7: Application for StuBS

It is time to reap the rewards of your hard work during this semester. In this assigment, you implement an application of your choice. If possible, use several threads and synchronize them via semaphores.

Learning Objectives

  • Using threads and semaphores
  • Applying more comprehensive libraries
  • Having fun


This is exercise is meant to be a playground for you. Therefore, we provide you with a multitude of libraries and infrastructure that will assist you in writing an application. You are provided with a simple random number generator, a file system, a graphics mode, and a simple dynamic memory allocator. Equipped with these components, we encourage you to write a simple game, a minimal shell or an office program.

A short explanation of all additional components follows.

Random Number Generator

Random provides a pseudo-random number generator based on the Mersenne Twister. You have to initialize the instance with an initial value (a so called seed), and then it will return a new "random" number (32 bit) with every subsequent call to Random::number().

Instances with the same initial value will return the same sequence of numbers (not very random, right?). Without implementing a driver for the RTC, you have no proper source of randomness for the seed. Therefore, better avoid using Random for cryptography!

Dynamic Memory Allocator

Can you still remember writing a dynamic memory allocator during your undergraduate studies ? Well, the file system and parts of the graphics library (e.g. PNG) rely on a proper allocator for variable sized objects to work properly.

In order to lift the burden of implementing an allocator, you have already done enough this semester, we provide you with a simple buddy allocator that distribures a pre-allocated memory block [array]. The allocator provides you with malloc() and free() and lives in utils/alloc.h and utils/alloc_buddy.h.

Furthermore, we also extended the template to provide the C++ operators new and delete: Both are just thin wrappers around malloc() and free(). The implementation of this lives in compiler/

Minix File System

We provide you with a driver for Minix file systems. The "disk" for this driver is supplied by an initial ramdisk (initrd) that is loaded by the bootloader into memory.


The Minix (3) file system (extracted from Linux) may simplify your data management. Minix not only influenced the Linux kernel, but its file system also influenced the extended file system (you probably know or even use one of its successors ext2 and ext4).

The VFS offers you a POSIX-like interface (e.g., VFS::open() and VFS::read()) to access the contents.

Image Creation

You can easily create file system images using standard Linux tools. Here is an example that creates an image with a size of one megabyte:

dd if=/dev/zero of=~/file.img bs=1MiB count=1
mkfs.minix -3 /dev/loop0  # optional --inodes <number>

In order to add files to the image, you must mount it first, e.g. with mount ~/file.img /mnt/tmp/.

However, the utility in fs/tool uses the same file system code as StuBS to access an image directly – without requiring special privileges, you can copy and modify the files and folders with FTP-like commands.

To simplify things, we have already provided you an abstraction for building and executing the FSTool in your Makefile: it will automatically pack all files in the kernel folder ./initrd/ into a new initial ramdisk (stored in build/initrd.img), along with about one megabyte of free memory. You can change the directory location and the free memory (in bytes) using the Makefile variables ‘INITRD_DIR’ and ‘INITRD_FREE’ respectively.

Usage in StuBS

The data for the file system lives in the main memory in an initial ramdisk.

While using a proper disk drive (e.g. ATA) would allow us to make changes persistently, it is easier for this exercise to rely on transient memory. The StuBS Makefile is already able to transfer your image file as initial ramdisk to the test systems or load it in Qemu/KVM.

If you now want to use it in StuBS, you must first initialize the Ramdisk (with the memory address provided by the Multiboot information) as a block-oriented device before you can mount the actual file system:

#include "fs/ramdisk.h"
#include "fs/vfs.h"
// ...
void main() {
// ...
// Load the ramdisk (= the first module)
if (initrd == nullptr) {
kout << "No initial ramdisk - abort!" << endl;
Ramdisk ramdisk(initrd->getStartAddress(), initrd->getSize());
int error = VFS::mount("minix", &ramdisk, "");
if (error != 0) {
kout << "Error mounting ramdisk (minix): " << -error << endl;
// ...
// Open file with VFS::open() (or GuardedVFS::open() in an thread)
int fd = VFS::open("title.txt", O_RDONLY);
if (fd >= 0) {
char buffer[200];
int n = VFS::read(fd, buffer, sizeof(buffer) - 1);
buffer[n] = 0;
kout << buffer << endl;
Boot Module (also known as initrd = initial Ramdisk)
Definition: data.h:51
void * getStartAddress() const
Get start of this boot module.
Definition: data.h:61
size_t getSize() const
Get the size of this boot module.
Definition: data.h:75
static ssize_t read(int fd, void *buf, size_t count)
Lesen von einem Dateideskriptor fd in Speicher buf der Länge count. Siehe man 2 read.
static int mount(const char *fstype, BlockDevice *bdev, const void *data)
Siehe man 2 mount.
static int open(const char *pathname, int flags)
Öffnet und erstellt (je nach flags) Dateien. Siehe man 2 open.
Multiboot Interface
void die()
Permanently halts the core.
Definition: core.h:107
Module * getModule(unsigned i)
Retrieve a certain boot module.
OutputStream & endl(OutputStream &os)
Prints a newline character to the stream and issues a buffer flush.
int main()
Kernels main function.

Graphics Mode

Graphics provides you with a simple interface to the VESA BIOS Extensions, a basic graphics mode. However, if you want to use it, you will need to do a little work.


A suitable graphics mode is already selected by the Multiboot-compatible boot loader. You can specify the desired attributes in the file boot/multiboot/ by setting MULTIBOOT_VIDEO_MODE in the MULTIBOOT_HEADER_FLAGS and adjusting MULTIBOOT_VIDEO_WIDTH, MULTIBOOT_VIDEO_HEIGHT and MULTIBOOT_VIDEO_BITDEPTH.

If the desired mode is not available, a similar mode will be selected. Hence, you cannot rely completely on the exact screen resolution.
Qemu/KVM does not offer a real Multiboot compatible bootloader when started with the kernel parameter (which is used in the Makefile). Therefore, you have to create a full system image with an extra bootloader (e.g., Grub). This is already implemented in our Makefile. Just append -iso to the emulation targets, like make kvm-iso. However, PXELinux used for the netboot is compatible and does not require any special handling.

Similar to TextStream, you need a global instance of GuardedGraphics in your kernel, calling GuardedGraphics::init() during system initialization:

// enthält extern GuardedGraphics graphics;
void main() {
// ...
if (!graphics.init(true)) {
kout << "Not able to initialize Framebuffer - abort!" << endl;
// ...
bool init(bool force=false)
Initialize GraphicsPrinter according to the current video mode.
GuardedGraphics, a guarded interface for Graphics

Basic Usage

Additionally to initializing the graphics card's framebuffer, the example code above reserves two memory areas for double buffering:

  • The front buffer contains a full screen image ready to be displayed
  • Drawing operations are performed on the back buffer

The provided graphics primitives allow drawing lines and rectangles, output of text (like demonstrated in the example Title ) with different fonts and direct pixel manipulation (see example Fire).

After you have finished all drawing operations on the back buffer, call Graphics::switchBuffers() to atomically exchange both buffers: the back buffer will become the new front buffer and vice versa.

With Graphics::scanoutFrontbuffer() the contents of the front buffer are copied into the video memory. You can either call this method as part of the drawing loop whenever a new frame has been finished, or you can execute it in Watch::epilogue(), which ensures that the graphics card's frame buffer is updated at a fixed frequency. The GraphicsExample uses the second variant.

Since the scanout is quite expensive, you should not execute it on every timer interrupt – it would cause a very high system load. A refresh every 20ms (corresponds to a maximum of 50 frames per second) is a good compromise between the frame rate and the overhead caused by the copy operations. Since your timer interrupt will usually occur every millisecond, you should perform the scanout only every twentieth epilogue. The PC example will measure and display the current refresh rate using a frame buffer console.

Minimal Working Example

After initializing the graphics subsystem, you can just use the following code to print a moving "Hello":

void main() {
Color fg(0x33, 0x88, 0xcc);
int x = 0;
while(1) {
graphics.text({.x=230+x, .y=10+x}, "Hallo", 5, fg);
x = (x + 1) % 20;
void text(const Point &p, const char *string, unsigned len, const Color &color, const Font *font=nullptr)
Print text (without automatic word wrap) on the current back buffer.
Definition: graphics.h:202
void clear()
Clear all pixel of the current back buffer (set full screen to black)
Definition: graphics.h:111
void scanoutFrontbuffer()
Copy current front buffer to the video memory.
Definition: guarded_graphics.h:40
bool switchBuffers()
Switch front and back buffer (only if front buffer was already copied to video memory)
Definition: guarded_graphics.h:27

Example Application

We also ship with a larger example application in user/graphic/example.h. In order to activate that, create an appropriate thread object and hand it to the scheduler.

#include "user/graphic/example.h"
void main() {
GraphicsExample * graphicsExample = new GraphicsExample();
void ready(Thread *that)
Include a thread in scheduling decisions.
For this application it is required to GuardedGraphics::scanoutFrontbuffer() periodically. Most probably you want to place it in the Watch::epilogue().


If you want to include your own images like demonstrated in the Pong example, open/draw them in GIMP and export them as C source code (*.c). You should not use glib types. The resulting .c file contains the corresponding binary data in a struct (this structure is identical to GIMP), which can be displayed using the image method.

Embedding bitmaps directly in the source code can considerably increase the size of the resulting system image.

Portable Network Graphics

Using lossless compressed PNG files might solve problems of large binary files.

The library only supports RGB and grayscale images (with and without alpha channel) – but not images with a custom color palette.

You can either include the image as a static data array in C source code using xxd -i image.png > image.c, or you can simply use the file system by storing the PNG image at ./initrd/image.png, while using /image.png as path for a new PNG object in StuBS.

Since unpacking compressed images is resource-intensive, make sure you have enough memory – both stack and heap!

The methods provided by the graphics library also support sprite sheets, which can be used for animations (see example Cat)


Since the messages written to the CGA TextMode are no longer visible on the screen after switching to the Graphics mode, it might be a good idea to redirect the debug output via the serial connection. It is quite easy to modify the existing DBG macro accordingly after replacing dout with a global SerialStream instance:

Console (VT100 compatible) via Serial interface.
Definition: serialstream.h:23
TextStream dout[Core::MAX]
Debug window for the CGA screen.
Serial output stream