Re: Thảo luận Bài 8

LE DUY NHAT AN (I91C) 9/11/2011, 23:02

BuiVanHoc(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.

Mình cũng đóng góp thêm lời giải coi như học lại bài vậy có gì các bạn góp ý nhé:

Câu a:

- Ta có Avialable = 3 - (1+1)=1
- Need = Max - Allocation
Ta có bảng sau:
P Allocation Max Need Available
P1 1 2 1 1
P2 1 2 1

Từ đây ta đi tìm chuỗi an toàn:
Work>= Need[i] P[i] Allocation[i]
1 1 P2 1
2 1 P1 2

- Kết luận: Tồn tại chuỗi an toàn: {P2,P1}( nếu xét cách khác cũng có thêm chuỗi an toàn là: {P1,P2})

Câu b:
Tại thời điểm T P2 yêu cầu cung cấp thêm một máy scan nữa:

Ta xét 2 đều kiện:

Request<=Avialable ta có 1<=1 đúng
Request<=Need ta có 1<=1 đúng

Khi này Allocation[2] của P2= Allocation[2]+Request=1+1=2
Và Need[2] của P2=Need[2]-Request= 1-1=0
Và Avialable = Avialable-Request=1-1=0

Ta lập bảng:

P Allocation Max Need Available
P1 1 2 1 0
P2 2 2 0

Đi tìm chuỗi an toàn:

Work>= Need[i] P[i] Allocation[i]
0 0 P2 2
2 1 P1 1

Kết luận: Tại thời điểm T tiến trình P2 xin thêm 1 máy scan hệ thống vẫn tồn tại chuỗi an toàn: {P2,P1}

À lúc làm xong mình nghỉ các bạn nên ghi câu la do tồn tại ít nhất 1 chuỗi an toàn(chuỗi nào cũng được),nên trạng thái hệ thống tại thời điểm đó an toàn

NguyenNgocMyTien(I11C) 9/11/2011, 23:04

BuiHuuThanhLuan(I11C) đã viết:
08H1010052 đã viết:
TranQuyThanh (I11C) đã viết: Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:

Loại tài nguyên
Số phiên bản
Được các tiến trình yêu cầu
Đã cấp cho các tiến trình
Máy in kim
2
P₁
P₂, P₃
Máy in laser
1

P₃
Ổ băng từ
2
P₂
P₁, P₃

Mình xin vẽ đồ thị bài này như sau:

=> Không xảy ra deadlock trong đồ thị trên mặc dù xảy ra chu trình giữa 2 tiến trình P2 và P1. Lý do là vì tiến trình P3 sẽ giải phóng tài nguyên trả lại cho máy in kim và ổ băng từ khi kết thúc tiến trình của nó. Từ đó chu trình P1 và P2 sẽ bị phá vỡ và tránh được deadlock.
Mong các bạn góp ý nhé.
Thân chào các bạn!

Đồ thị bạn vẽ và giải thích đúng rồi. cảm ơn bạn nhé
Thêm ý nữa là mình thấy tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock

Mình không hiểu ý của bạn BuiHuuThanhLuan(I11C)
Theo mình thì có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản chứ không thể nói tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock
Các bạn cho ý kiến chỗ này giúp mình với.

LE DUY NHAT AN (I91C) 9/11/2011, 23:19

NguyenNgocMyTien(I11C) đã viết:
BuiHuuThanhLuan(I11C) đã viết:
08H1010052 đã viết:
TranQuyThanh (I11C) đã viết: Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:

Loại tài nguyên
Số phiên bản
Được các tiến trình yêu cầu
Đã cấp cho các tiến trình
Máy in kim
2
P₁
P₂, P₃
Máy in laser
1

P₃
Ổ băng từ
2
P₂
P₁, P₃

Mình xin vẽ đồ thị bài này như sau:

=> Không xảy ra deadlock trong đồ thị trên mặc dù xảy ra chu trình giữa 2 tiến trình P2 và P1. Lý do là vì tiến trình P3 sẽ giải phóng tài nguyên trả lại cho máy in kim và ổ băng từ khi kết thúc tiến trình của nó. Từ đó chu trình P1 và P2 sẽ bị phá vỡ và tránh được deadlock.
Mong các bạn góp ý nhé.
Thân chào các bạn!

Đồ thị bạn vẽ và giải thích đúng rồi. cảm ơn bạn nhé
Thêm ý nữa là mình thấy tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock
Mình không hiểu ý của bạn BuiHuuThanhLuan(I11C)
Theo mình thì có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản chứ không thể nói tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock
Các bạn cho ý kiến chỗ này giúp mình với.

Mình nhớ thầy có nói là :
-Không có chu trình thì không tồn tại deadlock
-Có chu trình: sẽ có 2 trường hợp có hoặc ko 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 thôi.
*Có thể không có deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản(từ đó áp dụng và làm thui)

ThanhThao04(I11C) 9/11/2011, 23:44

ToThiThuyTrang (I11C) đã viết:
vothihonggam đã viết: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.

ví dụ: 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.

Ví dụ 2: Hiện tượng kẹt mạng tại tổng đài 1080:
+ ví dụ tổng đài 1080 gồm có 100 điện thoại viên.
+ 100 khách hàng gọi tới cùng một lúc. Khách hàng 101,102…. Gọi tới, sẽ phải chờ.
+ 1 khách hàng ứng với một điện thoại viên có thể xem như một tài nguyên.
+ nếu deadlock xuất hiện, nó có thể được giải quyết nếu 1 trong 100 khách hàng đã được điện thoại viên trả lời xong và nhường tài nguyên cho các khách hàng tiếp theo...

ví dụ 2 Trang đưa ra không xảy ra deadlock vì khi những khách hàng khác đã được giải quyết xong thì sẽ đến lượt những vị khách 101,102... do đó những vị khách chỉ phải đợi đến lượt giải quyết.
- Deadlock là kẹt mãi mãi. Còn với tổng đài 1080, "kẹt" có một lúc thôi. Khách hàng chỉ phải chờ một khoảng thời gian hữu hạn. Không có chuyện ai đó hỏi mãi được. Còn có cơ chế "Tiếm quyền" nữa: Nếu lâu quá, cô trả lời sẽ tìm cách kết thúc cuộc gọi. Chưa kể, có thể kết nối bị ngắt tự động khi timeout.

NguyenNgocMyTien(I11C) 10/11/2011, 00:05

dangminhthinh2107 đã viết:
giải thích đồ thị:
trong đồ đị hiện có hai tài nguyên R1 & R2 ta cho trong hai tài nguyên đó R1 có hai phiên bản là máy in HP1, HP2. R2 cũng có hai phiên bản là Canon1, Canon2
giả sử tại thời điểm lúc 6h
- Cung yêu cầu từ P1 -> R1: Thể hiện tiến trình (TT) P1 yêu cầu R1 cấp cho một phiên bản.
- Tài nguyên (TN) R1 đã cấp cho P2 một phiên bản (một máy in) nghĩa là tại thời điểm này P2 được cấp phát một máy in hoặc được sở hữu một máy in HP.
- TN R1 cũng đã cấp phát cho TT P3 một máy in HP.
- Đồng thời lúc này P3 yêu cầu R2 cấp cho mình một phiên bản Canon
- R2 đã cấp phát cho TT P1 một phiên bản máy in Canon
Ta nhìn thấy đồ thị lúc này có chu trình các mũi tên đuổi nhau hiện tượng chờ xoay vòng (Circular Wait) đây là dấu hiệu của deadlock (vòng tròn). P1 đang chờ tài nguyên R1 cấp một máy in HP nhưng TN của R1 đang được P2 & P3 giữ.
giã sử tại thời điểm 6h5p
- Lúc 6h R1 & R2 cấp TN (máy in HP & Canon) cho hai TT P2 & P4 ( hai TT này nằm ngoài chu trình) nhưng tại thời điểm 6h5p hai TT P2 & P4 đã làm việc xong nên TN được trả lại.
- TN được trả lại sẻ được cấp phát cho P1 & P3 yêu cầu
Tại thời điểm này sẻ không xảy ra hiện tượng deadlock.
Những lý giải này là theo cách nghĩ của mình có gì không đúng mong các bạn bổ xung thêm.

Các bạn xem thêm cách giải thích này nhé!
Giả sử tại thời điểm 6h00:Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R1 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Tiến trình P4 đang giữ 1 phiên bản của tài nguyên R2.
Từ hình vẽ chúng ta thấy xảy ra 1 chu trình P1 → R1 → P3 → R2 → P1 nhưng không có deadlock vì lúc 6h10 tiến trình P4 thực thi xong công việc và trả lại phiên bản của loại tài nguyên R2. Tài nguyên đó có thể được cấp phát tới P3 lúc 6h15 ( hoặc lúc 6h12 tiến trình P2 thực thi xong công việc và trả lại phiên bản của loại tài nguyên R1. Tài nguyên đó có thể được cấp phát tới P1 lúc 6h20), chu trình sẽ không còn.

nguyenduc_gia.18(I11c) 10/11/2011, 00:13

- 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).
cảm ơn thầy em đã hiểu rỏ
ở trên lớp em ơ cuối lớp em không nghe kỷ được

