Assignments

There are two assignments. The first assignment is focused on multi threading, thread interaction, process execution, process manipulation and process interaction. The second assignment is focused on virtual memory. You have the possibility to choose from a wide range of tasks, but a good understanding of virtual memory is required for most of them.

For each assignment you can get 50 points (=100%) + bonus points.

SWEB runs on different architectures. You can choose to support one or more architectures during your exercises. Have a look at the Tutors Points List A1 and Tutors Points List A2 to estimate the bonus points you get.

In Assignment 1 you will acquire basic knowledge about the inner workings of multi threading and multi processing on modern operating systems.

You will start with the basic SWEB kernel which has neither multi threading nor multi processing implemented for userspace programs. Instead there is one thread per process. You have to figure out what to change to make SWEB support multi threading.

Threads share their address space with all other threads within the same process. However, each thread has its own stack, own set of cpu register values and maybe other resources. When the operating system interrupts a thread, it has to store these resources so that the thread execution can be continued later.

Interaction between userspace and kernelspace is only possible through syscalls. You can implement any syscall you like. However, for reasons of automated testing of your implementation you are required to comply with the POSIX standard in terms of function names and parameters.

You will need to implement at least the following syscalls:

1. pthread_create to create a new thread
2. pthread_exit to allow a thread to terminate itself
3. pthread_cancel to terminate another thread
4. pthread_join to wait for termination of another thread

Furthermore you are required to implement several user programs which demonstrate that your implementations works as expected.

We want to give our user programs the ability to start new user programs. The POSIX compatible way of doing so, is to use the fork syscall (and the exec syscall). Fork creates an exact copy of the currently running process, with only the calling thread copied to the new process. The copied thread in the new process continues execution right after the fork call. We want to remind you to comply exactly to the POSIX standard for reasons of automated testing.

The two mandatory tasks are designed to give 30 points (of 50 points). We expect you to choose your own additional tasks. In the Tutors Points List A1 (not recommended for student use) you find a long list with numerous suggestions what you could implement. DON’T just use this list. Neither you nor we will be happy with the result. These are bonus tasks, come up with your own ideas, come up with your own improved variants of features.

We strongly encourage implementing your own interesting ideas, as long as they are related to this course, by giving you points. But, before you start, ask your tutor. For tasks that fall into one of the topics of Assignment 2 you can’t get any points in Assignment 1 (and the other way round).

In the first assignment you already caught a glimpse at how powerful the concept of virtual memory is. In the second assignment we will dive much deeper into this concept and try to understand it completely. For this purpose we will implement swapping and copy-on-write.

SWEB already has a basic implementation of paging and on-demand-loading. When you start a program the binary image is not loaded into physical memory completely. Instead, the binary image is divided into page frames (just as the physical and the virtual memory is). As soon as the user process tries to access a page not yet loaded, a page fault occurs and the operating system loads the data from the file. This results in significantly less physical memory pages wasted on data which is rarely used by a program.

Copy-on-write is mechanism to reduce the number of physical memory pages with identical content. When forking a process, an exact copy of the virtual address space has to be created. However, usually a significant number of pages in the virtual address space are not changed. Therefore, the operating system maps virtual pages from both processes to the same physical page. In order to avoid the processes influencing each other, the pages are set to read-only. As soon as one user process tries to write to such a shared page, a page fault occurs. The page is then copied and set to writable. Just as on-demand-loading, copy-on-write is completely transparent (unnoticeable) to the user program.

Swapping reduces the number of physical memory pages which are used once, but rarely used afterwards^**. A page replacement algorithm selects pages which are likely to not be used in the near future. These pages are then swapped out (written to hard disk and removed from physical memory). As soon as a user process tries to access a swapped out page, a page fault occurs. The operating system will then swap in (read from hard disk and write into physical memory) the page. This is again completely transparent to the user program.

We expect your implementation to fulfill all of the following requirements:

• Write at least one kernel thread to select physical pages for swap out
• Requesting a free physical page may never fail
• You have to use the swap partition on the block device for swap out
• You have to write test programs which use more memory than is physically available
• There may not be a negative impact on performance unless physical memory utilization is scratching the limit
• Implement a reasonable page replacement algorithm. Better solutions yield more points. FIFO strategy is by far not enough.

You have to implement a user program visualizing (any readable form is good enough: log on screen, show a table, show a graph, …) virtual memory and swap device statistics. Furthermore you are required to implement several user programs which demonstrate that your implementations works as expected.

The mandatory task is designed to give 40 points (of 50 points). We expect you to choose your own additional tasks. In the Tutors Points List A2 (not for student use) you find a long list with numerous suggestions what you could implement. DON’T just use this list. Neither you nor we will be happy with the result. These are bonus tasks, come up with your own ideas, come up with your own improved variants of features.

We strongly encourage implementing your own interesting ideas, as long as they are related to this course, by giving you points. But, before you start, ask your tutor. For tasks that fall into one of the topics of Assignment 1 you can’t get any points in Assignment 2 (and the other way round).