Một trưởng nhóm sắp có cuộc họp gấp nhất trong ngày đang chờ chìa khóa phòng họp. Nhưng nhân viên mới giữ chìa khóa lại liên tục bị các đồng nghiệp đàn anh gọi đi làm việc vặt nên mãi không trả phòng. Tình huống kỳ lạ khi việc quan trọng nhất lại được xử lý sau cùng này cũng xảy ra y hệt bên trong máy tính, và được gọi là ‘đảo ngược ưu tiên (Priority Inversion)’.
Nói đơn giản, đảo ngược ưu tiên có nghĩa là ‘hiện tượng một tác vụ có mức ưu tiên cao, vì phải chờ tài nguyên dùng chung mà tác vụ ưu tiên thấp đang giữ, nên trên thực tế bị đẩy xuống mức ưu tiên còn thấp hơn’. Đây là vấn đề được biết đến từ lâu trong các hệ thống thời gian thực, nơi nhiều tác vụ chia sẻ bộ xử lý theo mức ưu tiên định sẵn, và trở nên nổi tiếng vào năm 1997 khi tàu thăm dò Mars Pathfinder liên tục khởi động lại trên sao Hỏa.
Trong bài viết này, chúng ta sẽ lần lượt tìm hiểu đảo ngược ưu tiên xảy ra như thế nào, nguyên lý hoạt động qua ba tác vụ, sự cố Pathfinder thực sự đã diễn ra trên sao Hỏa, và cuối cùng là các cách ngăn chặn cùng bài học rút ra.
Khi mức ưu tiên cao phải chờ mức ưu tiên thấp
1. Đảo ngược ưu tiên xảy ra như thế nào?

Trong lập lịch theo mức ưu tiên, bộ xử lý luôn được giao trước cho tác vụ có mức ưu tiên cao nhất trong số các tác vụ sẵn sàng chạy. Quy tắc đơn giản này bắt đầu lung lay khi nhiều tác vụ cùng dùng một tài nguyên.
(1) Tài nguyên dùng chung và khóa
Nếu nhiều tác vụ cùng lúc sửa một vùng bộ nhớ hay một thiết bị, dữ liệu sẽ bị rối. Vì vậy hệ điều hành dùng các loại khóa như mutex để mỗi lúc chỉ một tác vụ được dùng tài nguyên. Tác vụ nào giành được khóa trước sẽ độc chiếm tài nguyên, bất kể mức ưu tiên, cho đến khi làm xong việc và nhả khóa.
(2) Tác vụ cao phải chờ
Nếu tác vụ ưu tiên cao yêu cầu cùng tài nguyên trong lúc tác vụ ưu tiên thấp đang giữ khóa, tác vụ cao phải dừng lại cho đến khi khóa được nhả. Vì khóa sẽ sớm được nhả khi tác vụ thấp làm xong đoạn găng ngắn ngủi, nên kiểu chờ này là ‘đảo ngược có giới hạn’, có thể tính trước được.
(3) Tác vụ trung bình chen ngang
Rắc rối thật sự xuất hiện khi trong lúc đó có một tác vụ ưu tiên trung bình, không liên quan gì đến khóa, thức dậy. Tác vụ trung bình có mức ưu tiên cao hơn tác vụ thấp nên chiếm lấy bộ xử lý, còn tác vụ thấp phải dừng lại trong khi vẫn giữ khóa. Kết quả là tác vụ cao phải chờ đến khi tác vụ trung bình, vốn có mức ưu tiên thấp hơn mình, chạy xong; nếu có nhiều tác vụ trung bình, thời gian chờ có thể kéo dài không biết đến bao giờ.
2. Nguyên lý hoạt động qua ba tác vụ

Đảo ngược ưu tiên thường được giải thích bằng ba tác vụ: cao, trung bình và thấp. Nếu chỉ nhìn vào mức ưu tiên thì tác vụ cao phải xong đầu tiên, nhưng chỉ cần một chiếc khóa xen vào là thứ tự thực thi thật sự bị đảo ngược.

- Lập lịch theo mức ưu tiên (Priority Scheduling): cách gán mức ưu tiên cho từng tác vụ và xử lý trước tác vụ có mức ưu tiên cao nhất trong số các tác vụ sẵn sàng. Khi tác vụ cao thức dậy, nó dừng tác vụ thấp và tiếp quản bộ xử lý.
- Mutex: viết tắt của loại trừ lẫn nhau (Mutual Exclusion), là khóa cho phép mỗi lúc chỉ một tác vụ dùng tài nguyên dùng chung.
- Đoạn găng (Critical Section): đoạn mã thao tác trên tài nguyên dùng chung trong khi giữ khóa. Đoạn này càng ngắn, thời gian các tác vụ khác phải chờ càng ít.
- Đảo ngược có giới hạn và không giới hạn (Bounded and Unbounded Inversion): nếu tác vụ cao chỉ phải chờ bằng thời gian đoạn găng của tác vụ thấp thì đó là đảo ngược có giới hạn; nếu các tác vụ trung bình cũng chen vào khiến không thể đặt giới hạn trên cho thời gian chờ thì đó là đảo ngược không giới hạn.
Trong hệ thống thời gian thực, đáng sợ là đảo ngược không giới hạn, vì không còn cách nào biết khi nào một tác vụ bắt buộc phải xong trong thời gian quy định mới thật sự xong. Điều khiến vấn đề này khó phát hiện là bề ngoài mọi tác vụ đều tuân thủ mức ưu tiên đúng quy tắc, nhưng kết quả tổng thể lại giống như mức ưu tiên đã bị đảo ngược.
3. Sự cố Pathfinder trên sao Hỏa

