Bài giảng Tác vụ tuần hoàn và không tuầnhoàn

Tác vụ tuần hoàn và không tuần hoàn Topics „ Khái niệm „ Tác vụ không tuần hoàn „ Khoảng deadline sớm nhất đầu tiên „ Tác vụ tuần hoàn „ Lập lịch đơn điệu 2Vũ Quang Dũng Sách tham khảo „ P. Marwedel: Embedded System Design (paperback), Springer Verlag, December 2005, ISBN: 0387292373. „ G.C. Buttazzo: Hard Real-Time Computing Systems. Kluwer Academic Publishers, 1997. „ W. Wolf: Computers as Components – Principles of Embedded System Design. Morgan Kaufman Publishers, 2000. „ J. Teich: Digitale Hardware/Software Systeme, Springer Verlag, 1997. Mở đầu „ Lập lịch trong tác vụ không tuần hoàn với thời gian thực thông qua một số thuật toán …Theo deadline sớm nhất (EDD – Earliest Deadline Due) …Deadline sớm nhất đầu tiên (EDF – Earliest Deadline First) Theo deadline sớm nhất (EDD) „ Luật Jackson: Cho một bộ n tác vụ. Xử lý theo thứ tự của các deadline không giảm là sự tìm giá trị tối ưu nhỏ nhất của khoảng trễ cực đại. „ Chứng minh: EDD ví dụ 1 EDD ví dụ 2 Deadline sớm nhất đầu tiên (EDF) „ Luật Horn: Cho a là tập hợp n tác vụ độc lập với thời gian đến tùy ý, bất kỳ thuật toán mà tác vụ tuân theo, thực thi với deadline tuyệt đối sớm nhất trong các tác vụ sẵn sàng, thì thuật toán đó là tối ưu khi tìm cách làm giảm giá trị của độ trễ cực đại. „ Chứng minh: Cho mỗi khoảng thời gian [t, t+1) được chứng thực, khi tác vụ thực thụ thực thi là với deadline tuyệt đối sớm nhất. Nếu không phải như trên, thì tác vụ với deadline tuyệt đối sớm nhất được thực thi trong khoảng thời gian thay thế. Sự hoạt động đó không làm tăng khoảng trễ cực đại. EDF tiếp „ Các đại lượng sử dụng như sau: …σ(t) – nhận biết tác vụ thực thi trong khoảng [t, t+1) …E(t) – nhận biết tác vụ sẵn sàng tại thời gian t, mà có deadline sớm nhất. … tE(t) – là thời gian (≥ t) mà mỗi khoảng tiếp theo của tác vụ E(t) bắt đầu thực thi theo sự lập lịch hiện tại. EDF tiếp Tác vụ nào đang thực thi? Tác vụ nào có deadline sớm nhất? Khoảng thời gian Khoảng thời gian thay đổi Trạng thái sau khi thay đổi EDF – tiếp „ Đảm bảo … Thời gian kết thúc xấu nhất của tác vụ i: „ Trong đó ck là thời gian thực thi xấu nhất còn lại của tác vụ k. … Điều kiện đảm bảo EDF: … Thuật toán Algorithm: EDF_guarantee (J, Jnew) { J’=J∪{Jnew }; /* ordered by deadline */ t = current_time(); f0 = 0; for (each Ji ∈J’) { fi = fi-1 + ci (t); if (fi > di ) return(INFEASIBLE); } return(FEASIBLE); } EDF – ví dụ Thuật toán EDF* „ Vấn đề trong lập lịch với n tác vụ với ép buộc quyền ưu tiên có thể được giải quyết trong hàm đa thức về thời gian nếu tác vụ được ưu tiên. „ Thuật toán EDF* xác định sự lập lịch có thể thực hiện được trong trường hợp tồn tại một tác vụ ép buộc quyền ưu tiên. „ Đảm bảo về sự tồn tại của sự lập lịch đúng đắn … Tác vụ bắt đầu thực thi không sớm hơn thời gian giải phóng và không sớm hơn thời gian kết thúc của tác vụ ngay trước đó. … Tất cả các tác vụ kết thúc sự thực thi trong deadline của nó. EDF* - tiếp „ Tác vụ phải bắt đầu sự thực thi không sớm hơn thời gian giải phóng „ Tác vụ phải không bắt đầu thực thi sớm hơn thời gian kết thúc nhỏ nhất của tác vụ trước nó Tác vụ b phụ thuộc vào a: Ja → Jb „ Giải pháp: rj* = max(rj, max(ri* + Ci : Ji→ Jj)) EDF* - tiếp „ Tác vụ phải kết thúc thời gian thực thi theo deadline „ Tác vụ phải không kết thúc thời gian thực thi muộn hơn giá trị bắt đầu thời gian lớn nhất của tác vụ sau nó Tác vụ b phụ thuộc vào a: Ja → Jb „ Giải pháp: di* = min(di, min(dj* - Cj : Ji→ Jj)) EDF* - tiếp „ Thuật toán dành cho giải phóng thời gian: 1. Cho bất kỳ điểm bắt đầu nào của cây ưu tiên ri * = ri 2. Chọn tác vụ j sao cho thời gian giải phóng không thay đổi, nhưng thời gian giải phóng của tất cả các tác vụ liền trước nó i thay đổi. Nếu không tồn tại, thoát khỏi thuật toán. 3. rj * = max(rj , max(ri * + Ci : Ji → Jj )) 4. Quay lại bước 2. „ Thuật toán dành cho deadline 1. Cho bất kỳ điểm cuối nào của cây ưu tiên di * = di 2. Lựa chọn tác vụ i sao cho deadline của nó không thay đổi, nhưng thời gian giải phóng của tất cả các tác vụ j ngay sau đó thay đổi. Nếu không tồn tại, thoát khỏi thuật toán. 3. di * = min(di , min(dj * - Cj : Ji → Jj )) 4. Quay lại bước 2. Mô hình tác vụ tuần hoàn „ Γ : biểu thị tập hợp tác vụ tuần hoàn „ τi : biểu thị tác vụ tuần hoàn chung „ Τi,j : biểu thị trường hợp thứ j của tác vụ I „ ri,j : biểu thị thời gian giải phóng (release) „ si,j : biểu thị thời gian bắt đầu (start) „ fi,j : biểu thị thời gian kết thúc (finish) „ di,j : deadline tuyệt đối của thời điểm j trong tác vụ i „ Φi : pha của tác vụ i „ Di : deadline tương đối của tác vụ i Mô hình tác vụ tuần hoàn „ Giả thuyết sau: … Thời điểm của tác vụ tuần hoàn được kích hoạt đều đặn tại một khoảng cố định. Khoảng Ti giữa hai lần kích hoạt liên tục được gọi là chu kỳ. Thời gian giải phóng ri,j = Φi + (j-1)Ti … Tất cả các thời điểm đều cùng có WCET Ci … Tất cả các thời điểm của tác vụ tuần hoàn đều cùng có một deadline tương đối Di. Theo đó deadline tuyệt đối tính theo công thức sau di,j = Φi + (j-1)Ti + Di … tiếp „ Giả thuyết sau: …Thông thường, deadline tương đối bằng với chu kỳ Di = Ti, vì thế di,j = Φi + jTi …Tất cả các tác vụ tuần hoàn đều độc lập với nhau, không có sự ưu tiên và ràng buộc tài nguyên. …Tác vụ không thể tự dừng. …Mọi tác vụ được giải phóng nhanh như khi nó tới …Mọi tầng trên của OS kernel theo giả thiết bằng 0 Ví dụ Rate-monotonic Scheduling (RM) „ Mệnh đề: … Tác vụ ưu tiên được gán cho tác vụ trước khi thực thi và không thay đổi trong thời gian thực thi. (phân bố sự ưu tiên tĩnh) … RM về bản chất là sự ưu tiên: tác vụ đang thực thi được ưu tiên bởi tác vụ có độ ưu tiên cao hơn. … Deadline sẽ bằng chu kỳ Di = Ti „ Thuật toán: Mỗi một tác vụ được gán cho một độ ưu tiên. Tác vụ với mức đòi hỏi cao hơn (với chu kỳ ngắn hơn) sẽ có mức ưu tiên cao hơn. Tác vụ với mức ưu tiên cao hơn sẽ ngắt các tác vụ với mức ưu tiên thấp. RM tiếp „ Tối ưu: RM được tối ưu thông qua sự phân bố mức ưu tiên cố định mà không có thuật toán về ưu tiên cố định được lập lịch bởi RM. „ Phân tích khả năng lập lịch: bộ tác vụ tuần hoàn là có thể lập lịch với RM nếu (điều kiện đủ) „ Biểu thức: biểu thị hệ số sử dụng bộ xử lý U, là phân số của thời gian xử lý trong quá trình thực thi của tác vụ Deadline Monotonic Scheduling (DM) „ Mệnh đề: giống với RM, nhưng … Deadline có thể nhỏ hơn chu kỳ Ci ≤ Di ≤ Ti „ Thuật toán: Mỗi một tác vụ được gán với một mức ưu tiên. Tác vụ với deadline nhỏ hơn sẽ có mức ưu tiên cao hơn. Tác vụ với mức ưu tiên cao hơn ngắt các tác vụ với mức ưu tiên thấp. „ Phân tích khả năng lập lịch: tập hợp của tác vụ tuần hoàn là có thể lập lịch với DM nếu (điều kiện đủ) DM tiếp „ Sự cần và đủ kiểm tra khả năng lập lịch … Sự đòi hỏi bộ xử lý trong trường hợp xấu nhất xảy ra khi mọi tác vụ được giải phóng cùng một lúc tại các thời điểm có tính quyết định của chúng. … Cho mỗi tác vụ i, tổng thời gian xử lý của chúng và sự cản trở bởi các tác vụ có mức ưu tiên cao hơn phải nhỏ hơn hoặc bằng Di … Đo sự cản trở trong trường hợp xấu nhất của tác vụ i có thể được tính bằng tổng của thời gian xử lý của mọi tác vụ ở mức độ ưu tiên cao hơn được giải phóng trước thời gian t, mà theo thứ tự i < j Ù Di < Dj DM tiếp „ Thời gian response dài nhất Ri của tác vụ tuần hoàn i được tính bằng tổng thời gian tính toán của nó tại thời điểm có tính quyết định, và sự cản trở bởi tác vụ có mức ưu tiên cao hơn Ri = Ci + Ii „ Kiểm tra tính lập lịch khả thi cần phải tính toán giá trị nhỏ nhất của Ri cho mọi tác vụ i với Ri ≤ Di DM tiếp „ Thời gian response dài nhất Ri của tác vụ tuần hoàn i có thể được tính theo thuật toán sau Algorithm: DM_guarantee (Γ) { for (each τi ∈Γ){ I = 0; do { R = I + Ci ; if (R > Di ) return(UNSCHEDULABLE); I = Σj=1,…,(i-1) [R/Tj ] Cj ; } while (I + Ci > R); } return(SCHEDULABLE); } DM ví dụ „ Cho các tác vụ … Tác vụ 1: C1 = 1; T1 = 4; D1 = 3 … Tác vụ 2: C2 = 1; T2 = 5; D2 = 4 … Tác vụ 3: C3 = 2; T2 = 6; D3 = 5 … Tác vụ 4: C4 = 1; T4 = 11; D4 = 10 „ Thuật toán cho tác vụ 4: … Bước 0: R4 = 1 … Bước 1: R4 = 5 … Bước 2: R4 = 6 … Bước 3: R4 = 7 … Bước 4: R4 = 9 … Bước 5: R4 = 10 DM ví dụ tiếp DM ví dụ tiếp Lập lịch EDF „ Mệnh đề: … Phân bố mức ưu tiên động … Độ ưu tiên thực chất … Di ≤ Ti „ Thuật toán: Tác vụ đang thực thi được ưu tiên khi sự tuần hoàn với deadline sớm hơn được kích hoạt di,j = Φi + (j-1) Ti + Di „ Tối ưu: không tồn tại thuật toán khác có thể lập lịch bởi EDF Lập lịch EDF „ Kiểm tra tính lập lịch khả thi cần và đủ nếu Di = Ti …Tập hợp các tác vụ tuần hoàn được lập lịch với EDF nếu và chỉ nếu „ Biểu thức sau biểu thị sử dụng bộ xử lý trung bình Lập lịch EDF „ Nếu sự sử dụng bộ xử lý U>1, thì không có lập lịch thỏa mãn. Tổng thời gian tính toán theo yêu cầu trong khoảng T = T1·T2· · ·Tn là „ Nếu sự sử dụng bộ xử lý U<1, thì sẽ có lập lịch thỏa mãn. Giả thiết deadline bị thiếu tại thời gian t2 Lập lịch EDF tiếp „ Với khoảng [t1, t2], tổng thời gian tính toán theo yêu cầu bởi tác vụ tuần hoàn được giới hạn bởi „ Deadline bị thiếu tại thời gian t2 Số chu kỳ hoàn thành của tác vụ i trong khoảng thời gian [t1 , t2 ] Tác vụ tuần hoàn „ Ví dụ: cho 2 tác vụ, deadline = chu kỳ, U=97% Vấn đề trong tập hợp trộn tác vụ „ Trong nhiều chương trình, cùng tồn tại các tác vụ tuần hoàn lẫn không tuần hoàn. „ Tác vụ tuần hoàn: hướng thời gian, thực thi với thời gian cưỡng ép. „ Tác vụ không tuần hoàn: hướng sự kiện, có thể là hard, soft và không phải thời gian thực, phụ thuộc vào chương trình. „ Tác vụ rời rạc: hướng sự kiện, offline theo tác vụ không tuần hoàn với thời gian ép buộc có thể hoàn thành với sự giả định đúng đắn của môi trường, có thể theo thời gian tới lớn nhất đối với mỗi sự kiện. Tác vụ không tuần hoàn xác định bởi khoảng thời gian lớn nhất giữa tác vụ được gọi là rời rạc. Lập lịch cơ sở „ Giải pháp đơn giản cho lập lịch theo RM và EDF của các tác vụ tuần hoàn … Tiến trình của tác vụ không tuần hoàn khi không có yêu cầu tuần hoàn … Tác vụ tuần hoàn không bị ảnh hưởng … Sự đáp lại của các tác vụ không tuần hoàn có thể ngăn cấm, và không thể gán mức ưu tiên cao hơn tới chúng Bài tập „ Đọc thêm về RM Polling Server và EDF Total Bandwidth Server trong quyển sách “P. Marwedel: Embedded System Design” „ Bài tập về EDF …Cho 5 tác vụ với thời gian tới, thời gian thực thi và deadline theo bảng sau: Bài tập …Tại thời gian t=3, tác vụ mới Jx tham gia với thời gian thực thi Cx = 2 và deadline dx = 10. …Câu hỏi: Có thể đảm bảo rằng có khả năng lập lịch khả thi đối với tác vụ mới Jx trên hay không? Giải thích?