[컴퓨터 구조] Chapter 11 CPU 스케줄링

CPU 스케줄링 개요

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 한다.
 

1) 프로세스 우선순위

프로세스는 종류마다 입출력 장치를 이용하는 시간과 CPU를 사용하는 시간의 양에 차이가 있다.
비디오 재생과 같이 입출력 작업이 많은 프로세스도 있고, 컴파일, 그래픽 처리와 같은 CPU작업이 많은 프로세스도 있다. 입출력 작업이 많은 프로세스를 입출력 집중 프로세스라고 하며, CPU 작업이 많은 프로세스를 CPU 집중 프로세스라고 한다.
입출력 집중 프로세스는 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무르며, CPU 집중 프로세스는 대기 상태보다 실행 상태에 더 많이 머무른다. 그러나! CPU 집중 프로세스는 입출력 집중 프로세스에 비해 더 많은 CPU를 사용하는데 동일한 빈도로 CPU를 사용하면 비합리적이다.
각각의 상황에 맞게, 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 프로세스마다 우선순위를 부여하는 방법으로 위의 문제를 해결할 수 있다.
 

2) 스케줄링 큐

PCB에 우선순위가 적혀있긴 하지만, CPU를 사용할 다음 프로세스를 찾기위해 운영체제가 일일이 PCB를 뒤적거리는 것은 비효율적이다.
그래서 운영체제는 프로세스들에게 줄을 서서 기다릴 것을 요구하는데, 이를 스케줄링 큐라고 한다.
스케줄링 큐는 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고싶은 프로세스들, 특정 입출력 장치를 사용하고 싶은 프로세스들을 모두 줄세우는 것이다.
운영체제가 관리하는 큐에는 준비 큐와 대기 큐가 있다.
준비 큐란 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐란 입출력 장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다.

 

3) 선점형과 비선점형 스케줄링

이미 CPU를 사용하고 있는 상황에서 다른 프로세스가 CPU를 사용하길 요청한다면?
CPU를 사용중인 프로세스로부터 CPU의 자원을 빼앗아 다른 프로세스에게 할당할 수도 있고,
CPU를 사용중인 프로세스의 작업이 끝날 때까지 다른 급한 프로세스를 기다리게 할 수도 있다.
 
선점형 스케줄링이란 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식을 의미한다. 즉 어느 하나의 프로세스가 자원 사용을 독점할 수 없다는 것을 의미한다.
반면 비선점형 스케줄링이란 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전 까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미한다. 비선점형 스케줄링 방식으로 자원을 이용하는 프로세스가 있다면 다른 프로세스들은 그 프로세스의 사용이 끝날 때까지 기다려야 한다.
 
이러한 선점형 스케줄링은 더 급한 프로세스가 언제든 끼어들 수 있는 스케줄링 방식이므로 어느 한 프로세스의 독점을 막고 프로세스에 골고루 자원을 배분할 수 있다는 장점이 있지만, 문맥 교환 과정에서 오버헤드가 발생할 수 도 있다.
 
비선점형 스케줄링은 문맥 교환의 횟수가 선점형 스케줄링보다 적기 때문에 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적지만, 하나의 프로세스가 자원을 사용중이라면 계속 기다려야 한다는 단점이 존재한다. 즉 모든 프로세스가 골고루 자원을 사용하지 못하는 것이다.
 
 

CPU 스케줄링 알고리즘

1) 스케줄링 알고리즘의 종류

선입 선처리 스케줄링

선입 선처리 스케줄링은 FCFS 스케줄링이라고 부른다. 단순히 말해 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다. 먼저 요청한 프로세스부터 CPU를 할당하는 것인데 가끔 프로세스들이 기다려야 하는 시간이 길어질 수 있다는 부작용이 있다.
프로세스 A는 17ms 동안 CPU를 이용하고 프로세스 B는 5ms 동안 CPU를 이용한다. 이때 2ms동안 CPU를 이용하는 프로세스 C가 들어오면, 프로세스 C는 2ms를 사용하기 위해 17 + 5의 시간을 기다려야 하는 것이다. 이를 호위 효과라고 한다.
 

최단 작업 우선 스케줄링

호위 효과를 방지하기 위해서는 CPU 사용 시간이 짧은 프로세스를 먼저 실행하면 된다. 이처럼 준비 큐에 삽입된 프로세스들 중 CPU의 이용시간 길이가 짧은 것부터 실행하는 스케줄링 방식을 최단 작업 우선 스케줄링 혹은 SJF 스케줄링이라고 한다.
 

라운드 로빈 스케줄링

라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 이용할 수 있는 정해진 시간을 의미한다. 즉, 라운드 로빈 스케줄링은 정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
 

최소 잔여 시간 우선 스케줄링

최소 잔여 시간 우선 스케줄링 혹은 SRT 스케줄링은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합한 방식이다.
최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
 

우선 순위 스케줄링

우선 순위 스케줄링은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스들부터 실행하는 스케줄링 알고리즘이다. 우선 순위가 낮은 프로세스들은 우선 순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있는데, 이를 기아현상이라고 부른다.
이를 방지하기 위한 대표적인 기법이 에이징이다. 에이징은 대기 중인 프로세스의 우선순위를 마치 나이먹듯 점차 증가시키는 방법이다. 에이징 기법을 적용하면 우선순위가 낮아 마냥 기다리기만 하는 프로세스가 없어지게 된다.
 

다단계 큐 스케줄링

다단계 큐 스케줄링은 우선순위별로 준비큐를 여러개 사용하는 방식이다. 다단계 큐 스케줄링 하에서 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스를 처리하는 방식이다.
 

다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태이다. 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없기에 우선순위가 낮은 프로세스는 계속 연기된다. 즉 다시한번 기아 현상이 발생하게 되는 것이다. 이를 보완한 스케줄링 알고리즘이 다단계 피드백 큐 스케줄링이다. 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있다. 즉 CPU를 오래 사용해야하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고 CPU를 비교적 적게 사요하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝나게 되는 것이다.