Đảo ngược độ ưu tiên (Priority Inversion)

1. Tổng quan

A. Định nghĩa

Đảo ngược độ ưu tiên (Priority Inversion) là hiện tượng trong lập lịch thời gian thực, tác vụ có độ ưu tiên cao lại bị thực thi muộn hơn vì phải chờ tài nguyên dùng chung đang bị tác vụ có độ ưu tiên thấp chiếm giữ. Thứ tự ưu tiên trên thực tế bị đảo ngược, công việc ưu tiên thấp vượt lên trước công việc ưu tiên cao.

Lý do đảo ngược độ ưu tiên nguy hiểm nằm ở chỗ “việc gấp nhất bị việc vặt vãnh nhất níu chân”. Hệ thống thời gian thực (RTOS) được thiết kế để gán độ ưu tiên cao cho các tác vụ gấp phải tuân thủ thời hạn (deadline), và bộ lập lịch luôn thực thi trước tác vụ có độ ưu tiên cao nhất trong số các tác vụ sẵn sàng (ready). Chừng nào quy tắc này được tuân thủ, thời gian đáp ứng có thể dự đoán được. Tuy nhiên, ngay khi nhiều tác vụ cùng dùng một tài nguyên chung (ví dụ: bộ đệm toàn cục được bảo vệ bằng semaphore), khả năng dự đoán này có thể sụp đổ.

Mầm mống của vấn đề là loại trừ lẫn nhau (mutual exclusion). Khi tác vụ ưu tiên thấp đang khóa tài nguyên mà tác vụ ưu tiên cao yêu cầu cùng tài nguyên đó, tác vụ cao buộc phải chờ đến khi tác vụ thấp giải phóng tài nguyên. Đến đây vẫn là “chờ đợi bình thường” không thể tránh khi dùng loại trừ lẫn nhau. Vấn đề thật sự phát sinh khi trong khoảng chờ đó một tác vụ ưu tiên trung bình chen vào, đẩy tác vụ thấp đang giữ tài nguyên ra và chiếm CPU. Tác vụ giữ tài nguyên không được thực thi nên cũng không giải phóng được tài nguyên, và rốt cuộc tác vụ ưu tiên cao nhất phải chờ vô hạn vì một tác vụ trung bình có độ ưu tiên thấp hơn mình. Việc không thể dự đoán cận trên của thời gian chờ này là điều chí mạng đối với hệ thống thời gian thực.

Thực tế, năm 1997 tàu thăm dò sao Hỏa Mars Pathfinder của NASA đã gặp sự cố khởi động lại liên tục sau khi hạ cánh, và nguyên nhân chính là đảo ngược độ ưu tiên này. Khi tác vụ ưu tiên thấp giữ tài nguyên bị tác vụ liên lạc ưu tiên trung bình đẩy ra nên không giải phóng được tài nguyên, bộ định thời watchdog giám sát thời hạn của tác vụ quản lý ưu tiên cao đã reset hệ thống. Tình huống này cho thấy đảo ngược độ ưu tiên không phải là rủi ro lý thuyết mà là khiếm khuyết thực tế đe dọa nhiệm vụ thực.

B. Điều kiện phát sinh

Đảo ngược độ ưu tiên phát sinh khi ba điều kiện chồng lên nhau. Thứ nhất, các tác vụ dùng chung tài nguyên được bảo vệ bằng loại trừ lẫn nhau. Thứ hai, độ ưu tiên được phân thành từ ba mức trở lên (cao·trung bình·thấp). Thứ ba, trong khi tác vụ thấp giữ tài nguyên, tác vụ ưu tiên trung bình có thể chiếm quyền (preempt). Thiếu bất kỳ điều kiện nào thì sự đảo ngược dẫn đến trì hoãn vô hạn sẽ không thành lập. Ví dụ, nếu chỉ có hai mức tác vụ thì việc chờ tài nguyên sẽ kết thúc trong khoảng thời gian hữu hạn của vùng găng.

2. Ví dụ phát sinh (dựa trên phép toán P/V)

Xem theo trình tự thời gian quá trình đảo ngược xảy ra với phép toán P (lấy)·V (trả) của semaphore như sau. Giả sử Task1 có độ ưu tiên cao nhất, Task2 trung bình, Task3 thấp nhất.

