MỘT VÍ DỤ ĐỂ HIỂU THÊM VỀ GIẢI THUẬT ĐỊNH THỜI ROUND ROBIN

MỘT VÍ DỤ ĐỂ HIỂU THÊM VỀ GIẢI THUẬT ĐỊNH THỜI ROUND ROBIN

GIỚI THIỆU

Round robin là một giải thuật định thời CPU, trong đó mỗi tiến trình được gán một thời gian giữ CPU nhất định trong một chu kỳ chạy, thời gian đó được gọi là thời gian xoay vòng (quantum).

Giải thuật Round Robin có một số đặc điểm sau

– Là giải thuật chạy theo cơ chế không độc quyền vì mỗi tiến trình đều có một thời gian xoay vòng như nhau

– Đơn giản, dễ thực thi, và tất cả các tiến trình tránh được tình trạng “đói CPU”

– Khuyết điểm chính của giải thuật là tốn nhiều thời gian chuyển ngữ cảnh

 

VÍ DỤ MINH HỌA

 

Tiến trình Thời gian đến Ready List (RL) Thời gian xử lý (thực thi)
P1 0 7
P2 1 16
P3 3 8
P4 4 3
P5 2 2

 

Giả sử thời gian quantum=3

Biểu đồ Gantt trong trường hợp này là:

 

TÍNH THỜI GIAN CHỜ VÀ THỜI GIAN HOÀN TẤT CỦA MỖI TIẾN TRÌNH

– Thời gian chờ (waiting time) của mỗi tiến trình:

P1=0+(8-3)+(20-11)=14

P2=(3-1)+(17-6)+(24-20)+(29-27)=19

P3=(11-3)+(21-14)+(27-24)=18

P4=14-4=12

P5=6-2=4

– Thời gian hoàn tất (turnaround time) của mỗi tiến trình

P1=21

P2=36-1=35

P3=29-3=26

P4=17-4=13

P5=8-2=6

 

PHÂN TÍCH QUÁ TRÌNH NHẬN/TRẢ CPU CỦA CÁC TIẾN TRÌNH

Quá trình nhận CPU của các tiến trình được diễn tả như sau:

– Tại 0t: P1 vào RL nhận CPU, chạy hết thời gian quantum cho phép là 3t, sau đó quay về hàng đợi RL, đúng ngay thời điểm mà P3 vào RL (2 tiến trình cùng đến RL tại một thời điểm), hệ điều hành sẽ chọn tiến trình cũ (là P1) xếp vào RL trước tiến trình mới (là P3). Khi đó trong RL đã có P2 và P5 đang đợi trong RL theo thứ tự P2,P5. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P2,P5,P1,P3

– Tại 3t: P2 nhận CPU và chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình có mặt trong RL. Tại thời điểm 4t, khi mà P2 đang chạy thì P4 vào RL và đang đợi cùng với các tiến trình khác theo thứ tự P5,P1,P3,P4. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P5,P1,P3,P4,P2

→ P5 KẾT THÚC QUÁ TRÌNH CHẠY Ở BƯỚC TIẾP THEO

– Tại 6t: P5 nhận CPU và chạy 2t thì kết thúc và trả CPU lại. Thứ tự nhận CPU là: P1,P3,P4,P2

– Tại 8t: P1 nhận CPU và chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình đang đợi trong RL. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P3,P4,P2,P1

– Tại 11t: P3 nhận CPU và chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình đang đợi trong RL. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P4,P2,P1,P3

→ P4 KẾT THÚC QUÁ TRÌNH CHẠY Ở BƯỚC TIẾP THEO

– Tại 14t: P4 nhận CPU và chạy 3t thì kết thúc và trả CPU lại. Thứ tự nhận CPU là: P2,P1,P3

– Tại 17t: P2 nhận CPU và chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình đang đợi trong RL. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P1,P3,P2

→ P1 KẾT THÚC QUÁ TRÌNH CHẠY Ở BƯỚC TIẾP THEO

– Tại 20t: P1 nhận CPU, chạy 1t thì kết thúc và trả lại CPU. Thứ tự nhận CPU tiếp theo là: P3,P2

– Tại 21t: P3 nhận CPU chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình đang đợi trong RL. Thứ tự nhận CPU tiếp theo là: P2,P3

– Tại 24t: P2 nhận CPU và chạy 3t, sau đó quay về hàng đợi RL, đứng cuối cùng trong danh sách các tiến trình đang đợi trong RL. Do đó, thứ tự nhận CPU tiếp theo sẽ là: P3,P2

→ P3 KẾT THÚC QUÁ TRÌNH CHẠY Ở BƯỚC TIẾP THEO

– Tại 27t: P3 nhận CPU, chạy 2t thì kết thúc và trả lại CPU. Lúc này trong RL chỉ còn có P2 với thời gian xử lý còn lại là 7t. P2 nhận CPU nhưng vẫn thực hiện nhận và trả CPU xoay vòng theo khoảng thời gian là 3t cho đến khi chạy xong.

KẾT LUẬN

Giải thuật Round Robin là một trong những giải thuật được sử dụng phổ biến trong các hệ điều hành để điều phối hoạt động của các tiến trình. Đặc điểm nổi trội của nó là tạo ra sự công bằng cho các tiến trình trong khi chạy. Nhưng nó cũng còn hạn chế vì phụ thuộc thời gian xoay vòng của các tiến trình. Hiểu sâu về giải thuật này, giúp cho các nhà phát triển cải tiến giải thuật ngày một tối ưu hơn.

Bình luận

avatar