Ⅳ CPU 스케줄링

Part 02 프로세스 관리

Chapter 04 CPU 스케줄링

1. 스케줄링의 개요

① 스케줄링의 개념

스케줄링이라고 하는 것은 READY 상태에 있는 프로그램 중 누군가를 골라서 스케줄러에게 주는 것을 의미한다. 한 줄로 서있으므로 맨 앞에 있는 것을 골라주면 될 것 같지만, 그렇게 간단하지 않다. READY 상태의 운영체제 관련된 프로세스도 프로세스이고, 일반 프로세스도 프로세스다. 일반 프로세스와 OS의 프로세스 2개가 같이 있을 경우, 운영체제의 프로세스부터 CPU에 줘야 한다. 운영체제가 해야할 작업을 못하게 되면 먼저 들어간 프로세스가 아무 메모리나 돌아다니면서 장난치거나, 시스템을 공격하는 것을 막을 방법이 없기 때문이다. 그러면, 시간을 얼만큼 줘야 하는지의 문제가 있을 수 있다. 예를 들어, 우리가 고급 레스토랑에 갔을 때, 매니저가 있다. 매니저가 하는 일을 OS에서는 CPU 스케줄러라는 친구가 하고 있다. 이 매니저가 하는 일 중에, 상황을 봤더니 원래 1번 테이블의 손님이 먼저 오고 2번 테이블의 손님이 나중에 왔는데, 1번은 엄청 천천히 먹고 있고, 2번 테이블은 허겁지겁 먹고 있다. 이때, 2번 테이블 메뉴를 먼저 준비하도록 주방에 알려주는 역할을 하는 것이 CPU 스케줄러다. 즉, 어떻게 CPU에게 프로세스 전달을 해서 작업을 시킬 것인가 하는 것을 결정하는 역할을 하는 게 CPU 스케줄러다.

 

② CPU 스케줄링

CPU 스케줄링은 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.

- 고수준 스케줄링: 테이블이 30개인데 예약 손님 300명을 받을 수 없다. 전체 상황을 보고 결정하는 것.

- 저수준 스케줄링: 실제 누구를 실행할 것인가 (ex.대기줄에 있는 손님들 중에서 VIP 가 있는 경우)

- 중간수준 스케줄링: 직접 실행할 수 있는 READY 상태를 결정하는 것. 저수준 스케줄링이 원만하게 이루어지도록 완충하는 Buffer 역할을 한다.

 

 

③ 스케줄링의 목적

CPU 스케줄링의 원래 목적은 모든 프로세스가 공평하게 작업하도록 하는 것이다. 특정 프로세스에 편중되지 않도록 골고루 자원을 배분하기 위해 공평성을 유지하면서도 안정적으로 작동해야 한다. 즉, 특정 프로세스가 시스템 자원을 독점하거나 파괴하는 것을 막기 위해 중요도에 따라 우선순위를 배정해야 한다. 또한 시스템 자원을 효율적으로 배분하여 전체적인 시스템의 성능을 높여야 한다. 더불어 확장성도 고려해야 한다. 확장성은 프로세스의 개수가 증가해도 성능에 갑작스러운 변화가 없어야 함을 의미한다. 정리하면, CPU 스케줄링의 목적은 공평성, 효율성, 안정성, 확장성, 반응 시간 보장, (프로세스 작업) 무한 연기 방지에 있다.

 

 

 

2. 스케줄링 시 고려 사항

① 선점형 스케줄링과 비선점형 스케줄링 (p.203~204)

- 선점형 스케줄링 Preemptive Scheduling : 뺏을 수 있는 스케줄링

- 비선점형 스케줄링 Non-Preemptive Scheduling : 뺏을 수 없는 스케줄링

 

내가 작업이 끝날 때까지 쫓겨나지 않는 것 ‘비선점형 스케줄링’

시간이 되면 내가 쫓겨날 수 있는 것 ‘선점형 스케줄링’

 

오늘의 중요한 내용에 해당한다. 표로 정리하면 다음과 같다.

 

 

 

 

② 프로세스 우선순위

프로세스는 항상 우선순위가 있다. (p.205) OS프로세스의 우선순위가 일반 프로세스의 우선순위보다 훨씬 높다. 비디오 플레이어의 우선순위 설정칸에 ‘높음’으로 되어 있다. 비디오 플레이어는 실시간으로 돌아야 하기 때문에 우선순위를 높게 만들어놨다. 그래서 비디오 플레이어를 돌리면 다른 프로세스들은 조금씩 느리게 돌 수밖에 없다. 비디오 플레이어 우선순위를 낮음으로 바꾸면 느리게 돌고, 비디오가 끊겨서 보인다. 우선순위가 높은 프로세스가 먼저 실행되고, 더 빨리 실행된다. 그럼, 우선순위가 낮은 애들은 느리게 실행되고 끊겨 보이기도 한다.

 

 

③ CPU 집중 프로세스와 입출력 집중 프로세스 (p.206)

