UG3 Operating Systems

Practical Coursework

1 Introduction

The goal of the Operating Systems practical coursework is to implement important function￾ality in an existing research operating system called InfOS. The coursework counts for 30% of

the total course mark, and is marked out of a total of 100.

The coursework is split into three main tasks:

• Task 1: Implement a process scheduler. [10 marks]

(due Thursday 30th January 2020 at 4pm GMT—Week 3)

• Task 2: Implement a page-based memory allocator. [60 marks]

(due Thursday 5th March 2020 at 4pm GMT—Week 7)

• Task 3: Implement a device driver for a real-time clock. [30 marks]

(due Thursday 19th March 2020 at 4pm GMT—Week 9)

You may start any of the tasks as early as you wish, but you MUST submit each task before

their respective deadline. Coursework submitted after these deadlines may still be marked (at

the discretion of the marker), but will attract a score of zero.

The submission mechanism will be electronic, using the standard DICE submit command. No

other form of submission will be accepted.

1.1 Background

The research operating system that is the subject of this coursework is called InfOS and has

been developed specifically for this course. It is a 64-bit x86 operating that has been written

from scratch in C++, and is not based on any other particular OS.

InfOS is structured as a monolithic kernel, similar to Linux, but as it is written in C++, it

employs object-oriented principles in its implementation. It is not a Unix-like system, and does

not subscribe to the POSIX standards. It is modular in the sense that functionality can be

plugged in/out at compile time, but does not currently support dynamically loadable kernel

modules.

1

1.2 Necessary Skills

This coursework involves programming in C++, so familiarity with object oriented programming

and the C++ programming language will be very helpful. You should also take this as an

opportunity to expand your C++ programming skills.

The coursework tasks are designed to follow the syllabus, so it is essential that you keep up-to￾date with the course content.

1.3 Overview

For each task, you will be implementing a piece of core operating system functionality to be

loaded into the InfOS kernel. To ensure that each task is mutually exclusive, and that your

implementations do not predjudice each other, InfOS is shipped with basic implementations

already built-in. This means that InfOS will boot unmodified, and you can work on each task

separately, without worrying that one implementation might affect another.

1.3.1 Development Environment

You are encouraged to develop your coursework on DICE, as this is the only supported platform.

Questions about the development environment will only be answered for this set-up. Once

you have acquired the InfOS source-code, you can load it into an IDE such as NetBeans or

Eclipse.

If you want to work remotely, you can use the Informatics Remote Desktop Service to access a

remote DICE desktop. See the following website for details:

http://computing.help.inf.ed.ac.uk/remote-desktop

See Section 2.2.1 for information on setting up the correct version of the tool chain.

1.3.2 Testing

To test the operating system, Qemu will be used as an emulator. Qemu is a virtualisation

environment that can be used to boot real operating systems in a virtual machine. It is installed

on DICE and has been tested with the version of InfOS that you will be using.

Helper scripts are provided to quickly compile and run InfOS in Qemu. See the individual

tasks for more details.

2 InfOS

2.1 Introduction

InfOS is a new research operating system, developed from scratch by Tom Spink. It is a 64-bit

x86 operating system, designed in C++ to promote readability and use of familiar object￾oriented programming paradigms.

InfOS was developed because modern versions of the Linux kernel are incredibly complex,

and contain highly optimised implementations of core operating system operations, such as the

2

process scheduler and memory allocator. It is not feasible to understand the entirety of the Linux

kernel, nor is it feasible to re-implement core functionality without a significant understanding

of the kernel architecture. InfOS tackles this problem by providing well-defined interfaces for

these subsystems, and providing a “pluggable” architecture that enables swapping different

algorithms in and out.

2.2 Source Code

A fully booting version of the InfOS kernel, along with the associated user-space is available

in a public git repository, which lives here:

https://github.com/tspink/infos

https://github.com/tspink/infos-user

2.2.1 DICE Environment

When logged into a DICE machine, you must issue the following command before attempting

to build the operating system:

$ scl enable devtoolset-7 bash

This will ensure you are using an up-to-date version of the C++ compiler on the DICE platform.

If you are compiling this yourself, you must ensure you are using a compiler that supports at

least the -std=gnu++17 command-line option.

2.2.2 Source Code Environment

To assist in preparing the environment for your coursework, a helper script has been provided

that will create a new directory, clone the necessary repositories into it and copy in skeleton

files for the coursework tasks. To run this script, open a new terminal and from your home

directory execute the following command:

$ /afs/inf.ed.ac.uk/group/teaching/cs3/os/prepare-coursework.sh

This command will create a new directory called os-coursework in your home directory, and

