Virtualization - CPU Scheduling

Virtualization - CPU Scheduling

CPU의 코어의 갯수가 한정적이지만 프로세스는 많을 경우

사용자가 답답하지않도록 운영체제는 프로세스들을 잘 줄지어서 CPU 코어를 배정해줘야한다.

이를 CPU Scheduling이라고 한다.

 

사용자의 화면에 떠서 사용자가 클릭하고 타이핑하는 류의 프로세스는 반응성이 중요하다.

그래서 짧게라도 자주 CPU 코어에 배정해줘야한다.

반면 백그라운드에서 돌지만 계산이 오랜 시간 필요한 프로세스는 얼마동안 배정받지않더라도 사용자에게 답답함을 유발하지 않는다. 가끔 길게 CPU 코어를 배정해주면 될 것이다.

 

Time Sharing & Time Slicing (같은 말이다.)

Muti programming 시대가 열리면서 프로세스간에 동시에 도는 것을 지원한다.

계속해서 짧은 시간마다 다른 프로세스를 실행하면 여러 프로세스가 동시에 실행하는 것처럼 보일 것이다.

실제로 운영체제는 그렇게 해주고 있다.

그럼 어떻게 계속 다른 프로세스로 주도권을 넘겨줄 수 있을까?

 

Cooperative (협력적인)

프로세스 자체가 계속해서 주도권을 넘겨주면 되는 것이다.

그러면 유저 프로세스가 실행하다가 양보하면 운영체제가 다음 프로세스에게 주도권을 준다.

그리고 다음 프로세스가 양보하면 운영체제가 다다음 프로세스에게 주도권을 준다.

 

Preemptive Scheduling

한국어론 “선점형 스케쥴링”이라고 한다.

프로세스 자체가 양보하지않아도 운영체제가 애초에 타이머를 걸어놓고 주도권을 뺏어온다.

그리고 스케쥴링 알고리즘에 따라 다음 프로세스를 선정하여 주도권을 준다.

 

Non-Preemptive Scheduling

한국어론 “비선점형 스케쥴링”이라고 한다.

한 프로세스가 전부 실행을 완료할때까지 다음 프로세스에게 주도권을 넘겨주지않는 방식이다.

 

*보통은 Preemptive Scheduling을 사용한다.

 

*Turnaround Time (반환시간)

프로세스가 시작된 이후부터 끝나는데까지 걸린 시간이다.

이 시간안에는 CPU의 코어 배정을 받았다가 말았다가하는 시간들이 전부 포함된다.

 

*Response Time (반응시간)

Turnaround Time도 중요하지만 Response Time도 중요하게 생각해야한다.

Response Time은 처음에 작업이 도착하고나서 처음 해당 작업이 CPU를 점유하게 되기까지의 시간이다.

작업을 요청했는데 한참 후에 시작한다면 이건 사용자에게 안좋은 경험을 줄것이다.

 

Scheduling Algorithms

스케줄링 알고리즘 종류는 어떤게 있을까?

 

FCFS (First Come First Server)

선입 선처리 스케쥴링.

말그대로 먼저 실행을 시작한 프로세스가 먼저 코어를 배정받는다는 것.

Non-Preemptive, 비선점형 스케쥴링이라 실행중인 프로세스가 전부 끝나야 다음 프로세스의 차례가 온다.

 

A, B, C가 동시에 실행을 시작했는데 A → B → C 가 아주 조금의 차이로 시작했다고 하자.

그리고 각각의 프로세스가 끝마치기 위해서는 10초씩 돌아야한다고 치자.

그럼 다음과 같이 실행될 것이다.

 

그럼 평균 Turnaround Time은 얼마인가?

A는 10초, B는 20초, C는 30초일것이고 평균하면 20초이다.

근데 A가 엄청 오래걸리는 작업이라고 한다면…?

 

예를 들어 100초 걸린다고 한다면 평균 Turnaround Time은 110초가 된다.

이걸 convoy effect 라고 불린다.

*호위 효과(convoy effect)라 한다. 호위 효과가 발생할 경우 CPU와 장치 이용률이 낮아진다.

 

SJF (Shortest Job First)

최단 작업 우선 스케쥴링.

남은 시간이 짧은 것을 먼저 끝낸다는 것이다.

Preemptive 로도 구현될 수 있지만 Non-Preemptive로도 구현될 수 있다.

 

SJF를 활용하면 평균 Turnaround Time은 훨씬 줄어들 수 있다.

그래서 아주 좋은 알고리즘이다. 하지만 현실적이지 못하다.

현실에서는 컴퓨터가 어떤 프로세스의 작업이 얼마나 걸릴지 알수가 없기때문이다.

 

그리고 Non-Preemptive이고 오래 걸리는 A가 먼저오고 A가 실행되는중에 B, C가 도착하면 같은 문제가 발생한다.

 

SRT (Shortest Remaining Time)

최소 잔여 시간 우선 스케쥴링.

Shortest Time-to-Completion First (STCF) 이라고 부르는 책도 있다.

SJF의 Preemptive 버전이라고 보면 된다.

 

RR (Round Robin)

라운드 로빈 스케쥴링.

FCFS 스케쥴링에 Time Slicing의 개념이 더해진것이다.

먼저 들어온 프로세스가 먼저 코어를 배정받지만 짧게 실행하고 다음 프로세스에게 넘기고 큐의 뒤로 들어간다.

작업들을 순서대로 Queue에 넣고 시간을 잘게 쪼개서 계속 다른 작업으로 스케줄링하는 방법이다.

가끔 Round Robin은 Time Slicing이라고 불리기도 한다.

근데 RR은 Response Time은 최적이지만 Turnaround Time은 최악이다.

빨리 끝날 수 있는 작업도 다른 작업들과 Time Slicing하면서 돌아가느라 엄청나게 나중에 끝나버린다.

 

MLFQ (The Multi-Level Feedback Queue)

다음 알고리즘은 Round Robin으로 해결했던 Response Time은 그대로 최적으로 두되,

놓쳤던 Turnaround Time을 최적화하는 것이다.

 

Round Robin과 같이 작업들을 Queue에 넣되, 여러개의 Queue를 두고 각 Queue에는 Priority를 배정이다.

한 프로세스에 계속 같은 Priority를 배정하는 것이 아닌 그때그때마다 동적으로 작업마다 Priority가 바뀐다.

CPU를 반복적으로 양보하며 I/O를 하는 작업은 우선순위를 높게 유지한다.

대신 긴 시간동안 CPU를 집중적으로 사용하는 작업은 우선순위를 낮춘다.

 

MLFQ의 두 가지 기본 규칙은 다음과 같다.

• 규칙 1 : Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행X)
• 규칙 2 : Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.

하지만 이 방법도 문제점은 존재한다.

• 기아 상태 (Starvation) : 시스템에 너무 많은 I/O 작업을 반복적으로 사용하는 프로세스들만 존재하면 그들 모두 Priority가 높게 배정될 것이고 실행 시간이 긴 작업은 CPU를 할당받지 못할 것이다.
• 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 하게 만드는 것이 가능해진다. 실행 시간이 긴 작업같이 보이다가 할당 시간이 다 끝나갈때쯤 I/O를 요청하면 Priority를 높게 받을 것이다.