운영체제 - CPU스케줄링 알고리즘(선점형, 비선점형)

강의 소개

현재 수강하고 있는 KOCW 내 이화여자대학교 운영체제(2017, 반효경) 강의의 내용을 정리하였습니다.

개발자 관점에서 운영체제 기초를 학습하는 무료 강의로 자세한 강의 내용은 수강을 추천드립니다.

---

 

CPU스케줄링을 하는 이유

스케줄링이란 운영체제가 어떤 프로세스를 실행되게 할 것인지 정하는 것이다.

ready queue에 들어간 프로세스들이 실행을 하는 순서를 정한다.

시스템 자원을 효율적으로 사용하기 위해 중요하다.

 

 

CPU스케줄링의 여러 가지 알고리즘

 

크게 CPU를 빼앗을 수 있는지 여부에 따라 비선점 스케줄링, 선점 스케줄링으로 나눌 수 있다.

 

선점형이란 특정 프로세스가 1개의 CPU를 사용하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 있는 방법이다.

프로세스의 우선순위가 높은 프로세스가 CPU를 먼저 차지하기가 쉬어 높은 우선순위의 프로세스들이 급히 실행해야 할 경우에 유용하다. 많은 오버헤드(근본적으로 해야 할 일들을 하기 위해서 준비하는 작업이나 먼저 처리해두어야 하는 일 등으로 원래 하려던 작업이 아닌, 부가적인 작업을 일컫는다.)를 초래한다. 문맥 교환이 비선점에 비해 많다. (문맥 교환은 운영체제에서 오버헤드의 큰 요인 중 하나이다.)

대화식 시분할 시스템에서 빠른 응답 시간을 유지하는데 요구된다.

 

비선점형이란 프로세스가 이미 할당된 CPU를 빼앗을 수 없고, 모든 프로세스들의 요구를 공정하게 처리한다.

따라서 응답 시간의 예측이 쉽고, 문맥 교환 횟수가 적다. CPU 사용 시간이 짧은 작업이 사용 시간이 긴 작업을 기다리는 경우가 발생할 수도 있는 것이 단점이다.

일괄처리(batch processing)에 유리하다.

 

---

비선점형(nonpreemptive) 스케줄링 종류

 

1. 선입 선출 스케줄링(FCFS: First-Come First-Served)

FIFO(First-In First-Out)라고도 부르며, 먼저 온 프로세스에게 CPU를 주는 방법이다. 

프로세스의 도착 순서대로 처리한다. CPU스케줄링에서는 비효율적이다.

ex. 은행에서 고객을 처리하는 순서는 도착순이다.

- Convoy effect(호위 효과): 처리시간이 긴 프로세스가 먼저 도착하게 되면 평균 대기시간이 매우 길어진다. 즉, 처리시간이 짧은 short process가 늦게 오면 long process 때문에 오래 기다리게 된다.

 

 

2. 최단 작업 우선 스케줄링(SJF: Shortest-Job-First)

CPU burst 시간이 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.

일단 CPU를 잡으면 더 짧은 프로세스가 들어와도 먼저 CPU를 준 프로세스의 CPU burst가 완료될 때까지 CPU를 빼앗지 않는다. (CPU를 유지시킨다.)

최소 평균 대기시간을 제공하지만, 빠른 응답 시간을 제공해야 하는 대화식 시분할 시스템에는 부적절하다.

짧은 작업일수록 더 좋은 서비스를 받을 수 있어 오버헤드 측면에서 SJF는 짧은 작업 프로세스에 유리하다.

 

 

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

우선순위가 제일 높은 프로세스에게 CPU를 할당한다. 일반적으로 우선순위 값 (priority number)가 작을수록 높은 우선순위를 갖는다.

SJF는 일종의 우선순위 스케줄링 (Priority Scheduling)이다. (우선순위 = 예상되는 다음 CPU 버스트 시간)

 

- 종류

1) nonpreemptive

먼저 CPU를 잡으면 더 높은 우선순위를 가진 프로세스가 들어와도 CPU burst가 완료될 때까지 CPU를 빼앗기지 않는다.

 

2) preemptive

CPU를 사용 중이라 하더라도 더 높은 우선순위를 가진 프로세스가 들어오면 CPU를 빼앗긴다.

> 문제점

Starvation (기아 현상): 우선순위가 낮은 프로세스는 영원히 CPU를 잡지 못할 수 있다.

-> 해결 방안

Aging (노화): 아무리 우선순위가 낮은 프로세스라 하더라도 대기 시간이 오래 지나면 우선순위를 높여주는 방법이다.

 

 

4. 실시간 스케줄링 (Real-time Scheduling)

다른 스케줄링과 달리, deadline이 이 있어 정해진 시간 안에 반드시 작업이 실행이 되어야 하는 프로세스일 때 사용한다.

빨리 실행되는 것보다 deadline을 지키는 것이 중요하다.

 

- 종류 

1) 경성 실시간 시스템 (hard real-time system)

deadline 안에 반드시 작업이 끝나도록 스케줄링해야 한다. 

 

2) 연성 실시간 시스템 (soft real-time system)

동영상을 재생할 때 초당 프레임을 읽어오는 상황처럼, deadline 존재하기는 하지만 지키지 못했다고 해서 위험한 상황이 생기지는 않는다.

일반 프로세스에 비해 높은 우선순위를 높여주어 가능하면 먼저 CPU를 얻도록 해야 한다.

 

 

5. HRN(Highest Response ratio Next)

짧은 작업과 대기 시간이 긴 작업의 우선순위를 높인다.

SJF의 단점인 긴 작업과 짧은 작업의 과도한 불평등을 보완하기 위한 기법이다.

한 프로세스가 CPU를 사용하면 작업이 완성될 때까지 실행하며, 대기시간이 고려되어 긴 작업과 짧은 작업 사이의 불평등을 어느 정도 완화한다.

 

---

 

선점형(preemptive) 스케줄링 종류

 

1. SRT(Shortest-Remaining-Time) 스케줄링

SJF스케줄링을 선점형으로 구현한 기법으로, SRTF (Shortest-Remaining-Time-First)라고도 부른다.

먼저 CPU를 잡았다 하더라도 더 짧은 프로세스가 들어오면 CPU를 빼앗기는 방식이다. 더욱 최적의 스케줄링 방법이다.

현재 CPU를 사용하고 있는 프로세스가 있더라도, 다른 프로세스들이 Ready queue에 도착할 때마다 지금 CPU를 사용하고 있는 프로세스의 잔여 작업시간과 비교한다.

 

- 사용 예시

프로세스 A가 5초를 사용해야 하고(= Burst time이 5초), 이미 작업을 수행 중이어서 2초가 걸리는 작업이 남았는데, 이때 프로세스 B가 1초 작업을 수행해야 하면 남은 수행 시간을 기준으로 2초 > 1초 이기 때문에 프로세스 B에게 넘어가는 방법이다.

 

- 문제점

Starvation(기아)

: 짧은 프로세스로 인해 긴 프로세스가 영원히 CPU를 잡지 못할 수 있다. 너무 효율성만 고려해서 짧은 프로세스에게만 우선권을 주기 때문이다.

CPU burst 시간을 미리 알 수 없다.

: 과거 CPU burst time(사용시간)을 통해 예측만 가능하다.

 

 

2. 라운드 로빈 스케줄링 (RR: Round Robin)

CPU 스케줄링에서 현재 가장 많이 사용하는 방법의 근간이다.

 

- 방법

각 프로세스는 동일한 크기의 할당 시간인 time quantum을 가진다.

timer에 할당 시간이 끝나면 timer interrupt에 의해 프로세스는 CPU를 운영체제에게 빼앗기고 Ready queue 맨 뒤에 가서 줄을 서게 된다.

 

- 특징

CPU의 독점권을 막는다. (timer에 의해 preemptive 된다.)

I/O bound job과 CPU bound job을 구분하는 효과를 가진다. (I/O bound job은 CPU 사용 시간 이 짧아 원하는 만큼 사용 후 나가는 반면, CPU bound job은 CPU 사용시간이 길어 할당된 시간에 다 사용하지 못해 사용했다가 빼앗겼다를 반복한다.)

짧은 응답 시간을 보장한다.

(조금씩 CPU를 줬다 뺏었다를 반복하기 때문에 CPU를 최초로 얻기까지 걸리는 시간이 짧다.)

기다리는 시간이 프로세스가 CPU를 쓰려는 시간과 비례한다. (CPU를 길게 쓰려면 줄 선 횟수가 길어진다. 그에 반해 짧게 쓰는 프로세스들은 한 번에 CPU를 쓰고 나간다)

 

- 성능

할당 시간이 커질수록 FCFS(= FIFO)에 가까워진다. 

할당 시간이 작아질수록 context switch(문맥 교환) 오버헤드가 증가한다.

=> 적절한 할당 시간은 I/O bound job은 한 번에 나갈 수 있고, CPU bound job은 한 번에 나갈 수 없는 시간을 줘야 한다.

 

- 장점

일반적으로 SJF보다 평균 turnaround time(소요 시간)이 길지만, response time(응답 시간: 프로세스가 CPU를 얻으러 들어가서 첫 번째 CPU를 얻기까지의 시간)은 더 짧다. 이것의 장점은 interactive job이 많은 경우 효율적이게 된다.

 

- 단점

시간이 오래 걸리는 long job과 짧게 걸리는 short job이 섞여 있을 때는 효율적이지만, 모든 시간이 동일한 job만 있을 때는 비효율적이다. (하나씩 처리하면 조금씩 걸릴 텐데, 모든 작업이 오랜 시간 걸려 동시에 몰려서 작업이 끝난다.)

 

 

3. 멀티 레벨 큐 (다단계 큐, Multi-Level Queue : MQ)

CPU는 1개지만 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법이다.

Ready Queue를 우선순위에 따라 여러 개로 분할한다. 그룹화된 작업들은 각각의 Ready Queue에 넣어두고 각 큐의 독자적인 스케줄링 알고리즘으로 CPU를 할당받는다.

 

• 전면 작업(foreground, 전위 큐): 빠른 응답을 필요로 하는 interactive 작업을 넣는다. 주로 라운드 로빈 스케줄링 기법을 사용한다.(응답 시간이 빨라야 하므로)
• 후면 작업(background, 후위 큐): 일괄처리 작업들로, 즉 human interaction 없이 일반적으로 CPU를 오래 사용하는 계산 위주의 작업을 넣는다. 주로 FCFS 스케줄링 기법을 사용한다. (long job들은 CPU를 얻었다가 빼앗기는 것, 즉 잦은 문맥 교환이 더 비효율적이기 때문이다.)

 

- 종류

멀티 레벨 큐 자체에 대한 스케줄링이 필요하다.

1) 고정 우선순위 방식 (Fixed Priority Scheduling)

전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고, 전위 큐가 비어 있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당된다.

후위 큐에 대해서 Starvation(기아 현상) 가능성이 있다.

 

2) 타임 슬라이스 방식 (Time Slice)

전위 큐에 우선순위를 주지만, 조절해서 우선순위를 주는 방법이다.

각 큐에 CPU time을 적절한 비율로 할당한다. 이를 통해 전위 큐에 우선순위를 주면서 후위 큐에 Starvation을 방지할 수 있다.

ex) 80%는 전위 큐, 20%는 후위 큐

 

 

4. 멀티 레벨 피드백 큐(다단계 피드백 큐, Multi-Level Feedback Queue : MFQ)

