Chương 1: Tổng quan RTS

1.1.1Các K Niệm hệ thống 

>Phần cứg of 1 mtính đa năg giải quyết các vđ bằg cách thực thi lặp lại các đoạn lệnh,thường đc gọi là pmềm. Pmềm thườg đc pchia thành các ctrình hthống và ctrình ưdụng

>Các ctrình hthống bao gồm pmềm gtiếp với pcứng mtính như: bộ phân lịch trình,các bộ đkhiển tbị,các bộ điều vận và các ctrình đóg vai trò là các ccụ cho phép ptriển các ctrình ứd.Các ccụ này bgồm ctrình dịch(chuyển đổi nngữ ltrình sag hợp ngữ);assebler(dịch hngữ sang mã máy);các linker(cbị mã máy để tthi). 1 hđh là 1tập hợp các ctrình hthống qlý tài nguyên vlý của mtính.Vì vậy mà 1 hđh tgt là 1 ctrình hthống

>Các ctrình ưd là các ctrình đc vít để giải n~ btoán cụ thể,như cbị các bảg lương,hđơn và đinh hướg đg đi

>Kniệm hthống là tâm điểm của cnghệ pmềm.Nó đc đnghĩa : Hthốg là 1 ánh xạ từ 1 tập đầu vào tới 1 tập đầu ra

Khi mà ko quan tâm tới chi tiết bên trong của hthống,cta có thể xem ánh xạ đó như 1 hộp đen với 1 hay n' đầu vào và đưa ra 1 hay nhiều đầu ra. Bất kỳ 1 thực thể trong tgiới thực nào cũg đều có thể mô hình thành 1 hthống.Trong các hthống tính toán,đầu vào bdiễn bởi dliệu số từ các tbị pcứng và từ các pmềm #.Các đầu vào thườg lquan tới các bộ cảm ứng,các camera,và các tbị # ccấp các đầu vào tuần tự,các đầu vào này sau đố đc chuyển đổi thành các dliệu kthuật số,hoặc chúng ccấp đầu vào dưới dạg digital trực tiếp.Đầu ra kỹ thuật số của hthống mtính cóthể đc chuyển đổi thành đầu ra tuần tự để đkhiển pcứng bên ngoài như các bộ phát động hay các bộ trình diễn

->Tgian đáp ứng của hthống :Khoảng tgian trễ giữa việc bdiễn 1 tập đầu vào trên 1 hthống(các tín hiệu kích thích)và việc đưa ra đc 1 hđộng cần thiết(đáp ứng),bao gồm sự có mặt của tất cả các đầu ra đc gọi là tgian đáp ứng của hthống.Tgian đáp ứng của hthống cần phải nhanh như thế nào phụ thuộc vào mtiêu của hthống.

1.1.2 >ĐNghĩa tgt: 1 hệ tgt là 1 hthống phải tmãn các ràng buộc tường minh vê tgian đáp ứng hoặc sẽ có nguy cơ gặp phải n~ hquả ngtrọng,thậm chí thât bại của hthống.

VD : 1 hệ thống phóng tên lửa hay nhà máy điện ngtử,có thể dễ ràng nhận ra sự nghiêm trọng của tbại nếu xảy ra.như 1 máy ATM,kniệm tbại ko rõ ràng bằng tbại trong các hthống trên

>1 Hệ thống tbại là 1 hthống ko thể thỏa mãn 1 hay 1 số ycầu được đề cập trong phần đặc tả hthống.

> ĐN # : 1 hệ tgt là 1 hthống mà sự chính xác logic của nó đc dựa trên cả sự cxác của đầu ra và sự đúng thời điểm của chúng.

Các hệ tgt thường là các hệ tương tác hay hệ nhúng.Các hệ tương tác là n~ hệ mà việc xếp lịch trình bị tác động bởi kquả ttác với mtrường,vd: 1 hthống đk cháy pthuộc vào kquả tương tác với các nút nhấn bởi ng phi công.Các hệ thống nhúng là những hệ được tìm thấy trong các hthống ko phải là 1 máy tính.vd : 1 xe otô chứa nhiều mtính nhúng đkhiển việc phun xăng,bung túi khí...các tbị như tivi,hthống âm thanh,máy giặt...

Cả 3 hệ thống được đề cập ở trên đều thỏa mãn các tiêu chuẩn của một hệ thời gian thực. Một máy bay phải xử lý dữ liệu từ gia tốc kế trong một khoảng thời gian nào đó phụ thuộc vào các đặc tả của máy bay, ví dụ như cứ 10 mili giây một lần. Không làm được việc đó có thể làm cho máy bay xác định sai vị trí, đường bay, thông báo tốc độ không chính xác và làm cho máy bay đi sai đường, thậm chi gây ra tai nạn. Với một bài toán lò phản ứng hạt nhân, không đáp ứng nhanh có thể làm nóng chảy lò phản ứng. Cuối cùng một hệ thống bán vé máy bay phải phản ứng với lượng lớn khách hàng trong một khoảng thời gian chấp nhận được (ít nhất là trước khi máy bay cất cánh). Tóm lại, một hệ thống không nhất thiết phải xử lý dữ liệu trong các khoảng mili giây mới được gọi là hệ thời gian thực, nó chỉ đơn giản phải có các ràng buộc về thời gian đáp ứng. 

>Một hệ thống thời gian thực mềm là một hệ thống mà kết quả của nó giảm đi chứ không mất đi khi không thỏa mãn các ràng buộc về thời gian đáp ứng. 

