Hãy hình dung hai chiếc ô tô đi vào từ hai đầu của một cây cầu hẹp chỉ có một làn và chạm mặt nhau ngay giữa cầu. Nếu cả hai tài xế đều đứng yên chờ người kia lùi lại trước, hai chiếc xe sẽ mãi mãi không qua được cầu. Khó mà nói đó là lỗi của ai, nhưng một tình huống không ai tiến lên được đã hình thành.
Điều y hệt như vậy cũng xảy ra bên trong máy tính, và nó được gọi là “bế tắc (Deadlock)”. Nói đơn giản, bế tắc là trạng thái nhiều chương trình cùng chờ tài nguyên mà chương trình khác đang giữ, nên không chương trình nào tiếp tục công việc được và tất cả đều dừng lại. Không ít trường hợp máy tính chẳng hề hỏng mà bỗng nhiên như bị treo chính là do bế tắc này.
Trong bài viết này, chúng ta sẽ lần lượt tìm hiểu bế tắc xuất hiện ra sao, bốn điều kiện làm phát sinh bế tắc là gì, một ví dụ nổi tiếng dùng để giải thích nó, và cả những cách máy tính xử lý bế tắc.
Những chiếc máy tính dừng lại vì chờ nhau
Bế tắc hình thành như thế nào
Bên trong máy tính, nhiều chương trình chạy cùng lúc và dùng chung các tài nguyên như máy in, tệp và bộ nhớ.
(1) Tài nguyên chỉ dùng được từng cái một
Có những tài nguyên mà nếu nhiều chương trình dùng cùng lúc thì nội dung sẽ bị xáo trộn, nên khi một chương trình đang dùng, các chương trình khác phải chờ. Cơ chế cho phép một chương trình tạm thời chiếm giữ riêng tài nguyên như vậy được gọi là khóa (Lock).
(2) Sự dừng lại do thứ tự chéo nhau
Ví dụ, chương trình thứ nhất khóa tệp A trong khi chờ tệp B, còn chương trình thứ hai khóa tệp B trong khi chờ tệp A. Vì cả hai đều không buông thứ mình đang giữ mà chỉ chờ thứ của bên kia, cả hai sẽ mãi mãi đứng im.
(3) Biểu hiện bên ngoài
Chương trình rơi vào bế tắc không hề báo lỗi mà chỉ đơn giản là không phản hồi. Ở những nơi xử lý rất nhiều yêu cầu cùng lúc như mạng máy tính ngân hàng hay hệ thống đặt chỗ, sự dừng lại như vậy có thể dẫn đến hậu quả nghiêm trọng.
Bốn điều kiện làm phát sinh bế tắc
Năm 1971, nhà khoa học máy tính Edward G. Coffman Jr. đã tổng kết rằng để bế tắc xảy ra, bốn điều kiện sau phải cùng lúc được thỏa mãn. Chúng được gọi là các điều kiện Coffman theo tên ông.
- Loại trừ lẫn nhau (Mutual Exclusion): Mỗi lần chỉ một chương trình được dùng tài nguyên.
- Giữ và chờ (Hold and Wait): Chương trình đã giữ một tài nguyên nhưng vẫn chờ thêm tài nguyên khác.
- Không thể chiếm đoạt (No Preemption): Không thể cưỡng ép lấy tài nguyên mà bên khác đang giữ; chỉ bên đang giữ mới tự nhả ra được.
- Chờ vòng tròn (Circular Wait): Số 1 chờ số 2, số 2 chờ số 3, số 3 lại chờ số 1, khiến sự chờ đợi nối với nhau thành một vòng.
(1) Chỉ cần cắt một mắt xích là gỡ được
Chỉ cần thiếu một trong bốn điều kiện, bế tắc sẽ không xảy ra. Vì vậy, phần lớn các cách ngăn bế tắc đều bắt đầu từ việc cắt đứt một trong bốn mắt xích này.
Bài toán bữa tối của các triết gia
Câu chuyện thường được dùng nhất để giải thích bế tắc là “bài toán bữa tối của các triết gia (Dining Philosophers Problem)”, bắt nguồn từ một bài toán do nhà khoa học máy tính người Hà Lan Edsger W. Dijkstra đưa ra.
(1) Tình huống của bài toán
Năm triết gia ngồi quanh một chiếc bàn tròn, giữa mỗi hai người có đặt một chiếc nĩa, tổng cộng năm chiếc. Triết gia suy nghĩ, rồi khi đói thì phải cầm được cả hai chiếc nĩa ở hai bên mới có thể ăn.
(2) Khoảnh khắc tất cả đều đói
Nếu cả năm người cùng lúc cầm chiếc nĩa bên trái, tất cả sẽ phải chờ chiếc nĩa bên phải. Vì không ai đặt chiếc nĩa bên trái xuống, cuối cùng cả năm người đều không ăn được mà chỉ ngồi chờ. Đây là một ca bế tắc điển hình khi cả bốn điều kiện đều được thỏa mãn.
(3) Cách giải đơn giản
Nếu đánh số cho từng chiếc nĩa và quy định ai cũng phải cầm chiếc nĩa có số nhỏ hơn trước, vòng chờ đợi sẽ không hình thành. Điều này cho thấy rõ chỉ cần đặt ra một thứ tự là đủ để phá vỡ sự chờ vòng tròn.
Cách máy tính xử lý bế tắc
Hệ điều hành và cơ sở dữ liệu lựa chọn nhiều cách khác nhau tùy theo tình huống.
(1) Phòng ngừa
Quy định sẵn thứ tự sử dụng tài nguyên, hoặc buộc chương trình yêu cầu toàn bộ tài nguyên cần thiết ngay từ đầu, để một trong bốn điều kiện hoàn toàn không thể xảy ra.
(2) Tránh né
Trước khi cấp tài nguyên, hệ thống tính trước xem nếu đáp ứng yêu cầu này thì sau đó có thể xảy ra bế tắc hay không. Thuật toán chủ ngân hàng (Banker’s Algorithm) do Dijkstra nghĩ ra là phương pháp tiêu biểu, giống như ngân hàng khi cho vay sẽ cân nhắc xem mình có đáp ứng được nhu cầu của mọi khách hàng đến cùng hay không.
(3) Phát hiện và gỡ bỏ
Tạm thời cho phép bế tắc xảy ra, theo dõi xem ai đang chờ ai, và nếu phát hiện một vòng thì dừng một chương trình hoặc cho nó chạy lại từ đầu để gỡ nút thắt. Nhiều cơ sở dữ liệu dùng cách này.
(4) Làm ngơ
Nếu bế tắc rất hiếm khi xảy ra và thiệt hại nhỏ, hệ thống cũng có thể chọn không ngăn chặn mà khi xảy ra thì khởi động lại. Được ví với con đà điểu vùi đầu vào cát, cách này được gọi là thuật toán đà điểu (Ostrich Algorithm).
Bế tắc không phải do một ai đó làm sai, mà là vấn đề nảy sinh khi tất cả đều nắm chặt phần của mình và chỉ chờ người khác. Vì thế, lời giải cũng bắt đầu từ việc đặt ra thứ tự, và đôi khi là buông thứ mình đang giữ trước.
Hiểu rằng chỉ cần buông một trong những bàn tay đang níu giữ nhau là con đường sẽ mở ra, đó chính là bước đầu tiên của sự khôn ngoan giúp một hệ thống đang đứng im chuyển động trở lại.