nguyenduc_gia.18(I11c) 10/11/2011, 00:21

> Định nghĩa Deadlock? Ví Dụ
Định nghĩa: Tình huống bị 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(event) có thể chỉ được gây ra bởi một tiến trình khác.
vd1: Hiện tượng deadlock xảy ra trên 1 cây cầu mà ở giữa cầu có 1 đoạn cầu rất hẹp ( tại 1 thời điểm chỉ duy nhất 1 xe đi qua cầu). Khi các ô tô duy chuyển trên cầu và đi qua đoạn cầu hẹp, tại 1 thời điểm cả 2 đều đi ngang đoạn giữa cầu hẹp và cả 2 xe đều kẹp ở giữa cầu => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.)
vd2: 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) vd này đơn giản dể hiểu và dể nhớ
>Giải pháp ngăn chặn Deadlock

+Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung

> Phân tích khái niệm tài nguyên hệ thống
- Các tài nguyên hệ thống được chia thành nhiều Loại, mỗi loại có 1 hoặc nhiều Phiên bản (Instances). Các tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.
- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trình đang giữ 1 ổ băng.
- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in

>Thứ tự sử dụng tài nguyên của tiến trình.

1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.

2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiện I/O, in ra giấy, ...).

3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý.

NguyenNgocMyTien(I11C) 10/11/2011, 01:01

