Chapter 4 Synchronization
1 mark
d) List the solutions to critical section problem
Answer: Critical section is a code segment that can be accessed by only one process at a time. It contains shared variables which needs to be synchronized to maintain consistency of data variables.
The problem is defined as , A situation in a concurrent system where multiple processes access and manipulate shared resources, and there is a possibility of data inconsistency.
We can solve the problem in following ways:
1) Mutual Exclusion: Ensuring only one process can execute in the critical section at a time.
2) Progress: If no process is in the critical section and some processes wish to enter, only those not in the remainder section can enter.
3) Bounded Waiting: There exists a limit on the number of times other processes are allowed to enter the critical section after a process has made a request.
Solutions are:
Peterson's Solution :
Description : A software-based approach using two variables and flags to achieve mutual exclusion and progress.
Advantages : Simple, but limited to two processes.
Bakery Algorithm (j):
Description : Assigns a unique number to each process, and the process with the lowest number enters the critical section first.
Advantages : Suitable for a larger number of processes.
Synchronization Problems Solution :
Approach: Utilize synchronization constructs like semaphores to coordinate process execution.
Advantages: Provides a more general and flexible solution for handling critical sections.
i) What are the two types of semaphores?
Answer:
Binary Semaphore (a): Has two states, 0 or 1, often used for mutual exclusion.
Counting Semaphore (b): Can have multiple values, used for general counting and synchronization purposes.
- c) Define the term semaphore
Answer: A semaphore is a variable used to control access to a common resource by multiple processes and avoid critical section problem.
(h) What are the types of semaphores ?
(f) “Counting semaphore can be implemented by using binary semaphore.” True/False Justify.
Answer: True (a): Counting semaphore can be implemented using binary semaphore.
Justification (b): Binary semaphores can be used to implement a counting semaphore by allowing the value of the binary semaphore to represent the count.
e) What is synchronisation?
Answer: Definition: Synchronization is the coordination or ordering of multiple processes to ensure the correct and orderly execution of a program.
4 mark
(c) What is critical section problem ? Explain two general approaches to handle critical section in operating system.
Answer:
Q. (c) What is critical section problem ? how it is solved.
(i) What is critical section problem ? Give Peterson’s solution to solve critical section problem.
Answer:
Critical Section Problem:
Definition : In concurrent programming, the critical section problem involves multiple processes accessing shared resources, and the goal is to ensure mutual exclusion to avoid data inconsistencies.
Peterson's Solution:
Description : Peterson's Solution is a software-based approach designed for two processes to achieve mutual exclusion within their critical sections.
Components :
Flags: Two boolean flags, one for each process, indicating their interest in entering the critical section.
Turn: A variable indicating whose turn it is to enter the critical section.
Algorithm :
1) Entry Section:
Set the flag of the current process to true, indicating interest.
Set the turn to the other process.
Wait until the other process is not interested or has the turn.
2) Critical Section:
Perform operations within the critical section.
3) Exit Section:
Set the flag of the current process to false, indicating no interest.
Advantages :
1) Simple and easy to implement.
2) Guarantees mutual exclusion.
Limitations :
1) Limited to two processes.
2) May not be as efficient in scenarios with a large number of processes.
(c) Explain Bounded-Buffer problem
Answer: Bounded-Buffer Problem:
Definition : A synchronization challenge involving multiple producer and consumer processes sharing a fixed-size buffer.
Objective : To ensure that producers do not overflow the buffer and consumers do not read from an empty buffer.
Solution : Semaphore-based synchronization is commonly used to address the Bounded-Buffer Problem.
(B) (i) Discuss the bounded buffer problem with its solution. [4]
b) Which three requirements must be satisfied while designing a solutions to the critical section problem? Explain in detail.
Answer:
Mutual Exclusion :
Definition : Only one process can be in the critical section at a time.
Importance : Ensures that conflicting operations on shared resources do not overlap, preventing data inconsistencies.
Implementation : Techniques like locks, semaphores, or atomic operations can be employed to enforce mutual exclusion.
Progress :
Definition : If no process is in the critical section and some processes wish to enter, only those not in the remainder section can enter.
Importance : Guarantees that processes do not remain indefinitely excluded from the critical section, avoiding potential deadlock scenarios.
Implementation : Systems may use various algorithms or constructs to manage progress, such as turn-taking or priority-based approaches.
Bounded Waiting :
Definition : There exists a limit on the number of times other processes are allowed to enter the critical section after a process has made a request.
Importance : Prevents a process from being overtaken indefinitely by others, ensuring fair access to the critical section.
Implementation : Utilizes techniques like counting semaphores, ensuring fairness in granting access while avoiding resource starvation for any particular process.
c) Explain producer, consumer problem
Answer:
Definition:
Problem Scenario: Involves two types of processes – producers and consumers – sharing a common, fixed-size buffer.
Producers: Generate items and place them in the buffer.
Consumers : Remove items from the buffer for processing or consumption.
Objective:
Producer's Goal: Fill the buffer with items.
Consumer's Goal: Consume items from the buffer.
Synchronization Challenges:
Buffer Overflow: Producers must not add items to a full buffer.
Buffer Underflow: Consumers must not remove items from an empty buffer.
Solution:
Semaphore Implementation: Utilizes semaphores to manage access to the buffer.
Empty and Full Semaphores: Track the number of empty and full slots in the buffer.
Mutex (Mutual Exclusion) Semaphore: Ensures mutual exclusion for buffer access.
Steps:
1) Producers acquire the empty slot semaphore before adding items to the buffer.
2) Consumers acquire the full slot semaphore before removing items from the buffer.
3) Mutual exclusion is enforced using the mutex semaphore.
4) Semaphores are adjusted to reflect changes in buffer occupancy.
b) Explain reader-writer problem in brief
Answer:
Reader-Writer Problem:
Definition:
Problem Scenario: Involves processes that either read or write to a shared resource, such as a file or database.
Readers : Access the resource for reading.
Writers : Access the resource for writing.
Objectives:
Readers' Goal: Concurrently read the resource without interfering with each other.
Writers' Goal: Access the resource exclusively for writing.
Synchronization Challenges:
Read-Write Conflict: Writers must have exclusive access, while multiple readers can access concurrently.
Write-Write Conflict: Only one writer should write at a time.
Solution:
Semaphore Implementation: Typically uses semaphores to manage access to the shared resource.
Mutex (Mutual Exclusion) Semaphore: Ensures mutual exclusion for resource access.
Reader and Writer Count Semaphores: Track the number of readers and writers accessing the resource.
Steps:
1) Readers acquire the mutex semaphore before accessing the resource for reading.
2) Writers acquire the mutex semaphore exclusively for writing.
3) Reader count is updated, allowing multiple readers to read concurrently.
4) Writer count is updated, ensuring exclusive access for writers.
b) Explain bounded buffer problem in detail.
Answer:
Bounded Buffer Problem:
Definition:
Problem Scenario: Multiple producer and consumer processes share a fixed-size buffer.
Objective : Ensure that producers do not overflow the buffer, and consumers do not read from an empty buffer.
Synchronization Challenges:
Buffer Overflow: Producers must not add items to a full buffer.
Buffer Underflow: Consumers must not remove items from an empty buffer.
Solution:
Semaphore Implementation: Utilizes semaphores to manage access to the buffer.
Empty and Full Semaphores: Track the number of empty and full slots in the buffer.
Mutex (Mutual Exclusion) Semaphore: Ensures mutual exclusion for buffer access.
Steps:
1) Producers acquire the empty slot semaphore before adding items to the buffer.
2) Consumers acquire the full slot semaphore before removing items from the buffer.
3) Mutual exclusion is enforced using the mutex semaphore.
4) Semaphores are adjusted to reflect changes in buffer occupancy.
Detailed Implementation:
1) Producers increment the empty semaphore when adding items and decrement the full semaphore.
2) Consumers increment the full semaphore when removing items and decrement the empty semaphore.
3) Mutual exclusion is ensured using the mutex semaphore during buffer access.