Thảo luận Bài 8

NguyenXuanThi(I22A) đã viết:

Huynh Xuan Dat(I22A) đã viết:Để ngăn chặn Deadlock ta phải làm sao?
vd1 :2 con dê đi qua cầu, dê trắng và dê đen đều mún mình qua cầu chẳng ai chịu nhường ai cả, và cả 2 đều mắc kẹt mãi trên cầu....(có thể tranh chấp dẫn đến xảy ra đến cả 2 con đều rơi xuống cầu) tham khảo khóa trước
vd2:Giả sử tổng đài 1080 có tất cả 50 điện thoại viên. Cùng 1 lúc có 50 khách gọi đến nhờ phục vụ . Lúc này người thứ 51 gọi vào 1080 phải chờ . Xãy ra hiện tượng deadlock
tham khảo khóa trước
nhưng vd2 minh chưa thực sự hiểu bản chất lắm máy bạn giải thích giúp

Theo mình nghĩ ví dụ 2 vẫn chưa gọi là deadlockl vì khi một người nào đó trong 50 người đã được phục vụ cúp máy thì người 51 vẫn được đáp ứng nhu cầu bình thường

Bạn này nói đúng, cũng giống như Thầy nói về cái ví dụ về chờ sử dụng máy Photocopy không phải là hiện tượng Kẹt khoá (Deadlock).
=> Deadlock là hiện tượng kẹt mãi mãi.

Bài tập: 3 loại tài nguyên: A (10 phiên bản), B (5 phiên bản), C (7 phiên bản).
Thời điểm T0 :

P(i)	Đang giữ	Max	Hệ có
	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 0 2	4 3 3

Vậy tại thời điểm T0 có tồn tại chuỗi an toàn: {P1, P3, P4, P0, P2} ?

Giải:

Hệ có: Available = (10, 5, 7) - (7, 2, 5) = (3, 3, 2)
Ma trận Need = Max - Allocation:

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

Bảng hô trợ

Work	Need(i)	P(i)	Allocation
A B C	A B C		A B C
3 3 2	1 2 2	P1	2 0 0
5 3 2	0 1 1	P3	2 1 1
7 4 3	4 3 1	P4	0 0 2
7 4 5	7 4 3	P0	0 1 0
7 5 5	6 0 0	P2	3 0 2

Vậy tại thời điểm T0 hệ thống tồn tại chuỗi an toàn:{P1, P3, P4, P0, P2}.

Định Nghĩa Deadlock ?
Tình huống kẹt của 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.

vd1: 2 xe đi cùng chiều qua một cây cầu hẹp, mà cầu chỉ có một làn xe, nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường.
vd2: 5 lớp học điều cần máy chiếu . Trong khi đó phòng thiết bị chỉ có 1 máy chiếu .điều này dẫn tới ranh chấp chữa các lớp dùng máy chiếu .
vd3 : giả sử tổng đài 1080 có tất cả 50 điện thoại viên. Cùng 1 lúc có 50 khách gọi đến nhờ phục vụ . Lúc này người thứ 51 gọi vào 1080 phải chờ . Xãy ra hiện tượng deadlock

1.Phát hiện và phục hồi từ deadlock:
Phát hiện deadlock:

Dùng các giải thuật phát hiện vòng chờ các process.
Do người quản trị hệ thống.


Phục hồi từ deadlock:

Kết thúc các process bị deadlock.
Kết thúc tất cả các process bị deadlock.
Lần lượt kết thúc các process bị deadlock cho đến khi hết deadlock.


Thông số chọn process để kết thúc:

Độ ưu tiên.
Thời gian đã thực thi.
Thời gian còn lại.
Số tài nguyên đã cấp phát.
Số tài nguyên đang chờ.
Lấy lại tài nguyên từ process.
Lần lượt lấy lại các tài nguyên đã cấp phát cho các process cho đến khi hết deadlock.
Phụ thuộc bản chất của tài nguyên.
Sử dụng công cụ của hệ điều hành.
Phục hồi các điểm kiểm tra.
Định kỳ tạo các điểm kiểm tra (checkpoint).
Lưu trạng thái hệ thống tại điểm kiểm tra.
Thực hiện lại (rollback) các process bị deadlock tại các điểm kiểm tra.
Lần lượt thực hiện lại các process bị deadlock tại các điểm kiểm tra cho đến khi hết deadlock.