sequenceDiagram
  participant T1 as Task1 (cao)
  participant T2 as Task2 (trung bình)
  participant T3 as Task3 (thấp)
  T3->>T3: P(S) chiếm tài nguyên
  T1->>T1: Yêu cầu tài nguyên → chờ (chờ T3 trả)
  T2->>T2: Chiếm quyền thực thi (đẩy T3 ra)
  Note over T1,T3: T1 chờ vô hạn vì T2 = xảy ra đảo ngược
  T2->>T2: Kết thúc
  T3->>T3: Tiếp tục → V(S) trả tài nguyên
  T1->>T1: Lấy được tài nguyên → thực thi muộn

Ban đầu, Task3 ưu tiên thấp đang thực thi thì khóa tài nguyên dùng chung bằng P(S). Trong lúc đó, Task1 thức dậy và yêu cầu cùng tài nguyên, nhưng vì Task3 đã chiếm giữ nên Task1 chuyển sang trạng thái chờ. Đến đây vẫn là độ trễ có thể chấp nhận được, sẽ sớm được giải phóng khi Task3 đi qua vùng găng ngắn của mình.

Thời điểm quyết định khiến đảo ngược thành lập là khi Task2 chuyển sang trạng thái sẵn sàng. Task2 có độ ưu tiên cao hơn Task3 nên bộ lập lịch đẩy Task3 ra và thực thi Task2. Task2 làm việc của mình không liên quan đến tài nguyên, nhưng vì thế Task3 không có được CPU và mất cả cơ hội trả tài nguyên bằng V(S). Kết quả là Task1 đang chờ tài nguyên phải tiếp tục chờ cho đến khi Task2 kết thúc.

Ở đây bản chất của sự đảo ngược (inversion) lộ ra. Task1 có độ ưu tiên cao nhất lại được thực thi muộn hơn Task2 ưu tiên trung bình vốn chẳng liên quan gì đến tài nguyên. Hơn nữa, nếu nhiều Task2 dồn đến hoặc thực thi lặp lại, thời gian chờ của Task1 về lý thuyết có thể kéo dài vô hạn, rơi vào trạng thái “không thể tính được cận trên của độ trễ”. Việc đảm bảo thời gian đáp ứng — lý do tồn tại của hệ thống thời gian thực — sụp đổ tại điểm này.

3. Các kỹ thuật giải quyết

Giải pháp cho đảo ngược độ ưu tiên có chung ý tưởng “tạm thời nâng độ ưu tiên của tác vụ ưu tiên thấp đang chiếm tài nguyên để ngăn tác vụ ưu tiên trung bình chiếm quyền”. Nếu để tác vụ giữ tài nguyên không bị tác vụ trung bình đẩy ra mà nhanh chóng thoát khỏi vùng găng và trả tài nguyên, thời gian chờ của tác vụ cao sẽ bị chặn (bounded) bởi độ dài vùng găng.

Kỹ thuật	Nguyên lý	Đặc điểm
Kế thừa độ ưu tiên (Priority Inheritance)	Tác vụ chiếm tài nguyên (T3) tạm thời kế thừa độ ưu tiên của tác vụ cao đang chờ (T1) để thực thi nhanh·trả tài nguyên	Ứng phó khi xảy ra, hiện thực đơn giản
Trần độ ưu tiên (Priority Ceiling)	Mỗi tài nguyên được đặt độ ưu tiên trần, khi chiếm tài nguyên lập tức được nâng lên mức trần đó → phòng ngừa bế tắc·đảo ngược	Phòng ngừa trước, ngăn cả bế tắc

A. Giao thức kế thừa độ ưu tiên

Kế thừa độ ưu tiên (Priority Inheritance Protocol, PIP) là phương thức ứng phó ngay khi phát hiện đảo ngược. Khi Task1 ưu tiên cao bắt đầu chờ tài nguyên do Task3 giữ, Task3 ngay lúc đó “thừa hưởng” độ ưu tiên cao của Task1. Task3 được nâng độ ưu tiên sẽ không bị Task2 ưu tiên trung bình chiếm quyền, nên nhanh chóng hoàn tất vùng găng của mình và trả tài nguyên bằng V(S). Ngay khi trả tài nguyên, Task3 trở về độ ưu tiên thấp ban đầu, và Task1 đang chờ lấy được tài nguyên để thực thi.