ngocquynh2091(i11C) đã viết:
Như ví dụ thầy đã đưa trong slide bài giảng, chúng ta tìm được 1 chuỗi an toàn khác là: {P3,P1, P4, P2, P0}

Cũng bài ví dụ của thầy trên lớp về thuật giải nhà băng mình tìm được 1 chuỗi an toàn khác các bạn xem có đúng không nhé.

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 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 chuỗi an toàn < P1, P3, P0, P2, P4 >
Vậy : Trạng thái ở thời điểm T0 là an toàn.

TranThanhHoang(I91C) 10/11/2011, 04:31

NguyenNgocMyTien(I11C) đã viết:
ngocquynh2091(i11C) đã viết:
Như ví dụ thầy đã đưa trong slide bài giảng, chúng ta tìm được 1 chuỗi an toàn khác là: {P3,P1, P4, P2, P0}

Cũng bài ví dụ của thầy trên lớp về thuật giải nhà băng mình tìm được 1 chuỗi an toàn khác các bạn xem có đúng không nhé.

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 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 chuỗi an toàn < P1, P3, P0, P2, P4 >
Vậy : Trạng thái ở thời điểm T0 là an toàn.

hehe mình làm ra kết quả giống y chang bạn.
mình post chậm quá nên bạn post trước mất,tiết ghê Sad

.

Dù sao cũng thanks bạn nhiều nhan

TranThanhHoang(I91C) 10/11/2011, 04:34

