[OS/운영체제] CPU scheduling

1. CPU scheduling이란?

• CPU는 한번에 하나의 프로세스만을 수행할 수 있다. 여러개의 프로세스가 있어도 현재 CPU가 실행하고 있는 프로세스가 끝날때 까지 기다려야한다. 또한 I/O요청이 들어올 경우 CPU는 들어온 I/O요청이 끝날 때 까지 기다린 후 I/O가 끝나면 다시 실행된다. 즉, 다른 프로세스들을 실행하지 못하고 무한 대기하고 있기 때문에 대시 시간만큼 CPU를 낭비하는 것이다.
• 이를 해결하기 위해 멀티 프로그래밍 환경에서 CPU를 효율적으로 사용하기 위해 I/O요청이 오면 다른 프로세스한테 CPU를 양도하고 I/O가 끝나면 다시 Ready-queue에 들어가서 실행을 준비하고 실행하고 이런 CPU를 효율적으로 사용하기 위한 방법을 Scheduling이라고 한다.

2. CPU I/O burst cycle

 

그림1

위의 그림 1을 보면 CPU burst와 I/O burst가 번갈아가며 나온다. 즉 기본적인 연산을 할 때를 CPU brust time이라고 하고 이때 하는 기본적인 연산은 CPU를 사용한다. 그 다음 I/O요청이 들어오게 되면 interrupt로 인해 CPU에서 실행중인 프로세스는 waiting 상태에 빠지고 이때 CPU burst에서 I/O burst로 전환된다. 이때는 CPU가 하던 연산을 멈추고 I/O 요청이 끝날 때 까지 대기한다.

잠시 burst에 대해 정리하고 가자면

CPU burst (time) / CPU bound: CPU가 연산을 하는 시간 (running 상태)

I/O burst (time) / I/O bound : 입출력을 하고 대기하는 시간 (waiting or ready 상태) - ex) Input : 파일을 읽어오거나 키보드 입력을 받는것 // Output : 파일에 쓰거나 화면에 출력하는 것.

이렇게 정리할 수 있다.

그림2

그림 2를 보면 처음에 frequency(빈도)가 높은 그래프 축이 I/O burst time의 빈도가 높은 프로세스의 수이고 왼쪽 부분이 CPU burst time의 빈도가 높은 프로세스의 수이다. 이 히스토그램을 통해 대부분의 프로세스는 CPU를 사용해서 연산을 하는 시간보다 I/O로 인해 대기를 하는 시간이 많다는 것을 볼 수 있다.

그렇기 때문에 우리는 time-sharing을 사용한 스케줄링을 해서 I/O요청을 대기하는 시간에 context switching을 통해 다른 프로세스를 실행하다가 I/O요청이 완료되면 다시 queue에 넣고 ready-excute하는 것 처럼 I/O를 무작정 대기하지 않아도 되기 때문에 CPU효율을 올릴 수 있다.

3. Dispatcher & CPU scheduler 

그래서 이번에 알아 볼 CPU scheduler문제는 CPU가 I/O요청을 기다릴 때(idel) ready-queue에서 실행을 기다리고 있는 프로세스들을 어떤 기준으로 선택해서 실행 할 건지 고르는게 CPU scheduler다. 여기엔 여러가지 방법이 있고, 이 방법에 대해 중점적으로 알아 볼 것이다.

 

위에서 본 CPU scheduler가 프로세스들을 어떤 기준에 따라서 context-switch할지 정하면 실질적으로 context switching을 시키는 애가 Dispatcher다.

Dispatcher의 기능은

4. Non-Preemptive(비 선점형) VS Preemptive(선점형)

Non-Preemptive / 비 선점형

- CPU가 실행하고 있는 프로세스의 작업이 끝날 때 까지 다른 프로세스가 기다리는 것

- Non-preemptive한 경우

running상태에서 I/O를 만나 waiting 상태로 넘어갔을 때

process의 작업이 완료되어 terminate 상태가 됐을 때

Preemptive / 선점형

- CPU가 실행하고 있는 프로세스가 있어도 스케줄러가 현재 실행중인 프로세스를 다른 프로세스로 변경할 수 있음.

- Preemptive한 경우

running 상태에서 interrupt가 발생하여 ready상태가 됐을 때

waiting 상태에서 I/O가 완료되어 ready상태가 됐을 때

이때 우선순위, 프로세스를 처리하는 시간등에 따라 CPU를 넘겨줘서 preemptive하게 처리해 줄 수 있다.

5. 스케줄링에 대한 기준은?

1. CPU Utilization (CPU 사용률)

- 효율이 높은 CPU를 얼마나 쉬지않고 일을 시킬 수 있는지에 대한 척도이다. CPU Utilization에 초점을 맞추면 스케줄러는 CPU를 최대한 효율적으로 사용할 수 있도록 스케줄링 한다.

2. Throughput (처리량)

- 단위 시간당 완료된 작업의 갯수가 최대화 되도록 스케줄링 한다.

3. Turnaround time(총 처리시간)

