Concurrency Notes

Introduction

• Multiprogramming: Management of multiple processes within a single processor system.

• Multiprocessing: Management of multiple processes within a multiprocessor system.

• Distributed Processing: Management of multiple processes executing on multiple distributed computer systems.

Concurrency

• Definition:

  • Communication among processes.

  • Sharing and competing for resources.

  • Synchronization of activities of multiple processes.

  • Allocation of processor time to processes.

When Concurrency Arises

• Multiple applications.

• Structured applications.

• Operating system structure.

Race Conditions

• A race condition occurs when two or more processes/threads access and manipulate the same data concurrently.

• The outcome of the execution depends on the particular order in which the access takes place.

• Synchronization is needed to prevent race conditions.

Principles of Concurrency

• Problems encountered:

  • Sharing of global resources is fraught with peril.

  • Difficulty in managing the allocation of resources optimally.

  • Difficulty in locating a programming error because results are typically not deterministic and reproducible.

Simple Example

• An echo program is loaded into global memory and shared by applications.

• The problem can be solved by controlled access to the shared resource.

OS Concerns

• Design and management issues raised by concurrency:

  • The OS should keep track of active processes.

  • The OS should allocate and deallocate resources to active processes, such as:

    • Processor time.

    • Memory.

    • Files.

    • I/O devices.

  • The OS should protect against interference by other processes.

  • The result of a process should be independent of the speed of execution relative to other concurrent processes (process interaction).

Degree of Awareness

Competition Among Processes for Resources

• 3 Control problems:

  • Mutual exclusion (e.g., printer).

  • Mutual exclusion leads to two more additional problems:

    • Deadlock.

    • Starvation.

  • Mutual exclusion can be achieved by locking a resource prior to its use.

The Critical-Section Problem

• Consider a system consisting of $n$ processes ${ P<em>0, P</em>1, …, P_n }$.

• Each process has a segment of code called a critical section in which the process may be changing common variables, updating a table, writing a file, and so on.

• When one process is executing in its critical section, no other process is allowed to execute in its critical section.

• The critical-section problem is to design a protocol that the processes can use to cooperate.

Sections within a Process

• Each process must request permission to enter its critical section.

  • The section of code implementing this request is the entry section.

  • The critical section may be followed by an exit section.

  • The remaining code is the remainder section.

• Structure of a typical process:

  do {
      entry section
      critical section
      exit section
      remainder section
  } while (TRUE);
  

Requirements for Critical-Section Problem Solutions

• A solution to the critical-section problem must satisfy the following three requirements:

  1. Mutual Exclusion: If process $P_i$ is executing in its critical section, then no other processes can be executing in their critical sections.

  2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

  3. Bounded Waiting: There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Critical Section and Mutual Exclusion

• A critical section is a section of code in which a process accesses shared resources.

• The execution of critical sections must be mutually exclusive (e.g., at most one process can be in its critical section at any time).

• The critical-section problem is to design a protocol that processes can use to cooperate.

• Example:
  c++ int count; // shared critical sections count++; --count; cout << count;

The Critical Section Protocol

• A critical section protocol consists of two parts: an entry section and an exit section.

• Between them is the critical section that must run in a mutually exclusive way.

  do {
      entry section
      critical section
      exit section
  } while (1);
  

Solutions to the Critical Section Problem

• Any solution to the critical section problem must satisfy the following three conditions:

  • Mutual Exclusion

  • Progress

  • Bounded Waiting

• Moreover, the solution cannot depend on CPU's relative speed and scheduling policy.

Cooperation Among Processes by Sharing

• Examples: shared variables/files/database.

• Data items may be accessed in reading and writing mode, and only the writing mode must be mutually exclusive.

• Requirement: data coherence.

Cooperation Among Processes by Communication

• Communication provides a way to synchronize or coordinate the various activities.

• This is done by messaging.

• Mutual exclusion is not a control requirement for this sort of cooperation.

• Has deadlock and starvation problems.

Requirements of Mutual Exclusion (ME)

• ME should be enforced.

• A process that halts in its noncritical section should not interfere with other processes.

