MODERN OPERATING SYSTEMS Third Edition ANDREW S. TANENBAUM Chapter 2 Processes and Threads

UNIT 2 Inter-process Communication: Race Conditions, Critical Regions, Mutual Exclusion with Busy Waiting, Semaphores, Mutexes, Monitors, Message Passing, Avoiding Locks, Read- Copy-Update..

[Audio] This course offers a comprehensive overview of inter-process communication, covering topics such as race conditions, critical regions, mutual exclusion, semaphores, mutexes, monitors, message passing, and avoiding locks. The course aims to provide students with a thorough understanding of these concepts, which are crucial for ensuring efficient and reliable communication between processes..

Text Books.

Modules.

[Audio] Memory management strategies include swapping, contiguous memory allocation, paging, segmentation, and virtual memory management. These techniques help manage memory efficiently by allocating and deallocating memory blocks dynamically. This allows multiple processes to share the same physical memory, improving overall system performance..

[Audio] InterProcessCommunication is a fundamental concept in computer science where we discuss how processes interact with each other. We have to ensure that these interactions are safe and efficient. One major challenge is the mutual exclusion problem where multiple processes need to access shared resources simultaneously. To solve this issue we can use software approaches like Dekker's and Peterson's algorithms hardware support through atomic operations OS solutions using semaphores PL solutions employing monitors and distributed OS solutions relying on message passing. These solutions help us avoid the reader/writer problem and the Dining Philosophers Problem ensuring that our concurrent systems operate correctly.

[Audio] There are three main problems we face when dealing with interprocess communication. How to actually implement this communication is the first challenge. The second issue is addressing process conflicts, where two processes might want to access the same resource simultaneously, leading to situations like two airline passengers trying to reserve the same seat. Lastly, ensuring proper sequencing when there are dependencies involved is crucial, as we should aim to fire only when all necessary preparations are complete, much like aiming a gun before pulling the trigger. Notably, these same issues arise when working with threads as well, and the solutions are similar..

[Audio] Competing processes refer to situations where multiple processes are running concurrently, each trying to access the same system resources such as disk, file, or printer. This can lead to potential problems like deadlock and starvation. On the other hand, cooperating processes involve results from one or more processes being needed for another process. There are two ways this cooperation can occur: through sharing, such as sharing an I/O buffer, which requires mutual exclusion; or through direct communication, where coordination through synchronization becomes essential..

[Audio] When multiple processes access and modify shared data simultaneously, a race condition occurs. This situation can result in unpredictable outcomes, as the final value of the shared data depends on the order in which processes complete their operations. To mitigate this issue, concurrent processes must be synchronized to ensure that they access shared resources in a controlled manner..

[Audio] When multiple processes access shared resources, race conditions can occur. A race condition arises when two or more processes simultaneously access and modify a shared resource, resulting in unpredictable outcomes. For instance, consider a local variable holding a pointer to the next free slot. This variable is utilized by various processes to allocate memory. A race condition may emerge if two processes attempt to access this variable simultaneously. One process might read the variable's value while the other process modifies it, potentially leading to one process allocating memory from a slot already allocated by another process. To circumvent such scenarios, it is essential to guarantee that only one process accesses the shared resource at a time, which can be accomplished using methods like mutual exclusion, semaphores, or monitors..

[Audio] Successful use of concurrency among processes requires defining critical sections and enforcing mutual exclusion. This ensures that multiple processes can access shared resources simultaneously without interference. By doing so, we prevent race conditions from occurring, where the outcome depends on the order in which processes execute..

[Audio] A critical section is a code segment that can be executed by only one process at a time. This section contains shared variables that require synchronization to maintain the consistency of data variables. In other words, the critical section problem involves designing a mechanism for cooperative processes to access shared resources without introducing data inconsistencies..

[Audio] Mutual Exclusion ensures that only one process can access the Critical Region at a time, which prevents data corruption and ensures consistency. Progress guarantees that a process waiting to enter the Critical Region will not be blocked by another process already inside. Bounded Wait ensures that a process will not wait indefinitely to access the Critical Region. Finally, Architectural Neutrality means that the synchronization mechanism should work regardless of the underlying architecture and the relative speeds of the processes..

[Audio] Only one process should execute in its critical section at any given time. This ensures mutual exclusion among processes. Additionally, waiting processes should be able to proceed as soon as a process exits its critical section, thereby promoting progress. Furthermore, there should be a limit on the delay between a process's request to enter its critical section and its actual entry into that section, thus preventing indefinite blocking..

What we are trying to do.

