OS202
Race Condition A race condition occurs when processes have concurrent access to shared data and the final result depends on the particular order in which concurrent accesses occur. Race conditions can result in corrupted values of shared data.
Peterson’s Solution doesn’t work on modern computer
Because of the way modern computer architectures perform basic machine-language instructions, such as load and store,
there are no guarantees that Peterson’s solution will work correctly on such architectures.
Hardware Solution to Critical-section Problem
Hardware support for the critical-section problemincludes memory barriers; hardware instructions,
such as the compare-and-swap instruction; and atomic variables.
Deadlock
A deadlock is a state in which each member of a group is waiting for another member, including itself, to take action, such as sending a message or more commonly releasing a lock.
Deadlock is a common problem in multiprocessing systems, parallel computing, and distributed systems, where software and hardware locks are used to arbitrate shared resources and implement process synchronization.
Mutual Exclusion The mutual-exclusion condition must hold. That is, at least one resource must be nonsharable. Shareable resources do not require mutually exclusive access and thus cannot be involved in a deadlock.
Hold and Wait To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a thread requests a resource, it does not hold any other resources. One protocol that we can use requires each thread to request and be allocated all its resources before it begins execution
No Preemption If a thread is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the thread must wait), then all resources the thread is currently holding are preempted. In other words, these resources are implicitly released.
Circular Wait To ensure that this condition never holds is to impose a total ordering of all resource types and to require that each thread requests resources in an increasing order of enumeration.
Safe State A state is safe if the system can allocate resources to each thread (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence.
Resource allocation graph algorithm If we have a resource-allocation system with only one instance of each resource type, we can use a variant of the resource-allocation graph for deadlock avoidance.
Banker’s algorithm When a newthread enters the system, it must declare the maximum number of instances of each resource type that it may need. When a newthread enters the system, it must declare the maximum number of instances of each resource type that it may need. If it will, the resources are allocated; otherwise, the thread must wait until some other thread releases enough resources.
Single Instance Detection Algorithm
If all resources have only a single instance, then we can define a deadlock-detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph.
We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges.
Several instance detection algorithm
The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type.
We turn now to a deadlock-detection algorithm that is applicable to such a system. The algorithmemploys several time-varying data structures that are similar to those used in the banker’s algorithm.
Process and thread termination
Resource Preemption To eliminate deadlocks using resource preemption, we successively preempt some resources fromprocesses andgive these resources to other processes until the deadlock cycle is broken.