라운드 로빈 스케줄링

Round-robin scheduling
이 기사는 컴퓨팅 스케줄에 관한 것입니다.그 외의 용도는, 라운드 로빈(동음이의)을 참조해 주세요.
quantum=3을 사용하는 라운드 로빈 사전 스케줄링 예제

Round-Robin(R; 라운드 로빈)은 프로세스 및 네트워크스케줄러에 의해 [1][2]컴퓨팅에 사용되는 알고리즘 중 하나입니다.일반적으로 시간 조각(시간 퀀텀이라고도 함)[3]이 각 프로세스에 동일한 부분과 순환 순서로 할당되어 모든 공정을 우선 순위 없이 처리합니다(순환 이그제큐티브라고도 함).라운드 로빈 스케줄링은 간단하고 구현이 용이하며 굶주림이 없습니다.라운드 로빈 스케줄링은 컴퓨터 네트워크에서의 데이터 패킷스케줄링 등 다른 스케줄링 문제에 적용할 수 있습니다.이것은 운영 체제의 [4]개념입니다.

알고리즘의 이름은 다른 분야에서 알려진 라운드로빈 원리에서 유래한 것으로, 각 사람이 동일한 점유율을 차지합니다.

프로세스 스케줄링

프로세스를 공정하게 스케줄 하기 위해 라운드 로빈 스케줄러는 일반적으로 시간 공유를 사용하여 각 작업에 시간 슬롯 또는[5] 퀀텀(CPU 시간 허용)을 부여하고 그때까지 완료되지 않으면 작업을 중단합니다.다음 번에 해당 프로세스에 시간 슬롯이 할당될 때 작업이 재개됩니다.프로세스가 속성 시간 양자 중에 종료되거나 대기 상태로 변경되면 스케줄러는 Ready 큐에서 실행할 첫 번째 프로세스를 선택합니다.시분할이 없거나 일자리의 크기에 비해 퀀텀이 크면 큰 일자리를 창출하는 프로세스가 다른 프로세스보다 선호될 것이다.

라운드로빈 알고리즘은 시간 쿼터가 만료되면 스케줄러가 프로세스를 CPU에서 강제로 내보내므로 프리엠프티브알고리즘입니다

예를 들어 타임슬롯이 100밀리초이고 job1이 완료하는데 총 250밀리초의 시간이 걸리는 경우 라운드 로빈 스케줄러는 100밀리초 후에 작업을 일시정지하고 다른 작업에 CPU 상의 시간을 부여합니다.다른 작업이 동일한 점유율(각각 100밀리초)을 갖게 되면 job1은 CPU 시간을 다시 할당받아 사이클을 반복합니다.이 프로세스는 작업이 완료되고 CPU에 더 이상 시간이 필요하지 않을 때까지 계속됩니다.

  • 작업 1 = 완료까지의 총 시간 250 ms(최대 100 ms).
  1. 첫 번째 할당 = 100 ms.
  2. 두 번째 할당 = 100 ms.
  3. 세 번째 할당 = 100 ms이지만 job1은 50 ms 후에 자동으로 종료됩니다.
  4. 작업의 총 CPU 시간 1 = 250 ms

라운드 로빈 스케줄링을 이해하기 위해 양자 시간이 100ms인 프로세스의 도착 시간과 실행 시간을 다음 표에 나타냅니다.

공정명 도착시간 실행시간
P0 0 250
P1 50 170
P2 130 75
P3 190 100
P4 210 130
P5 350 50
Round Robin Scheduling

또 다른 방법은 양자 크기가 프로세스의 크기에 비례하도록 모든 프로세스를 동일한 수의 타이밍 양자로 나누는 것입니다.따라서 모든 프로세스가 동시에 종료됩니다.

네트워크 패킷 스케줄링

주요 기사:네트워크 스케줄러

best effort 패킷스위칭 및 기타 통계적 다중화에서는 선착순 큐잉의 대체 수단으로서 라운드로빈 스케줄링을 사용할 수 있습니다.