nguyenduc_gia.18(I11c) đã viết:> Định nghĩa Deadlock? Ví Dụ
Định nghĩa: Tình huống bị 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(event) có thể chỉ được gây ra bởi một tiến trình khác.
vd1: Hiện tượng deadlock xảy ra trên 1 cây cầu mà ở giữa cầu có 1 đoạn cầu rất hẹp ( tại 1 thời điểm chỉ duy nhất 1 xe đi qua cầu). Khi các ô tô duy chuyển trên cầu và đi qua đoạn cầu hẹp, tại 1 thời điểm cả 2 đều đi ngang đoạn giữa cầu hẹp và cả 2 xe đều kẹp ở giữa cầu => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.)
vd2: 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) vd này đơn giản dể hiểu và dể nhớ
>Giải pháp ngăn chặn Deadlock

+Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung

> Phân tích khái niệm tài nguyên hệ thống
- Các tài nguyên hệ thống được chia thành nhiều Loại, mỗi loại có 1 hoặc nhiều Phiên bản (Instances). Các tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.
- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trình đang giữ 1 ổ băng.
- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in

>Thứ tự sử dụng tài nguyên của tiến trình.

1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.

2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiện I/O, in ra giấy, ...).

3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý.

nguyenduc_gia.18(I11c) pro quá,nhớ được bài học hồi tiểu học.thanks vì ví dụ 2 con dê.thi mà ra câu này mình sẽ lấy 2 con dê của bạn vào bài làm.

thanks

NguyenDoTu (I11C) 10/11/2011, 07:50

Đề bài: Một hệ thống có 3 máy quét hình(Scanner) và 2 tiến trình P1,P2, với trạng thái cấp phát tài nguyên ở 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. C/m trạng thái này an toàn<1đ>
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<1đ>
Giải :
Hệ có: Available=3-(1 + 1)=1
Giá trị trên được tính bằng cách lấy số phiên bản (3 máy quét) trừ đi tồng các giá trị alloction của các tiến trình

P[i]	Đang giữ (Allocation)	Max	Need	Hệ Có (Available)
P1	1	2	1	1
P2	1	2	1	1

Tìm chuỗi an toàn :

Work	Need	Pi	Allocation
1	1	P1	1
2	1	P2	1

LeMInhTien(I11C) 10/11/2011, 08:08

- Một trạng thái được gọi là "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ả các process thực thi hoàn tất.
- Khi đó hệ thống tồn tại 1 chuỗi an toàn {P1,P2, ..., P3} 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 cho 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.

DangMinhQuang(I11C) 10/11/2011, 09:12

Khi nào chúng ta cần giải thuật phát hiện deadlock? Câu trả lời phụ thuộc vào hai yếu tố:

· Deadlock có khả năng xảy ra như thế nào?

· Có bao nhiêu tiến trình sẽ bị ảnh hưởng bởi deadlock khi nó xảy ra ?

Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện deadlock sẽ được thực hiện thường xuyên. Tài nguyên được cấp phát cho deadlock sẽ được rảnh rỗi cho đến khi deadlock bị phá vỡ. Ngoài ra, số lượng tiến trình tham gia vào trong chu trình deadlock có thể tăng lên.

Deadlock xảy ra khi một tiến trình thực hiện yêu cầu mà không được cấp phát tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối cùng hoàn thành một chuỗi các tiến trình chờ. Trong trường hợp này chúng ta có thể gọi giải thuật phát hiện deadlock mỗi khi yêu cầu cấp phát không được cấp phát tức thì. Chúng ta không chỉ biết được tập hợp các tiến trình bị deadlock mà còn xác định tiến trình đã gây ra deadlock (Trong thực tế, mỗi tiến trình trong suốt quá trình bị deadlock là một liên kết trong chu trình của đồ thị tài nguyên vì thế tất cả chúng gây ra deadlock). Nếu có nhiều loại tài nguyên khác nhau, một yêu cầu tạo ra một chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi các yêu cầu gần đây nhất và “gây ra” bởi một tiến trình có thể xác định.

