Operating System 2024-25 BCA30110 Module IV (OS) PDF

Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Table of Contents Module No. Module Name Content Definition and Importance of concurrency...

Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Table of Contents Module No. Module Name Content Definition and Importance of concurrency Challenges towards process synchronization Critical Section Problem - Principles of Concurrency Solution Criterions - Mutual Exclusion, Progress, Bounded Waiting. Software-Based Solutions (Peterson's Solution). Mutex (Mutual Exclusion Locks), their Synchronization characteristics and uses. Mechanisms Semaphores, their types and (Solutions for the Critical implementation. Section Problem) Condition Variables Classical Synchronization Producer-Consumer Problem and Solution Process Problems Readers-Writers Problem and Solution IV Synchronization & Deadlock concept and Conditions Mutual Exclusion necessary for deadlock Strategies related to dealing with deadlocks - Deadlock Prevention Strategies Avoidance Techniques ○ RAG ○ Banker's Algorithm Detection and Recovery Shared Memory Model Process Communication Message Passing Model Definition, role and benefits of Virtual Machines in OS. Virtual Machines and Virtualization Techniques - Virtualization Full Virtualization Para-Virtualization Hardware-Assisted Virtualization Prepared By - The Department of Computational Sciences Page 1  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Principles of Concurrency Definition and Importance of Concurrency Concurrency in operating systems refers to the capability of an OS to handle more than one task or process at the same time, thereby enhancing efficiency and responsiveness. It may be supported by multi-threading or multi-processing whereby more than one process or threads are executed simultaneously or in an interleaved fashion. It allows several tasks to be in progress at the same time, either by running on separate processors or through context switching on a single processor. Concurrency is essential in modern OS design to handle multitasking, increase system responsiveness, and optimize performance for users and applications. There are two types of processes: Independent Processes - Its state is not shared with any other process. ○ The result of execution depends only on the input state. ○ The result of the execution will always be the same for the same input. ○ The termination of the independent process will not terminate any other. Cooperating Processes - Its state is shared along other processes. ○ The result of the execution depends on the relative execution sequence and cannot be predicted in advance(Non-deterministic). ○ The result of the execution will not always be the same for the same input. ○ The termination of the cooperating process may affect other processes. In systems where multiple processes or threads run simultaneously, they often need to share resources like memory, files, or hardware devices. This simultaneous execution, called concurrency, introduces challenges in ensuring the processes do not interfere with each other or produce incorrect results. Process synchronization is a key concept within concurrency control that addresses this issue. The Need for Synchronization Process synchronization is an essential part of managing concurrency in operating systems and software systems. It focuses on coordinating the execution of processes or threads that interact with shared resources to ensure correctness, consistency, and efficiency. Without proper synchronization, issues such as race conditions, inconsistent data, and unpredictable system behavior can occur. When multiple processes or threads access shared resources, such as memory, files, or devices, there is a possibility of conflict. For example, two threads updating a shared counter without proper coordination might result in incorrect values due to simultaneous access. Synchronization ensures that processes execute in an organized manner, especially when they share critical resources. Prepared By - The Department of Computational Sciences Page 2  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Challenges towards Process Synchronization Process synchronization ensures safe access to shared resources, but presents several challenges. The Critical Section Problem arises when multiple processes access shared resources simultaneously, risking data inconsistency. Race conditions occur when processes execute in unsynchronized order, leading to unpredictable outcomes. In order to combat the various challenges faced during process synchronization, several techniques are employed. Mutexes and semaphores are commonly used to control access to critical sections, preventing race conditions. While synchronization mechanisms like semaphores and mutexes introduce some overhead, they are essential tools for ensuring the smooth operation of concurrent processes. Race Conditions When more than one process is executing the same code or accessing the same memory or any shared variable in that condition there is a possibility that the output or the value of the shared variable is wrong so for all the processes doing the race to say that my output is correct this condition is known as a race condition. Consider the following pseudocode as an example. There are two threads which are executing and they are accessing a shared variable “counter”. The threads contain code for either incrementing or decrementing the value of the “counter” variable. counter = 5 Thread1 (): Instruction 1: a = Read counter Instruction 2: Increment a Instruction 3: Write counter = a Thread2 (): Instruction 1: b = Read counter Instruction 2: Decrement b Instruction 3: Write counter = b If we were to first increment and then decrement the counter then the value stored would have been 5 + 1 - 1 = 5. But if the threads containing the incrementation and decrementation logic are running concurrently and the CPU is scheduling the threads then some of the possible situations that can happen are : Thread 1 → Instruction 1 ✅ ✅ (a = 5) Thread 2 → Instruction 1 ✅ ✅ (b = 5) Thread 2 → Instruction 1 Thread 1 → Instruction 2 ✅ ✅ (b = 5) (a = 5 + 1 = 6) Thread 1 → Instruction 1 Thread 2 → Instruction 2 ✅ ✅ (a = 5) (b = 5 - 1 = 4) Thread 2 → Instruction 2 Thread 1 → Instruction 3 Thread 2 → Instruction 3 ✅ ✅ (b = 5 - 1 = 4) (counter = a = 6) (counter = b = 4) Thread 1 → Instruction 2 Thread 2 → Instruction 3 Thread 1 → Instruction 3 ✅ ✅ (a = 5 + 1 = 6) (counter = b = 4) (counter = a = 6) ∴ Final value of counter becomes 4 ∴ Final value of counter becomes 6 Depending on the order of execution of the threads the value within the “counter” variable can vary and although the correct answer is 5 the value obtained can either be 4 or 6. This phenomenon is called race condition. Prepared By - The Department of Computational Sciences Page 3  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 This example shows how concurrent operations on shared resources (in this case, counter) can result in inconsistent outcomes when processes or threads aren't synchronized. Several processes / threads access and process the manipulations over the same data concurrently, and then the outcome depends on the particular order in which the access takes place. Critical Section Problem A race condition is a situation that may occur inside a critical section. This happens when the result of multiple thread execution in the critical section differs according to the order in which the threads execute. A critical section is a code segment that can be accessed by only one process at a time. The critical section contains shared variables that need to be synchronized to maintain the consistency of data variables. So the critical section problem means designing a way for cooperative processes to access shared resources without creating data inconsistencies. Consider a shared resource like a printer. If two processes try to print simultaneously, the output may get jumbled unless access to the printer is synchronized. Solution Criterions Any solution to the critical section problem must satisfy three requirements: Mutual Exclusion : If a process is executing in its critical section, then no other process is allowed to execute in the critical section. Progress : If no process is executing in the critical section and other processes are waiting outside the critical section, then only those processes that are not executing in their remaining section can participate in deciding which will enter the critical section next, and the selection can not be postponed indefinitely. Bounded Waiting : A bound must exist 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. The use of critical sections in a program can cause a number of issues, including: Deadlock: When two or more threads or processes wait for each other to release a critical section, it can result in a deadlock situation in which none of the threads or processes can move. Deadlocks can be difficult to detect and resolve, and they can have a significant impact on a program’s performance and reliability. Starvation: When a thread or process is repeatedly prevented from entering a critical section, it can result in starvation, in which the thread or process is unable to progress. This can happen if the critical section is held for an unusually long period of time, or if a high-priority thread or process is always given priority when entering the critical section. Prepared By - The Department of Computational Sciences Page 4  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Overhead: When using critical sections, threads or processes must acquire and release locks or semaphores, which can take time and resources. This may reduce the program’s overall performance. To solve the critical section problem, various approaches are used: Software Solutions: Algorithms like Peterson’s Algorithm enforce mutual exclusion. Hardware Solutions: Special machine instructions like test-and-set or compare-and-swap. Synchronization Primitives: High-level constructs like locks, semaphores, and monitors. In the upcoming section we will discuss software based solutions such as Peterson’s solution which can be used to solve the critical section problem. Software Based Solution (Peterson’s Solution) Peterson's Solution is a classic software-based algorithm designed to achieve mutual exclusion between two processes in a critical section problem. Proposed by Gary L. Peterson in 1981, this algorithm ensures that two processes can share a single-use resource (the critical section) without interference, while adhering to the principles of mutual exclusion, progress, and bounded waiting. It is particularly effective in uniprocessor environments where memory consistency is guaranteed. The synchronization problem arises in scenarios where multiple processes need access to shared resources. To prevent data inconsistency or race conditions, only one process should access the critical section at a time. Synchronization mechanisms like Peterson's Solution help enforce this mutual exclusion in a fair and deadlock-free manner. Peterson's Solution operates under the following assumptions: 1. Two processes: It is specifically designed for two processes, commonly denoted as P0​ and P1. 2. Shared variables: Two shared variables, flag[ ] and turn, are used for communication between the processes: ○ flag[i]: Indicates the intent of process Pi to enter the critical section. It is a boolean variable. ○ turn: Denotes whose turn it is to attempt entering the critical section. It can take values 0 or 1, representing P0​and P1, respectively. Algorithm Description - The algorithm is structured into three main sections for each process: 1. Entry Section: This section ensures mutual exclusion by coordinating access to the critical section. 2. Critical Section: The shared resource or critical code that only one process can execute at a time. 3. Exit Section: The process relinquishes its claim to the critical section. 4. Remainder Section: Any code outside the critical section where the process performs other tasks. Prepared By - The Department of Computational Sciences Page 5  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Pseudocode for Peterson’s Solution Thread (i) { flag[i] = true; // Declare intent to enter the critical section. j = 1 − i. // Whichever thread i is j will be the opposite one. turn = j; // Allow the other thread to proceed first. while (flag[j] && turn == j){ // Wait and let the other thread execute if the other thread has priority wait(i); }; // execute own Critical Section flag[i] = false; // Relinquish claim to the critical section (Exit Section) // Remainder Section } Explanation: 1. Peterson’s solution works for up to two concurrent processes/threads so we consider 2. Say we have 2 threads T0 and T1 which are to be executed by the CPU concurrently, when CPU executes T0 we set the flag of T0 to True signifying that T0 wants to execute. ∴ i = 0. 3. But If T1 wants to execute at the same time we will allow T1 to execute first. (as j = 1 - i = 1 and turn = j = 1). 4. While Thread T1 executes we do not execute T0’s critical section and keep thread T0 in waiting state. 5. After T1 completes execution, T0 is free to execute its critical section. 6. After executing its own critical section, thread T0 will relinquish claim to the critical section by setting its own flag value to False. 7. Then the remainder of the code is executed. Peterson's solution satisfies all the solution criterions for the critical section problem. Mutual Exclusion: The critical section is accessed by only one process at a time. If 𝑃0 is in the critical section, 𝑃1 cannot enter because the conditions flag && turn == 0 will not be true for 𝑃1. Progress: If no process is in the critical section and one or both wish to enter, the decision on who enters is made without indefinite delay. Bounded Waiting: A process cannot be starved; it will eventually enter the critical section after a finite number of entries by the other process. Prepared By - The Department of Computational Sciences Page 6  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Synchronization Mechanisms Synchronization mechanisms are techniques used in concurrent programming to manage the access of multiple threads or processes to shared resources, ensuring data consistency and preventing race conditions. These mechanisms are critical in multi-threaded or multi-process systems where different threads/processes may operate simultaneously on shared data. Common Synchronization Mechanisms 1. Mutex (Mutual Exclusion): ○ A mutex is a lock that ensures only one thread can access a critical section of code or a shared resource at a time. ○ Once a thread locks the mutex, other threads trying to acquire it are blocked until it is unlocked. 2. Semaphore: ○ A semaphore is a signaling mechanism that allows threads to access a shared resource. ○ There are two types: Binary Semaphore: Works like a mutex but doesn't track ownership. Counting Semaphore: Allows a fixed number of threads to access the resource simultaneously. 3. Spinlock: ○ A lightweight synchronization mechanism where a thread continuously checks (or "spins") for the lock to become available. ○ Useful in situations where the waiting time is expected to be very short. 4. Monitors: ○ High-level synchronization constructs that encapsulate data, locks, and condition variables in a single structure. ○ Languages like Java and Python provide built-in support for monitors. 5. Condition Variables: ○ Used with mutexes to allow threads to wait for certain conditions to be met. ○ Threads can "sleep" while waiting for the condition, releasing the associated lock, and are woken up when another thread signals the condition. 6. Read-Write Locks (RWLocks): ○ Allow multiple threads to read a resource simultaneously but give exclusive access to a single thread for writing. ○ Useful when reads are more frequent than writes. Mutex A mutex provides a locking mechanism. It stands for Mutual Exclusion Object. Mutex is mainly used to provide mutual exclusion to a specific portion of the code so that the process can execute and work with a particular section of the code at a particular time. A mutex enforces strict ownership. Only the thread that locks the mutex can unlock it. It is specifically used for locking a resource to ensure that only one thread accesses it at a time. Due to this strict ownership, a mutex is not only typically used for signaling between threads, but it is used for mutual exclusion also to ensure that a resource is accessed by only one thread at a time. Prepared By - The Department of Computational Sciences Page 7  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Mutex uses a priority inheritance mechanism to avoid priority inversion issues. The priority inheritance mechanism keeps higher-priority processes in the blocked state for the minimum possible time. However, this cannot avoid the priority inversion problem, but it can reduce its effect up to an extent. Advantages of Mutex No race condition arises, as only one process is in the critical section at a time. Data remains consistent and it helps in maintaining integrity. It is a simple locking mechanism that enters a critical section and is released while leaving the critical section. Disadvantages of Mutex If after entering into the critical section, the thread sleeps or gets preempted by a high-priority process, no other thread can enter into the critical section. This can lead to starvation. When the previous thread leaves the critical section, then only other processes can enter into it, there is no other mechanism to lock or unlock the critical section. Implementation of mutex can lead to busy waiting, which leads to the wastage of the CPU cycle. Uses of Mutex 1. Critical Section Protection: ○ Used to protect critical sections of code where shared resources are accessed or modified. Example: pthread_mutex_t lock; void critical_section() { pthread_mutex_lock(&lock); // Acquire the lock // Critical section: access shared resource pthread_mutex_unlock(&lock); // Release the lock } Prepared By - The Department of Computational Sciences Page 8  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 2. Thread Safety: ○ Ensures thread-safe access to shared variables, data structures, or resources. 3. Preventing Race Conditions: ○ Mutex prevents simultaneous updates to shared resources, avoiding inconsistent or corrupted states. 4. Coordination Between Threads: ○ Helps synchronize actions between threads in a multi-threaded environment. 5. Database or File Access: ○ Used to manage exclusive access to databases, files, or other shared I/O operations. 6. Inter-Process Communication (IPC): ○ In some systems, mutexes are used for synchronization between processes rather than just threads. Semaphores A semaphore is a signaling mechanism and a thread that is waiting on a semaphore can be signaled by another thread. This is different from a mutex as the mutex can be signaled only by the thread that is called the wait function. A semaphore uses two atomic operations, wait and signal for process synchronization. A Semaphore is an integer variable, which can be accessed only through two operations: wait() and signal(). There are two types of semaphores: Binary Semaphores and Counting Semaphores. Binary Semaphores: They can only be either 0 or 1. They are also known as mutex locks, as the locks can provide mutual exclusion. All the processes can share the same mutex semaphore that is initialized to 1. Then, a process has to wait until the lock becomes 0. Then, the process can make the mutex semaphore 1 and start its critical section. When it completes its critical section, it can reset the value of the mutex semaphore to 0 and some other process can enter its critical section. Counting Semaphores: They can have any value and are not restricted to a certain domain. They can be used to control access to a resource that has a limitation on the number of simultaneous accesses. The semaphore can be initialized to the number of instances of the resource. Whenever a process wants to use that resource, it checks if the number of remaining instances is more than zero, i.e., the process has an instance available. Then, the process can enter its critical section thereby decreasing the value of the counting semaphore by 1. After the process is over with the use of the instance of the resource, it can leave the critical section thereby adding 1 to the number of available instances of the resource. Prepared By - The Department of Computational Sciences Page 9  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Some Points Regarding P and V Operation P operation is also called wait, sleep, or down operation, and V operation is also called signal, wake-up, or up operation. Both operations are atomic and semaphore(s) are always initialized to one. Here atomic means that the variable on which read, modify, and update happens at the same time/moment with no pre-emption i.e. in between read, modify, and update no other operation is performed that may change the variable. Uses of Semaphores Mutual Exclusion: Semaphore ensures that only one process accesses a shared resource at a time. Process Synchronization: Semaphore coordinates the execution order of multiple processes. Resource Management: Limits access to a finite set of resources, like printers, devices, etc Reader-Writer Problem: Allows multiple readers but restricts the writers until no reader is present. Avoiding Deadlocks: Prevents deadlocks by controlling the order of allocation of resources. Advantages of Semaphores A simple and effective mechanism for process synchronization Supports coordination between multiple processes Provides a flexible and robust way to manage shared resources. It can be used to implement critical sections in a program. It can be used to avoid race conditions. Disadvantages of Semaphores It Can lead to performance degradation due to overhead associated with wait and signal operations. Can result in deadlock if used incorrectly. It can cause performance issues in a program if not used properly. It can be difficult to debug and maintain. Condition Variables Synchronization mechanisms need more than just mutual exclusion; also need a way to wait for another thread to do something (e.g., wait for a character to be added to the buffer) Condition variables: used to wait for a particular condition to become true (e.g. characters in buffer). wait(condition, lock): release lock, put thread to sleep until condition is signaled; when thread wakes up again, re-acquire lock before returning. signal(condition, lock): if any threads are waiting on condition, wake up one of them. Caller must hold the lock, which must be the same as the lock used in the wait call. Prepared By - The Department of Computational Sciences Page 10  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 broadcast(condition, lock): same as signal, except wake up all waiting threads. Note: after signal, signaling thread keeps lock, waking thread goes on the queue waiting for the lock. Warning: when a thread wakes up after cond_wait there is no guarantee that the desired condition still exists: another thread might have snuck in. Classical Synchronization Problems Producer Consumer Problem The problem describes two processes, User and Consumer, who share a common fixed size buffer. Producer consumer problem also known as the "Bounded Buffer Problem" is a multi-process synchronization problem. Producer: The producer's job is to generate a bit of data, put it into the buffer and start again. Consumer: The consumer is consuming the data(i.e remaining it from the buffer) one piece at a time. If the buffer is empty, then a consumer should not try to access the data item from it. Similarly, a producer should not produce any data item if the buffer is full. Counter: It counts the data items in the buffer. or to track whether the buffer is empty or full. Counter is shared between two processes and updated by both. How does it work? Counter value is checked by the consumer before consuming it. If the counter is 1 or greater than 1 then start executing the process and update the counters. Similarly producers check the buffer for the value of Counter for adding data. If the counter is less than its maximum values, it means that there is some space in Buffer. Prepared By - The Department of Computational Sciences Page 11  Course Name: Operating System Course Code : BCA30110 Academic Session: 2024-25 Producer Consumer Problem using Semaphores Producer consumer problem is a classical synchronization problem. We can solve this problem by using semaphores. A semaphore S is an integer variable that can be accessed only through two standard operations : wait() and signal(). The wait() operation reduces the value of semaphore by 1 and the signal() operation increases its value by 1. wait(S){ while(S