16 Deadlocks

More on Synchronization and Deadlocks Lecture 16

Introduction to Embedded Systems

Summary of Previous Lecture •

Critical sections – the atomicity requirement

•

Techniques to enforce critical sections – – – – – –

•

Solution 1: too hard-wired Solution 2: does not work! Solution 3: deadlock! Solution 4: starvation! Solution 5: Dekker’s algorithm Semaphores: good…

Implementing Semaphores – test-and-set instructions – ARM instructions

Introduction to Embedded Systems

Quote of the Day

Conceit is bragging about yourself. Confidence means you believe you can get the job done. – Johnny Unitas

Introduction to Embedded Systems

Outline of This Lecture • • •

Types of Synchronization Deadlocks Some classical synchronization problems

Introduction to Embedded Systems

Types of Synchronization •

There are 2 basic types of synchronization:

P1:: P(s1) ... V(s1)

P2:: P(s1) ... V(s1)

Mutex

P1:: P(s1) ... V(s2)

P2:: P(s2) ... V(s1)

Barrier Synchronization

Introduction to Embedded Systems

Deadlocks • •

When a program is written carelessly, it may cause a... deadlock!!! Each process will wait for the other process indefinitely – How can we deal with these abnormalities? – Avoidance, prevention, or detection and resolution

•

Which one is more efficient?

P1:: P(s1); P(s2); ... V(s2); V(s1);

P2:: P(s2); P(s1); ... V(s1); V(s2);

Introduction to Embedded Systems

Dining Philosophers •

There were some hungry philosophers, and some angry philosophers – Each needed two forks, each shared both his/her forks – Possible deadlock situation! HOW? • Is it possible to have a (literally) starvation situation?

•

What is the best solution? – Round-robin? FIFO? How good are FIFO and RR?

•

Important: what is the metric to judge a solution by? – Least overhead? Minimum starvation? – How to evaluate fairness?

Introduction to Embedded Systems

Deadlocks •

Several processes “executing” at the same time, and one is waiting (blocked) for (by) another, which in turn is waiting for another, which in turn... which in turn is waiting for the first. – No process can finish, since they are all waiting for something

•

The difference between deadlock and starvation of a process is that – In deadlock, a process must be able to acquire a resource at first, and then go into deadlock. – In starvation, the request may be deferred infinitely • the resource may be in use for an infinite amount of time

Introduction to Embedded Systems

Necessary Conditions for a Deadlock •

Formally: (these conditions must hold for deadlock to occur) • mutual exclusion: some resource is non-sharable, (eg, a printer) • hold and wait: there must exist a process holding for a resource (eg, a printer) and waiting for another resource (eg, a plotter) • no preemption: the system will not preempt the resources in contention • circular wait: there must exist a circular chain of processes. – One is holding a resource and waiting for the next process

Introduction to Embedded Systems

Deadlock Handling •

Prevention: structure the system is such a way as to avoid deadlocks (ie, in a way to avoid one of the conditions above). – This is done in the design phase: design a system and ensure that there is no deadlock in the system.

•

Avoidance: does not make deadlock impossible (as in prevention) – Instead, it rejects requests that cause deadlocks by examining the requests before granting the resources. If there will be a deadlock, reject the request.

•

Detection and Recovery: after the deadlock has been detected, break one of the 4 conditions above. The mechanisms of deadlock detection and deadlock recovery are very much tied to each other. • deadlock detection varies from a centralized to a distributed system • deadlock recovery can be optimistic or pessimistic, depending on system design (which depends on the probability of deadlock occurrence)

Introduction to Embedded Systems

Deadlock Avoidance Special Case: Banker's Algorithm • It is based on how a bank would work with several clients that borrow and invest money – It differentiates between safe (deadlock is impossible, because there are enough resources) and unsafe states (the opposite) – The OS will refuse requests for resources from processes if the request will take the system to an unsafe state. – If the system is always in a safe state, there will never be a deadlock. – When a request arrives, the Banker's algorithm checks whether there will be enough resources (money) to cover all the money to be returned to the clients in case they decide to withdraw. – Since withdrawal can only occur sequentially, the Bank does not need to have all the money in escrow.

Introduction to Embedded Systems

