notes-shivam

assignment 2

13 min read

4. What is semaphore? Give the need of busy( signal ) wait implementation of semaphore. What are the problems with it how these problem over come in the given semaphore

1. Definition of Semaphore

A semaphore is a synchronization primitive used in operating systems to manage and control access to shared resources by multiple processes or threads. It is essentially an integer variable that is used to signal the availability of resources. Semaphores are used to prevent race conditions, where multiple processes or threads try to access and modify shared data concurrently.

Semaphores can be of two types:

  • Binary Semaphore (can only take the values 0 or 1, similar to a mutex)
  • Counting Semaphore (can take non-negative integer values, typically used to control access to a pool of resources)

2. Busy-Wait Implementation of Semaphore

In a busy-wait implementation of semaphores, a process continuously checks a condition in a loop (also known as spinning) until the resource it is waiting for becomes available. The basic semaphore operations (P and V, also known as wait and signal) work as follows:

  • wait(S) or P operation:
    • Decrement the value of the semaphore.
    • If the value is negative, the process enters a busy wait and keeps checking until the semaphore is positive again.
  • signal(S) or V operation:
    • Increment the value of the semaphore.
    • If the semaphore was negative, this signals a process waiting for the resource to proceed.

Need for Busy-Waiting

The busy-waiting technique is used to:

  • Ensure immediate access: In situations where processes require immediate access to shared resources as soon as they are free, busy-waiting ensures there is no context switching overhead.
  • Simplified implementation: It can be simpler to implement semaphores using busy-waiting, especially when there is a need for low-level resource management in multi-processor systems.

3. Problems with Busy-Waiting

Busy-waiting, although simple, introduces several problems:

  1. Wasted CPU Cycles: A process continuously consumes CPU cycles while it is waiting, even though it cannot do any useful work until the resource becomes available.
  2. Performance Overhead: Constantly checking the condition wastes computational power, which could otherwise be used by other processes. This can severely degrade system performance, especially in single-core systems.
  3. Unfairness: Processes that are in a busy-wait loop may monopolize CPU resources, potentially leading to fairness issues where some processes are favored over others.
  4. Scalability Issues: In a multiprocessor environment, busy-waiting can lead to a situation called contention, where multiple processors try to access the shared semaphore at the same time, causing performance bottlenecks.

4. Overcoming Problems with Busy-Waiting in Semaphores

The problems associated with busy-waiting are often addressed by using more efficient semaphore implementations, which avoid spinning and unnecessary CPU utilization. These include:

  1. Blocking Semaphores: Instead of busy-waiting, processes that cannot acquire the semaphore are placed in a blocked (or sleep) state. The OS can suspend the process, freeing up the CPU for other tasks. When the semaphore becomes available (via the signal operation), the OS wakes up the blocked process to continue execution.

  2. Spinlocks with Time Limits: In multiprocessor systems, spinlocks can be used with a timeout mechanism, where a process busy-waits for a small amount of time and then switches to blocking if it doesn’t succeed in acquiring the resource.

    • Advantage: Useful for short critical sections where the wait time is very small.
    • Disadvantage: Still consumes CPU resources during the spinlock period.

  3. Priority Inheritance: To address fairness, semaphores can be designed to incorporate priority inheritance, where higher-priority processes are given preference in acquiring resources, thus preventing priority inversion and unfair monopolization of resources.

5. Summary

  • A semaphore is a synchronization mechanism used to manage concurrent access to shared resources.
  • Busy-waiting in semaphores is used to ensure quick access to resources, but it leads to problems like wasted CPU cycles, performance degradation, and fairness issues.
  • These problems can be overcome by using blocking semaphores or spinlocks with time limits that allow processes to sleep rather than waste CPU cycles while waiting.

5. Explain the classical problem of inter process communication and synchronization with the help of example

1. Classical Problem of Inter-Process Communication and Synchronization

  1. Inter-Process Communication (IPC) and synchronization are critical in operating systems when multiple processes run concurrently and need to coordinate their actions.
  2. Without proper synchronization, processes might interfere with each other, leading to issues like data corruption, race conditions, or deadlocks.
  3. Some of the classical problems in IPC and sync :
    • Producer-Consumer (Bounded Buffer) Problem
    • Dining Philosophers Problem
    • Readers-Writers Problem
  4. Each of these problems demonstrates a typical scenario where processes or threads must coordinate their use of shared resources.
  5. Illustrate the challenges of managing shared resources and ensuring proper coordination between processes in a concurrent environment

2. Example of Classical Problems

(i) Producer-Consumer Problem (Bounded Buffer Problem)

The Producer-Consumer problem models two types of processes:

  • The producer generates data and stores it in a buffer.
  • The consumer retrieves data from the buffer and processes it.

