Đọc truyện hdh

hdh

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

Đa bộ xử lý, là gì

-nhiều bộ xử lý chạy ở tốc độ bình thường

- tăng tốc độ tính toán có thể song song hóa được

Đa bộ xử lý, làm thế nào

-cách thức kết nối giữa các tiến trình

+chia sẻ bộ nhớ

+truyền thông điệp

-Đa bộ xử lý chia sẻ bộ nhớ

+chia sẻ không gian địa chỉ

+các chỉ dẫn nạp (LOAD) và lưu trữ (STORE)

+dễ trên các máy quy mô nhỏ

+độ trễ chậm hơn

+làm thế nào để truy cập bộ nhớ chia sẻ

<Truy cập bộ nhớ đồng dạng(UMA)

<Non UMA (NUMA)

Đa bộ xử lý chia sẻ bộ nhớ

Truy cập bộ nhớ đồng dạng

-Bus-dựa trên các cấu trúc

+trao đổi 1 bus cho thông tin

+được giới hạn bởi băng thông bus

+thêm bộ nhớ đệm cho các tiến trình

+thêm các bộ nhớ riêng được sử dụng để lưu trữ: các phần văn bản, dữ liệu chỉ đọc, ngăn xếp, các biến cục bộ

+chỉ được sử dụng cho các hệ thống kích cỡ nhỏ

Giới thiệu về hệ thống thời gian thực

Hệ thống thời gian thực cung cấp các dịch vụ trong khi đáp ứng một số thời gian hạn chế.

+ không nhất thiết phải nhanh, nhưng phải đáp ứng một số thời hạn thời gian.

+ Nhiều hệ thống thời gian thực được nhúng vào như là một phần của một số thiết bị lớn hơn hoặc hệ thống.

. Máy giặt, máy photo, điện thoại di động, oto, máy bay, nhà máy công nghiệp.

. quá trình điều khiển kỹ thuật số, điện thoại và đa phương tiện.

Thường xuyên yêu cầu xác nhận tính đúng đắn.

+ Nhiều hệ thống nhúng thời gian thực là quan trọng an toàn : nếu họ không hoàn thành trong một cơ sở kịp thời và chính xác, kết quả nghiêm trọng.

+ Lỗi trong các hệ thống nhúng thời gian thực thường có thể là khó khăn hoặc chi phí khắc phục : bạn có thể không chỉ cần chạy “ phần mềm cập nhật” trên 1 chiếc xe hơi.

VD: quá trình điều khiển kỹ thuật số.

Các loại của hệ thống thời gian thực.

Hoàn thành theo chu kỳ.

+ Mỗi công việc thực hiện định kỳ.

+ Nhu cầu tài nguyên( ví dụ: máy tính, truyền thông hoặc lưu trữ) không thay đổi đáng kể từ giai đoạn này sang giai đoạn khác.

+ ví dụ: các bộ điều khiển kỹ thuật số và theo dõi thời gian thực.

Chủ yếu là theo chu kỳ.

+ hầu hết các nhiệm vụ thực hiện định kỳ.

+ hệ thống này cũng phải đáp ứng một số sự kiện bên ngoài không đồng bộ ( ví dụ: phục hồi lỗi và các lệnh bên ngoài)

+ ví dụ: hệ thống điện tử hiện đại và hệ thống điều khiển quá trình.

Không đồng bộ , chủ yếu là dự đoán.

+ Hầu hết các nhiệm vụ là không định kỳ

+ Thời gian giữa các thực hiện liên tiếp của một nhiệm vụ có thể khác nhau đáng kể, hoặc các biến thể trong sử dụng tài nguyên trong các giai đoạn khác nhau có thể lớn.

+ Những biến thể có hoặc giới hạn phạm vi hoặc các số liệu thống kê được biết đến.

Không đồng bộ, không thể đoán trước.

+ các ứng dụng phản ứng với các sự kiện bên ngoài và\ hoặc có nhiệm vụ có độ phức tạp cao và biến thời gian chạy.

+ ví dụ : điều khiển thông minh thời gian thực.

Thực hiện cân nhắc

Một số hệ thống nhúng thời gian thực rất phức tạp, thực hiện trên phần cứng hiệu quả cao.

+ Ví dụ : kiểm soát nhà máy công nghiệp, hệ thống điện tử và hệ thống kiểm soát bay.

Tuy nhiên, nhiều là được thực hiện trên phần cứng là chi phí thất, điện năng thấp, hiệu suất thấp nhưng trọng lượng nhẹ và mạnh mẽ.

+ ví dụ: hàng tiêu dung.

+ thường được thực hiện trong C hoặc lắp ráp, lắp đặt trong vòng một vài kilobytes của bộ nhớ, quan tâm tính đúng đắn,

Chúng tôi quan tâm trong chứng minh tính đúng đắn của lịch và nâng cao mức độ trừu tượng trong lập trình hệ thống như vậy.

Các công việc, các nhiệm vụ, quá trình xử lý và tài nguyên.

Một công việc là một đơn vị của công việc lên kế hoạch và thực hiện bởi hệ thống.

+ Một nhiệm vụ T là tập hợp các công việc liên quan j1, j2,…jn cùng một số chức năng.

+ nếu công việc xẩy ra trên một chu kỳ thường xuyên, nhiệm vụ này được gọi là định kỳ.

+ Nếu công việc là không thể đoán trước , nhiệm vụ được gọi là không tuần hoàn ( hoặc không thường xuyên, nếu công việc có thời hạn một lần phát hành)

Công việc thực hiện trên một bộ xử lý và có thể phụ thuộc vào một số tài nguyên.

Bộ vi xử lý là các thiết bị hoạt động trên đó công việc được lên kế hoạch.

+ ví dụ: threads scheduled trên một CPU, lịch trình dữ liệu trên một liên kết truyền dẫn.

Một tài nguyên R là thực thể thụ động mà công việc có thể phụ thuộc

+ ví dụ: hệ thống bộ nhớ, một thiết bị phần cứng.

Thời gian thực hiện của công việc.

Một công việc Ji sẽ thực hiện cho thời gian ei

+ đây là số lượng thời gian cần thiết để để hoàn thành thực hiện của J khi nó thực hiện một mình trên bộ xử lý và có tất cả tài nguyên cần thiết.

+ giá trị của ei phụ thuộc vào độ phức tạp của công việc và tốc độ của bộ vi xử lý, nó có thế khác nhau trên một bộ xử lý do ngành có điều kiện trong công việc, những ảnh hưởng của bộ xử lý caches,…

Thời hạn và hạn chế thời gian.

ví dụ:

Một hệ thống giám sát và điều khiển một hệ thống sưởi.

+ Hệ thống sẽ mất 20ms để khởi động khi bật.

+ Sau khi khởi động, mỗi 100ms hệ thống:

. mẫu và đọc cảm biến nhiệt độ.

. luật điều khiển cho lò để xử lý các bài đọc nhiệt độ, xác định tỷ lệ dòng chảy chính xác của không khí, nhiên liệu và chất làm mát.

. Điều chỉnh lưu lượng dòng chảy để phù hợp với giá trị tính toán.

Hệ thống có thể được mô hình hóa như một nhiệm vụ, T , bao gồm các công việc J0, J1,…, Jk,…

Thời gian phát hành hiệu quả và thời hạn.

Đôi khi thời gian phát hành của một công việc có thể là sau này hơn so với thừa kế của nó, hoặc thời hạn của nó có thể sớm hơn so với quy định cho người tiền nhiệm của nó.

+ Làm cho không có ý nghĩ: lấy được thời gian phát hành có hiệu lực thời hạn có hiệu quả phù hợp với tất cả các ưu tiên hạn chế, và tiến bộ sử dụng mà

+ thời gian giải phóng hiệu quả.

+ Thời hạn hiệu quả.

Hard vs soft real- time systems

Firmness của thời gian hạn chế ảnh đến hệ thống của chúng tôi.

+ Nếu một công việc không bao giờ phải bỏ lỡ thời hạn của nó, hệ thống thời gian thực.

+ Nếu một số thời hạn có thể được bỏ qua thỉnh thoảng với xác suất thấp, sau đó hệ thống được mô tả là thời gian thực mềm.

Thời gian thực cứng và mềm là hai đầu cảu một quang phổ.

+ Trong nhiều hệ thống thực tế, các khó khăn là xác suất và phụ thuộc vào khả năng và hậu quả của sự thất bại.

+ Hệ thống không đảm bảo là luôn luôn đáp ứng thời hạn của nó: Luôn luôn có một số xác suất của sự thất bại.

Periodic Tasks

Một tập hợp các công việc được thực hiện tại các khoảng thời gian thường xuyên có thể được mô hình hóa như là một nhiệm vụ tuần hoàn nhiều hệ thống thực tế phù hợp với mô hình này.

+ Mỗi periodic tasks T1 là trình tự công việc Ji,1, Ji,2,…, Ji,n

+ Giai đoạn φi của nhiệm vụ Ti là thời gian phát hành ri,1 của công việc đầu tiên Ji,1.

+ Thời gian pi của nhiệm vụ Ti là chiều dài tối thiểu thời gian giữa các lần phát hành các công việc liên tiếp .

