[정보처리기사/OS] SJF 최단 작업 우선스케줄링 알고리즘

1. 요약
2. 1. SJF 최단 작업 우선스케줄링 알고리즘이란?
3. 2. SJF 알고리즘의 동작 원리
4. 3. SJF 알고리즘의 장점과 단점
5. 4. 비선점형 SJF와 선점형 SJF 설명
6. 5. SJF 알고리즘의 예시
7. 6. SJF 알고리즘의 시간 복잡도

 

 

 

 

SJF는 프로세스를 스케줄링 하는 알고리즘 중에서 실행시간이 가장 빠른 순서대로 진행한다.

 

 

 

요약

SJF 최단 작업 우선스케줄링 알고리즘은 작업의 실행 시간이 가장 짧은 순서대로 프로세스를 스케줄링하는 알고리즘입니다. 실행 시간이 짧은 작업을 우선적으로 처리하여 평균 대기 시간을 최소화합니다.

 

대기 시간을 감소시키는 SJF

 

 

 

 

1. SJF 최단 작업 우선스케줄링 알고리즘이란?

SJF(Shortest Job First) 알고리즘은 작업의 실행 시간이 가장 짧은 순서대로 프로세스를 스케줄링하는 프로세스 스케줄링 알고리즘입니다. 이 알고리즘은 프로세스의 실행 시간을 예측하여 짧은 작업을 먼저 처리하는 방식으로 작동합니다.

 

SJF는 무조건 실행시간이 짧은 프로세스가 우선 처리되는 알고리즘이다.

 

 

 

2. SJF 알고리즘의 동작 원리

SJF 알고리즘은 준비 큐 내의 프로세스 중에서 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식으로 동작합니다. 새로운 프로세스가 도착할 때마다 현재 실행 중인 프로세스의 남은 실행 시간과 비교하여 스케줄링 결정을 합니다.

 

비선점 SJF 알고리즘 (https://wonit.tistory.com/104)

 

 

 

 

 

3. SJF 알고리즘의 장점과 단점

장점: 실행 시간이 짧은 작업을 우선적으로 처리하기 때문에 평균 대기 시간을 최소화할 수 있습니다.

단점: 실행 시간을 정확하게 예측하기 어렵기 때문에 실제로는 많은 프로세스에서 사용하기 어렵습니다. 또한, 긴 작업이 계속해서 도착하는 경우 짧은 작업이 무한정 대기할 수 있는 문제가 발생할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

4. 비선점형 SJF와 선점형 SJF 설명

비선점형 SJF: 프로세스가 실행을 시작하면 그 동안 중단되지 않고 작업을 완료할 때까지 프로세스가 CPU를 점유합니다.

 

비선점 SJF 모델

 

 

 

선점형 SJF: 더 짧은 실행 시간을 가진 프로세스가 도착하면 현재 실행 중인 프로세스를 중단하고 새로운 프로세스로 교체합니다.

 

선점형 SJF 모델

 

 

 

 

5. SJF 알고리즘의 예시

SJF 알고리즘의 예시를 살펴보겠습니다.

프로세스 별 작업 시간이 다음과 같다고 가정합니다:

• 프로세스 A: 5
• 프로세스 B: 3
• 프로세스 C: 8
• 프로세스 D: 6

이 경우 SJF 알고리즘에 따라 프로세스가 실행되는 순서는 다음과 같습니다:

1. 프로세스 B (3)
2. 프로세스 A (5)
3. 프로세스 D (6)
4. 프로세스 C (8)

 

 

 

6. SJF 알고리즘의 시간 복잡도

SJF 알고리즘의 시간 복잡도는 작업의 개수와 정렬 알고리즘에 따라 다를 수 있습니다. 대부분의 경우에는 작업을 정렬하는 과정이 가장 오래 걸리며, 이는 O(n log n)의 시간 복잡도를 갖습니다.