라운드 로빈 스케줄링
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
라운드 로빈 스케줄링은 각 작업에 시간 슬롯을 할당하여 프로세스를 공정하게 스케줄링하는 프로세스 스케줄링 알고리즘이다. 시간 할당량 내에 작업이 완료되지 않으면 중단하고, 다음에 시간 슬롯이 할당될 때 재개한다. 이 알고리즘은 선점형이며, CPU 시간을 공정하게 분배하지만, 문맥 교환 오버헤드와 시간 할당량 설정에 따른 성능 변화가 단점이다. 네트워크 패킷 스케줄링에서도 사용되며, 각 데이터 흐름에 별도의 대기열을 할당하여 공정한 전송 기회를 제공한다. 가중 라운드 로빈(WRR)과 부족 라운드 로빈(DRR)과 같은 변형 알고리즘도 존재한다.
더 읽어볼만한 페이지
- 네트워크 스케줄링 알고리즘 - 트래픽 셰이핑
트래픽 셰이핑은 네트워크 정체를 방지하고 서비스 품질을 보장하기 위해 트래픽의 양과 속도를 제어하는 기술이다. - 네트워크 스케줄링 알고리즘 - 무작위 조기 검출
무작위 조기 감지(RED)는 통계적 확률을 기반으로 네트워크 혼잡을 관리하는 기술이며, 테일 드롭보다 공평하고 TCP 글로벌 동기화를 방지하며, 가중 RED(WRED), 입출력을 가진 RED(RIO), 적응/동적 RED(ARED), 강력한 무작위 조기 감지(RRED) 등의 변형이 존재한다. - 스케줄링 알고리즘 - 스케줄링 (컴퓨팅)
스케줄링은 운영 체제가 시스템의 목적과 환경에 맞춰 작업을 관리하는 기법으로, 장기, 중기, 단기 스케줄러를 통해 프로세스를 선택하며, CPU 사용률, 처리량 등을 기준으로 평가하고, FCFS, SJF, RR 등의 알고리즘을 사용한다. - 스케줄링 알고리즘 - 선입 선출
선입 선출(FIFO)은 먼저 들어온 데이터가 먼저 나가는 큐(Queue) 형태의 자료 구조로, 컴퓨터 과학, 전자 공학, 네트워크 장비 등에서 널리 활용된다.
| 라운드 로빈 스케줄링 | |
|---|---|
| 개요 | |
| 유형 | 스케줄링 알고리즘 |
| 클래스 | 컴퓨터 과학 |
| 자료 구조 | 큐 |
| 세부 사항 | |
| 작동 방식 | 각 프로세스에 고정된 시간 할당량을 부여하고, 할당 시간이 만료되면 다음 프로세스로 전환 |
| 시간 할당량 | 일반적으로 10~100 밀리초 |
| 특징 | 공정성 구현 용이성 예측 가능성 |
| 장점 | 모든 프로세스가 CPU 시간을 공정하게 할당받음 긴급한 작업이 없는 경우 유용 |
| 단점 | 문맥 교환으로 인한 오버헤드 발생 시간 할당량 크기에 따라 성능이 달라짐 짧은 작업을 기다리게 할 수 있음 |
| 활용 분야 | 시분할 시스템 패킷 큐잉 네트워크 스케줄링 운영체제 스케줄링 다중 프로그래밍 환경 실시간 시스템 (제한적) |
| 성능 | |
| 응답 시간 | 프로세스 수에 비례하여 증가 |
| 처리량 | 시간 할당량 크기와 문맥 교환 오버헤드에 따라 달라짐 |
| 공정성 | 모든 프로세스에 동일한 기회를 제공하여 비교적 높음 |
| 변형 | |
| 가중치 라운드 로빈 | 각 프로세스에 가중치를 부여하여 CPU 시간 할당량을 조정 |
| Fair Queueing | 각 연결 또는 흐름에 공정한 대역폭을 할당 |
| 예시 | |
| 운영체제 | 유닉스 리눅스 윈도우 |
| 네트워크 | 패킷 큐잉 알고리즘 |
| 기타 | |
| 관련 항목 | 스케줄링 알고리즘 큐 문맥 교환 데드락 |
2. 프로세스 스케줄링
프로세스 스케줄러는 프로세스 스케줄링을 위해 각 작업에 "퀀텀"[4] (CPU 시간 할당량)을 부여하고, 해당 시간 내에 작업이 완료되지 않으면 작업을 중단하는 방식으로 자원을 배분한다. 중단된 작업은 나중에 다시 CPU 시간을 할당받아 실행을 재개한다. 프로세스가 할당된 시간 퀀텀 동안 종료되거나 대기 상태로 변경되면, 스케줄러는 실행할 준비 큐에서 첫 번째 프로세스를 선택한다.
라운드 로빈 알고리즘은 스케줄러가 시간 할당량이 만료되면 CPU에서 프로세스를 강제로 내보내기 때문에 선점형 알고리즘이다. 만약, 시분할이 없거나 퀀텀이 작업의 크기에 비해 큰 경우, 큰 작업을 생성하는 프로세스가 다른 프로세스보다 우선시될 수 있다.
다른 접근 방식으로는 모든 프로세스를 동일한 수의 타이밍 퀀텀으로 나누어 퀀텀 크기가 프로세스 크기에 비례하도록 하는 방법이 있다. 이 경우 모든 프로세스가 동시에 종료된다.
2. 1. 기본 원리
라운드 로빈 스케줄러는 프로세스 스케줄링을 위해 시분할 방식을 사용한다. 각 프로세스에 동일한 시간 할당량, 즉 "퀀텀"을 부여하고, 이 시간 안에 작업이 완료되지 않으면 프로세스를 중단시킨다.[4] 중단된 프로세스는 나중에 다시 CPU 시간을 할당받아 실행을 재개한다. 만약 프로세스가 할당된 퀀텀 시간 동안 종료되거나 대기 상태로 변경되면, 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택하여 실행한다.라운드 로빈 알고리즘은 스케줄러가 시간 할당량이 만료되면 CPU에서 프로세스를 강제로 내보내기 때문에 선점형 알고리즘에 해당한다.
예를 들어, 시간 슬롯(퀀텀)이 100ms이고 "작업1"이 완료하는 데 총 250ms가 걸린다면, 라운드 로빈 스케줄러는 100ms 후에 "작업1"을 중단하고 다른 작업에 CPU 시간을 부여한다. 다른 작업들이 각각 동일한 시간(100ms)을 할당받으면, "작업1"은 다시 CPU 시간을 할당받고, 이 순환이 반복된다. 이 프로세스는 "작업1"이 완료되어 더 이상 CPU 시간이 필요하지 않을 때까지 계속된다.
- '''작업1 = 총 완료 시간 250ms (퀀텀 100ms)'''
# 첫 번째 할당 = 100ms
# 두 번째 할당 = 100ms
# 세 번째 할당 = 100ms이지만 "작업1"은 50ms 후에 자체 종료
# "작업1"의 총 CPU 시간 = 250ms
다음 표는 퀀텀 시간이 100ms일 때, 각 프로세스의 도착 시간과 실행 시간을 나타낸 것이다.
| 프로세스 이름 | 도착 시간 | 실행 시간 |
|---|---|---|
| P0 | 0 | 250 |
| P1 | 50 | 170 |
| P2 | 130 | 75 |
| P3 | 190 | 100 |
| P4 | 210 | 130 |
| P5 | 350 | 50 |
다른 접근 방식으로는 모든 프로세스를 동일한 수의 타이밍 퀀텀으로 나누어, 퀀텀 크기가 프로세스 크기에 비례하도록 하는 방법이 있다. 이렇게 하면 모든 프로세스가 동시에 종료된다.
비선점형 시스템(협력형 멀티태스킹)에서는 환형 목록을 준비하여, 어떤 태스크에서 빠져나오면 다음 태스크를 호출하는 방식으로 구현할 수 있다.
2. 2. 예시
예를 들어, 시간 할당량이 100ms이고 "작업1"이 완료하는 데 총 250ms가 걸리면 라운드 로빈 스케줄링은 100ms 후에 작업을 중단하고 다른 작업에 CPU 시간을 부여한다. 다른 작업이 각각 동일한 시간(100ms)을 할당받으면 "작업1"은 CPU 시간을 다시 할당받고 사이클이 반복된다. 이 프로세스는 작업이 완료되어 더 이상 CPU 시간이 필요하지 않을 때까지 계속된다.[4]- '''작업1 = 총 완료 시간 250ms (퀀텀 100ms)'''
# 첫 번째 할당 = 100ms.
# 두 번째 할당 = 100ms.
# 세 번째 할당 = 100ms이지만 "작업1"은 50ms 후에 자체 종료된다.
# "작업1"의 총 CPU 시간 = 250ms
라운드 로빈 스케줄링을 이해하기 위해 퀀텀 시간이 100ms인 프로세스의 도착 시간과 실행 시간을 다음 표로 나타내었다.
| 프로세스 이름 | 도착 시간 | 실행 시간 |
|---|---|---|
| P0 | 0 | 250ms |
| P1 | 50 | 170ms |
| P2 | 130 | 75ms |
| P3 | 190 | 100ms |
| P4 | 210 | 130ms |
| P5 | 350 | 50ms |
2. 3. 장단점
라운드 로빈 스케줄링은 모든 프로세스에 공정한 CPU 시간을 보장하고, 응답 시간을 개선할 수 있다는 장점이 있다.[4] 각 프로세스는 동일한 시간 할당량(퀀텀)을 받기 때문에, 특정 프로세스가 CPU를 독점하는 현상을 방지할 수 있다. 이는 사용자와 상호작용하는 프로그램에서 특히 유용하며, 빠른 응답 시간은 사용자 경험을 향상시킨다.하지만 잦은 문맥 교환으로 인한 오버헤드가 발생할 수 있으며, 시간 할당량 설정에 따라 성능이 달라질 수 있다는 단점도 존재한다.[4] 시간 할당량이 너무 짧으면 문맥 교환이 빈번하게 발생하여 오버헤드가 커지고, 반대로 너무 길면 응답 시간이 느려져 라운드 로빈 스케줄링의 장점을 살리기 어렵다. 따라서 적절한 시간 할당량을 설정하는 것이 중요하다.
예를 들어, 시간 할당량이 100ms이고, "작업1"이 완료하는 데 총 250ms가 걸리는 경우를 생각해보자. 라운드 로빈 스케줄러는 "작업1"을 100ms 실행한 후 중단시키고 다른 작업에 CPU 시간을 부여한다. 이후 다시 "작업1"에 100ms를 할당하고, 마지막으로 50ms를 실행하여 작업을 완료한다. 이처럼 라운드 로빈 스케줄링은 각 프로세스에 균등하게 CPU 시간을 분배하여 공정성을 확보한다.
3. 네트워크 패킷 스케줄링
최선형 노력 패킷 교환 및 기타 통계적 다중화에서 라운드 로빈 스케줄링은 선착순 대기열의 대안으로 사용될 수 있다. 라운드 로빈 스케줄링을 제공하는 다중화기, 스위치 또는 라우터는 각 데이터 흐름(데이터의 송신자와 수신자의 주소로 구분)에 대해 별도의 대기열을 가지며, 대기열에 데이터 패킷이 있는 모든 활성 데이터 흐름이 주기적으로 반복되는 순서로 공유 채널에서 패킷을 전송하는 데 번갈아 가며 사용할 수 있도록 한다.
이 방식에는 가중치를 부여하여 특정 흐름에 더 많은 기회를 주는 가중 라운드 로빈(WRR)과, 가중 라운드 로빈의 변형으로 평균 패킷 크기를 미리 알지 못해도 되는 부족 라운드 로빈(DRR)이 있다.
3. 1. 라운드 로빈 방식
라운드 로빈 스케줄링은 최선형 노력 패킷 교환 및 기타 통계적 다중화에서 선착순 대기열의 대안으로 사용될 수 있다.라운드 로빈 스케줄링을 제공하는 다중화기, 스위치 또는 라우터는 각 데이터 흐름(데이터의 송신자와 수신자의 주소로 구분)에 대해 별도의 대기열을 가진다. 이 알고리즘은 대기열에 데이터 패킷이 있는 모든 활성 데이터 흐름이 주기적으로 반복되는 순서로 공유 채널에서 패킷을 전송하는 데 번갈아 가며 사용할 수 있도록 한다. 이 스케줄링은 작업 보존 스케줄러로, 한 흐름에 패킷이 없으면 다음 데이터 흐름이 그 자리를 차지한다는 의미이다. 따라서, 스케줄링은 링크 리소스가 사용되지 않는 것을 방지하려고 한다.
라운드 로빈 스케줄링은 데이터 패킷의 크기가 동일한 경우 최대-최소 공정성을 제공한다. 가장 오랫동안 대기한 데이터 흐름에 스케줄링 우선 순위가 부여되기 때문이다. 데이터 패킷의 크기가 작업마다 크게 다른 경우에는 바람직하지 않을 수 있는데, 큰 패킷을 생성하는 사용자가 다른 사용자보다 선호되기 때문이다. 이러한 경우 공정 대기열이 더 선호된다.
보장되거나 차별화된 서비스 품질이 제공되고 최선형 노력 통신만 제공되는 경우, 결손 라운드 로빈(DRR) 스케줄링, 가중 라운드 로빈(WRR) 스케줄링 또는 가중 공정 대기열(WFQ)을 고려할 수 있다.
여러 단말기가 공유 물리적 매체에 연결된 다중 접속 네트워크에서 라운드 로빈 스케줄링은 토큰 전달 채널 접속 방식(예: 토큰 링) 또는 중앙 제어 스테이션의 폴링 또는 리소스 예약을 통해 제공될 수 있다.
여러 스테이션이 하나의 주파수 채널을 공유하는 중앙 집중식 무선 패킷 무선 네트워크에서 중앙 기지국의 스케줄링 알고리즘은 라운드 로빈 방식으로 이동 스테이션에 대한 시간 슬롯을 예약하고 공정성을 제공할 수 있다. 그러나, 링크 적응을 사용하는 경우, 채널 조건이 다르기 때문에 특정 양의 데이터를 "비싼" 사용자에게 전송하는 데 다른 사용자보다 훨씬 더 오랜 시간이 걸린다. 채널 조건이 개선될 때까지 전송을 기다리거나 적어도 덜 비싼 사용자에게 스케줄링 우선 순위를 부여하는 것이 더 효율적이다. 라운드 로빈 스케줄링은 이를 활용하지 않는다. 더 높은 처리량과 시스템 스펙트럼 효율은 채널 종속적 스케줄링(예: 비례 공정 알고리즘 또는 최대 처리량 스케줄링)을 통해 달성될 수 있다. 후자는 바람직하지 않은 스케줄링 기아로 특징지어진다는 점에 유의해야 한다. 이 유형의 스케줄링은 컴퓨터 운영 체제를 위한 매우 기본적인 알고리즘 중 하나이며 원형 큐 데이터 구조를 통해 구현할 수 있다.
3. 2. 가중 라운드 로빈 (Weighted Round-robin, WRR)
가중 라운드 로빈(WRR)은 각 연결에 가중치를 부여하여, 가중치가 높은 연결에 더 많은 전송 기회를 제공하는 스케줄링 방식이다. 이는 일반 프로세서 공유(GPS) 방식의 단순화된 형태로 볼 수 있다. GPS에서는 비어 있지 않은 연결에 대해 아주 작은 데이터량을 고려하는 반면, WRR은 비어 있지 않은 연결에 대해 패킷 수를 고려한다. 여기서 패킷 수는 '가중치 / 평균 패킷 크기'를 정규화한 값이다.3. 2. 1. 문제점
가중 라운드 로빈(WRR)은 평균 패킷 크기를 사전에 알아야 가중치를 정확하게 정규화할 수 있다는 문제가 있다. 인터넷 상에서 평균 패킷 크기를 미리 예측하는 것은 어렵기 때문에, 대략적인 예측에 의존해야 하는데 이 또한 쉽지 않다. 또한, WRR은 한 번의 라운드 내에서 공정성이 부족할 수 있다.3. 3. 부족 라운드 로빈 (Deficit Round-robin, DRR)
'''부족 라운드 로빈'''(Deficit Round-robin, DRR)은 가중 라운드 로빈의 변형이다. DRR은 1995년에 M. 슈리드하르(M. Shreedhar)와 G. 바르게세(G. Varghese)가 제안했으며, 평균 패킷 크기를 미리 알지 못해도 임의의 크기를 가진 패킷을 처리할 수 있다.DRR에서는 1라운드에서 송출 가능한 양(F)을 미리 정해둔다. 각 플로우(커넥션)의 1라운드당 통신량은 "가중치 × F"가 되며, 이 값을 부족 카운터(Deficit Counter)로 설정한다. 각 플로우에서 패킷을 송출할 때마다 해당 패킷 크기만큼 부족 카운터에서 값을 감소시키며, 부족 카운터가 음수가 되지 않는 한 송출을 계속한다. 한 라운드가 끝나면 부족 카운터에 다시 "가중치 × F"를 더하여 다음 라운드를 준비한다.
4. 다중 접속 네트워크에서의 활용
여러 단말기가 공유 물리적 매체에 접속하는 다중 접속 네트워크에서 라운드 로빈 스케줄링은 토큰 전달 방식이나 중앙 제어 스테이션의 폴링 또는 리소스 예약을 통해 구현될 수 있다.[1]
4. 1. 토큰 전달 방식
다중 접속 네트워크에서 라운드 로빈 스케줄링은 토큰 전달 채널 접속 방식(예: 토큰 링)에 적용될 수 있다. 이는 중앙 제어 스테이션의 폴링 또는 리소스 예약을 통해 제공될 수 있다.[1]4. 2. 폴링 또는 자원 예약
다중 접속 네트워크에서 여러 단말기가 공유 물리적 매체에 연결된 경우, 라운드 로빈 스케줄링은 토큰 전달 채널 접속 방식(예: 토큰 링)을 사용하거나 중앙 제어 스테이션의 폴링 또는 리소스 예약을 통해 제공될 수 있다.[1] 중앙 제어 스테이션이 각 단말기에 순차적으로 전송 기회를 부여하는 방식이다.[1]여러 스테이션이 하나의 주파수 채널을 공유하는 중앙 집중식 무선 패킷 무선 네트워크에서, 중앙 기지국의 스케줄링 알고리즘은 라운드 로빈 방식으로 이동 스테이션에 대한 시간 슬롯을 예약하고 공정성을 제공할 수 있다.[1] 그러나 링크 적응을 사용하는 경우, 채널 조건이 다르기 때문에 특정 양의 데이터를 "비싼" 사용자에게 전송하는 데 다른 사용자보다 훨씬 더 오랜 시간이 걸린다.[1] 따라서 채널 조건이 개선될 때까지 전송을 기다리거나, 적어도 덜 비싼 사용자에게 스케줄링 우선 순위를 부여하는 것이 더 효율적이다.[1] 라운드 로빈 스케줄링은 이러한 채널 조건의 차이를 활용하지 않는다.[1]
5. 무선 네트워크에서의 고려 사항
중앙 집중식 무선 패킷 무선 네트워크에서 중앙 기지국의 스케줄링 알고리즘은 라운드 로빈 방식으로 이동 스테이션에 시간 슬롯을 예약하여 공정성을 제공할 수 있다.[1] 그러나 링크 적응을 사용하면 채널 조건에 따라 특정 양의 데이터를 전송하는 데 걸리는 시간이 달라진다. 즉, "비싼" 사용자에게 데이터를 전송하는 데 다른 사용자보다 훨씬 더 오랜 시간이 걸릴 수 있다.[1] 따라서 채널 조건이 개선될 때까지 전송을 기다리거나, 덜 비싼 사용자에게 스케줄링 우선 순위를 부여하는 것이 더 효율적이다.[1] 하지만 라운드 로빈 스케줄링은 이러한 채널 적응을 활용하지 않는다.[1] 더 높은 처리량과 시스템 스펙트럼 효율은 비례 공정 알고리즘이나 최대 처리량 스케줄링과 같은 채널 종속적 스케줄링을 통해 달성할 수 있지만, 이러한 방식은 스케줄링 기아 문제를 야기할 수 있다는 단점이 있다.[1]
6. 구현
프로세스 스케줄링에서 사용되는 라운드 로빈 스케줄링은 원형 큐 데이터 구조를 통해 구현할 수 있다. 이 방식은 각 프로세스에 동일한 CPU 시간(퀀텀)을 할당하고, 퀀텀이 만료되면 다른 프로세스로 전환하는 방식으로 작동한다.
참조
[1]
서적
Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction]
http://pages.cs.wisc[...]
Arpaci-Dusseau Books
2014
[2]
서적
Fundamentals of Mobile Data Networks
Cambridge University Press
2016
[3]
서적
Operating Systems: Internals and Design Principles
Pearson
[4]
서적
Operating System Concepts
John Wiley & Sons
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com