[OS] CPU 스케쥴링

jh Seo·2025년 8월 16일

목록 보기

3/4

CPU 스케쥴링

운영체제의 CPU 스케쥴러는 READY 상태의 프로세스 중 어떤 프로세스에게
CPU를 할당할지 결정한다.
Dispatcher는 CPU 제어권을 CPU 스케쥴러에 의해 선택된 프로세스에게 넘긴다.
이를 Context Switching이라고한다.

장기 스케쥴링(Long Term)

가장 큰 틀에서 이뤄지는 CPU 스케쥴링이다.
고수준 스케쥴링, 작업 스케쥴링이라고도 함.
프로세스에 메모리 및 각종 자원을 주는 문제를 스케쥴링함.
전체 시스템 부하를 고려해 작업 요청을 승인할지, 거부할지 결정함.
new 상태의 프로세스를 admitted하는 작업을 함.
장기 스케쥴링 결정에 따라 시스템 내부의 프로세스의 총 갯수가 정해진다.
(degree of multiprogramming)
최근 운영체제에서는 장기 스케쥴러가 없다!
프로그램 실행시키면 바로 ready 상태에 돌입한다.

중기 스케쥴링(Medium term scheduler, Swapper)

장기 스케쥴링이 프로세스의 활성화 승인을 담당한다면, 중기 스케쥴링은 이미 활성화된 프로세스를 관리한다.
시스템 과부하를 막기위해 활성화된 프로세스들의 중지 여부를 결정해 활성화된 프로세스 수를 조절한다.
여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아내는 역할도 맡는다.(Swap out)
-> degree of multiprogramming을 조절한다.
중기 스케쥴링에 의해 중지된 프로세스들은 보류상태(stopped, suspended)가 된다.

단기 스케쥴링(short-term scheduler, CPU scheduler)

가장 작은 단위의 스케쥴링을 단기 스케쥴링이라고 한다.
어떤 프로세스에 CPU를 할당할 지(Running), 어떤 프로세스를 대기 상태(Wait)로 보낼지 결정한다.
단기 스케쥴러가 어떤 기준에 따라 프로세스를 선택하고,
어느 정도 자원을 배분할지 따라 시스템에 큰 영향을 끼친다.

CPU 스케쥴링의 목적

모든 프로세스가 적당히, 공평하게, 효율적으로 자원을 할당받도록 한다.

공평성
* 프로세스에게 자원 배분받는 과정이 공평해야한다.
효율성
* 시스템 자원이 쉬는 시간 없어야 함.(CPU의 여유시간 최대한 없도록)
안정성
* 중요 프로세스들은 우선권을 주어야한다. 프로세스가 증가해도 안정적으로 실행되어야한다.
확장성
* 시스템 자원이 늘어나는 경우, 이 혜택이 전체 시스템에 반영되어야한다.
반응 시간 보장
* 프로세스의 요구가 있을 경우, 적절 시간 내에 반응을 해야한다.
무한 연기 방지
* 특정 프로세스의 작업이 무한정 연기되면 안 된다!

스케쥴링 고려 사항

1. 선점형 스케쥴링과 비선점형 스케쥴링

어떤 프로세스가 CPU를 할당받을 때, 이를 운영체제가 강제로 회수할 수 있는지에 따라
선점형과 비선점형으로 나뉜다.

선점형 스케쥴링

운영체제가 필요하다고 판단되면 실행 상태의 프로세스 작업을 중단시키고 새로운 작업 시작한다.
보통 TIMEOUT 상황, I/O interrupt, System Call등 발생시 CPU 강제 회수 절차에 돌입한다.

이 과정에 의해 발생하는 Context Switching 으로 인한 오버헤드가 발생한다.
그러나 하나의 프로세스가 독점시, 멀티 태스킹을 못하므로 대부분 저수준 스케쥴러는 선점형 스케쥴러를 사용한다.

비선점형 스케쥴링

