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

vutanthanh68 (113A) 27/9/2012, 00:00

thầy ơi em sửa vậy được chưa thầy

ThuyDuong23 (I12A) 27/9/2012, 00:01

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.

TranMinhNhat61 (102c) 27/9/2012, 08:14

Work0 = hệ có
Work1 = Work0 + Allocation0
Work2 = Work1 + Allocation1
................
Workn = Work(n-1) + Allocation(n-1)

trantrungnam-HC11TH2A 27/9/2012, 11:26

hế nào là trạng thái an toàn của hệ thống?
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.

Trình bày 4 cách ngăn chặn Deadlock.
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN(tai nguyên) nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

voanhvy (113A) 27/9/2012, 16:02

Thanks nhiều nhé mấy bạn Very Happy

PhamHoangQuan (113A) 27/9/2012, 23:49

VoHoangTrung (113A) đã viết:
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

Chưa theo kịp lớp nhưng hi vọng từ nay tới thi sẽ nắm hết đễ pass qua môn này Idea

DangThiKimKhanh (113A) 28/9/2012, 09:49

vutanthanh68 (113A) đã viết:chúng ta có 12 ổ băng từ
Tiến Trình Đã Cấp Tối Đa Cần(MAX)
P₁ 5 10
P₂ 2 4
P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+2)=3
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 2 9 (MAX- ĐangGiữ)=9-2=7

Work >= Need P_i Allocation
3 2 P₂ 2
5 5 P₁ 5
10 7 P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+3)=2
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 3 9 (MAX- ĐangGiữ)=9-3=6

[/tr]
Work >= Need P_i Allocation
2 >= 2 P₂ 2
4 < 5 P₁ 5 //không đáp ứng được 4<5
4< 6 P₃ 3 //không đáp ứng được

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ứ?

Cảm ơn sự hướng dẫn của thầy và bài làm của bạn .!!!!

nguyenvantinh (11a3) 28/9/2012, 11:04

DangThiKimKhanh (113A) đã viết:
vutanthanh68 (113A) đã viết:chúng ta có 12 ổ băng từ
Tiến Trình Đã Cấp Tối Đa Cần(MAX)
P₁ 5 10
P₂ 2 4
P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+2)=3
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 2 9 (MAX- ĐangGiữ)=9-2=7

Work >= Need P_i Allocation
3 2 P₂ 2
5 5 P₁ 5
10 7 P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+3)=2
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 3 9 (MAX- ĐangGiữ)=9-3=6

[/tr]
Work >= Need P_i Allocation
2 >= 2 P₂ 2
4 < 5 P₁ 5 //không đáp ứng được 4<5
4< 6 P₃ 3 //không đáp ứng được

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ứ?
Cảm ơn sự hướng dẫn của thầy và bài làm của bạn .!!!!

Cảm ơn thầy và bài làm của bạn .!!!!

VuMinhTan (113A) 28/9/2012, 14:57

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

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.

TranThiThuyQuyen (113A) 28/9/2012, 18:38

Cám ơn Thầy và các bạn, hôm trước trên lớp còn nhiều thắc mắc nhưng đã được giải đáp. Đã hiểu được vấn đề ^.^

TranThiHuyenTrang(113A) 29/9/2012, 20:24

Mình chọn cái nào trước cũng đựoc vì trong mot bài toán xét trạng thái an toàn khi dùng thuật giải nhà băng thì có thể co nhiều chuỗi an toàn chứ khong phải chỉ co mot chuoi
Khi làm bài thi thì cũng chỉ cần tìm mot chuoi an toàn là đủ

TranVanTien (I12A) 30/9/2012, 14:20

TranVanTien (I12A) 30/9/2012, 14:28

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

Admin
- Trình bày tốt !
- Kết luận chưa "trúng". Thử nêu lại xem sao !

TranVanTien (I12A) 30/9/2012, 15:04

TranThichThem (113A) 30/9/2012, 21:26

Ví dụ : – 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)
.............

a) Thời điểm T0 :
Hệ thống an toàn (P3,P1,P2,P4,P0)

b)Thời điểm T1 : P1 yêu cầu (1,0,2)
Hệ thống an toàn (P3,P1,P2,P4,P0)

