Thảo luận Bài 8

Trang 6 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

Phương pháp giải bài toán: Xác định xem có nên đáp ứng hay không yêu cầu cấp thêm tài nguyên cho tiến trình

Bài gửi  tranphanhieu36_i11c on 6/11/2011, 09:27

Phương pháp này thầy đã giảng chắc là nhiều người biết rồi nhưng mình xin trình bày cho các bạn nào nhìn thấy mấy bài giải mà chẳng biết vì sao lại như thế, chỉ biết làm theo thôi Smile

Mình xin đưa ra một số ý từ ví dụ quản lý tiền ngân hàng của thầy theo cách mình hiểu. Bạn xét lần lượt 2 thứ sau :
1.Đầu tiên các bạn phải xác định yêu cầu này có hợp lệ hay hiện tại hệ có thể đáp ứng không bằng cách xét 2 điều kiện sau
+ Request(i) <= Need(i). Yêu cầu vay tiền > Số tiền cần =>không thể cho vay. Vì cho vay thì số tiền > Max(được vay). Không hợp lý vì giải thuật này hạn chế số tiền cho vay.
+ Request(i) <= Avalable.Yêu câu vay tiền > Số tiền ngân hàng đang có => Hiện giờ không cho vay được. Vì đâu có tiền mà cho vay. Ở thời điểm sau có thể đáp ứng được chứ thời điểm này thì chưa được -> Quay lại sau Smile

2. Khi đã thỏa điều kiện ở bước 1. Ở bước này là: Xét xem "nếu cấp phát tài nguyên theo yêu cầu này thì hệ thống có còn ở trạng thái an toàn nữa không", nếu có (còn tồn tại chuỗi an toàn mới sau khi cấp phát) thì cấp phát. Nếu không (không có chuỗi an toàn mới sau khi cấp phát) thì không cấp phát.
Các bạn giả sử đã cấp phát theo yêu cầu thì sẽ cập nhật lại dữ liệu mới sau khi đã cấp phát và tìm chuỗi an toàn như ở bài trên mình hướng dẫn ở bài trên để xác định xem có nên đáp ứng hay không yêu cầu này nha.
Cụ thể các bạn cập nhật một số dữ liệu mới như sau :
+Cập nhật lại tài nguyên mà tiến trình yêu cầu đang giữ (Allocation) = tài nguyên trước đó + tài nguyên mới yêu cầu.
+Cập nhật lại Need(i)tiến trình yêu cầu sau khi đã cấp phát=Max(i)-Allocation mới tính
+Cập nhật lại tài nguyên mà hệ có =Tài nguyên chưa dùng (cũ)-Tài nguyên tiến trình yêu cầu
=>Với dữ liệu mới hãy tìm chuỗi an toàn và kết luận xem có nên đáp ứng không.

Các bạn có bổ sung gì thì cứ góp ý nha !

Admin
Hiếu đúng. Văn tốt, tuy về "chính tả" có thể hơn được nữa !

tranphanhieu36_i11c

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

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

Về Đầu Trang Go down

Giải bài tập

Bài gửi  Nguyenminhduc (I11C) on 6/11/2011, 21:17

Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:
Tiến trình Đã được cấp Tối đa cần
P1 5 10
P2 2 4
P3 2 9
Dùng thuật giải nhà băng:
Hệ có:Available=12-9=3
Ma trận Need=Max-Allocation:
Need
P1 5
P2 2
P3 7
Xác định chuỗi an toan:
Ta có:
Work need Pi Allocation
3 2 P2 2
5 5 P1 5
10 7 P3 2
=> Tồn tại chuỗi an toàn={P2,P1,P3}
Vậy trạng thái hệ thống là an tòan.

Nguyenminhduc (I11C)

Tổng số bài gửi : 18
Join date : 07/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  LeTanDat (I11C) on 6/11/2011, 21:18

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).
Mình cũng đang thắc mắc nhưng giờ Thầy giải thích thì đã hiểu rồi! Very Happy
Em cám ơn Thầy!

LeTanDat (I11C)

Tổng số bài gửi : 24
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  TrinhThiOanh (I11C) on 6/11/2011, 22:23