2.Ngăn chặn deadlock: Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:

Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.


Loại bỏ điều kiện loại trừ tương hỗ:

Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.


Vd: chỉ 1 printer daemon dùng máy in.
Các process gởi yêu cầu cho printer daemon.

Loại bỏ điều kiện giữ và chờ tài nguyên:
Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới.
Process khai báo tài nguyên và được cấp phát 1 lần.
Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.

Loại bỏ điều kiện không lấy lại tài nguyên:

Lấy lại tài nguyên từ process.
Không thể với tài nguyên như máy in.


Loại bỏ vòng chờ các process:

Có thể quy định số thứ tự tài nguyên.
Process chỉ được yêu cầu tài nguyên theo thứ tự tăng.
Giả sử có deadlock:
P1 giữ Ri, chờ Rj -> i < j.
P2 giữ Rj, chờ Rj -> j < i.



3.Tránh deadlock:
Chấp nhận các điều kiện tạo deadlock.
Theo dõi và tránh dẫn đến deadlock.

Hai hướng giải quyết:
1/Không tạo process mới nếu có thể dẫn đến deadlock:
Process cần khai báo số lượng tài nguyên cần sử dụng.
Không tạo process mới nếu số lượng tài nguyên hệ thống không đủ, có thể dẫn đến deadlock.

2/Không cấp phát thêm tài nguyên cho process:
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process.
Định nghĩa trạng thái hệ thống với:
Vector E: tổng số các loại tài nguyên.
Vector A: số tài nguyên mỗi loại chưa dùng.
Ma trận C: số tài nguyên đã cấp phát cho các process.
Ma trận R: số lượng tài nguyên các process sẽ tiếp tục yêu cầu.

Đồ 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.

phuquoccuong(I22A) đã viết:Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau:

Dùng thuật giải nhà băng để:
a.Chứng minh trạng thái này an toàn.
b.Xác định có nên đáp ứng yêu cầu (0, 4, 3, 0) của P1 ?
Giải:
a. Xét tại thời điểm To mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]

Tìm chuỗi an toàn:


Vậy tại thời điểm To tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.

b. Ta thấy, yêu cầu thêm (0, 4, 3, 0) của P1 thoả điều kiện Request1 <= Need1, nhưng không thoả điều kiện: Request1 <= Available vì tài nguyên C trong hệ thống chỉ còn 2 mà yêu cầu 3. Do vậy, không thể cấp phát thêm (0, 4, 3, 0) cho P1 được.

Cách giải rõ ràng, mình cũng giải giống như bạn này. không biết có bạn nào có cách giải khác không?

1. Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
2. Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
3. Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiên trình này tự nguyên trả lại hệ thống sau khi dung xong.
4. Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.
Ví dụ dễ hiểu mà ai cũng biết đó là câu chuyện 2 con dê trắng & đen qua cầu, không con nào chịu nhường con nào thì cả 2 sẽ chẳng bao giờ thực hiện đc mục đích là qua được bờ bên kia cả => xảy ra deadlock.

=> Để ngăn chặn DeadLock thì chỉ cần phủ định một trong bốn điều kiện trên không cho chúng xảy ra đồng thời.

NguyenHoangKimVu (I11C) đã viết:

MaiXuanSon (I22B) đã viết:

NguyenThiMai(I22A) đã viết:Trình bày khái niệm Deadlocks và ví dụ minh họa Deadlocks
- Khái niệm: Deadlocks là tình huống 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 có thể chỉ được gây ra bởi một tiến trình khác.
- Ví dụ:

• có 1 cái hang mà 2 con cua giành chiếm dẫn đến chúng ghanh ghét nhau, 2 con cùng chui vào hang vì cái hang hẹp nên những cái càng của chúng bị vướng vào nhau và rồi chúng bị rơi vào tình huống kẹt.

• 2 lớp học I22A và I22B đều cần thực hành.Trong khi đó phòng máy chỉ có 1 phòng trống => deadlock

• Giả sử tổng đài viettell có 20 tổng đài viên. Cùng 1 lúc có 20 khách gọi đến hỏi về những thắc mắc.Vào lúc này người thứ 21 gọi vào phải chờ => hiện tượng deadlock

