Project #2

Problem

Detailed Description and Requirements

When jobs initially arrive in the system, they are put on the job scheduling queue which is maintained in FIFO order. The job scheduling algorithm is run when a job arrives or terminates. Job scheduling allows as many jobs to enter the ready state as possible given the following restriction: a job cannot enter the ready state if there is not enough free memory to accommodate that job's memory requirement. Do not start a job unless it is the first job on the job scheduling queue. When a job terminates, its memory is released, which may allow one or more waiting jobs to enter the ready state.

A job can only run if it requires less than or equal to the system's main memory capacity. The system has a total of 512 blocks of usable memory. If a new job arrives needing more than 512 blocks, it is rejected by the system with an appropriate error message. Rejected jobs do not factor into the final statistics (described below).

Note that all jobs in the ready state must fit into available main memory.

Process scheduling is managed as a multilevel feedback queue. The queue has two levels, both using a round robin scheduling technique. New jobs are put on the first level when arriving in the ready state. When a job from the first level is given access to the CPU, it is allowed a quantum of 100 time units. If it exceeds that time quantum, it is preempted and moves to the second level.

The jobs on the second level may only be allocated the CPU if there are no jobs on the first level. When a job on the second level is given access to the CPU, it is allowed a quantum of 300 time units. If it exceeds that, it is preempted and put back on the second level of the ready queue.

Process scheduling decisions are made whenever any process leaves the CPU for any reason (e.g., expiration of a quantum or job termination). When a job terminates, do job scheduling first, then process scheduling. Also, give preference to first level jobs, i.e., if a job from the second level of the ready queue is running, and a new job enters the first level, the running job is preempted to the second level in favor of the first level job.

While executing on the CPU, a job may require I/O, which preempts it to the I/O wait queue for the duration of its I/O burst.

While executing on the CPU, a job may perform a semaphore operation. Assume there are 5 semaphores shared among all jobs running in the system, numbered 0 through 4, each initialized to 1. If a job must wait because of a semaphore, it goes onto the appropriate wait queue until it is signaled. There is a separate wait queue for each semaphore.

When a job completes, put it on a finished list for later processing.

The simulator is driven by the events read from standard input. Examples of possible events are given below. The first field will be the first character of the line, and subsequent fields will be separated by one of more spaces or tabs. The header of each field in the following examples does not appear in the input file.

A new job arrives:

Event Time Job Memory Run Time
A     140  12  24     2720

Interpretation: job 12 arrives at time 140, requires 24 blocks of memory and uses the CPU for a total of 2720 time units.

A job needs to perform I/O:

Event Time I/O Burst Time
I     214  85

Interpretation: the job currently running on the CPU will not finish its quantum because at time 214 it needs to perform I/O for a duration of 85 time units.

A job performs a wait on a semaphore:

Event Time Semaphore
W     550  2

Interpretation: the job currently running on the CPU performs a wait on semaphore number 2 which may or may not cause it to be preempted. Initialize each semaphore to 1.

A job performs a signal on a semaphore:

Event Time Semaphore
S     622  2

Interpretation: the job currently running on the CPU performs a performs a signal on semaphore number 2 which may allow a job to re-enter the ready state.

Display the status of the simulator:

Event Time
D     214

Interpretation: display the status of the simulator at time 214.

You may assume that events appear on the input stream in ascending time order and no two events happen at the same time. However, realize that the events given in the input stream are not only events which your simulator must handle. For instance, a time quantum expiration is not an event given in the input stream, but it is an event which your simulator must handle. Furthermore, an internal event, such as a time quantum expiration, not in the input stream, may occur at the same time as an event in the input stream, e.g., a new job arrival. Events in the input stream are external events.

The following is a list of internal events (i.e., not given on the input file) which your simulator must handle:

• I/O completion (C)
• time quantum expiration (E)
• job termination (T)

Assume that context switching, semaphore operations, and displays take no simulator time (an unrealistic assumption in a real operating system).

When a display is requested, print the contents of all queues as well as the job currently running on the CPU to standard output using only the format used in the sample output given below.