[Audio] First attempts to achieve mutual exclusion were based on busy waiting. This involved proposing a series of mechanisms to ensure that only one process could enter a critical region at a time. These included disabling interrupts, lock variable mechanisms, the TSL mechanism, strict alternation, and Peterson's solution..

[Audio] Disabling interrupts is an idea where a process disables interrupts, enters its critical section, and then enables interrupts when it leaves the critical section. This approach, however, has two major problems. One problem is that a process might never enable interrupts, which would cause the system to crash. Another problem is that this method will not work on multi-core chips because disabling interrupts only affects one CPU at a time. When interrupts are disabled, no clock interrupts can occur, and the CPU will not switch between processes. As a result, once a process has disabled interrupts, it can safely examine and update the shared memory without worrying about interference from other processes..

[Audio] When a process enters its critical region, it first checks the state of the lock. If the lock is available, the process acquires it by setting it to a busy state and then proceeds into the critical region. However, if the lock is already held by another process, the current process will wait until the lock becomes available again. This mechanism ensures that only one process can access the critical region at any given time, thereby preventing race conditions and guaranteeing mutual exclusion..

[Audio] When the TSL test set lock mechanism is used, a process enters a region code for TSL results in busy waiting, where the process keeps testing the lock. The clock runs out, and the process is bumped from the CPU because there is no clock for threads. As a result, a spinning thread could wait forever, necessitating our getting the spinner out of there. To do this, we employ thread_yield, which relinquishes the CPU to another thread. Notably, thread_yield is swift, occurring in user space, and no kernel calls are required for mutex_lock or mutex_unlock..

[Audio] In this implementation of TestAndSet, mutual exclusion is ensured by setting the lock to true once a process enters the critical section, thereby preventing other processes from entering until the first process exits. Progress is ensured by allowing each process to enter the critical section one by one. However, the lack of queue maintenance means that bounded waiting is not guaranteed, as multiple processes can enter the critical section simultaneously if they find the lock to be false. To address this issue, the Strict Alternation mechanism is implemented..

[Audio] When two processes compete for access to a critical region, an integer variable named turn tracks whose turn it is to enter the region. Initially, process 0 inspects turn and finds it to be zero, subsequently entering its critical region. However, process 1 also discovers turn to be zero and remains idle in a tight loop, persistently examining turn to determine when it becomes one. This phenomenon is referred to as busy waiting, wherein a process repeatedly verifies a condition until it becomes valid. In this instance, process 1 squanders CPU resources by perpetually inspecting turn..

[Audio] When we employ strict alternation, we encounter some problems. One issue arises from busy waiting, where while waiting for the critical section, a process spins, wasting CPU cycles. Another problem occurs when one process is outside the critical section and it's its turn, in which case another process has to wait until the outside process finishes both its outside and inside work, leading to unbounded delays..

[Audio] Peterson's Solution is a software-based solution to the mutual exclusion problem that combines the ideas of taking turns and lock variables and warning variables. This solution was first devised by a Dutch mathematician, T. Dekker, who did not require strict alternation. In this solution, there are two shared variables: a boolean array initialized to false, indicating no one is interested in entering the critical section, and an integer variable tracking the process whose turn it is to enter the critical section..

. Peterson's Solution.

[Audio] Initially, neither process is in its critical region. Process 0 calls enter region, indicating its interest by setting its array element and setting turn to 0. Since process 1 is not interested, enter region returns immediately. However, if process 1 now makes a call to enter the region, it will hang there until interested[0] goes to FALSE, which occurs only when process 0 calls leave region to exit the critical region. Now, both processes call enter region almost simultaneously. They will store their process numbers in turn, but whichever store is done last is the one that counts, as the first one is overwritten and lost. Suppose process 1 stores last, so turn becomes 1. When both processes reach the while statement, process 0 executes it zero times and enters its critical region. Meanwhile, process 1 loops and does not enter its critical region until process 0 exits its critical region..

[Audio] Peterson's solution ensures mutual exclusion by allowing only one process to access the critical section at a time. This means that if a process is executing in its critical section, no other process can enter the critical section until the first process exits. Additionally, progress is ensured since a process outside the critical section does not block other processes from entering the critical section. Furthermore, bounded waiting is preserved as every process gets a fair chance to enter the critical section. However, there are some disadvantages to consider. Firstly, Peterson's solution involves busy waiting, which can waste CPU cycles. Secondly, it is limited to two processes, making it impractical for use in systems with more than two processes. Finally, Peterson's solution is not suitable for modern CPU architectures due to its limitations..