Ngược lại, các hệ thống thời gian thực cứng là các hệ thống mà nếu không thỏa mãn được các ràng buộc về thời gian đáp ứng có thể gây ra những thảm họa thực sự. 

VD về các hthống tgt cứng mềm và vững : hthống ksoát vkhí đtử hàng không,Máy nhặt cỏ,máy ATM

>Một hệ thống thời gian thực vững là một hệ thống cho phép không thỏa mãn một số thời hạn, khi không thỏa mãn một số thời hạn sẽ không gây ra sự thất bại toàn bộ, nhưng nếu không thỏa mãn quá nhiều có thể gây ra thảm họa thực sự cho hệ thống. 

>ĐN sự kiện :Bất kỳ sự việc nào làm cho chương trình chuyển hướng không tuần tự được coi là một thay đổi của dòng điều khiển,  và được gọi là một sự kiện. 

>Thời gian giải phóng là thời điểm một thể hiện của tác vụ đãc  được lập lịch sẵn sàng chạy, và nó thường đi cùng với một ngắt. 

1.1.3.1Các sự kiện đồng bộ và không đồng bộ 

Một sự kiện có thể là đồng bộ (synchronous) hoặc không đồng bộ (asynchronous). Các sự kiện đồng bộ là những sự kiện xảy ra tại những thời điểm được dự đoán trước trong dòng điều khiển

1.1.3.2Tính tiền định

Trong bất kỳ hệ thống nào, hệ thống nhúng không phải là ngoại lệ, việc duy trì điều khiển là rất quan trọng. Với một hệ thống vật lý bất kỳ có những trạng thái nào đó tồn tại mà hệ thống không kiểm soát được, khi đó phần mềm điều khiển phải cố gắng tránh những trạng thái đó. Ví dụ như một hệ thống dẫn đường máy bay nào đó, việc quay nhanh 1800 có thể gây ra mất kiểm soát hồi chuyển. Phần mềm phải có khả năng đoán trước được và ngăn chặn tình huống này. 

>Một hệ thống được xem là có tính tiền định nếu như với mỗi trạng thái có thể xuất hiện và mỗi tập đầu vào, hệ thống có thể đưa một tập đầu ra duy nhất và trạng thái tiếp theo. Tính tiền định sự kiện có nghĩa là các trạng thái kế tiếp và các đầu ra của hệ thống đã được định trước tương ứng với mỗi tập đầu vào gây ra các sự kiện. Vậy, một hệ thống có tính tiền định là một hệ thống có tính tiền định sự kiện. Mặc dù khó có thể quyết định một hệ thống là tiền định khi chỉ dựa vào các đầu vào gây ra các sự kiện, do vậy tiền định sự kiện không có nghĩa là tiền định. 

Cũng cần chú ý rằng rất khó để có thể thiết kế các hệ thống hoàn toàn có tính tiền định sự kiện, chúng ta không thể tránh khỏi việc kết thúc quá trình thiết kế bằng một hệ thống không tiền định. Nhưng cũng rất khó để chủ động thiết kế một hệ thống không tiền định. Tình huống này nảy sinh do sự khó khăn trong việc thiết kết các bộ sinh số ngẫu nhiên hoàn toàn. Ví dụ như khi chúng ta thiết kế các hệ thống máy đánh bạc, chúng ta mong muốn xây dựng những hệ thống chủ động không tiền định. 

Nếu như trong một hệ thống tiền định thời gian đáp ứng của mỗi tập đầu ra được xác định trước thì hệ thống cũng biểu diễn một tiền định theo thời gian. 

Một lợi ích của thiết kế các hệ thống tiền định là có thể đảm bảo rằng hệ thống sẽ có khả năng phản hồi ở bất kỳ thời điểm nào, và với hệ thống tiền định theo thời gian, chúng ta biết khi nào chúng sẽ phản hồi. 

1.1.4   Về mặt cấu tạo, RTS thường được cấu thành từ các thành tố chính sau :

+ Đồng hồ thời gian thực: Cung cấp thông tin thời gian thực.

+ Bộ điều khiển ngắt: Quản lý các biến cố không theo chu kỳ.

+ Bộ định biểu: Quản lý các quá trình thực hiện.

+ Bộ quản lý tài nguyên: Cung cấp các tài nguyên máy tính.

+ Bộ điều khiển thực hiện: Khởi động các tiến trình.

Các thành tố trên có thể được phân định là thành phần cứng hay mềm tùy thuộc vào hệ thống và ý nghĩa sử dụng. Thông thường, các RTS được kết hợp vào phần cứng có khả năng tốt hơn so với hệ thống phần mềm có chức năng tương ứng và tránh được chi phí quá đắt cho việc tối ưu hóa phần mềm. Ngày nay, chi phí phần cứng ngày càng rẻ, chọn lựa ưu tiên phần cứng là một xu hướng chung.

1.1.5  Hệ điều hành thời gian thực:

Hệ điều hành thời gian thực (RTOS-Realtime operating system) là hệ điều hành (HĐH) có sự chú trọng giải quyết vấn đề đòi hỏi khắc khe về thời gian cho các thao tác xử lý hoặc dòng dữ liệu. Đây là HĐH hiện đại, tinh vi, thời gian xử lý nhanh, phải cho kết quả chính xác trong thời gian bị thúc ép nhanh nhất. RTOS thường sử dụng một đồng hồ hệ thống có cho kỳ ngắt nhỏ vào khoảng vài micro giây để thực hiện điều phối các tiến trình.

1.1.6Tận dụng CPU

