본문 바로가기
강의/Operating Systems

7. Deadlock

by 사향낭 2022. 11. 13.
  • The deadlock problem:
    • Systems usually have multiple locks
    • Threads often need to hold multiple locks at the same time.
    • Deadlock definition:
      • A collection of threads are all blocked.
      • Each thread is waiting for a resource owned by one of the other threads.
      • Since all therads are blocked, none can release their resources.
    • Simple examples:
Thread A Thread B
lock_acquire(l1); lock_acquire(l2);
lock_acquire(l2); lock_acquire(l1);
... ...
lock_release(l2); lock_release(l1);
lock_release(l1); lock_release(l2);
  • Four conditions for deadlocks:
    • Limited access: resources cannot be shared.
    • No preemption. Once given, a resource cannot be taken away.
    • Multiple independent requests: threads don't ask for resources all at once (hold resources while waiting).
    • A circularity in the graph of requests and ownership.
  • Complexities:
    • Deadlock can occur over anything that causes waiting:
      • Locks
      • Network messages
      • Disk drive
      • Memory space exhausted
    • Deadlock can occur over discrete resources (e.g. locks) or quantities of a more continuous resource (pages of memory).
    • In general, don't know in advance which resources a thread will need.
  • Solution #1: deadlock detection
    • Determine when system is deadlocked
    • Break the deadlock by termnating one of the threads
    • Usually not practical in operating systems, but often used in database systems where transactions can be aborted and retried
  • Solution #2: deadlock prevention: eliminate one of the necessary conditions for deadlock
    • Don't allow exclusive access? Not reasonable for most applications.
    • Create enough resourcees so that they never run out? May work for things like disk space, but locks for synchronization are intentionally limited in number.
    • Allow preemption? Works for some resources but not others (e.g., can't preempt a lock)/
    • Require threads to request all resources at the same time; either get them all or wait for them all.
      • Tricky to implement: must wait for several things without locking any of them.
      • Inconvenient for thread: hard to predict needs in advance. May require thread to over-allocate just to be safe.
    • Prevent circularities: all threads request resources in the same order (e.g., always lock l1 before l2). This is the most common approach used in operating systems.

 

Summary

  • Deadlock 문제는 thread들이 lock을 가지고 있으면서 다른 thread가 가지고 있는 lock을 획득하려 할 때 서로 자신이 들고 있는 lock을 놓아주지 않아 발생하는 문제다.
  • Deadlock의 네 가지 조건: 자원이 공유되지 않음, 우선권이 없음, 한 번에 모든 자원을 요청하는 것이 아닌 독립적으로 여러 번 자원을 요청한다, 자원의 요청과 소유 graph가 cycle 형태를 이룬다.
  • Lock 뿐만아니라 network messages, disk drive, memory 등을 기다릴 때 발생할 수 있다.
  • Solution #1: deadlock detection을 통해 원인 중 한 thread를 종료시킨다.
  • Solution #2: deadlock의 네 가지 조건을 공략한다. 모든 thread가 같은 순서로 자원을 요청하도록 만드는 방법이 OS에서 가장 흔하게 쓰이는 접근이다. (이를 통해 cycle을 없앤다.)

'강의 > Operating Systems' 카테고리의 다른 글

8. Linkers and Dynamic Linking  (1) 2022.11.14
6. Implementing Locks  (0) 2022.11.13
5. Scheduling  (0) 2022.11.13
4. Locks and Condition Variables  (0) 2022.11.12
3. Concurrency  (0) 2022.11.12

댓글