CIS 307: TOPIC: Scheduling

• Introduction
• First-Come-First_Served (FCFS), and Shortest Job First (SJF)
• Exponential Averaging
• Round Robin (RR)

Scheduling is treated in Tanenbaum Section 2.4

Introduction

Consider a single server queue system:

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

The scheduling discipline (or policy) is used to select a job out of the queue whenever the server becomes available. Examples of scheduling disciplines are FCFS (First Come First Served), SJF (Shortest Job First), RR (Round Robin).
What should we look for in selecting which scheduling policy to use? Usually we look for three things:

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.

Unfortunately it is not possible to have a scheduling discipline that is optimal from all three viewpoints. Currently people tend to favor fairness, over response time, over utilization. Or they favor response time, over fairness, over utilization.

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

I 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).

Here are a few scheduling disciplines and their features:

	               | 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
=======================================================================

First-Come-First_Served (FCFS), and Shortest Job First (SJF)

Let's evaluate FCFS and SJF in the case of the following jobs, listed in arrival order:

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

The schedule for FCFS is

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, ..

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 >q

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.

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).
  ingargiola.cis.temple.edu