어떤 프로세스가 실행 상태에 들어가면 그 프로세스가 끝나거나 CPU를 자진 반납하는 경우가 아니라면 해당 프로세스가 CPU 점유한다.

Context Switching으로 인한 오버헤드도 없고, 스케쥴러가 할 일이 적어 효율적일수 있으나,
전체 시스템 처리율이 떨어진다.

2. 프로세스 우선 순위

커널 프로세스와 일반 프로세스

프로세스는 커널 프로세스와 일반 프로세스로 나뉘는 데, 커널 프로세스의 우선순위가 높다.

프로세스의 우선순위가 높다는 건?
=> 해당 프로세스가 더 빨리 자주 실행된다.

일반 프로세스끼리도 우선순위가 나뉜다.
워드 프로그램과 영상 프로그램이 동시 실행되었을 때, 우선순위가 같다면 영상이 끊기는 현상이 발생한다.

CPU Bound 프로세스와 I/O Bound 프로세스

프로세스에는 여러 상태가 존재한다.
실행 상태(Running)일때와 대기 상태(Ready)일때 실제 작업이 발생한다.

실행 상태는 CPU를 사용하는 상태이고,
대기 상태는 입출력 작업이 완료되기를 기다리는 작업이 이루어진다.

프로세스가 CPU를 사용하여 연산하는 구간을 CPU Burst ,
입출력 요청을 수행하고 완료되기를 기다리는 구간을 I/O Burst 라고한다.

CPU Bound 프로세스
CPU Burst가 상대적으로 많아 계산 작업이 위주인 프로세스 CPU를 할당받으면 주어진 시간을 다 쓸 가능성이 크다.
I/O Bound 프로세스
I/O 버스트가 상대적으로 많아 입출력 작업이 위주인 프로세스 CPU를 짧게 사용한 뒤
곧바로 I/O 작업을 요청하고 대기 상태로 전환되는 경우가 많다.

스케쥴링 관점에서는 I/O Bound 프로세스를 우선적으로 실행 상태로 옮기는 것이 더 효율적이다.
I/O Bound 프로세스는 CPU를 잠깐만 사용하고 즉시 I/O 요청으로 대기 상태로 전환되므로
CPU를 다른 프로세스에게 빠르게 넘길 수 있다.

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

전면 프로세스는 GUI를 사용하는 OS에서 화면 제일 앞에 놓인 프로세스를 의미한다.

전면 프로세스는 현재 입출력을 사용하는 프로세스이며 사용자와 상호작용이 가능하다.
후면 프로세스는 사용자와 상호작용 없는 프로세스다. 예시) 압축 프로그램 등

전면 프로세스는 사용자의 요구를 즉각 처리한다.
반면에 후면 프로세스는 상호작용이 없다.

-> 따라서 전면 프로세스의 우선순위가 높다.

CPU 스케쥴링의 성능 척도

시스템 입장에서의 성능 척도

시스템 입장에서의 성능 척도는 CPU를 쉬지않고 계속 실행하는 걸 뜻한다.

CPU Utilization (CPU 이용률)
전체 시간 중 CPU가 일한 시간의 비율
Throughput (처리량)
단위 시간당 처리량. 즉, 단위 시간당 프로세스를 몇개 완료했는 지 뜻한다.

사용자 입장에서 성능 척도

사용자 입장에서는 자신이 요청한 작업이 최대한 빨리 처리되는 것을 뜻한다.

Waiting Time (대기 시간)
프로세스가 Ready Queue에서 기다린 시간
Response Time (응답 시간)
프로세스가 최초로 CPU를 얻기까지 걸린 시간
Turnaround Time (소요 시간, 반환 시간)
프로세스가 처음 도착해서 끝나기까지 걸린 시간

CPU 스케쥴링 알고리즘

FCFS(First Come First Served) 스케쥴링

먼저 온 프로세스를 먼저 처리해주는 방식.
비선점형이다.
도착한 프로세스 순서에 따라 average-waiting time이 크게 달라진다.
먼저 온 프로세스의 cpu 할당이 오래걸리는 경우, 그 뒤 프로세스들이 다 기다려야한다.

