/
/

스케줄링

자격증정보처리스케줄링
avatar
전상욱
2025.04.11
·
13 min read

프로세스가 생성되여 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.
프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 된다.

스케줄링 종류

장기 스케줄링

- 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 의미한다.
- 작업 스케줄링 (Job Scheduling), 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행된다.

중기 스케줄링

- 어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업을 의미한다.
- CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절한다.

단기 스케줄링

- 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미한다.
- 프로세서 스케줄링 (Processor Scheduling), 하위 스케줄링이라고도 한다.
- 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행된다.

프로세서(스) 스케줄링의 기법

비선점 (Non-Preemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

  • 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.

  • 모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.

  • 프로세스 응답 시간의 예측이 용이하며, 일괄 처리방식에 적합하다.

  • 중요한 작업 (짧은 작업)이 중요하지 않은 작업 (긴 작업)을 기다리는 경우가 발생할 수 있다.

비선점 스케줄링의 종류에는 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있다.

선점 (Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

  • 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.

  • 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용된다.

  • 많은 오버헤드(Overhead)를 초래한다.

  • 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록(Clock)이 필요하다.

선점 스케줄링의 종류에는 Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘이 있다.

주요 스케줄링 기법

FCFS (First Come First Service, 선입 선출) = FIFO (First In First Out)

준비상태 큐 (대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘이다.

- 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을 기다리게 된다.
또한, 중요한 작업이 중요하지 않은 작업을 기다리게 된다.

문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, FCFS 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.
(제출시간은 없으며 시간의 단위는 초이다.)

프로세스 번호

P1

P2

P3

실행 시간

20

4

6

1. 실행 시간을 이용하여 다음과 같이 각 프로세스의 대기 시간과 반환 시간을 구한다.
1.1. 대기 시간 : 프로세스가 대기한 시간으로, 바로 앞 프로세스까지의 진행 시간으로 계산
1.2. 반환 시간 : 프로세스의 대기 시간과 실행 시간의 합
2. 실행 시간, 대기 시간, 반환 시간의 평균은 각 프로세스 시간의 합 / 프로세스의 개수를 이용한다.

5137

평균 실행 = (20 + 4 + 6) / 3 = 10
평균 대기 = (0 + 20 + 24) / 3 = 14.6
평균 반환 = (20 + 24 + 30) / 3 = 24.6

SJF (Shortest Job First, 단기 작업 우선)

SJF는 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다.

문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.
(제출 시간이 없을 경우)

프로세스 번호

P1

P2

P3

실행 시간

20

4

6

1. 실행 시간이 짧은 프로세스를 먼저 처리하도록 이동시킨 후 각 프로세스의 대기시간과 반환 시간을 구한다.
2. 실행 시간, 대기 시간, 반환 시간, 각 시간의 평균은 FCFS의 방법과 동일하게 구한다.

5138

평균 실행 = (20 + 4 + 6) / 3 = 10
평균 대기 = (0 + 4 + 10) / 3 = 4.6
평균 반환 = (4 + 10 + 30) / 3 = 14.6

문제 2. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.
(제출 시간이 있을 경우)

프로세스 번호

P1

P2

P3

실행 시간

20

7

4

도착 시간

0

1

2

1. 가장 먼저 도착한 P1을 실행한 후 요구된 실행 시간이 적은 P3, P2 순으로 수행한다.
2. 대기 시간은 현재 프로세스가 수행되기 전까지의 진행 시간에서 도착 시간을 차감하고, 반환시간은 실행 시간과 대기 시간의 합으로 구한다.

5165

평균 실행 = (20 + 4 + 7) / 3 = 10.3
평균 대기 = (0 + 18 + 23) / 3 = 13.6
평균 반환 = (20 + 22 + 30) / 3 = 24

HRN (Highest Response-ratio Next)

HRN은 실행 시간이 킨 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로,
대기 시간과 서비스 (실행) 시간을 이용하는 기법이다.

우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여된다.

5139

문제 1. 다음과 같은 프로세스가 HRN 기법으로 스케줄링될 때 우선순위를 계산하시오.

프로세스 번호

P1

P2

P3

실행 시간

20

4

6

대기 시간

10

20

10

우선순위 계산

(10 + 20) / 20 = 1.5

(20 + 4) / 4 = 6

(10 + 6) / 6 = 2.6

우선순위 : P2 > P3 > P1

RR (Round Robin)

RR (Round Robin)은 시분할 시스템 (Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점 (Preemptive) 형태로 변형한 기법이다.

할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생된다.

문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, 평균 대기 시간, 평균 반환 시간을 구하시오.
(단, Time Slice는 4초이다.)

프로세스 번호

P1

P2

P3

실행 시간

20

4

6

1. 주어진 시간 할당량 (Time Slice) 동안 실행되지 못할 경우 준비상태 큐의 가장 마지막으로 재배치하여 차례를 기다리므로 다음과 같이 표시할 수 있다.

5167

2. 반환 시간 : 각 프로세스가 완료되는 시간을 이용하여 구한다.
3. 대기 시간 : 대기 시간을 구하고자 하는 프로세스의 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구하되, 해당 프로세스가 앞에서 여러 번 실행되었을 경우 실행된 시간은 제외한다.

프로세스 번호

P1

P2

P3

평균

반환 시간

30

8

18

56 / 3 = 18.6

대기 시간

26 - 16 = 10

4

16 - 4 = 12

26 / 3 = 8.6

- 컬렉션 아티클