Thảo luận Bài 8

Các giải pháp ngăn chặn Deadlocks bằng cách phủ định một trong 4 điều kiện dẫn đến Deadlocks
•Loại bỏ điều kiện loại trừ tương hỗ:

Vì tại một thời điểm chỉ có 1 tiến trình được sử dụng tài nguyên, mà đây là tài nguyên không chia sẽ nên ta sẽ tăng số lượng tài nguyên lên. Giải pháp này thực tế là không khả thi.
Ví dụ: trong trường hợp ổ cứng bị đầy và chỉ còn đủ để cung cấp trong một tiến trình thì phương pháp này không thực hiện được
Cấp phát tài nguyên dạng ống.(spool)

•Loại bỏ điều kiện giữ và chờ (Hold and Wait):

Do một tiến trình đang giữ tài nguyên và yêu câu một tài nguyên mới nên nguyên tắc để loại bỏ là: tiến trình không được giữ tài nguyên khi yêu cầu tài nguyên mới. Khi cần, nó khai báo tài nguyên và đươc cấp phát một lần. Nếu nó yêu cầu thêm tài nguyên và không được thì phải trả cái tài nguyên mà nó đang giữ.
Giải pháp này cũng không khả thi bởi trong thực tế một tiến trình cần nhiều hơn 1 tài nguyên mới có thể hoạt động được.
Tiến trình phải yêu cầu và được cấp tất cả tài nguyên mà nó cần ngay đầu công việc. Giải pháp này cũng không khả thi vì nó tốn nhiều tài nguyên

•Loại bỏ Không tiếm quyền( No Preemption):

Hệ điều hành sẽ lấy lại tài nguyên từ tiến trình mà nó đang chiếm giữ khi sử dụng xong. Nhưng với một số tài nguyên có thể không lấy lại được.

•Loại bỏ chờ xoay vòng( Circular Wait):

Có thể cấp số thứ tự cho mỗi tài nguyên, và mỗi tiến trình chỉ được yêu cầu tài nguyên theo thứ tự tăng dần

Các giải pháp trên đây đều không khả thi trong thực tế, có người cho rằng không cần học, nhưng có thể từ những giải pháp này, sẽ có giải pháp tốt hơn và hoàn thiện hơn được sáng tạo trong tương lai .

Bài tập: Một hệ thống có 12 ổ băng từ và 3 tiến trình với bả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

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}

Bài tập: Một hệ thống có 12 ổ băng từ và 3 tiến trình với bả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

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

=>Tìm được chuỗi an toàn={P2,P1,P3}.Vậy trạng thái hệ thống an toàn.

Phương pháp giải bài toán: Xác định xem có nên đáp ứng hay không yêu cầu cấp thêm tài nguyên cho tiến trình

Phương pháp này thầy đã giảng chắc là nhiều người biết rồi nhưng mình xin trình bày cho các bạn nào nhìn thấy mấy bài giải mà chẳng biết vì sao lại như thế, chỉ biết làm theo thôi

Mình xin đưa ra một số ý từ ví dụ quản lý tiền ngân hàng của thầy theo cách mình hiểu. Bạn xét lần lượt 2 thứ sau :
1.Đầu tiên các bạn phải xác định yêu cầu này có hợp lệ hay hiện tại hệ có thể đáp ứng không bằng cách xét 2 điều kiện sau
Request(i) <= Need(i). Yêu cầu vay tiền > Số tiền cần =>không thể cho vay. Vì cho vay thì số tiền > Max(được vay). Không hợp lý vì giải thuật này hạn chế số tiền cho vay.
Request(i) <= Avalable.Yêu câu vay tiền > Số tiền ngân hàng đang có => Hiện giờ không cho vay được. Vì đâu có tiền mà cho vay. Ở thời điểm sau có thể đáp ứng được chứ thời điểm này thì chưa được -> Quay lại sau

