Chapter 4. CPU 스케줄링

1. 스케줄링의 개요

1-1. 프로세스 스케줄링과 CPU 스케줄링

프로세스의 상태 전환을 관리하는 것을 프로세스 스케줄링이라고 한다.

프로세스 스케줄링은 규모에 따라 세 가지로 나눌 수 있다.

① 고수준 스케줄링

고수준 스케줄링(long-term scheduling)은 가장 큰 틀에서 이루어지는 스케줄링으로 시스템 내의 전체 작업 수를 조절하는 것이다.

생성 상태의 프로세스를 준비 상태로 전환하는데 관여한다.

고수준 스케줄링은 멀티프로그래밍의 정도를 결정한다.

② 저수준 스케줄링

저수준 스케줄링(short-term scheduling)은 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.

즉, 저수준 스케줄링이 CPU 스케줄링이다.

③ 중간 수준 스케줄링

중간 수준 스케줄링(mid-term scheduling)은 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 시스템의 과부하를 막는 역할을 한다.

1-2. 스케줄링의 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 한다.
• 효율성: 시스템 자원이 효율적으로 사용되도록 스케줄링을 한다.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호한다.
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
• 반응성: 시스템이 적절한 시간 안에 프로세스 요구에 반응하도록 해야 한다.
• 무한 연기 방지: 프로세스의 작업이 무한히 연기되어서는 안 된다.

2. 스케줄링 시 고려 사항

2-1. 선점형 스케줄링과 비선점형 스케줄링

• 선점형 스케줄링: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
• 비선점형 스케줄링: 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.

2-2. 프로세스 우선순위

프로세스는 크게 커널 프로세스와 사용자 프로세스로 나뉜다.

CPU 스케줄러는 커널 프로세스에 사용자 프로세스보다 높은 우선순위를 부여한다.

이처럼 CPU 스케줄러는 프로세스 별로 중요도나 하는 일을 고려해서 우선순위를 부여하고 이를 고려해서 스케줄링한다.

2-3. CPU 집중 프로세스와 입출력 집중 프로세스

대부분의 프로세스는 CPU의 사용과 입출력 처리를 번갈아가면서 처리된다.

CPU를 할당받아 실행하는 작업을 CPU 버스트라고 하고 입출력 작업을 입출력 버스트라고 한다.

CPU 버스트와 입출력 버스트의 비중에 따라 프로세스를 나눌 수 있다.

• CPU 집중 프로세스: CPU 버스트가 많은 프로세스이다.
• 입출력 집중 프로세스: 입출력 버스트가 많은 프로세스이다.

입출력 집중 프로세스는 사용자와 상호작용이 많기 때문에 CPU 집중 프로세스와 입출력 집중 프로세스가 있을 때 입출력 집중 프로세스를 먼저 처리하는 것이 효율적이다.

2-4. 전면 프로세스와 후면 프로세스

• 전면 프로세스: GUI를 사용하는 운영체제에서 화면 맨 앞에 놓은 프로세스를 말한다.
• 후면 프로세스: 사용자와 상호작용이 없는 프로세스이다.

전면 프로세스는 사용자의 요구에 즉각 반응해야 하지만 후면 프로세스는 상호작용이 없다.

따라서 전면 프로세스의 우선순위가 후면 프로세스보다 높다.

3. 다중 큐

3-1. 준비 상태의 다중 큐

준비 큐는 우선순위에 따라 여러 큐가 만들어져 있는데 이것을 다중 준비 큐라고 한다.

프로세스가 준비 상태로 들어올 때 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.

프로세스의 우선순위를 배정하는 방식에는 두 가지가 있다.

• 고정 우선순위: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다.
• 변동 우선순위: 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.

3-2. 대기 상태의 다중 큐

대기 상태에서도 다중 큐를 사용한다.

시스템의 효율을 높이기 위하여 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다.

그러면 특정 장치에서 인터럽트가 들어왔을 때 이를 처리하기 편리하다.

4. 스케줄링 알고리즘

4-1. 스케줄링 알고리즘의 평가 기준

어떤 스케줄링 알고리즘이 효율적인지 파악하려면 평가 기준이 있어야 한다.

가장 많이 사용되는 평가 기준은 다음과 같다.

• CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정한다.
• 처리량: 단위 시간 동안 작업을 마친 프로세스 수를 측정한 것이다.
• 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간이다.
• 응답 시간: 프로세스 시작 후 첫 번째 반응이 나올 때까지 걸리는 시간이다.
• 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸린 시간이다.

스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다.

4-2. FCFS 스케줄링

FCFS(First Come First Served) 스케줄링은 준비 큐에 도작한 순서대로 CPU를 할당받는 비선점형 방식이다.

FCFS 스케줄링은 단순하고 공평하지만, 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스의 대기시간이 길어지는 콘보이 효과가 발생한다.

4-3. SJF 스케줄링

SJF(Shortest Job First) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다.

SJF 스케줄링은 FCFS 스케줄링보다 평균 대기시간이 줄어들어서 효율적이다.

그러나 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵고 작업 시간이 긴 특정 프로세스가 계속 실행되지 못하는 아사 현상(starvation)이 발생한다.

 

4-4. HRN 스케줄링

HRN(Highest Response Ratio Next) 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 모두 고려하는 스케줄링 방식이다.

HRN 스케줄링에서 프로세스의 우선순위를 결정하는 기준은 다음과 같다.

우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

HRN 스케줄링은 SJF 스케줄링에서 발생하는 아사 현상을 해결할 수 있다.

4-5. 라운드 로빈 스케줄링

라운드 로빈 스케줄링은 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.

라운드 로빈 스케줄링은 선점형 방식이기 때문에 콘베이 효과나 아사 현상이 발생하지 않는다.

라운드 로빈 스케줄링에서는 타임 슬라이스의 크기를 결정해줘야 한다.

타임 슬라이스의 크기가 너무 크면 FCFS 스케줄링과 다를 바가 없고 타임 슬라이스의 크기가 너무 작으면 문맥 교환이 너무 자주 일어나 효율이 떨어진다.

따라서 적당한 크기의 타임 슬라이스를 설정해야 한다.

4-6. SRT 우선 스케줄링

SRT(Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다.

SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

SRT 스케줄링은 SJF 스케줄링과 마찬가지로 아사 현상이 일어나고 운영체제가 프로세스의 종료 시간을 예측하기 어렵다.

4-7. 우선순위 스케줄링

프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다.

우선순위 스케줄링은 여러 스케줄링 알고리즘에 기본적으로 들어가 있는 알고리즘이다.

4-8. 다단계 큐 스케줄링

다단계 큐(multilevel queue) 스케줄링은 우선순위에 따라 여러 준비 큐를 사용하는 방식이다.

우선순위는 고정형 우선순위를 사용하며, 우선순위가 높은 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

다단계 큐 스케줄링에서는 각각의 큐마다 다른 스케줄링 알고리즘을 적용할 수 있다.

다단계 큐 스케줄링에서는 우선순위가 낮은 프로세스의 작업이 연기되는 문제가 발생한다.

4-9. 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용한다.

하지만 다단계 피드백 큐 스케줄링에서는 CPU를 사용하고 난 프로세스의 우선순위가 낮아져서 낮은 우선순위의 큐로 들어가게 된다.

다단계 피드백 큐 스케줄링의 또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기를 다르게 할 수 있다는 것이다.

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식이다.

 

「쉽게 배우는 운영체제」 조성호