반응형

스케줄링 알고리즘 선택 기준


스케줄링 알고리즘을 선택하기 위해서는 몇가지 특성을 고려하여 선택해야 한다.


프로세서 사용률 :: 프로세서를 항상 실행 상태로 유지하여 유휴 상태(CPU가 쉬는 시간)이 되지 않도록 해야한다.

따라서 이때는 입출력 중심 작업 보다는 프로세서 중심 작업을 실행한다.


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


반환시간 :: 작업이 메모리에 들어가기까지 걸린 시간, Ready Queue에 머무는 시간, 실행 시간, I/O 시간 등 작업을 완료하는데 걸리는 시간을 최소화 시킨다. (끝난시간 - 도착시간)


대기시간 :: Ready Queue에서 기다리는 시간을 최소화 시킨다.  (시작시간 - 도착시간)


반응시간 :: 작업을 요청한 시간부터 반응을 시작하는 시간까지의 간격을 의미한다. 대화형 시스템에서 중요하다.



반환시간 :: 끝난시간 - 도착시간



스케줄링 알고리즘



비선점 방법


선입 선처리 스케줄링(FCFS, First Come First Served or FIFO)


선입선처리 스케줄링은 비선점 방법이며 프로세서 스케줄링 알고리즘 중 가장 간단하다.

프로세서를 요청하는 순서대로 프로세서를 할당해준다. 이때 구현은 Queue로 하며 FIFO 형태를 이룬다.


장점

스케줄링의 구현이 쉽다.

Ready Queue에 있는 모든 프로세스가 실행될 수 있으므로 Starvation이 없다.

프로세서가 지속적으로 프로세스를 처리하므로 처리율이 높다.


단점

비선점식이라 대화식 프로세스에는 부적합하다.

장기 실행 프로세스가 단기 실행 프로세스를 모두 지연시켜 평균 대기시간이 길어지게 된다.(최악의 대기시간)


프로세스 

도착 시간

실행 시간 

P1

0

10

P2

1

20

P3

2

25

P4

3

14

P5

4

18


이 상황에서는 아래 그림으로 다음과 같이 나타낼 수 있다.


대기 시간

P1 :: 0

P2 :: 10 - 1 = 9

P3 :: 30 - 2 = 28

P4 :: 55 - 3 = 52

P5 :: 69 - 4 = 65


평균 대기시간 = (0 + 9 + 28 + 52 + 65) / 5 = 30.8


반환 시간

P1 :: 10 - 0 = 10

P2 :: 30 - 1= 29

P3 :: 55 - 2 = 53

P4 :: 69 - 3 = 66

P5 :: 87 - 4 = 83


평균 반환시간 :: (10 + 29 + 53 + 66 + 83) / 5 = 48.2



최소작업 우선 스케줄링(SJF, Shortest Job First)


최소작업 우선 스케줄링은 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능 할 때 실행시간이 가장 짧은 프로세스부터 자원을 할당해주는 방식이다.


즉 위의 FCFS의 방법과는 같지만 실행 시간이 작은 순서대로 우선순위 큐를 이용한다고 생각하면 된다.

(우선순위 큐 스케줄링은 따로 있다. SJF는 특이한 상황의 우선순위 큐 스케줄링이라 보면 된다.)



장점

항상 실행 시간이 짧은 작업을 가장 먼저 실행하므로 평균 대기시간이 가장 짧다


단점

초기의 긴 작업이 짧은 작업들이 끝날 때까지 기다려야하기에 Starvation 현상이 일어난다.

기본적으로 짧은 작업이 항상 먼저 시작되기에 불공평하다.

실행시간을 예측하기 어렵다.



프로세스 

도착 시간

실행 시간 

P1

0

10

P2

1

20

P3

2

25

P4

3

14

P5

4

18


대기 시간

P1 :: 0

P2 :: 42 - 1 = 41

P3 :: 62 - 2 = 60

P4 :: 10 - 3 = 7

P5 :: 24 - 4 = 20


평균 대기시간 = (0 + 41 + 60 + 7 + 20) / 5 = 25


반환 시간

P1 :: 10 - 0 = 10

P2 :: 62 - 1= 61

P3 :: 87 - 2 = 85

P4 :: 24 - 3 = 21

P5 :: 42 - 4 = 38


평균 반환시간 :: (10 + 61 + 85 + 21 + 38) / 5 = 43



