[Operating System] CPU 스케줄링

CPU Scheduling(CPU 스케줄링)?

• CPU 사용률을 극대화하기 위해선 멀티프로그래밍(MultiProgramming)이 필요하다.
• 만약 CPU 코어가 1개인 경우 한번에 하나의 프로세스만 실행 가능하다.
  • 이때 필요한 것이 CPU 스케줄링
• CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할 것인지 결정하는 작업

CPU 스케줄링의 목표

• Batch System
  • 가능하면 많은 일을 수행
  • 시간(time)보다 처리량(throughout)이 중요함
• Interactive System
  • 빠른 응답 시간
  • 적은 대기 시간
• Real-time System
  • 기간(Deadline) 맞추기
• 오버헤드를 낮추고, CPU 사용률을 높이고, 기아 현상을 낮춰야함

선점과 비선점

선점(Preemptive)형 스케줄링

• 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 이를 강제로 뺐을 수 있는 방식
• CPU 처리시간이 긴 프로세스의 CPU 사용독점을 막을 수 있어 효율적인 방식
• 잦은 Context Switching(문맥 교체)으로 인해 오버헤드(OverHead)가 높아질 수 있다.

비선점(Non-Preemptive)형 스케줄링

• 프로세스가 CPU를 점유하고 있다면 이를 뻇을 수 없는 방식
• 필요한 Context Switching만 일어나기 때문에 오버헤드가 생대적으로 적음
• 프로세스의 배치에 따라 효율성 차이가 많이 난다.

CPU Scheduler(스케줄러)

• CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 함
• 스케줄러 디스패치는 준비 상태에 있는 프로세스 중 하나를 선택하여 실행한다.
• CPU 스케줄러는 프로세스들이 아래와 같은 상황에 있을 때 스케줄링을 결정한다.
  1. 실행(Running) 상태에서 대기(Waiting) 상태로 전환될 때 (I/O 발생 시)
  2. 실행(Running) 상태에서 준비(Ready) 상태로 전환될 때 (interrupt 발생 시)
  3. 대기(Waiting) 상태에서 준비(Ready) 상태로 전환될 때 (I/O 발생 시)
  4. 종료(Terminated)될 때
• 1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점 스케줄링이라고 함
• 이외에 상황에 스케줄링되는 것을 선점 스케줄링이라고 함

CPU 스케줄링 평가 기준(Sheduling Criteria)

• CPU 이용률(Utilization)
  • 시간당 CPU를 사용한 시간의 비율
  • 프로세서를 실행 상태로 항상 유지하려고 해야 한다.
• 처리율(Throughput)
  • 시간당 처리한 작업의 비율
  • 단위 시간 당 완료되는 작업 수가 많도록 해야 한다.
• 반환 시간(Turnaround Time)
  • 프로세스가 생성된 후 종료되어 사용하던 작업을 모두 반환할 때까지 걸리는 시간
  • 작업이 준비 큐(Ready Queue)에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합이다.
• 대기 시간(Waiting Time)
  • 대기열에 들어와 CPU를 할당받기 까지 기다린 시간
  • 준비 큐에서 기다린 시간의 총 합
• 반응 시간(Response Time)
  • 대기열에서 처음으로 CPU를 할당받을 때까지 걸린 시간
  • CPU를 할당 받은 최초의 순간까지 기다린 시간 한번 만을 측정
• CPU 이용률과 처리율은 극대화하는 것이 좋고, 반환 시간, 대기 시간, 반응 시간은 줄이는 것이 일반적으로 좋다. 

CPU 스케줄링 알고리즘

FCFS(First Come First Served)

• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식
  • 큐에 도착한 순서대로 CPU를 할당
• 비선점 스케줄링 방식
• 작성이 간단하고 이해하기 쉬움
• 평균 대기 시간(Average Waiting Time)이 길어질 수 있다.
  • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
• 응답 시간(Response Time)이 길어질 수 있다.
• 반환 시간(Turnaround Time) 면에서는 좋을 수 있다.
• 호위 효과(Convoy Effect)가 발생할 수 있다.
  • 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것

FCFS 예시

• P1, P2, P3 모두 0초에 순서대로 도착했다고 하면 위와 같은 결과가 나온다.

SJF(Shortest Job First)

• CPU burst time을 고려하여 스케줄링을 결정하는 방식
  • CPU burst time : CPU 할당 후 입출력을 요구할 때까지의 시간
• 비선점과 선점형이 따로 존재한다.
• 비선점형은 실행되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 프로세스가 더 빨리 끝낼 수 있는 프로세스인 경우 실행하는 프로세스를 바꾸게 된다.
  • SRTF(Shortest Remaing Time First)라고 부른다.
• SJF는 평균 대기 시간을 줄일 수 있다.
• 단, 프로세스의 CPU burst time을 예측하는 것이 어렵다는 단점이 있다.

SJF 예시

SRTF 예시

• 실행 중이던 프로세스보다 도착한 프로세스의 남은 시간이 짧으면 해당 프로세스로 전환

HRN(Hightest Response-ratio Next)

• 우선순위를 계산하여 점유 불평등을 보완한 방법
  • SJF의 단점을 보안
• 우선순위 = (대기시간 + 실행시간) / (실행시간)
• 비선점 알고리즘
• 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방법
• 기아 상태를 해결할 수 있음

HRN 예시

• 평균 대기 시간 = (0 + 24 + 36)/3 = 20ms

Priority Scheduling

• 각각의 프로세스에 우선순위가 있으며 가장 높은 우선순위부터 CPU를 할당
  • 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 선점 알고리즘
• 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation이 생길 수 있음
• Aging(노화) 방법으로 기아 문제를 해결할 수 있음
  • 시간이 지날수록 프로세스의 우선순위를 높여주는 방법

Priority 예시

• 프로세스가 모두 0초에 도착한 경우 위와 같이 처리된다.

Round Robin(RR)

• 프로세스에 동일한 CPU 할당 시간을 부여하여 해당 시간 동안만 CPU를 이용하도록 한다.
• 할당 시간 내 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점 알고리즘이다.
• FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU를 할당 받음
  • Time Quantum, Time Slice : 실행의 최소 시간
• 할당 시간(Time Quantum)이 크면 FCFS와 같아지며, 작으면 Context Switching이 잦아져 오버헤드가 증가

CPU Time Quantum = q
프로세스 수 = n
어떤 프로세스도 (n - 1) * q 시간 이상을 기다리지 않아도 된다.
q가 커진다면 FCFS처럼 작동
q가 매우 작아진 경우 process sharing이라고 부름
n개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미

RR 예시

• 모든 프로세스가 0초에 도착한 경우

Multilevel-Queue(다단계 큐)

• 준비 큐가 여러개의 큐로 나뉜다.
• 각각의 큐는 각자의 스케줄링 알고리즘을 가진다.
• 각 큐 사이 프로세스는 이동할 수 없다.
• 기아 상태가 발생할 수 있음

• 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용
• 우선순위가 높은 큐는 작은 Time Quantum 할당.
• 우선순위가 낮은 큐는 큰 Time Quantum 할당.

Multilevel-Feedback-Queue(다단계 피드백 큐)

• 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로 유지
  • Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문이다.
• 짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌
• 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

 

 

 

 

출처

https://code-lab1.tistory.com/45

[운영체제] CPU 스케줄링 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin

OS는 할껀데 핵심만 합니다. 5편 스케줄링2, 비선점형 스케줄링 알고리즘

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