Thảo luận Bài 8

Trang 9 trong tổng số 10 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

Bài gửi  PhamVanNgo(I11C) on 10/11/2011, 16:50

DuongTrungTinh(I11C) đã viết:
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ê Sad .

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

Chào cả nhà, như khi trên lớp học thì cũng có bạn hỏi tại sao cùng thời điểm đó cũng có 1 tiến trình khác thỏa đk mà kô chọn mà lại chọn tiến trình khác, và Thày cũng có trả lời là chúng ta có thể tìm được nhiều hơn 1 chuỗi an toàn mà. Mình còn nhớ là Thày nói về nhà tìm thêm các chuỗi an toàn khác nữa và post lên diễn đàn thảo luận đấy. Nhưng quan trọng là chúng ta hiểu và làm được đã là thành công 1 bước rồi.

PhamVanNgo(I11C)

Tổng số bài gửi : 23
Join date : 30/09/2011
Đến từ : HCTH11C

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  PhamHuyHoang (I11C) on 10/11/2011, 23:59

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.
bạn ơi cho mình hỏi là khi cấp thêm 1 máy nữa sao hệ thống vẫn còn 3 máy quét hình?

PhamHuyHoang (I11C)

Tổng số bài gửi : 13
Join date : 27/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  tranvanhai_21(I11c) on 13/11/2011, 08:33

ledinhngankhanh (i11c) đã 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
P24-2 =2
P3 9-2= 7

Work Need(i) P(i) Allocation
3 >= 2P2 2
5 >=4 P15
10 >= 7P3 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ó
P15 52
P2 22 2
P33 6 2

[tr]
Work Need(i) P(i) Allocation
2 >= 2P2 2
4 <5 P15
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.

mình cũng giả ra không thoã điều kiện giống như bạn làn không thể đáp ứng được thêm 1 ổ cho P3.
nhưng mình bổ xung ý của bạn là :
câu b :
- Request (3)<= need (3) thoả vì 1 <=7
- Request (3)<= available thoả vì 1<=3
--> đáp án cuối cùng là không thể cấp thêm 1 ổ cho P3.
avatar
tranvanhai_21(I11c)

Tổng số bài gửi : 47
Join date : 25/08/2011
Age : 34
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 14/11/2011, 19:06