앞선 멀티 레벨 큐와 동일하게 CPU는 1개지만 여러 Ready Queue로 줄 서는 것을 의미한다.

하지만, 프로세스가 다른 큐로 이동이 가능하다. 우선순위의 변화, 즉 재배치가 가능하다.

(반면, 앞선 멀티 레벨 큐는 한 번 정해진 우선순위의 변화가 없다.)

 

- 특징

구현 방식에 따라 상이하지만 아래와 같은 특징이 있다.

큐를 여러 개 둘 수 있고, 각각의 큐에 따라 스케줄링 알고리즘을 정할 수 있다.

또한, 각각의 프로세스를 상위 큐, 하위 큐로 보내는 기준을 지정할 수 있다. 

프로세스가 CPU를 사용하려 할 때, 들어갈 큐를 결정하는 기준을 지정할 수 있다.

aging과 같은 방식으로 구현이 가능하다.

 

[멀티 레벨 피드백 큐를 구현한 하나의 예시]

출처: 운영체제(이화여자대학교, 2017년 1학기 반효경)

멀티 레벨 피드백 큐 중 1가지를 구현한 예시이다.

단계별로 시간 할당량을 다르게 주는 방식이다.

어떤 프로세스든 CPU를 쓰러 들어오면 최고 우선순위 큐에 줄을 선다. 만약 첫 번째 큐에서 라운드 로빈 알고리즘을 사용하여 할당 시간(사진의 예시에서 8) 안에 CPU를 다 쓰면 쓰고 나간다. 반면 할당 시간 안에 다 쓰지 못하면 우선순위가 다음 순위로(사진의 예시에서 16) 하락한다.

 

---

 

그 외

 

1. 멀티 프로세서 스케줄링(Multi-Processor Scheduling)

CPU가 여러 개인 경우이다. 

복수의 CPU의 역량이 같은 경우(Homogeneous processor): Queue에 프로세스들을 한 줄로 세워서 빈 프로세스에서 처리하도록 할 수 있다. CPU가 알아서 대기 중인 프로세스를 꺼내가도록 할 수 있다.

ex. 여러 창구가 있고, 손님의 차례가 되면 비어있는 창구로 보낸다.

일부 CPU에 작업이 몰리는 것을 방지하기 위해 Load sharing(Load Balancing 이라고도 부른다.) 메커니즘을 고려한다. 예를 들어 CPU 별로 별개의 큐를 두는 방법과 모든 CPU에 대한 공동 큐를 사용하는 방법 등을 고려하는 것이다.

 

- 종류

1) 대칭형 다중 처리(Symmetric Multiprocessing, SMP)

각 CPU가 각자 알아서 스케줄링을 결정한다.

2) 비대칭형 다중 처리(Asyemmetric Multiprocessing)

하나의 CPU가 나머지 모든 CPU의 스케줄링과 데이터 접근을 책임지고 다른 모든 CPU들은 그것에 따른다.

 

 

2.  스레드 스케줄링(Thread Scheduling)

스레드란 1개의 CPU안에 수행 단위가 여러 개 있는 것을 일컫는다.

스레드를 구현하는 방식은 아래와 같이 2가지가 있다.

 

- 종류

1) Local Scheduling

유저 레벨 스레드의 경우 운영체제가 해당 스레드의 존재를 모른다. 사용자 프로세스가 직접 내부에 스레드를 여러 개 두고 있기 때문이다.

따라서 OS가 아닌 사용자 프로세스 CPU를 받았을 때 직접 어느 스레드한테 CPU를 줄 것인지 결정한다.

 

2) Global Scheduling

커널 레벨 스레드의 경우 운영체제가 스레드를 알고 있다. 따라서 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄 할지 결정한다. 즉, 운영체제가 스케줄링한다.

 

 

출처: 운영체제와 정보기술의 원리(반효경 저)

참고자료: 정보처리 자격증 취득을 위한 운영체제론(조영성, 박석규 공저)