모든 프로세스는 CPU를 필요로 하고, 먼저 CPU를 사용하고 싶어 합니다. 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 합니다. CPU 스케줄링은 컴퓨터 성능과도 직결되는 대단히 중요한 문제입니다.
CPU 스케줄링
프로세스들에게 현명하게 CPU를 배분하지 못하면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 당장 급하지 않은 프로세스들만 주로 실행되는 상태가 발생할 수 있습니다. 운영체제는 CPU 스케줄링을 이용하여 공정하고 합리적으로 CPU 자원을 배분합니다.
프로세스 우선순위
운영체제는 프로세스마다 상황과 중요도에 맞게 CPU를 이용할 수 있는 우선순위(Priority)를 부여합니다. 운영체제는 각 프로세스의 PCB에 우선순위를 명시합니다. PCB에 적힌 우선순위가 먼저 처리할 프로세스의 기준이 됩니다. 결국, 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행됩니다.
스케줄링 큐
운영체제는 프로세스들에 "줄을 서서 기다릴 것"을 요구합니다. 운영체제는 이 줄을 스케줄링 큐로 구현하고 관리합니다. 운영체제가 관리하는 대부분의 자원은 큐로 관리됩니다. 우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 할지라도, 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있습니다. 높은 우선순위를 가진 프로세스는 마치 VIP와도 같습니다.
- 준비 큐: CPU를 이용하고 싶은 프로세스들이 서는 줄
- 대기 큐: 입출력장치를 이용하고 싶은 프로세스들이 서는 줄
비선점형 스케줄링
비선점형 스케줄링은 하나의 프로세스가 자원을 사용하고 있을 때, 다른 프로세스가 해당 자원을 빼앗을 수 없습니다.
FCFS 스케줄링
FCFS(First Come First Served) 스케줄링은 선입 선처리 스케줄링이라고 불리며, 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리합니다. 가장 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있습니다. 예를 들어, CPU를 오래 사용하는 프로세스가 먼저 도착하면, 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다리는 호위 효과가 발생합니다.
SJF 스케줄링
SJF(Shortest Job First) 스케줄링은 최단 작업 우선 스케줄링이라고 불리며, 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간이 가장 짧은 프로세스부터 처리합니다.
HRN 스케줄링
HRN(Highest Response-ratio Next) 스케줄링은 준비 큐에 삽입된 프로세스들 중 가장 높은 응답률을 가진 프로세스부터 처리합니다.
- 응답률 = ( 대기 시간 + 실행 시간 ) / 실행 시간
우선순위 스케줄링
우선순위 스케줄링은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행합니다. 하지만, 우선순위가 높은 프로세스만 계속 먼저 실행되고, 우선순위가 낮은 프로세스는 계속 뒤로 밀리는 기아 현상이 발생할 수 있습니다. 기아 현상을 해결하기 위해 에이징 기법을 사용할 수 있습니다. 에이징 기법은 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시킵니다. 지금은 우선순위가 낮더라도, 언젠가는 높은 우선순위가 될 수 있습니다.
선점형 스케줄링
선점형 스케줄링은 하나의 프로세스가 자원을 사용하고 있을 때, 다른 프로세스가 해당 자원을 빼앗을 수 있습니다.
RR 스케줄링
RR(Round Robin) 스케줄링은 FCFS 스케줄링에 타임 슬라이스라는 개념이 더해진 방식입니다. 타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미합니다. 큐에 삽입된 프로세스들은 삽입된 순서대로 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입됩니다. 이때 문맥 교환이 발생합니다.
SRT 스케줄링
SRT(Shortest Remaining Time) 스케줄링은 최소 잔여 시간 우선 스케줄링이라고 불리며, SJF 스케줄링과 RR 스케줄링을 합친 방식입니다. 프로세스들은 정해진 타임 슬라이스만큼 CPU를 이용하고, 다음 프로세스는 남아있는 작업 시간이 가장 적은 프로세스가 선택됩니다.
다단계 큐 스케줄링
다단계 큐 스케줄링은 우선순위별로 준비 큐를 여러 개 사용하는 방식입니다. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 그다음 우선순위가 가장 높은 큐에 있는 프로세스들을 처리합니다. 예를 들어, 우선순위 0 큐에 삽입된 프로세스들, 우선순위 1 큐에 삽입된 프로세스들, 우선순위 2 큐에 삽입된 프로세스들 순서대로 CPU를 할당받아 실행됩니다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태입니다. 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없지만, 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있습니다. 다단계 피드백 큐 스케줄링은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 큐에서 너무 오래 기다리면 높은 우선순위 큐로 이동시킬 수 있습니다.
참고
CPU 스케줄링 알고리즘 요약정리
비선점 스케줄링과 선점 스케줄링
정보처리기사 실기 프로그래밍 기출: 프로세스 스케줄링
혼자 공부하는 컴퓨터구조+운영체제