Sự kiện khiến đảo ngược ưu tiên được biết đến rộng rãi nhất đã xảy ra trên sao Hỏa. Tàu Mars Pathfinder của Cơ quan Hàng không và Vũ trụ Hoa Kỳ (NASA), hạ cánh xuống sao Hỏa ngày 4 tháng 7 năm 1997, bắt đầu gặp sự cố toàn bộ hệ thống đột ngột khởi động lại chỉ vài ngày sau khi hạ cánh.
(1) Liên tục khởi động lại
Máy tính của Pathfinder chạy hệ điều hành thời gian thực VxWorks của Wind River Systems. Sự cố xuất hiện vào khoảng thời gian tàu bắt đầu thu thập dữ liệu thời tiết. Mỗi lần khởi động lại, công việc dự định trong ngày bị dời sang hôm sau, nên đội vận hành trên Trái Đất phải nhanh chóng tìm ra nguyên nhân.
(2) Nguyên nhân được tái hiện trên Trái Đất
Nhóm của Phòng thí nghiệm Sức đẩy Phản lực (JPL) cho chạy cùng tình huống trên thiết bị thử nghiệm ở Trái Đất với chức năng ghi vết được bật, và chưa đầy 18 giờ đã làm lại được lỗi khởi động lại. Nguyên nhân là một ca đảo ngược ưu tiên điển hình như trong sách giáo khoa. Trong lúc tác vụ dữ liệu thời tiết có mức ưu tiên thấp giữ khóa, các tác vụ ưu tiên trung bình được chạy, còn tác vụ quản lý bus thông tin có mức ưu tiên cao đang chờ chiếc khóa đó không thể hoàn thành trong chu kỳ quy định. Một tác vụ quản lý cấp trên phát hiện điều này, coi đó là lỗi nghiêm trọng và kích hoạt khởi động lại.
(3) Sửa từ xa chỉ bằng một biến toàn cục
Chiếc khóa gây sự cố được tạo với thiết lập mặc định, trong đó chức năng kế thừa ưu tiên bị tắt vì lý do hiệu năng. Nhóm đã gửi lên tàu trên sao Hỏa một bản vá thay đổi giá trị của một biến toàn cục để bật chức năng này, và vấn đề được giải quyết. Câu chuyện trở nên nổi tiếng sau khi được trình bày tại một hội nghị về hệ thống thời gian thực vào tháng 12 cùng năm, và trưởng nhóm phần mềm bay Glenn Reeves cũng đã tự mình giải thích diễn biến sự việc.
4. Cách ngăn chặn đảo ngược ưu tiên

Chừng nào còn dùng khóa thì rất khó loại bỏ hoàn toàn đảo ngược ưu tiên, nhưng có thể ngăn thời gian chờ kéo dài vô tận. Các giải pháp tiêu biểu được trình bày trong bài báo năm 1990 về các giao thức kế thừa ưu tiên (Priority Inheritance Protocols) của Lui Sha, Ragunathan Rajkumar và John Lehoczky.
(1) Kế thừa ưu tiên
Khi tác vụ cao bắt đầu chờ khóa, tác vụ thấp đang giữ khóa được tạm nâng lên cùng mức ưu tiên với tác vụ cao. Khi đó tác vụ trung bình không thể chen vào, tác vụ thấp nhanh chóng làm xong đoạn găng và trở về mức ưu tiên ban đầu ngay khi nhả khóa. Đây chính là phương pháp đã cứu Pathfinder.
(2) Giao thức trần ưu tiên
Đây là cách đặt sẵn cho mỗi khóa một ‘mức trần’, tức mức ưu tiên cao nhất trong số các tác vụ có thể dùng khóa đó. Phương pháp được đề xuất trong cùng bài báo này giúp tính trước được thời gian chờ tối đa, đồng thời ngăn bế tắc, tình trạng các khóa mắc vào nhau khiến mọi thứ dừng lại.
(3) Bài học trong thiết kế
Việc rút ngắn các đoạn giữ khóa và thiết kế sao cho những tác vụ có mức ưu tiên chênh lệch lớn không dùng chung một tài nguyên cũng rất quan trọng. Ngày nay nhiều hệ điều hành thời gian thực và cả Linux đều cung cấp loại khóa hỗ trợ kế thừa ưu tiên. Trường hợp Pathfinder còn cho thấy việc kiểm tra một thiết lập mặc định và giữ lại chức năng ghi vết có thể tái hiện lỗi quan trọng đến mức nào.
Ý tưởng đơn giản ‘đẩy giúp tác vụ chậm đang chặn việc gấp một chút để nó xong trước’, đó chính là bước đầu tiên để hiểu đảo ngược ưu tiên.