2. Khi đã thỏa điều kiện ở bước 1. Ở bước này là: Xét xem "nếu cấp phát tài nguyên theo yêu cầu này thì hệ thống có còn ở trạng thái an toàn nữa không", nếu có (còn tồn tại chuỗi an toàn mới sau khi cấp phát) thì cấp phát. Nếu không (không có chuỗi an toàn mới sau khi cấp phát) thì không cấp phát.
Các bạn giả sử đã cấp phát theo yêu cầu thì sẽ cập nhật lại dữ liệu mới sau khi đã cấp phát và tìm chuỗi an toàn như ở bài trên mình hướng dẫn ở bài trên để xác định xem có nên đáp ứng hay không yêu cầu này nha.
Cụ thể các bạn cập nhật một số dữ liệu mới như sau :
Cập nhật lại tài nguyên mà tiến trình yêu cầu đang giữ (Allocation) = tài nguyên trước đó tài nguyên mới yêu cầu.
Cập nhật lại Need(i)tiến trình yêu cầu sau khi đã cấp phát=Max(i)-Allocation mới tính
Cập nhật lại tài nguyên mà hệ có =Tài nguyên chưa dùng (cũ)-Tài nguyên tiến trình yêu cầu
=>Với dữ liệu mới hãy tìm chuỗi an toàn và kết luận xem có nên đáp ứng không.

Admin
- Hiểu tốt !
- Cần thêm Bước cuối: Tìm Chuỗi An toàn theo Quy trình của thày ! (sau khi giả định đáp ứng yêu cầu của tiến trình)

TranHuyCuong17 (I12A) đã viết:Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:

Tiến trình	Đang giữ	Max
P1	5	10
P2	2	4
P3	2	9

Hệ thống có: Available = (số tài nguyên lúc đầu - đang giữ) = 12 - (5+2+2) = 3

Need = (Max - Đang giữ)

Tiến trình	Need
P1	5
P2	2
P3	7

	Work	>=	Need i	P i	Allocation
Available	3		2	P2	2
	5		5	P1	5
	10		7	P3	2

=> tìm được chuỗi an toàn = {P2,P1,P3}, vậy trạng thái hệ thống an toàn


Giả sử P3 yêu cầu thêm 1 ổ

yêu cầu này thỏa các điều kiện

Request3 <= Need 3 vì 1<=7

Request3 <= Availabe vì 1<=3

Tiến trình	Đang giữ	Max
P1	5	10
P2	2	4
P3	3	9

Hệ thống có: Available = (số tài nguyên lúc đầu - đang giữ) = 12 - (5+2+3) = 2

Need = (Max - Đang giữ)

Tiến trình	Need
P1	5
P2	2
P3	6

	Work	>=	Need i	P i	Allocation
Available	2		2	P2	2
	4		5	P1	3	ko thỏa
	4		6	P3	5	ko thỏa

--> tới đây, ko thỏa, nên ko biết kết luận thế nào, ai giúp dùm với

trời. đi tới Roma rồi mà không biết tìm cửa vào...
tới đây bạn chỉ cần kết luận là: "Vậy tại thời điểm này, hệ thống rơi vào trạng thái không an toàn. Không thể cấp thêm cho P3 một ổ đĩa nữa."
thế thôi, chúc bạn ôm trọn điểm câu này.hihi
Thân

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.

thailongI12C đã viết:

phamphihung55 đã viết:

NguyenHongHaiI12C đã viết:-Hệ thống có 12 ổ băng.
-Có 3 tiến trình P1,P2,P3.

