운영체제의 CPU 스케줄링 알고리즘 (선점 / 비선점)

오늘은 정처기 단골 출제 문제인 CPU 스케줄링 알고리즘에 대해 포스팅해볼까 한다. 전에 정처기 공부할 땐 단순 암기를 했었기 때문에 외운 것들이 서로 연결되는 느낌은 없었다. 근데 스케줄링의 필요성에 대해 이해하게 되니까 외운 것들이 서로 연결되어 크고 단단하게 뭉쳐진 느낌이 든다. 그럼 스타트.

 

📌 keypoint. 'Context Switching'

 

스케줄링(Scheduling)?

: 프로세스가 생성되어 실행될 때 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업.

 

운영체제가 CPU의 자원을 어떤 프로세스에게 할당해 줄 지 그 일정을 짜는 것이라고 이해하면 쉽다. 이 일정을 어떻게 짰는지에 따라 CPU의 자원을 효율적으로 사용할 수 있게 된다. 

 

Context Switching?

: CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트(Interrupt) 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때, 기존 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터값(Context)를 교체하는 작업을 Context Switching이라고 한다.

 

🔎 Context를 좀 더 자세히 알아보자.

 

OS에서 Context는 CPU가 프로세스를 실행하기 위한 해당 프로세스의 정보들이다. 이 Context는 프로세스의 PCB(Proceess Control Block)에 저장된다. 그래서 Context Switching때 PCB의 정보를 읽어 CPU가 전에 프로세스가 일 하던거에 이어서 수행이 가능하다.

 

✔ PCB(Process Control Block)의 저장 정보

1. 프로세스 상태 : 생성, 준비, 수행, 대기, 중지
2. 프로그램 카운터 : 프로세스가 다음에 실행 할 명령어 주소
3. 레지스터 : 누산기, 스택, 색인 레지스터
4. 프로세스 번호

Context Switching은 즉, 'Context(프로세스에 대한 정보)를 Switching(교체, 전환)'하는 행위이다.

*참고. Context Switching때 해당 CPU는 아무런 일을 하지 못한다. ( = CPU 자원을 아무 프로세스도 점유하지 못함. )그래서 Context Switching이 잦아지면 오히려 오버헤드가 발생해 효율(성능)이 떨어진다.

 

스케줄링과 컨텍스트 스위칭의 정의를 알아봤으니 이제 CPU 스케줄링 알고리즘에 대해 알아보도록 하자. 그전에 CPU 스케줄링을 왜 해야하는 걸까? 이 질문에 대한 답을 찾기 위해 운영체제로 올라가본다. 운영체제라는 건 컴퓨터가 효율적으로 일을 하게 만들기 위한 시스템이다. 그런데 Context Swiching이 자주 발생하게 되면* 오히려 CPU 성능이 떨어지게 된다. 즉, Context Switching 과정을 자주 반복하지 않고 필요한 순간에 적절히 Switching하도록 하는 알고리즘이 필요하다. 

 

 

🔎 스케줄링 알고리즘의 종류

 

자원을 할당해달라고 하는 프로세스는 굉장히 많을 텐데 어떤 기준으로 자원이 할당되는 걸까? 이 우선순위를 결정하는 방법은 크게 '비선점(non-preemptive)'과 '선점(preemptive)'으로 분류할 수 있다.

 

 

비선점 스케줄링

: 이미 한 프로세스에 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법.

 

프로세스가 CPU를 놓아주는 시점까지 스케줄링이 일어나지 않기 때문에 응답시간 예측이 편하며, 일괄 처리 방식에 적합하다. 하지만 긴급하게 처리되어야 할 프로세스가 우선순위로 처리되지 못할 수 있다.

 

✔ 비선점 스케줄링 종류

1. FCFS (First Come First Serve Scheduling)
2. SJF (Shortest Job First)
3. HRN (Highest Response Ratio Next)
4. 우선순위 (Priority)
5. 기한부 (Deadline)

 

➕ 선입 선처리 스케줄링 (FCFS, First-Come-First-Served)

 

프로세스가 Ready Queue에 도착한 순서대로 CPU에 할당하는 방식이다. P1(24ms), P2(3ms), P3(3ms) 프로세스가 있다 가정하면, CPU 스케줄링의 결과는 다음과 같이 표현된다.

가장 간단한 방식이지만, 평균 대기 시간(average waiting time) 을 생각해보자, (p1(0) + p2(24) + p3(27)) / 3 = 17ms.
p3 가 priority 가 가장 높은 프로세스였다면 의미 없는 대기 시간을 기다려야만한다. 이런 식으로 다른 모든 프로세스들이 한 프로세스가 끝날때까지 기다리는 현상을 호위 상태(Convoy Effect; 콘보이 이펙트)라고 한다.

 

 

