CPU 스케줄링(2022.03.13 수정)

CPU란?

프로그램의 명령을 수행하는 컴퓨터 내의 중앙 처리 장치를 의미합니다.

 

CPU burst, I/O burst, CPU bound process, I/O bound process

프로세스는 CPU 작업, I/O 작업이 반복적으로 구성됩니다

 

CPU 작업

• 사용자 프로그램 자체에서 수행
• 사용자 프로그램이 CPU를 직접 가지고 있음

 

I/O 작업

• 특권 명령으로 규정
• 사용자 프로그램이 직접 수행할 수 없고 OS를 통해 수행
• 운영체제의 커널이 CPU 제어권을 가지고 있음

 

CPU burst

• I/O 작업이 끝나고 다음 I/O 요청이 올 때까지 직접 CPU를 가지고 명령 수행
• 사용자 프로그램이 CPU를 가지고 있음

 

I/O burst

• I/O 작업이 요청되고 다시 CPU burst로 돌아가기까지의 작업
• 운영체제의 커널이 CPU 제어권을 가지고 있음

 

CPU bound process

• I/O 작업을 거의 하지 않아 CPU burst가 길게 나타남

 

I/O bound process

• I/O burst가 빈번하여 CPU burst가 짧게 나타남

 

CPU 스케줄러

CPU가 사용 가능한 상태일 때, ready 큐에 있는 프로세스(PCB) 중 어느 프로세스에게 CPU를 할당할지 결정하는 것을 말합니다.

어느 프로세스에게 할당할 지 선택하는 과정을 "CPU 스케줄링"이라고 하며, "CPU 스케줄러"에 의해 수행됩니다.

 

CPU 스케줄러는 누가 하는 걸까요?

운영체제 안에 CPU 스케줄링을 하는 코드가 존재합니다. 따라서 CPU 스케줄러의 주체는 운영체제입니다.

 

디스패처(dispatcher)

CPU 스케줄러에 의해 선택된 프로세스에게 CPU를 넘겨주는 역할을 하는 커널 코드를 의미합니다.

 

디스패처 지연

하나의 프로세스를 정지하고 다른 프로세스를 시작하는데 소요되는 시간을 의미합니다.

현재 수행 중인 프로세스의 컨텍스트를 PCB에 저장하고, 바뀔 프로세스의 컨텍스트를 불러옵니다.

새로운 프로세스의 문맥을 불러온 뒤, 시스템의 상태를 사용자 모드로 전환하고 사용자 프로그램에게 CPU 제어권을 넘깁니다.

 

CPU 스케줄링은 언제 필요할까?

CPU bound job, I/O bound job의 특징을 연관지어 생각해보면, cpu bound job은 CPU를 사용하는 시간이 굉장히 깁니다.

반대로 I/O bound job은 CPU를 사용하는 시간이 짧습니다.

그렇다면 CPU bound job을 하는 프로세스가 계속 CPU를 가지고 있다면, I/O bound job은 계속 기다려야합니다.

I/O bound job은 클라이언트와 interactive한 job이기 때문에 해당 작업이 오래 걸린다면 응답 시간이 늦어져 클라이언트 관점에서는 느리게 느겨집니다.

 

즉, 컴퓨터 시스템 안에 있는 작업들은 I/O bound job, CPU bound job이 섞여있기 때문에 효율적으로 CPU를 할당하기 위해서 필요합니다.

 

Running -> Blocked(waiting) 비선점

프로세스가 I/O 작업과 같이 오래 걸리는 작업을 하러 가는 경우에 자진해서 CPU를 반환합니다.

• I/O 요청하는 시스템 콜
• 자식 프로세스가 종료되기를 기다리기 위해 wait() 호출

 

Running -> Ready 선점

독점적인 CPU 사용을 막기 위해서 할당 시간 만료(timer interrupt)될 시 CPU를 뺏습니다.

 

Blocked(waiting) -> Ready 선점

I/O 작업이 끝나면 device controller가 인터럽트를 걸어서 I/O 작업이 끝났다며 알리면서 wait한 프로세스의 상태를 ready로 변경합니다

 

여기서 중요한 점은 ready 상태로 바꿔주면서 CPU를 할당받을 수 있는 권한을 주는 것이지 바로 CPU를 할당하는 것이 아닙니다.

 

Terminate

프로세스가 종료될 때 CPU를 반환합니다.

 

CPU 스케줄링을 평가하는 기준

 

시스템 입장에서의 성능 척도

시스템 입장에서는 하나의 CPU를 가지고 많은 일을 시키면 성능이 좋다고 할 수 있습니다

 

이용률 (CPU Utilization)

전체 시간 중 CPU가 놀지 않고 일한 시간을 비율로 나타낸 것을 의미합니다.

즉, CPU가 일을 하지 않고 휴면 상태에 머무르는 시간을 줄이면 이용률이 올라가게 됩니다.

 

처리량 (throughput)

처리량은 주어진 시간 동안 "몇 개"의 일을 처리했는지 나타냅니다.(단위 시간 당 완료된 프로세스의 개수)

