CS414 Programming Project 2

In the first project, you implemented a nonpreemptive user-level threads package. In this project, your task is to extend it to support preemption. In project 1, achieving concurrency between different threads required inserting explicit minithread_yield() operations in your application code. Preemption allows concurrent threads to run without explicit yields being added, so the system is more robust to slow or ill-behaved threads: forcible preemption prevents a thread from grabbing the CPU and not relinquishing it.

We have provided you with some code that emulates clock interrupts. The interrupts arrive on the stack of the currently executing thread, just like they do on native hardware. Your main task is to write a clock handler which performs a context switch when triggered by an interrupt.

Project organisation

1. Make your threads package preemptive: to do this you should use the interfaces in interrupts.h. In order to activate preemption, initialise the clock module by calling minithread_clock_init(), and then enable interrupts with set_interrupt_level(ENABLED). You should then start getting clock interrupts, which will cause your clock interrupt handler to be called. To begin with, make the clock interrupt handler force a context switch. In order to make debugging easier, you may wish to set the value of the PERIOD constant in interrupts.h to some large value (e.g. 5 seconds) so that the time slice is large. Once you have preemption working, reset it to its original value.

   Unfortunately, you will rapidly find out that simply adding a clock handler will result in incorrect code: you need to protect critical code against clock interrupts, which could occur and force a context switch at any point in either application or "system" code. This can occur at "inconvient" moments, such as when a system invariant does not hold (e.g. ready queue operations). Disabling and enabling interrupts judiciously will allow you to protect critical sections of code. Don't run with interrupts disabled unnecessarily, you will be penalisd. User code should certainly never run with interrupts disabled.

   It is worth noting that the minithread_switch() function enables interrupts before it returns, this should help you in ensuring that context switches are atomic.

2. Add an alarm facility by which processes can request an arbitrary procedure to be called N milliseconds in the future. You will have to keep track of how many clock ticks have passed by in your clock interrupt handler in order to be able to decide when the alarms ought to expire. It's ok if the user specifies a clocktick value that is below the precision of your time quantum. Do the best you can with such requests instead of ignoring them.

3. Use alarms to implement an interface, minithread_sleep_with_timeout(int milliseconds), by which threads can give up the CPU, go to sleep (i.e. relinquish the processor entirely) and wake up after a given number of milliseconds have elapsed.

4. Implement the factorisation problem and evaluate the results (see below).

Most programs which you write will rely on library routines provided in the standard C library (e.g. printf). Unfortunately, the C library and other Windows libraries which the compiler links to your application are not minithreads-safe (of course, they are NT kernel thread-safe). It is not safe to preempt a minithread running in Windows library code, since the data structures in the libraries are not synchronised using minithreads concurrency-control structures.

For example, if multiple minithreads concurrently attempt to allocate memory or print to the screen, there may get a crash in library code. To prevent this, the minithreads interrupt subsystem disables preemption whenever your threads execute library code. More specifically, if a clock interrupt arrives while a minithread is in a library, we ignore it and wait for the next one. This is a cheap and easy technique to continue to use "external" or other legacy code without having to rewrite all of it. The downside is that programs that spend virtually all of their time in a library (e.g. performing large amounts of output to the screen in a loop) will not receive clock interrupts. There are two options: rewrite the C library to be minithread-safe, or restructure the program to spend less time in library code.

Evaluation

As well as writing code for this project, you must also take some measurements of the code you have written. Good systems design necessarily involves measurement to validate your design decisions. To make some meaningful measurements, you first need to implement an application problem which does some non-trivial computation in memory, the factorisation problem.

The Factorisation Problem. This problem is similar to the food services problem, in that it's a modified producer-consumer problem. It works like this: there is one producer of numbers, and N factorisers. The producer runs in a loop in which it generates a random odd number r, and puts it on a shared input queue. Once it has generated C numbers, it blocks waiting on the shared output queue. A factoriser runs in a loop in which it removes a number from the input queue, and factorises it by finding two numbers p, q so that r = p * q, for p, q not equal to 1 or r. If p and q exist, then r is composite, otherwise it's prime. When it has successfully found factors of r, or discovered it to be prime, the factoriser puts the number on the output queue and wakes the producer, and which then the results (prime or composite and factors).

Implement the factorisation problem in an application which takes two arguments: N and C. Use the C srandom() and random() calls to generate the random numbers (you can use random() % SOME_LARGE_NUMBER if factorising is taking too long, for SOME_LARGE_NUMBER of at least a million). To use random() you must include <stdlib.h>.

Run the following experiments, using _ftime() to take timing measurements (you'll need to include <sys/time.h>, <time.h>). Repeat each measurement at least 5 times.

1. Measure the time taken to do a context-switch between two threads.
2. For C = 360, run the application and measure how long it takes for some different values of N (e.g. at least N = 1, 2, ... 10). Explain your results and give a possible explanation.
3. Pick values of C and N and try varying the time slice (PERIOD). Try at least 5 different values. What relationship would you expect to see between the time slice length and execution time? Does it hold in practice? How variable are your measurements for a single parameter setting?
4. Measure the difference between the time a thread spends sleeping in minithread_sleep_with_timeout(int milliseconds) and the parameter value, for some different values of milliseconds. Discuss the discrepancy.

How to get started

• Make a backup copy of your Project 1 code.
• Download the code here: minithreads2.zip
• The rest of the instructions are the same as those for Project 1. You can change which main routine you are linking against by modifying the Makefile, which should make life a little easier.

There is a minithreads FAQ which you may find useful.

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.

Demonstrate that your preemption code works by making "food services" and the test cases from the previous project work under preemption. Remove the minithread_yield() calls and see if the tests still work.

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.

Grading

Submitting your project