Executing the scheduler

Your program will be a single executable "scheduler" that takes no command line arguments. Since this means you can't specify any file names, your scheduler must take its input from the UNIX standard input and print to the standard output.

Input

The input to your program will be an ASCII stream of job control commands. Each job is identified by a positive integer, and has a duration and a "niceness" value. (The higher the niceness, the less attention the job will get.)

The first line of the input will contain the maximum job number. While no job number will ever exceed this maximum, it may be possible for more than this number of jobs to be submitted by reusing the numbers of jobs that have completed. The test data that we will supply (in the directory /usr/class/cs161/project/data) will never submit a new job with the same id as an active job, so if your program detects such a request, it's an indication that something's wrong with your job queue.

Each subsequent line of the input will be one of the following: 

tick RUN  job duration niceness
tick KILL job
tick NICE job niceness
tick TOP
The tick numbers indicate the time at which the command has been submitted. They will always appear in non-decreasing order. The job numbers are positive integers. The other numeric arguments are non-negative integers.

The RUN command submits a new job to put into the queue. The KILL command indicates that a job should be removed from the queue immediately. The NICE command causes a job's "niceness" to be set to the specified value and its priority to be re-evaluated. The TOP command shows the job at the top of the priority queue.

Library routines

The main objective of this project is to implement an efficient priority queue structure. So that you can concentrate on that aspect, we will provide you with a library of routines that handle I/O and the job priority and aging computations. When we evaluate the performance of your program, the running times of these routines will be subtracted out and only the time spent in your own code will be counted.

The library /usr/class/cs161/project/lib/projlib.a contains the following routines:

newPriority(int CPUusage,int nice)
computes a job's priority based on it's "niceness" and its CPU usage so far
compare(unsigned long long a,unsigned long long b)
compares two priorities, returning -1/0/1 if a's priority value is lower than/equal to/higher than b's. If two priorities are equal, you should break the tie yourself by pretending that the job with the lower job id number had the lower priority.
ageCPUusage(int CPUusage,int nice)
"ages" a job, giving a modified estimate of its recent CPU usage
initialize(void)
must be called at the start of your program
finalize(void)
must be the last function called at the end of your program. Reports the number of comparisons made and then exits the program.

readCommand(void)
reads a command line from stdin. Puts the first letter of the command (in upper case) into the global variable cmdletter. Puts the command time, job id, job duration, and job niceness in cmdtick, cmdjobid, cmdduration, cmdnice respectively, when appropriate. When the input is exhausted, cmdletter becomes '\0'
printTop(int jobid,int duration,int nice,int heapsize)
Prints a line on stdout indicating the clock time, the queue size, and the parameters of the job at the top of the queue. This should be called when a TOP command is issued, and also when a job is completed. If the job queue is empty when a TOP command is issued, you should use 0 for the jobid parameter.

If you add your own diagnostic output on stdout, please begin each line with a # character so that it can be easily discarded when analyzing the output.

warn(char *s)
reports the command number, the clock time, and the supplied error message.
die(char *s)
reports the command number, the clock time, and the supplied error message, then exits the program.
pritostr(unsigned long long p)
returns a hexadecimal representation of the priority p. The returned pointer is to a static storage area. (Shouldn't be needed)
strtopri(char *s)
converts a hexadecimal string to an unsigned long long. (Also shouldn't be needed)
Prototypes for these procedures are in the header file /usr/class/cs161/project/src/projlib.h. You do not need the directory prefix if you use the standard makefile.

Handling Priorities

The values returned by newPriority are scrambled in such a way as to be meaningless to anyone except the compare routine. There is really no need for you to know the exact values of the priorities, only their relative order, so this shouldn't present a problem. You can substitute your own functions to replace newPriority and compare during testing if you feel it's necessary, but the program you submit has to use the library routines, otherwise you won't be using the right priority values.

The Scheduler

In /usr/class/cs161/project/src/scheduler.c we have provided you with the skeleton of our own scheduler. Most of the details of the code are missing, but it should give you a precise idea of what the operation of the scheduler should be. You do not have to adhere to this code's structure (and some changes could definitely make it more efficient), but your scheduler must produce the same results.

The one part of the supplied scheduler that must be preserved is the constant CPU_PER_TICK. This is defined in the projlib.h header file.


Preparing your account

You must have an account on the elaine machines in Sweet Hall to do the project. All of the materials we will supply for the project will reside in the directory /usr/class/cs161/project.

You can arrange your workspace any way you like. When the time comes for you to submit your project, just make sure your project directory contains all the necessary project files/directories. Only the approved source and documentation files will be submitted. See the submission page for details.

We recommend that you add /usr/class/cs161/project/bin to your PATH environment variable, so that you can omit the whole directory prefix when executing our scripts.

Compiling

Your code must compile on one of the elaine machines in Sweet Hall, using the Makefile found in /usr/class/cs161/project/src/Makefile. This means that you must supply your code in two files "scheduler.c" and "pqops.c", plus any of your own header files that you need to include.

The command /usr/class/cs161/project/bin/161make will run this makefile for you.

Verifying and Evaluating

An executable of our (highly inefficient) scheduler is in /usr/class/cs161/project/bin/161scheduler. If your program is working correctly, this program's output will be identical to yours.

Remember that your program will be judged on the correctness of the output, the number of comparisons performed, and the out-of-library running time. We have supplied a script /usr/class/cs161/project/bin/161run that runs a scheduler some number of times and computes the average running time (total time and out-of-library time). You can use this script to measure the efficiency of your program versus ours. This script leaves output files and profiling data in your directory, which you can clean out with the command /usr/class/cs161/project/bin/161clean.

Submitting

NOTE: There is a separate submission web page with a much more detailed description of the submission requirements.

When you are ready to submit your program, clear your directory of unnecessary files and run the /usr/class/cs161/project/bin/161submit script. The script will ignore the usual output files and profile data when it can. Please do not submit other large files or profile data, as there is limited space in the class directory. All you really need to submit are your writeup and source files, since we will recompile everything for evaluation. We will be using the same Makefile we supplied to you, so be sure your program compiles properly with it.

Your writeup should contain the names of everyone in your project group, and each group should only make one submission. If you need to re-submit, make sure you do so from the same user's account as before.