Helpex - Trao đổi & giúp đỡ Đăng nhập

Hiệu suất của hàng đợi phản hồi đa cấp

Trong blog này, tôi sẽ thảo luận về các đặc điểm hiệu suất của hàng đợi Phản hồi Đa cấp, là một chính sách lập lịch trình ưu đãi cho các công việc ngắn hạn. Chính sách này còn được gọi là chính sách chia sẻ thời gian đa cấp (MLTP). Một số bộ lập lịch hệ điều hành sử dụng hàng đợi phản hồi đa cấp để lập lịch công việc và nó cho phép một quá trình di chuyển giữa các hàng đợi. Một trong những ưu điểm chính của việc sử dụng chính sách này là nó có thể tăng tốc luồng các tác vụ nhỏ. Điều này có thể dẫn đến cải thiện hiệu suất tổng thể khi phân phối thời gian phục vụ của các tác vụ tuân theo phân phối đuôi dài (lưu ý: phân phối đuôi dài được giải thích chi tiết ở phần sau của bài viết này).

Hình sau minh họa mô hình:

Hiệu suất của hàng đợi phản hồi đa cấp

Mô hình

Chức năng cơ bản của chính sách lập lịch chia sẻ thời gian đa cấp được xem xét trong bài viết này như sau.

Mỗi tác vụ mới đến hệ thống được đặt trong hàng đợi thấp nhất, nơi tác vụ được phân phối theo cách Người đến trước được phục vụ trước (FCFS) cho đến khi nó nhận được lượng dịch vụ tối đa là q1 (lưu ý: q1 đại diện cho một thời gian thời hạn).

Nếu thời gian phục vụ của tác vụ nhỏ hơn hoặc bằng q1, tác vụ sẽ khởi hành hệ thống (sau khi nhận được tối đa q1 lượng dịch vụ). Nếu không, tác vụ được đặt trong Hàng đợi 2, nơi tác vụ được xử lý theo cách FCFS cho đến khi nó nhận được tối đa q2 lượng dịch vụ, v.v.

Tác vụ được truyền thông qua hệ thống các hàng đợi cho đến khi tổng thời gian xử lý mà tác vụ đã nhận được cho đến nay bằng với thời gian phục vụ của nó, lúc này nó sẽ rời khỏi hệ thống.

Một nhiệm vụ đang chờ được phân phối trong Hàng đợi 1 có mức độ ưu tiên của dịch vụ hơn các tác vụ đang chờ được phân phối trong Hàng đợi 1 + 1, 1 + 2,…, N, trong đó N biểu thị số cấp. Tuy nhiên, một tác vụ hiện đang được xử lý không được ưu tiên khi có một tác vụ mới vào hệ thống.

Hai biến thể

Trong bài viết này, tôi sẽ xem xét hai mô hình sau:

Chính sách chia sẻ thời gian lượng tử tối ưu đa cấp với N mức (N-MLTP-O): Lượng tử (q1, q2,…, qn) cho N-MLTP-O được tính toán để tối ưu hóa thời gian chờ dự kiến ​​tổng thể.

Chính sách chia sẻ thời gian lượng tử bằng nhau đa cấp với N mức (N-MLTP-E): Lượng tử cho N-MLTP-E bằng nhau trên mỗi mức , tức là, q1 = q2 = q3 =… = qn.

Phân phối dài hạn

Trong bài báo của mình , LE Schrage đã đưa ra thời gian chờ dự kiến ​​cho chính sách chia sẻ thời gian đa cấp theo phân phối thời gian dịch vụ chung khi nhiệm vụ đến thực hiện theo  quy trình Poisson . Chúng tôi đã sử dụng kết quả này trong công việc trước đây của mình để nghiên cứu hiệu suất của chính sách chia sẻ thời gian đa cấp trong phân phối thời gian dịch vụ dài hạn . Chúng tôi đã đặc biệt xem xét các phân phối thời gian dịch vụ dài hạn vì có bằng chứng cho thấy thời gian phục vụ của các tải công việc tính toán nhất định theo sát các phân phối đó . Trong các bản phân phối như vậy:

  1. Có một xác suất rất cao là kích thước của một nhiệm vụ là rất nhỏ (ngắn) và xác suất để kích thước của một nhiệm vụ rất lớn (dài) là rất nhỏ. Điều này dẫn đến phân phối thời gian phục vụ có phương sai rất cao.
  2. Mặc dù xác suất xuất hiện của một nhiệm vụ rất lớn là rất nhỏ, nhưng tải áp đặt lên hệ thống bởi (số lượng rất nhỏ) các nhiệm vụ lớn này có thể cao tới 50% tải của hệ thống.
  3. Khi phân phối thời gian phục vụ thể hiện phương sai rất cao, một số nhiệm vụ nhỏ có thể xếp sau một nhiệm vụ rất lớn. Điều này dẫn đến sự suy giảm hiệu suất đáng kể, đặc biệt nếu các nhiệm vụ được xử lý theo cách thức FCFS cho đến khi hoàn thành

Đặc biệt, chúng tôi đã xem xét hiệu suất của chính sách chia sẻ thời gian đa cấp trong Phân phối Pareto (một trong những phân phối đuôi dài thường xuất hiện) và điều tra xem sự thay đổi của thời gian phục vụ ảnh hưởng như thế nào đến hiệu suất của chính sách chia sẻ thời gian đa cấp dưới các tải hệ thống khác nhau. Hàm mật độ xác suất của Phân phối Pareto được cho bởi