SJF(Shortest Job First) 스케쥴링

FCFS 알고리즘을 개선한 방식
CPU를 가장 짧게 쓰는 프로세스에게 CPU를 먼저 할당한다.
waiting time 측면에서는 최적의 방법이다.
-> minimum average wating time 보장한다!
비선점형, 선점형 둘 다 가능하다.
* 비선점형 동작 방식은 프로세스가 CPU 할당받으면 CPU burst 완료될 때까지 CPU 소유한다.
- 선점형 동작 방식은 실행중인 프로세스의 남은 burst 타임보다
  새로 도착한 프로세스의 CPU burst타임이 더 짧은 경우 CPU를 새 프로세스에게 할당해준다.
단점
* Starvation
CPU burst 시간이 긴 프로세스는 영원히 CPU 를 못 가지는 경우가 생긴다.
- 프로세스의 CPU burst 타임을 정확히 계산할 수 없다.
  과거 CPU burst 시간을 가지고 예측 정도만 가능하다.

Priority 스케쥴링 (우선순위 스케쥴링)

프로세스에 우선순위 값을 설정해 스케쥴링하는 방식
SJF 방식도 CPU burst 시간에 우선순위를 매긴 방식이다!
-> 따라서 SJF스케쥴링도 우선순위 스케줄링에 포함된다
SJF처럼 비선점형, 선점형 모두 구현이 가능하다.
SJF처럼 starvation 문제가 생길 수 있다.
->aging이라는 기법으로 해결한다. 프로세스가 기다리는 시간이 늘어날 수록 우선순위를 높이는 방식이다.

RR(Round Robin) 스케쥴링

각 프료세스에 동일한 크기의 시간(time slice) 할당해줌
할당 시간이 지나면 프로세스의 CPU 제어 강제로 뺏고 Ready Queue 에 넣어준다.
이 방식은 n개의 프로세스가 ready Queue에 있고, time slice가 t일 때,
모든 프로세스는 (n-1)*t 이상 기다리지 않게한다.
Time Slice가 너무 커진다면 FCFS 알고리즘이 되어버리고,
너무 짧다면 context switching이 빈번히 일어나 오버헤드가 커진다.
Time Slice를 I/O Bound 프로세스의 CPU Burst 시간 정도로 잡게된다면 합리적이다.
보통 10ms~ 100ms 사이이다.
RR은 SJF보다 turnaround time(프로세스 끝날때까지 걸리는 시간)은 길지만,
Response time이 짧다. 따라서 interactive한 상황이면 장점이다!

Multilevel Queue

Ready Queue를 여러 개로 분할해 작업한다.
우선순위가 높은 큐에는 System 프로세스나 interactive 프로세스들을 삽입하고,
CPU Bound 프로세스의 경우 후순위 큐에 삽입한다.
각 큐마다 독립적인 스케쥴링 알고리즘을 적용해 효율성을 높인다.
Interactive 프로세스들이 많은 큐에는 RR 알고리즘을 적용하고,
Batch 프로세스들이 있는 큐에는 FCFS 알고리즘을 사용하는 식으로
각 프로세스의 성격에 맞게 처리한다.
각 큐들에 대한 스케쥴링이 필요하다!
-> 가장 우선순위 높은 큐부터 비워나가는 방식과 각 큐마다 CPU시간을 적절한 비율로 할당하는 경우가 존재한다.
-> 전자의 경우 우선순위 높은 프로세스부터 빠르게 처리 가능하지만,
Starvation 생길 위험이 있어 후자를 통해 보완하는 식이다.

Multilevel Feedback Queue
여러 큐로 나눈 점에서 Multilevel Queue와 동일하다.
다른 점은 프로세스가 다른 큐로 이동이 가능하다.
우선순위 낮은 큐에 있는 프로세스가 다른 큐로 이동가능하다는 점이 일종의 Aging 기법이다.
프로세스가 다른 큐로 이동하는 기준은 다양하다.