Lập lịch QT có nhiều dạng khác nhau khi thêm vào ràng buộc thời gian. Trong nhiều ứng dụng, HĐH cần đảm bảo việc sắp xếp các thao tác sao cho chúng tuân thủ các ràng buộc thời gian đã đặc tả. Hệ thống này được gọi là hệ thống thời gian thực vì chúng có ràng buộc tới hạn thời gian thực. Tồn tại nhiều hệ thống máy tính thời gian thực, như hệ thống máy tính hàng không, máy tính điều khiển tự động hoá, hệ tự động hóa sản xuất, hệ thống thương mại chứng khoán.

Dịch vụ thời gian thực được gắn với tập các tác vụ thời gian thực. Mỗi tác vụ $τ$ được miêu tả bằng:

$τ_{i}$ = (S_i,_{C_i,_{D_i)}}

trong đó S_i là thời điểm sớm nhất có thể bắt đầu tác vụ $τ_{i}$ , C_i là thời gian thực hiện trong trường hợp xấu nhất của $τ_{i}$ và D_i là thời điểm chết của $τ_{i}$ . Tập V tác vụ thời gian thực là:

V= i{ $τ_{i}$ / =1…n}

Tồn tại các dạng hệ thời gian thực chủ yếu sau đây

 Trong các hệ thống thời gian thực liên quan tới điều khiển theo mức độ an toàn hoặc thiết bị có mức tới hạn, mọi tác vụ buộc phải hoàn thành trước điểm chết nếu không tai hoạ xảy ra. Hệ thống này gọi là hệ thống thời gian thực cứng vì chỉ được coi là đúng nếu như mọi tác vụ phải bảo đảm hoàn thành trước điểm chết.

 Trong các hệ thống (như hệ thống đa phương tiện) có những điểm chết nhưng vẫn có thể hoạt động nếu không lỡ qua điểm chết quá nhiều lần. Chúng được gọi là hệ thống thời gian thực mềm. ở đây một tác vụ vẫn tiếp tục phải hoàn thành dẫu rằng đã qua điểm chết.

 Hệ thống thời gian thực tĩnh về mặt nào đó tương tự như hệ thống thời gian thực mềm nhưng tác vụ qua điểm chết sẽ không được thực hiện. Ví dụ, máy tính tự động sản xuất không thể khởi sự một thao tác cơ học để tránh cho thiết bị khỏi tự làm hư hỏng.

 Nếu tác vụ được xuất hiện theo cách tại thời điểm tuỳ ý, chúng được gọi là không theo chu kì. ở nhiều hệ thống thời gian thực thì thời điểm tác vụ xảy ra, khoảng thời gian thực hiện và điểm chết có thể tiên đoán được. Tập tác vụ như vậy gọi là có chu kì.

Ví dụ, máy tính điều khiển động cơ phải tính được lượng nhiên liệu và suy ra thời gian tối đa động cơ còn vận hành liên tục trước khi nạp nhiên liệu.

Miêu tả tập tác vụ thời gian thực có chu kì đơn giản. Mỗi tác vụ thực hiện một trong n công việc. Yêu cầu thực hiện công việc i một lần trong khoảng Ti giây. Các phần công việc phía trước phải hoàn thành trước khi phần công việc mới được bắt đầu. Như vậy, thời điểm bắt đầu của tác vụ mới là điểm chết của tác vụ cũ. Do vậy tại một thời điểm chỉ một tác vụ được thực hiện, ta gán cho tác vụ thực hiện phần công việc i là $τ_{i}$ . Đặc tả tập tác vụ rút gọn lại bởi tập thời khoảng và khoảng thời gian thực hiện n công việc:

V = {J_i = (C_i,T_i)/ 1 ≤ i ≤ n}

