#

Round Robin là gì? Đặc điểm của thuật toán lập lịch

Với những tính năng tuyệt vời thuật toán lập lịch Round-Robin có thể được triển khai ở tất cả các hệ điều hành. Trong bài viết dưới đây, BKHOST sẽ thông tin tổng quan về khái niệm, đặc điểm của Round-Robin và những ví dụ điển hình.

Round-Robin là gì?

Round-Robin la gi

Tên gọi của thuật toán Round-Robin có nguồn gốc từ chính nguyên tắc quay vòng. Round-Robin được đánh giá là một trong những thuật toán lập lịch đơn giản và có tuổi đời cao nhất. Với thuật toán này lần lượt mỗi tác vụ sẽ được chạy trong một hàng đợi với giới hạn thời gian cụ thể. Khả năng thực thi của thuật toán liên tục, tuần hoàn.

Đăng ký Gmail Doanh Nghiệp tại BKHOST

BKHOST đang có chương trình khuyến mại cực tốt cho khách hàng đăng ký dịch vụ Gmail Tên Miền Riêng:

  • Giảm giá lên đến 20%.
  • Giá chỉ từ 495k/5 mail.
  • Dung lượng lên đến 30GB/user.

Đăng ký ngay:

dịch vụ email

Đặc điểm của thuật toán Round-Robin

Thuật toán lập lịch Round-Robin sở hữu những đặc điểm quan trọng như:

  • Round-Robin là giải thuật ưu tiên.
  • Sau khoảng thời gian cố định CPU sẽ được chuyển sang quy trình tiếp theo.
  • Ở cuối hàng đợi thêm các quy trình mới tạo.
  • Round-Robin được điều khiển bằng đồng hồ tự nhiên.
  • Thời gian để xử lý một tác vụ cụ thể phải đặt ở mức tối thiểu. Và điều này có thể khác nhau ở mỗi hệ điều hành.
  • Các sự kiện ở thuật toán này đều được giới hạn trong một khoảng thời gian cụ thể.
  • Công bằng, dễ dàng, lâu đời và được sử dụng rộng rãi ở các hệ điều hành truyền thống là những điểm nổi bật của Round-robin.

Ví dụ về lập kế hoạch Round-robin

Lập kế hoạch Round –robin được diễn ra theo các bước sau:

Hàng đợi tiến trìnhThời gian bắt đầu tiến trình
P14
P23
P35

Va du ve lap ke hoach Round-robin

Bước 1: Quy trình P1 bắt đầu được thực thi với thời gian bắt đầu là 4 trong khi đó P2 và P3 đang ở hàng đợi. Mỗi quy trình này đều diễn ra trong khoảng thời gian là 2s.

Va du ve lap ke hoach Round-robin-b1

Bước 2: P1 sẽ được thêm vào cuối hàng đợi khi at time = 2 và lúc này P2 được thực thi.

Va du ve lap ke hoach Round-robin-b2

Bước 3: P3 được thực thi và P2 được thêm vào cuối hàng đợi khi at time = 4.

Va du ve lap ke hoach Round-robin-b3

Bước 4: P1 được thực thi khi at time = 6 và P3 lại thêm vào cuối hàng đợi.

Va du ve lap ke hoach Round-robin-b4

Bước 5: Thời gian nổ của P1 là 4 vì thế khi at time = 8 thì P1 hoàn thành việc thực thi, kế tiếp sẽ là P2.

Va du ve lap ke hoach Round-robin-b5

Bước 6: Thời gian nổ của P2 là 3 như vậy khi at time = 9 P2 sẽ thực thi xong, quá trình thực thi P3 bắt đầu cho đến khi hoàn thành.

Va du ve lap ke hoach Round-robin-b6

Bước 7: Thời gian chờ trung bình của ví dụ trên được tính như dưới đây:

Thời gian chờ đợi:

  • P1= 0+ 4= 4
  • P2= 2+4= 6
  • P3= 4+3= 7

Ưu và nhược điểm của lập kế hoạch Round-Robin

