Schedueling?
운영체제에서 의미하는 스케줄링은 운영체제가 CPU의 자원을 어떤 프로세스에게 할당해 줄 것인지 그 일정을 짜는것이다. Context Switching에는 많은 자원이 소모되므로, 이 일정을 어떻게 짰는지에 따라 CPU자원 사용의 효율성이 결정된다.
Context Switching 에서의 Context
CPU가 프로세스를 실행하기 위한, 프로세스에 대한 정보를 의미한다. 그 정보로는 현재 프로세스의 상태, 프로세스가 다음에 실행할 명령어, 레지스터 값, 프로세스 번호 등이다.
멀티프로세스 환경에서는 여러 프로세스가 동시에 실행되는 것처럼 보이기 위해 노력중이다. 그 노력의 일환인 프로세스간 CPU 자원 할당 이동이 Context Switching 이며, CPU는 기존 할당된 프로세스의 Context를 저장하고, 새로 자원을 할당할 프로세스의 Context로 교체하는 과정을 거쳐 새로운 프로세스에게 자원을 할당한다.
주의 할 점이 있는데 Context Switching 중에는 CPU는 아무 일도 하지 못 한다. 프로세스에 의해 CPU 자원이 점유되고는 있지만, Context Switching중이기 때문에 실제로 사용되는 프로세스가 없다는 것이고, 이 말은 즉, Context Switching이 너무 자주 발생하면 CPU의 성능이 떨어지게 되는 것이다.
CPU의 성능이 떨어지지 않게 필요한 순간에 적절하게 Context Switching이 발생하도록 하는 알고리즘이 필요하며, 이 알고리즘을 사용하는 주체가 바로 운영체제 스케줄러다.
이 친구는 우선순위가 가장 높은 프로세스에게 CPU 자원을 할당 해 준다. 그렇다면 이 우선순위는 어떻게 결정될까?
비선점 스케줄링
어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료 될 때까지 다른 프로세스는 CPU를 사용할 수 없다.
해당 프로세스는 자기 일이 끝날때까지 CPU를 양보하지 않는다. Context Switching을 최소화 할 수 있지만, 급하게 처리 되어야 할 일이 있어도 처리하지 못하게 될 수도 있다.
FCFS (First Come First Service)
프로세스가 Ready Queue에 도착한 순서대로 CPU에 할당하는 방식이다. 작업 완료 시간을 예측할 수 있지만, 위에서 언급했듯이 급하게 처리해야 하면서 짧은 처리 시간을 가진 작업이 자기 순서를 한참 기다려야 할 수도 있다. 이러한 상황을 Convoy Effect, 호위 상태라고 한다.
SJF (Shortest Job First)
프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다. 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식으로 알려져 있다. 그러나 CPU 처리 시간이 긴 프로세스는 뒤로, 뒤로 계속 밀려난다. 자기 순서가 오지 않는 상황이 발생 할 수도 있다. 이러한 상황을 기아 상태라고 한다.
HRN (Highest Response Ratio Next)
SJF 방식에서 발생할 수 있는 기아 상태를 해결하기 위한 방식이다. 우선순위 처리를 단순 CPU 처리시간이 아닌, Ready Queue 에서 대기한 시간까지 고려해서 결정한다.
((대기 시간 + CPU 처리 시간) / CPU 처리 시간)
기다린 시간에 비례하여 우선순위를 높이는 방식으로 에이징 기법이라고 한다.
HRN이 이상적인 방식으로 보이고 FCFS 를 사용할 이유가 없어 보이지만 실제로는 SJF 나 HRN 을 사용하기 어렵다. 현실적으로는 프로세스마다 CPU 처리 시간이 얼마나 걸릴지 알 방법이 없다.
선점 스케줄링
어떤 프로세스가 CPU를 점유하고 있을 때 우선순위가 높은 다른 프로세스가 점유를 빼앗아 CPU를 점유할 수 있다. 긴급히 처리되어야 할 프로세스가 먼저 처리 될 수 있지만, Context Switching이 자주 일어날 수 있다.
SRT (Shortest Remaining Time)
SJF 방식을 선점 스케줄링 방식으로 변경 한 기법이다. SJF 와 동일해 보이지만 선점 방식이기 때문에 CPU를 점유중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우에는 CPU 점유를 뺏어버릴 수 있다.
라운드로빈 (Round-Robin)
FCFS 방식에 선점 방식과 Time Quantum 개념을 추가한 방식이다. 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 주는데, 이를 Time Quantum이라고 한다. Time Quantum시간만큼 CPU를 점유했다면, 해당 프로세스로부터 자원을 회수하고, Ready Quene의 가장 뒤로 보낸다. Time Quantum이 너무 길다면, 기존의 문제점인 호위상태가, 너무 짧다면 Context Switching이 자주 일어나게 된다.
다단계 큐 (Multi-Level Queue)
프로세스를 그룹으로 나누고, 그룹마다 Queue를 둔다. Ready Queue가 여러개인 것이다. 또한 각각의 Queue마다 다른 스케줄링 방식을 적용할 수도 있다. 다음의 Fore 와 Back을 보자.
Foreground Queue 와 Background Queue
사용자와 직접 상호작용하고 있는 프로세스는 빠르게 처리되어야 하니까 Fore Queue에 모이고 라운드로빈 같은 방식을 채택하고, 그렇지 않은 애들은 일괄처리 하도록 해서 Back에 모이고 FCFS같은 비선점 방식중 하나를 채택한다.
또한 여러개의 Queue를 사용함으로써 어떤 Queue에 CPU를 오래 할당할지를 결정해야 한다.
고정 우선순위
Queue마다 우선순위를 둬서 우선순위가 높은 Queue에 프로세스가 남아있다면 반드시 모두 처리한 뒤에 다음으로 넘어간다. 오.. 앞에서 비슷한 놈이 있었다. 그렇다. SJF처럼 기아 상태가 발생할 수 있다. 우선순위가 낮은 Queue는 계속해서 밀릴 것이다.
타임 슬라이스
운영체제가 Time Slice를 두고 이 시간 비율에 따라서 Queue에 자원을 할당한다. 7:3의 비율이라면 Fore에 7, Back에 3
다단계 피드백 큐 (Multi-Level Feedback Queue)
우선순위가 낮은 Queue에서 오래 기다린 프로세스의 우선순위를 점점 올려서 우선순위가 높은 Queue로 올려주는 방식의 에이징 기법을 적용했다. 고정 우선순위에서 발생하는 기아 상태를 어느정도 해결 해 준다.
