Mô hình thời gian thực

Chia sẻ: abel86

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.

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Mô hình thời gian thực

Mô hình thời gian thực
Topics
Khái niệm thời gian thực
Lập lịch
Thời gian
Các phương pháp tính




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.
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
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản