*Câu 1: Nêu khái niệm lập lịch, phân loại 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.

->Phân loại :

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

Câu 2 : Tư tưởng ttoán lập lịch background cho tập tvụ có chu kỳ hoặc ko có ckỳ mềm:

-Tư tưởng :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

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.

Câu 3: Hiểu biết về lập lịch offline và online:

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 .

Câu 4 : Lập lich có tác vụ thứ tự,phương pháp sửa tham số cho các tvụ có dmục thứ tự khi sd thuật toán EDF để lập lịch

Kiểu ràng buộc trước sau của các tác vụ tgt nếu việc thực thi trước tác vụ Tj hay nói cách khác Tj phải đợi Ti hoàn thành trước khi nó bắt đầu thì ký hiệu Ti->Tj

Ràng buộc thứ tự là thực thi tất định, quan hệ này được mô ta nhờ 1 đồ thị trong đó các nút biểu thị các tác vụ, mui tên biểu diễn ràng buộc theo thứ tự giữa hai nút.Khi tỷ lệ truyền thông giữa các tác vụ không bằng nhau thì kí hiệu T1 --- T1 / 4 T2---->T2

- Để mô tả ràng buộc thứ tự dễ dàng hơn, chúng ta chỉ xét ràng buộc thứ tự đơn giản,nghĩa là nếu tác vụ Ti phải truyền thông kết quả quá trình xư lý của nó cho Tj thì những tác vụ này phải được lập lịch sao cho sự thực thi của thể hiện thứ k của tác vụ Ti thực thi trước thể hiện thứ k của tác vụ Tj

- Nếu Ti > Tj thì nó phải tuân thủ các đk :

+ rj >ri

+ priori > priorj (Thuật toán lập lịch)

*Chúng ta quan tâm tới ngữ cảnh đánh giả của các tác vụ trên 2 quan điểm : thực thị và đánh giá hợp lệ

+ Thực thi dựa vào độ ưu tiên

+ Đánh giá hợp lệ dựa vào khả năng lập lịch

Phương pháp sửa tham số cho các tác vụ có danh mục thứ tự khi sủ dụng Thuật toán :

1. RM

Ti -> Tj

Thỏa mãn 2 điềukiện :

+ rj* >= max {ri,rj*}

+ priori > priorj

Với : rj* là thời điểm bắt đầu của tác vụ j (Khi tác vụ j đã được sửa đổi)

2. Thuật toán EDF : Ti -> Tj thỏa mãn 3 điều kiện

+ rj* >= max{rj,ri*}

+ Dj >= max{Dj,Di*}

+ priori > priorj

Với : rj* là thời điểm bắt đầu của tác vụ j (khi tác vụ j được sửa đổi)

Dj* là thời hạn của tác vụ j (khi tác vụ j được sửa đổi)

3. Thuạt toán thời hạn sơm nhất

trong trường hợp này việc sửa đổi các tham số dựa vào thời hạn đầu tiên : Ti -> Tj

rj* >= max{(ri* +Ci);rj}

Trong đó Ci là time xử lý được tăng thêm

di* >= min{(dj* - Cj);di}

Thủ tục sửa đổi các thời điểm bắt đầu và các thời hạn có thể cài đặt trước khi các tác vụ thực hiện trước. để thay đổi các tác vụ thực hiện sau với thời hạn của chúng

Câu 5 :  * Ý nghĩa HTTGT :

Các hệ thống điều khiển giao thông: Mạng lưới dịch chuyển đường ray, điều khiển giao thông đường bộ, điều khiển giao thông đường không

Các hệ thống điều khiển phương tiện giao thông: Các hệ nhúng trong xe hơi, các tên lửa nối không

Điều khiển dây chuyền: Điều khiển sản xuất, dây chuyền điện nguyên tử, các dây chuyền hóa học

Cơ sở dữ liệu: Hệ thống đặt vé máy bay, dò đường radar

Phân loại HTTGT :

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.

Máy ATM

Mềm

Nếu như không đạt được các thời hạn sẽ không tạo ra các thất bại nghiêm trọng của hệ thống, nó chỉ giảm hiệu quả của hệ thống mà thôi, giảm sự thỏa mãn của khách hàng

Bộ điều khiển định hướng nhúng dùng cho robot nhặt cỏ

Firm

Nếu như không thỏa mãn các thời hạn định hướng quan trọng có thể làm cho robot thay đổi hướng đi không ngừng, mất kiểm soát và phá hoại mùa màng

Hệ thống kiểm soát các vũ khí điện tử hàng không trong đó việc nhấn một nút có thể kích hoạt/phóng một tên lửa không nối hông

Cứng

Việc không thỏa mãn được các thời hạn để phóng tên lửa trong một khoảng thời gian nhất định sau khi ấn nút cho thể làm chệch mục tiêu, và sẽ gây ra thảm họa

Câu 6 .7 Kỹ thuật chấp nhận lỗi :

Ý tưởng cơ bản của kỹ thuật này là dựa vào mô hình tính toán không chính xác, dựa vòa việc đưa ra kết quả có sẵn có chất lượng tương đối nhưng chấp nhận được, có 2 cách tiếp cận được đề xuất : mô hình kỹ thuật thời hạn và mô hình tính toán không chính xác

* Mô hình kỹ thuật thời hạn : mô hình này yêu cầu mỗi tác vụ Ti có 1 c trình chính (Tip) và 1 c trình phụ Tia.