[Audio] When trouble arises, the producer wants to put a new item in the buffer, but it is already full. To solve this issue, the producer goes to sleep, waiting for the consumer to remove one or more items. Similarly, when the consumer wants to remove an item from the buffer and finds it empty, it goes to sleep until the producer puts something in the buffer and wakes it up. This ensures that both processes operate independently, without interfering with each other..

[Audio] Two processes share a common, fixed-size buffer. One of them, the producer, puts information into the buffer, and the other one, the consumer, takes it out. To keep track of the number of items in the buffer, we use a variable called count. The producer checks if the buffer is full by comparing count to its maximum capacity N. If it is, the producer sleeps until the consumer removes some items, allowing the buffer to become available again. If the buffer is not full, the producer adds an item and increments count. Similarly, the consumer checks if the buffer is empty by comparing count to zero. If it is, the consumer sleeps until the producer adds some items, making the buffer available. If the buffer is not empty, the consumer removes an item and decrements count. Both processes also check if the other needs to be awakened and wake each other up if necessary..

[Audio] The Producer-Consumer Problem is a classic example of inter-process communication where two processes share a common, fixed-size buffer. The producer puts information into the buffer, while the consumer removes it. Trouble arises when the buffer is full or empty, requiring the processes to communicate and coordinate their actions. This problem can be solved using busy waiting, semaphores, or monitors..

[Audio] When a producer produces something and sends a wake-up call to the consumer, but the consumer is not asleep, it will ignore the wake-up call because it still thinks the count is zero. This can lead to a situation where both the producer and consumer sleep forever, resulting in lost wake-up calls..

[Audio] Semaphores are a tool used in operating systems to help manage how different processes share resources, like memory or data, without causing conflicts. A semaphore is a special kind of synchronization data that can be used only through specific synchronization primitives. Semaphores are used to implement critical sections, which are regions of code that must be executed by only one process at a time. By using semaphores, processes can coordinate access to shared resources, such as shared memory or I/O devices. Semaphores use a counter to control access, allowing synchronization for multiple instances of a resource. Processes can attempt to access one instance, and if it is not available, they can try other instances..

[Audio] Semaphores differ from basic locks in that they can handle more complex synchronization scenarios involving multiple processes or threads. By controlling when and how processes access shared data, semaphores help prevent problems like race conditions. The process of using semaphores involves two primary operations: waiting and signaling. When the value of the semaphore is zero, any process that waits will be blocked until another process signals..

[Audio] When a process performs a wait operation on a semaphore, it first checks whether the value of the semaphore is greater than zero. If so, it decrements the value and allows the process to continue its execution. Otherwise, it blocks the process on the semaphore. A signal operation on a semaphore activates a process blocked on the semaphore, if any, or increments the value of the semaphore by one. The initial value of a semaphore determines how many processes can successfully complete their wait operations..

[Audio] Semaphores are of two types. One type is the binary semaphore, which can only be in one of two states: 0 or 1. It is also known as a mutex lock because it provides mutual exclusion. Multiple processes can share the same mutex semaphore, which is initially set to 1. A process must wait until the lock becomes 0 before entering its critical section. Once inside, the process sets the mutex semaphore back to 1 and then resets it to 0 when it exits, allowing another process to enter its critical section..

[Audio] Counting semaphores are used to control access to resources that have limitations on the number of simultaneous accesses. They can be initialized to the number of instances of the resource, and each time a process wants to use that resource, it checks if there are remaining instances available. If yes, the process enters its critical section, decreases the value of the semaphore by one, and then leaves the critical section when it's done with the resource. This ensures that the resource is not accessed simultaneously by multiple processes..

[Audio] Semaphores are a fundamental concept in inter-process communication. They are integer variables shared among multiple processes, designed to synchronize and control access to common resources in a concurrent environment. The down operation on a semaphore checks if the value is greater than zero, decrementing it if so, and putting the process to sleep if the value reaches zero. This atomic operation ensures that once a semaphore operation starts, no other process can access the semaphore until the operation completes or blocks. This atomicity is crucial in solving synchronization problems and avoiding race conditions..

[Audio] In the bounded buffer problem, also known as the producer-consumer problem, there are two processes working together to achieve a specific goal. The producer inserts data into the buffer, while the consumer removes data from the buffer. However, these two processes need to operate independently to ensure efficient execution. Without proper synchronization, the producer and consumer may not produce the expected output when executed concurrently. This problem highlights the importance of ensuring mutual exclusion between the producer and consumer to avoid conflicts and ensure successful communication..

[Audio] In producer-consumer problems, semaphores can be used to solve the issue. Three types of semaphores are employed: mutex, empty, and full. The mutex semaphore ensures mutual exclusion by acquiring and releasing the lock. The empty semaphore tracks the number of empty slots in the buffer, whereas the full semaphore counts the number of occupied slots. This combination enables efficient management of the buffer and prevents conflicts between producers and consumers..

