Introduction
Generically, a resource is something a process needs in order to proceed with its execution.
physical components of the computational system (processor, memory, I/O devices, etc.).
common data structures defined at the operating system level (PCT, communication channels, etc,) or among processes of a given application.
Resources can be:
preemptable – if they can be withdraw from the processes that hold them.
ex: processor, memory regions used by a process address space.
non-preemptable – if they can only be released by the processes that hold them.
ex: a file, a shared memory region that requires exclusive access for its manipulation.
For this topic, only non-preemptable resources are relevant.
Illustrating deadlock
P needs S to proceed, which is on possession of Q.
Q needs R to proceed, which is on possession of P.
What are the conditions for the occurrence of deadlock?
Necessary conditions for deadlock
It can be proved that when deadlock occurs 4 conditions are necessarily observed:
It can be proved that when deadlock occurs 4 conditions are necessarily observed:
mutual exclusion – only one process may use a resource at a time.
if another process requests it, it must wait until it is released.
hold and wait – A process waits for some resources while holding others at the same time.
no preemption – resources are non-preemptable.
only the process holding a resource can release it, after completing its task.
circular wait – a set of waiting processes must exist such that each one is waiting for resources held by other processes in the set.
there are loops in the graph.
IIlustrating with the philosopher dinner problem
5 philosophers are seated around a table, with food in from of them. To eat, every philosopher needs two forks, the ones at her/his left and right sides. Every philosopher alternates periods in which she/he medidates with periods in which she/he eats.
Modelling every philosopher as a different process or thread and the forks as resources, design a solution for the problem.
Last updated