+ Thời gian hoàn thành, ei của nhiệm vụ Ti là thời gian hoàn thành lớn nhất của tất cả các công việc trong nhiệm vụ.

+ việc sử dụng các nhiệm vụ Ti là ui = ei/ pi và đo phần của thời gian mà nhiệm vụ thực hiện.

Ví dụ : Periodic tasks

Nhiệm vụ rời rạc và không tuần hoàn

Nhiều hệ thống thời gian thực được yêu cầu phải đáp ứng các sự kiện không thể đoán trước được.

Đây là những mô hình như công việc không tuần hoàn, công việc không thường xuyên.

+ Một công việc không tuần hoàn không có thời hạn, một công việc không thường xuyên có thời hạn khi phát hành.

+ Nó thường có thể để mô tả đến công việc đó thoe một số phân phối xác suất.

Sự hiện diện của công việc không tuần hoàn và rải rác rất nhiều phức tạp về một hệ thống

+ Nhiệm vụ lẻ tẻ làm cho việc không thể thiết kế của một hệ thống thời gian thực cứng, trừ khi một số giới hạn có thể được đặt liên tiếp đến thời gian và thời hạn tương đối.

Hệ thống động và tĩnh

Một hệ thống đa xử lý, nếu các công việc có thể di chuyển giữa các bộ xử lý, đó là tĩnh nếu( bộ) công việc bị ràng buộc vào bộ xử lý duy nhất.

Hệ thống tĩnh mong đợi để có hiệu suất kém hơn( về thời gian tổng thể công suất đáp ứng) so với hệ thống động.

Thuật toán lập lịch thời gian thực

Hai bước chính của thuật toán.

+ thuật toán Clock-driven được sử dụng cho các hệ thống chủ yếu là tĩnh, nơi mà tất cả các thuộc tính của tất cả các công việc được biết đến vào thời gian thiết kế, như vậy mà các thuật toán lập kế hoạch offline có thể đc sử dụng.

+ các thuật toán theo định hướng ưu tiên được sử dụng cho các hệ thống động, với 1 kết hợp các nhiệm vụ định kỳ và hướng sự kiện( ko tuần hoàn và/hoặc không thường xuyên), nơi mà hệ thống phải thích ứng với sự kiện thay đổi và điều kiện.

1.Clock- driven scheduling

Quyết định công việc nào được thi hành ở thời điểm t

+ thơi điểm đó đã được chọn trước khi hệ thống thi hành .

+ sử dụng ngắt đồng hồ có tính chu kì. Lập lịch sẽ tỉnh dậy sau mỗi ngắt để thực hiện công việc trong thơi gian tiếp theo.

VD: lò điều khiển Ví dụ, với một ngắt mỗi 100ms

Thông thường trong kỳ hệ thống điều khiển đồng hồ:

• Tất cả các thông số của các công việc thời gian thực được cố định và được biết đến

• Một lịch trình của các công việc được tính ngoại tuyến và được lưu trữ để sử dụng tại thời gian chạy, kết quả là, lập kế hoạch trên tại thời gian chạy có thể được giảm thiểu

• Đơn giản và thẳng về phía trước, không linh hoạt.

Ràng buộc giả định

Tham số của job đều được viết sẵn , cố định.

Thời gian chạy của thuật toán lập lịch không liên quan đến job.

Không thay đổi được simple and straight – forw……

Assumptions - Giả định

•

Đồng hồ định hướng lập kế hoạch đối với các hệ thống xác định

• Một công việc chu kỳ hạn chế mô hình:

• Các thông số của tất cả các nhiệm vụ chu kỳ kỳ được biết đến một ưu tiên

• Đối với mỗi phương thức hoạt động, hệ thống có một số cố định, n, nhiệm vụ chu kỳ.

Đối kỳ mỗi Ti nhiệm vụ, công việc Ji, k là đã sẵn sàng để thực hiện tại thời gian phát hành ri, k và được phát kỳ kỳ đơn kỳ pi thời gian sau khi công việc trước đây như vậy mà ri, k = ri, k-1 + pi

• công việc không tuần hoàn có thể tồn tại, cho rằng hệ thống duy trì một hàng đợi đơn cho công việc không tuần hoàn, và rằng công việc ở phần đầu của hàng đợi này

thực hiện bất cứ khi nào các bộ vi xử lý có sẵn cho công việc không tuần hoàn

• Không có job thường xuyên.