HRN 스케줄링


SJF 방식에서 짧은 실행시간을 가진 것들만 프로세서를 차지하는 것을 어느정도 보완하고자 만들었다.

대기 시간과 실행 시간을 혼합하여 어느 작업을 CPU를 사용할 지 결정하는 방법이다.


이때 실행시간이 분모이므로 실행시간이 낮을수록 우선순위를 높게 받는다.


그리고 대기시간이 길수록 우선순위가 높아진다.


장점

자원을 효율적으로 활용할 수 있다.

Starvation 상태가 발생하지 않는다.


단점

잦은 context switching으로 인해 오버헤드가 높을 수 있다.



비선점  & 선점 방법


우선순위 스케줄링(Priority)


우선순위 스케줄링은 프로세스가 Ready Queue에 도착하면 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서(CPU)를 할당하는 방식이다.


장점

각 프로세스의 상대적 중요도를 명시 할 수 있다.

실시간 시스템에 유리하다


단점

높은 우선순위 프로세스가 계속 오면 우선순위가 낮은 프로세스는 Starvation 현상을 겪을 수 있다.



우선순위 정하는 방법


우선순위(P)는 프로세서 버스트 시간의 역이다. 즉, P = 1/τ이다.

이때 프로세서 버스트 시간이라는 것은 프로세스 실행 시간과 동치이다.

즉, 실행 시간이 클수록 우선순위가 낮게된다.

'

우선순위는 외부, 내부적으로 정의도 가능하다. 


내부적 우선순위로는 제한시간, 사용파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트 비율 등등이 있고

외부적 우선순위로는 프로세스의 중요성, 사용료를 많이 낸 사용자, 정책적인 요인 등등이 있다.


우선순위 스케줄링은 선점 또는 비선점 방식이 가능한데 


선점 우선순위 스케줄링은 새로 도착한 프로세스의 우선순위가 현재 실행중인 프로세스의 우선순위보다 높으면 프로세서(CPU)를 획득한다.


비선점 우선순위 스케줄링은 실행중인 것과 무관하게 우선순위가 높다면 큐의 제일 앞에 넣어준다.


프로세스 

도착 시간

실행 시간 

 우선순위

P1

0

10

 3

P2

1

28

 2

P3

2

6

 4

P4

3

14

 1

P5

4

14

 2



대기 시간

P1 :: 8 - 0 - 2 = 6

P2 :: 16 - 1 = 15

P3 :: 2 - 2 = 0

P4 :: 58 - 3 = 55

P5 :: 44 - 4 = 40


평균 대기시간 = (6 + 15 + 0 + 55 + 40) / 5 = 23.2


반환 시간

P1 :: 16 - 0 = 16

P2 :: 44 - 1= 43

P3 :: 8 - 2 = 6

P4 :: 62 - 3 = 59

P5 :: 58 - 4 = 54


평균 반환시간 :: (16 + 43 + 6 + 59 + 54) / 5 = 35.6




대기 시간

P1 :: 0

P2 :: 16 - 1 = 15

P3 :: 10 - 2 = 8

P4 :: 58 - 3 = 55

P5 :: 44 - 4 = 40


평균 대기시간 = (0 + 15 + 8 + 55 + 40) / 5 = 23.6


반환 시간

P1 :: 10 - 0 = 10

P2 :: 44 - 1= 43

P3 :: 16 - 2 = 14

P4 :: 62 - 3 = 59

P5 :: 58 - 4 = 54


평균 반환시간 :: (10 + 43 + 14 + 59 + 54) / 5 = 36


에이징


우선순위 스케줄링 알고리즘에서 가장 큰 허점은 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스가 계속 들어오면 영원히 스케줄러에 선택받지 못하게 된다. 즉, 기아 상태(Starvation)가 된다.


따라서 에이징이라는 기법을 이용하여 오래 대기하는 프로세스가 우선순위를 점진적으로 증가시켜주는 방법을 이용한다.




선점형 스케줄링


라운드 로빈 스케줄링(Round Robin)


라운드 로빈 스케줄링은 프로세스가 프로세서에서 동작할 수 있는 시간을 할당해준다.


이때 라운드 로빈 큐는 원형 큐로 설계되어있어 프로세스가 시간을 다 쓰면 OS가 인터럽트를 걸어 현재 PCB가 큐의 가장 뒤로 가는 방식이다.


장점

