운영체제 - 스케줄링

dobby·2025년 3월 3일

CS 운영체제

스케줄링의 목적

스케줄링의 주된 목적은 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것이다.

스케줄링 5가지 목적

공평성
모든 프로세스가 공평하게 실행되어야 한다.
특정 프로세스가 실행되지 않는 경우가 없도록 스케줄링해야 한다.
효율성
자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링해야 한다.
시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
안정성
우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
확장성
프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
또한 시스템 자원이 늘어나는 경우, 이 혜택이 시스템에 반영되게 해야 한다.
프로세스의 개수가 증가해도 성능에 갑작스러운 변화가 없어야 함을 의미한다.
반응 시간 보장
프로세스가 오랜 시간 응답이 없으면, 사용자는 시스템이 멈춘 것으로 보기 떄문에 일정 시간 내에 응답할 수 있도록 스케줄링 해야 한다.
무한 연기 방지
특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링 해야 한다.

스케줄링 단계

장기 스케줄링 (long-term scheduling)

잡 스케줄링 또는 승인 스케줄링 이라고도 한다.
준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다.

중기 스케줄링 (mid-term scheduling)

메모리에 로드된 프로세스 수를 동적으로 조절한다. (준비큐에 있는 프로세스 수)
메모리에 프로세스가 많이 로드되면 스왑 아웃(swap out) 해서 일부 프로세스를 통째로 저장 공간에 저장한다.
스왑 아웃된 프로세스는 중단 상태(suspened) 가 된다.

[중단 상태]

준비 상태에서 스왑 아웃된 중단된 준비 상태
대기 상태에서 스왑 아웃된 중단된 대기 상태

단기 스케줄링 (short-term scheduling)

준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘을 결정한다.
즉, 어떤 프로세스를 디스패치할지 결정하는데, 이를 CPU 스케줄링 이라고도 한다.

[스케줄링 단계]

[스케줄러 관점에서 스케줄링]

스케줄러가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치한다. 이때 스케줄링 알고리즘을 이용한다.
CPU에서 프로세스를 실행한다. 이때 프로세스는 실행 상태다.
프로세스 수행이 완료되면 프로세스를 종료한다.
일정 시간을 초과하면 인터럽트가 발생해 프로세스가 준비 큐로 들어가고, 준비 상태가 된다.
입출력 요청이 들어오면 인터럽트가 발생한다. 이때 프로세스는 대기 큐로 들어가고 대기 상태가 된다.
입출력이 완료되면 프로세스는 준비 큐로 들어간다.
fork()가 호출되면 자식 프로세스가 생성되고, 자식 프로세스는 준비 큐로 들어간다.

스왑 아웃 (swap out)
프로세스가 실행되려면 메모리에 로드되어야 한다.
그런데 메모리 공간보다 많은 프로세스가 로드되는 경우가 있을 수 있다.
이럴 때 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간(SSD와 같은 영역)에 옮겨 저장하는 것을 스왑 아웃이라고 한다.

스왑 인 (swap in)
스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 다시 메모리에 로드하는 것을 스왑 인이라고 한다.

스와핑 (swapping)
스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것을 스와핑이라고 한다.
스와핑하면 메모리 공간보다 많은 프로세스를 실행할 수 있다는 장점이 있다.

기아 상태가 무엇인가요?
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 의미합니다.

기아 상태를 어떻게 해결할 수 있나요?
오래 기다린 프로세스의 우선순위를 높여서 기아 상태를 해결할 수 있습니다.

CPU 스케줄링에 대해 설명해주세요.
CPU 스케줄링은 준비 큐에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할지 결정하는 것입니다.
여러 프로세스들이 번갈아가며 수행되는 시분할 시스템에서 각 프로세스들의 CPU 수행시간은 다 다릅니다.
어떤 프로세스는 CPU를 잡고 있는 시간이 길고, 어떤 프로세스는 굉장히 짧을 수 있습니다.
이런 경우에, CPU 스케줄링을 통해 프로세스들에게 CPU를 적절히 할당 해줘서 빠른 사용자 응답 시간을 제공하고, CPU와 I/O 장치의 효율을 높여줄 수 있습니다.

