Overview

Program behavior -

A program typically alternates between CPU bursts and IO bursts.

A program may be  either IO-bound or CPU-bound:

IO-Bound - the program will have many short CPU bursts.

CPU-Bound - the program will have many long CPU bursts.

Figure 6-1

Figure 6-2

Scheduling algorithms may be either:

Preemptive - the CPU is taken away from a process while it is running

Non-preemptive - CPU cannot be taken away.

Dispatcher - The module that gives control of the CPU to the process selected by the scheduler. Dispatch latency refers to the amount of time from when a higher priority thread becomes available and when it is finally running on a CPU.

Scheduling Criteria

1. CPU utilization

2. Throughput

3. Turnaround time

4. Waiting time

5. Response time

Generally, desktop operating systems favor short interactive processes at the expense pf CPU-intensive processes. Servers (i.e. webservers) may be configured to favor I/O bound processes.
 

Scheduling Algorithms

FCFS - no preemption

SJF - no preemption

Priority Scheduling

Round-Robin

Multilevel Queue Scheduling - Figure 6-6

Multilevel Feedback Queue Scheduling - Figure 6-7
 
<<We will work through an example illustrating RR scheduling with priorities.>>

SMP Scheduling

The benefits of SMP architectures is (1) greater system-wide throughput and (2) load sharing.
 

Realtime Scheduling

Hard RT - Guarantees a a response to a RT process in a bounded period of time.

Soft RT - Gives RT processes a higher priority than non-RT processes.

Most general purpose operating systems provide "support" for RT processes/threads (i.e. Windows NT/2000/XP, Linux, Solaris).

Furthermore POSIX has a realtime standard as does Java.

RT Scheduling Issues

Early operating systems (i.e. early versions of UNIX) were not preemptible while in kernel mode. While in kernel mode, interrupts were disabled. This results in not guaranteeing response times to a higher priority process (i.e. a RT process) when it becomes available to run.

Many modern operating systems are now fully preemptible, including Solaris and Mach. Linux and Windows 2000 are not fully preemptive. 

A problem with RT scheduling is priority inversion. Consider the scenario with  three processes P1, P2, and P3. P1 has the highest priority, P2 the next highest, and P3 the lowest. Assume a resouce P3 is assigned a resource R that P1 wants. Thus, P1 must wait for P3 to finish using the resource. However, P2 becomes runnable and preempts P3. What has happened is that P2 - a process with a lower priority than P1 - has indirectly prevented P3 from gaining access to the resource.

To prevent this from occurring, a priority inheritance protocol is used. This simply allows the priority of the highest thread waiting to access a shared resource to be assigned to the thread currently using the resource. Thus, the current owner of the resource is assigned the priority of the highest priority thread wishing to acquire the resource.

An important feature of RT systems is to minimize and bound the dispatch latency time. (Dispatch latency is the amount of time required to suspend one process and start another.)

Figure 6-8

Dispatch latency consists of a (1) conflict phase and (2) dispatch phase. The dispatch phase is simply scheduling the selected process to run on a CPU.

The conflict phase consists of:

1. Preempting any process running in the kernel.

2. Release of resources by low-priority processes needed by the high-priority process.

Obviously a fully-preemptive kernel is necessary to minimize dispatch latency. Furthermore, a priority inheritance protocol is necessary to ensure resources are made available to higher priority processes.

Thread Scheduling

Process Contention Scope (PCS)  - How the threads library schedules a thread onto an available LWP. Competition for the CPu is among threads belonging to the same process.

System Contention Scope (SCS)  - How the kernel decides which kernel thread to run next.

On systems where the mapping is 1:1, only SCS is used. On M:1 and M:M, scheduling is done using PCS.

POSIX Realtime Scheduling

POSIX defines three scheduling classes for realtime threads:

1. SCHED_FIFO - threads are scheduled using a FCFS policy with no time-slicing among threads of equal priority.
   
   
2. SCHED_RR - similar to SCHED_FIFO, except there is time-slicing among threads of equal priority.
   
   
3. SCHED_OTHER - system dependent and unspecified. May behave differently on different systems.
   

POSIX also defines two different scheduling policies:

1. PTHREAD_SCOPE_PROCESS - schedules threads using PCS.
   
   
2. PTHREAD_SCOPE_SYSTEM - schedules threads using SCS.
   

On systems using M:M, PTHREAD_SCOPE_SYSTEM binds each user-level thread to an associated LWP, thus effectively creating a 1:1 mapping.

- thrd-book.c

A more interesting example that illustrates how priorities may be altered:

- thrd.c

Solaris 2 Scheduling

- Four classes of proceses - (1) realtime, (2) system, (3) interactive, and (4) time sharing. The default class is time-sharing.

- within each class are different priorities and scheduling algorithms.

Figure 6-10

The timesharing scheduling algorithm dynamically alters priorities and assigns time slices of different lengths using a multilevel feedback queue. (times are in milliseconds)

Kernel threads all have a class-specific priority that is mapped to  a global priority.

The kernel thread with the highest global priority runs until:

(1) it blocks

(2) its time-slice expires

(3) it is preempted by a higher priority thread.
 
 

Windows 2000 Scheduling

We will work through an example of this in class.
 

Java Thread Scheduling

Loosely-defined, priority-based scheduling algorithm. The specification says threads with higher priority should be favored over lower priority threads. However, the JVM does not dynamically alter the priorities of individual threads so a lower priority thread may in fact run at the expense of a higher priority thread to prevent starvation.

A scheduling event occurs when:

1) the currently running thread exits the Runnable state.

2) the currently running thread is preempted.

Time Slicing

The specification for the JVM does not ensure threads are time-sliced or not.

To ensure time-slicing, a thread can voluntarily yield control of the CPU via the yield() method:
 

public void run() {
    while (true) {
        // perform some operation
        . . .
        // now yield control of the CPU
        Thread.yield();
    }
}

Thread Priorities

Each thread has a priority within the range of Thread.MIN_PRIORITY and Thread.MAX_PRIORITY. The default thread priority is Thread.NORM_PRIORITY. The default values for these constants are:
 
 

Threads may alter their priorities via the setPriority() method.
 
HighThread.java