[운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링

이전 글에서 간단하게 프로세스 스케줄링을 알아보았어요.

[운영체제 OS] - [OS/운영체제] Process Scheduling 프로세스 스케줄링

[OS/운영체제] Process Scheduling 프로세스 스케줄링

CPU burst 와 I/O burst

CPU 활용은 multiprogramming을 통해 성능을 향상시킬 수 있어요.

CPU burst는 CPU명령을 수행하는 것을 의미하고 I/O burst는 I/O를 요청한 후 기다리는 시간을 의미해요.

프로세스는 CPU burst와 I/O burst가 왔다갔다 하면서 프로그램을 실행합니다. 

즉, 프로세스는 CPU에서 명령어 수행하다가 I/O 기다리다가, I/O 작업이 끝나면 CPU의 남은 명령어를 수행하고...반복하는 것이죠.

 

그래서 CPU burst가 5초면 CPU 명령어 수행을 5초해야만 하고 그 후엔 I/O burst 입력받는 작업을 5초동안 수행해야 다시 CPU 명령어 수행 작업을 할 수 있어요.

 

프로세스는 CPU burst가 크면 CPU bound process라고 부르고, I/O burst가 크면 I/O bound process라고 부릅니다.

CPU bound process는 사용자가 관여하지 않는 프로세스겠죠.

Histogram of CPU-burst Times

사용자가 관여하지 않는 CPU bound 프로세스들의 CPU burst 시간을 잰 그래프입니다. 보이듯이 이렇게 짧습니다.

 

사실 프로세스의 대부분은 I/O bound process이랍니다.

 

 

nonpreemptive비선점 vs preemptive선점 스케줄링 

스케줄링은 Ready queue에서 프로세스를 고르고 Dispatch는 이를 CPU에 할당하는 것이에요.

Short-term scheduler가 이 작업을 수행해요.

 

비선점형 스케줄링은 프로세스가 terminate될 때까지 계속 CPU를 잡는(점유하는) 것이고, 종료terminate되거나 running을 대기상태(waiting or ready)로 전환해요. 굉장히 비효율적이죠....

선점형 스케줄링은 context switching을 발생시켜 현재 수행 프로세스가 언제든지 다른 프로세스로 교환이 가능해요. 왜냐하면 인터럽트가 언제든지 발생할 수 있어요. 그리고 shared data에 대한 접근을 허용해요. 중요한 커널코드는 lock으로 보호(interrupt 막기)할 수 있어요.

인터럽트 신호가 무엇인지에 대해선 이 게시글에서 자세히 다루었어요.

[운영체제 OS] - [운영체제/OS] 운영체제 Operating System는 무엇이고 하는 일은 무엇인가?

[운영체제/OS] 운영체제 Operating System는 무엇이고 하는 일은 무엇인가?

 

Dispatcher 모듈은 short-term scheduler가 스케줄링으로 선택된 프로세스를 CPU위에 올려놓는(할당하는) 작업을 해요. 

context switching과 user mode로 변환과 restart하기 위해 user프로그램을 적정위치에 다시 두는 작업을 해요.

Dispatch latency - dispatch 지연시간이며 dispatcher가 한 프로세스를 stop하고 다른 프로세스를 다시 runnng할 때까지 소요되는 시간을 의미해요.

 

Dispatch Latency

 

 

Scheduling Criteria

CPU 스케줄링은 효율성을 판단하는 기준이 어떻게 있을까요

 

#최대화해야 하는(효율성을 증가하는) 기준

-CPU utilization(CPU 사용률) : "CPU가 idle하지(쉬지) 않고, 얼마나 열심히 일하는가(busy한가)". 사용률이 높을수록 좋은 알고리즘이겠죠. CPU는 비싼 자원이기에 바쁘면 바쁠수록 좋습니다.

-Throughput: 단위시간(time unit)당 작업수행을 완료한 프로세스의 수(#)

즉, 단위시간당 처리하는 일의 양이죠. 이것 또한 다다익선입니다.

 

#최소화해야 하는 기준

-Turnaround time (총처리시간): 요청 받은 특정 프로세스를 수행하는데 걸리는 시간. 적으면 적을수록 좋겠죠?

-Waiting time(평균 대기시간) : 프로세스가 ready queue에서 running 상태가 될 때까지 기다려야하는 평균 시간. 여러 번 반복될 수 있으므로 평균! 시간입니다.

-Response time (응답시간) : Turnaround time과 비슷한데, 요청 후 첫 응답을 받을 때까지의 시간입니다.(output과는 다름) 

결과가 나오기 시작전까지만!의 시간입니다. 총 출력까지의 시간은 turnaround time입니다. 

 

스케줄링 알고리즘 비교를 위한 측정 요소는 평균 대기시간(Waiting time)을 주로 사용한답니다. 

물론 다른 요소들도 함께 고려합니다.

 

 

 

 

그렇다면 이제 대표적인 네 가지의 CPU 스케줄링 알고리즘들을 알아볼까요.

-선입 선처리 스케줄링(First-Come, First-Served : FCFS)

-최단 작업 우선 스케줄링(Shortest Job First: SJF)

-라운드 로빈 스케줄링(Round Robin Scheduling: RR)

-우선순위 스케줄링(Priority Scheduling) 

 

 

First-Come, First-Served 선입 선처리 스케줄링 : FCFS 스케줄링

최적화하긴 힘든 알고리즘이라 단순구현 때 용이해요.

자료구조 시간 때 배운 큐처럼 (FIFO) 먼저 큐에 도착한 애들 순서대로 수행되는 것이에요.

 

예를 들어 프로세스 P1, P2, P3가 순서대로 도착했어요.

 waiting time은 P1 = 0; P2 = 24; P3 = 27입니다.

Average waiting time은 (0 + 24 + 27) /3 = 17

 

순서를 바꿔보겠습니다. 다른 예로, 프로세스가 P2, P3, P1 순서대로 왔을 때

Waiting time은 P1 = 6; P2 = 0; P3 = 3입니다.

Average waiting time은 (6 + 0 + 3) / 3 = 3

훨씬 성능이 좋죠.

 

FCFS 스케줄링은 Non-preemptive 비선점형 프로세스 스케줄링입니다.

굉장히 비효율적이고 Convoy effect, 일종의 교통 체증 같은, 짧은 프로세스가 긴 프로세스 뒤에서 기다리느라 작업을 수행 못 하고 있는 현상입니다

Convoy effect

 

Shortest-Job-First 최단 작업 우선 스케줄링: SJF 스케줄링

CPU burst(남아있는 CPU수행시간) 가장 빠른대로 먼저 수행하는 알고리즘입니다.

비선점형 프로세스 스케줄링이라서 마찬가지로 양보를 하지 않습니다. (선점형 버전도 있는데 이는 참고로 shortest-remaining time first 알고리즘이라고 따로 있습니다.)

 

SJF 스케줄링은 다음 프로세스의 CPU burst 길이를 고려합니다. 

하지만 예측하는 건 어려우므로 최소의 평균대기시간을 스케줄링 차트로 만듭니다.

Average waiting time = ( 3 + 16 + 9 + 0 ) / 4 = 7

I/O 요청 명령어가 나와야 그 다음 CPU burst를 예측할 수 있는데, 다음 CPU 요청의 길이를 알긴 상당히 어렵습니다.

그래서 SJF는 이전 burst시간을 활용하여 다음 burst시간을 예측했어요.

다음 CPU는 이전 CPU burst들의 지수 평균을 가질 것이라고 생각하고 다음 공식을 씁니다.

위의 공식을 활용하면 다음과 같은 그래프가 나옵니다. tn은 n번째 CPU burst의 길이입니다. 

파란색이 예측 값이고 검은색이 실제 값입니다. 예측과 실제가 차이가 큰 결과가 나타나고, SJF는 FCFS와 마찬가지로 적합하지 않다고 판단되고 잘 쓰이지 않습니다. 

 

SJF의 선점형 스케줄링 버전인 Shortest-remaining-time-first 알고리즘도 알아볼게요.

 

프로세스 P1, P2, P3, P4는 Arrival time이 각 0,1,2,3, burst time이 각 8,4,9,5일 때, 

선점형이므로 프로세스 P1이 CPU를 계속 점유하고 있지 않고 다른 프로세스에게 양보합니다.

그래서 waiting time은 프로세스 순서대로

(10-1) + (1-1) + (17-2) + (5-3) 이고 이를 4로 나누어 평균대기시간은 6.5입니다.

 

 

 

 

 

Priority Scheduling 우선순위 스케줄링

 

그럼 이제 우선순위 스케줄링을 알아봅시다. 

개발자가 우선순위를 프로세스에게 부여하는 순서대로 스케줄링이 됩니다.

그렇다면 우선순위를 어떻게 부여하는지가 중요하겠죠?

 

우선순위 스케줄링에서 조심해야하는 부분은 Starvation 문제에요.

이는 우선순위 낮은 애가 계속 기다리고 있는 현상인데요.

실제로 MIT가 1973년에 IBM 7904를 폐쇄할 때, 1967년에 입력된 프로세스가 계속 대기중인 상태였다죠.........ㅋㅋ

 

이를 위한 해결책으론 Aging입니다. 프로세스의 나이가 들수록 우선순위를 올려주는 것인데, 이 간격은 개발자 설계 마음입니다.

 

 

우선순위 스케줄링은 자기 정해진 기준대로 설계하는 것인데 예시를 보겠습니다.

Average waiting time은 P2, P5, P1, P3, P4 순서대로 (0 + 1 + 6 + 16 + 18 ) / 5 = 8.2 입니다.

 

 

 

Round Robin Scheduling 라운드 로빈 스케줄링 : RR Scheduling

공평하게 프로세스들이 돌아가면서 수행하는 알고리즘입니다.

각 프로세스들이 작은 CPU 단위 시간(time quantum)을 부여 받아 비선점형으로 ready queue에서 기다리게 됩니다.

 

time quantum을 길게 주면 FIFO와 비슷하고

time quantum이 짧아질수록 context switch가 늘어나요. 너무 많이 늘어나면 오버헤드가 발생되서 안 좋아요.

일반적으론, 80%의 프로세스들이 time quantum보단 짧아야 해요. (20%만 context switching되도록) 

 

time quantum이 4인 라운드 로빈 스케줄링의 예시입니다.

 

정리하자면, time quantum은 context switching시간에 비해 커야 합니다.

Turnaround time(총처리 시간)은 time quantum에 영향을 받습니다. 

time quantum이 6이나 7이라면, 평균 총처리 시간은 10.5입니다.

하지만 time quantum이 1이라면, 평균 총처리 시간은 11.0입니다. 

 

 

 

 

보통 일반적으로 라운드로빈 스케줄링을 우선순위 스케줄링과 섞어서 활용합니다.

Priority with RR Scheduling 

 

여기까지 네 가지 스케줄링 알고리즘을 알아보았고요.

다음엔 Multilevel Queue 와 Multilevel Feedback Queue 스케줄링을 알아볼게요.