Tiến trình	Được cấp (đang giữ)	Max
P1	5	10
P2	2	4
P3	2	9

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1 P2 P3)= 12- (5 2 2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5=5
P2	4-2=2
P3	9-2=7

vì hệ số là 3, nên để work >= Need(i), nên chỉ chọn P2 vì Need của P2 =2 thỏa điều kiện nên tiến trình P2 xét trước.
Tiếp tục lấy allocation work (2 3=5) ,5 so với bảng Need(i) thỏa điều kiện với P1 vì Need (P1=5), nên P(i) lúc này =5, Làm tương tự ta cho đến P3, sẽ được bảng như sau

	Work	Need(i)	P(i)	Allocation
Available	3 >=	2	P2	2
	5 >=	5	P1	5
	10 >=	7	P3	2

- Kết luận :
-Tìm được chuỗi an toàn= {P2,P1,P3} vậy trạng thái hệ thống 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?
-Xét điều kiện :
Request(1) <= Need(i) thỏa vì 1<=7.
Request(1) <= Available thỏa vì 1<=3.
Available = Max - (P1 P2 P3) = 12- (5 2 3)=2.
Ta có trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2
P3	3	6

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
Vậy trạng thái ở thời điểm lúc ban đầu là an toàn
Nên không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

cho mình bổ sung ý kiến của mình vào đáp án câu b của bạn:

vì chuỗi an toàn phải có đủ p1,p2,p3. nếu chỉ tìm được p1 và p2 thì khả năng gây ra deadlock .
vậy:hệ không tồn tại chuỗi an toàn

Câu b P1 cũng không thỏa mà bạn.

Bạn ơi! Bạn chú ý tới điều kiện Work >= Needs nhé! Chính vì vậy mà ở câu b P1 vẫn thoả điều kiện.

- Mutual exclusion: với mỗi tài nguyên chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài nguyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu trình khép kín các yêu cầu tài nguyên.

HoNgocTuan142(I12A) đã viết:

LeXuanHau (I12C) đã viết:
bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

mình xin trả lời câu hỏi của bạn Lê Xuân Hậu, nếu ace thấy chưa đúng hay chưa thỏa đáng thì cứ chém thẳng tay nha.
thực ra tìm chuỗi an toàn rất dễ, tại một thời điểm (ở đây mình xin phép nói là bài toán cho dễ hiểu) có thể có nhiều chuỗi an toàn khác nhau.
Ở ví dụ của thầy trong Slide là thầy đã biết trước kết quả nên thầy chọn ra một chuỗi an toàn tốt nhất đấy thôi, còn nếu muốn dễ hiểu thì bạn cứ duyệt từ trên xuống, nếu thấy tiến trình P_i nào có Need_i <= Work thì bạn đưa vào xét thôi (chú ý: Work đầu tiên cho bằng Available, sau đó Work = Work + Allocation_i của tiến trình P_i vừa được chọn).
nói thì có vẻ khó hiểu để mình làm luôn một ví dụ cho dễ hiểu (tuy hơi lười nhưng vì sự nghiệp kháng chiến... quất tới thôi )
Bài Tập (lấy lại ví dụ của mình trong bài trước)

1/ dùng giải thuật nhà băng để chứng minh trạng thái này an toàn.
2/ xác định có nên đáp ứng yêu cầu <0,4,3,0> của tiến trình P1?

GIẢI:
1/chứng minh trạng thái an toàn
-tính Need = MAX - Allocation

Tiến 		  Need
Trình		A  B  C  D
P0 		0  0  0  0
P1 		0  7  5  0
P2 		1  0  0  2
P3 		0  0  2  0
P4 		0  6  4  2

-Tìm chuỗi an toàn của hệ thống:
trước tiên cho Work = Available. Sau đó duyệt theo bảng Need từ trên xuống nếu thỏa Need<=Work thì chọn. Tiến trình nào chọn rồi hoặc không thỏa thì bỏ qua, kiểm tra tiến trình kế tiếp, đến cuối dãy thì lặp lại.

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P0,P2,P3,P4,P1} => hệ thống tại thời điểm này là an toàn.
-ở đây đã "may mắn" tìm ra được chuỗi an toàn. dừng lại và kết luận trạng thái này an toàn.
-nếu không tìm ra chuỗi an toàn thì ta duyệt theo một thứ tự khác cũng gần như vậy. miễn tìm ra được chuỗi an toàn thỏa mãn tất cả các điều kiện.
****Trên đây là cách duyệt cơ bản. Vì có thể có nhiều chuỗi an toàn khác nhau nên có nhiều cách tìm ra nó. Theo mình nghĩ cách của thầy trong ví dụ ở Slide là khá tối ưu, vì trong những tiến trình thỏa điều kiện Need<= Word thì chọn tiến trình nào có Need thấp và Allocation cao trước. Như thế sẽ có nhiều Availble (Work) dư ra để dễ dàng cấp cho các tiến trình sau hơn. cách này mà không tìm ra được chuỗi an toàn thì không cách nào tìm ra được (Nghĩa là không tồn tại chuỗi an toàn)
Và đây là kết quả của một thứ tự duyệt khác:

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   2   0         P3     0   6   3   2
1  11   5   2 	   0   6   4   2         P4     0   0   1   4
1  11   6   6 	   1   0   0   2         P2     1   3   5   4
2  14  11  10 	   0   7   5   0         P1     1   0   0   0
3  14  11  10 	   0   0   0   0         P0     0   0   1   2

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.
giống như bài viết của bạn Hiển đã tìm ra tất cả các chuỗi an toàn rồi đấy, các bạn có thể tham khảo thêm tại đây
2/Giả sử P1 có yêu cầu mới = (0,4,3,0)
Dựa vào yêu cầu mới của P1 ta có thể khẳng định không nên đáp ứng yêu cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available
Suy ra: (0,4,3,0) Không <= (1,5,2,0)

