Technical note

Operating Systems: A Brief Overview (Part 2)

Context switching, threads, mutual exclusion, semaphores, and deadlocks — part two of the operating systems series.

This is part 2 of 3 in the operating systems series. Part 1 covered understanding computers, the OS, kernels, multi-programming, and processes.

Context Switching

When does a process switch occur?

  • Interrupts — when hardware servicing is needed
  • Trap — when OS support is required
  • Blocking System Calls — when a process requests OS support

When a context switch (process switch) occurs, all of the process's context (state, memory, etc.) is saved into the PCB. The PCB then moves to a different queue (ready / blocked). Meanwhile, another process is selected with the help of a short-term scheduling algorithm and moved to the processing block. Memory management is updated accordingly. When the process finishes, the initial context of the previous process is restored. The original process is left unaware of the switch, and carries on the work from where it left off.

On a multi-processing computer, problems related to process switching become more complex and happen more often.

Multi-Threaded Environments

First, let's understand threads better.

Threads

Threads are the smallest unit of work in programming. They share resources of the processes they belong to, yet run independently and asynchronously.

Why Have Multiple Threads?

  • Ease of communication
  • An effective solution to prevent blocking while reading data
  • Easy to create (creates a TCB)

Disadvantages of Multiple Threads

Risk of asynchronicity may occur when two threads run at the same time:

  • A running thread may be interrupted due to hardware considerations, and a different thread chosen to run.
  • Two threads running on two different CPUs, not properly synchronized, can cause a lot of trouble.

Three important things to note:

  • Processes concern themselves with resource ownership.
  • Threads are the running parts, or executables, of the process.
  • No process can exist without a thread.

Process: Process Control Block

The PCB is responsible for memory allocation, linkage, and files.

Threads: Thread Control Block

Responsible for context in processor registers, stacks that store local variables, and access to all the resources of the thread.

Reasons for Multi-Threading

  • Foreground / background applications
  • Asynchronous processing
  • Infrequent tasks
  • Speeding up reads
  • Synchronous processing

Downsides of Threads

  • Concurrency issues
  • Overuse of threads leads to confusion

Implementation of Threads

  • Kernel Level Threads — different from kernel threads
  • User Level Threads (ULTs) — with their own downsides
  • Hybrid Approach — lightweight processes
  • Thread Scheduling — has its own set of details worth exploring separately

Critical Section

Critical Code

Critical code is the part of a program that always runs through to completion without being interrupted. A good program makes sure the critical code is as small as possible, and that the CPU gets in and out of the critical section as soon as possible. An important rule of critical code is that it should always run atomically.

Mutual Exclusion

Mutual exclusion explicitly states that no two threads can be in the critical section at the same time.

Fundamentals of Mutual Exclusion: Using a System Bus

Using a system bus to transfer memory is one of the most fundamental ways to enforce mutual exclusion. While one thread has access to memory via the system bus, the other thread has to wait.

Software Solution to Mutual Exclusion: Peterson's Algorithm

The main purpose of Peterson's algorithm is to protect two threads from accessing the same resource at the same time. Each thread is assigned a boolean flag variable, and there's also a turn variable used for checking and changing the flag. When a thread wants to enter a critical section, it raises its flag and offers the turn to the other thread.

flag = [False, False]
turn = 0

def P0():
    while True:
        flag[0] = True
        turn = 1
        while flag[1] and turn == 1:
            pass  # do nothing
        # critical section
        flag[0] = False

def P1():
    while True:
        flag[1] = True
        turn = 0
        while flag[0] and turn == 0:
            pass  # do nothing
        # critical section
        flag[1] = False

The problem with Peterson's algorithm: it limits the number of threads that can access the critical section to two.

Hardware Solutions to Mutual Exclusion

  1. Disable Interrupts — prevents the CPU from being interrupted, and also prevents asynchronicity. In practice, though, it's a very bad idea to disable interrupts.
  2. Test and Set — a single machine-language instruction checks a memory location using a boolean flag and sets it if not already set. The result indicates success or failure.
  3. Exchange — the location in memory is swapped with a register, making it unavailable to other threads and processes.

Semaphores

A semaphore provides mutual exclusion and is very similar to a boolean flag. The operating system provides some semaphore services, most of which happen in user space. The primary functions of a semaphore are:

  • wait() — causes the thread to block if there are no signals.
  • signal() — can be queued, or if a thread is waiting, can cause it to be released.

To consume a signal, a thread is queued to await the next one.

A semaphore relies on a signal being queued initially. Before entering the critical section, a thread calls wait(); while exiting, it calls signal(). No thread in the critical section means there's a signal() in the queue.

Internal Semaphore

Internally, a semaphore keeps a counter for the number of signal()s sent. wait() decrements the counter; if the counter drops below 0, the thread and all subsequent threads are blocked and queued by the OS.

The problem with an internal semaphore: the act of checking and modifying it is itself a critical section, so semaphores have to rely on a hardware solution to prevent asynchronicity.

Deadlocks

Threads that are all waiting for each other to release resources are termed deadlocked, also known as a permanent block. There is no efficient general solution for handling deadlocks.

Deadlock Resource Types

  • Reusable — memory, devices, data structures, and semaphores
  • Consumable — interrupts, signal()s, messages, data in an I/O buffer

Requirements for Deadlock

  • Mutual Exclusion — occurs when resources aren't shareable
  • Hold and Wait — holding a resource while waiting for new resources
  • No Preemption — resources can't be forcefully released or removed unless the process releases them
  • Circular Wait — a set of processes waiting for each other in a circular chain

Deadlock Solutions

  • Deadlock Prevention — eliminate any one requirement for deadlock
  • Deadlock Avoidance — Banker's Algorithm, which ensures resources are never allocated in a way that fails to satisfy every thread's needs
  • Deadlock Detection and Recovery — a detection algorithm runs periodically to detect deadlocks, which are then recovered preemptively
  • Ignore the Problem — when deadlock is rare, it's sometimes ignored altogether

This was part 2 of a 3-part series on operating systems. Part 3 dives into memory management — partitioning strategies, the buddy system, paging, virtual memory, and replacement strategies.

← All writing