Mình thấy 3 ví dụ của bạn này không đúng lắm, không biết các bạn nghĩ sao về 3 ví dụ của bạn này.
- Ví dụ về 2 lớp học thực hành nhưng chỉ có 1 phòng.
+ Trường hợp này lớp 1 học xong thì lớp 2 vẫn tiếp tục học được => Không bị Deadlock.
- Ví dụ tổng đài Vietell.
+ Cùng lúc 20 khách gọi đến thì có 20 tổng đài viên trả lời, nếu có khách thứ 21 gọi đến thì chờ 1 lúc rồi 1 trong 20 tổng đài viên kia trả lời xong. Thì lúc này vẫn đáp ứng khách thứ 21 được.

Kiến thức mình sơ sài mong Thầy và các Bạn giúp.

Những ví dụ này tương tự như ví dụ về máy photocopy, nên những trường hợp này không thể xem là deadlock được. Những trường hợp này chỉ phải chờ một chút thôi.

Mih cũng nghĩ vd3 của bạn này hok đúng. Deadlock thì phải chờ mãi mãi. còn vd3 đó sau khoảng thời gian ngắn thì 1 trong 20 người đó disconnect thì người tiếp theo gọi vào lại được rùi...

Bài tập: Một hệ thống có 12 ổ băng từ và 3 tiến trình với tình trạng cấp phát tài nguyên như sau:
Tiến trình Đã được cấp Max
P1 5 10
P2 2 4
P3 2 9
a) Chứng minh trạng thái là an toàn.
b) Xác định có nên đáp ứng nhu cầu cần thêm một ổ băng nữa của P3?
Câu a:
Hệ có:Available=12-(5+2+2)=3

Need=Max-Allocation

Need
P1 5
P2 2
P3 7

Work=> Need(i) P(i) Allocation(i)
Available 3 2(thỏa đk) P2 2
5 5(thỏa đk) P1 5
10 7(thỏa đk) P3 2

=>Chuỗi an toàn={P2,P1,P3}

Câu b:

Tiến trình Đã được cấp Max
P1 5 10
P2 2 4
P3 3 9

-Yêu cầu này thỏa các đk:

Request(3)<=Need(3) vì 1<=7
Request(3)<=Available vì 1<=3

Hệ có:Available=12-(5+2+3)=2

Need=Max-Allocation

Need
P1 5
P2 2
P3 6

Work=> Need(i) P(i) Allocation(i)
Available 2 2 P2 2
4 5(ko thỏa) P1 5

Hoặc:
Work=> Need(i) P(i) Allocation(i)
Available 2 2 P2 2
4 6(ko thỏa) P3 3


Kết luận:Vậy không có chuỗi an toàn,không nên đáp ứng cấp cho P3 1 ỗ nữa vì có thể dẫn đến Deadlock

Câu 2: Trình bày bốn điều kiện cần dẫn đến Deadlocks và biện pháp ngăn chặn Deadlock?

Trả lời
Deadlocks có thể xảy ra khi có 4 điều kiện cần sau:
- Loại trừ lẫn nhau: Đây là tính chất khi mà trong 1 thời điểm chỉ có một tiến trình được sử dụng tài nguyên của HĐH mà thôi

- Giữ và chờ: Có 1 tiến trình đang giữ 1 tài nguyên và tiến trình này lại đang yêu cầu thêm 1 tài nguyên khác nữa mà tài nguyên này đang bị chiếm giữ bởi 1 tiến trình khác

- Không có tiếm quyền: Cho tiến trình sử dụng thoải mái tài nguyên để hoàn tất công việc của nó và trả lại 1 cách tự nguyện cho HĐH

- Chờ xoay vòng: Giả sử có n tiến trình đang chờ tài nguyên với quy luật xoay vòng như sau: tiến trình P1 chờ tài nguyên của tiến trình P2, tiến trình P2 chờ tài nguyên của tiến trình P3,..., tiến trình Pn chờ tài nguyên của tiến trình P1.

Biện pháp
- Loại trừ lẫn nhau: Tài nguyên nào cũng được dùng chung bởi nhiều tiến trình trong cùng một lúc.

- Giữ và chờ: Không cho bất kì 1 tiến trình nào đang giữ 1 tài nguyên mà yêu cầu thêm 1 tài nguyên khác hoặc cấp phát hết tài nguyên cần và đủ để hoàn tất công việc của 1 tiến trình ngay từ lúc đầu.

