비선점형 SJF (Shortest Job First)

 비선점형의 의미

비선점형이란 한 번 CPU를 할당받은 프로세스가 자신의 작업을 완료할 때까지 CPU를 계속 사용하는 방식이다. 즉, 다른 프로세스가 도착하더라도 현재 실행 중인 프로세스는 끝까지 실행되며, 실행 도중에 중단되지 않는다.

def sjf(processes):
    processes.sort(key=lambda x: (x[1], x[0]))  # 도착 시간 -> 실행 시간 순으로 정렬
    time = 0
    waiting_time = 0
    completed = []

    while processes:
        # 도착한 프로세스들 중에서 실행 시간이 가장 짧은 프로세스 선택
        available_processes = [p for p in processes if p[0] <= time]
        if available_processes:
            process = min(available_processes, key=lambda x: x[2])
            processes.remove(process)
            print(f"Process {process[0]} is running")
            time += process[2]  # 실행 시간 더하기
            waiting_time += time - process[0] - process[2]  # 대기 시간 계산
            completed.append(process)
        else:
            time += 1  # 프로세스 도착 대기

    average_waiting_time = waiting_time / len(completed)
    print(f"Average Waiting Time: {average_waiting_time}")

# (도착 시간, 프로세스 이름, 실행 시간)
processes = [(0, 'P1', 6), (1, 'P2', 8), (2, 'P3', 7), (3, 'P4', 3)]
sjf(processes)

 
1. 정렬 후 실행: 프로세스들은 실행 시간이 짧은 순서대로 한 번 정렬되고 나면, 그 순서대로 차례대로 실행된다.
   
2. 중간에 인터럽트 없음: 한 프로세스가 실행을 시작하면, 그 프로세스는 완료될 때까지 CPU를 점유하고, 다른 프로세스가 그 사이에 도착하더라도 그 프로세스가 끝나기 전까지 기다린다.

중간에 프로세스를 멈추고 다른 프로세스를 실행하지 않기 때문에 비선점형이다.

 

 

 

SJF (Shortest Job First) 알고리즘을 사용하여 주어진 프로세스들을 처리하는 과정

 

  프로세스 정보
- P1: 도착 시간 0, 실행 시간 6
- P2: 도착 시간 1, 실행 시간 8
- P3: 도착 시간 2, 실행 시간 7
- P4: 도착 시간 3, 실행 시간 3

 SJF 실행 순서 및 대기 시간 계산

대기 시간 계산

• P4: 대기 시간 = 6 - 3 - 3 = 0
• P1: 대기 시간 = 12 - 0 - 6 = 6
• P3: 대기 시간 = 19 - 2 - 7 = 10
• P2: 대기 시간 = 27 - 1 - 8 = 18
• 총 대기 시간 = 0 + 6 + 10 + 18 = 34
• 평균 대기 시간 = 34 / 4 = 6.25