Thuật ngữ cuối cùng và quan trọng nhất cần phải định nghĩa là một công cụ cho phép đo được hoạt động của hệ thời gian thực. Vì trong mô hình von Neumann, CPU liên tục lấy, giải mã, và thực thi các lệnh khi nào nó còn có nguồn điện, như vậy CPU sẽ thực thi các lệnh bất kỳ, có thể các lệnh không chạy được, cách lệnh không liên quan tới việc thỏa mãn các thời hạn. Định lượng thời gian sử dụng để thực hiện tiến trình nhàn rỗi theo cách nào đó thể hiện thời gian xử lý đã dùng là bao nhiêu? 

Hệ số tận dụng CPU hay hệ số thời gian tải (time loading) U là một đơn vị tính theo phần trăm của các xử lý không phải nhàn rỗi. 

Một hệ thống được gọi là quá tải thời gian nếu U > 100%. Các hệ thống mà CPU được dùng quá nhiều cũng không tốt vì rất khó thêm các thay đổi và các công việc nảy sinh vào hệ thống mà không gây ra quá tải. Các hệ thống không được tận dụng đúng mức cũng không hẳn là tốt, vì điều này nói lên rằng hệ thống còn có thể được chạy với phần mềm rẻ hơn. Khi mà mức độ tận dụng 50% là phổ biến cho những sản phẩm mới, chúng ta có thể dùng mức độ 80% cho những hệ thống ít có biến động lớn. Tuy nhiên 70% là mục tiêu mà chúng ta đặt ra cho U trong hầu hết các hệ thống thời gian thực khi các tác vụ là theo chu kỳ và độc lập nhau

1.2Các vấn đề về thiết kế Hệ thời gian thực ( RTS)

RTS là một nhánh con phức tạp của công nghệ về hệ thống máy tính và nó bị ảnh hưởng nhiều bởi lý thuyết điều khiển, công nghệ phần mềm và vận trù học 

Việc thiết kế và thực thi RTS đòi hỏi phải quan tâm tới nhiều vấn đề. Những vấn đề đó bao gồm: 

Việc lựa chọn phần cứng và phần mềm, đánh giá sự thỏa hiệp cần thiết để có được một lời giải có chi phí hợp lý, liên quan tới hệ thống tính toán phân tán, và những vấn đề về xong xong và đồng bộ. 

Đặc tả và thiết kế RTS và việc biểu diễn chính xác các hành động phụ thuộc thời gian (temporal behavior). 

Hiểu được các sắc thái của các ngôn ngữ lập trình (NNLT) và các ứng dụng thời gian thực (TGT) khi NNLT được dịch sang mã máy. 

Tối đa khả năng chịu lỗi và độ tin cậy của hệ thống thông qua thiết kế chi tiết cẩn thận. 

Việc thiết kế và kiểm soát các lần kiểm thử và việc lựa chọn công cụ phát triển và kiểm thử. 

Tận dụng công nhệ và khả năng tương kết của các hệ thống mở. Một hệ thống mở là một tập hợp lớn các ứng dụng được viết độc lập tương tác với nhau để hoạt động như một hệ thống được tích hợp. Ví dụ như một số phiên bản của hệ điều hành mở Linux đã sử dụng ứng dụng thời gian thực. Khả năng tương kết có thể được định lượng theo khả năng tuân theo những tiêu chuẩn của hệ mở như chuẩn thời gian thực CORBA. 

Cuối cùng, việc định lượng và dự đoán thời gian phản hổi và giảm thiểu thời gian đó. Tiến hành phân tích khả năng xếp lịch, có nghĩa là xác định và đảm bảo thỏa mãn các thời hạn. Đây là tâm điểm của hầu hết các lý thuyết xếp lịch. 

Các kỹ thuật sử dụng cho các RTS cứng cũng có thể được sử dụng cho các loại hệ thống khác để mang lại những cải thiện về hiệu quả và tốc độ. Đây là một trong những lý do chúng ta nên nghiên cứu về RTS. 

1.3Ví dụ về RTS

Chúng ta có thể thấy sự có mặt phổ biến của các hệ thống thời gian thực nhúng, chúng ta có thể tìm thấy chúng trong các thiết bị gia dụng và đồ chơi. Chúng ta có thể tham khảo như trong bảng 1.4. 

Bảng 1.4: Một số lĩnh vực ứng dụng của RTS

Lĩnh vựcỨng dụng

Hàng khôngĐịnh hướng đường bay

MultimediaTrò chơi

Thiết bị mô phỏng/mô hình hóa

Y tếPhẫu thuật robot

Phẫu thuật từ xa

Các hệ thống công nghiệpCác đường dây sản xuất sử dụng robot

Hệ thống tự động theo dõi/giám sát

Dân sựĐiều khiển thang máy

Các hệ thống tự động hóa

1.4Những nhận thức sai về RTS hay gặp

Để hiểu được bản chất của RTS, chúng ta cũng nên biết một số nhận thức sai về RTS thường gặp. Chúng ta có thể tóm tắt như sau: 

1.Các hệ thống thời gian thực đồng nghĩa với các hệ thống nhanh. 

2.Phân tích đơn nguyên tỷ lệ (rate-monotonic) đã giải quyết vấn đề thời gian thực. 

3.Có những phương pháp được chấp nhận toàn cầu cho việc đặc tả và thiết kế các RTS. 

4.Không cần phải thiết kế các hệ điều hành thời gian thực từ đầu vì đã có nhiều sản phẩm trên thị trường 

5.Việc nghiên cứu RTS chủ yếu là nghiên cứu về (lý thuyết) xếp lịch (scheduling). 

