Mutual Exclusion in Operating system
Mutual Exclusion in Operating system
The meaning and implications of mutual exclusion:
A feature of concurrency management known as mutual exclusion makes sure that only one process at a time can access a shared resource. Race circumstances, which can happen when several processes use the same resource at once and change it inconsistently, must be avoided in order to do this.
For numerous concurrent systems to operate correctly, mutual exclusion is crucial. It is utilized, for instance, to safeguard shared data structures in databases, guarantee that only one application can print to a printer at once, and avoid deadlocks in multithreaded programs.
A description of the crucial passages and the necessity of synchronisation
A portion of code that makes use of a common resource is known as a vital section. A process must have exclusive access to the resource when it is in its critical phase. A synchronisation mechanism, like a mutex or semaphore, is used to enforce this.
The possibility of numerous processes running at once creates the requirement for synchronisation. It is feasible for two processes to attempt to modify the same common asset simultaneously if they both try to access it at the same moment. This could result in a race circumstance, where the resource's actual state is unpredictable.
By limiting simultaneous access to a shared resource to one process, synchronisation methods aid in the prevention of race circumstances. To do this, access to the resource is restricted using locks or semaphores.
The advantages of mutual exclusion include the following:
- Race circumstances are prevented, which might result in inconsistent data and other issues.
- It guarantees that all processes utilise shared resources fairly.
- By lowering the level of resource contention, it can enhance the efficiency of concurrent systems.
The following are some difficulties in putting mutual exclusion into practise:
- Making sure that every process appropriately uses the synchronisation mechanism might be challenging.
- Operations may have to wait in order to access shared resources, which might increase system overhead.
- In distributed systems, mutual exclusion might be challenging to implement.
An explanation of the issue with the critical part
When numerous processes must access a common resource, the concurrent programming challenge known as the crucial section problem occurs. The resource may end up in a race condition, where the final state is inconsistent, if the processes fail to coordinate their access to the resource.
A portion of code that makes use of a common resource is known as a vital section. A process must have exclusive access to the resource when it is in its crucial phase. This is required to avoid racial situations.
Here are some instances where having multiple users access a shared resource simultaneously may cause problems:
- The same variable is being updated by two different processes. The ultimate value of the variable can be inconsistent if the processes do not synchronise their updates.
- The same printer is being used by two different processes. The output of the two processes can be printed in the wrong sequence by the printer if the processes do not synchronise their printing.
- The same data structure is being accessed by two different programmes. It is possible for the data structure to get corrupted if processes do not synchronise their access to it.
An explanation of the idea of reciprocal exclusion as a possible solution
A feature of concurrency management known as mutual exclusion makes sure that only one process at a time can access a shared resource. This is required to avoid racial situations.
There are numerous ways to put mutual exclusion into practise. Using a mutex, a lock that a process can obtain to get exclusive access to a resource, is one typical method. A mutex prevents access to a resource from being made by another process until it is released.
Using semaphores is another approach to put mutual exclusion into practise. Counters called semaphores can be employed to regulate access to a common resource. The semaphore counter decreases each time a process attempts to access a resource. When the counter reaches 0, the process is halted until the counter is increased by another process.
An essential idea in concurrent programming is mutual exclusion. Race conditions are avoided, and it makes sure that all processes consume shared resources equally.
Mutual Exclusion Techniques:
Software-based approaches
For mutual exclusion, there are numerous various software-based methods. Among the most popular remedies are:
Mutexes, semaphores, and locks
Mutual exclusion is a problem that can be solved with software using locks, semaphores, and mutexes.
They all function by limiting simultaneous access to a shared resource by several programmes. They vary, nevertheless, in terms of how they're put into practise and the features they provide.
Locks
- Simple but powerful
- a variable that a process can obtain to obtain exclusive access to a resource
- Other processes cannot access a resource after a process locks it until the lock is released.
Semaphores
- More difficult but more adaptable
- Access-controlling counters for a shared resource
- The semaphore counter decreases whenever a process attempts to access a resource.
- The process is halted until another process increases the counter if the counter is 0.
Mutexes
- a particular kind of lock created for mutual exclusion
- Usually, semaphores are used to implement
- Include some extra functions that make them simpler to utilise.
Application, benefits, and restrictions
The easiest and clearest approach to create mutual exclusion is through locks. They can be ineffective, though, as they can obstruct processes that are patiently waiting to gain a lock.
Locks are simpler than semaphores, but semaphores are more effective. Mutual exclusion is one of the many synchronisation primitives that can be implemented using semaphores.
A particular kind of lock made for mutual exclusion is called a mutex. Semaphores are often used to implement mutexes, but they offer certain other capabilities that make them simpler to utilise.
The fundamental benefit of software-based mutual exclusion solutions is that they are reasonably simple to put into practise. However, they could be ineffective and challenging to apply in intricate systems.
Examples of the code used to implement them in various programming languages:
Here are a few lines of code from several programming languages that demonstrate how locks, semaphores, and mutexes are implemented:
def lock(resource):
global lock_holder
if lock_holder is not None:
print("Resource is already locked by", lock_holder)
return False
lock_holder = resource
return True
def unlock(resource):
global lock_holder
lock_holder = None
Introduction to atomic operations and hardware instructions:
An operation that is promised to be finished in a single step, unaffected by other actions, is known as an atomic operation. Hardware instructions are directives that the computer's hardware carries out.
Examining mutual exclusion techniques based on hardware, such as fetch-and-add, compare-and-swap, and test-and-set
Hardware-based techniques for mutual exclusion come in a variety of forms. Among the most popular mechanisms are:
Test-and-set
A hardware instruction called test-and-set atomically tests and sets a variable. The variable's value is initially tested by the instruction. The instruction returns one and sets the variable's value to one if the value is zero. The instruction returns 0 if the variable's value is not zero.
def test_and_set(some_variable):
old_value = some_variable
some_variable = 1
return old_value
Compare-and-swap
A hardware instruction called compare-and-swap compares a variable's value atomically to a provided value and, if both values are equal, sets the variable's value to a new value. If the values are equal and the variable was properly changed to the new value, the instruction returns one. The instruction returns 0 if the values were not equivalent.
def compare_and_swap(variable, old_value, new_value):
current_value = variable
if current_value == old_value:
variable = new_value
return 1
else:
return 0
Fetch-and-add
A hardware instruction known as the fetch-and-add operation atomically gets the value of an array variable and adds a specified value to it. The command restores the variable's previous value.
def fetch_and_add(some_variable, value):
old_value = some_variable
some_variable = old_value + value
return old_value
Software-based and hardware-based methods are compared.
Software-based mutual exclusion solutions are often less effective than hardware-based ones. This is due to the assurance of atomicity in hardware instructions, which software-based solutions do not provide. Hardware-based solutions are more difficult to implement, though.
For devices where efficiency is important, hardware-based solutions are typically a solid option. Software-based solutions are an excellent option for systems where flexibility and simplicity are priorities.
Synchronization Primitives:
Mutexes
A mutex is a basic for synchronisation that makes sure only one thread at a time can access a shared resource. Mutual exclusion is frequently implemented in concurrent programming using mutexes.
A thorough discussion of mutex locks and their characteristics:
A thread can acquire a mutex lock, a variable, to get exclusive access to a resource. Other threads cannot access a resource after a thread locks a mutex till the lock is released.
Several characteristics of mutex locks include:
Mutual exclusion: A mutex lock can only be held by one thread at a time.
Arbitration: If several threads attempt to obtain a mutex lock at the same moment, only one of them will be successful, and the others will be blocked.
Reentrancy: A thread can repeatedly obtain a mutex lock without blocking.
Fairness: There is no guarantee that the sequence in which threads obtain mutex locks is fair.
Read-write locks and reentrant mutexes are the two primary categories of mutexes.
The same thread can repeatedly obtain reentrant mutexes without blocking. This is advantageous in circumstances when a thread must repeatedly access a shared resource without releasing the lock.
Multiple threads can read from a shared resource at once thanks to read-write locks, but only one thread can write to the resource at once. This is helpful when just one thread has to write to a shared resource but numerous threads need to read from it.
Here is a sample Python code showing how to use mutexes:
import threading
def criticalsection():
print("In critical section")
def main():
mutex = threading.Lock()
# Acquire the mutex lock
mutex.acquire()
# Enter the critical section
criticalsection()
# Release the mutex lock
mutex.release()
if __name__ == "__main__":
main()
Output:
![Mutual Exclusion in Operating system](https://static.tutorialandexample.com/operating-system/mutual-exclusion-in-operating-system1.png)
Semaphores
To manage access to a shared resource, synchronization primitives called semaphores are utilized. Semaphores are frequently used to perform mutual exclusion, but they may also be employed to implement barriers and counting semaphores, in addition to mutual exclusion.
A description of semaphores in general, including the binary and counting types
A data type that can store an integer value is a semaphore. The variety of resources that are available is tracked using the semaphore's value. The semaphore value is decreased by a process when it needs to access a resource. The process is halted until the semaphore value is increased by another process if the semaphore value is zero.
Binary semaphores and counting semaphores are the two basic categories of semaphores.
- Only the values 0 and 1 can be stored in binary semaphores. When a binary semaphore has the value 0, it means that there are no resources available, and when it has the value 1, it means that there is one resource accessible.
- Any integer value can be stored in counting semaphores. The availability of n resources is indicated by a counting semaphore with the value n.
An explanation of wait and signal semaphore actions:
Semaphores can be used for two different types of operations: wait and signal.
- The semaphore's value drops when you wait. The procedure is blocked if the semaphore's value is zero.
- Signal increases the semaphore's value. A process gets unblocked if it has been blocked on the semaphore.
import threading
import time
def criticalsection(semaphore):
print("In critical section")
time.sleep(1)
def main():
semaphore = threading.Semaphore(1)
# Acquire the semaphore
semaphore.acquire()
# Enter the critical section
criticalsection(semaphore)
# Release the semaphore
semaphore.release()
if __name__ == "__main__":
main()
Output:
![Mutual Exclusion in Operating system](https://static.tutorialandexample.com/operating-system/mutual-exclusion-in-operating-system2.png)
Monitors
A monitor is a synchronisation mechanism that enables threads to wait (block) until a specific condition is no longer true as well as mutual exclusion. The ability to alert other threads when a condition has been satisfied is another feature of monitors.
Overview of monitors and how they help mutual exclusion happen
A monitor is a mechanism to organise concurrent code in a way that makes it simple to analyse and troubleshoot. Only one thread can be running at a time in a monitor because to the mutual exclusion mechanism enforced by monitors. This is crucial to preventing the corruption of shared data.
Examining condition variables and how monitors use them:
A condition variable is a type of basic synchronization that enables threads to wait for something particular to occur.
A thread is blocked until the condition is met when it uses the wait() method on a condition variable. After then, the thread is free to continue running.
Monitors support wait-notify semantics via condition variables. This implies that a thread can stand by for a condition to materialise before receiving notification from another thread when it does.
Here is some sample Python code illustrating the use of monitors:
import threading
class Monitor:
def __init__(self):
self.lock = threading.Lock()
self.condition = threading.Condition(self.lock)
def critical_section(self):
with self.lock:
print("In critical section")
def wait(self, condition):
with self.lock:
while not condition:
self.condition.wait()
def notify(self):
with self.lock:
self.condition.notify()
def main():
monitor = Monitor()
thread1 = threading.Thread(target=monitor.critical_section)
thread2 = threading.Thread(target=monitor.wait, args=(True,))
thread1.start()
thread2.start()
thread1.join()
thread2.join()
if __name__ == "__main__":
main()
Output:
![Mutual Exclusion in Operating system](https://static.tutorialandexample.com/operating-system/mutual-exclusion-in-operating-system3.png)
In this code, a lock and a condition variable are defined by the Monitor class. The criticalsection() method enters the critical section after acquiring the lock. The wait() method first obtains the lock before waiting for the condition to materialize.
After obtaining the lock, the notify() method notifies each thread that is awaiting the condition.
A Monitor object is created by the main() function, which then launches two threads. The crucial section is entered when the first thread invokes the criticalsection() method. The wait() method is used by the second thread, and it blocks until the condition is satisfied. The thread that has been waiting on the condition is woken up by the notify() method, which is invoked by the main() function. The thread that is now executing then resumes while waiting for the condition.
Deadlocks and Starvation:
A deadlock occurs when two or more processes are halted while they wait for one another to release a resource. This can happen if two processes are competing for the same resource.
Deadlock requires the following four factors to take place:
Mutual exclusion: Only one process at a time may hold a given resource.
Hold and wait: A process has the ability to hold one resource while requesting another that is being held by a different process.
Pre-emption is not allowed: Processes that are retaining resources cannot be made to give them up.
Circular chain of processes: Each process in the chain is waiting for a resource that is being held by the process after it in the chain.
Starvation
When a process is unable to obtain the resources it requires to function, it is said to be starving. This might occur if some processes are constantly using up all the resources or if the operating system's scheduling method is unfair.
The two main forms of famine are as follows:
- When a process cannot access a resource that it requires to function, it suffers from denial of service hunger.
- When a process is unable to obtain adequate resources to function, it experiences resource hunger.
Methods for avoiding, avoiding deadlock, and detecting it
Deadlocks can be resolved using three basic strategies: detection, avoidance, and prevention.
Deadlock avoidance
A group of methods called "deadlock prevention" can be applied to stop deadlocks from happening. These methods consist of:
Resource allocation ordering: Resources are distributed to processes in a certain order using this strategy, which makes sure of it.
Resource preemption: The operating system can preempt a process using the resource preemption technique if it keeps a resource that is required by another process.
Deadlock detection: In this method, the operating system checks for deadlocks on a regular basis and breaks them if any are discovered.
Avoiding a deadlock
A collection of methods called "deadlock avoidance" can be applied to stop deadlocks from happening. These methods consist of:
A graph of all the system's resources and operations is created using the resource allocation technique. The graph is then examined to look for potential deadlocks.
Banker's algorithm: This algorithm determines the most resources each process is allowed to have. The method then determines whether any process can deadlock given the distribution of resources at that moment.
Detection of deadlocks:
The OS periodically scans for deadlocks using the deadlock detection approach, breaking them if any are discovered. Although this method is the least efficient of the three, it is also the simplest to use.
Strategies for preventing starvation
There are a variety of methods for preventing starving, including:
- Priority-based scheduling: Priorities are assigned to processes using this scheduling method. When allocating resources, higher priority processes are given preference.
- Fairness: By using this method, all processes receive an equal distribution of resources.
Readers-Writers Problem: Synchronisation Issues and Solutions
Computer science's most well-known synchronisation issue is the readers-writers problem. Allowing several readers to use a resource that is shared while only permitting one writer to use it at a time is problematic.
The readers-writers issue can be resolved in two ways:
- Locks for readers and writers: This straightforward method uses two locks, one for users and one for authors. Readers can obtain the reader lock, but before writers can use the shared resource, they must first obtain the writer lock.
- Listed in order of importance: One lock each for readers, writers, and priority readers makes up this more intricate approach. Even if there are authors waiting to access the shared resource, priority readers are still permitted access.
Problem with Dining Philosophers
Another well-known synchronisation issue in computer science is the dining philosopher’s problem. Modelling the problem involves placing a fork in front of each of the five philosophers as they sit at a round table. The philosophers must have both forks in order to eat, and they can only have both forks if the other four philosophers do not.
The employment of semaphores is one of the most common answers to the dining philosophers puzzle. A basic for synchronization known as semaphores can be used to manage access to a shared resource. Semaphores can be employed in the dining philosopher’s problem to guarantee that only one philosopher is able to use a fork at once.
import threading
class Monitor:
def __init__(self):
self.lock = threading.Lock()
self.condition = threading.Condition(self.lock)
def critical_section(self):
with self.lock:
print("In critical section")
def wait(self, condition):
with self.lock:
while not condition:
self.condition.wait()
def notify(self):
with self.lock:
self.condition.notify()
def main():
monitor = Monitor()
thread1 = threading.Thread(target=monitor.critical_section)
thread2 = threading.Thread(target=monitor.wait, args=(True,))
thread1.start()
thread2.start()
thread1.join()
thread2.join()
if __name__ == "__main__":
main()
Output:
![Mutual Exclusion in Operating system](https://static.tutorialandexample.com/operating-system/mutual-exclusion-in-operating-system4.png)
Techniques for buffering data to ensure uniformity and prevent racial situations:
Some buffering techniques to ensure data consistency and prevent race circumstances are as follows:
Use one buffer: If a buffer will only be accessed by one process or thread, just one buffer has to be used. The most basic and most effective strategy is this one.
Use several buffers: If a buffer will be accessed by several processes or threads, use multiple buffers. By enabling many threads or processes to make use of the buffers concurrently, this can aid in performance improvement.
Use a lock system to make sure that just one thread or process is able to access a buffer at once. This could aid in averting racial situations.
Use a versioning scheme to keep track of changes made to a buffer: Versioning schemes are used to keep track of changes made to buffers. This may make it easier to maintain data consistency.
Buffer overflow flaws and how they affect system security:
When a programme sends more data into a buffer than the buffer can retain, a buffer overflow is a software error that happens. This might overwrite nearby memory locations, which might have different security repercussions.
For instance, a buffer overflow vulnerability might be used by an attacker to change the return address on the stack and so take over the program's execution. They could be able to use this to run arbitrary code, steal private information, or bring down the system.
Techniques for mitigating buffer overflow attacks:
Buffer overflow attacks can be reduced using a variety of approaches, such as:
Bounds checking: Bounds checking is a method for making sure that data being written to a buffer does not go over its limits. By doing this, buffer overflows may be avoided.
Address space randomization is a technique that can be used to randomly generate the addresses of code and data in memory. As a result, attackers will find it more challenging to take advantage of buffer overflows since they won't be aware of the precise location of the return address of the stack.
A security tool that can be used to stop buffer overflow attacks is the stack cookie. Before the return address, a little amount of data known as a stack cookie is added to the stack. The stack cookie will be overwritten in addition to the return address. As a result, buffer overflow attacks can be stopped because the stack cookie will no longer be valid.
Code writing best practises for thread safety
- Use primitives for synchronisation. Primitives for synchronisation can regulate access to shared resources. Mutexes, semaphores, and monitors are a few examples of frequently used synchronisation primitives.
- Don't let there be any race. When two or more threads access the same shared resource concurrently and the outcomes of the access rely on the sequence in which the threads access the resource, this is known as a race condition.
- Keep locks to a minimum. Because locks are costly, it's necessary to use them rarely. Locking a resource should only be done when absolutely necessary.
- Put atomic operations to use. Processes that are assured to be carried out atomically, or without interruption from other threads, are referred to as atomic operations.
- Apply RAII. Resource release when they aren't needed anymore is made possible via the RAII approach. This could aid in stopping resource leakage.
Trade-offs and performance factors
- Primitives for synchronisation may affect performance. Selecting the incorrect synchronisation primitive could result in extra overhead in your code, so it's critical to do your research.
- Performance and safety must be compromised in some way. Better safety may be offered by synchronisation primitives with more limitations, but performance may suffer as a result.
- In order to comprehend how synchronisation affects performance, it's critical to profile your code. This will assist you in selecting the appropriate synchronisation primitives and performance-tuning your code.
Real-world case studies
Here are some examples of real-world situations where mutual exclusion was used:
File systems: In order to make sure that only one thread at a time can access a file, file systems use mutual exclusion. To avoid data corruption, this is crucial.
Databases: Databases utilise mutual exclusion to guarantee that only one thread at a time can access a record. This is crucial to avoid racial tensions.
Network protocols: According to network protocols, only one thread at a time is permitted to send or receive data on a network socket. This is done through the use of mutual exclusion. To avoid data corruption, this is crucial.