[운영체제] 6. cpu스케쥴링

6. CPU 스케줄링

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 이때 다음 프로세스가 어느 프로세스 인지를 선택하는 알고리즘을 CPU Scheduling 알고리즘이라 한다. 간단히 생각해보면 먼저 온 프로세스가 먼저 실행되는 것이 가장 좋을 것이라 생각 할 수 있다. 하지만 여러 상황에서 사용되는 컴퓨터 환경에서 꼭 이러한 방법이 좋다고 할 수 없다. (단순한 환경에서도 이 방법이 반드시 빠른 것도 아니다.) 그러므로 CPU 스케줄링에는 여러가지 방법이 존재한다.

1. Preemptive VS Non-preemptive

1.1 Preemptive

Preemptive(선점)은 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유 할 수 있다.

즉, 프로세스가 정상적으로 수행 중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행 할 수 있는 것이다.

1.2. Non-preemptive

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

2. Scheduling criteria

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

• CPU Utilization(이용률, %): CPU가 수행되는 비율
• Throughput(처리율, jobs/sec): 단위 시간 당 처리하는 작업의 수 (처리량)
• Turnaround time (반환시간): 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간이다. (CPU, waiting, I/O 등 모든 시간을 포함한다.) 반환 시간은 짧을 수록 좋다.
• waiting time(대기시간): CPU를 점유하기 위해서 ready queue에서 기다린 시간을 말한다. (다른 큐에서 대기한 시간은 제외한다.)
• Response time(응답시간): 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.

3. CPU Scheduling Algorithms

3.1. First-Come, First-Served(FCFS)

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

Gantt Chart

Process Burst Time(msec)

P1	24
P2	3
P3	3

!https://user-images.githubusercontent.com/34755287/53879661-5d666b80-4052-11e9-8453-bad918a563ef.png

첫 번째 표는 3개의 프로세스와 각 프로세스가 CPU를 사용한 시간(Burst time)을 나타낸다. 이를 간트 차트로 표현하면 표 아래의 그림과 같다. (도착 시간을 모두 0초라고 가정) 평균 대기 시간을 계산하면 아래와 같다.

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

만약, 프로세스가 들어온 순서가 p3,p2,p1이라면 간트 차트 는 아래 그림처럼 바뀔 것이다.

!https://user-images.githubusercontent.com/34755287/53879665-5d666b80-4052-11e9-8ad5-8639b73b13ac.png

• Average Waiting Time = (6+3+0)/3 = 3 msec

두 예제에서 모든 프로세스가 끝난 시간은 30 msec로 같지만, 평균 대기시간으로 봤을 때는 위의 예제는 17msec이고 아래는 3 msec로 차이가 난다. 즉,들어온 순서로 수행한다고 해도 반드시 효율적인 것은 아닌 것을 알 수 있다.

위 예제처럼 p1, p2, p3 순서로 들어온 것을 Convoy Effect라고 한다. 이는 CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스들은 그만큼 오래 기다리는 것을 말한다. p1이 수행되는 동안 p2, p3는 오래 기다려야 하는 예제에서 볼 수 있다. 이는 FCFS는