운영체제 6-1강 (CPU 스케줄링)

늘보·2021년 7월 6일

OS

목록 보기

10/25

본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
본 글은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성되었습니다.
강의 링크 : http://www.kocw.net/home/search/kemView.do?kemId=1226304

CPU 스케줄링을 설명하기에 앞서 그 배경에 대해 잠깐 설명하자. 프로그램이 실행이 되면 어떤 프로그램이든 간에 다음과 같은 과정을 따라 수행이 된다. “load store”, “add store”와 같은 것들은 CPU에서의 instruction 즉, 기계어이다. 그리고 중간중간 I/O를 위한 작업이 있다. 그러니까 프로그램의 일반적인 구성상 CPU를 썼다가 I/O를 했다가 하며 반복적으로 번갈아 가며 수행될 것이다. 여기서 일련의 CPU instruction을 수행하는 단계를 CPU burst라고 하고 I/O를 수행하는 단계를 I/O burst라고 한다.

프로세스의 특성 분류

I/O-bound process

I/O에 많은 시간이 필요한 job (짧다)

CPU-bound process

계산 위주의 job (길다)

다음은 일반적인 job들의 CPU-burst time의 분포를 그린 것이다. CPU burst와 I/O burst의 수행 횟수를 비교해봤더니 I/O burst가 중간에 많이 일어나게 되어 CPU burst의 지속 기간이 짧은 job들이 월등히 많았고, CPU intensive한 job들은 적었다. 전자를 I/O bound job이라 하며 사람과 interact 하는 job(Interactive job)이라 하며 후자를 CPU bound job이라 한다. 그러나 이렇다고 해서 CPU를 많이 쓰는 job이 I/O bound job이라고 단정할 수는 없다. 단순히 CPU-burst time의 지속 시간이 짧은 job들이 I/O bound job이며 이들의 빈도가 많았을 뿐이다.

여기서 CPU 스케줄링이 필요한 이유가 대두된다. CPU bound job은 빈도도 낮으며 한 번 CPU를 쓰면 오래 쓴다. 그러나 I/O bound job의 경우 CPU를 짧게 여러 번 사용한다. 따라서 두 job들이 맞물려 있다면 I/O bound job을 적절히 수행할 수 없게 되며 사용자가 답답함을 느끼게 될 것이다. 따라서 적절한 관리가 필요하다.

그러나 무조건 공평하게 CPU를 분배한다고 해결되는 것은 아닐 것이다. 사용자의 입장에서는 무조건 공평한 것 보다는 사용자와 가까운, 즉, Interactive job에게 더 우선적으로 스케줄링을 해주는 것이 좋을 것이다. 그러니까 Interactive job이 너무 오래 기다리지 않게 하도록 하는 것, 이것이 바로 CPU 스케줄링의 핵심이다.

* CPU Scheduler & Dispatcher에 대한 간단한 설명

CPU scheduler는 누구에게 CPU를 줄지 결정한다. 스케줄러라 하니 꼭 무슨 소프트웨어나 하드웨어를 일컫는 것 같지만 사실은 운영체제 커널 내부에 있는 스케줄링 코드 부분을 말한다.

Dispatcher도 하드웨어도 아니며 소프트웨어도 아니다. CPU를 누구에게 줄 지 결정했으면 그 프로세스에게 넘겨주는 운영체제 커널 코드를 말한다. CPU를 넘겨줄 때 해야 되는 것이 있었지 않은가? 바로 문맥 저장! 그러니까 프로세스의 Context를 저장하고, 새로이 CPU를 넘겨받을 프로세스의 Context를 펼쳐 놓아야 한다. CPU register 값 세팅하고 Program Counter에 앞으로 실행할 코드 영역 가져다 놓고… 이후 CPU를 넘겨주는 작업을 담당한다.

CPU 스케줄링은 언제 필요한가?

1. Running -> Blocked

I/O와 같이(오래 걸리는 작업임) 어차피 당장 CPU를 가지고 있어도 무언가를 할 수 없을 때 스케줄러는 스케줄링을 한다.

2. Running -> Ready

나는 CPU를 계속 쓰고 싶으나 무한정 시간을 제공할 수는 없다. Timer가 존재하기 때문인데 이 Timer가 할당한 시간이 만료가 되어 Timer interrupt가 발생할 때이다.