- Không có tiếm quyền: Bắt buộc tiến trình A nào đó đang sử dụng tài nguyên phải trả lại tại nguyên cho một tiến trình B cũng đang cần tài nguyên này mà không cần biết tiến trình A đó đã sử dụng tài nguyên này để hoàn tất công việc của nó hay chưa.

Câu trả lời của em rất có thể sẽ còn nhiều thiếu sót, vậy nên em rất mong thầy và các bạn nhiệt tình sửa chữa, góp ý, em xin cảm ơn thầy và các bạn!

NguyenVanLanh (I22A) đã viết:

NguyenHoangKimVu (I11C) đã viết:

MaiXuanSon (I22B) đã viết:

NguyenThiMai(I22A) đã viết:Trình bày khái niệm Deadlocks và ví dụ minh họa Deadlocks
- Khái niệm: Deadlocks là tình huống 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 có thể chỉ được gây ra bởi một tiến trình khác.
- Ví dụ:

• có 1 cái hang mà 2 con cua giành chiếm dẫn đến chúng ghanh ghét nhau, 2 con cùng chui vào hang vì cái hang hẹp nên những cái càng của chúng bị vướng vào nhau và rồi chúng bị rơi vào tình huống kẹt.

• 2 lớp học I22A và I22B đều cần thực hành.Trong khi đó phòng máy chỉ có 1 phòng trống => deadlock

• Giả sử tổng đài viettell có 20 tổng đài viên. Cùng 1 lúc có 20 khách gọi đến hỏi về những thắc mắc.Vào lúc này người thứ 21 gọi vào phải chờ => hiện tượng deadlock

Mình thấy 3 ví dụ của bạn này không đúng lắm, không biết các bạn nghĩ sao về 3 ví dụ của bạn này.
- Ví dụ về 2 lớp học thực hành nhưng chỉ có 1 phòng.
+ Trường hợp này lớp 1 học xong thì lớp 2 vẫn tiếp tục học được => Không bị Deadlock.
- Ví dụ tổng đài Vietell.
+ Cùng lúc 20 khách gọi đến thì có 20 tổng đài viên trả lời, nếu có khách thứ 21 gọi đến thì chờ 1 lúc rồi 1 trong 20 tổng đài viên kia trả lời xong. Thì lúc này vẫn đáp ứng khách thứ 21 được.

Kiến thức mình sơ sài mong Thầy và các Bạn giúp.

Những ví dụ này tương tự như ví dụ về máy photocopy, nên những trường hợp này không thể xem là deadlock được. Những trường hợp này chỉ phải chờ một chút thôi.

Mih cũng nghĩ vd3 của bạn này hok đúng. Deadlock thì phải chờ mãi mãi. còn vd3 đó sau khoảng thời gian ngắn thì 1 trong 20 người đó disconnect thì người tiếp theo gọi vào lại được rùi...

Mình củng đồng ý với bạn là 3vd trên không phải là Deadlock vì cái nào củng cần chờ là sẽ tới lượt. Mình xin nêu ra ví dụ như thế này:
Có 4 lớp học mỗ lớp đều có nhu cầu sử dụng cùng lúc 2 thiết bị máy chiếu cùng với mic, tại thời điểm T0 nào đó lớp 1 muốn hoạt động nhưng lại chỉ có 1 mic cần thêm máy chiếu nên phải chờ máy chiếu của lớp 2 trong khi lớp 2 lại phải chờ mic của lớp 3, lớp 3 lại chờ máy chiếu của lớp 4, còn lớp 4 lại chờ mic của lớp 1 => Deadlock.
theo mình vd trên là Deadlock còn các bạn nghỉ sao ???

Các giải pháp xử lý Deadlock
1.Phát hiện và phục hồi từ deadlock:
Phát hiện deadlock:
Dùng các giải thuật phát hiện vòng chờ các process.
Do người quản trị hệ thống.
Phục hồi từ deadlock:
Kết thúc các process bị deadlock.
Kết thúc tất cả các process bị deadlock.
Lần lượt kết thúc các process bị deadlock cho đến khi hết deadlock.
Thông số chọn process để kết thúc:
Độ ưu tiên.
Thời gian đã thực thi.
Thời gian còn lại.
Số tài nguyên đã cấp phát.
Số tài nguyên đang chờ.
Lấy lại tài nguyên từ process.
Lần lượt lấy lại các tài nguyên đã cấp phát cho các process cho đến khi hết deadlock.
Phụ thuộc bản chất của tài nguyên.
Sử dụng công cụ của hệ điều hành.
Phục hồi các điểm kiểm tra.
Định kỳ tạo các điểm kiểm tra (checkpoint).
Lưu trạng thái hệ thống tại điểm kiểm tra.
Thực hiện lại (rollback) các process bị deadlock tại các điểm kiểm tra.
Lần lượt thực hiện lại các process bị deadlock tại các điểm kiểm tra cho đến khi hết deadlock.
2.Ngăn chặn deadlock:
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
Loại bỏ điều kiện loại trừ tương hỗ:
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
Các process gởi yêu cầu cho printer daemon.
Loại bỏ điều kiện giữ và chờ tài nguyên:
Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới.
Process khai báo tài nguyên và được cấp phát 1 lần.
Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.
Loại bỏ điều kiện không lấy lại tài nguyên:
Lấy lại tài nguyên từ process.
Không thể với tài nguyên như máy in.
Loại bỏ vòng chờ các process:
Có thể quy định số thứ tự tài nguyên.
Process chỉ được yêu cầu tài nguyên theo thứ tự tăng.
Giả sử có deadlock:
P1 giữ Ri, chờ Rj -> i < j.
P2 giữ Rj, chờ Rj -> j < i.
3.Tránh deadlock:
Chấp nhận các điều kiện tạo deadlock.
Theo dõi và tránh dẫn đến deadlock.
Hai hướng giải quyết.
Không tạo process mới nếu có thể dẫn đến deadlock.
Process cần khai báo số lượng tài nguyên cần sử dụng.
Không tạo process mới nếu số lượng tài nguyên hệ thống không đủ, có thể dẫn đến deadlock.
Không cấp phát thêm tài nguyên cho process:
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process.
Định nghĩa trạng thái hệ thống với:
Vector E: tổng số các loại tài nguyên.
Vector A: số tài nguyên mỗi loại chưa dùng.
Ma trận C: số tài nguyên đã cấp phát cho các process.
Ma trận R: số lượng tài nguyên các process sẽ tiếp tục yêu cầu.

Deck lock này mình diễn đạt đơn giản như trong 2 quá trình đang chạy . quá trình 1 có khóa [key1], quá trình 2 có khóa [key2]. Tại một thời điểm nào đó quá trình 1 cần thêm [key2] để hoạt động , và quá trình 2 lại cần [key1] để hoạt động

Lúc đó cả quá trinh 1 và 2 đều rơi vào trạng thái block. Xảy ra tình trạng 2 hằn chờ nhau mải mà không thằng nào chết để đưa key lại cho hệ thống.

Trạng thái block này mãi mãi vì chờ quá trình chết để lấy [key]. Đây chính là trạng thái deaklock.

Note ( Quá trình ở đây phải hiểu là Thread )

Demo Nhỏ Nằm chung 1 class nha. Đây là bài học trong phần deadclock mình có post trong tài liệu về thread. các bạn tham khảo

Những điều kiện cần thiết gây ra deadlock
Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một lúctrong hệ thống:
-Loại trừ hỗ tương: ít nhất một tài nguyên phải được giữ trong chế độ không chiasẻ; nghĩa là, chỉ một quá trình tại cùng một thời điểm có thể sử dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình yêu cầu phải tạm dừngcho đến khi tài nguyên được giải phóng.
-Giữ và chờ cấp thêm tài nguyên: quá trình phải đang giữ ít nhất một tài nguyên vàđang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi quá trình khác.
-Không đòi lại tài nguyên từ quá trình đang giữ chúng: Các tài nguyên không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bởi quá trình đanggiữ nó, sau khi quá trình đó hoàn thành tác vụ.
-Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá trình {P0,P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1, P1đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ tài nguyên đang được giữ bởi quá trình P0.1Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlock xảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiệnkhông hoàn toàn độc lập

Bài 1: Một hệ thống có 3 máy quét hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation= (0,2,1), và Max(2,2,2). Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có đáp ứng được hay không yêu cầu thêm 1 máy nữa của P2.
Giải:

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0+2+1)=0
Tiến trình Đang giữ Max Hệ có
P1 0 2 0
P2 2 2
P3 1 2

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need
P1 2
P2 0
P3 1