PhamHuyHoang (I11C) đã viết:
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.
bạn ơi cho mình hỏi là khi cấp thêm 1 máy nữa sao hệ thống vẫn còn 3 máy quét hình?
T sửa lại bài làm hoàn chỉnh về cách trình bày như bữa cuối đi học thầy có ôn như sau:
Bài giải
a/ Ta có: Available = 3-(1+1)=1
Need=Max-Allocation=(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=Max-Allocation=(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.
Bạn Hoàng hỏi "khi cấp thêm 1 máy nữa sao hệ thống vẫn còn 3 máy quét hình"
T hiểu theo cách hiểu mình như sau: Theo đề bài: Có đáp ứng hay không yêu cầu cấp thêm 1 máy nữa của P2 ->lúc này ta xét đề bài yêu cầu thêm bao nhiêu máy của tiến trình, xem có thỏa điều kiện Request [2] <= Need [2]Request [2] <=Available nếu thỏa điều kiện thì số tiến trình của P2 thay đổi, sau đó làm các bước như trên, hệ thống đề bài không thay đổi tức là vẫn có 3 máy quét. Nếu không thỏa thì kết luận không đáp ứng như yêu cầu đề bài. Với bài này yêu cầu cấp thêm 1 máy nữa của P2 tức là Request [2]=1 nên thỏa điều kiện.
T giải thích vậy nếu không đúng các bạn góp ý với nha.
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 15/11/2011, 00:01

minhgiangbc đã viết: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
T làm bài này như sau bạn minhgiangbc xem có giống bài bạn làm không nha.
A/CM trạng thái này an toàn ?
Ta có bảng sau:

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

Kết luận: Tồn tại chuỗi an toàn {P2,P2,P3}
B/xác định có nên đáp ứng hay không yêu cầu xin them 2 ổ nữa của p3?
Xét điều kiện: Request [3]<=Need[3] thỏa vì 2<=2
Request[3] <=Available không thỏa vì 2>1
Vậy không đáp ứng được yêu cầu xin cấp thêm 2 ổ nữa của P3.
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

Tổng hợp lại các định nghĩa

Bài gửi  NguyenMinhNhut.(I11c) on 15/11/2011, 11:15

Mình xin tổng hợp lại những định nghĩa hôm bữa thầy cho kiểm tra

khái niệm time-sharering: (hệ chia thời gian): mỗi tiến trình chỉ được dùng cpu 1 thời gian
ngắn, sau đó bị ngắt (dù chưa thực hiện xong) và chuyển cpu cho tiến trình khác, cứ thế
xoay vòng
ví dụ: trong chương trình truyền hình, khi hết giờ chiếu phim thì sẽ chuyển sang chương
trình khác ví dụ như thời sự, hôm sau lại quay lại chiếu phim tiếp. hoặc trong nhà hàng
người bồi bàn phục vụ mỗi bàn trong 1 thời gian ngắn sau đó chuyển sang bàn khác

khái niệm Symmetric Multiprocessor system (đa xử lý đối xứng): các cpu chung bộ nhớ và
thiết bị, các cpu này ngang hàng nhau.
ví dụ: tổng đài 1088 có nhiều cô điện thoại viên và các cô này ngang hàng nhau.

khái niệm caching (nguyên tắc lưu gần):dữ liệu, các lệnh được đưa từ RAM (bộ nhớ thứ
cấp) sang cache (bộ nhớ sơ cấp) (không phải thanh ghi), cpu sẽ lấy thông tin đó từ cache
mà không phải lấy từ RAM
ví dụ: nước chứa trong bể được chuyển sang thùng. nước từ thùng được chuyển sang ấm
nước, nước từ ấm rót ra ly khi cần sử dụng

khái niệm thread-pool (tập luồng): khi tiến trình cha được khởi tạo thì cũng đồng thời khởi
tạo 1 tập luồng gồm nhiều luồng con, các luồng con này trong trạng thái sẵn sàng. khi có 1
yêu cầu tới tiến trình cha (ví dụ webSever) thì 1 luồng con được đưa vào sử dụng, sau khi
xong thì luồng con được trả về cho tiến trình cha. khi số lượng yêu cầu > số luồng con thì
phải chờ cho đến khi có 1 luồng con được trả về cho tiến trình cha để sử dụng tiếp
ví dụ: trong doanh trại có 1 đội quân, khi có 1 tên địch đến thì 1 anh lính được cử ra chiến
đấu. sau khi chiến đấu xong thì anh lính quay lại đội quân và ngủ

khái niệm Preemptive scheduling (điều phối tiếm quyền): khi 1 tiến trình hết thời lượng
(hoặc tiến trình mới có thời lượng CPU ngắn hơn, hoặc có độ ưu tiên cao hơn) thì bị HDH
thu hồi CPU/ tài nguyên lại để cấp cho tiến trình mới đó.
ví dụ: trong chương trình truyền hình, khi đang chiếu phim thì bị chen phần quảng cáo vào

khái niệm Busy-waiting (chờ bận): khi buffer đầy/rỗng thì nhà sản xuất/nhà tiêu thụ không
được sắp thêm sản phẩm/ lấy sản phẩm và phải chờ (vòng lặp tại chỗ kiểm tra buffer có
đầy/rỗng không). đến khi có chỗ trống/có sản phẩm thì mới được tiếp tục công việc
ví dụ: vào các dịp lễ tết thì hành khách nhiều, do đó số lượng tàu/xe không đủ để đáp ứng.
khi đó hành khách phải liên tục gọi điện đến bến xe/ nhà ga để hỏi xem có vé xe/tàu không

khái niệm Mutual exclusion (loại trừ lẫn nhau hay loại trừ tương hỗ): tại mỗi thời điểm chỉ
có 1 tiến trình vào đoạn tương tranh, tức là chỉ có 1 tiến trình được phép truy cập, sử dụng,
thay đổi bộ nhớ chung/ tài nguyên dùng chung
ví dụ: khi chụp hình tập thể thì chỉ có 1 người sắp xếp người đứng chụp là người thơ chụp
hình. nếu có 1 người nữa sắp xếp thì sẽ mất trật tự, không chụp hình được

NguyenMinhNhut.(I11c)

Tổng số bài gửi : 8
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 15/11/2011, 13:27

NguyenMinhNhut.(I11c) đã viết:Mình xin tổng hợp lại những định nghĩa hôm bữa thầy cho kiểm tra

khái niệm time-sharering: (hệ chia thời gian): mỗi tiến trình chỉ được dùng cpu 1 thời gian
ngắn, sau đó bị ngắt (dù chưa thực hiện xong) và chuyển cpu cho tiến trình khác, cứ thế
xoay vòng
ví dụ: trong chương trình truyền hình, khi hết giờ chiếu phim thì sẽ chuyển sang chương
trình khác ví dụ như thời sự, hôm sau lại quay lại chiếu phim tiếp. hoặc trong nhà hàng
người bồi bàn phục vụ mỗi bàn trong 1 thời gian ngắn sau đó chuyển sang bàn khác

khái niệm Symmetric Multiprocessor system (đa xử lý đối xứng): các cpu chung bộ nhớ và
thiết bị, các cpu này ngang hàng nhau.
ví dụ: tổng đài 1088 có nhiều cô điện thoại viên và các cô này ngang hàng nhau.

khái niệm caching (nguyên tắc lưu gần):dữ liệu, các lệnh được đưa từ RAM (bộ nhớ thứ
cấp) sang cache (bộ nhớ sơ cấp) (không phải thanh ghi), cpu sẽ lấy thông tin đó từ cache
mà không phải lấy từ RAM
ví dụ: nước chứa trong bể được chuyển sang thùng. nước từ thùng được chuyển sang ấm
nước, nước từ ấm rót ra ly khi cần sử dụng

khái niệm thread-pool (tập luồng): khi tiến trình cha được khởi tạo thì cũng đồng thời khởi
tạo 1 tập luồng gồm nhiều luồng con, các luồng con này trong trạng thái sẵn sàng. khi có 1
yêu cầu tới tiến trình cha (ví dụ webSever) thì 1 luồng con được đưa vào sử dụng, sau khi
xong thì luồng con được trả về cho tiến trình cha. khi số lượng yêu cầu > số luồng con thì
phải chờ cho đến khi có 1 luồng con được trả về cho tiến trình cha để sử dụng tiếp
ví dụ: trong doanh trại có 1 đội quân, khi có 1 tên địch đến thì 1 anh lính được cử ra chiến
đấu. sau khi chiến đấu xong thì anh lính quay lại đội quân và ngủ

khái niệm Preemptive scheduling (điều phối tiếm quyền): khi 1 tiến trình hết thời lượng
(hoặc tiến trình mới có thời lượng CPU ngắn hơn, hoặc có độ ưu tiên cao hơn) thì bị HDH
thu hồi CPU/ tài nguyên lại để cấp cho tiến trình mới đó.
ví dụ: trong chương trình truyền hình, khi đang chiếu phim thì bị chen phần quảng cáo vào

khái niệm Busy-waiting (chờ bận): khi buffer đầy/rỗng thì nhà sản xuất/nhà tiêu thụ không
được sắp thêm sản phẩm/ lấy sản phẩm và phải chờ (vòng lặp tại chỗ kiểm tra buffer có
đầy/rỗng không). đến khi có chỗ trống/có sản phẩm thì mới được tiếp tục công việc
ví dụ: vào các dịp lễ tết thì hành khách nhiều, do đó số lượng tàu/xe không đủ để đáp ứng.
khi đó hành khách phải liên tục gọi điện đến bến xe/ nhà ga để hỏi xem có vé xe/tàu không

khái niệm Mutual exclusion (loại trừ lẫn nhau hay loại trừ tương hỗ): tại mỗi thời điểm chỉ
có 1 tiến trình vào đoạn tương tranh, tức là chỉ có 1 tiến trình được phép truy cập, sử dụng,
thay đổi bộ nhớ chung/ tài nguyên dùng chung
ví dụ: khi chụp hình tập thể thì chỉ có 1 người sắp xếp người đứng chụp là người thơ chụp
hình. nếu có 1 người nữa sắp xếp thì sẽ mất trật tự, không chụp hình được
Bạn NguyenMinhNhut post bài nhầm topic rùi đóa, thầy có làm riêng topic Giải đề thi kiểm tra giữa kỳ mà, bạn xem lại nha, dù sao cũng Thank bài giải của bạn hj.
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  nguyenthithuylinh (I11C) on 17/11/2011, 22:10

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.

nguyenthithuylinh (I11C)

Tổng số bài gửi : 23
Join date : 26/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 20/11/2011, 08:16

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.


Được sửa bởi ThanhThao04(I11C) ngày 20/11/2011, 23:17; sửa lần 1.
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

Học trên này thấy cũng rất là đủ

Bài gửi  NguyenDongGiang on 20/11/2011, 10:17

Học trên này thấy cũng đầy đủ, cảm ơn các bạn nhiều!
avatar
NguyenDongGiang

Tổng số bài gửi : 19
Join date : 23/02/2011
Age : 29

Xem lý lịch thành viên http://nguyendonggiang.blogspot.com

Về Đầu Trang Go down

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

Bài gửi  08H1010052 on 21/11/2011, 08:56

ledinhngankhanh (i11c) đã 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
P24-2 =2
P3 9-2= 7
Work Need(i) P(i) Allocation
3 >= 2P2 2
5 >=4 P15
10 >= 7P3 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ó
P15 52
P2 22 2
P33 6 2

[tr]
Work Need(i) P(i) Allocation
2 >= 2P2 2
4 <5 P15
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ài giải của bạn đúng rồi đấy. Các bạn tham khảo để nắm được cách làm bài nha vì bài thi Thầy nói cũng sẽ có dạng này chỉ thay đổi số liệu thôi.
Chúc các bạn thành công!

08H1010052

Tổng số bài gửi : 52
Join date : 02/07/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  NguyThiGai (I11C) on 21/11/2011, 09:10

08H1010052 đã viết:
ledinhngankhanh (i11c) đã 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
P24-2 =2
P3 9-2= 7
Work Need(i) P(i) Allocation
3 >= 2P2 2
5 >=4 P15
10 >= 7P3 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ó
P15 52
P2 22 2
P33 6 2

[tr]
Work Need(i) P(i) Allocation
2 >= 2P2 2
4 <5 P15
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ài giải của bạn đúng rồi đấy. Các bạn tham khảo để nắm được cách làm bài nha vì bài thi Thầy nói cũng sẽ có dạng này chỉ thay đổi số liệu thôi.
Chúc các bạn thành công!
Bài giải của bạn ledinhngankhanh (i11c) đúng rồi nhưng need của P1 ở trên là 5 mà xuống dưới ghi là 4. Như vậy có bị Thầy trừ điểm không nhỉ?

Admin
- Em phát hiện đúng.
- Không bị trừ điểm ! (bạn "sơ suất" chút thôi)

NguyThiGai (I11C)

Tổng số bài gửi : 28
Join date : 26/08/2011
Age : 30

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  DaoVanHoang (I11C) on 21/11/2011, 21:21

08H1010052 đã viết:
ledinhngankhanh (i11c) đã 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
P24-2 =2
P3 9-2= 7
Work Need(i) P(i) Allocation
3 >= 2P2 2
5 >=5 P15
10 >= 7P3 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ó
P15 52
P2 22 2
P33 6 2

[tr]
Work Need(i) P(i) Allocation
2 >= 2P2 2
4 <5 P15
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ài giải của bạn đúng rồi đấy. Các bạn tham khảo để nắm được cách làm bài nha vì bài thi Thầy nói cũng sẽ có dạng này chỉ thay đổi số liệu thôi.
Chúc các bạn thành công!
vậy là bài tập chỉ có 2 dạng là thuật giải nhà băng và điều phối dạng Round Robin thui đó các bạn à, cố gắng ôn thật kỹ để lấy trọn điểm bài tập nhé ^^

DaoVanHoang (I11C)

Tổng số bài gửi : 24
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 22/11/2011, 11:03

PhamVanNgo(I11C) đã viết:
NgoDucTuan (I11C) đã viết:
Bạn nào hiểu thuật giải nhà băng giúp mình giải thích và giải bài toán này. Theo đề bên trên.
Cảm ơn các bạn đã giúp mình.
Very Happy

Hi bạn, mình sẽ giải theo những gì mình hiểu nhé. nếu sai thì cùng nhau sửa và học hỏi lẫn nhau nhé Laughing
a) Buớc 1 : Phải đi tính Need = MAX - Allocation
TT Need
ABCD
P0 0000
P1 0750
P2 1002
P3 0020
P4 0642

Bước 2 : Tìm chuỗi an toàn của hệ thống:
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

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.

b) Giả sử P1 có y/cầu mới = (0,4,3,0)
Dựa vào y/cầu mới của P1 ta có thể khẳng định không nên đáp ứng y/cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available <==> (0,4,3,0) kô <= (1,5,2,0)

