CSC 420 Programming Assignment #1

Description

Write a C++ program that simulates the operation of a simple operating system. Assume there are N jobs running in the system, all initially in the Ready Queue. At time zero, the first process is dispatched to the CPU and begins running. A running process may either:

  1. Complete execution and terminate
  2. Run to the end of its time slice and return to the Ready Queue
  3. Call for I/O and be sent to the I/O Queue

This model is a simplified version of the "Queue-ing diagram" found on page 101 of our text, without the fork and generic interrupt options.

Please use a round-robin scheduling algorithm (page 163 of our text) to determine when processes are allotted CPU time. Processes are returned to the end of the Ready queue after the end of a CPU time slice or an I/O request.

Please use 10 milliseconds as your time slice for all simulations.

Input

The input to your program will be a text file of process descriptions to be placed on the ready queue. The format of the file will be:

<process_id> <cpu_burst> <io1_time> <io1_length> <io2_time> <io2_length>

   one process per line, where:
      <process_id> is the identifier for the process
      <cpu_burst> is the length of CPU burst needed for the process
      <io1_time> is the process CPU time at the first I/O request
      <io1_length> is the length of the first I/O request
      <io2_time> is the process CPU time at the second I/O request
      <io2_length> is the length of the second I/O request

Note that I/O requests 1 and 2 are optional. Time and length values of zero means that no I/O is needed. For example, the line:

1   50   22   10   29   12

means that process ID #1 requires 50 total milliseconds of CPU time. After 22 milliseconds of CPU time, the process will block for I/O request #1, lasting 10 milliseconds. After another 7 milliseconds of CPU time (or 29 milliseconds of total CPU time), the process will block again for 12 milliseconds for the 2nd I/O request.

All processes are assumed to arrive at time zero, but in the order they appear in the file. Please ignore lines in the file that begin with #; these lines will be considered comments.

Here's an example file:

# This is the example from our text, page 173
# You can run this example and compare results to 
# what is shown in the text. No I/O in this one
1   10   0   0   0   0
2   29   0   0   0   0
3   3   0   0   0   0
4   7   0   0   0   0
5   12   0   0   0   0

You will be expected to run your program on a set of data files of this format. These files will be located in the CSC 420 k: drive common folder:

k:/02SP/CSC420/Common Area/prog01/data/

Output

Your output should include:
Echo the input file, so that I/you know what your input data was
For each process, indicate:
the time of completion
the total wait time experienced... wait time is defined to be time spent on the Ready Queue waiting for the CPU.

For example, the output for the page 173 example input file above should be something like:

Process 1 completed at time 10 with a wait time of 0.
Process 3 completed at time 23 with a wait time of 20.
Process 4 completed at time 30 with a wait time of 23.
Process 5 completed at time 52 with a wait time of 40.
Process 2 completed at time 61 with a wait time of 32.

Deliverables and Schedule

Program #1 is worth 50 points, or 5% of your class grade.

Please place your source code, executable, and output data in a folder called "prog01" on your k: drive.

Design Phase [10 points]

Your design of Program #1 is due Tue Apr 9.

Your design should minimally address the following questions/issues:
What classes are defined in your program? What are the public methods?
What is the flow (in pseudo-code) of your program?
How will system time be maintained?
How will process stats be maintained?
Our programs are not multi-processing or multi-threaded, so how will you simulate "interrupts" for I/O blocking, I/O completion, time slice completion, process CPU completion, etc.
Describe the startup of your program. How will you know that your simulation is done?

So, please hand-in:

  1. C++ header files defining the public interface for each "important" class, including comments describing each class and public method. Here's an example of what I mean: process.h
  2. Pseudo-code describing your program's execution flow; this is probably your main() function.
  3. Your main.cpp file should include all the headers that you have defined, and it should successfully compile.

I hate to do it, but please print your headers and pseudo-code for grading/review.

Program Finale [40 points]

Program #1 is due Thursday April 18.

Deliverables include:

  1. Source code - commented and beautiful, of course
  2. Executable  - I must be able to run your program and get your results
  3. Output files - for each data set
  4. A README file - for organization notes or things I need to know when reviewing your program

You will be graded on:
Correctness of your results
Object-oriented design practices (though this does not mean I will take points off for not using the STL containers)
Clean code with understandable comments

I am less interested in:
Efficiency - I won't be grading how fast or efficient your simulation is
Error handling - I won't be giving you any "bad" data sets
I/O - I don't care how elegantly you handle program parameters and don't bother gussying-up the output

Notes

We will share design strategies and hints on Tuesday (so don't miss that class, eh).

Also, I will have the complete suite of test data by Tuesday as well.

Apr 16, 2002

Program is due on Thursday, the 18th. Please printout and hand in:

  1. Your README file describing how I can run your program, and anything else I should know about your program.
  2. Your output file for each dataset. Each output file should be less than a page long, or in other words, turn off your debugging for your final output runs.

Please don't print out your code. I will check this on the k: drive.

Also, I must be able to execute your program to verify your results. So, please make sure that an executable version of your program is available on the k: drive.

Thanks... yow, bill

 
Apr 10, 2002

First off, the 3 datasets for program #1 are available in the Common Area of our k: drive. I'll copy them here for people working off-campus:
page173.txt
data2002.txt
data1983.txt

Also, you are certainly free to copy these files to your local folder, so that you don't have long path to type in each time you debug.

We talked about a lot of things Tuesday. Here's a synopsis of some of the major "hints" or design approaches we discussed:
There's a formula you can use for "total wait time" for a process, rather than maintaining it while the process is on the Ready Queue.
Your CPU may not always be busy.
 Key classes and/or objects that we discussed include: Process, CPU, Scheduler, Interrupt, Ready Queue, IO List, etc. The objects and classes you select are up to you, of course.
Key areas to simulate are system clock and interrupts.

Make sure this weekend is a productive one and good luck!