Resource Allocation Graph (RAG)

Resource allocation graph (RAG) là đồ thị có hướng, thường được sử dụng để phát hiện deadlock.

RAG bao gồm tập đỉnh $V$ và tập cạnh $E$:

• Tập đỉnh gồm hai loại:
  1. Process: $P=\{P_1,P_2,\dots ,P_N\}$ (tất cả tiến trình trong hệ thống)
  2. Resource type: $R=\{R_1,R_2,\dots ,R_M\}$ (tất cả các loại tài nguyên trong hệ thống, mỗi loại tài nguyên có thể có nhiều thực thể).
• Tập cạnh gồm hai loại:
  1. Request edge: cạnh có hướng từ tiến trình đến tài nguyên cho biết tiến trình đó đang cần tài nguyên.
  2. Assignment edge: cạnh có hướng từ tài nguyên đến tiến trình cho biết tài nguyên đang bị giữ bởi tiến trình.

Ví dụ minh họa:

Important

• Nếu RAG không có chu trình lặp thì không có deadlock.
• Trường hợp RAG chứa một hoặc nhiều chu trình lặp và mỗi loại tài nguyên chỉ có một thực thể thì sẽ có deadlock.

Ví dụ bên dưới có chu trình lặp nhưng do mỗi loại tài nguyên có nhiều thực thể nên sẽ không xảy ra deadlock.

Cụ thể hơn, P4 ở trong hình trên do có đủ tài nguyên nên sẽ thực thi và trả lại tài nguyên (R2).

Related

• Operating System
• Deadlock

Resources

• Slide deadlock của đại học Bách Khoa.
• Deadlock in Operating System: What is, Circular Wait (Examples) (guru99.com)