Nhận thức sai lầm đầu tiên, RTS là những hệ thống nhanh, xuất phát từ sự thật rằng nhiều hệ thống thời gian thực cứng phải đáp ứng với ràng buộc là các thời hạn trong những khoảng 1/10 miligiây, ví dụ như hệ thống định hướng máy bay. Nhưng những hệ thống như hệ thống nước xốt mì ở trên có thể các bình di chuyển dọc theo băng chuyền qua một điểm cho trước trong mỗi khoảng 2 giây. Hệ thống đặt vé máy bay có thời hạn là 15 giây. Những thời hạn như vậy không phải là nhanh, nhưng đáp ứng được chúng sẽ mang lại thành công cho hệ thống. 

Nhận thức sai lầm thứ 2, các hệ thống đơn nguyên tỷ lệ đưa gia lời giải cho việc xây dựng các hệ thống thời gian thực. Các hệ thống đơn nguyên tỷ lệ - một hệ thống mang tính chu kỳ (periodic system) trong đó ưu tiên ngắt được xác định sao cho tần suất thực thi cao hơn thì sẽ có ưu tiên ngắt cao hơn – hệ thống này nhận được quan tâm nhiều từ những năm 1970. Trong khi chúng đưa ra định hướng thiết kế RTS và cũng có nhiều lý thuyết hỗ trợ cho chúng thì chúng cũng không phải là thuốc chữa bách bệnh. Các hệ thống đơn nguyên tỷ lệ sẽ được nghiên cứu kỹ hơn sau này. 

Còn nhận thức sai lầm thứ 3 thì sao?  Thật không may là tới nay vẫn chưa có những phương pháp được chấp nhận toàn cầu và được chứng minh đầy đủ cho việc thiết kế và đặc tả RTS. Vấn đề này không phải là thất bại của những nhà khoa học hay thất bại của lĩnh vực công nghiệp phần mềm mà do việc quá khó để bao trùm toàn bộ các lời giải. Sau hơn 30 năm nghiên cứu chúng ta vẫn chưa có một phương pháp nào trả lời tất cả các vấn đề của việc thiết kế và đặc tả thời gian thực trong mọi bối cảnh. 

Nhận thức sai lầm thứ 4 là không cần phải xây dựng một hệ điều hành thời gian thực hoàn toàn mới. Hiện tại đã có một số hệ điều hành thời gian thực có tính thương mại, chi phí hợp lý, phổ biến, nhưng chúng không phải là liều thuốc chữa bách bệnh. 

*Các KN liên quan

Hệ tương tác: Liên tục tương tác với môi trường 

Hệ nhúng: hệ thống máy tính được đóng gói bên trong môi trường của nó (thiết bị mà nó điều khiển), sự kết hợp giữa phần cứng máy tính và phần mềm và được dành cho mục tiêu cụ thể. 

Hệ thống cần an toàn cao(safty-critical system): sự thất bại của hệ thống có thể gây ra thương vong, tử vong hay những mất mát tài chính lớn. 

Một hệ thống thất bại: là một hệ thống không thể thỏa mã một hay một số yêu cầu được đề cập trong phần đặc tả hệ thống 

*Phân loại RTS : Mềm (Soft): hệ thống giảm sút hiệu suất nhưng không bị hỏng dù không đáp ứng được các yêu cầu về thời gian đáp ứng.

Cứng (Hard): bỏ lỡ dù chỉ 1 thời hạn sẽ dẫn đến hậu quả nghiêm trọng và làm hệ thống hỏng hoàn toàn.

Nhũn (Firm): bỏ lỡ 1 vài thời hạn không làm hỏng hệ thống, nhưng bỏ lỡ nhiều hơn vài thời hạn sẽ làm hệ thống hỏng hoàn toàn

>ĐẶc trưng RTS :Phần cứng và phần mềm đi cùng nhau: Sử dụng phần cứng có chức năng đặc biệt và có kiến trúc đặc biệt 

Điều khiển đồng thời các thành phần riêng rẽ của hệ thống: các thiết bị hoạt động song song trong thế giới thực

Độ an toàn và tin cậy cực cao: RTS thường là hệ thống yêu cầu an toàn cao

>Từ đâu có thời hạn :Thời hạn xuất phát từ các hiện tượng vật lý của hệ thống đang điều khiển

Ví dụ: trong hệ thống hiển thị hoạt ảnh, các ảnh phải được cập nhật khoảng 30 khung hình trong một giây. Trong hệ thống định hướng/dò đường các thông tin gia tốc kế phải được đọc với một tỉ lệ dựa trên tốc độ tối đa của phương tiện

Đôi khi một số hệ thống xác định thời hạn dựa vào dự đoán 

 Hiểu được cơ sở và bản chất của các ràng buộc về thời gian để từ đó có thể xử lý chúng hiệu quả 

>Hệ số sd cpu :Hệ số tận dụng CPU hay hệ số thời gian tải (time loading) U là một đơn vị tính theo phần trăm của các xử lý không phải nhàn rỗi

Một hệ thống được gọi là quá tải thời gian nếu U > 100%

  Hệ số tận dụng 50% là phổ biến cho những sản phẩm mới, chúng ta có thể dùng mức độ 80% cho những hệ thống ít có biến động lớn. Tuy nhiên 70% là mục tiêu mà chúng ta đặt ra cho U trong hầu hết các hệ thống thời gian thực khi các tác vụ là theo chu kỳ và độc lập nhau 