Banker's Algorithm If there is a process that can be satisfied with the currently available resources, that process will eventually relinquish the other resources it holds. If all the resources held by a process are sufficient to cover the needs of another process, that will be second in line, and so on: safe = T; available = #_available_res; L = list of all active processes; repeat { if there is a process P in L such that available >= #_unclaimed_res[P] then { delete P from L; available += #_held_res[P]; } else safe = F; } until (L is empty) or (safe = False)

Introduction to Embedded Systems

Deadlock Prevention •

The most usual prevention methods rely on a certain ordering on resource acquiring – e.g., a numbering scheme

•

The resources are numbered with unique identifiers and the processes request resources in increasing id (number) – Another method forces processes to acquire all resources that will be needed at once • success or failure in getting resources – Another method will force the processes to release all resources acquired (it is currently holding) whenever it blocks on the next resource request

Introduction to Embedded Systems

Graph Models for Deadlock Detection • •

•

If each resource has a single instance in a system, a graph model can directly tell you if there is a deadlock in the system. A WFG (wait-for graph) is a graph in which if a process (depicted by a node) is waiting for a resource being held by another process, there is an edge between those nodes If there is a cycle in the WFG, then there is a deadlock present – The deadlock will consist of the processes involved in the cycle – One can generalize this concept, for systems in which more than a single instance of a resource is present. – In this new model, there will be two types of nodes • processes depicted by squares • resources, depicted by circles – smaller circles inside are instances

– Resources can be of two types: • reusable or consumable Introduction to Embedded Systems

Modeling Processes/Resources •

Reusable resources: can be used over and over again – serially reusable: can only be used by one process at a time (printer) – sharable: usage can be interleaved by several processes at a time (cpu)

• •

Consumable resources: disappears after use by a process (message) Resource/process graphs are bipartite, partitioned into P and R sets, and there can be more than 1 instance of a resource (e.g., memory) – The resource graph (also called wait-for graph WFG) denotes whether there is a deadlock in the system – If there is a cycle in WFG after graph reduction, then a deadlock is present

•

If it is possible to eliminate all edges from WFG, then there is no deadlock P2

request R2

consumable

R1

assign

P1

Introduction to Embedded Systems

Graph Model • •

A graph is called completely reducible if a sequence of reductions eliminates all edges of the graph A reduction can be done as follows: – If R is a reusable resource, delete all (P,R) and (R,P) and increment the number of units of R by 1. – If R is a consumable resource, delete all (P,R) and (R,P) edges, decrement the number of units of R by number of edges (P,R) and (R,P), and if P is a producer, set the number of units of R to infty

• •

A graph is in an expedient state if all processes with unfulfilled requests are blocked. A knot is a set of nodes in the graph from which you can only get to nodes in that set. – In the case of a graph in an expedient state, a knot is a sufficient condition for deadlock.

Introduction to Embedded Systems

Producers/Consumers • •

1+ processes produce data, other 1+ processes consume data Producing means the data is put in a buffer; consuming means the data is removed from the buffer (and therefore no other process should be able to read/remove that item) – The buffer has k positions, where k = 1, 2 … k < ., or k = .

•

Problem definition: Both producers and consumers operate concurrently, but data items are consumed in the order they are produced (ie, FIFO)

•

The solutions will differ, according to the size of the buffer – If there is a single buffer (ie, k = 1), the solution is simple – For the unbounded buffer problem, the solution is less than trivial, but still simple – For the bounded buffer problem, with multiple consumers and producers, the problem is a bit more complex

Introduction to Embedded Systems

Readers / Writers •

Another classical concurrency problem, similar to producer/consumer – The difference is that the consumers do not remove the data item being “consumed”, they just read it. – Therefore, many readers can potentially access the same data item at once, since no common data structures are modified

•

The writers can only act one at a time, due to the ME (mutual exclusion) constraints; – – – –

•

What if there is a single writer and a single reader? concurrency? What if there is a single writer and multiple readers? What if there are multiple writer and multiple readers? Should readers be given preference or writers? When?

Define the problem carefully, then devise solution

Introduction to Embedded Systems

Summary of Lecture • •

Types of Synchronization Deadlocks – necessary conditions for deadlocks – dealing with deadlocks

•

Some classical synchronization problems – producer/consumer problems – reader/writer problems – the “dining philosophers” problem

Introduction to Embedded Systems