Bài giảng Thiết kế hệ thống nhúng - Chương 5: RTOS – Hệ điều hành thời gian thực - Bài 9: RTOS và Kỹ thuật lập lịch
Universität Dortmund
- 1 -
CHƯƠNG 5: RTOS – HỆ ĐIỀU HÀNH THỜI
GIAN THỰC
Bài 9: RTOS và Kỹ thuật lập lịch
Universität Dortmund
- 2 -
RTOS
• Phần lõi (Kernel): Thực hiện việc lập lịch (schedules
tasks)
• Tác vụ (Tasks): Là các hoạt động hiện tại với các
trạng thái riêng của nó (PC, registers, stack, etc.)
Universität Dortmund
- 3 -
RTOS
Universität Dortmund
- 4 -
CÁC YÊU CẦU VỚI RTOS
• Kích thước nhỏ (lưu trữ toàn bộ trong ROM)
• Sử dụng hệ thống ngắt
• Không nhất thiết phải có các cơ chế bảo vệ
• Tăng tốc
• Khi các quá trình ứng dụng đang thực hiện thì các yêu
cầu hệ thống điều hành có thể được thực hiện thông
qua các lời gọi hàm thay vì sử dụng cơ chế ngắt mềm
Universität Dortmund
- 5 -
CÁC NHIỆM VỤ (Tasks)
• Các nhiệm vụ = Code + Data + State (trạng thái)
• Trạng thái của nhiệm vụ được lưu trữ trong khối
điều khiển nhiệm vụ (Task Control Block - TCB)
khi nhiệm vụ không được thực hiện trên CPU
• Một TCB điển hình:
Universität Dortmund
- 6 -
Các trạng thái của nhiệm vụ
• Executing: Đang thực hiện trên CPU
• Ready: Có thể chạy trên CPU nhưng một nhiệm vụ
khác đang sử dụng CPU
• Blocked: Đợi sự kiện (I/O, signal, resource, etc.)
• Dormant: Tạo ra nhưng chưa được thực hiện
• Terminated: Không còn tác động nữa
RTOS thực hiện một cơ chế chuyển trạng thái cho
mỗi nhiệng thái.
Universität Dortmund
- 7 -
Task States Transitions
Universität Dortmund
- 8 -
Bộ lập lịch RTOS
• Thực hiện cơ chế chuyển trạng thái
• Chuyển giữa các nhiệm vụ
• Thuật toán chuyển:
1.Lưu trữ trạng thái hiện tại vào TCB
2.Tìm
3.Khôi phục trạng thái từ TCB mới
4.Tiếp tục
• Chuyển đổi giữa trạng thái EXECUTING -> READY:
1.Nhiệm vụ được thực hiện tuần tự: NON-PREEMPTIVE
2.RTOS chuyển trạng thái cho các nhiệm vụ ưu tiên cao hơn:
PR
Universität Dortmund
- 9 -
Quá trình lập lịch
Mục đích: Đảm bảo yêu cầu về thời gian
• Lập lịch trước khi chạy (static): Xác định chính xác
giản đồ thời gian cho các nhiệm vụ tại thời điểm thiết kế
• Lập lịch khi chạy chương trình (dynamic): Lập lịch
được thực hiện tự động bởi RTOS, dựa trên sự ưu tiên.
Universität Dortmund
- 10 -
Phân bố các nhiệm vụ (1)
Một chu kỳ của nhiệm vụ (Đối với các nhiệm vụ có chu kỳ - periodic
tasks):
• Các ràng buộc ưu tiên: Xét xem có bất cứ nhiệm vụ nào cần được ưu tiên
không.
• Thời gian xuất hiện-ai (arrival time): Là khoảng thời gian khi sự kiện xảy ra và
nhiệm vụ tương ứng được kích hoạt.
Thời điểm bắt đầu thực thi ri (release time): Thời điểm sớm nhất khi việc xử
lý đã sẵn sàn
• Thời điểm bắt đầu thực hiện - si (starting time): Là thời điểm mà tại đó tác vụ
bắt đầu việc thực hiện của mình.
• Thời gian tính toán/thực thi - ci (Computation time): Là khoảng thời gian cần
thiết để bộ xử lý thực hiện xong nhiệm vụ của mình mà không bị ngắt.
• Thời điểm hoàn thành - fi (finishing time): Là thời điểm mà tại đó tác vụ hoàn
thành việc thực hiện của mình.
• Thời gian rủthực hiện
lâu nhất có thể xảy ra.
• Thời điểm kết thúc - di (due time): Thời điểm mà tác vụ phải hoàn thành.
Universität Dortmund
- 11 -
Model nhiệm vụ
Mô hình nhiệm vụ đơn giản:
• Tất cả các nhiệm vụ phải có yêu cầu khắt khe về chu
kỳ thực hiện.
• Thời gian để hoàn thành nhiệm vụ chính là chu kỳ của
nhiệm vụ.
• Tất cả các nhiệm vụ độc lập – không có ràng buộc về
quyền ưu tiên.
• Không có nhiệm vụ nào có bộ phận không ưu tiên
• Chỉ có nhiệm vụ xử lý.
Universität Dortmund
- 12 -
Các kỹ thuật lập lịch
1. First Come First Serve (FCFS)
• Các quá tình được xử lý theo thứ tự mà nó xuất hiện yêu cầu và cho
đến khi hoàn thành
• Cơ chế lập lịch này thuộc loại không ngắt được và có ưu điểm là dễ
dàng thực thi
• Không phù hợp cho hoạt động đáp ứng thời gian thực
2. Shortest Job First (SJF)
• Tác vụ ưu tiên cao
nhất và sẽ được phục vụ trước
• Không biết trước được thời gian thực thi của các tác vụ tham
gia trong chương trình và thông thường phải áp dụng cơ chế
tiên đoán và đánh giá dựa vào kinh nghiệm về các tác vụ thực
thi trong hệ thống
• Có thể không ngắt
được
Universität Dortmund
- 13 -
Các kỹ thuật lập lịch
3. Rate Monotonic (RM)
• Phương pháp này dựa trên một số giả thiết sau:
- Tất cả các tác vụ tham gia hệ thống phải có deadline kiểu chu kỳ
- Tất cả các tác vụ độc lập với nhau
- Thời gian thực hiện của các tác vụ biết trước và không đổi
- Thời giathể bỏ qua
• Thuật toán RM được thực thi theo nguyên lý gán mức ưu tiên
cho các tác vụ dựa trên chu kỳ của chúng (chu kỳ nhỏ thì
mức ưu tiên cao)
• Với các tác vụ chu kỳ không thay đổi thì RM sẽ là phương
pháp lập lịch cho phép ngắt và mức ưu tiên cố định
Universität Dortmund
- 14 -
Các kỹ thuật lập lịch
3. Earliest Deadline First (EDF)
• Sử dụng deadline của tác vụ như điều kiện ưu tiên để xử lý
điều phối hoạt động
• Tác vụ có deadline gần nhất sẽ có mức ưu tiên cao nhất và
các tác vụ có deadline xa nhất sẽ nhận mức ưu tiên thấp nhất
4. Minimu
• Cơ chế lập lịch này sẽ ưu tiên tác vụ nào còn ít thời gian còn
lại để thực hiện nhất trước khi nó phải kết thúc để đảm bảo yêu
cầu thực thi đúng
• Cơ chế lập lịch gán quyền ưu tiên động và dễ đạt được sự tối
ưu về hthống
Universität Dortmund
- 15 -
Các kỹ thuật lập lịch
5. Round Robin (RR)
• Mỗi một tác vụ được xử lý/phục vụ trong một khoảng thời gian
nhất định và lặp lại theo một chu trình xuyên suốt toàn bộ các
tác vụ tham gia trong hệ thống
• Khoảng thời gian phục vụ cho mỗi tác vụ trong quá trình là một
sự thoả và thời
gian thực hiện một chu trình
15 trang
19/04/2022
2820
Bạn đang xem tài liệu "Bài giảng Thiết kế hệ thống nhúng - Chương 5: RTOS – Hệ điều hành thời gian thực - Bài 9: RTOS và Kỹ thuật lập lịch", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thiet_ke_he_thong_nhung_chuong_5_rtos_he_dieu_hanh.pdf
