[ 운영체제 ] CPU Scheduling (2)

 

1. 우선순위 알고리즘 [ Priority Scheduling Algorithm ]

 

알고리즘은 높은 우선순위에 있는 [ = 적은 숫자를 가지고 있는 ] 프로세스에게 CPU를 할당시킨다.

=> SJF도 우선순위 알고리즘의 종류 중 하나이다.

 

장점

대기 시간이 지남에 따라, 프로세스의 우선순위를 높임으로써 "Aging" 문제를 해결 할 수 있다.

 

단점

낮은 우선순위의 프로세스는 절대 실행 될 수 없다. [ Starvation ]

 

2. 라운드로빈 알고리즘 [ Round Robin Scheduling Algorithm ]

 

- RR 알고리즘은 FCFS 알고리즘과 유사하지만[Ready queue], 각 프로세스가 작동 될 수 있는 시간인 Time qunantum이라는 개념을 도입한 알고리즘이다.

 

- 프로세스의 개수를 N , 타임 퀀텀을 Q라고 가정한다면 하나의 프로세스는 (N-1) * Q이상의 시간이 지나면 자동으로 Context switching 된다.

 

- 타임퀀텀이 클 경우 FCFS 알고리즘과 같아지게 된다.

 

3) Multilevel Queue Scheduling

분리된 여러개의 Ready Queue로 구성 되어있다.

각 프로세스는 특정한 큐에 영구적으로 할당되고 다른 큐로 이동이 불가능하다.

 

예시 1) Fixed Priority ( 각 레디 큐의 우선순위는 고정 )

Real-time > System > Interactive > Batch

 

예시 2) Time Slice

높은 우선순위에 있는 프로세스에게 더 많은 CPU TIME을 제공한다.

 

3-1 ) Multilevel Feedback Queue

- 일반적인 멀티 큐 알고리즘과는 다르게 프로세스가 큐를 이동 할 수 있도록 한다.

CPU Burst time에 따라 프로세스를 나누고[많으면 낮 / 적으면 높 ], 대기 시간이 길어지면 높은 순위로 이동

=> Starvation 문제를 해결

 

구체적 예시)

Q0 에 들어왔던 작업이 8초 안에 작업을 마치지 못하면 -> Q1으로 이동

Q1으로 이동된 작업이 16초(주어진 시간 ) 내에 작업을 X -> Q2로 이동

Q2에서는 FCFS의 방식으로 먼저 온 작업을 우선적으로 처리해주지만, Starvation 방지를 위해 대기를 오래 한 작업은 우선순위 큐로 이동시켜준다.

 

3-2 ) Multi-Processor Queue

1) SMP vs AMP

S) 각각의 프로세서들이 자신의 스케줄링 알고리즘을 가지고 있다.

A ) 하나의 프로세서가 나머지 프로세서의 데이터 구조등을 평가 &정의한다.

 

* Loading Sharing on SMP system

각각의 프로세스들은 균등하게 작업을 분배 받는다.

 

3-3) Real-Time scheduling

 

1) Hard : 주어진 시간 내에 반드시 중요한 작업들을 완료 시키기 위해 요구되는 알고리즘

2) Soft : 운이 없는 작업보다 더 높은 우선순위를 요구하는 작업들을 요구하는 알고리즘