CPU 스케줄링 기법

CPU 스캐줄링

컴퓨터의 자원을 효율적으로 상용하기 위해서 정책을 계획하는 것이다. 특정 자원을 요청하고 있는 프로세스를 대상으로 CPU 자원을 할당해 주는 순서를 정해주는 것이다. 사용 목적은 다음과 같다.

• CPU 활용 극대화 : CPU의 유휴 시간 최소화
• 응답시간 단축 : 프로세스 평균 응답 시간 단축
• 공평한 자원 활용 : 주어진 기간 동안 특정 자원 사용 효율화
• Multi-tasking 효율화 : 다중 프로세스의 공평한 처리

 

스케줄러 역할에 따른 구분

장기 스케줄러	상위 스케줄링으로 어떤 작업이 시스템의 자원들을 차지할 것인지 결정한다. 결정된 작업은 큐에 적재된다.
중기 스케줄러	어떤 프로세스들이 CPU를 할당받을 것인지 결정한다. CPU를 사용하려는 프로세스 간 중재하여 일시적으로 보류하거나 재 활성화 한다.
단기 스케줄러	CPU 스케줄링, 프로세스 스케줄링이라고도 한다. CPU 스케줄러인 Dispatcher에 의해 동작한다. 프로세스를 CPU에 할당한다.

 

스케줄러의 점유 방식에 따른 구분

	선점(Preeptive)	비선점(Non-Preemtive)
개념	프로세스가 CPU 점유 중에도 다른 프로세스가 CPU를 점유할 수 있다.	프로세스가 CPU를 해제할 때까지 다른 프로세스는 대기한다.
장점	빠른 응답을 할 수 있으며 대화식 처리가 가능하다. 주로 모바일이나 RTOS에서 사용된다.	응답 시간을 예측할 수 있다. Batch Proccess에 적합하며 프로세스에 요구를 공정하게 처리한다.
단점	문맥 교환으로 인한 Overhead가 발생한다.	짧은 작업에도 장시간 대기하는 경우가 발생할 수 있다.
스케줄링 기법	Round-robin, SRT	FCFS, SJF, HRN

 

CPU 스케줄링 기법

• FCFS(First Come First Service : 대기 큐에 도착한 순서에 따라 CPU를 할당한다. 일단 프로세스가 CPU를 점유하면 작업이 끝날 때 까지 계속 사용하는 비선점형 스케줄러이다. 긴 작업으로 인해 짧은 작업들이 오래걸릴 수 있으며, 중요하지 않은 작업이 중요한 작업을 기다리게 할 수 있다.
• SJF(Shortest Job First) : 대기 중인 작업 중에 수행 시간이 가장 짧다고 판단한 것부터 CPU를 점유한다. FCFS보다 평균 대기시간을 감소시키지만 큰 작업에 대해서는 FCFS에 비해 대기시간을 예측하기 힘들다. 또한 CPU를 점유하기 시작하면 다른 작업이 들어와도 진행중이 작업이 끝나기 전까지는 CPU를 점유할 수 없는 비 선점형 스케줄러이다.
• 라운드 로빈(Round Robin) : FCFS에 의해서 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당한다. 할당된 시간안에 작업이 끝나지 않으면 해당 작업을 중단하고 다른 작업이 CPU를 점유하는 선점형 스케줄러이다. 타임 아웃으로 인해 취소된 작업은 준비 완료 리스트의 가장 뒤로 보내진다.
• SRT(Shortest Remaining Time) : SJF와 마찬가지로 처리가 완료되는데 가장 시간이 짧게 걸리는 작업을 우선을 CPU 점유권을 준다. 단, 짧다고 생각한 작업보다 더 짧은 작업이 들어오면 해당 작업과 교체되는 선점형 스케줄러이다. 실시간 시스템에 유리하다.
• Multi Level Queue : 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 스케줄링 기법이다. 그룹화된 작업들은 독자적인 알고리즘을 통해 CPU를 할당받는다.
• Multi Level Feedback Queue : 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 타임 슬라이스를 부여한다. 새로운 프로그램이 들어오면 우선순위 1을 할당해 주고 즉시 CPU 점유를 시작한다. 이후 들어오는 작업들에 대해 우선순위를 쭉 부여해주다가 일정 우선순위 이상이 되면 앞의 작업이 완료될 때 까지 라운드로빈 방식으로 순환된다. 초기에 우선순위에 따라 처리하는 비 선점형 방식을 이용하다가 나중에는 선점형을 이용하여 Hybrid 스케줄링 기법이다.