[Audio] Semaphores can be used to solve the producer-consumer problem. We have two types of semaphores: a mutex, which ensures mutual exclusion, and two counting semaphores, empty and full, which keep track of the available slots in the buffer. The mutex is used to protect access to the buffer, while the counting semaphores ensure that the producer does not overwrite data that has not been consumed by the consumer. This approach allows us to avoid busy waiting and achieve efficient communication between the producer and consumer..

[Audio] Semaphores offer several advantages. They enable multiple threads to access the critical section simultaneously, increasing the overall system performance by allowing multiple tasks to be executed concurrently. They are machine-independent, making them suitable for use in a variety of environments. They prevent multiple processes from entering the critical section at the same time, ensuring data consistency and integrity. Since they involve busy waiting, there is no waste of processing time and resources. They can also be used to manage resources flexibly, allowing for efficient allocation and utilization of system resources..

[Audio] Mutexes are a type of synchronization mechanism that allows multiple processes or threads to share resources while ensuring that only one process or thread accesses a critical region at any given time. This is achieved by locking the mutex when a process or thread wants to access the critical region, and unlocking it when it has finished using the region. If a process or thread finds that the mutex is already locked, it will block until the mutex is unlocked. This ensures that only one process or thread can access the critical region at any given time, preventing conflicts and errors..

[Audio] When a process enters a region code for TSL results in busy waiting, it keeps testing the lock. This means that the clock runs out, and the process is bumped from the CPU. Since there is no clock for threads, a spinning thread could wait forever, making it necessary to get the spinner out of there. To achieve this, we use thread_yield to give up the CPU to another thread. Fortunately, thread yield is fast and occurs in user space, requiring no kernel calls for mutex_lock or mutex_unlock..

[Audio] Pthread calls for mutexes, trying to lock a mutex. If it fails, it returns an error code and can do something else..

[Audio] Monitors are another way to achieve process synchronization. They are supported by programming languages to achieve mutual exclusion between processes. For instance, Java synchronized methods provide this functionality, along with wait() and notify() constructs. A monitor is essentially a combination of condition variables and procedures packaged together in a special kind of module or package. This means that processes running outside the monitor cannot access its internal variables, but they can call its procedures. Moreover, only one process can execute code within a monitor at any given time..

[Audio] In order to fully realize the potential of monitors, we need to introduce one additional new data type, known as a condition. A variable of this type has only two legal operations, wait and signal. If X was defined as type condition, then legal operations would be X.wait() and X.signal(). The wait operation blocks a process until some other process calls signal, and adds the blocked process onto a list associated with that condition. The signal process does nothing if there are no processes waiting on that condition. Otherwise, it wakes up exactly one process from the condition's list of waiting processes. This contrasts with counting semaphores, which always shared..

Monitor-a picture.

[Audio] When two different operations are performed on the condition variables of the monitor, wait and signal operations take place. We declare two condition variables, x and y. The wait operation suspends the process performing this operation on any condition variable, placing the suspended processes in the block queue of that condition variable. Note that each condition variable has its unique block queue. The signal operation allows a process to perform a signal operation on a condition variable, giving one of the blocked processes a chance when executed. If the block queue is empty, the signal is ignored, otherwise, a process is resumed from the block queue..

[Audio] Monitors have several advantages over other synchronization mechanisms. They simplify parallel programming, reducing the likelihood of errors. In contrast, techniques like semaphores require more complex implementation. However, monitors also have some limitations. They need to be integrated into the programming language itself, which adds complexity to the compiler. Moreover, this integration requires knowledge of the underlying operating system's facilities for controlling access to critical sections. Some popular programming languages that support monitors include Java, C#, Visual Basic, Ada, and Concurrent Euclid..

[Audio] In this slide, we examine message passing as a means of exchanging information between machines. The two fundamental operations involved are sending and receiving. When sending a message, we specify both its destination and content. Conversely, when receiving a message, we identify its source and expected contents. Nevertheless, numerous design issues arise from employing message passing. A significant concern is message loss, where a message may fail to reach its intended recipient during transmission. To mitigate this risk, we utilize techniques such as acknowledgments and timeouts. Furthermore, authentication is another critical consideration, as processes must verify the identity of the sender to ensure secure communication..

[Audio] Consumer and producer processes communicate using message passing. In this scenario, the consumer sends N empty messages to the producer, indicating its readiness to receive data. The producer then fills these messages with data and sends them back to the consumer. This approach allows the two processes to coordinate their actions and exchange information efficiently..