clone the necessary repositories into it. It will also copy helper scripts into this directory that

are useful for building and running the kernel in the Qemu emulator.

This command also copies the skeleton files for each task into the os-coursework/coursework

subdirectory, which is where you will implement your algorithms. See the individual task

descriptions for further details.

This command does not issue the environment change command described above (2.2.1). You

must issue this command manually, if required.

To try out InfOS, change into the new os-coursework directory and run the build-and-run.sh

script:

$ cd $HOME/os-coursework

$ ./build-and-run.sh

3

The InfOS kernel will be compiled, followed by the userspace disk image, and then Qemu

will start booting the kernel. A lot of information will appear on your terminal, and a Qemu

graphics window will appear, where you can begin interacting with the shell.

2.2.3 Coursework Skeletons

You are provided with skeleton implementations for each coursework task, which are automat￾ically compiled by the InfOS build system when you use the build.sh or build-and-run.sh

scripts. This means that to complete your coursework, you simply need make modifications to

the skeletons in the os-coursework/coursework directory.

However, if you find that you’ve made a serious mistake and wish to start again, then read￾only copies of the skeleton have been copied into the os-coursework/coursework-skeletons

directory for you. You can then use these originals to restore the skeleton in whole or in

part.

2.2.4 Structure and Implementation

The top-level directory structure (which you will find in the $HOME/os-coursework/infos

directory) has the following directories, each loosely representing a major subsystem of the

InfOS kernel:

• arch/ Architecture-specific code.

• drivers/ Device drivers.

• fs/ File-system drivers and VFS subsystem.

• kernel/ Core kernel routines.

• mm/ Memory management subsystem.

• util/ Utility functions.

There are also some directories that contain support files:

• build/ Build system support files.

• include/ C++ header files (following the source-code structure)

• out/ Kernel build output directory.

InfOS is written in C++, and so all source-code files have the extension .cpp. However, due

to the low-level nature of operating system development, some code is written in x86 assembly

language. Being architecture specific, these files primarily live in the arch/x86 directory, and

have the extension .S.

Nearly every C++ source-code file has an associated header file (although there are some

exceptions), which exists under the include/ directory. The structure of the include directory

follows that of the top-level source-code directory, except the header files have the extension .h.

Normally, there is one class declaration per header file, and then one corresponding source-code

file that implements that class. For strongly related classes, occasionally there will be multiple

declarations in the header file.

4

To better organise the class hierarchy, and promote readability, nested directories typically

correspond to C++ namespaces, with the root namespace being infos.

For example, if you are interested in looking at the ATA storage device driver, you will be

interested in looking at the following files:

• drivers/ata/ata-device.cpp

• include/drivers/ata/ata-device.h

A class called ATADevice is declared in the header file ata-device.h, and it is implemented

in the source-code file ata-device.cpp. The class is declared within the following namespace

hierarchy:

infos 7→ drivers 7→ ata 7→ ATADevice

It should be clear that each level of the namespace hierarchy corresponds to the directory in

which the source-code and header file live.

2.2.5 Modules

InfOS is built on modules, but it currently does not support dynamically loading them. Instead,

the architecture of the OS is built around object-oriented principles, and as such producing a

different implementation for a particular feature simply requires subclassing the appropriate

type, and implementing the interface.

2.3 Start-up

InfOS uses the multiboot protocol to boot, which is a very convenient way of starting an

operating system. This protocol is supported by many boot loaders, and Qemu supports

booting multiboot enabled kernels natively.

Execution starts in 32-bit mode, in the multiboot start assembly language function. This

function lives in the arch/x86/multiboot.S source-code file. After this, execution transi￾tions into the start32 assembly language function, in the arch/x86/start32.S source-code

file.

This function initialises 64-bit mode, and jumps to start64 in the arch/x86/start64.S source￾code file. Finally, control transfers to the x86 init top function, which is the first executed

C++ function, in the arch/x86/start.cpp source-code file. From there, you can follow the

sequence of events that bring up the operating system.

2.4 Memory Manager

The memory manager is responsible for providing memory to programs/subsystems that request

it. The majority of requests will be for memory that can be used to store objects, (e.g. via the

C++ new operator), but some requests may be for entire pages of memory (e.g. for allocating

page tables).

A page of memory is a block of memory that is the most fundamental unit dealt with by the

underlying architecture. Pages are always aligned to their size boundaries (i.e. the address of

5

a page is always a multiple of their size) and on x86 (and therefore in InfOS) the page size is

4096 bytes.

InfOS has two memory allocators: a physical memory allocator, and an object allocator. The

