1. 스케줄링이란

운영체제에서 말하는 스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업을 의미한다.

즉, 운영체제가 CPU의 자원을 어떤 프로세스에게 할당해줄 지 일정을 짜는 작업이다.
프로세스 간의 컨텍스트 스위칭 과정은 많은 자원 손실을 발생시키기 때문에, 이 일정을 어떻게 짰는지에 따라 CPU의 자원을 얼마나 효율적으로 사용하게 되는지가 결정된다.
한마디로, 스케줄링은 운영체제 입장에서 매우 중요한 과정이라고 할 수 있다.

프로세스는 생성되어 완료될 때까지 여러 종류의 스케줄링 과정을 거치게 되는데, 이러한 스케줄링의 종류에는 장기 스케줄링, 중기 스케줄링, 단기 스케줄링이 있다.

스케줄링 기준

• CPU 이용률(utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량 (throughput) : 단위 시간당 완료된 프로세스 수
• 총 처리 시간(turnaround time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간(준비큐에서 대기한 시간 + CPU에서 실행한 시간 + I/O 시간을 합한 시간)
• 대기 시간(waiting time) : 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합
• 응답 시간(response time) : 하나의 요청을 제출한 후 첫번째 응답이 나올때까지의 시간
  → CPU 이용률과 처리량을 최대화하고 총처리시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직하다.

2. Context Switching과 스케줄링이 필요한 이유

Context Switching은 CPU가 프로세스를 실행하기 위한 (프로세스에 대한)정보를 말한다.
자세히 말하면, Context는 현재 프로세스의 상태, 프로세스가 다음에 실행할 명령어(PC), 레지스터 값, 프로세스 번호 등의 정보를 담고 있으며 이는 운영체제의 PCB(Process Control Block)에 저장된다.

멀티프로세스 환경에서는 여러 프로세스가 동시에 실행된다.
이 환경에서는 필연적으로 프로세스 간 CPU 자원 할당 이동이 일어날 수 밖에 없다. 이 이동 과정을 Context Switching이라고 하며, CPU는 기존에 할당된 프로세스의 Context를 저장하고, 새로 자원을 할당할 프로세스의 Context로 교체하는 과정을 거치면서 자원을 새로운 프로세스에게 할당하게 된다.
여기서 주의해야할 점이 있다. Context Switching 중에는 CPU의 자원이 어떤 프로세스에게 할당된 상태가 아니기 때문에 CPU가 아무 일도 하지 못한다. 따라서 Context Switching 과정이 너무 자주 발생하면 오히려 CPU 성능이 떨어지게 된다.

위에서 말했듯, Context Switching 과정이 너무 자주 발생하면 오히려 CPU 성능이 떨어지게 된다.
이 말은 바로 Context Switching 과정을 쓸데없이 자주 반복하지 않도록 하고, 필요한 순간에 적절하게 하도록 하는 알고리즘이 필요하다는 뜻이다. 그리고 이 알고리즘을 사용하는 주체가 바로 운영체제 스케줄러다.

Context Switching 중에는 CPU의 자원이 어떤 프로세스에게 할당된 상태가 아니라고 했는데, 사실 할당이라는 단어를 썼지만 정확히는 프로세스가 점유중이지만 사용 중은 아닌 상태다. 특정 프로세스에 의해 CPU 자원이 점유되고는 있는데, Context Switching 중이기 때문에 실제로 사용되는 프로세스가 없는 상태인 것이다. CPU가 아무 일도 하지 못한다는 것은 결국 CPU 자원을 아무 프로세스도 사용하지 못한다는 말이고 이는 오버헤드가 발생되었다는 뜻이다.

3. 스케줄링의 종류

장기 스케줄링(작업 스케줄링, 상위 스케줄링)

어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 의미한다. 작업 스케줄러에 의해 수행된다.

중기 스케줄링

어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업을 의미한다. CPU를 할당받으려는 프로세스가 많을 경우, 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절한다.

단기 스케줄링(프로세서 스케줄링, 하위 스케줄링)

프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미한다. 프로세서 스케줄링 및 컨텍스트 스위칭은 프로세서 스케줄러에 의해 수행된다.

4. 프로세서 스케줄링 기법

비선점 스케줄링

• 어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료될 때까지 다른 프로세스가 강제로 CPU를 빼앗아 사용할 수 없는 스케줄링 기법이다.
• 즉, 프로세스가 CPU를 놓아주는 시점까지 스케줄링이 일어나지 않는다.
• 프로세스 응답 시간의 예측이 용이하며, 프로세스 일괄 처리에 적합하고 ContextSwitching을 최소화할 수 있다.
• 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있다.
  즉, 긴급히 처리되어야 할 프로세스가 처리되지 못할 수 있다.
• 비선점 스케줄링의 종류 : FCFS, SJF, 우선순위, HRN, 기한부 알고리즘

1) FCFS (First Come First Served)

• 프로세스가 Ready Queue에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다.
• 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법이다.
• 작업 완료 시간을 예측하기 용이하다.
• CPU 처리 시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있다.
  → 이를 콘보이 효과라고 한다.

• 콘보이 효과 : CPU를 매우 오래 사용하는 프로세스가 도착하게 되면, 다른 프로세스가 CPU를 사용하는 데 기다리는 대기 시간이 매우 커지는 현상

2) SJF (Shortest Job First)

