Chương 6: Deadlock – Khóa cứng

6.1 Mở đầu

Trong hệ thống đa chương trình, một process nằm trong trạng thái deadlock hay treo, nếu như nó chờ sự kiện (event) nào đó không bao giờ xảy ra. Tình huống treo hệ thống là tình huống có một hay nhiều process nằm trong trạng thái treo.

Trong các hệ thống đa chương trình một trong những chức năng quan trọng của HĐH là quản lý, phân chia tài nguyên. Khi tài nguyên được chia sẻ giữa các user, mỗi người có toàn quyền điều khiển, sử dụng tài nguyên đ• được phân chia cho anh ta, do đó hoàn toàn có thể xảy ra deadlock và process của người dùng có thể chẳng bao giờ kết thúc.

Trong chương này chúng ta xem xét vấn đề deadlock và một số kết quả nghiên cứuvề vấn đề ngăn ngừa, phòng tránh và phát hiện tình trạng deadlock cũng như khôi phục sau đó. Chúng ta cũng xem xét vấn đề liên quan là chờ vô tận (indefinite postponement- ho•n không xác định) khi process chờ một sự kiện nào đó có thể chẳng bao giờ xảy ra do lý do chủ quan nào đó trong hệ thống điều khiển tài nguyên.

Các khả năng, giải pháp cân bằng giữa giá phải trả cho các phương tiện ngăn chặn deadlock với lợi ích nó mang lại cũng được xem xét. Trong nhiều trường hợp, giá phải trả cho việc loại trừ tình trạng deadlock quá cao. Còn trong các trường hợp khác (ví dụ các hệ thống điều khiển thời gian thực) thì giá đó là không tránh khỏi vì deadlock có thể gây ra những hậu quả không lường trước.

6.2 Ví dụ tình trạng deadlock

Có lẽ cách đơn giản nhất để tạo deadlock là chương trình mà Holt đưa ra bằng ngôn ngữ PL/1, chạy dưới OS 360:

Revenge: procedure options (main, task);

                wait (event)

end revenge;

process gắn với chương trình này sẽ luôn chờ sự kiện event nhưng nó lại không xem xét dấu hiệu xuất hiện event. Hệ thống bắt buộc nhận thấy process đó bị treo và sau đó phải loại bỏ process để thoát khỏi tình trạng deadlock.

Deadlock do lỗi chương trình hay thuật toán thường khó phát hiện

6.2.1 Ví dụ trong thực tế

tắc nghẽn giao thông:

6.2.2 Ví dụ deadlock trong phân chia tài nguyên

Trong HĐH, deadlock phần lớn xuất hiện do hậu quả của sự tranh chấp sử dụng (chiếm) các tài nguyên mà tại mỗi thời điểm chỉ cấp cho một user, do đó đôi khi được gọi là tài nguyên sử dụng tuần tự. Trên hình 6.2 đưa ra một ví dụ đơn giản deadlock dạng này. Trên sơ đồ phân chia tài nguyên có hai process và hai tài nguyên. Mũi tên đi ra từ tài nguyên vào process chỉ ra rằng tài nguyên đó đang thuộc quyền sử dụng của process đó. Còn mũi tên đi ra từ process vào tài nguyên chỉ ra rằng process đang yêu cầu sử dụng tài nguyên nhưng chưa được cấp phát tài nguyên tương ứng.

Sơ đồ này biểu diễn hệ thống đang ở trong tình trạng deadlock: processA đang chiếm resource1 và để tiếp tục hoạt động nó cần resource2. Trong khi đó processB đang chiếm resource2 lại cần resource1 để tiếp tục.

Mỗi process đợi để process kia giải phóng resource mà nó đang cần, mặt khác mỗi process không giải phóng resource khi mà process kia chưa giải phóng tài nguyên của mình. Tình huống đợi vòng quanh này đưa hệ thống vào tình trạng deadlock.

6.2.3 Deadlock trong hệ thống dùng spooling

Hệ thống spooling thường xảy ra deadlock. Chế độ spooling (vào/ra với buffer) được áp dụng để nâng cao hiệu suất của hệ thống bằng cách phân cách chương trình khỏi các liên lạc trực tiếp với thiết bị ngoại vi tốc độ thấp như máy in, ... Nếu như chương trình đưa một dòng text ra máy in mà phải đợi đến khi in xong dòng đó mới tiếp tục in dòng tiếp theo thì chương trình hoạt động chậm đi nhiều do hạn chế tốc độ của máy in. Để tăng tốc độ thực hiện chương trình, đầu tiên các dòng dữ liệu được ghi ra các thiết bị có tốc độ cao hơn như đĩa cứng và được lưu tạm thời ở đó trước khi được đưa ra máy in. Trong một số hệ thống spooling, chương trình phải định dạng (format) toàn bộ thông tin ra, chỉ sau đó mới bắt đầu thực sự in. Do đó khi một vài process đưa dữ liệu vào spooling file để in, hệ thống có thể rơi vào tình trạng deadlock, nếu như buffer định trước bị đầy khi chưa hoàn tất công việc. Để khôi phục, hay thoát khỏi tình trạng đó có thể phải restart system- dẫn đến mất toàn bộ kết quả công việc đ• tiến hành, hoặc phải loại bỏ một số chương trình để các chương trình còn lại có thể hoạt động tiếp tục.