c)Thời điểm T2 : P4 yêu cầu (3,3,0)
Hệ thống không an toàn do Request4 (3,3,0) > Available (2,3,0)(ở thời điểm T1)

d)Thời điểm T3 : P0 yêu cầu (0,2,0)
Hệ thống không an toàn do P2 : Work(2,4,1) < Need(6,0,2)(ở thời điểm T1)
->Chỉ tồn tại chuỗi (P3,P1,P4,P0)

Bạn nào làm ví dụ theo hướng xét P3(ở thời điểm T0) trước thì cho mình kiểm tra lại đáp án nhé !
Thanks !

huynhquanghao_I92C 1/10/2012, 17:17

nguyenvantinh (11a3) đã viết:
DangThiKimKhanh (113A) đã viết:
vutanthanh68 (113A) đã viết:chúng ta có 12 ổ băng từ
Tiến Trình Đã Cấp Tối Đa Cần(MAX)
P₁ 5 10
P₂ 2 4
P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+2)=3
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 2 9 (MAX- ĐangGiữ)=9-2=7

Work >= Need P_i Allocation
3</SUB> 2 P₂ 2
5 5 P₁ 5
10 7 P₃ 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ó
P₁ 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+3)=2
P₂ 2 4 (MAX- ĐangGiữ)=4-2=2
P₃ 3 9 (MAX- ĐangGiữ)=9-3=6

[/tr]
Work >= Need P_i Allocation
2 >= 2 P₂ 2
4 < 5 P₁ 5 //không đáp ứng được 4<5
4< 6 P₃ 3 //không đáp ứng được

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<sub>3</sub>

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ứ?
Cảm ơn sự hướng dẫn của thầy và bài làm của bạn .!!!!
Cảm ơn thầy và bài làm của bạn .!!!!

VoHoangTrung (113A) 1/10/2012, 21:02

2 bài tâp 4 điểm cố lên

NguyenThanhHien (113A) 1/10/2012, 23:51

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 !

Trường hợp cụ thể:
Một hệ thống có 10 máy qué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 (3,1,1) và Max (9,4,8 ).
Dùng thuật giả 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 cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process	Allocation	Max	Need	Available
P1	3	9	6	5
P2	1	4	3
P3	1	8	7

Bảng trợ giúp:

Work >=	Needi	Pi	Allocation
5	3	P2	1
6	6	P1	3
9	7	P3	1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là 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 cho tiến trình P3
Gọi yêu cầu là Request3. Ta cáo Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process	Allocation	Max	Need	Available
P1	3	9	6	4
P2	1	4	3
P3	2	8	6

Bảng trợ giúp:

Work >=	Needi	Pi	Allocation
4	3	P2	1
5	?	?	?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn

ngongocdiep06 (113A) 2/10/2012, 10:40

Đề bài:
Một hệ thống có 12 ổ 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 vectơ Allocation=(5,2,2) Max=(10,4,9). 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 hay không yêu cầu xin thêm 1 ổ nữa của P3?

Bài giải:
a) Chứng minh trạng thái này an toàn:
Tính Available = 12 - (5+2+2) = 12 - 9 = 3
Trạng thái của hệ thống:

Process	Allocation	Max	Need	Available
P1	5	10	5	3
P2	2	4	2
P3	2	9	7

Bảng trợ giúp:

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

Tìm được chuỗi an toàn: {P2,P1,P3}.
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Xác định có nên đáp ứng hay không yêu cầu xin them 1 ổ nữa của P3:
Gọi yêu cầu là Request3 ta có:
Request3 = 1
Request3 <= Need3 (vì 1 <=7 )
Request3 <= Available (vì 1 <= 3)
Tràng thái mới của hệ:

Process	Allocation	Max	Need	Available
P1	5	10	5	2
P2	2	4	2
P3	3	9	6

Bảng trợ giúp:

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

Không nên đáp ứng yêu cầu Request3 vì hệ thống sẽ không an toàn (không tìm thấy chuỗi an toàn).

Admin
Trước khi kết luận là không nên đáp ứng yêu cầu Request3, cần khẳng định là không tồn tại chuỗi an toàn nào (chỉ tìm được 1 chuỗi không đầy đủ bắt đầu từ P2) !

nguyenlehuutai(113A) 2/10/2012, 11:21

Cam on bai giai cua ban