đó là theo cách hiểu của mình tự "mổ xẻ" từ ví dụ thầy giải trên lớp. các bạn thấy không đúng chỗ nào không đúng hay không thỏa đáng thì góp ý cho mình nha.
tất cả vì sự nghiệp thi đậu

Admin
- Rất Hiểu bài, Nhiệt tình và Tự nhiên !
- Đã sửa đôi chỗ, nhất là Word (từ) => Work (biến tạm, làm việc, trung gian, dùng tích lũy tổng Available+Allocation_i1+Allocation_i2+...)

Chào bạn !
Bạn vui có thể giải thích dùm mình cách duyệt các tiến trình được không?

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

chổ cột Pi vì sao xét thứ tự P0 ->P2->P3->P4->P1 khi mình chưa biết chuỗi an toàn?

hệ thống có 12 ổ băng và 3 tiến trình với bảng cấp phát tài nguyên như sau :

tiến trình Được cấp(ổ đĩa) tối đa cần(ổ đĩa)
P1 5 10
P2 2 4
P3 2 9
Dùng thuật toán 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 một ở nữa cho p3

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1+ P2 + P3)= 12- (5+2+2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5 =5
P2	4-2 =2
P3	9-2= 7

Work	Need(i)	P(i)	Allocation
3 >=	2	P2	2
5 >=	4	P1	5
10 >=	7	P3	2

- Kết luận :
+Tồn tại một chuỗi an toàn= {P2,P1,P3}
+Vậy trạng thái hệ thống ở thời điểm To 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?
-Xét điều kiện :
+ Request(1) <= Need(i) thỏa vì 1<=7.
+Request(1) <= Available thỏa vì 1<=3.
Available = Tổng - (P1+P2+P3) = 12- (5+2 +3)=2.
Trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2	2
P3	3	6	2

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
+ Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
+Vậy trạng thái ở thời điểm T1 là không an toàn
+ Không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

plminhhoangI12A đã viết: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

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:]Giả sử cấp thêm chi P3 1 ổ

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

Admin
Giải và Trình bày tốt !

Thanks Ban nhieu nha.

- Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .

- Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.

- Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.

- Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn

- Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.

Chào mọi người!!!
Mình có 1 bài tập về thuật giải nhà băng, mình có giải thử rùi nhưng không biết đúng không nữa. Mọi người cùng nhau giải nhen.
Bài tập: 1 hệ thống có 5 ổ 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 các vector Allocation = (1,2,1) và max = (3,2,3),dung thuật giải nhà băng để:
A/CM 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 them 2 ổ nữa của p3?

vothingocthuy87(I11C) đã viết:Chào mọi người!!!
Mình có 1 bài tập về thuật giải nhà băng, mình có giải thử rùi nhưng không biết đúng không nữa. Mọi người cùng nhau giải nhen.
Bài tập: 1 hệ thống có 5 ổ 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 các vector Allocation = (1,2,1) và max = (3,2,3),dung thuật giải nhà băng để:
A/CM 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 them 2 ổ nữa của p3?

Mình giải theo cách mình hiểu có gì các bạn góp ý thêm nha:
a)
Available = 5 - (1 + 2 + 1) = 1
Need = Max - Allocation
P Allocation MAx Need Available
P1 1 3 2
P2 2 2 0 1
P3 1 3 2

Tìm chuỗi an toàn:
Work>= Need[i] P[i] Allocation[i]
1 0 P2 2
3 2 P1 1
4 2 P3 1

=>Tìm được chuỗi an toàn={P2, P1, P3}
Vậy trang thái hệ thống là an toàn.

b) Yêu cầu xin thêm 2 ổ nữa của p3
Không đủ tài nguyên vì Request3 > Available (2 > 1).
=>Không thể đáp ứng yêu cầu xin thêm 2 ổ nữa của P3.

Mong thầy và các bạn góp ý thêm.

dangvannhan_11h1010085 đã viết:

HoNgocTuan142(I12A) đã viết:

LeXuanHau (I12C) đã viết:
bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

