[운영체제] CPU 스케줄링

본 게시글은 KOCW 이화여자대학교 반효경 교수님의 <운영체제> 강의를 듣고,
<혼자 공부하는 컴퓨터구조 + 운영체제> 책을 참고하여 정리한 내용입니다.
게시글에 포함되는 이미지 자료는 <운영체제> 강의에 포함된 강의 자료입니다.

CPU 스케줄링이란?

모든 프로세스는 CPU를 필요로 하고, 먼저 CPU를 사용하고 싶어 합니다. 이러한 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위해 운영체제는 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 기다리게 할지를 결정합니다.

이렇게 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링(CPU Scheduling)이라고 합니다.

프로그램의 실행 단계 (CPU and I/O Bursts)

합리적이고 효율적인 CPU 자원 배분을 위해 어떤 프로세스에게 CPU를 먼저 할당하는 것이 좋을지를 판단하기 위해서는 프로세스가 어떤 단계를 거치며 실행되는지 생각해보아야 합니다.

 

 

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됩니다.

그렇기 때문에 실행 중인 프로세스(= 프로그램)는 대부분 위 그림과 같이 CPU 사용, I/O 장치 사용의 단계를 반복하게 됩니다.

 

• CPU Burst: CPU만 연속적으로 사용하며 instruction을 실행하는 단계
• I/O Burst: I/O를 실행하고 있는 단계

프로그램이 실행된다는 것은 CPU Burst와 I/O Burst가 반복되며 실행되는 것이라고 할 수 있습니다.

단, 프로세스의 종류에 따라 각각의 빈도나 길이가 다를 수 있습니다. (프로세스마다 CPU, I/O 장치 이용 시간 차이가 있음)

 

• CPU bound process: CPU를 이용하는 시간이 상대적으로 긴 계산 위주의 작업을 하는 프로세스
• I/O bound process: CPU를 잡고 계산하는 시간보다 입출력 작업에 더 많은 시간이 소요되는 프로세스

CPU-burst Time의 분포

위의 그래프에서 알 수 있듯이, I/O bound process의 경우에는 CPU를 사용하는 시간은 짧지만 CPU를 잡는 빈도가 높습니다.

반면, CPU bound process의 경우 CPU를 한 번 잡으면 사용시간이 길다는 것을 확인할 수 있습니다.

이렇게 다른 특성을 가진 프로세스가 섞여 있기 때문에 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용하기 위해 CPU 스케줄링이 필요한 것입니다.

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름
• CPU를 할당할 프로세스를 결정하는 운영체제 코드로, 별도의 하드웨어나 소프트웨어가 아님

Dispatcher

• CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 실제로 넘겨주는 과정을 담당하는 코드
• 이 과정을 문맥 교환(context switch)이라고 함

CPU 스케줄링이 필요한 경우는 다음과 같은 상태 변화가 있는 경우

1. Running -> Blocked (ex. I/O 요청 시스템 콜) 

2. Running -> Ready (ex. timer 인터럽트 (=할당 시간 만료)) 

3. Blocked -> Ready (ex. I/O 완료 후 인터럽트)

4. Terminate - nonpreemptive (자진 반납)

 

CPU 스케줄링이 필요한 경우는 프로세스가 자진 반납한 경우(nonpreemptive, 비선점형)와 강제로 빼앗아서 새로운 프로세스에게 CPU 제어권을 넘겨줘야하는 경우(preemptive, 선점형)로 나뉩니다.

1, 4 에서의 스케줄링은 nonpreemptive, 나머지 경우 preemptive

스케줄링 성능 척도

1. 시스템 입장에서의 성능 척도 - CPU가 일을 많이 하면 할 수록 성능이 높은 것

• CPU utilization (이용률): CPU가 일을 한 시간 / 전체 시간
• Throughput (처리량): 주어진 시간 안에 몇 개의 일(process)를 처리했는가 

2. 프로그램 입장에서의 성능 척도 - CPU를 얻어서 작업을 빨리 끝낼수록 성능이 높은 것

• Turnaround time(소요시간, 반환시간): CPU를 얻어서 쓰고 빠져나갈 때까지 걸린 총 시간 (대기시간 + CPU사용 시간 총합)
• Waiting time (대기 시간): ready queue에서 기다린 시간의 총합(한 번의 burst 에도 얻었다 빼앗겼다 여러번 반복 될 수 있음)
• Response time (응답 시간): 최초로 CPU를 얻기 까지 걸린 시간

CPU 스케줄링 알고리즘

FCFS (First-Come First-Served)

