In this project you will design a CPU scheduler. Your scheduler will test different scheduling policies and report results of how well these policies perform.

The scheduler you are creating will be developed exclusively in C/C++ using POSIX threads. POSIX threads are a standard thread API (application programming interface). The POSIX thread package is available on hops and malt and is more portable than the Solaris thread package which is also available on these machines.

You must work in groups of 2-4 people. I strongly encourage working with people who you know you can work well with. Remember that their performance on this project will be reflected in your grade, so be sure you choose your partners wisely.

I recommend you read through a reference book on POSIX threads if you are unfamiliar with their use. A book which I have found helpful is Programming with POSIX Threads by David R. Butenhof. The library owns one copy of this book which has been placed on 2-hour reserve.

Also, the man pages on hops/malt are very helpful. As a start, try "man threads". The thread man pages on Solaris will include information on both Solaris threads and POSIX threads. Be sure to use the POSIX threads.

III. Sample POSIX code

Included with Butenhof's book on POSIX threads is a tar file including lots of example POSIX programs. This tar file is available for you to look through. Note that not all of the programs included in this tar file are will be useful for learning how to use POSIX threads but are included for more advanced topics which we will not use for this assignment. You should discover which files are helpful to you by reading through the code and running the programs. Caution: The semaphore examples do not work because Solaris 2.5 (the operating system used on hops/malt) does not implement POSIX semaphores. This affects the files semaphore_wait.c and semaphore_signal.c.

You can download the tar file and instructions for its use from this web page.

Note: If you should decide to download a copy of the tar file from another source, you may find problems with their Makefile. The version included on the course web page will work on hops/malt.

Start with the easy examples such as hello.c and work your way through the more complicated examples.

IV. Project Description

The goal of this project is to design and test CPU scheduling techniques. The CPU scheduler in a real operating system will schedule other processes. Your project, however, will run as a single UNIX process. It will not fork any new processes! Be sure you do not create code that forks new processes. Programming with fork is very dangerous to the system and can crash the system with improper use.

Within your single UNIX process, you will create many separate threads.

One thread will be the CPU scheduler. Your CPU scheduler will run many different algorithms. You should create a separate function for each and have a command-line argument which allows you to choose which scheduler to use. Also, the different algorithms may also take extra parameters specifying other details. For example, you may want to choose a parameter specifying the length of a time-slice in round-robin scheduling.

The scheduling algorithms you will implement are:

1. First Come, First Served
2. Round Robin (pre-emptive) [time quantum will be a command-line parameter]
3. Shortest Job First (non-preemptive)
4. Shortest Remaining Time First (preemptive)
5. Round Robin with Priorities and Aging (preemptive) [the amount of time a job must wait before an increase in priority occurs will be a command-line parameter]

The rest of the threads you will create for this assignment will do one thing: count. These threads don't do anything except take time to run. (You should make them count to very high numbers so that there is a significant amount of time that each thread needs to run.) The reason we create them is to show how the scheduler can switch between them. Each thread will be passed the following parameters:

1. how high it is supposed to count,
2. its priority,
3. what time it was created

Jobs will not all be created at time 0. Instead, jobs must be created over time. The interval of time between submitted jobs will be dictated by a Poisson distribution. (Code for implementing a Poisson distribution will be made available.) To test your program initially, you should simply create all jobs at time 0.

Each of the sleeping threads will also keep track of when they started running and when they completed execution. When the thread has completed running, it will return its turnaround time. Turnaround time is computed by subtracting the time a thread was created from the time the thread completed.

When all the created threads have completed, your CPU scheduler will return to the main program the average of all the values returned by the threads.

V. What to turn in

You will have turn in all code that you created. All of your programs should be concisely and thoroughly documented. Threaded code is often very difficult to read. For the graders' sake and your own, please be sure you comment comprehensively.

You should create graphs of the performances of these different algorithms. Also, for the priority and shortest job/shortest remaining time algorithms, you should show how higher priority/shorter jobs had better turnarounds than lower priority/longer jobs.

You should also include a report talking about why the scheduling algorithms did what they did and what the results show.