CIS 307: TOPIC: Scheduling

Scheduling is treated in Tanenbaum Section 2.4

Introduction

		  ---+   +--+
	--------->||||-->|  |----> Departures
	Arrivals  ---+   +--+
		Queue    Server

Utilization: The ratio between the time the server is busy and the total observation time. Utilization is particularly significant when the cost of the server is high with respect to the cost of the time of the users. [This was the case in the Sixties when computers were very expensive. Computer centers in those days mainly cared about keeping their systems busy.]

Response Time: The time interval between when a job arrives to the system and when it leaves the system. Response time matters to users. The smaller the response time, the happier the user [of course, below certain response times, say a few hundredths of a second, it does not matter any more].

Fairness: Providing response times that are similar for users of the same kind. Fairness matters to users, expecially when it takes the form of a guaranty that the delay will not exceed a specified value.

Throughput: Number of jobs completed per unit of time. A useful observation is that we can determine easily a maximum throughput, called the saturation throughput. It is just the inverse of the service time. For example, for a disk where reads take 10 milliseconds we can do at most 100 reads per second.

A scheduling discipline can be simple or complex. Typically, the more frequent the scheduling decisions, the less sophisticated the scheduling discipline that is used. For example, the scheduling discipline used in the ready queue (micro-scheduling), is usually fairly simple, just priority scheduling. The scheduling discipline used for batch or swapped out jobs (macro-scheduling) tends to be more sophisticated.

The following features are used to classify scheduling disciplines (Ruschitzka&Fabry):

Decision Mode

It expresses when and how scheduling decisions are made. It can be:

• Preemptive (forced transition from running to ready state)
• Non-Preemptive, and
• Selective-Preemptive (for example, pairwise preemption).

Scheduling Function

It acts as a priority function. It is usually time based. It can represent:

• The attained service time a (i.e. the time spent on the server up to now)
• The real service time r (i.e. the time spent in the system up to now)
• The total service time t (i.e the total service time required for this job).

Arbitration Rule

It breaks ties in the scheduling function. It usually takes values:

• Random: the choice is made arbitrarily.
• Chronological: the choice favors the jobs that are longest in the system
• Cyclic: in the case of jobs that arrive and depart a number of times, it gives cyclically preference to the various jobs.

Feasibility

It indicates if the scheduling discipline can be actually implemented. It takes values:

• Realistic: it can be implemented
• Ideal: it cannot be implemented. For example, we cannot actually know for any job what will be its total service time (Turing's Halting Theorem).

	               | Priority | Decision  | Arbitration | Feasibility
Scheduling Algorithm   | Function | Rule      | Rule        | 
========================================================================
FIFO (FirstInFirstOut) | r        | No-Preempt| Random      | Realistic
------------------------------------------------------------------------
LIFO (LastInFirstOut)  | -r       | No-Preempt| Random      | Realistic
------------------------------------------------------------------------
SJF (ShortestJobFirst) | -t       | No-Preempt| Chronologic | Ideal
------------------------------------------------------------------------
SRT(ShortestRemainTime)| a-t      | Preempt   | Chronologic | Ideal
------------------------------------------------------------------------
RR (RoundRobin)        | constant | Preempt   | Cyclic      | Realistic
=======================================================================

	Job | Time
	=========
	1   | 6
	2   | 3
	3   | 8
	4   | 7

1:2:3:4

R = (6)+(6+3)+(6+3+8)+(6+3+8+7) = 1*7+2*8+3*3+4*6 = 56/4 = 14.

2:1:4:3

R = (3)+(3+6)+(3+6+7)+(3+6+7+8) = 1*8+2*7+3*6+4*3 = 52/4 = 13.

Theorem: SJF is optimal among non-preemptive scheduling disciplines.

Exponential Averaging

A job does not execute to completion without interruptions. Instead, it runs for a while, then blocks, then runs again, then blocks, etc. If we focus on these separate runs, and their execution times t1, t2, .., tn, we see a time series. If i runs have already taken place, and we need to estimate the time taken by the (i+1)th run, we can use information about the execution times and the estimated times that have occurred up to now. Here is a method for doing such estimating.

Let a be a real number in the interval [0,1]. Let e1 be an initial time estimate, then, for any i >= 1, we set

ei+1 = a*ti + (1-a)*ei

e2=8, e3=7, e4=6.5, e5=6.25, ..

A way to use the ideas of exponential averaging is the following (quantum is the amount of time that a process is allowed to run before it is preempted):

• Start a process at high priority and short time quantum.
• If a process blocks before its time quantum expires, reduce its quantum and increase its priority.
• If a process runs out its quantum without blocking, increase its quantum and reduce its priority.

Another way is the following:

• Say that we have N processes so that each process should receive about 1/N of the time. Initially all processes have their "natural" priority.
• If a process receives less than its fair share, its priority is increased
• If a process receives more than its fair share its priority is decreased.

An important thing to remember is that the scheduling we are discussing here (often called macroscheduling) is concerned with re-adjusting priorities that will then be used in (micro) scheduling at the level of the ready queue. These re-adjustments are done at regular intervals (usually more than one second).

Round Robin (RR)

Going back to the jobs considered earlier, let's examine their response time under the RR scheduling discipline for a variety of values of Q.

In case that Q is 2, the schedule has form

1:2:3:4:1:2 :3:4:1 :3:4:3 :4

In case that Q is 1, the schedule has form

1:2:3:4:1:2:3:4:1:2 :3:4:1:3:4:1:3:4:1 :3:4:3:4 :3

As you have seen, in Round-Robin both the schedule and response time change with changes in the Quantum Q. For example, if Q is chosen sufficiently large, say, greater than the service time of any job, then RR becomes equal to FCFS. People have chosen to evaluate RR when the value of the quantum goes to 0. In this case we say that we are in the processor sharing situation. Processor sharing seems to be the fairest way of using the computer since each user receives at all times the same amount of time, but it is inefficient because of all the process switches it requires (each process switch takes from 0.1 to 1ms, (thread switches can be almost an order of magnitude faster)). In practice the quantum tends to be 10 to 100 milliseconds.

In our example, job 2 will terminate after 12 seconds, job 1 after a total of 21 seconds, job 4 after a total of 23 seconds, and job 3 after 24 seconds. That is, the (average) Response Time becomes 80/4 = 20.

Notice that:

• In RR the Response Time has been growing as we approach processor sharing.
• RR is very fair, but has terrible average Response Time.
• Our example does not say anything about utilization (all schedules give the same utilization in this case).