Chương 7 Tắt Nghẽn - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (24 trang)

Trang chủ

Giáo án - Bài giảng

Cao đẳng - Đại học

Chương 7 Tắt nghẽ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 (393.04 KB, 24 trang )

P a g e | 37.1. Khái niệm: Trong môi trường đa nhiệm, nhiều tiến trình khác nhau có thể cùng cạnh tranh 1 tài nguyên. Khi một tiến trình đang chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình khác chiếm giữ, thì tiến trình đó đi vào trạng thái chờ và rất có thể sẽ không bao giờ chuyển trạng thái trở lại nếu không có sự tác động từ bên ngoài. Hiện tượng này được gọi là: Deadlock. Hay nói 1 cách khác: Hiện tượng Deadlock bắt nguồn từ sự xung đột về tài nguyên của 2 hoặc nhiều tiến trình đang hoạt động đông thời trên hệ thống.+ Xem 2 ví dụ sau: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 Deadlock. Ví dụ 2: Giả sử không gian bộ nhớ còn trống là 300Kb, và trong hệ thống có hai tiến trình P1 và P2 hoạt động đồng thời. P1 và P2 yêu cầu được sử dụng bộ nhớ như sau: P1 P2…. ….Yêu cầu lần thứ 1 100Kb 120Kb… … Yêu cầu lần thứ 2 50Kb 60Kb … … Deadlock xảy ra khi cả hai tiến trình cùng yêu cầu thêm bộ nhớ lần thứ hai. Tại thời điểm này không gian bộ nhớ còn trống là 80Kb, lớn hơn lượng bộ nhớ mà mỗi tiến trình yêu cầu (50Kb và 60Kb), nhưng vì cả hai tiến trình đồng thời yêu cầu thêm bộ nhớ, nên hệ thống không để đáp ứng được, và Deadlock xảy ra.• Khi hệ thống xảy ra Deadlock, nếu HĐH không kịp thời phá bỏ Deadlock thì hệ thống có thể rơi vào tình trạng treo toàn bộ hệ thống.CHƯƠNG 7.DEADLOCK| TinK31Atài nguyênR2tài nguyênR1Tiến trình P2Tiến trìnhP1Yêu cầuYêu cầuGiữGiữChờ đợi vòng trònP a g e | 4• Một lập trình viên đang phát triển những ứng dụng đa luồng phải quan tâm đặc biệt tới vấn đề này, bởi vì nhiều luồng có thể cạnh tranh trên một tài nguyên chia sẻ.Lưu ý:• Một hệ thống chứa số tài nguyên hữu hạn được phân bổ giữa nhiều tiến trình khác nhau và cạnh tranh nhau.• Trước khi sử dụng một tài nguyên nào đó, một tiến trình phải yêu cầu hệ thống thông qua các lời gọi, và sau đó phải giải phóng tài nguyên đó. (Thứ tự sử dụng tài nguyên của 1 tiến trình dưới sự điều hành của 1 hệ thống thông thường)• Số tài nguyên được yêu cầu không được vượt quá tổng số tài nguyên sẵn có trong hệ thống. Nếu yêu cầu không được đáp ứng tức thì thì tiến trình đó sẽ đi vào trạng thái chờ.7.2. Điều kiện hình thành Deadlock:Năm 1971, Coffman đã đưa ra và chứng tỏ được rằng, nếu hệ thống tồn tại đồng thời bốn điều kiện sau đây thì hệ thống sẽ xảy ra Deadlock:1. Độc quyền sử dụng: Tồn tại ít nhất 1 tài nguyên không thể chia sẻ và được giữ bởi duy nhất 1 tiến trình. Nếu có 1 tiến trình khác yêu cầu tài nguyên này, thì tiến trình đó phải ở trong trạng thái chờ cho đến khi tài nguyên yêu cầu được giải phóng.2. Giữ và chờ cấp thêm tài nguyên: Một tiến trình ở thời điểm hiện tại đang giữ tài nguyên lại yêu cầu cấp phát thêm tài nguyên mới.3. Không đòi lại tài nguyên từ tiến trình đang giữ: Không một tiến trình nào có thể tự giải phóng tài nguyên mà nó đang chiếm giữ.Trong nhiều trường hợp các điều kiện trên là rất cần thiết đối với hệ thống. Sự thực hiện độc quyền là cần thiết để bảo đảm tính đúng đắn của kết quả và tính toàn vẹn của dữ liệu (chúng ta đã thấy điều này ở phần tài nguyên găng trên đây). Tương tự, sự ưu tiên không thể thực hiện một cách tuỳ tiện, đặt biệt đối với các tài nguyên có liên quan với nhau, việc giải phóng từ một tiến trình này có thể ảnh hưởng đên kết quả xử lý của các tiến trình khác. Deadlock có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra chỉ với 3 điều kiện đó. Để chắc chắn Deadlock xảy ra cần phải có điều kiện thư tư.4. Tồn tại chu trình trong đồ thị cấp phát tài nguyên: Một tập các tài nguyên đang ở trong trạng thái chờ {P0, P1, , Pn} mà khi đó P0 đang chờ 1 tài nguyên được giữ bởi P1, P1 đang chờ tài nguyên được giữ bởi P2, , Pn đang chờ tài nguyên được giữ bởi P0.Ba điều kiện đầu là điều kiện cần chứ không phải là điều kiện đủ để xảy ra Deadlock. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu. 7.2.1 Đồ thị cấp phát tài nguyên:CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 5Deadlock 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ợp cá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 tiến 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ừ tiến trình Pi tới loại tài nguyên Rj được ký hiệu Pi  Rj, nó biểu thị rằng tiến trình Pi đã yêu cầu loại tài nguyên Rj và hiện đang chờ loại tài nguyên đó. Một cạnh có hướng từ loại tài nguyên Rj tới tiến 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 tiến 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 tiến trình Pi là một hình tròn, và mỗi loại tài nguyên Rj là hình chữ nhật. Vì loại tài nguyên Rj có 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 vuông. Chú ý rằng mộ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 vuông.Khi tiến trình Pi yê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ạnh yêu cầu lập tức được truyền tới cạnh gán. Khi tiến 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ị xoá.Đồ thị cấp phát tài nguyên được hiển thị trong hình dưới đây mô tả trường hợp sau: Trạng thái tiến trình• Tiến trình P1 đang giữ một thể hiện của loại tài nguyên R2 và đang chờ một thể hiện của loại tài nguyên R1.• Tiến trình P2 đang giữ một thể hiện của loại tài nguyên R1 và R2 và đang chờ một thể hiện của loại tài nguyên R3.• Tiến trình P3 đang giữ một thể hiện của R3CHƯƠNG 7.DEADLOCK| TinK31ACác tập P, R, và E:P = {P1, P2, P3}R = {R1, R2, R3, R4}E = {P1R1, P2R3, R1P2, R2P2, R3P3}Các thể hiện tài nguyên• Một thể hiện của tài nguyên loại R1 • Hai thể hiện của tài nguyên loại R2 • Một thể hiện của tài nguyên loại R3 • Ba thể hiện của tài nguyên loại R4P a g e | 6Đồ 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ó tiến 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 nguyên có chính xác một thể hiện, thì một chu trình ngụ ý rằng mộ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 tiến trình chứa trong chu 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 ra. 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 trên. Giả sử tiến trình P3 yêu cầu một thể hiện của loại tài nguyên R2. Vì không có thể hiện tài nguyên 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:P1  R1  P2  R3  P3  R2  P1P2  R3  P3  R2  P2Tiến trình P1, P2, và P3 bị Deadlock. Tiến trình P3 đang chờ tài nguyên R3, hiện được giữ bởi tiến trình P2. Hay nói cách khác, tiến trình P3 đang chờ tiến trình P1 hay P2 giải phóng tài nguyên R2. Ngoài ra, tiến trình P1 đang chờ tiến trình P2 giải phóng tài nguyên R1.Bây giờ xem xét đồ thị cấp phát tài nguyên trong hình dưới đây. Trong thí dụ này, chúng ta cũng có một chu trình: P1  R1  P3  R2  P1Tuy nhiên, không có Deadlock. Chú ý rằng tiến trình P4 có 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 P3 sau đó, chu trình sẽ không còn.Tóm lại, nếu đồ thị cấp phát tài nguyên không có chu trình thì hệ thống không có trạng thái Deadlock.Ngoài ra, nếu có chu trình thì có thể có hoặc không trạng thái Deadlock. Nhận xét này là quan trọng khi chúng ta giải quyết vấn đề Deadlock.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 77.3. Các phương pháp xử lý Deadlock:Nói chung, chúng ta có thể giải quyết vấn đề Deadlock theo một trong ba cách:1. Chúng ta có thể sử dụng một giao thức để ngăn chặn hoặc tránh những Deadlock, bảo đảm rằng hệ thống sẽ không bao giờ đi vào trạng thái Deadlock.• Giải thuật ngăn chặn deaclock: 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 trong các điều kiện cần thiết để Deadlock không thể xảy ra( ràng buộc yêu cầu về tài nguyên) . Chúng ta sẽ thảo luận về những phương pháp này trong phần 7.4. • Tránh Deadlock: Yêu cầu hệ điều hành cung cấp thêm thông tin bổ sung về loại tài nguyên mà một tiến trình sẽ yêu cầu và sử dụng trong thời gian hoạt động của nó. Với thông tin bổ sung này, hệ thống sẽ đưa ra quyết định đối với mỗi tiến trình rằng có nên chờ hay không. Lúc đó, hệ thống xem xét tài nguyên hiện có, tài nguyên cần cấp phát cho mỗi tiến trình, và các yêu cầu giải phóng trong tương lai của mỗi tiến trình. Chúng tôi sẽ thảo luận các vấn đề này trong phần 7.5. 2. 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.Nếu một hệ thống không sử dụng giải thuật ngăn chặn hay tránh Deadlock thì Deadlock có thể phát sinh. Hệ thống có thể cung cấp một thuật toán nhằm kiểm tra tình trạnnhiện tại có xảy ra Deadlock chưa và một thuật toán để phục hồi (nếu một Deadlock đã thực sự xảy ra). Chúng tôi thảo luận về những vấn đề này trong mục 7.6 và mục 7.7 3. Chúng ta có thể bỏ qua vấn đề này và giả thiết rằng 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.Nếu hệ thống không đảm bảo rằng Deadlock sẽ không bao giờ xảy ra, cũng không cung cấp một cơ chế để phát hiện và phục hồi Deadlock, thì khi đó có thể dẫn đến trường hợp hệ thống đang ở trạng thái Deadlock nhưng không có cách để nhận biết. Trong trường hợp này, Deadlock không bị phát hiện sẽ làm giảm hiệu suất của hệ thống, bởi vì tài nguyên đang được tổ chức bởi các tiến trình mà nó không thể chạy, các tiến trình ngày càng nhiều, khi đó chúng có những yêu cầu về tài nguyên, và đi vào trạng thái Deadlock. Cuối cùng, hệ thống sẽ ngừng các hoạt động và cần phải khởi động lại bằng tay.7.4. Ngăn chặn Deadlock Trong phần II, có 4 điều kiện để cho deadlock xảy ra. Bằng cách đảm bảo rằng ít nhất một trong những điều kiện đó không xảy ra, chúng ta có thể ngăn chặn sự xuất hiện của deadlock. 7.4.1. Độc quyền sử dụng:Điều kiện độc quyền sử dụng là tồn tại tài nguyên không được chia sẻ. Ví dụ, một máy in không thể cùng lúc được chia sẻ bởi nhiều tiến trình. Ngược lại, các tài nguyên có thể CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 8chia sẽ không đòi hỏi truy xuất độc quyền và do đó không thể dẫn đến Deadlock. Những tập tin có thuộc tính read-only là một ví dụ điển hình của một tài nguyên có thể chia sẻ. Nếu vài tiến trình thử mở một tập tin này cùng lúc, chúng có thể được cấp quyền truy cập đồng thời vào tập tin. Một tiến trình không cần thiết phải chờ một nguồn tài nguyên có thể chia sẻ.Tuy nhiên, thường thì chúng ta không thể ngăn chặn Deadlocks bằng cách từ chối điều kiện độc quyền sử dụng, bởi vì một số tài nguyên về bản chất là không thể chia sẻ. Tuy nhiên, với những tài nguyên thuộc loại không chia sẻ được thì hệ điều hành có thể sử dụng kỹ thuật SPOOL (Smulataneous Peripheral Operation Online) để tạo ra nhiều tài nguyên ảo cung cấp cho các tiến trình đồng thời.).7.4.2. Giữ và chờ cấp thêm tài nguyên:Để đ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 bảo đảm rằng: bất cứ khi nào một tiến trình yêu cầu tài nguyên, nó không đang chiếm giữ bất kỳ tài nguyên khác.• Phương pháp 1: Đòi hỏi tất cả tài nguyên của mỗi tiến trình trước khi nó bắt đầu thực thi, bằng cách đặt lời gọi hệ thống yêu cầu tài nguyên cho một tiến trình trước tất cả các lời gọi hệ thống khác.• Phương pháp 2: Cho phép một tiến trình yêu cầu tài nguyên khi nó không đang giữ tài nguyên nào. Trước khi 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ả các nguồn tài nguyên mà nó hiện đang được cấp phát. Ví dụ: Chúng ta xem xét một tiến trình sao chép dữ liệu từ một ổ đĩa DVD vào một tập tin trên đĩa (1), sắp xếp tập tin (2) và in ấn kết quả ra máy in (3).• Phương pháp 1: Nếu tất cả các tài nguyên được yêu cầu ngay từ lúc tiến trình bắt đầu, thì tiến trình phải gởi yêu cầu đến cả ổ đĩa DVD, tập tin trên đĩa, và máy in. Nó sẽ giữ máy in trong toàn bộ thời gian thực thi, mặc dù nó chỉ cần máy in vào giai đoạn cuối.• Phương pháp 2: Cho phép tiến trình chỉ gởi yêu cầu đến ổ đĩa DVD và tập tin trên đĩa. Nó sao chép DVD vào đĩa và sau đó giải phóng cả DVD và tập tin trên đĩa . Tiến trình lại gởi yêu cầu đến tập tin và máy in. Sau khi sao chép các tập tin vào máy in, nó giải phóng cả hai tài nguyên này và kết thúc.Cả hai giao thức này có hai nhược điểm chính. 1. Lãng phí tài nguyên. Tài nguyên có thể được giao nhưng không được sử dụng trong một thời gian dài. Trong ví dụ trên, chúng ta có thể giải phóng ổ đĩa DVD và tập tin, và sau đó lại một lần nữa đưa ra yêu cầu tập tin và máy in, nếu chúng ta chắc chắn rằng dữ liệu của chúng ta vẫn còn ở trên tệp đĩa. Nếu chúng ta không thể yên tâm về điều đó, thì sau đó chúng ta phải đòi hỏi tất cả tài nguyên bắt đầu lại đối với cả 2 phương pháp. 2. Sự thiếu thốn có thể xảy ra. Một tiến trình cần sử dụng những tài nguyên hay được sử dụng có thể phải chờ vô hạn định, vì có thể một trong những tài nguyên mà nó cần lại luôn được giao cho một số tiến trình khác .7.4.3. Không đòi lại tài nguyên từ quá trình đang giữ nó. CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 9Điều kiện cần thứ ba cho Deadlock là không đòi lại được tài nguyên mà đã được cấp phát. Để đảm bảo các điều kiện này không xảy ra, chúng ta có thể sử dụng phương pháp sau đây:Nếu một tiến trình đang ở trạng thái chờ, thì hệ thống sẽ thu hồi tài nguyên mà tiến trình đó đang giữ, cấp cho tiến trình khác. Và tiến trình đó sẽ được khởi động lại chỉ khi nó được cung cấp lại đầy đủ tài nguyên cũ cũng như tài nguyên mới mà nó yêu cầu.Hiểu theo cách khác, nếu một tiến trình yêu cầu một vài tài nguyên, trước tiên chúng ta kiểm tra xem chúng có sẵn hay không .(1) Nếu có, sẽ phân phối.(2) Nếu không, chúng ta kiểm tra xem có phải chúng đã được phân phối cho các tiến trình khác đang chờ hay ko, để chúng ta chặn trước tài nguyên từ tiến trình chờ và phân bổ chúng vào tiến trình yêu cầu. (3) Nếu những tài nguyên không sẵn có mà cũng không được giữ bởi một tiến trình chờ, thì đòi hỏi tiến trình phải đợi. Trong khi đang chờ đợi, những tài nguyên của nó có thể được chặn trước, trừ khi tiến trình khác đòi hỏi chúng. Một tiến trình chỉ có thể được khởi động lại khi nó được cấp phát những tài nguyên mới mà nó đòi hỏi và khôi phục bất kỳ tài nguyên nào mà được chặn trước trong khi nó đang chờ đợi. Phương pháp này thường được ứng dụng vào những tài nguyên mà có trạng thái có thể dễ dàng được lưu trữ và khôi phục sau đó như : CPU, không gian bộ nhớ. Nó có thể không được áp dụng cho những tài nguyên như máy in và băng từ. 7.4.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à cuối cùng là tồn tại một chu trình trong đồ thị cấp phát tài nguyên. Một cách để đảm bảo đ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 tiến trình theo thứ tự tăng dần của số lượng. Để minh họa, cho R = (R1, R2, , Rn) là tập hợp các loại tài nguyên. Gán mỗi loại tài nguyên cho một số nguyên duy nhất, mà cho phép chúng ta dùng để so sánh hai tài nguyên và để xác định liệu có hay không một tài nguyên khác được sắp xếp trước trong sự điều chỉnh của chúng ta. Về hình thức, chúng tôi định nghĩa hàm một đối một : F: R  N, trong đó N là tập hợp các số tự nhiên. Chẳng hạn như, nếu tập hợp các loại tài nguyên R bao gồm: các ổ đĩa băng, ổ đĩa, và máy in, sau đó chức năng hàm F có thể được định nghĩa như sau:F(tape drive) =1F(disk drive) = 5F(printer) = 12Bây giờ chúng ta có thể xem xét phương thức sau đây để ngăn chặn Deadlocks: Mỗi tiến trình có thể yêu cầu tài nguyên duy nhất chỉ trong thứ tự tăng của số lượng. Nghĩa là, một tiến trình ban đầu có thể yêu cầu bất kỳ số lượng thể hiện của một loại tài nguyên Ri. Sau đó, tiến trình có thể yêu cầu thêm loại tài nguyên Rj khi và chỉ khi F(Rj) > F (Ri). Nếu một vài trường hợp các loại tài nguyên đó là cần thiết, thì chúng phải đưa ra. Ví dụ, bằng cách sử dụng chức năng xác định trước đó, một tiến trình mà muốn sử dụng ổ đĩa băng và máy in cùng một lúc đầu tiên phải yêu cầu các ổ đĩa băng và sau đó yêu cầu máy in. Cách CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 10khác, bất cứ khi nào một tiến trình đòi hỏi tài nguyên Rj, nó sẽ đưa ra bất cứ tài nguyên Ri sao cho F(Ri) ≥ F(Rj).Nếu hai giao thức này được sử dụng, thì điều kiện tồn tại chu trình không thể xảy ra. Giả sử một tập hợp của những tiến trình phức tạp của các tiến trình {P0,P1,…,Pn}, trong đó Pi là chờ đợi nguồn tài nguyên Ri, mà được giữ bởi tiến trình Pi+1. Theo số học modul được sử dụng trên các chỉ số, Pn đợi một tài nguyên Rn được giữ bởi P0. Sau đó trong khi tiến trình Pi+1 vừa nắm giữ tài nguyên Ri vừa yêu cầu tài nguyên Ri+1 thì chúng ta phải có F(Ri)<F(Ri+1), cho tất cả các i. Nhưng điều kiện này có nghĩa F(Ro)< F(R1)< < F (Rn)< F (Ro). Do tính bắc cầu, F(Ro) < F(Ro) là không thể đạt được. Bởi vậy, ở đó ko thể có chu trình. 7.5 Tránh DeadlockPhương pháp ngăn chặn Deadlock đã được đề cập ở trên là đảm bảo một trong những điều kiện gây ra Deadlock không thể xảy ra. Tuy nhiên phương án này có nhược điểm là việc sử dụng thiết bị chậm và thông lượng hệ thống bị giảm.Một phương pháp khác để tránh deadlock là yêu cầu thông tin bổ sung về các tài nguyên được yêu cầu. Thí dụ, trong một hệ thống với một ổ băng từ và một máy in, tiến trình P sẽ yêu cầu ổ băng từ và máy in trước khi giải phóng cả hai tài nguyên. Trái lại, tiến trình Q sẽ yêu cầu và giải phóng máy in trước và sau đó mới đến ổ băng từ. Với thông tin về thứ tự hoàn thành của yêu cầu và giải phóng cho mỗi tiến trình, chúng ta có thể quyết định cho mỗi yêu cầu của tiến trình sẽ chờ hay không để tránh khả năng xảy ra deadlock.Ta có thể xây dựng một giải thuật đảm bảo hệ thống sẽ không bao giờ đi vào trạng thái deadlock. Đây là giải thuật định nghĩa tiếp cận tránh deadlock. Giải thuật tránh deadlock tự xem xét trạng thái cấp phát tài nguyên để đảm bảo điều kiện tồn tại chu trình trong đồ thị cấp phát tài nguyên không bao giờ xảy ra. Trạng thái cấp phát tài nguyên được định nghĩa bởi số tài nguyên sẳn dùng và tài nguyên được cấp phát với số yêu cầu tối đa của các tiến trình. 7.5.1 Trạng thái an toàn:Một trạng thái là an toàn nếu hệ thống có thể cấp phát các tài nguyên tới mỗi tiến trình theo một vài thứ tự nhất định và vẫn tránh deadlock. Hay nói cách khác, một hệ thống ở trong trạng thái an toàn chỉ nếu ở đó tồn tại một thứ tự an toàn. Thứ tự của các tiến trình <P1, P2, …, Pn> là một thứ tự an toàn cho trạng thái cấp phát hiện hành nếu đối với mỗi thứ tự Pi, các tài nguyên mà Pi yêu cầu vẫn có thể được thoả mãn bởi tài nguyên hiện có cộng với các tài nguyên được giữ bởi tất cả Pj, với j<i. Trong trường hợp này, nếu những tài nguyên mà tiến trình Pi yêu cầu không sẳn dùng tức thì thì Pi có thể chờ cho đến khi tất cả Pj hoàn thành. Khi chúng hoàn thành, Pi có thể đạt được tất cả những tài nguyên nó cần, hoàn thành các tác vụ được gán, trả về những tài nguyên được cấp phát cho nó và kết thúc. Khi Pi kết thúc, Pi+1 có thể đạt được các tài nguyên nó cần, Nếu không có thứ tự như thế tồn tại thì trạng thái hệ thống là không an toàn. Một trạng thái an toàn là trạng thái không bao giờ xảy ra deadlock. Do đó, deadlock là trạng thái không an toàn. Tuy nhiên, không phải tất cả trạng thái không an toàn là deadlock. Một trạng thái không an toàn có thể dẫn đến deadlock. Với điều kiện trạng thái là an toàn, hệ điều hành có thể tránh trạng thái không an toàn (và deadlock). CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 11Không gian trạng thái an toàn, không an toàn, deadlockĐể minh hoạ, chúng ta xét một hệ thống với 12 ổ băng từ và 3 tiến trình: P0, P1, P2. Tiến trình P0 yêu cầu 10 ổ băng từ, tiến trình P1 có thể cần 4 và tiến trình P2 có thể cần tới 9 ổ băng từ. Giả sử rằng tại thời điểm t0, tiến trình P0 giữ 5 ổ băng từ, tiến trình P1 giữ 2 và tiến trình P2 giữ 2 ổ băng từ. (Do đó, có 3 ổ băng từ còn rảnh).Nhu cầu tối đa Nhu cầu hiện tạiP0 10 5 P1 4 2 P2 9 2 Tại thời điểm t0, hệ thống ở trạng thái an toàn. Thứ tự <P1,P0, P2> thoả điều kiện an toàn vì tiến trình P1 có thể được cấp phát tức thì tất cả các ổ đĩa từ và sau đó trả lại chúng (sau đó hệ thống có 5 ổ băng từ sẳn dùng), sau đó tiến trình P0 có thể nhận tất cả ổ băng từ và trả lại chúng (sau đó hệ thống sẽ có 10 ổ băng từ sẳn dùng), và cuối cùng tiến trình P2 có thể nhận tất cả ổ băng từ của nó và trả lại chúng (sau đó hệ thống sẽ có tất cả 12 ổ băng từ sẳn dùng).Một hệ thống có thể đi từ trạng thái an toàn tới một trạng thái không an toàn. Giả sử rằng tại thời điểm t1, tiến trình P2 yêu cầu và được cấp 1 ổ băng từ nữa. Hệ thống không còn trong trạng thái an toàn. Tại điểm này, chỉ tiến trình P1 có thể được cấp tất cả ổ băng từ của nó. Khi nó trả lại chúng, chỉ tiến trình P1 có thể được cấp phát tất cả ổ băng từ. Khi nó trả lại chúng, hệ thống chỉ còn 4 ổ băng từ sẳn có. Vì tiến trình P0 được cấp phát 5 ổ băng từ, nhưng có tối đa 10, tiến trình P0 phải chờ. Tương tự, tiến trình P2 có thể yêu cầu thêm 6 ổ băng từ và phải chờ dẫn đến deadlock. Lỗi của chúng ta là gán yêu cầu từ tiến trình P2 cho 1 ổ băng từ nữa. Nếu chúng ta làm cho P2 phải chờ cho đến khi các tiến trình khác kết thúc và giải phóng tài nguyên của nó thì chúng ta có thể tránh deadlock. Với khái niệm trạng thái an toàn được cho, chúng ta có thể định nghĩa các giải thuật tránh deadlock. Ý tưởng đơn giản là đảm bảo hệ thống sẽ luôn còn trong trạng thái an toàn. Khởi đầu, hệ thống ở trong trạng thái an toàn. Bất cứ khi nào một tiến trình yêu cầu một tài nguyên hiện có, hệ thống phải quyết định tài nguyên có thể được cấp phát tức thì hoặc tiến CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 12trình phải chờ. Yêu cầu được gán chỉ nếu việc cấp phát để hệ thống trong trạng thái an toàn. Trong mô hình này, nếu tiến trình yêu cầu tài nguyên đang có, nó có thể vẫn phải chờ. Do đó, việc sử dụng tài nguyên có thể chậm hơn mà không có giải thuật tránh deadlock. 7.5.2 Giải thuật cấp phát tài nguyên:Nếu chúng ta có một hệ thống cấp phát tài nguyên với thể hiện của mỗi loại, một biến dạng của đồ thị cấp phát tài nguyên có thể được dùng để tránh deadlock. Ngoài các cạnh yêu cầu và gán, chúng ta có một loại cạnh mới được gọi là cạnh thỉnh cầu (claim edge). Một cạnh thỉnh cầu Pi  Rj hiển thị quá trình Pi có thể yêu cầu tài nguyên Rj vào một thời điểm trong tương lai. Cạnh này tương tự cạnh yêu cầu về phương hướng nhưng được hiện diện bởi dấu đứt quãng. Khi quá trình Pi yêu cầu tài nguyên Rj, cạnh thỉnh cầu Pi  Rj chuyển tới cạnh yêu cầu. Tương tự, khi một tài nguyên Rj được giải phóng bởi Pi, cạnh gán Rj  Pi được chuyển trở lại thành cạnh thỉnh cầu Pi  Rj. Chúng ta chú ý rằng các tài nguyên phải được yêu cầu trước trong hệ thống. Nghĩa là, trước khi Pi bắt đầu thực thi, tất cả các cạnh thỉnh cầu của nó phải xuất hiện trong đồ thị cấp phát tài nguyên. Chúng ta có thể giảm nhẹ điều kiện này bằng cách cho phép một cạnh Pi  Rj để được thêm tới đồ thị chỉ nếu tất cả các cạnh gắn liền với quá trình Pi là các cạnh thỉnh cầu. Giả sử rằng Pi yêu cầu tài nguyên Rj. Yêu cầu có thể được gán chỉ nếu chuyển cạnh yêu cầu Pi Rj tới cạnh gán Rj  Pi không dẫn đến việc hình thành chu trình trong đồ thị cấp phát tài nguyên. Chú ý rằng chúng ta kiểm tra tính an toàn bằng cách dùng giải thuật phát hiện chu trình. Một giải thuật để phát hiện một chu trình trong đồ thị này yêu cầu một thứ tự của n2 thao tác, ở đây n là số quá trình trong hệ thống.Nếu không có chu trình tồn tại, thì việc cấp phát tài nguyên sẽ để lại hệ thống trong trạng thái an toàn. Nếu chu trình được tìm thấy thì việc cấp phát sẽ đặt hệ thống trong trạng thái không an toàn. Do đó, tiến trình Pi sẽ phải chờ yêu cầu của nó được thoả. Để minh hoạ giải thuật này, chúng ta xét đồ thị cấp phát tài nguyên của hình dưới. Giả sử rằng P2 yêu cầu R2. Mặc dù R2 hiện rảnh nhưng chúng ta không thể cấp phát nó tới P2 vì hoạt động này sẽ tạo ra chu trình trong đồ thị bên cạnh. Một chu trình hiển thị rằng hệ thống ở trong trạng thái không an toàn. Nếu P1 yêu cầu R2 và P2 yêu cầu R1 thì deadlock sẽ xảy ra.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 137.5.3 Giải thuật của Banker Giải thuật đồ thị cấp phát tài nguyên không thể áp dụng tới hệ thống cấp phát tài nguyên với nhiều thể hiện của mỗi loại tài nguyên. Giải thuật tránh deadlock mà chúng ta mô tả tiếp theo có thể áp dụng tới một hệ thống nhưng ít hiệu quả hơn cơ chế đồ thị cấp phát tài nguyên. Giải thuật này thường được gọi là giải thuật của Banker. Tên được chọn vì giải thuật này có thể được dùng trong hệ thống ngân hàng để đảm bảo ngân hàng không bao giờ cấp phát tiền mặt đang có của nó khi nó không thể thoả mãn các yêu cầu của tất cả khách hàng. Khi một tiến trình mới đưa vào hệ thống, nó phải khai báo số tối đa các thể hiện của mỗi loại tài nguyên mà nó cần. Số này có thể không vượt quá tổng số tài nguyên trong hệ thống. Khi một người dùng yêu cầu tập hợp các tài nguyên, hệ thống phải xác định việc cấp phát của các tài nguyên này sẽ để lại hệ thống ở trạng thái an toàn hay không. Nếu trạng thái hệ thống sẽ là an toàn, tài nguyên sẽ được cấp; ngược lại tiến trình phải chờ cho tới khi một vài tiến trình giải phóng đủ tài nguyên. Nhiều cấu trúc dữ liệu phải được duy trì để cài đặt giải thuật Banker. Những cấu trúc dữ liệu này mã hoá trạng thái của hệ thống cấp phát tài nguyên. Gọi n là số tiến trình trong hệ thống và m là số loại tài nguyên trong hệ thống. Chúng ta cần các cấu trúc dữ liệu sau: • Available: một vector có chiều dài m hiển thị số lượng tài nguyên sẵn dùng của mỗi loại. Nếu Available[j] = k, có k thể hiện của loại tài nguyên Rj sẵn dùng. • Max: một ma trận n x m định nghĩa số lượng tối đa yêu cầu của mỗi tiến trình. Nếu Max[i,j] = k, thì tiến trình Pi có thể yêu cầu nhiều nhất k thể hiện của loại tài nguyên Rj. • Allocation: một ma trận n x m định nghĩa số lượng tài nguyên của mỗi loại hiện được cấp tới mỗi tiến trình. Nếu Allocation[i,j] = k, thì tiến trình Pi hiện được cấp k thể hiện của loại tài nguyên Rj. • Need: một ma trận n x m hiển thị yêu cầu tài nguyên còn lại của mỗi tiến trình. Nếu Need[i,j] = k, thì tiến trình Pi có thể cần thêm k thể hiện của loại tài nguyên Rj để hoàn thành tác vụ của nó. Chú ý rằng, Need[i,j] = Max[i,j] – Allocation [i,j]. Cấu trúc dữ liệu này biến đổi theo thời gian về kích thước và giá trị. Để đơn giản việc trình bày của giải thuật Banker, chúng ta thiết lập vài ký hiệu. Gọi X và Y là các vector có chiều dài n. Chúng ta nói rằng X ≤ Y nếu và chỉ nếu X[i] ≤ Y[i] cho tất cả i = 1, 2, …, n. Thí dụ, nếu X = (1, 7, 3, 2) và Y = (0, 3, 2, 1) thì Y ≤ X, Y < X nếu Y ≤ X và Y ≠ X. Chúng ta có thể xem xét mỗi dòng trong ma trận Allocation và Need như là những vectors và tham chiếu tới chúng như Allocationi và Needi tương ứng. Vector Allocationi xác định tài nguyên hiện được cấp phát tới tiến trình Pi; vector Needi xác định các tài nguyên bổ sung mà tiến trình Pi có thể vẫn yêu cầu để hoàn thành tác vụ của nó. 7.5.3.1 Giải thuật an toàn Giải thuật để xác định hệ thống ở trạng thái an toàn hay không có thể được mô tả như sau: 1. Gọi Work và Finish là các vector có chiều dài m và n tương ứng.Khởi tạo Work :=Available và Finish[i]:=false với i = 1, 2, …,n. 2. Tìm i thỏa: CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 14a) Finish[i] = false b) Need i ≤ Work. Nếu không có i nào thỏa, di chuyển tới bước 4 3. Work:=Work + Allocationi Finish[i] := true Quay trở lại bước 2. 4. Nếu Finish[i] = true cho tất cả i, thì hệ thống đang ở trạng thái an toàn. Giải thuật này yêu cầu độ phức tạp O(mxn2) thao tác để quyết định trạng thái là an toàn hay không. 7.5.3.2 Giải thuật yêu cầu tài nguyên Cho Requesti là vector yêu cầu cho tiến trình Pi. Nếu Requesti[j] = k, thì tiến trình Pi muốn k thể hiện của loại tài nguyên Rj. Khi một yêu cầu tài nguyên được thực hiện bởi tiến trình Pi, thì các hoạt động sau được thực hiện: 1. Nếu Requesti ≤ Needi, tới bước 2 Ngược lại, phát sinh một điều kiện lỗi vì tiến trình vượt quá yêu cầu tối đa của nó. 2. Nếu Requesti ≤ Available, tới bước 3. Ngược lại, Pi phải chờ vì tài nguyên không sẳn có. 3. Giả sử tiến trình Pi yêu cầu hệ thống cấp phát tài nguyên Requesti , thì: Available := Available – Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti; Nếu kết quả trạng thái cấp phát tài nguyên là an toàn, thì giao dịch được hoàn thành và tiến trình Pi được cấp phát tài nguyên của nó. Tuy nhiên, nếu trạng thái mới là không an toàn, thì Pi phải chờ Requesti và trạng thái cấp phát tài nguyên cũ được phục hồi.7.5.3.3 Thí dụ minh họa Xét một hệ thống với 5 tiến trình từ P0 tới P4, và 3 loại tài nguyên A, B, C. Loại tài nguyên A có 10 thể hiện, loại tài nguyên B có 5 thể hiện và loại tài nguyên C có 7 thể hiện. Giả sử rằng tại thời điểm T0 trạng thái hiện tại của hệ thống như sau: Allocation Request AvailableA B C A B C A B CP00 1 0 7 5 3 3 3 2P12 0 0 3 2 2P23 0 2 9 0 2P32 1 1 2 2 2P40 0 2 4 3 3Nội dung ma trận Need được định nghĩa là Max-Allocation và làCHƯƠNG 7.DEADLOCK| TinK31AP a g e | 15NeedA B CP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1Chúng ta khẳng định rằng hệ thống hiện ở trong trạng thái an toàn. Thật vậy, thứ tự <P1, P3, P4, P2, P0> thỏa tiêu chuẩn an toàn. Giả sử bây giờ P1 yêu cầu thêm một thể hiện loại A và hai thể hiện loại C, vì thế Request1 = (1, 0, 2). Để quyết định yêu cầu này có thể được cấp tức thì hay không, trước tiên chúng ta phải kiểm tra Request1 ≤ Available (nghĩa là, (1, 0, 2)) ≤ (3, 3, 2)) là đúng hay không. Sau đó, chúng ta giả sử yêu cầu này đạt được và chúng ta đi đến trạng thái mới sau:Allocation Request AvailableA B C A B C A B CP00 1 0 7 4 3 2 3 0P13 0 0 0 2 0P23 0 2 6 0 2P32 1 1 0 1 1P40 0 2 4 3 1Chúng ta phải xác định trạng thái mới này là an toàn hay không. Để thực hiện điều này, chúng ta thực thi giải thuật an toàn của chúng ta và tìm thứ tự <P1, P3, P4, P0, P2> thỏa yêu cầu an toàn. Do đó, chúng ta có thể cấp lập tức yêu cầu của tiến trình P1. Tuy nhiên, chúng ta cũng thấy rằng, khi hệ thống ở trong trạng thái này, một yêu cầu (3, 3, 0) bởi P4 không thể được gán vì các tài nguyên không sẳn dùng. Một yêu cầu cho (0, 2, 0) bởi P0 không thể được cấp mặc dù tài nguyên sẳn dùng vì trạng thái kết quả là không an toàn.7.6 Phát hiện deadlock.Nếu một hệ điều hành không sử dùng giải thuật ngăn chặn hay tránh Deadlock thì hiện tượng này có thể xảy ra. Trong môi trường này thì hệ điều hành phải chuẩn bị:• Giải thuật kiểm tra tình trạng của hệ thống để xác định có deadlock hay không.• Một giải thuật để phục hồi deadlock.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 16 7.6.1 Loại tài nguyên có một thể hiện. Nếu hầu hết các loại tài nguyên chỉ có một thể hiện thì ta có thể xác định được giải thuật để phát hiện deadlock như sử dụng một biến thể của dạng đồ thị cấp phát tài nguyên gọi là đồ thị chờ. Chúng ta có được các nguồn tài nguyên này từ các đồ thị cấp phát nguồn tài nguyên bằng cách loại bỏ các nút nguồn tài nguyên và xóa các cạnh thích hợp.Chính xác hơn, một cạnh từ Pi tới Pj trong đồ thị chờ hiển thị rằng tiến trình Pi chờ đợi tiến trình Pj để giải phóng tài nguyên mà Pi cần. Cạnh Pi→Pj tồn tại trong đồ thị chờ nếu và chỉ khi đồ thị cấp phát nguồn tài nguyên tương ứng chứa các cạnh Pi→Rq và Rq→Pi cho tài nguyên Rq.Ví dụ: trong hình trên, chúng ta có một biểu đồ phân bổ tài nguyên và đồ thị chờ tương ứng.Như trước đây, deadlock tồn tại trong hệ thống khi và chỉ khi đồ thị chờ chứa chu trình. Để phát hiện deadlock, hệ thống cần duy trì đồ thị chờ và định kì gọi giải thuật để tìm kiếm chu trình trong đồ thị. Để phát hiện một chu kì trong đồ thị đòi hỏi độ phức tạp O(n2) thao tác, trong đó n là số đỉnh của đồ thị.7.6.2 Loại tài nguyên nhiều thể hiện.Kế hoạch đồ thị chờ không áp dụng cho một hệ thống mà tài nguyên có nhiều thể hiện .Giả thuật phát hiện deadlock khác được áp dụng cho hệ thống. Giải thuật thực hiện nhiều cấu trúc dữ liệu khác nhau thay đổi theo thời gian mà chúng tương tự như sử dụng thuật toán Banker (mục 7.5.3).• Available: Một vector có chiều dài cho biết số lượng tài nguyên sẵn của từng loại.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 17• Allocation: Một ma trận m×n xác định số lượng các nguồn tài nguyên của mỗi loại hiện được cấp phát cho mỗi tiến trình.• Request: Một ma trận m×n chỉ ra các yêu cầu hiện tại của mỗi tiến trình. Nếu Request[i,j] = k ,thì tiến trình Pi đang yêu cầu k nhiều loại tài nguyên Rj.Các mối quan hệ giữa hai vector được định nghĩa trong phần 7.5.3. Để kí hiệu đơn giản hóa chúng ta trở lại coi các ma trận Allocation và Request như vector, chúng ta coi chúng như Allocationi và Requeati. Giải thuật được phát hiện ở đây đơn giản xem xét mọi thứ tự cấp phát có thể đối với các tiến trình còn lại để được hoàn tất. So sánh các thuật toán này với các thuật toán Banker của phần 7.5.3.1. Gọi Work và Finish là các vector có chiều dài m và n.Khởi tạo Work = Available.Duyệt i=0 ,1,…,n-1.Nếu Allocationi ≠ 0,thì Finish[i] = false. Nếu không, Finish[i] = true.2. Tìm một chỉ số i sao cho cả hai : a) Finish[i] = false b) Request ≤ Work. Nếu không có i nào thỏa mãn thì tới bước 4.3. Work := Work + Allocationi Finish[i] := true Di chuyển về bước 2.4. Nếu Finish[i] == false, đối với một số i,0 ≤ i ≤ n, thì hệ thống đang ở trạng thái deadlock. Ngoài ra, nếu Finish[i] = false thì tiến trình Pi bị deadlock.Giải thuật này đòi hỏi độ phức tạp O(m×n2) để phát hiện xem hệ thống có trong trạng thái deadlock hay không.Câu hỏi đặt ra là tại sao chúng ta lại trả lại tài nguyên của tiến trình Pi (trong bước 3) ngay sau khi chúng ta xác định rằng Requesti ≤ Work (trong bước 2b). Chúng ta biết rắng Pi hiện tại không liên quan đến deadlock (vì Request ≤ Work). Vì thế chúng ta lạc quan và khẳng định rằng Pi sẽ không yêu cầu thêm tài nguyên để hoàn thành công việc của nó; do đó nó sẽ trả về tất cả tài nguyên hiện được cấp phát tới hệ thống. Nếu như giả định là không chính xác, thì deadlock có thể xảy ra sau đó. Deadlock sẽ được phát hiện tại thời điểm kế tiếp mà giải thuật phát hiện deadlock được gọi.Để minh họa giải thuật này, chúng ta xét hệ thống với 5 tiến trình P0 đến P4 và 3 nguồn loại A, B, và C. Loại tài nguyên A có 7 thể hiện, nguồn tài nguyên loại B có 2 thể hiện, và nguồn tài nguyên C có 6 thể hiện. Giả sử tại thời điểm t0, chúng ta có các trạng thái cấp phát tài nguyên sau:Allocation Request AvailableA B C A B C A B CP00 1 0 0 0 0 0 0 0P12 0 0 2 0 2P23 0 3 0 0 0CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 18P32 1 1 1 0 0P40 0 2 0 0 2Hệ thống không ở trong trạng thái deadlock. Thật vậy chúng ta thực hiện một giả thuật, chúng ta sẽ tìm thấy thứ tự < P0,P2,P3,P1,P4> kết quả Finish[i] = true cho tất các i.Bây giờ giả sử rằng tiến trình P2 thực hiện yêu cầu thêm thể hiện tài nguyên C. Ma trận Request được sửa đổi như sau: RequestA B CP00 0 0P12 0 2P20 0 1P31 0 0P40 0 2Hệ thống lúc này đang deadlock. Mặc dù chúng ta có thể giành các nguồn tài nguyên được tổ chức bởi tiến trình Po, số lượng các nguồn tài nguyên có được không đủ để hoàn thành các yêu cầu của các tiến trình khác. Do đó deadlock tồn tại.7.6.3 Sử dụng giải thuật phát hiện deadlockKhi nào chúng ta cần giải thuật phát hiện deadlock? Câu trả lời phụ thuộc vào hai yếu tố:• Deadlock có khả năng xảy ra như thế nào?• Có bao nhiêu tiến trình sẽ bị ảnh hưởng bởi deadlock khi nó xảy ra ?Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện deadlock sẽ được thực hiện thường xuyên. Tài nguyên được cấp phát cho deadlock sẽ được rảnh rỗi cho đến khi deadlock bị phá vỡ. Ngoài ra, số lượng tiến trình tham gia vào trong chu trình deadlock có thể tăng lên.Deadlock xảy ra khi một tiến trình thực hiện yêu cầu mà không được cấp phát tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối cùng hoàn thành một chuỗi các tiến trình chờ. Trong trường hợp này chúng ta có thể gọi giải thuật phát hiện deadlock mỗi khi yêu cầu cấp phát không được cấp phát tức thì. Chúng ta không chỉ biết được tập hợp các tiến trình bị deadlock mà còn xác định tiến trình đã gây ra deadlock (Trong thực tế, mỗi tiến trình trong suốt quá trình bị deadlock là một liên kết trong chu trình của đồ thị tài nguyên vì thế tất cả chúng gây ra deadlock). Nếu có nhiều loại tài nguyên khác nhau, một yêu cầu tạo ra một chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi các yêu cầu gần đây nhất và “gây ra” bởi một tiến trình có thể xác định.Tất nhiên, nếu thuật toán phát hiện deadlock được gọi cho mọi yêu cầu tài nguyên điều này có thể gây ra chi phí lớn trong thời gian tính toán. Một phương pháp để giảm chi phí là ta gọi giải thuật trong thời điểm ít thường xuyên hơn - ví dụ mỗi giờ hoặc bất cứ khi nào CPU sử dụng dưới 40%. Nếu giải thuật phát hiện deadlock được gọi vào thời điểm bất kỳ, CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 19có thể có nhiều chu trình trong đồ thị tài nguyên. Chúng ta không thể xác định được tiến trình nào “gây ra” deadlock.7.7 Phục hồi deadlockKhi giải thuật phát hiện deadlock xác định tồn tại một deadlock, có 2 cách để giải quyết:• Một là thông báo cho người điều hành biết deadlock xảy ra và để cho người điều hành khắc phục bằng tay.• Hai là để cho hệ thống phục hồi tự động. Có hai tùy chọn để phá vỡ deadlock. Một giải pháp đơn giản là hủy một hay nhiều tiến trình để phá vỡ tồn tại chu trình trong đồ thị cấp phát tài nguyên. Lựa chọn thứ hai là lấy lại một hay nhiều tài nguyên từ tiến trình deadlock.7.7.1 Kết thúc tiến trình.Để loại bỏ deadlock bằng hủy bỏ tiến trình, chúng ta sử dụng một trong hai phương pháp. Cả hai phương pháp này có điểm chung là hệ thống lấy lại các nguồn tài nguyên từ các tiến trình bị kết thúc. • Hủy bỏ tất cả tiến trình bị deadlock: Phương pháp này sẽ phá vỡ chu kì deadlock, nhưng chi phí cao, các tiến trình deadlock có thể có tính toán trong thời gian dài, và kết quả tính toán từng phần này phải được loại bỏ và rất có thể phải tính lại sau đó.• Hủy bỏ một tiến trình ở thời điểm hiện tại 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, sau khi tiến trình bị hủy bỏ, giải thuật phát hiện deadlock được gọi xác định có còn tiến trình nào bị deadlock hay không.Hủy bỏ tiến trình có thể không dễ dàng. Nếu một tiến trình đang ở giai đoạn cập nhật tập tin, nếu kết thúc nó sẽ để tập tin trong trạng thái không phù hợp. Tương tự nếu dữ liệu đang ở 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 trước khi in công việc tiếp theo.Nếu như phương pháp hủy bỏ một phần được sử dụng, sau đó chúng ta phải xác định tiến trình tiếp theo bị deadlock. Việc xác định này là cả một quyết định tương tự như vấn đề lập lịch cho CPU. Câu hỏi mang tính chất kinh tế, chúng ta nên hủy bỏ tiến trình nào thì sự kết thúc của tiến trình có 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.Những yếu tố xác định đến tiến trình nào được chọn bao gồm:1. Mức độ ưu tiên của tiến trình. 2. Tiến trình đã thực hiện được bao lâu và còn bao lâu nữa thì hoàn thành?3. Tiến trình đang sử dụng bao nhiêu loại tài nguyên? 4. Tiến trình cần bao nhiêu tài nguyên nữa để hoàn thành? CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 205. Bao nhiêu tiến trình sẽ cần được kết thúc. 6. Tiến trình độc lập hay liên quan đến các tiến trình khác.7.7.2 Đòi Lại Tài Nguyên Để loại trừ deadlock chúng ta có thể sử dụng biện pháp đòi lại tài nguyên, tức là: chúng ta lần lược đòi lại một phần tài nguyên từ các tiến trình và đưa các tài nguyên này đến các tiến trình khác cho đến khi chu trình deadlocks bị phá bỏ.Nếu phương pháp này được yêu cầu để giải quyết deadlock thì có ba vấn đề cần được xác định : • Chọn đối tượng cần được tác động: Những tài nguyên và tiến trình nào bị đòi lại? Trong khi kết thúc tiến trình, chúng ta phải xác định trình tự đòi lại để chi phí là ít nhất. Yếu tố chi phí có thể bao gồm số lượng tài nguyên một tiến trình deadlock đang giữ và lượng thời gian mà tiến trình deadlock tiêu thụ trong khi thực thi nó.• Quay trở lại: Nếu chúng ta đòi lại tài nguyên từ một tiến trình, cái gì nên được kết thúc với tiến trình đó? Rõ ràng nó không thể tiếp tục việc thực thi bình thường của nó, nó đang làm mất một số tài nguyên cần thiết. Chúng ta phải quay tiến trình tới một số mức an toàn và khởi động lại nó từ mức đó. Từ trạng thái bị deadlock thông thường rất khó xác định mức an toàn là mức nào, cách đơn giản nhất là quay lại toàn bộ tức là: bỏ dở tiến trình và sau đó khởi động lại nó. Mặc dù nó có tác dụng hơn quay tiến trình lại đến mức cần thiết đủ để phá vỡ deadlocks nhưng phương pháp này yêu cầu hệ thống phải giữ nhiều thông tin về các mức của tất cả các tiến trình đang chạy.• Sự đói tài nguyên: Làm sao chúng ta đảm bảo sự đói tài nguyên sẽ không xảy ra? Tức là làm sao để chúng ta có thể đảm bảo tài nguyên đó sẽ luôn không bị đòi lại từ cùng một tiến trình?Trong một hệ thống, việc chọn “nạn nhân” chủ yếu dựa trên yếu tố chi phí, có thể có 1 tiến trình luôn được chọn là “nạn nhân”. Kết quả là tiến trình này không bao giờ hoàn thành công việc nó được chỉ định, cho nên trạng thái đói tài nguyên phải chắc chắn được giải quyết trong bất kỳ một hệ thống thiết thực nào. Rõ ràng chúng ta phải chắc chắn một tiến trình có thể được chọn như một nạn nhân chỉ với một số lần xác định(nhỏ). Giải pháp phổ biến nhất là bao gồm cả số lần quay lại trong yếu tố chi phí.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 217.8. TÓM TẮTDeadlock bắt nguồn từ sự xung đột về tài nguyên của 2 hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống.Các phương thức giải quyết deadlocks : • Sử dụng một vài giao thức để ngăn ngừa hoặc tránh xa deadlock, đảm bảo hệ thống đó sẽ không bao giờ có deadlock.• Cho phép hệ thống ở tình trạng deadlock, phát hiện và sau đó phục hồi lại.• Lờ đi vấn đề tất cả các vấn đề và giả vờ như deadlocks chưa bao giờ xảy ra trong hệ thống.Deadlocks chỉ có thể xảy ra nếu bốn điều kiện cần thiết đó cùng lúc trong hệ thống.Nếu một hệ thống không sử dụng một phương pháp để chắc chắn rằng deadlock sẽ không bao giờ xảy ra, thì phương pháp phát hiện và phục hồi sẽ được dùng đến. Nếu deadlock đã được ngăn chặn thì hệ thống phải phục hồi bằng cách chấm dứt một số quá trình bị deadlock hay là đòi lại tài nguyên từ những tiến trình đã bị deadlock.Để đòi lại tài nguyên hoặc tiến trình đã gây ra deadlocks, ba vấn đề cần phải xác định là: chọn nạn nhân, quay trở lại, và sự đói tài nguyênCHƯƠNG 7.DEADLOCK| TinK31AP a g e | 227.9 MỘT VÀI CÂU HỎI LUYỆN TẬP7.1 Ba ví dụ về deadlock không liên quan đến môi trường máy tính.Trả lời: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ên3. 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.7.2 Giả sử rằng hệ thống đang ở trong trạng thái không an toàn. Chỉ ra rằng có khả năng cho các tiến trình đang thực hiện có thể hoàn thành công việc mà không rơi vào trạng thái deadlock.Trả lời:Một trạng thái không an toàn không nhất thiết là có deadlock, nhưng chúng ta không thể đảm bảo rằng deadlock sẽ không xảy ra. Do đó có thể hệ thống trong trạng thái không an toàn nhưng các tiến trình vẫn hoàn thành mà không có deadlock xảy ra. Xét một hệ thống có 12 tài nguyên được phân bố cho các tiến trình P0, P1, và P2 theo như bảng sau:Max Current NeedP010 5 5P14 2 2P29 3 6for(int i=0;i<n; i++) {// đầu tiên tìm dòng có finish for(int j=0;j<n; j++) { if (!finish[j]) { boolean temp = true; for(int k=0;k<m; k++) { if (need[j][k] > work[k]) temp = false; } if (temp) { // if dòng này có finish finish[j] = true; for(int x=0;x<m; x++) work[x] += work[j][x];CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 23 } } }} Hình 7.1 Thuật toán an toàn của thuật toán BankerHiện có 2 tài nguyên sẵn có. Hệ thống đang ở trong trạng thái không an toàn vì vậy tiến trình P1 cần hoàn thành, sau đó giải phóng 4 tài nguyên. Nhưng chúng ta không thể đảm bảo rằng P0 và P2 có thể hoàn thành. Tuy nhiên, một tiến trình phải giải phóng những tài nguyên trước khi yêu cầu bất kì tài nguyên nào khác.Ví dụ, tiến trình P2 có thể giải phóng một tài nguyên, do đó tăng tổng số các tài nguyên sẵn có lên 5. Điều này cho phép tiến trình P0 hoàn thành, sau đó sẽ giải phóng 9 tài nguyên, điều này cho phép tiến trình P2 hoàn thành.7.3 Chứng minh rằng thuật toán an toàn trình bày trong mục 7.5.3 có độ phức tạp O( m x n2 )Trả lời:Hình 7.1 cung cấp mã Java cho thuật toán an toàn của thuật toán Banker. Có thể thấy rằng, ở ngoài có hai vòng lặp lồng nhau, cả hai đều lặp n lần nên được biểu diễn n2 lần. Phía trong hai vòng lặp là vòng lặp lặp m lần. Nên độ phức tạp của thuật toán này là O(m×n2). 7.4 Xem xét một hệ thống máy tính chạy 5000 việc mỗi tháng mà không có phương pháp phòng hoặc tránh deadlock. Deadlock xảy ra khoảng hai lần mỗi tháng, trong trường hợp này các nhà điều hành phải chấm dứt và chạy lại 10 công việc cho mỗi lần deadlock. Mỗi công việc có trị giá khoảng $2 và thường có xu hướng chấm dứt những công việc đã làm một nửa. Một chương trình đã ước tính rằng một thuật toán tránh deadlock có thể được cài trong hệ thống với thời gian thực hiện mỗi công việc có thể tăng trung bình khoảng 10%, máy tính hiện có khoảng 30% thời gian nhàn rỗi, tất cả 5000 công việc đều có thể chạy được, mặc dù thời gian quay vòng cho mỗi tháng sẽ tăng trung bình khoảng 20%.a. Lí do để cài đặt thuật toán tránh deadlock?b. Các căn cứ chống lại việc cài đặt thuật toán tránh deadlock? Trả lời:Một lí do để cài đặt thuật toán tránh deadlock là chúng ta có thể đảm bảo không bao giờ xảy ra deadlock. Mặc dù tăng thời gian quay vòng nhưng tất cả 5000 công việc vẫn có thể chạy. Một luận cứ chống lại việc cài đặt phần mềm tránh deadlock là deadlock xảy ra không thường xuyên và chi phí.7.5 Hệ thống có thể phát hiện một số tiến trình “đang đói” hay không? Nếu trả lời là “Có”, thì làm thế nào để phát hiện. Nếu trả lời là “Không” thì có thể giải thích hệ thống làm thế nào để giải quyết khi tình trạng “đói” xảy ra.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 24Trả lời:“Đói” là vấn đề khó xác định. Nó có thể được xác định khác nhau trong các hệ điều hành khác nhau. Với mục đích câu hỏi này, chúng ta có thể xác định tình trạng đói là tình trạng mà một tiến trình phải chờ ngoài khoảng thời gian hợp lí có lẽ phải chờ khi yêu cầu một tài nguyên, nó có thể dẫn tới là chờ vô hạn. Một cách để phát hiện tiến trình “đói” là đầu tiên xác định một khoảng thời gian T - được coi là thời gian quá giới hạn. Khi mà tiến trình yêu cầu tài nguyên, thời gian được bắt đầu tính, nếu thời gian trôi qua vượt quá T, tiến trình được coi là đói.Một trong những phương pháp để phát hiện tiến trình “đang đói” là xác định tiến trình có thời gian chờ đợi tài nguyên là dài nhất.Ví dụ như tiến trình Pa đã chờ đợi tài nguyên X lâu hơn tiến trình Pb, nên các yêu cầu tài nguyên của tiến trình Pb sẽ được đáp ứng sau yêu cầu tài nguyên của tiến trình Pa được đáp ứng.Có một phương pháp ít được nghiêm ngặt hơn so với phương pháp đề cập trên. Trong phương pháp này thì tài nguyên được cấp phát cho tiến trình ít chờ đợi hơn, miễn là các tiến trình khác không bị đói. Tuy nhiên, một số tiến trình khác được coi là đói, nếu như yêu cầu của nó được đáp ứng trước.7.6 Xem xét sự phân bố tài nguyên: Yêu cầu và đáp ứng tài nguyên được cho phép bất kì lúc nào, nếu mà tài nguyên không có sẵn thì yêu cầu tài nguyên không được đáp ứng. Chúng ta sẽ kiểm tra một số tiến trình đang bị khóa hay chờ tài nguyên. Nếu có yêu cầu thêm tài nguyên, thì chúng sẽ bị thu hồi tài nguyên và đưa đến cho tiến trình đang yêu cầu. Các tiến trình đang chờ yêu cầu thêm tài nguyên sẽ được đáp ứng.Ví dụ : Hệ điều hành có ba loại tài nguyên và vecto Available là (4,2,2). Nếu tiến trình P0 yêu cầu (2,2,1) và được đáp ứng. Nếu tiến trình P1 yêu cầu (1,0,1) và được đáp ứng. Tiếp theo P0 yêu cầu (0,0,1) nó bị khóa (tài nguyên C không có sẵn). Nếu P0 yêu cầu ngay (2,0,0) mà có sẵn (1,0,0) thì 1 đó được phân cho P0, vecto Allocation giảm xuống (1,2,1) và vecto Need là (1,0,1).a. Deadlock có thể xảy ra không? Nếu bạn trả lời “Có”, hãy đưa ra ví dụ. Nếu trả lời là “Không”, xác định những điều kiện để không xảy ra deadlock.b. Có thể ngăn chặn sự chờ đợi vô hạn xảy ra? Giải thích.Trả lời:a. Deadlock không thể xảy ra bởi vì điều kiện “quyền ưu tiên” không tồn tại. b. Có. Một tiến trình có thể không bao giờ giành được tất cả các tài nguyên mà nó cần nếu như nó liên tiếp được ưu tiên bởi một loạt các yêu cầu.7.7 Giả sử bạn đă có giải thuật phòng tránh deadlock, bây giờ yêu cầu thi hành giải thuật phát hiện deadlock. Theo bạn, có thể sử dụng giải thuật an toàn và định nghĩa lại Maxi = Waitingi + Allocationi, trong đó vector Waitingi chỉ rõ tài nguyên đang đợi của tiến trình i, và Allocationi như đã được định nghĩa trong phần 7.5 không? Giải thích.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 25Trả lời : Được. Vector Max mô tả yêu cầu tối đa một tiến trình có thể cần. Khi tính toán giải thuật an toàn chúng ta sử dụng ma trận Need, nó được mô tả Need = Max - Allocation. Theo như câu hỏi, ma trận Waiting có vai trò giống như ma trận Need, do đó Max = Waiting + Allocation.7.8 Có phải hiện tượng deadlock chỉ xảy ra đối với hệ thống đơn tiến trình không? Giải thích.Trả lời : Không. Vì điều kiện tiếp theo là điều kiện giữ và chờ tài nguyên, nên hệ thống đa tiến trình nếu xảy ra điều kiện này vẫn có thể bị deadlock.CHƯƠNG 7.DEADLOCK| TinK31AP a g e | 26MỤC LỤC7.1. KHÁI NIỆM: 37.2. ĐIỀU KIỆN HÌNH THÀNH DEADLOCK: 4 7.2.1 Đồ thị cấp phát tài nguyên: 47.3. CÁC PHƯƠNG PHÁP XỬ LÝ DEADLOCK: 77.4. NGĂN CHẶN DEADLOCK 7 7.4.1. Độc quyền sử dụng: 7 7.4.2. Giữ và chờ cấp thêm tài nguyên: 8 7.4.3. Không đòi lại tài nguyên từ quá trình đang giữ nó. 8 7.4.4 Tồn tại chu trình trong đồ thị cấp phát tài nguyên 97.5 TRÁNH DEADLOCK 10 7.5.1 Trạng thái an toàn: 10 7.5.2 Giải thuật cấp phát tài nguyên: 12 7.5.3 Giải thuật của Banker 137.5.3.1 Giải thuật an toàn 137.5.3.2 Giải thuật yêu cầu tài nguyên 147.5.3.3 Thí dụ minh họa 147.6 PHÁT HIỆN DEADLOCK 15 7.6.1 Loại tài nguyên có một thể hiện 16 7.6.2 Loại tài nguyên nhiều thể hiện 16 7.6.3 Sử dụng giải thuật phát hiện deadlock 187.7 PHỤC HỒI DEADLOCK 197.7.1 Kết thúc tiến trình 197.7.2 Đòi Lại Tài Nguyên 207.8. TÓM TẮT 217.9 MỘT VÀI CÂU HỎI LUYỆN TẬP 22 7.1 Ba ví dụ về deadlock không liên quan đến môi trường máy tính 22 7.2 Giả sử rằng hệ thống đang ở trong trạng thái không an toàn. Chỉ ra rằng có khả năng cho các tiến trình đang thực hiện có thể hoàn thành công việc mà không rơi vào trạng thái deadlock. 227.3 Chứng minh rằng thuật toán an toàn trình bày trong mục 7.5.3 có độ phức tạp O( m x n2 ). 23CHƯƠNG 7.DEADLOCK| TinK31A