SJF(Shortest Job First) 스케줄링의 선점형 버전을 SRTF(Shortest Remaining Time First)라고 합니다. SRTF에서는 완료까지 남은 시간이 가장 적은 프로세스가 실행되도록 선택됩니다. 실행 중인 프로세스는 완료되거나 남은 시간이 더 짧은 새 프로세스가 도착할 때까지 계속되므로 가장 빠른 마무리 프로세스가 항상 우선 순위를 갖습니다.
SJF 알고리즘의 예:
시나리오 1: 도착 시간이 동일한 프로세스
예: 세 가지 프로세스의 도착 시간과 버스트 시간에 대한 다음 표를 고려하십시오. P1 P2 및 P3 .
| 프로세스 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6ms | 0ms |
| P2 | 8ms | 0ms |
| P3 | 5ms | 0ms |
단계별 실행:
- 시간 0-5 (P3) : P3은 남은 시간이 가장 짧아서 5ms(총 남은 시간: 0ms) 동안 실행됩니다.
- 시간 5-11 (P1) : P1은 남은 시간이 가장 짧아서 6ms(총 남은 시간: 0ms) 동안 실행됩니다.
- 시간 11-19 (P2) : P2는 남은 시간이 가장 짧으므로 8ms 동안 실행됩니다(총 남은 시간: 0ms).
간트 차트:
반복자 자바 맵
이제 평균을 계산해보자 기다리는 시간과 돌아서 시간:
우리가 알고 있듯이
- 턴어라운드 시간 = 완료시간 - 도착시간
- 대기시간 = 턴어라운드 시간 - 버스트 시간
| 프로세스 | 도착 시간 (에) | 버스트 시간 js 세트 (BT) | 완료 시간(CT) | 처리 시간(TAT) | 대기 시간(WT) |
|---|---|---|---|---|---|
| P1 | 6 | 11 | 11-0 = 11 | 11-6 = 5 | |
| P2 | 프레임 tkinter | 8 | 19 | 19-0 = 19 | 19-8 = 11 |
| P3 | 5 | 5 | 5-0 = 5 | 5-5 = 0 |
지금
- 평균 처리 시간 = (11 + 19 + 5)/3 = 11.6ms
- 평균 대기 시간 = (5 + 0 + 11 )/3 = 16/3 = 5.33ms
시나리오 2: 도착 시간이 다른 프로세스
세 가지 프로세스 P1, P2 및 P3에 대한 도착 시간 및 버스트 시간에 대한 다음 표를 고려하십시오.
| 프로세스 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6ms | 0ms |
| P2 | 3ms | 1ms |
| P3 | 7ms | 2ms |
단계별 실행:
kmp 알고리즘
- 시간 0-1 (P1) : P1은 남은 시간이 가장 짧기 때문에 1ms(총 남은 시간: 5ms) 동안 실행됩니다.
- 시간 1-4 (P2) : P2는 P1과 P2 중 남은 남은 시간이 가장 짧기 때문에 3ms 동안 실행됩니다(총 남은 시간: 0ms).
- 시간 4-9 (P1) : P1은 P1과 P3 중 남은 남은 시간이 가장 짧기 때문에 5ms 동안 실행됩니다(총 남은 시간: 0ms).
- 시간 9-16 (P3) : P3은 남은 시간이 가장 짧기 때문에 7ms 동안 실행됩니다(총 남은 시간: 0ms).
간트 차트:
이제 평균을 계산해보자 기다리는 시간과 돌아서 시간:
| 프로세스 | 도착 시간(AT) | 버스트 시간(BT) | 완료 시간(CT) | 처리 시간(TAT) | 대기 시간(WT) |
|---|---|---|---|---|---|
| P1 | uml 다이어그램 자바 | 6 | 9 | 9-0 = 9 | 9-6 = 3 |
| P2 | 1 | 3 | 4 | 4-1 = 3 | 3-3 = 0 |
| P3 | 2 | 7 | 16 | 16-2 = 14 | 14-7 = 7 |
- 평균 처리 시간 = (9 + 14 + 3)/3 = 8.6ms
- 평균 대기 시간 = (3 + 0 + 7 )/3 = 10/3 = 3.33ms
SRTF 알고리즘 구현
1단계: 도착 시간 및 버스트 시간과 함께 프로세스 수를 입력합니다.
2단계: 남은 시간(버스트 시간)을 현재 시간 = 0으로 초기화하고 카운터합니다.
3단계: 매 시간 단위마다 준비 대기열에 도착한 프로세스를 추가합니다.
4단계: 남은 시간이 가장 짧은 프로세스를 선택합니다(더 짧은 시간이 도착하면 선점).
5단계: 1 단위에 대해 선택한 프로세스를 실행하여 남은 시간을 줄이고 현재 시간을 늘립니다.
6단계: 프로세스가 완료되면:
- 처리 시간 = 완료 시간 − 도착 시간
- 대기 시간 = 처리 시간 − 버스트 시간
7단계: 모든 프로세스가 완료될 때까지 3~6단계를 반복합니다.
8단계: 평균 대기 시간과 처리 시간을 계산합니다.
9단계: 평균과 함께 각 프로세스의 완료 대기 및 처리 시간을 표시합니다.
코드 구현
Shortest Remaining Time First를 구현하는 프로그램은 다음과 같습니다.
C++#include
import java.util.*; class Process { int id arrivalTime burstTime remainingTime waitingTime turnaroundTime completionTime; public Process(int id int arrivalTime int burstTime) { this.id = id; this.arrivalTime = arrivalTime; this.burstTime = burstTime; this.remainingTime = burstTime; } } public class SRTF { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Process[] processes = new Process[n]; for (int i = 0; i < n; i++) { int arrivalTime = sc.nextInt() burstTime = sc.nextInt(); processes[i] = new Process(i + 1 arrivalTime burstTime); } Arrays.sort(processes Comparator.comparingInt(p -> p.arrivalTime)); int currentTime = 0 completed = 0; while (completed < n) { int idx = -1; for (int i = 0; i < n; i++) { if (processes[i].arrivalTime <= currentTime && processes[i].remainingTime > 0 && (idx == -1 || processes[i].remainingTime < processes[idx].remainingTime)) { idx = i; } } if (idx != -1) { processes[idx].remainingTime--; currentTime++; if (processes[idx].remainingTime == 0) { processes[idx].completionTime = currentTime; processes[idx].turnaroundTime = currentTime - processes[idx].arrivalTime; processes[idx].waitingTime = processes[idx].turnaroundTime - processes[idx].burstTime; completed++; } } else { currentTime++; } } double totalWT = 0 totalTAT = 0; for (Process p : processes) { totalWT += p.waitingTime; totalTAT += p.turnaroundTime; System.out.println('P' + p.id + ' CT: ' + p.completionTime + ' WT: ' + p.waitingTime + ' TAT: ' + p.turnaroundTime); } System.out.println('Avg WT: ' + totalWT / n + ' Avg TAT: ' + totalTAT / n); } }
class Process: def __init__(self id arrival_time burst_time): self.id = id self.arrival_time = arrival_time self.burst_time = burst_time self.remaining_time = burst_time def srtf(processes): current_time completed = 0 0 while completed < len(processes): idx = -1 for i p in enumerate(processes): if p.arrival_time <= current_time and p.remaining_time > 0 and (idx == -1 or p.remaining_time < processes[idx].remaining_time): idx = i if idx != -1: processes[idx].remaining_time -= 1 current_time += 1 if processes[idx].remaining_time == 0: processes[idx].completion_time = current_time processes[idx].turnaround_time = current_time - processes[idx].arrival_time processes[idx].waiting_time = processes[idx].turnaround_time - processes[idx].burst_time completed += 1 else: current_time += 1 def print_results(processes): total_wt total_tat = 0 0 for p in processes: total_wt += p.waiting_time total_tat += p.turnaround_time print(f'P{p.id} CT: {p.completion_time} WT: {p.waiting_time} TAT: {p.turnaround_time}') print(f'Avg WT: {total_wt / len(processes)} Avg TAT: {total_tat / len(processes)}') n = int(input('Enter number of processes: ')) processes = [Process(i + 1 *map(int input(f'Enter arrival and burst time for P{i + 1}: ').split())) for i in range(n)] srtf(processes) print_results(processes)
산출
Enter number of processes: Avg WT: -nan Avg TAT: -nan
SRTF의 장점 스케줄링
- 평균 대기 시간 최소화 : SRTF는 남은 실행 시간이 가장 짧은 프로세스의 우선 순위를 지정하여 평균 대기 시간을 줄입니다.
- 짧은 프로세스에 효율적 : 짧은 프로세스가 더 빨리 완료되어 전반적인 시스템 응답성이 향상됩니다.
- 시간이 중요한 시스템에 이상적 : 시간에 민감한 프로세스가 신속하게 실행되도록 보장합니다.
SRTF의 단점 스케줄링
- 긴 프로세스의 기아 상태 : 더 짧은 프로세스가 계속 도착하면 더 긴 프로세스가 무한정 지연될 수 있습니다.
- 버스트 시간 예측이 어려움 : 프로세스 버스트 시간을 정확하게 예측하는 것은 어렵고 일정 결정에 영향을 미칩니다.
- 높은 오버헤드 : 빈번한 컨텍스트 전환은 오버헤드를 증가시키고 시스템 성능을 저하시킬 수 있습니다.
- 실시간 시스템에는 적합하지 않음 : 실시간 작업은 잦은 선점으로 인해 지연이 발생할 수 있습니다.