단순히 ready queue에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식입니다.

즉, CPU를 먼저 요청한 프로세스부터 CPU 할당하는 스케줄링 방식이므로 공정해보이긴 하지만 효율성이 높지는 않습니다.

 

비선점형 스케줄링 방식이기 때문에 먼저 선점한 프로세스의 작업이 오래걸릴 경우, 뒤에 있는 프로세스들은 작업시간이 짧더라도 선점한 프로세스의 작업이 끝날 때까지 기다려야 하므로 이러한 경우 효율성이 낮아지게 됩니다.

위의 그림에서 먼저 선점한 P1이 24초 동안 CPU를 사용하므로 뒤에 있는 프로세스들은 고작 3초간 CPU를 사용하기 위해 각각 24초, 27초동안 기다리게 되므로 평균 대기시간(waiting time)은 17초((0 + 24 + 27) / 3 = 17)가 됩니다. 

이 경우와 같이 먼저 도착한 프로세스가 CPU에서 수행되는 버스트 시간이 매우 길어 그 다음 도착한 프로세스가 매우 긴 시간을 기다리게 되는 것을 convoy effect(호위 효과) 라고 합니다.

SJF (Shortest-Job-First)

ready queue에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식입니다.

SJF에는 두 가지 방식이 존재합니다. (기본적으로는 비선점형 스케줄링 알고리즘으로 분류되긴 함)

 

Nonpreemptive(비선점형)

• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

Preemptive(선점형)

• 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부름
• 가장 짧은 평균 대기 시간(waiting time)을 보장

Nonpreemptive vs. Preemptive

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

SJF (Nonpreemptive)

 

• 프로세스가 CPU를 다 사용하고 나가는 시점에 스케줄링을 결정
• 도착시간이 가장 빠른 P1이 가장 먼저 CPU 선점
• P1의 작업이 끝나는 시점에 P2, P3, P4 가 모두 도착해있으므로 그 중 CPU 이용시간 가장 짧은 P3 먼저 실행
• 평균 대기 시간: (0 + 6 + 3 + 7) / 4 = 4

SRTF (Preemptive)

 

• 새로운 프로세스가 도착할 때 마다 새로 스케줄링
• 가장 먼저 도착한 P1의 작업이 끝나기 전에 CPU 이용시간이 더 짧은 P2가 도착하면 P1에게서 CPU를 빼앗아 P2에 할당하는 방식으로 P4의 작업까지 끝나는 동안 여러 프로세스가 번갈아서 CPU를 사용하게 됨
• 평균 대기 시간: (9 + 1 + 0 + 2) / 4 = 3
• 어떤 알고리즘을 써도 SRTF(= preemptive SJF) 보다 짧은 waiting time을 가질 수 없음 (평균 대기 시간이 가장 짧음)

SJF의 단점

1. starvation (기아 현상)

극단적으로 CPU 사용시간이 짧은 프로세스를 선호하기 때문에 영원히 CPU를 할당받지 못하는 프로세스가 생길 수 있습니다.

CPU 이용 시간이 긴 프로세스가 ready queue에 하나 있는 상황에서 CPU 이용 시간이 짧은 프로세스들이 계속해서 들어오게 되면 긴 프로세스는 영원히 실행되지 못할 수 있습니다.

 

2. CPU 사용시간을 미리 알 수 없다.

SJF는 CPU burst time이 짧은 프로세스에게 먼저 CPU를 할당하게 되는데, 다음 실행할 프로세스를 결정할 때 OS는 각 프로세스가 CPU를 얼마나 사용할지 정확히 알 수 없고, 과거의 CPU burst time을 통해 예측하기 때문에 실제 사용시간과 차이가 있을 수 있습니다.

Priority Scheduling (우선순위 스케줄링)

우선순위가 높은 프로세스에게 먼저 CPU를 할당하는 방식입니다.

우선순위의 기준에는 여러가지가 있을 수 있기 때문에 SJF도 우선순위 스케줄링에 포함될 수 있습니다. (기준: CPU 이용 시간이 짧은 프로세스가 높은 우선순위)

우선순위 스케줄링에도 비선점형, 선점형(우선순위 높은 프로세스가 들어오면 CPU 빼앗김) 이렇게 두 가지 방식이 존재합니다.

 

또한, starvation(기아 현상)이라는 문제점이 존재(우선순위 낮은 프로세스가 영원히 CPU를 할당 받지 못하는 상황이 생길 수 있음)하는데, 이는 특정 프로세스가 지나치게 차별받기 때문에 생기는 문제이므로 아무리 우선순위가 낮은 프로세스라 하더라도 지나치게 오래 기다리게 되면 우선순위 높여주는 aging으로 이러한 문제를 해결할 수 있습니다.