Giải pháp thực tế cho sự cố Pathfinder chính là kế thừa độ ưu tiên này. Việc từ Trái Đất vá phần mềm từ xa để bật tùy chọn kế thừa cho semaphore có vấn đề và khắc phục được hiện tượng khởi động lại cho thấy một cách tiêu biểu hiệu quả thực tế của kỹ thuật này. Tuy nhiên, kế thừa độ ưu tiên có hạn chế: khi nhiều tài nguyên đan xen sẽ phát sinh chặn dây chuyền (chained blocking) — sự kế thừa nối đuôi nhau — khiến việc tính toán độ trễ phức tạp, và không ngăn được bản thân bế tắc (deadlock).

B. Giao thức trần độ ưu tiên

Trần độ ưu tiên (Priority Ceiling Protocol, PCP) là phương thức phòng ngừa vấn đề từ trước. Với mỗi tài nguyên dùng chung, chỉ định trước độ ưu tiên cao nhất trong số các tác vụ có thể dùng tài nguyên đó làm “trần (ceiling)”. Ngay khi một tác vụ chiếm tài nguyên đó, bất kể độ ưu tiên gốc của mình, nó lập tức được nâng lên độ ưu tiên trần. Như vậy, tác vụ giữ tài nguyên ngay từ đầu đã không bị tác vụ trung bình đẩy ra, hơn nữa tình huống các tác vụ khác nhau khóa đan chéo nhiều tài nguyên bị chặn từ gốc, nên phòng ngừa được cả bế tắc và chặn dây chuyền.

Hai kỹ thuật có tính chất khác nhau. Nếu kế thừa độ ưu tiên là “kiểu ứng phó” nâng độ ưu tiên một cách hậu kiểm khi đảo ngược thực sự xảy ra, thì trần độ ưu tiên là “kiểu phòng ngừa” nâng lên mức cao nhất ngay khi lấy tài nguyên. Về hiệu quả phòng ngừa và chống bế tắc, trần độ ưu tiên vượt trội hơn, nhưng kéo theo gánh nặng thiết kế là phải tính toán·quản lý chính xác mức trần cho từng tài nguyên. Vì vậy, các RTOS thương mại (VxWorks, FreeRTOS, v.v.) thường cung cấp kế thừa độ ưu tiên như tùy chọn mặc định của mutex, và dùng có chọn lọc giao thức trần trong các hệ thống cực kỳ đề cao an toàn.

4. Chuyên sâu — Góc độ áp dụng thực tiễn và kiểm chứng

Trong thực tế, đảo ngược độ ưu tiên là loại khiếm khuyết “triệu chứng rõ ràng nhưng nguyên nhân ẩn giấu”. Bề ngoài nó xuất hiện dưới dạng một công việc ưu tiên cao cụ thể thỉnh thoảng lỡ thời hạn, nhưng mã của chính công việc đó không có vấn đề, còn nguyên nhân gốc là tranh chấp tài nguyên không liên quan, nên khó tái hiện và truy vết. Vì vậy, cách tiếp cận phòng ngừa là quan trọng: ở giai đoạn thiết kế, liệt kê phổ độ ưu tiên của các tác vụ sử dụng từng tài nguyên dùng chung, và áp dụng tường minh giao thức kế thừa·trần cho các tài nguyên trải qua từ ba mức trở lên.

Từ góc độ kiểm chứng, phân tích thời gian đáp ứng (Response Time Analysis) và tính toán thời gian thực thi xấu nhất (WCET, Worst-Case Execution Time) là cốt lõi. Khi áp dụng kế thừa·trần độ ưu tiên, cận trên của thời gian mà tác vụ cao có thể bị tác vụ thấp làm trễ (blocking time) bị chặn ở “một lần độ dài vùng găng”, nên có thể đưa giá trị này vào số hạng chặn của phân tích khả năng lập lịch (ví dụ: RMA, Rate Monotonic Analysis) để chứng minh định lượng việc tuân thủ thời hạn. Trong các miền tuân theo tiêu chuẩn an toàn như điện tử hàng không (DO-178C), ô tô (ISO 26262), chứng minh tính bị chặn về thời gian như vậy nằm trong yêu cầu chứng nhận, nên phòng chống đảo ngược độ ưu tiên không phải là vấn đề chức năng mà là vấn đề an toàn.

