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. Windows does not have a user-level threads library. Your task is to write one.

We have provided you with some skeletal code that creates an environment on top of Windows that closely resembles the environment on top of raw hardware shortly after booting. We use Windows to provide us with a virtual processor and memory. Windows 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 Windows 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 demonstrate your threads package by implementing a solution to the "food services" problem. This is actually an instance of the better-known multiple-producer, multiple-consumer problem. There are N cooks (each a separate minithread) that constantly produce burgers. We'll assume for debugging purposes that each burger has a unique id assigned to it at the time it is created. The cooks place their burgers on a stack (at the front of the queue you built earlier in this assignment). There are M hungry students (each a separate minithread) that constantly grab burgers from the stack and eat them. Each time a student eats a burger, she prints a message containing the id of the burger she just ate. Ensure, for health and sanity reasons, that a given burger is consumed at most once by at most one student.

How to get started

To unpack and set up minithreads, do the following:

For Visual Studio 2008:

  1. Unzip the PortOS1.zip file in the directory for your project.

  2. In VS2008, select File -> New -> Project from Existing Code.

  3. Create a C++ project and choose the directory where you unpacked PortOS1.zip. (you should chose the directory created by the zip, not its parent).

  4. Name the project minithreads and under File types to add to the project replace the list of extensions with "*" to add all files in the directory.

  5. Click the Next button, choose Use external build system, click Next again.

  6. Make the following entries:
    • Under Build command line enter: nmake.
    • Under Rebuild command line enter: nmake /a.
    • Under Clean command line enter: nmake clean.
  7. Click Next and Finish.

To build minithreads you will need to first edit the Makefile for your architecture.

  • If you are running 32-bit Windows, the top of your Makefile should have the following lines uncommented:

    SDKLIBPATH = "C:\Program Files\Microsoft SDKs\Windows\v6.0A\Lib"
    VCLIBPATH = "C:\Program Files\Microsoft Visual Studio 9.0\VC\lib"
    WINVER = "WIN32"
    MACHINE = "I386"
    PRIMITIVES = machineprimitives_x86_asm
    
  • If you are running 64-bit Windows, the top of your Makefile should have the following lines uncommented:

    SDKLIBPATH = "C:\Program Files\Microsoft SDKs\Windows\v6.0A\Lib\x64"
    VCLIBPATH = "C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\lib\amd64"
    WINVER = "WIN64"
    MACHINE = "X64"
    PRIMITIVES = machineprimitives_x86_64_asm
    

After modifying the Makefile, open a Visual Studio 2008 Command Prompt through the Windows start menu:

  1. Start

  2. All programs

  3. Microsoft Visual Studio 2008

  4. Visual Studio Tools

  5. Visual Studio 2008 Command Prompt

    Note

    If you are on Windows x64 (64-bit), you should use the Visual Studio 2008 x64 Command Prompt.

Enter these commands into the command prompt to build and run your application:

> cd "C:\path\to\PortOS1"
> nmake
> minithreads

If you decide not to use the Visual Studio integrated development environment, you can use any other editor you like and compile the code from the command line (using the instructions above).

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. You should include a README file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality (although you will have trouble later on if you do not complete this project now, so you should not be submitting a broken project).

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 the barber shop problem

The barber shop problem can be described as:
  • The barber shop has two rooms: the waiting room and the barber room. At any given time there can be at most one customer in the barber room but any number of customers in the waiting room.
  • If the barber is busy (shaving a customer) and another customer arrives, the new customer will wait in the waiting room.
  • If a customer arrives and the barber is sleeping in the waiting room, the customer wakes the barber
  • When the barber finishes shaving a customer and no other customer is waiting in the waiting room, the barber goes to sleep in the waiting room.

Add Preemption

Add preemption and implement a multilevel feedback queue with four levels, with round-robin at each level, and where the time quanta doubles at every level. Demonstrate that it works as intended.

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