여기서 일이란 ready 큐에서 기다리고 있는 프로세스를 의미하며 처리량은 이러한 프로세스들 중 몇 개를 끝냈는지 말합니다.

즉, CPU burst가 짧은 프로세스에게 먼저 할당해주면 많은 프로세스를 처리할 수 있게 되므로 처리량이 올라갑니다.

 

프로그램 입장에서의 성능 척도

 

총 처리 시간(turnaround time)

프로세스를 실행하는데 소요된 시간을 의미하기 때문에 제출 시간과 완료 시간의 간격을 총 처리 시간이라 합니다.

ready 큐 대기시간 + CPU 이용한 시간 + I/O 시간을 총 처리 시간이라 합니다.

중요한 점은 프로그램이 시작해서 종료까지의 시간이 아니란 점입니다.

 

대기 시간(waiting time)

ready 큐에서 대기하며 기다린 시간의 합을 의미합니다.

총 처리 시간에서 말한 ready 큐 대기시간이 해당 waiting time을 의미합니다.

 

응답 시간(response time)

ready 큐에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간을 의미합니다.

응답 시간은 사용자 입장에서 가장 중요한 성능 척도이자 interactive한 작업에서의 적합한 척도이기도 합니다.

 

CPU 스케줄링 알고리즘

 

FCFS(First-Come First-Served)

• 비선점형 스케줄링
• 먼저 온 순서대로 처리
• 처음에 CPU를 오래 쓰는 프로세스가 도착한다면 CPU를 짧게 쓰는 프로세스들이 계속 기다려야하므로 비효율
• convoy effect

 

SJF(Shortest-Job-First)

• 비선점형 스케줄링
• CPU를 제일 짧게 쓰는 프로세스에게 CPU 할당
• 더 짧게 쓰는 프로세스가 도착해도 현재 작업하고 있는 프로세스의 작업이 끝날 때까지 뺏지 않음

 

문제점

• 우선순위가 낮은 프로세스(CPU를 오래 쓰는 프로세스)는 영원히 CPU를 할당받지 못하는 starvation 발생 가능성
• CPU 사용시간을 미리 알 수 없다

 

SRTF

• SJF와 다르게 짧게 쓰는 프로세스가 올 경우 현재 작업하고 있는 프로세스로부터 CPU를 뺏음

 

Priority Scheduling

우선순위가 제일 높은 프로세스에게 CPU를 할당합니다. 일반적으로 우선순위를 나타내는 숫자가 적을수록 우선순위가 높습니다.

앞서 배운 SJF도 cpu burst time이 가장 적은 것을 기준으로 하는 우선순위 스케줄링이라고 할 수 있습니다

우선순위가 같을 경우에는 FCFS와 같이 스케줄링 합니다.

 

문제점

• 우선순위가 낮은 프로세스는 영원히 CPU를 할당받지 못하는 starvation 발생 가능성

 

해결 방법

위 문제점을 해결하기 위해서 aging 기법을 도입합니다. aging 기법이란 우선순위가 낮은 프로세스에게 오래 기다릴수록 우선순위를 조금씩 높여주는 기법을 의미합니다.

 

Round Robin(RR)

1. 현대적인 컴퓨터 시스템에서 주로 사용하는 CPU 스케줄링 알고리즘이라고 합니다
2. CPU를 할당할 때 할당 시간을 세팅하여, 해당 시간이 끝나면 CPU를 강제로 뺏습니다
3. 할당 시간이 끝나도 프로세스가 끝나지 않았따면 큐의 꼬리로 이동합니다. 즉, RR에서의 준비 큐는 원형 큐로 구현되어있는 것을 알 수 있습니다
4. CPU를 줬다 뺏었다를 반복하기 때문에 최대 (n-1)*t 시간을 기다리면 CPU를 할당받을 수 있기 때문에 응답 시간이 빠릅니다
5. 어떤 프로세스가 CPU를 오래 쓸지 모르는 상황에서 굳이 예측할 필요 없이 CPU를 짧게 쓰는 작업은 빨리 쓰고 나갈 수 있습니다
6. CPU를 길게 쓰는 프로세스는 오래 기다리기 때문에 프로세스의 대기 시간이 CPU 사용 시간에 비례하게 됩니다
7. 타임 퀀텀을 매우 크게 하면 FCFS가 되고, 짧게 하면 문맥 교환을 자주하기 때문에 오버헤드가 커집니다.

 

문제점

만약 모든 프로세스가 필요한 CPU 시간이 모두 동일할 경우, 타임 퀀텀 때문에 계속 잘리게 되어 오버헤드를 야기할 수 있습니다.

 

Multi-Level Queue

지금까지의 스케줄링 알고리즘은 모두 ready 큐를 한 줄로 세웠습니다.

하지만 멀티 레벨 큐나, 멀티 레벨 피드백 큐는 여러 줄로 줄 세우기를 합니다.

큐마다 우선순위가 존재하고, 제일 위에 있는 큐의 우선순위가 가장 높습니다.

