예제가 포함된 라운드 로빈 스케줄링 알고리즘

라운드 로빈 스케줄링이란 무엇입니까?

이 알고리즘의 이름은 각 사람이 차례로 무언가를 동일한 몫으로 얻는 라운드 로빈 원칙에서 유래되었습니다. 멀티태스킹에 주로 사용되는 가장 오래되고 간단한 스케줄링 알고리즘입니다.

라운드 로빈 스케줄링에서는 준비된 각 태스크가 제한된 시간 동안 순환 큐에서 순차적으로 실행됩니다. 이 알고리즘은 또한 프로세스의 기아 실행을 방지합니다.

라운드 로빈 스케줄링의 특성

라운드 로빈 스케줄링의 중요한 특징은 다음과 같습니다.

• 라운드 로빈은 선점형 알고리즘입니다.
• CPU는 일정 시간 간격(시간 퀀텀/시간 슬라이스라고 함) 후에 다음 프로세스로 전환됩니다.
• 선점된 프로세스는 대기열 끝에 추가됩니다.
• 라운드 로빈은 클럭 속도에 따라 작동하는 하이브리드 모델입니다.
• 시간 분할은 특정 작업을 처리하는 데 할당된 최소 시간이어야 합니다. 하지만 이는 운영체제마다 다를 수 있습니다.
• 이는 특정 시간 제한 내에 이벤트에 반응하는 실시간 알고리즘입니다.
• 라운드 로빈 방식은 가장 오래되고 공정하며 쉬운 알고리즘 중 하나입니다.
• 이는 기존 운영체제에서 널리 사용되는 스케줄링 방식입니다.

라운드 로빈 스케줄링의 예

다음 세 가지 과정을 고려해 보세요.

단계 1) 실행은 버스트 시간이 1인 프로세스 P4에서 시작됩니다. 여기서 모든 프로세스는 2초 동안 실행됩니다. P2와 P3은 아직 대기 대기열에 있습니다.

단계 2) 시간 = 2일 때 P1이 큐의 끝에 추가되고 P2가 실행되기 시작합니다.

단계 3) 시간 = 4에서 P2가 선점되어 큐의 끝에 추가됩니다. P3가 실행을 시작합니다.

단계 4) 시간 = 6에서 P3가 선점되어 큐의 끝에 추가됩니다. P1가 실행을 시작합니다.

단계 5) 시간 8에서 P1의 버스트 시간은 4입니다. 실행이 완료되었습니다. 이제 P2가 실행을 시작합니다.

단계 6) P2의 버스트 시간은 3입니다. 이미 2개의 인터벌 동안 실행되었습니다. 시간 = 9에 P2의 실행이 완료됩니다. 그런 다음 P3가 실행을 시작하여 완료될 때까지 계속됩니다.

단계 7) 위 예시의 평균 대기 시간을 계산해 보겠습니다.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

라운드 로빈 스케줄링의 장점

라운드 로빈 방식의 장점/이점은 다음과 같습니다.

• 기아 문제나 호송대 효과와 같은 문제에 직면하지 않습니다.
• 모든 작업에는 CPU가 공정하게 할당됩니다.
• 이는 우선순위와 관계없이 모든 프로세스를 처리합니다.
• 실행 대기열의 총 프로세스 수를 알고 있으면 동일한 프로세스에 대해 최악의 응답 시간을 가정할 수도 있습니다.
• 이 스케줄링 방식은 버스트 시간에 의존하지 않습니다. 따라서 시스템에 쉽게 구현할 수 있습니다.
• 특정 기간 동안 프로세스가 실행되면 해당 프로세스는 선점되고 해당 기간 동안 다른 프로세스가 실행됩니다.
• 운영체제가 컨텍스트 스위칭 방식을 사용하여 선점된 프로세스의 상태를 저장할 수 있도록 합니다.
• 평균 응답 시간 측면에서 최고의 성능을 제공합니다.

라운드 로빈 스케줄링의 단점

라운드 로빈 스케줄링 사용의 단점은 다음과 같습니다.

• 운영체제의 슬라이싱 시간이 짧으면 프로세서 출력이 감소합니다.
• 이 방법은 컨텍스트 전환에 더 많은 시간을 소모합니다.
• 성능은 시간 양자에 크게 좌우됩니다.
• 프로세스에 대한 우선순위를 설정할 수 없습니다.
• 라운드 로빈 스케줄링은 더 중요한 작업에 특별한 우선순위를 부여하지 않습니다.
• 이해력을 저하시킨다.
• 시간 양자화 값이 낮을수록 시스템에서 컨텍스트 스위칭 오버헤드가 높아집니다.
• 이 시스템에서 정확한 시간 양자를 찾는 것은 상당히 어려운 작업입니다.

최악의 경우 지연 시간

이 용어는 모든 작업을 실행하는 데 소요되는 최대 시간에 사용됩니다.

• dt는 작업이 목록에 추가된 시점을 나타내는 감지 시간입니다.
• st = 한 작업에서 다른 작업으로 전환하는 데 걸리는 시간을 나타냅니다.
• et는 작업 실행 시간을 나타냅니다.

수식 :

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

자주 묻는 질문