<cs> CPU 스케줄링

ming·2023년 5월 31일

CS

목록 보기

8/10

스케줄링?
CPU 를 잘 사용하기 위해 CPU 스케줄링 알고리즘을 이용해 프로세스를 잘 배정하는 것을 말한다.

1.Scheduling criteria(스케줄링 척도)

Scheduling criteria(척도)는 스케줄링의 효율을 분석하는 기준들이다.

CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률을 말한다.
처리량(Throughput): 단위 시간당 완료된 프로세스의 개수로써 나타낼 수 있다.
총처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 한다.
대기 시간(Waiting Time): 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.
응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간이다.

알고리즘의 선택이 목표 : CPU 이용률, 처리량을 최대화⬆︎ && 총처리 시간, 대기 시간, 응답시간을 최소화⬇︎

CPU 스케줄링의 목표 : 오버헤드, 기아 현상 최소화 / cpu이용률 최대화하는 것.
1. Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
2. Interactive System: 빠른 응답 시간. 적은 대기 시간.
3. Real-time System: 기한(deadline) 맞추기.

CPU Scheduling Algorithms

크게 선점, 비선점 스케줄링으로 분류된다.

Preemptive VS Non-preemptive

Preemptive

Preemptive(선점)은 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유 할 수 있다. 즉, 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다. (처리시간 예측 어려움)

Non-preemptive

Non-preemptive(비선점)은 말 그대로 preemptive의 반대이다.
한 프로세스가 한 번 CPU를 점유했다면, I/O(프로세스 상태가 실행 -> 대기로 변경되는 경우) 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다. (처리시간 예측 가능)

1.FCFS (선입 선처리, First-Come First-Served)

FCFS는 먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다.
그리고 FCFS는 Non-preemptive 이다.
이는 매우 단순하고 많이 사용하는 방법이지만, 모든 부분에서 효율적인 것은 아니다.

예시

Process	Burst Time(msec)
P1	24
P2	3
P3	3

평균 대기시간을 계산하면 아래와 같다.

Average Waiting Time = 0+24+27 / 3 = 17msec

만약, 프로세스가 들어온 순서가 P3, P2, P1 이라면 간트 차트는 아래 그림과 같이 바뀔 것이다.
Average Waiting Time = 6+3+0 / 3 = 3msec

-> 들어온 순서로 수행한다고 해도 반드시 효율적인 것은 아닌 것을 알 수 있다.

실행 시간이 긴 게 먼저 실행되면 평균 대기 시간이 길어짐

2. SJF (최단 작업 우선 스케줄링, Shortest-Job-First)

가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 것을 말한다.
앞서 알아본 FCFS의 단점을 이용한 알고리즘으로 가장 효율적이다.

하지만 매우 비현실적이다.왜냐하면 현실적인 컴퓨터 환경에서는 프로세스의 CPU 점유 시간(burst time)을 알 수 없다. 왜냐하면 한 프로세스가 실행 중에는 많은 변수가 존재하기 때문에 CPU 점유 시간을 알려면 실제로 수행하여 측정하는 수 밖에 없다.
실제 측정한 시간으로 예측해서 SJF를 사용할 수도 있지만, 이는 오버헤드가 매우 큰 작업으로 잘 사용되지 않는다.

SJF는 preemptive와 non-preemptive 둘 다 사용가능하다.

예시

Process Arrival Time Burst Time(msec)
P1 0 8
P2 1 4
P3 2 9
P4 3 5
- non-preemptive
  
  가장 먼저 도착한 P1이 수행되는 동안 P2, P3, P4 모두 도착하지만, non-preemptive이므로 이미 수행중인 프로세스가 끝날 때까지 기다려야 한다.
  Average Waiting Time(AWT) = 0+7+15+9 / 4 = 7.75msec
- preemptive
  
  도착시간이 0인 P1이 먼저 실행 중이고, 실행시간이 1초가 될 때 = P2가 도착했을 때 현재 남은 burst time 중 가장 짧은 프로세스인 P2이므로 P1를 중단하고 P2가 수행 시작한다.
  Average Waiting Time(AWT) = 9+0+15+2 / 4 = 6.5msec

Process	Arrival Time	Burst Time(msec)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

현재 남아있는 시간 중 가장 짧은 프로세스를 선택하므로 Shortest-Remaining-Time-First(최소잔여시간 우선) 이라 불리기도 한다.

3. Priority Scheduling (우선순위 스케줄링)

CPU 코어는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄 된다.
우선순위는 내부적 또는 외부적으로 정의될 수 있다.
우선순위 스케줄링은 preemptive 또는 non-preemptive이 될 수 있다.

문제점

무한 봉쇄(indefinite blocking) : 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄 된 것으로 간주할 수 있다.
기아 상태(starvation) : 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 도 있다.

해결 방안

aging : ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 것이다.

4. Round-Robin(RR)

Round-Robin은 원 모양으로 모든 프로세스가 돌아가며 스케줄링하는 것을 말한다. 이는 시분할 시스템에서 주로 사용하는 방식이다.
일정 시간(time quantum)을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다. 그리고 다음 프로세스가 역시 같은 시간동안 수행한 후 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와서 반복한다.

한 프로세스가 종료되기 전에 할당시간(time quantum)이 끝나면 다른 프로세스로 CPU를 넘겨주기 때문에 preemptive 이다.

할당 시간이 작으면 context switching이 잦아져 오버헤드가 증가
할당 시간이 크면 FCFS와 비슷해짐

5. Multilevel Queue Scheduling (다단계 큐 스케줄링)

프로세스는 기준에 따라 여러 그룹으로 나눌 수 있다.

System processes(시스템 작업): 운영체제 커널 수준의 프로세스
Interactive processes(대화형 작업): 유저 수준의 대화형 프로세스
Interactive editing processes(편집 작업)
Batch processes(일괄 처리형 작업): 대화형 프로세스의 반대인 것으로 일정량을 한 번에 처리하는 프로세스
(Ex, 컴파일러)
Student processes(학생 작업)

각 그룹에 따라 큐를 두어 여러 개의 큐를 사용하는 것이 Muitilevel Queue 방식이다.

큐마다 우선순위를 지정해줄 수 있다. 프로세스 그룹을 보면 System process는 커널 수준에서 중요한 작업이므로 우선순위가 높은 그룹이라 볼 수 있다. 위 그림에서 System process, Interactive process, Batch process 순으로 우선순위가 높은 순서이다. Batch 프로세스는 운영체제의 개입이 매우 적으므로 우선순위가 가장 낮다고 볼 수 있다.
큐마다 CPU 시간을 다르게 줄 수도 있고, 큐마다 다른 스케줄링 방식을 사용할 수도 있다.