Khái niệm đồ thị cấp phát tài nguyên. Biết cách vẽ và cách giải thích một đồ thị cho trước

Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E. + Tập nút V gồm 2 loại: P ={P1, P2, ..., Pn} tập hợp các tiến trình đang vận hành trong hệ thống. R ={R1, R2, ..., Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều phiên bản. VD: máy in có 3 phiên bản, ... +Tập cung E bao gồm: Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj. Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp phát cho Pi. Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình. o Không có chu trình: không tồn tại Deadlock o Có chu trình: có hoặc không có Deadlock .Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản. .Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.