Thảo luận Bài 8

PhamThiHoa-I91C đã viết:

nguyenquoctruong (I11C) đã viết:

DaoQuangSieu (I11C) đã viết:

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Chào Thầy và các bạn !!
Theo ý kiến của mình: Trong quá trình xét các tiến trình tìm chuỗi an toàn, nếu tiến trình nào không thỏa điều kiện thì ta sẽ xác định ngay không tồn tại chuỗi an toàn. Ví dụ: p1 đã thỏa điều kiện nhưng khi xét đến p2 thì p2 không thỏa điều kiện thì ta có thể không xét các tiến trình khác và kết luận ngay đây không tồn tại chuỗi an toàn.
Không biết như vậy có được không, mong Thầy và các bạn góp ý.

Theo mình thì chưa được. Tìm chuổi an toàn là phải xét từ đầu đến cuối. ví dụ có (P1, P2, P3, P4) lần lược xét P1 thỏa, xét tiếp P2 không thỏa, tiếp tục xét P3, xét P4. xét hết, cuối cùng mới kết luận có tồn tại chuổi an toàn hay không.

Chào bạn quốc trường, mình nghĩ là thầy nói như thế rất rõ đó bạn à, những lời thầy nói đều giống ý của bạn đó, vì bạn chưa thật sự hiểu ý của thầy thôi, (ý của bạn cũng đúng)

Mình cũng xin góp ý thêm là thế này, tìm chuỗi an toàn có nghĩa là xét tất cả các tiến trình nếu thoả đk thì có chuỗi an toàn, chứ kô nhất thiết phải theo thứ tự p1, p2, ....
Chuỗi an toàn khác với chuỗi "thứ tự" an toàn bạ àh, cho nên xét p1, qua p2 mà không thoả thì bạn có thể chuyển qua p3 hay p4 hay pn nào đó cũng được miễn là thoả đk, sau đó trở lại p2 vẫn ok. Vì thế trên lớp Thày thường nói là có thể có rất nhiều chuỗi an toàn mà nhưng chỉ cần tìm 1 là okei rồi.

ThanhThao04(I11C) đã viết:

ngocquynh2091(i11C) đã viết:1 hệ thống có 3 máy quét hình và 2 tiến trình P1 và P2, với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng vector Allocation (1,1) và max (2,2). Dùng giải thuật nhà băng để:
a) CM trạng thái an toàn này.
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 của P2

Có bạn nào hiểu bài tập này không? Mình chưa hiểu đề bài tập dạng này.
Giúp mình nhé. Tks.

Bài giải

a/ Ta có: Available = 3-(1+1)=1
Need[i]=Max[i]-Allocation[i]=(2,2)-(1,1)=(1,1)
Ta được bảng tổng quát sau:

Tìm chuỗi an toàn (Xét tại thời điểm Ti)

Kết luận: Tồn tại chuỗi an toàn = {P1,P2}
Vậy trạng thái ở thời điểm Ti là an toàn
b/ Xét điều kiện: Request[2]<=Need[2] vì 1<=1
Request[2]<=Available vì 1<=1
Lúc này với Available=3-(1+2)=0
Need[i]=Max[i]-Allocation[i]=(2,2)-(1,2)=(1,0)
Ta có trạng thái mới

Xét tại thời điểm Ti

Kết Luận: Tồn tại chuỗi an toàn ={P2,P1}
Vậy trạng thái ở Ti là an toàn
--> Do vậy ta có thể cấp thêm 1 máy của P2 tại thời điểm này.
Không biết mình làm vậy có đúng không, các bạn góp ý với nha.

yeah! bạn làm đúng rồi đó

ThanhThao04(I11C) đã viết:

nguyenthithuylinh (I11C) đã viết:

NguyenThiThanhThuy(I11C) đã viết:dùng thuật giải nhà băng chứng minh trạng thái này an toàn
tiến trình Được cấp(ổ đĩa) tối đa cần(ổ đĩa)
P1 5 10
P2 2 4
P3 2 9


-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7
work ≥ Need Pi Allocation(i)
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.

P2 Yêu cầu cấp thêm 1 ổ đĩa thì :

tiến trình Được cấp(ổ đĩa) tối đa cần(ổ đĩa)
P1 5 10
P2 3 4
P3 2 9


-Available=12-10=2
-Need=Max-Allocation
P1=10-5=5
P2=4-3=1
P3=9-2=7


-Không Tồn tại chuỗi an toàn
Yêu cầu thêm 1 ổ đĩa của p2 không được đáp ứng vì không an toàn .

Mình thấy bài này là tìm được trạng thái an toàn mà bạn, với bạn bạn làm kẻ ô thì mọi người dễ tham khảo hơn.

T góp ý sau
Thứ nhất đề bài của bạn không nói rõ 1 hệ thống có bao nhiêu ổ băng từ?
Thứ 2 là bài bạn trình bày không rõ cho lắm.
Theo bài bạn trình bày thì hệ thống này có 12 ổ băng từ và 3
tiến trình với trạng thái cấp phát tài nguyên ở thời điểm thể hiện bằng các
vecto: Allocation=(5,2,2) và Max=(10,4,9)
Mình làm lại sau, bạn tham khảo nha.
Ta có bảng:



