1. CPU 스케줄링
: 운영체제가 프로세스들에 공정하고 합리적으로 CPU 자원을 배분하는 것이다.
가장 공정한 CPU 스케줄링
: 입출력 작업이 많은 프로세스의 우선순위는 CPU 작업이 많은 프로세스의 우선순위보다 높다.
스케줄링 큐
스케줄링 큐(Scheduling Queue)는 작업(Task)이나 요청(Request)을 일정한 규칙에 따라 저장하고, 꺼내서 처리 순서를 관리하는 큐 구조를 말합니다.
운영체제(OS), 서버 아키텍처, 마이크로서비스, 메시지 브로커(예: Redis, RabbitMQ), 그리고 웹 서버의 요청 처리 등 다양한 곳에서 사용됩니다.
준비 큐와 대기 큐
-
준비 큐: CPU를 이용하기 위해 기다리는 줄
-
대기 큐: 입출력장치를 이용하기 위해 기다리는 줄
- 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
- 같은 큐에서도 우선순위별로 처리한다.
프로세스 상태 다이어그램
선점형과 비선점형 스케줄링
1. 선점형 스케줄링
-
현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
- 우선순위가 높은 작업이 오면 즉시 CPU를 차지할 수 있음
- 빠른 응답성과 반응성을 제공
- 멀티태스킹에 적합
- Context Switching(문맥 교환)이 자주 발생
장점
- 긴 작업 때문에 짧은 작업이 오래 기다리는 문제를 줄일 수 있음
- 실시간 시스템, GUI 시스템 등에 적합
- 전체 시스템의 반응 속도가 빠름
단점
- 문맥 교환이 잦아져 오버헤드 발생
- 알고리즘이 복잡함
2. 비선점형 스케줄링
-
한 번 CPU가 어떤 프로세스에 배정되면, 그 프로세스가 스스로 끝나거나 I/O 요청으로 CPU를 반환하기 전까지 CPU를 빼앗지 않는 방식입니다.
- CPU 강제 회수가 없음
- Context Switching이 적어 오버헤드가 적음
- 예측 가능한 실행 흐름
장점
- 구현이 쉽고 안정적
- 문맥 교환 오버헤드가 거의 없음
- 배치 처리 시스템에 적합
단점
- 짧은 작업이 긴 작업 때문에 굉장히 오래 기다릴 수 있음 → Convoy Effect(선두 차단 현상)
- 실시간성이 떨어짐
- 우선순위가 낮아도 CPU를 독점할 수 있음
2. CPU 스케줄링의 대표적인 알고리즘
선입 선처리 스케줄링(FCFS 스케줄링)
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용
최단 작업 우선 스케줄링(Shortest Job First, SJF)
- 호위 효과를 방지하려면?
- CPU 사용 시간이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행
- CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
라운드 로빈 스케줄링
= Round Robin 스케줄링
-
선입 선처리 스케줄링 + 타임 슬라이스
-
타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
-
정해진 타임 슬라이스만큼 돌아가며 CPU를 이용하는 선점형 스케줄링
-
큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
-
정해진 시간을 모두 사용했음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥 교환)
-
최소 잔여 시간 우선 스케줄링
= SRT(Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링: 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스로 선택
우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리 방식으로 스케줄링
- 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 실행이 연기될 수 있음
- 우선순위 스케줄링의 근본적인 문제, 기아 현상
- 우선순위가 높은 프로세스만 계속 실행될 수 있다.
- 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 실행이 연기될 수 있다.
& 기아 현상 해결법
-
에이징 기법
-
오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
-
대기 중인 프로세스의 우선순위를 마치 나이를 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.
-
다단계 큐 스케줄링
= Multilevel Queue 스케줄링
-
우선순위 스케줄링의 발전된 형태
-
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스 처리
다단계 피드백 큐 스케줄링
-
다단계 큐 스케줄링의 발전된 형태이다.
-
큐 간의 이동이 가능한 다단계 큐 스케줄링
-
다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동이 불가능
-
우선순위가 낮은 프로세스는 계속해서 실행이 연기될 우려
-
기아 현상 발생 가능
-
- 즉, 어떤 프로세스의 CPU 사용 시간이 길면 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식
- CPU 스케줄링 방식으로 알려져 있다.
정리
CPU 스케줄링은 운영체제가 여러 프로세스에 CPU 자원을 공정하게 배분하는 방식으로, 준비 큐(Ready Queue)에서 CPU 사용을 기다리는 프로세스와 대기 큐(Wait Queue)에서 I/O 처리를 기다리는 프로세스를 관리하며 수행된다. 스케줄링 방식은 크게 선점형과 비선점형으로 나뉘는데, 선점형은 우선순위가 높은 프로세스가 CPU를 즉시 차지하여 시스템 반응성을 높이지만 문맥 교환 비용이 크며, 비선점형은 안정적이고 단순하지만 긴 작업 때문에 짧은 작업이 오래 대기할 수 있는 선두 차단(Convoy) 문제가 발생한다. 이러한 CPU 관리의 기본 개념을 바탕으로 다양한 방식의 스케줄링 알고리즘이 설계된다.
대표적인 스케줄링 알고리즘에는 FCFS(선입 선처리), SJF(최단 작업 우선), 라운드 로빈, SRT(최소 잔여 시간 우선), 우선순위 스케줄링 등이 있으며 각각 장단점을 가진다. 기아 현상이 발생할 수 있는 우선순위 스케줄링은 에이징을 통해 문제를 해결한다. 또한 멀티레벨 큐 스케줄링은 여러 우선순위 큐를 두고 가장 높은 우선순위 큐부터 처리하며, 이를 확장한 다단계 피드백 큐 스케줄링은 프로세스의 행동에 따라 큐 간 이동이 가능해 CPU 사용량이 많은 프로세스는 낮은 우선순위로, 오래 대기하는 프로세스는 높은 우선순위로 조정해 전체적인 공정성과 효율성을 높인다.
참고