giải thích thêm : việc xem xét có đáp ứng y/cầu mới hay kô thì phải thỏa 2 đk sau :
1. Request(i) <= Available
2. Request(i) <= MAX(i)
===========
Xin mọi người chỉ giáo thêm.

T xin góp ý: Xét điều kiện Request(i) <= Need(i) chứ không phải Request(i) <= MAX(i)
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamdieptuan (I11C) on 29/11/2011, 11:11

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.
Mình thấy bài này bạn giải rất rõ và dễ hiểu, mình cũng chung đáp án với ban.

phamdieptuan (I11C)

Tổng số bài gửi : 21
Join date : 26/08/2011
Age : 30
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamdieptuan (I11C) on 29/11/2011, 11:57

minhgiangbc đã viết: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

Theo mình giải bài này như sau:
a)
Available = 5 - (1 + 2 + 1) = 1
Need = Max - Allocation
PAllocation MAx Need Available
P1 1 3 2
P2 22 0 1
P3 13 2
Tìm chuỗi an toàn:
Work>= Need[i] P[i] Allocation[i]
1 0P2 2
32 P1 1
4 2P3 1
=>Tồn tại chuỗi an toàn{P2, P1, P3}
Vậy tại thời điểm Ti trang thái hệ thống là an toàn.

b) Yêu cầu xin thêm 2 ổ nữa của p3
Không đủ tài nguyên vì Request3 > Available (2 > 1).
=>Không thể đáp ứng yêu cầu xin thêm 2 ổ nữa của P3.

