알고리즘의 종류

프로세스들이 작업을 수행하기 위해서는 프로세스 스케줄러로 부터 CPU를 할당 받아야 한다. 이런 작업은 운영체제에 의해 구현되고 CPU를 언제, 어떤 프로세스에게 배당되는지 결정하는 작업을 프로세스 스케줄링 이라 한다. 프로세스 스케줄링은 방법에 따라서 선점 스케줄링과 비선점 스케줄링으로 나눌수 있다. 다음은 프로세스 스케줄링의 종류이다. 

각각 스케줄링 알고리즘의 특징을 알기 전에 스케줄링의 목절을 알아보면 다음과 같은 목적을 고려해서 스케줄링 되어야 한다. 

●  공정한 스케줄링 : 스케줄링할 때 모든 프로세스들은 공평하게 취급되어야 하며 어느 프로세스도 무한정 대기 하는일이 없어야 한다. 

●  처리량 극대화 : 스케줄링할 때 프로세스들의 가능한 한 단위 시간당 처리량을 최대화 한다. 

●  응답 시간 최소화 : 대화식 사용자에게는 가능한 최대한 응답 시간을 빠르게 한다. 

●  반환 시간 예측 가능 : 시스템의 부하에 관계없이 일정한 작업은 같은 시간 내에 같은 비용으로 실행, 완료되어 반환시기를
 예측 가능해야 한다. 
●  균형 있는 자원 사용 : 스케줄링 시 시스템 내의 자원들이 유휴 상태로 놓이지 않게 골고루 사용하게 하고, 유휴 상태의 자원을 사용하는 프로세스에게 더 나은 서비스를 제공 한다. 
●  응답 시간과 자원 이용간의 조화 : 빠른 응답 시간과 자원의 활용도를 고려하여 응용에 따라 적절하게 조화시킨다.

●  우선 순위제를 실시 : 프로세스들에게 우선순위를 부여하여 우선순위가 높을수록 먼저 실행되도록 한다. 

●  페이지 부재를 적게 발생시키는 프로세스에게 더 좋은 서비스를 해준다. 

■ 선점 스케줄링  

선점은 한 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지 할 수 있는 방식이다. 우선순위가 높은 프로세스가 먼저 수행 될 때 유리하고, 빠른 응답시간을 요구하는 시분할 시스템에 유용하다. 하지만
선점 때문에 많은 오버헤드를 초래한다. 

□ Round robin 스케줄링

라운드 로빈 스케줄링은 FCFS (First come First service) 방식으로 각 프로세스는 같은 크기의 타임 슬라이스를 할당 받는다. 
만약 프로세스가 할당 받은 시간동안 작업을 완료하지 못하면 다음 프로세스로 넘어가고 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다. 

라운드 로빈 방식의 특징은 다음과 같다. 

● 시분할 방식의 시스템에서 효과적이다. 
● 할당 시간의 크기는 시스템의 효과적인 동작에 절대적인 영향을 미친다.
● 할당 시간이 크면 FCFS 방식과 같다. 
● 할당 시간이 작으면 자주 문맥교환이 발생하므로 오버헤드가 커진다. 

□ SRT 스케줄링

준비 큐에 있는 프로세스들 중에서 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 시킨다. 
SJF 방식에 선점 방식을 도입한 방식이라고 생각하면 편하다. 

현재 프로세스가 CPU를 할당 받아 사용중이더라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 실행 중인 프로세스는 선점될 수 있다. 또한 수행 중인 각각의 작업들의 실행 시간을 추적 보유하고 있어야 한다. 

□ MLQ 스케줄링 

작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 스케줄링 기법이다. 그룹화된 작업들은 각각의 준비 큐에 넣어서 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당 받는다. 

● 다단계 큐 알고리즘은 준비 상태 큐를 여러 종류로 분할해 둔다.
● 각 큐는 자신만의 독자적인 스케줄링을 가지고 있다. 
● 각각의 서로 다른 작업들이 다른 묶음으로 분류될 수 있을 때 사용되는 알고리즘이다. 
● 일괄 처리 작업이 실행 중일지라도 상위 단계 큐에 작업이 들어오면 일괄 처리 작업은 선점 당한다.
● 한 큐에서 다른 큐로의 작업 이동은 불가능 하다.

□ MFQ 스케줄링

