Luận văn Nghiên cứu giải thuật định thời cho các bài toán song song, độc lập trên môi trường tính toán lưới

14 Chương 3. Những nghiên cứu về lập lịch trên môi trường tính toán lưới 3.1 Giới thiệu bài toán lập lịch Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường tính toán phân tán như môi trường tính toán lưới. Quá trình lập lịch là quá trình quyết định sẽ thực thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là thích hợp nhất do đó sẽ ảnh hưởng rất lớn đến hiệu năng hoạt động của hệ thống. Quá trình lập lịch trên môi trường lưới có nhiều khó khăn và thách thức hơn so với môi trường khác vì số lượng công việc và các nguồn tài nguyên thường rất lớn. Mặt khác các tài nguyên này còn nằm phân tán và hỗn tạp, mỗi nguồn tài nguyên có thể do một tổ chức riêng biệt quản lý, có các chính sách và chi phí hoạt động khác nhau, bên cạnh đó tải (load) và tính sẵn sàng (availability) của các hệ thống cũng rất khác nhau; do đó vấn đề lập lịch (scheduling) trong hệ thống lưới vẫn còn đòi hỏi nhiều công sức nghiên cứu [5]. Có khá nhiều câu hỏi được đặt ra và cần giải quyết khi nghiên cứu về quá trình lập lịch trong môi trường tính toán lưới: • Mối liên hệ và tác động lẫn nhau giữa các ứng dụng trong quá trình thực thi • Những đòi hỏi, yêu cầu khác nhau của từng ứng dụng trong hệ thống • Sự không đồng nhất và biến động của các nguồn tài nguyên trong môi trường • Mô hình hoạt động và các chính sách về truy xuất, bảo mật … của hệ thống 3.2 Các ứng dụng song song, độc lập Trong môi trường tính toán lưới, lớp bài toán gồm các tác vụ độc lập với nhau hiện đang được tập trung nghiên cứu. Bài toán dạng này là một trong những bài toán đặc trưng, thường thấy trên môi trường lưới [6], thông thường sẽ bao gồm N tác vụ độc lập (các tác vụ này có thể thực thi cùng một chức năng tính toán, nhưng 15 trên các tập dữ liệu khác nhau) chạy trên M máy tính phân tán, N sẽ lớn hơn M nhiều lần. Đây là một mô hình tính toán đơn giản nhưng lại được sử dụng nhiều trong những bài toán lớn và hữu ích: phân tích cấu trúc protein, phân tích hoạt động của não bộ, mô phỏng chuyển động và sự va chạm của một hệ thống, phân tích các dữ liệu vật lý, kinh tế… [11]. Việc lập lịch cho các ứng dụng độc lập tưởng chừng như đơn giản, tuy nhiên khi kết hợp vào một số yêu cầu của người dùng như ràng buộc về thời hạn kết thúc (deadline), chi phí hoạt động (budget) và một vài yêu cầu riêng biệt khác sẽ trở thành một bài toán lớn và khá phức tạp. Luận văn cũng sẽ tập trung nghiên cứu các bài toán gồm nhiều tác vụ song song, có thể thực thi hoàn toàn độc lập với nhau trong quá trình hoạt động như hình 3-1 Hình 3-1 Mô hình ứng dụng: các tác vụ độc lập 3.3 Các hướng nghiên cứu trong bài toán lập lịch Hầu hết mọi nghiên cứu về lập lịch trên môi trường lưới ngày nay đều nhắm vào hai mục tiêu: (a) performance-base: tận dụng tối đa hiệu năng của hệ thống, giảm thiểu thời gian hoạt động; (b) economics-base: giảm thiểu chi phí hoạt động của hệ thống [7]. Việc tận dụng tối đa hiệu năng của hệ thống, đưa thời gian cần thiết để giải quyết công việc xuống mức mức thấp nhất là một nhu cầu thực tế, là yếu tố được nghĩ đến đầu tiên khi triển khai ứng dụng trên môi trường lưới. Do đó hiển nhiên đây là một hướng nghiên cứu quan trọng. 16 Ngoài ra, việc lập lịch theo chi phí vận hành hệ thống cũng là một hướng nghiên cứu cần thiết trong thực tế, nhất là trong những hệ thống lưới đã được thương mại hóa. Người sử dụng muốn thực thi ứng dụng của mình trên môi trường lưới cần phải trả phí (phí này có thể tính trên thời gian thực thi của ứng dụng- cost per time, hoặc tính trên số thao tác tính toán của ứng dụng – cost per instruction, tùy theo chính sách của người quản trị tài nguyên qui định). Việc qui định chi phí thực thi sẽ khuyến khích những tổ chức có tài nguyên rảnh (idle resources) tham gia vào hệ thống, mở rộng qui mô hệ thống lưới và việc phân bố các tác vụ sao cho chi phí thực thi thấp nhất là một nhu cầu thiết thực với người sử dụng trên môi trường tính toán lưới. 3.4 Lập lịch theo hiệu năng hệ thống Như đã trình bày, các nghiên cứu dạng này hướng đến mục đích giảm tối đa thời gian hệ thống cần thiết để hoàn tất các ứng dụng, thời gian này được gọi là makespan của hệ thống. Có nhiều hướng tiếp cận khác nhau được đề cập đến trong nghiên cứu [8],[9]: OLB, MCT, Min-Min, Max-Min, Sufferage… 3.4.1 OLB (Opportunistic Load Balancing) Đây là chiến lược rất đơn giản, phân phối công việc cho tài nguyên có thời điểm sẵn sàng sớm nhất mà không quan tâm đến thời gian thực thi của công việc trên tài nguyên đó. 3.4.2 MET (Minimum Execution Time) Ngược lại với OLB, phân phối công việc vào các tài nguyên có khả năng thực thi công việc nhanh nhất, không quan tâm đến thời điểm bắt đầu và kết thúc của công việc trên tài nguyên đó. Thuật giải này thường có nhược điểm là không cân bằng tải vì hầu như các công việc đều được tập trung thực thi trên các tài nguyên có năng lực cao nhất Ví dụ: 17 Giả sử ta có 2 tác vụ cần thực thi là T1,T2. Các tác vụ lần lượt có kích thước T1=60, T2=120. Hệ thống có 2 máy tính cụm, mỗi máy tính cụm có 2 máy tính (host), năng lực lần lượt là: Cluster 1: H1=30, H2=60 Cluster 2: H3=45, H4=50 Gọi Eij = Ti/Hj là thời gian thực thi của tác vụ i trên host j, ta có: E11=T1/H1=2 E21=T2/H1=4 E12=T1/H2=1 (nhỏ nhất) E22=T2/H2=2 (nhỏ nhất) E13=T1/H3=1.3 E23=T2/H3=2.6 E14=T1/H4=1.2 E24=T2/H4=2.4 Như vậy cả 2 tác vụ đều thực thi trên host H2, makespan của hệ thống = 1 + 2 = 3 3.4.3 MCT (Minimum Completion Time) Dựa trên khái niệm thời gian hoàn thành nhỏ nhất của tác vụ. Thời gian hoàn thành được tính bằng thời gian thực thi của tác vụ cộng với thời gian sẵn sàng của tài nguyên. Việc dựa trên thời gian hoàn thành nhỏ nhất sẽ giúp hệ thống cân bằng tải tốt hơn. Ví dụ: Các số liệu tương tự như mục 3.4.2, ta định nghĩa Cij = Bj + Eij với Cij là thời gian hoàn thành của tác vụ i trên host j, Bj là thời gian sớm nhất host j có thể thực thi tác vụ (thời gian sẵn sàng). C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 C22= B2 + E22 = 0 + 2 =2 C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 18 Tác vụ T1 theo thứ tự được chọn tài nguyên trước, sẽ chọn thực thi trên host H2 (thời gian hoàn thành thấp nhất). Thời gian bắt đầu B2 được cập nhật thành 1, vì chỉ sau thời điểm này H2 mới có thể thực thi các tác vụ khác. Giá trị E22 thay đổi: B2=1 C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. Chúng ta có thể thấy, dựa vào giá trị MCT hệ thống sẽ cân bằng hơn dựa vào giá trị MET. 3.4.4 Thuật giải Min – Min Thuật giải Min – Min sẽ tính toán thời gian hoàn thành của tất cả các tác vụ trên tất cả các tài nguyên hiện có. Tác vụ nào có giá trị MCT nhỏ nhất sẽ được phép chọn tài nguyên trước. Sau đó cập nhật thời gian sẵn sàng cho tài nguyên được chọn, tính toán lại thông số với tất cả các tác vụ chưa được điều phối. Quá trình lặp lại cho đến khi tất cả các tác vụ đều đã chọn được tài nguyên thực thi. Ta định nghĩa một số khái niệm: T là tập các tác vụ, Hj,k là máy (host) thứ k của cluster j. C(Ti,Hj,k) là thời gian hoàn thành tác vụ Ti trên host Hj,k. Gọi f là một ánh xạ từ Rn vào R, toán tử argmin được định nghĩa: f(argminxєRn f(x))=minxєRn(f(x)) Chú thích: Gía trị C(Ti,Hj,k) là thời gian hoàn thành của tác vụ Ti trên host Hj,k. Lúc này nếu argminj,k(C(Ti,Hj,k)) gồm 2 thành phần (ܿ௜ଵ ,  ݄௜ଵ ) thì giá trị C(Ti,  ܪ௖೔భ,௛೔భ )) là nhỏ nhất. Host ݄௜ଵ trên cluster ܿ௜ଵ là host có khả năng hoàn tất tác vụ Ti sớm nhất. Thuật giải Min-Min: 19 Ví dụ, với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 MCT(T1) nhỏ hơn, do đó tác vụ T1 được chọn host H1 để thực thi trước. Giá trị E22 thay đổi: B2=1 C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. 3.4.5 Thuật giải Max-Min Tương tự như thuật giải Min-Min, tuy nhiên thuật giải Max-Min cho phép các tác vụ có MCT lớn hơn được ưu tiên chọn host để thực thi trước. Thuật giải này được đánh giá tốt và cân bằng hơn Min-Min vì trong khi các tác vụ dài hơn được ưu tiên chọn thiết bị tốt để thực thi trước, các tác vụ ngắn có thể luân phiên thực thi ở while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) end foreach s=argmini(C(Ti, ܪ௖೔భ,௛೔భ)) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 20 các thiết bị có năng lực yếu hơn. Các tác vụ dài không phải mất thời gian chờ các tác vụ ngắn hơn như ở thuật giải Min-Min. Toán tử argmax được định nghĩa tương tự toán tử argmin f(argmaxxєRn f(x))=maxxєRn(f(x)) Thuật giải Max-Min: Ví dụ: Cũng với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 Lúc này tác vụ T2 có MCT lớn hơn nên được phép chọn host thực thi trước. T2 sẽ thực thi trên host H2. Giá trị B2 = 2 C12 = B2 + E12 = 2 + 1 =3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 = 1.2 là nhỏ nhất while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) end foreach s=argmaxi(C(Ti, ܪ௖೔భ,௛೔భ)) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 21 Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song (nhỏ hơn với trường hợp Min-Min) 3.4.6 Thuật giải Sufferage Suferage lấy ý tưởng từ thuật giải Min-Min và Max-Min đã đề ra trước đó. Thuật giải Sufferage tính toán giá trị MCT thấp nhát và thấp nhì đối với từng tác vụ trong hệ thống. Giá trị này được gọi là độ “thiệt hại” (suffering) của một tác vụ khi nó không được thực thi trên tài nguyên tốt nhất. Tác vụ có độ thiệt hại lớn nhất sẽ được ưu tiên chọn tài nguyên để thực thi trước. Thuật giải Sufferage: Thuật giải này đặc biệt hiệu quả nếu tính đến vấn đề vận chuyển dữ liệu đến nơi thực thi tác vụ. Nếu một tài nguyên đã có sẵn dữ liệu của một tác vụ, tác vụ nếu thực thi trên tài nguyên này sẽ tiết kiệm được thời gian rất nhiều so với khi thực thi trên một tài nguyên khác. Tác vụ trong trường hợp này sẽ có giá trị Sufferage cao nên được ưu tiên thực thi trước. Ví dụ: Cũng với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) (ܿ௜ଶ, ݄௜ଶ)=argminj≠ci1,k≠hi1(C(Ti,Hj,k)) sufi=C(Ti,Hci2, hi2)-C(Ti, Hci1, hi1) end foreach s=argmaxi(sufi) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 22 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị Suff(T1)= C14 – C12 = 0.2 Giá trị Suff(T2)= C24 – C22 = 0.4 Vì suff(T2) cao hơn nên tác vụ T2 được phép chọn host H2 để thực thi trước. Giá trị B2 = 2 C12 = B2 + E12 = 2 + 1 = 3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 = 1.2 là nhỏ nhất Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song. Ví dụ ở trên khá đơn giản, chỉ có chiều dài tác vụ ảnh hưởng đến thời gian thực thi của tác vụ nên trường hợp Sufferage khá giống Max – Min. 3.4.7 Thuật giải XSufferage Do nhóm nghiên cứu Casanova đề ra [10], phát triển từ thuật toán Sufferage. Các máy tính trong một Máy tính cụm thường có năng lực như nhau, do đó giá trị sufferage thường dần về 0. Điều này khiến một tác vụ Ti, khi rất cần chạy trên máy tính cụm j (ví dụ dữ liệu input của Ti đã nằm sẵn trên máy tính cụm j), nhưng trong trường hợp máy tính cụm này lại có 2 máy năng lực tương đương nhau khiến Suff(Ti) ≈ 0 nên Ti sẽ không có cơ hội chạy trên máy tính cụm j. Cải tiến ở đây là khái niệm Suf sẽ được tính ở mức cluster, không phải ở mức host. Thuật giải XSufferage: while (T ≠ Ø) foreach (Ti є T) foreach cluster j hi,j=argmink(C(Ti,Hj,k)) end foreach ܿ௜ ଵ = argminj(C(Ti,H௝,௛೔,ೕሻሻ //Cluster có MCT nhỏ nhất 23 ܿ௜ ଶ = argmin௝ஷ௖೔భ(C(Ti,H௝,௛೔,ೕሻሻ //Cluster có MCT nhỏ nhì sufi = C(Ti,ܪ௖೔మ,௛೔,೎೔మ ሻ െ CሺTi, ܪ௖೔భ,௛೔,೎೔భ ሻ //Tính suf trên 2 cluster nhỏ nhất và nhì end foreach s=argmaxi(sufi) assign Ts to ܪ௖ೞభ,௛ೞ,೎ೞభ T=T-{Ts} end while Đặc điểm các thuật giải trên: ™ Phải duyệt tất cả các máy trong mọi máy tính cụm có thể dẫn đến độ phức tạp rất lớn ™ Ứng dụng là ứng dụng rất lớn gồm rất nhiều tác vụ chạy song song, các tác vụ đóng vai trò như sau. ™ Một task có thể chạy trên host bất kỳ, không có sự ràng buộc về địa điểm thực thi. 3.4.8 Các thuật giải điều phối cho các ứng dụng vừa và nhỏ Tác giả Trần Công Tú trong luận văn nghiên cứu về lập lịch [20] đã đề xuất một giải pháp lập lịch cho các ứng dụng vừa và nhỏ trong hoàn cảnh Việt Nam. Tác giả đã tập trung gom nhóm mỗi ứng dụng con lên một máy tính cụm, ưu tiên hoàn thành từng ứng dụng một cách nhanh nhất, trước khi tiếp tục cho các ứng dụng chưa được phân tài nguyên. Đây cũng là một hướng tiếp cận mà luận văn này kế thừa và tập trung nghiên cứu sâu hơn. 24 3.5 Lập lịch theo hiệu năng kinh tế Với bài toán lập lịch này, thay vì chỉ chú trọng đến thời gian thực thi của hệ thống ta còn phải quan tâm đến một khía cạnh không kém quan trọng là hiệu quả về mặt kinh tế của hệ thống. Mỗi tác vụ lúc này sẽ có hai ràng buộc đi kèm: - Deadline: thời hạn thực thi cuối cùng của tác vụ, tác vụ phải được thực thi xong trước thời điểm này - Budget: ngân sách của tác vụ, chi phí thực thi tác vụ phải nhỏ hơn ngân sách của tác vụ đó. Việc nghiên cứu về bài toán lập lịch dạng này nhìn chung phức tạp hơn ở trường hợp chỉ chú trọng đến thời gian thực thi, vì bây giờ mỗi tác vụ cần thỏa mãn cùng lúc 2 ràng buộc. Cũng đã có khá nhiều nghiên cứu về các thuật giải lập lịch có chú trọng đến hiệu năng kinh tế của hệ thống 3.5.1 Time Minimization Thuật giải Time Minimization [3] đặt mục tiêu hoàn thành các công việc một cách nhanh nhất có thể trong điều kiện ràng buộc của ngân sách (Budget). Thuật giải có thể được mô tả như sau: • Lấy ra một tác vụ chưa được điều phối: o Với mỗi tài nguyên, tính toán thời gian hoàn thành cho tác vụ đó (đã xem xét đến các tác vụ đang có sẵn tại tài nguyên này trước đó) o Sắp xếp các tài nguyên theo thời gian hoàn thành tăng dần o Điều phối tác vụ vào tài nguyên đầu tiên thỏa mãn ràng buộc (chi phí thực thi trên tài nguyên đó thấp hơn hoặc bằng ngân sách của tác vụ) • Lập lại cho đến khi tất cả các tác vụ đều được điều phối 25 3.5.2 Cost Minimization Thuật giải Cost Minimization [3] đề ra hướng tiếp cận khác so với Time Minimization, tập trung thực thi các tác vụ sao cho chi phí là thấp nhất trong điều kiện ràng buộc về thời điểm kết thúc (Deadline). Thuật giải được mô tả như sau: • Sắp xếp các tài nguyên theo chi phí thực thi tăng dần • Với mỗi tài nguyên theo thứ tự đó, điều phối tối đa số lượng tác vụ lên tài nguyên trong khi chưa vi phạm ràng buộc về Deadline. Cả hai thuật giải này đều chưa chú ý đến việc sắp xếp thứ tự các tác vụ được điều phối và broker phải làm việc trực tiếp với từng tài nguyên trong hệ thống dẫn đến thời gian điều phối có thể rất lớn. 3.5.3 DBC (Deadline and Budget constrained scheduling) Thuật giải DBC [11] được nhóm nghiên cứu Buyya cải tiến dựa trên thuật giải Time Minimization và Cost Minimization, nhắm đến mục tiêu không chỉ tối ưu về chi phí phát sinh mà còn giảm thiểu thời gian thực thi khi điều kiện cho phép. Thuật giải có thể được mô tả như sau: • Sắp xếp các tài nguyên theo giá thành tăng dần, nếu các tài nguyên có cùng chi phí ưu tiên cho các tài nguyên có năng lực tính toán mạnh hơn xếp trước. • Tạo thành các nhóm tài nguyên bao gồm các tài nguyên có cùng chung giá thành • Khi còn tác vụ chưa được điều phối, thực hiện các bước sau với mỗi nhóm tài nguyên: o Ứng với mỗi tác vụ trong tập các tác vụ chưa điều phối: ƒ Với mỗi tài nguyên trong nhóm, tính toán thời gian hoàn thành của tác vụ trên tài nguyên đó ƒ Điều phối tác vụ cho tài nguyên có khả năng hoàn thành tác vụ đó sớm nhất, đánh dấu tác vụ đã được điều phối. 26 ƒ Nếu không có tài nguyên thỏa mãn ràng buộc, tác vụ được giữ nguyên và sẽ tìm kiếm tài nguyên trong các nhóm tài nguyên có giá thành cao hơn. Thuật giải sẽ chia tài nguyên thành các nhóm có giá thành ngang nhau, tìm kiếm tài nguyên tốt nhất trong một nhóm. Khi không thỏa mãn mới chuyển sang nhóm có giá thành cao hơn. Thuật giải đã cố gắng tạo sự cân bằng giữa 2 yếu tố chi phí và thời gian thực thi. 3.5.4 HRED (Highest Rank Earliest Deadline) Được đề ra bởi nhóm nghiên cứu Subodha Kumar và Kaushik Dutta [7], với mục tiêu giảm thiểu chi phí thực thi của hệ thống trong điều kiện ràng buộc về thời gian. Nhóm nghiên cứu tiếp cận bài toán lập lịch theo quan điểm một hệ bất phương trình. Tuy nhiên việc giải một hệ bất phương trình dẫn đến thời gian tính toán quá dài, không khả thi trong thực thế. Nhóm nghiên cứu đề ra thuật giải HRED (Highest Rank Earliest Deadline) nhằm ứng dụng được trong thực tế. Theo các số liệu thực nghiệm của nhóm nghiên cứu, kết quả của thuật giải HRED có chênh lệch khoảng 3% - 4% so với việc giải hệ bất phương trình. Một số qui ước: • tij: thời gian thực thi của tác vụ i trên tài nguyên thứ j. • pj: giá thành của tài nguyên j • Bi: ngân sách của tác vụ i • Li: khoản tiền phải bồi thường khi từ chối thực thi tác vụ i. Tham số này đại diện cho độ ưu tiên của một tác vụ, tác vụ có khoản tiền phạt càng cao càng được hệ thống ưu tiên thực thi. Qui định Li ≥ Bi (khoản tiền phạt lớn hơn ngân sách của một tác vụ). • Vij = (Li – tijpj) là hiệu số của khoản tiền phạt so với chi phí thực thi tác vụ i trên tài nguyên j. Khi hệ thống từ chối một tác vụ Ti, ta có thể tiết kiệm được 27 một phần chi phí thực thi tác vụ tijpj nhưng phải trả khoản tiền phạt Li. Có thể xem Vij là khoản chi phí hệ thống bị thiệt hại khi từ chối thực thi tác vụ Ti. Thuật giải HRED sẽ chú trọng làm cho các khoản thiệt hại này là bé nhất. Thuật giải được mô tả như sau: Bước 1: Tính toán giá trị Vij = (Li – tijpj) cho mỗi tác vụ i và tài nguyên j, sắp xếp tập giá trị V theo thứ tự Vij giảm dần. Bước 2: Xóa bỏ các giá trị Vij âm vì khi đó tijpj > Bi (vì Li ≥ Bi) Bước 3: Gọi ViMax jMax là giá trị lớn nhất trong tập V, T là tập các tác vụ hiện đã được điều phối trên tài nguyên jMax. Bước 4: Tập T’ là kết hợp tác vụ iMax và tập tác vụ T, sắp xếp T’ theo Deadline tăng dần. Cố gắng thực thi tập tác vụ T’ trên tài nguyên jMax theo thứ tự đã sắp xếp. Nếu tập T’ có thể thực thi thành công mà không vi phạm các ràng buộc về giá và thời gian thì tác vụ iMax có khả năng thực thi trên tài nguyên jMax. Bước 5: Nếu điều kiện ở bước 4 thỏa mãn, điều phối tác vụ iMax cho tài nguyên jMax. Xóa bỏ tất cả các tổ hợp của iMax trong tập V. Bước 6: Nếu tập tác vụ V còn tác vụ chưa điều phối, quay trở lại bước 3. Độ phức tạp O(m2nlogm) 3.5.5 Các mô hình thường áp dụng trong bài toán lập lịch theo hiệu năng kinh tế Để phục vụ cho bài toán lập lịch theo hiệu năng kinh tế, có nhiều mô hình đã được đề ra. Các mô hình này đều hoạt động dựa trên quá trình giao tiếp giữa người mua (user) và người bán (resource) nhằm tìm ra chi p