tranphanhieu36_i11c đã viết:Phương pháp này thầy đã giảng chắc là nhiều người biết rồi nhưng mình xin trình bày cho các bạn nào nhìn thấy mấy bài giải mà chẳng biết vì sao lại như thế, chỉ biết làm theo thôi Smile

Mình xin đưa ra một số ý từ ví dụ quản lý tiền ngân hàng của thầy theo cách mình hiểu. Bạn xét lần lượt 2 thứ sau :
1.Đầu tiên các bạn phải xác định yêu cầu này có hợp lệ hay hiện tại hệ có thể đáp ứng không bằng cách xét 2 điều kiện sau
+ Request(i) <= Need(i). Yêu cầu vay tiền > Số tiền cần =>không thể cho vay. Vì cho vay thì số tiền > Max(được vay). Không hợp lý vì giải thuật này hạn chế số tiền cho vay.
+ Request(i) <= Avalable.Yêu câu vay tiền > Số tiền ngân hàng đang có => Hiện giờ không cho vay được. Vì đâu có tiền mà cho vay. Ở thời điểm sau có thể đáp ứng được chứ thời điểm này thì chưa được -> Quay lại sau Smile

2. Khi đã thỏa điều kiện ở bước 1. Ở bước này là: Xét xem "nếu cấp phát tài nguyên theo yêu cầu này thì hệ thống có còn ở trạng thái an toàn nữa không", nếu có (còn tồn tại chuỗi an toàn mới sau khi cấp phát) thì cấp phát. Nếu không (không có chuỗi an toàn mới sau khi cấp phát) thì không cấp phát.
Các bạn giả sử đã cấp phát theo yêu cầu thì sẽ cập nhật lại dữ liệu mới sau khi đã cấp phát và tìm chuỗi an toàn như ở bài trên mình hướng dẫn ở bài trên để xác định xem có nên đáp ứng hay không yêu cầu này nha.
Cụ thể các bạn cập nhật một số dữ liệu mới như sau :
+Cập nhật lại tài nguyên mà tiến trình yêu cầu đang giữ (Allocation) = tài nguyên trước đó + tài nguyên mới yêu cầu.
+Cập nhật lại Need(i)tiến trình yêu cầu sau khi đã cấp phát=Max(i)-Allocation mới tính
+Cập nhật lại tài nguyên mà hệ có =Tài nguyên chưa dùng (cũ)-Tài nguyên tiến trình yêu cầu
=>Với dữ liệu mới hãy tìm chuỗi an toàn và kết luận xem có nên đáp ứng không.

Các bạn có bổ sung gì thì cứ góp ý nha !

Admin
Hiếu đúng. Văn tốt, tuy về "chính tả" có thể hơn được nữa ! Bạn này triển vọng. Sau khi có bằng đại học, nên chuyển ngay lên Cao học ! Sau này liên hệ lại để thày tư vấn !

Bài trước thầy giảng trên lớp mình chỉ hiểu cách làm bài nhưng không hiểu ví dụ thầy cho lắm. Khi đọc qua bài này thì mình có thể hiểu sâu sắc hơn>> Không chỉ bài này mà các bài khác cũng cần phải hiểu chi tiết như thế.HI Kams un Thày và bạn nhiều! Chúc các bạn ai cũng qua được môn này!

TrinhThiOanh (I11C)

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

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  TrinhThiOanh (I11C) on 6/11/2011, 22: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 >


Cám ơn bạn!
Có vài chỗ chưa hiểu qua bài này thì vài chỗ còn lơ tơ mơ đã được rõ. Chỉ có điều cách trình bày chưa rõ ràng. Bạn chịu khó vẽ form đàng hoàng sẽ giúp mọi người dễ hình dung hơn. Kams un

TrinhThiOanh (I11C)

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

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  VoMinhHoang (I11C) on 7/11/2011, 00:04

ngocquynh2091(i11C) đã viết:
LaVanKhuong (I11C) đã viết:Đị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.
ví dụ:
Có hai xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có một làm xe nên khi hai xe vào đến giữa cầu thì không thể tiếp tục tiến đi được nữa xảy ra kẹt xe(deadlock) vì không người nào chịu nhường đường.