RR(Round Robin)

FCFS에 타임 슬라이스라는 개념이 더해진 스케줄링 방식입니다.

타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

즉, Round Robin 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링입니다.

현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 라운드 로빈에 기반하고 있습니다.

 

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 milliseconds)
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 서게 됨
• 할당 시간이 너무 길어지면 FCFS와 동일해짐
• 할당 시간이 너무 짧다면 context switching이 빈번해져 오버헤드가 커짐

Round Robin

 

일반적으로 SJF보다 평균 대기시간이 길지만 응답시간(response time)은 더 짧습니다.

RR의 장점

1. 응답시간(CPU를 최초로 얻기 까지의 시간)이 빨라진다.

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻게 됩니다. 그렇기 때문에 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않습니다.

 

2. CPU 사용시간 예측이 필요없다.

어떤 프로세스가 CPU를 오래 사용하게 될지 모르는 상황에서 굳이 예측할 필요없이 burst time이 짧은 프로세스가 빨리 CPU를 사용하고 나갈 수 있도록 해줍니다.

 

3. waiting time이 burst time에 비례해서 길어진다. (공정성)

CPU 사용시간이 짧은 프로세스는 할당 시간 안에 CPU를 사용하고 빨리 나갈 수 있으므로 상대적으로 대기 시간이 짧아지기 때문에 waiting time이 CPU 사용시간에 비례해져 공정한 방식이라고 할 수 있습니다.

Multilevel Queue

우선순위 스케줄링의 발전된 형태로, 우선순위별로 ready queue를 여러 개 사용하는 방식입니다.

CPU는 우선순위가 높은 큐부터 스케줄링하게 됩니다.

 

Multilevel Queue

• Ready Queue 를 여러개로 분할 - 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐 
  • foreground : interactive
  • background : batch - no human interaction 
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐(각 큐에 맞는 스케줄링 방식)
  • foreground : RR
  • background : FCFS
• 큐에 대한 스케줄링 필요
  • Fixed priority scehduling
    • ex) background보다 forground 먼저
    • starvation 가능성 있음 (우선 순위 낮은 큐는 영원히 CPU 할당받을 수 없을수도)
  • Time slice
    • 각 큐에 CPU Time 을 적절한 비율로 할당
    • ex) 80% foreground in RR, 20% background in FCFS

Multilevel Feedback Queue

Multilevel Queue 방식에서는 프로세스들이 큐 사이를 이동할 수  없기 때문에 우선순위가 낮은 프로세스는 CPU 할당이 계속 연기되어 영원히 할당 받지 못하는 starvation(기아 현상)의 가능성이 있는데, 이를 보완한 스케줄링 알고리즘이 Multilevel Feedback Queue입니다.

 

• 프로세스가 다른 큐로 이동 가능
• aging 기법을 이런 방식으로 구현하여 stavation 예방
• 고려사항
  • Queue 의 수
  • 각 큐의 schedhuling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 쫓아내는 기준
  • 프로세스가 CPU 서비스를 받으려고 할 때 들어갈 큐를 결정하는 기준

Multilevel Feedback Queue

 

Multilevel Feedback Queue 알고리즘에서는 새로 ready 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 큐에 삽입되고 일정시간(time quantum)동안 실행됩니다. 이 때, 우선순위가 가장 높은 큐에게는 time quantum 짧게 할당하고, 우선순위가 낮은 큐일수록 긴 time quantum을 할당합니다. 그리고, 우선순위가 가장 낮은 큐는 FCFS 알고리즘을 사용합니다.

만약 우선순위가 높은 큐의 할당 시간이 만료되면 실행이 끝나지 않은 프로세스는 아래 큐로 강등되는 방식으로 운영됩니다.

그렇기 때문에 CPU 이용시간이 짧은 프로세스는 짧은 시간안에 큐를 빠져나갈 수 있게 되고, CPU 이용시간이 긴 프로세스는 아래 큐로 이동하면서 점점 더 긴 할당시간을 받게 됩니다. 즉, CPU 사용시간이 짧은 프로세스에게 높은 우선순위를 주는 방식입니다.

그러나, 위의 큐가 비어있을 때만 아래 큐를 처리하는 방식이기 때문에 가장 먼저 도착한 프로세스는 빨리 처리되지만 이후에 들어온 프로세스의 경우 우선순위가 높은 위의 큐가 빌 때까지 기다려야 합니다.