Tác vụ tuần hoàn và không tuần hoàn

Chia sẻ: Nhữ Quang Khải | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

106
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tác vụ tuần hoàn và không tuần hoà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 2 Vũ 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: Cho bất kỳ điểm bắt đầu nào của cây ưu tiên ri* = ri 1. Chọn tác vụ j sao cho thời gian giải phóng không thay đổi, 2. 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. rj* = max(rj, max(ri* + Ci : Ji → Jj)) 3. Quay lại bước 2. 4. Thuật toán dành cho deadline Cho bất kỳ điểm cuối nào của cây ưu tiên di* = di 1. Lựa chọn tác vụ i sao cho deadline của nó không thay đổi, 2. 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. di* = min(di, min(dj* - Cj : Ji → Jj)) 3. Quay lại bước 2. 4.
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ụ