(mô hình giới hạn có tính chu kỳ : tương tự trên/

Số lượng job là cố định

ri,k=ri,k-1+ pi

Các thông điệp ko có tính chu kỳ(xảy ra hoặc có thể tồn tai…)

Notation

Định nghĩa 1 nhiệm vụ thông qua bộ 4 phần tử Ti=(φi, pi, ei, Di)

Pi: khoảng cách 2 job

Di: relative deadline (thời hạn tương đối)

φi : pha thời gain để job mới được thi hành

ei : execution time (thòi gian thi hành)

Nếu không có gì thì mặc định φi = 0, pi= Di.

VD :

T1 = (1, 10, 3, 6)

⇒

1 = 1 ; p1 = 10 ;e1 = 3 ; D1 = 6

T2 = (10, 3, 6)

⇒

2 = 0 ; p2 = 10 ; e2 = 3 ; D2 = 6

T3 = (10, 3)

⇒

φ3 = 0 ;p3 = 10 ;e3 = 3 ; D3 = 10

Static, Clock-driven Cyclic Scheduler

Lịch được tính toán off-line, không ảnh hưởng gì đến bài toán .

Thời gian không liên quan gì đến thuật toán

Có thể tìm một lập lịch tối ưu cho hệ thống, sử dụng lập lịch có chu kỳ.

ví dụ

như xét hệ thống có 4 nhiện vụ định kỳ:

T1 = ( 4, 1.0)

• T2 = ( 5, 1.8) [Phase and deadline take default values- Giai đoạn và thời hạn có giá trị mặc định]

• T3 = (20, 1.0)

• T4 = (20, 2.0)

Bội số chung nhỏ nhất H=20 (bội số chung nhỏ nhất của 4,5,20,20)

Thực hiện một Scheduler Cyclic

Lưu trữ lập lịch trong 1 bảng

Thiết lập ngắt ở thời điểm đầu tiện tk=0.

Khi nhận được một ngắt tại tk

Scheduler thiết lập thời gian ngắt hết hạn tại tk+1

nếu trước đây công việc overrunning, xử lý lỗi.

Job :

+ rảnh thì gọi T(tk) =

+ Nếu không, hãy gọi công việc tiếp theo trong nhiệm vụ T(tk) thi hành

Input: stored schedule (tk, T(tk)) for k = 0, 1, n – 1.

Task SCHEDULER:

set the next decision point i = 0 and table entry k = 0;

set the timer to expire at tk;

do forever:

accept timer interrupt;

if an aperiodic job is executing, preempt the job;

current task T = T(tk);

increment i by 1;

compute the next table entry k = i mod n;

set the timer to expire at [i / n] * H + tk;

if the current task T is I,

let the job at the head of the aperiodic queue execute;

else

let the task T execute;

sleep;

end do.

End SCHEDULER.

Thuật toán Static

Sử dụng ngắt để lập trình

Hệ thống hoạt động sử dụng ngắt đồng hồ

Sau 1 khoảng thời gian lập lịch chấp nhận ngắt

Sử dụng ưu tiên

Structured Cyclic Schedules

Có cấu trúc thì dễ dàng lập lịch hơn

Bảng điều khiển tùy ý lịch trình linh hoạt; không hiệu quả

Dựa vào ngắt hẹn giờ chính xác, có bộ đếm thời gian trên không cao dễ dàng hơn để thực hiện nếu cấu trúc áp đặt:

Thực hiện quyết định lập lịch theo định kỳ (khung) chiều dài của f

Thực hiện một danh sách cố định của việc làm với mỗi khung hình, không cho phép ngoại trừ tại ranh giới khung trước emption

Yêu cầu giai đoạn của mỗi nhiệm vụ định kỳ là một số nguyên không âm bội số của kích thước khung hình, công việc đầu tiên của mỗi nhiệm vụ được phát hành vào đầu của một khung

Cung cấp cho hai lợi ích:

Scheduler có thể dễ dàng kiểm tra vượt và bỏ lỡ thời hạn vào cuối của mỗi frame

Có thể sử dụng một đồng hồ chu kỳ ngắt đoạn, hơn là hẹn giờ lập trình

Kích thước hạn chế của farme

Làm thế nào để lựa chọn độ dài khung? 3 hạn chế

Để tránh quyền ưu tiên, muốn công việc để bắt đầu và hoàn thành thực hiện trong một khung duy nhất:

Để giảm thiểu số lượng các mục trong lịch trình tuần hoàn, thời kỳ siêu phải là một bội số của kích thước khung hình (

⇒

f chia đều vào các khoảng thời gian ít nhất là một nhiệm vụ)

Để cho phép lập lịch để kiểm tra xem công việc hoàn thành đúng thời hạn của họ, nên có ít nhất một khung ranh giới giữa thời gian phát hành các công việc và thời hạn:

Ví dụ Kích thước hạn chế của farme

Xem lại các hệ thống nhiệm vụ độc lập định kỳ từ ví dụ trước đây của chúng tôi:

Hạn chế:

Giải pháp có thể là:

Công việc Slices

Đôi khi, một hệ thống không thể đáp ứng tất cả các hạn chế kích thước ba khung hình cùng một lúc

Thường có thể giải quyết bằng cách phân vùng một công việc với thời gian thực hiện lớn thành lát mỏng (sub-việc làm) với thời gian thực hiện ngắn hơn / thời hạn

Ví dụ:

Không kể từ khi nhưng

Giải quyết bằng cách chia tách trong như vậy có thể được sắp xếp với

(khác chia tách tồn tại; chọn dựa trên kiến thức miền ứng dụng)

Xây dựng một lập lịch có cấu trúc chu kỳ

Để xây dựng một lịch trình tuần hoàn, chúng ta cần phải thực hiện ba loại quyết định thiết kế:

Chọn một kích thước khung hình dựa trên các ràng buộc

Phân vùng việc làm thành lát

Đặt lát trong khung hình

Những quyết định này không thể được thực hiện một cách độc lập

Lý tưởng nhất là muốn như là vài lát càng tốt, nhưng có thể buộc phải sử dụng nhiều hơn để có được một kế hoạch khả thi

Thực hiện: Điều hành chu kỳ

Sửa đổi bảng điều khiển lịch trình được dựa trên khung, với F mục, F = H / f

Chu kỳ điều hành thực hiện ngắt đồng hồ báo hiệu sự bắt đầu của một khung(farme)

Xác định khối lập kế hoạch thích hợp cho khung này và thực hiện các công việc theo thứ tự

Trên không ít hơn so với khối nguyên chất thúc đẩy lịch trình, vì chỉ bị gián đoạn về ranh giới khung

Lập kế hoạch công việc không tuần hoàn

Như vậy đến nay, công việc không tuần hoàn được lên kế hoạch trong nền sau khi đã hoàn thành tất cả các công việc với thời hạn cứng dự kiến trong mỗi frame

Do đó, giảm thiểu thời gian đáp ứng cho công việc không tuần hoàn thường là một mục tiêu thiết kế của lập lịch thời gian thực

Chùng Đánh cắp cho công việc không tuần hoàn

Việc làm định kỳ theo lịch trình trong khung hình kết thúc trước thời hạn của họ, có thể có một thời gian thấp điểm trong khung hình sau khi hoàn tất công việc định kỳ

Di chuyển thời gian thấp điểm bắt đầu của khung, chạy các công việc định kỳ chỉ trong thời gian đáp ứng thời hạn, và các công việc không tuần hoàn trong thời gian thấp điểm trước công việc định kỳ

Giảm thời gian đáp ứng cho công việc không tuần hoàn, nhưng đòi hỏi tính giờ chính xác

Lập kế hoạch Công Việc rải rác

Chúng tôi cho rằng không có công ăn việc làm không thường xuyên - điều gì sẽ xảy ra nếu điều này là thư giãn?

Công việc rải rác có thời hạn cứng, phát hành và thời gian thực hiện mà không được biết trước, do đó, một đồng hồ điều khiển tĩnh lịch trình không thể đảm bảo rằng họ đáp ứng thời hạn của họ

Tuy nhiên, lịch trình có thể xác định nếu một công việc không thường xuyên có thể được sắp xếp khi nó đến

Lập kế hoạch theo định hướng đồng hồ: Ưu điểm

Khái niệm đơn giản

Khả năng xem xét phụ thuộc phức tạp, sự chậm trễ thông tin liên lạc, và nguồn lực ganh đua giữa các công việc khi xây dựng lịch trình tĩnh, đảm bảo không có bế tắc và sự chậm trễ không thể đoán trước

Lịch trình toàn bộ được lưu giữ trong một bảng tĩnh

Chế độ hoạt động khác nhau có thể được đại diện bởi các bảng khác nhau

Hiệu quả

Không có kiểm soát đồng thời hoặc đồng bộ hóa cần thiết

Chọn kích thước khung hình để giảm thiểu các chi phí chuyển đổi ngữ cảnh

Tương đối dễ dàng để xác nhận, kiểm tra và xác nhận

Khi khối lượng công việc chủ yếu là định kỳ và tiến độ là cyclic, hạn chế thời gian có thể được kiểm tra và thực thi tại mỗi ranh giới khung

Lập kế hoạch theo định hướng đồng hồ: Nhược điểm

Không linh hoạt:

Biên dịch trước khi kiến thức vào bảng lịch trình có nghĩa là nếu thay đổi bất cứ điều gì về vật chất, phải làm lại các thế hệ bảng

Thích hợp nhất cho hệ thống hiếm khi được sửa đổi một lần xây dựng

Lập lịch dựa trên độ ưu tiên của Nhiệm vụ định kỳ (

Periodic Tasks)

1. Lập lịch dựa trên độ ưu tiên (

Priority-driven scheduling)

• Chỉ định ưu tiên cho các công việc, dựa trên thời hạn (deadline) của chúng hoặc

thời gian hạn chế khác

• Các thuật toán thực hiện theo định hướng ưu tiên tại địa phương tối ưu quyết định về công việc để chạy

Những thuận lợi và bất lợi

• Lập lịch priority-driven (lập lịch dựa trên độ ưu tiên) có nhiều lợi thế hơn lập lịch clock - driven

- phù hợp cho các ứng dụng yêu cầu về tài nguyên, thời gian.

- Thời gian chạy tương đối nhỏ.

•Tuy nhiên, khó khăn hơn để xác nhận chính xác:

- Dị thường lập lịch có thể xảy ra đối với đa hệ thống, nếu preemption là không được phép, hoặc nếu có tranh cho các nguồn tài nguyên.

- Không cho phép bỏ 1 ứng dụng đang chạy ra ngoài.

- Rất khó để nhận ra thuật toán

Lập lịch theo độ ưu tiên

• Nhiều thuật toán lập lịch thời gian thực dựa vào độ ưu tiên (

priority-driven real-time scheduling algorithms

) tồn tại :

- Cái nào có deadline (tg chết) sớm nhất thì chạy trước

- Thời gian chùng ít nhất thì chạy trước

* Rate monotonic: tác vụ nào càng diễn ra thường xuyên càng được ưu tiên.

* Deadline monotonic: tác vụ nào càng gấp, có thời hạn cuối càng sớm càng được ưu tiên.

* Least laxity: tác vụ nào có tỷ lệ thời gian tính toán/thời hạn cuối cùng(deadline) càng lớn càng được ưu tiên.

2. Cố định và thuật toán Dynamic-Ưu tiên (

Fixed- and Dynamic-Priority Algorithms

a. Rate Monotonic Scheduling

Đây là thuật toán fixed – priority -> mức ưu tiên cố định ở mức job

Gán độ ưu tiên dựa trên pi (là nghịch đảo của period)

Period càng nhỏ thì độ ưu tiên càng cao.

Ví dụ, hãy xem xét một hệ thống 3 tasks:

•

= (4, 1) => rate = 1/4

= (5, 2) => rate = 1/5

= (20, 5) => rate= 1/20

Mức ưu tiên tương đối : T1 > T2 > T3

Deadline Monotonic Scheduling (

deadline tương đối

- Có deadline ngắn thì độ ưu tiên cao (Khoản (t) thi hành nhỏ thì được thi hành trước)

- Khi

deadline (

thời hạn) tương đối của mỗi task phù hợp thời gian của nó, rate monotonic và deadline monotonic cho kết quả giống nhau (nếu nó tỷ lệ).

- Khi deadline tương đối là tùy ý:

+ deadline monotonic đôi khi có thể tạo ra một lịch trình khả thi trong trường hợp rate monotonic không thể, rate monotonic luôn thất bại khi deadline monotonic không thành công.

The EDF and LST Scheduling Algorithms

Hai thuật toán phổ biến dựa vào độ ưu tiển

• EDF

Earliest deadline first

- Gán mức ưu tiên công việc dựa trên deadline: thời hạn cũ hơn = ưu tiên cao hơn

- Đơn giản, chỉ đòi hỏi kiến thức của deadline

•

Least Slack Time first (LST)

• Một job Ji có deadline di , thời gian thực hiện ei , và được phát hành tại thời điểm ri

• Tại thời điểm t <di: Còn lại thời gian thực hiện trem=ei – (t - ri)

Gán mức ưu tiên dựa trên slack time ít nhất, tslack = di – t - trem (khoảng thời gian còn lại)

• Strict LST: lập lịch quyết định bất cứ khi nào một công

queued job’s slack time

trở nên nhỏ hơn so với

the executing job’s slack time – high overhead

, không sử dụng, Quyết định lập kế hoạch LST Không nghiêm ngặt: chỉ khi công việc phát hành

hoặc hoàn toàn

• Phức tạp hơn, đòi hỏi kiến thức về thời gian thực hiện và thời hạn

Tối ưu của EDF và LST

• Các thuật toán EDF và LST tối ưu

- Một bộ xử lý duy nhất, miễn là preemption được phép và jobs không tranh cho các nguồn tài nguyên; có thể thất bại để sắp xếp một tập khả thi của công việc nếu có nhiều bộ xử lý, hoặc nếu preemption được phép

• Optimality of EDF and LST: Proof (bằng chứng)

Bất kỳ lịch trình khả thi có thể được chuyển đổi thành một lịch trình EDF

- Nếu Ji được lên kế hoạch để chạy trước khi Jk , nhưng Ji’s thời hạn chậm nhất là Jk'S hoặc là:

+ Thời gian xuất hiện của Jk là sau khi Ji hoàn thành =>thỏa mãn EDF•

+ Thời gian xuất hiện của Jk là trước khi kết thúc của khoảng thời gian mà Ji

•

Di chuyển any jobs following idle periods forward into the idle period

Kết quả là một lịch trình EDF

Vì vậy, nếu EDF không để sản xuất một kế hoạch khả thi, thì không có lịch trình như vậy tồn tại

Nếu một lịch trình khả thi tồn tại, nó có thể được chuyển đổi vào một kế hoạch EDF, mâu thuẫn với tuyên bố rằng EDF không để sản xuất một kế hoạch khả thi [bằng chứng cho LST là tương tự]

•Relative Merits (đo lường, so sánh thuật toán)

- Các thuật toán lập lịch trình cố định và năng động ưu tiên (

Fixed- and dynamic-priority)

có tính chất khác nhau, không thích hợp cho tất cả mọi ngườitrường hợp.

- Các thuật toán EDF ưu tiên cao hơn cho các công việc mà đã bỏ lỡ thời hạn của họ hơn là việc làm có hạn chót là vẫn còn trong tương lai

+ Không nhất thiết phải phù hợp với hệ thống, nơi thường xuyên quá tải không thể tránh khỏi

- Các thuật toán năng động như EDF có thể sản xuất khả thi lịch trình trong trường hợp RM và DM không thể

• Việc sử dụng là 1.0; không có thời gian chùng (slack time)

- Mong đợi một số các thuật toán dẫn đến thời hạn bỏ lỡ (deadlines)!

- Đây là một trong những trường hợp EDF hoạt động tốt hơn so với RM / DM

• Chứng minh bằng mô phỏng đầy đủ rằng LST và EDF đáp ứng thời hạn, nhưng FIFO và RM không.

Schedulable Utilisation

Nhớ lại: một periodic task (nhiệm vụ định kỳ) Tiđược xác định bởi các 4- tuple

(φi, pi, ei, Di)

với việc sử dụng ui = ei / pi

• Tổng sử dụng hệ thống U= where 0<=U<=1

• Một thuật toán lập lịch khả thi có thể lên lịch hệ thống periodic tasks (nhiệm vụ tuần hoàn) trên một bộ xử lý nếu Ulà bằng hoặc nhỏ hơn so với các schedulable utilisation tối đa của các thuật toán, UALG

• Điều này mang lại một kiểm tra schedulability, một hệ thống có thể được xác nhận bằng cách cho thấy rằng U UALG

• Nếu UALG = 1, Thuật toán là tối ưu

Schedulable Utilisation: EDF

• Định lý: một hệ thống độc lập preemptable định kỳ các nhiệm vụ (periodic tasks) với Di=pi có thể là dự kiến khả thi trên một bộ vi xử lý bằng cách sử dụng EDF khi và chỉ khi U1

• UEDF = 1 độc lập, nhiệm vụ preemptable định kỳ với Di = pi

• Hệ quả tất yếu: Kết quả này cũng nắm giữ nếu thời hạn dài hơn giai đoạn: UEDF= 1 cho độc lập preemptable định kỳ các nhiệm vụ với

Schedulable Utilisation: EDF

• Thử nghiệm không thành công nếu Di < pi đối với một số i

• Tuy nhiên, có một bài kiểm tra thay thế:

- Mật độ của nhiệm vụ, Ti, là

- Mật độ của hệ thống là

Δ = δ1 + δ2 + … + δn

- Định lý: Một hệ thống T độc lập, nhiệm vụ preemptable định kỳ có thể dự kiến khả thi trên một bộ xử lý bằng cách sử dụng EDT nếu

Δ ≤ 1

• Lưu ý:

• Đây là một điều kiện đủ, nhưng không phải là một điều kiện cần thiết - tức là một hệ thống là đảm bảo được khả thi nếu

Δ ≤ 1

Nhưng vẫn còn có thể là khả thi (feasible) nếu

Δ > 1

(Sẽ phải chạy các mô phỏng đầy đủ để chứng minh)

Schedulable Utilisation of RM

Một hệ thống n độc lập preemptable định kỳ nhiệm vụ với Di = pi có thể khả thi dự kiến vào một bộ vi xử lý bằng cách sử dụng RM, nếu

≤

(21/

– 1)

U URM (n)

là một điều kiện đủ, nhưng không cần thiết - tức là khả thi tỷ lệ lịch trình đơn điệu được đảm bảo tồn tại nếu U URM (n), Nhưng có thể vẫn có thể nếu

• Điều gì sẽ xảy ra nếu thời hạn tương đối (relative deadlines) cho các nhiệm vụ không bằng với các giai đoạn tương ứng của chúng?

• Nếu thời hạn là một bội (

a multiple)

của period:

.pk

• Nó có thể được chỉ ra rằng:

Chương 5. Priority-driven Scheduling of Periodic Tasks (lập lịch theo hướng ưu tiên của công việc có chu kỳ)

TỐI ƯU VÀ KHẢ NĂNG LẬP LỊCH(Optimality and Schedulability)

+ lập lịch tối ưu với độ ưu tiên động EDF và LST

- Luôn luôn tạo ra một lịch trình khả thi nếu tồn tại trên một bộ xử lý duy nhất, miễn là quyền ưu tiên được cho phép và các job không đấu tranh cho các nguồn tài nguyên

+ Các thuật toán với độ ưu tiên cố định nhìn chung không tối ưu:

RM và DM đôi khi lập lịch lỗi các task nên có thể được lập lịch bằng các thuật toán khác

TÍNH TỐT CỦA THUẬT TOÁN RM VÀ DM(Optimality of RM and DM Algorithms)

Tuy nhiên các thuật toán tối ưu cố định có thể được tối ưu trong hệ thống hạn chế

Ví dụ:

RM và DM được tối ưu trong hệ thống 1 chu kỳ

Một hệ thống của tasks có chu kỳ là chu kỳ đơn nếu thời gian của từng task là một bội số nguyên thời gian của các task khác, pk = n

⋅

pi, pi <pk và n là một số nguyên dương, cho tất cả Ti và Tk

Đúng đối với nhiều hệ thống thực tế, từ đó dễ dàng thiết kế quanh bội số của một vòng lặp đơn.

Tập các chu kỳ đơn, độc lập, task preemptable với Di ≥ pi được lập lịch trên một tiến trình sử dụng RM hoặc DM nếu U<1.

CM:

Hệ thống chu kỳ đơn, giả sử task trong giai đoạn(phase)

Trường hợp tồi tệ nhất thời gian thực thi sẽ xảy ra khi các task trong giai đoạn này.

T1 bỏ lỡ deadline tạo thời điểm t khi t là bội số của pi

Lần nữa, trường hợp tồi tệ khi => Di = pi

Chu kỳ đơn => t bội số của các chu kỳ của tất cả các tasks có độ ưu tiên cao

Tổng thời gian yêu cầu để hoàn thành jobs với deadline <=t là

Thì thất bại khi Ui>1.

Khả năng sinh lập lịch của Fixed-priority tasks

Một vài định nghĩa kiểm tra khả năng lập lịch đơn cho lập lịch fixed-priority

Một hệ thống n độc lập với preemptable tasks chu kỳ với Di =pi có thể có lịch khả thi trên một tiến trình sử dụng RM nếu U<=n.(21/n -1).

Một hệ thống chu kỳ đơn độc lập với các task preemptable với Di>=pi được lập lịch trên một tiến trình sử dụng thuật toán RM nếu U<=1.

Kết quả giống thế với DM

Nhưng: có thuật toán và các vùng hoạt động mà chúng ta không kiểm tra được khả năng lập lịch và phải sử dụng đến mô hình đầy đủ

Có cách kiểm tra khả năng lập lịch tổng quát hơn không?

Có, mở rộng phương pháp cho khả năng lập lịch của hệ thống chu kỳ đơn

Tìm điểm trầm trọng

Một điểm trầm trọng của một job là trường hợp xấu nhất thời điểm ngắt của job, có tính đến tất cả các công việc có ưu tiên cao hơn.

i.e là ngắt job tại cùng điểm trầm trọng với tất cả các job với độ ưu tiên cao, được ngắt và phải chờ cho tất cả các job hoàn thành trước khi nó thực thi.

Thời gian trả lời của một job trong khi ngắt Ti tại điểm trầm trọng được gọi là lớn nhất(có thể) thời gian trả lời và được biểu thị bởi Wi .

Kiểm tra khả năng lập lịch bao gồm kiểm tra mỗi task trong vòng, để xác minh rằng nó có thể lập lịch khi bắt đầu tại điểm trầm trọng.

Nếu lập lịch tại tất cả các điểm trầm trọng, sẽ làm việc ở thời gian khác.

Kiểm tra nhiều công việc cho việc sử dụng lập lịch lớn nhất, nhưng ít hơn nhiều so với một mô phỏng đầy đủ

Một điểm trầm trọng của 1 task Ti là một thời điểm sao cho

Nếu wi,k <Di,k cho tất cả Ji,k trong Ti thì

Ngắt job tại điểm trầm trọng có thời gian trả lời lớn nhất cho tất cả các job trong Ti và Wi=wi,k

Nếu tồn tại Ji,k : wi,k >Di,k thì

Ngắt job tại điểm trầm trọng có thời gian trả lời >D khi wi,k là thời gian trả lời của job.

Trong một hệ thống fixed-priority khi mỗi job hoàn thành trước khi job tiếp theo trong cùng task được ngắt, một điểm trầm trọng xẩy ra khi các job của nó Ji,c là ngắt tại cùng thời điểm với mỗi job từ tất cả các task có độ ưu tiên cao.

Ví dụ tìm điểm trầm trọng:

3 task lập lịch sử dụng tỉ lệ đơn điệu

Thời gian phản hồi của job trong T2 là: r2,1=0.8, r2,3=0.2,r2,4=0.3,r2,5=0.8….

Do đó điểm trầm trọng của T2 là t=0 và t=10

Sử dụng điểm trầm trọng

Phân tích nhu cầu thời gian

Cho mỗi job Ji,c ngắt tại điểm trầm trọng, nếu Ji,c và tất cả task có độ ưu tiên cao hoàn thành thực thi trước chúng deadline tương đối hệ thống có thể được lập lịch.

Tính tổng nhu cầu thời gian xử lý các một job tại điểm trầm trọng của một task, và tất cả các task có độ ưu tiên cao, như một hàm thời gian từ điểm trầm trọng, kiểm tra nếu nhu cầu có thể đáp ứng trước deadline của job :

Hãy xem một task, Ti, tại 1 thời điểm, bắt đầu với độ ưu tiên cao nhất và giảm dần đến công việc có độ ưu tiếp thấp nhất.

Tập trung vào một job, Ji trong Ti thời gian ngắt, t0 của công việc đó là điểm trầm trọng của Ti

Tại thời điểm t0 +t cho t>=0, một tiến trình cần thời gian wi(t) cho job đó và tất cả các job có độ ưu tiên cao ngắt trong [t0,t] là

wi(t)=

ei : là thời gian thực thi của job Ji

wi(t) = hàm nhu cầu thời gian

Phân tích nhu cầu thời gian

So sánh nhu cầu thời gian wi(t) với thời gian có sẵn

Nếu wi(t) cho một vài t<=Di, thì job Ji, gặp deadline của nó, t0 +Di

Nếu wi(t)>t cho tất cả 0<t<=Di thì task có thể không hoàn thành bởi vì nó deadline ;và hệ thống không có khả năng được lập lịch sử dụng thuật toán ưu tiên cố định.

Chú ý: đây là một điều kiện đủ, nhưng không phải là một điều kiện cần. Mô phỏng có thể hiển thị điểm trầm trọng không bao giờ xảy ra trong thực tế, do đó hệ thông có tính khả thi…

Sử dụng phương pháp này để kiểm tra xem tất cả các task được lập lịch nếu ngắt tại điểm trầm trọng, nếu có kết luận toàn bộ hệ thống có thể được lập lịch.

Ví dụ: phân tích nhu cầu thời gian

Tỉ lệ đơn điệu: T1=(3,1),T2=(5,2),T3=(10,2),U=0.933

Hàm nhu cầu thời gian w1(t),w2(t) và w3(t) không được

PHÂN TÍCH YÊU CẦU VỀ THỜI GIAN

+ Yêu cầu thời gian

là một hàm bậc thang

- Các bước trong yêu cầu thời gian cho một task là bội số của thời gian của task ưu tiên cao hơn

Giá trị

tuyến tính giảm từ 1 bước cho đến bước tiếp theo

+ Nếu điều chúng ta quan tâm là khả năng lập lịch của một task, đủ để kiểm tra nếu

tại time instants(khoảng thời gian) khi một job có độ ưu tiên cao hơn được released; kiểm tra nếu một hệ thống được lập lịch có thể trở thanh:

Tính

Kiểm tra xem có thõa mãn tại bất kì trong đó và

Blocking and Priority Inversion (Ngăn chặn và ưu tiên ngược)

+ Một job sẵn sàng bị chặn bởi một job ưu tiên thấp hơn;

+ Sự ưu tiên ngược là khi một job ưu tiên thấp hơn

thực hiện trong khi job ưu tiên cao hơn bị chặn

+ Những điều này xảy ra nếu job không thể giành quyền ưu tiên trước:

Nhiều lý do tại sao một job có thể có vùng non-preemptable

+ Vùng quan trọng over một tài nguyên; một vài hệ thống như vậy được gọi là non-preemptable; Lập lịch I/O;etc

+ Nếu một job là non-preemptablem, ưu tiên ngược có thể xảy ra, điều này có thể gây ra task ưu tiên cao hơn sẽ miss deadline

+ Khi cố gắng để xác định một task đáp ứng tất cả các deadline của nó, phải xem xét không chỉ tất cả các nhiệm vụ có ưu tiên cao hơn, mà cũng phải xem vùng non-preemptable của task ưu tiên thấp hơn

- Thêm thời gian chặn(blocking time) khi tính toán nếu một task lập lịch

Hệ thống treo(tự dừng) và chuyển ngữ cảnh

- Hệ thống treo(tự dừng)

Một công việc có thể gọi một hoạt động bên ngoài (ví dụ như một yêu cầu hoạt động I / O), trong thời gian nó bị treo(bị dừng).

Điều này có nghĩa là nhiệm vụ không đúng định kỳ ... một lần nữa cần phải đưa vào thời gian treo(tự dừng) khi tính toán một lịch trình.

- Chuyển ngữ cảnh

Giả sử số lượng tối đa các thiết bị chuyển ngữ cảnh Ki

cho một job ở Ti được biết đến; từng mất tCS đơn vị thời gian.

Bù đắp bằng cách thiết lập thời gian thực hiện của từng công việc (nhiều hơn nếu công việc bị treo, kể từ khi thiết bị chuyển ngữ cảnh bổ sung)

Đánh dấu lập lịch

Trình bày trước về lập lịch ưu tiên - bởi job release và các job hoàn thành các sự kiện

Ngoài ra, có thể thực hiện lập lịch ưu tiên với lượng tử lập lịch cố định

Các yếu tố để phân tích khả năng lập lịch.

Implementing Rate Monotonic Scheduling( Thực hiện lập lịch tốc độ đơn điệu).

- Tốc độ đơn điệu và thời gian lịch trình đơn điệu một cách tự nhiên nhiên có thể được thực hiện bằng cách sử dụng POSIX nguyên thủy

+ Phân công ưu tiên cho các nhiệm vụ theo cách thông thường cho RM / DM

+ Truy vấn phạm vi các ưu tiên hệ thống cho phép (sched_get_priority_min () và sched_get_priority_max ())

+ Bản đồ nhiệm vụ đặt lên ưu tiên hệ thống

+ Luồng bắt đầu cho mỗi nhiệm vụ bằng cách sử dụng ưu tiên được giao và SCHED_FIFO

- Không có hỗ trợ rõ ràng để chỉ ra thời hạn, thời gian

+ Thực hiện bằng tay, như một vòng chạy cho mỗi công việc

Lecture06-aperiodic_Yến

Lập kế hoạch theo định hướng ưu tiên không tuần hoàn và nhiệm vụ rời rạc

Giả định

Một bộ xử lý hệ thống, độc lập chiếm trước nhiệm vụ định kỳ theo lịch trình bằng cách sử dụng một định hướng

thuật toán

ưu tiên.

Các Job không tuần hoàn và / hoặc không thường xuyên tồn tại.

Dựa trên thời gian thực hiện và thời hạn mỗi điều mới đến công việc không thường xuyên, quyết định có chấp nhận hoặc từ chối công việc

Nhằm mục đích để hoàn thành mỗi công việc không tuần hoàn càng sớm càng có thể, mà không gây ra các nhiệm vụ tuần hoàn hoặc

chấp nhận việc làm không thường xuyên bỏ lỡ thời hạn.

Định nghĩa: Độ chính xác

Một lịch trình chính xác là một trong tất cả các nhiệm vụ tuần hoàn, và bất kỳ nhiệm vụ rời rạc đã được chấp nhận,

đáp ứng thời hạn của họ.

Một thuật toán lập lịch hỗ trợ các job không tuần hoàn và / hoặc công việc không thường xuyên là một thuật toán chính xác nếu nó chỉ

sản xuất lịch trình chính xác cho hệ thống

Định nghĩa: Tối ưu

Một thuật toán lập lịch công việc không tuần hoàn là tối ưu nếu nó

giảm thiểu hoặc là:

+ Thời gian phản ứng của công việc ở phần đầu của hàng đợi công việc không tuần hoà.

+ Thời gian phản ứng trung bình của tất cả các công việc không tuần hoàn cho một hàng đợi kỷ luật nhất định.

Một thuật toán lập lịch công việc không thường xuyên là tối ưu nếu nó chấp nhận một công việc mới không thường xuyên, và lịch trình công việc hoàn thành đúng thời hạn của nó, nếu và chỉ nếu công việc mới có thể được chính xác dự kiến sẽ hoàn thành trong thời gian

+ Một thuật toán tối ưu luôn luôn tạo một lịch trình khả thi nếu công việc chấp nhận

Lập lịch các job không tuần hoàn.

Hãy xét trường hợp đơn giản: lập lịch các job không tuần hoàn cùng với một hệ thống các job định kỳ

+ Bỏ qua công việc không thường xuyên

Hai phương pháp tiếp cận đơn giản:

+ Thực hiện công việc không tuần hoàn trong nền sau.

+ Thực hiện các công việc không tuần hoàn bằng cách làm gián đoạn công việc định kỳ

Lập lịch của các job không tuần hoàn

Công việc không tuần hoàn được lên kế hoạch và thực hiện chỉ vào thời gian khi không có công việc định kỳ hoặc job không thường xuyên sẵn sàng để thực hiện

+ Lập lịch rõ ràng chính xác, cực kỳ đơn giản để thực hiện.

+ Không tối ưu vì nó gần như đảm bảo để trì hoãn thực hiện job không tuần hoàn có lợi cho công việc định kỳ và job rời rạc, cho phản ứng quá mức thời gian dài cho các công việc không tuần hoàn.

Gián đoạn lập lịch của các job không tuần hoàn

Làm thế nào chúng ta có thể cải thiện thời gian phản ứng công việc không tuần hoàn?

Bất cứ khi nào một công việc không tuần hoàn đến, thực hiện nhiệm vụ tuần hoàn bị gián đoạn, và công việc không tuần hoàn

được thực hiện.

Slack stealing

cho các Job không tuần hoàn

Nền sau hoặc thực hiện theo định hướng gián đoạn không lý tưởng

Một lựa chọn tốt hơn

slack stealing

việc định kỳ

Giảm thời gian đáp ứng cho công việc không tuần hoàn và chính xác, nhưng phức tạp và khó khăn lý do gồm:

+ Máy tính chùng có khó khăn trong thực tế cho các hệ thống theo định hướng ưu tiên

Thực hiện kiểm tra vòng cho Jobs không tuần hoàn

Một cách thông thường để sắp xếp công việc không tuần hoàn bằng cách sử dụng một máy chủ kiểm tra vòng

+ Một job không tuần hoàn (ps,es) lập lịch theo các thuật toán định kỳ, nói chung là công việc ưu tiên cao nhất

+ Khi thực hiện, kiểm tra hàng đợi công việc không tuần hoàn.

Đơn giản để chứng minh tính đúng đắn, hiệu suất ít hơn hơn lý tưởng - kể từ khi thực hiện các công việc không tuần hoàn

trong thời gian cụ thể - chúng ta có thể cải thiện?

Định kỳ máy chủ

Một nhiệm vụ mà hành động giống như một nhiệm vụ định kỳ, nhưng

được tạo ra cho mục đích thực hiện job không tuần hoàn là một máy chủ định kỳ

Một máy chỉ định kỳ Tps = (Pps, eps) không bao giờ thực hiện cho hơn eps đơn vị thời gian trong từng thời kỳ

+ Tham số eps là thực hiện kho của máy chủ định kỳ

+ Khi một máy chủ được lên kế hoạch và thực hiện công việc không tuần hoàn, nó sẽ chiếm kho với tỷ lệ 1 trên một đơn vị thời gian, kho đã cạn kiệt khi nó đạt đến 0.

+ Ngay lập tức khi ngân sách bổ sung được gọi là thời gian bổ sung

Một máy chủ định kỳ được tồn đọng bất cứ khi nào hàng đợi công việc không tuần hoàn

không rỗng, nó là nhàn rỗi nếu hàng đợi rỗng

Máy chủ định kỳ được lên kế hoạch như bất kỳ nhiệm vụ tuần hoàn nào khác dựa trên

đề án ưu tiên được sử dụng bởi các thuật toán lập lịch trình

+ Ngoại trừ: máy chủ là đủ điều kiện để thực hiện khi và chỉ khi nó được backlogged và có ngân sách khác không.

Các loại máy chủ định kỳ trong ngân sách được tiêu thụ khi nhàn rỗi, và khi

ngân sách được bổ sung

Một máy chủ kiểm tra vòng là một loại máy chủ định kỳ đơn giản

Bảo quản băng thông máy chủ

Sự thiếu hụt của máy chủ kiểm tra vòng: nếu máy chủ được lên kế hoạch

khi không backlogged, nó sẽ mất ngân sách

Các thuật toán cải thiện phương pháp kiểm tra trong

thuật toán băng thông - bảo quản máy chủ

băng thông - Bảo quản máy chủ là máy chủ định kỳ với quy tắc tiêu thụ và bổ sung thêm ngân sách

Làm thế nào để các máy chủ như vậy?

+ Một băng thông - bảo quản máy chủ backlogged đã sẵn sàng để thực hiện khi nó

có ngân sách.

+ Các kế hoạch theo dõi việc tiêu thụ ngân sách và đình chỉ các máy chủ khi nó cạn kiệt, hoặc máy chủ trở nên nhàn rỗi

+ Các kế hoạch di chuyển các máy chủ trở lại hàng đợi sẵn sàng một khi nó giúp bổ sung ngân sách, nếu máy chủ được backlogged tại thời điểm đó.

+ Nếu xuất hiện của một công việc không tuần hoàn gây bởi các máy chủ để trở thành backlogged, và có ngân sách, máy chủ được đưa trở lại vào hàng đợi sẵn sàng: khắc phục này hạn chế máy chủ kiểm tra.

Nhiều loại băng thông - bảo quản máy chủ:

+ Deferrable máy chủ

+ Máy chủ rời rạc

+ Liên tục sử dụng các máy chủ

+ Tổng băng thông máy chủ

Máy chủ hàng đợi

Deferrable máy chủ

Băng thông - Bảo quản máy chủ đơn giản

+ Cải thiện thời gian đáp ứng công việc không tuần hoàn, so với máy chủ kiểm tra vòng.

Quy tắc tiêu thụ:

+ Ngân sách được tiêu thụ với tốc độ của một trong mỗi đơn vị thời gian bất cứ khi nào máy chủ thực hiện

+ Ngân sách chưa sử dụng được giữ lại trong suốt thời gian, được sử dụng bất cứ khi nào có những công việc không tuần hoàn để thực hiện

Bổ sung quy tắc:

+ Ngân sách được thiết lập để es tại bội số của giai đoạn.

Tức là thời gian k.ps với k=0,1,2…

+ Lưu ý: máy chủ không được phép để thực hiện ngân sách từ giai đoạn đến giai đoạn.

Nhiệm vụ T1 và T2 được lập lịch theo thuật toán đơn điệu.

Thêm máy chủ deferrable, dự kiến theo tỷ lệ ưu tiên đơn điệu, nhưng với mức tiêu thụ ngân sách và các quy tắc bổ sung ảnh hưởng đến thời gian thực hiện của nó. Các máy chủ deferrable thường chạy ở mức ưu tiên cao nhất, nhưng điều này không yêu cầu nghiêm chỉnh

Deferrable Server: Schedulability (1)

Lập lịch tối đa thử nghiệm utilisation không thành

+ Utilisation khác nhau tùy thuộc vào thời gian đến công việc được thực hiện bởi máy chủ

+ Sử dụng thời gian phân tích nhu cầu dựa trên các khoảnh khắc quan trọng nếu

hệ thống có thể được lập lịch.

Tìm các khoảnh khắc quan trọng:

+ Giả sử một hệ thống ưu tiên cố định T khi Di ≤ pi,

∀

I lập lịch với 1 máy chủ deferrable (ps,es) điều đó có ưu tiên cao nhất trong số tất cả các nhiệm vụ

+ Một khoảnh khắc quan trọng của tất cả các nhiệm vụ định kỳ Ti xảy ra tại thời điểm t0 khi tất cả sau đây là đúng:

Một công việc ji,c bị từ chối tại t0

Một công việc trong tất cả các nhiệm vụ ưu tiên cao hơn job định kỳ bị từ chối tại t0.

Ngân sách của máy chủ là es tại t0, một hoặc nhiều hơn job định kỳ bị từ chối tại t0 và chúng giữ máy chủ backlogged từ đây.

Thời gian bổ sung tiếp theo của máy chủ là t0 + es

Định nghĩa quan trọng là giống hệt nhau cho các job tuần hoàn mà không có máy chủ deferrable

Các yêu cầu trường hợp xấu nhất cho máy chủ

Chức năng thời gian yêu cầu là:

+ Chuyển tiếp nhiệm vụ Ti là lập lịch, đơn giản chúng ta cần phải kiểm tra wi(t) ≤ t để t ≤ Di.

+ Hãy nhớ rằng, đây là một điều kiện đủ, không cần thiết - tức là, nếu điều này điều kiện là không đúng sự thật, hệ thống có thể không lập lịch.

Nói chung, không có lập lịch tối đa có thể xác định kế hoạch cho một hệ thống ưu tiên cố định

với một máy chủ deferrable

+ một trường hợp đặc biệt: 1 hệ thống của n độc lập, các nhiệm vụ định kỳ cần thời gian đáp ứng ps < p1 < p2 < … < pn < 2ps và pn > ps + es, trường hợp thời hạn tương đối bằng khoảng thời gian tương ứng của họ, có thể được sắp xếp tỷ lệ đơn điệu với một máy chủ deferrable cung cấp U < URM/DS(n):

Nó dễ dàng hơn để lý do về kế hoạch của một

hệ thống điều khiển thời hạn với một máy chủ deferrable

+ Thời hạn của một máy chủ deferrable là thời gian tiếp theo bổ sung của nó.

+ Một nhiệm vụ định kỳ Ti trong một hệ thống N độc lập, nhiệm vụ định kỳ là lập lịch với một máy chủ deferrable với thời gian ps, thực hiện ngân sách es và sử dụng us, theo thuật toán EDF nếu:

+ Phải được tính toán cho từng công việc trong hệ thống, kể từ khi bao gồm Di.

+ Ví dụ: nhiệm vụ T1=(3, 0.6), T2=(5.0, 0.5), T3=(7, 1.4) lập lịch với 1 máy chủ deferrable ps=4, es=0.8.

+ Phía bên trái của bất đẳng thức trên là 0913, 0828 và 0792 tương ứng, vì thế mà có ba nhiệm vụ là lập lịch.

Chương 7: Lập kế hoạch theo định hướng ưu tiên không tuần hoàn và

Hạn chế của máy chủ Deferrable

Giới hạn của các máy chủ deferrable - họ có thể trì hoãn

nhiệm vụ ưu tiên thấp hơn cho nhiều thời gian hơn một định kỳ

nhiệm vụ với cùng kỳ và thời gian thực hiện:

rời rạc máy chủ

• Một máy chủ không thường xuyên được thiết kế để loại bỏ

giới hạn

• Một loại khác nhau của máy chủ băng thông bảo quản: phân nhóm khác nhau

• phức tạp hơn tiêu dùng và các quy tắc bổ sung đảm bảo rằng một

lẻ tẻ máy chủ với pS thời gian và ngân sách ES không bao giờ đòi hỏi nhiều hơn

thời gian xử lý hơn so với một công việc định kỳ với các thông số tương tự

Đơn giản cố định ưu tiên rời rạc Server

Hệ thống, T, độc lập preemptable định kỳ

nhiệm vụ và một máy chủ lẻ tẻ với các thông số (ps, es)

• lập kế hoạch ưu tiên cố định, hệ thống có thể được tiến hành nếu máy chủ lẻ tẻ

cư xử như một công việc định kỳ với các thông số (ps, es)

• Xác định:

• TH: nhiệm vụ định kỳ với ưu tiên cao hơn so với máy chủ (có thể rỗng)

• tr: thời gian qua máy chủ ngân sách bổ sung

• tf: ngay lập tức đầu tiên sau khi tr máy chủ bắt đầu thực hiện

• Tại bất kỳ thời điểm t xác định:

• BEGIN như sự bắt đầu của khoảng thời gian bận rộn đầu tiên trong chuỗi tiếp giáp gần đây nhất của

khoảng thời gian bận rộn của TH bắt đầu trước khi t (khoảng thời gian bận rộn liền kề nhau nếu sau này bắt đầu

ngay lập tức trước đó kết thúc)

• END như là kết thúc của khoảng thời gian bận rộn nhất trong dãy này nếu khoảng thời gian này kết thúc trước khi t;

define END = ∞ nếu khoảng thời gian kết thúc sau khi t

• quy tắc tiêu thụ:

• Tại bất kỳ thời gian t ≥ tr, nếu máy chủ có ngân sách và nếu một trong hai sau đây

điều kiện là đúng, ngân sách được tiêu thụ ở tỷ lệ 1 trên một đơn vị thời gian:

• C1: Các máy chủ được thực hiện

• C2: Các máy chủ đã thực hiện kể từ khi tr và END <t

• Khi họ không đúng sự thật, máy chủ nắm giữ ngân sách

• Đó là:

• Các máy chủ thực hiện không có nhiều thời gian hơn trong triển khai thực hiện ngân sách

• máy chủ giữ lại ngân sách của mình nếu:

• Một công việc ưu tiên cao hơn được thực hiện, hoặc

• Nó đã không được thực hiện kể từ khi tr

• Nếu không, ngân sách giảm khi máy chủ thực hiện, hoặc nếu nó nhàn rỗi

trong khi nó có ngân sách

• Bổ sung quy tắc

• R1: Khi hệ thống bắt đầu thực hiện, và mỗi ngân sách thời gian được bổ sung,

thiết lập ngân sách để ES và tr = thời gian hiện tại.

• R2: Khi máy chủ bắt đầu để thực hiện (quy định thời gian như tf)

nếu END = tf sau đó

te = max (tr, BEGIN) te = thời gian hiệu quả bổ sung

khác nếu END <tf sau đó

te = tf

Thời gian bổ sung tiếp theo được thiết lập để te + pS

• R3: ngân sách bổ sung đồng thời bổ sung tiếp theo, trừ khi:

• Nếu te + pS sớm hơn tf ngân sách được bổ sung ngay sau khi nó bị cạn kiệt

• Nếu T trở nên nhàn rỗi trước khi te + pS, và trở nên bận rộn một lần nữa tại tb, ngân sách được bổ sung

min (tb, te + pS)

Simple Fixed-Priority Sporadic Server

• phức tạp hơn so với một máy chủ bỏ phiếu hoặc một deferrable

máy chủ, nhưng dễ dàng hơn để chứng minh hệ thống có thể được

dự kiến

• Định lý: với mục đích chứng thực một lịch trình,

bạn có thể điều trị một máy chủ đơn giản không thường xuyên (ps, es) trong một

hệ thống cố định ưu tiên chính xác giống như bất kỳ khác

Ti nhiệm vụ định kỳ với pi = ps và ei = es

• liên phát hành thời gian thực tế của máy chủ lẻ tẻ đôi khi sẽ

lớn hơn ps, và thời gian thực hiện của họ ít hơn es, nhưng điều này không

ảnh hưởng đến tính chính xác

Simple Dynamic-Priority Sporadic Server(Simple Dynamic-Ưu tiên rời rạc Server)

Nó có thể để xác định một máy chủ đơn giản lẻ tẻ

hoạt động trong một môi trường năng động ưu tiên

• Ví dụ:, khi sử dụng EDF hoặc LST lập kế hoạch

• Mức tiêu thụ và các quy tắc bổ sung khái niệm

tương tự như đối với một lịch trình cố định ưu tiên,

sửa đổi nhỏ mà giải thích cho sự khác biệt

trong lịch trình thuật toán

• Cung cấp đảm bảo lịch trình tương tự như các máy chủ lẻ tẻ đơn giản cho

ưu tiên lập lịch cố định

• Một đơn giản, rời rạc máy chủ (ps, es) trong một hệ thống EDF hoặc LST có thể được điều trị

chính xác giống như bất kỳ Ti nhiệm vụ khác với pi = ps và ei = es khi thử nghiệm

cho dù hệ thống có thể được sắp xếp

Other Bandwidth Preserving Servers(Bảo tồn băng thông khác Máy chủ)

Hai thuật toán bảo tồn băng thông máy chủ

thường được sử dụng cho quá trình lập kế hoạch:

• Thường xuyên sử dụng máy chủ

• Tổng băng thông máy chủ

• Được sử dụng trong các hệ thống máy ảo, giao được biết đến

phần nhỏ của thời gian xử lý một số nhiệm vụ

• Nhằm cung cấp chia sẻ công bằng, thời gian cách ly, hoặc thông qua bảo lãnh

Constant Utilisation Server(Liên tục Utilisation Server)

Sử dụng máy chủ liên tục bảo lưu một phần nhỏ, chúng ta,

thời gian xử lý để thực hiện của máy chủ

• Giống như các máy chủ bảo tồn băng thông khác, nó có một

ngân sách và được xác định trong việc tiêu thụ và

bổ sung quy tắc

• Khi ngân sách không phải là zero, máy chủ

theo lịch trình với các nhiệm vụ khác trên cơ sở EDF

• Ngân sách và thời hạn của máy chủ được chọn sao cho việc sử dụng

của máy chủ là không đổi khi nó thực hiện, và nó luôn luôn cho

đủ ngân sách để hoàn thành công việc ở phần đầu của hàng đợi của nó mỗi lần nó

ngân sách bổ sung

• Các máy chủ không bao giờ có bất kỳ ngân sách nếu nó không có công việc để làm

Liên tục Utilisation Server

Tiêu thụ quy tắc:

• Một máy chủ sử dụng không đổi chỉ tiêu thụ ngân sách khi nó thực hiện

• Bổ sung quy định:

• Ban đầu, ngân sách es = 0 và thời hạn d = 0

• Khi một công việc không tuần hoàn với thời gian thực hiện e đến tại thời điểm t một sản phẩm nào

không tuần hoàn công việc hàng đợi

• Nếu t <d, không phải làm gì (􃱺 máy chủ đang bận, chờ cho nó để trở thành nhàn rỗi)

• Nếu t ≥ d sau đó thiết lập d = t + e / chúng tôi và es = e

• Tại d thời hạn của máy chủ

• Nếu máy chủ được backlogged, thiết lập d = d + e / chúng tôi và es = e (􃱺 bận rộn khi công việc đến)

• Nếu máy chủ là nhàn rỗi, không làm gì cả

• nghĩa là máy chủ luôn luôn được cung cấp đủ ngân sách để hoàn thành công việc tại

đứng đầu của hàng đợi của nó, với việc sử dụng được biết đến, khi ngân sách được bổ sung

Total Bandwidth Server(Tổng băng thông máy chủ)

Một máy chủ tổng băng thông được cải thiện đáp ứng

bằng cách cho phép một máy chủ để yêu cầu bồi thường thời gian nền không

được sử dụng bởi các nhiệm vụ tuần hoàn

• Thay đổi các quy tắc bổ sung một chút, để lại tất cả khác nhau:

• Ban đầu, es = 0 và d = 0

• Khi một công việc không tuần hoàn với thời gian thực hiện e đến tại thời điểm t một hàng đợi công việc trống không tuần hoàn,

set d = max (d, t) + e / chúng tôi và es = e

• Khi máy chủ hoàn thành công việc hiện tại không tuần hoàn, công việc được lấy ra từ hàng đợi và,

nếu máy chủ được backlogged, thiết lập d = d + e / chúng tôi và es = e; nếu máy chủ là nhàn rỗi, làm không có gì

• Luôn luôn sẵn sàng để thực hiện khi backlogged

• Gán chúng tôi phần ít nhất của bộ vi xử lý đến một công việc

Scheduling Sporadic Jobs(Lập kế hoạch Công Việc rời rạc)

Hãy xem xét các vấn đề lập kế hoạch công việc không thường xuyên

cùng với một hệ thống nhiệm vụ tuần hoàn và không tuần hoàn

việc làm

• Nhớ lại những vấn đề công việc lập kế hoạch rời rạc:

• Dựa trên thời gian thực hiện và thời hạn của mỗi lẻ tẻ mới đến

công việc, quyết định chấp nhận hoặc từ chối công việc

• Chấp nhận công việc ngụ ý rằng công việc sẽ hoàn thành trong thời hạn của nó,

mà không gây ra bất kỳ công việc định kỳ hoặc trước đây chấp nhận công việc không thường xuyên

bỏ lỡ thời hạn của nó

• Không chấp nhận một công việc không thường xuyên nếu không thể đảm bảo nó sẽ đáp ứng thời hạn của nó

Model for Scheduling Sporadic Jobs (Mô hình cho Lập lịch Jobs rời rạc)

Khi công việc không thường xuyên đến nơi, họ đều được chấp nhận

và dự kiến trong EDF để

• Trong một hệ thống năng động, ưu tiên, đây là thứ tự tự nhiên của thực hiện

• Trong một hệ thống ưu tiên cố định, các công việc không thường xuyên được thực hiện bởi một băng thông

bảo quản máy chủ, mà thực hiện một bài kiểm tra chấp nhận và chạy

công việc không thường xuyên trong EDF để

• Trong cả hai trường hợp, không có thuật toán lập lịch trình mới là cần thiết

• Định nghĩa:

• công việc rời rạc được biểu thị bằng Si (ri, di, ei) ri là thời gian phát hành, di

thời hạn (tuyệt đối), và ei là thời gian thực hiện tối đa

• Mật độ của một công việc không thường xuyên Δi = ei / (di-ri)

• Mật độ của một hệ thống công ăn việc làm của n là Δ = Δ1 + Δ2 + ... + Δn

• Các công việc đang hoạt động trong khoảng thời gian ri khả thi (của nó, di]

Sporadic Jobs in Dynamic-Priority Systems(Jobs rời rạc trong hệ thống Dynamic-Ưu tiên)

Định lý: Một hệ thống độc lập preemptable

công việc lẻ tẻ có thể được sắp xếp bằng cách sử dụng EDF

tổng số mật độ của tất cả các công việc hoạt động trong hệ thống ≤ 1

tất cả các lần

• Đây là bài kiểm tra lập kế hoạch tiêu chuẩn cho EDF hệ thống, nhưng bao gồm cả

công việc không thường xuyên và định kỳ

• Xét nghiệm này sử dụng mật độ kể từ khi thời hạn có thể không bằng thời gian, do đó nó

là một thử nghiệm đầy đủ, nhưng không phải là một thử nghiệm cần thiết

• Điều này có nghĩa là gì?

• Nếu chúng ta có thể bị ràng buộc tần số với các công việc không thường xuyên xuất hiện.

chạy hệ thống, chúng ta có thể đảm bảo rằng không được bỏ qua

• Ngoài ra, khi một công việc không thường xuyên đến, nếu chúng ta suy ra rằng tổng số

mật độ sẽ vượt quá 1 trong khoảng thời gian khả thi của nó, chúng tôi từ chối rời rạc

kiểm soát công việc (nhập học)

Admission Control for Sporadic Jobs/EDF()

Tại thời điểm t có n công việc hoạt động không thường xuyên, lưu trữ trong

không giảm thứ tự của thời hạn đăng ký

• Các phân vùng thời hạn thời gian từ t ∞ thành n + 1 khoảng thời gian rời rạc:

I1, I2, ..., trong +1

• I1 bắt đầu tại t và kết thúc thời hạn công việc sớm nhất rời rạc

• Đối với mỗi 1 ≤ k ≤ n, mỗi khoảng thời gian Ik 1 bắt đầu khi khoảng thời gian kết thúc Ik, và kết thúc ở tiếp theo

Hạn chót trong danh sách (hoặc ∞ Trong 1)

• Các kế hoạch duy trì Δs tổng mật độ, k của mỗi Ik khoảng thời gian

• Hãy Il là khoảng thời gian có chứa các d thời hạn chót là

công việc không thường xuyên mới S (t, d, e)

• Các kế hoạch chấp nhận công việc nếu

cho tất cả các k = 1, 2, ..., l

• tức là chấp nhận nếu công việc không thường xuyên mới có thể được thêm vào, mà không làm tăng

mật độ của bất kỳ khoảng thời gian quá khứ 1

• Ghi chú:

• kiểm tra nghiệm thu này không phải là tối ưu: một công việc không thường xuyên có thể bị từ chối ngay cả

mặc dù nó có thể được dự kiến (kết quả cho việc sử dụng schedulable

dựa trên mật độ và do đó là đủ nhưng không cần thiết)

• Nó có thể để lấy được một phức tạp hơn nhiều - biểu hiện có tính đến

tài khoản chùng thời gian, đó là tối ưu. Không rõ ràng nếu phức tạp là đáng giá.

• Thử nghiệm này chấp nhận giả định mọi công việc lẻ tẻ đã sẵn sàng để thực hiện

khi phát hành

• Nếu đây không phải là trường hợp, phải thay đổi nghiệm thu đưa vào tài khoản thời gian khi

công ăn việc làm trở nên sẵn sàng, hơn là thời gian phát hành của họ, khi kiểm tra khoảng thời gian để xem nếu họ

mật độ vượt quá 1

Sporadic Jobs in Fixed-Priority Systems(Jobs rời rạc trong hệ thống cố định ưu tiên)

Sử dụng một máy chủ không thường xuyên thực hiện các công việc không thường xuyên trong một

ưu tiên hệ thống cố định

• Các máy chủ (ps, es) có ngân sách đơn vị es ps từng đơn vị thời gian, do đó,

lịch trình có thể tính toán thời gian ít nhất có sẵn cho tất cả

công việc không thường xuyên trong hệ thống

• Giả sử rằng công việc không thường xuyên ra lệnh với nhau trong EDF

• Khi lần đầu tiên S1 công việc không thường xuyên (t, ds, 1, es, 1) đến, có ít nhất

⎣

(ds, 1 - t) / ps

⎦

⋅

es đơn vị thời gian xử lý cho máy chủ

trước thời hạn của công việc

•

⎣

(ds, 1 - t) / ps

⎦

= số lượng thời gian máy chủ có sẵn

• Vì vậy nó chấp nhận S1 nếu chùng của công việc

Sporadic Jobs in Fixed-Priority Systems (Jobs rời rạc trong hệ thống cố định ưu tiên)

Để quyết định nếu một công việc mới Si (t, ds, i, es, i) là chấp nhận được khi có được n lẻ tẻ

công ăn việc làm trong hệ thống, lần đầu tiên lên lịch tính σs chùng, i (t) của Si:

nơi ξs, k là thời gian thực hiện của các phần hoàn thành của Sk công việc

Công việc không thể được chấp nhận nếu σs, i (t) <0

• Đối với σs, 1 (t), nhưng chiếm đã chấp nhận công việc không thường xuyên

• Nếu σs, i (t) ≥ 0, scheduler sau đó kiểm tra nếu có hiện tại Sk công việc không thường xuyên với

thời hạn sau khi ds, tôi có thể bị ảnh hưởng bất lợi bởi sự chấp nhận của Si

• Kiểm tra nếu σs chùng, k (t) cho mỗi Sk vào thời điểm đó là ít nhất bằng es thời gian thực hiện, tôi Si

(tức là, Si được chấp nhận nếu σs, k (t) - es, i ≥ 0 cho mỗi Sk công việc lẻ tẻ với thời hạn ≥ ds, i)

• Thử nghiệm này chấp nhận cho hệ thống ưu tiên cố định là phức tạp hơn

cho các hệ thống năng động, ưu tiên, nhưng vẫn còn phức tạp thời gian hợp lý để

được thực hiện "on-line"

Bạn đang đọc truyện trên: Truyen2U.Pro

Trước Sau