운영체제

스케줄링 알고리즘

주멘이 2018. 5. 29. 19:21

CPU 스케줄링 : 메모리에 있는 Ready상태의 프로세스 중 하나를 선택해 CPU 자원을 할당하는 것.


결정 시점 :    Running -> Waiting

     Running -> Ready

     Waiting -> Ready

     Running -> Terminated



<비선점형 vs 선점형>

- 비선점형 스케줄링(Non-preemptive Scheduling)

- 프로세스가 CPU를 할당 받으면 종료되거나 입출력 요청으로 자발적으로 중지될 때까지 계속 실행되도록 보장한다.

- 순서대로 처리되는 공정성이 있고, 스케줄러 호출 빈도가 낮고, 문맥 교환에 의한 오버헤드가 적다.

- 일괄 처리에 적합

- 처리 시간이 긴 프로세스가 실행 중일때, 처리 시간이 짧은 프로세스들을 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 존재.

   (Convoy Effect)

- 알고리즘

1. FCFS 

- 구현이 간단하고, 처리 순서가 명확

- Convoy Effect 발생

2. SJF (Shortest Job First)

- 처리 시간이 짧은 프로세스부터 할당받는다.

- Shortest Remaining Time First ? 할당시 짧은 프로세스 먼저 할당받지만, 

- if (작업 중 들어온 프로세스의 burst < 실행중인 프로세스의 burst) 

- 선점시킨다 (평균 대기시간 감소)

- 최소의 평균 대기시간 실현

- Starvaion 발생 : 우선순위가 작거나, 처리 시간이 긴 프로세스가 계속 자원을 할당받지 못하는 상태

(긴 프로세스는 후순위라 오랫동안 대기했음에도 불구하고 계속 자원을 할당받지 못하는 문제가 생긴다)

- Aging으로 해결 : 대기 큐에 있는 프로세스에 age를 부여

  처리 시간이 긴 프로세스라도 age가 크다면 ? 할당

3. HRRN (Highest Response Ratio Next)

- SJF의 단점을 보완. 

- 처리 시간(Burst) + 대기 시간(Waiting Time) / Busrt

- 처리 시간에 비해 대기 시간이 크다면 우선순위가 크다.


- 선점형 스케줄링(Preemptive Scheduling)

- 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.

- 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합, 긴급한 프로세서를 제어할 수 있다.

- 알고리즘

1. RR

2. SRTF

3. MLQ(Multi Level Queue)

- 여러개의 대기 큐로 구분

- 일반적으로 시스템, 대화형, 편집, 일괄 처리형, 학생 작업 순서대로 구분하여 우선순위를 부여

- 상위 대기 큐에 작업이 들어오면 하위 대기 큐의 작업이 수행중이더라도 선점한다.

4. MFQ(Multi-level Feedback Queue)

- MLQ에서 발생할 수 있는 Starvation을 보완.

- MLQ에서 우선순위가 작은것은 뒤로 밀려난다. (SJF에서 처리 시간이 긴 프로세스가 밀려나는 것과 같은 맥락)

- 중요도 별로 여러 대기 큐를 두고, 각 대기 큐마다 할당 시간을 부여해

- 대기 큐를 비선점형으로 운용하는 알고리즘



출처 및 참고

http://jwprogramming.tistory.com/17