what is deadlock?Explain deadlock characterizations and Resource Allocation graph.

Deadlock:

 When  a  process is     waiting    for   some resources  but   these  resources     already   held by   other   waiting   processes . This situation is called a deadlock.
System Models:
A   system    consists   of   a   finite    number    of    resources   to    be    distributed   among    a number   of   competing   processes.The   resources   may  be   partitioned   in   to    several
types   ,    each   consisting  of  some   number   of    identical    instances.
Files   ,input/  output   devices ,memory  space   and   CPU  cycles   are  some  resource types.
Deadlocks   may  also   involve  different   resource   types . For  example  ,  consider  a  system  with  one   printer   and one  DVD  drive . Suppose  that   process   Px   is  holding    the   DVD   and   process   Py   is   holding   the    printer  .  If   Px   requests   the    printer    and    Py  requests   the   DVD   drive  ,  a   deadlock   occurs.
A   process    must   request  a   resource   before   using  it  and   must   release   the   resource after   using   it. A   process  may   requests   many    resources  as   it    requires    to    carry    out its   designated    task.
Each  resource  type   Rn  may  have   Nn  instances.
 Each   process    may    utilize   a   resource   as  follow:"
 . Request:
 The   process   requests   the    resource  , if    the   request    cannot    be granted  immediately (For  example  ,    if    the  resource   is   being   used   by   another    process), then   the   requesting    process    must    wait   until   it    can    acquire   the resource.
 . Use:
The   process   can   operate   on   the  resource  (  For   example  ,    if    the   resource    is    a printer  ,   the    process     can    print   on   the   printer) .
. Release.After  the  actions  the   process   releases   the   resource.

                               Deadlock  characterization

Some necessary  Conditions  of  deadlock:
 A  deadlock   situation    can   arise  if   the   following   four   conditions   holds    simultaneously in   a   system.
1.  Mutual   exclusion.
Only  one process   at  a time   can use  a resource.
 At   least    one    resource    must    be    held   in   a   non   share able   mode   that  is  , only  one    process   at   a    time    can    use    the     resource .  If    another    process    requests   that resource ,   the   requesting    process    must    be    delayed   until   the    resource    has   been  released.
2. Hold and wait. 
A   process   must   be    holding  at  least   one   resource    and   waiting   to    acquire   additional    resources    that    are   currently   being    held   by   other    processes.
3.No  preemption:
Resources can not be preempted  ,a resource  is not released, untill  that process  has completed its task.
4. Circular  Wait:
A   set    {P0 , P1, ..., Pn}  of waiting processes must exist such that P0 is waiting for a
 resource   held by P1, P1 is waiting for a resource heldby P2,..., Pn−1 is waiting for a  resource    holding  by   Pn a    pn is waiting for  a resource   held  by  p0.



Resource-Allocation Graph:
Deadlocks   can  be described   more  precisely   in  terms  of   directed  graph  called  system  resource   allocation    graph. Graph  consists  of  set  of  vertices  V  and  set   of  edges E.
The   set  of   vertices   V  is  partitioned   in  to  two  different   types   of  nodes  : P  =  {
P1  ,   P2  .., Pn} the set consisting of  all  the  active    processes in  the  system  and  R = { R1, R2, ..., Rm},   the set consisting of  all  resource type in the  system.

                                                       

                                                                     Figure (a)

A  directed  edge  from process  Pi  to  resource  type  Rj  is  denoted  by   Pi → Rj;
it signifies that process Pi has requested an  instance  of   resource  type  Rj  and
is  currently  waiting  for that resource . A directed  edge from resource type Rj to
process Pi is denoted by Rj → Pi ; it signifies that an instance of resource type Rj has
been allocated to process Pi.
A directed edge  Pi → Rj  is called a request edge;
A directed edge Rj → Pi is called an assignment edge.
When  process  Pi requests  an   instance   of   resource  type  Rj ,  a  request  edge  is
 inserted  in  the  resource  allocation  graph .When  this request  can  be  fulfilled
the  requested  edge  is instantaneously  transformed  to  an  assignment  edge . When  the  process  no longer
needs  access  to  the   resource ,  it  releases  the  resource .As  a   result ,the  assignment  edge  is    deleted.
The resource allocation  graph  shown  in   Figure (a) depicts  the  following situation.
 • The sets P, R and E:
  P ={P1, P2, P3}
 ◦ R ={R1, R2, R3, R4}
 ◦ E ={P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
 • Resource instances:
 ◦ One  instance  of  resource  type  R1.
 ◦ Two  instances  of  resource type  R2.
 ◦ One instance of resource type   R3.
 ◦ Three  instances  of resource type   R4.
 • Process states: 
 ◦ Process  P1  is  holding  an  instance of  resource type  R2  and is  waiting  for  an  instance  of  resource  type  R1 .
 ◦ Process  P2  is  holding  an  instance  of  R1  and   an  instance   of   R2  and  is   waiting  for   an  instance  of  R3 .
 ◦ Process  P3  is  holding  an  instance  of  R3 .


                                         Resource Allocation Graph with deadlock

                                      

.At  this  point , two  minimal cycles exist  in  the  system :
 P1 → R1 → P2 → R3 → P3 → R2 → P1
 P2 → R3 → P3 → R2 → P2
 Processes P1 ,P2 , and P3 are  dead locked . Process P2 is waiting  for the  resource  R3 ,which  is  held  by  process  P3 .
 Process  P3  is  waiting  for  either  process  P1  or  process  P2  to release  resource  R2 .
 In addition , process P1  is  waiting  for  process  P2  to  release  resource  R1 .