Khi người điều hành bắt đầu công việc anh ta thiết lập kích thước cho spooling file. Một trong những cách làm giảm khả năng xuất hiện deadlock khi spooling là thiết lập kích thước ban đầu lớn hơn so với dự tính. Nhưng cách này không phải luôn thực hiện được (khả thi) khi bộ nhớ thiếu,... Giải pháp thông dụng hơn đối với process thiết lập ngưỡng để spooling không tiếp nhận thêm công việc từ các chương trình khác khi spooling file đ• sử dụng ví dụ tới 75% không gian. Giải pháp này có thể dẫn tới giảm hiệu suất của hệ thống nhưng đó là giá phải trả để giảm xác suất xảy ra deadlock.

Các hệ thống ngày nay hoàn thiện hơn, nó có thể  cho phép bắt đầu in trước khi kết tất cả dữ liệu được định dạng nhờ đó một phần hay toàn bộ spooling file được giải phóng (xoá) ngay trong quá trình thực hiện công việc. Trong nhiều hệ thống có khả năng cấp phát bộ đệm (buffer) động để khi spooling file sắp đầy thì nó được tăng kích thước.

Dù sao đi nữa ưu thế của spooling vẫn lớn hơn rất nhiều những vấn đề deadlock có thể nảy sinh.

6.3 Vấn đề chờ vô tận-ho•n không xác định (indefinite postponement)

Trong hệ thống, khi các process phải chờ ví dụ khi nó chờ được cấp phát tài nguyên hay lập lịch trình, có thể xuất hiện tình huống mà (quyền) được sử dụng BXL bị ho•n không xác định. Tình huống này gọi là ho•n vô thời hạn (không xác định) có thể dẫn tới tình huống không chấp nhận được cũng như tình trạng deadlock.

Tình trạng ho•n vô thời hạn có thể xảy ra do cách điều khiển tài nguyên của hệ thống. Khi tài nguyên được phân bố theo nguyên tắc ưu tiên thì có thể xảy ra trường hợp một process sẽ chờ được cấp tài nguyên lâu vô hạn, bởi vì luôn có các process khác với độ ưu tiên cao hơn.

Khi thiết kế HĐH cần xem xét các chiến lược điều khiển các process nằm trong trạng thái chờ. Trong nhiều hệ thống tình trạng ho•n vô hạn được ngăn chặn do độ ưu tiên của process tăng dần cùng với thời gian nó chờ được cấp tài nguyên. Do đó cuối cùng thì process đó có độ ưu tiên cao nhất và nó sẽ được phục vụ.

6.4 Khái niệm tài nguyên - resource

Một chức năng quan trọng của HĐH là quản lý và điều khiển các tài nguyên của hệ thống. Nó có trách nhiệm phân phối các tài nguyên thuộc các loại khác nhau của hệ thống. Chúng ta xem xét các tài nguyên được coi là preemtible (được xử dụng nhiều nhất)  như là BXL hay bộ nhớ; Chương trình đang nằm trong bộ nhớ có thể bị đưa ra ngoài để cấp vùng nhớ đó cho các chương trình khác cần bộ nhớ, ví dụ như khi chương trình thực hiện yêu cầu vào/ra nói chung nó không sử dụng bộ nhớ trong suốt khoảng thời gian thực hiện thao tác vào/ra. Nói chung, trong hệ thống, tài nguyên được sử dụng nhiều nhất (năng động nhất) là BXL, BXL luôn phải phục vụ các process song song, chuyển từ process này sang process khác để tất cả process đều được tiếp tục với tốc độ chấp nhận được. Nếu một process không sử dụng hợp lý BXL ví dụ khi đang thực hiện thao tác I/O, quyền sử dụng BXL của process này cần tạn thời ngăn cấm, trao cho các process khác. Do đó, việc tổ chức phân chia tài nguyên động là chỉ tiêu rất quan trọng để đảm bảo hoạt động hiệu quả của các hệ thống đa chương trình.

Các dạng tài nguyên xác định là "không phân chia" với ý nghĩa là chúng không thể tuỳ ý lấy lại từ process mà chúng được cấp. Ví dụ như băng từ, thông thường được cấp cho một process trong khoảng thời gian dài. Thiết bị kiểu này không thể đơn giản lấy lại từ process đó để cấp cho process khác.

Có những loại tài nguyên khác cho phép chia sẻ giữa một vài process, còn có những loại chỉ do một process độc quyền sử dụng. Ví dụ ổ đĩa thường chứa các file thuộc nhiều process nhưng đôi khi do một process chiếm giữ. Bộ nhớ và BXL được sử dụng chia sẻ bởi nhiều process.

Dữ liệu và chương trình cũng là các tài nguyên và chúng cũng cần các cơ cấu điều khiển, cấp phát tương ứng. Ví dụ trong một hệ, nhiều user có thể cùng cần chạy một chương trình. Bởi vì nếu mỗi user có một bản copy của chương trình trong bộ nhớ thì không tiết kiệm, do đó có thể chỉ nạp một bản copy của chương trình vào bộ nhớ còn mỗi user sẽ có một vùng dữ liệu riêng.

