CS운영체제

프로세스 스케줄링 알고리즘

목차

프로세스 스케줄링 알고리즘

프로세스 스케줄링이란? 이름에서 알 수 있듯이 프로세스 실행 순서 를 정해주는 것을 의미한다.

  • 프로세스 실행 순서는 자원(CPU, Memory) 를 할당 받는 순서에 따라 실행된다.
  • 프로세스 스케줄링의 목적은 Cpu나 Memory 같은 한정된 자원을 효율적으로 사용해 동일한 시간에 더 높은 처리 능력 을 갖기 위함이다.
  • 스케줄링 알고리즘은 크게 비 선점 스케줄링 과 선점 스케줄링 으로 나뉜다.

비 선점 스케줄링

실행 중인 프로세스로 부터 CPU 자원 을 뺏어 올 수 없다.

  • 한 프로세스에 CPU가 할당 되면 해당 작업이 끝나거나 대기상태로 전활될 때까지 CPU자원을 계속해서 차지한다.
  • 비 신점 스케줄링으로는 FCFS, SJF, HRN 방식이 있다.

FCFS(First Come, First Served) - 들어온 순서

Ready Queue 에 들어온 순서대로 CPU자원을 할당해주는 방식이다.

  • 구현이 엄청 단순하고 처리 순서가 확실해 확실한 작업 처리를 보장 받을 수 있다는 장점이 있지만
  • Convoy Effect 가 생길 수 있다는 단점이 있다.

Convoy Effect : 긴 작업시간을 요구하는 프로세스 때문에 간단히 끝낼 프로세스가 자원을 할당 받지 못하는 상황이다.

SJF(Shortest Job First) - 처리시간이 짧은 순서

Ready Queue 에서 처러시간이 짧은 Job을 우선적으로 처리해주는 알고리즘이다.

  • Ready Qeueu에 있는 프로세스들을 작업시간을 기준으로 우선순위를 정한다.(우선순위 큐 사용)
  • 작업시간이 가장 짧은 프로세스가 자원을 할당 받는 형식으로 작업을 한다.
  • Average Waiting Time이 줄어든다는 장점이 있지만, Starvation 이 생길 수 있는 단점이 있다.

Starvation : 작업시간이 길어 메모리상에 계속 프로세스가 존재하는 상태, 영구적으로 자원을 할당받지 못하고 갇혀 있을 수 있다.
Aging : 들어온 시간 으로 우선순위를 메기는 방식, 오래 남아있을 수록 우선순위가 높아져 오래 남아 있는 프로세스들도 자원을 할당받을 수 있다.

HRN(Hightest Response ratio Next) 스케줄링

SJF의 단점을 보완한 알고리즘, 처리시간 과 대기시간 을 모두 고려해 우선순위를 정한다. 처리시간 과 대기시간 을 고려한 공식을 적용한다.

  • (대기시간 + 처리시간) / 처리시간
  • 대기시간이 길어지면 길어질 수록 높은 우선순위를 가질 수 있다.

선점 스케줄링

실행 중인 프로세스로부터 CPU 자원 을 뺏어 올 수 있다.

  • 작업중인 프로세스를 중지시키고 CPU자원을 차지할 수 있도록 하는 방법이다.
  • 선점 스케줄링 방식으로는 RR, SRT, MLQ 방식이 있다

RR(Round Robin) 스케줄링

  • FCFS알고리즘을 선점 스케줄링 형식으로 바꾼 버전이다.
  • 보통 시분할 시스템 에서 사용이된다.
  • 할당되는 시간이 커지면 커질 수록 FCFS알고리즘과 비슷해진다.

SRT(Shortest Temainint Time)

  • SJF알고리즘을 선점 스케줄링 형식으로 바꾼 버전

MLQ(Multi Level Queue : 다단계 큐)

작업들을 여러 종류의 Ready queue로 구분하여 스케줄링하는 기법

MFQ(Multi Level Feedback Qeueu : 다단계 피드백 큐)

  • MLQ에서 생길 수 있는 Starvation을 보완한 스케줄링 기법.
  • 우선숨위가 가장 낮은 큐는 FCFS 또는 RR을 사용하고 나머지는 모두 RR스케줄링을 사용한다.
  • 우선순위가 높은 큐일수록 짧은 Time Slice를 주고 해당 Time Slice내에 못 끝내게 될 경우 우선순위가 한단계 낮은 큐로 보내진다.
  • 반대로 일정시간동안 실행되지 못하고 남아있는 프로세스의 경우 우선순위가 한단계 높은 큐로 보내준다.
Share