Synchronization and Concurrency - TarisMajor/5143-OpSystems GitHub Wiki

1_9Gmxqu0Z82bO4L8tBqn7Mw

Synchronization and Concurrency

Synchronization and concurrency are key concepts in multi-threaded environments. Concurrency refers to the ability of an operating system to handle multiple tasks at the same time. Synchronization ensures that multiple threads or processes can safely access shared resources without causing data corruption or inconsistencies.

Critical Section

A critical section is a part of a program that accesses shared resources (like variables or memory) that must not be concurrently accessed by more than one thread or process. Proper synchronization is required to avoid race conditions.

Mutual Exclusion

Mutual exclusion is a property of a system where only one process or thread can access a critical section at any given time. This ensures that shared resources are not simultaneously accessed, which can cause inconsistencies.

Race Conditions

A race condition occurs when the outcome of a program depends on the non-deterministic order in which multiple threads or processes are executed. This can lead to unexpected behavior and errors when shared resources are accessed concurrently without proper synchronization.

Semaphores

Semaphores are synchronization primitives used to control access to shared resources by multiple threads or processes. A semaphore can be binary (with values 0 or 1) or counting (which can take on a range of values). It is used to signal or block threads based on conditions.

Mutexes

A mutex (short for mutual exclusion) is a type of lock used to enforce mutual exclusion by allowing only one thread or process to access a shared resource at any given time. Unlike semaphores, mutexes are typically used for locking critical sections.

Monitors

Monitors are high-level synchronization primitives that provide a mechanism to manage concurrent access to shared resources. They allow a thread to lock and access a resource, and they also provide condition variables to wait or signal certain conditions during execution.

Deadlock

Deadlock occurs when a set of processes are unable to proceed because each process is waiting for another process to release a resource. This leads to a situation where none of the processes can make progress.

Starvation

Starvation is a condition in which a process is perpetually denied access to resources, preventing it from executing. This typically occurs when high-priority processes continuously preempt the lower-priority ones.

Busy Waiting

Busy waiting occurs when a process continuously checks a condition in a loop without releasing the CPU, often causing unnecessary consumption of processing resources. It typically happens when a thread is waiting for a specific event or resource to become available.

Condition Variables

Condition variables are synchronization primitives that allow threads to block until a particular condition is met. They are typically used in conjunction with mutexes to coordinate the execution of threads based on shared conditions.

Spinlocks

Spinlocks are a type of lock where a thread repeatedly checks if the lock is available and "spins" in a busy-wait loop until it can acquire the lock. They are useful when the lock is expected to be held for a short period.

Atomic Operations

Atomic operations are operations that are completed in a single step, without being interrupted or interfered with by other operations. They are crucial for avoiding race conditions and ensuring data consistency in concurrent systems.

Synchronization Problems

Synchronization problems refer to common challenges in concurrent programming where multiple processes or threads need to safely interact with shared resources. Some well-known problems include:

Producer-Consumer Problem

In the Producer-Consumer Problem, a producer thread generates data and stores it in a buffer, while a consumer thread retrieves and processes the data. The problem lies in ensuring that the producer and consumer synchronize properly to avoid issues like buffer overflow or underflow.

Readers-Writers Problem

The Readers-Writers Problem involves scenarios where multiple processes need access to a shared resource: some processes (readers) only need to read the resource, while others (writers) need to write to it. The challenge is to allow multiple readers to access the resource concurrently while ensuring that writers have exclusive access when necessary.

Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem where philosophers sit around a table, each needing two forks to eat. The challenge is to ensure that they don’t starve (due to deadlock) and that they all have fair access to the forks.

Sleeping Barber Problem

The Sleeping Barber Problem involves a barber who sleeps when there are no customers and serves one customer at a time. The challenge is to manage customer arrival and barber service while ensuring the barber doesn’t sleep too long when there are customers waiting.

Sources:

  1. Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne

  2. Modern Operating Systems by Andrew S. Tanenbaum and Herbert Bos

  3. Operating Systems: Design and Implementation by Andrew S. Tanenbaum

  4. The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit

  5. ChatGPT