Code của chương trình mà không được thay đổi trong thời gian chạy gọi là reentrant (hay có thể chạy nhiều lần đồng thời) còn code của chương trình có thể thay đổi trong thời gian chạy gọi là code sử dụng nối tiếp (serial reusable). Với reentrant code - có thể có một số process cùng làm việc còn với code nối tiếp chỉ một process làm việc với nó tại một thời điểm. Khi nói về một tài nguyên nào đó, chúng ta cần hình dung xem chúng có thể được sử dụng bởi nhiều process đồng thời hay bởi nhiều process nhưng chỉ một process tại mỗi thời điểm. Chính loại tài nguyên thứ hai thường gây ra deadlock.

6.5 Bốn điều kiện xuất hiện deadlock

Coffman, Elphick và Sheshani đ• phát biểu 4 điều kiện xuất hiện deadlock:

Các process yêu cầu quyền độc quyền sử dụng tài nguyên sẽ cấp phát cho nó (điều kiện loại trừ nhau).

Process giữ cho mình các tài nguyên đ• được cấp và đồng thời yêu cầu tài nguyên bổ sung (điều kiện chờ tài nguyên)

Tài nguyên không được lấy lại từ process khi các tài nguyên đó chưa được sử dụng để kết thúc công việc (điều kiện không phân chia)

Tồn tại vòng kín các process, trong đó mỗi process giữ tài nguyên mà process kế tiếp đang đòi hỏi (điều kiện chờ vòng).

6.6 Các hướng nghiên cứu cơ bản về vấn đề deadlock

Vấn đề deadlock là một trong các vấn đề được nghiên cứu nhiều trong lĩnh vực công nghệ thông tin, các thành tựu trong lĩnh vực đó cho phép đề ra các thuật toán giải quyết nhiều bài toán. Các nghiên cứu có thể chia ra làm 4 hướng chính sau:

Ngăn chặn deadlock

Tránh deadlock

Phát hiện deadlock

Khôi phục sau deadlock

Hướng thứ nhất có mục đích tìm những điều kiện để loại trừ khả năng xuất hiện tình trạng deadlock. Hướng này là giải pháp trực diện đối với vấn đề deadlock, nhưng nó thường dẫn tới việc sử dụng tài nguyên không hiệu quả. Nhưng dù sao các phương pháp ngăn chặn deadlock được áp dụng khá phổ biến.

Mục đích của các biện pháp tránh deadlock là ở chỗ cho phép những điều kiện ít nghiêm ngặt hơn so với các biện pháp ngăn chặn deadlock, và cũng đảm bảo sử dụng tài nguyên tốt hơn. Các biện pháp tránh deadlock không đòi hỏi loại bỏ hoàn toàn để không xảy ra tình trạng dealock trong hệ thống. Ngược lại nó chú ý các khả năng xuất hiện deadlock, trong trường hợp xác suất xuất hiện dealock tăng lên thì áp dụng các biện pháp tránh xảy ra deadlock.

Các phương pháp phát hiện deadlock áp dụng trong các hệ thống có khả năng xuất hiện deadlock do hậu quả của các thao tác vô ý hay cố ý. Mục đích của các biện pháp phát hiện là xác định sự tồn tại tình trạng deadlock trong hệ thống, xác định các process và tài nguyên nằm trong tình trạng deadlock. Sau đó có thể áp dụng các biện pháp thích hợp để khắc phục.

Các biện pháp khôi phục sau deadlock áp dụng khi loại bỏ tình trạng deadlock để hệ thống có thể tiếp tục hoạt động, còn các process rơi vào tình trạng deadlock có thể phải kết thúc và các tài nguyên của nó được giải phóng. Sau đó các process đó thường được nạp và bắt đầu từ đầu (các công việc đ• thực hiện đến lúc xảy ra deadlock sẽ bị mất).

6.7 Ngăn chặn deadlock

Đến nay các nhà thiết kế khi giải quyết các vấn đề deadlock thường đi theo hướng loại trừ những tình huống deadlock hay xảy ra nhất. Chúng ta sẽ xem xét các phương pháp ngăn chặn deadlock và đánh giá hậu quả của nó đối với user cũng như với hệ thống đặc biệt là về mặt hiệu quả công việc và tính năng sử dụng.

Havender đ• chỉ ra rằng khả năng xuất hiện deadlock không thể có ngay cả khi tồn tại một trong bốn điều kiện xuất hiện dealock. Havender đề ra các chiến lược sau:

Mỗi process phải yêu cầu tất cả các tài nguyên nó cần ngay một lần, và không thể bắt đầu cho đến khi chưa có đủ các tài nguyên đó.

Nếu process đang có các tài nguyên nào đso, bị từ chối cấp phát tài nguyên mới (bổ sung) thì nó phải giải phóng các tài nguyên ban đầu (đ• có) và trong trường hợp cần thiết phải yêu cầu cấp lại  cùng với các tài nguyên bổ sung.