• Ready Queue에 있는 프로세스 중 CPU 처리 시간이 짧은 순서대로 CPU를 할당하는 비선점형 방식이다.
• 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있다. → 콘보이 효과 완화
• 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식으로 알려져 있다.
• CPU 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어오면 Ready Queue에서 무한정 CPU를 기다려야 하는 상황이 발생할 수 있다.
  → 이를 기아(starvation) 현상이라고 한다.

• 기아(starvation) 현상 : 자신보다 우선순위가 높은 프로세스 때문에 오랫동안 CPU 할당을 받지 못하고 무한정 기다리는 현상

3) HRN(Highest Response Ratio Next)

• SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식이다.
• 우선순위를 단순히 CPU 처리 시간으로 결정하지 않고, Ready Queue에서 대기한 시간까지 고려하여 결정한다. -> aging 기법

• 노화(aging) 기법 : 기아현상을 해결하기 위한 기법으로 오랫동안 기다린 프로세스에게 기다린 시간에 비례하여 우선순위를 높여주는 기법

HRN 스케줄링 방식이 선점일 경우엔 우선순위가 높은 다른 프로세스들이 너무 자주 생기기 때문에 Context Switching이 너무 자주 발생한다. 이에 따라 스케줄러의 일이 너무 늘어나기 때문에 HRN 스케줄링 방식은 비선점 방식으로 이루어진다.

지금까지 설명만 읽어봤다면 FCFS 스케줄링 방식을 사용할 하등의 이유가 없는 것처럼 보인다. HRN 스케줄링 방식이 다른 비선점 스케줄링 방식에 비해 이상적으로 훨씬 우월해 보이기 때문이다. 그러나 실제로 SJF, HRN 등의 방식을 사용하기 어려운 이유가 있는데, 현실적인 상황에서는 프로세스마다 CPU 처리 시간이 얼마나 걸릴지 알 수 있는 방법이 없기 때문이다. 이는 SRT 스케줄링 방식에서도 동일하게 적용되는 부분이다.

4) 우선순위 (Priority)

• 대기중인 프로세스들에게 우선순위를 부여해 우선순위가 높은 프로세스에게 CPU를 먼저 할당한다.
  • 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄 된다.
• 대기시간이 늘어날수록 프로세스들의 우선순위를 증가시킨다. → 노화(aging) 기법, 기아 상태 방지
• 선점형이거나 또는 비선점형이 될 수 있다.
• 우선순위는 정적 혹은 동적으로 부여될 수 있다.
  • 동적으로 부여할 경우 구현이 복잡하고 오버헤드가 많다는 단점이 있으나, 시스템의 응답속도를 증가시킨다.
  • 정적의 경우는 이 반대다.

