CPU 스케줄링

https://inf.run/bXfg

그림으로 쉽게 배우는 운영체제 - 인프런 | 강의

본 포스팅은 위 링크의 강의를 요약/정리한 것으로, 지식의 공유보다는 개인적으로 공부하고 복습하기 위해 기록한 것입니다.

 

CPU스케줄링 개요

 

CPU 스케줄링

🔗운영체제가 프로세스에 CPU를 할당하고 해제하는 것

🔗스케줄러(운영체제)가 고려하는 것

• 어떤 프로세스에 CPU 리소스를 줘야 하는가?
• 프로세스가 얼마나 오래 CPU를 사용해야 하는가?

🔗CPU Burst: CPU를 할당받아 실행하는 것

🔗I/O Burst: 입출력 작업

---

다중 큐

 

다중큐

🔗프로세스의 상태 중 준비와 대기는 큐(Queue) 자료구조로 관리된다.

🔗프로세스가 실행 상태에서 준비 상태로 갈 때 운영체제는 해당 프로세스 PCB를 우선 순위에 따라 적합한 준비 큐에 넣는다.

🔗CPU 스케줄러는 준비 상태의 다중 큐에 들어 있는 프로세스 중에 적당한 프로세스를 선택해서 실행 상태로 전환한다.

🔗프로세스가 실행 상태에서 대기 상태로 오게 되면 해당 프로세스의 PCB가 I/O 작업 종류에 따라 분류된 큐에 들어간다.

---

스케줄링 목표

 

스케줄링 목표

🔗CPU 사용률을 높이거나 I/O 디바이스의 사용률을 높인다.(리소스 사용률 증가)

🔗스케줄링을 하는 계산이 너무 복잡하거나 컨텍스트 스위칭을 자주 하면 오버헤드가 발생한다. 스케줄러는 오버헤드를 최소한으로 줄여야 한다.(오버헤드 최소화)

🔗모든 프로세스에 CPU를 공평하게 할당해야 한다.(공평성)

• 공평성의 의미는 시스템에 따라 달라진다. 예를 들어, 자율주행 자동차에서는 안전과 관련된 프로세스가 가장 중요하다.

🔗같은 시간 내에 더 많은 작업을 처리해야 한다.(처리량)

🔗작업을 요청하고 실행하기까지의 대기 시간이 짧아야 한다.

🔗응답 시간이 짧아야 한다.

🔗모든 목표를 최고 수준으로 달성하기는 어렵다. 목표간에 상반되는 상황이 있기 때문이다. 따라서 사용 환경을 고려해 목표를 다르게 설정한다.

• ex) 터치스크린은 응답시간을 줄이는 데에 초점을 맞추고 과학 계산은 처리량이 높이는 데에 초점을 맞춘다.

---

CPU 스케줄링 알고리즘

 

FIFO

🔗First In First Out

🔗스케줄링 큐에 들어온 순서대로 CPU를 할당받는다. 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스를 실행할 수 있다.

🔗단순하고 직관적이지만 CPU 사용률이 떨어지고 평균 대기 시간이 길다. 때문에 현대 운영체제에서는 잘 쓰이지 않고 일괄처리시스템에 쓰인다.

 

SJF

🔗Shortest Job First

🔗처리 시간이 짧은 작업 먼저 처리한다. 이론적으로 FIFO 방식보다 성능이 좋음.

🔗문제점

• 어떤 프로세스가 얼마나 실행될지 모른다.(ex 사용자가 언제 유튜브를 종료할지 알 수 없다)
• Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있다.

 

RR

🔗Round Robin

🔗프로세스가 CPU를 사용하는 시간에 제한을 둬서 일정 시간이 지나면 강제로 다른 프로세스가 CPU를 사용하게 하는 알고리즘. CPU 할당을 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려나서 다시 차례가 오기를 기다린다.

• 프로세스가 할당받는 일정 시간을 타임 슬라이스 혹은 타임 퀀텀이라고 부른다.

🔗일반적으로 RR 알고리즘은 FIFO 알고리즘보다 평균 대기 시간이 짧다.

🔗RR 알고리즘이 FIFO 알고리즘보다 비효율적인 경우

• 타임 슬라이스가 너무 큰 경우
  • 타임 슬라이스가 너무 크면 FIFO 알고리즘과 평균 대기 시간이 비슷해진다. 평균 대기 시간이 비슷하다면 컨텍스트 스위칭을 처리해야 하는 RR 알고리즘이 FIFO 알고리즘보다 비효율적이다.
• 타임 슬라이스가 너무 작은 경우
  • 타임 슬라이스가 너무 작으면 컨텍스트 스위칭이 더 자주 일어나고, 컨텍스트 스위칭 처리량이 프로세스의 처리량보다 더 커져서 비효율적이다.(오버헤드가 커짐)

🔗최적의 타임 슬라이스 값은 여러 프로세스가 버벅이지 않고 동시에 실행되는 것처럼 느껴지면서 오버헤드가 작은 값이다.

 

MIFQ

🔗Multi Level Feedback Queue

🔗RR의 단점을 개선한 알고리즘으로 오늘날 운영체제에서 가장 많이 쓰인다.

🔗기본적으로는 크기가 작은 타임 슬라이스를 선택해 CPU 사용률과 I/O 사용률을 높이지만 I/O Bound 프로세스보다 CPU Bound 프로세스에 더 큰 타임 슬라이스를 부여한다.

• CPU Bound 프로세스: CPU Burst가 많은 프로세스
• I/O Bound 프로세스: I/O Burst가 많은 프로세스
• 운영체제는 프로세스의 CPU 사용량을 보고 프로세스가 CPU Bound인지 I/O Bound인지 판단한다.(ex 타임 슬라이스를 초과해 CPU 사용권을 뺏긴다면 CPU Bound일 확률이 높음)

🔗알고리즘

• 우선순위 큐를 여러 개 생성한 뒤 우선순위가 높을수록 작은 타임 슬라이스를 부여한다.
• 프로세스가 타임 슬라이스를 초과해 CPU 사용권을 뺏기면 기존에 있던 큐보다 우선순위가 더 낮은 큐로 이동한다.
• 다음 실행에서도 타임 슬라이스를 초과해 CPU 사용권을 뺏기면 또 우선순위가 더 낮은 큐로 이동한다.
• 이렇게 반복하다 보면 프로세스가 점점 더 많은 타임 슬라이스를 할당받기 때문에 FIFO처럼 연속적으로 작업을 마칠 수 있게 된다.