정보처리산업기사, 정보처리기사 - SJF, 우선 스케줄링 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다.

 

SJF(Shortest Job First) 알고리즘

SJF 알고리즘은 CPU 스케줄링에서 사용되며,

실행 시간이 가장 짧은 프로세스를 가장 먼저 처리하는 방식으로 동작합니다.

 

이 알고리즘은 실행 시간을 미리 알고 있어야 하며,

동일한 실행 시간을 가진 프로세스가 여러 개인 경우 FCFS 방식으로 처리됩니다.

 

SJF 알고리즘 동작 방식

1. 도착 시간 기다리기
   • 프로세스가 도착할 때까지 기다립니다.
2. 실행 시간 비교
   • 도착한 프로세스들 중에서 가장 짧은 실행 시간을 가진 프로세스를 선택합니다.
3. 프로세스 실행
   • 선택된 프로세스를 실행합니다.
4. 프로세스 완료

• 프로세스가 완료되면 다음으로 진행합니다.

 

 

SJF 알고리즘의 장단점

• 장점
  1. 평균 대기 시간을 최소화합니다.
  2. 짧은 프로세스에게 우선 순위를 부여하여 시스템 성능을 향상시킵니다.
• 단점
  1. 실행 시간을 미리 알아야 합니다.
  2. 실행 시간이 긴 프로세스가 도착 시간이 빠른 경우 기다리는 시간이 길어질 수 있습니다.

 

비선점형과 선점형 알고리즘

• 비선점형(SJF) 알고리즘
  • 비선점형 SJF 알고리즘은 한 번 시작된 프로세스의 실행을 중단시키지 않고 실행 시간이 가장 짧은 프로세스 부터 처리하는 방식입니다.
    프로세스가 시작되면 CPU를 할당받아 실행되며, 다른 프로세스가 도착하더라도 현재 실행 중인 프로세스가 완료될때까지 기다립니다.
• 선점형(SJF) 알고리즘
  • 선점형 SJF 알고리즘은 실행 중인 프로세스의 실행을 중단시킬 수 있고,
    도착한 프로세스 중에서 현재 실행 중인 프로세스보다 실행 시간이 더 짧은 프로세스가 도착하면 우선적으로 처리하는 방식입니다.
    이 경우, 실행 중인 프로세스가 중단되고 새로운 프로세스가 실행됩니다.
• 비선점형과 선점형 비교
  • 비선점형
    1. 실행 중인 프로세스를 중단시키지 않기 때문에 문맥 교환(context switch) 비용이 적습니다.
    2. 실행 시간을 미리 알아야 하며, 실행 시간이 긴 프로세스가 먼저 도착하면 기다리는 시간이 길어질 수 있습니다.
  • 선점형
    1. 실행 중인 프로세스를 중단시킬 수 있어서 더 짧은 프로세스가 도착하면 즉시 처리할 수 있습니다.
    2. 문맥 교환 비용이 비선점형에 비해 더 많이 발생할 수 있습니다.

※ 문맥 교환

컴퓨터 시스템에서 현재 실행 중인 프로세스나 스레드의 상태를 저장하고 다음으로 실행할 프로세스나 스레드의 상태를 복원하는 작업을 말합니다.

다중 프로세스 또는 다중 스레드를 지원하는 운영 체제에서 발생합니다.

 

※ 문맥 교환 비용

문맥 교환이 발생하면 CPU가 다음 프로세스나 스레드로 전환되어야 하므로 일정한 오버헤드가 발생합니다.

이를 문맥 교환 비용이라고 하며 문맥 교환 비용은 CPU의 성능과 시스템의 상태에 따라 다르지만,

전체 시스템 성능에 영향을 줄 수 있습니다.

 

SJF 알고리즘 예시

간단하게 프로세스 도착 시간과 실행 시간을 나타내는 표로 예시를 들겠습니다.

프로세스	도착 시간	실행 시간
P1	0	3
P2	1	5
P3	2	2
P4	3	8

 

이 표에서 SJF 알고리즘을 적용하면,

먼저 도착한 프로세스부터 시작하여 다음과 같이 처리됩니다.

프로세스 P1이 0초에 도착하여 3초 동안 실행이 됩니다.

그 다음 프로세스 P2가 먼저 도착하지만 P1이 실행하는 동안 P3, P4도 도착을 하고,

 

P3가 P2보다 실행시간이 더 짧기 때문에 P3를 먼저 실행하게 되어 2초 동안 실행을 하게 됩니다.

그 다음 P2가 실행되고 P4가 실행됩니다.

 

총 실행 시간은 3 + 5 + 2 + 8 = 18 초가 되며 평균 실행 시간은 18 / 4 = 4.5초 입니다.

총 대기 시간은 0 + 4 + 1 + 7 = 12 초가 되며 평균 대기 시간은 12 / 4 = 3초 입니다.