스케줄러의 종류는 무엇이 있나요?
1. 단기 스케줄러 (=CPU 스케줄러)
준비 상태의 프로세스 중에서 어떤 프로세스를 다음 번에 실행 상태로 만들 것인지를 결정합니다.

중기 스케줄러
너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우를 막기 위해, 프로세스를 동적으로 조절하기 위한 스케줄러입니다.
일부 프로세스를 메모리에서 디스크로 스왑 아웃시켜서 프로세스를 관리합니다.

장기 스케줄러 (=작업 스케줄러)
준비 큐로 보낼지 말지 결정하는 스케줄러입니다.
(현대에서는 프로세스가 시작되면 장기 스케줄러 없이 곧바로 프로세스에 메모리를 할당해 준비 큐에 넣습니다.)

스케줄링 알고리즘

스케줄링 알고리즘은 CPU 스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는 데 사용한다.

[스케줄링 기준 평가]

CPU 사용률: CPU를 놀리지 않고 사용하는지 판단
처리량: 단위 시간당 작업을 마친 프로세스 수
응답 시간: 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
반환 시간: 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간 (대기시간 + 실행시간)
대기 시간: 프로세스가 대기 큐에서 대기하는 시간의 총합

비선점형 스케줄링

실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다.
비선점형 스케줄링은 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적다.

그러나 CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다.

비선점형 스케줄링은 과거의 일괄 작업 시스템에서 사용하던 방식이다.

FCFS 스케줄링(First Come First Served)
준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘이다.
또한, 큐가 하나라 모든 프로세스의 우선순위가 동일하다.
FCFS 스케줄링 알고리즘은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어진다.
또한, 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다는 것이다.
SJF(Shortest Job First) 스케줄링
준비 큐에 있는 프로세스 중 실행 시간이 짧은(CPU를 점유하는 실행 시간) 프로세스가 우선순위를 갖는 알고리즘으로, 최단 작업 우선 스케줄링이라고도 한다.
SJF 스케줄링은 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다.
하지만 다음과 같은 이유로 사용하기 어렵다.
1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
2. SJF 알고리즘은 공평성에 위배된다.
평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.
두 가지 문제를 해결할 방법이 전혀 없는 것은 아니지만, 한계가 있기에 잘 사용하지 않는다.
HRN(Highest Response Ratio Next) 스케줄링
SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 한다.
HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식이다.

HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도, 대기 시간을 고려하여 아사 현상을 완화한다. 그러나 여전히 공평성이 위배되어 많이 사용되지 않는다.

선점형 스케줄링

스케줄러가 실행 중인 프로세스를 중단시키고, 다른 프로세스를 실행할 수 있음을 의미한다.
선점형 스케줄링은 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생긴다는 단점이 있다.

그러나 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다.

RR(Round Robin) 스케줄링
비선점형 스케줄링과 달리 프로세스 간 우선순위가 없는 가장 단순한 선점형 스케줄링 방식이다.
모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간을 초과하면 다른 프로세스를 실행한다.
콘텍스트 스위칭이 빈번하게 일어나서 오버헤드가 크다는 단점이 있지만, 모든 프로세스가 반복 수행되어 응답 속도가 빠르다는 장점도 있다.

[사용 사례]
- 네트워크 스위치의 패킷 전송: 네트워크 스위치는 여러 개의 입력 포트로부터 도착하는 패킷을 출력 포트로 전송해야 한다. 라운트 로빈 알고리즘은 입력 포트로부터 도착한 패킷을 순서대로 출력 포트로 전송하여 패킷 전송을 공정하게 처리하는 데 사용된다.
- 로드 밸런서: 로드 밸런서가 서버로 요청을 넘겨줄 때 라우팅 알고리즘을 사용해 요청을 넘겨줄 서버를 결정한다.
  가장 많이 사용되는 라우팅 알고리즘 중 하나로, 라운드 로빈 알고리즘이 있다.
  먼저 로드 밸런서가 들어오는 요청을 각 서버에 번갈아가며 보낸다. 이는 각 서버의 성능이 동일하고, 요청 처리 시간이 짧은 애플리케이션의 경우에 균등하게 분산할 수 있다는 장점이 있다.
로드밸런서는 특정 서버에 요청이 몰려 부하가 발생하는 것을 방지하기 위해 여러 서버에 트래픽을 분산시키는 장치 또는 소프트웨어다.
SRTF(Shortest Remaining Time First) 스케줄링
준비 큐에서 실행 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘으로, SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다.
최소 잔류 시간 우선 스케줄링이라고도 한다.
한 프로세스가 실행 중일 때, 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 된다.
평균 대기 시간이 짧다는 장점이 있지만, 수행 시간이 긴 프로세스는 기아 상태가 되기 쉽다.
그렇기에 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고, 아사 현상이 일어나기 때문에 잘 사용하지 않는다.
MLQ(Multi-Level Queue) 스케줄링
준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘으로, 다단계 큐 스케줄링이라고 한다.
분리한 큐는 각각 우선순위가 있고, 각자 다른 스케줄링 알고리즘을 적용할 수 있다.
다단계 큐에서는 우선순위에 따라 다단계로 나뉘며, 각각의 큐는 라운드 로빈으로 운영된다.
우선순위는 고정형 우선순위를 사용하며, 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없다.
여러 개의 큐는 foreground 큐와 background 큐로 나뉜다.
foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 중요시하는 프로세스가 들어간다.
MLFQ(Multi-Level Feedback Queue) 스케줄링
다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다.
다단계 큐 스케줄링이 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에 변화가 없는데 반해, 다단계 피드백 큐 스케줄링은 CPU를 사용한 후 프로세스의 우선순위가 낮아진다. CPU를 사용한 후의 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
물론 프로세스의 우선순위가 낮아진다고 할지라도 커널 프로세스와 일반 프로세스의 큐에 삽입되지는 않는다.

선점형 스케줄링과 비선점형 스케줄링의 차이가 무엇인가요?
선점형 스케줄링은 프로세스가 CPU를 계속 사용하기를 원하더라도 스케줄러가 실행 중인 프로세스를 중단시키고, 다른 프로세스를 실행할 수 있음을 의미합니다.
비선점형 스케줄링은 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미합니다.

선입선출 스케줄링(FCFS)에 대해 설명해주세요.
FCFS는 먼저 준비 큐에 도착한 프로세스 순서대로 CPU를 할당해 주는 스케줄링 방식입니다.
구현이 간단하지만, 만약 CPU 사용 시간이 매우 긴 프로세스가 먼저 도착한다면, 뒤이어 도착한 다수의 프로세스들이 긴 시간을 기다려야 한다는 단점이 있습니다.

최단 작업 우선 스케줄링(SJF)에 대해 설명해주세요.
SJF는 Shortest Job First라는 뜻으로, CPU 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당 하는 방식입니다.
평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있습니다.

최소 잔류 시간 우선 스케줄링(SRTF) 방식에 대해 설명해주세요.
SRTF 방식은 SJF의 선점 버전입니다.
현재 CPU에서 실행 중인 프로세스의 남은 CPU 실행 시간보다 더 짧은 CPU 실행 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗아 할당 해줍니다.
하지만 CPU 실행시간이 짧은 프로세스가 계속 도착한다면 CPU 실행 시간이 긴 프로세스는 영원히 CPU를 할당받지 못하는 기아 현상이 발생할 수 있습니다.

우선순위 스케줄링에 대해 설명해주세요.
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 방식입니다.
우선순위를 결정하는 방식에는 여러 가지가 있을 수 있습니다.
예를 들어 SJF 알고리즘처럼 CPU 버스트 시간을 기준으로 잡을 수 있습니다.
우선순위 스케줄링의 문제점 중 하나는 기아 현상이 발생할 수 있다는 점입니다.
우선순위가 낮은 프로세스가 계속 CPU를 할당받지 못할 수 있기 때문입니다.