입출력을 많이 쓰는 CPU, 수학적 계산을 많이 하는 CPU가 있다. CPU를 가장 많이 차지하는 프로세스를 CPU Bound Process, 입출력을 많이 사용하는 프로세스를 I/O Bound Process 라고 한다. I/O Bound Process 에게 우선순위를 주면 CPU를 잠깐 사용한 뒤, 대기상태로 빠진다. 그래서 다음 프로세스를 데려올 여유가 있다. 따라서 I/O Bound Process 에게 우선순위를 주는 것이 유리하다. 왜냐하면 대기상태로 빠져버리기 때문이다.

 

 

④ 전면 프로세스와 후면 프로세스

전면 프로세스는 맨 앞에 나와서 키보드와 마우스를 차지하고 있는 프로세스, 화면 뒤에서 돌아가는 프로세스를 후면 프로세스라고 한다. 우선순위를 정리해 보면, 커널 프로세스의 우선순위가 일반 프로세스보다 높을 거고, 전면 프로세스가 후면 프로세스보다 우선순위가 높을 것이다. Time Sharing을 사용하는 프로세스가 batched process 보다 우선순위가 높다. 그리고 IO 바운드 프로세스가 CPU 바운드 프로세스보다 우선순위가 높다. 이 정도까지만 이해하고 넘어가도록 하자.

 

 

⑤ 프로세스의 우선순위 정리

작업의 중요도가 높아 우선순위가 높은 프로세스는 커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 집중 프로세스다. 반대로 우선순위가 낮은 프로세스는 일반 프로세스, 후면 프로세스, 일괄 작업 프로세스, CPU 집중 프로세스다. 다음은 지금까지 설명한 CPU 스케줄링을 할 때 고려해야 할 사항을 정리한 것이다.

 

 

 

 

3. 다중 큐

① 우선순위 큐

많은 프로세스 중 우선순위가 높은 것을 찾아서 넘겨줘야 한다. 이것은 굉장히 불편하다. 그래서 우선순위별로 ‘큐’를 만들어서 링크드 리스트를 만들어 나간다. 즉, 한 줄로 서있는 것이 아니라 우선순위별로 서있는 것을 의미한다. C에서 맨날 하는 일은 스텝 구현과 큐 구현이다.

 

② 대기상태 (p.210)

IO가 끝나길 기다리는 상태가 대기상태, 그런데 그것도 중구난방으로 끊어 놓으면 불편하기 때문에 하드디스크를 기다리는 것, 네트워크를 기다리는 것 등으로 따로 구분한다. 프로세스의 상태도는 정확하게 5가지다. 다단계의 큐를 같이 넣어서 그려보면 그런 모양이 된다. (그림, 글) 읽어보면 쉽게 이해가 갈 것이다.

 

 

 

4. 스케줄링 알고리즘

 

스케줄링 알고리즘은 크게 3종류로 나뉘는데, 비선점형, 선점형, 우선순위 스케줄링 알고리즘이 있다. 어떤 알고리즘이 성능이 우수하고 우수하지 않은지를 판단하기 위한 기준으로서, CPU사용률, 처리량, 대기시간, 응답시간, 반환시간 등을 고려한다. 대기시간은 프로그램이 도착해서 실행하기까지 기다린 시간을 의미하며 응답시간은 CPU에 도착을 해서 첫 번째 답이 나오는 시간, 처리량은 처음 시작부터 끝날 때까지 걸린 시간을 의미한다. 또, 반환시간은 대기시간과 실행시간을 다 합친 것을 의미한다. 우리가 사용할 것은 ‘대기시간’이다. 대기시간은 도착을 해서 첫 번째 실행을 할 때까지 기다린 시간을 다 더해서 나누면 평균 대기시간이 되고, 각 알고리즘들의 성능들을 비교한다. 이제부터 CPU 스케줄링 알고리즘을 하나씩 천천히 살펴보도록 하자.

 

 

① 선점형 알고리즘[뺏을 수 있는 알고리즘] 선입선출 FCFS

batched system 뺏을 수 없는 시스템이므로 끝까지 종료한 뒤에 다음 프로세스가 작업할 수 있는 가장 오래된 방식이다. p1은 0초에 도착했고, 작업시간 30초, p2는 3초에 도착했고, 작업시간은 18초. 평균 대기시간을 계산해 보면(p.218) p0는 오자마자 실행을 하였으므로 대기시간이 0이다. p2는 3초에 도착했지만 p1의 작업이 끝날 때까지 기다렸다. 즉, p2의 대기시간은 27초, p3는 6초에 도착해서 48초에 작업을 시작했으므로 42초가 대기시간이 된다. 전부 더해서 3으로 나누면 평균 대기시간이 된다.  즉, 23초가 된다.

 

 

② 최단 작업 우선 SJF (Shortest Job First)

p2는 18, p3 9일 경우, p3가 먼저 실행된다. 평균 대기시간은 20초로 줄어든다. 작은 작업을 먼저 수행하게 되면 당연히 평균 대기시간이 줄어들게 된다.

그런데 이 방법은 쓸 수 없다.

원인1: 작업시간을 정확히 알 수 없다.