The problem arises when both the producer and consumer need access to a bounded buffer (a shared resource with limited size), leading to the need for synchronization to ensure the producer doesn’t overflow the buffer and the consumer doesn’t consume from an empty buffer.

Example:

  • Scenario: Imagine a scenario where a news website has a producer process that gathers news articles (producer) and a consumer process that displays these articles on the website (consumer). The articles are placed in a buffer (the shared resource) that can only hold a certain number of articles at once.

    • Synchronization Need:
      • producer should not add new articles to full buffer
      • Consumer should not try to retrieve articles from empty buffer
      • Both processes must not access the buffer simultaneously.

    Solution using Semaphores:

    • Two semaphores are used:
      • Empty: Indicates the number of empty slots in the buffer.
      • Full: Indicates the number of filled slots in the buffer.
    • Mutex: A binary semaphore is used to ensure mutual exclusion when accessing the buffer.
    semaphore empty = N;  // N is the size of the buffer
semaphore full = 0;
semaphore mutex = 1;
 
// Producer process
wait(empty);        // Wait if no empty slots
wait(mutex);        // Wait for mutual exclusion
// Add item to the buffer
signal(mutex);      // Release mutual exclusion
signal(full);       // Signal a full slot is available
 
// Consumer process
wait(full);         // Wait if no full slots
wait(mutex);        // Wait for mutual exclusion
// Remove item from the buffer
signal(mutex);      // Release mutual exclusion
signal(empty);      // Signal an empty slot is available

Challenges:

  • Race Conditions: If both the producer and consumer access the buffer without proper synchronization, the shared buffer’s state could become inconsistent.
  • Deadlock: If the producer or consumer incorrectly handles the semaphores, they might end up waiting forever, leading to a deadlock.

(ii) Dining Philosophers Problem

  1. multiple processes (philosophers) competing for shared resources (forks) , in a way that can lead to deadlock or starvation.
  2. Scenario:
    1. There are 5 philosophers sitting around a table.
    2. Each philosopher has a plate of food in front of them
    3. they need two forks to eat (left and right).
    4. The table has 5 forks (one between each pair of philosophers).
    5. Philosophers alternate between thinking and eating, and they can only eat if they have both the left and right forks.

Problem: If every philosopher picks up their left fork at the same time, none of them can pick up their right fork, leading to deadlock.

Solution using Semaphores:

  • A semaphore is assigned to each fork to indicate whether it is in use or not.
  • Philosophers can only pick up a fork if it’s available (signaled by the semaphore).
semaphore forks[5] = {1, 1, 1, 1, 1};  // 1 means fork is available
 
void philosopher(int i) {
    while (true) {
        // Think
        wait(forks[i]);                // Pick up left fork
        wait(forks[(i + 1) % 5]);      // Pick up right fork
        // Eat
        signal(forks[i]);               // Put down left fork
        signal(forks[(i + 1) % 5]);     // Put down right fork
    }
}

Challenges:

  • Deadlock: If all philosophers try to pick up the left fork at the same time, none can pick up their right fork, and they all wait indefinitely.
  • Starvation: A philosopher might be unable to get both forks for a long time, while others repeatedly take the forks, leading to starvation.

Solutions to Avoid Deadlock and Starvation:

  • Asymmetric solution: Have philosophers alternate between picking up the left fork first or the right fork first. This reduces the likelihood of deadlock.
  • Resource hierarchy: Impose an order on the forks, so that philosophers always pick them up in a specific order (e.g., lower-numbered forks first).

(iii) Readers-Writers Problem

The Readers-Writers problem models the synchronization problem where:

  • Readers are processes that only read from a shared resource.
  • Writers are processes that modify the shared resource.

The problem is to allow multiple readers to access the resource concurrently but ensure that only one writer can modify the resource at any time, without any readers.

Example:

  • Scenario: A database system where multiple users (readers) can query data simultaneously, but only one user (writer) can update the database at a time.

    Solution:

    • Use two semaphores:
      • ReadCount: Keeps track of how many readers are currently reading.
      • Mutex: Ensures mutual exclusion when updating the ReadCount.
      • Write: Ensures that only one writer can access the shared resource.
    semaphore mutex = 1;
semaphore write = 1;
int readCount = 0;
 
// Reader
wait(mutex);
readCount++;
if (readCount == 1) wait(write);  // First reader locks writers
signal(mutex);
 
// Reading...
 
wait(mutex);
readCount--;
if (readCount == 0) signal(write);  // Last reader unlocks writers
signal(mutex);
 
// Writer
wait(write);  // Wait until no readers or other writers
// Writing...
signal(write);  // Release the resource for other readers or writers