Mong thầy và các bạn góp ý thêm.

phamdieptuan (I11C)

Tổng số bài gửi : 21
Join date : 26/08/2011
Age : 30
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  Duongthithanhhuynh (I11C) on 30/11/2011, 09:26

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

Dù sao cũng thanks bạn nhiều nhan
hi quan trọng là mình hiểu thôi bạn ơi, nhưng suy nghĩ lại thì post lên cũng quan trọng lắm vì có post lên thầy mới biết là mình có làm và có lên forum. mà mình thấy có nhiều bài post trùng nhau nhiều quá vô đọc hoa cả mắt, mong là thầy đừng chấm điểm theo số lượng.
avatar
Duongthithanhhuynh (I11C)

Tổng số bài gửi : 26
Join date : 26/08/2011
Age : 28
Đến từ : Tiền Giang

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  ThanhThao04(I11C) on 30/11/2011, 13:36

phamdieptuan (I11C) đã viết:
minhgiangbc đã viết: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

Theo mình giải bài này như sau:
a)
Available = 5 - (1 + 2 + 1) = 1
Need = Max - Allocation
PAllocation MAx Need Available
P1 1 3 2
P2 22 0 1
P3 13 2
Tìm chuỗi an toàn:
Work>= Need[i] P[i] Allocation[i]
1 0P2 2
32 P1 1
4 2P3 1
=>Tồn tại chuỗi an toàn{P2, P1, P3}
Vậy tại thời điểm Ti trang thái hệ thống là an toàn.