Thuật toán cung cấp chất lượng dịch vụ tốt nhưng với độ dài thời hạn không biết trước, Chương trình phụ tạp ra 1 kết quả chấp nhận được có thể không tốt như mong đợi với độ dài time xác định biết trước.

Để đạt được mục tiêu có thể ấp dụng 2 chiến lược

+ Kỹ thuật cơ hội đầu tiên

  LẬp lịch các c trình phụ trước, c trình chính được lập lịch vào các phần còn lại khi c trình phụ đi kèm đã hoàn thành. Nếu c trình chính kết thục trước thời hạn thì kết quả của nó được thay thế cho kết quả của c trình phụ

+ Kỹ thuật cơ hội cuối cùng : Lập lịch các c trình phụ trong khoảng thời gian muộn nhất c trình chính được lập lich vào các thời gian còn lại trước các c trình phụ di kèm.Bằng cách áp dụng chiến lược này, bộ lập lich sẽ tước quyền thực thi của c trình chính để thực thi c trình phụ tương ứng vào thời điểm phù hợp nhằm thỏa mãn thời hạn . Nếu c trình chính kết thúc thành công thì việc thực thi c trình phụ không cần thiết

-         Kỹ thuật cơ hội cuối cùng tốt hơn về mặt chất lượng dịch vụ và tải xử lý.  Điểm yếu của nó là sự phúc tạp của việc lập lich phải luôn k tra và đảm bảo ở mỗi thời gian vòn lại trước thời hạn có đủ để thực hiện c trình phụ hay không

 Câu 8 : Server : là 1 tác vụ có chu kỳ được lập lịch bằng các thuật toán lập lkichj cho các tác vụ có chu kỳ thứ tự thực hiện của các tác vụ ser ver tùy thuộc vào thuật toán

Một số loại server

+ polling server

+spordie server

+priority exchange server

+ deforable server

Câu 10 : TRình bày tư tưởng RM và EDF

RM  : Với tập các tác vụ có chu kì thì gán ưu tiên cho các tác vụ, nghĩa là tác vụ nào có chu kỳ nhỏ thì gán độ ưu tiên cao hơn.

Địn lý giới hạn của thuật toán RM :

U= xích ma từ i=1 tới n của  (Ci/Ti) <= n(2^(1/n) -1 )

EDF : Gán độ ưu tiên cho các tác vụ theo thời hạn tuyệt doois của chúng (d) tác vụ nào 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 n tác vụ các tạc vụ Ti có thời hạn = khoảng thời gian,Điều kiện cần và đủ để có thể lap lich tap hop nay bang Phuong phap EDF là u <=1 (u=xich ma Ci/Ti)

l      So sánh :

 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.

Câu 11.Quá trình phát hiện quá tải

-Các chính sách sử dụng giá trị độ quan trọng

+ Mỗi tác vụ được đặc trưng bởi thời hạn để đn độ khẩn cấp và giá trị để Đn độ quan trọng của việc thực thi tác vụ tương quan với các tác vụ khác trong TGT

Vào thời điểm t bất kì có x hiện 1 tác vụ có tính chu kỳ hay không có chu kì một sự đảm bảo động được thực thi để tác vụ mới xhien này không làm quá tải bộ xử lý. Sự đảm bảo động tính toán độ trễ của hệ thống vào thời điểm t chính là sự tính toán thời gian tối đa mà bộ xử lý ở trạng thái không làm việc

Độ trễ LCi= Di – xichma Cj(t)  ; dj<di

Độ trễ của hệ thống là LP(t) = min {LCi(t)}

1 tình huống quá tải bị phát hiện ngay khi LP(t) < 0

Sự quá tải được giải quyết nhờ chính sách từ chối dựa vào việc loại bỏ những tác vụ có thời hạn nhỏ hơn hay bằng tác vụ chậm trễ và có giá trị độ quan trọng là nhỏ nhất.

+ Chính sach đa chế độ : Mục tiêu của chính sách này là việc ủng hộ thực thi các tác vụ có giá trị độ quan trong cao nhất ( tức là những tv gặp ít lỗi về thời gian và bị bỏ qua it hơn )

Mỗi tv được đặc trưng bởi hai thuộc tính gọi chung là các thuộc tính thực thi. Nó cho biết 1 tv có thể lỡ 1 lần thực thi.

-         Thuộc tính bỏ dở :  tức là 1 tv có thẻ bị bỏ dở khi thực thi nếu có thể bị dừng lại và không thẻ quay lại tiếp tục thực hiện nữa .

-         Thuộc tính hoãn : tức là nếu yêu cầu của nó có thể bị hủy bỏ như vậy tác vụ với độ quan trọng cao nhất được thực thi khi quá tải xảu ra

+ Chính sách tính toán giá trị độ quan trọng : Với chính sach này giá trị độ quan trọng được gán cho 1 tác vụ tùy theo thời điểm tác vụ được vận hành. Hiểu quả của cs này được tính nhờ việc tích lũy giá trị của các tv hoàn thành trước thời hạn.

Giá trị tích lũy (beta) hệ số cạnh tranh (phi) : Một thuật toán có hệ số cạnh tranh (phi) nếu và chỉ nếu nó có thể đảm bảo 1 giá trị tích lũy (beta) > (phi).(beta*)

Trong đó (beta*) là giá trị tích lũy được khi lập lịch tối ưu.

Câu 12 .Một số khái niệm : Ràng buộc trước sau tương ứng với đồng bộ hay truyền thong giữa các tác vụ

Rằng buộc loại trừ lẫn nhau để bảo vệ tài nguyên chia sẻ