Hiệu suất của hàng đợi phản hồi đa cấp

trong đó 2> α> 0. α đại diện cho sự thay đổi của thời gian phục vụ tác vụ. Giá trị của α phụ thuộc vào loại nguyên công. Ví dụ, yêu cầu CPU xử lý Unix có giá trị α là 1,0. Giá trị của alpha càng thấp thì thời gian phục vụ càng có nhiều biến động.

Hành vi của Thời gian chờ Dự kiến ​​Tổng thể (hoặc Thời gian Chờ Trung bình Tổng thể)

Các số liệu sau đây cho thấy thời gian chờ dự kiến ​​tổng thể và yếu tố cải thiện thời gian chờ dự kiến ​​trong MLTP so với FCFS.

Trong hình 1:

Trục Y: E [W] - Thời gian chờ dự kiến ​​tổng thể (hoặc thời gian chờ trung bình tổng thể) của một nhiệm vụ được đưa vào hệ thống (đơn vị: đơn vị thời gian).

Trục X: α : Đại diện cho sự thay đổi của thời gian phục vụ tác vụ (tham khảo phần trước). Giá trị alpha càng thấp thì thời gian phục vụ càng thay đổi.

Trong hình 2:

Trục Y: Yếu tố cải thiện MLTP so với FCFS.

Trục X: α : Đại diện cho sự thay đổi của thời gian phục vụ tác vụ (tham khảo phần trước). Giá trị alpha càng thấp thì thời gian phục vụ càng thay đổi.

Hiệu suất của hàng đợi phản hồi đa cấp

Hiệu suất của hàng đợi phản hồi đa cấp

Đầu tiên, chúng ta hãy xem xét hiệu suất của 2-MLTP-O, 2-MLTP-E và FCFS.

Chúng tôi lưu ý từ Hình 1, 2-MLTP-O hoạt động tốt hơn cả 2-MLTP-E và FCFS trong tất cả các tình huống được xem xét. Ví dụ: dưới tải hệ thống là 0,7, khi α = 0,4 , 2-MLTP-O hoạt động tốt hơn FCFS và 2-MLTP-E theo hệ số 3 và 2 tương ứng .

Trong cùng một tải hệ thống, khi α bằng 1,1 , 2-MLTP-O hoạt động tốt hơn FCFS và 2-MLTP-E theo hệ số tương ứng là 2 và 1,5 . Chúng tôi lưu ý rằng yếu tố cải thiện rất có ý nghĩa khi cả tải hệ thống và sự thay đổi kích thước nhiệm vụ đều cao (nghĩa là α thấp).

Mặt khác, nếu cả tải hệ thống và sự thay đổi kích thước nhiệm vụ đều thấp (nghĩa là α cao), thì yếu tố cải thiện không có ý nghĩa cao.

Ngoài ra, hãy lưu ý rằng khi bạn tăng số lượng cấp độ, chúng tôi sẽ cải thiện hiệu suất. Ví dụ: dưới tải hệ thống là 0,7, khi α bằng 0,4, 3-MLTP-O hoạt động tốt hơn 1,6 lần so với 2-MLTP-O.

Số lượng tác động của các cấp độ

Hình sau vẽ biểu đồ thời gian chờ dự kiến ​​so với số mức ( N ) cho một số giá trị α đã chọn và tải hệ thống. Lưu ý rằng trong các biểu đồ này, các trục x và y ở trong thang log (cơ số 10).

Trong hình bên dưới:

E [W] : Thời gian chờ dự kiến ​​tổng thể (hoặc thời gian chờ trung bình tổng thể) của một tác vụ được đưa vào hệ thống (đơn vị: đơn vị thời gian).

N : Số lượng hàng đợi / cấp độ

α : Đại diện cho sự thay đổi của thời gian phục vụ tác vụ (tham khảo phần trước). Giá trị của alpha càng thấp thì thời gian phục vụ càng có nhiều biến động.

Hiệu suất của hàng đợi phản hồi đa cấp

Một trong những nhận xét chính là khi sự thay đổi của thời gian phục vụ rất cao, thì chúng ta có thể nhận được sự cải thiện đáng kể trong thời gian chờ trung bình bằng cách tăng số lượng cấp độ.

Phần kết luận

Trong blog này, chúng tôi đã xem xét hiệu suất của chính sách lập lịch hàng đợi phản hồi đa cấp (còn gọi là chính sách chia sẻ thời gian đa cấp) với số lượng hàng đợi hữu hạn. Chúng tôi đã so sánh hiệu suất của chính sách chia sẻ thời gian đa cấp với FCFS theo hai tình huống: (1) lượng tử của chính sách chia sẻ thời gian đa cấp được tính toán để tối ưu hóa thời gian chờ dự kiến ​​(MLTP-O) và (2) lượng tử bằng nhau trên mỗi cấp ( MLTP-E). Chúng tôi nhận thấy rằng nếu sự thay đổi của thời gian dịch vụ cao, chúng tôi có thể nhận được những cải tiến đáng kể bằng cách sử dụng MLTP-O. Chúng tôi nhận thấy rằng cả MLTP-O và MLTP-E đều hoạt động tốt hơn đáng kể so với FCFS, đặc biệt là khi sự thay đổi của thời gian phục vụ cao. Nếu sự thay đổi của thời gian phục vụ thấp, thì không có sự khác biệt đáng kể nào về hiệu suất. 

12 hữu ích 0 bình luận 4.5k xem chia sẻ

Có thể bạn quan tâm

loading