Thuật toán lập kế hoạch Round Robin với ví dụ

⚡ Tóm tắt thông minh

Lập lịch Round-Robin là thuật toán CPU ưu tiên lâu đời nhất và đơn giản nhất, trong đó mỗi tiến trình sẵn sàng sẽ chạy trong một khoảng thời gian cố định trong hàng đợi tuần hoàn, đảm bảo thực thi công bằng và không bị tắc nghẽn cho đa nhiệm.

🔄 Định nghĩa: Mỗi tác vụ sẵn sàng sẽ lần lượt chạy trong một khoảng thời gian cố định.
🇧🇷 Lượng tử thời gian: CPU chuyển đổi giữa các tiến trình sau một khoảng thời gian cố định, được gọi là lượng tử thời gian.
⚖️ Công bằng: Mỗi tiến trình đều được cấp thời gian xử lý CPU như nhau, tránh tình trạng thiếu tài nguyên.
🧮 Mang tính phòng ngừa: Tiến trình bị gián đoạn sẽ chuyển xuống cuối hàng đợi.
✅ Ưu điểm: Phân bổ công bằng, không có hiệu ứng đoàn xe, thời gian phản hồi có thể dự đoán được.
⚠️ Nhược điểm: Hiệu năng phụ thuộc vào lượng thời gian và làm tăng thêm chi phí chuyển đổi ngữ cảnh.

Đọc thêm

Lập kế hoạch Round-Robin là gì?

Tên của thuật toán này xuất phát từ nguyên tắc quay vòng, trong đó mỗi người lần lượt nhận được phần bằng nhau của một thứ gì đó. Đây là thuật toán lập lịch đơn giản nhất, lâu đời nhất, chủ yếu được sử dụng cho đa nhiệm.

Trong thuật toán lập lịch Round-robin, mỗi tác vụ sẵn sàng sẽ chạy lần lượt trong một hàng đợi tuần hoàn trong một khoảng thời gian giới hạn. Thuật toán này cũng cho phép thực thi các tiến trình mà không bị "đói" tài nguyên.

Đặc điểm của lập kế hoạch Round-Robin

Dưới đây là các đặc điểm quan trọng của Lập kế hoạch vòng tròn:

Thuật toán luân phiên (round robin) là một thuật toán ưu tiên loại trừ.
CPU sẽ chuyển sang tiến trình tiếp theo sau một khoảng thời gian cố định, được gọi là lượng thời gian/lát thời gian.
Quá trình được ưu tiên sẽ được thêm vào cuối hàng đợi.
Round robin là một mô hình lai hoạt động dựa trên xung nhịp.
Thời gian phân bổ tối thiểu cho mỗi tác vụ cụ thể cần được xử lý nên được giữ ở mức thấp nhất. Tuy nhiên, thời gian này có thể khác nhau tùy thuộc vào hệ điều hành.
Đây là một thuật toán thời gian thực, phản hồi sự kiện trong một khoảng thời gian xác định.
Thuật toán vòng tròn (Round robin) là một trong những thuật toán lâu đời nhất, công bằng nhất và dễ sử dụng nhất.
Đây là một phương pháp lập lịch được sử dụng rộng rãi trong các hệ điều hành truyền thống.

Ví dụ về lập kế hoạch luân phiên

Hãy xem xét ba quy trình sau:

Hàng đợi xử lý	Thời gian bùng nổ
P1	4
P2	3
P3	5

Bước 1) Quá trình thực thi bắt đầu với quy trình P1, có thời gian bùng nổ là 4. Ở đây, mọi quy trình thực thi trong 2 giây. P2 và P3 vẫn đang trong hàng đợi.

Bước 2) Tại thời điểm t = 2, P1 được thêm vào cuối hàng đợi và P2 bắt đầu thực thi.

Bước 3) Tại thời điểm t = 4, P2 bị chiếm quyền ưu tiên và được thêm vào cuối hàng đợi. P3 bắt đầu thực thi.

Bước 4) Tại thời điểm t = 6, P3 bị chiếm quyền ưu tiên và được thêm vào cuối hàng đợi. P1 bắt đầu thực thi.

Bước 5) Tại thời điểm t = 8, P1 có thời gian thực thi là 4. Nó đã hoàn thành quá trình thực thi. P2 bắt đầu thực thi.

Bước 6) P2 có thời gian thực thi là 3. Nó đã thực thi được 2 chu kỳ. Tại thời điểm t = 9, P2 hoàn thành quá trình thực thi. Sau đó, P3 bắt đầu thực thi cho đến khi hoàn thành.

Bước 7) Chúng ta hãy tính thời gian chờ trung bình cho ví dụ trên.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Ưu điểm của phương pháp lập lịch luân phiên

Dưới đây là những ưu điểm/lợi ích của phương pháp lập lịch luân phiên (Round-robin):