각 큐는 독립적인 스케줄링 알고리즘을 가지며, 상위 우선순위 큐가 비어있다면 아래의 큐에 CPU를 할당할 수 있습니다. 그래서 상위 큐가 비어있지 않게 되면 아래의 큐에 존재하는 프로세스들은 starvation을 겪을 수 있습니다.

 

동작 과정

프로세스의 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 해당 알고리즘을 사용할 수 있습니다.

foreground(대화형) 프로세스는 interactive 한 job으로써, RR을 사용하고

background(배치) 프로세스는 사람과 interaction 없이 CPU만을 오래 사용하고, 응답 시간이 빠르다고 좋을 것이 없습니다. 

따라서 CPU를 얻었다 뺏었다 하는 문맥 교환 오버헤드를 줄이기 위해 FCFS를 사용하는 것이 효율적입니다.

 

그래서 큐와 큐 사이의 스케줄링, 큐 안에서의 프로세스끼리의 스케줄링이 필요합니다.

 

문제점 & 해결 방법

우선순위가 낮은 큐는 아예 CPU를 얻지 못할 수 있습니다. 이에 각 큐에 시간을 나눠주는 방식이나 하위 우선순위가 오래 기다리면 상위로 올라가게 하는 방식으로 해결할 수 있습니다.

그래서 멀티 피드백 큐가 등장하게 됩니다.

 

Multi-Level Feedback Queue

멀티 레벨 큐와 다른 점은 프로세스가 큐끼리 “이동 가능"합니다.

멀티 레벨 큐는 큐를 구분하는 기준이 프로세스 유형인데, 프로세스가 다른 큐로 이동한다는 의미는 프로세스의 유형을 바꿔야합니다. 즉, 말이 안되므로 멀티 레벨 큐에서는 프로세스가 큐끼리 이동할 수 없습니다.

따라서 멀티 레벨 피드백 큐는 CPU burst 성격에 따라서 구분합니다.

어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위 큐로 이동합니다. 반대로 I/O bound process나 interation process들을 높은 우선순위의 큐에 넣습니다.

여기서 starvation을 예방하기 위해 낮은 우선순위의 큐에서 오래 기다리는 프로세스는 높은 우선순위의 큐로 이동할 수 있습니다.

 

동작 과정

1. 새로 진입하는 프로세스는 제일 상위에 존재하는 큐에 넣습니다
2. 8밀리초 안에 프로세스가 끝나지 않으면 큐1의 꼬리로 이동합니다
3. 큐 0이 비어있으면 큐 1의 머리에 있는 프로세스에 16밀리초의 시간을 할당해줍니다
4. 프로세스가 완료되지 않는다면 선점되어 큐 2에 넣습니다
5. 큐 0, 큐 1이 비어있을 때만 큐 2에 있는 프로세스들이 FCFS 방식으로 실행됩니다
6. starvation을 방지하기 위해 우선순위가 낮은 큐에서 너무 오래 대기하는 프로세스가 점차 우선순위가 높은 큐로 이동할 수 있습니다

 

멀티 프로세서 스케줄링

CPU가 여러 개 있을 경우에는 특정 CPU만 일하고 나머지 CPU는 놀고 있으면 안되기 때문에 load balancing을 해야합니다.

 

스레드 스케줄링

 

Local 스케줄링(Process Contention Scope) PCS

user level thread의 경우 사용자 프로세스가 직접 스레드를 관리하고 OS는 스레드의 존재를 모릅니다.

그래서 OS 입장에서는 프로세스에게 CPU를 할당하고, 프로세스 내부에서는 어떤 스레드에게 CPU를 할당할지 결정합니다. 즉, OS가 하는 것이 아닌 사용자 프로세스가 결정하게 됩니다

 

Global 스케줄링(System Contention Scope) SCS

kernel level thread의 경우 OS가 스레드의 존재를 알기 때문에 OS 자체가 프로세스 스케줄링하듯 어떤 알고리즘에 근거하여 어떤 스레드에게 CPU를 할당할지 결정하는 것입니다.

 

정리

• 커널은 본질적으로 커널 스레드에 대한 스케줄링만을 제공
• 유저 프로세스는 결국 어떤 커널 스레드에 의해 실행되어야만함
• 해당 유저 프로세스는 내부적으로 여러 개의 스레드를 가질 수 있는데, 이를 유저 레벨 스레드라 표현
• 해당 유저 레벨 스레드의 스케줄링에는 커널이 관여할 수 없고, 유저 레벨에서 결정됨
• 스케줄링 정책과 메커니즘은 개발자가 명시적으로 작성할 수도 있고, 라이브러리 등에서 암묵적으로 정의될 수 있음

 

REFERENCES

https://core.ewha.ac.kr/publicview/C0101020140328151311578473?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f

출처 :- ABRAHAM SILBERSCHATZ ET AL., OPERATING SYSTEM CONCEPTS, NINTH EDITION, WILEY, 2013- 반효경, 운영체제와 정보기술의 원리, 이화여자대학교 출판부, 2020