Any sufficiently large program eventually becomes an operating system.
This coursework focuses on development of an operating system kernel. The practical nature of this task is important from an educational perspective: it should offer a) deeper understanding of various topics covered in theory alone, and transferable experience applicable when you either b) develop software whose effectiveness and efficiency depend on detailed understanding how it interacts with hardware and/or a kernel, or c) develop software for a platform that lacks a kernel yet still requires run-time support of some kind (that you must therefore offer). The constituent stages offer a variety of options, in attempt to cater for differing levels of interest in the topic as a whole. In particular, note that they offer an initially low barrier to entry for what is obviously a challenging task when considered as a whole.
The assignment description may refer to marksheet.txt. Download this ASCII text file, then complete and include it in your submission: this is important, and failure to do so may result in a loss of marks.
The coursework design includes two heavily supported, closed initial stages which reflect a lower mark, and one totally unsupported, open final stage which reflects a higher mark. This suggests the marking scale is non-linear: it is clearly easier to obtain X marks in the initial stages than in the final stage.
The terms open and closed should be read as meaning flexibility wrt. options for work, not openendedness wrt. workload: each stage has clear success criteria that should limit the functionality you implement, meaning you can (and should) stop work once they have been satisfied.
Perhaps more so than other assignments, this one has a large design space of possible approaches for each stage. Part of the challenge, therefore, is to think about and understand which approach to take: this is not purely a programming exercise st. implementing an approach (elsewhere perhaps even prescribed in the description) is enough. Such decisions should ideally be based on a reasoned argument formed via your own background research (rather than reliance on the teaching material alone).
Since the overarching goal of the assessment process is to reward better solutions (within indicative weights assigned to each stage), you can interpret “better” as meaning a) higher quality (e.g., functionality whose implementation is more robust or complete), and/or b) more realistic (e.g., functionality that more closely models a real kernel). Keep in mind that wrt. the latter, and in line with the associated worksheets, justified simplifications will sometimes make sense if they allow progress toward a more limited or partial solution.
You should submit your work via the SAFE submission system including all source code, written solutions and any auxiliary files you think are important (e.g., any example input or output).
Your submission will be assessed in a 20 minute viva (meaning oral exam). By the stated submission deadline, select a viva slot online to suit your schedule. Note that:
- The viva will be based on your submission via SAFE: you will need to know your candidate number1 so this can be downloaded.
Your submission will be marked using a platform equivalent to the CS lab. (MVB-2.11). As a result, it must compile, execute and be thoroughly tested against default operating system and development tool-chain versions available.
The discussion will focus on demonstration and explanation of your solution wrt. the stated success criteria. Keeping this in mind, it is essential you have a simple, clear way to execute and demonstrate your work. Ideally, you will be able to a) use one (or very few) command(s) to build a kernel image (e.g., using a script or Makefile), then b) demonstrate that a given success criteria has been met by discussing appropriate diagnostic output. Any significant editing and/or recompilation of the solution during the viva is strongly discouraged, as are multi-part solutions (e.g., use of separately compiled source code for each stage).
Immediate personal feedback will be offered verbally, with a general, written marking report released at the same time as the marks.
Download and unarchive the file somewhere secure within your file system (e.g., in the Private sub-directory in your home directory). The content and structure of this archive, as illustrated in Figure 1, should be familiar: it closely matches that used by the lab. worksheets, and thus represents a skeleton starting point for your submission.
There are two extra (sub-)Makefile are provided: these relate to Appendix A and Appendix B, effectively automating associated commands, and are introduced at the appropriate point below.
The extra files disk.[ch] and disk.py also relate to Appendix B, but are only relevant for one option within the final stage.
In combination, image.ld, lolevel.[sh] and int.[sh] implement a interrupt handling skeleton for the reset, SVC and IRQ interrupts: it is analogous to worksheet #2, with each low-level interrupt handler function invoking an associated high-level, empty placeholder in hilevel.[ch].
The overarching goal of this assignment is to develop an initially simple but then increasingly capable operating system kernel. It should execute and thus manage resources on a specific ARM-based target platform, namely a RealView Platform Baseboard for Cortex-A8  emulated by QEMU2 . The capabilities of said platform suggest a remit for the kernel, or, equivalently, a motivating context: if and when it makes sense to do so, imagine the platform and kernel form an embedded, consumer electronics product (e.g., set-top box3 or media center).
This stage is designed to match the task in lab. worksheet #4: you should implement a simple, functioning operating system kernel that supports pre-emptive multi-tasking (for some fixed number of user processes stemming from statically linked programs).
Success criteria. Initialise the kernel so that the three user programs P3, P4 and P5 are automatically executed, and then demonstrate their concurrent execution.
This stage involves the design and implementation of some standard improvements to the starting point above. Initialise the kernel so that only the console user program (an overview of which is given in Appendix A) is executed automatically: this will allow you to interact with the kernel via a command-line shell4 , and thus, with appropriate alterations, control each (sub-)stage.
(a) The kernel developed in the lab. worksheet(s) assumed a fixed number of user processes exist. Improve on this by supporting dynamic5 creation and termination of processes via fork, exec and exit system calls. Since you design the semantics of these system calls, any reasoned simplifications are allowed provided they support the desired functionality: fork could be simpler than in POSIX [2, Page 881], for example.
Success criteria. Altering the provided user programs where appropriate, demonstrate the dynamic creation and termination of some user processes (i.e., correct behaviour of the underlying fork, exec and exit system calls) via appropriate use of the console.
(b) The kernel developed in the lab. worksheet(s) used a special-purpose scheduling algorithm: it could do so as the result of assuming a fixed number of user processes exist. Improve on this by implementing an alternative; you can select or design an algorithm, but it must be able to capitalise on the concept of priorities somehow.
Success criteria. Demonstrate the differing behaviour of your implementation vs. round-robin scheduling (as implemented in the same kernel), and explain when and why this represents an improvement.
(c) The kernel developed in the lab. worksheet(s) lacked any mechanism for Inter-Process Communication (IPC). The first half of the unit introduced various ways to support the concept of IPC: implement one of them in the kernel.
Success criteria. Develop a new user program which uses your IPC mechanism to solve the dining philosophers6 problem: upon execution, it should first use fork to spawn 16 new “philosopher child processes” which then interact with each other via IPC. Demonstrate execution of this new program from the console, and explain how the solution a) ensures mutual exclusion and b) prevents starvation.
This stage includes several diverse, more challenging options which you can select between. Keep in mind that a) you should only attempt this stage having first completed each previous (sub-)stage, and b) per marksheet.txt, you select and submit one option only: if you submit more, only the option with the highest mark will be considered wrt. assessment.
- (a) As shown in worksheet #1, the PB-A8 represents a complete computer system. As such, an ambitious but realistic goal is to investigate various devices not utilised thus far. For example, either:
- i. Success criteria. Demonstrate use of the MMU to a) prevent access by one process into an address space allocated to the kernel or another process, and b) offer some degree of memory virtualisation (i.e., a uniform address space per process).
- ii. Success criteria. Demonstrate a) management of the LCD and PS/2 controllers within an appropriate device driver framework, and b) implementation of an improved UI vs. interaction via the QEMU terminal and hence command-line shell: this could be achieved either with a user- or kernel-space window manager, for example, however simple.
- (b) In contrast to investigating one of the various real, albeit emulated devices supported by the PB-A8, we could consider a compromise: for certain cases we could consider a simplified device instead, and therefore focus on higher-level use rather than low-level detail of the device itself. Appendix B outlines the source code provided in order to support such a case. The goal is to use a simplified disk, which offers block-based storage of data, to implement a file system: ideally this will a) implement a UNIX-like, inode-based data structure, allowing some form of directory hierarchy, and b) support a suite of system calls such as open, close, read and write, with semantics of your own design, which, in turn, demand management of file descriptors.
Success criteria. Demonstrate either a) two new user programs which model the cat and wc tools (i.e., the ability to write data into a new file, or append to an existing file, then count the lines etc. in it), and/or b) the kernel dynamically loading a user program from the disk then executing it (vs. using one of the statically compiled user programs, as assumed above).
- (c) Originally, emulation of the PB-A8 was motivated by a need to a) reduce the challenge of software development, and b) address the issue of scale when used in the context of the unit. That said, investigation of a physical alternative such the RaspberryPi7 can be a rewarding exercise. So, provided you are willing to accept the associated and significant challenges, the goal is to port your existing kernel and have it execute on such a platform.
Success criteria. Demonstrate the kernel executing on whatever physical target platform you select, and, ideally, utilising board-specific devices available.
Consider the diagram below: development platform target platform
Although the terms are often conflated, is is common to define a console as a (command-line) terminal specific to local, kernel-mode interaction; this contrasts with a more general terminal, where interaction a) can often be remote (e.g., over a network), and b) is related to user-mode login. The mechanism used to implement a console differs system-by-system, but in embedded contexts, use of a UART is not uncommon: a RaspberryPi, for example, has such a console by default. In fact, the lab. worksheet(s), we already made extensive use of this model: QEMU was configured st. an emulated UART (namely the PL011_t instance UART0) is associated with the emulation terminal: this meant the kernel could read and write input and output, and hence interact with the user. However, QEMU is more flexible than this. It also supports association between an emulated UART and a network port; reading or writing bytes to or from the UART thus implies receiving or transmitting them across the network.
This is essentially what the diagram shows. A user program implementing the console (i.e., console.[ch]) executes under control of the kernel, using the PL011_t instance UART1. This is associated with a network port, allowing a connection from a terminal emulator executing on the development platform: the net result could be viewed as roughly analogous to a command-line terminal resulting from (remote) login to snowy.cs.bris. ac.uk using SSH.
The approach outlined above is not a radical simplification at all. In fact, the only significant difference vs. a real kernel is direct use of UART1 by the console implementation: this would obviously need to be managed, by the kernel, via a device driver in reality. The major advantage of this minor simplification is the fact that console I/O can be segregated from I/O by other user programs. This is important, in so far as it offers a clearer interactive interface with the kernel. Put simply, the alternative of interleaving all I/O can be confusing and therefore hinder progress wrt. the core ILOs.
Note that Makefile.console extends the vanilla Makefile provided with variables and build targets related to use of the console. We explain how to do so directly below, but keep in mind that, as a result, the same steps can and perhaps should be automated.
- Ensure the line in Makefile that reads
QEMU_UART += telnet:127.0.0.1:1235,server
is uncommented, then launch QEMU as normal in one terminal: this instructs QEMU to associate the
PL011_t instance UART1 with the network port 1235. Note that QEMU will initially wait for a connection to be made via said port, indicated by a message similar to
QEMU waiting for connection on: disconnected:telnet:127.0.0.1:1235,server
- Issue the command nc
in another terminal we refer to as the console terminal.
- Once you execute the kernel (e.g., issue a continue command to gdb), the console terminal should show a command prompt (assuming the kernel has automatically executed the associated user process): by typing commands into the console terminal, you can interact with the console and hence the kernel.
The lower part of the diagram illustrates components that exists on the development platform:
disk.bin models the disk mechanism: it stores the disk content as a sequence of bytes as a so-called disk image. This is a standard file, in so far it is stored on the standard file system available via the development platform.
disk.py models the disk controller: it acts as an interface, accepting high-level commands that it satisfies at a low level using the underlying disk mechanism. When executed, the controller will connect to and communicates via a network port. Note it imposes structure on the disk content, so rather than a “flat” sequence of bytes it is interpreted as some number of blocks of a given length.
The upper part of the diagram illustrates components that exists on the target platform, which in this case is represented by QEMU (and so is, in turn, executing on the development platform). As was the case in Appendix A, we capitalise on the ability to form an association between emulated UART and network port: by connecting the disk controller to the same port, we allow the kernel image and disk controller to communicate. disk.[ch] includes a set of high-level functions the kernel can call; you could view this source code as a primitive form of device driver, which acts as an abstraction of the communication protocol.
Hopefully it is obvious that the approach outlined above is not how a real disk would be connected to a real computer system like the PB-A8! Likewise, the communication protocol used has, at best, a limited relationship with a real analogy such as SCSI8 .
As a result, it is fair to question whether the approach represents a reasonable or useful simplification of reality. The answer is basically that it offers a compromise. That is, what it lacks wrt. realism, it gains in allowing a focus on high(er)-level ILOs: with a simplified low-level, block-based storage medium you can focus on high-level design and implementation of a file system without complicating detail that would exist otherwise. In particular, the approach allows a) inspection and manipulation of the disk state using more familiar and “trusted” tools on the development platform, and/or b) manual interaction with the disk controller in order to test and verify behaviour of a command (you can type a command, and then inspect the response).
Used correctly, both can make the implementation challenge vastly easier.
Creation of an initial, empty disk image is simple. For example, by issuing the command dd of=disk.bin if=/dev/zero count=1048576 bs=1 we instruct dd to copy 1048576Bs from the input file /dev/zero to the output file disk.bin. Given that reading from /dev/zero will always produce a sequence of zero bytes (i.e., whose value is 00(16) ), this will create a 1MiB file disk.bin that is entirely zero bytes. Note that:
Although the use of dd initialises the disk image via 1048576 blocks each of 1B, the disk controller using said image must select a block length of more than 1B: not doing so basically means this is not a block device, and masks many inherent issues.
Beyond this restriction, the total capacity should equal the product of whatever block count and length you opt for. For example, you could opt for more, shorter blocks st. 65536 16B = 1MiB or for fewer, longer blocks st. 256 4096B = 1MiB to suit: both result in the same capacity, but imply that the controller will interpret the underlying sequence of bytes in a different way.
You can inspect the byte-by-byte file content using the command
hexdump -C disk.bin
Initially, however, it will produce somewhat limited output: the repeated zero bytes are printed in a “compressed” form, rather than in their entirety.
Note that Makefile.disk extends the vanilla Makefile provided with variables and build targets related to use of the disk. We explain how to do so directly below, but keep in mind that, as a result, the same steps can and perhaps should be automated. Also note disk.py has an optional –debug flag, which causes it to emit extra debugging information: this can be useful if/when use of it fails to behave as you expect.
The communication protocol used by the disk controller is, by design, very simple: it receives a command then transmits a response where
- each command and response is 1-line of ASCII text terminated by an EOL character,
- each such line is comprised of some number of fields separated by space characters,
- each field is a sequence of bytes, represented in hexadecimal; the bytes are presented so when read left-to-right, the 0-th byte (resp. (n 1)-th byte) is toward the left (resp. right) of the field, and
- the first field of each command or response is a 1-byte code which identifies the type (e.g., distinguishes between a write command vs. a read command, or success vs. failure response).