ở đây chỉ quan tâm đến lập lịch các tác vụ theo đó, tác vụ thỏa mãn ràng buộc về thời điểm chết. Chúng ta cũng chỉ quan tâm lập lịch trên hệ thống đơn xử lý. Lịch là phân công CPU cho các tác vụ thời gian thực mà nhiều nhất một tác vụ được phân công tại thời điểm bất kỳ. Chính xác hơn, lịch là tập A các khoảng thời gian được miêu tả:

A= {(s_i,f_i,t_i)/ i=1…n}

Trong đó si là thời điểm bắt đầu, fi là thời điểm kết thúc và ti là tác vụ được thực hiện trong khoảng thời gian đó. Lịch có giá trị chỉ khi thoả mãn các ràng buộc:

1. ∀i=1, …, s_i< f_i

2. ∀i=1, …, f_i< s_i+1

3. Nếu t_i=k thì S_k s_i và f_i D_k

Điều kiện 1 đòi hỏi khoảng thời gian thực hiện thực sự là một khoảng. Điều kiện 2 đòi hỏi các khoảng thời gian được sắp theo thứ tự. Điều kiện 3 đòi hỏi tác vụ phải thực hiện sau thời điểm cho phép và phải hoàn thành trước điểm chết. Tập tác vụ được gọi là khả thi nếu mọi tác vụ $τ_{k}$ nhận được tối thiết C_k giây CPU thực hiện trong lịch. Tức là, nếu gọi:

A( $τ_{k}$ ) = {a=(s_i,f_i,t_i)/ a∈Avà t_i=k}

Như vậy, lịch là khả thi nếu mọi $τ_{k}$ ∈ V mà

\sum_{S_{i}, f_{i}, k = τ_{i}} f_{i} - S_{i} C_{k}

Tập tác vụ được gọi là khả thi nếu tồn tại một lập lịch khả thi cho tập tác vụ đó. Mục đích của thuật toán lập lịch thời gian thực là tìm lịch khả thi nếu nó tồn tại. Chương này tìm hiểu các thuật toán lập lịch thời gian thực với giả thuyết ràng buộc khác nhau. Để đơn giản, chỉ xem xét hệ thống thời gian thực cứng.

Hệ thống đơn điệu đều

Kiểu đơn giản nhất của lập lịch thời gian thực có các giả thiết sau:

1. Mọi tác vụ là chu kỳ và T_i là khoảng thời gian của tác vụ $τ_{i}$

2. Các tác vụ không truyền thông tới nhau

3. Các tác vụ có mức độ ưu tiên và độ ưu tiên đó là cố định (lập lịch ưu tiên tĩnh).

Việc cố định các độ ưu tiên đã làm đơn giản hoá bài toán lập lịch. Trong lập lịch ưu tiên tĩnh, bộ lập lịch chỉ tìm kiếm tác vụ có độ ưu tiên cao nhất cho bước kế tiếp. Trong khi đó ở hệ độ ưu tiên động, bộ lập lịch phải tính toán lại giá trị ưu tiên sau các bước. Tuy nhiên, dẫu có nhiều tập tác vụ thích hợp với cách ưu tiên động, nhưng lớp bài toán lập lịch ưu tiên tĩnh vẫn là ý tưởng khởi đầu tốt và dễ thực hiện.

Quan sát tập tác vụ khả thi đơn giản chưa được lập lịch ưu tiên tĩnh. Nếu tập tác vụ đó có một lịch khả thi được tạo ra bằng bộ lập lịch ưu tiên tĩnh thì gọi tập tác vụ như thế là có một lịch phân công ưu tiên tĩnh khả thi. Mục đích của phần này là tìm lịch trên nếu nó tồn tại.

