Deadlock và 1 số ví dụ

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

Deadlock và 1 số ví dụ

Bài gửi  v_hoangminh[I22B] on 8/4/2013, 09:49

* Khái niệm deadlock:
- Tất cả hiện tượng tắc nghẽn đều bắt nguồn từ sự xung đột về tài nguyên của hai hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống. Tài nguyên ở đây có thể là một ổ đĩa, một record trong cơ sở dữ liệu, hay một không gian địa chỉ trên bộ nhớ chính. Sau đây là một số ví dụ để minh hoạ cho điều trên.

Ví dụ 1: Giả sử có hai tiến trình P1 và P2 hoạt động đồng thời trong hệ thống. Tiến trình P1 đang giữ tài nguyên R1 và xin được cấp R2 để tiếp tục hoạt động, trong khi đó tiến trình P2 đang giữ tài nguyên R2 và xin được cấp R1 để tiếp tục hoạt động. Trong trường hợp này cả P1 và P2 sẽ không tiếp tục hoạt động được. Như vậy P1 và P2 rơi vào trạng thái tắc nghẽn.

- Tắc nghẽn thường xảy ra do xung đột về tài nguyên thuộc loại không phân chia được, một số ít trường hợp xảy ra với tài nguyên phân chia được. Ví dụ sau đây là trường hợp tắc nghẽn do xung đột về tài nguyên bộ nhớ, là tài nguyên thuộc loại phân chia được.

Ví dụ 2: Trong các ứng dụng cơ sở dữ liệu, một chương trình có thể khoá một vài record mà nó sử dụng, để dành quyền điều khiển về cho nó. Nếu tiến trình P1 khoá record R1, tiến trình P2 khoá record R2, và rồi sau đó mỗi tiến trình lại cố gắng khoá record của một tiến trình khác. Tắc nghẽn sẽ xảy ra.

Như vậy tắc nghẽn là hiện tượng: Trong hệ thống xuất hiện một tập các tiến trình, mà mỗi tiến trình trong tập này đều chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình trong tập này chiếm giữ. Và sự đợi này có thể kéo dài vô hạn nếu không có sự tác động từ bên ngoài.

- Trong trường hợp của ví dụ 1 ở trên: hai tiến trình P1 và P2 sẽ rơi vào trạng thái tắc nghẽn, nếu không có sự can thiệp của hệ điều hành. Để phá bỏ tắc nghẽn này hệ điều hành có thể cho tạm dừng tiến trình P1 để thu hồi lại tài nguyên R1, lấy R1 cấp cho tiến trình P2 để P2 hoạt động và kết thúc, sau đó thu hồi cả R1 và R2 từ tiến trình P2 để cấp cho P1 và tái kích hoạt P1 để P1 hoạt động trở lại. Như vậy sau một khoảng thời gian cả P1 và P2 đều ra khỏi tình trạng tắc nghẽn.

- Khi hệ thống xảy ra tắc nghẽn nếu hệ điều hành không kịp thời phá bỏ tắc nghẽn thì hệ thống có thể rơi vào tình trạng treo toàn bộ hệ thống. Như trong trường hợp tắc nghẽn ở ví dụ 1, nếu sau đó có tiến trình P3, đang giữ tài nguyên R3, cần R2 để tiếp tục thì P3 cũng sẽ rơi vào tập tiến trình bị tắc nghẽn, rồi sau đó nếu có tiến trình P4 cần tài nguyên R1 và R3 để tiếp tục thì P4 cũng rơi vào tập các tiến trình bị tắc nghẽn như P3, … cứ thế dần dần có thể dẫn đến một thời điểm tất cả các tiến trình trong hệ thống đều rơi vào tập tiến trình tắc nghẽn. Và như vậy hệ thống sẽ bị treo hoàn toàn.

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

Ví dụ 4: 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_hoangminh[I22B]

Tổng số bài gửi : 24
Join date : 17/03/2013
Age : 26

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

Về Đầu Trang Go down

Re: Deadlock và 1 số ví dụ

Bài gửi  NguyenThiThom(I22A) on 12/4/2013, 02:03

Ví dụ 4: 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...
Theo mình thấy ví dụ này không đúng lắm. Nó không được gọi là Deadlock vì deadlock là chờ mãi mãi mà không được đáp ứng, còn ở đây khách hàng 101, 102 có thể chờ trong 1 khoảng thời gian để những khách hàng khác gọi xong sẽ đến lượt mình Very Happy

NguyenThiThom(I22A)

Tổng số bài gửi : 28
Join date : 11/03/2013

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

Về Đầu Trang Go down

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