CPU 스케줄링 - 프로세스 우선순위 / 스케줄링 큐 / 선점형 · 비선점형 스케줄링 / 스케줄링 알고리즘

 

 

운영체제의 역할 중 하나인 CPU 스케줄링에 대해 알아보자.

 

 

---

 

✅ CPU 스케줄링이란?

 

모든 프로세스는 CPU를 필요로 한다.

또한 모든 프로세스는 CPU를 먼저 사용하고 싶어 한다.

 

이러한 프로세스들에게 공정하게 CPU를 할당하도록

CPU 자원을 배분하는 것을 CPU 스케줄링이라고 한다.

 

 

프로세스들에게 현명하게 CPU를 배분하지 못한다면

프로세스들이 무질서한 상태가 되는 등의 결과를 초래할 수 있다.

 

그렇기에 CPU 스케줄링은 컴퓨터 성능과도 직결될 수 있는 중요한 문제로 다루어진다.

 

 

 

---

 

✅ 프로세스 우선순위

 

단순하게 생각해본다면, CPU를 사용하고 싶어하는 프로세스들이

차례대로 돌아가며 CPU를 사용하게 하는 방법이 있다.

 

CPU를 사용하고 싶다고 먼저 어필한 프로세스부터

순서대로 번갈아 CPU를 사용하게 해주는 방법이다.

 

이는 합리적인 방법인 것 같지만, 좋은 방법은 아니다.

그 이유는 프로세스마다 우선순위가 다르기 때문이다.

 

 

우선순위가 높은 프로세스는 빨리 처리해야 하는 프로세스를 의미한다.

대부분 입출력 작업이 많은 프로세스가 우선순위가 높은 편이다.

 

그 이유에 대해서는 프로세스가 실행되는 과정을 생각해봐야 한다.

이는 이전 포스팅에서 어느정도 설명하였으니 참고해도 좋다.

 

프로세스 / 프로세스 실행 · 제어 · 상태

 

---

 

프로세스는 실행 상태와 대기 상태를 반복해가며 실행된다.

 

그리고 입출력 작업이 많은 프로세스는 보통 입출력 작업을 위한 대기 상태에 더 많이 머무르게 된다.

결론적으로, 입출력 작업이 많은 프로세스는 실질적으로 CPU를 비교적 덜 사용한다.

 

그렇다면 CPU를 많이 사용하는 프로세스가 우선순위가 더 높겠네?

라고 생각할 수 있지만 그 반대다.

 

CPU를 얼마 사용하지 않을 프로세스부터 빠르게 처리하고

CPU를 많이 사용할 프로세스에게 순위가 넘어간다.

(많이 사용할 예정인 녀석에게는 기다린만큼 더 오래 사용하게 해주는 느낌이다)

 

 

프로세스 1의 경우 CPU 집중 프로세스라고 하며,

프로세스 2는 입출력 집중 프로세스라고 한다.

 

결론적으로 입출력 집중 프로세스가 우선순위는 더 높다.

하지만 실질적으로 CPU를 더 오래 사용하는 것은 CPU 집중 프로세스라고 볼 수 있다.

 

 

이렇듯 모든 프로세스가 CPU를 공정하게 번갈아 사용하지는 않는다.

 

각각의 상황에 맞게끔 CPU를 배분하여 사용하며

이러한 프로세스 우선순위는 운영체제가 부여해준다.

 

또한 프로세스 우선순위는 PCB에 명시된다.

 

 

 

---

 

✅ 스케줄링 큐

 

PCB에 프로세스 우선순위가 명시되어 있다고는 하지만,

CPU를 사용할 프로세스를 찾기 위해 PCB를 뒤적거리는 것은 비효율적이다.

 

그리하여 운영체제는 프로세스들에게 '줄을 서서 기다릴 것'을 요구하며,

이 줄을 스케줄링 큐로 구현하고 관리한다.

 

*Queue 방식은 대부분 선입선출(FIFO) 자료 구조이지만,

스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없다.

 

 

이렇게 프로세스들을 줄 세워 놓고, 우선순위가 높은 프로세스는 차출되어 먼저 실행된다.

사람으로 따지면 줄을 서지 않는 VIP 취급을 받는다고 볼 수 있다.

 

 

사실 이는 CPU에만 국한되는 것이 아니고, 운영체제가 관리하는 대부분의 자원은 큐로 관리된다.

 

 

 

---

 

✅ 선점형 · 비선점형 스케줄링

 

스케줄링 방식은 선점형 · 비선점형으로 분류할 수 있다.

 

 

어떤 프로세스가 이미 CPU 자원을 사용하고 있는 상황에서,

정말 급하게 처리되어야 할 프로세스가 CPU 자원을 빼앗고자 할 수도 있다.

 

이러한 상황에서 운영체제가 할 수 있는 선택은 2가지다.

 

 

- 선점형 스케줄링

이미 CPU 자원을 사용중인 프로세스로부터 자원을 빼앗아 급한 프로세스에게 할당하는 방법

 

- 비선점형 스케줄링

아무리 급하더라도 이미 사용중인 프로세스의 작업이 끝날 때까지 기다리게 하는 방법

 

---

 

선점이란, '남보다 앞서서 차지함'을 의미한다.

선점형 스케줄링 방식은 어느 하나의 프로세스가 자원 사용을 독점할 수 없다고도 볼 수 있다.

 

프로세스가 할당받은 시간만큼 CPU 자원을 사용하고,

정해진 시간을 모두 소비하면 다음 순서의 프로세스가 CPU 자원 사용하는 방식은

사실 선점형 스케줄링 방식에 해당한다.

 

정해진 시간을 모두 소비하면 인터럽트가 발생하고,

운영체제가 CPU 자원을 빼앗아 다음 프로세스에게 할당한다고 볼 수 있기 때문이다.

 

그렇기에 대부분의 운영체제의 스케줄링 방식은 선점형 스케줄링 방식을 차용한다고 볼 수 있다.

 

 

 

반면, 비선점형 스케줄링 방식은 CPU 자원을 사용하고 있는 프로세스가 종료되거나

스스로 대기 상태에 접어들기 전까지 다른 프로세스가 선점할 수 없는데,

이는 곧 하나의 프로세스가 CPU 자원을 독점할 수 있다고도 볼 수 있다.

 

 

 

---

 

✅ CPU 스케줄링 알고리즘

 

운영체제마다 CPU 스케줄링을 적용하는 알고리즘이 다르고 그 종류도 매우 많다.

하지만 모든 CPU 스케줄링 알고리즘을 빠삭하게 암기해야 할 필요는 없다.

 

알고리즘은 '용어'가 아닌 '아이디어'에 가깝기 때문에,

작동 방식과 장단점 정도로 간단하게 알아보도록 하자.

 

---

 

● 선입 선처리 스케줄링

 

선입 선처리 스케줄링은 FCFS 스케줄링이라고도 불린다.

준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.

 

큐에 삽입되는 순서는 CPU를 먼저 요청한 순서이며,

단순하게 보면 가장 공정한 방식이라고 볼 수 있다.

 

하지만, A 프로세스가 500ms 동안 사용하고, B 프로세스가 2ms 사용할 예정이라면

B 프로세스 입장에서는 고작 2ms를 위해 500ms를 기다려야 하는 상황이 생긴다.

 

이를 호위 효과라고 하며, 어떻게 보면 비효율적인 방식이라고 볼 수도 있다.

 

 

 

---

 

● 최단 작업 우선 스케줄링

 

준비 큐에 삽입된 프로세스 중 CPU 자원 사용 시간이 짧은 프로세스부터 처리해주는 방식으로,

앞서 설명한 FCFS 스케줄링에 대비되는 방식이다.

 

최단 작업 우선 스케줄링은 SJF 스케줄링이라고도 불리우며,

기본적으로 비선점형 스케줄링 방식으로 분류된다.

 

 

 

---

 

● 라운드 로빈 스케줄링

 

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