Xét tại thời điểm Ti






Tồn tại chuỗi an toàn {P2,P1,P3}
Vậy trạng thái ở thời điểm Ti là an toàn.
b/ P2 yêu cầu cấp thêm 1 ổ đĩa
Xét điều kiện:
Request [2]<=Need [2] vì 1<=2
Request [2]<=Available vì 1<=3
Ta có trạng thái mới sau:





Xét tại thời điểm Ti:



Tồn tại chuỗi an toàn {P2,P1,P3}
Vậy trạng thái ở thời điểm Ti là an toàn.
Do vậy ta có thể cấp thêm 1 máy của P2 tại thời điểm này.

chào bạn (I11C), bạn giải chính xác rồi, mình cũng giải ra kết quả giống bạn

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.



Bài 2: Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work	≥	Need	Pi		Allocation(i)
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.



Bai 3:



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 T_i 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=<p1,p2>.
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=<p2,p1>
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

PhamVanNgo(I11C) đã viết:

PhamThiHoa-I91C đã viết:

nguyenquoctruong (I11C) đã viết:

DaoQuangSieu (I11C) đã viết:

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Chào Thầy và các bạn !!
Theo ý kiến của mình: Trong quá trình xét các tiến trình tìm chuỗi an toàn, nếu tiến trình nào không thỏa điều kiện thì ta sẽ xác định ngay không tồn tại chuỗi an toàn. Ví dụ: p1 đã thỏa điều kiện nhưng khi xét đến p2 thì p2 không thỏa điều kiện thì ta có thể không xét các tiến trình khác và kết luận ngay đây không tồn tại chuỗi an toàn.
Không biết như vậy có được không, mong Thầy và các bạn góp ý.

Theo mình thì chưa được. Tìm chuổi an toàn là phải xét từ đầu đến cuối. ví dụ có (P1, P2, P3, P4) lần lược xét P1 thỏa, xét tiếp P2 không thỏa, tiếp tục xét P3, xét P4. xét hết, cuối cùng mới kết luận có tồn tại chuổi an toàn hay không.

Chào bạn quốc trường, mình nghĩ là thầy nói như thế rất rõ đó bạn à, những lời thầy nói đều giống ý của bạn đó, vì bạn chưa thật sự hiểu ý của thầy thôi, (ý của bạn cũng đúng)

Mình cũng xin góp ý thêm là thế này, tìm chuỗi an toàn có nghĩa là xét tất cả các tiến trình nếu thoả đk thì có chuỗi an toàn, chứ kô nhất thiết phải theo thứ tự p1, p2, ....
Chuỗi an toàn khác với chuỗi "thứ tự" an toàn bạ àh, cho nên xét p1, qua p2 mà không thoả thì bạn có thể chuyển qua p3 hay p4 hay pn nào đó cũng được miễn là thoả đk, sau đó trở lại p2 vẫn ok. Vì thế trên lớp Thày thường nói là có thể có rất nhiều chuỗi an toàn mà nhưng chỉ cần tìm 1 là okei rồi.

các bạn có ai hiểu trả lời dùm mình câu b trong bài thuật giải nhà băng xét một điều kiện thỏa hay cà hai điều kiện thỏa mới đươc.

Duongthithanhhuynh (I11C) đã viết:

PhamVanNgo(I11C) đã viết:

PhamThiHoa-I91C đã viết:

nguyenquoctruong (I11C) đã viết:

DaoQuangSieu (I11C) đã viết:

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Chào Thầy và các bạn !!
Theo ý kiến của mình: Trong quá trình xét các tiến trình tìm chuỗi an toàn, nếu tiến trình nào không thỏa điều kiện thì ta sẽ xác định ngay không tồn tại chuỗi an toàn. Ví dụ: p1 đã thỏa điều kiện nhưng khi xét đến p2 thì p2 không thỏa điều kiện thì ta có thể không xét các tiến trình khác và kết luận ngay đây không tồn tại chuỗi an toàn.
Không biết như vậy có được không, mong Thầy và các bạn góp ý.

Theo mình thì chưa được. Tìm chuổi an toàn là phải xét từ đầu đến cuối. ví dụ có (P1, P2, P3, P4) lần lược xét P1 thỏa, xét tiếp P2 không thỏa, tiếp tục xét P3, xét P4. xét hết, cuối cùng mới kết luận có tồn tại chuổi an toàn hay không.

Chào bạn quốc trường, mình nghĩ là thầy nói như thế rất rõ đó bạn à, những lời thầy nói đều giống ý của bạn đó, vì bạn chưa thật sự hiểu ý của thầy thôi, (ý của bạn cũng đúng)

Mình cũng xin góp ý thêm là thế này, tìm chuỗi an toàn có nghĩa là xét tất cả các tiến trình nếu thoả đk thì có chuỗi an toàn, chứ kô nhất thiết phải theo thứ tự p1, p2, ....
Chuỗi an toàn khác với chuỗi "thứ tự" an toàn bạ àh, cho nên xét p1, qua p2 mà không thoả thì bạn có thể chuyển qua p3 hay p4 hay pn nào đó cũng được miễn là thoả đk, sau đó trở lại p2 vẫn ok. Vì thế trên lớp Thày thường nói là có thể có rất nhiều chuỗi an toàn mà nhưng chỉ cần tìm 1 là okei rồi.

