Thảo luận Bài 8: Thuật giải Nhà băng

Tránh kẹt khoá (Deadlock) bằng thuật giải Nhà băng. Giải các bài tập liên quan.

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.

Thuật giải nhà băng
Trạng thái mới:
Đang giữ Need Hệ có
A B C A B C A B C
P0 0 1 0 7 4 3 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

Available=(10,5,7)-(8,2,7)=(2,3,0)
WORK NEED Pi ALLOCATION
A B C A B C A B C
2 3 0 0 2 0 P1 3 0 2
5 3 2 0 1 1 P3 2 1 1
7 4 3 7 4 3 P0 0 1 0
7 5 3 6 0 0 P2 3 0 2
10 5 5 4 3 1 P4 0 0 2

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


P/S : Không biết mình post ảnh các bạn có thấy ko? reply cho mình biết nhé

Dữ liệu : – có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay )
- 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)
=>Đây là các loại tiền mà nhà băng có.
- Tại thời điểm To:




Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation)
Tổng :7 2 5

Chú ý :
- Allocation tổng số các loại tiền mà các công ty đang có
- Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có
- Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 )

Ta có : Need = Max – Allocation
=>Số loại tiền tối đa mà các công ty có thể vay thêm.
Ta có ma trận sau : Need



Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước.
Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có.



Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,2,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau:





Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu.
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

P1 muốn tăng tiền vay (1,0,2) thì phải thỏa điều kiện:

1 – Request (yêu cầu) <= Need vì (1,0,2) <= (1,2,2) // Thỏa điều kiện
2- Request (yêu cầu) <= Available vì (1,0,2) <= (3,3,2) // Thỏa điều kiện

Ta lại làm lại từ đầu và xét trạng thái mới
Ta có:
Bảng Max sẽ được thay bằng bảng Need (Vì Need đã là giá trị lớn nhất để có thể tồn tại chuổi an toàn).
Allocation của P1 sẽ đổi do cộng đồn giá trị Allocation ban đầu với giá trị Allocation mới:
(2,0,0) + (1,0,2) = (3,0,2)

Need của P1 cũng thay đổi do điều kiện xét ta có:
Need (P1)[mới] = Need(P1)[cũ] – Request = (1,2,2) – (1,0,2) = (0,2,0)
Available cũng thay đổi do:
Available (mới) = Available (củ) – Request = (3,3,2,) – (1,0,2) = (2,3,0)








Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >
Các bạn chú ý là việc tìm chuỗi trên ko chỉ có tính duy nhất nhé

Bài Tập : 1 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 ( Số Ổ) Tối Đa cần số ổ
P1 5 10
P2 2 4
P3 2 9
Dùng Thuật giải nhà băng để:
a) Chứng minh trạng thái này là 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 ?
Các bạn giải bài này thử mình k hiểu lắm

các bạn cho mình hỏi(bài giải trên lớp)!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

VoHoangTrung (113A) đã viết:Bài Tập : 1 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 ( Số Ổ) Tối Đa cần số ổ
P1 5 10
P2 2 4
P3 2 9
Dùng Thuật giải nhà băng để:
a) Chứng minh trạng thái này là 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 ?
Các bạn giải bài này thử mình k hiểu lắm

a)
-Hệ có :Available=12-(5+2+2)=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work Needi Pi Allocation
3 2 P2 2
5 5 P1 5
10 7 P3 2

-Tồn tại chuỗi an toàn T0={P2,P1,P3}
Vậy trạng thái tại thời điểm T0 là an toàn.
k biết đúng hem

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

mình cũng nghĩ là vậy mà sợ sai nên lên đây hỏi và chờ thầy lên tiếng cho chắc ăn hơn!!
thầy xác nhận giúp em với

Admin
- Bạn Trung nói đúng: Tiến trình Pi nào thoả điều kiện Needi ≤ Work (ban đầu Work=Available) thì chọn. Do P1 và P3 đều thích hợp => Chọn anh nào cũng được ! Trang 8.26 của Giáo trình chọn P1. Em thử chọn P3 xem sao !
- Em ghi P1=(1,2,2) và P3=(0,1,1) là sai ! Đúng phải là: Need1=(1,2,2) và Need3=(0,1,1)

