Thảo luận Bài 8

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

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

Thảo luận Bài 8

Bài gửi  Admin on 1/8/2011, 15:58

Thảo luận những vấn đề liên quan đến Bài 8

Admin
Admin

Tổng số bài gửi : 293
Join date : 18/02/2009

Xem lý lịch thành viên http://hedieuhanh.forumvi.net

Về Đầu Trang Go down

Định nghĩa deadlock

Bài gửi  vothihonggam on 27/10/2011, 20:30

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.

vothihonggam

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

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

Về Đầu Trang Go down

4 điều kiện cần dẫn đến deadlock

Bài gửi  dinhtrongnghia(I11C) on 27/10/2011, 20:46

- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độ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 dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {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.

dinhtrongnghia(I11C)

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

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

Về Đầu Trang Go down

Giải pháp ngăn Deadlock

Bài gửi  tannamthanh(I11C) on 27/10/2011, 21:59

Phần lớn, chúng ta có thể giải quyết vấn đề deadlock theo một trong ba cách:
• Chúng ta có thể 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
• Chúng ta có thể cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và phục hồi.
• Chúng ta có thể 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.
• Chúng ta sẽ 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 trong các phần sau đây.
Để đảm bảo deadlock không bao giờ xảy ra, hệ thống có thể dùng kế hoạch ngăn chặn hay tránh deadlock. Ngăn chặn deadlock là một tập hợp các phương pháp để đảm bảo rằng ít nhất một điều kiện cần không thể xảy ra. Các phương pháp này ngăn chặn deadlocks bằng cách ràng buộc yêu cầu về tài nguyên được thực hiện như thế nào. Chúng ta thảo luận phương pháp này trong phần sau.
Ngược lại, tránh deadlock yêu cầu hệ điều hành cung cấp những thông tin bổ sung tập trung vào loại tài nguyên nào một quá trình sẽ yêu cầu và sử dụng trong thời gian sống của nó. Với những kiến thức bổ sung này, chúng ta có thể quyết định đối với mỗi yêu cầu quá trình nên chờ hay không. Để quyết định yêu cầu hiện tại có thể được thoả mãn hay phải bị trì hoãn, hệ thống phải xem xét tài nguyên hiện có, tài nguyên hiện cấp phát cho mỗi quá trình, và các yêu cầu và giải phóng tương lai của mỗi quá trình.
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ó 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ăng và cần được khởi động lại bằng thủ công.
Mặc dù phương pháp này dường như không là tiếp cận khả thi đối với vấn đề deadlock nhưng nó được dùng trong một số hệ điều hành. Trong nhiều hệ thống, deadlock xảy ra không thường xuyên; do đó phương pháp này là rẻ hơn chi phí cho phương pháp ngăn chặn deadlock, tránh deadlock, hay phát hiện và phục hồi deadlock mà chúng phải được sử dụng liên tục. Trong một số trường hợp, hệ thống ở trong trạng thái cô đặc nhưng không ở trạng thái deadlock. Như thí dụ, xem xét một quá trình thời thực chạy tại độ ưu tiên cao nhất (hay bất cứ quá trình đang chạy trên bộ định thời biểu không trưng dụng) và không bao giờ trả về điều khiển đối với hệ điều hành. Do đó, hệ thống phải có phương pháp phục hồi bằng thủ công cho các điều kiện không deadlock và có thể đơn giản sử dụng các kỹ thuật đó cho việc phục hồi deadlock.

tannamthanh(I11C)

Tổng số bài gửi : 23
Join date : 03/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  NgoLeYen48(I11C) on 27/10/2011, 22:01

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.
avatar
NgoLeYen48(I11C)

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

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

Về Đầu Trang Go down

Giải bài tập về nhà

Bài gửi  tannamthanh(I11C) on 27/10/2011, 22:04

"Thực thi đèn hiệu CritSec theo cách như với SemEmpty & SemFull"
Bạn nào lảm được thì post lên cho mọi người tham khảo nha

tannamthanh(I11C)

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

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

Về Đầu Trang Go down

Ví dụ về Deadlock

Bài gửi  ToThiThuyTrang (I11C) on 27/10/2011, 22:18

vothihonggam đã viết:Tình huống kẹt của của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.

ví dụ: 2 xe đi cùng chiều qua một cây cầu hẹp, mà cầu chỉ có một làn xe, nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường.

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

Tổng số bài gửi : 33
Join date : 25/08/2011
Age : 28
Đến từ : Bà Rịa-Vũng Tàu

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

Về Đầu Trang Go down

Khái niệm trạng thái an toàn và giải pháp tránh deadlock

Bài gửi  XuanThai_I11C on 27/10/2011, 22:30

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

XuanThai_I11C

Tổng số bài gửi : 20
Join date : 10/09/2011
Age : 31

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

Về Đầu Trang Go down

khái niệm đồ thị cấp phát tài nguyên. Biết cách vẽ và cách giải thích một đồ thị cho trước

Bài gửi  nguyenvulinh_i11c on 27/10/2011, 22:35

Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E. + Tập nút V gồm 2 loại: P ={P1, P2, ..., Pn} tập hợp các tiến trình đang vận hành trong hệ thống. R ={R1, R2, ..., Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều phiên bản. VD: máy in có 3 phiên bản, ... +Tập cung E bao gồm: Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj. Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp phát cho Pi. Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình. o Không có chu trình: không tồn tại Deadlock o Có chu trình: có hoặc không có Deadlock .Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản. .Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.

nguyenvulinh_i11c

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

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

Về Đầu Trang Go down

Khái niệm trạng thái an toàn và giải pháp tranh deadlock

Bài gửi  nguyenvulinh_i11c on 27/10/2011, 22:39

 Thế 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.

nguyenvulinh_i11c

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

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

Về Đầu Trang Go down

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:

Bài gửi  nguyenvulinh_i11c on 27/10/2011, 22:40

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

nguyenvulinh_i11c

Tổng số bài gửi : 24
Join date : 28/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 27/10/2011, 22:44

ToThiThuyTrang (I11C) đã viết:
vothihonggam đã viết:Tình huống kẹt của của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.

ví dụ: 2 xe đi cùng chiều qua một cây cầu hẹp, mà cầu chỉ có một làn xe, nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường.

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

Ví dụ 3: có 07 thầy đề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.
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  NgoDucTuan (I11C) on 27/10/2011, 22:49

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.
nguyenvulinh_i11c bạn có thể post lại bài này font trên bài viết của bạn lỗi rồi, nên mọi người chắc không đọc được. Cảm ơn bạn nhiều
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  BuiVanHoc(I11C) on 27/10/2011, 23:05

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.

Bạn copy ở đâu mà font chữ bể tè le, chẳng đọc được gì Smile
avatar
BuiVanHoc(I11C)

Tổng số bài gửi : 32
Join date : 26/08/2011
Age : 34
Đến từ : Ho Chi Minh City

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

Về Đầu Trang Go down

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

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

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.

Hiện tượng deadlock mình thường gặp nhất là hiện tượng khi các bạn chạy nhiều ứng dụng lớn chiếm nhiều ram và cpu, nhưng máy lại có cấu hình thấp dẫn đến PC bị treo(deadlock) và phải restart lại máy để giải phóng các tiến trình Smile
avatar
BuiVanHoc(I11C)

Tổng số bài gửi : 32
Join date : 26/08/2011
Age : 34
Đến từ : Ho Chi Minh City

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

Về Đầu Trang Go down

Ưu nhược điểm của Deadlock Prevention

Bài gửi  DangNgocMinh(I11C) on 27/10/2011, 23:17

Deadlock Prevention

  • Ưu điểm: ngăn chặn bế tắc (deadlock
    prevention) là phương pháp tránh được bế
    tắc bằng cách làm cho điều kiện cần không
    được thỏa mãn


  • Nhược điểm:
    _Giảm khả năng tận dụng tài nguyên và giảm
    thông lượng của hệ thống
    _Không mềm dẻo




DangNgocMinh(I11C)

Tổng số bài gửi : 26
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  caotanthanh(i11c) on 27/10/2011, 23:34



avatar
caotanthanh(i11c)

Tổng số bài gửi : 16
Join date : 03/09/2011
Age : 29
Đến từ : Buôn Hồ-KrongBuk-ĐakLak

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  caotanthanh(i11c) on 27/10/2011, 23:40

















avatar
caotanthanh(i11c)

Tổng số bài gửi : 16
Join date : 03/09/2011
Age : 29
Đến từ : Buôn Hồ-KrongBuk-ĐakLak

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

Về Đầu Trang Go down

Re:Định nghĩa Deadlock? Ví Dụ

Bài gửi  LaVanKhuong (I11C) on 28/10/2011, 07:00

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

LaVanKhuong (I11C)

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

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

Về Đầu Trang Go down

Giải pháp ngăn chặn Deadlock !!!

Bài gửi  DaoQuangSieu (I11C) on 28/10/2011, 08:53

dinhtrongnghia(I11C) đã viết:- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độ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 dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {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.
Giải pháp để ngăn chặn DeadLock là 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: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung.

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

Deadlock và các vd minh họa hiện tượng này.

Bài gửi  Tranvancanh(I11C) on 28/10/2011, 09:12

- Đị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).

Tranvancanh(I11C)

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

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

Về Đầu Trang Go down

Phân tích khái niệm tài nguyên hệ thống.

Bài gửi  TranQuyThanh (I11C) on 28/10/2011, 09:27

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

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

phương thức xử trí Deadlock

Bài gửi  TranQuyThanh (I11C) on 28/10/2011, 09:32

- Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.

- Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).

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

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

Ví dụ về điều kiện dẫn đến deadlock

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

dinhtrongnghia(I11C) đã viết:- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độ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 dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {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.
Mình xin bổ sung thêm ví dụ về điều kiện dẫn đến deadlock.
- Loại trừ lẫn nhau:
VD: băng từ không thể dùng chung được
-Giữ và chờ:
VD: 2 xe (tiến trình) trên 1 cầu (tài nguyên). 1 xe đã giữ nữa cầu lại xin thêm nữa cầu kia.
- Chờ xoay vòng:
VD: Có 5 người A, B, C, D, E (tiến trình) ngồi trên bàn ăn và mỗi người cần phải có 2 cái nĩa để ăn nhưng trên bàn chỉ có 5 cái nĩa (tài nguyên) và mỗi người đã giữ 1 cái nĩa. Để ăn được thì người A cần cái nĩa của người B, người B cần cái nĩa của người C, người C cần cái nĩa của người D, người D cần cái nĩa của người E, người E cần cái nĩa của người A.

Mình chưa hiểu lắm về điều kiện Không có tiếm quyền dẫn đến deadlock nên chưa đưa ra được ví dụ. Bạn nào hiểu thì đưa ra ví dụ giúp mình nhé!


Được sửa bởi NguyThiGai (I11C) ngày 28/10/2011, 09:34; sửa lần 1.

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

4 cách ngăn chặn Deadlock

Bài gửi  TranQuyThanh (I11C) on 28/10/2011, 09:33

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

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


Sponsored content


Về Đầu Trang Go down

Trang 1 trong tổng số 10 trang 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