Bài giảng Tổng quan về phần mềm trong hệ thống nhúng

Tổng quan về phần mềm trong hệ thống nhúng Topics „ Tổng quan chung trong thiết kế phần mềm dành cho hệ thống nhúng „ Sự khác nhau trong hình thức phát triển phần mềm 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. Phát triển phần mềm WCET – Trường hợp xấu nhất trong thời gian thực thi „ WCET – là giới hạn trên trong thời gian thực thi của các công việc trong hệ thống „ Cần thiết cho tất cả các phương thức, nhằm đảm bảo các trạng thái thời gian của ứng dụng WCET - WCET - WCET’ (gần giới hạn trên) - Có thể xảy ra worst case - Tuân theo thời gian thực thi - Tính tôt nhất trong thời gian thực thi - Gần giới hạn dưới dành cho best case - Giới hạn dưới có thể tốt nhất trong thời gian thực thi t Khoảng thời gian thực thi có thể xảy ra Sự hiệu qua của phương thức ở mức hệ thống Hệ thống thực Sự đo lường Mô hình hóa Phân tích WCET – tiếp „ Tính phức hợp … Trong trường hợp tổng quát: tính không nhất quyết nếu tồn tại giới hạn … Cho những chương trình hạn chế: như các thiết kế đơn giản, tính phức tạp dành cho các thiết kế mới bao gồm pipelines, caches, interrupt, virtual memory … „ Tiếp cận theo hướng phân tích … Dành cho phần cứng: cần thiết của tổng hợp phần cứng. … Dành cho phần mềm: cần phải có máy chương trình, phân tích, sự cần thiết của một mô hình phần cứng. Thời gian thực thi trung bình „ Mô hình hóa (simulation): dưới các mức độ khác nhau trong phân tích tỉ mỉ có thể nhất của hệ thống, mô phỏng trạng thái của môi trường „ Sự mô phỏng (emulation): một phần của hệ thống được thay thế bởi phần cứng mô phỏng „ Sự định hình (profiling): thời gian thực thi được đo trong hệ thống thực thi thực tế „ Vấn đề (Problem): trên tổng quát, WCET không thể được xác định bằng phương pháp dựa trên môi trường, dữ liệu đầu vào, nó được sử dụng thông qua thời gian thực thi trung bình của toàn hệ thống Hệ thống điều khiển thời gian thực „ A/D: analog to digital „ D/A: digital to analog Đa xử lý „ Khái niệm của xử lý song song phản ánh bằng trực giác các chức năng của hệ thống nhúng. „ Xử lý giúp cho quản lý thời gian hệ thống: … Tốc độ đa xử lý „ Đa phương tiện „ Tự động … Đầu ra không đồng bộ „ Giao diện người sử dụng „ Hệ thống trao đổi thông tin Ví dụ: máy điều khiển „ Xử lý: …Điều khiển đánh lửa …Cảm giác tay quay …Hỗn hợp khí – nhiên liệu …Bộ lọc Kalman – thuật toán điều khiển Khái niệm đồng thứ tự „ Các kỹ năng lập trình được sử dụng trong phát triển ES „ Sự gọi hàm quyết định địa chỉ trả về „ Đồng thứ tự này sẽ trao quyền điều khiển cho đồng thứ tự khác „ Phần chuyển điều khiển được nhúng trong m㠄 Các vấn đề: … Khó xác định được vết thực thi từ chương trình … Không giấu dữ liệu Phương pháp đồng thứ tự „ Ví dụ trong mã assembler của ARM Tổng quan „ Có rất nhiều cấu trúc khác nhau của một chương trình nhúng. „ Những nguyên tắc cơ bản: … Tiếp cận theo time trigger „ Tính chu kỳ „ Thực thi tuần hoàn „ Lập lịch … Tiếp cân theo event trigger „ Không ưu tiên „ Ưu tiên – stack „ Ưu tiên – lập lịch „ Ưu tiên – đa tiến trình Hệ thống time trigger (TT) „ Mô hình đơn giản … Không xảy ra ngắt bởi bộ thời gian … Bộ lập lịch định trước – không sử dụng thuật toán … Xác định tại trạng thái run-time … Tương tác với môi trường thông qua các giao tiếp Lập lịch TT theo chu kỳ „ Bộ thời gian hoạt động đều đặn theo chu kỳ P „ Tất cả các tiến trình đều có cùng chu kỳ P „ Đặc điểm … Các tiến trình sau (T2, T3) không thể dự đoán trước khi bắt đầu … Không xảy ra vấn đề gì trong liên lạc giữa các tiến trình hay sử dụng các tài nguyên, như có một thứ tự tĩnh Ví dụ về lập lịch TT theo chu kỳ Lập lịch TT thực thi tuần hoàn „ Tiến trình có thể có các chu kỳ khác nhau „ Chu kỳ P được chia ra thành từng đoạn frame với độ dài f „ Vấn đề: nếu có các tiến trình dài, và cần được phân chia thành các luồng tiến trình nhỏ hơn, thì nó sẽ không phù hợp, khi các trạng thái local phải phân chia và lưu thành các trạng thái global Lập lịch TT thực thi tuần hoàn „ Điều kiện: … Tiến trình thực thi trong một frame f <= p(k) với mọi k (p – chu kỳ đối với tiến trình k) … Chu kỳ P tối thiểu phải là tích của tất cả tiến trình p(k) … Các tiến trình bắt đầu và kết thúc trong khoảng một frame f >= WCET(k) với mọi k …Giữa các lần cấp phát thời gian và deadline của mọi tiến trình, xuất hiện ít nhất một frame 2f – gcd(p(k),f) <= D(k) với mọi k (D(k) – deadline của tiến trình k) Lược đồ của điều kiện cuối cùng Ví dụ về lập lịch thực thi tuần hoàn „ Ràng buộc … f <= min{4,5,20} = 4 … f >= max{1.0, 1.0, 1.8, 2.0} = 2.0 … 2f – gcd(p(k), f) <= D(k) với mọi k ⇒Giải pháp f = 2 Lập lịch TT „ Trong toàn hệ thống TT, cấu trúc điều khiển tạm thời của mọi tiến trình được thành lập vào khoảng trước hoạt động, và được đưa vào trong danh sách đặc tả tiến trình (TDL – Task-Descriptor List), chứa sự lập lịch thực thi tuần hoàn của mọi hoạt động hệ thống. „ Lịch được lập sẽ cân nhắc các quyền ưu tiên, và các quan hệ qua lại lẫn nhau giữa các tiến trình. „ Dispatcher (sự gửi) được kích hoạt bởi đồng hồ đồng bộ. Nó sẽ tìm kiếm trong TDL, sau đó thực thi các hành động đã được lên kế hoạch trong khoảng thời gian đó. Ví dụ về lập lịch TT Kết luận về lập lịch TT „ Tính quyết định của lập lịch, dễ dàng kiểm chứng, test và xác thực „ Sử dụng chia xẻ tài nguyên „ Liên kết ngoài chỉ thông qua polling „ Tính bất biến của môi trường „ Sẽ có vấn đề nếu tiến trình dài „ Không cho phép ngắt? „ Cho phép quyền ưu tiên của tiến trình đang hoạt động. Hệ thống Even Trigger (ET) „ Sự lập lịch của các tiến trình được xác định bởi các sự cố ngắt ngoài … Tính động và tính thích nghi (dynamic and adaptive) - sử dụng chia xẻ tài nguyên, bộ đệm … Tính đảm bảo (guarantees) – trong quá trình run-time hoặc lập lịch ban đầu hệ thống Lập lịch ET không ưu tiên „ Cơ chế: … Đối với mỗi sự kiện, sẽ kích hoạt tiến trình tương ứng … Sự kiện được phản ánh bởi „ Ngắt ngoài „ Tự tiến trình của nó … Dự kiện được lựa chọn thông qua hàng đợi, phụ thuộc vào tính kỷ luật. … Tiến trình không được ngắt „ Ngoại lệ: … Tiến trình hiện tại đã được kích hoạt được hoạt động tiếp nếu hàng đợi rỗng … Tính thời gian của sự kiện tham gia vào hàng đợi chỉ sau một khoảng thời gian Ví dụ về lập lịch ET không ưu tiên Lập lịch ET không ưu tiên „ Tính chất: … Liên kết giữa các tiến trình đơn giản, ngắt có thể là nguyên nhân với chia xẻ tài nguyên … Xảy ra tràn bộ đệm nếu có quá nhiều sự kiện cùng kích hoạt bởi môi trường hoặc tiến trình … Tiến trình dài ngăn cản các tiến trình khác trong thực thi và tràn bộ đệm „ Chia tiến trình thành các phần nhỏ hơn Lập lịch ET ưu tiên – Stack „ Tiến trình sẽ được ưu tiên so với tiến trình khác „ Nếu có sắp xếp của các tiến trình ưu tiên, có thể sử dụng cơ chế ngăn xếp Lập lịch ET ưu tiên – Stack (tiếp) „ Tiến trình phải kết thúc trong thứ tự LILO „ Chia xẻ tài nguyên phải theo cơ chế bảo mật, như loại bỏ ngắt, sử dụng semaphore Ví dụ lập lịch ET ưu tiên – Stack Tiến trình „ Tiến trình là sự kích hoạt duy nhất của chương trình „ Tiến trình có trạng thái riêng của nó …Trạng thái thanh ghi …Ngăn xếp Tiến trình và CPU „ Kích hoạt: …Copy trạng thái tiến trình …Thanh ghi và cấu trúc dữ liệu cục bộ „ Chuyển đổi: …Trạng thái CPU hiện tại sẽ được chuyển sang trạng thái mới Đa tiến trình „ Mỗi tiến trình được phép chuyển đổi khi gọi hàm cswitch() (context switch) „ Sự riêng biệt trong lập lịch để chọn tiến trình kích hoạt tiếp theo „ Lợi ích: … Dự đoán xảy ra trạng thái chuyển đổi … Ít lỗi xảy ra khi sử dụng chia xẻ tài nguyên „ Lỗi: … Chương trình lỗi có thể giữ các tiến trình khác, không giải phóng khỏi CPU … Tính thời gian thực có thể xảy ra rủi ro nếu tiến trình dài Ví dụ đa tiến trình Tính ưu tiên của đa tiến trình „ Lập lịch điều khiển các trạng thái chuyển đổi „ Lập trình quyết định tiến trình sẽ kích hoạt tiếp theo „ Sử dụng đồng hồ để gọi tới OS và chuyển đổi trạng thái „ Sử dụng ngắt cứng/mềm, hoặc gọi trực tiếp chương trình ngắt từ OS Luồng điều khiển ưu tiên Bài tập „ Cho hệ thống thời gian thực với 4 tiến trình được kích hoạt J1, J2, J3, J4 với thời gian đến và deadline cho theo bảng sau, và hàm lập lịch σ(t) theo sơ đồ sau. Bài tập (tiếp) „ Hãy xác định …Sự trễ lớn nhất? …Trạng thái không bền vững của tiến trình? …Sử dụng processor dành cho bộ lập lịch này? „ Nhận xét tính khả thi của bộ lập lịch?