스케줄링 개념 정리

스케줄링이란?

CPU 버스트*를 고려하여 운영체제가 공정하고 합리적으로 CPU 자원을 분배하는 것이다.

 

CPU 버스트: CPU를 사용하는 구간

 

스케줄링을 사용하는 이유

스케줄링의 주요 목적은 멀티 프로그래밍 환경에서 CPU의 유휴(idle) 시간을 최소화하여 CPU의 이용률을 최대하하는 것에 있다.

물론 아무 프로세스나 랜덤으로 넣어서는 안되고 프로세스들의 여러 조건들을 고려해서 어떤 것부터 처리할 지 결정한다.

 

한가지 예를 들어보자

입출력 작업이 많은 프로세스와 CPU 사용이 많은 프로세스가 있다. 이 둘 중 어떤 것을 먼저 처리해야 될까?

이 경우 일반적으로 입출력 작업이 우선 순위를 가진다. 

왜냐하면, 입출력 작업을 먼저 빨리 끝마친 뒤에 CPU 사용이 많은 프로세스에게 많은 CPU 자원을 할당해줄 수 있기 때문이다.

 

CPU 스케줄링은 이처럼 중요성과 우선 순위를 고려해서 프로세스들에게 자원을 할당해준다.

만약 무조건 먼저 요청한 순서대로 처리한다면, 당장 급한 프로세스가 실행되지 않고 별로 급하지 않은 프로세스들만 실행될 수 있다.

이는 곧 전체 성능의 저하를 초래하기 때문에 적절한 스케줄링 규칙은 필수로 요구된다.

 

스케줄링 동작 방식

앞에서 스케줄링을 시에 CPU 버스트를 고려하여서 우선 순위를 책정한다고 하였다.

이러한 우선 순위 정보들은 PCB 라는 곳에 저장되어 있는데, CPU 입장에서 PCB를 일일이 뒤져서 스케줄링을 하는 것은 여간 번거로운 일이 아닐 것이다.

 

따라서 이때 사용하는 것이 스케줄링 큐인데 이 큐를 이용하여서 프로세스들의 대기열을 관리할 수 있다.

 

스케줄링 큐는 대표적으로 두가지가 있다.

 

- 준비큐(ready queue)

메인 메모리에 상주하면서 CPU를 할당받아서 실행될 준비가 된 프로세스 집합이다. 즉, 스케줄러에게 선택되어 CPU에 올라가기를 기다리는 프로세스들의 집합이다.

 

- 대기큐(wait,device queue)

입출력 작업이 필요하지만 지금 당장 CPU를 사용하지 않는 장치들이 대기하고 있는 프로세스들의 집합이다.

예를 들어 프로세스가 디스크에 입출력 요청을 했다고 가정했을 시에 디스크는 여러 요청을 처리하느라 지연이 발생할 수 있다.

이때 CPU를 사용하지도 않는 프로세스가 CPU 자원을 받는 것은 비효율 적이기 때문에 대기큐로 빠지게 된다.

 

이렇게 큐에 프로세스들이 쌓이는 것을 알았다면 어떻게 프로세스를 선점하는 지를 알아보자

그 전에 스케줄링 디스패처의 구조를 알 필요가 있다.

 

대게 스케줄러와 디스패처를 같은 범주로 묶어서 말한다. 하지만 둘의 역할은 명확한 차이가 있다.

 

프로세스의 상태 변화로 인해 프로세스가 비어있게 되면 어느 프로세스를 CPU로 가져올지에 대한 작업이 이루어진다.

이 과정은 스케줄러가 담당한다.

스케줄러는 앞에서 배웠던 준비 큐에서 우선 순위에 따라 프로세스를 선택하고 실행한다.

 

디스패처는 이렇게 선택된 프로세스가 실제로 CPU에서 실행될 수 있도록한다.

선택 된 프로세스로 컨텍스트 스위칭을 해주며 이 작업을 위해 커널모드로 진입했다가 다시 프로세스 실행을 위해 유저 모드로 전환한다.

그리고 새로운 프로세스의 마지막 작업 상태를 불러오고 적절한 위치로 이동시켜준다.

 

그렇다면 "어떻게 CPU를 선점할 것인가?" 에 대한 고민이 필요한데 크게 선점형 , 비선점형 방식이 있다.

 

비선점형

실행 상태에서 프로세스의 자발적인 상태 변경으로 인한 스케줄링이 일어나는 것을 말한다.

 

1. IO request : 발생 시

2. terminate 발생 시 : 실행하던 프로세스가 끝났을 경우

 

