Scribd Logo
Upload

Welcome to Scribd!

  • 0 views

    2d752d_Dead Lock 15

    Uploaded by

    Daud Khan

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    2d752d_Dead Lock 15

    Uploaded by

    Daud Khan
    0 views9 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    0 views9 pages

    2d752d_Dead Lock 15

    Uploaded by

    Daud Khan

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 9

    Graph Theory

    Outline for today’s Lecture

    What is Deadlock in Operating System


    (OS)?
    Deadlock in Graph theory

    Every process needs some resources to complete its execution.


    However, the resource is granted in a sequential order.

    1.The process requests for some resource.


    2.OS grant the resource if it is available otherwise let the
    process waits.
    3.The process uses it and release on the completion.
    Dead Lock?

    A Deadlock is a situation where each of the computer process


    waits for a resource which is being assigned to some another
    process.

    In this situation, none of the process gets executed since the


    resource it needs, is held by some other process which is also
    waiting for some other resource to be released.
    Dead Lock?

    Let us assume that there are three processes P1, P2 and P3. There
    are three different resources R1, R2 and R3. R1 is assigned to P1, R2
    is assigned to P2 and R3 is assigned to P3.
    After some time, P1 demands for R2 which is being used by P2. P1
    halts its execution since it can't complete without R2. P2 also
    demands for R3 which is being used by P3. P2 also stops its
    execution because it can't continue without R3. P3 also demands for
    R1 which is being used by P1 therefore P3 also stops its execution.
    In this scenario, a cycle is being formed among the three
    processes. None of the process is progressing and they are all
    waiting.

    The computer becomes unresponsive since all the processes


    got blocked.
    Necessary conditions for Deadlocks

    1. Mutual Exclusion
    A resource can only be shared in mutually exclusive manner. It
    implies, if two process cannot use the same resource at the same
    time.
    2. Hold and Wait
    A process waits for some resources while holding another resource
    at the same time.
    3. No preemption
    The process which once scheduled will be executed till the
    completion. No other process can be scheduled by the scheduler
    meanwhile.
    4. Circular Wait
    All the processes must be waiting for the resources in a cyclic
    manner so that the last process is waiting for the resource which is
    Resource Allocation Graph

    In a Resource Allocation Graph where all the


    resources are single instance, If a cycle is being
    formed, then system is in a deadlock state.
    If no cycle is being formed, then system is not in a
    deadlock state.

    • Assign Edge (shown in 1) 2

    • Request Edge (shown in 2)

    1
    Resource Vertex

    • Single Instance
    CPU, Monitor etc.

    • Multi Instance
    Register, Printer

    You might also like