>Ví dụ RTS :xét một hệ thống giám sát cho một dây chuyền phản ứng hạt nhân, nó sẽ kiểm soát 3 sự kiện thông qua ngắt. Sự kiện đầu tiên được kích hoạt bởi một trong số các tín hiệu ở nhiều điểm kiểm soát an ninh khác nhau, tín hiệu đó cho biết có sự xâp nhập an ninh. Hệ thống phải phản hồi lại tín hiệu này trong vòng 1 giây. Sự kiện thứ 2 (và là sự kiện quan trọng nhất) là nó chỉ ra rằng lõi hạt nhân đạt tới sự quá tải về nhiệt độ. Tín hiệu này phải được trả lời/giải quyết trong vòng 1 miligiây. Cuối cùng là việc cập nhật thông tin cho một màn hình điều khiển khoảng 30 lần mỗi giây. Hệ thống dây chuyền hạt phản ứng nhân yêu cầu một kỹ thuật để đảm bảo rằng chỉ số “Sắp xảy ra nóng chảy lõi hạt nhân” có thể ngắt bất kỳ tiến trình nào khác. Làm sao để đạt được việc này? 

>Lich su phat trien :1940s, 1950s: xuất hiện các hệ thống thời gian thực phục vụ một số ứng dụng cụ thể (chủ yếu trong quốc phòng).

1960s: tiền thân của hệ điều hành thời gian thực (IBM Basic Executive).

1970s: hệ điều hành thời gian thực RSX, RTE cho minicomputers (DEC, HP).

1973: lý thuyết về các hệ thống tần suất đơn điệu (rate monotonic) (Liu và Layland).

1980s: hệ điều hành thời gian thực cho microcomputers (RMX-80, MROS 68K…).

1983: Ada83, ngôn ngữ lập trình cho các hệ thống thời gian thực (US DoS).

1995: Ada95.

II. Mo hinh tac vu TGT :Tác vụ thời gian thực là một thực thể cơ bản thực thi được và được lập lịch, có thể là tác vụ có chu kỳ và tác vụ không có chu kỳ. 

Chia làm tác vụ có ràng buộc thời gian cứng và tác vụ có ràng buộc thời gian mềm

Mộ mô hình tác vụ thời gian thực được định nghĩa thông qua các tham số thời gian chính yếu

>Tham số chính của tác vụ :r: thời điểm giải phóng tác vụ, có nghĩa là thời điểm bắt đầu có yêu cầu thực thi tác vụ

C: thời gian tính toán tác vụ trong trường hợp xấu nhất và bộ xử lý được cấp đầy đủ cho tác vụ

D: thời hạn tương đối của tác vụ, có nghĩa là trễ tối đa có thể chấp nhận được cho xử lý của tác vụ

T: khoảng thời gian tác vụ (chỉ đúng cho tác vụ có chu kỳ). 

Khi tác vụ có ràng buộc thời gian thực cứng thì với một thời hạn tương đối ta có thể tính toán thời hạn tuyệt đối (absolute deadline: thời điểm phải hoàn thành cho lần thực thi tác vụ). d = r + D. Việc vượt qua thời hạn tuyệt đối gây nên lỗi thời gian

>Lưu ý :Tham số T chỉ áp dụng cho các tác vụ có chu kỳ, còn tác vụ không có chu kỳ thì không áp dụng được

Thời điểm giải phóng yêu cầu của tác vụ có chu kỳ với r0 là lần giải phóng đầu: 

rk = r0 + kT, với rk là lần giải phóng thứ k+1

Thời hạn tuyệt đối: dk = rk + D. Nếu D = T, tác vụ có chu kỳ có thời hạn tương đối bằng với khoảng thời gian 

Một tác vụ được hình thành tốt nếu 0 < C <= D <= T 

>Mô hình tổng quát :t(r0, C, D, T) với 0 <= C <= D <= T

r0: thời điểm giải phóng yêu cầu đầu tiên của tác vụ

C: Thời gian tính toán của tác vụ trong trường hợp xấu nhất 

D: thời hạn tương đối

T: khoảng thời gian

rk: thời điểm giải phóng của yêu cầu thứ k+1 của tác vụ

rk = r0 + kT được biểu diễn bởi (mũi tên lên)

dk: thời hạn tuyệt đối của yêu cầu thứ k + 1 của tác vụ

dk = rk + D được biểu diễn bởi (Mũi tên xuống)

> CÁC tham số động của tác vụ :

Các tham số động sau giúp chúng ta theo dõi quá trình thực thi của tác vụ: 

s là thời điểm bắt đầu thực thi tác vụ

e là thời điểm kết thúc thực thi tác vụ

D(t) = d – t là thời hạn tương đối còn lại vào thời điểm t: 0  D(t)  D. 

C(t) là thời gian thực thi còn lại (chưa thực thi) vào thời điểm t: 0  C(t)  C

L = D – C là trễ trên danh nghĩa của tác vụ (cũng được gọi là thời gian trống) và nó cho biết khoảng trễ tối đa cho thời điểm bắt đầu s khi nó có toàn quyền sử dụng bộ xử lý 

L(t) = D(t) – C(t) là độ trễ trên danh nghĩa còn lại của tác vụ vào thời điểm t, nó cho biết khoảng trễ tối đa để quay lại thực thi khi nó có toàn quyền sử dụng bộ xử lý; chúng ta cũng có L(t) = D + r – t – C(t). 

TR = e – r là thời gian phản hồi của tác vụ, chúng ta có C  TR   D khi không có lỗi thời gian 

