Download miễn phí Bài giảng Mô hình thời gian thực
Kháiniệmcơbản
Hệhard RT: các tác vụcủahệthống bắtbuộc
phảinằm trong khoảng deadline cho phép của
hệthống. Mọihoạt động nằm ngoài deadline đó
đượccoilà lỗicủahệthống. (vượt quá WCET)
Hệsoft RT: tác vụcó thểdo mộtsốnguyên
nhân, được phép gia hạn thêm thời gian ngoài
khoảng deadline củahệthống, mà không gây
ảnh hưởng nghiêm trọng tớimôi trường cũng
nhưtính chính xác củahệthốngđó
Để 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:
Mô hình thời gian thựcTopics
Khái niệm thời gian thực
Lập lịch
Thời gian
Các phương pháp tính
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.
Khái
niệm cơ
bản
Hệ hard RT: các tác vụ của hệ thống bắt buộc
phải nằm trong khoảng deadline cho phép của
hệ thống. Mọi hoạt động nằm ngoài deadline đó
được coi là lỗi của hệ thống. (vượt quá WCET)
Hệ soft RT: tác vụ có thể do một số nguyên
nhân, được phép gia hạn thêm thời gian ngoài
khoảng deadline của hệ thống, mà không gây
ảnh hưởng nghiêm trọng tới môi trường cũng
như tính chính xác của hệ thống đó.
Lập lịch
Cho tập hợp các tác vụ J = {J1, J2, …}
Lập lịch là sự gán cho các tác vụ sự xử lý, mà
mỗi tác vụ được thực thi hoàn toàn
Lập lịch có thể được xác định như một hàm
số nguyên σ: R → N, trong đó σ(t) – tác vụ tại
thời điểm thực thi t. Nếu σ(t) = 0 thì tiến trình
được gọi là rỗi (idle)
Nếu σ(t) thay đổi giá trị của nó tại một thời
điểm nào đó thì tiến trình được gọi là chuyển
đổi ngữ cảnh (context switch)
Lập lịch
(tiếp)
Đối với mỗi khoảng mà σ(t) là hằng, thì tiến
trình đó được gọi là phần thời gian (time slice)
Lập lịch ưu tiên là lập lịch mà các tác vụ đang
hoạt động có thể bị ngắt tùy ý tại mọi thời
điểm, và gán CPU cho tác vụ khác theo kế
hoạch đã được lập trước đó
Lập lịch
và
thời gian
Lập lịch có thể thực hiện được, nếu mọi tiến trình có thể
kết thúc theo một sự bắt buộc cho trước
Tập hợp các tiến trình có thể lập lịch được, nếu tại đó
tồn tại ít nhất một giải thuật mà thủ tập lập lịch có thể
thực hiện được
Thời gian đến ai (arrival time) hay thời gian giải phóng
(release time) ri là thời gian mà tại đó tiến trình sẵn sàng
để thực thi
Sự ước tính thời gian Ci (computation time) là thời gian
cần thiết để CPU thực thi một tiến trình mà không xảy ra
ngắt
Lập lịch
và
thời gian (tiếp)
Deadline di là thời gian mà mỗi tiến trình
phải hoàn thành
Thời gian bắt đầu si (start time) là điểm bắt
đầu thực thi của tiến trình
Thời gian kết thúc fi (finishing time) là điểm
kết thúc thực thi của tiến trình
Lập lịch
và
thời gian
Sử dụng các định nghĩa trên, ta có di ≥ ri + Ci
Sự trễ (lateness) Li = fi – di, là sự trễ về kết thúc của tiến
trình so với deadline. Nếu tiến trình kết thúc trước
deadline thì không có trễ
Thời gian vượt trội (exceeding time) Ei = max(0, Li), là
thời gian mà tiến trình sau deadline
Tính lỏng lẻo thời gian (slack time) Xi = di – ai – Ci, là
thời gian lớn nhất mà tiến trình có thể trễ để hoàn thành
trong deadline
Deadline
Deadline là khoảng thời gian mà một tiến trình
cần để hoàn thành
Relative deadline Di: là thời gian cho phép lớn nhất
đối với một tiến trình
Absolute deadline di: là thời gian mà tiến trình bắt
buộc phải hoàn thành
Job và
task
Job – là đơn vị công việc được lập lịch bởi
hệ thống
Task – là tập hợp các job có quan hệ tham
gia vào hệ thống
Lập lịch
và
thời gian
Tác vụ tuần hoàn τi: sự nối tiếp liên tục của
những hoạt động đồng nhất, gọi là jobs, mà
được hoạt động theo quy tắc tại khoảng cố định
với chu kỳ Ti. Thời gian hoạt động của job thứ
nhất được gọi là pha Φi
Ví
dụ
Computation time: C1=9, C2=12
Start time: s1=0, s2=6
Finishing time: f1=18, f2=28
Lateness: L1=-4, L2=1
Exceeding time: E1=0, E2=1
Slack time: X1=13, X2=11
Ép
buộc
quyền
ưu tiên
Ép buộc quyền ưu tiên trong graphs có thể
được mô tả thông qua hướng không tuần hoàn
graph G, mà tiến trình được thể hiện bằng các
node và các quan hệ cao hơn bởi các mũi tên
Có thể có các giải thích khác nhau
Mọi sự kế thừa của tiến trình được thực
thi (thực thi song song)
Một kết thừa của tiến trình được thực thi
(không có sự lựa chon mang tính quyết
định)
Ví
dụ
Thực thi song song
Hình ảnh thu được acq1,
acq2
Xử lý ảnh mức độ thấp
edge1, edge2
Tách hình shape
Đối tượng với kích thước H
Đối tượng nhận dạng rec
Phân
loại thuật toán lập lịch
Thuật toán lập lịch ưu tiên – tiến trình hoạt động có thể
bị ngắt tại mọi thời điểm, và gán sự xử lý tới tiến trình
khác, thông qua sự lập lịch cho trước
Thuật toán lập lịch không ưu tiên – tiến trình, một khi đã
được thực thi, thi sẽ thực thi cho đến khi kết thúc
Thuật toán lập lịch tĩnh – sự quyết định của lập lịch được
xây dựng trên những tham số cố định, được gán cho
tiến trình trước khi thực thi
Thuật toán lập lịch động – sự quyết định của lập lịch
được xây dụng trên những tham số động, mà có thể
thay đổi trong suốt quá trình thực thi
Phân
loại thuật toán lập lịch
Một thuật toán được gọi là tối ưu nếu có thể tối giản
được giá trị hàm được định nghĩa trong tiến trình
Một thuật toán được gọi là tự tìm (heuristic algorithm)
nếu nó nhắm tới sự hoàn thiện, nhưng không đảm bảo
tìm ra sự lập lịch tối ưu
Các
phép
tính
Ví
dụ
Ví
dụ
lập lịch
(a) – sự trễ lớn nhất được tối giản, nhưng các tiến trình
không nằm trong deadline
(b) – sự trễ lớn nhất đã được tăng, nhưng chỉ một tiến
trình không nằm trong deadline
...