b) Yêu cầu xin thêm 2 ổ nữa của p3
Không đủ tài nguyên vì Request3 > Available (2 > 1).
=>Không thể đáp ứng yêu cầu xin thêm 2 ổ nữa của P3.

Mong thầy và các bạn góp ý thêm.
hj bạn, bài bạn làm giống t đó, ah t có post bài nì ròi, bạn tham khảo thêm ngen.
avatar
ThanhThao04(I11C)

Tổng số bài gửi : 34
Join date : 31/08/2011
Đến từ : Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  DuongTrungTinh(I11C) on 30/11/2011, 21:47

Tranvancanh(I11C) đã viết: - Định nghĩa Deadlock (Kẹt khoá): 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.
- Deadlock 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.
+ Yêu cầu tài nguyên.
+ Sử dụng tài nguyên.
+ Trả lại tài nguyên.

Các VD minh họa:
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ớ Razz .
Phương pháp xử lý deadlock :
- Sử dụng 1 giao thức để hệ thống không bao giờ rơi vào trạng thái deadlock (Ngăn chặn bế tắc, tránh bế tắc ).
- Có thể cho phép hệ thống bị deadlock, phát hiện deadlock và xử lý deadlock đó.
- Bỏ qua deadlock, xem như deadlock chẳng bao giờ xuất hiện trong hệ thống (dùng nhiều trong windows và Unix).
Giải pháp chặn deadlock : Bằng cách phủ định một trong bốn điều kiện trên như sau:
+ Loại trừ lẫn nhau (Mutual Exclusion).
+ Giữ và chờ (Hold and Wait).
+ Không có tiếm quyền (No Preemption).
+ Chờ xoay vòng (Circular Wait).