mình xin trả lời câu hỏi của bạn Lê Xuân Hậu, nếu ace thấy chưa đúng hay chưa thỏa đáng thì cứ chém thẳng tay nha.
thực ra tìm chuỗi an toàn rất dễ, tại một thời điểm (ở đây mình xin phép nói là bài toán cho dễ hiểu) có thể có nhiều chuỗi an toàn khác nhau.
Ở ví dụ của thầy trong Slide là thầy đã biết trước kết quả nên thầy chọn ra một chuỗi an toàn tốt nhất đấy thôi, còn nếu muốn dễ hiểu thì bạn cứ duyệt từ trên xuống, nếu thấy tiến trình P_i nào có Need_i <= Work thì bạn đưa vào xét thôi (chú ý: Work đầu tiên cho bằng Available, sau đó Work = Work + Allocation_i của tiến trình P_i vừa được chọn).
nói thì có vẻ khó hiểu để mình làm luôn một ví dụ cho dễ hiểu (tuy hơi lười nhưng vì sự nghiệp kháng chiến... quất tới thôi )
Bài Tập (lấy lại ví dụ của mình trong bài trước)

1/ dùng giải thuật nhà băng để chứng minh trạng thái này an toàn.
2/ xác định có nên đáp ứng yêu cầu <0,4,3,0> của tiến trình P1?

GIẢI:
1/chứng minh trạng thái an toàn
-tính Need = MAX - Allocation

Tiến 		  Need
Trình		A  B  C  D
P0 		0  0  0  0
P1 		0  7  5  0
P2 		1  0  0  2
P3 		0  0  2  0
P4 		0  6  4  2

-Tìm chuỗi an toàn của hệ thống:
trước tiên cho Work = Available. Sau đó duyệt theo bảng Need từ trên xuống nếu thỏa Need<=Work thì chọn. Tiến trình nào chọn rồi hoặc không thỏa thì bỏ qua, kiểm tra tiến trình kế tiếp, đến cuối dãy thì lặp lại.

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P0,P2,P3,P4,P1} => hệ thống tại thời điểm này là an toàn.
-ở đây đã "may mắn" tìm ra được chuỗi an toàn. dừng lại và kết luận trạng thái này an toàn.
-nếu không tìm ra chuỗi an toàn thì ta duyệt theo một thứ tự khác cũng gần như vậy. miễn tìm ra được chuỗi an toàn thỏa mãn tất cả các điều kiện.
****Trên đây là cách duyệt cơ bản. Vì có thể có nhiều chuỗi an toàn khác nhau nên có nhiều cách tìm ra nó. Theo mình nghĩ cách của thầy trong ví dụ ở Slide là khá tối ưu, vì trong những tiến trình thỏa điều kiện Need<= Word thì chọn tiến trình nào có Need thấp và Allocation cao trước. Như thế sẽ có nhiều Availble (Work) dư ra để dễ dàng cấp cho các tiến trình sau hơn. cách này mà không tìm ra được chuỗi an toàn thì không cách nào tìm ra được (Nghĩa là không tồn tại chuỗi an toàn)
Và đây là kết quả của một thứ tự duyệt khác:

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   2   0         P3     0   6   3   2
1  11   5   2 	   0   6   4   2         P4     0   0   1   4
1  11   6   6 	   1   0   0   2         P2     1   3   5   4
2  14  11  10 	   0   7   5   0         P1     1   0   0   0
3  14  11  10 	   0   0   0   0         P0     0   0   1   2

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.
giống như bài viết của bạn Hiển đã tìm ra tất cả các chuỗi an toàn rồi đấy, các bạn có thể tham khảo thêm tại đây
2/Giả sử P1 có yêu cầu mới = (0,4,3,0)
Dựa vào yêu cầu mới của P1 ta có thể khẳng định không nên đáp ứng yêu cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available
Suy ra: (0,4,3,0) Không <= (1,5,2,0)

đó là theo cách hiểu của mình tự "mổ xẻ" từ ví dụ thầy giải trên lớp. các bạn thấy không đúng chỗ nào không đúng hay không thỏa đáng thì góp ý cho mình nha.
tất cả vì sự nghiệp thi đậu

Admin
- Rất Hiểu bài, Nhiệt tình và Tự nhiên !
- Đã sửa đôi chỗ, nhất là Word (từ) => Work (biến tạm, làm việc, trung gian, dùng tích lũy tổng Available+Allocation_i1+Allocation_i2+...)

Chào bạn !
Bạn vui có thể giải thích dùm mình cách duyệt các tiến trình được không?

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

chổ cột Pi vì sao xét thứ tự P0 ->P2->P3->P4->P1 khi mình chưa biết chuỗi an toàn?

