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

	// 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)


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:


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:


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