선점 스케줄링

• 하나의 프로세스가 CPU를 점유하고 있을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.
• 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
• 주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용된다.
• 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요하다.
• 프로세스 I/O 요청, I/O 응답, 인터럽트 발생, 작업 완료 등의 특별한 상황에서 스케줄링이 발생한다.
• 긴급히 처리되어야 할 프로세스를 처리할 수 있다는 장점이 있지만 비선점 스케줄링 방식에 비해 Context Switching이 자주 일어나 그에 따른 오버헤드가 커질 수 있다는 단점이 있다.
• 선점 스케줄링 종류 : 라운드로빈, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 알고리즘

• 인터럽트용 타이머 클록이란?
  하나의 시스템 내에서 동작하는 장치들을 감시하기 위해 주기적인 신호를 발생하는 것으로, 하나의 프로세스가 자원을 독점하기

1) SRT(Shortest Remaining Time)

• SJF 방식을 선점 스케줄링 방식으로 변경한 기법이다.
• CPU를 점유중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 기존 프로세스의 CPU 점유를 빼앗아 점유할 수 있다.
• 어떤 알고리즘보다 평균 대기 시간이 가장 짧은 알고리즘이지만, 기본적으로 선점형 방식이기 때문에 잦은 Context Switching이 일어나고 그에 따른 오버헤드가 커진다.
• starvation 현상이 더 심각하게 발생할 수 있다.
• CPU 의 예상 시간은 예측하기가 너무 힘들기 때문에 실제로 사용되기가 매우 어렵다.

2) 우선순위 (Priority)

SJF와 SRT의 관계와 마찬가지로 비선점 우선순위 스케줄링 방식의 선점 방식인 선점 우선순위 스케줄링 방식이 있다

3) 라운드 로빈(Round Robin)

• FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식이다.
• 프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 그 시간 동안만 CPU를 이용하게 한다.
• 어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나면 이 프로세스로부터 CPU 자원을 회수하고, 이 프로세스를 Ready Queue의 가장 뒤로 보내는 것이다.
• 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 큰 장점이 있다.
  자연스럽게 콘보이 효과 역시 줄어든다.
• 적당한 Time Quantum을 설정하는 것이 중요하다.
  • 크면 CPU 처리 시간이 긴 프로세스가 CPU를 오래 점유하며 정작 다른 프로세스들은 이 프로세스의 작업이 끝날 때까지 기다려야 하기 때문에 결국 FCFS 스케줄링 방식에서 발생하던 콘보이 효과가 또 발생한다.
  • 작으면 잦은 Context Switching으로 오버헤드가 상당히 커진다.
  • 보통 10-100ms로 설정한다.

6) 다단계 큐(Multi-Level Queue)

• 프로세스를 어떤 프로세스냐에 따라 여러 종류의 그룹으로 나누고, 그룹마다 Queue를 두는 방식이다. 한 마디로 Ready Queue를 여러 개로 나누어 사용하는 방식이다.
• 각각의 Queue마다 서로 다른 스케줄링 방식을 적용할 수도 있다.
• 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되어야 다음 우선순위 큐가 실행될 수 있다.
• 한 번 우선순위가 매겨져 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다. 즉, 큐들 사이를 이동할 수 없다.
• starvation 현상과 공평성 문제가 있다.

이 방식에 대해 이해하려면 먼저 Foreground Queue와 Background Queue에 대해 알고가야 한다.

운영체제는 프로세스를 분류할 때 사용자와 직접 상호작용하는 프로세스와 백그라운드에서 돌아가는 프로세스의 중요도를 다르게 분류한다. 사용자와 직접 상호작용하는 프로세스는 빠르게 처리되어야 하고, 백그라운드에서 일괄 처리되는 프로세스의 경우 덜 빠르게 처리되어도 괜찮다고 분류하는 것이다.
사람들은 대부분 지금 내가 보고 있는 프로세스와의 상호작용이 빠르게 처리되기를 바라지 일단 켜두고 오래 방치한 프로세스와 상호작용하느라 내가 보고 있는 프로세스에 렉이 걸리는 상황을 바라지 않는다.

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