➕ 최소 작업 우선 스케줄링 (SJF, Short Job First)

 

프로세스를 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다. 주로 평균 응답 시간을 최소화하기 위해 사용한다. 그러나 CPU 처리 시간이 긴 프로세스는 계속 Ready Queue의 뒤로 밀려나기 때문에 무한 대기 현상이 발생할 수 있다. 이 상태를 기아 상태(Starvation; 스타베이션)이라고 한다. (FCFS의 Convoy Effect를 완화하려고 했더니 Starvation 발생,,? )

 

SFJ는 이론만 들어보면 꽤 좋은 스케줄링 같지만, 다음과 같은 이유로 현실적으로 사용하기 힘들다.

1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
: 현재 운영체제에서는 프로세스의 작업길이를 추정하는 게 어렵다.

2. 공평성이 부족하다.
: p1이 ready queue에서 작업을 기다리고 있는데 p1보다 작업 시간이 적은 p2, p3 .. 들이 계속 들어온다면 p1은 작업을 시작할 수 없다. (Starvation 현상)

위와 같은 문제들을 해결할 수 있는 방법으로 1. 미리 실행 시간을 고지하거나 2. 에이징 기법을 사용할 수 있는데 미리 실행 시간을 알려주는 방식도 한계가 있고, 나이를 먹게하는 aging값을 어떤 기준으로 정할건 지 등의 문제도 있어 잘 사용하지 않는다.

 

➕ HRN (Highest Response Ratio Next)

SJF 스케줄링 방식에서 발생하는 긴 작업과 짧은 작업간의 지나친 불평등을 완화 하기 위해 나온 기법이다. 우선 순위를 ((대기 시간 + CPU 처리 시간) / CPU처리 시간)으로 결정한다. 이 처럼 기다린 시간에 비례하여 우선순위를 높이는 기법은 에이징(Aging) 기법이라고 한다. 하지만 이 스케줄링 또한 프로세스마다 CPU처리 시간이 얼마나 걸릴지 알 수 없기 때문에 현실적으로 사용하기가 어렵다.

 

➕ 우선순위(Priority)

각 프로세스 별로 우선순위가 주어지고, 우선순위에 따라 CPU를 할당하는 스케줄링 기법이다. 선점형으로도 구현할 수 있으며 우선순위가 높은 작업이 계속적으로 들어오게 될 경우 기아현상(Starvation)이 발생하기 때문에 여기서도 Aging기법을 사용한다. 동일한 우선 순위일 경우는 FCFS 스케줄링으로 처리한다. 우선순위는 정적 혹은 동적으로 부여될 수 있으며, 동적으로 부여될 경우 구현이 복잡하고 오버헤드가 많다는 단점이 있지만 시스템의 응답속도는 증가한다. 정적의 경우는 이 반대이다.

 

➕ 기한부(Deadline)

작업을 명시된 시간이나 기한 내에 완료하도록 하는 스케줄링이다. 특히 리눅스와 같은 멀티태스킹 운영체제에서 'Realtime Schedular'는 모든 실시간 작업들이 deadline 안에 끝나는 것을 보장해야 하는데 이러한 요구사항을 만족시키기 위해서 리눅스에서 'POSIX Realtime Scheddular'와 지금 설명하고 있는 'Deadline Schedular'를 제공한다.

 

선점 스케줄링

: 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식.

 

✔ 선점 스케줄링 종류

1. 라운드로빈 (Round-Robin)
2. SRT (Shortest Remaining Time)
3. 우선순위 (Priority) 
4. 다단계 큐 (Multi-Level Queue)
5. 다단계 피드백 큐 (Multi-Level Feedback Queue)

프로세스의 I/O 요청, I/O 응답, Interrupt 발생, 작업 완료 등 특별한 상황에 선점형 스케줄링이 발생한다. 긴급히 처리되어야 할 프로세스를 처리할 수 있다는 장점이 있지만 처리 시간을 예측하기 힘들고 비선점형과 비교 했을 때 상대적으로 Context Switching이 더 일어날 수 있다.

 

➕ 라운드로빈 (Round-Robin)

 

FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Slice(Time Quantum이라고도 함.)개념을 추가한 방식이다. 각 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 두고 (Time Slice or Time Quantum) 프로세스가 CPU를 사용한 시간이 Time Slice만큼 지나면, 이 프로세스로부터 CPU를 회수하고 Ready Queue의 가장 뒤로 보낸다.

 

CPU처리 시간을 계산하지 않아도 되고 우선순위도 없기때문에 매우 공편한 방식이다. 하지만, Time Slice를 너무 크게 잡을 경우 프로세스 처리 시간이 길어 CPU의 효율성이 떨어질 수 있다. 또, 타임 슬라이스를 무한대로 두면 FCFS 스케줄링과 다를 바 없어진다. (Convoy Effec 발생) 그렇다고 Time Slice를 너무 작게 잡으면 Context Switching이 자주 발생하여 오버헤드가 커진다.

 

