ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM ĐỨC MẠNH
PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN
THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ
HẠN KHÔNG RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2013
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM ĐỨC MẠNH
PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN
THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ
HẠN KHÔNG RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH
Ngành: Công nghệ thông tin
Chuyên ngành: Công nghệ phần mềm
Mã số: 60 48 10
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HUYỀN CHÂU
2.2.3. Các phƣơng pháp kiểm định chính xác hệ có độ ƣu tiên cố định.............12
2.2.3.1. Response Time Analysis (RTA) .....................................................12
2.2.3.2. Processor Demand Analysis (PDA) ................................................16
CHƢƠNG 3. PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN
THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ HẠN KHÔNG
RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH .................................................................21
3.1. Một số khái niệm ............................................................................................. 21
3.2. Các kết quả ban đầu ......................................................................................... 24
3.3. Phân tích khả năng lập lịch của hệ thời gian thực sử dụng biểu đồ xấp xỉ ......28
3.3.1. Thuật toán: Approx(𝜏, 𝑖, 𝑘) .......................................................................28
3.3.2. Ví dụ minh họa ......................................................................................... 31
3.4. Tính đúng đắn của thuật toán ...........................................................................33
CHƢƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ HIỆU QUẢ CỦA BIỂU ĐỒ XẤP XỈ .......40
4.1. Phƣơng pháp thực nghiệm ...............................................................................40
4.2. Phƣơng pháp đánh giá......................................................................................41
4.3. Kết quả thực nghiệm ........................................................................................ 41
CHƢƠNG 5. KẾT LUẬN ............................................................................................. 45
5.1. Xuất xứ bài toán nghiên cứu ............................................................................45
5.2. Phƣơng pháp đề xuất và kết quả đạt đƣợc ....................................................... 45
5.3. Hƣớng phát triển trong tƣơng lai .....................................................................45
TÀI LIỆU THAM KHẢO ............................................................................................. 47
DANH MỤC CÁC TỪ VIẾT TẮT
RTA
Bộ xử lý trung tâm (Central Processing Unit).
DANH MỤC CÁC BẢNG
Số hiệu
bảng
Tên bảng
Trang
2.1
Tập các nhiệm vụ có độ ƣu tiên cố định
8
2.2
Tập các nhiệm vụ đƣợc kích hoạt từ thời điểm 𝑡 = 0
8
2.3
Tập các nhiệm vụ với kỳ hạn không ràng buộc
8
2.4
5
2.3
Chuỗi các tác vụ của một nhiệm vụ tuần hoàn 𝜏𝑖 .
6
2.4
Hàm RBF (Request Bound Function).
10
2.5
Hàm W (Workload Function).
11
2.6
Thời điểm ngặt nghèo.
12
2.7
Khoảng thời gian bận rộn mức i.
27
3.4
Tác vụ đầu tiên hoàn thành trong khoảng thời gian nguyên tố.
30
3.5
Tác vụ cuối cùng hoàn thành trong khoảng thời gian nguyên tố.
31
4.1
Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo số nhiệm vụ
của hệ.
41
4.2
Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo hệ số sử dụng
CPU.
42
4.3
thực hiện thông qua một bộ điều khiển gia nhập có khả năng quyết định chấp nhận hay
từ chối một nhiệm vụ nào đó nhằm điều tiết lƣợng công việc dựa trên các tính toán về
khả năng lập lịch. Những tính toán này đòi hỏi phải đủ nhanh do chúng đƣợc thực hiện
thƣờng xuyên trong suốt thời gian tồn tại của hệ thống.
Tồn tại 2 phƣơng pháp phân tích chính xác khả năng lập lịch của một hệ thống
thời gian thực với độ ƣu tiên cố định là Response Time Analysis (RTA - [4, 6]) và
Processor Demand Analysis (PDA - [5, 6]). Mặc dù có độ phức tạp giả đa thức nhƣng
cả 2 phƣơng pháp này đều đƣợc cài đặt rất hiệu quả trong thực tế. Tuy nhiên, với
những hệ mà các nhiệm vụ đƣợc sản sinh động, các test kiểm định đƣợc gọi liên tiếp
với số lƣợng lớn, một thuật toán với độ phức tạp giả đa thức trở nên quá chậm. Thay
vào đó, chúng ta hƣớng đến một thuật toán có độ phức tạp đa thức. Một trong số đó là
phƣớng pháp biểu đồ xấp xỉ mà luận văn sử dụng.
Việc sử dụng phƣơng pháp xấp xỉ để phân tích tính khả thi của hệ đã đƣợc trình
bày trong [2] cho trƣờng hợp các nhiệm vụ có độ ƣu tiên cố định với kỳ hạn ràng buộc
và đƣợc mở rộng cho hệ với kỳ hạn không ràng buộc trong [3]. Những kiểm định xấp
xỉ này chạy trong thời gian đa thức và đƣợc điều khiển bởi một tham số chính xác 𝜀.
Trong [10] đã đƣa ra một phƣơng pháp kiểm định xấp xỉ dựa trên khái niệm cận trên
thời gian phản ứng cho hệ có độ ƣu tiên cố định với kỳ hạn ràng buộc và độ trễ phát
hành (release jitters) và sau đó đƣợc chuẩn hóa và mở rộng trong [12, 13]. Tiếp đó,
[14] đã trình bày và sửa chữa các vấn đề kỹ thuật trong [3], đồng thời đề xuất một
thuật toán xấp xỉ cải thiện cho hệ với kỳ hạn không ràng buộc. Nó cũng đƣợc mở rộng
để tính toán cận trên thời gian phản ứng trong [11].
Nhƣ vậy, hiện chƣa có phƣơng pháp kiểm định xấp xỉ nào cho hệ có độ ƣu tiên
cố định với kỳ hạn không ràng buộc và độ trễ phát hành. Do đó, luận văn nghiên cứu
đề xuất một thuật toán kiểm định xấp xỉ cho hệ này, với mức độ xấp xỉ đƣợc tham số
hóa, cho phép chúng ta “co dãn” thuật toán để cân bằng giữa độ chính xác và độ phức
tạp của thuật toán.
2
CHƢƠNG 2. CƠ SỞ LÝ THUYẾT
2.1. Mô hình nhiệm vụ hệ thời gian thực
2.1.1. Hệ thống thời gian thực
2.1.1.1. Khái niệm
Hệ thống thời gian thực là hệ thống máy tính có khả năng phản ứng chính xác
và kịp thời với các sự kiện trong môi trƣờng. Một phản ứng xảy ra quá muộn sẽ vô ích
hoặc gây nguy hiểm cho hệ thống. Nhƣ vậy, hệ thời gian thực đƣợc hiểu nhƣ là một
mô hình xử lý mà tính đúng đắn của nó không chỉ phụ thuộc vào sự chính xác của kết
quả mà còn phụ thuộc vào thời điểm đƣa ra kết quả đó. Hệ thống bị cho là có lỗi khi
yêu cầu về thời gian không đƣợc đáp ứng.
2.1.1.2. Tầm quan trọng của hệ thời gian thực
Ngày nay, các hệ thống thời gian thực đóng một vai trò quan trọng trong xã hội
vì ngày càng có nhiều hệ thống phức tạp dựa một phần hoặc hoàn toàn vào sự điều
khiển của máy tính. Những ứng dụng về thời gian thực đã và đang đƣợc sử dụng rộng
rãi trong rất nhiều lĩnh vực nhƣ: tự động hóa công nghiệp, robot, kiểm soát tiến trình
(điều khiển nhà máy hạt nhân, hệ thống chuyển mạch đƣờng sắt, hệ thống kiểm soát
bay), trong y tế, quân sự và viễn thông …
Một trong những vấn đề thu hút sự quan tâm của giới khoa học nghiên cứu về
thời gian thực đó là điều hành thời gian thực và lập lịch vì tầm quan trọng của nó. Đa
số các vụ tai nạn xảy ra trong các nhà máy điện hạt nhân, hoặc hệ thống phòng thủ
thƣờng do lỗi của phần mềm trong hệ thống điều khiển. Một lỗi xảy ra trong quá trình
lập lịch có thể là một thảm họa, gây thiệt hại lớn về kinh tế hoặc thậm chí gây hậu quả
thảm khốc, bao gồm cả sự mất mát về ngƣời.
2.1.1.3. Phân loại nhiệm vụ thời gian thực
Ở cấp độ xử lý, sự khác biệt chính giữa một nhiệm vụ thời gian thực và một
nhiệm vụ không phải thời gian thực là nhiệm vụ thời gian thực đƣợc đặc trƣng bởi một
kỳ hạn (deadline). Đó là khoảng thời gian tối đa mà nhiệm vụ phải hoàn thành. Tùy
thuộc vào những hậu quả có thể xảy ra do kỳ hạn bị lỗi, các nhiệm vụ thời gian thực có
Cho đến nay, có rất nhiều phƣơng pháp đã đƣợc đề xuất để nâng cao khả năng
dự báo của hệ thống thời gian thực. Để trình bày những kết quả này, tôi đƣa vào các
tham số đặc trƣng của một nhiệm vụ thời gian thực. Những tham số này sẽ đƣợc sử
dụng trong các phần sau.
𝑇𝑖
𝑅𝑇𝑖
𝐶𝑖
𝐽𝑖
𝑎𝑖
𝑡
𝑟𝑖
𝑓𝑖
𝑠𝑖
𝑑𝑖
𝐷𝑖
Hình 2.1. Các tham số đặc trƣng của một nhiệm vụ thời gian thực 𝜏𝑖 .
- Thời điểm đến (Arrival time) 𝒂𝒊 : là thời điểm mà tại đó nhiệm vụ đƣợc
kích hoạt, hay nói cách khác là nhiệm vụ yêu cầu đƣợc xử lý.
5
- Thời điểm phát hành (Release time) 𝒓𝒊 : là thời điểm mà tại đó nhiệm vụ
sẵn sàng để thực hiện
khi đó, các nhiệm vụ không tuần hoàn thì các tác vụ của nó đƣợc kích hoạt không theo
chu kỳ.
Luận văn của tôi tập trung nghiên cứu các nhiệm vụ tuần hoàn. Để rõ ràng, tôi
ký hiệu một nhiệm vụ tuần hoàn là 𝜏𝑖 , tác vụ thứ 𝑙 của 𝜏𝑖 ký hiệu là 𝜏𝑖,𝑙 . Thời gian kích
hoạt của tác vụ thứ 𝑙 đƣợc cho bởi công thức 𝑎𝑖,𝑙= 𝑙 − 1 𝑇𝑖 − 𝐽𝑖 với 𝑇𝑖 là chu kỳ kích
hoạt của nhiệm vụ (khoảng thời gian giữa 2 lần kích hoạt liên tiếp của nhiệm vụ).
Trong thực tế, một nhiệm vụ tuần hoàn đƣợc đặc trƣng bởi thời gian tính toán 𝐶𝑖 , chu
kỳ 𝑇𝑖 , độ trễ phát hành 𝐽𝑖 và kỳ hạn tƣơng đối 𝐷𝑖 của nó. Gọi 𝜏 là một tập các nhiệm vụ
định kỳ, 𝜏 = 𝜏𝑖 𝑇𝑖 , 𝐶𝑖 , 𝐷𝑖 , 𝐽𝑖 , 𝑖 = 1, … , 𝑛 .
6
Tiếp theo, tôi sẽ đƣa ra những tham số đặc trƣng cho một tác vụ của nhiệm vụ
tuần hoàn.
Tác vụ thứ 𝑙 (𝜏𝑖,𝑙 )
Tác vụ đầu tiên
𝑅𝑇𝑖,𝑙
𝑇𝑖
𝜏𝑖
𝐽𝑖
𝑎𝑖,1
𝐶𝑖
𝑟𝑖,1
- Hệ số sử dụng CPU của tập các nhiệm vụ: thể hiện tỉ lệ thời gian mà CPU
đã dùng để thực thi các nhiệm vụ này. Với 𝑈𝑖 là tỉ lệ thời gian mà CPU dùng vào việc
thực thi nhiệm vụ 𝜏𝑖 , do đó hệ số sử dụng CPU cho tập n nhiệm vụ đƣợc cho bởi công
thức sau:
𝑛
𝑈≝
𝑈𝑖
𝑖=1
Đây là một tiêu chuẩn để đánh giá tải trọng của CPU cho một tập các nhiệm vụ
tuần hoàn. Một hệ thời gian thực có khả năng lập lịch thì phải đảm bảo điều kiện cần
là hệ số sử dụng CPU là 𝑈 ∈ (0, 1]. Nếu 𝑈 > 1 thì hệ không thể lập lịch bằng bất kỳ
thuật toán nào do tồn tại 𝐶𝑖 > 𝑇𝑖 .
7
2.2. Các phƣơng pháp kiểm định dựa trên độ ƣu tiên cố định
2.2.1. Một số khái niệm về lập lịch
2.2.1.1. Lập lịch là gì
- Lịch trình: khi bộ xử lý đơn phải thực hiện nhiều nhiệm vụ một cách đồng
thời, các nhiệm vụ đó có thể chồng chéo lên nhau trong thời gian chạy. Nhƣng CPU
không thể xử lý cùng lúc nhiều nhiệm vụ, do đó nó cần đƣợc phân phối cho những
nhiệm vụ khác nhau theo một tiêu chuẩn đƣợc xác định trƣớc, đó là một lịch trình.
- Lập lịch: là một tập các quy tắc xác định thứ tự thực hiện của các nhiệm vụ
hay nói cách khác là xác định lịch trình.
2.2.1.2. Phân loại lập lịch
Bảng 2.1. Tập các nhiệm vụ có độ ƣu tiên cố định
Nhiệm vụ
𝜏1
𝜏2
𝜏3
𝜏4
𝜏5
Thời gian thực hiện (ms)
10
1
2
1
5
Độ ƣu tiên
3
1
4
5
2
Sử dụng thuật toán lập lịch dựa trên độ ƣu tiên, ta có thứ tự thực hiện của các
nhiệm vụ nhƣ sau:
𝜏2
𝜏5
ri
0
0
Ci
2
4
Ti
5
7
Ta có 𝑇1 < 𝑇2 , do đó theo RM thì 𝜏1 có độ ƣu tiên cao hơn 𝜏2 .
- Lập lịch Deadline Monotonic (DM): trong thuật toán này, các nhiệm vụ
đƣợc gán độ ƣu tiên cố định tỉ lệ nghịch với kỳ hạn tƣơng đối của nó. Nghĩa là, tại mọi
thời điểm, nhiệm vụ nào càng gấp, có kỳ hạn tƣơng đối càng ngắn sẽ đƣợc ƣu tiên thực
hiện. DM đƣợc biết đến là tối ƣu cho cả trƣờng hợp kỳ hạn tƣơng đối vƣợt quá chu kỳ
(𝐷𝑖 > 𝑇𝑖 ).
Giả sử cho hệ nhiệm vụ nhƣ sau:
Bảng 2.3. Tập các nhiệm vụ với kỳ hạn không ràng buộc
Task
𝑪𝒊
𝑻𝒊
𝑫𝒊
Bài toán: Giả sử rằng các nhiệm vụ tuần hoàn chạy trên cùng một bộ xử lý, độc lập
với nhau. Tất cả các nhiệm vụ có độ ƣu tiên cố định, đƣợc thiết lập trƣớc khi ứng dụng
bắt đầu và không thay đổi trong quá trình hoạt động. Tại bất kỳ thời điểm nào, nhiệm
vụ có độ ƣu tiên cao nhất đƣợc lựa chọn để thực hiện trong số những nhiệm vụ đã sẵn
sàng. Không mất tính tổng quát, tôi giả sử rằng các nhiệm vụ đƣợc đánh chỉ số theo
thứ tự giảm dần của độ ƣu tiên: 𝜏1 có độ ƣu tiên cao nhất và 𝜏𝑛 có độ ƣu tiên thấp nhất.
Một nhiệm vụ tuần hoàn 𝜏𝑖 1 ≤ 𝑖 ≤ 𝑛 đƣợc đặc trƣng bởi thời gian thực hiện
𝐶𝑖 , kỳ hạn tƣơng đối 𝐷𝑖 , độ trễ phát hành 𝐽𝑖 và chu kỳ 𝑇𝑖 . Giả sử rằng kỳ hạn không
liên quan đến chu kỳ, hay nói cách khác là kỳ hạn không ràng buộc. Tác vụ thứ 𝑙 của
𝜏𝑖 đƣợc ký hiệu là 𝜏𝑖,𝑙 . Tôi giả sử rằng tất cả các tham số là số nguyên, 𝐽𝑖 < 𝑇𝑖 , và
𝐶𝑖 ≠ 0.
2.2.2.2. Hàm Request Bound Function (𝑅𝐵𝐹)
Hàm Request Bound Function của nhiệm vụ 𝜏𝑖 tại thời điểm t (𝑅𝐵𝐹 𝜏𝑖 , 𝑡 ) thể
hiện tổng thời gian mà 𝜏𝑖 yêu cầu CPU thực hiện trong khoảng thời gian (0, 𝑡]. Với bộ
xử lý có công suất đơn vị là 1 thì hàm này cũng chính là lƣợng công việc mà nhiệm vụ
𝜏𝑖 đòi hỏi CPU phải thực hiện trong khoảng thời gian trên.
𝑅𝐵𝐹 𝜏𝑖 , 𝑡 ≝
𝑡+𝐽 𝑖
𝑇𝑖
𝐶𝑖
(2.1)
Trong công thức này, mỗi lần nhiệm vụ 𝜏𝑖 phát hành 1 tác vụ thì 𝐶𝑖 đơn vị thời
gian xử lý đƣợc yêu cầu. Nói các khác, mỗi lần tăng lên 𝑇𝑖 đơn vị thời gian thì 𝐶𝑖 đơn
vị thời gian yêu cầu đƣợc thêm vào. Do đó, 𝑅𝐵𝐹 đƣợc gọi là hàm nhảy bậc, không liên
tục. Hàm này sẽ đƣợc sử dụng để tính tổng thời gian mà các nhiệm vụ yêu cầu CPU
Hàm Workload (𝑊𝑖,𝑙 (𝑡)) biểu diễn tổng thời gian (hay lƣợng công việc) yêu cầu
CPU thực hiện của tất các các nhiệm vụ có độ ƣu tiên cao hơn 𝜏𝑖 và thời gian thực hiện
của 𝑙 tác vụ đầu tiên của 𝜏𝑖 trong thời gian 𝑡.
𝑊𝑖,𝑙 𝑡 ≝ 𝑙𝐶𝑖 +
𝑗
t
𝑇2
−𝐽3
t
𝑇3
0
t
Hình 2.6. Thời điểm ngặt nghèo.
2.2.2.5. Khoảng bận rộn mức i (level-i busy period)
Để xác định thời gian phản ứng trong trƣờng hợp xấu nhất của nhiệm vụ 𝜏𝑖 ,
khái niệm về khoảng bận rộn mức 𝑖 đƣợc giới thiệu. Khoảng thời gian khi mà chỉ có
các nhiệm vụ với độ ƣu tiên cao hơn hoặc bằng 𝑖 đang thực hiện. Khoảng thời gian này
đƣợc gọi là khoảng bận rộn mức 𝑖 (level- 𝑖 busy period [2,3]).
𝑅𝑇𝑖,1
𝑇𝑖
...
𝑎𝑖,1
𝑎𝑖,2 𝑓𝑖,1
𝑎𝑖,3
13
Dựa trên hàm 𝑊𝑖,𝑙 (𝑡) biểu diễn lƣợng công việc mà tác vụ 𝜏𝑖,𝑙 yêu cầu CPU xử
lý, chúng ta định nghĩa giao điểm đầu tiên giữa hàm này và đƣờng 𝑦 = 𝑡, ký hiệu là
𝑅𝑖,𝑙 cho mỗi tác vụ 𝜏𝑖,𝑙 nhƣ sau:
𝑅𝑖,𝑙 ≝ min 𝑡 > 0 | 𝑊𝑖,𝑙 𝑡 = 𝑡
(2.3)
Trong công thức trên, 𝑅𝑖,𝑙 chính là giao điểm mà tại đó lƣợng công việc yêu cầu
CPU thực hiện đúng bằng công suất của CPU. Nói cách khác là tại điểm này nhiệm vụ
đƣợc hoàn thành. Và nếu chúng đƣợc hoàn thành trong kỳ hạn thì nhiệm vụ có khả
năng lập lịch.
Tải
𝑦=𝑡
𝑊𝑖,𝑙 𝑡
𝑅𝑖,𝑙
𝑊𝑖,𝑙 𝑡 = 𝑡
: Điểm hoàn thành nhiệm vụ
t
0
Hàm tải công việc
Hàm công suất bộ xử lý
Hình 2.8. Hàm W (Workload Function) trong phƣơng pháp RTA.
Gọi số tác vụ trong khoảng bận rộn mức 𝑖 là 𝑁𝑖 , thì 𝑁𝑖 chính là chỉ số của tác vụ
cuối cùng trong khoảng này hay là chỉ số của tác vụ đầu tiên mà không lấn sang tác vụ
tiên 𝜏𝑖,1 theo cách sau: 𝑊𝑖,1 =
(𝑘+1)
Tiếp tục tính 𝑊𝑖,1
𝑖
𝑗 =1
𝐶𝑗 .
𝑘+1
nhƣ sau: 𝑊𝑖,1
= 𝐶𝑖 +
(𝑘)
𝑖−1
𝑗 =1 𝑅𝐵𝐹(τj , 𝑊𝑖,1 ).
(𝑘)
Với 𝑊𝑖,1 là lƣợng công việc mà 𝜏𝑖,1 yêu cầu CPU thực hiện ở lần thứ k.
(𝑘+1)
Việc tính toán sẽ dừng lại khi 𝑊𝑖,1
(𝑘)
= 𝑊𝑖,1 , lúc này lƣợng công việc mà tác
(𝑘)
Với 𝑊𝑖,𝑙 là lƣợng công việc mà tác vụ 𝜏𝑖,𝑙 yêu cầu CPU thực hiện ở lần thứ k.
(𝑘+1)
Việc tính toán sẽ dừng lại khi 𝑊𝑖,𝑙
(𝑘)
= 𝑊𝑖,𝑙 , lúc này lƣợng công việc mà tác
(∗)
vụ 𝜏𝑖,𝑙 yêu cầu CPU thực hiện không thay đổi. Khi đó, điểm chững 𝑊𝑖,𝑙 = 𝑅𝑖,𝑙 . Thời
(∗)
gian phản ứng của tác vụ 𝜏𝑖,𝑙 là: 𝑅𝑇𝑖,𝑙 = 𝑊𝑖,𝑙 − 𝑟𝑖,𝑙 . So sánh giá trị này với 𝑇𝑖 , nếu
𝑅𝑇𝑖,𝑙 > 𝑇𝑖 , nghĩa là khoảng bận rộn mức i chƣa kết thúc, ta xét tiếp tác vụ 𝜏𝑖,𝑙+1 .
Ngƣợc lại, chứng tỏ khoảng bận rộn đã kết thúc, chúng ta dừng việc tính toán.
Thời gian phản ứng trong trƣờng hợp tồi nhất của τ𝑖 đƣợc tính theo công thức:
𝑅𝑇𝑖 = max𝑙 ≤ 𝑁𝑖 𝑅𝑇𝑖,𝑙 . So sánh giá trị này với 𝐷𝑖 để xác định khả năng lập lịch của
nhiệm vụ τ𝑖 .
(0)
Trong phƣơng pháp này, giá trị của 𝑊𝑖,𝑙 đóng vai trò quan trọng trong việc
giới hạn số lần tính toán để tìm ra điểm nhỏ nhất mà 𝑊𝑖 𝑡 = 𝑡.
Ví dụ: Cho hệ nhiệm vụ với kỳ hạn không ràng buộc và độ trễ phát hành nhƣ sau:
Bảng 2.4. Hệ với kỳ hạn không ràng buộc và độ trễ phát hành
15
τ3
3
15
8
5
Xét nhiệm vụ τ1 :
(0)
𝑊1,1 = 1
(1)
𝑊1,1 = 1 ⟹ 𝑅1,1 = 1
⟹ 𝑅𝑇1,1 = 1 + 𝐽1 = 1 + 2 = 3 < 𝑇1 = 4
-
⟹ 𝑅𝑇1 = max 𝑅𝑇1,𝑙 = 3 < 𝐷1 = 8. Do đó, τ 1 có khả năng lập lịch.
Xét nhiệm vụ τ 2
(0)
+ 𝑊2,1 = 𝐶2 + 𝐶1 = 2 + 1 = 3
(1)
3+𝐽 1
(1)
𝑊2,2 = 2 ∗ 𝐶2 +
(2)
𝑊2,2 = 2 ∗ 𝐶2 +
𝑇1
6+𝐽 1
𝑇1
=4+
=4+
5+2
4
6+2
=6
= 6 ⟹ 𝑅2,2 = 6
4
⟹ 𝑅𝑇2,2 = 𝑅2,2 − 2 − 1 𝑇2 + 𝐽2 = 3 < 𝑇2 = 6
-
⟹ 𝑅𝑇2 = max 𝑅𝑇2,𝑙 = 7 = 𝐷2 . Do đó τ 2 có khả năng lập lịch.
Tƣơng tự với τ 3
(0)
𝑇2
8+𝐽 2
𝑇2
=3+
=3+
=3+
6+2
4
7+2
4
8+2
4
6+3
+
=7
6
7+3
+
=8
6
8+3
𝑇1
+
+
+
9+𝐽 2
𝑇2
11+𝐽 2
𝑇2
13+𝐽 2
𝑇2
=6+
=6+
=6+
9+2
+
4
11+2
4
13+2
4
9+3
6
16+𝐽 1
(3)
𝑇1
18+𝐽 1
𝑊3,3 = 3 ∗ 𝐶3 +
𝑊3,3 = 3 ∗ 𝐶3 +
𝑇1
+
+
+
12+𝐽 2
𝑇2
16+𝐽 2
𝑇2
18+𝐽 2
𝑇2
=9+
=9+
=9+
12+2
4
16+2
cho hệ có độ trễ phát hành nhƣ sau:
Định lý 1: Hệ nhiệm vụ 𝜏 với độ trễ phát hành có khả năng lập lịch khi và chỉ khi
∀ τ𝑖 ∈ τ, ∀ 𝑙 𝑙 > 0 ∈ N, ∃ t ∈ (𝑟𝑖,𝑙 , 𝑑𝑖,𝑙 ], 𝑊𝑖,𝑙 (𝑡) ≤ 𝑡.
Để xác định độ phức tạp của thuật toán, chúng ta cần xác định đƣợc các thời
điểm mà tại đó định lý 1 cần đƣợc kiểm tra. Nhƣ trong [5], chúng ta có thể thiết lập tập
các điểm lập lịch trong khoảng bận rộn cần xét nhƣ sau:
𝑆𝑖 = {𝑎𝑇𝑏 − 𝐽𝑏
𝑏 = 1 … 𝑖 − 1, 𝑎 = 1 …
𝐷𝑖 + 𝐽 𝑏
𝑇𝑏
∪ {𝐷𝑖 }
(2.7)
17
Tải
y=t
𝑊𝑖,𝑙 (𝑡)
𝑊𝑖,𝑙 𝑡 ≤ 𝑡
Điểm cắt
Điểm lập lịch đầu tiên
sau điểm cắt
+ Nếu không tồn tại ⟹ kết luận nhiệm vụ không lập lịch đƣợc.
∗
+ Nếu tồn tại ⟹ xét xem có tồn tại 𝑡𝑖,2
∈ 0, 2𝑇𝑖 không ?
• Nếu tồn tại ⟹ kết luận nhiệm vụ lập lịch đƣợc và kết thúc.
• Ngƣợc lại ⟹ tiếp tục bƣớc 3.
∗
Bƣớc 𝑘: Xét xem có tồn tại 𝑡𝑖,𝑘
∈ 0, 𝑘 − 1 𝑇𝑖 + 𝐷𝑖 không ?
+ Nếu không tồn tại ⟹ kết luận nhiệm vụ không lập lịch đƣợc.
∗
+ Nếu tồn tại ⟹ xét xem có tồn tại 𝑡𝑖,𝑘
∈ 0, 𝑘𝑇𝑖 không ?
•
•
Nếu tồn tại ⟹ kết luận nhiệm vụ lập lịch đƣợc và kết thúc.
Ngƣợc lại ⟹ tiếp tục bƣớc 𝑘 + 1.
18
∗
Ở mỗi bƣớc, 𝑡𝑖,𝑘
chính là điểm cắt đầu tiên không lấn sang tác vụ kế tiếp. Để tìm
∗
𝑡𝑖,𝑘
∈ (0, 𝑡𝑟 ) ta thực hiện nhƣ sau:
Xây dựng tập 𝑆𝑖,𝑡 𝑟 :
+ 𝑆1,4 = 2, 4
∗
∗
⟹ Tồn tại 𝑡1,1
∈ 0, 𝐷1 và 𝑡1,1
∈ 0, 𝑇1 để 𝑊1 (𝑡) ≤ 𝑡.
Do đó 𝜏1 lập lịch đƣợc.
-
Xét nhiệm vụ 𝜏2 :
∗
Bƣớc 1: Xét xem có tồn tại 𝑡2,1
∈ 0, 𝐷2 không ?
+ 𝑆2,7 = 2, 6, 7
𝑊2,1 2 = 1. 𝐶2 +
𝑊2,1 6 = 1. 𝐶2 +
2+ 𝐽 1
𝑇1
6+ 𝐽 1
𝑇1
𝐶1 = 2 +
𝐶1 = 2 +
2+ 2
𝑇2
Copyright: Tài liệu đại học ©