원인2: 설사 알 수 있다 치더라도 작업이 크게 밀리는 문제가 발생할 수 있다.

작업시간이 긴 프로세스가 무한히 뒤로 밀려버릴 가능성이 있는 것이다. 그러면, Starvation 아사 현상이 발생한다. 계속 뒤로 밀려서 굶어 죽는 것이다. Aging에 의해 한 번 양보할 때마다 카운트하고 5가 되면 더 이상 양보하지 않게 하는 방법도 있지만 ‘공평성’을 위배하므로 이러한 방식은 잘 사용되지 않는다. 작업이 길다는 이유만으로 무조건 뒤로 내칠 수는 없는 노릇이다.

 

 

③ HRN [비선점형 알고리즘]

우선순위를 정해서 프로세스를 실행한다. 대기시간과 수행시간을 모두 더해서 사용량을 나눠버린다. 대기를 길게 한 프로세스들이 먼저 실행이 되어서 똑같이 아사 현상이 발생한다. 그래서 이 방식도 어차피 사용하지 않는다. 문제는, 정보처리기사에 알고리즘에 관한 표가 나오고 이 알고리즘이 어떤 것인지 물어보는 문제가 나온 전적이 있으므로 일부러 넣어 놓았다. 여기까지 뺏을 수 있는 알고리즘이었고 지금부터는 뺏을 수 있는 CPU 스케줄링 알고리즘을 설명하도록 하겠다.

 

 

④ RR (Round Robin)

한 번 CPU를 잡으면 작업이 끝나는 것이 아니라, 타임 슬라이스 이후 무조건 쫓겨나기 때문에 시간 계산이 까다롭다. 1time slice를 10초로 잡았다. 끝나고 난 다음 p2 실행하는데 3초에 도착했으므로 대기시간은 7초(수행시간 10초)가 되고, p3의 대기시간은 14초(수행시간 9초), 19초 동안 기다린 p1이 10초 나머지를 실행하면서 끝낸다. 대기시간을 계산할 것이 매우 많아졌다. 결국, 22.33초 정도 걸린다. 결과적으로 FCFS와 성능 차이가 거의 없다고 보아도 무방하다.

 

 

⑤ SRT(Shortest Remaining Time) 스케줄링

뺏을 수 있는 작업 중 작업 시간이 짧은 것을 먼저 실행한다. 남은 시간이 적은 프로세스에게 CPU를 사용할 권한을 준다. p1이 아니라 p3가 먼저 실행된다. 그런데 아사현상이 발생할 수 있다. 그래서 잘 안 쓴다.

 

 

⑥ 우선순위 스케줄링 [선점형, 비선점형 모두 적용 가능]

뺏을 수 있는 방식과 뺏을 수 없는 방식 둘 다에서 사용 가능하다. 즉, 양쪽으로 구현이 가능하다. 중요한 것은, 현대에 있는 모든 CPU 스케줄링 시스템은 우선순위 시스템으로 사용되고 있다는 것이다. 커널 프로세스가 당연히 사용자 프로세스보다 우선순위가 높으므로 걔부터 돌려주는 게 맞다. 그런데 우선순위를 기준으로 하는 가장 최근에 만들어진 스케줄링이 p.225에 있는 다단계 스케줄링이다.

 

 

⑦ MLQ (Multi-Level Queue) 스케줄링

현대 스케줄링의 원형은 다단계 큐 스케줄링이다. 우선순위가 있는 큐가 여러 개 생성된다. 우선순위 0~3번, 그리고 각 큐는 RR로 움직인다. 프로세스가 들어오게 되면 CPU를 잡고 타임 슬라이스 아웃이 되면 다시 제자리로 돌아오고 돌아오는 Round Roading의 형태로 작동한다. 그런데 이 시스템에서 가장 큰 맹점이 뭐냐 하면, 0번을 실행하면 밑의 애들을 실행할 확률이 없어진다는 것이다. 이것이 우리가 쓰는 시스템의 원형이기도 한데, 그러한 단점이 있는 것이다. 그래서 다단계 피드백 큐가 등장한다.

 

 

⑧ MLFQ (Multi-Level Feedback Queue) 스케줄링

다단계 피드백 큐 스케줄링은 한 번 CPU를 잡을 때마다 자기 우선순위를 밑으로 내려버린다. 그래서 밑의 큐가 작업을 잡을 확률이 높아진다. 그럼에도 불구하고 여전히 위에 있는 큐보다 아래에 있는 큐가 CPU를 잡을 확률은 점점 더 떨어진다. 그래서 무엇을 조정했냐 하면, 타임 슬라이스를 조정했다. 밑으로 갈수록 타임 슬라이스를 크게 잡아준다. 한 번 잡기만 하면 작업 시간을 더 많이 가지도록 하는 합리적인 시스템이다. 맨 마지막 3번 큐에는 무한대의 시간을 할당한다. 이는 FCFS가 된다. 맨 마지막 밑바닥에 있는 것은 FCFS처럼 작동한다. 한 번 잡으면 끝까지 실행한다는 것이다.