[운영체제] CPU 스케줄링

cs-study에서 스터디를 진행하고 있습니다.

CPU I/O Burst Cycle

지난 시간에서 프로세스의 상태를 배웠다. 아래 사진은 활성 상태인 프로세스다.

 

 

프로세스의 실행은 CPU 실행(execution)과 I/O 요청 대기(I/O wait)가 번갈아가며 이루어지는데, 이를 CPU I/O Burst Cycle라고 한다. CPU 스케줄링을 통해 이 CPU Burst Distribution을 관리한다.

 

 

CPU 스케줄링이란?

작업을 처리하기 위해서 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 것이다.

 

 

CPU 스케줄링 대상 프로세스는 Ready Queue에 있는 프로세스들로, 스케줄링 정책에 따라 Queue에 정렬을 한 후 앞에 있는 프로세스부터 CPU를 주게 된다.

 

Dispatcher

스케줄러에는 멀티 프로그래밍에 이용되는 long-term 스케줄러와 CPU 스케줄링에 이용되는 short-term 스케줄러가 있다.

 

💡 넓은 의미의 스케줄링 = 스케줄링(Ready Queue 정렬) + Dispatch(프로세스를 CPU에 올림)

 

CPU 스케줄링의 필요성

CPU를 효율적으로 사용하기 위해 프로세스들을 잘 배정해야 한다. Ready Queue에 있는 프로세스 대상으로 CPU를 할당하는 순서와 방식을 결정하는 것을 의미한다.

 

스케줄링 Criteria : Goal

수 많은 프로세스들을 어떤 순서로 정렬할지 정책을 수립하는 것이 스케줄링이라면, 좋은 정렬 방법과 나쁜 정렬 방법이 있을 것이다. 이렇게 스케줄링 알고리즘을 평가할 수 있는 기준을 스케줄링 Criteria라고 한다.

 

1. CPU Utilization: CPU가 쉬고 있지 않게 해야 한다.
2. Throughput: 단위 시간 당 처리량 (of instructions / second)
3. Turnaround Time: 수행을 요청한 후 작업이 끝날 때까지 걸린 시간
4. Waiting Time: 수행을 요청한 후 작업이 시작될 때까지 걸린 시간 (Running이 되고 Ready Queue에 들어간 시간)
5. Response Time: 요청한 후 응답이 올 때까지 걸린 시간

 

CPU Utilitzation, Throughput은 늘리고, Time 지표들은 감소하는 것이 스케줄링 목표가 된다.

 

시스템 별 목표

CPU 스케줄링의 세부적인 목표는 시스템마다 다르다.

 

Batch System

배치 시스템은 한 번에 하나의 프로그램만 수행하는 것이다. 가능한 한 많은 일을 수행하기 위해 throughout과 CPU utilization이 중요하다.

 

Interactive System

사용자가 컴퓨터 앞에서 대화형으로 동작하는 시스템이다.

 

• Response Time → 프로세스가 Ready Queue에서 대기하는 시간을 최소화한다.
• Waiting Time → 프로세스가 Wait Queue에 서 대기하는 시간을 최소화한다.
• Proportionality → 사용자가 요구하는 바를 이루어야 한다.

 

이러한 시스템의 경우, Time Sharing 기법을 이용해야 한다.

 

Real-time System

시간 제약 조건이 걸려 있는 시스템이다.

 

• Metting Deadlines
• Predictability

 

CPU 스케줄링 방식

방법에 따라

비선점

프로세스 종료 또는 입출력 등의 이벤트가 있을 때까지 실행을 보장

 

장점

• 모든 프로세스들에게 공정하다.
• 응답 시간을 예측할 수 있다.

 

단점

• 짧은 작업을 수행하는 프로세스라도 긴 작업이 종료될 때까지 기다려야 할 수 있다.

 

선점

OS가 CPU의 사용권을 선점할 수 있는 경우에 강제로 회수한다.

 

장점

• 높은 우선 순위를 가진 프로세스를 빠르게 처리하려는 시스템에 유용하다.
• 빠른 응답 시간을 요구하는 시분할 시스템에 유용하다.

 

단점

• 높은 우선 순위를 가진 프로세스들만 들어오는 경우 Overhead가 발생한다.

 

