8.1 System model

• 系統中存在一系列的資源(resource，例如 CPU cycle、記憶體空間、 I/O 裝置等)，分別為 R1R2…Rm
• 每一個種資源 Ri只會有 Wi個實體(instance)可以使用，也就是同時間最 多Wi個process 可以取用 Ri資源
• 每一個 process 使用資源的流程：
  • Request：要求資源，等待可用的資源被配給到該 process
  • Use：使用資源
  • Release：釋放資源以供其他 process 使用
• 一系列被 blocked 的 processes 持有部份資源且都在等待獲得其他 processes 擁有的資源
• 課本上的例子

8.2 Deadlock Characterization

先提供如何實現deadlock的方法：

/* Create and initialize the mutex locks */
pthread mutex t first mutex;
pthread mutex t second mutex;
pthread mutex init(&first mutex,NULL);
pthread mutex init(&second mutex,NULL);

/* thread one runs in this function */
void *do work one(void *param)
{
pthread mutex lock(&first mutex);
pthread mutex lock(&second mutex);
/**
* Do some work
*/
pthread mutex unlock(&second mutex);
pthread mutex unlock(&first mutex);
pthread exit(0);
}
/* thread two runs in this function */
void *do work two(void *param)
{
pthread mutex lock(&second mutex);
pthread mutex lock(&first mutex);
/**
* Do some work
*/
pthread mutex unlock(&first mutex);
pthread mutex unlock(&second mutex);
pthread exit(0);
}

• Two threads (thread_one and thread_two) are created, each trying to acquire both mutexes, but in a different order.

  • thread_one locks first_mutex first, then second_mutex.
  • thread_two locks second_mutex first, then first_mutex.

• Deadlock can occur if thread_one successfully acquires first_mutex and, at the same time, thread_two successfully acquires second_mutex.

• At this point:

  • thread_one is waiting for second_mutex (held by thread_two), and
  • thread_two is waiting for first_mutex (held by thread_one).

• 出現deadlock的充要條件：

• Mutual exclusion：某些資源在同一個時間點最多只能被一個 process 使用

• Hold and wait：某 process 持有部分資源，並等待其他 process 正在持有的資源

• No preemption：process 不可以任意強奪其他 process 所持有的資源，資源只能被持有的 process 自己放棄

• Circular waiting：系統中存在一組 processes P={P0,P1,…,Pn}，其中P0等待P1所持有的資源...Pn等待P0所持有的資源，形成循環式等待。(因此，deadlock不會存在於single process環境中)