ví dụ về deadlock không liên quan đến môi trường máy tính:
1. Hai chiếc xe đi qua một cây cầu chỉ có 1 làn đường.

2. Một người đi xuống một cái thang, trong khi một người khác đang leo lên

3. Hai đoàn tàu đi trên cùng một tuyến đường.

4. Hai thợ mộc cùng phải đóng những cái đinh. Có một cây búa duy nhất và một thùng duy nhất chứa những cái đinh. Deadlock xảy ra nếu một người có búa và người khác có đinh.

Ví dụ của bạn về 2 người thợ mộc và xảy ra Deadlock - kẹt vùng tranh chấp 1 người giữ búa còn ngkia giữ đinh- có tranh chấp xảy ra. thks bạn! Very Happy

VoMinhHoang (I11C)

Tổng số bài gửi : 26
Join date : 08/09/2011
Age : 31
Đến từ : Tp Tan An - Long An

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  VoMinhHoang (I11C) on 7/11/2011, 00:29

08H1010052 đã viết:Định nghĩa: Là 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.
Ví dụ: Tại ngã 4, 4 xe tại 4 hướng khác nhau cùng đến giao lộ, không xe nào chịu nhường đường cho xe nào nên tất cả đều phải chờ đến khi có đường trống để đi => kết quả là kẹt xe. Như thế tất cả 4 xe đều trong trạng thái chờ hay nói cách khác các tiến trình đang chờ tài nguyên của nhau và cứ xoay vòng và như thế tất cả tiến trình đều kẹt(deadlock).
Deadlock là một vấn đề quan trọng không những lĩnh vực công nghệ(chương trinh vận hành) mà còn ảnh hưởng đến các lĩnh vực khác trong đời sống(như là giao thông).
+ Công nghệ: nếu 1 chương trình đang vận hành một hệ thống gì đó quan trọng phức tạp và nguy hiểm thì tuy deadlock rất hiếm gặp nhưng khi xảy ra thì sẽ mang lại thiệt hại cực kì nghiêm trọng, có thể làm sụp đổ cả 1 hệ thống (vd: nhà máy điện hạt nhân nếu mà bị kẹt tiến trình => hệ thống làm lạnh các thanh nhiên liệu nguyên tử không hoạt động thì nhiệt độ tăng cao gây ra nổ hạt nhân. Chất phóng xạ lan ra ngoài sẽ tàn phá sự sống.)
+ Còn trong giao thông: sẽ gây kẹt xe làm trễ công việc => gây thiệt hại rất lớn về tiền bạc cũng như thời gian.

Thân chào!

Bổ sung thêm nếu ko có cảnh sát giao thông làm nhiệm vụ điều phối làn đường cho các xe chạy thì Deadlock cứ tiếp diễn- Deadlock là tình trạng kẹt mãi mãi Arrow

VoMinhHoang (I11C)

Tổng số bài gửi : 26
Join date : 08/09/2011
Age : 31
Đến từ : Tp Tan An - Long An

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  HoiHoangHongVu I11C on 7/11/2011, 08:22

TrinhThiOanh (I11C) đã viết:
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ám ơn bạn!
Có vài chỗ chưa hiểu qua bài này thì vài chỗ còn lơ tơ mơ đã được rõ. Chỉ có điều cách trình bày chưa rõ ràng. Bạn chịu khó vẽ form đàng hoàng sẽ giúp mọi người dễ hình dung hơn. Kams un
Sao mà rối quá vậy ta. hix

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồng Nai

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

Về Đầu Trang Go down

Thuật giải tránh deadlock RAG

Bài gửi  onlyminhlong on 7/11/2011, 10:06