Bạn chú ý điều kiện Work>=Needi, Đầu tiên tính Available(Thầy đã nói theo thuật giải nhà băng lúc đầu Work=Available) rồi theo điều kiện Work>=Needi mà xét cái nào trước cái nào sau thôi! Ở trên bạn Tuấn cũng đã giải thích rõ rồi ban xem kỹ lại là hiểu ah!

nguyenthimao_I12A đã viết:

dangvannhan_11h1010085 đã viết:

HoNgocTuan142(I12A) đã viết:

LeXuanHau (I12C) đã viết:
bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

mình xin trả lời câu hỏi của bạn Lê Xuân Hậu, nếu ace thấy chưa đúng hay chưa thỏa đáng thì cứ chém thẳng tay nha.
thực ra tìm chuỗi an toàn rất dễ, tại một thời điểm (ở đây mình xin phép nói là bài toán cho dễ hiểu) có thể có nhiều chuỗi an toàn khác nhau.
Ở ví dụ của thầy trong Slide là thầy đã biết trước kết quả nên thầy chọn ra một chuỗi an toàn tốt nhất đấy thôi, còn nếu muốn dễ hiểu thì bạn cứ duyệt từ trên xuống, nếu thấy tiến trình P_i nào có Need_i <= Work thì bạn đưa vào xét thôi (chú ý: Work đầu tiên cho bằng Available, sau đó Work = Work + Allocation_i của tiến trình P_i vừa được chọn).
nói thì có vẻ khó hiểu để mình làm luôn một ví dụ cho dễ hiểu (tuy hơi lười nhưng vì sự nghiệp kháng chiến... quất tới thôi )
Bài Tập (lấy lại ví dụ của mình trong bài trước)

1/ dùng giải thuật nhà băng để chứng minh trạng thái này an toàn.
2/ xác định có nên đáp ứng yêu cầu <0,4,3,0> của tiến trình P1?

GIẢI:
1/chứng minh trạng thái an toàn
-tính Need = MAX - Allocation

Tiến 		  Need
Trình		A  B  C  D
P0 		0  0  0  0
P1 		0  7  5  0
P2 		1  0  0  2
P3 		0  0  2  0
P4 		0  6  4  2

-Tìm chuỗi an toàn của hệ thống:
trước tiên cho Work = Available. Sau đó duyệt theo bảng Need từ trên xuống nếu thỏa Need<=Work thì chọn. Tiến trình nào chọn rồi hoặc không thỏa thì bỏ qua, kiểm tra tiến trình kế tiếp, đến cuối dãy thì lặp lại.

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P0,P2,P3,P4,P1} => hệ thống tại thời điểm này là an toàn.
-ở đây đã "may mắn" tìm ra được chuỗi an toàn. dừng lại và kết luận trạng thái này an toàn.
-nếu không tìm ra chuỗi an toàn thì ta duyệt theo một thứ tự khác cũng gần như vậy. miễn tìm ra được chuỗi an toàn thỏa mãn tất cả các điều kiện.
****Trên đây là cách duyệt cơ bản. Vì có thể có nhiều chuỗi an toàn khác nhau nên có nhiều cách tìm ra nó. Theo mình nghĩ cách của thầy trong ví dụ ở Slide là khá tối ưu, vì trong những tiến trình thỏa điều kiện Need<= Word thì chọn tiến trình nào có Need thấp và Allocation cao trước. Như thế sẽ có nhiều Availble (Work) dư ra để dễ dàng cấp cho các tiến trình sau hơn. cách này mà không tìm ra được chuỗi an toàn thì không cách nào tìm ra được (Nghĩa là không tồn tại chuỗi an toàn)
Và đây là kết quả của một thứ tự duyệt khác:

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   2   0         P3     0   6   3   2
1  11   5   2 	   0   6   4   2         P4     0   0   1   4
1  11   6   6 	   1   0   0   2         P2     1   3   5   4
2  14  11  10 	   0   7   5   0         P1     1   0   0   0
3  14  11  10 	   0   0   0   0         P0     0   0   1   2

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.
giống như bài viết của bạn Hiển đã tìm ra tất cả các chuỗi an toàn rồi đấy, các bạn có thể tham khảo thêm tại đây
2/Giả sử P1 có yêu cầu mới = (0,4,3,0)
Dựa vào yêu cầu mới của P1 ta có thể khẳng định không nên đáp ứng yêu cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available
Suy ra: (0,4,3,0) Không <= (1,5,2,0)

