CPU Scheduling (2) - SJF (Shortest Job First)

0. 스케줄링 개요

실행시간이 가장 짧은 작업을 먼저 실행시켜주는 스케줄링 방법이다. FCFS에서는 작업시간이 길다고 하더라도 먼저 큐에 들어오면 그 작업을 먼저 실행시켜줬는데, 이렇게 하면 Convoy Effect (호위효과)가 발생한다. 즉, 짧은 작업들이 긴 작업 뒤에 오랫동안 나란히 대기하고 있어야한다.

 

예를 들어 우리가 화장실에 갔는데 소변을 누길 원하는 2명과 대변을 누길 원하는 1명의 사람이 있다고 해보자. 그러면 상식적으로 생각해도 2명이 소변을 빠르게 누고와서 그 후에 대변을 누는 사람이 들어가는 게 맞다. 만약 대변을 누는 사람이 먼저 들어가면 소변을 누는 사람 2명은 매우 오랫동안 참고 기다려야한다. 이는 상식적으로 생각해도 매우 비효율적이다. 때문에 작업시간이 가장 짧은 작업을 먼저 실행하는 것이다. SJF 스케줄링은 우리가 일번적으로 알고있는 공중화장실의 암묵적인 규칙을 컴퓨터 프로세스에 적용한 것과 동일하다! (띠용)

 

1. SJF는 Average Waiting Time이 짧다

SJF와 FCFS와 AWT(Average Waiting Time)를 비교해보자. 3개의 프로세스 P1, P2, P3가 순서대로 있고 각각 대기시간이 24(대변), 3(소변), 3(소변) msec이라고 해보자. 만약 FCFS 스케줄링을 적용하여 가장 먼저 도착한 P1부터 실행하면 P1의 대기시간은 0msec(바로실행), P2의 대기시간은 24msec, P3의 대기시간은 27msec으로 평균 대기시간은 (0 + 24 + 27) / 3으로  17msec이 된다.

 

그러나 SJF를 적용하여 P2, P3, P1 순으로 실행한다면 P2의 대기시간은 0msec, P3의 대기시간은 3msec, P1의 대기시간은 6msec이 되어 평균 대기시간은 (0 + 3 + 6) / 3으로 3msec이 된다. 수학적으로도 SJF가 최적의 결과를 낸다는 것이 증명되었다. (여기에서 증명은 중요한게 아니니 생략한다)

 

2. 그러나 SJF는 비현실적인 스케줄링 기법이다.

위처럼 프로세스를 실행하기도 전에 그 프로세스가 얼마걸릴지 알고, 짧은 순서대로 실행할 수 있다면 참 좋겠지만, 프로세스 시작전에 프로세스가 얼마나 걸릴지 어떻게 알겠는가. 즉, SJF는 이상적이고 매우 빠른 스케줄링 기법이지만 실행하기 전에 그 프로세스가 얼마나 걸릴지 모르기 때문에 어떠한 예측 과정을 거쳐야한다. 때문에 현실적으로 SJF를 그대로 적용하는 것은 매우 어렵다.

 

+) 예측은 어떻게 할까?

일반적으로 Time Sharing System을 지원하는 OS라면 프로세스가 계속 실행(Running)되는 것이 아니라 일정 분량의 작업을 수행하고 다시 Ready Queue에 들어가거나(Ready), I/O 작업을 실행하기 위해 Device Queue에 들어간다.(Waiting) 프로세스가 CPU의 서비스를 받을 때마다 CPU는 프로세스별로 어떤 프로세스가 한번의 서비스에서 얼마나 많은 CPU Time을 소모했는지 계속해서 기록해놓다가 미래에 일어날 작업의 CPU 시간을 예측하게 된다. 그러나 이런 예측과정을 거치기 위해서는 더 많은 오버헤드가 발생한다는 단점이 있다. (Context Switching은 매우 잦기 때문에 오버헤드가 굉장히 많이 일어나게 된다)

 

3. SJF는 비선점 스케줄링이지만, SRTF는 선점 스케줄링이다.