After processing all jobs, write the following to standard output (in this order, as shown on the sample output given below):

1. completion time for each job (in order of completion),
2. average turnaround time (where turnaround time is defined as completion time minus arrival time), and
3. average job scheduling wait time (where wait time is defined as the number of time units spent in the job scheduling queue).

Event Collisons

Often more than one event happen at the same time. Use the following rules to determine which events to process first:

• If an internal event (e.g., an event not on the input file such as time slice expiration, I/O completion, or job termination) and an external event (i.e., an event given explicitly on the input file) happen at the same time, process the internal event first.
• If a job is scheduled to come off the I/O wait queue at the same time a job is scheduled to come off the semaphore wait queue, take the job off the I/O wait queue first.

Graphical View of the Simulator

Additional Requirements

• Your implementation must be distributed across more than one source code file, in some sensible manner which reflects the logical purpose of the various components of your design, to encourage problem decomposition and modular design.
• Include a README file in your submission which describes (i) the language you used to develop your program, (ii) the name of the compiler or interpreter, including version and URL where it can be downloaded, which you used to compile or interpret your program, and (iii) the OS (name and version) under which you developed your program.
• If you develop your simulator in a compiled language (C, C++, Java), you must provide a Makefile. Your Makefile must include target directives for every derived file produced during the compilation process (i.e., each program, each object file, and any other intermediate files produced during code compilation). Make sure that each directive also lists all files on which the derived file depends in its dependency list. Also, your Makefile must be written so carries out only the commands necessary to bring any produced file up-to-date. Your Makefile must do just enough, but no extra, work to bring the final executable for your simulator up-to-date every time make is invoked. In addition, it must have an all directive and a clean directive to remove all generated files Use variables where appropriate in your Makefile to improve its readability. Your Makefile must bring everything up-to-date, without any warnings or errors, when make is invoked on our system.

Hints and notes

• You are advised to define a PCB (process control block) structure and use it as a node in the various queues of your simulator.
• When debugging your simulator, you are advised to add extra display events to the sample input to trace the movement of jobs throughout the various queues of the system.
• You are advised to organize jobs on the I/O wait queue in the order in which they are scheduled to come off.
• You are advised to organize jobs on each of the 5 semaphore wait queues in FIFO order.
• Since this program involves so many queues (I count 10), you are advised to use a programming language which has list operations built into the language, such as Python, or one which provides a queue data structure in a standard library, such as Java or C++. You are advised against re-inventing the wheel. You are also advised against using this project as an opportunity to learn a new language. Use tools which you are already familiar with and focus on the operating systems components of the project.
• If designed properly, the program required to solve this project should occupy no more than 1,000 lines of code (or less if you use built-in data structures or data structures from libraries).

Test data: sample input and output

1. p2a.dat and output
2. p2b.dat and output
3. p2c.dat and output
4. p2d.dat and output

When developing your simulator, you are encouraged to get it to work on the simple test data first (p2d.dat) and progressively refine your program to the point where it works on the most complex test data (p2a.dat).

How to submit

1. Prepare your submission file as /home/<logname>/projects/p2/p2.tar. This archive must contain only the most minimal set of files necessary to build your simulator from scratch. Only the file /home/<logname>/projects/p2/p2.tar will be electronically collected from your account on the deadline.
2. Submit pretty-printed printouts (using a2ps or some comparable utility) of all source code files as well as your Makefile in class at 3:00pm.

Evaluation

Ninety percent of your score will come from correctness and 10% of your score will come from following our programming style guide. Applicable submission penalties will then be applied.

• If your program produces this output exactly when run on p2a.dat (all events: A, I, W, S, and D), you can earn up to 90 points.
• If your program produces this output exactly when run on p2b.dat (only events: A, I, W, and S), you can only earn up to 70 points.
• If your program produces this output exactly when run on p2c.dat (only events: A and I), you can only earn up to 50 points.
• If your program produces this output exactly when run on p2d.dat (only event: A), you can only earn up to 30 points.
• If your program does not produce this output exactly when run on p2d.dat, you will not earn any points.
• If your program does not compile or execute without errors or warnings, you will not earn any points.