CPU 스케줄링(CPU scheduling)이란
CPU 스케줄링이란 운영체제가 프로세스들에게 효율적으로 CPU 자원을 배분하는 것을 말합니다.
즉, 준비 큐에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할지 결정하는 것입니다.
스케줄러의 종류
- 단기 스케줄러(CPU 스케줄러): 준비 상태의 프로세스 중에서 실행할 프로세스를 선택하여 CPU를 할당합니다.
- 중기 스케줄러: 너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우에 대비해 메모리에 적재된 프로세스의 수를 동적으로 조절합니다.
- 장기 스케줄러(작업 스케줄러): 어떤 프로세스를 준비 큐에 삽입할지를 결정하는 역할을 합니다.
선점형 / 비선점형 스케줄링
CPU 스케줄링은 크게 선점형 스케줄링(preemptive scheduling)과 비선점형 스케줄링(non-preemptive scheduling)으로 구분할 수 있습니다.
선점형 스케줄링이란 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 강제로 자원을 빼앗아 다른 프로세스에 할당할 수 있는 방식을 말합니다.
반면에, 비선점형 스케줄링이란 하나의 프로세스가 자원을 사용하고 있다면 해당 프로세스가 종료되거나 스스로 대기 상태에 진입하기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미합니다.
장점과 단점
선점형 스케줄링은 더 급한 프로세스가 언제든 끼어들어 사용할 수 있어 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다는 장점이 있지만, 문맥 교환 과정에서 오버헤드가 발생할 수 있습니다.
비선점형 스케줄링은 문맥 교환 횟수가 적어 이로 인한 오버헤드는 선점형 스케줄링보다 적지만, 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 프로세스가 있어도 기다려야 합니다. 즉, 모든 프로세스가 골고루 자원을 사용할 수 없다는 단점이 있습니다.
CPU 스케줄링 알고리즘
선입선출 스케줄링(FCFS, First Come First Served)
준비 큐에 들어간 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식입니다. 즉, CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 방식입니다.
CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스들은 기다려야 하기 때문에 평균 대기 시간이 길어질 수 있다는 단점이 있습니다.
최단 작업 우선 스케줄링(SJF, Shortest Job First)
준비 큐에 들어간 프로세스들 중에 CPU 이용 시간이 가장 짧은 프로세스부터 실행하는 스케줄링 방식을 말합니다.
시간이 짧은 프로세스부터 실행하기 때문에 FCFS 스케줄링보다 평균 대기 시간이 감소합니다.
라운드 로빈 스케줄링(Round Robin)
라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링 방식입니다.
큐에 삽입된 프로세스들은 순서대로 정해진 시간만큼만 CPU를 이용하고, 정해진 시간이 지나도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입합니다.
라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 중요합니다. 타임 슬라이스가 지나치게 크면 FCFS와 같게 되고, 지나치게 작으면 문맥 교환이 잦아져서 오버헤드가 증가합니다.
최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time)
프로세스들이 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스를 선택하는 방식입니다.
우선순위 스케줄링(priority scheduling)
프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘입니다.
이때 우선 순위가 낮은 프로세스들이 무한정 기다리는 기아(starvation) 현상이 발생할 수 있습니다.
이러한 기아 현상은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 에이징(aging) 기법으로 해결할 수 있습니다.
다단계 큐 스케줄링(multilevel queue)
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식입니다.
우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리합니다.
큐를 여러 개 두어 프로세스 유형별로 우선순위를 구분하여 실행할 수 있습니다. 또한 큐마다 타임 슬라이스를 다르게 지정할 수 있고, 다른 스케줄링 알고리즘을 사용할 수도 있습니다.
다단계 피드백 큐 스케줄링(mutilevel feedback queue)
다단계 큐 피드백 스케줄링 알고리즘은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘입니다.
새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 큐에 삽입되고 타임 슬라이스 동안 실행됩니다. 만약 프로세스가 해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐에 삽입합니다. 이 과정을 통해 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아집니다.
즉, CPU를 비교적 오래 사용하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 끝나게 됩니다.
또한 큐 사이를 이동할 수 있는 방식이기 때문에 낮은 우선순위 큐에서 장시간 대기하는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있습니다.