phamanhtuan95(113A) đã viết:

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é

ngongocdiep06 (113A) 3/10/2012, 08:30

ngongocdiep06 (113A) đã viết:Đề bài:
Một hệ thống có 12 ổ 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 vectơ Allocation=(5,2,2) Max=(10,4,9). 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 hay không yêu cầu xin thêm 1 ổ nữa của P3?

Bài giải:
a) Chứng minh trạng thái này an toàn:
Tính Available = 12 - (5+2+2) = 12 - 9 = 3
Trạng thái của hệ thống:
Process Allocation Max Need Available
P1 5 10 5 3
P2 2 4 2

P3 2 9 7

Bảng trợ giúp:
Work >= Needi Pi Allocation
3 2 P2 2
5 5 P1 5
10 7 P3 2

Tìm được chuỗi an toàn: {P2,P1,P3}.
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Xác định có nên đáp ứng hay không yêu cầu xin them 1 ổ nữa của P3:
Gọi yêu cầu là Request3 ta có:
Request3 = 1
Request3 <= Need3 (vì 1 <=7 )
Request3 <= Available (vì 1 <= 3)
Tràng thái mới của hệ:
Process Allocation Max Need Available
P1 5 10 5 2
P2 2 4 2

P3 3 9 6

Bảng trợ giúp:
Work >= Needi Pi Allocation
2 2 P2 2
4 ? ? ?

Không nên đáp ứng yêu cầu Request3 vì hệ thống sẽ không an toàn (không tìm thấy chuỗi an toàn).

Admin
Trước khi kết luận là không nên đáp ứng yêu cầu Request3, cần khẳng định là không tồn tại chuỗi an toàn nào (chỉ tìm được 1 chuỗi không đầy đủ bắt đầu từ P2) !

Cảm ơn thầy đã hướng dẫn thêm cho em

MaiThiHongTham70 (113A) 6/10/2012, 22:48

Cảm ơn thầy và các bạn đã giúp em hiểu rõ hơn bài tập này

nguyenchithuc(113A) 11/10/2012, 02:06

Một hệ thống có 10 máy qué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 (3,1,1) và Max (9,4,8 ).
Dùng thuật giả 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 cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process Allocation Max Need Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7

Bảng trợ giúp:
Work >= Needi Pi Allocation
5 3 P2 1
6 6 P1 3
9 7 P3 1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là 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 cho tiến trình P3
Gọi yêu cầu là Request3. Ta cáo Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process Allocation Max Need Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6

Bảng trợ giúp:
Work >= Needi Pi Allocation
4 3 P2 1
5 ? ? ?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn

NguyenNgocThuan76_113A 14/10/2012, 03:10

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

Tiến Trình	Đã Cấp	Tối Đa Cần(MAX)
P₁	5	10
P₂	2	4
P₃	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ó
P₁	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+2)=3
P₂	2	4	(MAX- ĐangGiữ)=4-2=2
P₃	2	9	(MAX- ĐangGiữ)=9-2=7

Work >=	Need	P_i	Allocation
3	2	P₂	2
5	5	P₁	5
10	7	P₃	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ó
P₁	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+3)=2
P₂	2	4	(MAX- ĐangGiữ)=4-2=2
P₃	3	9	(MAX- ĐangGiữ)=9-3=6

[/tr]

Work >=	Need	P_i	Allocation
2 >=	2	P₂	2
4 <	5	P₁	5 //không đáp ứng được 4<5
4<	6	P₃	3 //không đáp ứng được

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₃

NguyenVanQuan105 25/10/2012, 10:42

4 Điều kiện:
+ Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-sharable), nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được sử dụng nó.
+ Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác.
+ Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi sử dụng xong.
+ Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là { P1 , P2, ... , Pn }, khi đó P1 chờ TN giữ bởi P2 , tiến trình P2 chờ TN giữ bởi P3 , ... , Pn chờ P1 .
* Bốn điều kiện này không hoàn toàn độc lập với nhau: ví dụ, Điều kiện 4 kéo theo Điều kiện 2.

Giải pháp xử lý:
1. Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
2. Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
3. Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).
Biện pháp ngăn chặn:
Bằng cách sao cho ít nhất 1 trong 4 điều kiện cần kể trên không xảy ra.
° Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
° Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
° Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
° Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

Sponsored content

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