Đưa vào các tài nguyên tuyến tính đối với tất cả process, tức là nếu process được cấp tài nguyên loại nào đó (phân loại theo thứ tự) thì sau đó nó chỉ có thể yêu cầu các tài nguyên loại có bậc lớn hơn.

Chúng ta thấy rằng chỉ có ba chiến lược (chứ không phải bốn)

Mỗi nguyên tắc có mục đích loại trừ (phá vỡ) một trong các điều kiện tồn tại của deadlock. Điều kiện đầu tiên (điều kiện loại trừ nhau), theo đó process có độc quyền điều khiển tài nguyên được cấp cho nó, chúng ta không muốn loại trừ bởi vì chúng ta cần cho phép khả năng làm việc với tài nguyên đơn.

6.7.1 Loại bỏ điều kiện “chờ tài nguyên bổ sung”

Nguyên tắc thứ nhất của Havender đòi hỏi process phải yêu cầu tất cả (toàn bộ) tài nguyên mà nó cần ngay từ đầu. Hệ thống phải cấp các tài nguyên này theo nguyên tắc "có tất cả hoặc không có gì". Nếu tập hợp các tài nguyên có đủ thì hệ thống có thể cấp tất cả để cho process có thể tiếp tục công việc. Nếu lúc đó không có đủ tài nguyên thì process phải chờ đến khi các tài nguyên có đủ (nhờ được các process khác giải phóng). Bởi vì process nằm trong trạng thái chờ không được giữ tài nguyên nào, do đó ngăn chặn được sự xuất hiện điều kiện "chờ tài nguyên bổ sung" và tình huống deadlock không thể xảy ra.

Kết quả đó được trả giá bởi việc sử dụng tài nguyên không hiệu quả. Ví dụ, chương trình vào lúc nào đó cần 10 thiết bị băng từ, bắt buộc phải yêu cầu và có được đủ cả 10 thiết bị trước khi có thể bắt đầu. Nếu như 10 thiết bị đó cần suốt trong thời gian hoạt động thì không có vấn đề gì về hiệu suất sử dụng. Nhưng nói chung thì không phải tất cả chúng đều được sử dụng trong cả quá trình tồn tại của process mà chúng chỉ cần trong những khoảng thời gian nào đó, như thế các thiết bị được sử dụng với hiệu suất rất thấp, không thể chấp nhận.

Một trong những cách để nâng cao hiệu suất là phân chia chương trình thành một vài giai đoạn tương đối độc lập với nhau. Do đó có thể thực hiện việc cấp phát tài nguyên cho từng giai đoạn chương trình thay vì cấp một lần cho cả chương trình. Điều này cho phép giảm việc l•ng phí tài nguyên nhưng lại tăng chi phí khi thiết kế và cả khi thực hiện chương trình.

Chiến lược này làm tăng khả năng process phải chờ vô hạn (không xác định) bởi vì không phải tất cả tài nguyên cần thiết đều có vào lúc process cần. Như thế hệ thống phải thực hiện (đén khi kết thúc) số lượng khá lớn bài toán khác và giải phóng tài nguyên cấp cho chúng để bài toán đang chờ có thể hoạt động. Vào khoảng thời gian các tài nguyên cần có được thu thập thì chúng không thể cấp cho các task khác, tức là lúc đó chúng không hoạt động. Từ khía cạnh kinh tế thì các chi phí đó cần phải tính. Có nhiều ý kiến khác nhau về việc ai phải trả chi phí đó. Có người cho rằng vì khi đó các tài nguyên được thu thập cho người sử dụng nên người dùng phải trả tiền cả cho thời gian chúng dừng. Còn những người khác cho rằng điều đó không hợp lý vì lúc đó người dùng không thực sự sử dụng tài nguyên. Nếu người dùng muốn thực hiện chương trình vào giờ cao điểm thì anh ta sẽ phải trả nhiều hơn đáng kể so với trường hợp thực hiện vào thời gian khác.

6.7.2 Loại bỏ điều kiện “không phân bố lại”

Tiêu chuẩn thứ hai của Havender (xem xét độc lập) , ngăn chặn việc xuất hiện điều kiện "không phân bố lại". Giả sử rằng hệ thống cho phép các process yêu cầu thêm các tài nguyên bổ sung và vẫn giữ những tài nguyên đ• được cấp. Nếu như hệ thống có đủ tài nguyên trống để phân phối thì không có tình trạng deadlock. Nhưng nếu yêu cầu không được giải quyết thì có thể có tình huống một process chiếm giữ tài nguyên mà process khác yêu cầu để tiếp tục hoạt động, còn process thứ hai đó lại chiếm giữ tài nguyên mà process đầu cần tức là xuất hiện deadlock.

Nguyên tắc Havender thứ hai đòi hỏi rằng nếu một process không được cấp phát tài nguyên bổ sung khi nó yêu cầu thì nó phải giải phóng tất cả tài nguyên nó đang chiếm giữ, và trong trường hợp cần thiết phải yêu cầu lại tất cả cùng với tài nguyên bổ sung.

Nguyên tắc này thật sự loại trừ được yếu tố "không phân bố lại" và có thể lấy được tài nguyên từ các process đang chiếm chúng trước khi các process hoàn thành.