Nếu tác vụ $τ_{i}$ được yêu cầu thực hiện tại thời điểm t, $τ_{i}$ sẽ không vượt điểm chết nếu thời gian thực hiện các tác vụ ưu tiên cao hơn trong khoảng thời gian (t,t+D_i) nhỏ hơn hay bằng D_i-C_i. Khi thực hiện tác vụ được đòi hỏi (tức là, bắt đầu thời khoảng của nó), tác vụ có thể hoặc không thể hoàn thành công việc trước điểm chết, phụ thuộc vào dịch vụ CPU đòi hỏi cho các tác vụ ưu tiên cao hơn. Tuy nhiên, có thể định vị trường hợp tồi nhất. Mốc tới hạn của tác vụ τi xuất hiện khi nó và mọi tác vụ có độ ưu tiên cao hơn được lập lịch đồng thời. Mô tả mốc tới hạn của τ5 trong hình 5.13 (vùng rời nét là thực hiện tác vụ, khối biên liền nét là thời gian chờ tác vụ). Nếu tác vụ τi phù hợp điểm chết khi được lập lịch theo mốc tới hạn thì nó luôn phù hợp điểm chết trong cách lập lịch khác.

Lý do được minh họa trong hình 5.13. Hãy chú ý điều xảy ra khi lập lịch τi nếu di chuyển thời gian đòi hỏi của tác vụ ưu tiên cao hơn τh lên hoặc xuống. Nếu cho thời điểm đòi hỏi của τh lên t+ε thì tương ứng phải giảm thời gian thực hiện các tác vụ này trong khoảng (t, t+Dτi) đi ε. Tuy nhiên tổng số thời gian dành cho thực hiện τh trong (t,t+Dτi) không tăng lên. Tương tự với việc giảm. Do vậy, tại mốc tới hạn, tổng thời gian các tác vụ có độ ưu tiên cao thực hiện là lớn nhất.

Vì thế, có thể xác định nếu kết quả phân công ưu tiên trong một lịch khả thi bằng cách mô phỏng thực hiện các tác vụ tại mốc tới hạn của tác vụ có độ ưu tiên nhỏ nhất. Nếu tác vụ có độ ưu tiên nhỏ nhất phù hợp điểm chết khi bắt đầu từ khoảng tới hạn thì các tác vụ khác cũng phù hợp điểm chết của chúng. Tác vụ có khoảng thời gian quá ngắn sẽ có ít thời gian thực hiện công việc của nó hơn là tác vụ có khoảng thời gian dài. Bằng trực giác, thấy sẽ tốt hơn nếu gán mức ưu tiên cao cho tác vụ có khoảng thời gian ngắn và ngược lại.

Đặt PR_h là độ ưu tiên của tác vụ τh. Giả sử rằng nếu PR_h>PR₁, CPU sẽ xử lý τh trước τl (tức là giá trị PR cao hơn tương ứng mức ưu tiên cao hơn). Qui tắc phân công ưu tiên tác vụ được gọi là phân công độ ưu tiên tốc độ đều RM (Rate Monotonic) như sau:

Hệ phân công ưu tiên RM

Nếu T_h<T₁ thì PR_h>PR₁

Phép phân công ưu tiên tốc dộ đều rất dễ thi hành vì chỉ cần xếp các tác vụ theo độ dài các khoảng thời gian của nó. RM cũng tạo ra một phân công độ ưu tiên tốt. Có thể chỉ ra rằng nếu tồn tại một lập lịch ưu tiên cố định cho một tập các tác vụ có chu kì thì RM sẽ tạo ra một lịch như vậy.

Nói ngắn gọn, RM là một thuật toán phân công độ ưu tiên tối ưu theo nghĩa nếu tồn tại một phân công ưu tiên tĩnh mà lập lịch kết quả là khả thi thì phân công đơn điệu đều cũng sẽ sinh ra lịch khả thi.

Để hiểu được tính chất này của phân công RM, giả sử rằng có một phân công A không RM sản sinh ra một lịch khả thi. Có thể hiển thị các tác vụ đã xếp theo ưu tiên giảm dần mà τ1 cao nhất còn τn thấp nhất. Vì A là hệ không-RM nên tồn tại cặp 2 tác vụ τi và τi+1 mà T_i>T_i+1. Nếu thay đổi độ ưu tiên của 2 tác vụ này thì hệ vẫn sẽ là hệ khả thi?

