Seri tổng hợp_Chương 5 : Dead lock

Tóm tắt nội dung bài học hôm nay
-Vấn đề DeadLock : dead lock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn ở trạng thái waiting mãi mãi .
-Mô hình hệ thống : trong một hệ thống , các tiến trình từ khi được gọi đến khi kết thúc sẽ qua các giai đoạn sau :
+Yêu cầu tài nguyên (request): nếu yêu cầu không được giải quyết ngay (vd khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
+Sử dụng tài nguyên (use)
+Giải phóng tài nguyên (release)

-Mô tả deadlock : Dead lock xảy ra với 4 điều kiện sau xảy ra đồng thời :
+ Ngăn chặn(loại trừ) lẫn nhau : vì chỉ có 1 tiến trình đc ở trong găng
+ Giữ và đợi (Hold and wait)
+ Không có ưu tiên(độc quyền)(No preemption): tiến trình thực hiện mãi mà ko dừng để giải phóng tài nguyên cho tiến trình khác
+ Chờ đợi vòng tròn(Circular Wait)
Chú ý : trong biểu đồ phân phối tài nguyên RAG (Resource Allocation Graph )
_______Nếu đồ thị không chu trình ko xảy ra deadlock.
_______Nếu đồ thị có chu trình
__________Nếu mỗi loại tài nguyên chỉ một cá thể thì chắc chắn xảy ra deadlock.
__________Nếu mỗi loại tài nguyên có một vài cá thể thì deadlock có thể xảy ra hoặc không.





-Các phương pháp xử lý deadlock : có 3 cách
+ Ngăn ngừa hoặc tránh xa, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.(sẽ nói rõ ở bài học sau)
We can use a protocol to prevent or avoid d.eadlocks, ensuring that the system will never enter a deadlock state.
+ Cho phép hệ thống đi vào trạng thái deadlock rồi khôi phục lại.(sẽ nói rõ ở bài học sau)
We can allow the system to enter a deadlock state, detect it, and recover.
_______Hủy bỏ tất cả các tiến trình bị deadlock
_______Hủy bỏ một tiến trình tại một thời điểm đến khi chu trình deadlock được loại trừ (có thể _______hủy bỏ theo mức ưu tiên , thời gian tiến trình thực hiện , tài nguyên sử dụng....)
+ Bỏ qua dead lock , coi như ko có dead trong hệ thống
We can ignore the problem altogether and pretend that deadlocks never
occur in the system.


- Trạng thái an toàn ( safe state) : mình đưa nguyên văn cả đoạn cho nó chính xác , chứ khó diễn đạt bằng tiếng việt lắm :
"A safe state is not a deadlocked state. Conversely, a deadlocked state
an unsafe state. Not all unsafe states are deadlocks, however (Figure 7
An unsafe state Jlwy lead to a deadlock. As long as the state is safe,
operating system can avoid unsafe (and deadlocked) states. In an unsafe sta
the operating system cannot prevent processes fronT requesting resources su
that a deadlock occurs: The behavior of the processes controls unsafe states
To illustrate, we consider a system with 12 magnetic tape drives and th
processes: Po, PI, and P2 . Process Po requires 10 tape drives, process PI m
need as many as 4 tape drives, and process P2 may need up to 9 tape driv
Suppose that, at time to, process Po is holding 5 tape drives, process P
holding 2 tape drives, and process P2 is holding 2 tape drives. (Thus, there
3 free tape drives.
___Maximum Needs___Current Needs
P1___10________________5
P2___4_________________2
P3___9_________________2

At time to, the system is in a safe state. The sequence < PI, Po, P2 > satisfies
the safety condition. Process PI can inu11cdiatcly be allocated all its tape drives
and then return them (the system will then have 5 available tape drives); then
process Po can get all its tape drives and return them (the system will then have
10 available tape drives); and finally process P2 can get all its tape drives and
return thenl (the system will then have all 12 tape drives available).
A system can go from a safe state to an unsafe state. Suppose th.at, at time
h, process P2 requests and is allocated one more tape drive. The system is no
longer in a safe state. At this point, only process Pj can be al10cated all its tape
drives. When it returns them, the system will have only 4 available tape drives.
Since process Po is allocated 5 tape drives but has a maximum of 10, it may
request 5 more tape drives. Since they are unavailable, process Po must wait.
Similarly, process P2 may request an additional 6 tape drives and have to wait,
resulting in a deadlock. Our mistake was in granting the request from process
P2 for one more tape drive. If we had made P2 wait until either of the other
processes had finished and released its resources, then we could have av6ided
the deadlock.
Given the concept of a safe state, \ve can define avoidance algorithms that
ensure that the system"will never deadlock. The idea is simply to ensure that the
system vvill ahvays remain in a safe state. Initially! the system is in a safe state.
Whenever a process requests a resource that is currently available, the system
must decide whether the resource can be allocated immediately or whether
the process must wait. The request is granted only if the allocat{on leaves the
system in a safe state.
In this scheme, if a process requests a resource that is currently available!
it may still have to wait. Thus! resource utilization may be lower than it would
otherwise be.
Nói tóm lại :
-Một hệ thống ở trong trạng thái an toàn chỉ nếu ở đó tồn tại một thứ tự an toàn.
-Một trạng thái an toàn không là trạng thái deadlock
-Trạng thái deadlock là trạng thái không an toàn. Tuy nhiên, không phải tất cả trạng thái không an toàn là deadlock
---------------------------------------


Nội dung bài sau sẽ nói rõ về các thuật toán để xác định các dead lock và các thuật toán để giải quyết dead lock và safety state :
+ Thuật toán RAG (Resource-Allocation-Graph Algorithm)
+ Thuật toán Banker (Banker's Algorithm) // của thầy dịch là thuật toán nhà băng...tớ thì chịu
+ Thuật toán Safety (Safety Algorithm)
+ Thuật toán yêu cầu tài nguyên (Resource-Request Algorithm)
+ thuật toán xác định dead lock (Deadlock Detection)
.....

Ở phần bài trước ,chúng ta đã mô tả 1 hệ thống deadlock , các điều kiện xảy ra deadlock (4 đk đồng thời) , quá trình hệ thống xử lý khi xảy ra deadlock , khái niệm thế nào là 1 hệ thống an toàn

Ở phần bài này , chúng ra sẽ đi tìm hiểu các giải thuật ngăn chặn deadlock , giữ cho hệ thống luôn trong trạng thái an toàn

<III> Ngăn chặn deadlock
là đảm bảo ít nhất một trong bốn điều kiện không thể xuất hiện
a.Ngăn cản lẫn nhau – đảm bảo là hệ thống không có các file không thể chia sẻ.
Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ
Ví dụ: read-only files(vì file read only thì nhiều tiến trình truy xuất nó cũng không ảnh hưởng gì-nội dung file không thay đổi)
Một số tài nguyên là không thể chia sẻ
Ví dụ: chế độ toàn màn hình
b.Giữ và đợi cấp thêm tài nguyên – phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác.
Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi không có tài nguyên nào cả.
c.Không có ưu tiên_không đòi lại tài nguyên từ tiến trình đang giữ chúng_
Nếu một tiến trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng.
Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi.
Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.
d.Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên
Mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ
Muốn có tài nguyên j, tiến trình phải giải phóng tất cả các tài nguyên có trọng số i > j (nếu có)

<IV> Tránh deadlock
Phần này sẽ trình bày các nội dung :
-Một số thông tin ưu tiên
-Giải thuật đồ thị cấp phát tài nguyên
-Giải thuật Banker
____Giải thuật an toàn
____Giải thuật yêu cầu tài nguyên

4.1.Một số thông tin ưu tiên trong hệ thống :
-Mô hình hữu dụng nhất và đơn giản nhất yêu cầu mỗi tiến trình công bố số lượng tài nguyên lớn nhất của mỗi loại mà nó có thể cần đến.
-Giải thuật tránh deadlock luôn kiểm tra trạng thái phân phối tài nguyên để đảm bảo rằng sẽ không bao giờ có tình trạng chờ đợi vòng tròn.
-Trạng thái phân phối tài nguyên được xác định bởi số tài nguyên khả dụng (Available) và đã được phân phối (Allocation) cũng như số tài nguyên tối đa (max)tiến trình yêu cầu.

4.2.Giải thuật đồ thị cấp phát tài nguyên (đc dùng với tài nguyên đơn cá thể)
- Ngoài các cạnh yêu cầu và gán, chúng ta giới thiệu một loại cạnh mới được gọi là
cạnh thỉnh cầu (claim edge). Một cạnh thỉnh cầu Pi → Rj hiển thị quá trình Pi có thể yêu cầu tài nguyên Rj vào một thời điểm trong tương lai. Cạnh này tương tự cạnh yêu cầu về
phương hướng nhưng được hiện diện bởi dấu đứt khoảng. Khi quá trình Pi yêu cầu tài
nguyên Rj, cạnh thỉnh cầu Pi → Rj chuyển tới cạnh yêu cầu. Tương tự, khi một tài
nguyên Rj được giải phóng bởi Pi, cạnh gán Rj → Pi được chuyển trở lại thành cạnh
thỉnh cầu Pi → Rj. Chúng ta chú ý rằng các tài nguyên phải được yêu cầu trước trong hệ
thống. Nghĩa là, trước khi Pi bắt đầu thực thi, tất cả các cạnh thỉnh cầu của nó phải xuất
hiện trong đồ thị cấp phát tài nguyên. Chúng ta có thể giảm nhẹ điều kiện này bằng cách
cho phép một cạnh Pi → Rj để được thêm tới đồ thị chỉ nếu tất cả các cạnh gắn liền với
quá trình Pi là các cạnh thỉnh cầu. Giả sử rằng Pi yêu cầu tài nguyên Rj. Yêu cầu có thể được gán chỉ nếu chuyển cạnh yêu cầu Pi → Rj tới cạnh gán Rj→Pi không dẫn đến việc hình thành chu trình trong đồ thị cấp phát tài nguyên. Chú ý rằng chúng ta kiểm tra tính an toàn bằng cách dùng giải
thuật phát hiện chu trình. Một giải thuật để phát hiện một chu trình trong đồ thị này yêu
cầu một thứ tự của n2 thao tác, ở đây n là số quá trình trong hệ thống.
Nếu không có chu trình tồn tại, thì việc cấp phát tài nguyên sẽ để lại hệ thống
trong trạng thái an toàn. Nếu chu trình được tìm thấy thì việc cấp phát sẽ đặt hệ thống
trong trạng thái không an toàn. Do đó, quá trình Pi sẽ phải chờ yêu cầu của nó được thoả.

hot hot