các bạn có ai hiểu trả lời dùm mình câu b trong bài thuật giải nhà băng xét một điều kiện thỏa hay cà hai điều kiện thỏa mới đươc.

Cả hai !!!!???

các bạn có ai hiểu trả lời dùm mình câu b trong bài thuật giải nhà băng xét một điều kiện thỏa hay cà hai điều kiện thỏa mới đươc

Theo mình nghĩ thì là thỏa cả 2.

DoThiNgocNuong (I11C) đã viết:
các bạn có ai hiểu trả lời dùm mình câu b trong bài thuật giải nhà băng xét một điều kiện thỏa hay cà hai điều kiện thỏa mới đươc

Theo mình nghĩ thì là thỏa cả 2.

Uhm phai cả 2 luôn bạn,nhưng mà hình như cũng chưa chắc đúng
mình phải tìm xem hệ thông có trạng thái an toàn ko nữa lúc đó mới chắc chắn Nương àh
if tồn tại 1 chuỗi an toàn bất kỳ thì ok
else....
hơi muộn nhưng hy zong giúp đc ai đó

thanks,
regards

Điều kiện xuất hiện tắc nghẽn :
1 . Có sử dụng tài nguyên không thể chia sẻ .
2. Sự chiếm giữ và yêu cầu tài nguyên thêm .
3. Không thu hồi tài nguyên từ tiến trình đã sử dụng ,
4. Tồn tại 1 chu kỳ trong đồ thị cấp phát tài nguyên .
5. Có 2 tiến trình chờ đợi lẫn nhau : tiến trình này đang chờ được cấp phá tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại .
=> Khi có 4 điều kiện này thì tắc nghẽn xảy ra . Nếu thiếu 1 trong 4 điều kiện trên thì không có tắc nghẽn.

vd : 5 nhà triết học cùng ngồi vào bàn ăn để thưởng hức món mì ý . Để dùng bữa thì mỗi người cần dùng 2 cái nĩa mà trên bàn thì chỉ có 5 nĩa xếp xen kẽ 5 đĩa mì , Vậy nếu 5 người cùng ăn 1 lúc thì sẽ xảy ra hiện tượng tranh chấp gây ra hiện tượng .==> Hiên tượng Deadlock

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

Duongthithanhhuynh (I11C) đã viết:

PhamVanNgo(I11C) đã viết:

PhamThiHoa-I91C đã viết:

nguyenquoctruong (I11C) đã viết:

DaoQuangSieu (I11C) đã viết:

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Chào Thầy và các bạn !!
Theo ý kiến của mình: Trong quá trình xét các tiến trình tìm chuỗi an toàn, nếu tiến trình nào không thỏa điều kiện thì ta sẽ xác định ngay không tồn tại chuỗi an toàn. Ví dụ: p1 đã thỏa điều kiện nhưng khi xét đến p2 thì p2 không thỏa điều kiện thì ta có thể không xét các tiến trình khác và kết luận ngay đây không tồn tại chuỗi an toàn.
Không biết như vậy có được không, mong Thầy và các bạn góp ý.

Theo mình thì chưa được. Tìm chuổi an toàn là phải xét từ đầu đến cuối. ví dụ có (P1, P2, P3, P4) lần lược xét P1 thỏa, xét tiếp P2 không thỏa, tiếp tục xét P3, xét P4. xét hết, cuối cùng mới kết luận có tồn tại chuổi an toàn hay không.

Chào bạn quốc trường, mình nghĩ là thầy nói như thế rất rõ đó bạn à, những lời thầy nói đều giống ý của bạn đó, vì bạn chưa thật sự hiểu ý của thầy thôi, (ý của bạn cũng đúng)

Mình cũng xin góp ý thêm là thế này, tìm chuỗi an toàn có nghĩa là xét tất cả các tiến trình nếu thoả đk thì có chuỗi an toàn, chứ kô nhất thiết phải theo thứ tự p1, p2, ....
Chuỗi an toàn khác với chuỗi "thứ tự" an toàn bạ àh, cho nên xét p1, qua p2 mà không thoả thì bạn có thể chuyển qua p3 hay p4 hay pn nào đó cũng được miễn là thoả đk, sau đó trở lại p2 vẫn ok. Vì thế trên lớp Thày thường nói là có thể có rất nhiều chuỗi an toàn mà nhưng chỉ cần tìm 1 là okei rồi.

các bạn có ai hiểu trả lời dùm mình câu b trong bài thuật giải nhà băng xét một điều kiện thỏa hay cà hai điều kiện thỏa mới đươc.

Phải thỏa cả 2 điều kiện mới xét đến có chuỗi an toàn k nữa, nếu như chỉ thỏa 1 đk thì k cần xét đến chuỗi an toàn mà có thể đi đến kết luận là trạng thái k an toàn, bạn có thể kham khảo ở Slide 8.28