Nguyên tắc này cũng có nhiều nhược điểm. Nếu như process trong quá trình làm việc sử dụng các tài nguyên mà sau đó giải phóng chúng thì nó có thể mất các kết quả làm việc đến lúc đó. Giá đó có vẻ quá lớn, tuy nhiên nó còn phụ thuộc vào tần số (xác suất) xảy ra. Nếu tình huống đó ít xảy ra thì có thể nói rằng tiêu chuẩn này không phải là quá đắt. Còn nếu như thường xuyên xảy ra thì giá của nó là quá đắt, đặc biệt với các process có mức ưu tiên cao hay khẩn cấp.

Một trong những nhược điểm lớn của biện pháp này là xác suất xảy ra 'chặn vô hạn' (indefinite posponement). Sự thực hiện process mà nhiều lần phải yêu cầu rồi giải phóng cùng một tài nguyên có thể bị dừng một thời hạn không xác định. Trong trường hợp đó hệ thống có thể phải loại process đó để các process khác có thể tiếp tục. Cũng không thể không tính khả năng khi process bị chặn vô hạn nhưng hệ thống không nhận ra, tình huống này làm l•ng phí tài nguyên và giảm hiệu suất của cả hệ thống.

6.7.3 Loại trừ điều kiện “chờ vòng quanh”

Nguyên tắc thứ ba của Havender loại trừ sự xuất hiện tình trạng chờ vòng. Vì tất cả các tài nguyên được gán một số duy nhất và các process phải yêu cầu các tài nguyên với số tăng dần do đó không thể xuất hiện tình trạng 'chờ vòng quanh'. Nguyên tắc này được thực hiện trong nhiều HĐH nhưng nó cũng gây ra các khó khăn nhất định:

Vì các tài nguyên được yêu cầu (cấp phát) theo thứ tự tăng dần và các số gán cho tài nguyên  được gán từ đầu do đó trong trường hợp đưa thêm vào hệ thống các tài nguyên loại mới có thể gây ra tình huống phải thiết kế lại chương trình và cả hệ thống.

Rõ ràng rằng việc gán số cho tài nguyên cần thể hiện thứ tự thông thường mà phần lớn các task sử dụng tài nguyên. Đối với các task thực hiện theo thứ tự đó thì các tài nguyên có thể được sử dụng có hiệu quả. Còn nếu như task lại yêu cầu tài nguyên theo thứ tự ngược lại thì nó sẽ chiếm giữ tài nguyên lâu hơn cần thiết (tính đến lúc tài nguyên thực sự được dùng) .

Bởi vì chức năng quan trọng của HĐH là cho phép người dùng sử dụng thuận tiện nhất. Người dùng phải có khả năng thiết kế chương trình với ít thứ không cần thiết nhất do sự hạn chế từ phía  máy tính và HĐH. Nguyên tắc thứ ba của Havender ngăn chặn được tình trạng 'chờ vòng' nhưng lại ảnh hưởng xấu đến công việc của user trong quá trình làm việc (lập trình).

6.8 Ngăn chặn deadlock và thuật toán Banker

Ngay cả khi tồn tại các điều kiện xuất hiện deadlock thì vẫn có thể tránh tình trạng đó nếu như tài nguyên được cấp phát theo những qui tắc nhất định. Có lẽ thuật toán thông dụng nhất để tránh tình trạng deadlock là thuật toán banker do Dijstra đề xuất.

6.8.1 Thuật toán banker của Dijstra

Khi xem xét thuật toán banker chúng ta sẽ xem xét các tài nguyên chúng ta sẽ giới hạn xét các tài nguyên cùng một loại, nhưng thuật toán này có thể dễ dàng thay đổi để áp dụng cho các tài nguyên nhiều loại khác nhau.

Chúng ta xem trường hợp ví dụ như phân chia t thiết bị lưu trữ băng từ.

HĐH  phải đảm bảo phân chia một số t thiết bị cho mốt số cố định u người sử dụng. Mỗi người dùng sẽ phải báo trước số thiết bị lớn nhất mà anh ta sẽ cần khi thực hiện bài toán. HĐH sẽ chấp nhận yêu cầu của người dùng nếu yêu cầu cao nhất đó không vượt quá số thiết bị t.

Người dùng có thể chiếm hay giải phóng từng thiết bị một. Có thể rằng anh ta sẽ phải chờ được cấp tài nguyên nhưng HĐH đảm bảo rằng sự chờ đợi đó không phải là vô hạn. Số thiết bị cấp cho người dùng tại một thời điểm không bao giờ vượt quá số thiết bị nhiều nhất anh ta cần đến. Nếu HĐH có đủ số thiết bị thoả m•n yêu cầu lớn nhất của người dùng, thì người sử dụng đảm bảo rằng các thiết bị đó sẽ được sử dụng và trả lại cho HĐH sau khoảng thời gian hữu hạn nào đó.

Trạng thái hiện thời của máy tính gọi là ổn định nếu HĐH có thể đảm bảo tất cả các chương trình ứng dụng hiện thời trong hệ thống có thể hoàn thành (kết thúc bình thường) sau một khoảng thời gian hữu hạn nào đó. Còn trong trường hợp ngược lại thì trạng thái là không ổn định.

