Aufgabe 7: Anwendung
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.
- Using threads and semaphores
- Applying more comprehensive libraries
- Having fun
Videos (in German)
This assignment is meant to be a playground for you. To assist you in writing an application of your choice, the handout provides a multitude of libraries and infrastructure, including:
- a simple random number generator
- a file system and
- a graphics mode However, you will have to implement a dynamic allocator in order to use the full functionality of the latter two.
Equipped with these components, we encourage you to write (or port) a simple game, a minimal shell or an office program.
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?). You can use the RTC as seed for a (ostensibly) more non-deterministic behaviour. But better avoid using Random for cryptography!
Dynamic Memory Allocator
Can you still remember writing a dynamic memory allocator during your undergraduate studies (Halde in Systemprogrammierung)? Well, the file system and parts of the graphics library (e.g. PNG) need one to work properly. A very basic implementation providing malloc() and free() is sufficient: A pre-allocated memory block [array] with the management of memory blocks done in a linked list. If you are keen (and have too much spare time), you can try to implement more sophisticated allocation strategies, like the buddy allocator, for example. However, you might want to check the correct behaviour in user space (easier than debugging in your kernel).
- For the graphics example, you have to ensure that the statically allocated memory is large enough (at least 16 MiB are required).
Having implemented the allocator, you can easily extend StuBS in such a way that it supports the C++ operators
delete: Just define
void *operator new(size_t) as a thin wrapper of malloc() (and extend
void operator delete(void *) to use free()) in
compiler/libcxx.cc – don't worry, it's just a one-liner!
Minix File System
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).
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/. In the CIP this is not as easy due to security concerns (and the lack of a working FUSE file system). A possible solution would be libguestfs, which works internally with a virtual machine and thus allows access to the file system.
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
You can provide the file system either using the ATA driver for (QEMU-) hard disks or via a temporary data carrier in main memory (e.g., the initrd).
While the second variant does not allow you to store changes persistently, it should nevertheless be used on the test hardware due to its easy deployment – 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:
A suitable graphics mode is already selected by the Multiboot-compatible boot loader. You can specify the desired attributes in the file
boot/multiboot/config.inc by setting
MULTIBOOT_VIDEO_MODE in the
MULTIBOOT_HEADER_FLAGS and adjusting
- 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
kernelparameter (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
-isoto the emulation targets, like
make kvm-iso. However, PXELinux used for the netboot is compatible and does not require any special handling.
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
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.
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 (based on uPNG) requires dynamic memory management.
- 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!
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:
Hall of Fame
Worthy solutions for this assignment from previous years can be found on the test hardware in the network boot menu entry Hall of Fame.
- Unfortunately, some of the old examples no longer work on out test computers due to the switch to the "new" test hardware (Intel Core i series, which is a bit more sensitive to the standard than the previous Intel Core 2 series). However, you can still run most of them in QEMU/KVM:
kvm -kernel /proj/i4bs/halloffame/13_schach.elf
You've created some amazing application? Please send them to us (preferably with source), and with a bit of luck it will soon be in the Hall of Fame as well!