SRTF(Shortest Remaning Time First)

최소 잔류 시간 우선 스케줄링 (shortest remaining time)은 SJF 스케줄링을 비선점에서 선점 형태로 수정한 스케줄링 알고리즘으로 현재 작업 중인 프로세스를 중단시키고 새로 들어온 프로세스의 처리를 시작하는 방식이다. SRT 스케줄링 ,SRTF 스케줄링이라고도 한다.

import heapq

def solution(process:list) -> list:
    """[summary]
    SRTF Scheduling Algorithm 구현
    if) Processing_time is same, Next Priority: Process_id(Order by asc)
    
    Args:
        process (list): 작업들. [Arrival_time, Processing_time]

    Returns:
        list: 작업이 먼저 끝난 Process_id순으로
    """
    ans = []

    # 1. Order by Arrival time, Processing time, Process_id
    lst = []
    for i in range(len(process)):
        ## [Arrival_time, Processing_time, Process_id]
        lst.append([process[i][0], process[i][1], i+1])

    lst.sort()

    # 2. SRTF(Shortest Remaining Time First) Scheduling
    works = []
    heapq.heapify(works)
    ## element: [Processing_time, Process_id, Arrival_time]
    for arrival_t, process_t, p_id in lst:
        if not works:
            heapq.heappush(works, [process_t, p_id, arrival_t])
            continue

        running_time = arrival_t - works[0][2]
        works[0][0] -= running_time
        if works[0][0] <= 0:
            _, end_p_id, __ = heapq.heappop(works)
            ans.append(end_p_id)

        heapq.heappush(works, [process_t, p_id, arrival_t])

    while works:
        _, end_p_id, __ = heapq.heappop(works)
        ans.append(end_p_id)

    return ans

print(solution([[0, 8], [2, 4], [5, 1], [9, 8], [3, 2]]))