Thảo luận Bài 8

Trong một nhà xe có một xe máy, một chìa khóa, một mũ bảo hiểm.Nếu một người muốn đi xe thì cần phải có đủ 3 tài nguyên trên(xe, chìa khóa, mũ bảo hiểm).Có 3 người(3 tiến trình) đều có nhu cầu đi xe.Người thứ nhất giành chìa khóa, người thứ hai giành xe máy, người thứ ba giành mũ bảo hiểm.Như vậy tất cả các tài nguyên đều đã bị chiếm dụng mà không một tiến trình nào hoàn tất công việc vì người thứ nhất chờ tài nguyên xe và mủ bảo hiểm, người thứ hai chờ tài nguyên chìa khóa và mũ bảo hiểm, người thứ ba chờ tài nguyên chìa khóa và xe.kết quả là các tiến trình rơi vào trạng thái deadlock.

Xét một hệ thống với 5 quá trình từ P0 tới P4, và 3 loại tài nguyên A, B, C. Loại tài nguyên A có 10 thể hiện, loại tài nguyên B có 5 thể hiện và loại tài nguyên C có 7 thể hiện. Giả sử rằng tại thời điểm T0 trạng thái hiện tại của hệ thống như sau:

	Allocation			Max       .			Available
	A	B	C	A	B	C	A	B	C
P0	0	1	0	7	5	3	3	3	2
P1	2	0	0	3	2	2
P2	3	0	2	9	0	2
P3	2	1	1	2	2	2
P4	0	2	2	4	3	3

Nội dung ma trận Need được định nghĩa là Max-Allocation là:

	Need   .
A	B	C
P0	7	4	3
P1	1	2	2
P2	6	0	2
P4	4	3	1

Chúng ta khẳng định rằng hệ thống hiện ở trong trạng thái an toàn. Thật vậy, thứ tự thỏa tiêu chuẩn an toàn. Giả sử bây giờ P1 yêu cầu thêm một thể hiện loại A và hai thể hiện loại C, vì thế Request1 = (1, 0, 2). Để quyết định yêu cầu này có thể được cấp tức thì hay không, trước tiên chúng ta phải kiểm tra Request1  Available (nghĩa là, (1, 0, 2))  (3, 3, 2)) là đúng hay không. Sau đó, chúng ta giả sử yêu cầu này đạt được và chúng ta đi đến trạng thái mới sau:

	Allocation			Max       .			Available
	A	B	C	A	B	C	A	B	C
P0	0	1	0	7	4	2	2	3	0
P1	3	0	2	0	2	0
P2	3	0	2	6	0	0
P3	2	1	1	0	1	1
P4	0	0	2	4	3	1

Chúng ta phải xác định trạng thái mới này là an toàn hay không. Để thực hiện điều này, chúng ta thực thi giải thuật an toàn của chúng ta và tìm thứ tự thỏa yêu cầu an toàn. Do đó, chúng ta có thể cấp lập tức yêu cầu của quá trình P1.

Tuy nhiên, chúng ta cũng thấy rằng, khi hệ thống ở trong trạng thái này, một yêu cầu (3, 3, 0) bởi P4 không thể được gán vì các tài nguyên là không sẳn dùng. Một yêu cầu cho (0, 2, 0) bởi P0 không thể được cấp mặc dù tài nguyên là sẳn dùng vì trạng thái kết quả là không an toàn.

- Coi như không có vấn đề Deadlock.
- Dựa trên cơ sở: Deadlock rất ít xảy ra, chi phí giải quyết rất cao.
- Được dùng trên các hệ điều hành: UNIX và Windows.

" />
- Thứ nhất: Đúng là nếu khi tài nguyên trên chu trình chỉ có 1 phiên bản thì có Deadlock
- Thứ hai: Câu hỏi đặt ra: "khi tài nguyên R2 chỉ có một phiên bản thì có xảy ra Deadlock không? "
Thì theo mình thì sẽ không có Deadlock. Theo như trong Slide của Thầy thì “Có thể không có Deadlock khi 1 tài nguyên thuộc chu trình có nhiều phiên bản”. Loại tài nguyên R1 có 2 phiên bản: 1 phiên bản thuộc một chu trình, còn phiên bản kia được cấp tới tiến trình P2.

  Còn đây là theo cách hiểu của mình:
Mình giả sử như loại tài nguyên R2 chỉ có 1 phiên bản. Khi đó chúng ta sẽ nhìn ra có một chu trình từ P1->R1->P3->R2->P1. Nhưng vì tiến trình P2 có thể trả lại phiên bản của loại tài nguyên R1 và tài nguyên đó có thể được cấp cho tiến trình P1 đang có nhu cầu thì khi đó sẽ không còn chu trình nữa dẫn tới không có Deadlock.
Vậy thì theo bạn thì có Deadlock hay không có Deadlock? Bạn nào giải thích giúp mình trường hợp này với, để có gì mình hoc hỏi thêm...

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.

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ả.

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.

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ả.

