CPU 스케쥴링

CPU 스케줄링은 운영체제가 CPU를 효율적으로 활용하기 위한 방법이다. 이는 여러 프로세스들 중에서 어떤 프로세스를 먼저 실행할지, 얼마나 오랫동안 실행할지 등을 결정하는 일련의 과정을 말한다. CPU 스케줄링은 시스템 성능을 높이고, 시스템 자원을 효율적으로 사용하여, 다양한 작업을 보다 빠르게 처리할 수 있도록 도와준다.

• 프로그램을 실행해주는 주체 = 프로세스
  • ex) 카카오톡 💬을 실행하는 프로세스
• 작업을 처리해주는 주체 = 쓰레드
  • ex) 메세지 발송 📤을 처리하는 쓰레드

CPU 를 잘 사용하기 위해 프로세스를 잘 배정해야 한다.

• CPU는 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 합니다.
• 이해하기 쉽게 표현하다면, OS는 실행 대기중인 프로그램(프로세스)들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있다. (결국 처리는 CPU 가 하니까)
• 공통 배정조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
  • 오버헤드 : 프로세스가 필요한 자원보다 더 많이 사치부리며 사용하지 않도록(=투머치🤑)
  • 사용률 : 프로세스가 최대한 자원을 많이받고 빨리 처리하도록 (=알잘딱깔쎈🤓)
  • 기아 현상 : 프로세스가 자원할당을 못받아서 배고픈상태로 대기하지 않도록(=지못미🤕)
• 목표에 따른 배정조건 :
  1. 배치 시스템 : 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
  2. 대화형 시스템 : 빠른 응답 시간. 적은 대기 시간이 중요
  3. 실시간 시스템 : 실시간(time) 즉, 최소 응답시간(dead line) 이 중요!

💡 정책에 따라서 3가지로 나뉩니다.
1.CPU이용률을 최대화,
2.오버헤드를 최소화,
3.모든 프로세스가 공평하게 분배하는 방식이 있다.

스케쥴링의 단위

프로세스 실행은 “CPU실행 ↔ 입/출력 대기” 의 반복을 의미

• CPU Burst
  • 프로세스의 사용중에 연속적으로 CPU를 사용하는 구간을 의미.
  • 즉, 실제 CPU 를 사용하는 스케쥴링의 단위이다.
• I/O Burst
  • 프로세스의 실행 중에 I/O작업이 끝날때까지 Block되는 구간을 의미.

스케쥴링 종류

선점 스케쥴링(Preemptive Scheduling)

선점 스케쥴링이란 OS가 나서서 CPU사용권을 '선점'하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다.

• 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있다.
• 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

1. Priority Scheduling(우선순위 스케쥴링)

💡 Priority Scheduling 특징

• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상 발생 가능
• Aging 방법으로 기아현상 문제 해결 가능

• 미리 주어진 프로세스의 우선순위에 따라서 스케쥴링하는 방식이다. 2번에서 다룬 SJF도 Priority Scheduling의 일종
• 그러나 우선순위가 낮은 프로세스는 할당되지 않기도 하는데, 이를 기아(Starvation)이라고 부른다.
• 이를 방지하기 위한 해결법으로는 노화(Aging)이 있는데 기다리는 시간에 따라 우선순위를 증가시켜주는 방식입니다. 마찬가지로 우선순위가 같으면 FCFS를 적용한다.

2. Round Robin(라운드로빈)

라운드로빈은 FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할당하는 방법으로,

• 정해진 시간 할당량 만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환 큐)의 가장 마지막에 가서 재할당을 기다리는 방법이다.

• 시간 할당량이 중요한데, 너무 작으면 빈번한 문맥 전환(Context Switching)이 발생하고, 너무 길면 FCFS와 다를 바 없어진다.

3. Multilevel-Queue(다단계 큐)

준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식. 메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당된다. 따라서 큐와 큐 사이에도 스케쥴링이 필요하다. 우선순위 방식 혹은 시분할 방식으로 한다.

고정 우선순위의 선점형 방식으로 구현되며, 따라서 우선순위에 따른 큐의 스케쥴링은 절대적이다. 예를 들어,

우선순위가 높은 Forground Queue

• 대화형 프로세스를 위한 큐
• Round Robin

우선순위가 낮은 Background Queue

• 연산작업을 처리하는 프로세스 큐
• FCFS

  여기서 Forground큐가 비어있지 않는 한 Background큐는 먼저 실행될 수 없으며, Background큐가 먼저 실행중이더라도 Forground큐에 프로세스가 들어오면 선점된다.

비선점 스케쥴링(Non-Preemptive Scheduling)

비선점 스케쥴링이란 어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장하는 방법이다.

• 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있습니다.
• 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적습니다.
• 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있습니다.

1. FCFS (First Come , First Serve)

FCFS 란 먼저 도착한 프로세스를 먼저 처리하는 기본적인 스케쥴링 알고리즘이다.
FCFS 특징

• 큐에 도착한 순서대로 CPU 할당
• 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐

• 비 선점형이며 FIFO큐(먼저 입력된것 먼저 출력)를 이용하여 간단하게 구현한다.
• 다만, Convoy Effect(호위효과)가 발생하는데, 긴 처리시간의 프로세스가 선점되어버리면 나머지 프로세스들은 끝날때 까지 대기해야 한다.
• 따라서 먼저 도착한 프로세스의 버스트 타임에 따라서 평균 대기시간의 편차가 크다.

2. SJF(Shorted Job First)

SJF란 CPU버스트 타임이 가장 짦은, 최단작업을 우선 스케쥴링 하는 알고리즘이다.
SJF 특징

• 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
• FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리

• 가장 적은 평균 대기 시간을 달성할 수 있다.
• 만약 CPU버스트 시간이 동일하다면 FCFS방식을 따른다.
• 다만 선점형인 경우에는 위와같이 진행이 되지만 비 선점형일 경우엔 최소잔여시간우선 법칙을 따른다.

• 현재 CPU에 할당된 프로세스의 남은 잔여시간과, 새로 들어온 프로세스의 CPU버스트 타임을 비교하여 더 적은 프로세스에게 할당하게끔 한다.
• 최적이긴 하지만 다음 프로세스의 버스트시간을 계산하기 어렵다는 단점이 있어서 '비슷할것이다'라고 추측을 통해 진행하기도 한다.

3. HRN (Highest Response-ratio Next)

HRN 특징

• 우선순위를 계산하여 점유 불평등 보완(SJF 단점 보완)
• 우선순위 = (대기시간 + 실행시간) / (실행시간)

스케쥴링 동작시점

스케쥴링 알고리즘에 따라 프로세스들은 상태변화가 일어나며 준비/수행 상태일때 CPU를 사용하게 됩니다.
아래 그림에서

• 🟠은 프로세스들의 상태를 의미하고
• 🔜 은 스케쥴링에 따라 상태가 변화되는 동작을 의미합니다.

1. 수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때
2. 수행 -> 종료 (Running -> Terminate) : 프로세스를 종료시켯을때
3. 수행 -> 준비 (Running-> Ready) : 인터럽트가 발생했을때
4. 대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을때
   여기서 1,2은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링이 발생되고 3,4은 프로세스에서 CPU를 강제로 할당(회수)해야 하므로 선점 스케쥴링 이 발생된다.

예시)
1. 준비 (Ready) 상태:
카카오톡을 띄워서 메시지를 입력하고 있을 때, 해당 프로세스는 준비 상태가 됩니다.
2. 대기 (Waiting) 상태:
카카오톡이 비활성화 되어있거나, 가만히 상대방의 답장을 기다릴때 대기 상태가 됩니다.
3. 수행 (Running) 상태
사용자가 메시지를 발송하거나 상대방의 메시지를 수신할때 수행 상태가 됩니다.
4. 종료 (Terminated) 상태:
카카오톡 프로그램을 종료하면 해당 프로세스는 중지 상태로 변경됩니다.