đó là theo cách hiểu của mình tự "mổ xẻ" từ ví dụ thầy giải trên lớp. các bạn thấy không đúng chỗ nào không đúng hay không thỏa đáng thì góp ý cho mình nha.
tất cả vì sự nghiệp thi đậu

Admin
- Rất Hiểu bài, Nhiệt tình và Tự nhiên !
- Đã sửa đôi chỗ, nhất là Word (từ) => Work (biến tạm, làm việc, trung gian, dùng tích lũy tổng Available+Allocation_i1+Allocation_i2+...)

Chào bạn !
Bạn vui có thể giải thích dùm mình cách duyệt các tiến trình được không?

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

chổ cột Pi vì sao xét thứ tự P0 ->P2->P3->P4->P1 khi mình chưa biết chuỗi an toàn?

Bạn chú ý điều kiện Work>=Needi, Đầu tiên tính Available(Thầy đã nói theo thuật giải nhà băng lúc đầu Work=Available) rồi theo điều kiện Work>=Needi mà xét cái nào trước cái nào sau thôi! Ở trên bạn Tuấn cũng đã giải thích rõ rồi ban xem kỹ lại là hiểu ah!

OK! đồng ý là ngay Pi là P0 trc, nhưng tại sao mình k xét tới P1 rùi tới P2,P3,P4 là lại để P1 cuối, mình dự vào điều j để xét tiếp, mong các bạn giải thix dùm và nếu dc thì đưa ra 1 vd 1 trường hợp k thỏa, thanks!!!

hjhj; vô cùng cám ơn các bạn nhiều.

mong rằng lớp chúng ta sẽ tai qua nạn khỏi

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 giải thuật nhà băng để xác định:
a) Nội dung ma trận Need
b) Trạng thái này có an toàn không?
c) Nếu P1 yêu cầu (0,4,2,0) có thể đáp ứng ngay được không ?

a) Nội Dung của Ma trận Need
Xét tại thời điểm Ti mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] --- Allocation[i]


b) Tìm Chuỗi An Toàn
Available = (1 5 2 0)


tồn tại chuỗi an toàn ={p0,p2,p3,p4,p1}
vậy hiện tại ở thời điểm Ti trạng thái an toàn.
c) ta thấy yêu cầu thêm (0,4,2,0) của P1 thỏa điều kiện:
Request<= Need1; và thỏa điều kiện (0,4,2,0)<=(0,7,5,0)
Request1<=Available suy ra 0,4,2,0 <= 1,5,2,0) --->Available=(1,1,0,0).


Bài tập còn mang tính chất tham khảo,Mong các bạn gần xa chỉ giáo thêm.

vothingocthuy87(I11C) đã viết:Chào mọi người!!!
Mình có 1 bài tập về thuật giải nhà băng, mình có giải thử rùi nhưng không biết đúng không nữa. Mọi người cùng nhau giải nhen.
Bài tập: 1 hệ thống có 5 ổ 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 các vector Allocation = (1,2,1) và max = (3,2,3),dung thuật giải nhà băng để:
A/CM 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 them 2 ổ nữa của p3?

Bài Làm:
a.Chứng minh trạng thái an toàn.

- Hệ có: Available = 5-(1+2+1) = 1
- Need: Max – Allocation:

Tìm chuỗi an toàn:

KL: Tìm được chuỗi an toàn {P2, P1, P3}
b. Xác định có nên đáp ứng hay không yêu cầu xin them 2 ổ nữa của p3?
- Giả sử P3 xin cấp thêm 2 ổ nữa:
Request (3) <= Need(3): 2<=2 (thỏa).
Nhưng:
Request(3) không <= Available do: 2>1 (Không thỏa). => Không thể đáp ứng cấp cho P3 2 ổ nữa.

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

plminhhoangI12A đã viết: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

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:]Giả sử cấp thêm chi P3 1 ổ

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

Admin
Giải và Trình bày tốt !

Thank! bạn nhiều. Nhờ bài giải của bạn mà mình hiểu được thuật giải nhà băng.
Mình đang đau đầu thuật giải SJFS có tiếm quyền, ngồi ngâm cả buổi mà chẳng hỉu gì hết. hu..hu..

-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)

[img]url=http://www.upanh.com/upanh_new_bitmap_image/v/2rh0ct0eceq.htm][/url][/img]