Mặt khác, trong các hệ thống thời gian thực đa lõi gần đây, vấn đề trở nên phức tạp hơn. Khi tác vụ được phân tán giữa các lõi, phát sinh tình huống tác vụ trên một lõi chờ tài nguyên do lõi khác giữ, và để xử lý điều này, các giao thức chia sẻ tài nguyên cho đa lõi như MSRP·MrsP đang được nghiên cứu·áp dụng. Chi tiết kỹ thuật và phạm vi áp dụng là lĩnh vực đang tiếp tục phát triển, nên khi áp dụng thực tế, nên xác nhận qua tài liệu chính thức các giao thức mà RTOS và phần cứng đang dùng hỗ trợ.

5. Những điểm cần cân nhắc và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)

Là yếu tố thiết yếu quyết định độ tin cậy của hệ thống thời gian thực. Trong hệ thống thời gian thực buộc phải tuân thủ thời hạn, đảo ngược độ ưu tiên sinh ra độ trễ không thể dự đoán và dẫn thẳng đến vi phạm thời hạn, nên RTOS hỗ trợ kế thừa·trần độ ưu tiên như chức năng mặc định hoặc tùy chọn của mutex. Chỉ cần dùng mutex có chức năng kế thừa thay vì semaphore đơn thuần cũng có thể giảm đáng kể rủi ro.
Hiểu chính xác trade-off của các kỹ thuật để lựa chọn. Kế thừa độ ưu tiên hiện thực đơn giản và ứng phó khi xảy ra nhưng vẫn còn khả năng chặn dây chuyền·bế tắc, còn trần độ ưu tiên phòng ngừa cả bế tắc nhưng đòi hỏi chi phí thiết kế là tính toán·quản lý mức trần theo từng tài nguyên. Phải lựa chọn phù hợp với cấp độ an toàn của hệ thống và mức độ đan xen tài nguyên.
Tối thiểu hóa tài nguyên dùng chung là phòng ngừa căn bản nhất. Ngay từ đầu giảm tài nguyên dùng chung giữa các tác vụ có độ ưu tiên khác nhau, và khi không tránh được thì giữ vùng găng ngắn nhất có thể, sẽ làm giảm bản thân thời gian bị chặn, qua đó thu hẹp cả khả năng đảo ngược lẫn cận trên độ trễ. Cách tiếp cận loại bỏ hẳn trạng thái dùng chung bằng cấu trúc dữ liệu không khóa (lock-free) hoặc thiết kế dựa trên hàng đợi thông điệp cũng hiệu quả.
Phải chứng minh định lượng tính bị chặn về thời gian. Áp dụng giao thức không phải là mục đích tự thân, mà là phương tiện để chặn thời gian bị chặn xấu nhất và chứng minh tuân thủ thời hạn bằng phân tích khả năng lập lịch. Trong các hệ thống thiết yếu về an toàn, chứng minh này là yêu cầu chứng nhận, nên phải được tích hợp vào quy trình thiết kế·kiểm chứng cùng với tính toán WCET·phân tích thời gian đáp ứng.

Tài liệu tham khảo

What Really Happened on Mars? (Mike Jones, tổng hợp tình huống NASA JPL) — https://www.rapitasystems.com/blog/what-really-happened-software-mars-pathfinder-spacecraft
FreeRTOS — Tài liệu Priority Inheritance/Mutexes — https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html

Tóm tắt một câu: Đảo ngược độ ưu tiên là hiện tượng tác vụ ưu tiên cao bị thực thi muộn một cách không thể dự đoán do tác vụ thấp chiếm tài nguyên và tác vụ trung bình chiếm quyền, được giải quyết bằng kế thừa độ ưu tiên (tạm thời kế thừa độ ưu tiên của tác vụ đang chờ) và trần độ ưu tiên (lập tức nâng lên mức trần theo tài nguyên, phòng ngừa cả bế tắc), và về căn bản được phòng ngừa bằng cách tối thiểu hóa tài nguyên dùng chung·vùng găng.