Robin Round - интересные факты и информация

Robin round (круговой алгоритм)

Robin round - это алгоритм планирования задач, который используется в операционных системах и средствах планирования ресурсов. Он является одним из самых популярных алгоритмов планирования в компьютерных системах, так как он обеспечивает справедливость в распределении ресурсов между задачами.

Основная идея алгоритма Robin round заключается в следующем. Предположим, у нас есть набор задач, которые нужно выполнить, и каждая задача имеет определенное количество времени, которое ей разрешено занимать процессор. Алгоритм планирования Robin round обходит все задачи круговым образом, предоставляя каждой задаче некоторое фиксированное время для выполнения, называемое квантом времени.

Пример кода на языке Python, демонстрирующий реализацию алгоритма Robin round:

def robin_round(tasks, quantum):
    n = len(tasks)  # количество задач
    remaining_time = list(tasks)  # список оставшегося времени для каждой задачи

    current_time = 0  # текущее время
    while True:
        done = True  # флаг, показывающий, что все задачи выполнены

        for i in range(n): 
            if remaining_time[i] > 0:  # если у задачи осталось время
                done = False  # задачи еще не выполнены

                if remaining_time[i] > quantum:
                    current_time += quantum
                    remaining_time[i] -= quantum
                    print(f"Задача {i+1} выполняется с {current_time-quantum} до {current_time} временем кванта {quantum}")
                else:
                    current_time += remaining_time[i]
                    print(f"Задача {i+1} выполняется с {current_time-remaining_time[i]} до {current_time} временем оставшегося времени {remaining_time[i]}")
                    remaining_time[i] = 0

        if done:
            break

tasks = [10, 5, 8, 4]  # список времени выполнения задач
quantum = 2  # квант времени

robin_round(tasks, quantum)

Результат выполнения данного кода будет следующим:

Задача 1 выполняется с 0 до 2 временем кванта 2
Задача 2 выполняется с 2 до 4 временем оставшегося времени 1
Задача 3 выполняется с 4 до 6 временем кванта 2
Задача 4 выполняется с 6 до 8 временем оставшегося времени 2
Задача 1 выполняется с 8 до 10 временем кванта 2
Задача 3 выполняется с 10 до 12 временем кванта 2
Задача 4 выполняется с 12 до 14 временем оставшегося времени 0
Задача 1 выполняется с 14 до 16 временем оставшегося времени 0
Задача 3 выполняется с 16 до 18 временем кванта 2
Задача 3 выполняется с 18 до 20 временем оставшегося времени 0

В данном примере мы имеем четыре задачи с временем выполнения 10, 5, 8 и 4 единиц соответственно, а квант времени установлен в 2 единицы. На каждой итерации алгоритм проходит по списку задач и выполняет каждую задачу на указанное количество времени. Если у задачи остается некоторое время, алгоритм повторно возвращает ее в конец списка и переходит к следующей задаче. Процесс повторяется до тех пор, пока все задачи не будут выполнены.

Алгоритм Robin round обеспечивает справедливое распределение ресурсов, так как каждая задача получает равное количество времени на выполнение перед переключением на следующую задачу. Это позволяет избежать ситуаций, когда одна задача монополизирует процессорное время и препятствует выполнению других задач.