3. Blocked -> Ready

I/O를 요청했던 프로세스의 I/O 작업이 끝난 경우이다. 그런데 지금까지는 I/O가 끝났더라도 바로 running 되는 것이 아니었다. 일반적으로 이미 CPU를 소유하고 있던 프로세스에게 다시 넘어가는데 이 경우는 Timer에 기반한 스케줄링한 경우이다. 만약 우선순위에 기반한 스케줄링이었고, 이전에 I/O 작업을 요청했던 프로세스의 I/O 작업이 끝난 그 프로세스가 우선순위가 가장 높았다면, 중간에 CPU를 빼앗겼던 프로세스의 시간이 남아있다 하더라도 우선순위가 가장 높은 프로세스로 CPU가 넘어간다. 이러한 이유로 I/O 작업 요청으로 인해 Blocked 상태였던 프로세스에서 Ready 상태로 넘어가는 때에 스케줄링이 필요하게 된다.

4. Terminate

프로세스가 종료돼서 할 게 없을 때 넘겨준다.

1번과 4번은 nonpreemptive(자진 반납), 2번과 3번은 preemptive(강제로 빼앗는) 스케줄링이라고 한다.

CPU 스케줄링 성능 척도

이번 강에서는 CPU 스케줄링 알고리즘에 대해 설명한다. 이를 설명하기에 앞서 스케줄링의 성능의 기준을 알아보자.

CPU utilization (CPU 이용률)은 전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율을 의미한다.
Throughput (처리량)은 단위 시간당 CPU의 처리량을 의미한다. CPU가 얼마나 많은 일을 했는가를 나타낸다.
Turnaround time (소요 시간) 부터는 모두 시간과 관련된 것이다.
Waiting time (대기 시간)
Response time (응답 시간)

이 다섯 가지 기준을 쉬운 예시를 통해 살펴보자.

우리가 건물주가 되어 중국집을 차려서 중국집 주방장(CPU)을 고용한다고 가정하자. 우리로서는 주방장이 최대한 많은 시간 동안 일을 하는 것이 좋을 것이다. 뿐만 아니라 하루 동안에 많은 손님을 받아 많은 요리를 만들어 내면 더 좋을 것이고, 한 가지 요리를 완성하는 시간이 짧으면 더 좋을 것이다. 그러나 손님들이 똑같은 음식들을 주문하더라도 그 주방장이 어떤 순서로 요리를 하느냐에 따라 주방장이 일한 시간(CPU utilization)이 달라질 수 있을 것이다. 게다가 요리 순서에 따라 하루에 손님을 얼마나 받는지(Throughput)도 달라질 수 있다. 추가적으로 요리 순서를 바꿈으로써 중국집을 찾은 손님들이 기다린 시간(Waiting time)이나, 음식이 나오는 시간(Response time), 모두 먹고 나가는 데 걸리는 시간(Turnaround time)이 전부 달라질 수 있다. 여기서 음식의 스케줄링, 컴퓨터로 치면 CPU 스케줄링의 필요성이 대두된다.

'시간'에 대해 조금 더 이야기해보자. 우리가 중국집에 들어갔으면 물이라도 먼저 가져다주거나 하물며 단무지라도 먼저 제공이 되어야 손님 입장에서는 내 주문이 확실히 들어갔다는 것을 느낄 수 있다. 이것이 응답 시간(Response time)이다. CPU를 얻기까지 '최초로' 걸린 시간을 의미한다. '최초'라는 단어가 중요한데 그 이유는 대부분의 운영체제는 preemptive scheduling을 선택하기 때문이다. Preemptive scheduling은 중간중간 CPU를 점유하는 CPU burst가 나뉘어 있기 때문에 이들 중간에 있는 CPU burst time의 시작이 아니라 가장 처음 CPU를 잡게 되는 시간이 프로세스 입장에서 Response time인 것이다. 대기 시간은 응답 시간과는 다르며, 중국집 요리를 먹으러 와서 기다린 시간(Waiting time)의 전체 합(프로세스가 CPU를 얻기 위해 기다린 시간의 총합)이다. 마지막으로 소요 시간(Turnaround time)은 기다린 시간과 밥 먹는 시간 전부 합친 것이다.