CS4411
Practicum in Operating Systems

Project 1: Non-preemptive Multitasking

Overview

Your task in this project is to write a non-preemptive user-level threads package. Most operating systems, provide such a lightweight thread abstraction because, as you might recall from the lectures and the reading, user-level threads provide concurrency with very low-overhead. Your task is to write one.

We have provided you with some skeletal code that creates an environment on top of (Windows,OSX,Linux) that closely resembles the environment on top of raw hardware shortly after booting. We use our host OS to provide us with a virtual processor and memory. It also bootstraps our kernel; that is, it loads it into memory and starts executing it at its entry point. Your task is to build high-level abstractions on top of this environment in the same manner the host OS builds its abstractions on top of the hardware.

There are a few distinct components to this project.

  • First, you will have to write some generic FIFO (first-in, first-out) enqueue and dequeue operations. We will be relying on this queue implementation throughout the rest of the semester, so it's important that the implementation be efficient. Specifically, enqueue and dequeue operations should both work in O(1) time.
  • Second, you need to define and implement thread control blocks, and the functions that operate on them. We suggest you start with minithread_create and minithread_yield, and go on to implement the scheduler. Once you have those two working, you can come back to implement the rest of the functionality.
  • Third, you need to implement a scheduler. For this assignment, all you need is a first-come, first-served scheduler. You can assume that your threads will voluntarily give up the CPU, which means that your test programs should make occasional calls to minithread_yield().
  • Fourth, you need to implement semaphores in order to be able to synchronize multiple threads.
  • Finally, you need to implement a simple "retail store" application that uses your minithread, queue, and semaphore implementations. The application models customers and employees at an electronics retail store as threads. Your application should make the best possible use of the components you developed in this project to simulate the following:
    • It is release day for the new PortPhone 5, the latest device running the revolutionary PortOS from Sirer Systems. Customers are flocking to their local retail store to purchase the new phones. Unfortunately, the new shipment of phones has just arrived and employees are struggling to keep up with demand.
    • There are N employees . Each employee constantly unpacks phones. Each phone has a unique serial number, and the phones are unpacked in increasing serial order.
    • There are M customers, who are served on a first come, first served basis. When a customer arrives at the store, they immediately receive a new phone if one is available. Otherwise, they wait in line until more phones become available. Ensure, for sanity
    • When a customer receives a phone, (s)he immediately activates it by printing the unique serial number to stdout.

How to get started

Install the CS4411 virtual machine

This semester we will only support the environment provided by the csug lab virtual machine. To install the VM, follow the instructions here. If you do not have CSUG lab access, you can also download the VM image here. The second image has a user named “haxor” already created with the password “cs4411”.

Download the release

The release is available here. You can download the release at the command line by running 

   wget http://www.cs.cornell.edu/courses/cs4410/2014fa/CS4411/projects/project1/cs4411-p1.tar.gz
and you can extract it using 
   tar -xzf cs4411-p1.tar.gz

Create a non-public git repository shared with your partner

Not mandatory but extremely highly recommended.

Compiling and running

To compile the code in the release directory, simply run make. This will compile the test applications that we have shipped; they won't do much though because the thread library is currently unimplemented.

Be sure to consult the README file for an overview of the source code. You may also wish to look at the Makefile to see more options for compiling your code.

How to Test Your Code

It's crucial that systems code be correct and robust. You must test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly. Note that you should maintain some separation between the minithread package and minithread applications. Most notably, your minithread applications should not contain any dependencies on the scheduling algorithm or on the lack of preemption.

To facilitate testing, we provided you with some test programs. It's a good idea to start with these, and develop your own tests as you need them.

Here's a list of test cases, each with a short description:

test1.c
A test of single thread creation.
test2.c
A test of multiple thread creation.
test3.c
A test of ping-pong between two threads.
buffer.c
A bounded buffer implementation. A producer and consumer keep producing and consuming values across a buffer of finite length.
sieve.c
A Sieve of Eratosthenes for concurrently searching for primes. It has a single thread on one end, injecting the numbers 1, 2, 3, 4, 5, 6, 7, 8, ... into a pipe. For each prime p, there is a thread in the middle of the pipe that consumes a number from the pipe if that number is divisible by p. Otherwise, it passes the value on to the next thread in the pipe. At the very end, there is a thread that prints the values that emerge from the pipe. Note that this assembly will only print out prime numbers, because the threads in the pipe will consume all non-primes.

Since we will soon make the threads package preemptive, all code you write should be properly synchronized. That is, everything should work no matter where in the application thread you place a minithread_yield. Consequently, it's a good idea to test your code with minithread_yields inserted at random locations throughout the application code (note that we don't expect the system code in minithread.c or synch.c to be yield-safe for this project - just the applications).

Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of threads are created and destroyed.

Submissions

Use CMS to submit your project. Your submission should contain a single folder called p1 with the following contents: 

$ tar -tzf submission.tar.gz | sort
p1/
p1/buffer.c
p1/defs.h
p1/end.c
p1/.gitignore
p1/interrupts.c
p1/interrupts.h
p1/interrupts_private.h
p1/machineprimitives.c
p1/machineprimitives.h
p1/machineprimitives_x86_64_asm.S
p1/machineprimitives_x86_64.c
p1/Makefile
p1/minithread.c
p1/minithread.h
p1/queue.c
p1/queue.h
p1/queue_test.c
p1/random.c
p1/random.h
p1/README
p1/README.your_netid
p1/sieve.c
p1/start.c
p1/synch.c
p1/synch.h
p1/test1.c
p1/test2.c
p1/test3.c
In addition, it should contain the source code for the additional tests you have created.

The file README.your_netid should contain your name, your partner's name, and anything that a user or grader would find useful about your implementation. In particular, you should document any errors that you are aware of (but you should fix them if you can!)

For the adventurous

Note: These suggestions for an extra challenge will be examined but not graded. They will have no impact on the class grades. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family (or perhaps better understand the material).

  • Implement monitors
  • Implement the 4410 synchronization problems using your threading package
  • Port the machine primitives to your favorite architecture

Final Word

We will maintain a list of frequently asked questions about this project.

If you need help with any part of the assignment, we are here to help. If you start early, this should be an incredibly fun project.

Powered by Firmant