physical memory allocator deals with allocating physical pages of memory, whilst the object

allocator deals with satisfying arbitrarily sized amounts of memory for storing objects. The

object allocator calls into the physical memory allocator to request large blocks of memory,

which are then used to store smaller objects.

The object allocator used is the open-source dlmalloc allocator. The built-in physical memory

allocator is an inefficient linear scan allocator.

2.4.1 Physical Memory

Fundamentally, a computer system has an amount of physical memory (RAM). This memory is

what is actually available for the storage of data, and is exposed in the physical memory space.

In modern systems, it is possible to address up to 52-bits (4096 Tb) of physical memory, but a

normal desktop system may have between 2-16Gb of memory installed.

The physical memory space consists of various regions of usable and unusable pages. It also

contains memory mapped devices that are not real memory, but allow the configuration and

operation of those devices by reading and writing to the associated memory address. To work

out what pages are available, an operating system needs some support from the bootloader and

the architecture.

2.4.2 Virtual Memory

Virtual memory is a flat view of memory as seen by the programs that are running. Each

program has its own virtual memory area (or VMA), which maps virtual addresses to physical

addresses. This mapping also includes protections, to prevent programs from reading and

writing to pages that it should not have access to, e.g. kernel pages.

The mapping specifies which virtual memory address corresponds to which physical memory

address, at the granularity of a page (i.e. 4096 bytes). A physical address may have multiple

virtual addresses pointing to it.

2.5 Process Scheduler

The InfOS process scheduler is responsible for sharing out execution time on the CPU for each

process that is on the ready queue. InfOS uses a timer, ticking at a frequency of 100Hz to

interrupt and pre-empt processes to determine if they need to be re-scheduled.

2.5.1 Scheduling Algorithms

There are many scheduling algorithms for process scheduling, and the built-in scheduler im￾plements an inefficient version of the Linux CFS scheduler. InfOS does not support process

priorities, greatly simplifying the scheduler implementation.

6

2.6 Device Manager

The InfOS device manager is responsible for detecting the devices that exist on the system,

and creating an abstraction that allows them to be accessed by programs that require them.

For example, it interrogates the system’s PCI bus to detect storage devices, and allows that

storage device to be accessed by file-system drivers.

2.7 Virtual Filesystem Switch (VFS)

The Virtual Filesystem Switch (or VFS) subsystem presents an abstract interface for accessing

files. Within a virtual file-system, physical file-systems (for example those that exist on a disk)

are mounted and can be accessed. Multiple physical file-systems can be mounted within the

virtual file-system, and they appear as normal directories within the VFS tree. Physical file￾systems could be local, on-disk file-systems, or they could be remote network file-systems. Some

file-systems could be dynamically created, e.g. InfOS creates a device file-system which contains

files that represent each registered device in the system. You can see this by entering:

> /usr/ls /dev

At the InfOS shell, to list the contents of the /dev directory.

2.8 InfOS API

As InfOS is a bare-metal operating system, it cannot use the standard C++ library, and hence

standard C++ routines and objects (such as strings, lists and maps) are not available.

Since these containers can be quite useful, InfOS implements its own versions of some of these

containers and exposes them for use by operating system code. They do not directly correspond

to the standard C++ implementations, but they provide all the methods you would expect these

containers to have. This section will describe some of these containers, particularly those which

you will find useful for the coursework, and how to use them.

You can see many examples of their use throughout the InfOS source-code.

2.8.1 List

The templated List class is a container for objects that is implemented as a linked-list. It

can be used by declaraing a variable of type List, where T is the type of object contained

within the list. To use it, you must #include the infos/util/list.h header file.

As an example, to create a list that contains integers, one would write:

List my_list;

The list object can be used as a stack or a queue, and can be iterated over with a C++ iterator

statement:

int sum = 0;

for (auto& elem : my_list) {

sum += elem;

} 7

The List class exposes the following methods:

void append(T elem) Appends elem to the end of the list.

void remove(T elem) Removes any element that equals elem from the list.

void enqueue(T elem) Appends elem to the end of the list.

T dequeue() Removes the element at the start of the list, and returns it.

void push(T elem) Inserts elem at the start of the list.

T pop() Removes the element at the start of the list, and returns it.

T first() Returns the element at the start of the list.

T last() Returns the element at the end of the list.

T at(int index) Returns the element at the given index in the list.

unsigned int count() Returns the number of elements in the list.

bool empty() Returns true if the list is empty.

void clear() Removes all items from the list.

2.8.2 Map

The templated Map class is a tree-based implementation of an associative array.

It is implemented as a red-black tree, so it is reasonably efficient, but the implementation details

are not important.