CS 111 Scribe Notes
Lecture 7: Scheduling Algorithms
Spring 2012

by Scott Banks for a lecture by Professor Paul Eggert on April 24, 2012

Table of Contents

Threads

Threads vs. Processes

Threads are like processes, but share memory, file descriptors, owner, etc.
Threads do not share: IP, other registers, and stack.

Process and threads graphic

Process Memory
+========+
+        +
+        +
+        +
+========+
+        + <- Stack for Thread 1
+========+
+        + <- Stack for Thread 2
+========+
+        +
+        +
+        +
+========+

Pluses and Minuses of Threads

+ Speed (more CPUs)
+ Easier, faster, inter-thread communication vs. inter-process communication
+ Threading can be used as a modularization technique
- Race conditions galore, especially concerning shared memory. These are hard to debug.

POSIX Threads

int pthread_create(pthread_t *ID, const pthread_attr_t *attr, void * (*f)(void *), void *arg);

int pthread_join(pthread_t ID, void *status);

int pthread_exit(void *status);

Typically, # threads > # CPUs

Two Approaches to Threading

  1. Cooperative multithreading
  2. Preemptive multithreading

Cooperative Multithreading

In cooperative multithreading, each thread must yield every now and then. There should be no long-running loops without yielding. The old MacOS used this model of threading.

Preemptive Multithreading

Timer interrupts for preemptive multithreading

+ No longer require yield() all over the place
- Threads can no longer assume code without yields is "safe" (bad for real time)
- More race conditions

States of a Thread

States of a thread:

  1. Running
  2. Runnable but not running
  3. Blocked, waiting for resource R (device, pipe, thread...)

Associated with each resource is a queue of threads waiting for it. This is maintained by a "next" field in each thread descriptor.

Aside on Signals

What happens if a signal occurs in the middle of a syscall?

Event Driven Programming (Inverse of Threads)

Main program example:

for(;;){
	// Wait for events pselect(...)
	// Invoke its callback
}

+ Fewer race conditions
- One core only

Scheduling Problem: Scheduling a CPU

Mechanism - details of clock interrupt, thread descriptor, RETI to resume a thread
Policies - how to decide which to run

Scheduling is important for the CPU, disk arm, network device, etc.

Scheduling Scale

Scheduling Metrics

Developed for auto manufacturing!
Auto manufacturing analogy: an order for cars is received at the factory

Scheduling metrics graphic

Scheduling Statistics

There is a context switch time: this is the time it takes to switch from one task to another.

Scheduling Algorithms: First Come First Served (FCFS)

Example:

Job Arrival Time Run Time Wait Time Turnaround Time
A 0 5 Δ 5 + Δ
B 1 2 4 + 2Δ 6 + 2Δ
C 2 9 5 + 3Δ 14 + 3Δ
D 3 4 13 + 4Δ 17 + 4Δ
Avg: 5.5 + 2.5Δ 10.5 + 2.5Δ

The job is run as follows:

ΔAAAAAΔBBΔCCCCCCCCCΔDDDD

Total Time: 20 + 4Δ

Utilization: 20/(20 + 4Δ)

FCFS Characteristics:

Scheduling Algorithms: Shortest Job First (SJF)

Assumes job length is known.

The above example would be run as follows:

ΔAAAAAΔBBΔDDDDΔCCCCCCCCC

Job Wait Time Turnaround Time
A Δ 5 + Δ
B 4 + 2Δ 6 + 2Δ
C 9 + 4Δ 18 + 4Δ
D 4 + 3Δ 8 + 3Δ
Avg: 4.25 + .5Δ 9.25 + 2.5Δ

Total time: same as before

Utilization: Same as before

SJF Characteristics:

Valid HTML 4.01 Strict