OS CO2 NOTES

Module 3: Concurrency & Synchronization

1. Concurrency
Definition: The execution of multiple threads seemingly at the same time.
While only one thread is executed by a single CPU at any instant, the CPU
rapidly switches between them (context switching), creating the illusion of
parallel execution.

Relationship with Multithreading: Multithreading is a programming technique

used to achieve concurrency.

Key Point: Concurrency is not parallelism but gives an illusion of it.

2. Process vs. Thread & Inter-process Communication (IPC)

Process: A program in execution. It has its own memory space.

Thread: A "Light Weight Process" (LWP) within a process.

Each thread has its own program counter, stack, and set of registers.

Crucial Difference: Threads within the same process share the same
address space (code, data, files), unlike processes.

Inter-process Communication (IPC): Mechanisms for processes/threads to

exchange data and coordinate.

Shared Memory: Processes communicate by reading/writing to a common

region of memory. Faster but requires careful synchronization.

Message Passing: Processes communicate by explicitly sending and

receiving messages through the OS.

3. Thread API
Thread Libraries: Provide an API for creating and managing threads.

POSIX Pthreads: Common on UNIX/Linux systems.

OS CO2 NOTES 1
 Win32 threads: For Windows systems.

Java threads: Implemented on top of the host OS's threads (Pthreads or

Win32).

Key Functions:

pthread_create() : Creates a new thread.

pthread_join() : Waits for a specific thread to complete.

4. Common Concurrency Problems

Non-Deadlock Bugs:

Atomicity Violation: A sequence of operations that should be executed

indivisibly is interrupted, leading to an incorrect state (e.g., checking a
value, getting interrupted, and then using a now-changed value).

Order Violation: The desired order of execution between two threads is

violated (e.g., using a resource before it has been initialized).

Deadlock Bugs: A set of threads are blocked forever, each waiting for a
resource held by another.

5. Locks
Definition: A synchronization mechanism used to enforce mutual exclusion
within a critical section.

Basic Idea: A lock variable that can be either available (unlocked) or acquired
(locked).

Evaluation Criteria:

Mutual Exclusion: Does the lock prevent multiple threads from entering
the critical section?

Fairness: Does each thread get a fair chance to acquire the lock?
(Prevents starvation).

Performance: What is the time overhead added by using the lock?

Implementing Locks:

OS CO2 NOTES 2
 Test-and-Set (Atomic Exchange): A hardware instruction that tests and
sets a value atomically. Used to build spinlocks (threads wait in a loop).

Compare-and-Swap (CAS): Checks if a value is as expected, and if so,

swaps it.

Fetch-and-Add: Atomically increments a value and returns the old one.

Used to build a ticket lock for fairness.

Using Queues: Sleeping Instead of Spinning: Instead of busy-waiting,

threads are put to sleep and woken up when the lock is free.

6. Locked Data Structures

The goal is to make data structures thread-safe by adding locks, balancing
correctness and performance.

Examples:

Concurrent Counters: A simple counter with a single lock is correct but

not scalable.

Concurrent Linked Lists: A single lock for the entire list.

Concurrent Queues: Often use two locks (one for the head, one for the
tail) to allow enqueue and dequeue operations to proceed concurrently.

Concurrent Hash Tables: Use a lock per hash bucket, allowing concurrent
access to different buckets.

7. Condition Variables
Definition: A synchronization primitive that allows threads to wait for a certain
condition to become true.

Operations:

: Puts the calling thread to sleep, releasing the lock. Upon

wait(cond, mutex)

waking, it re-acquires the lock.

signal(cond) : Wakes up one waiting thread.

broadcast(cond) : Wakes up all waiting threads.

OS CO2 NOTES 3
 Use Case: Used to solve the Producer/Consumer (Bounded Buffer) problem,
where producers wait if the buffer is full and consumers wait if it is empty.

8. Mutex
Definition: A specific kind of binary semaphore that is used to provide a
locking mechanism. It stands for Mutual Exclusion Object.

Function: Used to provide mutual exclusion to a specific portion of the code

so that the process can execute and work with a particular section of the code
at a particular time.

Operation:

wait(mutex) : Locks the mutex before entering a critical section.

signal(mutex) : Unlocks the mutex when exiting the critical section.

Use Case: Ensures that only one thread at a time can enter a critical section.
Tries to solve the Producer-Consumer problem by ensuring mutual exclusion.

9. Semaphores
Definition: A variable or abstract data type (an integer value) used to control
access to a common resource by multiple threads.

Operations:

sem_wait() (or P() ): Decrements the semaphore. If the value becomes

negative, the thread blocks.

(or V() ): Increments the semaphore. If there are waiting threads,

sem_post()

one is unblocked.

Types:

Binary Semaphore: Value is 0 or 1 (similar to a lock/mutex).

Counting Semaphore: Value can be any integer, used for controlling

access to a pool of N identical resources.

Classic Problems Solved:

Dining Philosophers: Philosophers think and eat, but need two forks.
Semaphores can be used to avoid deadlock.

OS CO2 NOTES 4
 Reader-Writer Problem: Multiple readers can access the resource
concurrently, but writers require exclusive access.

10. Monitors
Definition: A high-level synchronization construct that encapsulates shared
data and the procedures that operate on it within a single module. Mutual
exclusion is implicit—only one thread can be active in the monitor at a time.

Condition Variables: Used within monitors for more complex synchronization.

Threads can wait on a condition ( [Link]() ) and be signaled by others ( [Link]() ).

Implementation: Typically built using locks (mutexes) and condition variables.

Use Case: Provides a cleaner, less error-prone way to implement solutions like
the Dining Philosophers problem.

11. Deadlocks
Definition: A situation where a set of processes/threads are blocked because
each is holding a resource and waiting for another resource acquired by some
other process in the set.

Necessary Conditions (All four must hold):

1. Mutual Exclusion: At least one resource must be held in a non-shareable

mode.

2. Hold and Wait: A process must be holding at least one resource and
waiting to acquire additional resources held by other processes.

3. No Preemption: Resources cannot be forcibly removed from a process;

they must be released voluntarily.

4. Circular Wait: There exists a set of waiting processes {P0, P1, ..., Pn} such
that P0 is waiting for a resource held by P1, P1 is waiting for P2, ..., and Pn
is waiting for P0.

Methods for Handling Deadlocks:

Prevention: Design the system so that at least one of the four necessary
conditions can never hold (e.g., by acquiring all resources at once to

OS CO2 NOTES 5
 prevent "Hold and Wait," or by imposing a total ordering on resource
acquisition to prevent "Circular Wait").

Avoidance: The OS is given advance information about the maximum

resources a process may request. It dynamically checks if granting a
request would lead to an unsafe state (a state that could lead to
deadlock).

Banker's Algorithm: A classic deadlock avoidance algorithm.

Detection & Recovery: Allows the system to enter a deadlock state, then
uses an algorithm to detect it and subsequently recovers.

Recovery Methods: Process termination (abort one or more

processes) or resource preemption (rollback a process and take its
resources).

OS CO2 NOTES 6