>Trạng thái của tác vụ : Khi đã được tạo ra, một tác vụ biến đổi giữa hai trạng thái: Bị động và được kích hoạt. Chia sẻ bộ xử lý và tài nguyên sẽ làm xuất hiện nhiều trạng thái tác vụ mới: 

Được chọn (elected): một bộ xử lý được cấp phát cho tác vụ; C(t) và D(t) giảm, L(t) không giảm. 

Bị khoá (blocked): tác vụ đợi một tài nguyên, một thông điệp hay một tín hiệu đồng bộ; L(t) và D(t) giảm. 

Sẵn sàng (ready): tác vụ đợi để được chọn, trong trường hợp này L(t) và D(t) giảm. 

Bị động: tác vụ hiện tại không có yêu cầu nào 

Không tồn tại: tác vụ không được tạo ra 

>Khi đã được tạo ra, một tác vụ biến đổi giữa hai trạng thái: Bị động và được kích hoạt. Chia sẻ bộ xử lý và tài nguyên sẽ làm xuất hiện nhiều trạng thái tác vụ mới: 

Được chọn (elected): một bộ xử lý được cấp phát cho tác vụ; C(t) và D(t) giảm, L(t) không giảm. 

Bị khoá (blocked): tác vụ đợi một tài nguyên, một thông điệp hay một tín hiệu đồng bộ; L(t) và D(t) giảm. 

Sẵn sàng (ready): tác vụ đợi để được chọn, trong trường hợp này L(t) và D(t) giảm. 

Bị động: tác vụ hiện tại không có yêu cầu nào 

Không tồn tại: tác vụ không được tạo ra 

>Các đặc trưng khác của tác vụ :

Một số tác vụ khi đã được chọn không được dừng lại trước khi hoàn thành thực thi, chúng được gọi là các tác vụ không thể tước quyền (non-preemtive tasks). 

Ngược lại, khi một tác vụ đã được chọn có thể được dừng lại và khởi động lại ở trạng thái sẵn sàng để cấp phát bộ xử lý cho tác vụ khác được gọi là một tác vụ có thể tước quyền (preemtive tasks)

Độ phụ thuộc của tác vụ (dependancey of task): Các tác vụ tương tác theo thứ tự bộ phận có nghĩa là cố định hay do việc truyền một thông điệp hay bằng cách đồng bộ tường minh. Điều này tạo ra mối quan hệ trước – sau (precedence relationships) giữa các tác vụ. Quan hệ trước sau được biết trước khi thực thi, có nghĩa là chúng tĩnh  

Tính khẩn cấp (Urgency): thời hạn tác vụ cho phép đặc tả tính khẩn cấp của dữ liệu được tác vụ đó cung cấp. Hai tác vụ có cùng độ khẩn cấp được cho cùng deadline. 

Độ quan trọng (importance): Khi một số tác vụ của một tập có khả năng vượt qua các lỗi thời gian và tránh việc lan truyền lỗi thời gian, hệ thống điều khiển có thể tạm ngưng thực thi của một số tác vụ. Hệ thống phải biết rõ tác vụ nào được ngưng đầu tiên hay nói cách khác tác vụ nào là cần thiết cho ứng dụng và không nên bị ngưng thực thi. Một tham số độ quan trọng được sử dụng để nói lên tầm quan trọng của một tác vụ. Hai tác vụ có cùng độ khẩn cấp  (có cùng deadline) có thể được phân biệt bởi độ quan trọng khác nhau. 

>Phân loại ttoán lập lịch :

Lập lịch offline: lập lịch offline xây dựng một dãy kế hoạch hoàn thiện với tất cả các thông số cho tập tác vụ. Lịch biểu được biết trước khi tác vụ thực thi và có thể được cài đặt một cách hiệu quả. Tuy nhiên, phương pháp tiếp cận này là tĩnh và rất cứng nhắc, nó giả sử tất cả các tham số, gồm cả thời điểm giải phóng là cố định và nó không thể thích nghi với thay đổi môi trường 

Lập lịch online cho phép chọn ở bất kỳ thời điểm nào tác vụ được chọn tiếp theo và nó có kiến thức về tham số của các tác vụ đã được kích hoạt hiện thời. 

Khi một sự kiện mới xảy ra thì tác vụ được chọn có thể bị thay đổi mà không quan tâm tới việc có biết trước sự xuất hiện của sự kiện này hay không. 

Cung cấp các phát biểu ít chính xác hơn so với cách tiếp cận tĩnh vì nó sử dụng ít thông tin hơn. 

quản lý sự xuất hiện bất ngờ của các tác vụ và cho phép việc tạo ra luỹ tiến dãy kế hoạch 

>Lập lịch có thể tước quyền và kô thể tước quyền:

Trong lập lịch có tước quyền, một tác vụ được chọn có thể bị tước ưu tiên và bộ xử lý được cấp phát cho một tác vụ khẩn cấp hơn hay một tác vụ khác có độ ưu tiên cao hơn, tác vụ bị tước ưu tiên được chuyển sang trạng thái sẵn sàng và đợi được chọn lại sau đó.

Lập lịch có thể tước quyền có thể sử dụng được với các tác vụ có thể tước quyền.

 Lập lịch không thể tước quyền không cho dừng thực thi một tác vụ đang thực thi. 

Một trong những yếu điểm của lập lịch không thể tước quyền là có thể xuất hiện lỗi thời gian mà thuật toán có thể tước quyền có thể dễ dàng tránh được. Trong kiến trúc một bộ xử lý, chia sẻ tài nguyên quan trọng dễ hơn với lập lịch không thể tước quyền vì nó không cần kỹ thuật truy cập cho loại trừ lẫn nhau và xếp hàng tác vụ. Tuy nhiên, sự đơn giản của nó không phù hợp với kiến trúc đa xử lý. 