Giả sử rằng có n người sử dụng

Giả sử l(i) là số thiết bị cấp cho người sử dụng thứ i. Ví dụ người dùng thứ 5 đang dùng 4 thiết bị thì l(5)=4.

Giả sử m(i) là số thiết bị lớn nhất mà người dùng thứ i có thể cần ví dụ người dùng thứ 5 cần nhiều nhất 6 thiết bị thì m(5)=6. Tại một thời điểm, c(i) là yêu cầu lớn nhất hiện thời của người dùng i- bằng hiệu giữa số thiết bị nhiều nhất có thể yêu cầu và số thiết bị hiện có, tức là c(i)=m(i)-l(i) ví dụ ở trên ta có c(5)= m(5)-l(5) = 6-4=2

Trong hệ thống với t thiết bị thì số thiết bị còn rỗi tại một thời điểm là a sẽ bằng t trừ tổng các thiết bị được cấp phát: a = t - l(i)

Thuật toán banker của Dijkstra yêu cầu rằng các thiết bị chỉ được cấp phát cho người dùng theo yêu cầu trong trường hợp sau khi cấp phát thì hệ thống vẫn ở trạng thái ổn định. Trạng thái ổn định là trạng thái mà với các tài nguyên đang có,  tất cả ứng dụng của người dùng có khả năng kết thúc (bình thường) công việc của mình. Còn trạng thái không ổn định là trạng thái có thể dẫn tới deadlock.

6.8.2 Ví dụ về trạng thái ổn định

Giả sử hệ thống có 12 thiết bị, và chúng được phân chia giữa 3 người dùng với trạng thái status1 được biểu diễn trong bảng sau:

Trạng thái status1

    Số thiết bị đang được cấp    Số thiết bị lớn nhất có thể cần

Người dùng 1    1    4

Người dùng 2    4    6

Người dùng 3    5    8

Dự trữ còn lại    2

Trạng thái đó là ổn định vì cả 3 người dùng có khả năng kết thúc công việc.

6.8.3 Ví dụ về trạng thái không ổn định

Giả sử hệ thống cũng có 12 thiết bị, và chúng được phân chia giữa 3 người dùng với trạng thái status2 được biểu diễn trong bảng sau:

Trạng thái status2

    Số thiết bị đang được cấp    Số thiết bị lớn nhất có thể cần

Người dùng 1    8    10

Người dùng 2    2    5

Người dùng 3    1    3

Dự trữ còn lại    1

Trong trường hợp này 11 thiết bị trong trạng thái được cấp phát và chỉ còn 1 thiết bị dự trữ. Trạng thái này không ổn định vì bất cứ người dùng nào yêu cầu thêm một thiết bị và hệ thống đáp ứng thì chúng ta không thể đảm bảo các chương trình đều kết thúc bình thường.

Chúng ta cần chú ý rằng thuật ngữ 'trạng thái không ổn định' không có nghĩa là vào lúc đó hoặc thời điểm nào đó 'nhất định' sẽ xuất hiện tình trạng deadlock, mà nó chỉ nói rằng trong trường hợp xấu, hệ thống 'có thể' rơi vào tình trạng deadlock.

6.8.4 Ví dụ chuyển từ trạng thái ổn định sang không ổn định.

Nếu như trạng thái hiện thời của hệ thống là ổn định thì điều đó không có nghĩa là tất cả các trạng thái sau đó đều là ổn định. Cơ chế cấp phát cần phải phân tích các yêu cầu trước khi cấp phát tài nguyên.

Giả sử  hệ thống đang ở trạng thái 3, rõ ràng trạng thái đó là ổn định. Người dùng thứ 3 yêu cầu tài nguyên bổ sung. Nếu như thoả m•n yêu cầu đó thì hệ thống chuyển sang trạng thái 4. Dễ thấy trạng thái 4 là trạng thái không ổn định.

Trạng thái 3

    Số thiết bị đang được cấp    Số thiết bị lớn nhất có thể cần

Người dùng 1    1    4

Người dùng 2    4    6

Người dùng 3    5    8

Dự trữ còn lại    2

Trạng thái 4

    Số thiết bị đang được cấp    Số thiết bị lớn nhất có thể cần

Người dùng 1    1    4

Người dùng 2    4    6

Người dùng 3    6    8

Dự trữ còn lại    1

Tất nhiên trạng thái 4 không nhất thiết dẫn tới tình trạng deadlock. Tuy nhiên hệ thống đ• chuyển từ trạng thái 3 (ổn định) sang trạng thái 4 (không ổn định)

6.8.5 Phân phối tài nguyên theo thuật toán banker

