[OS] 3. CPU 스케줄링 (CPU Scheduling)

3. CPU 스케줄링

1. CPU Scheduling
2. 비선점 스케줄링
3. 선점 스케줄링

 

1. CPU Scheduling

1.1. 프로세스의 특성

프로세스는 그 특성에 따라 다음과 같이 나눠진다

I/O-bound process

• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요함
• many short CPU bursts (빈번하고 짧은 작업)

CPU-bound process

• 계산 위주의 작업 수행
• few very long CPU bursts (빈번하지 않고 긴 작업)

 

1.2. CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

Dispatcher

CPU제어권을 CPU scheduler에 의해 선택된 프로세서에게 넘긴다

 

1.3. Scheduling Criteria

성능 척도를 나타내는 5가지 요소는 아래와 같다

• CPU utilization (이용률)
• Throughput (처리량)
• Turnaround time (소요시간, 반환시간)
• Waiting time (대기 시간)
• Response time (응답 시간)

 

1.4. 프로세스를 스케줄링하기 위한 큐

Job Queue

현재 시스템 내에 있는 모든 프로세스의 집합

(Ready Queue, Device Queue 에 있는 프로세스 포함)

Ready Queue

현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합

Device Queue

I/O device의 처리를 기다리는 프로세스의 집합

 

 

2. 비선점 스케줄링

비선점 스케줄링 (Nonpreemptive Scheduling)

• 이미 할당된 자원을 다른 프로세스가 뺏을 수 없음
• 응답시간의 예측이 편하며, 일괄처리 방식에 적합함
• 단점으로는 덜 중요한 작업이 자원을 할당 받으면 중요한 작업이 와도 먼저 처리 될 수 없음

 

2.1. FCFS (First-Come First-Served)

프로세스는 Ready Queue 에 도착한 순서대로 CPU를 할당 받는다. 작업 완료 시간을 예측하기에 매우 용이하다. 하지만 덜 중요한 작업으로 인해 중요한 작업이 기다릴 수도 있다. Convoy effect 가 발생할 수 있다.

Convoy effect : 수행 시간이 짧은 프로세스가 CPU를 오래 기다리는 현상

2.2. SJF (Shortest-Job-First)

Ready Queue 에 있는 프로세스 중, 수행시간이 짧은 것을 먼저 수행한다. 평균 대기 시간을 감소시킨다.

2.3. HRN (Hightest Response-ratio Next)

긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법이다. 수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다.

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

2.4. Priority Scheduling

프로세스마다 우선운위를 부여하여 높은 우선순위를 가진 프로세스에게 먼저 자원을 할당하는 기법이다. 우선순위가 낮을 경우 기아(Starvation) 현상이 일어날 수 있다.

기아현상(Starvation) : Ready Queue 에서 대기하고 있는 낮은 우선순위의 프로세스가 무한정 기다리는 현상

에이징(Aging) : 기아현상을 해결하기 위한 방법으로 오랫동안 기다린 프로세스에게 우선순위를 높여주는 기법

 

 

3. 선점 스케줄링

선점 스케줄링 (Preemptive Scheduling)

• 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
• 어떤 프로세스가 자원을 사용하고 있을 때, 우선순위가 더 높은 프로세스가 올 경우 자원을 뺏음
• 빠른 응답시간을 요구하는 시스템에서 사용
• 단점으로는 잦은 문맥 교환으로 오버헤드가 증가함

 

3.1. SRT (Shortest Reamining Time)

짧은 시간 순서대로 프로세스를 수행한다. 남은 처리 시간이 더 짧은 프로세스가 Ready Queue 에 들어오면 그 프로세스가 바로 선점된다. SJF 기법의 preemptive 버전 이라고 생각할 수 있다

3.2. Round-Robin

시분할 시스템에 사용되는 기법으로, 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 수행된다. 할당시간이 클 경우 FCFS 와 비슷해지고, 할당시간이 작은 경우 오버헤드가 증가한다.

3.3. Multi-level Queue

MQ 의 핵심은 Ready Queue 를 여러 개로 분할 하고, 이 Ready Queue 사이에 우선순위가 존재하는 것이다. 따라서 큐 사이에도 스케줄링 이 일어나게 된다. 따라서 각각의 큐에서 스케줄링 이 일어나며 Ready Queue 사이에서 스케줄링이 일어나 MQ 의 큐 개수 보다 한 개 더 많은 스케줄러가 필요하다. 또한 우선순위가 높은 큐에 지속적으로 프로세스가 들어오면 낮은 우선순위를 가진 프로세스에 기아현상(Starvation) 이 발생할 수 있다.

Foreground

• interactive 한 작업을 배치
• Round-Robin 으로 CPU 스케줄링

Background

• interactive 하지 않은 작업을 배치
• FCFS 으로 CPU 스케줄링

3.4. Multi-level Feedback Queue

MQ 와의 가장 큰 차이점은 큐 사이의 프로세스 이동 이다. 우선순위가 높은 프로세스에게는 불이익을, 낮은 프로세스에게는 이익을 제공하는 에이징(Aging) 을 통해 기아현상을 방지한다.

기본적으로 MFQ 에서는 가장 우선순위가 낮은 큐를 제외하고는 모두 Round-Robin 스케줄링을 사용한다. (가장 낮은 큐는 FCFS or RR)

이 때, 우선순위가 높은 큐 일 수록 짧은 Time slice 를 주고 한번의 Time Slice 안에 그 프로세스의 실행이 끝나지 않으면 한단계 낮은 우선순위를 가지고 있는 큐로 보내게 된다.

반대로, 어떤 큐에서 일정시간동안 실행되지 못한 프로세스는 한단계 높은 우선순위의 큐로 보내게 되는 것이다.