Những điều Kiện Cần Thiết Gây Ra Deadlock Đồ Thị Cấp Phát Tài Nguyên

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Kỹ thuật lập trình >

Những điều kiện cần thiết gây ra deadlock Đồ thị cấp phát tài nguyên

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (451.45 KB, 20 trang )

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

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 q 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 ngun đó, q trìnhu 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àinguyê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 ngun từ q trình đang giữ chúng: Các tài ngunkhơng thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bởi q trình đang giữ nó, sau khi q trình đó hồ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 {P , P1,…,Pn} đang chờ mà trong đó P đ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 P. Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlockxảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiện khơng hồn tồn độc lập.

IV.2 Đồ thị cấp phát tài ngun

Deadlock có thể mơ tả chính xác hơn bằng cách hiển thị đồ thị có hướng gọi là đồ thị cấp phát tài nguyên hệ thống. Đồ thị này chứa một tập các đỉnh V và tập hợpcác cạnh E. Một tập các đỉnh V được chia làm hai loại nút P = {P1, P2,…,Pn} là tập hợp các quá trình hoạt động trong hệ thống, và R = {R1, R2, ..., Rm} là tập hợp chứa tất cả các loại tài nguyên trong hệ thống.Một cạnh có hướng từ q trình Pitới loại tài ngun Rjđược ký hiệu Pi→Rj; nó biểu thị rằng q trình Piđã yêu cầu loại tài nguyên Rjvà hiện đang chờ loại tài nguyên đó. Một cạnh có hướng từ loại tài nguyên Rjtới quá trình Piđược hiển thị bởi Rj→ Pi; nó hiển thị rằng thể hiện của loại tài nguyên Rjđã được cấp phát tới quá trình Pi. Một cạnh có hướng Pi→ Rjđược gọi là cạnh yêu cầu; một cạnh có hướng Rj→ Piđược gọi là cạnh gán. Bằng hình tượng, chúng ta hiển thị mỗi quá trình Pilà một hình tròn, và mỗi loại tài ngun Rjlà hình chữ nhật. Vì loại tài ngun Rjcó thể có nhiều hơn một thể hiện, chúng ta hiển thị mỗi thể hiện là một chấm nằm trong hình vng. Chú ý rằngmột cạnh yêu cầu trỏ tới chỉ một hình vuông Rj, trái lại một cạnh gán cũng phải gán tới một trong các dấu chấm trong hình vng.Khi q trình Piyêu cầu một thể hiện của loại tài nguyên Rj, một cạnh yêu cầu được chèn vào đồ thị cấp phát tài nguyên. Khi yêu cầu này có thể được đáp ứng, cạnhyêu cầu lập tức được truyền tới cạnh gán. Khi q trình khơng còn cần truy xuất tới tài nguyên, nó giải phóng tài nguyên, và khi đó dẫn đến cạnh gán bị xố.Đồ thị cấp phát tài nguyên được hiển thị trong hình VI-1 dưới đây mô tả trường hợp sau:Biên soạn: Th.s Nguyễn Phú Trường - 092005 Trang 115Hình 0-1 Đồ thị cấp phát tài ngun• Các tập P, R, và E: oP = {P1, P2, P3} oR = {R1, R2, R3, R4} oE = {P1→R1, P2→R3, R1→P2, R2→P2, R3→P3} • Các thể hiện tài nguyêno Một thể hiện của tài nguyên loại R1o Hai thể hiện của tài nguyên loại R2o Một thể hiện của tài nguyên loại R3o Một thể hiện của tài ngun loại R4• Trạng thái q trình oQ trình P1đang giữ một thể hiện của loại tài nguyên R2và đang chờ một thể hiện của loại tài nguyên R1. oQuá trình P2đang giữ một thể hiện của loại tài nguyên R1và R2và đang chờ một thể hiện của loại tài nguyên R3. oQuá trình P3đang giữ một thể hiện của R3Đồ thị cấp phát tài nguyên hiển thị rằng, nếu đồ thị khơng chứa chu trình, thì khơng có quá trình nào trong hệ thống bị deadlock. Nếu đồ thị có chứa chu trình, thìdeadlock có thể tồn tại. Nếu mỗi loại tài ngun có chính xác một thể hiện, thì một chu trình ngụ ý rằngmột deadlock xảy ra. Nếu một chu trình bao gồm chỉ một tập hợp các loại tài nguyên, mỗi loại tài nguyên chỉ có một thể hiện thì deadlock xảy ra. Mỗi q trình chứa trongchu trình bị deadlock. Trong trường hợp này, một chu trình trong đồ thị là điều kiện cần và đủ để tồn tại deadlock.Nếu mỗi loại tài nguyên có nhiều thể hiện thì chu trình khơng ngụ ý deadlock xảy. Trong trường hợp này, một chu trình trong đồ thị là điều kiện cần nhưng chưa đủđể tồn tại deadlock. Để hiển thị khái niệm này, chúng ta xem lại đồ thị ở hình VII-1 ở trên. Giả sửquá trình P3yêu cầu một thể hiện của loại tài ngun R2. Vì khơng có thể hiện tài ngun hiện có, một cạnh yêu cầu P3→ R2được thêm vào đồ thị hình VI-2. Tại thời điểm này, hai chu trình nhỏ tồn tại trong hệ thống:Biên soạn: Th.s Nguyễn Phú Trường - 092005 Trang 116P1→ R1→ P2→ R3→ P3→ R2→ P1P2→ R3→ P3→ R2→ P2Hình 0-2 Đồ thị cấp phát tài nguyên với deadlockQuá trình P1, P2, và P3bị deadlock. Quá trình P3đang chờ tài nguyên R3, hiện được giữ bởi quá trình P2. Hay nói cách khác, q trình P3đang chờ q trình P1hay P2giải phóng tài ngun R2. Ngồi ra, q trình P1đang chờ q trình P2giải phóng tài ngun R1. Bây giờ xem xét đồ thị cấp phát tài ngun trong hình VI-3 dưới đây. Trong thídụ này, chúng ta cũng có một chu kỳ P1→ R1→ P3→ R2→ P1Hình 0-3 Đồ thị cấp phát tài ngun có chu trình nhưng khơng bị deadlockBiên soạn: Th.s Nguyễn Phú Trường - 092005 Trang 117Tuy nhiên, khơng có deadlock. Chú ý rằng q trình P4có thể giải phóng thể hiện của loại tài nguyên R2. Tài nguyên đó có thể được cấp phát tới P3sau đó, chu trình sẽ khơng còn.Tóm lại, nếu đồ thị cấp phát tài ngun khơng có chu trình thì hệ thống khơng có trạng thái deadlock. Ngồi ra, nếu có chu trình thì có thể có hoặc khơng trạng tháideadlock. Nhận xét này là quan trọng khi chúng ta giải quyết vấn đề deadlock.V Các phương pháp xử lý deadlockPhầ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, đảmbả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 hồn tồn vấn đề này và giả vờ deadlock không baogiờ 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 trong phần VI.4.1 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ờigian 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 u cầu hiện tại có thểđược thoả mãn hay phải bị trì hỗ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ủamỗi q 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ấpmộ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 đếntrườ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ởinhữ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 xun; 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 deadlockmà 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ộBiên soạn: Th.s Nguyễn Phú Trường - 092005 Trang 118đị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ềukiệ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.VI Ngăn chặn deadlockĐể 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ặnviệ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.

VI.1 Loại trừ hỗ tương

Xem Thêm

Tài liệu liên quan

• Dead lock - Khóa chết
  • 20
  • 860
  • 3

Tải bản đầy đủ (.pdf) (20 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(451.45 KB) - Dead lock - Khóa chết-20 (trang) Tải bản đầy đủ ngay ×