Các phương pháp xử lý Deadlock

+ 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.

+ Cho phép hệ thống đi vào trạng thái deadlock rồi khôi phục lại.

+ Bỏ qua dead lock , coi như ko có dead trong hệ thống

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

• dạng precinptive (process đang thực thi tam ngừng chuyển sang trạng thái sắn sàng)
• coi  thời gian thực thi còn lại của process nào còn lại ít nhất thì cho process đó thực thi



( Mới đầu p1 thực thi tới 2 thì p2 vào do p1 còn 1 đơn vị thời gian p2 còn 6 đơn vị thời gain nên p1 tiếp tục thực thi
P2 thực thi thới 4 thì p3 vào do p2 còn 5 đơn vị thời gian mà p3 co 4 đơn vị thời gian nên p3 được thực thi
P3 thực thi tới 6 p4 vào do p4 còn 5 đơn vị thời gian nên p3 thực thi hết công việc của mình
Khi p3 thực thi xong thì p5 lại vào đòi thực thi do p5 co 2 đơn vị thời gian ma p4 còn lại 5 đơn vị thời gian nên p5 được thực thi
Khi p5 thực thi xong bây giời còn p4 và p2 đều còn 5 đơn vị thời gian
Như p2 được ưu tiên hơn vì là 2 mà nên p2 được thực thi sau đó p4  thực thi )

DEADLOCK

P=(5,3,2,2) ( tổng các theo hàng cột vd như 3+0+1+1=5)

E=(6,3,4,2) (là tổng của p+A)
A=(1,0,2,0)
Hãy nhìn bên bảng R coi hàng nào có các phần từ nhỏ hơn A chỉ có R4 (nghĩa là D) nhỏ hơn
R4 được thực thi
A=A+C4=(1,0,2,0)+(1,1,0,1)=(2,1,2,1)
Ta tiếp tục nhìn bên bảng R thấy R1 (nghĩa là hàng A) nhỏ nhỏ hơn A  
R1 được thực thi
A=A+C1=(2,1,2,1)+(3,0,1,1)=(5,1,3,2)
Ta tiếp tục nhìn bên bảng R thấy R2 (nghĩa là hàng B) nhỏ nhỏ hơn A  
R2 được thực thi
A=A+C2=(5,1,3,2)+(0,1,0,0)=(5,2,3,2)
Ta tiếp tục nhìn bên bảng R thấy R3 (nghĩa là hàng C) nhỏ nhỏ hơn A  
R3 được thực thi
A=A+C3=(5,2,3,2)+(1,1,1,0)=(6,3,4,2)
Ta tiếp tục nhìn bên bảng R thấy R5 (nghĩa là hàng D) nhỏ nhỏ hơn A  
R5 được thực thi
A=A+C5=(5,2,3,2)+(0,0,0,0)=(6,3,4,2)
Cuối cùng A phải bằng E
Kết luận
Tồn tại 1 trình tự điều khiển đễ các process thực thi hoàn tất
p4-p1-p2-p3-p5

Sao mình thấy cái này giống cái phương pháp lớp học vậy ta?
deadlock

Định nghĩa: Là tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.
Ví dụ: Tại ngã 4, 4 xe tại 4 hướng khác nhau cùng đến giao lộ, không xe nào chịu nhường đường cho xe nào nên tất cả đều phải chờ đến khi có đường trống để đi => kết quả là kẹt xe. Như thế tất cả 4 xe đều trong trạng thái chờ hay nói cách khác các tiến trình đang chờ tài nguyên của nhau và cứ xoay vòng và như thế tất cả tiến trình đều kẹt(deadlock).
Deadlock là một vấn đề quan trọng không những lĩnh vực công nghệ(chương trinh vận hành) mà còn ảnh hưởng đến các lĩnh vực khác trong đời sống(như là giao thông).
+ Công nghệ: nếu 1 chương trình đang vận hành một hệ thống gì đó quan trọng phức tạp và nguy hiểm thì tuy deadlock rất hiếm gặp nhưng khi xảy ra thì sẽ mang lại thiệt hại cực kì nghiêm trọng, có thể làm sụp đổ cả 1 hệ thống (vd: nhà máy điện hạt nhân nếu mà bị kẹt tiến trình => hệ thống làm lạnh các thanh nhiên liệu nguyên tử không hoạt động thì nhiệt độ tăng cao gây ra nổ hạt nhân. Chất phóng xạ lan ra ngoài sẽ tàn phá sự sống.)
+ Còn trong giao thông: sẽ gây kẹt xe làm trễ công việc => gây thiệt hại rất lớn về tiền bạc cũng như thời gian.