라운드 로빈 스케줄링에 대해 설명해주세요.
라운드 로빈 방식에서는 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 타임 퀸텀(Time Slice, Time Quantum)으로 제한됩니다.
예를 들어, 한 프로세스가 타임 퀸텀만큼 CPU를 사용했다면, 타이머 인터럽트가 발생하고 준비큐에 줄 서있는 다른 프로세스에게 CPU를 할당합니다.
여러 프로세스들에게 빠른 시간안에 조금씩 CPU를 사용하게 해주는 방식이기 때문에 사용자에게 빠른 응답 시간을 제공해줄 수 있습니다.

멀티 레벨 큐 스케줄링에 대해 설명해주세요.
준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘으로, 다단계 큐 스케줄링이라고 합니다.
분리한 큐는 각각 우선순위가 있고, 각자 다른 스케줄링 알고리즘을 적용할 수 있습니다.
다단계 큐에서는 우선순위에 따라 다단계로 나뉘며, 각각의 큐는 라운드 로빈으로 운영됩니다.
우선순위는 고정형 우선순위를 사용하며, 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없습니다.
여러 개의 큐는 foreground 큐와 background 큐로 나뉩니다.
foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 중요시하는 프로세스가 들어갑니다.

멀티 레벨 피드백 큐 스케줄링에 대해 설명해주세요.
멀티 레벨 피드백 큐는 CPU 할당을 기다리는 프로세스들을 여러 개의 준비큐에 줄 세우는 방식입니다.
각 큐는 우선순위가 있으며, 어떤 프로세스가 CPU 할당을 받고 작업을 끝내지 못하면 CPU 작업 시간이 긴 프로세스로 간주하여 점점 우선순위가 낮은 큐로 이동시킵니다.
우선순위가 낮은 준비큐에서 너무 오래 기다린 프로세스에 대해서는 다시 우선순위가 높은 준비큐로 보내는 에이징 기법을 적용합니다.

전면 프로세스와 후면 프로세스

전면 프로세스는 GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다.
현재 엽력과 출력을 사용하는 프로세스이며, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 한다.

후면 프로세스는 사용자와 상호작용이 없는 프로세스다.

전면 프로세스는 사용자의 요구에 즉각 반응해야 하지만, 후면 프로세스는 상호작용이 없다.
따라서 전면 프로세스의 우선순위가 후면 프로세스보다 높다.
그만큼 후면 프로세스는 전면 프로세스보다 CPU를 할당받을 확률이 낮다.

작업 우선순위

작업의 중요도가 높아 우선순위가 높은 프로세스는 커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 프로세스다.
반대로 우선순위가 낮은 프로세스는 일반 프로세스, 후면 프로세스, 일괄 작업 프로세스, CPU 집중 프로세스다.

준비 상태의 다중 큐

준비 큐를 몇 개로 나눌지, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일은 스케줄링 알고리즘에 따라 달라진다.

고정 우선순위 방식은 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다.
시스템의 상황이 시시각각 변하는데 우선순위를 고정하면 시스템 변화에 대응하기 어려워 작업 효율이 떨어진다.

변동 우선순위 방식은 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.
이 방식은 구현하기 어렵지만 시스템의 효율성을 높일 수 있다.

대기 상태의 다중 큐

대기 상태에서도 다중 큐를 사용한다.
시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 대기 상태의 프로세스를 한 곳에 모아놓으면 관리하기가 불편하다.
따라서 시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다.

프로세스 제어 블록은 준비 상태의 다중 큐에 삽입되었다가 CPU 스케줄러에 의해 실행 상태로 옮겨지기 도 하고, 입출력 요청이 있으면 대기 상태의 다중 큐에 삽입되기도 한다.
그리고 입출력이 완료되면 다시 준비상태의 다중 큐로 이동하는데, 이러한 과정 전체를 CPU 스케줄러가 관리한다.