타임 슬라이스란 각 프로세스마다 CPU를 사용할 수 있는 정해진 시간을 의미한다.

 

즉, FCFS 스케줄링 방식처럼 프로세스가 큐에 삽입된 순서대로 공정하게 CPU를 사용하지만,

정해진 타임 슬라이스 시간이 끝나면 큐의 맨 뒤로 밀려나 다시 줄을 서게되는 방식이다.

 

다음과 같은 환경을 가정하여 예를 들어보겠다.

- A 프로세스 CPU 사용 시간 : 11ms
- B 프로세스 CPU 사용 시간 : 7ms
- C 프로세스 CPU 사용 시간 : 3ms
- 타임 슬라이스 : 4ms

적용 결과 ↓
A : 4ms ▶ B : 4ms ▶ C : 3ms ▶ A : 4ms ▶ B : 3ms ▶ A : 3ms

 

 

 

---

 

● 최소 잔여 시간 우선 스케줄링

 

SRT 스케줄링이라고 불리우며, SJF + 라운드 로빈 방식이라고 볼 수 있다.

 

CPU를 최단 시간 사용할 프로세스부터 처리하되,

타임 슬라이스가 끝나면 남아있는 작업 시간이 가장 적은 프로세스에게 순서가 넘어간다.

 

 

 

---

 

● 우선순위 스케줄링

 

프로세스에게 우선순위를 부여하고, 높은 우선순위의 프로세스부터 실행되는 방식이다.

만약 우선순위가 같다면 FCFS 방식으로 스케줄링된다.

 

앞서 설명한 SJF, SRT 스케줄링도 우선순위 스케줄링에 포함된다고 볼 수 있다.

작업 시간이 짧기에 높은 우선순위를 부여받은 것이라 볼 수 있기 때문이다.

 

 

하지만 우선순위 스케줄링 방식은 근본적인 문제를 가지고 있다.

 

CPU 사용 시간이 짧아서 우선순위가 높은 프로세스가 끊임없이 밀려들어온다면,

우선순위가 제일 낮은 프로세스는 영영 처리되지 못할 수도 있는 것이다.

 

이를 기아 현상이라고 하며, 이를 해소하기 위해 에이징 기법을 적용하기도 한다.

에이징 기법이란, 초기에 우선순위를 낮게 배정받은 프로세스도

일정 시간이 지나면 우선순위를 조금씩 높여주는 기법이다.

 

 

 

---

 

● 다단계 큐 스케줄링

 

우선순위 스케줄링의 발전된 형태라고 볼 수 있다.

우선순위별로 준비 큐를 여러 개 사용하는 방식이다.

 

1개의 큐 안에서 프로세스 우선순위를 따져 실행하는 것이 아닌,

큐 단위로 우선순위가 나뉘어서 우선순위가 높은 큐부터 처리된다.

 

다단계 큐 스케줄링 방식은 큐마다 다른 스케줄링 알고리즘을 적용할 수도 있어

확장성이 높은 스케줄링 방식으로 볼 수 있다.

 

 

 

---

 

● 다단계 피드백 큐 스케줄링

 

직전에 설명한 다단계 큐 스케줄링의 발전된 형태이다.

다단계 큐 방식과 거의 동일하지만, 프로세스가 여러 큐 사이를 이동할 수 있다.

 

라운도 로빈 방식에서 설명한 타임 슬라이스가 적용될 때마다

CPU를 오래 사용하는 프로세스들은 우선순위가 낮은 큐로 이동되고

짧게 사용하는 프로세스들은 우선순위가 높은 큐로 이동된다.

 

 

다단계 피드백 큐 스케줄링은 구현이 복잡하다는 단점이 있지만,

가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.

 

 

 

---

 

 

 

CPU 스케줄링에 대해 알아보았다.

이론적인 내용이 많은 것 같지만, 막상 읽다보면 이해하기 어려운 내용은 없다.

 

 

*자료 출처 : [혼자 공부하는 컴퓨터 구조 + 운영체제] 서적 - 강민철 지음