일반적으로 SJF 스케줄링은 비선점 스케줄링 (non Preemptive) 이다. 그러나 약간 바꾸면 선점 스케줄링으로도 사용 가능하다. SJF의 선점 스케줄링 버전은 SRTF(Shortest Remaining Time First)라고 불리는데, 아래 예시를 통해서 자세히 알아보자.

 

※ 프로세스 명세

PID	도착 시간	총 실행 시간
P1	0초	8초
P2	1초	4초
P3	2초	9초
P4	3초	5초

 

※ SJF 스케줄링 (비선점)

1) 가장 처음에 P1이 도착하여 실행된다. 실행중인 프로세스는 빨간색으로 표시한다.

Queue = [P1]

 

2) P1의 실행중에 P2, P3, P4가 차례대로 도착한다. 실행시간이 짧은 순으로 Queue에 삽입된다. SJF는 비선점 스케줄링이기 때문에 현재 진행중인 프로세스가 끝나기 전까지 프로세스를 전환하지 않는다.

Queue = [P1, P2, P4, P3] 

 

3)  P1이 끝나면 가장 실행시간이 짧은 P2를 실행한다.

Queue = [P2, P4, P3]

 

4) P2가 끝나면 P4를 실행한다.

Queue = [P4, P3]

 

5) P4가 끝나면 P3를 실행한다.

Queue = [P3]

 

6) P3가 끝나고 모든 프로세스가 종료되었다.

Queue = []

 

7) AWT 계산

PID	도착시간	총 실행시간	대기시간
P1	0초	8초	0초
P2	1초	4초	(8=8) - 1초 = 7초
P3	2초	9초	(8+4+5=17) - 2초 = 15초
P4	3초	5초	(8+4=12) - 3초 = 9초
총 계			(0+7+15+9)/4 = 7.75초

 

 

※ SRTF 스케줄링 (선점)

1) 가장 처음에 P1이 도착하여 실행된다. 마찬가지로 실행 중인 프로세스는 빨간색으로 표시하고 남은시간을 옆에 기록한다. 큐 옆에는 현재까지 진행된 시간을 적는다.

Queue(0) = [P1(8)]

 

2) 1초가 지나고 P2가 도착한다. P1의 남은 시간은 7초, P2의 남은시간은 4초이기 때문에 P1을 밀어내고 P2를 먼저 실행한다.

Queue(1) = [P2(4), P1(7)]

 

3) 또 1초가 지나고 P3가 도착한다. P1(7), P2(3), P3(9)중 가장 짦은 것은 여전히 P2이기 때문에 그대로 실행하고, P3는 P1의 뒤쪽에 위치시킨다.

Queue(2) = [P2(3), P1(7), P3(9)]

 

4) 또 1초가 지나고 P4가 도착한다. P1(7), P2(2), P3(9), P4(5) 중에 여전히 가장 짧은 것은 P2이다. 때문에 그대로 실행하고 P3는 P1보다는 실행시간이 짧기 때문에 P1보다 앞에 위치시킨다.

Queue(3) = [P2(2), P4(5), P1(7), P3(9)]

 

5) 2초가 흐르고 P2가 종료된다. 앞서서 들어온 프로세스들이 실행된다.

Queue(5) = [P4(5), P1(7), P3(9)]

 

6) 5초가 흐르고 P4가 종료된다. P1이 다시 재개된다.

Queue(10) = [P1(7), P3(9)]

 

7) 7초가 흐르고 P1이 종료된다. P3가 실행된다.

Queue(17) = [P3(9)]

 

8) 9초가 흐르고 P3가 종료된다. 모든 프로세스가 종료되었다.

Queue(26) = []

 

9) AWT 계산

PID	도착시간	총 실행시간	대기시간	계
P1	0초	8초	4(P2) + 5(P4)	9초
P2	1초	4초	0	0초
P3	2초	9초	3(P2) + 5(P4) + 7(P1)	15초
P4	3초	5초	2(P2)	2초
총 계				(9+0+15+2)/4 = 6.5초

