[OS] STCF 스케줄링(Scheduling) 이란?

서론

이번 글은 이전에 포스팅한 SJF 스케줄링 기법과 연결되는 내용으로 STCF 스케줄링을 이해하기 위해서는 아래 글을 먼저 참고하는 것을 권장한다.

• [OS] 최단 작업 우선 스케줄링(SJF) 이란?

[OS] 최단 작업 우선 스케줄링(SJF) 이란?

Shortest Time to Completion First(STCF) 스케줄링 이란?

어떤 프로세스가 수행되고 있을 때 새로운 프로세스가 도착한 경우, 기존의 프로세스와 새로 유입된 프로세스의 길이를 비교하여 짧은 것부터 처리하는 스케줄링 기법으로 Shortest Job First(SJF) 스케줄링 기법의 단점을 보완한 정책이다.

 

기존 SJF 정책과 다른 중요한 점은, 특정 프로세스가 CPU를 할당 받으면 일이 끝날 때까지 실행하지 않는다는 것이다.

STCF 특징

• 인터럽트(Interrupt)를 통한 문맥 교환(Context Switching)이 일어난다.
• 선점 스케줄링(Preemtive Scheduling) 방식이라고 표현한다.
  • 이전의 Shortest Job First(SJF) 스케줄링 기법은 비선점적 스케줄링 방식이라고 표현한다.
• SJF 스케줄링과 마찬가지로 수행시간이 짧은 프로세스가 무한히 들어오는 경우 기아 상태(starvation)에 빠질 수 있다.

그림을 통해 STCF 스케줄링 기법을 알아보자.

STCF 스케줄링 흐름

먼저 3개 프로세스의 특징은 다음과 같다.

• A는 해야할 일이 100, 도착 시간은 0초이다.
• B,C는 해야할 일이 10, 도착 시간은 모두 10초이다.

다음과 같은 특징을 가지는 3개의 프로세스가 존재할 때 STCF 스케줄링 흐름은 다음과 같다.

• 가장 먼저 도착한 A가 10만큼 일을 수행한다.
• 10초 시점에서 수행 시간이 짧은 B로 문맥 교환이 일어나며 B가 10만큼 일을 수행한다.
• 20초 시점에서 B가 끝나면 다음으로 C의 수행 시간이 짧기 때문에 C가 10만큼 일을 수행한다.
• 30초 시점에서 마지막으로 일이 남은 A가 90만큼 일을 수행한다.

위 그림을 토대로 반환 시간, 대기 시간을 구해보면 다음과 같다.

• 반환 시간(turnaround time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간 (완료 시간 - 도착 시간)
• 대기 시간(waiting time) : 프로세스가 준비 상태에서 대기한 시간 (시작 시간 - 도착 시간)

	대기 시간	반환 시간	도착 시간
A	0	120	0
B	0	10	10
C	10	20	10

위 표를 이용하여 평균 반환시간, 평균 대기시간을 구하면 다음과 같다.

• 평균 반환시간 : (120 + 10 +20) / 3 = 50
• 평균 대기시간 : (0 + 0 + 10) / 3 = 3.3333

SJF 스케줄링 정책과 비교했을 때 반환 시간, 대기 시간 모두 줄일 수 있다는 장점이 있다.