Work >= Need(i) P(i) Allocation(i)
0 0 P2 2
2 1 P3 1
3 2 P1 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.


Bai 2:

Một hệ thống có 3 máy quét hình và 2 tiến trình P1,P2 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation(1,1) và Max(2,2). Dùng thuật giải nhà băng để:

a) Chứng minh trạng thái an toàn
b) Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy nữa P2 ./.



Giải:
a) Allocation=(1,1), Max=(2,2);
Available=3-(1+1)=1;
Ta có: Need(i)=Max(i)-Allocation(i)
=> p1=(2-1)=1; p2=(2-1)=1;
Work >= Need(i) P(i ) Allocation
1 1 p1 1
2 1 p2 1
. Tồn tại chuỗi an toàn=.
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
b)
Request(2)<=Need(2) vì 1<=1
Request(2)<=Available vì 1<=1
Trạng thái mới:
Allocation(1,1+1)(vì thêm 1 máy nữa nên cộng thêm 1)
Available=3-(1+1+1)=0
Need(i):
p1 1
p2 0
Work >= Need(i) P(i) Allocation
0 0 p2 2
2 1 p1 1
Tồn tại trạng thái an toàn=
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

- Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
- Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
- Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).

1. Loại trừ tương hỗ: Nếu một tiến trình đang sử dụng tài nguyên dùng chung thì tiến trình khác phải chờ.
=> Biện pháp tránh loại trừ tương hỗ: Cho nhiều tiến trình cùng sử dụng tài nguyên đồng thời.
VD: Theo mình nghĩ là chúng ta cần phải có nhiều phiên bản của một loại tài nguyên để nhiều tiến trình có thể sử dụng đồng thời. Số tiến trình cần sử dụng tài nguyên <= Số phiên bản, nếu ngược lại thì phải chờ.

2. Giữ và chờ: Khi một tiến trình đã giữ một tài nguyên rồi và nó cần thêm những tài nguyên khác nữa.
=> Biện pháp tránh Giữ và chờ: Không cho tiến trình yêu cầu thêm tài nguyên cho đến khi tài nguyên đang chiếm giữ được giải phóng.
VD: Hai xe đi ngược nhau qua cầu hẹp và cả 2 xe đều cần nửa mặt đường cầu còn lại để có thể qua được cầu. Chúng ta sẽ cấp luôn cả 1 mặt cầu cho 1 chiếc xe, chạy xong rùi ta mới cấp mặt cầu cho xe còn lại (nhưng giải pháp này phải tốn thời gian để chờ, chờ lâu => không hiệu quả về mặt thời gian).

3. Không tiếm quyền: Tiến trình dùng xong tài nguyên rồi tự trả lại, không có sự can thiệp của HĐH.
=> Biện pháp tránh Không tiếm quyền: Cần phải tiếm quyền.
VD: Hai xe đi ngược nhau qua cầu hẹp và cả 2 xe đều cần nửa mặt đường cầu còn lại để có thể qua được cầu. Để thuận tiện thì chúng ta sẽ dùng cần cẩu để cẩu 1 chiếc lên (đang tiếm quyền) cho chiếc còn lại chạy qua khỏi một đoạn rồi đặt xe xuống (cho phép thi hành tiếp) để tiếp tục chạy (=> hiệu quả về mặt thời gian).

4. Chờ xoay vòng: Khi các tiến trình chờ tài nguyên đang được cấp cho một tiến trình khác và tạo thành một vòng khép kín.
=> Biện pháp tránh Chờ xoay vòng: Cấp phát tài nguyên theo đúng một trật tự nào đó.
Mình không rõ VD cho biện pháp này lắm, bạn nào có thể giúp mình bổ sung cái này không?

Trình bày khái niệm Deadlocks và ví dụ minh họa Deadlocks
- Khái niệm: Deadlocks là tình huống 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 có thể chỉ được gây ra bởi một tiến trình khác.
- Ví dụ:
Trường ĐH Mở cho phép sinh viên đăng ký môn học trực tuyến. hệ thống đăng ký môn học trực tuyến là tài nguyên hệ thống. Do tài nguyên chỉ cho phép 1 số lượng sinh viên nhất định vào đăng ký mà lượng sinh viên đăng nhập lại rất lớn dẫn đến tình trạng nghẽn mạch không thể vào trong để đăng ký được