Chúng ta sẽ xem xét sự phân phối tài nguyên theo Dijkstra được thực hiện thế nào. Các điều kiện 'loại trừ nhau', 'chờ tài nguyên bổ sung' và 'không phân chia lại' có thể xảy ra. Các process có thể được độc quyền sử dụng các tài nguyên cấp cho nó. Các process được quyền yêu cầu và chờ tài nguyên bổ sung trong khi vẫn giữ các tài nguyên đ• được cấp, ngoài ra tài nguyên không bị lấy khỏi process. Người dùng không đặt ra cho hệ thống bài toán quá phức tạp khi tại mỗi thời điểm chỉ yêu cầu một tài nguyên. Hệ thống hoặc thoả m•n hoặc từ chối yêu cầu. Nếu yêu cầu bị từ chối thì user vẫn giữ các tài nguyên đ• được cấp và chờ trong một khoảng thời gian (hữu hạn) nào đó đến khi được cấp.

Hệ thống chỉ thoả m•n các yêu cầu mà sau đó trạng thái của hệ thống vẫn ổn định. Còn các yêu cầu có thể dẫn hệ thống tới trạng thái không ổn định thì bị ho•n một khoảng thời gian nào đó và cuối cùng vẫn sẽ được thoả m•n. Bởi thế, hệ thống luôn ở trạng thái ổn định, do đó tất cả các yêu cầu sẽ được thoả m•n và tất cả user có thể kết thúc công việc.

6.8.6 Những nhược điểm của thuật toán banker

Thuật toán banker có nhiều ưu điểm bởi vì nó cho phép cấp phát tài nguyên, tránh tình trạng deadlock. Nó cho phép tiếp tục thực hiện các process mà trong trường hợp dùng các biện pháp ngăn chặn thì chúng đ• bị dừng. Nhưng thuật toán banker cũng vẫn có những nhược điểm mà do đó các nhà thiết kế hệ thống có thể phải lựa chọn các cách khác nhau để giải quyết vấn đề deadlock.

1/ Thuật toán banker xuất phát từ giả thiết số tài nguyên là cố định. Nhưng bởi vì các tài nguyên không thể làm việc m•i (ví dụ dừng lại để bảo dưỡng) do đó chúng ta không thể cho rằng số lượng tài nguyên là cố định.

2/ Thuật toán đòi hỏi rằng số người dùng là không đổi. Yêu cầu đó cũng không thực tế, vì trong các hệ đa chương trình, số lượng người dùng luôn thay đổi

3/ Thuật toán đòi hỏi bộ phận phân phối tài nguyên phải đảm bảo thoả m•n tất cả các yêu cầu sau khoảng thời gian hữu hạn nào đó. Tuy nhiên trong thực tế người ta cần những con số cụ thể hơn nhiều.

4/ Cũng như thế, thuật toán đòi hỏi người dùng phải trả lại các tài nguyên được cấp, sau một khoảng thời gian nào đó- và trong thực tế cũng cần các chỉ số cụ thể.

5/ Thuật toán yêu cầu người dùng phải báo trước số lượng lớn nhất tài nguyên anh ta cần. Nhưng sự phân phối tài nguyên ngày càng phải linh động, và do đó càng khó đánh giá yêu cầu lớn nhất. Vì máy tính ngày càng thân thiện với người dùng nên sẽ ngày càng nhiều người dùng không có hình dung chính xác về số tài nguyên lớn nhất mà anh ta sẽ cần, thay vào đó khi nào cần tài nguyên người dùng mới yêu cầu.

6.9 Phát hiện deadlock

Phát hiện deadlock- là xác định sự kiện xuất hiện trạng thái deadlock, xác định các quá trình và tài nguyên nằm trong tình trạng deadlock. Các thuật toán xác định deadlock thường được áp dụng trong các hệ thống có xuất hiện ba điều kiện đầu tiên trong số các điều kiện làm xuất hiện deadlock. Và sau đó mới xác định xem có tồn tại trạng thái 'chờ vòng' hay không.

Tất nhiên sử dụng các thuật toán phát hiện deadlock cũng phải trả giá, đó là chi phí về thời gian máy. Và chúng ta lại gặp vấn đề phải xác định giải pháp trung hoà: các chi phí thực hiện thuật toán phát hiện deadlock có tiết kiệm hơn hẳn so với khi dùng các biện pháp cô lập, loại bỏ deadlock hay không.

6.9.1 Graph phân bố tài nguyên

Trong các thuật toán phát hiện deadlock, thường áp dụng cách biểu diễn phân bố tài nguyên dưới dạng đồ thị có hướng. Các hình vuông biểu diễn process, còn các hình tròn lớn biểu diễn các lớp tài nguyên. Các vòng tròn nhỏ biểu diễn số lượng tài nguyên của lớp đó.

Ví dụ trong vòng tròn lớn R1 có 3 vòng nhỏ tức là hệ thống có 3 tài nguyên thuộc lớp R1

Trên h.6.3 biểu diễn các quan hệ trên đồ thị giữa các process và tài nguyên. Trong hình 6.3(a) - process P1 đang yêu cầu tài nguyên lớp R1. Mũi tên từ P1 đến vòng tròn lớn có nghĩa rằng hiện thời yêu cầu của process đang được xem xét. Hình 6.3 (b) thể hiện rằng process P2 được cấp 1 tài nguyên lớp R2, ở đây mũi tên đi từ vòng tròn nhỏ nằm trong vòng tròn lớn R2 đến process P2.

Trên hình.6.3 (c) biểu diễn tình huống ở một ý nghĩa nào đó gần với tình trạng deadlock:  process P3 yêu câu tài nguyên lớp R3 đang được cấp cho process P4

