[OS] CPU 스케줄링

 

CPU 스케줄링

---

안녕하세요? 장장스입니다.

오늘은 CPU 스케줄링을 정리해 볼게요!

 

 

CPU 스케줄러

---

CPU 스케줄러는 준비(ready) 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드입니다.

 

그렇다면 CPU 스케줄러는 어떻게 작동할까요❓

 

프로세스가 CPU를 할당 받고 기계어 명령을 수행하다가 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출됩니다. 그러면 CPU 스케줄러는 준비 큐(ready queue)에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 됩니다.

 

위와 같은 경우 말고도 CPU 스케줄링이 필요한 다양한 경우들이 있습니다.

 

1. 실행(run)상태에 있던 프로세스가 I/O 요청 등에 의에 봉쇄(blocked)상태로 바뀌는 경우

2. 실행(run)상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비(ready)상태로 바뀌는 경우

3. I/O 요청으로 봉쇄(blocked)상태에 있던 프로세스가 I/O 작업이 완료되어 인터럽트가 발생하고 준비(ready)상태로 바뀌는 경우

4. CPU에서 실행(run)상태에 있는 프로세스가 종료되는 경우

 

 

비선점형(nonpreemptive) VS 선점형(preemptive) 

---

CPU 스케줄링 방식에는 2가지 방식이 있습니다.

 

비선점형 방식(nonpreemptive)은 CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗기지 않는 방법입니다.

 

선점형 방식(preemptive)은 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법입니다.

 

 

디스패처 (dispathcer) 

---

CPU 스케줄러가 다음 프로세스에게 CPU를 할당해야 할지 결정되면 실제로 CPU를 이양하는 작업이 필요합니다. 이러한 작업을 도와주는 운영체제의 코드를 디스패처(dispathcer)라고 합니다.

 

디스패처는 현재 수행중이던 프로세스의 문맥(context)을 PCB에 저장하고, 새로운 프로세스의 문맥(context)를 새로운 프로세스의 PCB로부터 복원 후 해당 프로세스에게 CPU를 넘기는 과정을 수행합니다.

 

 

스케줄링 알고리즘

---

(1) 선입선출 스케줄링 (FCFS) [비선점]

선입선출(First-Come First-Served) 스케줄링은 프로세스가 준비 큐에 도착한 순서대로 CPU를 할당하는 방식을 말한다.

 

먼저 온 요청을 먼저 처리하기 때문에 매우 합리적인 스케줄링 방식인 것 같지만 경우에 따라 비효율적인 결과를 초래하기도 한다. CPU 버스트가 긴CPU 사용 시간이 긴 작업) 프로세스 하나가 CPU 버스트가 짧은 프로세스 여러개보다 먼저 도착했다고 하자. 앞서 도착한 프로세스의 오랜 작업시간 동안 뒤에 있는 짧은 작업시간의 프로세스가 오랜 대기시간을 기다려야 하는 문제가 발생할 수 있다.

 

이처럼 FCFS 스케줄링 알고리즘은 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라 질 수 있다.

---

 

(2) 최단작업 우선 스케줄링 (SJF) [비선점][선점]

 

최단작업 우선(Shortest-Job First) 스케줄링 알고리즘은 CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 최단작업 우선 스케줄링(SJF)는 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.

 

비선점형 방식 구현은 현재 작업중인 프로세스가 CPU를 할당받아 작업중일 때 CPU 버스트가 짧은 요청이 새로 들어와도 해당 프로세스의 작업이 끝날 때까지 CPU를 반납하지 않는 방식이다.

 

선점형 방식 구현은 현재 작업중인 프로세스에게 CPU를 할당했다 하더라도 새로 들어온 요청의 CPU 버스트가 더 짧을 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식이다. 이러한 SJF의 선점형 구현방식을 SRTF(Shortest Remaining Time First)라고도 부른다.

 

SJF 스케줄링은 다음과 같은 문제점이 있다.

1. 프로세스의 CPU 버스트 시간을 미리 알 수 없다는 점

2. 기아 현상(starvation) 문제

CPU 버스트가 짧은 프로세스에게만 CPU를 할당하게 되면 CPU 버스트가 긴 프로세스는 준비 큐에 서서 무한정 기다리는 문제가 발생한다. 최악의 경우 영원히 CPU를 할당 받지 못할 수도 있다. 이는 SJF의 심각한 문제점이다.

---

 

(3) 우선순위 스케줄링 [비선점][선점]

우선순위(priority) 스케줄링이란 준비 큐에서 기다리는 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다. 우선순위는 우선순위값을 통해 결정되며 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.

 

현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점하게 되면 선점형 방식이 되고, 이와 달리 CPU를 자진 반납하기 까지 기다리게 되면 비선점형 방식이 된다.

 

