首页 > > 详细

UG3 Operating Systems

 UG3 Operating Systems 2019-20

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.
 
联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

联系我们 - QQ: 99515681 微信:codinghelp
© 2014 www.7daixie.com
程序代写网!