[정보처리기사: 운영체제] 라운드 로빈(Round Robin, RR) 스케줄링 알고리즘

---

라운드 로빈은 CPU 스케줄링 알고리즘 중 하나로, 여러 개의 프로세스가 CPU를 사용하기 위해 경쟁하는 환경에서 "CPU 사용 시간을 일정하게 할당"하는 방식입니다.

 

라운드 로빈 방식에서는 일정한 시간 간격으로 CPU를 할당해주며, 이 시간 간격을 "타임 슬라이스(Time Slice)" 또는 "양자(Quantum)"라고 부릅니다. 각 프로세스는 자신의 할당된 시간 동안 CPU를 사용할 수 있습니다.

 

만약 해당 프로세스가 타임 슬라이스 내에서 작업을 완료하지 못하면, 현재 작업을 일시 중단하고 다음 프로세스에게 CPU를 넘겨주게 됩니다.

라운드 로빈 방식은 모든 프로세스가 CPU를 공평하게 사용할 수 있도록 보장하기 때문에 "공정성"이 높다는 장점이 있습니다. 하지만, 타임 슬라이스가 너무 짧으면 CPU 스위칭이 빈번하게 일어나므로 "오버헤드"가 발생할 수 있고, 반대로 타임 슬라이스가 너무 길면 대기하는 프로세스들이 지연될 수 있습니다.

 

오버헤드 (Overhead)

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리

 

이러한 단점을 보완하기 위해 다음과 같은 변형 알고리즘이 개발되었습니다.

 

1) 랜덤화 (Randomization) 알고리즘

알고리즘 실행 시 특정 확률을 이용하여 무작위성을 부여하여 실행 결과를 얻는 알고리즘입니다.

예를 들어, 퀵정렬 (QuickSort) 알고리즘의 pivot을 무작위로 선택하는 것이 있습니다.

 

2) 분할 정복 (Divide and Conquer) 알고리즘

문제를 작은 단위의 문제로 분할하여 해결하는 알고리즘입니다.

예를 들어, 병합 정렬 (MergeSort) 알고리즘과 퀵 정렬 알고리즘이 있습니다.

 

3) 동적 계획법 (Dynamic Programming) 알고리즘

문제를 작은 단위의 문제로 쪼개어 해결한 후, 그 결과를 이용하여 전체 문제의 해를 구하는 알고리즘입니다.

예를 들어, 피보나치 수열을 구하는 알고리즘과 최장 공통 부분 문자열(Longest Common Subsequence)을 구하는 알고리즘이 있습니다.

4) 탐욕 알고리즘 (Greedy Algorithm)

현재 상황에서 최선의 선택을 하여 결과를 얻어내는 알고리즘입니다.

예를 들어, 최소 신장 트리(Minimum Spanning Tree)를 구하는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다.

 

5) 백트래킹 (Backtracking) 알고리즘

상태 공간 트리(State Space Tree)를 탐색하며 해를 찾는 알고리즘입니다.

예를 들어, N-Queens 문제와 Sudoku 퍼즐을 푸는 알고리즘이 있습니다.

 

6) 브루트 포스 (Brute Force) 알고리즘

가능한 모든 경우의 수를 다 해보는 알고리즘입니다.

예를 들어, TSP(Traveling Salesman Problem) 문제를 푸는 알고리즘이 있습니다.

 

7) 적응형 알고리즘 (Adaptive Algorithm)

실행 중인 알고리즘에 대한 정보를 수집하여 실행 중에 알고리즘을 최적화하는 알고리즘입니다.

예를 들어, 정렬 알고리즘에서 삽입 정렬 (Insertion Sort)와 퀵정렬을 적응적으로 사용하는 알고리즘이 있습니다.

---