>Lập lịch tập trung và phân tán :

Lập lịch được gọi là tập trung khi nó được cài đặt trên một kiến trúc tập chung hay trên một địa điểm có đặc quyền ghi lại các tham số của tất cả các tác vụ của một kiến trúc phân tán. 

Lập lịch được gọi là phân tán khi mỗi địa điểm định nghĩa lập lịch địa phương sau đó có thể có hợp tác giữa các địa điểm để tạo nên một chiến lược lập lịch toàn cục. Trong ngữ cảnh này, một số tác vụ có thể được gán cho một địa điểm, và rồi di cư sau đó 

>Một số khái niệm liên quan lịch biểu :Lịch biểu khả thi (feasible schedule): Một thuật toán lập lịch tạo một lịch biểu cho tập tác vụ. Lịch biểu này là khả thi nếu như tất cả các tác vụ thoả mãn ràng buộc thời gian. 

Tập tác vụ lập lịch được: một tập tác vụ được gọi là lập lịch được khi thuật toán lập lịch có thể đưa ra một lịch biểu khả thi cho tập tác vụ đó. 

Thuật toán lập lịch tối ưu: một thuật toán được gọi là tối ưu nếu nó có thể tạo ra một lịch biểu khả thi cho bất kỳ tập tác vụ lập lịch được nào

Kiểm tra khả năng lập lịch được: Một sự kiểm tra tính lập lịch được cho phép xác định một tập tác vụ có chu kỳ có thể sử dụng một thuật toán lập lịch nào đó và đưa ra một lịch biểu khả thi hay không

Kiểm tra chấp nhận: Lập lịch online tạo ra và chỉnh sửa lịch biểu động khi có các yêu cầu tác vụ mới được kích hoạt hay khi có một thời hạn bị lỡ. Một yêu cầu mới có thể được chấp nhận nếu như tồn tại ít nhất một lịch biểu cho phép tất cả các tác vụ được chấp nhận trước đó và cả yêu cầu này nữa thoả mãn thời hạn của chúng. 

Trong lập lịch phân tán, việc từ chối một yêu cầu bởi một địa điểm sau khi thực hiện kiểm tra chấp nhận có thể làm cho yêu cầu đó di cư 

>Các khái niệm lập lịch

Lập lịch tập tác vụ liên quan tới việc lên kế hoạch thực thi các yêu cầu của các tác vụ sao cho thoả mãn các ràng buộc thời gian: 

Của tất cả các tác vụ khi hệ thống chạy ở chế độ bình thường

Của ít nhất các tác vụ quan trọng (nghĩa là các tác vụ cần thiết để giữ tiến trình được kiểm  soát an toàn) trong chế độ bất thường. 

Của tất cả các tác vụ khi hệ thống chạy ở chế độ bình thường

Của ít nhất các tác vụ quan trọng (nghĩa là các tác vụ cần thiết để giữ tiến trình được kiểm  soát an toàn) trong chế độ bất thường 

Thuật toán lập lịch gán các tác vụ cho các bộ xử lý và cung cấp một danh sách thứ tự các tác vụ gọi là dãy kế hoạch hay là lịch biểu. 

Quay vòng tuần tự: các tiến trình thực hiện tuần tự cho đến khi kết thúc.

Quay vòng và phân chia thời gian: mỗi tiến trình được gán một lượng thời gian cố định để thực hiện. Khi chạy hết thời gian được cấp, nếu chưa hoàn thành, nhiệm vụ sẽ được lưu lại ngữ cảnh và chuyển tới cuối danh sách thực hiện.

Quay vòng kết hợp với giành quyền ưu tiên: các tiến trình có cùng mức ưu tiên được thực hiện theo chế độ quay vòng, nhưng có thể bị giành quyền bởi tiến trình có mức ưu tiên cao hơn

>Cyclic executive :CE là bộ lập lịch trong khi chạy: có nhiệm vụ xen kẽ và tuần tự hóa việc thực hiện các nhiệm vụ trên 1 CPU theo 1 lịch trình đã lập trước.

CE đưa ra các quyết định theo chu kỳ: khoảng thời gian giữa các quyết định này được gọi là khung (frame) hay chu trình nhỏ (minor cycle)  giành quyền không được xảy ra bên trong các khung.

Chu trình lớn hay siêu chu kỳ (major cycle/hyper-period): khoảng thời gian tối thiểu trong đó mọi tiến trình đều kết thúc chu kỳ thực hiện  chu trình lớn có độ dài đúng bằng bội số chung nhỏ nhất của các chu kỳ p1, p2,…, pn với hệ thống có n nhiệm vụ t1, t2,…, tn.

>So sanh EDF va RMA :EDF mềm dẻo hơn và do đó hiệu quả hơn về mặt sử dụng thời gian của CPU: không có chuyện CPU không làm gì khi vẫn còn nhiệm vụ đang chờ, điều vẫn có thể xảy ra với RMA.

Về mặt hành vi, hệ thống sử dụng RMA dễ dự liệu hơn: trong trường hợp quá tải, với RMA chỉ có các nhiệm vụ có mức ưu tiên thấp mới bị lỡ hạn, còn các nhiệm vụ có mức ưu tiên cao không bị ảnh hưởng, trong khi với EDF không thể nói trước nhiệm vụ nào sẽ bị lỡ hạn.

