proj02
Process scheduling

ITEC371 (OS), 2015fall-mhtay

Due 2015-Mar-18 (Wed)22 (Sun) 23:59, D2L and hardcopy (in following class)

Design and implement a program that simulates CPU scheduling techniques in UNIX environment. CPU scheduling is a fundamental operating ­system function. It is the allocation of CPU time to processes in multi programmed operating systems. The allocation scheme could be different from one system to another depending on their scheduling algorithms. Although this CPU scheduling project is not as complicated as in real operating systems, it allows you to design your own CPU scheduling policy.

Scheduling Policy:

You are required to implement a Multilevel Queue scheduling algorithm in this project. The general descriptions of this algorithm can be found in Silberschatz §5.3.6. The following are specific requirements of this project:

1. The ready-queue is partitioned into three separate queues: the foreground, intermediate, and background queue. All queues are scheduled by the round-robin scheduling algorithm (Silberschatz § 5.3.4).
2. New processes are added to the foreground queue. These processes will be assigned to the CPU in round-robin fashion. However, if a process has been assigned to the CPU for a certain quantum time and yet has not finished its execution, then the process will be re­allocated to the intermediate queue. Then, again if the process from the intermediate queue has not finished its execution after being assigned to CPU for a certain quantum time, the process will be shifted to the background queue. At the background queue, the roundrobin scheduling mechanism will be applied until the process finishes its execution. (Note that you may use the priority field in the PCB structure as a counter of the number of times the process has been assigned to the CPU).
3. Use a fixed-priority preemptive scheduling scheme: no process in the intermediate queue could run unless the foreground queue is empty. Likewise, a process in the background queue will not be allocated to the CPU unless the intermediate queue is empty. If a process enters the foreground queue during the execution of a process from the intermediate or background queues, the running process must be preempted and put back to the end of the appropriate queues; the preempted process may be put back to its old queue or to the new queue following the rule in the first requirement depending on the number of times it was assigned to the CPU.

Instructions

• Submit your program files along with a ReadMe file which explains:
  1. How to build and run your program;
  2. the data structures and algorithms you used;
  3. A summary of your results of this 3-tier algorithm: Which quanta seemed to work well? What are the strengths and weaknesses of this algorithm?

  You can write your program in C, C++, Java, Ada, python, or racket. (See me if you want to use a different language.) You may use standard libraries and data structures¹. Your main program should be named “schedule” with the appropriate suffix (and capitalized if using Java); for compiled languages the resulting executable should be named “schedule”.

• The main command-line inputs to your program is the number of jobs to simulate, but various parameters can optionally be supplied. Usage:
  
  schedule numJobs [foreground-quantum [intermediate-quantum [job-length [job-frequency [seed]]]]]
  
  • numJobs is the number of jobs to complete, before ending the simulation² (non-negative int).
  • foreground-quantum is the number of cpu-slices a job gets, before being moved to the intermediate-queue (non-negative int)
  • intermediate-quantum is the number of cpu-slices a job gets while in the intermediate-queue, before being moved to the background-priority queue (non-negative int)
  • job-length is the average job-length³ in cpu-slices (positive float). (Thus is a cpu-slice were a microsecond, then this would be the average job-length in seconds.)

    Edit: I have removed the 'scaling' for this parameter and the next; you can just enter number in straight-up cpu-slices (or, for the job-frequencey, jobs/cpu-slice). However, if you have already implemented the version where you scaled by 10⁶, that's fine too — just make it clear in your ReadMe file. Note that it's easy (but not required) to let the caller enter numbers in scientific notation, like “37e-4”; standard libraries (like Double.parseDouble in Java) will correctly turn this into a number.

  • job-frequency is the average number of new jobs per cpu-slice (non-negative float). This number is λ for the corresponding Poisson distribution, in jobs/cpu-slice.
  • seed is a value to seed the pseudorandom number generators (int). Running the program twice with the same seed should give the exact same results.
  Use reasonable defaults, for the optional arguments.

  Note that the unit of time is “cpu-slice” (rather than seconds), since this simulator is concerned with scheduling algorithms and progress on jobs, independent of what cpu it is running on.

• For each job, print:
  • its arrival-time,
  • a note about its queue-changes (if any),
  • its finish-time, and
  • its turnaround time (expressed as a multiple of its length).
  At the end of the simulation, print a summary: the input parameters, the average job-length, and average job-turnaround time (as a multiple of its length). You may print further pertinent statistics, if you like (e.g. cpu-usage).

  If you like, you may allow an initial, optional command-line argument “--summary-only”, which suppresses the per-job information.

• Use a pseudorandom-number generator to appropriately generate the time between job-arrivals (use an exponentional distribution), and job-lengths (use any reasonable distribution).