srt

SRT(Shortest Remaining Time) 알고리즘 설명

문제: SRT(Shortest Remaining Time) 알고리즘의 작동 방식과 특징에 대해 설명하세요.

답변:

1. 개념
   SRT(Shortest Remaining Time)는 선점형(Preemptive) 스케줄링 알고리즘으로, ‘남은 실행 시간이 가장 짧은 작업’을 우선 처리하는 방식입니다. 비선점형인 SJF(Shortest Job First)와 유사하지만, 실행 중인 프로세스보다 남은 시간이 더 짧은 프로세스가 도착할 경우, 현재 실행 중인 프로세스를 중단하고 새로 도착한 프로세스를 실행하는 방식이 차이점입니다. 이를 통해 평균 대기 시간과 평균 반환 시간을 최소화하는 효과가 있습니다.

2. 작동 원리
   • 프로세스가 대기 큐에 도착하면 시스템은 모든 프로세스의 남은 실행 시간을 비교합니다.
   • 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 있다면, 현재 프로세스는 대기 상태로 전환되고 새로 도착한 프로세스가 CPU를 할당받습니다.
   • 만약 대기 중인 프로세스가 없거나 현재 실행 중인 프로세스의 남은 실행 시간이 가장 짧다면, 현재 프로세스는 계속 실행됩니다.

3. 작동 순서

   1. 모든 프로세스가 대기 큐에 들어오면 남은 실행 시간을 기준으로 프로세스를 정렬합니다.
   2. 실행 중인 프로세스보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착할 때마다 작업을 선점하여 교체합니다.
   3. 남은 실행 시간이 0이 되어 작업이 종료될 때까지 이 과정을 반복합니다.

4. 예시
   다음은 SRT 알고리즘의 예시입니다.
   • P1: 도착 시간 0, 실행 시간 8
   • P2: 도착 시간 1, 실행 시간 4
   • P3: 도착 시간 2, 실행 시간 2
   • P4: 도착 시간 3, 실행 시간 1

실행 순서
1. 0초: P1이 실행을 시작합니다.
2. 1초: P2가 도착하며, P1의 남은 시간이 7초로 더 깁니다. P1은 중단되고 P2가 실행됩니다.
3. 2초: P3가 도착하고, P2의 남은 시간(3초)보다 P3의 총 실행 시간(2초)이 더 짧으므로 P3가 실행됩니다.
4. 3초: P4가 도착하고, P3의 남은 시간(1초)보다 P4의 실행 시간(1초)이 짧으므로 P4가 실행됩니다.
5. 이후 P3와 P2가 순차적으로 실행되고, 마지막으로 P1이 다시 실행됩니다.

5. 대기 시간 계산
   대기 시간은 각 프로세스가 준비 큐에 도착한 후부터 CPU를 할당받을 때까지의 시간을 의미합니다.
   • P1: 총 대기 시간 = 중간에 선점된 시간의 합
   • P2, P3, P4: 중간에 CPU 할당받기 전까지의 대기 시간

6. 장점
   • 평균 대기 시간과 반환 시간을 최소화할 수 있어 시스템 효율이 높아집니다.
   • 특히 짧은 작업을 우선으로 하여 응답성을 향상합니다.

7. 단점
   • 작업이 자주 중단되기 때문에, 오버헤드가 발생하여 시스템 리소스가 많이 소모될 수 있습니다.
   • 긴 작업은 계속 선점될 수 있어 ‘기아(starvation)’ 문제가 발생할 수 있습니다.

8. SRT와 SJF 비교
   • SJF는 비선점형으로, CPU를 할당받은 작업은 중단되지 않고 끝까지 실행됩니다.
   • SRT는 선점형으로, 남은 실행 시간이 더 짧은 작업이 도착하면 현재 작업이 중단될 수 있습니다.

9. 개선 가능성
   SRT 알고리즘은 기아 문제를 완화하기 위해 우선순위 조정을 추가하거나, 최대 대기 시간 제한을 두는 방식으로 보완할 수 있습니다.