우선순위 스케줄링에도 기아 현상(starvation) 문제가 발생한다. 이를 해결하기 위해 노화(aging) 기법을 사용할 수 있다. 대기 시간이 길어지는 프로세스의 우선순위를 조금씩 높여 CPU를 할당 받을 수 있게 해주는 것이다.

---

 

(4) 라운드 로빈 스케줄링 [선점]

라운드 로빈(Round Robin) 스케줄링은 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식이다.

각 프로세스가 CPU를 연속적으로 사용할 수 있는 특정 시간인 '할당시간(time quantum)'으로 제한하고,  할당시간이 경과되면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당하는 방식이다.

 

할당시간이 너무 짧으면 문맥교환(context switching)이 빈번하여 오버헤드가 커지고, 할당시간이 너무 길면 FCFS와 같은 결과가 나오게 된다. 즉, 적정 할당시간을 설정하는 것이 중요하다.

 

라운드 로빈 스케줄링은 대기 중인 모든 프로세스에게 CPU를 번갈아가며 할당할 수 있기에 대화형 프로세스의 빠른 응답시간을 보장할 수 있다는 장점이 있다.

---

 

(5) 멀티레벨 큐 [선점]

멀티레벨 큐(multi-level queue) 스케줄링은 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법을 말한다.

쉽게 말하면 CPU를 사용하기 위해 한 줄서기가 아니라 여러 줄로 서는 것이다.

 

일반적으로 멀티레벨 큐에서는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.

전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하는 반면, 응답시간이 중요하지 않은 후위 큐에서는 FCFS 스케줄링 기법을 사용해 문맥교환(context switching) 오버헤드를 줄인다.

 

멀티레벨 큐에는 또 다른 스케줄링이 필요하다. 바로 큐 자체에 대한 스케줄링이다. 우선순위가 높은 큐를 순서대로 처리하는 고정 우선순위(fixed priority) 방식이 있으며, 기아 현상(starvation)을 해결하기 위한 타임 슬라이스(time slice) 방식도 있다. 타임 슬라이스 방식은 각 큐에 CPU 시간을 적절한 비율로 할당하는 방법이다. 예를 들어 전위큐에 80% 후위 큐에 20%를 할당해 스케줄링하는 방식이다.

---

 

(6) 멀티레벨 피드백 큐 [선점]

멀티레벨 피드백 큐(Multilevel Feedback Queue)는 여러 큐에 줄을 세운다는 측면에서 멀티레벨 큐와 유사하나, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능하다는 점이 다르다.

 

그림에서 상위 2개의 큐는 각각 할당시간(Quantum)이 8과 16인 라운드 로빈 스케줄링을 사용한다. 세번 째 큐는 FCFS 스케줄링 기법을 사용한다.

 

1. 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. (할당시간 8)

2. CPU 사용시간이 짧은 프로세스는 작업이 완료되고, 작업이 완료되지 않은 프로세스들은 할당시간이 16인 두번째 큐로 내려가서 줄을 선다.

3. 두번째 큐에서도 작업이 완료 되지 않으면 계산 위주의 프로세스로 간주되어 최하위 큐로 이동하고 FCFS 스케줄링을 적용 받는다.

 

멀티레벨 피드백 큐는 상위 큐가 비었을 때 다음 하위 큐가 CPU를 할당 받는 구조이다. 이러한 방식은 라운드 로빈 스케줄링을 발전시켜 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하게 되고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 사용할 수 있게 한다.

---

 

(7) 다중처리기 스케줄링

현대의 CPU는 프로세스가 여러개인 다중처리기 시스템(multi-processor system)이다. 다중처리기 환경에서의 CPU 스케줄링은 CPU가 하나인 시스템보다 복잡한 문제가 된다.

 

1. 준비큐에 한줄로 세워 CPU가 알아서 프로세스를 꺼내어가도록 할 수 있다. 그러나 반드시 특정 CPU에서 수행되어야 하는 프로세스가 있는 경우라면 문제가 된다.

2. 각 CPU 별로 줄 세우기를 한다. 이러한 경우 특정 CPU에만 작업이 집중되는 현상이 발생할 수 있다. 따라서 다중 처리기 스케줄링에서는 이와 같은 현상을 방지하기 위한 부하균형(load balancing) 매커니즘을 필요로 한다.

---

 

(8) 실시간 스케줄링

실시간 시스템에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다. 

 

실시간 시스템은 데드라인(deadline)을 반드시 지켜야하는 경성 실시간 시스템과 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않는 연성 실시간 시스템이 있다.

 

실시간 환경에서의 스케줄링은 빠른 서비스도 중요하지만 데드라인을 지키는 것이 더욱 중요하다. 따라서 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용하게 된다.

 

 

 

 

Post

---

•  

References

---

• KOCW [운영체제] - 반효경 교수

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)