Giáo trình Hệ điều hành - Chương 6: Deadlock - Nguyễn Phú Trường

 nguyên A có 7 thể hiện, loại tài nguyên B có 2 thể 
hiện và loại tài nguyên C có 6 thể hiện. Giả sử rằng tại thời điểm T0, chúng ta có trạng 
thái cấp phát tài nguyên sau: 
Allocation Request Available 
A B C A B C A B C 
P0 0 1 0 0 0 0 0 0 0 
P1 2 0 0 2 0 2 
P2 3 0 3 0 0 0 
P3 2 1 1 1 0 0 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 128
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
P4 0 0 2 0 0 2 
Chúng ta khẳng định rằng hệ thống không ở trong trạng thái deadlock. Thật vậy, 
nếu chúng ta thực thi giải thuật, chúng ta sẽ tìm ra thứ tự sẽ dẫn 
đến trong Finish[i] = true cho tất cả i. 
Bây giờ giả sử rằng quá trình P2 thực hiện yêu cầu thêm thể hiện loại C. Ma trận 
yêu cầu được hiệu chỉnh như sau: 
Need 
A B C 
P0 0 0 0 
P1 2 0 2 
P2 0 0 1 
P3 1 0 0 
P4 0 0 2 
Chúng ta khẳng định rằng hệ thống bây giờ bị deadlock. Mặc dù chúng ta có 
thể đòi lại tài nguyên được giữ bởi quá trình P0, số lượng tài nguyên sẳn dùng không 
đủ để hoàn thành các yêu cầu của các quá trình còn lại. Do đó, deadlock tồn tại và bao 
gồm các quá trình P1, P2, P3, P4. 
VIII.3 Sử dụng giải thuật phát hiện deadlock 
Khi nào thì chúng ta nên nạp giải thuật phát hiện deadlock? Câu trả lời phụ thuộc 
vào hai yếu tố: 
1) Deadlock có khả năng xảy ra thường xuyên như thế nào? 
2) Bao nhiêu quá trình sẽ bị ảnh hưởng bởi deadlock khi nó sẽ ra? 
Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được nạp lên 
thường xuyên. Những tài nguyên được cấp phát để các quá trình bị deadlock sẽ rảnh 
cho đến khi deadlock có thể bị phá vỡ. Ngoài ra, số lượng quá trình liên quan trong 
chu trình deadlock có thể tăng lên. 
Deadlock xảy ra chỉ khi một số quá trình thực hiện yêu cầu mà không được cấp tài 
nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối hoàn thành một chuỗi các quá trình 
đang yêu cầu. Ngoài ra, chúng ta có thể nạp giải thuật phát hiện mọi khi một yêu cầu 
cho việc cấp phát không thể được cấp tức thì. Trong trường hợp này, chúng ta không 
chỉ định nghĩa tập hợp các quá trình bị deadlock, mà còn xác định quá trình đã gây ra 
deadlock. (Trong thực tế, mỗi quá trình trong suốt quá trình bị deadlock là một liên 
kết trong chu trình của đồ thị tài nguyên, vì thế tất cả chúng gây ra deadlock). Nếu có 
nhiều loại tài nguyên khác nhau, một yêu cầu có thể gây chu trình trong đồ thị tài 
nguyên, mỗi chu trình hoàn thành bởi yêu cầu mới nhất và “được gây ra” bởi một quá 
trình có thể xác định. 
Dĩ nhiên, nạp giải thuật phát hiện deadlock cho mỗi yêu cầu có thể gây ra một 
chi phí có thể xem xét trong thời gian tính toán. Một thay đổi ít đắt hơn là nạp giải 
thuật tại thời điểm ít thường xuyên hơn- thí dụ, một lần một giờ hay bất cứ khi nào 
việc sử dụng CPU rơi xuống thấp hơn 40%. Nếu giải thuật phát hiện deadlock được 
nạp trong những thời điểm bất kỳ, thì có nhiều chu trình trong đồ thị tài nguyên. 
Chúng ta không thể nói quá trình nào của nhiều quá trình bị deadlock gây ra deadlock. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 129
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
IX Phục hồi deadlock 
Khi giải thuật phát hiện xác định rằng deadlock tồn tại, nhiều thay đổi tồn tại. 
Một khả năng là thông báo người điều hành rằng deadlock xảy ra và để người điều 
hành giải quyết deadlock bằng thủ công. Một khả năng khác là để hệ thống tự động 
phục hồi. Có hai tuỳ chọn cho việc phá vỡ deadlock. Một giải pháp đơn giản là huỷ bỏ 
một hay nhiều quá trình để phá vỡ việc tồn tại chu trình trong đồ thị cấp phát tài 
nguyên. Tuỳ chọn thứ hai là lấy lại một số tài nguyên từ một hay nhiều quá trình bị 
deadlock. 
IX.1 Kết thúc quá trình 
Để xóa deadlock bằng cách hủy bỏ quá trình, chúng ta dùng một trong hai phương 
pháp. Trong cả hai phương pháp, hệ thống lấy lại tài nguyên được cấp phát đối với 
quá trình bị kết thúc. 
• Huỷ bỏ tất cả quá trình bị deadlock: phương pháp này rõ ràng sẽ phá vỡ chu 
trình deadlock, nhưng chi phí cao; các quá trình này có thể đã tính toán trong 
thời gian dài, và các kết quả của các tính toán từng phần này phải bị bỏ đi và 
có thể phải tính lại sau đó. 
• Hủy bỏ một quá trình tại thời điểm cho đến khi chu trình deadlock bị 
xóa:phương pháp này chịu chi phí có thể xem xét vì sau khi mỗi quá trình bị 
hủy bỏ, một giải thuật phát hiện deadlock phải được nạp lên để xác định có 
quá trình nào vẫn đang bị deadlock. 
Hủy bỏ quá trình có thể không dễ. Nếu một quá trình đang ở giữa giai đoạn cập 
nhật một tập tin, kết thúc nó sẽ để tập tin đó trong trạng thái không phù hợp. Tương 
tự, nếu quá trình đang ở giữa giai đoạn in dữ liệu ra máy in, hệ thống phải khởi động 
lại trạng thái đúng trước khi in công việc tiếp theo. 
Nếu phương pháp kết thúc một phần được dùng thì với một tập hợp các quá 
trình deadlock được cho, chúng ta phải xác định quá trình nào (hay các quá trình nào) 
nên được kết thúc trong sự cố gắng để phá vỡ deadlock. Việc xác định này là một 
quyết định chính sách tương tự như các vấn đề lập thời biểu CPU. Câu hỏi về tính 
kinh tế là chúng ta nên hủy bỏ quá trình nào thì sự kết thúc của quá trình đó sẽ chịu 
chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác. Nhiều yếu 
tố có thể xác định quá trình nào được chọn bao gồm: 
1) Độ ưu tiên của quá trình là gì. 
2) Quá trình đã được tính toán bao lâu và bao lâu nữa quá trình sẽ tính toán trước 
khi hoàn thành tác vụ được chỉ định của nó. 
3) Bao nhiêu và loại tài nguyên gì quá trình đang sử dụng. 
4) Bao nhiêu tài nguyên nữa quá trình cần để hoàn thành 
5) Bao nhiêu quá trình sẽ cần được kết thúc. 
6) Quá trình là giao tiếp hay dạng bó 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 130
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
IX.2 Lấy lại tài nguyên 
Để xóa deadlock sử dụng việc trả lại tài nguyên, sau khi chúng ta đòi một số tài 
nguyên từ các quá trình và cho các tài nguyên này tới các quá trình khác cho đến khi 
chu trình deadlock bị phá vỡ. 
Nếu việc đòi lại được yêu cầu để giải quyết deadlock thì ba vấn đề cần được xác 
định: 
• Chọn nạn nhân: những tài nguyên nào và những quá trình nào bị đòi lại? 
Trong khi kết thúc quá trình, chúng ta phải xác định thứ tự đòi lại để tối 
thiểu chi phí. Các yếu tố chi phí có thể gồm các tham số như số lượng tài 
nguyên một quá trình deadlock đang giữ, và lượng thời gian một quá trình 
deadlock dùng trong sự thực thi của nó. 
• Trở lại trạng thái trước deadlock: Nếu chúng ta đòi lại tài nguyên từ một 
quá trình, điều gì nên được thực hiện với quá trình đó? Rõ ràng, nó không 
thể tiếp tục việc thực thi bình thường; nó đang bị mất một số tài nguyên 
được yêu cầu. Chúng ta phải phục hồi quá trình tới trạng thái an toàn và 
khởi động lại từ trạng thái gần nhất trước đó. 
Thông thường, rất khó để xác định trạng thái gì là an toàn vì thế giải pháp đơn 
giản nhất là phục hồi toàn bộ: hủy quá trình và sau đó khởi động lại nó. Tuy nhiên, 
hữu hiệu hơn để phục hồi quá trình chỉ đủ xa cần thiết để phá vỡ deadlock. Ngoài ra, 
phương pháp này yêu cầu hệ thống giữ nhiều thông tin hơn về trạng thái của tất cả các 
quá trình đang chạy. 
Đói tài nguyên: chúng ta đảm bảo như thế nào việc đói tài nguyên không xảy 
ra? Nghĩa là, chúng ta có thể đảm bảo rằng tài nguyên sẽ không luôn bị đòi lại từ cùng 
một quá trình. 
Trong một hệ thống việc chọn nạn nhân ở đâu dựa trên cơ sở các yếu tố chi phí, 
nó có thể xảy ra cùng quá trình luôn được chọn như là nạn nhân. Do đó, quá trình này 
không bao giờ hoàn thành tác vụ được chỉ định của nó, một trường hợp đói tài nguyên 
cần được giải quyết trong bất kỳ hệ thống thực tế. Rõ ràng, chúng ta phải đảm bảo 
một quá trình có thể được chọn như một nạn nhân chỉ một số lần xác định (nhỏ). Giải 
pháp chung nhất là bao gồm số lượng phục hồi trong yếu tố chi phí. 
X Tóm tắt 
Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định 
một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về 
nguyên tắc, có ba phương pháp giải quyết deadlock: 
• Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đảm bảo rằng 
hệ thống sẽ không bao giờ đi vào trạng thái deadlock. 
• Cho phép hệ thống đi vào trạng thái deadlock, phát hiện và sau đó phục hồi. 
• Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ 
thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều 
hành bao gồm UNIX. 
Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra 
cùng một lúc trong hệ thống: loại trừ hỗ tương, giữ và chờ cấp thêm tài nguyên, 
không đòi lại tài nguyên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn 
chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra. 
Một phương pháp để tránh deadlock mà ít nghiêm ngặt hơn giải thuật ngăn chặn 
deadlock là có thông tin trước về mỗi quá trình sẽ đang dùng tài nguyên như thế nào. 
Thí dụ, giải thuật Banker cần biết số lượng tối đa của mỗi lớp tài nguyên có thể được 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 131
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
yêu cầu bởi mỗi quá trình. Sử dụng thông tin này chúng ta có thể định nghĩa giải thuật 
tránh deadlock. 
Nếu hệ thống không thực hiện một giao thức để đảm bảo rằng deadlock sẽ 
không bao giờ xảy ra thì lược đồ phát hiện và phục hồi phải được thực hiện. Giải 
thuật phát hiện deadlock phải được nạp lên để xác định deadlock có thể xảy ra hay 
không. Nếu deadlock được phát hiện hệ thống phải phục hồi bằng cách kết thúc một 
số quá trình bị deadlock hay đòi lại tài nguyên từ một số quá trình bị deadlock. 
Trong một hệ thống mà nó chọn các nạn nhân để phụv hồi về trạng thái trước đó 
chủ yếu dựa trên cơ sở yếu tố chi phí, việc đói tài nguyên có thể xảy ra. Kết quả là quá 
trình được chọn không bao giờ hoàn thành tác vụ được chỉ định của nó. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 132