Ưu điểm

  • Phân bổ công việc cho CPU hợp lý, không xảy ra vấn đề ùn tắc hoặc thời gian chết.
  • Tất cả các quy trình đều được xử lý mà không có bất cứ ưu tiên nào.
  • Round-robin được thực hiện dễ dàng trên hệ thống vì không phụ thuộc vào thời gian nổ.
  • Bạn sẽ giả định được thời gian phản hồi của quy trình khi biết tổng số quy trình đang ở trên hàng đợi.
  • Trong một khoảng thời gian cụ thể nếu một quy trình được thực thi thì quy trình đó sẽ được ưu tiên. Và trong khoảng thời gian nhất định đó một quy trình khác sẽ được thực thi.
  • Trạng thái của các quy trình được ưu tiên sẽ được hệ điều hành sử dụng phương thức Chuyển đổi ngữ cảnh để lưu lại.
  • Thời gian phản hồi trùng bình nhanh, kịp thời.

Nhược điểm

  • Đầu ra của bộ xử lý giảm khi thời gian cắt của hệ điều hành thấp.
  • Việc chuyển đổi ngữ cảnh ở Round-robin tốn khá nhiều thời gian.
  • Lượng tử thời gian ảnh hưởng lớn đến hiệu suất của thuật toán Round-robin.
  • Các quy trình và những nhiệm vụ quan trọng không được ưu tiên.
  • Trong hệ thống này vấn đề tìm một lượng tử thời gian chính xác là nhiệm vụ nan giải.
  • Chi phí chuyển ngữ cảnh cao và suy giảm khả năng hiểu.

Độ trễ trường hợp xấu nhất (Worst Case Latency)

Thời gian tối đa để thực hiện xong xuôi mọi nhiệm vụ được biểu thị bằng thuật ngữ Worst Case Latency, trong đó:

  • dt = thời gian phát hiện ra tác vụ.
  • st = thời gian chuyển đổi giữa các nhiệm vụ.
  • et = thời gian để thực hiện trọn vẹn tác vụ.

Công thức:

T worst = {(dt i + st i + et i ), + (dt i + st i + et i ) 2 +...+ (dt i + st i + et i ) N ., + (dt i + st i + et i + et i ) N} + t ISR
t, SR = tổng thời gian thực hiện

Tổng kết về Round-Robin

Round-Robin mang đến sự điều phối công bằng các nhiệm vụ cho CPU. Chúng tôi tin rằng với bài viết trên bạn sẽ không còn quá xa lạ với thuật toán lập lịch lâu đời này để vận dụng nó trong một số trường hợp.

Nếu còn gặp bất cứ vướng mắc gì về Round-Robin, hãy để lại ở bên bình luận bên dưới, BKHOST sẽ trả lời bạn trong thời gian sớm nhất.

P/s: Bạn cũng có thể truy cập vào Blog của BKHOST để đọc thêm các bài viết chia sẻ kiến thức về lập trình, quản trị mạng, website, domain, hosting, vps, server, email,… Chúc bạn thành công.


  • thuật toán round robin
  • round robin là gì

Mua Tên Miền .CO giá rẻ nhất thị trường

Với chỉ 2 ký tự, tên miền .CO rất ngắn gọn và dễ nhớ. Được hiểu là company (công ty) hoặc corporation (tập đoàn), tên miền .CO là sự lựa chọn hoàn hảo cho bất kỳ công ty, doanh nghiệp hoạt động trong bất kỳ lĩnh vực nào.

BKHOST cam kết giá tốt. Đăng ký ngay hôm nay:

Tên miền .CO

Tôi là Trịnh Duy Thanh, CEO & Founder Công ty Cổ Phần Giải Pháp Mạng Trực Tuyến Việt Nam - BKHOST. Với sứ mệnh mang tới các dịch vụ trên Internet tốt nhất cho các cá nhân và doanh nghiệp trong nước và quốc tế, tôi luôn nỗ lực hết mình nâng cấp đầu tư hệ thống phần cứng, nâng cao chất lượng dịch vụ chăm sóc khách hàng để đem đến những sản phẩm hoàn hảo nhất cho người tiêu dùng. Vì vậy, tôi tin tưởng sẽ đem đến các giải pháp CNTT mới nhất, tối ưu nhất, hiệu quả nhất và chi phí hợp lý nhất cho tất cả các doanh nghiệp.
Bình luận

Thanh toán linh hoạt

Chúng tôi chấp nhận thanh toán như ATM, Visa, Internet Banking, Paypal, Baokim, Ngân lượng

Gọi ĐT tư vấn ngay
Chat ngay qua Zalo
Chat ngay qua Messenger