Process Scheduling Algorithm(프로세스 스케줄링 알고리즘)

 

 

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

---

운영체제는 프로세스 스케줄링을 통해 어떤 프로세스에 CPU를 할당할 것인지를 결정한다.

Preemptive vs Non-preemptive

• Preemptive 방식
  • CPU 점유를 빼앗을 수 있는 방식이다.
  • 프로세스 P1이 CPU를 할당받아 실행중일 때 우선순위가 높은 프로세스 P2가 등장하여 CPU를 요청하면 P1의 CPU를 뺏어서 P2에게 할당하는 방식이다.
• Non-preemptive 방식
  • CPU 점유를 빼앗을 수 없는 방식이다.
  • 프로세스가 한번 CPU를 할당 받아 실행하면 실행이 끝날 때 까지 다른 프로세스에게 CPU를 넘겨주지 않는 방식이다.
    • 스스로의 할당 해제(I/O 작업 등)의 경우에만 CPU 할당 해제가 발생한다.

 

 

• 이후 언급될 스케줄링 기법들을 Turn-around Time(Waiting Time + Burst Time)을 기준으로 분석하였다.

 

각 Process의 정보는 아래 표와 같다.

 

 

FCFS(First Come First Served) 스케줄링

---

 

Ready Queue에 도착한 순서대로 CPU를 할당하는 방식

• Non-preemptive(비선점) 스케줄링이다.

Average Turn-around Time : ((0+3)+(1+6)+(5+4)+(7+5)+(10+2))/5 = 43/5

장점

• Starvation 이 발생하지 않는다.

단점

• 평균 대기시간(Average Waiting Time)이 길어질 수 있다.
• 응답 시간(Response Time)이 길어질 수 있다.
• convoy effect : 시간이 많이 필요한 작업이 먼저 수행되어서 나중에 도착한 시간이 빨리 끝나는 작업이 수행되지 못하는 것

 

 

Round Robin(RR) 스케줄링

---

 

각 프로세스에 동일한 CPU 할당 시간(time quantum)을 부여하고, 할당 시간이 경과되면 CPU를 회수해 Ready Queue에 있는 다음 프로세스에게 CPU를 할당하는 방식

• preemptive(선점) 방식이다.

Average Turn-around Time : ((1+3)+(10+6)+(9+4)+(9+5)+(5+2))/5 = 54/5

장점

• Response Time 이 빠르다.

단점

• time quantum 이 너무 짧으면 Context Switching이 자주 발생해 Overhead가 증가한다.
• time quantum 이 너무 길면 FCFS 와 같은 결과를 얻게 된다.

 

 

SJF(Shortest Job First) 스케줄링

---

burst time(남은 실행 시간, 예측된 값)이 짧은 프로세스부터 먼저 CPU를 할당하는 방식

• preemptive / non-preemptive 방식으로 나누어진다.

 

SPN(Shortest Process Next) 스케줄링

---

burst time 이 더 짧은 프로세스가 등장해도 실행하던 프로세스는 CPU를 반납하지 않는다.

• SJF의 Non-preemptive 방식이다.

Average Turn-around Time : ((0+3)+(1+6)+(7+4)+(9+5)+(1+2))/5 = 38/5

 

 

SRTF(Shortest Remaining Time First 또는 SRT) 스케줄링

---

burst time이 더 짧은 프로세스로 교체한다.

• SJF의 preemptive 방식이다.

Average Turn-around Time : ((0+3)+(7+6)+(0+4)+(9+5)+(0+2))/5 = 36/5

장점

• Optimal(최적)의 알고리즘이다.
• 더 짧은 Turn-around Time 은 불가능하다.

단점

• 비현실적이다.
  • burst time을 정확하게 예측하는 것은 불가능하다.
  • 예측하는 과정에서 overhead가 발생한다.
• starvation(기아 현상) 이 발생할 수 있다.
  • 최악의 경우에 burst time 이 긴 프로세스는 Ready Queue 에서 영원히 기다리게 된다.

 

 

HRRN(Highest Response Ratio Next) 스케줄링

---

프로세스가 끝나면 Ratio 값을 계산하고, Ratio 값이 큰 프로세스를 실행하는 방식이다.

Ratio : Burst time 대비 얼마나 기다렸는 지를 나타낸다.

• Non-preemptive 방식이다.

Average Turn-around Time : ((0+3)+(1+6)+(5+4)+(9+5)+(5+2))/5 = 40/5

장점

• Starvation이 발생하지 않는다. - Aging 기법 사용
  • Aging 기법 : 프로세스의 대기 시간이 길수록 우선순위를 높여주는 방식

단점

• burst time을 정확하게 예측할 수 없다.
• 예측하는 과정에서 Overhead가 발생한다.
• 최고의 성능을 보장하지 않는다.

 

 

MFQ(Multilevel Feedback QueueMFQ) 스케줄링

---

실행시간을 예측하지 않고, 실행시간이 짧은 것에 우선순위를 주는 방식이다.

• 실행시간이 긴 process에게 패널티를 주어 예측하지 않고 우선순위를 부여할 수 있다.

• preemptive 방식이다.

작동 방식

• N 개의 Ready Queue가 존재한다.
• 새로운 Process는 0번 Ready Queue에 추가된다.
• 0번 부터 작업을 시작하고, n번 큐까지 비어있을 때 N+1 번 큐의 작업을 시작한다.
• time quantum을 모두 사용한 Process는 다음 Ready Queue(N+1 번 큐) 로 넘어가게 된다.
• time quantum q는 해당 큐의 순위에 따라 다르다.(ex. n 번째 큐 : q = 2^N )

time quantum을 다르게 설정한 이유?
- 아래 큐로 밀려날수록 CPU를 점유할 확률이 낮다.
- 따라서, 긴 time quantum을 주어 한번 CPU를 점유 할 시 최대한 완료할 수 있게 구성한다.

장점

• burst time을 예측하지 않고 비슷한 효과를 낼 수 있다.
  • 예측에 필요한 overhead를 절약할 수 있다.

단점

• 설계 및 구현 과정에서 overhead가 발생한다.
• 여전히 starvation을 완벽하게 해결하지 못한다.

•  

 

 

추가 질문

---

Q. RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

• time quantum 이 너무 짧으면 Context Switching이 자주 발생해 Overhead가 증가한다.
• time quantum 이 너무 길면 response time 이 길어진다.

 

Q. 동시성과 병렬성의 차이에 대해 설명해 주세요.

동시성

• 하나의 코어로 빠르게 전환하며 여러 작업을 수행하는 것
• 여러 작업이 동시에 실행되는 것처럼 보인다.

병렬성

• 실제로 여러 코어로 여러 작업을 동시에 수행하는 것