Bài viết rất hay, mình thích ví dụ 2 con dê Laughing cám ơn bạn nhiều.

DuongTrungTinh(I11C)

Tổng số bài gửi : 31
Join date : 26/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  leanhhuy (I11C) on 3/12/2011, 09:07

[quote="08H1010052"]
ledinhngankhanh (i11c) đã 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
P24-2 =2
P3 9-2= 7
Work Need(i) P(i) Allocation
3 >= 2P2 2
5 >=4 P15
10 >= 7P3 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ó
P15 52
P2 22 2
P33 6 2

[tr]
Work Need(i) P(i) Allocation
2 >= 2P2 2
4 <5 P15
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.

Thanks bạn nhiều ,bài giải đúng chỉ sơ suất nhỏ chổ số 4 và 5 thôi ,mọi người thi tốt nha

leanhhuy (I11C)

Tổng số bài gửi : 22
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Nhờ mọi người giải thích dùm!

Bài gửi  NgoDucTuan (I11C) on 3/12/2011, 12:10



Tại sao mình biết "tiến trình P3 đang chờ tiến trình P1 hay P2 trả lại tài nguyên R2" và " tiến trình P1 đang chờ tiến trình P2 trả lại phiên bản tài nguyên R1 "?

"tiến trình P4 có thể trả lại phiên bản của loại tài nguyên R2" ????