• No deadlock and starvation.

• When no process is in the CS, a process requiring CS should be granted permission.

• A process remains in CS only for a finite time.

Ways to Arrive at Mutual Exclusion

• Software approaches:

  • Leave the responsibility to the processes that wish to execute concurrently.

  • Disadvantage: high processing overhead and bugs.

• Hardware approaches:

  • Special purpose machine instructions.

  • Advantage: reduces overhead.

• Some level of support within the OS or programming language:

  • Semaphores

  • Monitors

Mutual Exclusion: Software Approaches

• Can be implemented for concurrent processes that execute on a single processor or a multiprocessor machine with shared main memory.

• Example: Peterson’s Algorithm

Livelock

• The process keeps setting and resetting the flags alternatively, and neither process can enter its critical section.

• Alteration in the relative speed of the two processes will break this cycle and allow one to enter the critical section.

• This is called livelock.

Mutual Exclusion - Hardware Approach

• Interrupt Disabling

• Special machine instructions

  • Compare and swap

  • Exchange

Interrupt Disabling

• In a uniprocessor system, concurrent processes can have only interleaved execution.

• A process runs until it is interrupted.

• To guarantee ME, it's enough to prevent a process from being interrupted.

• Disadvantages:

  • Degree of interleaving is limited.

  • Does not work in a multiprocessor architecture.

Special Machine Instructions

• Processor designers have proposed several machine instructions that carry out two actions automatically (Read-Write/Read-Test) through a single instruction fetch cycle.

• Two such instructions:

  • Compare and swap instruction

  • Exchange instruction

Properties of Machine-Instruction Approach

• It is applicable to any number of processes on either a single processor or multiple processors sharing main memory.

• It is simple and therefore easy to verify.

• It can be used to support multiple critical sections; each critical section can be defined by its own variable.

Disadvantages of Machine-Instruction Approach

• Busy waiting is employed.

• Starvation is possible.

• Deadlock is possible.

Introduction

• Multiprogramming: Management of multiple processes within a single-processor system, aiming to maximize CPU utilization by overlapping CPU and I/O operations. This approach allows the OS to switch between processes when one is waiting for an I/O operation, thus keeping the CPU busy.

• Multiprocessing: Management of multiple processes within a multiprocessor system, leveraging multiple CPUs to execute processes in parallel. This can significantly reduce execution time for CPU-bound tasks and improve overall system throughput.

• Distributed Processing: Management of multiple processes executing on multiple distributed computer systems, enabling collaboration and resource sharing across a network. This is particularly useful for large-scale applications that require high availability and scalability.

Concurrency

• Definition:

  • Communication among processes, allowing them to exchange data and coordinate their activities.

  • Sharing and competing for resources, such as CPU time, memory, and I/O devices.

  • Synchronization of activities of multiple processes to ensure correct execution and data consistency.

  • Allocation of processor time to processes, determining which process gets to run and for how long.

When Concurrency Arises

• Multiple applications running simultaneously, each competing for system resources.

• Structured applications designed with modular components that can execute concurrently, improving performance and responsiveness.

• Operating system structure, where various OS services and functions run as concurrent processes, enabling efficient system management.

Race Conditions

• A race condition occurs when two or more processes/threads access and manipulate the same data concurrently, and the outcome depends on the specific order of execution.

• The final result of the shared data depends on the unpredictable order in which multiple processes access it, leading to potential data corruption and inconsistent program behavior.

• Synchronization mechanisms, such as locks and semaphores, are essential to prevent race conditions and ensure data integrity.

Principles of Concurrency

• Problems encountered:

  • Sharing of global resources can lead to conflicts and data corruption if not properly managed with synchronization techniques.

  • Difficulty in managing the allocation of resources optimally, as the needs of concurrent processes may vary dynamically.

  • Difficulty in locating a programming error because results are typically not deterministic and reproducible, making debugging challenging.

Simple Example

• An echo program is loaded into global memory and shared by applications, allowing multiple programs to use it simultaneously.

• The problem can be solved by controlled access to the shared resource using mutual exclusion mechanisms to prevent conflicts.