Challenges:

  • Writer Starvation: If there are always readers, writers may never get the chance to update the resource.

Solution:

  • Implement priority for writers by ensuring writers get access before any new readers start reading, thus preventing writer starvation.
  1. These problems demonstrate key issues like race conditions, deadlock, and starvation, and are solved using techniques like semaphores and mutex locks to ensure proper synchronization.

6. What is deadlock? Give the condition for occurrence of deadlock? Discuss techniques for (avoidance & prevention)

1. Definition of Deadlock

A deadlock occurs in a system when a set of processes is permanently blocked because each process is holding a resource and waiting for another resource that is being held by another process in the same set. None of the processes can proceed because the resources they need are locked in a circular chain of dependencies.

Example:

Consider two processes, P1 and P2, and two resources, R1 and R2:

  • P1 holds R1 and is waiting for R2.
  • P2 holds R2 and is waiting for R1. Since neither process can release the resource it holds until it gets the resource it’s waiting for, both processes are stuck in a deadlock.

2. Conditions for Deadlock Occurrence (Coffman Conditions)

For deadlock to occur, four conditions (also known as Coffman conditions) must be met simultaneously:

  1. Mutual Exclusion:
    • At least one resource must be held in a non-shareable mode. Only one process can use the resource at any given time.
  2. Hold and Wait:
    • A process is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.
  3. No Preemption:
    • Resources cannot be forcibly taken away from a process holding them. A process must voluntarily release the resource after completing its task.
  4. Circular Wait:
    • A circular chain of processes exists, where each process is waiting for a resource that the next process in the chain holds. For example, P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, and so on, until the last process is waiting for a resource held by P1.

If all four of these conditions are true, a deadlock can occur.

3. Techniques for Deadlock Avoidance and Prevention

A. Deadlock Prevention

Deadlock prevention strategies aim to ensure that at least one of the four necessary conditions for deadlock cannot hold, thus preventing deadlock from occurring.

Techniques for Prevention:

  1. Mutual Exclusion Elimination:

    • Try to make resources shareable. If a resource can be shared among multiple processes, the mutual exclusion condition does not hold. However, for certain resources (e.g., printers), mutual exclusion is unavoidable.

  2. Hold and Wait Elimination:

    • Solution: Require processes to request all resources at once, at the beginning of execution, instead of holding some resources and waiting for others.
    • Drawback: This leads to low resource utilization, as a process might hold onto resources it doesn’t immediately need, preventing others from using them.

  3. No Preemption Elimination:

    • Solution: Allow resources to be preempted. If a process is holding a resource and requests another resource that is unavailable, it must release all its currently held resources and request them again along with the new resource.
    • Drawback: This can lead to additional overhead and process starvation.

  4. Circular Wait Elimination:

    • Solution: Impose an ordering on the resources and require that each process requests resources in a pre-defined order (ascending or descending order of resource IDs).
    • Drawback: Not always feasible in dynamic resource allocation environments where processes might need resources in varying orders.

B. Deadlock Avoidance

Deadlock avoidance ensures that the system never enters a deadlocked state by carefully controlling resource allocation. The most common deadlock avoidance algorithm is Banker’s Algorithm, which checks for safe states before allocating resources.

Safe and Unsafe States:

  • A safe state means there is at least one sequence in which all processes can complete without leading to deadlock.
  • An unsafe state does not guarantee that deadlock will occur, but there is a possibility that it could happen.

Banker’s Algorithm:

  • Before allocating resources, the system checks if granting the request will leave the system in a safe state.
  • The algorithm uses three matrices:
    • Max: Maximum resources a process may need.
    • Allocation: Currently allocated resources.
    • Need: Remaining resources the process needs (calculated as Max - Allocation).

Steps in Banker’s Algorithm:

  1. When a process requests resources, the system checks if:
    • The request is less than or equal to the need of the process.
    • The requested resources are available.
  2. If the resources are available, the system provisionally allocates them to the process.
  3. After provisional allocation, the system checks if there is a safe sequence where all processes can finish.
  4. If such a sequence exists, the allocation is confirmed; otherwise, the resources are denied until the system reaches a safer state.

Drawbacks:

  • The algorithm needs advance knowledge of the maximum resources required by each process.
  • The overhead of constantly checking for safe states can be high.

4. Summary

  • Deadlock occurs when processes are stuck in a circular chain of resource dependencies.
  • The four conditions for deadlock are: mutual exclusion, hold and wait, no preemption, and circular wait.
  • Prevention techniques aim to violate one or more of the necessary conditions for deadlock, while avoidance techniques (like the Banker’s algorithm) ensure that the system never enters an unsafe state where deadlock might occur.

Graph View