Lập kế hoạch round-robin là gì?

Question

Trong ngữ cảnh hệ điều hành đa nhiệm, đôi khi bạn nghe thuật ngữ lập lịch biểu vòng tròn. Nó đã tham khảo những gì?
Có loại lịch trình nào khác?

Answer 1

Round Robin Scheduling

Nếu bạn là một máy chủ trong một bữa tiệc của 100 khách, lịch round-robin sẽ có nghĩa là bạn bỏ ra 1 phút (một số tiền cố định) cho mỗi khách. Bạn đi qua từng khách một, và sau 100 phút, bạn sẽ dành 1 phút cho mỗi khách. Thêm thông tin về Wikipedia.

Có nhiều loại lịch biểu khác, chẳng hạn như ưu tiên (tức là những người quan trọng nhất trước), trước tiên đến trước được phục vụ, sớm nhất-hạn chót trước (tức là người rời sớm nhất), v.v. bắt đầu bằng cách googling để lập lịch các thuật toán hoặc kiểm tra scheduling at Wikipedia

Answer 2

Thuật toán xoay vòng là thuật toán lập lịch đơn giản mà thời gian được chia đều giữa các công việc không có mức độ ưu tiên.

Ví dụ - nếu bạn có 5 quy trình đang chạy - mỗi quy trình sẽ được phép chạy cho 1/5 một đơn vị thời gian trước khi một quy trình khác được phép chạy. Vòng robin thường dễ thực hiện trong một hệ điều hành.

Answer 3

Câu trả lời ở đây và thậm chí bài viết trên Wikipedia mô tả lịch trình xoay vòng để bao gồm cả thời gian định kỳ. Mặc dù điều này rất phổ biến, tôi tin rằng lập lịch và thời gian Round-Robin là không phải chính xác điều tương tự. Chắc chắn, đối với thời gian để làm cho tinh thần, round-robin lập kế hoạch được ngụ ý khi quay để mỗi nhiệm vụ, tuy nhiên bạn có thể làm round-robin lập kế hoạch mà không cần có timeslicing. Tức là, mỗi tác vụ có cùng mức độ ưu tiên trong vòng xoay vòng có thể được phép chạy cho đến khi chúng đạt đến điều kiện khối tài nguyên và chỉ sau đó có nhiệm vụ tiếp theo trong lần chạy xoay vòng. Nói cách khác, khi các tác vụ có mức độ ưu tiên bằng nhau tồn tại, các điểm sắp xếp lại là không thời gian trước khi làm trống.

Ý tưởng trên thực tế được thực hiện cụ thể trong trường hợp hạt nhân VxWorks của Wind River. Trong kế hoạch ưu tiên của họ, nhiệm vụ của mỗi lần ưu tiên chạy vòng xoay nhưng không có thời gian mà không cần kích hoạt tính năng đó trong nhân. Lý do cho sự linh hoạt này là để tránh các chi phí của các nhiệm vụ timeslicing đã được biết là chạy vào một khối trong một thời gian cũng bị chặn.

Do đó, trong khi lập kế hoạch dựa trên thời gian ngụ ý lập lịch trình round-robin, lập kế hoạch round-robin không yêu cầu thời gian bằng nhau dựa trên thời gian.

Answer 4

Timeslicing là cố hữu cho bất kỳ hệ thống lập kế hoạch round-robin trong thực tế, AFAIK.

Tôi không đồng ý với ý nghĩa InSciTek Jeff rằng Sau đây là round-robin lịch:

Đó là, mỗi công việc ở mức ưu tiên tương tự trong xoay round-robin có thể được phép chạy cho đến khi họ đạt được một điều kiện chặn tài nguyên trước khi yeilding đến nhiệm vụ tiếp theo trong vòng quay.

Tôi không thấy làm thế nào điều này có thể được coi là round-robin. Đây thực sự là kế hoạch ưu tiên.Tuy nhiên, có thể có một thuật toán lập lịch biểu có các thành phần của cả lịch trình round-robin và preemptive, mà VxWorks thực hiện nếu việc lập lịch trình round-robin và preemption đều được kích hoạt (round-robin bị vô hiệu hóa theo mặc định). Cách bật lịch biểu round-robin là cung cấp giá trị khác 0 trong số kernelTimeSlice.

Tôi đồng ý với tuyên bố này:

Vì vậy, trong khi timeslicing lịch dựa nghĩa lịch round-robin, lịch round-robin không yêu cầu thời gian bằng nhau dựa timeslicing.

Bạn nói đúng là không yêu cầu thời gian bằng nhau. Ưu đãi có thể muck với điều đó. Và thực sự trong VxWorks, nếu một nhiệm vụ được preempted trong round-robin lập kế hoạch, khi nhiệm vụ được kiểm soát một lần nữa nó sẽ thực hiện cho phần còn lại của thời gian nó được phân bổ.

Chỉnh sửa hướng vào InSciTek Jeff (Tôi không có đặc quyền nhận xét) Có, tôi đã đề cập đến việc khóa/ngắt vô hiệu hóa mặc dù tôi rõ ràng không thể hiện rõ điều đó. Bạn đã khước từ tôi (ha!) Với bình luận thứ hai của bạn. Tôi hy vọng sẽ tranh luận về điểm nổi bật hơn, rằng bạn tin rằng việc lập lịch trình round-robin có thể tồn tại mà không cần cắt thời gian. Hay bạn chỉ có nghĩa là cắt thời gian dựa trên thời gian bằng nhau? Tôi không đồng ý với cái cũ, nhưng đồng ý với cái sau. Tôi háo hức muốn học. Cảm ơn.

Edit2 hướng vào Jeff:

Round-robin có thể tồn tại mà không timeslicing. Đó là chính xác những gì xảy ra trong VxWorks khi kernelTimeSlice bị vô hiệu hóa (zero).

Tôi không đồng ý với tuyên bố này. Xem this document mục 2.2.3 với tiêu đề Round-Robin Scheduling.

Round-robin lập lịch trình thời gian sử dụng cắt để đạt được phân bổ hợp lý của CPU cho tất cả các nhiệm vụ có mức ưu tiên tương tự . Mỗi tác vụ, trong một nhóm các nhiệm vụ có cùng mức độ ưu tiên, thực hiện cho một khoảng thời gian hoặc khoảng thời gian xác định. Lập lịch biểu vòng tròn được bật bởi gọi hàm kernelTimeSlice(), trong đó lấy tham số cho một lát thời gian hoặc khoảng thời gian . [...] Nếu tính năng lập lịch biểu tròn được bật và việc sử dụng được kích hoạt cho nhiệm vụ thực thi, số xử lý đánh dấu hệ thống sẽ tăng số lượng lát thời gian của nhiệm vụ .

Timeslicing vốn có trong lịch trình round-robin. Nếu không, bạn đang dựa vào một nhiệm vụ để từ bỏ việc kiểm soát CPU, lập kế hoạch round-robin nhằm mục đích giải quyết.

Answer 5

Actaully, bạn đang bối rối với tính năng Lên lịch ưu tiên và Vòng xoay tròn. Infact RR là một phần của kế hoạch Preemptive.

Answer 6

Ý kiến. Có vẻ như chúng ta đang đan xen hai cơ chế thành một. Giả sử chỉ xác nhận ban đầu của OP "Trong ngữ cảnh hệ điều hành đa nhiệm" thì

1 - Trình lên lịch vòng tròn luôn lên lịch mục tiếp theo trong hàng đợi hình tròn.

2 - Cách trình quản lý lịch biểu lấy lại quyền kiểm soát để thực hiện lập lịch là riêng biệt và không liên quan.

Tôi không đồng ý rằng phương pháp phổ biến nhất cho 2 là thời gian cắt/năng suất chờ tài nguyên, nhưng như đã được ghi nhận có những người khác. Nếu tôi không nhầm lẫn Mac đầu tiên không tận dụng thời gian cắt, họ đã sử dụng năng suất tự nguyện/năng suất chờ đợi tài nguyên (các tế bào não 20 tuổi có thể sai đôi khi);

Answer 7

Lập lịch trình Round Robin dựa trên chia sẻ thời gian còn được gọi là lượng tử (thời gian tối đa do CPU đưa ra cho bất kỳ quá trình nào trong một lần). Có nhiều quy trình (yêu cầu thời gian khác nhau để hoàn thành thời gian bùng nổ) trong hàng đợi và CPU phải xử lý tất cả để nó tiếp tục chuyển đổi giữa các quy trình để cung cấp cho mọi quá trình bằng nhau dựa trên giá trị lượng tử. Loại lịch trình này được gọi là lập lịch Round Robin. Kiểm tra video đơn giản này để hiểu lập lịch trình vòng tròn dễ dàng: https://www.youtube.com/watch?v=9hw-_qJ55K4