Download miễn phí Bài giảng Tác vụ tuần hoàn và không tuần hoàn
Deadline sớmnhấtđầutiên(EDF)
Luật Horn: Cho a là tậphợp n tác vụđộclậpvới
thờigianđếntùyý, bấtkỳthuật toán mà tác vụ
tuân theo, thựcthi với deadline tuyệtđốisớ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ảmgiá trị củađộtrễ cựcđại.
Chứng minh: Cho mỗikhoảng thời gian [t, t+1)
đượcchứng thực, khi tác vụthựcthụthựcthi là
với deadline tuyệtđốisớmnhất. Nếu không phải
nhưtrên, thì tác vụvới deadline tuyệtđốisớm
nhất đượcthự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
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Tác vụ tuần hoàn và không tuần hoànTopics
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ụ đư