프로세스가 실행부터 완료까지의 시간을 최소화 시켜 프로세스들이 빠르게 실행을 완료할 수 있도록 하는 방법이다.

총 처리시간을 줄이는데 초점을 맞춘 것!

* 총 처리시간 = ready-queue에서 대기한 시간 + CPU에서 실행하는 시간 + I/O대기 시간을 합친 것

4. Waiting time (대기 시간)

프로세스들이 ready-queue에서 대기한 시간들의 합을 최소화 시키는데 초점을 맞춘 방법

대기 시간을 줄이자!

5. Response time(응답 시간)

사용자들의 입력에 출력하는 간격, 즉 응답 시간을 최소화 시키는 데 초점을 맞춘 방법이다.

6. Priority (우선순위)

프로세스에 우선순위를 부여하고 우선순위가 높은 프로세스를 먼저 처리하는 방식

7. Fairness (공평성)

어떤 프로세스가 실행하지 못하고 기아 상태가 되는것을 방지하기 위해 모든 프로세스가 공평하게 CPU 자원을 할당 받을 수 있도록 스케줄링 하는 방법이다.

간단하게 요약해서 보면 이정도가 있다. 이제 위의 방법들을 자세하게 알고리즘적으로 나타낸 방법들을 살펴보자

 

1. FCFS (First-Come First-Served)

말 그대로 먼저 CPU를 점유한 프로세스가 먼저 처리되는 방식이다.

구현도 그냥 FIFO queue를 사용해서 완료되면 나가고 완료되면 나가고 하면 된다.

Process	Burst Time
P1	24
P2	3
P3	3

 

프로세스들이 위와 같은 순서대로 들어온다고 가정했을 때
waiting time을 계산해보자
P1:0 // P2 : 24 // P3:27
Total Waiting Time : 0 + 24 + 27 = 51
Everage Waithing Time : 51 / 3 = 17
하지만 프로세스들이 반대로 P3, P2, P1순서대로 들어오게되면 
 P3:0 // P2 : 3 // P1:6
Total Waiting Time : 0 + 3 + 6 = 9
Everage Waithing Time : 9 / 3 = 3

Turnarround Time을 계산해보자
P1 > P2 > P3 순서
P1:24 // P2 : 27 // P3 : 30
Total Turnarround Time : 24 + 27 + 30 = 81
Everage Turnarround Time  : 81 / 3 = 27

P3 > P2 > P1 순서
P1:3 // P2 : 6 // P3:30
Total Turnarround Time : 3 + 6 + 30 = 39
Everage Turnarround Time : 39 / 3 = 13

즉 FCFS방식에서는 얼만큼의 실행시간을 가진 프로세스가 어떤 순서대로 들어오는지가 Waiting time에 중요한 영향을 미치게 된다. > 실행시간이 긴, I/O 연산이 많은 프로세스가 먼저 들어올 경우 효율이 훨씬 떨어진다. (Convoy Effect)
그래서 FCFS방식은 비선점형이다.

2. SJF(Shortest Job First)

말 그대로 가장 짧은 시간을 가진 프로세스에게 CPU를 먼저 할당해주는 방식이다. 하지만 프로세스의 Burst Time을 예측하는것이 쉽지 않은것이 단점이다. SJF는 Non-Preemptive한 방식이기 때문에 Arrival time이 늦은애가 더 짧은 실행시간을 가지고 있어도 멈추지 않고 실행을 계속한다.

그림 2번을 보면 실제로 실행중인 P3보다 실행시간이 짧은 P4가 들어왔음에도 비선점형이기 때문에 Context switching이 일어나지 않고 계속 실행되는 것을 볼 수 있다. 이를 보완한 모델이 아래의 SRTF 모델이다.

3. SRTF(Shortest Remaining Time First)

2번에서 본 SJF의 선점형 방식이 SRTF이다. SRTF는 현재 실행하고 있는 프로세스의 실행 중간에 더 짧은 Burst time을 가진 프로세스가 들어오면 context switching을 통해 Burst time이 짧은 프로세스를 먼저 실행한다. 

위의 그림을 보면 0초에 들어온 P1이 바로 실행되다가 1초가 지난 후 P1의 Burst time은 7로 변경됐고 7보다 더 작은 4초를 가진 P2가 들어오자마자 P2가 실행돼는 간트 차트를 볼 수 있다. 

waiting time을 계산해보자
P1: (10-1) // P2 : (1-1) // P3: (17-2) //  P4 : (5-3)
Total Waiting Time : 9 + 0 + 15 + 2 = 26
Everage Waithing Time : 26 / 4 = 6.5

만약 위의 간트 차트로 Non-preemptive일때
waiting time을 계산해보자
P1: (0) // P2 : (8-1) // P3: (17-2) //  P4 : (12-3)
Total Waiting Time : 0 + 7 + 15 + 9 = 31
Everage Waithing Time : 31 / 4 = 7.75

4. RR(Round-Robin)

