Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới

Tăng Cẩm Nhung<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 65(03): 134 - 138<br /> <br /> NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN LẬP LỊCH<br /> VÀO MÔI TRƯỜNG TÍNH TOÁN LƯỚI<br /> Tăng Cẩm Nhung<br /> Trường Đại học Kỹ thuật Công nghiệp – ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> Nhờ có nhiều tiến bộ trong công nghệ mạng và các nguồn tài nguyên máy tính phong phú, công<br /> nghệ tính toán lưới đã ra đời và hiện nay là một lĩnh vực nghiên cứu khá hiệu quả. Một đặc điểm<br /> nổi bật của tính toán lưới đó là có thể kết hợp các nguồn tài nguyên phân tán rộng khắp và cung<br /> cấp số lượng dịch vụ không nhỏ cho người sử dụng. Để đạt được các mục tiêu đó, hệ thống lập<br /> lịch hiệu quả là một phần thiết yếu của lưới. Bài báo nghiên cứu và ứng dụng thuật toán lập lịch<br /> trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất<br /> các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min,<br /> Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán<br /> này khi được áp dụng vào mô hình cụ thể.<br /> Từ khóa: Tính toán lưới, lập lịch,OLB, MET,MCT,Max-Min, Min – Min, Sufferage, xSufferage<br /> <br /> ĐẶT VẤN ĐỀ<br /> Cũng như các công nghệ tính toán khác, tính<br /> toán lưới (Grid Computing) ra đời xuất phát từ<br /> nhu cầu tính toán của con người. Thực tế, càng<br /> ngày càng có nhiều bài toán lớn và phức tạp<br /> hơn được đặt ra và do đó các tổ chức cũng cần<br /> phải có những năng lực tính toán mạnh mẽ hơn.<br /> Có thể giải quyết vấn đề này bằng hai cách:<br /> Thứ nhất: Đầu tư thêm trang thiết bị, cơ sở hạ<br /> tầng tính toán (mua thêm máy chủ, máy trạm,<br /> siêu máy tính, cluster...). Rõ ràng là cách làm<br /> này hết sức tốn kém.<br /> Thứ hai: Một cách thực hiện hiệu quả hơn là<br /> phân bố lại hợp lý các nguồn tài nguyên trong tổ<br /> chức hoặc thuê thêm các nguồn tài nguyên từ<br /> bên ngoài (dĩ nhiên là với chi phí rẻ hơn nhiều<br /> so với việc đầu tư cho cơ sở hạ tầng tính toán).<br /> Đây là mục tiêu chính của tính toán lưới<br /> Môi trường lưới cho phép kết hợp các hệ thống<br /> xử lý lại với nhau để giải quyết một cách hiệu<br /> quả các nhu cầu ngày càng cao của con người<br /> [6]. Đặc biệt, đây là một công nghệ có khả năng<br /> kết hợp các nguồn tài nguyên từ những tổ chức<br /> khác nhau, phân tán trên phạm vi địa lý rộng và<br /> đặc biệt là không đòi hỏi các nguồn tài nguyên<br /> phải tương đồng về cấu trúc [7].<br /> Bài toán lập lịch là một trong những vấn đề<br /> quan trọng được nghiên cứu trong các môi<br /> trường tính toán, đặc biệt là các môi trường<br /> *<br /> <br /> *<br /> <br /> Tel: 0988724824; Email:<br /> <br /> tính toán phân tán như môi trường tính toán<br /> lưới. Do đặc thù của môi trường lưới như: số<br /> lượng công việc và các nguồn tài nguyên<br /> thường rất lớn. Mặt khác các tài nguyên này<br /> còn nằm phân tán và hỗn tạp, mỗi nguồn tài<br /> nguyên có thể do một tổ chức riêng biệt quản<br /> lý, có các chính sách và chi phí hoạt động khác<br /> nhau, bên cạnh đó tải (load) và tính sẵn sàng<br /> (availability) của các hệ thống cũng rất khác<br /> nhau; do đó vấn đề lập lịch (scheduling) trong<br /> hệ thống lưới có nhiều khó khăn và thách thức<br /> hơn so với môi trường khác, hiện tại vẫn còn<br /> đòi hỏi nhiều công sức nghiên cứu [3]<br /> GIỚI THIỆU BÀI TOÁN LẬP LỊCH<br /> TRONG MÔI TRƯỜNG LƯỚI[1]<br /> Bài toán lập lịch là một trong những vấn đề<br /> quan trọng được nghiên cứu trong các môi<br /> trường tính toán, đặc biệt là các môi trường tính<br /> toán phân tán như môi trường tính toán lưới.<br /> Quá trình lập lịch là quá trình quyết định sẽ<br /> thực thi công việc tại một nguồn tài nguyên<br /> cụ thể nào và vào thời điểm nào là thích hợp<br /> nhất do đó sẽ ảnh hưởng rất lớn đến hiệu năng<br /> hoạt động của hệ thống.<br /> Có khá nhiều vấn đề được đặt ra và cần giải<br /> quyết khi nghiên cứu về quá trình lập lịch<br /> trong môi trường tính toán lưới:<br /> <br /> Mối liên hệ và tác động lẫn nhau giữa<br /> các ứng dụng trong quá trình thực thi.<br /> <br /> Những đòi hỏi, yêu cầu khác nhau<br /> của từng ứng dụng trong hệ thống.<br /> <br /> Sự không đồng nhất và biến động của<br /> các nguồn tài nguyên trong môi trường.<br /> <br /> 134<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Tăng Cẩm Nhung<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> <br /> Mô hình hoạt động và các chính sách<br /> về truy xuất, bảo mật … của hệ thống.<br /> CÁC THUẬT TOÁN ÁP DỤNG TRONG<br /> BÀI TOÁN LẬP LỊCH THEO HIỆU NĂNG<br /> CỦA HỆ THỐNG<br /> Mục đích của phương pháp này hướng đến<br /> mục đích giảm tối đa thời gian hệ thống cần<br /> thiết để hoàn tất các ứng dụng, thời gian này<br /> được gọi là makespan của hệ thống. Một số<br /> hướng tiếp cận được đề cập đến như OLB,<br /> MCT, Min-Min, Max-Min, Sufferage…<br /> OLB (Opportunistic Load Balancing)<br /> Đây là chiến lược rất đơn giản, phân phối<br /> công việc cho tài nguyên có thời điểm sẵn<br /> sàng sớm nhất mà không quan tâm đến thời<br /> gian thực thi của công việc trên tài nguyên đó.<br /> MET (Minimum Execution Time)[3]<br /> Ngược lại với OLB, phân phối công việc<br /> vào các tài nguyên có khả năng thực thi<br /> công việc nhanh nhất, không quan tâm đến<br /> thời điểm bắt đầu và kết thúc của công việc<br /> trên tài nguyên đó.<br /> Giải thuật này thường có nhược điểm là<br /> không cân bằng tải vì hầu như các công việc<br /> đều được tập trung thực thi trên các tài<br /> nguyên có năng lực cao nhất<br /> Giả sử ta có 2 tác vụ cần thực thi là T1,T2.<br /> Các tác vụ lần lượt có kích thước T1=60,<br /> T2=120 [5]. Hệ thống có 2 máy tính cụm, mỗi<br /> máy tính cụm có 2 máy tính (host), năng lực<br /> lần lượt là:<br /> Cluster 1: H1=30, H2=60<br /> Cluster 2: H3=45, H4=50<br /> Gọi Eij = Ti/Hj là thời gian thực thi của tác vụ<br /> i trên host j, ta có:<br /> E11=T1/H1=2<br /> E12=T1/H2=1<br /> (nhỏ nhất)<br /> E13=T1/H3=1.3<br /> E14=T1/H4=1.2<br /> <br /> E21=T2/H1=4<br /> E22=T2/H2=2<br /> (nhỏ nhất)<br /> E23=T2/H3=2.6<br /> E24=T2/H4=2.4<br /> <br /> Như vậy cả 2 tác vụ đều thực thi trên host H2,<br /> makespan của hệ thống = 1 + 2 = 3<br /> MCT (Minimum Completion Time) [3]<br /> Dựa trên khái niệm thời gian hoàn thành nhỏ<br /> nhất của tác vụ. Thời gian hoàn thành được<br /> tính bằng thời gian thực thi của tác vụ cộng<br /> với thời gian sẵn sàng của tài nguyên.<br /> <br /> 65(03): 134 - 138<br /> <br /> Việc dựa trên thời gian hoàn thành nhỏ nhất<br /> sẽ giúp hệ thống cân bằng tải tốt hơn.<br /> Áp dụng với các số liệu tương tự như mục<br /> 3.2, ta định nghĩa Cij = Bj + Eij với Cij là thời<br /> gian hoàn thành của tác vụ i trên host j, Bj là<br /> thời gian sớm nhất host j có thể thực thi tác<br /> vụ (thời gian sẵn sàng).<br /> C11= B1 + E11<br /> =0+2=2<br /> C12= B2 + E12<br /> =0+1=1<br /> C13= B3 + E13<br /> = 0 + 1.3 = 1.3<br /> C14 =B4 + E14<br /> = 0 + 1.2 = 1.2<br /> <br /> C21= B1 + E21<br /> = 0 + 4 =4<br /> C22= B2 + E22<br /> = 0 + 2 =2<br /> C23= B3 + E23<br /> = 0 + 2.6 = 2.6<br /> C24 = B4 + E24<br /> = 0 + 2.4 = 2.4<br /> <br /> Tác vụ T1 theo thứ tự được chọn tài nguyên<br /> trước, sẽ chọn thực thi trên host H2 (thời gian<br /> hoàn thành thấp nhất). Thời gian bắt đầu B2<br /> được cập nhật thành 1, vì chỉ sau thời điểm<br /> này H2 mới có thể thực thi các tác vụ khác.<br /> Giá trị E22 thay đổi: B2=1<br /> C22 = B2 + E22= 1 + 2 = 3 > 2.4<br /> Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì<br /> có C24 nhỏ nhất. Thời gian thực thi toàn hệ<br /> thống makespan = 2.4 vì T1, T2 chạy song<br /> song trên 2 host khác nhau.<br /> Chúng ta có thể thấy, dựa vào giá trị MCT hệ<br /> thống sẽ cân bằng hơn dựa vào giá trị MET.<br /> Giải thuật Min – Min [2]<br /> Giải thuật Min – Min sẽ tính toán thời gian<br /> hoàn thành của tất cả các tác vụ trên tất cả các<br /> tài nguyên hiện có. Tác vụ nào có giá trị MCT<br /> nhỏ nhất sẽ được phép chọn tài nguyên trước.<br /> Sau đó cập nhật thời gian sẵn sàng cho tài<br /> nguyên được chọn, tính toán lại thông số với<br /> tất cả các tác vụ chưa được điều phối. Quá<br /> trình lặp lại cho đến khi tất cả các tác vụ đều<br /> đã chọn được tài nguyên thực thi.<br /> Ta định nghĩa một số khái niệm: T là tập các<br /> tác vụ, Hj,k là máy (host) thứ k của cluster j.<br /> C(Ti,Hj,k) là thời gian hoàn thành tác vụ Ti<br /> trên host Hj,k.<br /> Gọi f là một ánh xạ từ Rn vào R, toán tử<br /> argmin được định nghĩa:<br /> <br /> f (arg min n xR f ( x))  min n xR ( f ( x))<br /> Chú thích: Giá trị C(Ti,Hj,k) là thời gian hoàn<br /> thành của tác vụ Ti trên host Hj,k. Lúc này<br /> <br /> 135<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Tăng Cẩm Nhung<br /> <br /> nếu argminj,<br /> 1<br /> i<br /> <br /> k<br /> <br /> 1<br /> i<br /> <br /> phần( c , h<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> (C(Ti,Hj,k))gồm 2 thành<br /> )<br /> <br /> thì<br /> <br /> giá<br /> <br /> trị<br /> <br /> C (Ti , H c1 , h1 ) là nhỏ nhất . Host hi1<br /> i<br /> i<br /> trên cluster ci1 là host có khả năng hoàn tất<br /> tác vụ Ti sớm nhất.<br /> Giải thuật Min-Min:<br /> while(T≠  )<br /> foreach ( Ti  T )<br /> ( ci1 , hi1  arg min j ,k (C (Ti , H j ,k )) )<br /> endfor<br /> s= arg min i (C (Ti , H 1 1 ))<br /> ci , hi<br /> <br /> Ts  H<br /> <br /> c1s , h1s<br /> <br /> T=T-{T}<br /> endwhile<br /> Áp dụng với các số liệu mục 2<br /> C11= B1 + E11<br /> =0+2=2<br /> C12= B2 + E12<br /> = 0 + 1 = 1 (min)<br /> C13= B3 + E13<br /> = 0 + 1.3 = 1.3<br /> C14 =B4 + E14<br /> = 0 + 1.2 = 1.2<br /> <br /> C21= B1 + E21<br /> = 0 + 4 =4<br /> C22= B2 + E22<br /> = 0 + 2 =2 (min)<br /> C23= B3 + E23<br /> = 0 + 2.6 = 2.6<br /> C24 = B4 + E24<br /> = 0 + 2.4 = 2.4<br /> <br /> Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2<br /> MCT(T1) nhỏ hơn, do đó tác vụ T1 được chọn<br /> host H1 để thực thi trước.<br /> Giá trị E22 thay đổi: B2=1, C22 = B2 + E22= 1 +<br /> 2 = 3 > 2.4<br /> Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì<br /> có C24 nhỏ nhất. Thời gian thực thi toàn hệ<br /> thống makespan = 2.4 vì T 1, T 2 chạy song<br /> song trên 2 host khác nhau.<br /> Giải thuật Max-Min [2]<br /> Tương tự như giải thuật Min-Min, tuy nhiên<br /> giải thuật Max-Min cho phép các tác vụ có<br /> MCT lớn hơn được ưu tiên chọn host để thực<br /> thi trước. Giải thuật này được đánh giá tốt và<br /> cân bằng hơn Min-Min vì trong khi các tác vụ<br /> dài hơn được ưu tiên chọn thiết bị tốt để thực<br /> thi trước, các tác vụ ngắn có thể luân phiên<br /> thực thi ở các thiết bị có năng lực yếu hơn.<br /> Các tác vụ dài không phải mất thời tác vụ<br /> ngắn hơn như ở giải thuật Min-Min.<br /> <br /> 65(03): 134 - 138<br /> <br /> Toán tử argmax được định nghĩa tương<br /> toán tử argmin<br /> <br /> tự<br /> <br /> f (arg max n xR f ( x))  max n xR ( f ( x))<br /> <br /> Giải thuật Max-Min:<br /> while(T≠  )<br /> foreach( Ti  T )<br /> ( ci1 , hi1  arg min j ,k (C (Ti , H j ,k )) )<br /> endfor<br /> s= arg max i (C (Ti , H 1 1 ))<br /> ci , hi<br /> <br /> Ts  H<br /> <br /> c1s , h1s<br /> <br /> T=T-{T}<br /> endwhile<br /> Áp dụng với các số liệu như mục 2<br /> C11= B1 + E11<br /> =0+2=2<br /> C12= B2 + E12<br /> = 0 + 1 = 1 (min)<br /> C13= B3 + E13<br /> = 0 + 1.3 = 1.3<br /> C14 =B4 + E14<br /> = 0 + 1.2 = 1.2<br /> <br /> C21= B1 + E21<br /> = 0 + 4 =4<br /> C22= B2 + E22<br /> = 0 + 2 =2 (min)<br /> C23= B3 + E23<br /> = 0 + 2.6 = 2.6<br /> C24 = B4 + E24<br /> = 0 + 2.4 = 2.4<br /> <br /> Giá trị MCT(T1)= C12 =1,MCT(T2)=C22=2<br /> Lúc này tác vụ T2 có MCT lớn hơn nên được<br /> phép chọn host thực thi trước. T2 sẽ thực thi<br /> trên host H2.<br /> Giá trị B2 = 2,<br /> C12 = B2 + E12 = 2 + 1 =3 > 1.2<br /> Như vậy, sau đó tác vụ T1 sẽ thực thi trên host<br /> H4 vì lúc này C14 =1.2 là nhỏ nhất<br /> Thời gian hoàn thành của hệ thống makespan<br /> = 2 vì T1, T2 chạy song song (nhỏ hơn với giải<br /> thuật Min-Min)<br /> Giải thuật Sufferage<br /> Suferage lấy ý tưởng từ giải thuật Min-Min và<br /> Max-Min đã đề ra trước đó[1].<br /> Giải thuật Sufferage tính toán giá trị MCT<br /> thấp thứ nhất và thấp thứ hai đối với từng tác<br /> vụ trong hệ thống. Giá trị này được gọi là độ<br /> “thiệt hại” (suffering) của một tác vụ khi nó<br /> không được thực thi trên tài nguyên tốt nhất.<br /> Tác vụ có độ thiệt hại lớn nhất sẽ được ưu<br /> tiên chọn tài nguyên để thực thi trước.<br /> Giải thuật Suferage<br /> while(T≠  )<br /> foreach ( Ti  T )<br /> ( ci , hi )  arg min j ,k (C (Ti , H j ,k ))<br /> 1<br /> <br /> 1<br /> <br /> 136<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Tăng Cẩm Nhung<br /> <br /> (ci2 , hi2 )  arg min<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> (C (Ti , H j , k )) su<br /> j  c1i , k  hi1<br /> <br /> fi= C (Ti , H 2 2 )  C (Ti , H 1 1 ))<br /> ci , hi<br /> ci , hi<br /> endfor<br /> S= arg max i ( sufi )<br /> <br /> Ts  H<br /> <br /> c1s , h1s<br /> <br /> T=T-{T}<br /> endwhile<br /> Giải thuật này đặc biệt hiệu quả nếu tính đến<br /> vấn đề vận chuyển dữ liệu đến nơi thực thi<br /> Giải thuật này đặc biệt hiệu quả nếu tính đến<br /> vấn đề vận chuyển dữ liệu nơi thực thi tác vụ.<br /> Nếu một tài nguyên đã có sẵn dữ liệu của một<br /> tác vụ, tác vụ nếu thực thi trên tài nguyên này<br /> sẽ tiết kiệm được thời gian rất nhiều so với<br /> khi thực thi trên một tài nguyên khác. Tác vụ<br /> trong trường hợp này sẽ có giá trị Sufferage<br /> cao nên được<br /> Áp dụng với các số liệu như mục 2<br /> Giá trị Suff (T1)= C14 – C12 = 0.2<br /> Giá trị Suff (T2)= C24 – C22 = 0.4<br /> Vì suff (T2) cao hơn nên tác vụ T2 được phép<br /> chọn host H2 để thực thi trước.<br /> Giá trị B2 = 2<br /> C12 = B2 + E12 = 2 + 1 = 3 > 1.2<br /> Như vậy, sau đó tác vụ T1 sẽ thực thi trên<br /> host H4 vì lúc này C14 = 1.2 là nhỏ nhất<br /> Thời gian hoàn thành của hệ thống makespan<br /> = 2 vì T1, T2 chạy song song.<br /> C11= B1 + E11<br /> =0+2=2<br /> C12= B2 + E12<br /> = 0 + 1 = 1 (min)<br /> C13= B3 + E13<br /> = 0 + 1.3 = 1.3<br /> C14 =B4 + E14<br /> = 0 + 1.2 = 1.2<br /> <br /> C21= B1 + E21<br /> = 0 + 4 =4<br /> C22= B2 + E22<br /> = 0 + 2 =2 (min)<br /> C23= B3 + E23<br /> = 0 + 2.6 = 2.6<br /> C24 = B4 + E24<br /> = 0 + 2.4 = 2.4<br /> <br /> Ví dụ ở trên khá đơn giản, chỉ có chiều dài<br /> tác vụ ảnh hưởng đến thời gian thực thi của<br /> tác vụ nên trường hợp Sufferage khá giống<br /> Max – Min.<br /> Giải thuật XSufferage<br /> Do nhóm nghiên cứu Casanova đề ra, phát<br /> triển từ thuật toán Sufferage[1].<br /> <br /> 65(03): 134 - 138<br /> <br /> Các máy tính trong một Máy tính cụm thường<br /> có năng lực như nhau, do đó giá trị sufferage<br /> thường dần về 0. Điều này khiến một tác vụ<br /> Ti, khi rất cần chạy trên máy tính cụm j (ví dụ<br /> dữ liệu input của Ti đã nằm sẵn trên máy tính<br /> cụm j), nhưng trong trường hợp máy tính cụm<br /> này lại có 2 máy năng lực tương đương nhau<br /> khiến Suff(Ti) ≈ 0 nên Ti sẽ không có cơ hội<br /> chạy trên máy tính cụm j. Cải tiến ở đây là<br /> khái niệm Suf sẽ được tính ở mức cluster,<br /> không phải ở mức host.<br /> Giải thuật<br /> while(T≠  )<br /> foreach ( Ti  T )<br /> foreach clusterj<br /> hi,j=  arg min k (C (Ti , H j ,k ))<br /> endforeach<br /> <br /> c1i  arg min j (C (Ti , H j , hi , j ))<br /> <br /> ci2  arg min<br /> <br /> (C (Ti , H j , hi, j<br /> j  c1i<br /> <br /> ))<br /> <br /> sufi= C (Ti , H 2 2 )  C (Ti , H 1 1 ))<br /> ci , hi<br /> ci , hi<br /> endforeach<br /> s= arg max i ( sufi )<br /> <br /> Ts  H<br /> <br /> c1s , h 1<br /> s,cs<br /> <br /> T=T-{T}<br /> Endwhile<br /> KẾT LUẬN<br /> Bài báo đã nêu ra cái nhìn tổng quan nhất về<br /> vấn đề lập lịch trong môi trường lưới, và các<br /> thuật toán cụ thể được áp dụng cho lưới và<br /> các đặc điểm của giải thuật trên đó là:<br />  Phải duyệt tất cả các máy trong mọi máy<br /> tính cụm có thể dẫn đến độ phức tạp rất lớn.<br />  Ứng dụng rất lớn gồm nhiều tác vụ chạy<br /> song song, các tác vụ đóng vai trò như nhau.<br />  Một tác vụ có thể chạy trên host bất kỳ,<br /> không có sự ràng buộc về địa điểm thực thi.<br /> Từ cơ sở lý thuyết của các thuật toán đó đã<br /> được áp dụng vào hệ thống lưới gồm có hai<br /> máy tính cụm để chứng minh về tính hiệu quả<br /> của từng thuật toán đã được nêu ra.<br /> <br /> 137<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Tăng Cẩm Nhung<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> TÀI LIỆU THAM KHẢO<br /> [1] Fangpeng Dong and Selim G. Akl, January<br /> 2006,<br /> Scheduling<br /> Algorithms<br /> for<br /> Grid<br /> Computing:State of the Art and Open Problems,<br /> Technical Report No. 2006-504,<br /> [3] Kousalya.K and Balasubramanie.P, April<br /> 2008, An Enhanced Ant Algorithm for Grid<br /> Scheduling Problem, IJCSNS International<br /> Journal of Computer Science and Network<br /> Security, VOL.8 No.4,<br /> [4] Saurabh Kumar Garg , Rajkumar Buyya and<br /> H. J. Siegel, 2009, Scheduling Parallel<br /> Applications on Utility Grids:Time and Cost<br /> Trade-off Management, Proc. 32nd Australasian<br /> <br /> 65(03): 134 - 138<br /> <br /> Computer Science Conference (ACSC 2009),<br /> Wellington, New Zealand<br /> [5] Graham Ritchie and John Levine, A fast,<br /> effective local search for scheduling independent<br /> jobs in heterogeneous computing environments.<br /> [6] Ian Foster, C. Kesselman ,Computational<br /> Grids, Chapter 2 Of "The Grid:Blueprint For A<br /> New Computing Infrastructure", MorganKaufman, 1999.<br /> <br /> RESEARCH AND APPLY SCHEDULE ALGORITHMS TO GRID COMPUTING<br /> ENVIRONMENTS<br /> Tang Cam Nhung2<br /> Thai Nguyen University of Tecnology<br /> Thanks to advances in wide-area network technologies and the low cost of computing resources, Grid<br /> computing came into being and is currently an active research area. One motivation of Grid computing<br /> is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To<br /> achieve this goal, an efficient Grid scheduling system is an essential part of the Grid. This paper refers<br /> to the scheduling problem of grid system and some of scheduling algorithms applied to grid computing<br /> model so may reduce the maximum system time needed to complete the application. The algorithms<br /> are: OLB, MCT, Min-Min, Max-Min, Sufferage and in this paper is to compare the results of efficiency<br /> between algorithms when the applied to specific models.<br /> Keywords: grid computing, schedule, Opportunistic Load Balancing, Minimum Execution Time, Minimum<br /> Completion Time, Max-Min, Min – Min, Sufferage, xSufferage<br /> <br /> 2<br /> <br /> Tel: 0988724824; Email:<br /> <br /> 138<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br />