[운영체제] 스케쥴링(Scheduling) :: 개념과 종류

스케쥴링 Scheduling

 

간단히 말하면, 우선순위 정하는 것을 스케쥴링이라 한다.

연예인들이 많이 쓰는 표현이기도 하다.

 

같은 맥락에서, 컴퓨터에서는 중앙처리장치(CPU)가 작업(프로세스)을 어떤 순서로 처리할지 정하는 것을 말한다.

예컨대, 사람으로 치면 입이 하나이기 때문에 밥을 먼저 한입 먹고 반찬을 먹을지,

아니면 반찬을 먼저 먹고 밥을 먹을지 순서를 결정하는 것과 같다.(?)

 

 

---

~ 광고 타임 ~

---

 

 

 

종류

 

크게 선점(Preemptive)과 비선점(Non-Preemptive) 스케쥴링 기법으로 구분할 수 있다.

 

 

 

선점형 스케쥴링

 

여기서 선점은 자치한다는 의미다. 즉, 작업의 입장에서는 CPU를 자유롭게 차지할 수 있다.

이게 개인적으로 은근히 헷갈리는 용어였는데, 작업의 입장에서 생각하도록 하자.

 

다시 한 번, 선점은 경쟁을 허용하며 공유자원을 차지할 수 있다는 점을 기억하자.

 

 

1) SRT(Shortest Remaining Time)

 

작업 완료까지 가장 적은 시간을 가진 작업이 우선적으로 자원을 점유케하는 방식이다.

이는 평균 대기시간을 줄이기 위한 목적으로 고안되었다.

 

 

작업	남은시간	우선순위
A	100	3
B	50	2
C	10	1

C - B - A 순으로 스케쥴링이 된다.

 

 

 

---

~ 광고 타임 ~

---

 

 

작업	남은시간	우선순위
A	100	3 → 4
B	50	2 → 3
C	10	1 → 2
D	5	1

 

하지만 앞서 소개했듯이, 선점방식은 경쟁을 통해 자원을 차지할 수 있는 특징이 있다.

예컨대, 위와 같이 새로운 작업 D가 나타났다고 생각해보자.

 

선점 방식이기때문에 언제든 적자가 나타난다면 자원을 내어줘야 한다.

C가 먼저 작업 중이더라도 남은시간 6을 남겨둔 채로 D가 등장하면 C는 작업을 중단하게 된다.

 

결국 순서는 D - C - B - A가 될 것이다.

즉, 작업 A보다 남은시간이 적은 작업이 계속해서 들어온다면 끝까지 A는 실행되지 못할 수 있다.

 

이처럼 우선순위에 계속해서 밀리는 현상을 기아현상이라고 부른다.

 

그리고 기아현상을 해결하기 위한 방법엔 에이징(Aging) 기법이 있다.

에이징기법은 이름처럼, 작업에게 나이를 부여하는 방법이다.

이는 오래 기다린 작업을 연장자라 생각하고 우선순위를 높여주는 것이다.

 

 

 

2) 라운드로빈(Round Robin)

 

각 작업들에게 일할 시간을 주고, 시간내에 못끝내면 다음 순서로 넘기는 방식이다.

예컨대, 밥 한숟가락 먹고 김치먹고, 밥 한숟가락 먹고 고기 먹고, 고기먹고 밥먹고 등 골고루 먹을 수 있는 특징이 있다.

이는 하나의 공유자원(입)에 대해 여러 작업(밥, 고기, 김치)이 돌아가면서 시간을 할당받아 사용하기에 가능하다.

 

즉, 시간을 잘개 쪼갤 수록 동시에 진행된다고 느낄 수 있기때문에

실시간 시스템(Real time)에 어울리는 스케쥴링 기법이다.

 

 

하지만, 계속해서 숟가락 들었다가 젓가락 들었다가 해야되기 때문에 문맥교환(작업 교체)에 대한 오버헤드(Overhead)가 발생한다.

문맥교환과 오버헤드에 대한 포스팅은 링크를 참고하길 바란다.

 

 

 

---

~ 광고 타임 ~

---

 

 

 

비선점형 스케쥴링

 

비선점은 선점형과 다르게, 작업을 시작하면 누구의 방해도 받지않고 끝까지 자원을 사용하게 된다.

예컨대, 숟가락을 들고 밥을 한 숟가락 떳다면 밥그릇을 비울 때까지 밥만 먹는셈이다.

 

 

1) FCFS(First Come First Service) 또는 FIFO(First In First Out)

 

선입선출(先入先出) 방식으로, 큐(Queue) 자료구조와 같고 실제로 큐를 이용하여 스케쥴링 한다.

흔히 마트의 계산대로 비유하는데, 작업들은 새치기하지 못하며 들어온 순서대로 처리하게 된다.

 

 

작업	들어온 순서	남은시간	우선순위
A	1	100	1
B	2	50	2
C	3	10	3

 

위와 같이 남은시간에 관계없이 그냥 들어온 순서대로 처리하게 된다.

즉, 비효율적인 처리가 될 수도 있지만 오버헤드가 적으므로 상황에 따라선 효율적인 방법이 되기도 한다.

 

 

 

2) SJF(Shortest Job First)

 

SRT와 다르게, 가장 빨리 끝낼 수 있는 작업을 먼저 처리하는 방식이다.

 

작업	작업시간	우선순위
A	100	3
B	50	2
C	10	1

 

순서는 C - B - A 가 된다.

앞서 선점형 스케쥴링 기법인 SRT 스케쥴링과 SJF 스케쥴링 기법이 별 차이없어 보일 수 있다.

 

 

---

~ 광고 타임 ~

---

 

 

작업	남은시간	우선순위
A	100	3↑
B	50	2↑
C	10	1
D	5	2↑

 

이번에도 어김없이 D가 등장했다.

 

하지만, C가 작업중이라면 C는 끝까지 실행된다.

작업을 마친 후에 B - A - D 혹은 D가 중간에 추가된 형태로 스케쥴링이 완료될 것이다.

 

 

 

 

기타

 

어딜가나 예외는 존재한다.

예상했겠지만, 선점과 비선점을 고루 섞은 스케쥴링 기법이 있다.

 

 

1) 다단계 큐(Multi-level Queue)

 

여러 개의 큐(대기리스트)를 두어 각 큐마다 스케쥴링 기법을 적용하는 방법이다.

또한, 큐는 절대적인 우선순위가 부여된다.

 

 

큐	Q1	Q2	Q3
작업명	철수	아자르	삼겹살
	영희	무리뉴	육회
	길동	파브레가스	치킨

 

다단계 큐를 적용하면, 각각 큐는 제각각의 스케쥴링 기법을 적용할 수 있다는 의미다.

Q1은 FCFS, Q2는 SJF, Q3은 라운드 로빈 등이 가능하다.

 

하지만 Q1, Q2, Q3에 해당하는 각 큐 또한 우선순위를 갖고 있는데, 이에 대한 작업 이동은 불가능하다.

즉, Q1의 철수가 Q2로 넘어갈 수 없다는 의미다.

 

그리고 Q1이 Q2보다 우선순위가 높다고 가정할 때,

Q1에 작업이 들어온다면 Q2는 작업을 멈추고 Q1에게 자원 사용권한을 넘겨줘야한다.

일종의 VVIP인 셈이다.

 

 

 

---

~ 광고 타임 ~

---

 

 

2) 다단계 피드백 큐(Multi-level Feedback Queue)

 

다단계 큐와 유사하지만, 기능이 추가되었다.

바로, 작업이 큐를 이동할 수 있게 된 것이다.

 

 

 

 

 

끝.