라운드 로빈 스케줄링은 time quantum, time slice라고도 하는 로세스마다 CPU의 자원을 사용할 수 있는 제한시간을 둬서 시간이 지나면 바로 다음 프로세스로 context switching하는 방법이다. 할당된 Time quantum을 다 소비한 프로세스는 인터럽트를 통해 ready-queue로 가서 대기한다. 혹은 circular-queue로 구현가능하다. 라운드 로빈 알고리즘은 시간이 지나면 다른 프로세스가 CPU를 점유하기 때문에 Preemptive다

Process	Burst Time
P1	24
P2	3
P3	3

waiting time을 계산해보자
P1: (10-4) // P2 : 4 // P3: 7
Total Waiting Time : 6 + 4 + 7 = 17
Everage Waithing Time : 17 / 3 = 5.66

Turnarround Time을 계산해보자
P1 : 30 // P2 : 7 // P3 : 10
Total Turnarround Time : 30 + 7 + 10 = 47
Everage Turnarround Time  : 47 / 3 = 15.6
라운드 로빈은 time slicing을 치기때문에 처리량과 응답시간 SJF 측면에서는 훨씬 우수하다. 하지만 결과를 보면 Everage Waithing Time이 SJF보다 라운드 로빈에서 좀 더 길어진 것을 볼 수 있다. 그래서 라운드 로빈과 SJF를 섞어서 쓰기도 하는데, 그게 바로 6번에서 살펴 볼 Multi-Levle Queue다.

위 사진을 보면 Time quantum에 따라 context switch하는 횟수가 늘어나는 것을 볼 수 있다. context switch를 하게 되면 dispatch latency가 발생한다. 즉 Time quantum이 너무 길면 너무 오래잡고 반대로 짧으면 context switch가 빈번하게 일어나서 불필요한 자원낭비가 일어나기 때문에 적당한 Time quantum을 찾는게 중요하다.

5. Priority-based (우선순위)

Priority-based scheduling은 각 프로세스에 우선순위를 매겨 높은 우선순위를 가진 프로세스를 먼저 처리하는 방법이다. 사실 우리가 이전에 살펴본 SJF는 Priority scheduling의 Non-preemptive한 버전이다. 반대로 Preemptive한 버전은 SRTF이다.

우선순위 스케줄링에서 생각해야하는 문제는 Starvaion 즉 기아문제이다. 우선순위가 높은 프로세스들만 계속해서 들어오게 되면 우선순위가 낮은 프로세스들은 계속해서 ready-queue에서 대기만하게 된다. 그래서 이를 해결하는 방법이 aging이다. aging이란 기아 문제를 해결하기 위해 프로세스에 age를 매겨서 일정 시간이 지나면 age를 높여서 처리할 수 있게끔 하는 방법이다. 아무리 Burst time이 길어도 aging을 우선요소에 넣어서 처리할 수 있게 한다.

6. Multi-Level Queue

우선순위가 서로 다른 여러개의 queue를 만들어서 우선순위가 높은 queue에 들어있는 process들을 먼저 처리하는 방법이다. 아래 그림을 보면 실시간 프로세스부터 좀 우선순위가 낮은 배치프로세스까지 레벨을 나눠서 높은 우선순위를 가진 프로세스부터 처리한다.

위 모델에서의 문제점은 우선순위가 높은 큐가 비지 않으면 상대적으로 우선순위가 낮은 큐에 들어있는 프로세스들을 처리할 수 없다. 그래서 또 이 문제를 해결할 수 있는 모델을 아래에서 살펴보자

6. Multi-Level Feedback Queue(MLFQ)

이전에 봤던 모델에서는 우선순위에 따라 큐를 분리시킨 결과로 기아문제가 발생했다. Multi Level Queue에서 기아문제를 해결하는 방법이 Multi-Level Feedback queue방법이다. 아래의 그림을 참고하자

우선순위가 가장 높은 queue의 Time quantum을 8로 주고 여기서 작업을 완료하지 못한 프로세스는 다음 우선순위인 Time quantum이 16으로 설정된 큐로 간다. 여기서도 완료를 못하면 Time quantum을 더 늘려서 처리한다. 그림에서는 마지막은 FCFS로 그만큼 우선순위를 낮춘다는 의미로 사용한 것 같다. 또한 Aging을 사용해서 우선순위가 낮은 큐에서 기아 상태가 발생하면 우선순위를 높일수도 있다.

실제로 Solaris Os에서 사용하는 MLFQ에는 총 159개의 우선순위가 있다고 한다. 저 논문에 대한 요약은 처음 프로세스는 29번 우선순위로 등록된 후 입출력 연산, 대화형 프로세스들은 우선순위가 점점 낮게 책정되고 time slice를 전부 소비하기 전에 끝나면 우선순위가 높아진다는 내용이다. 궁금하면 링크를 들어가서 읽어보면 나름 MLFQ에 대해 이해가 될 것이다.

위의 캡처에 대한 출처는 아래의 paper에 있다.

 https://pages.cs.wisc.edu/~remzi/solaris-notes.pdf

 

사진 출처

https://velog.io/@seokjun0915/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