Tất nhiên, nếu thuật toán phát hiện deadlock được gọi cho mọi yêu cầu tài nguyên điều này có thể gây ra chi phí lớn trong thời gian tính toán. Một phương pháp để giảm chi phí là ta gọi giải thuật trong thời điểm ít thường xuyên hơn - ví dụ mỗi giờ hoặc bất cứ khi nào CPU sử dụng dưới 40%. Nếu giải thuật phát hiện deadlock được gọi vào thời điểm bất kỳ, có thể có nhiều chu trình trong đồ thị tài nguyên. Chúng ta không thể xác định được tiến trình nào “gây ra” deadlock.

====================================

Phục hồi deadlock

Khi giải thuật phát hiện deadlock xác định tồn tại một deadlock, có 2 cách để giải quyết:

· Một là thông báo cho người điều hành biết deadlock xảy ra và để cho người điều hành khắc phục bằng tay.

· Hai là để cho hệ thống phục hồi tự động. Có hai tùy chọn để phá vỡ deadlock. Một giải pháp đơn giản là hủy một hay nhiều tiến trình để phá vỡ tồn tại chu trình trong đồ thị cấp phát tài nguyên. Lựa chọn thứ hai là lấy lại một hay nhiều tài nguyên từ tiến trình deadlock.

Kết thúc tiến trình.

Để loại bỏ deadlock bằng hủy bỏ tiến trình, chúng ta sử dụng một trong hai phương pháp. Cả hai phương pháp này có điểm chung là hệ thống lấy lại các nguồn tài nguyên từ các tiến trình bị kết thúc.

· Hủy bỏ tất cả tiến trình bị deadlock: Phương pháp này sẽ phá vỡ chu kì deadlock, nhưng chi phí cao, các tiến trình deadlock có thể có tính toán trong thời gian dài, và kết quả tính toán từng phần này phải được loại bỏ và rất có thể phải tính lại sau đó.

· Hủy bỏ một tiến trình ở thời điểm hiện tại cho đến khi chu trình deadlock bị xóa. Phương pháp này chịu chi phí có thể xem xét, sau khi tiến trình bị hủy bỏ, giải thuật phát hiện deadlock được gọi xác định có còn tiến trình nào bị deadlock hay không.

Hủy bỏ tiến trình có thể không dễ dàng. Nếu một tiến trình đang ở giai đoạn cập nhật tập tin, nếu kết thúc nó sẽ để tập tin trong trạng thái không phù hợp. Tương tự nếu dữ liệu đang ở giai đoạn in dữ liệu ra máy in, hệ thống phải khởi động lại trạng thái trước khi in công việc tiếp theo.

Nếu như phương pháp hủy bỏ một phần được sử dụng, sau đó chúng ta phải xác định tiến trình tiếp theo bị deadlock. Việc xác định này là cả một quyết định tương tự như vấn đề lập lịch cho CPU. Câu hỏi mang tính chất kinh tế, chúng ta nên hủy bỏ tiến trình nào thì sự kết thúc của tiến trình có chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác.

Những yếu tố xác định đến tiến trình nào được chọn bao gồm:

1. Mức độ ưu tiên của tiến trình.

2. Tiến trình đã thực hiện được bao lâu và còn bao lâu nữa thì hoàn thành?

3. Tiến trình đang sử dụng bao nhiêu loại tài nguyên?

4. Tiến trình cần bao nhiêu tài nguyên nữa để hoàn thành?

5. Bao nhiêu tiến trình sẽ cần được kết thúc.

6. Tiến trình độc lập hay liên quan đến các tiến trình khác.

Đòi Lại Tài Nguyên

Để loại trừ deadlock chúng ta có thể sử dụng biện pháp đòi lại tài nguyên, tức là: chúng ta lần lược đòi lại một phần tài nguyên từ các tiến trình và đưa các tài nguyên này đến các tiến trình khác cho đến khi chu trình deadlocks bị phá bỏ.

Nếu phương pháp này được yêu cầu để giải quyết deadlock thì có ba vấn đề cần được xác định :

· Chọn đối tượng cần được tác động: Những tài nguyên và tiến trình nào bị đòi lại? Trong khi kết thúc tiến trình, chúng ta phải xác định trình tự đòi lại để chi phí là ít nhất. Yếu tố chi phí có thể bao gồm số lượng tài nguyên một tiến trình deadlock đang giữ và lượng thời gian mà tiến trình deadlock tiêu thụ trong khi thực thi nó.

