Process Synchronization and Types

• Process synchronization is the coordination of processes, crucial for correct execution, especially when processes share resources.
• It ensures safe execution of multiple processes, preventing race conditions and is essential for multitasking and multiprogramming.
• Process synchronization avoids race conditions, ensures data consistency, prevents deadlock and starvation, and supports Interprocess Communication (IPC).
• Core part of operating system design, ensuring safe resource sharing and preventing interference between processes.

Types of Process Synchronization

• There are several types based on process interaction.
• These types include independent, cooperative, concurrent, and parallel processes.

Independent Processes

• Independent processes do not share resources and do not affect each other's execution.
• They execute completely independently and don't require synchronization, with no communication or dependency.
• An example includes two processes working on entirely different data without needing to interact.

Independent Synchronization

• Independent Synchronization relies on the OS kernel to enforce synchronization, also known as pre-emptive synchronization.
• It has a higher overhead due to context switches and managing process execution.
• This enhances control and reduces the risk of conflicts, allowing the OS to enforce synchronization.
• Results in simplicity for programmers; application developers don't need to explicitly synchronize processes, relying on OS mechanisms.

Cooperative Processes

• Cooperative processes rely on the OS to manage synchronization, and interact with each other.
• They voluntarily yield control to each other for smooth execution.
• These processes communicate and share resources, cooperating for specific tasks like inter-process communication (IPC).
• In a voluntary cooperation, one process might give control to another.
• This involves processes that share memory or data and need to synchronize their execution.

Cooperative Synchronization

• It is also known as non-preemptive synchronization.
• Results in low overhead because processes cooperate voluntarily, reducing system intervention and enhancing performance.
• This type has increased complexity, requiring meticulous design and programming to enforce synchronization protocols.
• If processes do not follow established synchronization rules, there is a risk of conflicts and data corruption.

Concurrent Processes

• Concurrent processes execute at overlapping times, but not necessarily simultaneously.
• These can be interleaved on a single processor or run in parallel on multiple processors.
• Processes are executed in a way that their progress overlaps, but they do not necessarily run at the same time.
• Process synchronization may be required to avoid conflicts (race conditions).
• A web server handling multiple client requests demonstrates concurrent processes.

Parallel Processes

• Parallel processes run simultaneously on different processors or cores, performing tasks in parallel.
• It allows for true simultaneous execution.
• These processes can operate in parallel, with different parts of a task running simultaneously, requiring multi-core or multi-processor systems.
• It is demonstrated in video rendering applications that divide its workload among multiple cores for faster processing.

Summary of Process Synchronization Types

• Independent: No interaction or synchronization is needed.
• Cooperative: Interact and share resources voluntarily.
• Concurrent: Execute at overlapping times, not necessarily simultaneously.
• Parallel: Execute simultaneously on different processors or cores.

Significance of Processes

• Correctness ensures race conditions are prevented, data integrity is maintained, and exclusive access to shared resources is allowed.
• Resource Management: Enables orderly, efficient resource utilization, preventing conflicts.
• Deadlock Avoidance: Prevents/resolves deadlocks, ensuring continuous progress via prevention strategies and detection algorithms.
• Coordination: Facilitates effective communication, and actions/events signaling among processes.

Process Synchronization Example

• User 1 and User 2 are both trying to access the balance, if process 1 is for withdrawal, and process 2 is for checking the balance, then the user might get the wrong current balance
• Synchronizing these situations prevents data inconsistency.
• There are three processes; Process 1 is trying to write the shared data while Processes 2 and 3 are trying to read the same data
• This can cause huge changes in Process 2, and Process 3 might get the wrong data.

Process Section Breakdown

• Entry Section: Decides the entry of the process.
• Critical Section: Ensures only one process access and modifies shared data/resources.
• Exit Section: Allows processes waiting in the entry section to proceed and removes finished processes from the critical section.
• Remainder Section: Contains other parts of the code not in the Critical or Exit sections.

Entry Section Key Points

• The entry section decides when a process can enter the critical section, ensuring the process can safely begin accessing shared resources.
• This section determines if a process can safely access the critical section and uses mechanisms like locks or semaphores to manage entry.
• If the resource is unavailable, the process waits, and a mutex or semaphore is used to control access to the critical section.

Critical Section Key Points

• It is the part of the program where a process accesses or modifies shared data/resources. Only one process should be allowed to execute at a time.
• It ensures that only one process modifies the shared resource at a time
• The critical section also prevents race conditions, where multiple processes could interfere, along with using synchronization mechanisms for protection.
• Modifying a shared counter value, where two processes should not update it simultaneously, is an example of a critical section.

Exit Section Key Points