➕ SRT (Shortest Remaining Time)

SJF를 선점 스케줄링 방식으로 변경한 기법이다. CPU를 점유 중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 기존 프로세스의 CPU점유를 빼앗아 점유한다. 단점은, SJF의 단점과 동일하게 Starvation 현상이 발생할 수 있고 선점형 방식이기 때문에 잦은 Context Switching이 일어날 수 있다.

 

➕ 우선순위 (Priority) 

프로세스의 중요도에 따라 우선순위를 반영한 알고리즘으로, 비선점형 우선순위 스케줄링을 선점 스케줄링으로 변경한 기법이라고 이해하면 된다.

 

➕ 다단계 큐 (Multi-Level Queue)

프로세스를 여러 종류의 그룹으로 나누고 그 그룹마다 Queue를 두는 방식이다. 각 Queue마다 서로 다른 스케줄링 방식을 적용할 수 있는데 이 방식에 대해 이해하려면 먼저 Foreground Queue와 Background Queue에 대해서 알아야 한다.

 

운영체제는 사용자와 직접 상호작용 하는 프로세스의 중요도는 높게 분류 하고, 일괄 처리 해도 되는 프로세스는 전자에 비해 중요도를 낮게 둔다. 왜냐면 사람들은 지금 내가 보고 있는 프로세스와 상호작용이 빠르게 처리되기를 바라지 켜두고 오래 방치한 프로세스와 상호작용 하느라고 내가 보고 있는 프로세스에 렉이 걸리는 상황을 바라지 않기 때문이다.

 

그래서 보통 사용자와 직접 상호작용하는 프로세스가 모인 Foreground Queue에는 응답 시간을 줄이기 위해 라운드로빈 스케줄링 방식을 적용하고, 백그라운드에서 돌아가는 프로세스가 보인 Background Queue에는 응답시간이 보통 큰 의미가 없기 때문에 FCFS 스케줄링 방식을 적용한다. 이처럼 각 Queue 마다 운영체제가 가장 적절하다고 판단하는 방식을 사용한다.

 

다단계 큐 스케줄링의 우선순위는 우선순위가 높은 Queue의 프로세스 처리가 다 끝나야만 다음 우선순위의 Queue를 서비스 하는 '고정형 우선순위(Fixed Prority)'를 사용한다. 그렇기 때문에 우선순위가 높은 프로세스의 처리시간이 오래 걸린다면 우선순위가 낮은 프로세스의 작업이 무한 연기될 수 있다. 이러한 문제를 해결하기 위해 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)이 제안되었다. 

 

*다단계 피드백 큐 스케줄링 설명으로 넘어가기 전에, '고정형 우선순위'인데 왜 '선점형'? 이라는 의문이 드는 나같은 분들을 위해 설명을 덧붙이면 하나의 Queue에서는 선점형 방식으로 프로세스들이 Time Slice를 할당 받아 작업이 진행되지만, Queue들 끼리는 비선점형 방식으로 상위 Queue에서 프로세스들이 실행이 완료되기 전까지는 하위가 실행될 수 없다.

 

➕ 다단계 피드백 큐 (Multi-Level Feedback Queue)

위에서 언급한대로, 다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스가 무한정 대기상태를 할 수 있는 문제점을 보완한 방식이다. 다단계 큐 스케줄링과 기본적인 형태는 같기때문에 우선순위를 가진 여러 개의 큐를 사용한다는 점은 같다. 다른점은, CPU를 사용하고 난 프로세스는 우선순위를 하나 낮춰 원래 Queue로 돌아가지 않고 우선순위가 하나 낮은 Queue의 끝으로 들어간다. 

 

결국 다단계 피드백 큐 스케줄링에서 가장 우선순위가 낮은 프로세스는 무한대의 Time Slice를 얻는다. 때문에 가장 마지막 Queue는 FCFS 스케줄링 방식을 사용한다. 다단계 피드백 큐 스케줄링은 오늘날 운영체제가 CPU의 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다. Unix에서 Time Slice를 고정하지 않고(=고정 우선순위를 사용하지 않고.) 10~200ms 사이에서 조정할 수 있도록 한 이유는 바로 다단계 피드백 큐 스케줄링을 사용하기 때문이다.

 

References

https://jeong-pro.tistory.com/93
https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-6%ED%8E%B8-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%813-%EC%84%A0%EC%A0%90%ED%98%95-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Round-Robin-SRT-%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%EB%B0%A9%EC%8B%9D-Multilevel-Queue

https://eun-jeong.tistory.com/17