Bus Matrix에서 ‘라운드 로빈’ 알고리즘을 사용해서 마스터의 접근을 중재하는데, 이때 사용되는 ‘라운드 로빈’ 방식에 대해서 알아보고자 한다.
라운드 로빈 알고리즘이란?
해당 알고리즘은 ‘공정성’에 초점을 맞추었다는 특징을 가진다.
바로 예시를 들어보자.
상황: 3개의 작업(A, B, C)이 있고, 각 작업이 처리되기 위해 걸리는 시간이 주어진다.
- A: 6초, B: 4초, C: 8초
- Time Quantum(시간 조각): 2초
처리 순서:
- A 실행 (2초 사용, 남은 시간: 4초)
- B 실행 (2초 사용, 남은 시간: 2초)
- C 실행 (2초 사용, 남은 시간: 6초)
- 다시 A 실행 (2초 사용, 남은 시간: 2초)
- B 실행 (2초 사용, 남은 시간: 0초, 완료)
- C 실행 (2초 사용, 남은 시간: 4초)
- A 실행 (2초 사용, 남은 시간: 0초, 완료)
- C 실행 (4초 사용, 남은 시간: 0초, 완료)
기본 동작에 대해서는 더 언급할 것이 없는듯하다. 바로 동작 원리에 대해서 알아보자.
동작원리
먼저 해당 알고리즘은 모든 작업(요청)을 원형 큐에 저장한다.
그리고 ‘타임 퀀텀’ 만큼 해당 작업에 자원을 할당해주고, 이를 지나게되면 작업이 완료되었던 진행중이건 이를 중단시키고, 다른 작업에 자원을 할당하게 된다.
이때, 중단된 작업은 원형 큐의 가장 후순위로 배치된다.
특징
장점:
공정성 보장
: 자원 접근 기회가 고르게 분배된다.
스타베이션(기아 현상) 방지 : 특정 작업이 자원을 얻지 못하는 상황을 방지한다.
단순 구현 : 간단한 논리로 스케줄링이 가능하다.
단점:
시간 낭비 : Time Quantum이 너무 작으면 작업 전환이 잦아져 오버헤드가 증가한다.
적합하지 않은 경우 : 작업 시간이 Time Quantum보다 훨씬 짧거나 긴 경우 비효율적일 수 있다.