SJF란?

SJF(Shortest Job First) 스케줄링은은 준비큐에 있는 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU 를 할당하는 비선점형 방식이다.

최단 작업 우선 스케줄링이라고도 하며, 콘보이 효과를 완화하여 시스템의 효율성을 높인다.

평가

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움.
• 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐. (starvation 아사 현상)

Aging (나이먹기)

아사 현상의 완화 방법으로 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살 까지 양보하도록 규정하는 것이다.

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Comparator;

public class SJF {
    private List<Process> processQueue;

    public SJF(List<Process> incomingProcesses) {
        processQueue = new ArrayList<>(incomingProcesses);
        // 도착 시간으로 초기 정렬을 하여 준비 큐를 만듭니다.
        processQueue.sort(Comparator.comparingInt(proc -> proc.getArrivalTime()));
    }

    public void run() {
        PriorityQueue<Process> readyQueue = new PriorityQueue<>(Comparator.comparingInt(Process::getServiceTime));
        int currentTime = 0;
        int accumulatedWaitTime = 0;
        int accumulatedTurnaroundTime = 0;

        int processIndex = 0; // 이 인덱스는 전체 프로세스 목록을 추적합니다.

        System.out.println("PID | Arrival Time | Service Time | Start Time | Finish Time | Waiting Time | Turnaround Time");

        while (processIndex < processQueue.size() || !readyQueue.isEmpty()) {
            // 현재 시간에 맞춰 준비 큐에 프로세스를 추가합니다.
            while (processIndex < processQueue.size() && processQueue.get(processIndex).getArrivalTime() <= currentTime) {
                readyQueue.add(processQueue.get(processIndex));
                processIndex++;
            }

            if (readyQueue.isEmpty()) {
                // 다음 프로세스의 도착을 기다립니다.
                currentTime = processQueue.get(processIndex).getArrivalTime();
                continue;
            }

            Process currentProcess = readyQueue.poll(); // 가장 짧은 서비스 시간을 가진 프로세스 선택
            int startTime = currentTime;
            int finishTime = startTime + currentProcess.getServiceTime();
            int waitTime = startTime - currentProcess.getArrivalTime();
            int turnaroundTime = finishTime - currentProcess.getArrivalTime();

            System.out.printf("%3d | %12d | %12d | %10d | %11d | %12d | %15d\n",
                    currentProcess.getId(), currentProcess.getArrivalTime(), currentProcess.getServiceTime(), startTime, finishTime, waitTime, turnaroundTime);

            currentTime = finishTime; // 현재 시간 업데이트
            accumulatedWaitTime += waitTime; // 총 대기 시간 업데이트
            accumulatedTurnaroundTime += turnaroundTime; // 총 반환 시간 업데이트
        }

        // 평균 대기 시간과 평균 반환 시간을 계산하여 출력합니다.
        double averageWaitingTime = (double) accumulatedWaitTime / processQueue.size();
        double averageTurnaroundTime = (double) accumulatedTurnaroundTime / processQueue.size();

        System.out.printf("\nAverage Waiting Time: %.2f\n", averageWaitingTime);
        System.out.printf("Average Turnaround Time: %.2f\n", averageTurnaroundTime);
    }
}

결과