SJF(Shortest Job First)

최소작업 우선 스케줄링이란 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법이다.

Pros

• 항상 실행 시간이 짧은 작업을 먼저 실행하므로 평균 대기 시간이 가장 짧다.

Cons

• 기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행
  - 초기의 긴 작업을 짧은 작업을 종료할 때까지 대기시켜 기아(Starvation)가 발생
• 실행 시간을 예측하기 어려워 실용적이지 못함

구현

• 실행 시간이 짧은 작업을 먼저 작업 큐에 넣도록 최소 힙으로 구현
• 작업 큐가 비었을 경우엔 요청 시간(작업 도착 시간)이 빠른 것부터 큐에 넣음에 주의!!
  - 요청 시간이 같을 경우는 실행 시간이 짧은 순으로

import heapq

def solution(jobs:list) -> int:
    """[summary]
    Programmers 디스크 컨트롤러 문제
    
    SJF(Shortest Job First) Scheduling Algorithm
    - it has the shortest mean waiting time
    - it choose a shorter processing time
    
    Args:
        jobs (list): [Arrival_time, Processing_time]

    Returns:
        int: 작업의 요청부터 종료까지 걸린 time의 평균
    """
    ans = 0
    
    jobs.sort()

    # 1. init settings
    works = []
    N = len(jobs)
    # 2. SJF Scheduling
    ## element: [Processing_time, Arrival_time]
    cur_time = 0
    while jobs or works:
        if not works:
            a_t, p_t = jobs.pop(0)
            heapq.heappush(works, [p_t, a_t])
            continue
        
        w_p_t, w_a_t = heapq.heappop(works)
        if cur_time > w_a_t:
            ans += w_p_t + (cur_time - w_a_t)
            cur_time += w_p_t
        else:
            ans += w_p_t
            cur_time = w_p_t + w_a_t

        while jobs:
            a_t, p_t = jobs[0]
            if a_t < cur_time:
                heapq.heappush(works, [p_t, a_t])
                jobs.pop(0)
            else:
                break
    
    ans //= N

    return ans

print(solution([[0,3], [1,9], [2,6]]))
print(solution([[1, 9], [1, 7], [0, 3]]))