Thảo luận Bài 8

hoxuanvu_I12A đã viết:Giải thích thuật giải Nhà băng
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 >

NgoPhuQuoc_I12C đã 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

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

[tr]

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.

LeXuanHau (I12C) đã viết:

NgoPhuQuoc_I12C đã 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

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

[tr]

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.

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

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

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

   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

   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

TranHuyCuong17 (I12A) đã viết:

• Mỗi tiến trình (process) phải khai báo số lượng tối đa tài nguyên mỗi loại mà process đó cần để hoàn tất công việc.
  Khi tiến trình yêu cầu một tài nguyên thì có thể phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn
  Khi t

• Vì hệ số là 3,ta chọn need của P2 là 2(thỏa dk Work=>Need(3>2)).

• Sau khi P2 thực hiện xong,nó trả tài nguyên cho hệ thống.Lúc này tài nguyên hệ thống đang có là (3+2=5).Ta lấy need của P1 và P3 so với Work thì thầy need của P1 thỏa dk(Work=>Need(5=>5)).

• Sau khi P1 thực hiện xong,tài nguyên hệ thống đang có là 10.Xét need của P3 là 7 thỏa đk(10>7).

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.

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

thailongI12C đã viết:

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(Đã được cấp)

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

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

Giải thích:

• Vì hệ số là 3,ta chọn need của P2 là 2(thỏa dk Work=>Need(3>2)).

• Sau khi P2 thực hiện xong,nó trả tài nguyên cho hệ thống.Lúc này tài nguyên hệ thống đang có là (3+2=5).Ta lấy need của P1 và P3 so với Work thì thầy need của P1 thỏa dk(Work=>Need(5=>5)).

• Sau khi P1 thực hiện xong,tài nguyên hệ thống đang có là 10.Xét need của P3 là 7 thỏa đk(10>7).

=>Tìm được 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

-Xét điều kiện:
Request(3)<=Need(3) vì 1<7
Request(3)<=Need(3) vì 1<3
Hệ có:Available=12-(5+2+3)=2
Need=Max-Allocation

	Need
P1	10-5=5
P2	4-2=2
P3	9-3=6

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

Do need của P1 không thỏa dk vì Work=>Không tồn tại chuỗi an toàn.
Kết luận:Vậy trạng thái ở thời điểm đầu là an toàn,không thể cấp thêm cho P3 vì có thể gây ra Deadlock.

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

• Need=Max-Allocation
  

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

• Request(3)<=Available vì 1<=3
  

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

• Need=Max-Allocation
  

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

huynhthao.hc11th2a đã viết:

thailongI12C đã viết:

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(Đã được cấp)

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

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

Giải thích:

• Vì hệ số là 3,ta chọn need của P2 là 2(thỏa dk Work=>Need(3>2)).

• Sau khi P2 thực hiện xong,nó trả tài nguyên cho hệ thống.Lúc này tài nguyên hệ thống đang có là (3+2=5).Ta lấy need của P1 và P3 so với Work thì thầy need của P1 thỏa dk(Work=>Need(5=>5)).

• Sau khi P1 thực hiện xong,tài nguyên hệ thống đang có là 10.Xét need của P3 là 7 thỏa đk(10>7).

=>Tìm được 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

-Xét điều kiện:
Request(3)<=Need(3) vì 1<7
Request(3)<=Need(3) vì 1<3
Hệ có:Available=12-(5+2+3)=2
Need=Max-Allocation

	Need
P1	10-5=5
P2	4-2=2
P3	9-3=6

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

Do need của P1 không thỏa dk vì Work=>Không tồn tại chuỗi an toàn.
Kết luận:Vậy trạng thái ở thời điểm đầu là an toàn,không thể cấp thêm cho P3 vì có thể gây ra Deadlock.

nho bai ban minh hieu thêm.Thanks nha

• Khi 1 tiến trình yêu cầu tài nguyên, HĐH phải xác định việc cấp phát TN đó có đảm bảo hệ thống trong Trạng thái an toàn hay không. Nếu an toàn, tiến trình nhận được tài nguyên cần. Nếu không an toàn, tiến trình phải chờ.

• Trạng thái hệ thống được gọi là An toàn nếu 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

• Cấp phát tài nguyên theo chuỗi an toàn sẽ không dẫn đến Deadlock.

• Nếu không tồn tại chuỗi an toàn, trạng thái hệ thống gọi là Không an toàn.

• Deadlock là trạng thái không an toàn nhưng không phải tất cả các trạng thái không an toàn là trạng thái Deadlock.