Inor

[OS] CPU 스케줄링 알고리즘 본문

Computer Engineering/Operating System

[OS] CPU 스케줄링 알고리즘

Inor 2017. 11. 13. 21:47

- 스케줄링 알고리즘


 다중 프로그래밍 환경에서 여러 개의 프로세스가 있을때, 어떤 프로세스에게 컴퓨터의 자원을 언제 할당할지 정하는 알고리즘을 스케줄링 알고리즘이라고 합니다. CPU의 응답시간, 처리량, 효율성 등을 증대 시키기 위해서 자원을 효율적으로 할당해야 합니다. 스케줄링 알고리즘은 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스가 CPU를 강탈할 수 있는지 여부에 따라서 비선점, 선점 알고리즘으로 나뉘어집니다.




- 비선점 알고리즘


 비선점 알고리즘의 특징은 한번 CPU를 사용하면 프로세스가 종료될 때까지 CPU의 사용 권한을 반환하지 않습니다. 일괄 처리 방식에 용이합니다. 하나의 프로세스가 종료될 경우에만 문맥 교환(Context Switch)이 일어납니다. 그래서 문맥 교환(Context Switch)에의한 오버헤드가 적습니다. 모든 프로세스의 CPU 사용 요구를 순서대로 공정하게 처리할 수 있습니다. 중요한 프로세스의 요청이 들어와도 대기해야하는 문제점이 있습니다. 주요 알고리즘으로 FCFS, SJF, HRRN이 있습니다.



- FCFS (First Come First Served)


 대기 큐에 먼저 들어온 프로세스를 먼저 처리하는 알고리즘입니다. FIFO(First In First Out)이라고도 합니다. 실행 중이던 프로세스가 완료되면 대기 큐의 맨 앞에 있는 프로세스에게 CPU 사용 권한을 양도합니다. 대기 큐의 맨 앞에 있는 프로세스는 CPU를 사용하기 위해서 가장 오래 기다린 프로세스입니다. 실행 시간이 긴 프로세스에게 유리한 알고리즘입니다. 가장 기본적이고 간단한 스케줄링 알고리즘 입니다. 단일 알고리즘으로 사용되면 효율성이 매우 떨어집니다. 그리고 입출력 중심의 프로세스에게 불리합니다. 그러나 우선순위 기반의 알고리즘과 조합해서 사용한다면 매우 효율적인 알고리즘이 됩니다. 프로세스가 기아 상태에 빠질 가능성이 없습니다.


- SJF (Shortest Job First)


 실행 시간이 긴 프로세스에게 유리한 FCFS 알고리즘을 보완하기 위하여 만들어진 알고리즘입니다. 실행 시간이 짧은 프로세스를 먼저 실행 시키는 알고리즘입니다. 실행 시간이 짧은 프로세스가 대기 큐에 도착하면 큐의 맨 앞으로 이동합니다. 실행 중이던 프로세스가 완료되면 대기 큐의 맨 앞에 있는 프로세스에게 CPU 사용 권한을 양도합니다. 대기 큐의 맨 앞에 있는 프로세스는 대기하는 프로세스 중에 가장 실행 시간이 짧은 프로세스입니다. FCFS보다 프로세스의 평균 대기 시간이 짧아지는 효과가 있습니다. 프로세스가 기아 상태에 빠질 가능성이 있습니다.


- HRRN (Highest Response Ratio Next)


 실행 시간이 긴 프로세스에게 불리한 SJF 알고리즘을 보완하기 위하여 만들어진 알고리즘입니다. (대기 시간 + 실행 시간)/실행 시간을 이용하여 우선순위를 구합니다. 값이 높을수록 우선순위가 높은 프로세스입니다. 같은 실행 시간을 갖고 있는 프로세스가 있다면 대기 시간이 긴 프로세스일 경우에 우선순위가 높게 나옵니다. 프로세스가 기아 상태에 빠질 가능성이 없습니다.




- 선점 알고리즘


 선점 알고리즘의 특징은 프로세스가 CPU를 사용하고 있더라도 다양한 요인(프로세스의 우선순위, Time Quantum 등)에 의해서 다른 프로세스에게 CPU 사용 권한을 양보할 수 있습니다. 빠른 응답시간을 요구하는 대화식 시분할 시스템에 적합합니다. 긴급한 프로세스의 CPU 사용 요청을 빠르게 처리할 수 있습니다. 문맥 교환(Context Switch)이 자주 발생하기 때문에 많은 오버헤드를 초래합니다. 주요 알고리즘으로 RR, SRT가 있습니다.



- RR (Round Robin)


 FCFS와 비슷한 방식으로 동작하는 스케줄링 알고리즘입니다. 대신 실행 중이던 프로세스가 완료되지 않더라도 대기 큐의 프로세스에게 CPU를 양보합니다. 양보하는 기준은 CPU를 사용할 수 있도록 설정된 시간입니다. RR에서 가장 중요한 것은 프로세스에게 부여되는 CPU 사용 시간입니다. 이 시간이 지나면 Clock Interrupt가 발생 합니다. 그러면 CPU를 사용하던 프로세스는 다음 프로세스에게 CPU를 양보합니다. 마찬가지로 다음 프로세스도 Clock Interrupt가 발생할때까지만 실행합니다. 그리고 CPU를 양보한 프로세스는 대기 큐의 맨 마지막으로 이동합니다. 모든 프로세스는 설정된 시간만큼만 CPU를 사용할 수 있기 때문에 RR은 공평한 알고리즘입니다. 그러나 CPU 사용 시간이 너무 짧으면 문맥 교환(Context Switch)이 자주 발생하기 때문에 CPU 오버헤드가 증가합니다. CPU 사용 시간이 너무 길게 설정되면 FCFS와 같아집니다. 프로세스가 기아 상태에 빠질 가능성이 없습니다.


- SRTF (Shortest Remaining Time First)


  SJF의 선점 방식이라고 볼 수 있습니다. SRTF는 현재 실행 중인 프로세스와 대기 큐에 들어가기위해 대기하는 새로운 프로세스의 실행 예상 시간을 비교합니다. 새로운 프로세스의 실행 시간이 현재 실행 중인 프로세스의 남은 실행 시간보다 짧다면 새로운 프로세스는 CPU를 선점합니다. SJF의 경우에는 대기 큐의 맨 앞에 위치하도록 하지만 SRTF는 바로 CPU를 선점합니다. SJF와 마찬가지로 프로세스가 도착할때마다 실행 시간을 확인해야하는 부담은 여전히 존재합니다. 그리고 프로세스가 기아 상태에 빠질 가능성이 있습니다.

Comments