· Quay trở lại: Nếu chúng ta đòi lại tài nguyên từ một tiến trình, cái gì nên được kết thúc với tiến trình đó? Rõ ràng nó không thể tiếp tục việc thực thi bình thường của nó, nó đang làm mất một số tài nguyên cần thiết. Chúng ta phải quay tiến trình tới một số mức an toàn và khởi động lại nó từ mức đó. Từ trạng thái bị deadlock thông thường rất khó xác định mức an toàn là mức nào, cách đơn giản nhất là quay lại toàn bộ tức là: bỏ dở tiến trình và sau đó khởi động lại nó. Mặc dù nó có tác dụng hơn quay tiến trình lại đến mức cần thiết đủ để phá vỡ deadlocks nhưng phương pháp này yêu cầu hệ thống phải giữ nhiều thông tin về các mức của tất cả các tiến trình đang chạy.

· Sự đói tài nguyên: Làm sao chúng ta đảm bảo sự đói tài nguyên sẽ không xảy ra? Tức là làm sao để chúng ta có thể đảm bảo tài nguyên đó sẽ luôn không bị đòi lại từ cùng một tiến trình?

Trong một hệ thống, việc chọn “nạn nhân” chủ yếu dựa trên yếu tố chi phí, có thể có 1 tiến trình luôn được chọn là “nạn nhân”. Kết quả là tiến trình này không bao giờ hoàn thành công việc nó được chỉ định, cho nên trạng thái đói tài nguyên phải chắc chắn được giải quyết trong bất kỳ một hệ thống thiết thực nào. Rõ ràng chúng ta phải chắc chắn một tiến trình có thể được chọn như một nạn nhân chỉ với một số lần xác định(nhỏ). Giải pháp phổ biến nhất là bao gồm cả số lần quay lại trong yếu tố chi phí.

TÓM TẮT

Deadlock bắt nguồn từ sự xung đột về tài nguyên của 2 hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống.

Các phương thức giải quyết deadlocks :

· Sử dụng một vài giao thức để ngăn ngừa hoặc tránh xa deadlock, đảm bảo hệ thống đó sẽ không bao giờ có deadlock.

· Cho phép hệ thống ở tình trạng deadlock, phát hiện và sau đó phục hồi lại.

· Lờ đi vấn đề tất cả các vấn đề và giả vờ như deadlocks chưa bao giờ xảy ra trong hệ thống.

Deadlocks chỉ có thể xảy ra nếu bốn điều kiện cần thiết đó cùng lúc trong hệ thống.

Nếu một hệ thống không sử dụng một phương pháp để chắc chắn rằng deadlock sẽ không bao giờ xảy ra, thì phương pháp phát hiện và phục hồi sẽ được dùng đến. Nếu deadlock đã được ngăn chặn thì hệ thống phải phục hồi bằng cách chấm dứt một số quá trình bị deadlock hay là đòi lại tài nguyên từ những tiến trình đã bị deadlock.

Để đòi lại tài nguyên hoặc tiến trình đã gây ra deadlocks, ba vấn đề cần phải xác định là: chọn nạn nhân, quay trở lại, và sự đói tài nguyên

TRANTHINHPHAT (I11C) 10/11/2011, 11:00

Định nghĩa Bế tắc (Deadlock)
- Bế tắc là tình huống xuất hiện khi hai hay
nhiều “hành động” phải chờ một hoặc nhiều
hành động khác để kết thúc, nhưng không
bao giờ thực hiện được
- Máy tính: Bế tắc là tình huống xuất hiện khi
hai tiến trình phải chờ đợi nhau giải phóng tài
nguyên hoặc nhiều tiến trình chờ sử dụng
các tài nguyên theo một “vòng tròn” (circular
chain)

Ví dụ:

1.Hai con dê qua cầu: Bế tắc

2. Bế tắc giao thông tại ngã tư

3. Bế tắc trongmáy tính
- Tiến trình A:
{
…
Khóa file F1;
...
Mở file F2;
…
Đóng F1 (mở khóa F1);
}