1. Loại trừ tương hỗ: Nếu một tiến trình đang sử dụng tài nguyên dùng chung thì tiến trình khác phải chờ.Biện pháp tránh loại trừ tương hỗ: Cho nhiều tiến trình cùng sử dụng tài nguyên đồng thời.
2. Giữ và chờ: Khi một tiến trình đã giữ một tài nguyên rồi và nó cần thêm những tài nguyên khác nữa.
=> Biện pháp tránh Giữ và chờ: Không cho tiến trình yêu cầu thêm tài nguyên cho đến khi tài nguyên đang chiếm giữ được giải phóng.
3. Không tiếm quyền: Tiến trình dùng xong tài nguyên rồi tự trả lại, không có sự can thiệp của Hệ Điều Hành.
=> Biện pháp tránh Không tiếm quyền: Cần phải tiếm quyền.
4. Chờ xoay vòng: Khi các tiến trình chờ tài nguyên đang được cấp cho một tiến trình khác và tạo thành một vòng khép kín.

NguyenVanQuoc (I22B) đã viết:

cho mình hỏi là ở hình thứ 3 đó: nếu R2 chỉ có 1 phiên bản thui, tức là chỉ có 1 dấu chấm thui thì có xảy ra deadlock ko? nhờ thầy và các bạn giải thích dùm.

Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allocation = (1, 0, 1) và Max = (1, 2, 2):
Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của P3 ?

a. Chứng minh trạng thái ở thời điểm T0 là an toàn:
- Available = 3 – (1+0+1) = 3 – 2 = 1
-

- Tìm chuỗi an toàn:

- Chuỗi an toàn = {P1, P2, P3}. Vậy trạng thái hệ thống ở thời điểm T0 là an toàn
b. Có nên đáp ứng yêu cầu xin thêm 1 ổ nữa của P3:
-       Request3 = 1 <= Need3 = 1
       Request3 = 1 <= Available = 1
- Trạng thái mới của hệ thống:

- Tìm chuỗi an toàn:

- Việc cấp phát thêm 1 ổ nữa cho P3 thì hệ thống vẫn ở trạng thái an toàn do tồn tại chuỗi an toàn = {P1, P3, P2}.
- Vậy ta có thể cấp thêm cho yêu cầu xin thêm 1 của P3 tại thời điểm này.

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

LeThanhQuang (I22B) đã viết:

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

Cach 2 của bạn ko đúng rồi. cách này biến thành đường 1 chiều rồi... Mà trong trường hợp này là đường 2 chiều mà...

1/Loại trừ toàn bộ: hướng đến phá vỡ toàn bộ nhóm các tiến trình liên quan đến nguyên nhân gây ra Deadlock, sau đó, sẽ khởi chạy phục hồi lại chương trình đã bị phá vỡ trước đó.
2/Loại trừ từng phần: Sẽ tiến hành hủy bỏ lần lượt các tiến trình liên quan đến quá trình Deadlock, cho đến khi tài nguyên được lấy lại từ các tiến trình đã bị loại trừ, đủ cấp phát đủ các tiến trình còn lại hoạt động, quá trình Deadlock sẽ kết thúc dần dần .
- Ví dụ: Khi kẹt xe ở ngã tư đường (Deadlock) lúc này người Cảnh Sát sẽ cho các xe (tiến trình) ngừng di chuyển ,để nhường lại phần đường (tài nguyên) cho những xe có hướng được ưu tiên chạy, dần dần sẽ mở được những luồng xe nhỏ di chuyển ra khỏi nơi kẹt xe (Kết thúc Deadlock).
3/ Lấy lại tài nguyên: Tiến hành lấy lại tài nguyên đã cấp phát và tạm ngừng hoạt động cho nhóm các tiến trình chịu ảnh hưởng bởi quá trình Deadlock, sau đó sẽ tiến hành đưa các tiến trình trở lại trạng thái ban đầu chưa hoạt động, chưa được cấp tài nguyên.

LeThanhQuang (I22B) đã viết:

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

Thêm giải pháp một trong hai xe lùi lại nhường cho xe kia nữa chứ bạn.