결과적으로 AWT로 보면 SJF보다 SRTF가 더 짧다. (P2가 P1을 기다릴 필요가 없다는 것이 주요하다)

 

4. SJF 소스코드

1) Job 클래스

package jobs;

/**
 * @author : Hyunwoong
 * @when : 2020-02-04 오후 8:34
 * @homepage : https://github.com/gusdnd852
 */
public class Job {
    public int PID;
    public int remain;

    public Job(int PID, int remain) {
        this.PID = PID;
        this.remain = remain;
    }

    @Override
    public String toString() {
        return "P" + String.valueOf(PID) + "(" + remain + ")";
    }
}

 

2) SJF 스케줄러 클래스

package schedulers;

import jobs.Job;

import java.util.Comparator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * @author : Hyunwoong
 * @when : 2020-02-04 오후 8:30
 * @homepage : https://github.com/gusdnd852
 */
public class SjfScheduler {
    private List<Job> readyQueue = new CopyOnWriteArrayList<>();
    private ExecutorService runningThread = Executors.newSingleThreadExecutor();

    void insert(Job job) {
        readyQueue.add(job);
        readyQueue.sort(Comparator.comparingInt(j -> j.remain));
        // 가장 짧은 작업시간을 가진 프로세스를 앞으로 보내서 먼저 실행하게 함.
        // 그러나 현재 작업중인 프로세스를 밀어내지는 못함 (비선점 스케줄링)   
    }

    void flowTime() {
    	sleep(990);
        // 오버헤드 고려해서 10msec 빠르게
    }

    void start() {
        runningThread.execute(() -> {
            while (readyQueue.size() != 0) {
                for (Job job : readyQueue) {
                    while (job.remain > 0) {
                        log(job);
                        sleep(1000);
                        job.remain--;

                        if (job.remain == 0)
                            readyQueue.removeIf(j -> j.remain == 0);
                    }
                }
            }

            runningThread.shutdownNow();
            System.exit(0);
        });
    }

    public static void main(String[] args) {
        SjfScheduler scheduler = new SjfScheduler();

        scheduler.insert(new Job(1, 8));
        scheduler.start(); // time : 0 sec.

        scheduler.flowTime(); // time : 1 sec.
        scheduler.insert(new Job(2, 4));

        scheduler.flowTime(); // time : 2 sec.
        scheduler.insert(new Job(3, 9));

        scheduler.flowTime(); // time : 3 sec.
        scheduler.insert(new Job(4, 5));
    }

    void log(Job job) {
        System.out.println(job + " is running " + readyQueue);
    }