Cảm ơn mọi người nhiều. Chúc mọi người thi tốt nhé!
avatar
NgoDucTuan (I11C)

Tổng số bài gửi : 52
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  lytrannhutlinh i11c on 3/12/2011, 12:26


Tại sao mình biết "tiến trình P3 đang chờ tiến trình P1 hay P2 trả lại tài nguyên R2"


Bạn có thấy cái mũi tên của 2 phiên bản của R2 trỏ vào P1, P2 không ? Tưc là Nó đã cấp cho P1 và P2 rồi. Mũi tên P3 trỏ vào R2 tức là P3 đang yêu cầu 1 phien bản cho mình .. R2 đã cấp hết cho P1 và P2 nên nó phải chờ thôi .

và " tiến trình P1 đang chờ tiến trình P2 trả lại phiên bản tài nguyên R1 "?

Tương tự vậy R1 có 1 và đã cấp cho P2 rồi , P1 yêu cầu thì phải chờ thôi

"tiến trình P4 có thể trả lại phiên bản của loại tài nguyên R2" ????

Tức là sau 1 thời gian T nào đó, P4 sẽ sữ dụng xong tài nguyên của R2 nên nó trả lại và R2 nó sẽ cung cấp cho P3 đang yêu cầu thì sẽ không có chu trình nữa và k có deadlock


lytrannhutlinh i11c

Tổng số bài gửi : 50
Join date : 26/08/2011
Age : 29

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  PhamThiHoa-I91C on 3/12/2011, 14:35

PhamVanNgo(I11C) đã viết:
NgoDucTuan (I11C) đã viết:
Bạn nào hiểu thuật giải nhà băng giúp mình giải thích và giải bài toán này. Theo đề bên trên.
Cảm ơn các bạn đã giúp mình.
Very Happy

Hi bạn, mình sẽ giải theo những gì mình hiểu nhé. nếu sai thì cùng nhau sửa và học hỏi lẫn nhau nhé Laughing
a) Buớc 1 : Phải đi tính Need = MAX - Allocation
TT &nbsp;&nbsp; Need
&nbsp;&nbsp; ABCD
P0 &nbsp;&nbsp; 0000
P1 &nbsp;&nbsp; 0750
P2 &nbsp;&nbsp; 1002
P3 &nbsp;&nbsp; 0020
P4 &nbsp;&nbsp; 0642

Bước 2 : Tìm chuỗi an toàn của hệ thống:
Work >= &nbsp;&nbsp; Needi &nbsp;&nbsp; Pi&nbsp;&nbsp; &nbsp;&nbsp; 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

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.

b) Giả sử P1 có y/cầu mới = (0,4,3,0)
Dựa vào y/cầu mới của P1 ta có thể khẳng định không nên đáp ứng y/cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available <==> (0,4,3,0) kô <= (1,5,2,0)

giải thích thêm : việc xem xét có đáp ứng y/cầu mới hay kô thì phải thỏa 2 đk sau :
1. Request(i) <= Available
2. Request(i) <= MAX(i)
===========
Xin mọi người chỉ giáo thêm.
Cảm ơn bạn nhiều, giải thích rất dễ hiểu Smile

PhamThiHoa-I91C

Tổng số bài gửi : 29
Join date : 16/09/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  PhamThiHoa-I91C on 3/12/2011, 14:44

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 >

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ình không hiểu khúc này, sao có thể tồn tại chuỗi an toàn được mặc dù đủ điều kiện cấp phát, kết luận vậy là sao hả bạn? bạn có nhầm không?

PhamThiHoa-I91C

Tổng số bài gửi : 29
Join date : 16/09/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  PhamThiHoa-I91C on 3/12/2011, 15:03

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 ý. Very Happy
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) Smile

PhamThiHoa-I91C

Tổng số bài gửi : 29
Join date : 16/09/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  Sponsored content


Sponsored content


Về Đầu Trang Go down

Trang 9 trong tổng số 10 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết