[운영체제] CPU Scheduling

CPU And I/O Bursts in Program execution

 

CPU Burst는 CPU만 연속적으로 사용하면서 명령어를 실행하는 단계를 의미하고

I/O Burst는 I/O를 실행하고 있는 단계를 의미한다.

 

프로그램이 실행중일 때에는 CPU Burst와 I/O Burst가 반복적으로 번갈아가면서 실행 중이다.

 

I/O Burst의 빈도수가 많은 작업의 경우 I/O bound job이라 부르고

CPU Burst의 빈도수가 많은 작업의 경우에는 CPU bound job이라고 부른다.

 

 

 

 

 

 

스케줄링 기준 (Scheduling Criteria)

- 시스템 위주의 기준

CPU utilization - 이용률

Throughput - 처리량

- 프로세스 위주의 기준

Turnaround time - 소요 시간

Waiting time - 대기 시간

Response time - 응답 시간

 

 

 

 

 

 

 

FCFS (First-Come First-Served)

 

FCFS는 스케줄링 알고리즘의 하나로 들어온 순서대로 CPU를 사용하는 방법이다.

 

만약 P1, P2, P3 3개의 프로세스가 각각 10, 20, 30의 burst time을 갖고 있으며 P1, P2, P3의 순서대로 들어왔다면

들어온 순서대로 P1을 처리하고, P2를 처리하고, P3를 처리한다,

 

그럼 P2는 P1이 종료될 때까지 대기해야 하며 P3는 P1, P2가 종료될 때까지 대기해야 한다.

 

따라서 P1, P2, P3의 waiting time은 각각 0, 10, 30이다.

 

그러나 해당 알고리즘의 경우 burst time이 긴 프로세스가 먼저 온다면 평균 waiting time이 길어져 비효율적일 수 있다.

 

 

 

 

 

 

SJF (Shortest-Job First)

 

SJF는 CPU burst time이 가장 짧은 프로세스를 먼저 스케줄 하는 방법이다.

 

만약 P1, P2, P3가 6, 7, 4의 burst time을 갖고 있으며 동시에 도착했다고 가정하면 P3, P1, P2의 순서대로 처리된다.

 

따라서 P1, P2, P3의 waiting time은 각각 4, 10, 0이다.

 

해당 알고리즘의 경우에는 CPU burst time이 짧은 process를 선호하여 burst time이 긴 process는 계속 CPU를

점유하지 못할 가능성이 발생한다.

 

 

 

 

 

SRTF (Shortest Remaining Time First)

 

SRTF는 FCFS나 SJF와는 다르게 비선점형 알고리즘이다.

 

해당 알고리즘은 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 cpu burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗아 새로운 프로세스에 할당한다.

 

 

예를 들어 P1, P2, P3의 arrival time과 burst time이 각각 (0, 6), (1, 2), (4, 1)이라고 가정해 보자.

먼저 P1이 0초에 도착하여 P2가 도착하는 1초까지 실행된다. 이때 남은 P1의 burst time은 5이며 P2의 burst time은 2이다.

따라서 P1은 P2에게 CPU 점유를 빼앗긴다. 따라서 P2가 3초까지 실행되며 3초부터 P3가 도착하는 4초까지 P1이 실행된다.

이때 P1의 남은 burst time은 4초이다. 4초 시점에는 P3가 도착하며 P3의 burst time은 1초이다.

따라서 P1은 다시 P3에게 CPU 점유를 빼앗긴다. 따라서 P3가 4초부터 5초까지 실행되며 P1이 5초부터 9초까지 실행되는 것으로

모든 작업이 완료된다.

 

 

해당 알고리즘도 SJF와 같은 원리로 낮은 우선순위의 프로세스는 실행되지 않는 문제점이 여전히 존재한다.

이것을 시간이 진행될수록 프로세스의 우선순위를 높여주는 Aging을 통해 해결할 수 있다.

 

 

 

 

 

Round Robin(RR)

 

각 프로세스는 동일한 크기의 할당 시간(time quantum or time slice)을 가진다.

 

할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 들어가서 대기한다.

 

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 (n-1)*q time unit이상 기다리지 않는다.