Please enable JavaScript.

Coggle requires JavaScript to display documents.

Deadlocks (Deadlock characterization (Necessary conditions (Mutual…

- - - - Mutual
  - - - At least 1 resource must be held unshareable
    - - A process must wait for at leas 1 and hold at least 1 resource
    - - Resources can't bee preempted
    - - A cycle of resource needs must be met
- - - - Safe sequence
        
        Processes ask for resources in a way they can be given
  - - - Process Pi may request resource Rj
      - Must be caimed a priori
      - cycle detection avoids
        
        claims can not be met safely
      - Only works for single resource instance
  - - - Work and finish vectors
      - init as Work = available and finis[i] = false for is
      - find i such as finish[i]==false & & needi <= work
      - Work = work + alloc; finish[i] = true
      - if finis[i] == true for all i, system is safe
    - - Can resources be granted
        
        if request <= need
        
        if request <= available
        
        Modify states
        
        a = a - r
        
        alloc = alloci + ri
        
        Needi = needi-r
    - - Available
        
        Determines how many instances are available
      - Max
        
        Max amount of resources per process
      - Allocation
        
        Matrix of allocated resources per process
      - Need
        
        Matrix of needed resources per process
- - - - Detection of cycles
        
        maintain graph
        
        Periodically check for cycles
  - - - Available
        
        vector indicates the number of available for each resource
      - Allocation
        
        Matrix of allocated resources
      - Request
        
        mtrix of current request of each process
    - - Init work = available, if allocation != 0 then finish[i] = false, else true
        
        find index such that
        
        Finish == false
        
        && requesti <= work
        
        work = work + alloci; finish[i] = true
        
        if finish == false, system is deadlocked
  - - - How often is a deadlock likely
      - how many processes are affected per deadlock
- - - - Kill all deadlocked processes
      - kill one by one until cycle is over
  - - - Selecting victim
        
        Which resources are to be preempted?
      - Rollback
        
        Rollback to before deadlock
      - Starvation
        
        Make one of the processes starve
- - - - Shared resources
        
        How are these used?
        
        Request
        
        Process asks if process is available
        
        if it is it's adquired
        
        if not it must wait
        
        Use
        
        resource is used
        
        Release
        
        resource is given back
- - - - Mutual exclusion
        
        Can't be prevented because it's needed always
      - Hold and Wait
        
        Prevent a process from having more than one resource
        
        Requests only when none are hold
        
        Resource utilization is low
      - No preemption
        
        If a process asks for a resource
        
        And it is not available
        
        all current resources are preempted
        
        This prevents wait and hold condition
        
        Checks other process
        
        If it is waiting
        
        It is preempted for the new one
      - Circular wait
        
        Increased enumeration
        
        Requests only in ascending
        
        Task of the developer
        
        Or software
        
        Witness in BSD