    void sleep(int msec) {
        try {
            TimeUnit.MILLISECONDS.sleep(msec);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

출력 : 

P1(8) is running [P1(8)]
P1(7) is running [P2(4), P1(7)]
P1(6) is running [P2(4), P1(6), P3(9)]
P1(5) is running [P2(4), P1(5), P4(5), P3(9)]
P1(4) is running [P2(4), P1(4), P4(5), P3(9)]
P1(3) is running [P2(4), P1(3), P4(5), P3(9)]
P1(2) is running [P2(4), P1(2), P4(5), P3(9)]
P1(1) is running [P2(4), P1(1), P4(5), P3(9)]
P2(4) is running [P2(4), P4(5), P3(9)]
P2(3) is running [P2(3), P4(5), P3(9)]
P2(2) is running [P2(2), P4(5), P3(9)]
P2(1) is running [P2(1), P4(5), P3(9)]
P4(5) is running [P4(5), P3(9)]
P4(4) is running [P4(4), P3(9)]
P4(3) is running [P4(3), P3(9)]
P4(2) is running [P4(2), P3(9)]
P4(1) is running [P4(1), P3(9)]
P3(9) is running [P3(9)]
P3(8) is running [P3(8)]
P3(7) is running [P3(7)]
P3(6) is running [P3(6)]
P3(5) is running [P3(5)]
P3(4) is running [P3(4)]
P3(3) is running [P3(3)]
P3(2) is running [P3(2)]
P3(1) is running [P3(1)]

FCFS 코드와 비교하면, readyQueue에 넣기 전에 job을 시간순으로 정렬하고 넣은 것 외에는 차이가 없다. FCFS 글에도 코드가 있으니, 반드시 비교해서 실행해보길 권장한다. 대기시간으로만 치면 SJF가 FCFS보다 월등하게 짧다.

 

3) SRTF 스케줄러 클래스

package schedulers;

import jobs.Job;

import java.util.Comparator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * @author : Hyunwoong
 * @when : 2020-02-04 오후 8:30
 * @homepage : https://github.com/gusdnd852
 */
public class SrtfScheduler {
    private List<Job> readyQueue = new CopyOnWriteArrayList<>();
    private ExecutorService runningThread = Executors.newSingleThreadExecutor();

    void insert(Job job) {
        readyQueue.add(job);
        readyQueue.sort(Comparator.comparingInt(j -> j.remain));
    }

    void flowTime() {
    	sleep(990);
        // 오버헤드 고려해서 10msec 빠르게
    }

    void start() {
        runningThread.execute(() -> {
            while (readyQueue.size() != 0) {
                for (Job job : readyQueue) {
                    while (job.remain > 0) {
                        if (!job.equals(readyQueue.get(0)))
                            break;
                            // 현재 작업중인 프로세스보다 짧은 프로세스가 들어와서
                            // 현재 작업보다 앞쪽에 (0번 인덱스) 있으면 프로세스를
                            // 일시정지하고, 해당 프로세스로 건너 뜀 (선점 스케줄링)

                            log(job);
                            sleep(1000);
                            job.remain--;

                            if (job.remain == 0)
                                readyQueue.removeIf(j -> j.remain == 0);
                    }
                }
            }

            runningThread.shutdownNow();
            System.exit(0);
        });
    }


    public static void main(String[] args) {
        SrtfScheduler scheduler = new SrtfScheduler();

        scheduler.insert(new Job(1, 8));
        scheduler.start(); // time : 0 sec.

        scheduler.flowTime(); // time : 1 sec.
        scheduler.insert(new Job(2, 4));

        scheduler.flowTime(); // time : 2 sec.
        scheduler.insert(new Job(3, 9));

        scheduler.flowTime(); // time : 3 sec.
        scheduler.insert(new Job(4, 5));
    }

    void log(Job job) {
        System.out.println(job + " is running " + readyQueue);
    }

    void sleep(int msec) {
        try {
            TimeUnit.MILLISECONDS.sleep(msec);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

출력 : 

P1(8) is running [P1(8)]
P2(4) is running [P2(4), P1(7)]
P2(3) is running [P2(3), P1(7), P3(9)]
P2(2) is running [P2(2), P4(5), P1(7), P3(9)]
P2(1) is running [P2(1), P4(5), P1(7), P3(9)]
P4(5) is running [P4(5), P1(7), P3(9)]
P4(4) is running [P4(4), P1(7), P3(9)]
P4(3) is running [P4(3), P1(7), P3(9)]
P4(2) is running [P4(2), P1(7), P3(9)]
P4(1) is running [P4(1), P1(7), P3(9)]
P1(7) is running [P1(7), P3(9)]
P1(6) is running [P1(6), P3(9)]
P1(5) is running [P1(5), P3(9)]
P1(4) is running [P1(4), P3(9)]
P1(3) is running [P1(3), P3(9)]
P1(2) is running [P1(2), P3(9)]
P1(1) is running [P1(1), P3(9)]
P3(9) is running [P3(9)]
P3(8) is running [P3(8)]
P3(7) is running [P3(7)]
P3(6) is running [P3(6)]
P3(5) is running [P3(5)]
P3(4) is running [P3(4)]
P3(3) is running [P3(3)]
P3(2) is running [P3(2)]
P3(1) is running [P3(1)]

SRTF는 선점 스케줄링 알고리즘이기 때문에 while문 진행중에 만약 readyQueue에 더 짧은 잔여시간을 가진 프로세스가 입력되면 현재 프로세스를 중단하고 더 짧은 프로세스를 우선적으로 실행한다.

 

5. Reference

운영체제