VoHoangTrung (113A) đã viết:Bài Tập : 1 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 ( Số Ổ) Tối Đa cần số ổ
P1 5 10
P2 2 4
P3 2 9
Dùng Thuật giải nhà băng để:
a) Chứng minh trạng thái này là 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 ?
Các bạn giải bài này thử mình k hiểu lắm

a.cái này đơn giản hơn bài của thầy nè ^^

Available=12-(5+2+2)=3

Need=Max-Allocation
P1=5
P2=2
P3=7

work	Need	Pi	Allocation(i)
3	2	P2	2
5	5	P1	5
10	7	P3	2

trạng thái an toàn: P2,P1,P3

b.ko bít làm!!nhờ mọi người giúp

VoHoangTrung (113A) đã viết:Bài Tập : 1 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 ( Số Ổ) Tối Đa cần số ổ
P1 5 10
P2 2 4
P3 2 9
Dùng Thuật giải nhà băng để:
a) Chứng minh trạng thái này là 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 ?
Các bạn giải bài này thử mình k hiểu lắm

b)
Giả sử P3 bây giờ nên yêu cầu mới là 1 ổ
yêu cầu này thỏa mãn các điều kiện
1.request3<=need3 vì 1 <= 7 ( need 3= 9-2)
2.request3<= Available vì 1<=3 ( available = 12-(5+2+2)=3)
Trạng thái mới
Đang giữ Need Hệ Có
P1 5 5 3
P2 2 2
P3 3 6
Work NEEDi Pi Allocation
2 2 P2 2
4 5(vipham) P1 5
k có chuỗi an toàn nên k đáp ứng yêu cầu xin thêm 1 ổ nữa của P3
Neeb = Max - Allocation

LeHuynhChiTam (113A) đã viết:

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

mình cũng nghĩ là vậy mà sợ sai nên lên đây hỏi và chờ thầy lên tiếng cho chắc ăn hơn!!
thầy xác nhận giúp em với

Hôm qua mình cũng suy nghĩ như bạn cứ ngồi mò hoài nhưng lúc sau nghe mọi người nói là có thể có nhiều Chuỗi An Toàn nên cũng yên tâm rồi

- Có 5 tiến trình { P₀, P₁, P₂, P₃, P₄ }
- Có 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)
- Hệ có: Available = (10, 5, 7) - (8, 2, 7) = (2, 3, 0)

- Ma trận Need = Max - Allocation:

- Available = (2, 3, 0)

- Tồn tại chuổi an toàn ( P₁, P₃, P₄, P₀, P₂)
- Vậy trạng thái tại thời điểm T₀ là an toàn.

TranTuanVu (113A) đã viết:

LeHuynhChiTam (113A) đã viết:

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

mình cũng nghĩ là vậy mà sợ sai nên lên đây hỏi và chờ thầy lên tiếng cho chắc ăn hơn!!
thầy xác nhận giúp em với

Hôm qua mình cũng suy nghĩ như bạn cứ ngồi mò hoài nhưng lúc sau nghe mọi người nói là có thể có nhiều Chuỗi An Toàn nên cũng yên tâm rồi

Cái này bạn tìm được hết Thầy sẽ cho bạn 1 điểm siêng năng nữa đó, nếu bạn có đủ thời gian

LeHuynhChiTam (113A) đã viết:

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

mình cũng nghĩ là vậy mà sợ sai nên lên đây hỏi và chờ thầy lên tiếng cho chắc ăn hơn!!
thầy xác nhận giúp em với

Admin
- Bạn Trung nói đúng: Tiến trình Pi nào thoả điều kiện Needi ≤ Work (ban đầu Work=Available) thì chọn. Do P1 và P3 đều thích hợp => Chọn anh nào cũng được ! Trang 8.26 của Giáo trình chọn P1. Em thử chọn P3 xem sao !
- Em ghi P1=(1,2,2) và P3=(0,1,1) là sai ! Đúng phải là: Need1=(1,2,2) và Need3=(0,1,1)

Lúc học trên lớp em cũng chưa hiểu rõ khi Tiến trình Pi thoả điều kiện Needi ≤ Work thì sẽ chọn anh nào trước . Cám ơn Thầy và bạn Trung đã giải thích.

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

Chọn cái nào trước cũng đc miễn sao work>=need.Vi vậy mới có nhiều chuỗi an toàn :d

LeHuynhChiTam (113A) đã viết:

VoHoangTrung (113A) đã viết:

LeHuynhChiTam (113A) đã viết:các bạn cho mình hỏi!!
Ở slide 8.26 mình thắc mắc như sau:
thầy nói khi xét thì work>=need mới chọn !! như vậy khi đang xét lúc này Available=(3,3,2) còn P1=(1,2,2) và P3=(0,1,1) nghiã là P1 và P3 cùng nhỏ hơn Available vậy tại sao lại chọn P1 trước ??

Mình chọn cái nào trước cũng dc bạn ak vì Chuỗi an toàn có nhiều chuỗi chứ k nhất thiết fai là theo mình hiểu là như vậy

mình cũng nghĩ là vậy mà sợ sai nên lên đây hỏi và chờ thầy lên tiếng cho chắc ăn hơn!!
thầy xác nhận giúp em với

Admin
- Bạn Trung nói đúng: Tiến trình Pi nào thoả điều kiện Needi ≤ Work (ban đầu Work=Available) thì chọn. Do P1 và P3 đều thích hợp => Chọn anh nào cũng được ! Trang 8.26 của Giáo trình chọn P1. Em thử chọn P3 xem sao !
- Em ghi P1=(1,2,2) và P3=(0,1,1) là sai ! Đúng phải là: Need1=(1,2,2) và Need3=(0,1,1)

Em cám ơn thầy!!

chúng ta có 12 ổ băng từ

Tiến Trình	Đã Cấp	Tối Đa Cần(MAX)
P1	5	10
P2	2	4
P3	2	9

câu 1:dùng giải thuật nhà băng để chứng minh trạng thái này là an toàn.
câu 2:xác định có nên đáp ứng hay không khi P₃ xin thêm 1 ổ nữa

Giải


Câu 1:

Tiến Trình	Đang Giữ	MAX	Need	Hệ Có
P1	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+2)=3
P2	2	4	(MAX- ĐangGiữ)=4-2=2
P3	2	9	(MAX- ĐangGiữ)=9-2=7

Work >=	Need	Pi	Allocation
3	2	P2	2
5	5	P1	5
10	7	P3	2

chuỗi an toàn là:{P₂,P₁,P₃}
vậy trạng thái này là an toàn(điều cần chứng minh)

Câu 2:
giả sử P₃ xin thêm một ổ nữa
thỏa 2 điều kiện:
request₃<= Need vì 1< 7
request₃<= Available vì 1< 3
Trạng thái mới

Tiến Trình	Đang Giữ	MAX	Need	Hệ Có
P1	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+3)=2
P2	2	4	(MAX- ĐangGiữ)=4-2=2
P3	3	9	(MAX- ĐangGiữ)=9-3=6

[tr]

Work >=	Need	Pi	Allocation
2 >=	2	P2	2
4	?	?	?

P₁ và P₃ ko thỏa điều kiện Work >= NEED.không xác định được chuỗi an toàn.trạng thái này không an toàn.nên không thể cấp thêm cho P₃

thầy và các bạn nhận xét dùm em ạ



Admin (góp ý trước khi bạn Thành sửa)
- Đề bài không đầy đủ: Thiếu số lượng tài nguyên ban đầu là 12.
- Với Câu 2:
Đúng phải là: request₃<= Available vì 1< 3
Sau khi xác định được P₂ đầu tiên trong chuỗi, thấy P₁ không đáp ứng được thì phải xét thêm P₃ chứ?

Sở dĩ thuật giải này có tên là "thuật giải nhà băng" vì nguyên tắc của nó cũng giống ngân hàng: Cho vay và thu hồi vốn làm sao để đừng lâm vào tình trạng không thể cho ai vay và cũng không thể thu hồi vốn từ ai cả. Kể ra thì điều phối máy tính vẫn dễ vì ngoài thực tế, có nhiều doanh nghiệp lâm vào tình trạng không thể trả vốn đã vay đúng hạn và có thể cần vốn vay sớm hơn hoặc không cần vay vốn thêm.

Dữ liệu : - có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay )
- 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)
=>Đây là các loại tiền mà nhà băng có.
- Tại thời điểm To:
Đang giữ(Allocation) Max Hệ có (Available)
A B C A B C A B C
3 3 2
Po 0 1 0 7 5 3
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

Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation)
Tổng :7 2 5