Thuật giải tránh deadlock RAG (áp dụng cho trường hợp loại tài nguyên chỉ có 1 phiên bản) nếu có nhiều phiên bản thuật giải này không dùng được:
- Trên RAG, lúc đầu tất cả nhu cầu về tài nguyên của tiến trình phải được khai báo trước bằng các Cung Nhu cầu (Claim edge) Pi • • •> Rj chỉ báo rằng Pi có thể sẽ yêu cầu Rj - Cung Nhu cầu Pi • • •> Rj được chuyển thành Cung Yêu cầu (Request edge) Pi • • •> Rj khi Pi thực sự bắt đầu cần đến Rj . - Nếu yêu cầu Pi • • •> Rj được HĐH đáp ứng, cung Pi • • •> Rj chuyển thành Cung Ấn định (Assignment edge) Pi <• • • Rj nối phiên bản duy nhất của Rj với Pi . - Khi HĐH xét yêu cầu Pi • • •>Rj. Hệ chỉ cấp phát Rj cho Pi nếu Cung Ấn định Pi <• • • Rj không tạo ra vòng tròn đồng hướng trong RAG (xét cả các Cung Nhu cầu). - Thuật giải có độ phức tạp o(n²) với n là số tiến trình trong hệ. Ví dụ trách deadlock dùng RAG: Đầu tiên khai báo tất cả các nhu cầu của P1 và P2:P1 và P2 có thể sử dụng R1,R2.


onlyminhlong

Tổng số bài gửi : 3
Join date : 01/12/2009

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

Về Đầu Trang Go down

Định nghĩa Deadlock. Ví dụ

Bài gửi  TranQuyThanh (I11C) on 7/11/2011, 10:10

Deadlock: là tình huống kẹt tiến trình (process) với một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang có.

Ví dụ 1

Giả sử hệ thống có 2 file trên đĩa.

P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia.

Ví dụ 2

Semaphore A và B, khởi tạo bằng 1

P0 P1

wait (A); wait(B)

wait (B); wait(A)

TranQuyThanh (I11C)

Tổng số bài gửi : 53
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  chauchanduong (I11C) on 7/11/2011, 10:12

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


Deadlock là trạng thái xảy ra trong môi trường đa nhiệm khi 2 hoặc nhiều tiến trình đi vào vòng lặp chờ tài nguyên mãi mãi.

Chào Thầy, Chào Loan và tất cả các bạn
- Dương có một ví dụ thức tế đời thường mời các bạn xem và cùng nhau thảo luận nha.
- 3 tuần trước Dương có đi siêu thị Big C ở Tô Hiến Thành, khi đến nơi thì phải gửi xe . Nhưng hôm đó thì chỉ có 1 người vừa ghi thẻ gữi xe vừa bấm thẻ xe, thế thì tại thời điểm 6h thì chỉ có vài xe thôi, nhưng 10 phút sau xe càng lúc càng đông và xảy ra tình huống kẹt xe và những người gữi xe phải chờ cho người ghi thẻ phải bấm xong thì mới được vào vì làn xe đi vào rất hẹp chỉ đủ cho 1 chiếc mà thôi, và deadlock đã xãy ra càng lúc càng nhiều.
- Theo Dương nghĩ thì tình huống Dương nêu ra ở đây nó rơi vào 2 trường hợp :
+ Trường hợp 1 : Deadlock
---->Deadlock ở tình huống này là người gữi xe phải chờ cho đến khi người ghi và bấm thẻ xong thì mới được vào, nếu người ghi và bấm thẻ không ghi nữa thì mọi người đến gữi xe sẽ rơi vào tình huống chờ mãi mãi.
+ Trường hợp 2 : Nó rơi vào tình huống đồng bộ hoá tiến trình.
----> Đồng bộ là có chờ , thì ở đây người gửi xe phải chờ cho đến khi người ghi và bấm thẻ xong thì mới được vào.

- Thầy xem và cho nhận xét tình huống em nêu ra ở trên có đúng không Thầy.

Admin
Không đúng ! Phải nêu lại ! Hiểu sai cả khái niệm "Đồng bộ là có chờ".

chauchanduong (I11C)

Tổng số bài gửi : 18
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  chauchanduong (I11C) on 7/11/2011, 10:19

doanhongdao030(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).
Mình cảm ơn bạn đã đưa ra câu hỏi này nha, mình cũng đang thắc mắc cho này, giờ thì mình rõ rồi.
Em cám ơn thầy đã giải đáp

-Ohm không có gì, Ah mình biết bạn rồi, mình tên Dương, nick chat là chau_duong54 và email là: chauchanduong@gmail.com có gì thì pm nhé

chauchanduong (I11C)

Tổng số bài gửi : 18
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  NgoDucTuan (I11C) on 7/11/2011, 11:41

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 PhamVanNgo(I11C) rất nhiều mình đã hiểu vấn đề để giải quyết bài toán rồi.
Chúc tất cả các thành viên lớp mình thi đạt kết quả thật tốt nhé, trước mắt làm bài đạt trong phần thi giữa kỳ sắp tới.

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  08H1010052 on 7/11/2011, 11:42

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.

Thanks bạn nhiều, bài giải rõ ràng dể hiểu!

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  DaoQuangSieu (I11C) on 7/11/2011, 11:49

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

DaoQuangSieu (I11C)

Tổng số bài gửi : 29
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  NgoDucTuan (I11C) on 7/11/2011, 12:13

08H1010052 đã viết:
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.

Thanks bạn nhiều, bài giải rõ ràng dể hiểu!

Chào tất cả các bạn mình xin chia sẻ thêm với các bạn cách giải này:

a. Xét tại thời điểm T0 mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]

Tìm chuỗi an toàn:

Vậy tại thời điểm T0 tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.

b. Ta thấy, yêu cầu thêm (0, 4, 3, 0) của P1 thoả điều kiện Request1 <= Need1, nhưng không thoả điều kiện: Request1 <= Available vì tài nguyên C trong hệ thống chỉ còn 2 mà yêu cầu 3. Do vậy, không thể cấp phát thêm (0, 4, 3, 0) cho P1 được.

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  nguyenquoctruong (I11C) on 7/11/2011, 12:28

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.

nguyenquoctruong (I11C)

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

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

Về Đầu Trang Go down

Điều kiện xảy ra Deadlock : Có bốn điều kiện cần

Bài gửi  LeMinhDuc (I11C) on 7/11/2011, 15:03

+ Điều kiện loại trừ lẫn nhau: Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm

+ Điều kiện giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới

+ Điều kiện không thể chiếm: Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giử chúng

+ Điều kiện chu trình chờ: Các tiến trình giử tài nguyên và chờ các tài nguyên bị giử bởi tiến trình khác, tạo thành một chu trình. Ví dụ: Tiến trình 1, chiếm A1, chờ A2. Tiến trình 2 chiếm A2, chờ A3,... Tiến trình N chiếm An, chờ A1.

Ví dụ : Các ứng dụng cần RAM để xử lý nếu một người mở nhiều ứng dụng cùng lúc RAM sẽ thiếu và dẫn tới deadlock

LeMinhDuc (I11C)

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

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

Về Đầu Trang Go down

Cách phương pháp xử lý deadlock

Bài gửi  HuynhVanNhut (I11C) on 7/11/2011, 15:44

Phần lớn, chúng ta có thể giải quyết vấn đề deadlock theo một trong ba cách:
1. Sử dụng một giao thức để ngăn chặn hay tránh deadlocks, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
2. Cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và phục hồi.
3. Bỏ qua hoàn toàn vấn đề này và giả vờ deadlock không bao giờ xảy ra trong hệ thống. Giải pháp này được dùng trong nhiều hệ điều hành, kể cả UNIX.
4. Tìm hiểu vắn tắt mỗi phương pháp. Sau đó, chúng ta sẽ trình bày các giải thuật một cách chi tiết.
- Nếu một hệ thống không dùng giải thuật ngăn chặn hay tránh deadlock thì trường hợp deadlock có thể xảy ra. Trong môi trường này, hệ thống có thể cung cấp một giải thuật để xem xét trạng thái của hệ thống để xác định deadlock có thể xảy ra hay không và giải thuật phục hồi từ deadlock.
- Nếu hệ thống không đảm bảo rằng deadlock sẽ không bao giờ xảy ra và cũng không cung cấp một cơ chế phát hiện và phục hồi deadlock thì có thể dẫn đến trường hợp hệ thống ở trong trạng thái deadlock. Trong trường hợp này, deadlock không được phát hiện sẽ làm giảm năng lực hệ thống vì tài nguyên đang được giữ bởi những quá trình mà chúng không thể thực thi, đi vào trạng thái deadlock. Cuối cùng, hệ thống sẽ dừng các chức năg và cần được khởi động lại bằng thủ công.