Với EDF, nhiệm vụ bị lỡ hạn sẽ có mức ưu tiên cao hơn các nhiệm vụ chưa tới hạn  có thể gây lỡ hạn dây chuyền khi hệ thống quá tải  cần cơ chế loại bỏ những nhiệm vụ đã lỡ hạn mà không còn quan trọng.

>Định lý giới hạn của RMA :

Liu (1973): Một tập hợp bao gồm n nhiệm vụ có chu kỳ sẽ lập lịch được bằng phương pháp RM (RM-schedulable) nếu hệ số sử dụng CPU với tập hợp đó thỏa mãn điều kiện sau đây:

U  n(21/n1).

Chú ý: điều kiện trên chỉ là điều kiện đủ 

Khi n -> vô cùng: U -> ln2 =~ 0,69

Điều kiện đủ để lập lịch được n tác vụ có chu kỳ : U = tổng Ci/Ti <= n(2^(1/n)-1)

-----

>Thuật toán đảo ngược deadline gán các độ ưu tiên cho các tác vụ theo thời hạn của chúng: tác vụ với thời hạn tương đối ngắn nhất được gán cho độ ưu tiên cao nhất 

Với một tập tuỳ ý gồm n tác vụ với  các thời hạn ngắn hơn các khoảng thời gian, điều kiện đủ là:  U = tổng Ci/Di <= n(2^(1/n)-1)

---

>Thuật toán thời hạn sớm nhất trước :Nguyên lý: Gán độ ưu tiên cho các tác vụ theo thời hạn tuyệt đối của chúng: tác vụ với thời hạn sớm nhất sẽ được thực thi với độ ưu tiên cao nhất 

Định lý: Xét 1 tập hợp của n nhiệm vụ với giả thiết rằng cho mỗi nhiệm vụ i ta đều có pi = Di. Khi đó, điều kiện cần và đủ để có thể lập lịch cho tập hợp này bằng phương pháp EDF là hệ số sử dụng CPU của tập hợp đó thỏa mãn điều kiện: U <= 1.

----

>Thuật toán độ trễ nhỏ nhất trước : Gán độ ưu tiên cho các tác vụ theo độ trễ tương đối của chúng: Tác vụ với độ trễ nhỏ nhất sẽ được thực thi với độ ưu tiên cao nhất 

Ví dụ của một lịch biểu LLF với tập 3 tác vụ có chu kỳ 1(r0 = 0, C = 3, D = 7, T = 20), 2(r0 = 0, C = 2, D = 4, T = 5), 3(r0 = 0, C = 1, D = 8, T = 10). Độ trễ tương đối của các tác vụ chỉ được tính ở thời điểm tác vụ đến (thời điểm giải phóng) 

Các giá trị độ trễ tương đối của các tác vụ là: 

L(1) = 7 – 3 = 4; L(2) = 4 – 2 = 2; L(3) = 8 – 1 =  7 

-----

>Thuật toán lập lịch ko có chu kỳ mềm :

Lập lịch background: Các tác vụ không có chu kỳ được lập lịch ở background trong khi không có các tác vụ có chu kỳ sẵn sàng thực thi. Các tác vụ không có chu kỳ được xếp hàng theo chiến lược first come first served

ví dụ trong đó có hai tác vụ có chu kỳ 1(r0 = 0, C = 2, T = 5), 2(r0 = 0, C = 2, T = 10) được lập lịch với thuật toán Rm, và 3 tác vụ khôgn có chu kỳ: 3(r = 4, C = 2), 4(r = 10, C = 1) và 5(r = 11, C = 2) được thực thi trong background  

Trộm thời gian trống:Mỗi lần một yêu cầu không có chu kỳ đi vào hệ thống, thời gian phục vụ yêu cầu này được lất bằng cách trộm thời gian xử lý từ các tác vụ có chu kỳ mà không làm lỡ thời hạn. Vì thế, độ trễ của các tác vụ có chu kỳ được sử dụng để lập lịch các yêu cầu không có chu kỳ càng sớm càng tốt 

Với kỹ thuật lập lịch kết hợp: một thời hạn hư cấu fd được định nghĩa cho mỗi tác vụ không có chu kỳ để tác vụ không có chu kỳ có được thời gian phản hồi ngắn nhất có thể. fd được đặt ở thời điểm sớm hơn t, sao cho lượng thời gian xử lý của tác vụ bằng thời gian nhàn dỗi của bộ  xử lý trong khi tất cả các thời hạn của các tác vụ đợi vẫn được thoả mãn. 

---

>So sánh EDF và RMA :EDF mềm dẻo hơn và do đó hiệu quả hơn về mặt sử dụng thời gian của CPU: không có chuyện CPU không làm gì khi vẫn còn nhiệm vụ đang chờ, điều vẫn có thể xảy ra với RMA.

Về mặt hành vi, hệ thống sử dụng RMA dễ dự liệu hơn: trong trường hợp quá tải, với RMA chỉ có các nhiệm vụ có mức ưu tiên thấp mới bị lỡ hạn, còn các nhiệm vụ có mức ưu tiên cao không bị ảnh hưởng, trong khi với EDF không thể nói trước nhiệm vụ nào sẽ bị lỡ hạn.

Với EDF, nhiệm vụ bị lỡ hạn sẽ có mức ưu tiên cao hơn các nhiệm vụ chưa tới hạn  có thể gây lỡ hạn dây chuyền khi hệ thống quá tải  cần cơ chế loại bỏ những nhiệm vụ đã lỡ hạn mà không còn quan trọng.