Scheduling, Concurrency and Deadlock

Sharing one processor: scheduling

A processor can run only one thing at a time per core, yet a computer seems to run dozens of programs at once. The operating system's scheduler makes that happen. A running program is a process. The scheduler keeps the processes that are ready in a ready queue, picks one, lets it run for a while, and then picks another. Switching between them is a context switch: the state of the old process (its registers and program counter) is saved, and the state of the new one is loaded.

A scheduling algorithm tries to balance several goals, and they pull in different directions:

• throughput: finish as many processes as possible
• fairness: give every process a share, and let none starve
• response time: how soon a process starts running after it is ready
• turnaround time: from arrival to completion
• waiting time: the time spent in the ready queue, which is turnaround time minus the time actually running

A scheduler is pre-emptive if it can take the processor away from a running process. A non-pre-emptive one lets a process run until it finishes or waits.

Four algorithms

Take four processes, each with an arrival time and a burst time (how long it needs the processor):

• First come first served (FCFS). Run them in order of arrival. Simple and fair in its way, but one long job at the front delays every short one behind it (the convoy effect).
• Shortest job first (SJF). When the processor is free, run the waiting process with the smallest burst. It gives the best average waiting time for a non-pre-emptive scheduler, but needs to know how long each job will take, and long jobs may be starved.
• Shortest remaining time (SRT). A pre-emptive SJF: whenever a process arrives that needs less time than the one running has left, switch to it.

procs = [("A", 0, 8), ("B", 1, 4), ("C", 2, 9), ("D", 3, 5)]      # name, arrival, burst

def fcfs(procs):
    t, timeline = 0, []
    for name, arrival, burst in sorted(procs, key=lambda p: p[1]):
        while t < arrival:
            timeline.append(".")                  # the processor is idle
            t += 1
        timeline.extend([name] * burst)
        t += burst
    return timeline

def sjf(procs):
    todo, t, timeline = list(procs), 0, []
    while todo:
        ready = [p for p in todo if p[1] <= t]
        if not ready:
            timeline.append(".")
            t += 1
            continue
        job = min(ready, key=lambda p: p[2])      # the shortest of those waiting
        todo.remove(job)
        timeline.extend([job[0]] * job[2])
        t += job[2]
    return timeline

def srt(procs):
    left = {name: burst for name, arrival, burst in procs}
    t, timeline = 0, []
    while any(left.values()):
        ready = [(left[n], n) for n, arrival, burst in procs if arrival <= t and left[n] > 0]
        if not ready:
            timeline.append(".")
            t += 1
            continue
        _, name = min(ready)                      # the least time still to go
        left[name] -= 1
        timeline.append(name)
        t += 1
    return timeline

def report(title, timeline, procs):
    waits, turns, responses = [], [], []
    for name, arrival, burst in procs:
        finish = max(i for i, who in enumerate(timeline) if who == name) + 1
        start = timeline.index(name)
        turns.append(finish - arrival)
        waits.append(finish - arrival - burst)
        responses.append(start - arrival)
    count = len(procs)
    print(title.ljust(14), "".join(timeline))
    print(" " * 14, "average wait", round(sum(waits) / count, 2), "| turnaround", round(sum(turns) / count, 2),
          "| response", round(sum(responses) / count, 2))

report("first come", fcfs(procs), procs)
report("shortest job", sjf(procs), procs)
report("shortest left", srt(procs), procs)

Each letter in the line is one unit of time, so the line is a Gantt chart of who had the processor. Notice that SRT has the lowest waiting time of the three, and that FCFS has the worst: process D waited behind everything.

Round robin and multi-level queues

Round robin is built for sharing. Each process gets a fixed slice of time called the quantum. If it is not finished when the quantum ends, it is pre-empted and joins the back of the queue. Nobody waits long to start, so it suits interactive systems.

procs = [("A", 0, 8), ("B", 1, 4), ("C", 2, 9), ("D", 3, 5)]

def round_robin(procs, quantum):
    left = {name: burst for name, arrival, burst in procs}
    arrivals = sorted(procs, key=lambda p: p[1])
    queue, t, timeline, i = [], 0, [], 0
    while any(left.values()):
        while i < len(arrivals) and arrivals[i][1] <= t:
            queue.append(arrivals[i][0])
            i += 1
        if not queue:
            timeline.append(".")
            t += 1
            continue
        name = queue.pop(0)
        for _ in range(min(quantum, left[name])):
            timeline.append(name)
            t += 1
            left[name] -= 1
            while i < len(arrivals) and arrivals[i][1] <= t:
                queue.append(arrivals[i][0])
                i += 1
        if left[name] > 0:
            queue.append(name)                  # not finished: back of the queue
    return timeline

def report(title, timeline, procs):
    waits, responses = [], []
    for name, arrival, burst in procs:
        finish = max(i for i, who in enumerate(timeline) if who == name) + 1
        waits.append(finish - arrival - burst)
        responses.append(timeline.index(name) - arrival)
    count = len(procs)
    print(title.ljust(14), "".join(timeline))
    print(" " * 14, "average wait", round(sum(waits) / count, 2), "| response", round(sum(responses) / count, 2))

for quantum in (1, 3, 8):
    report("quantum " + str(quantum), round_robin(procs, quantum), procs)

Round robin has a worse average waiting time than FCFS here, but a far better response time: every process starts within a few units. The quantum is a trade-off. If it is too long, round robin behaves like FCFS (look at the quantum of 8). If it is too short, the processor wastes more and more time on context switches.

A multi-level feedback queue (MLFQ) has several queues of different priorities, so it can serve both kinds of job:

1. A new process enters the top queue, which has the shortest quantum.
2. The scheduler always runs a process from the highest queue that is not empty.
3. A process that uses its whole quantum is demoted to the queue below, which has a longer quantum.
4. A process that gives up the processor early, for example to wait for the keyboard, stays where it is.
5. To stop low-priority processes starving, a process that waits too long is moved up again (this is called aging).

Short and interactive jobs finish in the top queues, while long calculations sink to the bottom and run in big slices.

Tasks that take turns

Concurrency means several tasks are in progress at the same time, whether or not any two are being executed at the same instant. On one core the processor switches rapidly between them. Parallelism means tasks really are executing at the same instant, on separate cores. A concurrent program may run in parallel, but does not need to.

You can model concurrency in Python without any special tools, using generators. A function that contains yield can pause in the middle and be resumed exactly where it left off. A yield is a point where the task offers to give up the processor, and a small scheduler decides who runs next.

def task(name, steps):
    for step in range(1, steps + 1):
        print(name, "does step", step)
        yield                          # pause here: someone else can have a turn

def scheduler(tasks):
    queue = list(tasks)
    while queue:
        current = queue.pop(0)
        try:
            next(current)              # run it until its next yield
            queue.append(current)      # not finished: back of the queue
        except StopIteration:
            pass                       # finished: leave the queue

scheduler([task("A", 3), task("B", 2), task("C", 4)])

The output interleaves A, B and C. This is exactly round robin with a quantum of one step. Real schedulers use a timer interrupt to take the processor away, instead of waiting for a yield, but the effect on the programs is the same: the task is paused in the middle, and later carries on.

This model is useful because it is deterministic. You can choose exactly which task runs when, and so reproduce a bug that on a real system would appear once in a million runs.

Race conditions and locks

Tasks that share data can interfere. Suppose two tasks each deposit money into one account. Each does three things: read the balance, calculate the new balance, write it back. If task B reads the balance between task A's read and write, A's deposit is lost. The result depends on timing, which is a race condition.

Model the two steps that matter (read, then write) with a yield between them, and try every possible interleaving of the two tasks:

from itertools import permutations

def deposit(shared, amount):
    seen = shared["balance"]              # read
    yield                                 # the scheduler may switch tasks here
    shared["balance"] = seen + amount     # write

def run(order):
    shared = {"balance": 100}
    tasks = {"A": deposit(shared, 50), "B": deposit(shared, 25)}
    for who in order:
        try:
            next(tasks[who])
        except StopIteration:
            pass
    return shared["balance"]

outcomes = {}
for order in sorted(set(permutations("AABB"))):
    outcomes["".join(order)] = run(order)

for order, balance in outcomes.items():
    print(order, "->", balance)
print("possible final balances:", sorted(set(outcomes.values())))

The right answer is 100 + 50 + 25 = 175. It is only produced when A finishes completely before B starts, or the other way round. In the other four orderings one deposit overwrites the other, giving 125 or 150. The program is sometimes right, which is the worst kind of wrong.

The section of code that must not be interleaved is a critical section. The solution is mutual exclusion: only one task may be inside it at a time. A lock (or mutex) does this. A task must acquire the lock before entering, and others wait until it is released.

from itertools import permutations

def safe_deposit(shared, amount):
    while shared["locked"]:
        yield                              # wait for the lock to be free
    shared["locked"] = True                # acquire the lock
    seen = shared["balance"]
    yield                                  # even a switch here is now harmless
    shared["balance"] = seen + amount
    shared["locked"] = False               # release the lock