비선점형 방식은 상호 협력적(다른 프로세스를 위해 양보하는 경우)이라는 장점이 있는 반면에 느린 응답 시간*이라는 단점이 있다.

모든 프로세스를 공정하게 처리한다.

 

Response time(응답 시간): ready 큐에 들어와서 처음으로 CPU(최초로)를 얻기까지 걸린 시간

 

선점형

프로세스가 끝나지 않았음에도 운영체제가 개입할 수 있다.

 

1. interrupt 발생 시 : 외부에서 인터럽트가 들어온 경우

2. IO request : 발생 시

3. time-out 발생 시 : time slicing (시분할) 에 의해, 주어진 시간이 끝났을 경우

4. wake-up 발생 시 : 대기 큐에 있는 프로세스들을 준비 큐에 옮길때

5. terminate 발생 시 : 실행하던 프로세스가 끝났을 경우

 

기본적으로 비선점형에서 하는 방식을 모두 사용하지만 운영체제가 적극적으로 스케줄링에 개입한다.

이로 인해 데이터 일관성 문제가 발생하기도 한다. -> 이것을 방지하기 위해 뮤텍스 , 세마포어 기술 적용

 

외부 인터럽트를 허용한다! 하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드가 발생할 수 있다.

또한 우선 순위로 프로세스를 처리하기 때문에 우선 순위가 낮은 프로세스들은 CPU를 할당받지 못할 수 있다. (기아 현상)

 

이제 마지막으로 스케줄러가 어떤 알고리즘으로 큐에서 가져오는 지 알아보자

여러가지가 있지만 대표적으로 7가지만 추려보았다.

 

스케줄링 알고리즘

- FCFS

준비큐에 먼저 도착한 순서대로 처리한다.

프로세스들이 기다리는 시간이 매우 길어질 수 있다.

Convoy effect 현상이 발생할 수 있다. 

 Convoy effect: 실행 시간이 긴 프로세스로 인해 뒤에 있는 프로세스들의 대기시간이 길어지는 현상

 

- SJF(Shortest job first)

프로세스의 CPU 버스트가 가장 짧은 순서대로 실행한다.

CPU 사용시간이 긴 프로세스는 나중에 , 짧은 프로세스는 먼저!

기존적으로 비선점 형으로 구현된다.

 

- SRTF

SJF + Round Robin

남은 CPU 버스트가 가장 짧은 순서대로 실행한다.

time slice만큼 cpu를 이용하되, 남은 작업 시간이 가장 적은 프로세스부터 실행

 

- priority

우선 순위가 높은 프로세스부터 실행

우선 순위가 같다면 FCFS로 처리

 

starvation(기아) 현상이 발생할 수 있음 (우선 순위가 낮은 프로세스는 실행 무기한 지연)

-> 에이징 기법으로 해당 문제를 완화할 수 있음

 

- Round-Robin

FCFS + 타임 슬라이스

time slice로 나눠진 CPU time을 번갈아가며 실행

정해진 시간이 끝났음에도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입한다.

 

Round Robin에서 time slice의 크기가 너무 크다면 fcfs에서 발생하는 문제가 그대로 나타나고,

반대로 너무 작아져버리면 context switching으로 인한 CPU의 오버헤드가 발생한다.

따라서 적절한 time slice의 크기를 필연적으로 고려해야한다.

 

- multilevel-queue

우선 순위별로 준비큐를 여러개 사용하는 방식

프로세스 유형별로 그룹화해서 큐별로 다른 스케줄링 알고리즘을 적용할 수 있다.

 

queue 간의 이동이 불가능하고 기아 현상이 발생할 수 있다.

 

- multilevel-feedback-queue

queue 간의 이동이 가능한 multilevel-queue 스케줄링 방식

정해진 time slice 안에 프로세스를 완료하지 못했으면 우선 순위가 낮은 큐로 이동한다.

-> 다른 프로세스의 우선 순위가 상대적으로 높아짐

에이징 기법도 적용 가능하다.

 

CPU 스케줄링의 가장 일반적인 형태이다!

결론

운영체제는 멀티프로세스 환경에서 CPU의 이용률을 최대화하기 위해 여러 스케줄링 방식을 사용한다.

 

만일 적합하지 못한 방식을 사용한다면 프로세스가 무기한 지연되는 기아(starvation) 현상이나 응답 시간의 지연을 초래할 수 있다.

따라서 CPU 선점 방식에서부터 알고리즘 까지, 상황에 맞게 적당한 방식을 고르는 것이 중요하다.