Process Scheduling Algorithm (비선점)

스케줄링 알고리즘 성능평가 요소

1. 프로세서 이용률(CPU Utilization)

• 시간당 CPU를 사용한 시간의 비율
• 프로세서를 실행상태로 항상 유지하여 유휴상태가 되지 않도록 한다. 가능하면 입출력(I/O) 중심의 작업보다 프로세서 중심의 작업을 실행해야한다.

2. 처리율(Throughput)

• 시간당 처리한 작업의 비율
• 단위 시간당 완료되는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.

3. 반환시간 또는 소요시간(Turnaround Time)

• CPU burst time + waitting time
• 작업이 시스템에 맡겨져서 메인 메모리에 들어가기까지의 시간, 준비 큐에 있는 시간, 실행시간, 입출력시간 등 작업 제출 후 완료되는 순간까지의 소요시간이 최소화되도록 일괄 처리 작업을 우선 처리한다.

4. 대기시간(Waiting Time)

• 대기열에 들어와 CPU를 할당받기까지 기다린 시간
• 작업의 실행시간이나 입출력시간에는 실제적인 영향을 미치지 못하므로 준비 큐애서 기다리는 시간이 최소화되도록 사용자 수를 제한한다.

5. 반응시간 또는 응답시간(Response Time)

• 대기열에서 처음으로 CPU를 얻을때까지 걸린시간
• 반응시간은 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격으로 대화형 시스템에서 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업의 요구가 없을때까지 처리한다.

 

시스템 관점의 지표 : CPU 활용도, 처리량

사용자 관점의 지표 : 소요시간, 대기시간, 응답시간

 

FIFO ( First - In - First - Out ) =  FCFS ( First - Come - First - Served)

• 가장 먼저 Ready Queue에 들어온 프로세스가 먼저 실행되는 것이다.
• 비선점 기법이다.

Waiting time

P1 : 0 - 0 = 0 (기다린 시간이 없으므로)

P2 : 24 - 0 = 24 (P1이 끝날 때까지 기다려야 했으므로)

P3 : 27 - 0 = 27 (P1과 P2가 끝날 때까지 기다려야 했으므로)

Average Waiting Time : (0 + 24 + 27) / 3 = 17

 

장점

기아상태가 발생하지 않는다.(공평하게 CPU할당)

 

단점

cpu burst time이 큰 프로세스가 먼저 실행되면 평균대기시간이 길어진다.

FCFS의 단점을 Convey effect라고 부른다.

 

 

 

SJF (Shorteset - Job - First - Scheduling)

• 말 그대로 현재 Ready Queue에 있는 프로세스들 중 CPU burst가 가장 작은 프로세스에게 우선순위를 주는 것이다.
• 이렇게 되면 FCFS에서의 Convey effect를 해결해 average waitting time을 줄일 수 있다.  
• 비선점 기법이다.

waitting time

P1 : 0

P2 : 8-2 = 6

P3 : 7-4 = 3

P4 : 12-5 = 7

Average Waiting Time : (0 + 6 + 3 + 7) / 4 = 4

 

장점

평균 waitting time이 가장 짧다.

 

단점

실제로 사용하기 힘들다(어떤 프로세스가 얼마정도의 CPU Burst를 가지는지 예측하기가 어렵다.)

기아현상 발생가능

 

HRN 스케줄링 ( Highest Response ratio Next )

• SJF방식에서 기아상태가 발생하는 것을 보완하기 위해 만든 스케줄링이다.
• 우선순위 계산 시 대기시간을 추가하여 대기시간이 증가할수록 우선순위가 증가하게 만든다.

.

 

우선순위 스케줄링

• Priority Scheduling은 말 그대로 우선순위가 높은 프로세스를 먼저 스케줄링 한다.
• 사실 FCFS는 우선순위를 도착순서에 준것이고 , SJF는 CPU Burst가 작은것에 우선순위를 준 것이다.
• preemptive(선점) 과 non-preemptive(비선점) 모두 가능하다
• 몇몇 우선순위 스케쥴링에서는 기아상태(starvation)이 발생할 수 있다.

 

 

https://eunhyejung.github.io/os/2018/07/12/operatingsystem-study09.html

https://jhnyang.tistory.com/155?category=815411

https://jhnyang.tistory.com/34
https://operatingsystems.tistory.com/entry/OS-Scheduling-Algorithm?category=495588