-Tiến trình B
{
…
Khóa file F2;
...
Mở file F1;
…
Đóng F1 (mở khóa F1);
}

NgoDucTuan (I11C) 10/11/2011, 11:02

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.

Thanks bạn nhiều lắm. Bài giải mình thấy dễ hiểu.

TRANTHINHPHAT (I11C) 10/11/2011, 11:03

Thuật toán trạng thái an toàn
1. Khởi tạo Work=Available và Finish[i]=false
∀i=1..n
2. Tìm i sao cho Finish[i]==false và Need[i]≤Work
Nếu không tìm được i, chuyển đến bước 4
3. Work=Work+Allocation[i], Finish[i]=true
Chuyển đến bước 2
4. Nếu Finish[i]==true ∀i thì hệ thống ở trạng thái
an toàn
-Độ phức tạp tính toán của thuật toán trạng thái
an toàn: O(m.n2)

Thuật toán yêu cầu tài nguyên
1. Nếu Request[i]≤Need[i], chuyển đến bước 2
Ngược lại thông báo lỗi (không có tài nguyên rỗi)
2. Nếu Request[i]≤Available, chuyển đến bước 3.
Ngược lại Pi phải chờ vì không có tài nguyên
3. Nếu việc thay đổi trạng thái giả định sau đây:
Available=Availalble-Request[i]
Allocation=Allocation+Request[i]
Need[i]=Need[i]-Request[i]
đưa hệ thống vào trạng thái an toàn thì cấp phát tài
nguyên cho Pi, ngược lại Pi phải chờ Request[i] và
trạng thái của hệ thống được khôi phục như cũ

TRANTHINHPHAT (I11C) 10/11/2011, 11:08

Ví dụ banker 1
- Xét một hệ thống các tiến trình và tài nguyên
như sau:
Allocation Max Available Need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1

Ví dụ banker 2
- Hệ thống hiện đang ở trạng thái an toàn
- Thứ tự <P1,P3,P4,P2,P0> thỏa mãn tiêu chuẩn
an toàn
- Giả sử P1 có yêu cầu: Request[1]=(1,0,2)
-Để quyết định xem có cấp phát tài nguyên
theo yêu cầu này không, trước hết ta kiểm tra
Request[1]≤Available: (1,0,2)<(3,3,2): Đúng

Ví dụ banker 3
Allocation Need Available
A B C A B C A B C
P0 0 1 0 7 4 3 3 3 2
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
- Thực hiện thuật toán trạng thái an toàn và thấy rằng
thứ tự <P1,P3,P4,P0,P2>. Do đó có thể cấp phát tài
nguyên cho P1 ngay.

Ví dụ banker 4
- Tuy nhiên, nếu hệ thống ở trạng thái sau thì
- Yêu cầu (3,3,0) của P4 không thể cấp phát ngay
vì các tài nguyên không rỗi
- Yêu cầu (0,2,0) của P0 cũng không thể cấp phát
ngay vì mặc dù các tài nguyên rỗi nhưng việc
cấp phát sẽ làm cho hệ thống rơi vào trạng thái
không an toàn

HoangNgocQuynh(I11C) 10/11/2011, 14:02

TranThanhHoang(I91C) đã viết:
NguyenNgocMyTien(I11C) đã viết:
ngocquynh2091(i11C) đã viết:
Như ví dụ thầy đã đưa trong slide bài giảng, chúng ta tìm được 1 chuỗi an toàn khác là: {P3,P1, P4, P2, P0}

Cũng bài ví dụ của thầy trên lớp về thuật giải nhà băng mình tìm được 1 chuỗi an toàn khác các bạn xem có đúng không nhé.

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 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 chuỗi an toàn < P1, P3, P0, P2, P4 >
Vậy : Trạng thái ở thời điểm T0 là an toàn.

hehe mình làm ra kết quả giống y chang bạn.
mình post chậm quá nên bạn post trước mất,tiết ghê .

Dù sao cũng thanks bạn nhiều nhan

Mình nghĩ rằng đã tồn tại một chuỗi an toàn thì chắc các chuỗi khác cũng sẽ an toàn.

