CPU 스케줄링

cpu 스케줄링 개요

프로그램이 실행되면, 메모리에 프로세스가 생성된다. 또한 그 프로세스 안에는 1개 이상의 쓰레드가 존재한다.
프로세스는 CPU를 차지하기 위해 운영체제의 명령을 기다린다.
CPU 스케줄러 = 운영체제가 모든 프로세스에게 CPU를 할당 및 해제하는 과정
고려사항
- 어떤 프로세스에게 CPU 사용권을 주어야하는가?
- CPU를 할당받은 프로세스가 얼마의 시간동안 사용해야하는가?
⇒ 컴퓨터의 성능에 큰 영향을 끼친다.

프로세스 상태 중, 프로세스가 대기하는 준비상태와 대기상태는 큐로 관리한다.
- Running → Ready : 프로세스의 우선순위를 보고, 준비 큐에 넣는다.
- Runnign → Waiting : I/O 종류에 따라 분류된 큐에 넣는다. (HDD, LAN, 키보드 등)
큐에 프로세스가 들어가는 것이 아니라, PCB가 들어간다. (프로세스 정보가 저장된 것)

리소스 사용률 극대화
- CPU, I/O Device의 사용률을 극대화한다.
오버헤드 최소화
- 스케줄링을 위한 계산이 너무 복잡하거나, 컨텍스트 스위칭을 너무 자주해서는 안 된다.
- 이러한 오버헤드를 최소화한다.
공평성
- 모든 프로세스에게 공평하게 할당되어야한다.
- 시스템에 따라서 공평의 의미는 달라질 수 있다.
  - 자율주행 시스템 → 안전에 이유로 자율주행 관련 프로세스가 더 많은 cpu 시간을 가져가는 것이 공평하다.
처리량
- 같은 시간 내에 더 많은 작업을 처리한다.
대기시간
- 작업 요청 후, 실제 작업이 이루어지기 전까지 대기 시간이 짧아야한다.
응답시간
- 대화형 시스템에서 사용자의 요청에 빨리 반응해야한다.

이러한 목표들은 서로 상반되는 상황이 존재한다.
- 처리량 vs 응답시간
  처리량이 높으려면, 하나의 프로세스에 CPU 할당 시간이 길어야하며, 응답시간이 짧으려면 각각의 CPU 할당 시간이 짧아야한다. ⇒ 시스템에 따라 결정된다.

cpu 스케줄링의 성능 = 프로세스의 평균 대기시간
- 여러개의 프로세스가 실행될 대, 모든 프로세스가 실행되기까지의 평균 대기시간을 의미한다.
- 예) 프로세스 1 = 25초, 프로세스 2 = 5초, 프로세스3 = 4초라고 가정한다.
  1→2→3 으로 실행시 : (0 + 25 + 30) / 3
  3→2→1 으로 실행시 : (0 + 4 + 9) / 3

First in First out의 약자로, 먼저 들어온 프로세스를 먼저 실행하는 것이다.
- 즉, 스케줄링 큐에 들어온 프로세스를 먼저 실행한다.
단순하고 직관적인 장점이 있다.
먼저 들어온 프로세스가 무조건 끝나야 다음 프로세스가 실행될 수 있어서 다음과 같은 단점이 있다.
- 실행시간이 짧은 프로세스가 늦게 도착한다면, 이전 프로세스가 종료될때까지 계속 기다려야한다.(평균 대기시간이 길어진다)
- I/O 작업이 있으면, 그만큼 CPU의 대기시간이 생겨서 CPU의 사용률이 떨어진다.
FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 난다.
- 현대 운영체제에서 사용하지 않고, 일괄처리 시스템에서 사용된다.

이론적으로만 나온 알고리즘이다. (문제가 있어 사용되지 않았다)
- 이론적으로는 FIFO보다 성능이 더 좋다. (프로세스 평균 대기시간이 짧아지니까)
문제점
- 프로세스의 실행시간을 예측하는 것이 거의 불가능하다. (사용자에 따라 결정되는 경우가 많으므로)
- burst time이 긴 프로세스는, 오랫동안 실행되지 않을 가능성이 높다.

FIFO 알고리즘의 단점을 해결하기 위한 방법
- 한 프로세스에게 일정 시간만큼만 CPU를 제공한다. 할당 시간이 지나면, 다음 프로세스에게 CPU를 넘기는 방법이다. (이전 프로세스는 큐 맨 뒤로 이동한다.)
- 여기서 일정시간을 타임 슬라이스라고 부른다.
타임 슬라이스에 따라 RR의 성능이 결정된다.
적절한 타임 슬라이스 결정이 가장 중요하다.
- 타임 슬라이스가 너무 큰 경우
  - FIFO 알고리즘과 동일하다.
  - 만약 FIFO 알고리즘과 스케줄링 성능이 비슷하다면 RR이 더 비효율적일 것이다. (context switching도 일어나기 때문에)
  - 프로그램이 매우 버벅일 것이다.
- 타임 슬라이스가 너무 작은 경우
  - 컨텍스트 스위칭이 너무 자주 일어난다. (너무 큰 오버헤드 발생)

오늘날 OS에서 가장 일반적으로 사용되는 CPU 스케줄링 기법이다.
RR의 업그레이드 버전이다.
- 타임 슬라이스가 너무 짧은 경우, 응답시간은 빨랐지만, 컨텍스트 스위칭이 너무 자주 발생해 오버헤드가 크다는 것에서 착안된 기법이다.
  Untitled
특징
- 프로세스를 주로 CPU 작업을 하는 CPU Bound Process와 입출력을 주로 하는 I/O Bound Process로 구분한다.
- CPU Bound Process는 CPU 사용률과 처리량을 중요하게 생각하고, I/O Bound Process는 응답 시간을 중요하게 생각한다.
- 이에 CPU Bound Process는 타임 슬라이스를 크게 주는 방식이다.
CPU Bound와 I/O Bound를 어떻게 구분할 수 있을까?
- CPU를 스스로 반납하는 경우 I/O Bound일 확률이 높고, CPU를 강제로 뺏기는 프로세스는 CPU Bound일 확률이 높다.
- 이에 CPU를 강제로 빼앗기면, 우선순위가 더 낮은 큐로 이동하여 다음 차례에서는 CPU를 더 오랜 시간 차지할 수 있도록 하는 것이다.
- 우선순위가 낮을수록 CPU를 더 오랜시간 가질 수 있또록 하는 것이다.

Last updated 1 year ago