[OS]CPU 스케줄링이란?

Legday_Dev·2024년 3월 25일

OS cpu

CS

목록 보기

12/13

CPU Scheduling 이란 OS가 프로세스에 합리적으로 CPU 자원을 할당하는 정책을 만드는 것을 말한다. 즉, CPU 를 잘 사용하기 위해 프로세스를 배정하는 것이다.

스케줄링

CPU 스케줄링은 멀티태스킹을 위해 OS가 CPU의 가동시간을 적절히 나누어 프로세스에게 사용시간을 분배한다.
스케줄링의 조건은 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓ 이다.
이 때, 시스템과 사용자의 입장에서 CPU 성능에 대한 척도가 다를 수 있다.
1. 시스템 입장에서의 성능 척도 : CPU 사용률(CPU Utilization), 처리량(Throughput)
2. 사용자 입장에서의 성능 척도 : 대기시간(Wating Time), 응답시간(Response Time), 반환시간(Turnaround Time)
즉, 시스템 입장에서는 CPU 를 쉬지않고 최대한 많이 기동시키는 것이 중요하고, 사용자 입장에서는 요청한 작업이 빨리 처리되는 것이 중요하므로 각 상황에 맞게 CPU 스케줄링을 설계해야 한다.
위 처럼 스케줄링 방식에 따라 선점형과 비선점형으로 나누어진다.

선점형 스케줄링

OS가 CPU의 사용권을 선점한다. 즉, 강제 회수하는 경우이다(처리시간 예측이 어렵다.)
상황에 따라, OS가 필요하다고 판단하면 실행중인 프로세스를 중단하고 다른 프로세스에게 CPU를 할당하여 실행한다.
컨텍스트 스위칭 과정에서 오버헤드가 발생할 수 있다.

비선점형 스케줄링

프로세스 종료 등의 이벤트가 있을 때 까지 CPU를 점유하기 때문에 실행이 보장된다(처리시간 예측이 쉽다.)
컨텍스트 스위치 과정에 오버헤드가 없지만 전체 시스템의 처리율이 떨어질 수 있다.

프로세스 상태

선점 스케줄링 : Interrup, I/O or Event Completion, I/O or Event Wait, Exit
비선점 스케줄링 : I/O or Event Wait, Exit

프로세스 상태 전이

승인(Admitted)
- 프로세스 생성이 가능하여 승인됨
스케줄러 디스패치(Scheduler Dispatch)
- 준비 상태에 있는 프로세스 중 하나를 선택하여 실행
인터럽트(Interrupt)
- 예외, 입출력 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리
입출력 or 이벤트대기(I/O or Event wait)
- 실행 중인 프로세스 입출력/이벤트가 모두 끝날 때까지 대기상태로 만드는 것
입출력 or 이벤트완료(I/O or Event Completion)
- 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

CPU 스케줄링의 종류

비선점 스케줄링

FCFS(Fisrt Come Firste Served)
- 위 경우 p1 -> p2 -> p3 -> p4 순서대로 실행
- 도착시간이 전부 0초라면 평균 대기 시간은 (0+20+23+30)/4 = 18.25초가 걸린다.
- Queue 에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어짐
SJF(Shortest Job First)
- 위 경우 p2 -> p4 -> p3 -> p1 순서대로 실행
- 도착시간이 전부 0초라면 평균 대기 시간은 (0+3+8+15)/4 = 6.5초가 걸린다.
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
HRN(Hightest Response-ratio Nest)
- 우선순위를 계산하여 점유 불평등을 보완(SJF 단점 보완)
- 우선순위 = (대기시간 + 실행시간) / (실행시간)
  
  도착시간이 모두 0초이고 실행시간이 가장 짧은 p2 가 먼저 실행된다고 가정해보자.
  p1 : (3 + 20) / 20 = 1.15
  p3 : (23 + 7) / 7 = 4.3
  p4 : (30 + 5) / 5 = 7
  즉, 우선순위가 가장 높은 p2 -> p4 -> p3 -> p1 순서로 실행된다.
- 대기 시간이 길어질수록 우선순위가 높아지므로 p4 의 기아현상도 해소할 수 있다.

선점 스케줄링

Round Robin(RR, 라운드로빈)
- RR 알고리즘은 FCFS알고리즘을 선점형으로 변형한 알고리즘이다.
- 준비큐의 각각의 프로세스 각각의 시간을 가진다고 하자.
- RR 알고리즘에서는 타임 슬라이스(Time Slice)라는 프로세스마다 정해진 시간이 있다. 타임 슬라이스를 초과하면 타입아웃 인터럽트에 의해 CPU 점유를 뺴앗기고 준비 큐에 들어가게 된다.
- 아래 그림처럼 타임슬라이스가 5초라면 p1, p3는 20초,7초이므로 타임슬라이스 초과 시 Context Switching 이 일어나게 된다.
- 즉, p1 -> 문맥교환 -> p2 -> p3 -> 문맥교환 -> p4 -> p1 -> p3 -> p1 순서로 실행된다.
Sortest Remaining Time(SRT, 최소 잔여 시간 우선)
- SRT 알고리즘은 SJF 알고리즘을 선점형으로 변형한 알고리즘이다.
- SRT 알고리즘은 각각의 프로세스들이 타임 슬라이스(Time Slice)만큼 CPU를 사용하고, 남은 실행 시간이 짧다고 추정되는 프로세스에게 먼저 자원을 할당하는 CPU 스케줄링 알고리즘이다.
- 도착 시간이 0초라고 하면 p2 -> p4 -> p3 -> 문맥교환 -> p1 -> 문맥교환 -> p3 -> p1 순서로 실행된다.
Multi-level Queue(MQ, 다단게 큐)
- MQ 알고리즘은 프로세스의 특성별로 준비 큐를 여러 개 두어 우선순위를 부여하고, 높은 우선순위 큐에 있는 프로세스들에게 먼저 자원을 할당하는 CPU 스케줄링 알고리즘이다.
- 프로세스가 큐 간의 이동을 할 수 없기 때문에 우선순위가 낮은 큐에 있는 프로세스들은 기아 현상이 발생할 수 있다.
Multi-level Feedback Queue(MFQ, 다단계 피드백 큐)
- MFQ 알고리즘은 MQ 알고리즘이 발전된 형태로 프로세스가 큐 간의 이동이 가능한 CPU 스케줄링 알고리즘이다.
- MFQ 알고리즘의 경우 우선순위가 낮은 큐에 들어감으로써 프로세스의 기아 현상을 해결한다. 이 기법을 에이징(aging) 이라 한다.