위 사진을 예로 들면,
대화형 프로세스를 담기 위한 Foreground Queue에는 라운드로빈 스케줄링 방식을 적용하고, 프로세스 일괄 처리가 필요한 Background Queue에는 일괄 처리에 적합하다고 했던 비선점 방식 중 하나를 적용하면 될 것이다.

다만 다단계 큐 스케줄링 방식은 여러개의 Queue를 사용하기 때문에 고려해야 할 점이 하나 더 생긴다.
바로 어떤 Queue에 얼마나 CPU를 오래 할당할 지 결정하는 스케줄링이 필요하게 된다. 이 스케줄링은 크게 두 가지 정도를 떠올릴 수 있다.

• 고정 우선순위 (Fixed Priority)
  Queue마다 우선순위를 두는 방식이다. 우선순위가 높은 Queue에 처리해야 할 프로세스가 남아있다면, 무조건 그 Queue에 남아있는 프로세스를 처리한 뒤에 다음 우선순위의 Queue를 서비스한다. 이 방식은 사용자가 직접 원하는 프로세스에 CPU 자원을 우선 할당하기 때문에 좋아보이지만 SJF 스케줄링 방식처럼 결국 우선순위가 낮은 Queue에 있는 프로세스는 무한정 기다려야 하는 상황 즉, 기아 상태가 발생할 수 있다.

• 타임 슬라이스 (Time Slice)
  고정 우선순위 스케줄링 방식에서 기아 상태가 발생할 수 있기 때문에 이를 해결하고자 생긴 스케줄링 방식이다. 운영체제가 Time Slice를 두고, 이 시간 비율에 따라 각각의 Queue를 서비스하게 된다. 예를 들어, CPU 자원의 75%는 Foreground Queue, 25%는 Background Queue를 서비스하는 데 할당할 수 있다.

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

• 다단계 피드백 큐 스케줄링 방식은 다단계 큐 스케줄링 방식에 에이징 기법을 적용한 방식이다.
• 우선순위가 변동되기 때문에 큐 사이의 이동이 가능하다.
  • 우선순위 👍 : 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스의 우선순위를 점점 올려서 우선순위가 높은 큐로 옮겨준다. -> starvation을 예방
  • 우선순위 👎 : 한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아져 더 낮은 큐로 이동하게 된다.
• 우선순위가 높은 큐보다 낮은 큐에 타임 슬라이스 크기를 크게 준다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함이다.
• I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.(통상적으로 짧은 CPU 버스트가 특징이다.)

결론

우리는 컴퓨터를 사용할 때 수많은 프로세스를 동시에 실행하게 된다. CPU는 한 번에 한 가지 작업만 처리할 수 있기 때문에, 이 프로세스들을 동시에 처리하(는 것처럼 보이게 하)기 위해 CPU는 어떤 프로세스에게 얼마나 많은 자원을, 얼마나 긴 시간동안 할당해야 할 지 결정해야 한다. 프로세스를 빠르게 번갈아 처리해서 마치 동시에 프로세스가 실행되는 것처럼 보이게 하기 위해서다. 이를 결정하기 위한 방식 즉, CPU 스케줄링 방식은 비선점, 선점 방식으로 분류할 수 있는 수많은 방식이 존재한다.

멀티스레드의 스케줄링은 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응할 수 있어야 한다.
그러나 CPU 스케줄링은 멀티스레드와 다르게 운영체제가 사용자도 모르는 사이 자동으로 진행하는 작업이다.

참고

https://velog.io/@jehjong/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%99%80-%EC%A0%95%EB%B3%B4%EA%B8%B0%EC%88%A0%EC%9D%98-%EC%9B%90%EB%A6%AC-2%EC%9E%A5.-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B0%9C%EC%9A%94
https://bnzn2426.tistory.com/65
https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html
https://coding-factory.tistory.com/309
https://velog.io/@raejoonee/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%9D%98-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81