Chia sẻ và cân bằng động

Hai ví dụ về lập lịch của phần trên đây chính là cách thức lập lịch tĩnh. Khi một QT được đưa tới một nút, QT này được lưu lại đó cho đến khi nó được hoàn thiện. Cả 2 ví dụ trên đều đòi hỏi biết trước về thời gian chạy và cách thức truyền thông của quá trình. Với mô hình QT đi trước, mục tiêu đầu tiên là tối thiểu hoá thời gian hoàn thiện toàn bộ, trong khi mô hình QT TT cố gắng tối thiểu hoá tổng chi phí TT, đồng thời tìm cách thoả mãn những ràng buộc về tính toán. Một mô hình toán học và một thuật toán tốt là yếu tố cần thiết cho lập lịch. Tuy nhiên, việc tính toán lại tập trung và chỉ xảy ra tại một thời điểm định trước.

Biết trước thông tin về các QT là không thực tế trong hầu hết các ứng dụng phân tán. Với đòi hỏi kết nối và tính toán không cần thông tin trước, ta phải dựa trên một chiến lược lập lịch linh hoạt, cho phép những quyết định được thực hiện tại địa phương. Trong phần này, chúng ta sẽ sử dụng mô hình QT không liên kết để thể hiện một số chiến lược lập lịch động. Việc sử dụng mô hình không liên kết không có nghĩa là mọi QT không có liên hệ với nhau, mà được hiểu theo nghĩa: chúng ta không biết một QT này tương tác với các QT khác như thế nào. Vì vậy, ta có thể lập lịch với giả sử rằng chúng không kết nối. Điều này tương đương với việc bỏ qua sự phụ thuộc giữa các QT. Với mô hình này, mục tiêu của việc lập lịch khác so với mục tiêu của mô hình ưu tiên và mô hình liên hệ. Mục tiêu lớn nhất có thể thấy được trong lập lịch là hướng tới tính hiệu dụng (utilzation) của hệ thống và tính công bằng (fairness) cho các QT xử lý của người dùng. Tính hiệu dụng của các bộ xử lý có liên quan trực tiếp đến các thước đo tốc độ như khối lượng xử lý và thời gian hoàn thành. Sự công bằng rất khó để định nghĩa cũng như ảnh hưởng của nó đến hoạt động là không rõ ràng. Có thể nói hiệu dụng và công bằng là yêu cầu trong lập lịch cho mô hình không liên kết của một hệ thống phân tán.

Một chiến lược đơn giản để nâng cao hiệu quả sử dụng của một hệ thống là tránh được nhiều nhất tình trạng bộ xử lý rỗi. Giả sử rằng ta có thể chỉ định một QT điều khiển chứa đựng thông tin về kích thước hàng đợi của mỗi bộ xử lý. Các QT đến và ra khỏi hệ thống theo phương thức dị bộ. Một QT đến sẽ đưa ra yêu cầu đòi hỏi bộ điều khiển cung cấp một bộ xử lý. Bộ điều khiển sẽ lập lịch điều phối đưa QT đó đến một bộ xử lý có hàng đợi ngắn nhất. Để cập nhập thông tin về kích thước hàng đợi, mỗi bộ xử lý cần cung cấp thông tin cho bộ điều khiển ngay khi một QT được hoàn tất và ra khỏi khu xử lý. Việc kết nối với hàng đợi ngắn nhất chính là chiến lược điều phối tĩnh cho chia xẻ nhiệm vụ (static load sharing) nhằm mục đích giảm bớt thời gian rỗi của các bộ xử lý và giảm sự chênh lệch về hàng đợi (cân đối nhiệm vụ) giữa các bộ xử lý. Việc cân đối tải là đòi hỏi cao hơn so với chia xẻ tải, bởi vì chúng nâng cao hiệu quả sử dụng và đưa tới một cách cân đối đúng theo nghĩa bằng nhau về nhiệm vụ phải thực hiện của mỗi bộ xử lý. Cân bằng nhiệm vụ có tác dụng làm giảm thời gian phí tổn trung bình của các QT. Chiến lược này có thể được sửa đổi bằng cách cho phép di chuyển linh động một QT từ hàng đợi dài đến các hàng đợi ngắn hơn. Mô hình hàng đợi trên đã được đề cập đến trong hình 5.3 c, mô hình trạm làm việc. Tính hiệu quả và cân bằng càng được nâng cao bởi phương thức phân phối linh động lại các công việc hay còn gọi di trú QT.

Tuy nhiên, sự cân bằng đề cập ở trên vẫn chưa mang thật đầy đủ ý nghĩa bởi nó dựa trên quan điểm của hệ thống hơn là của người dùng. Trong các QT được phát sinh bởi người dùng tại các trạm địa phương. Vì vậy, một hệ thống cân bằng theo quan điểm người sử dụng phải là một hệ thống ưu tiên cho chương trình của người dùng nếu chương trình đó đòi hỏi chia xẻ các tài nguyên tính toán ít hơn các chương trình khác. Trên nguyên tắc này, bộ điều khiển phải kiểm soát được bộ xử lý hiện đang cấp phát cho một QT của người sử dụng. Ngay khi một bộ xử lý rỗi, bộ điều khiển sẽ cấp phát bộ xử lý đó cho một QT đang chờ đợi tại phía có số lần được cấp phát CPU ít nhất. Tính hiệu dụng được thể hiện bằng cách cố gắng định vị tối đa các bộ xử lý có thể được. Tiêu chuẩn này có thể được điều chỉnh bằng việc tính toán độ dài hàng đợi, thông số phản ánh nhiệm vụ tại mỗi vùng và cũng vì thế thực hiện được sự cân bằng các QT được nạp. So sánh với phương pháp điều phối “hàng đợi kết nối với QT ngắn nhất” (join-to-the-shortest queue), ta có thể thấy phương pháp này cho một định nghĩa tốt hơn về sự công bằng, việc điều phối được khởi tạo bởi một QT tại điểm xuất phát thay vì tại điểm đích, và vì thế nó phù hợp hơn cho mô hình xâu-bộ xử lý.