Chú ý :
- Allocation tổng số các loại tiền mà các công ty đang có
- Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có
- Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 )
Ta có : Need = Max – Allocation
=>Số loại tiền tối đa mà các công ty có thể vay thêm.
Ta có ma trận sau : Need
A B C
P0 7 4 3 (7,5,3) – (0,1,0)
P1 1 2 2 (3,2,2) – (2,0,0)
P2 6 0 0 (9,0,2) - (3,0,2)
P3 0 1 1 (2,2,2) - (2,1,1)
P4 4 3 1 (4,3,3) – (0,0,2)

Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước.
Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có.
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0
Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,2,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 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 6 0 0 P2 3 0 2
10 4 7 7 4 3 P0 0 1 0

Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

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 phát(số ổ băng) Tối đa cần(số ổ băng)
P1 5 10
P2 2 4
P3 2 9

Dùng thuật giải Nhà Băng để xác định trạng thái này có an toàn hay không?

Ta có
- Available=12-(5+2+2)=3
- Need=Max-Allocation
P[i] Allocation Max Need Available
P1 5 10 5 3
P2 2 4 2 3
P3 2 9 7 3

Xét tại thời điểm Ti
Work >= Need[i] P[i] Allocation[i]
3 2 P2 2
5 5 P1 5
10 7 P3 2

Vậy tồn tại chuỗi an toàn.Suy ra trạng thái hệ thống ở thời điểm Ti là an toàn.

em đã sửa lại nhưng câu 2 em vẫn chưa hiểu nên kết luận như thế nào.thầy giúp em với

Admin
Em sửa lời giải Câu 2 như vậy là sai, vì chỉ được dừng ở dòng 2 thôi (tại đây nếu P₁ không đáp ứng được thì xét P₃ xem sao, nếu P₃ vẫn không thoả thì kết luận là không tồn tại chuỗi an toàn, còn nếu P₃ thích hợp thì tiếp tục thuật giải và xét tiếp P₁ ở dòng 3).

Thưa Thầy! Em có chỗ này chưa rõ lắm mong thầy giúp em với ạ.

Giả sử bài toán có 5 tiến trình là P0, P1, P2, P3, P4
Và em bắt đầu xét chuỗi có an toàn hay không từ P1 nhưng P0, P2, P3, P4 đều không thỏa điều kiện thì em có thể kết luận là không tồn tại chuỗi an toàn được không ạ. Hay là em phải xét chuỗi lại từ đầu với P0 hoặc P2 hoặc P3 hay P4 gì ạ?

Em xin cảm ơn Thầy!

Admin
- Cái gì cũng nên cụ thể: Nêu bài toán cụ thể và bắt tay vào giải rồi đưa lên, vướng đâu hỏi đấy !
- Nếu chọn được P1 ở đầu chuỗi mà không tìm tiếp được nữa thì khẳng định ngay là không tồn tại chuỗi an toàn ! Vì đi theo hướng khác cũng sẽ bị "tắc" ! Thuật giải Nhà băng hay chính ở chỗ này !

Dạ em xin cảm ơn Thầy!
Giờ chưa gặp bài như vậy nhưng em sợ khi thi lại gặp mà không rõ rồi phải chọn lại rồi mất thời gian cho câu đó quá nhiều. Em cảm ơn Thầy ạ!

Admin
Em nêu vấn đề đúng ! Tốt !

NguyenThanhHien (113A) đã viết:Thưa Thầy! Em có chỗ này chưa rõ lắm mong thầy giúp em với ạ.

Giả sử bài toán có 5 tiến trình là P0, P1, P2, P3, P4
Và em bắt đầu xét chuỗi có an toàn hay không từ P1 nhưng P0, P2, P3, P4 đều không thỏa điều kiện thì em có thể kết luận là không tồn tại chuỗi an toàn được không ạ. Hay là em phải xét chuỗi lại từ đầu với P0 hoặc P2 hoặc P3 hay P4 gì ạ?

Em xin cảm ơn Thầy!

Admin
- Cái gì cũng nên cụ thể: Nêu bài toán cụ thể và bắt tay vào giải rồi đưa lên, vướng đâu hỏi đấy !
- Nếu chọn được P1 ở đầu chuỗi mà không tìm tiếp được nữa thì khẳng định ngay là không tồn tại chuỗi an toàn ! Vì đi theo hướng khác cũng sẽ bị "tắc" ! Thuật giải Nhà băng hay chính ở chỗ này !

câu hỏi của bạn rất bổ ích!!like