새로운 프로세스가 들어오면 높은 우선순위를 할당해 주어 단계1에서 즉시 수행해 주고 점차 낮은 우선순위를 부여하며 단계 n쯤 되는 나중에는 그 작업이 완료될 때까지 라운드 로빈으로 순환된다. 하나의 준비 큐를 통해 여러 피드백 큐를 걸치며 작업을 수행하는 방법이다. 이 방법은 CPU에 대한 요구량에 따라 프로세스들을 분류하는대 이상적인 방법이다.

● 짧은 작업에 유리하다.
● 입출력 장치를 효과적으로 이용하려고 입출력 위주의 작업들에 우선권을 준다.
● 가능한 빨리 작업의 특성을 알고 그것에 맞게 해당 작업을 스케줄링 한다.
● 프로세스가 보다 하위 단계의 큐로 옮겨갈수록 주어진 할당 시간은 점차 크게 설정된다. 

■ 비선점 스케줄링

비선점은 한 프로세스가 CPU를 할당받으면 다른 프로세스는 할당 받은 프로세스가 작업을 종료할때 까지 CPU를 사용 불가능 한 방식이다. 모든 프로세스의 요구를 공정히 처리할 수 있다. 응답시간이 예측 가능하다. 단 짧은 작업이 긴 작업을 기다리는 경우가 발생 할 수 있다. 

□ 우선순위 스케줄링

각 프로세스에게 우선순위를 부여하여 순위가 높은 순서대로 처리하는 방법이다. 우선순위는 보통 프로세스의 특성과 종류에 따라서 각각 다르게 부여될 수 있다. 우선순위 스케줄링은 정적 우선 방법과 동적 우선 방법이 있다. 

정적 우선순위 방법 : 실행이 쉽고 상대적으로 오버 헤드는 적지만 주위 여건의 변화에 적응하지 못하고 우선순위를 바꾸지 않는다.

동적 우선순위 방법 : 상항 변화에 잘 적응한다. 구현하기가 복잡하고 오버헤드가 많으나 시스템이 응답도를 증가시켜 주므로 효율성이 있다. 

□ 기한부 스케줄링 

기한부 스케줄링은 작업들이 명시된 시간이나 기한 내에 완료되게 계획되고 작업들의 결과가 시간내에 구해지면 유용하고 마감 시간이 지난 후에 결과가 구해지면 쓸모가 없게 된다. 

● 사용자는 사전에 작업이 요구하는 정확한 자원을 제시해야만 한다. 만약 기한 시간 내에 일을 끝내지 못하면 막대한 손해를 초래한다.
● 시스템은 다른 사용자들에 대한 서비스를 감소시키지 않으면서 기한부 작업을 실행할 수 있어야 한다.
● 시스템은 기한까지 일을 끝내기위해 자원 안배를 주의 깊게 계획해야 한다.
● 만약 많은 기한부 작업들이 동시에 실행된다면 스케줄링이 너무 복잡하게 된다.
● 기한부 스케줄링으로 요구되는 집중적인 자원 운영은 많은 오버헤드가 뒤따른다. 

□ FCFS(FIFO) 스케줄링

가장 단순한 방식으로 프로세스들이 대기 큐에 도착한 순서에 따라 CPU를 할당 받는 방식이다. 

이방식은 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행한다. 다른 방식에 비하여 작업 완료 시간을 예측하기가 쉽다. 선점이 불가능하기때문에 수행시간이 긴 프로세스가 할당받은 상태라면 수행시간이 짧은 프로그램이 대기할 경우가 생기고 중요한 작업이 대기하는 상황이 발생할수 있다. 또한 대화식 사용자들에게는 부적합하다.

□ SJF 스케줄링

SJF 방식 (SJN)은 준비큐에서 기다리는 작업중 수행시간이 가장 짧다고 판단되는 것을 가장 먼저 수행하는 스케줄링 방법이다. 

FCFS 보다 평균 대기 시간을 감소시키지만 큰 작업일수록 FCFS에 비해 예측이 어렵다. 긴 작업보다 짧은 작업일 수록 오버헤드 면에서 볼 때 유리하다. 하지만 이 방법은 수행할 작업이 얼마나 긴 것인지를 정확히 판단 해서 수행해야 하는대 수행시간을 정확히 얻는다는 것이 어렵다. 

□ HRN 스케줄링

이 방법은 SJF의 약점 특히 긴 작업과 짧은 작업 간의 불평등을 어느 정도 보안한 방법이다. 

이 방법도 비선점 스케줄링 방식이므로 한 작업이 CPU를 차지하면 그 작업은 완성될 때까지 실행한다. 
우선순위는  (대기 시간 + 버스트 시간) / 버스트 시간 으로 정한다. 

각각 스케줄링 방법을 표로 정리해보면 다음과 같다.