def run(order):
    shared = {"balance": 100, "locked": False}
    tasks = {"A": safe_deposit(shared, 50), "B": safe_deposit(shared, 25)}
    position = 0
    while tasks:
        who = order[position % len(order)]    # follow the plan, skipping tasks that have finished
        position += 1
        if who in tasks:
            try:
                next(tasks[who])
            except StopIteration:
                del tasks[who]
    return shared["balance"]

balances = {run(order) for order in set(permutations("AABB"))}
print("possible final balances:", balances)

Every order now gives 175. Locks have a cost: waiting tasks do nothing, and a lock that is never released stops everything behind it. A semaphore generalises a lock to a counter, allowing up to n tasks into a section at once, such as n connections to a database.

Deadlock

Locks fix one problem and can cause another. Suppose task 1 needs lock A and then lock B, and task 2 needs B and then A. If task 1 takes A and task 2 takes B, each is now waiting for a lock the other holds. Neither can go on, and neither will ever let go. This is deadlock.

A deadlock needs four conditions at once (the Coffman conditions):

1. Mutual exclusion. A resource can be used by only one task at a time.
2. Hold and wait. A task holds one resource while waiting for another.
3. No pre-emption. A resource cannot be forcibly taken from the task holding it.
4. Circular wait. A ring of tasks, each waiting for a resource held by the next.

Here is a tiny simulation. Each task is a generator that yields requests to acquire or release a lock, and the scheduler grants them if it can. If a whole round passes with no progress, the tasks are deadlocked. The scheduler then builds the wait-for graph and looks for a cycle.

def worker(first, second):
    yield ("acquire", first)
    yield ("acquire", second)
    yield ("release", second)
    yield ("release", first)

def simulate(tasks):
    held, waiting, requests = {}, {}, {}
    live = dict(tasks)
    for name, gen in live.items():
        requests[name] = next(gen)
    log = []
    while live:
        progress = False
        for name in list(live):
            kind, lock = requests[name]
            if kind == "acquire" and lock in held:
                waiting[name] = lock             # blocked: someone else holds it
                continue
            waiting.pop(name, None)
            if kind == "acquire":
                held[lock] = name
            else:
                del held[lock]
            log.append(name + " " + kind + " " + lock)
            progress = True
            try:
                requests[name] = next(live[name])
            except StopIteration:
                del live[name]
        if not progress:
            return log, waiting, held             # nobody can move
    return log, {}, {}

def find_cycle(waiting, held):
    graph = {task: held[lock] for task, lock in waiting.items()}     # waits for whoever holds its lock
    for start in graph:
        seen, node = [], start
        while node in graph and node not in seen:
            seen.append(node)
            node = graph[node]
        if node in seen:
            return seen[seen.index(node):]
    return None

print("opposite order:")
log, waiting, held = simulate({"T1": worker("A", "B"), "T2": worker("B", "A")})
print("  ", log)
print("   waiting:", waiting, "| held:", held)
print("   cycle:", find_cycle(waiting, held))

print("same order:")
log, waiting, held = simulate({"T1": worker("A", "B"), "T2": worker("A", "B")})
print("  ", log)
print("   waiting:", waiting)

In the first run T1 holds A and wants B, while T2 holds B and wants A: a cycle, so deadlock. In the second, both ask for the locks in the same order. T2 simply waits for T1 to finish, so a circular wait is impossible.

Dealing with deadlock

A related problem is starvation: a task that never gets a turn, because others keep being chosen first. The ageing in a multi-level queue is there to prevent it.

Threads, processes and parallel speed-up

A process is a running program with its own memory. A thread is a path of execution inside a process. Threads of one process share its memory, which makes them quick to create and easy to share data between, and also the source of every race condition above. Separate processes do not share memory, so they are safer and slower to communicate.

Python's real threading module runs in a browser tab only as a simulation, so the examples in this section need your own computer. The first uses a lock to protect a counter shared between four threads:

import threading

total = 0
lock = threading.Lock()

def count(times):
    global total
    for _ in range(times):
        with lock:                    # only one thread at a time in this block
            total += 1

threads = [threading.Thread(target=count, args=(100000,)) for _ in range(4)]
for t in threads:
    t.start()
for t in threads:
    t.join()                          # wait for each thread to finish

print(total)                          # always 400000 with the lock

A queue is the safe way to hand work from one thread to another. put waits if it is full and get waits if it is empty, so the producer and consumer never need a lock of their own:

import queue
import threading

jobs = queue.Queue(maxsize=3)

def producer():
    for n in range(6):
        jobs.put(n)
    jobs.put(None)                    # a marker meaning: no more work

def consumer():
    while True:
        item = jobs.get()
        if item is None:
            break
        print("handled", item)

workers = [threading.Thread(target=producer), threading.Thread(target=consumer)]
for w in workers:
    w.start()
for w in workers:
    w.join()

For many similar jobs, a pool is tidier. The next program fetches five things that each take half a second to arrive. One after another they would take two and a half seconds. In a pool of threads, they all wait at once:

import time
from concurrent.futures import ThreadPoolExecutor

def fetch(n):
    time.sleep(0.5)                   # stands for waiting on a network reply
    return n * n

start = time.perf_counter()
with ThreadPoolExecutor(max_workers=5) as pool:
    results = list(pool.map(fetch, range(5)))
print(results, round(time.perf_counter() - start, 1), "seconds")     # about 0.5

The same job with asyncio uses a single thread, and tasks that hand over control at each await. It is the same cooperative idea as the generators earlier, with the language doing the scheduling:

import asyncio

async def fetch(n):
    await asyncio.sleep(0.5)
    return n * n

async def main():
    results = await asyncio.gather(*(fetch(n) for n in range(5)))
    print(results)

asyncio.run(main())

Threads do not speed up heavy calculation

The standard version of Python has a global interpreter lock (the GIL): only one thread executes Python code at a time. Threads still help when programs spend their time waiting for a network or a disk, because the lock is released while they wait. But for a long calculation, four threads take as long as one. The remedy is separate processes, each with its own interpreter:

from multiprocessing import Pool

def count_primes(limit):
    count = 0
    for n in range(2, limit):
        if all(n % d for d in range(2, int(n ** 0.5) + 1)):
            count += 1
    return count

if __name__ == "__main__":
    with Pool(4) as pool:             # four processes, so up to four cores
        print(pool.map(count_primes, [60000] * 4))

How much faster can parallel processing be?

If a program is split between n processors, you might expect n times the speed. Amdahl's law says why not: part of any program cannot be split up (reading the input, combining the results). If a fraction p of the work can be run in parallel, the best possible speed-up with n processors is:

speed-up = 1 / ((1 - p) + p / n)

def speedup(p, n):
    return 1 / ((1 - p) + p / n)

print("processors  90% parallel  50% parallel")
for n in (1, 2, 4, 8, 16, 64, 1000):
    print(str(n).ljust(11), str(round(speedup(0.9, n), 2)).ljust(13), round(speedup(0.5, n), 2))
print("the limit when 90% is parallel is", round(1 / (1 - 0.9)), "times, however many processors")

A program that is 90% parallel can never go more than ten times faster, even with a thousand processors. The part that cannot be shared sets the limit. That is why parallel hardware pays off only for software designed to use it.

Key terms you must be able to define

Scheduler

The part of the operating system that decides which process uses the processor, and for how long.

Context switch

Saving the state of the running process and loading the state of the next one.

Pre-emption

The operating system taking the processor away from a running process before it has finished.

Round robin

A scheduling algorithm that gives each process in turn a fixed time slice, the quantum.

Shortest job first

A scheduling algorithm that runs the waiting process with the shortest burst time.

Multi-level feedback queue

A scheduler with several queues of different priorities, in which processes move between queues according to how they behave.

Turnaround time

The time from a process arriving to its completion.

Concurrency

Having several tasks in progress at once, by taking turns or by running at the same time.

Parallelism

Tasks actually executing at the same instant on separate processors or cores.

Race condition

A fault where the result depends on the exact timing of tasks that share data.

Critical section

A part of a program that accesses shared data and must not be run by two tasks at once.

Mutual exclusion (lock)

Allowing only one task at a time into a critical section, usually with a lock.

Deadlock

A state in which every task in a group is waiting for a resource held by another, so none can go on.

Starvation

A task never getting the processor or resource it needs because others are always chosen first.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Scheduling is examined as calculation and as comparison. Concurrency is examined as explanation, with an example.

• In a calculation, draw the Gantt chart first, then read the waiting times from it
• Waiting time = completion time - arrival time - burst time
• Compare algorithms against a criterion: fairness, response, starvation, throughput
• For a race condition, describe the interleaving that goes wrong, not just the phrase
• For deadlock, name the circular wait and state one way to prevent it, such as acquiring resources in the same order

Mistakes that cost marks here