모든 프로세스가 공정하게 시간을 할당받기에 starvation이 발생하지 않는다.

프로세스의 최악의 응답시간을 아는데 용이하다


단점

하드웨어 타이머가 필요하다

작업 시간 할당을 너무 짧게 하면 Context Switching이 자주 일어나 오버헤드가 일어난다.



프로세스 

도착 시간

실행 시간 

P1

0

10

P2

1

28

P3

2

6

P4

3

4

P5

4

14



CPU 점유 시간을 5로 제한했을 때


대기 시간

P1 :: 24 - 5*1 - 0 = 19

P2 :: 49 - 5*3 - 1 = 33

P3 :: 34 - 5-1 - 2 = 27

P4 :: 15 - 5*0 - 3 = 12

P5 :: 45 - 5*2 - 4 = 31


평균 대기시간 = (19 + 33 + 27 + 12 + 31) / 5 = 24.4


반환 시간

P1 :: 29 - 0 = 29

P2 :: 62 - 1= 61

P3 :: 35 - 2 = 33

P4 :: 19 - 3 = 16

P5 :: 49 - 4 = 45


평균 반환시간 :: (29 + 61 + 33 + 16 + 45) / 5 = 36.8





다단계 큐 스케줄링(MLQ, MultiLevel Queue)



다단계 큐 스케줄링은 준비 상태 큐를 여러 종류별, 단계별로 분할해두고 자신만의 독자적인 스케줄링 구현이 가능하다.

(즉, 시스템 프로세스는 우선순위 큐로, 학생 프로세스는 round-robin으로 등등..)


각 큐는 절대적인 우선순위를 가지며(여기선 시스템 프로세스가 우선순위가 가장 높다) 우선순위 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행 할 수 없다.


장점

응답이 빠르다.


단점

여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드가 발생

우선순위가 낮은 큐의 프로세스는 Starvation 현상이 일어 날 수 있다.




다단계 피드백 큐 스케줄링(MLFQ, MultiLevel Feedback Queue)



다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링에서 계속해서 프로세서를 선점하지 못하는 프로세스에 대해 큐의 이동을 시켜주는 방식을 이용한다.

즉, 다단계 큐 방식에서 오래 대기한 프로세스가 높은 레벨의 대기 큐로 이동한다.

혹은 프로세서 버스트 시간이 짧은 프로세스에 높은 우선순위를 주어 일직 종료시키거나 시간이 너무 오래 걸리면 낮은 우선순위로 변경시킨다.



장점

매우 유연하여 스케줄러를 특정 시스템에 맞게 구현 가능하다.

자동으로 입출력 중심, 프로세서 중심 프로세스를 구분한다.

적응성이 높아 프로세스의 사전 정보 없이도 최소작업 우선 스케줄링의 효과를 보여준다.


단점

설계와 구현이 매우 복잡하다.



짚고 넘어가기


1. 스케쥴링의 목적은 I/O 대기, Memory stall처럼 CPU 유휴 시간을 최소화 시켜 CPU 자원 활용을 극대화 하기 위함이다.

*memory stall : 프로세서가 메모리에 접근할 때, 데이터가 사용 가능할 때까지 많은 시간이 소모된다.* (EX : 컨텍스트 스위칭)


2. CPU 스케줄링실제 대상은 커널 스레드이다.(우리는 항상 프로세스라고 배웠지만 실제로는 프로세스를 담당하는 커널 스레드이다.) (참고 : http://drayong.tistory.com/13)


3. 우선순위 스케줄링 알고리즘에서는 에이징을 이용하여 Starvation을 방지하고, 우선순위 스케줄링은 선점, 비선점이 존재한다.

-> Priority 스케줄링 알고리즘은 우선순위 스케줄링은 선점 또는 비선점 방식이 가능한데 

선점 우선순위 스케줄링은 새로 도착한 프로세스의 우선순위가 현재 실행중인 프로세스의 우선순위보다 높으면 프로세서(CPU)를 획득한다. 

비선점 우선순위 스케줄링은 실행중인 것과 무관하게 우선순위가 높다면 큐의 제일 앞에 넣어준다.




이 게시물의 전체적인 내용은 그림으로 배우는 구조와 원리 운영체제를 기반으로 작성했습니다.

문제가 된다면 삭제 조치 하겠습니다.


 링크 : https://book.naver.com/bookdb/book_detail.nhn?bid=10786045







반응형