Cuộc tranh luận quanh bất kỳ vấn đề nào về hệ phân tán sẽ không bao giờ kết thúc trừ phi ta chứng minh được tác dụng của sự điều khiển tập trung (hoặc chứng minh loại bỏ nó). Nếu chúng ta huỷ bỏ sự điều khiển tập trung trong việc chuyển giao một QT từ 1 vùng này (nơi gửi) đến 1 vùng khác (nơi nhận), công việc chuyển giao QT phải được tạo lập bởi nơi gửi, nơi nhận, hoặc cả hai. Trong 2 phần tiếp, chúng ta sẽ thảo luận Thuật toán tạo lập trạm gửi và thuật toán tạo lập từ trạm nhận cho công việc chuyển giao QT.

Như đã thấy ở trên, thuật toán phân chia nhiệm vụ tạo lập từ trạm gửi giống như một mô hình “đẩy”, trong đó 1 QT được đẩy từ một bộ xử lý này tới bộ xử lý khác. Tương ứng với nó, một đỉnh nhận có thể kéo một QT từ một bộ xử lý khác về để xử lý: thuật toán lập tạo từ trạm nhận. Sử dụng chính sách chuyển nhượng tương tự như trên, thuật toán này sẽ tạo lập thao tác “kéo” khi độ dài hàng đợi tụt xuống dưới một ngưỡng RT (đã được định trước) vào thời điểm bắt đầu một QT. Một chiến lược thăm dò tương tự cũng được sử dụng trong chính sách định vị để tìm kiếm một đỉnh gửi đã quá tải. Tuy nhiên, chính sách lựa chọn lại đỏi hỏi một thứ tự ưu tiên khi các QT tại trạm gửi đã bắt đầu chạy. Việc quyết định QT nào chuyển đi sẽ không rõ ràng như trong thuật toán tạo lập từ trạm gửi. Ta phải tính sao cho lợi ích thu được từ việc chia xẻ nhiệm vụ phải lớn hơn phí tổn tính độ ưu tiên và phí tổn cho liên lạc.

Thuật toán tạo lập từ trạm nhận có tính ổn định hơn thuật toán tạo lập từ trạm gửi. Trong một hệ thống có mức tải lớn, việc di chuyển các QT xẩy ra ít, các trạm gửi được tìm thấy dễ dàng, lượng công việc được chia xẻ hiệu quả, phí tổn ít. Khi mức tải của hệ thống ở mức thấp, việc tạo lập các di chuyển xảy ra nhiều nhưng vẫn không làm giảm hoạt động của thuật toán. Tính trung bình, thuật toán tạo lập từ trạm nhận hoạt động tốt hơn thuật toán tạo lập từ trạm gửi.

Điều tất yếu là tìm cách kết hợp hai thuật toán. Ví dụ, một trạm xử lý có thể sử dụng thuật toán tạo lập từ trạm gửi khi hàng đợi qua ngưỡng giới hạn ST cũng như có thể kích hoạt thuật toán tạo lập từ trạm nhận khi kích cỡ hàng đợi giảm thiểu xuống dưới ngưỡng RT. Việc lựa chọn giữa 2 thuật toán dựa trên thông tin đánh giá về mức tải của hệ thống. Nếu 2 thuật toán trên là đối xứng và không linh hoạt thì việc kết hợp nói trên chính là một thuật toán thích ứng. Trong cả hai trường hợp (tải nặng hoặc nhẹ), mỗi trạm có thể linh hoạt đóng vai trò của trạm nhận hoặc trạm gửi. Các trạm gửi sẽ gặp trạm nhận tại các điểm hẹn.

Để tạo lập trên thực tế các điểm hẹn này, một dịch vụ đăng ký (registration service) được dùng đểkết hợp 1 trạm gửivới một tạm nhận. Việc thăm dò vì thế mà trở thành không cần thiết. Trạm phục vụ đăng ký( regisration phục vụ) hoạt động như một “ thương nhân” trao đổi giữa người trả giá cao nhất (sender) với người cung cấp rẻ nhất (receiver) mà giá cả hàng hoá thời gian thực hiện các QT. Một trạm “ tốt” phải biềt dùng thuật toán tạo lập từ trạm gửi, kích hoạt thuật toán tạo lập từ trạm nhận khi trạm cảm thấy hệ thống tải ở mức cao, và hoạt động ngượclại khi mức tải là thấp.Thuật toán vì thế sẽ tương thích với sợ thay đổi của hệ thống.

Hình 5. 10 so sánh hoạt động của thuật toán linh hoạt chia sẻ công việc. Thời gian lãng phí của hệ thống M/M/1 không chia xẻ tải là đường cơ sở cho việc so sánh.