Hình 6.3(d) biểu diễn tình trạng deadlock: process P5 yêu cầu tài nguyên lớp R4, trong khi tất cả tài nguyên lớp đó được cấp cho process p6, và ngược lại process P6 yêu cầu tài nguyên lớp R5- đang được cấp cho P5- tình trạng chờ vòng này là tình trạng deadlock hay gặp.

Đồ thị phân bố và yêu cầu cấp phát tài nguyên luôn thay đổi do quá trình các process yêu cầu tài nguyên, nhận tài nguyên và sau đó trả lại cho HĐH.

6.9.2 Sử dụng đồ thị phân bố tài nguyên

Cơ chế phát hiện deadlock- xác định xem có xuất hiện tình trạng deadlock hay không. Một trong những phương pháp phát hiện là rút gọn đồ thị phân bố tài nguyên (reduction of a resource allocation graph), nó cho phép xác định các process có thể kết thúc và các process có mặt trong tình huống deadlock.

Nếu như yêu cầu tài nguyên của một process nào đó có thể thoả m•n thì chúng ta nói rằng graph có thể rút gọn đối với process đó. Sự rút gọn đó tương đương với sự biểu diễn graph dưới dạng mà nó có khi process kết thúc công việc và trả lại các tài nguyên cho hệ thống. Sự rút gọn graph đối với một process nào đó được thể hiện bằng việc ngắt bỏ các cung đi tới proces đó từ các tài nguyên  (tức là tài nguyên đ• được cấp cho process) và các cung từ process đến tài nguyên (tức là các yêu cầu cấp phát hiện thời của process). Nếu như graph có thể rút gọn thành tất cả process cô lập có nghĩa là không có tình trạng deadlock, còn nếu không thể làm được thì các process không rút gọn được là các process nằm trong trạng thái deadlock.

Trên hình 6.4 là d•y thao tác rút gọn graph, kết quả cho ta thấy đối với trường hợp này thì không xuất hiện trạng thái deadlock. Chúng ta cần để ý rằng thứ tự thực hiện thao tác là không quan trọng. Dù ta rút gọn theo thứ tự nào thì kết quả cuối cùng vẫn là một.

Hình 6.4

6.10 Khôi phục sau deadlock

Hệ thống nằm trong trạng thái deadlock cân thoát ra khỏi tình trnạg đó bằng cách loại bỏ các điều kiện tồn tại deadlock. Thông thường thì một số process sẽ mất một phần hay toàn bộ kết quả đ• thực hiện được. Nhưng giá của nó nhỏ hơn nhiều khi hệ thống bị treo hoàn toàn. Mức độ phức tạp của việc khôi phục hệ thống phụ thuộc nhiều yếu tố:

Ngay từ đầu việc xác định tình trạng deadlock không phải luôn rõ ràng

Trong nhiều hệ thống không có các công cụ đủ hiệu quả để dừng process một thời hạn không xác định, đưa nó ra khỏi hệ thống và lại khởi động nó sau đó. Trong thực tế thì có một số process phải làm việc liên tục không cho phép dừng lại và khởi động.

Ngay cả khi hệ thống có các công cụ hữu hiệu để dừng/khởi động process thì việc sử dụng chúng cũng đòi hỏi chi phí đáng kể về thời gian máy,...

Khôi phục tình trạng deadlock ở quy mô nhỏ (có ít process nằm trong tình trạng đó) thường đòi hỏi ít công sức  nhưng khi có nhiều process nằm trong tình trạng deadlock thì có thể đòi hỏi một chi phí lớn.

Trong các hệ thống hiện nay việc khôi phục thường được thực hiện bằng cách loại một số process để có thể sử dụng các tài nguyên của chúng. Kết quả của các process bị huỷ thường bị mất nhưng nhờ đó các process còn lại có thể tiếp tục, kết thúc công việc của mình. Thuật ngữ 'khôi phục' cũng không chính xác lắm, ý nghĩa của nó là khôi phục khả năng làm việc bình thường của hệ thống.

Việc lựa chọn process để loại ra khỏi hệ thống cần phải theo một chỉ tiêu nào đó, ví dụ mức độ ưu tiên của process. Nhưng cũng có một số khó khăn.

Process nằm trong tình trạng deadlock có thể không còn giá trị priority

Priority của proces có thể không đúng do nguyên nhân nào đó ví dụ priority của process có thể tăng lên theo thời gian nó phải chờ.

Có lẽ phương pháp khôi phục tốt nhất là cơ chế tạm dừng/khởi động process (suspend/activate). Cơ chế này cho phép chúng ta chuyển process vào trạng thái chờ, sau đó nó sẽ được khởi động, các kết quả làm việc vẫn giữ nguyên không bị mất.

Deadlock có thể dẫn tới những hậu quả lớn trong các hệ thống thời gian thực. Các hệ thống đó phải hoạt động liên tục do đó không cho phép xảy ra tình trạng  deadlock. Nhưng không thể đảm bảo tuyệt đối là nó không xảy ra – đó vẫn là một vấn đề cần giải quyết.