Nó không phải đối mặt với các vấn đề về nạn đói hoặc hiệu ứng đoàn xe.
Tất cả các công việc đều được phân bổ CPU hợp lý.
Nó xử lý tất cả các quy trình mà không có bất kỳ sự ưu tiên nào.
Nếu bạn biết tổng số quy trình trên hàng đợi chạy thì bạn cũng có thể giả sử thời gian phản hồi trong trường hợp xấu nhất cho cùng một quy trình.
Phương pháp lập lịch này không phụ thuộc vào thời gian thực thi. Đó là lý do tại sao nó dễ dàng được triển khai trên hệ thống.
Khi một quy trình được thực thi trong một khoảng thời gian cụ thể, quy trình đó sẽ được ưu tiên và một quy trình khác sẽ thực thi trong khoảng thời gian nhất định đó.
Cho phép hệ điều hành sử dụng phương pháp chuyển đổi ngữ cảnh để lưu trạng thái của các tiến trình bị tạm dừng.
Nó mang lại hiệu suất tốt nhất về thời gian phản hồi trung bình.

Nhược điểm của lập kế hoạch luân phiên

Dưới đây là những nhược điểm của việc sử dụng phương pháp lập lịch luân phiên (Round-robin):

Nếu thời gian cắt lát của hệ điều hành thấp, hiệu suất của bộ xử lý sẽ giảm.
Phương pháp này tốn nhiều thời gian hơn cho việc chuyển đổi ngữ cảnh.
Hiệu suất của nó phụ thuộc rất nhiều vào lượng tử thời gian.
Không thể đặt mức độ ưu tiên cho các quy trình.
Lập lịch luân phiên không ưu tiên đặc biệt cho các tác vụ quan trọng hơn.
Nó làm giảm khả năng hiểu.
Lượng thời gian lượng tử thấp hơn dẫn đến chi phí chuyển đổi ngữ cảnh cao hơn trong hệ thống.
Việc tìm ra lượng tử thời gian chính xác là một nhiệm vụ khá khó khăn trong hệ thống này.

Độ trễ trong trường hợp xấu nhất

Thuật ngữ này được sử dụng cho thời gian tối đa cần thiết để thực hiện tất cả các nhiệm vụ.

dt = Ký hiệu thời gian phát hiện khi một tác vụ được đưa vào danh sách
st = Biểu thị thời gian chuyển đổi từ nhiệm vụ này sang nhiệm vụ khác
et = Biểu thị thời gian thực thi tác vụ

Công thức:

^T_worst = {(dt_i+ st_i+ et_i ), + (dt_i+ st_i+ et_i )₂ +...+ (dt_i+ st_i + et_i )_N., + (dt_i+ st_i + et_i  + et_i) N} + t_ISR
t_ISR = sum of all execution times

Câu Hỏi Thường Gặp

Lượng thời gian phân bổ, hay lát cắt thời gian, là khoảng thời gian CPU cố định mà mỗi tiến trình chạy trước khi bị gián đoạn. Nếu quá lớn sẽ hoạt động giống như FCFS (First Come First First - đến trước bảo toàn); nếu quá nhỏ sẽ làm tăng đáng kể chi phí chuyển đổi ngữ cảnh.

FCFS thực thi từng tiến trình theo thứ tự đến và không ưu tiên. Round Robin thì ưu tiên: nó cấp cho mỗi tiến trình một khoảng thời gian cố định và luân chuyển qua hàng đợi, cải thiện thời gian phản hồi và ngăn chặn các công việc kéo dài làm tắc nghẽn các công việc khác.

Vì mỗi tiến trình được đặt trong một hàng đợi tuần hoàn và nhận được một khoảng thời gian xử lý cố định theo thứ tự. Không có tiến trình nào bị bỏ qua hoặc bị trì hoãn vô thời hạn, do đó mỗi tiến trình cuối cùng đều nhận được thời gian xử lý của CPU bất kể độ dài hay thứ tự đến của nó.

Trí tuệ nhân tạo (AI) và máy học có thể dự đoán hành vi của quy trình và mô hình khối lượng công việc để điều chỉnh các quyết định lập lịch trong thời gian thực. Thay vì một chính sách cố định, hệ thống có thể điều chỉnh mức độ ưu tiên và phân bổ thời gian một cách linh hoạt, cải thiện hiệu suất sử dụng CPU, thông lượng và thời gian phản hồi.

Đúng vậy. Các mô hình AI có thể phân tích thời gian bùng nổ trong quá khứ và tải hệ thống để đề xuất một khoảng thời gian tối ưu, và điều chỉnh nó khi điều kiện thay đổi. Điều này cân bằng chi phí chuyển đổi ngữ cảnh với thời gian phản hồi tốt hơn so với một giá trị cố định duy nhất.