OS Concerns

• Design and management issues raised by concurrency:

  • The OS should keep track of active processes to manage their execution and resource allocation.

  • The OS should allocate and deallocate resources to active processes, such as:

    • Processor time, determining how long each process can run before being switched out.

    • Memory, allocating and managing memory space for each process.

    • Files, controlling access to files and ensuring data consistency.

    • I/O devices, managing access to input/output devices and handling I/O requests.

  • The OS should protect against interference by other processes to prevent unauthorized access and ensure system stability.

  • The result of a process should be independent of the speed of execution relative to other concurrent processes (process interaction), ensuring consistent and predictable behavior.

Degree of Awareness

Competition Among Processes for Resources

• 3 Control problems:

  • Mutual exclusion (e.g., printer), ensuring that only one process can access a shared resource at a time.

  • Mutual exclusion leads to two more additional problems:

    • Deadlock, where two or more processes are blocked indefinitely, waiting for each other to release resources.

    • Starvation, where a process is perpetually denied access to a resource it needs to complete its task.

  • Mutual exclusion can be achieved by locking a resource prior to its use, preventing other processes from accessing it until the lock is released.

The Critical-Section Problem

• Consider a system consisting of $n$ processes ${ P<em>0, P</em>1, …, P_n }$.

• Each process has a segment of code called a critical section in which the process may be changing common variables, updating a table, writing a file, and so on.

• When one process is executing in its critical section, no other process is allowed to execute in its critical section, preventing data corruption and ensuring consistency.

• The critical-section problem is to design a protocol that the processes can use to cooperate, allowing them to access shared resources safely and efficiently.

Sections within a Process

• Each process must request permission to enter its critical section using an appropriate synchronization mechanism.

  • The section of code implementing this request is the entry section, which may involve acquiring a lock or semaphore.

  • The critical section may be followed by an exit section, where the process releases the lock or semaphore, allowing other processes to enter their critical sections.

  • The remaining code is the remainder section, which does not require exclusive access to shared resources.

• Structure of a typical process:

do {
 entry section
 critical section
 exit section
 remainder section
} while (TRUE);

Requirements for Critical-Section Problem Solutions

• A solution to the critical-section problem must satisfy the following three requirements:

  1. Mutual Exclusion: If process $P_i$ is executing in its critical section, then no other processes can be executing in their critical sections, ensuring data consistency and preventing race conditions.

  2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely, preventing unnecessary delays and ensuring fairness.

  3. Bounded Waiting: There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted, preventing starvation and ensuring that all processes eventually get a chance to execute their critical sections.

Critical Section and Mutual Exclusion

• A critical section is a section of code in which a process accesses shared resources, such as variables, files, or databases.

• The execution of critical sections must be mutually exclusive (e.g., at most one process can be in its critical section at any time), preventing conflicts and ensuring data integrity.

• The critical-section problem is to design a protocol that processes can use to cooperate, allowing them to access shared resources safely and efficiently.

• Example:

c++ int count; // shared critical sections count++; --count; cout << count;

The Critical Section Protocol

• A critical section protocol consists of two parts: an entry section and an exit section, which manage access to the critical section.

• Between them is the critical section that must run in a mutually exclusive way, ensuring that only one process can execute it at a time.

do {
 entry section
 critical section
 exit section
} while (1);

Solutions to the Critical Section Problem

• Any solution to the critical section problem must satisfy the following three conditions:

  • Mutual Exclusion, ensuring that only one process can execute the critical section at a time.

  • Progress, ensuring that if no process is in the critical section and some processes want to enter, one of them will be allowed to do so.

  • Bounded Waiting, ensuring that each process has a finite wait time to enter the critical section.

• Moreover, the solution cannot depend on CPU's relative speed and scheduling policy, ensuring that it works correctly regardless of the system's configuration and workload.

Cooperation Among Processes by Sharing

• Examples: shared variables/files/database, where multiple processes can access and modify the same data.

• Data items may be accessed in reading and writing mode, and only the writing mode must be mutually exclusive to prevent data corruption.