HuynhVanNhut (I11C)

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

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

Về Đầu Trang Go down

THẢO LUẬN : Học cách ngăn chặn deadlock bằng cách phủ định 1 trong 4 điều kiện dẫn tới deadlock làm gì khi không dùng được ?

Bài gửi  tranphanhieu36_i11c on 7/11/2011, 15:45

Bài này mình viết theo suy nghĩ và kiến thức của mình qua những gì mình học hỏi và biết được trong cuộc sống nên các bạn cứ tham khảo và nhiệt tình thảo luận cho ý kiến góp ý nhé.
Vấn đề này thầy hỏi mà chắc là các bạn quên rồi, mình chờ mãi mà chẳng thấy ai thảo luận cả !

Đầu tiên mình xin nêu ra một số vấn đề và câu chuyện có thực nhé , mình biết những điều mình nói không liên quan trực tiếp tới ví dụ thầy hỏi nhưng cũng liên quan ít nhiều, đặc biệt là về suy nghĩ:
1-Người quản lý hỏi bác học Edison : "Chúng ta đã thử hơn 9000 vật liệu để tìm ra vật liệu làm dây tóc bóng đèn mà vẫn chưa tìm ra. Công sức chúng ta từ đó tới giờ vô ích hết sao ?"(tìm ra vật liệu thích hợp để bóng đèn sáng lâu và bền hơn, không bị cháy mà thử hơn 9000 lần chứ không ít nha mấy bạn)
-Edison thản nhiên đáp : "Không đâu, qua mỗi lần tôi đều học được 1 bài học là vật liệu đó không làm được giây tóc bóng đèn đó chứ !". Và đương nhiên nhờ mấy ngàn lần thử nghiệm không thành đó ông đã tích lũy được rất nhiều kinh nghiệm để chế tạo ra dây tóc bóng đèn như hiện nay đó. Smile
2.Nhà bác học Albert Einstein (người Việt nói nghe là Anh Xtanh") đã làm "rung chuyển" cả bầu trời vật lý và thế giới khi tìm ra được thuyết tương đối rộng và hẹp - . Trong khi đó cả ngàn nhà bác học chẳng nghĩ ra và có lẽ cũng sẽ khó mà nghĩ ra. Người ta hỏi ông vì sao lại có thể nghĩ được sâu xa về vũ trụ như thế ( trong khi ông lại ở dưới mặt đất ^^). Ông trả lời rằng :"Tôi không ngừng suy nghĩ về nó, có thể tới 9999 lần tôi sai, chỉ còn lại một lần tôi đúng."
3.Ví dụ này thực tế nhất nè : Nhà Hiếu ở trên núi (tây nguyên). Sẽ chẳng bao giờ bị lũ lụt đâu, với cũng chẳng mấy khi xuống sông nước. Thế nhưng Hiếu lại tập bơi từ nhỏ. Để làm gì nhỉ trong khi chẳng mấy khi H cần xuống nước làm gì ?
-Đầu tiên lúc tập bơi Hiếu sẽ khỏe người.(cũng như học sẽ khỏe não vậy, suy nghĩ tốt, nhanh nhạy).
-Thứ hai là lúc này tập bơi rồi thì khả năng bơi dưới nước đã có, có thể Hiếu chưa giúp được gì nhưng sau này khi gặp tình huống (bị rớt xuống ao, sông, cứu người..) sẽ giúp được Hiếu.( cũng như bây giờ bạn phải học nhiều thứ mà bạn nghĩ là sẽ chẳng dùng, mình cũng không chắc là bạn sẽ dùng được nó nhưng biết đâu một ngày nào đó những điều bạn học đó có thể giúp được bạn).

Bây giờ mình sẽ nói cụ thể về vấn đề chính : Vấn đề ngăn chặn DEADLOCK bằng cách phủ định 4 điều kiện dẫn tới DEADLOCK không dùng được nhưng tại sao vẫn học.
-Đầu tiên mình nghĩ học cái này bạn còn biết được nhiều vấn đề liên quan khác như : Tại sao lại không dùng được( vì thực tế tài nguyên phải có tính chia sẻ<dk1>, tiến trình cũng phải cần 1 lúc nhiều tài nguyên<dk2>....). Có hiểu mọi thứ liên quan tới bài học thì mới hiểu bài và học tốt được( VD: các ví dụ thực tế thầy cho, các tình huống ...)
-Cái thứ hai là không những học những điều đúng mà còn phải học từ những sai lầm nữa để mà "tránh". Như có 1 câu nói mình không nhớ tác giả nhưng nội dung là :"Chúng ta không những chỉ học những điều đúng điều hay mà còn phải học từ những cái sai cái dở mà tránh nữa. Học cả từ những sai lầm của người khác để mà tránh chứ chúng ta không đủ thời gian sống để trải qua các sai lầm mà học hỏi đâu. Và một số cơ hội chỉ có 1 lần duy nhất không có lần thứ 2 để làm lại khi ta đã mắc sai lầm và học được". => Vậy bạn biết là những cách tránh DEADLOCK này không dùng được thì bạn có dùng nữa không ? Hoặc tìm cách mới để giải quyết DEADLOCK thì bạn có xét qua những cách này nữa không khi bạn đã biết là nó không dùng được ?
-Thứ 3 là điều đúng có được thường nhờ đi qua và thử từ những điều chưa đúng. Để tìm được giải pháp tránh DEADLOCK người ta đã thử những cách mà mình mới học và kết quả là không dùng được nên người ta mới nghiên cứu tìm ra cách khác (thuật giải nhà băng là 1 ví dụ ) rồi nói ra kiến thức này cho chúng ta học bây giờ đó.


Được sửa bởi tranphanhieu36_i11c ngày 7/11/2011, 16:28; sửa lần 1.

tranphanhieu36_i11c

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

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

Về Đầu Trang Go down

Những điều kiện cần thiết gây ra deadlock

Bài gửi  HuynhVanNhut (I11C) on 7/11/2011, 16:04

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 gữ 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 {Po,P1,...,Pn} đang chờ mà trong đó Po đ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 Po.
Cả bốn điều kiện phải cùng phát sinh để deadlock xảy ra. Điều kiện chời đợi chương trình đế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.

HuynhVanNhut (I11C)

Tổng số bài gửi : 12
Join date : 07/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  HoiHoangHongVu I11C on 7/11/2011, 18:29

nguyenthingocloan (I11C) đã viết:
nguyenvulinh_i11c đã viết:- Trên RAG, lúc ð.u t.t c. nhu c.u v. tài nguyên c.a ti.n tr.nh ph.i ðý.c khai báo trý.c b.ng các Cung Nhu c.u (Claim edge) Pi • • •> Rj ch. báo r.ng Pi có th. s. yêu c.u Rj - Cung Nhu c.u Pi • • •> Rj ðý.c chuy.n thành Cung Yêu c.u (Request edge) Pi • • •> Rj khi Pi th.c s. b.t ð.u c.n ð.n Rj . - N.u yêu c.u Pi • • •> Rj ðý.c HÐH ðáp .ng, cung Pi • • •> Rj chuy.n thành Cung .n ð.nh (Assignment edge) Pi <• • • Rj n.i phiên b.n duy nh.t c.a Rj v.i Pi . - Khi HÐH xét yêu c.u Pi • • •>Rj. H. ch. c.p phát Rj cho Pi n.u Cung .n ð.nh Pi <• • • Rj không t.o ra v.ng tr.n ð.ng hý.ng trong RAG (xét c. các Cung Nhu c.u). - Thu.t gi.i có ð. ph.c t.p o(n²) v.i n là s. ti.n tr.nh trong h.. Ví d. trách deadlock dùng RAG: Ð.u tiên khai báo t.t c. các nhu c.u c.a P1 và P2:P1 và P2 có th. s. d.ng R1,R2.

Trời, đọc không được gì hết bạn ơi.
bạn này copy và paste chắc luôn , hjjhjh

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồ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  TrinhThiOanh (I11C) on 7/11/2011, 18:59

08H1010052 đã viết:
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.

Thanks bạn nhiều, bài giải rõ ràng dể hiểu!

Chuỗi an toàn của bạn là {P3, P4, P2, P1, P0}
Nhưng theo mình chuỗi an toàn là { P3, P4, P1, P2, P0}
Bạn nào có thể giúp mình giải thích vì sao chọn P2 trước mà không chọn P1. Sau khi xét tới P4 thì ta xét lại từ đầu mà. Vậy so sánh giữa work >= need[i] thì P1 cũng thỏa đk mà. Sau khi P1 được chọn thì ta mới tiếp tục xét tới P2.
Đặt ra câu hỏi là cả hai trường hợp đều chấp nhận được phải không. Hay bắt buộc phải là P2 trước P1

Mong các bạn giúp mình giải quyết thắc mắc.
Kam un!

TrinhThiOanh (I11C)

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

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  TrinhThiPhuongThaoI11C on 7/11/2011, 19:44

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

Thêm 1 ví dụ : 5 thầy giáo đều cần máy chiếu để dạy ngay trong khi ở phòng thiết bị hiện tại chỉ có 1 máy chiếu => dẫn đến tranh chấp.
Ví dụ cuả hai bạn rất hay! Mong hai bạn đóng góp nhiều hơn cho diễn đàn.

TrinhThiPhuongThaoI11C

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

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

Về Đầu Trang Go down

Thuật giải Nhà Băng xác định trạng thái an toàn

Bài gửi  08H1010052 on 7/11/2011, 20:03

#include <stdio.h>

#define N 10 /* Số tiến trình */
#define M 20 /* Số Loại tài nguyên */

int Available [M];
int Max [N][M];
int Allocation[N][M];
int Need [N][M];
int Request [N][M];

/* Available[j]=k – Số phiên bản của tài nguyên Rj */
/* Max[i, j] = k – Pi cần tối đa tới k phiên bản Rj */
/* Allocation [i, j] = k – Pi đang giữ k phiên bản Rj */
/* Need [i, j] = k – Pi còn cần thêm k phiên bản Rj */
/* Như vậy: Need [i, j] = Max[i, j] - Allocation [i, j] */
/* Request [i, j] = k – Pi yêu cầu k phiên bản Rj */

int Work [M];
/* Work=Available+Allocation[i1]+Allocation[i2]+ .... */
bool Finish [N];
int SafeSequence[N];/* Chứa Chuỗi An toàn (CAT) */
int i, j, k;
/* Trạng thái An toàn ? */
bool IsSafeState () {
Work = Available;
k = 0; /* Chỉ số trong CAT */
Finish [j] = false với j = 0, 1, ... , N-1;
while ( i : Finish[i] = false và Need[i]<=Work){
Work = Work + Allocation [i];
Finish [i] = true;
/* Thêm i vào CAT */
SafeSequence [ k ] = i; k++;
}

if ( Finish[i] == true với i )
/* Trạng thái An toàn */
return (true);
else
/* Trạng thái Không an toàn */
return (false);
}



/* Tiến trình i yêu cầu */
int ResourceRequest ( int i ) {
if (Request [i] > Need [i])
return (-2); /* Yêu cầu quá lớn */
if (Request [i] > Available){
Pi phải chờ vì chưa đủ TN;
return (-3);
}
Available = Available – Request [i];
Allocation [i] = Allocation [i] + Request [i];
Need [i] = Need [i] - Request [i];
if ( IsSafeState() ) {
/* Trạng thái An toàn */
Cấp tài nguyên cho Pi;
return (0);
}
else {/* Trạng thái Không An toàn */
Khôi phục các giá trị cũ của Available, Allocation [i]và Need [i];
Pi phải chờ vì yêu cầu không được đáp ứng;
return (-1);
}
}

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  Sponsored content


Sponsored content


Về Đầu Trang Go down

Trang 6 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