알고리즘에 따라

FCFS (First Come First Served)

큐에 도착한 순서대로 CPU를 할당한다.

 

• CPU burst가 완료될 때까지 CPU를 반환하지 않는다.
• 할당되었던 CPU가 반환 될 때에만 스케줄링이 이루어진다.

 

 

장점

• 개발이 용이하다.
• 공평성을 유지할 수 있다.
• Starvation 이슈가 발생하지 않는다.

 

단점

• Convoy Effect
  • 소요 시간이 긴 프로세스가 먼저 도달할 경우 효율성이 낮아진다.
  • 실행 시간이 짧은 작업이어도 뒤로 가면 대기 시간이 길어진다.

 

SJF (Shortest Job First)

FCFS 알고리즘을 보완하기 위해 만들어졌다. 수행 시간이 가장 짧다고 판단되는 작업을 우선 수행한다. 평균 대기 시간이 짧으므로 짧은 작업에 유리하지만, 사용 시간이 긴 프로세스는 영원히 CPU를 할당 받지 못할 수 있다. (Starvation)

 

HRN (Highest Response-ratio Next)

점유 불평등 현상이 발생하는 SJF 알고리즘을 보완하기 위해 만들어졌다. 우선 순위를 계산하여 동작한다.

 

💡 우선 순위 = (대기시간 + 실행시간) / (실행시간)

 

SRTF (Shortest Remaining Time First)

현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가진 새로운 프로세스가 도착할 경우 CPU를 강제로 회수한다.

 

새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU 사용 시간을 측정할 수 없고, Starvation 현상이 발생할 수 있다.

 

Priority 스케줄링

정적/동적으로 우선 순위를 부여하여 우선 순위가 높은 순서대로 처리한다. 선점형/비선점형 모두에 접목이 가능하다.

하지만, Starvation 현상이 발생할 수 있고 Indefinite Blocking 현상이 발생할 수 있다. Indefinite Blocking (무기한 봉쇄)는 실행 준비가 되어 있으나 CPU를 사용하지 못하는 프로세스가 CPU를 무한정 기다리는 상태를 의미한다. 이는 Aging 기법으로 문제 해결이 가능하다고 한다.

 

Round Robin

FSFC에 의해 프로세스를 받아 각 프로세스에 동일한 시간의 Time Quantum만큼 CPU를 할당한다. 현대적인 CPU 스케줄링 방식이며 할당 시간이 끝나면 프로세스는 Ready Queue의 제일 뒤에 삽입된다. 또한, CPU 사용 시간이 랜덤한 프로세스들이 섞여 있을 경우에 효율적이고, 프로세스의 Context를 저장할 수 있다.

 

💡 Time Quantum (Time Slice) : 실행의 최소 단위 시간

 

장점

• Response Time이 빨라진다.
• N개의 프로세스가 Ready Queue에 있고 할당 시간이 q (Time Quantum)인 경우, 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. → 어떤 프로세스도 (n - 1) * q * Time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가하는 공정한 스케줄링이다.

 

단점

• Time Quantum이 크면 FCFS와 같아진다.
• Time Quantum이 작으면 Context Switching이 잦아져서 Overhead가 증가한다.

 

다단계 큐 (Multilevel-Queue)

작업들을 여러 종류의 그룹으로 나누어 여러 개의 Queue를 사용한다. 우선 순위가 낮은 큐들이 실행 못하는 것을 방지하고자 큐마다 다른 Time Quantum을 설정해 준다. 우선 순위가 높은 큐에는 작은 Time Quantum을, 낮은 큐에는 큰 Time Quantum을 할당한다.

 

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

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

 

출처

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Operating System/CPU Scheduling.md
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#cpu-스케줄러
• https://www.notesjam.com/2018/11/scheduling-algorithms-examples.html
• https://jhnyang.tistory.com/category/별걸다하는 IT/운영체제 OS

결론

각 스케줄링 방식의 작동 방법, 특징 및 장단점을 설명할 수 있어야 한다.

 

• FCFS
• SJF
• HRN
• SRTF
• Priority
• Round Robin
• Multilevel-Queue
• Multilevel-Feedback-Queue