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
- Disable Interrupts — prevents the CPU from being interrupted, and also prevents asynchronicity. In practice, though, it's a very bad idea to disable interrupts.
- 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.
- 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.