Chuyện gì thật sự đã xảy ra trên sao Hỏa?
Đề bài
Mô tả
Phần mềm thời gian thực trên tàu vũ trụ Mars Pathfinder từng gặp một sự cố gọi là đảo ngược ưu tiên (priority inversion). Một kỹ thuật để khắc phục sự cố này là dùng Giao thức trần ưu tiên (Priority Ceiling Protocol).
Trong bài này, bạn sẽ mô phỏng việc thực thi nhiều tác vụ theo giao thức đó. Các tác vụ dùng chung một tập tài nguyên, mỗi tài nguyên tại một thời điểm chỉ được dùng bởi một tác vụ. Để bảo đảm điều này, tài nguyên phải được khoá trước khi dùng và mở khoá sau khi dùng. Mỗi tác vụ được xác định bởi một thời điểm bắt đầu, một độ ưu tiên gốc duy nhất và một dãy lệnh. Mỗi tác vụ còn có một độ ưu tiên hiện tại, có thể thay đổi trong quá trình thực thi. Có ba loại lệnh:
- compute: tính toán trong một micro giây;
- lock : khoá tài nguyên (không tốn thời gian xử lý);
- unlock : mở khoá tài nguyên (không tốn thời gian xử lý).
Sau khi khoá một tài nguyên, tác vụ được gọi là sở hữu tài nguyên đó cho tới khi nó mở khoá tài nguyên này. Một tác vụ chỉ mở khoá tài nguyên mà nó sở hữu và đã khoá gần đây nhất, không khoá một tài nguyên mà nó đang sở hữu, và khi kết thúc thì không sở hữu tài nguyên nào.
Mỗi tài nguyên có một trần ưu tiên cố định, bằng độ ưu tiên gốc lớn nhất trong số các tác vụ có chứa lệnh khoá tài nguyên đó.
Có một bộ xử lý duy nhất thực thi các tác vụ. Khi khởi động, bộ xử lý đặt đồng hồ bằng rồi chạy một vòng lặp vô hạn gồm các bước sau:
Bước 1. Xác định các tác vụ đang chạy. Một tác vụ đang chạy nếu thời điểm bắt đầu của nó nhỏ hơn hoặc bằng giá trị hiện tại của đồng hồ và nó chưa thực thi hết các lệnh.
Bước 2. Xác định độ ưu tiên hiện tại của các tác vụ đang chạy và những tác vụ đang chạy nào bị chặn. Một tác vụ đang chạy bị chặn nếu lệnh kế tiếp của là khoá tài nguyên và hoặc tài nguyên đã có tác vụ sở hữu, hoặc có ít nhất một tác vụ khác sở hữu một tài nguyên có trần ưu tiên lớn hơn hoặc bằng độ ưu tiên hiện tại của . Nếu bị chặn, ta nói bị chặn bởi mọi tác vụ sở hữu một tài nguyên hoặc như vậy. Độ ưu tiên hiện tại của tác vụ là giá trị lớn nhất trong số độ ưu tiên gốc của và độ ưu tiên hiện tại của mọi tác vụ bị chặn.
Bước 3. Thực thi lệnh kế tiếp của tác vụ đang chạy, không bị chặn, có độ ưu tiên hiện tại lớn nhất (nếu có). Nếu không có tác vụ như vậy hoặc lệnh vừa thực thi là compute, tăng đồng hồ thêm một micro giây. Nếu lệnh vừa thực thi là lock hoặc unlock, không tăng đồng hồ.
Giao thức trần ưu tiên định nghĩa như trên có các tính chất sau:
- Độ ưu tiên hiện tại được định nghĩa qua độ ưu tiên hiện tại và quan hệ chặn, còn quan hệ chặn lại được định nghĩa qua độ ưu tiên hiện tại. Dù trông có vẻ vòng quanh, luôn tồn tại duy nhất một bộ độ ưu tiên hiện tại thoả mãn các định nghĩa.
- Mọi tác vụ cuối cùng đều kết thúc.
- Ở bước 3 không bao giờ có hai tác vụ cùng độ ưu tiên lớn nhất.
Hãy cho biết thời điểm kết thúc của từng tác vụ.
Dữ liệu vào
Dòng đầu tiên gồm hai số nguyên là số tác vụ và là số tài nguyên.
Tiếp theo là dòng, dòng thứ mô tả tác vụ . Mô tả một tác vụ bắt đầu bằng ba số nguyên: thời điểm bắt đầu , độ ưu tiên gốc và số nguyên . Tiếp theo là xâu mô tả các lệnh. Mỗi xâu là một chữ cái (C, L hoặc U) ghép liền với một số nguyên:
- xâu
Cbiểu diễn một dãy gồm lệnh compute; - xâu
LvàUlần lượt biểu diễn lệnh khoá và mở khoá tài nguyên .
Không có hai tác vụ nào có cùng độ ưu tiên gốc.
Dữ liệu ra
Với mỗi tác vụ, in ra thời điểm nó thực thi xong, theo đúng thứ tự các tác vụ trong dữ liệu vào, mỗi số trên một dòng.
Ràng buộc
- , .
- , , .
- Với xâu
C: . Với xâuLvàU: .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 50 2 5 C1 L1 C1 U1 C1 1 1 5 C1 L1 C100 U1 C1 70 3 1 C1 |
106 107 71 |
Tác vụ 2 chạy từ thời điểm 1 và khoá tài nguyên 1 (trần ưu tiên 2) ở thời điểm 2. Tác vụ 1 bắt đầu ở thời điểm 50, tính xong C1 rồi bị chặn khi muốn khoá tài nguyên 1, nên tác vụ 2 được nâng độ ưu tiên hiện tại lên 2. Tác vụ 3 bắt đầu ở thời điểm 70 có độ ưu tiên 3 nên chạy ngay và kết thúc ở thời điểm 71. Tác vụ 2 tính xong C100 và mở khoá ở thời điểm 104, tác vụ 1 chạy nốt và kết thúc ở thời điểm 106, tác vụ 2 kết thúc ở thời điểm 107. |
| 3 3 5 3 5 C1 L1 C1 U1 C1 3 2 9 C1 L2 C1 L3 C1 U3 C1 U2 C1 1 1 9 C1 L3 C3 L2 C1 U2 C1 U3 C1 |
8 15 16 |
Tác vụ 3 khoá tài nguyên 3 (trần ưu tiên 2) ở thời điểm 2. Từ thời điểm 4 tác vụ 2 bị chặn khi muốn khoá tài nguyên 2 vì tài nguyên 3 của tác vụ khác có trần . Tác vụ 1 không bị chặn (tài nguyên đang bị sở hữu duy nhất là tài nguyên 3 với trần ) nên chạy từ thời điểm 5 tới 8. |
Bình luận