CSC468/2204 TUTORIAL – WEEK 6

by Tristan Miller -- Updated 7 November 2000

FOCUS ON ASSIGNMENT #2, QUESTION #1

  • question #1 involves simulating an OS’s process scheduler
  • just like in a real computer, jobs arrive at a scheduler at various intervals
  • the exact processing time of a job is known at arrival time (this is rarely true in real life, but it would be hard to make a simulation otherwise)
  • the scheduler’s job is to decide which process gets control of the CPU at any given instant

  • jobs (J0..Jn) enter the system, arriving at the scheduler, which maintains a queue of waiting jobs. The scheduler then uses some set of rules (i.e. a scheduling algorithm) to select a certain job from the queue and run it on the CPU
  • for some scheduling algorithms, the scheduler may remove a job from the CPU and put it back in the queue to resume processing later – this is known as preemption
  • with each job is associated a service time – that is, how much CPU time it takes to finish the job
  • the service time averages 9 seconds, and is randomly determined with an exponential distribution
  • with each job is also associated an interarrival time – that is, how long after the previous job arrived
  • jobs arrive an average of 10 seconds after the previous job arrives – the exact interarrival time is also randomly determined with an exponential distribution
  • for job interarrival and service time, we need to generate some random number r with an exponential distribution function f which is continuous and strictly increasing when 0 < f(x) < 1
  • to do this, first we generate some random number u between 0 and 1
  • then
  • what is the exponential function such that it has a given mean m? It’s .
  • therefore (for 0 < x < 1)
  • thus generates an exponentially distributed random number with mean m when u is some random number between 0 and 1
  • you will need to look up the Java functions for generating random numbers and for determining natural logarithms

* * * * *

What follows is an example of various scheduling algorithms. In the example, all the jobs (= processes) have integral service requirements and interarrival times. This is done for simplicity’s sake. In your assignment, you will be generating random service requirements and interarrival times which may fall betweenintegers. Do not round the numbers to the nearest integer!

Job

/ Service requirement /
Interarrival time
/
Arrival instant
P1 / 4 / 0 / 0
P2 / 2 / 0 / 0
P3 / 3 / 2 / 2
P4 / 2 / 4 / 6

FCFS (First Come, First Served)

Instant / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13
CPU / P1 / P2 / P3 / P4
Queue / P2 / P2
P3 / P3 / P4
  • At instant 0, both P1 and P2 arrive at the same time; either one may be selected to run while the other is put in the queue. (Let’s pick P1 to run.)
  • At instant 2, P3 arrives. P1 is already running, so P3 is put in the queue
  • At instant 4, the P1 finishes and the CPU becomes available. The scheduler selects P2 to run because it arrived first.

SRTF (Shortest Remaining Time First)

Instant / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13
CPU / P2 / P3 / P1 / P4 / P1
Queue / P1 / P1 / P1
  • At instant 0, both P1 and P2 arrive at the same time. The scheduler runs P2 first because it has the shortest remaining service time (2 vs. P1’s 4)
  • At instant 2, P2 finishes and P3 arrives. The scheduler runs P3 because it has 3 seconds left, compared to P1’s 4 seconds.
  • At instant 5, P3 finishes. P1 is the only process in the queue, so the scheduler runs it.
  • At instant 6, P4 arrives. It has a lower remaining service time (2 seconds) than P1 (3 seconds), so the scheduler preempts P1 and runs P4 instead
  • Important note: in your simulation, the scheduler should preempt only when a new process with a higher priority (i.e. lower SRT) arrives. Recomputing priorities should be done only when processes arrive or finish.
  • Use FCFS to resolve ties (i.e. if two or more processes have equal shortest remaining service times, the oldest process in the system gets the CPU).

RR (Round Robin)

Instant / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13
CPU / P1 / P2 / P1 / P3 / P2 / P1 / P3 / P4 / P1 / P3 / P4
Queue / P2 / P1 / P3
P2 / P2
P1 / P1
P3 / P3 / P4
P1 / P1
P3 / P3
P4 / P4
  • Quantum = 1
  • Scheduling is re-evaluated every 1 second after a process begins executing (or less if its remaining service time is less than 1 second). If there are waiting processes, the currently-running process is preempted and relegated to the end of the queue.
  • At instant 2, P3 arrives and is put on the end of the queue. Also at this instant, P2 is preempted and put on the end of the queue. P1 is at the head of the queue, so the scheduler runs it. (Actually, since the events are simultaneous, the scheduler may process the preemption of P2 before the arrival of P3, resulting in a different queue ordering. In your assignment, it is highly unlikely that you will ever have a quantum expire at the exact instant a process arrives, so you don’t have to deal with this.)

HRRN (Highest Response Ratio Next)

Instant / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13
CPU / P1 / P2 / P3 / P4
Queue / P2 / P2
P3 / P3 / P4
  • Job’s priority is calculated as (W + S) / S, where W is the job’s total waiting time (in the queue) and S is the job’s total service requirement
  • The algorithm is non-preemptive, so once a process is selected to run, it runs to completion
  • At instant 0, priority of P1 is (0 + 4) / 4 = 1 and priority of P2 is (0 + 2) / 2 = 1. Either one may be run. (Let’s pick P1.)
  • P1 runs to completion at instant 4. By then, there are two jobs in the queue. P2’s priority is (4 + 4) / 4 = 2 and P3’s priority is (2 + 3) / 3 = 1.666… Scheduler picks P2.
  • P2 runs to completion at instant 6. Simultaneously, P4 arrives, so it is a candidate, along with P3, for control of the CPU. P3’s priority is (4 + 3) / 3 = 2.333… and P4’s priority is (0 + 2) / 2 = 1. P3 is selected to run.
  • If two processes in the queue have the same priority, use FCFS to break the tie.

* * * * *

  • the assignment asks you to compute the sample mean and sample variance of job waiting time for each scheduling algorithm
  • recall from basic statistics, the mean is , where n is the total number of jobs sampled
  • e.g. for FCFS, there were 4 jobs. P1 waited for 0 seconds, P2 waited for 4 seconds, P3 waited for 4 seconds, and P4 waited for 3 seconds, so the mean is (0 + 4 + 4 + 3) / 4 = 2.75
  • similarly, the sample variance is
  • note that the assignment also asks you to consider the case where you have two processors with a single scheduler: