Thảo luận Bài 8

Trang 5 trong tổng số 11 trang Previous  1, 2, 3, 4, 5, 6 ... 9, 10, 11  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  NgoXuanQuoc_(102C) on 20/4/2012, 00:19

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


Thread 1 Muốn lấy tài nguyên A và B Chiếm tài nguyên A , chờ Thread 2 bắt đầu chạy cho tới khi Thread 2 đợi tài nguyên A giải phóng Đợi tài nguyên B giải phóng
Thread 2 Muốn lấy tài nguyên A và B Chiếm tài nguyên B Đợi tài nguyên A giải phóng

--> Deadlock

Điều kiện xảy ra Deadlock
Có 4 điều kiện cần thiết để deadlock có thể xảy ra.

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

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

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

4. Đ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.
avatar
NgoXuanQuoc_(102C)

Tổng số bài gửi : 42
Join date : 17/02/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  NgoXuanQuoc_(102C) on 20/4/2012, 00:33

Làm cách nào để Ngăn chặn Deadlock ???
- Để deadlock xảy ra, một trong bốn điều kiện mình đã trình bày ở trên cần phải xảy ra. Bằng cách đảm bảo ít nhất một trong bốn điều kiện này không thể xảy ra, chúng ta có thể ngăn chặn việc xảy ra của deadlock. Chúng ta tìm hiểu tỷ mỹ tiếp cận này bằng cách xem xét mỗi điều kiện cần riêng rẻ nhau.


1. Loại trừ hỗ tương
- Điều kiện loại trừ hỗ tương phải giữ cho tài nguyên không chia sẻ. Thí dụ, một máy in không thể được chia sẻ cùng lúc bởi nhiều quá trình. Ngược lại, các tài nguyên có thể chia sẻ không đòi hỏi truy xuất loại trừ hỗ tương và do đó không thể liên quan đến deadlock. Những tập tin chỉ đọc là một thí dụ tốt cho tài nguyên có thể chia sẻ.
- Nếu nhiều quá trình cố gắng mở một tập tin chỉ đọc tại cùng một thời điểm thì chúng có thể được gán truy xuất cùng lúc tập tin. Một quá trình không bao giờ yêu cầu chờ tài nguyên có thể chia sẻ.
- Tuy nhiên, thường chúng ta không thể ngăn chặn deadlock bằng cách từ chối điều kiện loại trừ hỗ tương: một số tài nguyên về thực chất không thể chia sẻ.

2. Giữ và chờ cấp thêm tài nguyên
- Để đảm bảo điều kiện giữ-và-chờ cấp thêm tài nguyên không bao giờ xảy ra trong hệ thống, chúng ta phải đảm bảo rằng bất cứ khi nào một quá trình yêu cầu tài nguyên, nó không giữ bất cứ tài nguyên nào khác.
- Một giao thức có thể được dùng là đòi hỏi mỗi quá trình yêu cầu và được cấp phát tất cả tài nguyên trước khi nó bắt đầu thực thi. Chúng ta có thể cài đặt sự cung cấp này bằng cách yêu cầu các lời gọi hệ thống yêu cầu tài nguyên cho một quá trình trước tất cả các lời gọi hệ thống khác.
- Một giao thức khác cho phép một quá trình yêu cầu tài nguyên chỉ khi quá trình này không có tài nguyên nào. Một quá trình có thể yêu cầu một số tài nguyên và dùng chúng.
- Tuy nhiên, trước khi nó có thể yêu cầu bất kỳ tài nguyên bổ sung nào, nó phải giải phóng tất cả tài nguyên mà nó hiện đang được cấp phát.

3. Không đòi lại tài nguyên từ quá trình đang giữ chúng
- Điều kiện cần thứ ba là không đòi lại những tài nguyên đã được cấp phát rồi. Để đảm bảo điều kiện này không xảy ra, chúng ta có thể dùng giao thức sau.
- Nếu một quá trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không được cấp phát tức thì tới nó (nghĩa là, quá trình phải chờ) thì tất cả tài nguyên hiện đang giữ được đòi lại.
- Nói cách khác, những tài nguyên này được giải phóng hoàn toàn. Những tài nguyên bị đòi lại được thêm tới danh sách các tài nguyên mà quá trình đang chờ. Quá trình sẽ được khởi động lại chỉ khi nó có thể nhận lại tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.

4. Tồn tại chu trình trong đồ thị cấp phát tài nguyên
- Điều kiện thứ tư và cũng là điều kiện cuối cùng cho deadlock là điều kiện tồn tại chu trình trong đồ thị cấp phát tài nguyên. Một cách để đảm bảo rằng điều kiện này không bao giờ xảy ra là áp đặt toàn bộ thứ tự của tất cả loại tài nguyên và đòi hỏi mỗi quá trình trong thứ tự tăng của số lượng.
avatar
NgoXuanQuoc_(102C)

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

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

Về Đầu Trang Go down

Bốn điều kiện dẫn đến Deadlock là những điều kiện gì?

Bài gửi  NguyenthechinhI12A on 20/4/2012, 00:34

- Mutual exclusion: với mỗi tài nguyên, chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài ngyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu kỳ khép kín các yêu cầu tài nguyên.
avatar
NguyenthechinhI12A

Tổng số bài gửi : 24
Join date : 16/02/2012
Age : 28
Đến từ : BẮC NINH - HCM

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

Về Đầu Trang Go down

Trình bày các phương thức xử trí Deadlock.

Bài gửi  NguyenthechinhI12A on 20/4/2012, 00:35

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

Tổng số bài gửi : 24
Join date : 16/02/2012
Age : 28
Đến từ : BẮC NINH - HCM

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

Về Đầu Trang Go down

Định nghĩa Deadlock và nêu các ví dụ minh họa về hiện tượng này

Bài gửi  DiepMaiNgocYen(I12A) on 20/4/2012, 10:02

Định nghĩa Deadlock và nêu các ví dụ minh họa về hiện tượng này
Deadlock : Là Một số tiến trình có thể tranh nhau bởi một số tài nguyên hạn chế.
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 tiến trình chờ có thể sẽ không bao giờ thay đổi lại trạng thái được vì các tài nguyên mà nó yêu cầu bị giữ bởi các tiến trình chờ khác.
+ Mỗi tiến trình sử dụng tài nguyên theo các bước sau:
• yêu cầu tài nguyên(request): Nếu yêu cầu không được giải quyết ngay( ví dụ khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
• Sử dụng tài nguyên(use)
• Trả lại(Release): Trả tài nguyên cho HĐH quản lý.
Ví dụ1: Hiện tượng tắc nghẽn trên cầu:
+Hai(hay nhiều hơn) ô tô đối đầu nhau trên một cây cầu hẹp chỉ đủ độ rộng cho một chiếc.
+ Mỗi đoạn của cây cầu 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 một hay một số ô tô lùi lại nhường đường rồi tiển ra sau.
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...

DiepMaiNgocYen(I12A)

Tổng số bài gửi : 27
Join date : 23/02/2012
Age : 28
Đến từ : Long Xuyên - An Giang

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

Về Đầu Trang Go down

Ngăn chặn deadlock

Bài gửi  thailongI12C on 20/4/2012, 10:32

Để deadlock xảy ra, một trong bốn điều kiện cần phải xảy ra. Bằng cách đảm bảo ít nhất một trong bốn điều kiện này không thể xảy ra, chúng ta có thể ngăn chặn việc xảy ra của deadlock. Chúng ta tìm hiểu tỷ mỹ tiếp cận này bằng cách xem xét mỗi điều kiện cần riêng rẻ nhau.

Loại trừ hỗ tương
Điều kiện loại trừ hỗ tương phải giữ cho tài nguyên không chia sẻ. Thí dụ, một máy in không thể được chia sẻ cùng lúc bởi nhiều quá trình. Ngược lại, các tài nguyên có thể chia sẻ không đòi hỏi truy xuất loại trừ hỗ tương và do đó không thể liên quan đến deadlock. Những tập tin chỉ đọc là một thí dụ tốt cho tài nguyên có thể chia sẻ. Nếu nhiều quá trình cố gắng mở một tập tin chỉ đọc tại cùng một thời điểm thì chúng có thể được gán truy xuất cùng lúc tập tin. Một quá trình không bao giờ yêu cầu chờ tài nguyên có thể chia sẻ. Tuy nhiên, thường chúng ta không thể ngăn chặn deadlock bằng cách từ chối điều kiện loại trừ hỗ tương: một số tài nguyên về thực chất không thể chia sẻ.

Giữ và chờ cấp thêm tài nguyên
Để đảm bảo điều kiện giữ-và-chờ cấp thêm tài nguyên không bao giờ xảy ra trong hệ thống, chúng ta phải đảm bảo rằng bất cứ khi nào một quá trình yêu cầu tài nguyên, nó không giữ bất cứ tài nguyên nào khác. Một giao thức có thể được dùng là đòi hỏi mỗi quá trình yêu cầu và được cấp phát tất cả tài nguyên trước khi nó bắt đầu thực thi. Chúng ta có thể cài đặt sự cung cấp này bằng cách yêu cầu các lời gọi hệ thống yêu cầu tài nguyên cho một quá trình trước tất cả các lời gọi hệ thống khác.

Không đòi lại tài nguyên từ quá trình đang giữ chúng

Điều kiện cần thứ ba là không đòi lại những tài nguyên đã được cấp phát rồi. Để đảm bảo điều kiện này không xảy ra, chúng ta có thể dùng giao thức sau. Nếu một quá trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không được cấp phát tức thì tới nó (nghĩa là, quá trình phải chờ) thì tất cả tài nguyên hiện đang giữ được đòi lại. Nói cách khác, những tài nguyên này được giải phóng hoàn toàn. Những tài nguyên bị đòi lại được thêm tới danh sách các tài nguyên mà quá trình đang chờ. Quá trình sẽ được khởi động lại chỉ khi nó có thể nhận lại tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.

Điều kiện thứ tư và cũng là điều kiện cuối cùng cho deadlock là điều kiện tồn tại chu trình trong đồ thị cấp phát tài nguyên. Một cách để đảm bảo rằng điều kiện này không bao giờ xảy ra là áp đặt toàn bộ thứ tự của tất cả loại tài nguyên và đòi hỏi mỗi quá trình trong thứ tự tăng của số lượng.

thailongI12C

Tổng số bài gửi : 35
Join date : 17/02/2012

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

Về Đầu Trang Go down

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

Bài gửi  plminhhoangI12A on 20/4/2012, 10:39

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.

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.

plminhhoangI12A

Tổng số bài gửi : 19
Join date : 22/02/2012

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

Về Đầu Trang Go down

Đồ thị cấp phát tài nguyên

Bài gửi  plminhhoangI12A on 20/4/2012, 11:06

Xét đồ thị có hướng bao gồm tập nút V và tập cung E:
  • V chia làm 2 loại:

P = { P1, P2, …, Pn } - tập hợp các tiến trình đang vận hành.
R = { R1, R2, …, Rm } - tập hợp các loại tài nguyên có trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều Phiên bản (Ví dụ: Loại Máy in có 3 phiên bản).
  • E bao gồm các:

Cung Yêu cầu (Request Edge) Pi Rj
Pi yêu cầu 1 phiên bản tài nguyên Rj .
Cung Ấn định (Assignment Edge) Rj Pi
Một phiên bản tài nguyên Rj đã được cấp phát cho Pi.



plminhhoangI12A

Tổng số bài gửi : 19
Join date : 22/02/2012

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

Về Đầu Trang Go down

DEAD LOCK - CÁCH THỰC HIỆN & PHÒNG TRÁNH

Bài gửi  ĐoànMinhQuangI12A on 20/4/2012, 11:10

Thưa các bạn, ngồi trên máy tính, có lẽ chúng ta ghét nhất khi đang dùng bỗng nhiên máy tính bị treo (Dead Lock) , lúc đấy chúng ta đành phải trông chờ vào 3 phím nóng “ ctrl + alt + del ”, cũng có thể tồi tệ hơn, chúng ta đành phải “restart” lại máy theo kiểu thủ công là “ bấm nút khởi động trên Case “, bực mình nhỉ Sad , vì vậy tớ xin trình bày cho mọi người hiểu rõ hơn về tình trạng này và phòng tránh nó

I.Dead lock (bế tắc) là một trạng thái chờ đợi vô tận của một tiến trình yêu cầu cấp phát tài nguyên nhưng không bao giờ được thoả mãn, nghĩa là một Process ( tiến trình ) sẽ không bao giờ thay đổi trạng thái chờ, lúc đó Process được gọi là Deadlock.
Dưới đây là những điều kiện để xảy ra DeadLock ( Gồm 4 điều kiện đồng thời ) :
1. Mutual Exclusion (Loại trừ): Lúc này có ít nhất một tài nguyên được giữ ở chế độ không chia sẻ được (nonshavable). Nếu như một tiến trình khác yêu cầu tài nguyên đó thì Process đó phải chờ đến khi tài nguyên được trả lại bởi Process đang sử dụng
2. Hold And Wait (Giữ và đợi) : Phải thuộc một Process đang giữ ít nhất một tài nguyên và đang đợi để yêu cầu thêm một tài nguyên mà Process này đang được giữ bởi một Process khác .
3. No Preemption (Không dành trước): Các tài nguyên không được dành trước, một tài nguyên chỉ có thể được trả lại bởi một Process đang dùng nó sau khi Process kết thúc công việc .
4. Circular Wait (Đợi vòng) : Phải thuộc một tập các Process P = {P1,P2,…..Pn) và một tập các tài nguyên R = {R1,R2…Rn), trong đó do P1 yêu cầu tài nguyên R1, nhưng R1 được cấp cho P2, P2 yêu cầu R2 nhưng R2 lại được cấp cho P3, P3 yêu cầu R3 nhưng R3 lại đang được dùng bởi P1. Do đó ta có một tập E là tập chứa chu kỳ mạch vòng : E ={P1→R1→P2→R2→P3→R3→P1}
Vì vậy, khi cả 4 điều kiện trên xảy ra đồng thời thì máy tính của bạn chẳng thể thoát khỏi “Dead Lock “ .

II.Cách chữa Dead Lock : (Ngăn 1 trong 4 điều kiện trên không xảy ra)
- Ngăn cản Motual Exclusion: Điều kiện loại trừ phải giữ các tài nguyên không chia sẻ được, VD: Một máy in không thể đồng thời dùng chung cho nhiều Process được
- Ngăn cản Hold And Wait: Bất cứ một Process nào yêu cầu tài nguyên thì nó sẽ không được giữ bất kỳ một tại nguyên nào khác .
- Ngăn cảnKhôngPreemtion: Hệ thống phải đảm bảo tài nguyên được sử dụng theo một thứ tự hoặc theo một nguồn .
- Ngăn cản Circutar Wait: Để đảm bảo điều kiện đợi vòng không bao giừo xảy ea thì số các thứ tự tài nguyên phải có một thứ tự truy cập . VD: Cho một tập R = { R1,R1…Rn} là tập các tài nguyên, ta gán cho mỗi nguyên một số nguyên duy nhất, so sánh hai tài nguyên với nhau để xác định thứ tự của chúng, mỗi Proces chỉ yêu cầu tài nguyên theo một thứ tự tăng dần, Proces có thể yêu cầu tài nguyên Rj khi và chỉ khi : E(Rj) > F(Ri).

III.Phòng tránh Dead lock :
- Tình trạng an toàn : Nghĩa là system có thể cấp phát tài nguyên cho mỗi Process mà vẫn tránh được Dead Lock, một System an toàn nếu nó thuộc một chuỗi an toàn .
- Các thuật toán cấp phát tài nguyên :
+Một ví dụ về thuật toán an toàn
Process Allocation Max Aoailable Need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A=10
B= 5
C=7
B1 3 3 2
Worde = ( 3 3 2 )
Finish[ 0] = finish[1] = finish[2] = finish [3] = finish[4] = facse
B2 finish[1] = tone
→ ( P0,P1,P2.P3,P4) hệ thống an toàn
+Một ví dụ về thuật toán yêu cầu tài nguyên :
- P1 yêu cầu tài nguyên ( 0 ,1 ,0) A,B,C
- Request1 = ( 0 ,1 ,0)
1. Request1<= need1 → true
2. Request1 <= Available →true
3. vailable = ( 3 ,2 ,2 )
Allocation1= (2 ,1, 0)
Need1 = (1 ,1 ,2)
Sau đó quay lại trạng thái an toàn xem system này có an toàn hay không

Admin
Deadlock là trạng thái kẹt của 1 nhóm tiến trình chờ lẫn nhau, chứ không phải của 1 tiến trình chờ mãi mãi tài nguyên đâu !

ĐoànMinhQuangI12A

Tổng số bài gửi : 31
Join date : 15/02/2012
Age : 27

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  TranTrungHienI12C on 20/4/2012, 11:24

Ví dụ về Deadlock thường gặp ở bên ngoài:
- Một nhân viên trực tổng đài với một chiếc điện thoại duy nhất. Nếu trong một thời điểm,có tới 6 cuộc gọi tới cùng một lúc,thì điều tắt nghẽn là điều xảy ra.
--> Giải pháp: Áp dụng một trong những điều kiện cần của Deadlock:Loại trừ tương hổ,chúng ta sẽ chia nhiều đường line điên thoại.
avatar
TranTrungHienI12C

Tổng số bài gửi : 19
Join date : 16/02/2012

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

Về Đầu Trang Go down

KHẮC PHỤC DEADLOCK

Bài gửi  ĐoànMinhQuangI12A on 20/4/2012, 11:31

Khi thuật toán phát hiện Deadlock xác định là đã có Deadloch đã xảy ra , cách khắc phục Very Happy :
A. Kết thúc tiến trình : Có 2 phương pháp
1. Bỏ dở tất cả các Process đã bị Deadlock . Phương pháp này sẽ ngắt chu kỳ Deadlock. Nhưng nhược điểm là chi phí đắt , các tiến trình này có thể phải chạy trong một thời gian dài.
2. Bỏ dở lần lượt từng Process cho tới khi chu kỳ Deadlock được loại bỏ. Khi chọn 1 Process để bỏ dở người ta phải xác định tới yếu tố kinh tế , người ta sẽ bỏ dở những Process nào mà có chi phí nhỏ nhất .Vậy để xác định Process nào được chọn phải theo yêu cầu sau :
- Quyền thuộc Process là gì ?
- Process sẽ thi hành mất bao lâu
- Có bao nhiêu kiểu tài nguyên mà Process dở đang sử dụng
- Có bao nhiêu kiểu tài nguyên mà Process cần để kết thúc công việc
- Có bao nhiêu Process cần phải kết thúc
B. Giành trước tài nguyên
1. Để loại trừ Deadlock bằng cách sử dụng giành trước tài nguyên chúng ta phải giành trước các tài nguyên từ những Process và cấp cho nó các Process khác cho tới khi chu kỳ Deadlock được loại bỏ.
2. Nếu giành trước tài nguyên thì phải tuân thủ 3 điều kiện sau:
- Chọn nạn nhân : Tài nguyên nào và Process nào cần được dành trước, phải xác định thứ tự của việc dành trước và chi phí nhỏ nhất.
- Quay vòng trở lại ( Roll Trở lại) : Nếu ta dành trước một R của một P thì ta sẽ chọn p nào ta phải quay vòng p tới trạng thái an toàn đó .
- Bỏ đợi (Starvation): Phải đảm bảo rằng các tài nguyên không luôn luôn được dành trước từ cùng một P.

ĐoànMinhQuangI12A

Tổng số bài gửi : 31
Join date : 15/02/2012
Age : 27

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

Về Đầu Trang Go down

PHÂN TÍCH VÀ TRÁNH DEADLOCKS TRONG SQL SERVER

Bài gửi  ĐoànMinhQuangI12A on 20/4/2012, 11:55

Microsoft SQL Server duy trì giao dịch toàn vẹn và cơ sở dữ liệu sự đồng bộ bằng cách sử dụng ổ khóa. SQL Server Phiên bản 6,5 tuỳ chọn sử dụng hàng- cấp khóa cho chèn các hoạt động và sử dụng trang cấp khóa cho khác hoạt động kinh doanh. Như với bất kỳ hệ thống cơ sở dữ liệu quan hệ, khóa có thể dẫn đến deadlocks giữa người sử dụng.
Ví dụ, giả sử User1 (hay Connection1) có một ổ khóa trên dữ liệu mục "A" và muốn một ổ khóa trên dữ liệu mục "B." User2 có một khóa trên dữ liệu mục "B" và bây giờ muốn một ổ khóa trên dữ liệu mục "A." Trong trường hợp này SQL Server, hoặc User1 hoặc User2 sẽ là một nạn nhân bế tắc, và người dùng khác sẽ được cấp các yêu cầu khóa.
Trong SQL Server, các nhà phát triển ứng dụng có thể quyết định kết nối sẽ là ứng cử viên cho bế tắc nạn nhân bằng cách sử dụng SET DEADLOCK_PRIORITY. Nếu nhà phát triển không chỉ định một ưu tiên cho deadlocks, SQL Server chọn các nạn nhân bế tắc bằng cách chọn quá trình đã hoàn tất các thông tư chuỗi ổ khóa.
Hệ thống ứng dụng cơ sở dữ liệu có thể hành xử một cách khác nhau khi được chuyển từ một trong những quan hệ cơ sở dữ liệu khác, dựa trên việc thực hiện các hệ thống cơ sở dữ liệu quan hệ. Một trong những khu vực để tìm các thay đổi hành vi là khóa. Bài viết này giải thích làm thế nào để phân tích các deadlocks trong SQL Máy chủ và các kỹ thuật bạn có thể sử dụng để tránh chúng.Bài viết này nhấn mạnh bằng cách sử dụng đầu ra của water cờ T1204 để phân tích deadlocks. Khi dấu vết cờ T1204 được thiết lập, SQL Server in thông tin về bế tắc khi nó xảy ra. Để sử dụng này cờ water, sử dụng các lệnh sau tại dấu nhắc lệnh để bắt đầu máy chủ SQL:
sqlservr -c -T1204
Kết quả water được gửi đến cửa sổ giao diện điều khiển, trừ khi bạn đặt cờ hiệu dấu vết T3605, mà sẽ gửi ra dấu vết cho lỗi đăng nhập.
Deadlocks có thể xảy ra khi hai kết nối Cập Nhật bảng theo thứ tự ngược lại. Ví dụ, một trong những kết nối chèn vào bảng "example1" đầu tiên và sau đó vào "example2," trong khi một kết nối chèn vào bảng "example2" đầu tiên và sau đó vào "example1" trong một giao dịch. Một kịch bản ví dụ là hữu ích để minh họa cách tránh deadlocks.
Sau đây là những điều khoản SQL được sử dụng để tạo ra bảng được sử dụng cho việc này Ví dụ:

create table example1 (column1 int, column2 char(20), column3 char(50))
go
create table example2 (column1 int, column2 char(20), column3 char(50))
go
declare @lvar int
select @lvar = 0
while @lvar < 500
begin
insert into example1 values (@lvar, 'AAA', 'CCC')
insert into example2 values (@lvar, 'AAA', 'CCC')
select @lvar = @lvar + 1
end
go
create unique clustered index ex1ind1 on example1 (column1, column2)
with fill factor = 90, PAD_INDEX
go
create unique clustered index ex2ind1 on example2 (column1, column2)
with fill factor = 90, PAD_INDEX
go

Ví dụ: Insertions sang các phần khác nhau của cùng một bảng
Bế tắc này cũng có thể xảy ra khi hai kết nối đưa vào khác nhau phần của cùng một bảng theo thứ tự ngược lại khi hàng chia sẻ các trang. Cho Ví dụ:

Connection1 > BEGIN TRANSACTION
Connection2 > BEGIN TRANSACTION
Connection1 > INSERT INTO example1 VALUES (100, 'AAAA', 'CCC')
Connection2 > INSERT INTO example1 VALUES (400, 'AAAB', 'CCC')
Connection1 > INSERT INTO example1 VALUES (400, 'AAAA', 'CCC')
Trong bảng ví dụ này, đó là một chỉ số cụm trên cột đầu tiên của bảng example1. Hàng với các giá trị tương tự cho các cột đầu tiên sẽ có xu hướng giảm trên cùng một trang. Trong ví dụ này, dòng thứ hai được đưa vào bởi Connection1 có lẽ sẽ rơi vào cùng một trang như hàng đầu được chèn vào bởi Connection2, bởi vì cả hai đều có một giá trị nhóm chỉ số 400. Điều này nguyên nhân gây Connection2 cho khối Connection1.

Connection2 > INSERT INTO example1 VALUES (100, 'AAAB', 'CCC')

Bây giờ Connection2 cũng có thể bị chặn bởi Connection1, dẫn tới một bế tắc. Sau đây là dấu vết bế tắc:

97/04/20 12:56:01.40 spid16 *** DEADLOCK DETECTED with spid 15 ***
spid 16 requesting EX_PAGE (waittype 0x8005), blocked by:
EX_PAGE: spid 15, dbid 6, page 0x2c5, table example1, indid 0
pcurcmd INSERT(0xc3), input buffer: INSERT INTO example1 VALUES (100,
'AAAB', 'CCC')
spid 15 waiting for EX_PAGE (waittype 0x8005), blocked by:
EX_PAGE: spid 16, dbid 6, page 0x8bd, table example1, indid 0
pcurcmd INSERT(0xc3), input buffer: INSERT INTO example1 VALUES (400,
'AAAA', 'CCC')
VICTIM: spid 16, pstat 0x0000 , cputime 130

Yêu cầu 16 spid cho EX_PAGE khóa cho trang 0x2c5 bị chặn bởi dịch vụ spid 15, mà đã giữ EX_PAGE khóa cho trang 0x2c5 sau khi nó đã làm người đầu tiên chèn. Và spid 15 cũng đã bị chặn bởi dịch vụ spid 16 ngày chờ đợi cho một EX_PAGE khóa cho page 0x8db dẫn đến deadlock.
Bế tắc này có thể tránh được bằng cách sử dụng lệnh sau để kích hoạt tính năng IRL Đối với bảng example1:

sp_tableoption 'example1', 'insert row lock', true
Nguồn microsoft support.

ĐoànMinhQuangI12A

Tổng số bài gửi : 31
Join date : 15/02/2012
Age : 27

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

Về Đầu Trang Go down

Định nghĩa Deadlock & Điều kiện cần để xảy ra deadlock

Bài gửi  TrinhThiPhuongThaoI12C on 20/4/2012, 12:56

Định nghĩa Deadlock
- Trong hệ thống đa chương, nhiều quá trình có thể
cạnh tranh một số giới hạn tài nguyên.
- Một quá trình yêu cầu tài nguyên, nếu tài nguyên
không sẵn dùng tại thời điểm đó, quá trình đi vào
trạng thái chờ.
-Quá trình chờ có thể không bao giờ chuyển trạng thái
trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những
quá trình khác
=>Trường hợp này gọi là deadlock(khóa chết).

Điều kiện cần để xảy ra deadlock :
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Loại trừ tương hổ (Mutual exclusion): ít nhất một
tài nguyển được giữ trong chế độ không chia sẻ
2. Giữ và chờ cấp thêm tài nguyên (Hold and wait):
một process đang giữ ít nhất một tài nguyên và
đợi thêm tài nguyên do quá trình khác đang giữ
3. Không có ưu tiên (No preemption): tài nguyên không thể bị lấy lại,mà chỉ có thể được trả lại từ process đang giử tài nguyên đó khi nó muốn.
4. Chu trình (Circular wait): tồn tại một chu trình của các yêu cầu tài nguyên và tài nguyên đã được cấp phát.

TrinhThiPhuongThaoI12C

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

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

Về Đầu Trang Go down

Các phương pháp giải quyết Deadlock

Bài gửi  BuiHuongTra(I12A) on 20/4/2012, 13:01

Dùng một giao thức (Protocol) để ngăn chặn hoặc tránh deadlock, đảm bảo rẳng hệ thống không bao giờ bị rơi vào tình trạng deadlock.
+ Deadlock Prevention
Tìm cách ngăn chặn sao cho 1 trong 4 điều kiện ko xẩy ra:
1. Ngăn cản lẫn nhau:(mutual exclusion)
- đảm bảo hệ thống ko có các file ko thể chia sẻ
Một process ko bao giờ chờ tài nguyên chia sẻ (shareble resource)
Vd: read-only file
Nhưng có 1 số tài nguyên ko chia sẻ được
Vd : chế độ toàn màn hình
2. Giữ và đợi:(Hold and wait)
- sử dụng cơ chế “All or none”
 Cách 1 : bắt buộc mỗi process phải yêu cầu tòan bộ tài nguyên cấn thiết 1 lần, nếu có đủ tài nguyên hế thống sẽ cấp phát, nếu ko đủ tài nguyên, process sẽ bị block.
 Cách 2: khi yêu cầu tài nguyên process không được sở hữu bất kỳ tài nguyên nào cả.nếu đang có thì phải trả lại trước khi yêu cầu.
 Khuyết điểm :
• Hiệu quả sử dụng tài nguyên rất thấp
Có khả năng xẩy ra bị đói starvation
3. No Preemption : Nếu process A có sở hữu tài nguyên và đang yêu cầu tài nguyên nhưng tài nguyên này chưa đáp ứng thì
Cách 1 : A phải trả cho hệ thống mọi tài nguyên đang sở hữu
Cách 2: Hệ thống sẽ kiểm tra tài nguyên mà A yêu cầu
=>Thường áp dụng cho tài nguyên có thể dễ dàng lưu và khôi phục trạng thái như CPU register, bộ nhớ …
4. Circular Wait : Các tài nguyên trong hệ thống được đánh dấu số thứ tự tuyến tính.
+Deadlock avoidance
-Deadlock prevention sử dụng tài nguyên không hiệu quả.
- Deadlock avoidance chỉ dựa trên điều kiện thứ 4 để tránh deadlock mà vẫn đảm bảo hiệu suất sử dụng tài nguyên tối đa đến mức có thể.
-Giải thuật deadlock-avoidance sẽ kiểm tra trạng thái cấp tài nguyên để đảm vảo hệ thống không bao giờ rơi vào deadlock

-Hệ thống có thể rơi vào trạng thái deadlock, sau đó phát hiện deadlock và phục hồi hệ thống
Bỏ qua mọi vấn đề, xem như không bao giờ có deadlock xảy ra trong hệ thống
=>Khá nhiều hệ điều hành sử dụng phương pháp này
-Nếu Deadlock không phát hiện và giải quyết =>giảm hiệu suất của hệ thống. Cuối cùng , hệ thống có thể ngưng hoạt động và phải khởi động lại.



BuiHuongTra(I12A)

Tổng số bài gửi : 12
Join date : 16/02/2012
Age : 29
Đến từ : Phú Yên

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

Về Đầu Trang Go down

Định nghĩa Deadlock, vấn đề quan trọng của Deadlock

Bài gửi  tranthithanhuyen85 (I11C) on 21/4/2012, 13:36

- Tình huống bị kẹt của 1 nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ 1 sự kiện có thể được gây ra bởi 1 tiến trình khác.
Ví dụ: 1 xe qua cầu hẹp, kẹt xe tại ngã tư.
- Deadlock khi các tiến trình yêu cầu tài nguyên.
- Tài nguyên cùng loại : giả sử có 3 ổ băng và 3 tiến trình đang chạy. Mỗi tiến trình đang giữ 1 ổ băng.
o Nếu mỗi tiến trình xin thêm 1 ổ băng nữa thì deadlock xảy ra.
o Mỗi tiến trình chờ 1 sự kiện : “ổ băng được trả lại hệ thống” bởi 1 tiến trình khác.
- Tài nguyên khác nhau : giả sử có 1 máy in, 1 ổ băng từ, tiến trình P1 đang giữ ổ băng, tiến trình P2 đang giữ máy in.
Nếu P1 xin thêm máy in và P2 xin thêm ổ băng để hoàn tất công việc thì deadlock xảy ra.

tranthithanhuyen85 (I11C)

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

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

Về Đầu Trang Go down

Phân tích 4 điều kiện cần dẫn đến Deadlock

Bài gửi  tranthithanhuyen85 (I11C) on 21/4/2012, 13:37

- Loại trừ lẫn nhau (Mutual exclusion): mỗi thời điểm chỉ có 1 tiến trình được sử dụng nó.
- Giữ và chờ (Hold and wait) : có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No preemtion) : tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi sử dụng xong.
- Chờ xoay vòng (circular wait): giả sử tiến trình đang chờ tài nguyên là {P1,P2,…,Pn} Khi đó P1 chờ tài nguyên giữ bởi P2, tiến trình P2 chờ tài nguyên giữ bởi P3, … Pn cho P1.
- 4 điều kiện này độc lập với nhau ( ví dụ : điều kiện 4 kéo theo điều kiện 2)
- Phủ định cả 4 điều kiện này có tác dụng ngăn chặn cho chúng không xảy ra.

tranthithanhuyen85 (I11C)

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

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

Về Đầu Trang Go down

Các giải pháp ngăn chặn Deadlocks bằng cách phủ định một trong 4 điều kiện dẫn đến Deadlocks?

Bài gửi  levanhop.it on 21/4/2012, 14:26

- Loại bỏ điều kiện loại trừ tương hỗ:

Vì tại một thời điểm chỉ có 1 tiến trình được sử dụng tài nguyên, mà đây là tài nguyên không chia sẽ nên ta sẽ tăng số lượng tài nguyên lên. Giải pháp này thực tế là không khả thi.
Ví dụ: trong trường hợp ổ cứng bị đầy và chỉ còn đủ để cung cấp trong một tiến trình thì phương pháp này không thực hiện được
Cấp phát tài nguyên dạng ống.(spool)

- Loại bỏ điều kiện giữ và chờ (Hold and Wait):

Do một tiến trình đang giữ tài nguyên và yêu câu một tài nguyên mới nên nguyên tắc để loại bỏ là: tiến trình không được giữ tài nguyên khi yêu cầu tài nguyên mới. Khi cần, nó khai báo tài nguyên và đươc cấp phát một lần. Nếu nó yêu cầu thêm tài nguyên và không được thì phải trả cái tài nguyên mà nó đang giữ.
Giải pháp này cũng không khả thi bởi trong thực tế một tiến trình cần nhiều hơn 1 tài nguyên mới có thể hoạt động được.
Tiến trình phải yêu cầu và được cấp tất cả tài nguyên mà nó cần ngay đầu công việc. Giải pháp này cũng không khả thi vì nó tốn nhiều tài nguyên

- Loại bỏ Không tiếm quyền( No Preemption):

Hệ điều hành sẽ lấy lại tài nguyên từ tiến trình mà nó đang chiếm giữ khi sử dụng xong. Nhưng với một số tài nguyên có thể không lấy lại được.

- Loại bỏ chờ xoay vòng( Circular Wait):

Có thể cấp số thứ tự cho mỗi tài nguyên, và mỗi tiến trình chỉ được yêu cầu tài nguyên theo thứ tự tăng dần

levanhop.it

Tổng số bài gửi : 40
Join date : 16/02/2012
Age : 27
Đến từ : Phan Thiết - Bình Thuận

Xem lý lịch thành viên http://www.facebook.com/Kenny Hop

Về Đầu Trang Go down

Deadlock

Bài gửi  LeLamThang (113A) on 21/4/2012, 22:32

Khi giải thuật phát hiện xác định rằng deadlock tồn tại, nhiều thay đổi tồn tại. Một khả năng là thông báo người điều hành rằng deadlock xảy ra và để người điều hành giải quyết deadlock bằng thủ công. Một khả năng khác là để hệ thống tự động phục hồi. Có hai tuỳ chọn cho việc phá vỡ deadlock. Một giải pháp đơn giản là huỷ bỏ một hay nhiều quá trình để phá vỡ việc tồn tại chu trình trong đồ thị cấp phát tài nguyên. Tuỳ chọn thứ hai là lấy lại một số tài nguyên từ một hay nhiều quá trình bị deadlock.
Kết thúc quá trình
Để xóa deadlock bằng cách hủy bỏ quá trình, chúng ta dùng một trong hai phương pháp. Trong cả hai phương pháp, hệ thống lấy lại tài nguyên được cấp phát đối với quá trình bị kết thúc.
  • Huỷ bỏ tất cả quá trình bị deadlock: phương pháp này rõ ràng sẽ phá vỡ chu trình deadlock, nhưng chi phí cao; các quá trình này có thể đã tính toán trong thời gian dài, và các kết quả của các tính toán từng phần này phải bị bỏ đi và có thể phải tính lại sau đó.
  • Hủy bỏ một quá trình tại thời điểm cho đến khi chu trình deadlock bị xóa:phương pháp này chịu chi phí có thể xem xét vì sau khi mỗi quá trình bị hủy bỏ, một giải thuật phát hiện deadlock phải được nạp lên để xác định có quá trình nào vẫn đang bị deadlock.

Hủy bỏ quá trình có thể không dễ. Nếu một quá trình đang ở giữa giai đoạn cập nhật một tập tin, kết thúc nó sẽ để tập tin đó trong trạng thái không phù hợp. Tương tự, nếu quá trình đang ở giữa giai đoạn in dữ liệu ra máy in, hệ thống phải khởi động lại trạng thái đúng trước khi in công việc tiếp theo.Nếu phương pháp kết thúc một phần được dùng thì với một tập hợp các quá trình deadlock được cho, chúng ta phải xác định quá trình nào (hay các quá trình nào) nên được kết thúc trong sự cố gắng để phá vỡ deadlock. Việc xác định này là một quyết định chính sách tương tự như các vấn đề lập thời biểu CPU. Câu hỏi về tính kinh tế là chúng ta nên hủy bỏ quá trình nào thì sự kết thúc của quá trình đó sẽ chịu chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác. Nhiều yếu tố có thể xác định quá trình nào được chọn bao gồm:
  1. Độ ưu tiên của quá trình là gì.
  2. Quá trình đã được tính toán bao lâu và bao lâu nữa quá trình sẽ tính toán trước khi hoàn thành tác vụ được chỉ định của nó.
  3. Bao nhiêu và loại tài nguyên gì quá trình đang sử dụng.
  4. Bao nhiêu tài nguyên nữa quá trình cần để hoàn thành.
  5. Bao nhiêu quá trình sẽ cần được kết thúc.
  6. Quá trình là giao tiếp hay dạng bó.

Lấy lại tài nguyên
Để xóa deadlock sử dụng việc trả lại tài nguyên, sau khi chúng ta đòi một số tài nguyên từ các quá trình và cho các tài nguyên này tới các quá trình khác cho đến khi chu trình deadlock bị phá vỡ.
Nếu việc đòi lại được yêu cầu để giải quyết deadlock thì ba vấn đề cần được xác định:

  1. Chọn nạn nhân: những tài nguyên nào và những quá trình nào bị đòi lại? Trong khi kết thúc quá trình, chúng ta phải xác định thứ tự đòi lại để tối thiểu chi phí. Các yếu tố chi phí có thể gồm các tham số như số lượng tài nguyên một quá trình deadlock đang giữ, và lượng thời gian một quá trình deadlock dùng trong sự thực thi của nó.
  2. Trở lại trạng thái trước deadlock: Nếu chúng ta đòi lại tài nguyên từ một quá trình, điều gì nên được thực hiện với quá trình đó? Rõ ràng, nó không thể tiếp tục việc thực thi bình thường; nó đang bị mất một số tài nguyên được yêu cầu. Chúng ta phải phục hồi quá trình tới trạng thái an toàn và khởi động lại từ trạng thái gần nhất trước đó.
  3. Thông thường, rất khó để xác định trạng thái gì là an toàn vì thế giải pháp đơn giản nhất là phục hồi toàn bộ: hủy quá trình và sau đó khởi động lại nó. Tuy nhiên, hữu hiệu hơn để phục hồi quá trình chỉ đủ xa cần thiết để phá vỡ deadlock. Ngoài ra, phương pháp này yêu cầu hệ thống giữ nhiều thông tin hơn về trạng thái của tất cả các quá trình đang chạy.
  4. Đói tài nguyên: chúng ta đảm bảo như thế nào việc đói tài nguyên không xảy ra? Nghĩa là, chúng ta có thể đảm bảo rằng tài nguyên sẽ không luôn bị đòi lại từ cùng một quá trình.
  5. Trong một hệ thống việc chọn nạn nhân ở đâu dựa trên cơ sở các yếu tố chi phí, nó có thể xảy ra cùng quá trình luôn được chọn như là nạn nhân. Do đó, quá trình này không bao giờ hoàn thành tác vụ được chỉ định của nó, một trường hợp đói tài nguyên cần được giải quyết trong bất kỳ hệ thống thực tế. Rõ ràng, chúng ta phải đảm bảo một quá trình có thể được chọn như một nạn nhân chỉ một số lần xác định (nhỏ). Giải pháp chung nhất là bao gồm số lượng phục hồi trong yếu tố chi phí.

LeLamThang (113A)

Tổng số bài gửi : 35
Join date : 15/02/2012

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  LeLamThang (113A) on 21/4/2012, 22:51

leminhtam13(I12A) đã viết:* Định nghĩa: Deadlock là tình huống hoặc trạng thái của một nhóm tiến trình đang trong tình trạng bị kẹt, do có quá nhiều tiến trình cùng nhau chờ đợi một, tranh chấp 1 sự kiện, dữ liệu nào đó xảy ra.
* Các ví dụ minh họa:
VD1: Trên 1 cây cầu hẹp chỉ có thể cho 1 xe đi qua, mà nếu trong cùng 1 lúc có 2 xe cùng chạy lên cầu xe nào cũng ko chịu nhường xe nào cùng nhau tranh chấp cầu để mình được đi => cuối cùng do cầu quá hẹp nên hậu quả là ko xe nào qua cầu được bị kẹt lại giữa cầu, thậm chí là bị ngã xuống nước.
VD2: Trong thực tế vừa qua "khi nhà sản xuất smartphone hàng đầu thế giới Apple công bố sẽ bán điện thoại IP 4s trong vào khoảng tháng 10/2011" thì một số lượng lớn tính đồ IP đã tìm đến các trung tâm Apple Store để chờ và mua cho bằng được sản phẩm mơ ước này, làm cho các cửa hàng bán IP chật kín cả người tại thời điểm sắp ra mắt IP 4s do có một số người muốn mua trước nên đã chen lấn gây mất ổn định làm cho cửa hàng phải ngừng bán sản phẩm ra=> ko ai mua được.
VD3: Có 2 người cùng té xuống sông và cả hai đều ko biết bơi và đuối sức, nếu 1 trong 2 buôn tay người kia ra thì có thể 1 người sẽ sống sót, nhưng ko ai chịu buôn ra hết (theo hoán tính của con người) => cả 2 đều chết đuối.
thêm hình minh họa Laughing



Sao Paulo (Brazil)

LeLamThang (113A)

Tổng số bài gửi : 35
Join date : 15/02/2012

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

Về Đầu Trang Go down

Phân tích 4 điều kiện cần dẫn đến Deadlock ?

Bài gửi  levanhop.it on 22/4/2012, 08:41

- Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyen có tính không chia sẽ (non-sharable), nghĩa là : Một thời điểm chỉ có 1 tiến trình được sử dụng nó.
vd : Xe qua cầu hẹp. Mỗi thời điểm chỉ có xe ô tô được đi qua cầu thôi. vì cầu hẹp nên không thể dùng chung được.
- Giữ và chờ ( Hold and Wait ) : Có một tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm tiến trình khác.
vd : Xe qua cầu hẹp . 2 xe đang đứng giữa cầu. Mỗi xe đang giữ nửa mặt cầu và muốn "xin" thêm nửa mặt cầu còn lại.
- Không có tiếm quyền ( No Preemption ) : Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi sử dung xong.
vd : Xe qua cầu hẹp .Phải để 2 xe A hoặc B tự nguyện trả lại mặt đường (tức là một trong 2 xe phải lùi lại). Còn có tiếm quyền (Preemption) nghĩa là cầu được lắp chiếc "cẩu" để khi cần thiết "nhấc" 1 ô tô lên khoảng 2 m (tiếm quyền sử dụng mặt cầu của nó) để chiếc kia qua được !
- Chờ xoay vòng ( Circular Wait ): Giả sử có n tiến trình đang chờ tài nguyên là { P1,P2,..,Pn }, khi đó P1 chờ TN bời giữ P2, tiến trình P2 chờ TN giữ bởi P3,...,Pn chờ P1.

Phủ định 1 trong 4 điều kiện này (tức là không cho nó xảy ra ) có tác dụng Ngăn chặn Deadlock !

Admin
Hiểu tốt (thày sửa đôi chỗ), nhưng chưa thấy có ví dụ minh hoạ Circular Waiting !


levanhop.it

Tổng số bài gửi : 40
Join date : 16/02/2012
Age : 27
Đến từ : Phan Thiết - Bình Thuận

Xem lý lịch thành viên http://www.facebook.com/Kenny Hop

Về Đầu Trang Go down

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

Bài gửi  Nguyen Doan Linh051(I11c) on 22/4/2012, 09:29

CÂU 1: ĐỊNH NGHĨA DEADLOCK VÀ NÊU CÁC VÍ DỤ MINH HỌA HIỆN TƯỢNG

Đị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 có thể chỉ được gây ra bởi một tiến trình khác
Ví dụ: 5 thầy giáo đều cần máy chiếu để dạy trong khi ở phòng thiết bị hiện tại chỉ có một máy chiếu=> dẫn đến tranh chấp.
2 chiếc xe đi ngược chiều cùng qua 1 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 vì không có xe nào chịu nhường xe nào

Admin
5 thày "tranh chấp" 1 máy chiếu không có nghĩa là "Kẹt khoá" (Deadlock) !

Nguyen Doan Linh051(I11c)

Tổng số bài gửi : 21
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  Nguyen Doan Linh051(I11c) on 22/4/2012, 09:38

CÂU 2: TRÌNH BÀY 4 ĐIỀU KIỆN CẦN DẪN ĐẾN DEADLOCK
- Loại trừ lẫn nhau ít nhất có một tài nguyên có tính không chia sẻ nghĩa là Mỗi thừi điểm chỉ có 1 tiến trình được sử dụng nó
- Giữ và chờ có 1 tiến trình đang giữ một tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác
- không có tiếm quyền : 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 tự nguyện trả lại hệ thống sau khi sự dụng xong
- Chờ xoay vòng : Giả sử có tiến trình đang chờ { 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

Nguyen Doan Linh051(I11c)

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

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

Về Đầu Trang Go down

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

Bài gửi  vothingocthuy87(I11C) on 22/4/2012, 17:23

* Ưu điểm Deadlock Prevention: 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 Deadlock Prevention:
_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


vothingocthuy87(I11C)

Tổng số bài gửi : 14
Join date : 01/09/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  vothingocthuy87(I11C) on 22/4/2012, 17:46

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.

Admin
Những thông tin này lấy ở đâu nhỉ ? Do em nghĩ ra ?



vothingocthuy87(I11C)

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

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

Về Đầu Trang Go down

4 điều kiện dẫn đến deadlock và giải pháp ngăn chặn

Bài gửi  phuongnguyen on 23/4/2012, 07:22

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

Giải pháp xử lý:
1. Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
2. Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
3. Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).

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

phuongnguyen

Tổng số bài gửi : 27
Join date : 17/02/2012

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 5 trong tổng số 11 trang Previous  1, 2, 3, 4, 5, 6 ... 9, 10, 11  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