PhamThiHoa-I91C 10/11/2011, 15:08

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

Thầy đã giải thích rõ ràng như vậy rồi mà

nguyenthanhhieu(i11c) 10/11/2011, 15:20

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úc trong hệ thống:

1) Loại trừ hỗ tương: ít nhất một tài nguyên phải được giữ trong chế độ không chia sẻ; 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ừng cho đến khi tài nguyên được giải phóng.

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

3) 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 đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.

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

Chú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ện không hoàn toàn độc lập.

minhgiangbc 10/11/2011, 16:09

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?

các bạn giải dùm mình bài này nhé .mình có giải rùi ma chác sai nên pót nên mọi người cùng giai và mình cũng dễ tham khảo hơn,không di học 1 buổi mà giờ cứ mơ màng cả nên roài cyclops

ledinhngankhanh (i11c) 10/11/2011, 16:15

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

DuongTrungTinh(I11C) 10/11/2011, 16:18

phamngoctan095 (I11C) đã viết:
minhgiangbc đã viết:
mình thì có ý kiến thế này
Sự tắc nghẽn có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra chỉ với 3 điều kiện đó. Để chắc chắn tắc nghẽn xảy ra cần phải có điều kiện thứ tư Đợi vòng tròn (Circular wait).
Đây là trường hợp của 1 ví dụ mà bài 7 thầy chưa có nói đó là Các nhà hiền triết cùng ngồi 1 bàn tròn

mỗi tiến trình đang chiếm giữ tài nguyên mà tiến trình khác đang cần.
Ba điều kiện đầu là điều kiện cần chứ không phải là điều kiện đủ để xảy ra tắc nghẽn. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu.
Các nhà hiền triết độc lập với nhau và trầm tư suy nghĩ.khi đói ,mỗi người nhấc đũa 2 bên và nếu dược cả đôi thì bắt đầu ăn,sau đó đặt từng chiếc đũa về vị trí cũ.Deadlkock xảy ra khi các hiền triết cùng 1 lúc nhấc đũa bên trái hoặc đũa bên phải cứ thế chờ nhau mà không ai dược ăn cả.đó là hiện tượng chờ xoay vòng

Bài viết và ví dụ của bạn đưa ra rất thực tế và phù hợp với nội dung của bài học, hy vọng sẽ tiếp tục nhận được những bài viết hay từ bạn. Thanks!

Một ví dụ hay, cảm ơn bạn nhiều Very Happy

DuongTrungTinh(I11C) 10/11/2011, 16:34

dongocthien (I11C) đã 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:
Allocation Max Available
A B C A B C A B C
Po 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
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 >
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)
Allocation Need Available
A B C A B C A B C
Po 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
Work Need(i) P(i) 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 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
104 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 >

Có vài chỗ hình như bạn sai thì phải? (những chỗ màu đỏ)
- Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2) : nếu dúng sẽ là (3,3,2)
- Work = (3,2,2)+(2,0,0) = (5,3,2) nếu đúng sẽ là Work = (3,3,2)+(2,0,0) = (5,3,2).

DuongTrungTinh(I11C) 10/11/2011, 16:38

TranThanhHoang(I91C) đã viết:
NguyenNgocMyTien(I11C) đã viết:
ngocquynh2091(i11C) đã viết:
Như ví dụ thầy đã đưa trong slide bài giảng, chúng ta tìm được 1 chuỗi an toàn khác là: {P3,P1, P4, P2, P0}

Cũng bài ví dụ của thầy trên lớp về thuật giải nhà băng mình tìm được 1 chuỗi an toàn khác các bạn xem có đúng không nhé.

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 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 chuỗi an toàn < P1, P3, P0, P2, P4 >
Vậy : Trạng thái ở thời điểm T0 là an toàn.

hehe mình làm ra kết quả giống y chang bạn.
mình post chậm quá nên bạn post trước mất,tiết ghê .

Dù sao cũng thanks bạn nhiều nhan

Cám ơn các bạn, kết quả chính xác như mình Laughing

Sponsored content

Thảo luận Bài 8