라운드로빈 스케줄링을 제공하는 멀티플렉서, 스위치 또는 라우터에는 데이터 플로우마다 별도의 큐가 있으며 데이터 플로우는 송신원주소와 수신처 주소로 식별할 수 있습니다.이 알고리즘을 사용하면 큐에 데이터 패킷이 있는 모든 활성 데이터 플로우가 주기적으로 반복되는 순서로 공유 채널 상의 패킷을 교대로 전송할 수 있습니다.스케줄링은 작업 절약형입니다.즉, 1개의 플로우가 패킷에서 벗어나면 다음 데이터 플로우가 그 자리를 차지합니다.따라서 스케줄링에서는 링크리소스가 사용되지 않도록 합니다.

라운드 로빈 스케줄링에서는 데이터 패킷의 사이즈가 같으면 max-min 공정성이 발생합니다.이는 가장 오랜 시간 대기한 데이터 흐름에 스케줄링 우선순위가 부여되기 때문입니다.데이터 패킷의 크기가 작업마다 크게 다를 경우 바람직하지 않을 수 있습니다.큰 패킷을 생성하는 사용자는 다른 사용자보다 우선됩니다.이 경우 공정한 대기 행렬이 선호됩니다.

best effort 통신뿐만 아니라 보증 또는 차별화된 서비스 품질을 제공하는 경우 Deficit Round-robin(DRR; 결손 라운드 로빈) 스케줄링, Weighted Round-robin(WRR; 가중 라운드 로빈) 스케줄링 또는 Weighted Fair Queuing(WFQ; 가중치 균등화 큐잉)을 고려할 수 있습니다.

복수의 단말기가 공유 물리 매체에 접속되어 있는 멀티 액세스네트워크에서는 토큰링 등의 토큰 패스 채널액세스 스킴 또는 중앙제어 스테이션으로부터의 폴링 또는 자원 예약에 의해 라운드 로빈 스케줄링이 제공될 수 있습니다.

복수의 스테이션이 하나의 주파수 채널을 공유하는 집중형 무선 패킷 무선 네트워크에서 중앙 기지국에서의 스케줄링 알고리즘은 라운드 로빈 방식으로 이동국을 위한 타임슬롯을 예약하여 공정성을 제공할 수 있다.단, 링크 적응을 사용하는 경우 채널 조건이 다르기 때문에 특정 양의 데이터를 다른 사용자보다 "비용이 많이 드는" 사용자에게 전송하는 데 훨씬 오랜 시간이 걸립니다.채널 조건이 개선될 때까지 전송을 기다리거나 적어도 비용이 적게 드는 사용자에게 스케줄링 우선순위를 부여하는 것이 더 효율적입니다.라운드 로빈 스케줄링에서는 이를 사용하지 않습니다.채널 의존 스케줄링(예를 들어 비례적으로 균등한 알고리즘 또는 최대 스루풋스케줄링)에 의해 throughput 및 시스템스펙트럼 효율이 향상될 수 있습니다.후자는 바람직하지 않은 스케줄링 부족이 특징입니다.이러한 유형의 예약은 순환 대기열 데이터 구조를 통해 구현할 수 있는 시스템의 운영 체제에 대한 가장 기본적인 알고리즘 중 하나입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
  2. ^ 모바일 데이터 네트워크의 기초, 캠브리지 대학 출판부, ISBN 1107143217, 2016, GiWang Miao, Jens Zander, Ki Won Sung 및 Ben Slimane.
  3. ^ Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. p. 409. ISBN 978-0-13-380591-8.
  4. ^ Nash, Stacey L. (2022-06-11). "Best scheduling software of 2022". Popular Science. Retrieved 2022-07-07.
  5. ^ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2010). "Process Scheduling". Operating System Concepts (8th ed.). John Wiley & Sons (Asia). p. 194. ISBN 978-0-470-23399-3. 5.3.4 Round Robin Scheduling