• The exit section ensures that the process releases the critical section when it is done, allowing other processes to enter.
• It releases synchronization mechanisms (e.g., locks or semaphores) and signals to other waiting processes.
• Proper synchronization is ensured when leaving the critical section.
• A process releases a mutex or semaphore after completing its task in the critical section.

Remainder Section Key Points

• Remainder section consists of code executed after the critical section.
• The code does not require synchronization, and does not access shared resources.
• Contains operations that do not involve shared resources.
• Can be executed independently without affecting other processes.
• Often involves I/O operations, computations, or waiting for the next task.

Section Summary

• Entry: Decides if a process can enter the critical section.
• Critical: Where shared data is accessed and modified.
• Exit: Releases the critical section for other processes.
• Remainder: Performs independent tasks that do not involve shared resources.

Race Condition

• A race condition occurs when more than one processes tries to access and/or modify the same shared data or resources.
• There are huge chances of the process getting the wrong result or data.
• Every process races to say that it has correct data or resources

Race Condition Example

• Two processes (P0 and P1) are creating child processes using the fork() system call, and there is a race condition on the kernel variable next_available_pid.
• If next_available_pid is not protected by the OS, the same process ID could be assigned to two different processes.

What is the Critical Section Problem?

• The issue is to ensure that only one process can access or modify shared data/resources at any given time.

Rules of Critical Sections

• Mutual Exclusion: Only one process can access the critical section. Prevents simultaneous access or resources modification.
• Progress: If a process wants to enter (and isn't in) a critical section, it should eventually be able to. Ensures fairness by allowing all waiting processes to enter.
• Bounded Waiting: A process waits for a limited time, preventing indefinite blocking while accessing the critical section.

Deadlock Problem

• Deadlock is a critical problem where multiple processes become stuck, waiting for resources that will never be released.
• A deadlock can bring an operating system to a standstill, so addressing this issue requires careful resource allocation and management.

Peterson's Solution

• An algorithm used to synchronize two processes, formulated by Gary Peterson in 1981.
• The solution is a classical software-based method to solve the critical section problem which introduces two shared variables, turn and flag.
• turn indicates which process gets priority and process sets it's flag to request access.
• A simple algorithm for solving the critical section problem
• Prevents race conditions and ensures fair access to shared resources.
• Aims to ensure that multiple processes do access same resources at the same time, along with that no two processes enter their critical sections at the same time as well.

Mutual Exclusion Requirements

• Key requirements include Mutual Exclusion (only one process in critical section), Progress and Bounded Waiting.

Peterson's Implementation

• Has two shared variables: a Boolean array flag[i] and an integer variable turn.
• flag[i] is a boolean array used to show if process i wants to enter the critical section.
• turn is an integer variable to decide which process has the priority to enter.
• Used for two processes

Example of Three Processes in Critical Section

• Assume there are N processes, and a process wanting to enter the critical section, it has to set its flag as true.
• TURN indicates the process number which is currently waiting to enter the Critical Section.

Disadvantages

• It can wastes CPU cycles that could be used to perform other tasks, such as in a busy waiting scenario..
• The solution is limited to 2 processes and cannot be used in modern CPU architectures, and/or is hard to scale to more processes.

Semaphore Solutions

• Semaphores - synchronization tool used to control access to shared resources in OS.
• First introduced by Dutch scientist Dijkstra in 1965.
• Semaphores can be achieved using signaling mechanism to allow access to shared resources.
• Uses access to two methods, Wait(), and Signal()

What is a Semaphore?

• A synchronization primitive used to manage access to shared resources in a concurrent system.
• Used to solve process synchronization and mutual exclusion problems in multi-threaded or multi-process environments.
• Semaphores ensure that processes execute in a controlled and synchronized manner.

Semaphore Operations

• wait() and signal() are the two basic operations used to manipulate semaphores.
• if a Semaphores (value > 0), then the Process can enter the critical Section area.
• Otherwise, if the Semaphore (value == 0), then the process has to wait.
• The process can also reduce the value of semaphore with the exit of the Critical Section.

Types of Semaphores

• Binary Semaphore: The value is only true/false or 0/1. It is commonly used for mutual exclusion.
• Counting Semaphore: Uses Value as Non-negative integers, used for managing a pool of resources when more than 1 instances are available.

Implementation

• Binary semaphores can only have two states: 0 or 1.
• Counting semaphores can have any non-negative integer value, indicating instances.

Advantages of Semaphores in the OS

• Enforce mutual exclusion to prevent race conditions.
• Synchronize process execution.
• Prevents race conditions in critical sections.
• Flexible for different types of synchronization (e.g., mutual exclusion, producer-consumer).

Disadvantages of Semaphores

• Improper handling results in deadlocks where processes are stuck waiting forever.
• If low-priority processes may block high-priority ones resulting to priority inversion.
• Managing multiple semaphores can be difficult, for debugging purposes.