Tao's Blog
0%

[UCSD CSE120]死锁-deadlock

Posted on Edited on In Comment Counts:
2k 2 mins.

本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记，这一课主要介绍了操作系统里面死锁概念包括出现的原因，以及避免（防止出现）以及解决办法（出现死锁时最好的方法是重启大法！！）

Basic

  1. Definition

    • Set of processes are permanently blocked
      • Unblocking of one relies on progress of another, but none can make progress

    • Example

      • Process A holding resource X, waiting for resource Y
      • Process B holding Y, waiting for X

      • these two process will not be able to make any progress

    • Another example: memory

      • Total memory = 200MB
      • P1 holds 80MB, requests 60MB
      • P2 holds 70MB, requests 80MB

  2. Four conditions for Deadlock

    • Mutual Exclusion
      • Only one process may use a resouce at a time
    • Hold-and-Wait
      • Process holds resouce while waiting for another
    • No Preemption
      • Can’t take a resource away from a process
    • Circular Wait
      • The waiting process form a cycle

  3. Attack the Deadlock Problem

    • Deadlock prevention
      • Make deadlock impossible by removing one (or more)condition
    • Deadlock Avoidance
      • Avoid getting into situations that lead to deadlock
    • Deadlock Detection
      • Don’t try to stop deadlocks
      • If they happen, detect and resolve

Attck the deadlock

  1. Deadlock prevention

    • Mutual exclusion -> relax where sharing is possible
    • Hold-and-Wait -> Get all resources simultaneously (wait until all free)
    • No preemption -> allow resources to be taken away
    • Circular wait -> order all the resources, force ordered acquisition

  2. Deadlock Avoidance

    • Avoid getting into situations that lead to deadlock
      • Selective prevention
      • Remove condition only when deadlock is possible
    • Works with incremental resource requests
      • Resources are asked for in increments
      • Do not grant request than can lead to a deadlock
    • Need maximum resource requirements

    • Banker’s Algorithm

      • Fixed number of processes and resources
      • System state: either safe or unsafe
        • Depends on allocation of resources to processes
      • Safe: deadlock is absolutely avoidable
        • Can avoid deadlock by certain order of execution
      • Unsafe: deadlock is possible(but not certain)
        • May not be able to avoid deadlock

      • Diagram

  3. Deadlock Detection (mostly used!)

    • Method

      • Periodically try to detect if a deadlock occurred
      • Do something (or nothing) about it

    • Resoning

      • Deadlocks rarely happen
      • Cost of prevention or avoidance not worth it
      • Deal with them in special way (may costly)

    • Recovery from deadlock

      • Terminate all deadlocked process (reboot)
    • Terminate deadlocked processed one at a time
      • need to detect