• Requirement: data coherence, ensuring that all processes see a consistent view of the shared data.

Cooperation Among Processes by Communication

• Communication provides a way to synchronize or coordinate the various activities of multiple processes.

• This is done by messaging, where processes exchange messages to signal events and share data.

• Mutual exclusion is not a control requirement for this sort of cooperation, as messages can be used to coordinate access to shared resources.

• Has deadlock and starvation problems that must be addressed with appropriate synchronization mechanisms.

Requirements of Mutual Exclusion (ME)

• ME should be enforced, ensuring that only one process can access the critical section at a time.

• A process that halts in its noncritical section should not interfere with other processes, preventing system instability.

• No deadlock and starvation, ensuring that all processes eventually get a chance to access the critical section.

• When no process is in the CS, a process requiring CS should be granted permission, maximizing resource utilization.

• A process remains in CS only for a finite time, preventing any single process from monopolizing the shared resource.

Ways to Arrive at Mutual Exclusion

• Software approaches:

  • Leave the responsibility to the processes that wish to execute concurrently, requiring them to implement their own synchronization mechanisms.

  • Disadvantage: high processing overhead and bugs, as ensuring correct synchronization can be complex and error-prone.

• Hardware approaches:

  • Special purpose machine instructions that provide atomic operations for synchronization.

  • Advantage: reduces overhead, as hardware-level synchronization is typically more efficient than software-based solutions.

• Some level of support within the OS or programming language:

  • Semaphores, which are signaling mechanisms that can be used to control access to shared resources.

  • Monitors, which are high-level synchronization constructs that provide mutual exclusion and condition synchronization.

Mutual Exclusion: Software Approaches

• Can be implemented for concurrent processes that execute on a single processor or a multiprocessor machine with shared main memory.

• Example: Peterson’s Algorithm, a classic software-based solution for achieving mutual exclusion between two processes.

Livelock

• The process keeps setting and resetting the flags alternatively, and neither process can enter its critical section, resulting in wasted CPU cycles.

• Alteration in the relative speed of the two processes will break this cycle and allow one to enter the critical section, but this is not a reliable solution.

• This is called livelock, a situation where processes are actively trying to resolve a conflict but are unable to make progress.

Mutual Exclusion - Hardware Approach

• Interrupt Disabling, where a process disables interrupts to prevent context switching during critical sections.

• Special machine instructions:

  • Compare and swap, an atomic instruction that compares the value of a memory location with a given value and, only if they are equal, modifies the memory location to a new value.

  • Exchange, an atomic instruction that exchanges the contents of two memory locations.

Interrupt Disabling

• In a uniprocessor system, concurrent processes can have only interleaved execution, as there is only one CPU to execute them.

• A process runs until it is interrupted by an event, such as an I/O request or a timer interrupt.

• To guarantee ME, it's enough to prevent a process from being interrupted while it is in its critical section.

• Disadvantages:

  • Degree of interleaving is limited, as disabling interrupts can reduce system responsiveness.

  • Does not work in a multiprocessor architecture, as disabling interrupts on one processor does not prevent other processors from accessing shared resources.

Special Machine Instructions

• Processor designers have proposed several machine instructions that carry out two actions automatically (Read-Write/Read-Test) through a single instruction fetch cycle, providing atomic operations for synchronization.

• Two such instructions:

  • Compare and swap instruction, which atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a new given value.

  • Exchange instruction, which atomically swaps the contents of two memory locations.

Properties of Machine-Instruction Approach

• It is applicable to any number of processes on either a single processor or multiple processors sharing main memory, making it a versatile solution for mutual exclusion.

• It is simple and therefore easy to verify, reducing the risk of errors and improving system reliability.

• It can be used to support multiple critical sections; each critical section can be defined by its own variable, allowing for fine-grained control over synchronization.

Disadvantages of Machine-Instruction Approach

• Busy waiting is employed, where processes repeatedly check a condition until it becomes true, wasting CPU cycles.

• Starvation is possible, where a process is repeatedly denied access to the critical section, even though it is eligible to enter