Nhớ lại, chỉ cần xem nếu τi và τi+1 _{phù hợp điểm chết tại mốc tới hạn. Chú ý điều gì xảy ra tại mốc tới hạn theo phân công độ ưu tiên A (hình 5.14). Trong khoảng thời gian (0,T_i+1) sau mốc tới hạn, tác vụ τi sau τi+1 là H giây. Do τi+1 phù hợp điểm chết của nó nên}

H+C_i+C_i+1 ≤ T_i+1

Tiếp đó, khi thay đổi độ ưu tiên của τi và τi+1. Tác vụ τi+1 chắc chắn phù hợp điểm chết vì đã tăng độ ưu tiên của nó. τi cũng phù hợp điểm chết vì nó sẽ hoàn thành công việc trong khoảng T_i+1<T_i. Do vậy, việc thay đổi trên vẫn dẫn đến một kết quả lịch khả thi.

Nếu lặp các bước hoán đổi sẽ tạo ra một phân công RM. Suy ra nếu một tập các tác vụ có chu kì có phân công ưu tiên cố định khả thi thì RM sẽ là một trong số các lịch đó.

Phân tích thời gian

Để chắc chắn tất cả các tác vụ phù hợp điểm chết, CPU sẽ được đặt ở chế độ rỗi trong một số chu kì thời gian (những chu kì này được sử dụng thực hiện các tác vụ không tới hạn) Chúng ta cũng phải cần chắc chắn về mức độ tốt của CPU mà thuật toán đem lại (ví dụ thời gian nhàn rỗi không quá dài).

Định nghĩa tải L của các tác vụ thời gian thực là phân số thời gian mà các tác vụ này sử dụng CPU

L = \sum_{i = 1}^{n} \frac{C_{i}}{T_{i}}

Các nghiên cứu chỉ ra rằng điều kiện đủ để RM là một phân công ưu tiên khả thi là $L \leq n (2^{1 / n} - 1)$ . Có nghĩa là nếu việc tải các tác vụ thời gian thực là tối thiểu thì RM sẽ là một phân công ưu tiên khả thi của chúng ta. Chứng minh điều này khá phức tạp và không cần thiết nên không đề cập đến. Tuy nhiên, biết rằng $n (2^{1 / n} - 1)$ sẽ lớn hơn 69 phần trăm khi n đủ lớn và do vậy RM sẽ không lãng phí quá 31 phần trăm của CPU.

Cận $n (2^{1 / n} - 1)$ tải không tỏ ra tốt, đây chỉ dùng để đánh giá, không phải là điều kiện tiên quyết. Trong ví dụ tập tác vụ V={(1,2), (1,3), (1,6)} có lịch phân công theo RM khả thi và 100 phần trăm CPU dành cho việc tải.

Có thể tìm thấy điều kiện cần thiết để xác định liệu tập tác vụ đã cho có thể lập lịch khả thi được hay không bằng cách thử đặt chúng (tức các tác vụ) vào các mốc tới hạn của chúng. Sắp các tác vụ theo độ ưu tiên giảm dần vào một danh sách. Đặc r_i là thời gian trả lời của tác vụ τi tại mốc tới hạn. Nên, τi sẽ thực hiện xong sau r_i sau mốc tới hạn. Trong thời gian đó, tác vụ có độ ưu tiên cao $τ_{k}$ sẽ yêu cầu dịch vụ [r_i/T_h] lần và sẽ cần C_h giây của CPU cho các yêu cầu đó. Suy ra r_i phải thoả mãn mệnh đề sau.

$r_{i} = C_{i} + \sum [\frac{r_{i}}{T_{k}}] C_{k}$

Vì r_i xuất hiện ở hai vế của mệnh đề nên tính trực tiếp nó khá là khó khăn. Nhưng có thể tính được r_i theo cách gián tiếp. Đầu tiên, giả sử τi không chờ bất kì một tác vụ có độ ưu tiên cao nào. Đặt giá trị r_i vào vế phải mệnh đề và tính được giá trị r_imới biểu diễn số các dịch vụ đã thực hiện trong C_i đầu tiên sau điểm tới hạn. Trong QT soát lại thời gian trả lời việc thực hiện một số tác vụ có độ ưu tiên cao có thể xảy ra. Tiếp tục đặt r_ivào vế phải mệnh đề và tiếp tục tính giá trị r_i đến khi ta tìm thấy giá trị ổn định. Các bước trên được biểu diễn tương đương bằng toán học như sau

r_i (0)=C_i

r_{i} (k + 1) = C_{i} + [\frac{r_{i} (k)}{T_{k}}] C_{k}

thực hiện đến khi r_i (k) = r_i(k+1). Nếu tại một số bước r_i(k)>T_i thì tập tác vụ không thể được sắp lịch khả thi.

Hệ thống điểm tới hạn đều

Một số tác vụ trong hệ thống thời gian thực cần hoàn thành công việc thực hiện trước một khoảng thời gian ngắn khi được yêu cầu. Chúng ta có thể tạo ra hệ thống kiểu này bằng cách thay đổi hệ thống các tác vụ có chu kì. Cho

V{J_i=(C_i, T_i,D_i)/ 1 $i \leq n$ }

là mô tả cho các công việc thực hiện trong hệ thống. Như phần trước, gán cho các tác vụ thực hiện chương trình i là $τ_{i}$ . Tác vụ $τ_{i}$ cần thực hiện một lần trong khoảng thời gian Ti và yêu cầu Ci thời gian của CPU để xử lý. Nếu $τ_{i}$ được yêu cầu tại thời điểm t, nó phải hoàn thành công việc trước thời gian t+D_i hoặc nó sẽ vượt qua điểm tới hạn.

Cách phân phối tối ưu dựa vào sự cố định độ ưu tiên cho mô hình này được thể hiện bằng thuật toán DM (Deadline Monotonic)

Phân công ưu tiên điểm tới hạn đều

Nếu D_h<D₁ thì PR_h>PR₁

Trường hợp để DM đạt được tối ưu tương đương như trong trường hợp của RM. Tuy vậy ta sẽ gặp một chút khó khăn khi phân tích DM nhiều hơn so việc phân tích RM bởi vì không có một công thức nào đặt cho công việc này dựa trên sự tải lịch tối ưu tin cậy. May mắn là ta có thể sử dụng thời gian trả lời response time (như trong mệnh đề 5.1) mà không cần sự thay đổi nào. Tác vụ gọi là khả thi nếu r_iD_i với mọi i =1->n.

Ưu tiên điểm tới hạn sớm nhất

Nếu quyết tâm xây dựng một phương pháp lập lịch phức tạp, phải cần đến sự phục vụ của CPU nhiều hơn so với nhiều phương pháp lập trước đó. ý tưởng chung là sử dụng phương pháp lập lịch có độ ưu tiên động (thay đổi). Có nghĩa là các quan hệ của độ ưu tiên của các tác vụ có thể thay đổi khi hệ thống hoạt động. Độ ưu tiên có thể đạt giá trị mới khi có sự kiện quan trọng xảy ra, kiểu như tác vụ kết thúc, tác vụ đồng bộ hay đơn giản tại thời điểm bắt đầu tác vụ.

Đặt τk(i) là tác vụ xảy ra trong khoảng thứ i của công việc J_k và đặt d_k(i) là điểm chết của nó. Tương tự, đặt PR_k(i) là độ ưu tiên phân công cho τk(i). Thuật toán phân công động tối ưu gọi là ưu tiên điểm tới hạn sớm nhất (Earliest Deadline First - EDF).

Phân công ưu tiên điểm tới hạn sớm nhất

Nếu d_h(i)<d₁(j) thì PR_h(i)>PR₁(j)

Ta có thể chỉ ra rằng EDF đạt tối ưu như cách ta đã tiến hành với RM và DM. Giả sử rằng tồn tại một cách sắp lịch khả thi không sử dụng phương pháp theo EDF. Khi đó ta sẽ có cặp tác vụ τk(i) và τl(j) mà d_h(i)<d₁(j) nhưng ưu tiên của τk(i) và τl(j). Lặp lại đế khi lịch là EDF.

Thực ra với D_i=T_i cho 1 tập các tác vụ có chu kì thì chúng là EDF (tồn tại cách phân công khả thi theo EDF) miễn là L $1$ .

Để ý EDF sử dụng điểm của các khoảng xảy ra chốc lát của các tác vụ để xác định các độ ưu tiên, không phải là thông tin về chính các khoảng đó. Do vậy, EDF thích hợp cho lập lịch có chu kì. Theo chứng minh EDF tối ưu được khi chỉ sử dụng điểm chết của các khoảng xảy ra chốc lát của các tác vụ. EDF là thuật toán tốt cho lập lịch các tác vụ thời gian thực có chu kì.

Đồng bộ thời gian thực

Như đã biết ở các mô hình tác vụ trước, ta đã giả sử mỗi tác vụ là độc lập với nhau. Tuy nhiên, một tập các tác vụ cũng có thể liên kết thực hiện một mục đích nên cần chia xẻ thông tin và do vậy phải thiết lập một cơ chế đồng bộ. Hơn nữa mỗi tác vụ cũng cần chiếm hữu các tài nguyên hệ thống (bộ nhớ, kênh truyền,…) trong QT hoạt động. Đồng bộ giữa các tác vụ thời gian được hiểu là phát hoặc thu semaphore (cờ tín hiệu). Không may, việc làm này có thể dẫn đến sự chậm trể thời gian tuy rất ngắn trong QT đồng bộ.

Xem xét hệ thống bao gồm t₁, t₂ và t₃ đã sắp theo thứ tự giảm của độ ưu tiên và semaphore S. Giả sử t₃ đã khoá S lại kh t₁được yêu cầu. Vì $τ_{1}$ có độ ưu tiên cao nhất nên nó sẽ được thực hiện. Nếu $τ_{1}$ thử khoá S, nó sẽ phải dừng lại và chờ cho đến khi $τ_{3}$ tháo khoá S. Tuy nhiên, trong trường hợp $τ_{3}$ liên quan đến $τ_{2}$ (ví như đã sẵn sàng trên hàng đợi) thì nó sẽ phải dừng việc tháo khoá S cho đến khi $τ_{2}$ hoàn thành. Suy ra $τ_{2}$ hoạt động có sự liên hệ phụ thuộc với $τ_{1}$ . Điều này gọi là sự đảo ngược ưu tiên bởi vì $τ_{2}$ đã có độ ưu tiên thực hiện cao hơn $τ_{1}$ trong một khoảng thời gian. Một cách khác có thể gọi đây là chuỗi khống chế. Coi $τ_{1}$ khoá semaphore R, $τ_{2}$ khoá R và S, $τ_{3}$ khoá S thì $τ_{1}$ sẽ coi như là bị khoá bởi $τ_{3}$ dù rằng $τ_{1}$ không khoá S.

Giao thức đồng bộ thời gian thực tương tác với lịch nhằm giảm bớt độ đảo ngược ưu tiên về mức nhỏ nhất và có thể suy đoán được. Việc tương tác này hoàn thành bằng cách điều chỉnh độ ưu tiên của các tác vụ thời gian thực và cung cấp một cách chọn lựa các lối vào sử dụng semaphore.

Giao thức kế thừa ưu tiên

Trong ví dụ trước, sự khống chế tác vụ $τ_{1}$ xảy ra không dự đoán được trong một thời gian dài bởi vì $τ_{2}$ có ưu thế hơn $τ_{3}$ trong khi $τ_{3}$ lại khống chế $τ_{1}$ . Tức là, $τ_{3}$ có quyền ưu tiên hơn $τ_{2}$ trong khi $τ_{3}$ khống chế $τ_{1}$ . Do vậy, $τ_{3}$ thừa kế độ ưu tiên của $τ_{1}$ . Từ đó dẫn đến giao thức kế thừa ưu tiên PIP (Priority Inheritance Protocol) có các luật sau:

- Một tác vụ được phân công thường (RM) khi nó được yêu cầu.

- Phân công cho CPU độ ưu tiên cao nhất

Trước khi một tác vụ bước vào phiên tới hạn, nó đầu tiên phải yêu cầu khoá semaphore các phiên tới hạn khác

Nếu tác vụ $τ_{k}$ bị khống chế thông qua S được điều khiển bởi $τ_{1}$ thì nó sẽ bị chuyển ra khỏi danh sách sàng và PR₁ sẽ được phân công thay cho PR_h (thừa kế độ ưu tiên của $τ_{k}$ )

- Kế thừa độ ưu tiên có thể mở rộng.

Tác vụ có độ ưu tiên cao nhất bị khống chế thông qua S sẽ được cho vào hàng sẵn sàng. Tác vụ $τ_{1}$ trả lại độ ưu tiên mà nó kế thừa qua S và tiếp tục ở độ ưu tiên nhỏ hơn.

Giao thức thừa kế độ ưu tiên giới hạn thời gian trong QT tác vụ bị khống chế (vd: thời gian lúc tác vụ có độ ưu tiên thấp đang hoạt động). Nếu tính được quãng thời gian lớn nhất mà $τ_{i}$ có thể bị khống chế, ta có thể có sự tính toán trước đó để khẳng định có tồn tại một cách sắp lịch khả thi cho tập tác vụ này không? Có hai phương pháp chỉ ra một tác vụ có độ ưu tiên thấp khống chế tác vụ có độ ưu tiên cao hơn. PHương pháp đầu tiên là khống chế trực tiếp. Nó xảy ra khi tác vụ có độ ưu tiên cao muốn khoá semaphore đã được quản lý bởi tác vụ có độ ưu tiên thấp. Phương pháp tứ hai liên quan đến giao thức thừa kế độ ưu tiên. Khống chế đẩy qua xảy ra khi một tác vụ có độ ưu tiên thấp thừa kế được mức ưu tiên cao và nó là tác vụ có độ ưu tiên trung bình có khống chế đẩy qua. Chú ý rằng khi tác vụ có độ ưu tiên thấp nhả semaphore, tác vụ có độ ưu tiên cao thực hiện và tác vụ có độ ưu tiên thấp bởi vì các tác vụ này hoạt động theo sự sắp xếp độ ưu tiên. (vd trong hình 5.16 khi $τ_{k}$ yêu cầu khoá S, nó bị khống chế trực tiếp bởi $τ_{1}$ qua S và $τ_{m}$ bị khống chế đẩy qua bởi $τ_{1}$ qua S).

Giao thức mức ưu tiên trần

Khi giao thức thừa kế ưu tiên hạn chế các khống chế, khoảng trống B_h vẫn còn khá dài. Giao thức mức ưu tiên trần (PCP) có thể biết sự giới hạn B_h ở trong một phiên tới hạn. Để hoàn thành nó, PCP sẽ thêm các hạn chế hà khắc khi tác vụ muốn đặt vào phiên bản tới hạn. Tuy nhiên, nhưng tới hạn đó cần phải được xem xét một cách tổng thể.

Khi tác vụ được yêu cầu (sử dụng PIP), có thể có một số các tác vụ có mức ưu tiên thấp $τ_{1}$ đang khoá semaphore S mà có thể khống chế $τ_{k}$ . Chúng ta phải khẳng định khi $τ_{k}$ được yêu cầu, tối đa một tác vụ có độ ưu tiên thấp khoá semaphore S đang khống chế $τ_{k}$ . Đòi hỏi này đặt ra một luật đơn giản: một tác vụ muốn khoá S chỉ khi không có tác vụ nào khác khoá R mà tác vụ $τ_{k}$ có thể bị khống chế thông qua S và R.

Luật khống chế trên yêu cầu cần có một phương thức đơn giản qua đó xác định các tác vụ nào bị semaphore khống chế. May mắn là ta đã có một phương thức như thế: ceiling (s) chính là độ ưu tiên của tác vụ có độ ưu tiên cao nhất mà có thể bị khống chế bởi S. Suy ra, $τ_{k}$ chỉ có thể bị khống chế qua S nếu và chỉ nếu ceiling (S) PR_h. Khi đó ta gọi ceiling(S) là mức ưu tiên tới hạn của S.

Khi $τ_{1}$ muốn khoá S, nó sẽ kiểm tra mức ưu tiên trần của tất cả các tác vụ bị khống chế qua semaphore R. Nếu mức ưu tiên trần của R nhỏ hơn PR₁, R không thể khống chế tác vụ mà $τ_{1}$ có thể khống chế thông qua S. Do vậy, tác vụ có độ ưu tiên cao $τ_{k}$ có thể bị khống chế qua S và R.

Một ví dụ minh chứng cho việc sử dụng luật PCP ở hình 5.17. Trong bước thực hiện tại phía trên của hình vẽ, tác vụ $τ_{m}$ bị khống chế qua semaphore S bởi vì $τ_{1}$ giữ R và ceiling(R) PR_m. Nếu $τ_{m}$ bị cấm khi yêu cầu S, $τ_{k}$ có thể bị khống chế bởi khoảng thời gian xác định của hai hoạt động phiên tới hạn. Tuy $τ_{m}$ bị khống chế bằng cách khoá như vậy nhưng nó không bao giờ thoát ra được. PCP bảo đảm các tác vụ chỉ bị khoá nhiều nhất một lần. Trong hoạt động ở phía dưới hình vẽ, ceiling(R)<PR_m nên $τ_{m}$ có thể giữ S mà không sợ bị khống chế $τ_{k}$ hai lần.

Theo quan điểm này, ta đã hâu như thiết lập ra giao thức mức ưu tiên tới hạn ngoài việc thêm vào một số luật kèm theo sau:

- Mỗi semaphore S có một liên kết mức ưu tiên tới hạn ceiling(S) với nó.

- Khi $τ_{1}$ muốn khoá S, việc này chỉ đúng khi PR₁ lớn hơn ceiling(R) với mọi semaphore R bị khoá bởi các tác vụ khác. Nếu không $τ_{1}$ sẽ bị khống chế.

- Nếu tác vụ $τ_{k}$ bị khống chế qua S bị giữ bởi $τ_{1}$ thì $τ_{1}$ sẽ thừa kế độ ưu tiên PR_h.

- Khi $τ_{1}$ nhà S, $τ_{1}$ nhà tất cả các độ ưu tiên mà nó kế thừa qua S. Tác vụ có độ ưu tiên cao nhất sẽ được đặt vào hàng đợi

Nếu ra tính được quãng thời gian khống tối đa cho mỗi tác vụ, ta sẽ sử dụng mệnh đề 5.4 để xác định rằng liệu tập các tác vụ có một cách sắp lịch khả thi sử dụng phân công ưu tiên hay không? Bởi vì một tác vụ có thể bị khống chế bởi nhiều nhất một tác vụ khác và qua nhiều nhất một semaphore nên ta có

$B_{h} \leq max \{E_{k} (S) ∣ ceiling (S) \geq {PR}_{k} ∣\}$ (5.5)

Lập lịch thời gian thực

Hệ thống đơn điệu đều

Hệ thống điểm tới hạn đều

Ưu tiên điểm tới hạn sớm nhất

Đồng bộ thời gian thực

Giao thức mức ưu tiên trần