CPU 스케줄링 (3) - 우선순위 스케줄링

0. 스케줄링 개요

Priority(우선순위) 스케줄링은 말 그대로 우선순위 순서대로 스케줄링을 진행하는 것이다. 우선순위는 정수값으로 주어지며 일반적으로 낮은 숫자가 높은 우선순위를 의미한다. 

 

1. 우선순위 선정

우선순위는 프로세스 내부적인 요인과 외부적인 요인에 의해 결정된다.

• 내부 요인 : 수행시간(SJF처럼), 메모리/IO/CPU 소비량(적은것 먼저)
• 외부 요인 : 유료 서버 컴퓨터의 경우 높은 등급의 사용자의 프로세스를 높혀주는 등

 

2. SJF처럼 선점, 비선점 모두 가능하다.

중간에 더 우선순위가 높은 프로세스가 입력되면 프로세스를 밀어내고 높은 우선순위의 프로세스가 먼저 실행된다면 선점, 그렇지 하지 않고 우선순위가 높은 프로세스가 입력되어도 프로세스를 밀어내지 않으면 비선점 스케줄링이다.

 

3. 우선순위 스케줄링의 문제점

• Starvation (기아) 상태 : 우선순위가 낮은 프로세스가 ReadyQueue에서 대기하고 있는데 뒤에서 계속 우선순위가 높은 프로세스가 지속적으로 큐에 삽입되면 우선순위가 낮은 프로세스는 영원히 기다려야 할 수도 있다. 이런 상태를 기아상태라고 한다. 
• Aging (에이징) : Starvation 상태의 해결법이다. 쉽게 말해서 프로세스가 나이를 먹는 것이다. 오래된 프로세스일 수록 우선순위가 낮더라도 오래 기다렸으면 우선순위를 조금씩 올려주는 방법으로 우선순위 프로세스를 적용하는 경우 많이 사용된다. 

 

4. 소스코드

1) PriorityJob 클래스

package jobs;

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

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

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

 

2) Priority 스케줄러 클래스

package schedulers;

import jobs.PriorityJob;

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 PriorityScheduler {
    private List<PriorityJob> readyQueue = new CopyOnWriteArrayList<>();
    private ExecutorService runningThread = Executors.newSingleThreadExecutor();

    void insert(PriorityJob job) {
        readyQueue.add(job);
        readyQueue.sort(Comparator.comparingInt(j -> j.priority));
        // 우선순위를 기준으로 정렬
    }

    void interval(int n, int m) {
        for (int i = n; i < m + n; i++) {
            sleep(990);
            // 오버헤드 고려해서 10msec 빠르게

            insert(new PriorityJob(i, 1, 5));
            if (i + 1 == m + n)
                System.exit(0);
        }
    }

    void start() {
        runningThread.execute(() -> {
            while (readyQueue.size() != 0) {
                for (PriorityJob job : readyQueue) {
                    while (job.remain > 0) {
                        if (!job.equals(readyQueue.get(0)))
                            break;

                        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) {
        PriorityScheduler scheduler = new PriorityScheduler();
        scheduler.insert(new PriorityJob(1, 1, 30));
        scheduler.insert(new PriorityJob(2, 1, 5));
        scheduler.insert(new PriorityJob(3, 1, 5));

        scheduler.start();
        scheduler.interval(4, 55);
    }

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

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

출력 :

P2(5) is running [P2(5), P3(5), P1(30)]
P3(5) is running [P3(5), P4(5), P1(30)]
P4(5) is running [P4(5), P5(5), P1(30)]
P5(5) is running [P5(5), P6(5), P1(30)]
P6(5) is running [P6(5), P7(5), P1(30)]
P7(5) is running [P7(5), P8(5), P1(30)]
P8(5) is running [P8(5), P9(5), P1(30)]
P9(5) is running [P9(5), P10(5), P1(30)]
P10(5) is running [P10(5), P11(5), P1(30)]
P11(5) is running [P11(5), P12(5), P1(30)]
P12(5) is running [P12(5), P13(5), P1(30)]
P13(5) is running [P13(5), P14(5), P1(30)]
P14(5) is running [P14(5), P15(5), P1(30)]
P15(5) is running [P15(5), P16(5), P1(30)]
P16(5) is running [P16(5), P17(5), P1(30)]
P17(5) is running [P17(5), P18(5), P1(30)]
P18(5) is running [P18(5), P19(5), P1(30)]
P19(5) is running [P19(5), P20(5), P1(30)]
P20(5) is running [P20(5), P21(5), P1(30)]
P21(5) is running [P21(5), P22(5), P1(30)]
P22(5) is running [P22(5), P23(5), P1(30)]
P23(5) is running [P23(5), P24(5), P1(30)]
P24(5) is running [P24(5), P25(5), P1(30)]
P25(5) is running [P25(5), P26(5), P1(30)]
P26(5) is running [P26(5), P27(5), P1(30)]
P27(5) is running [P27(5), P28(5), P1(30)]
P28(5) is running [P28(5), P29(5), P1(30)]
P29(5) is running [P29(5), P30(5), P1(30)]
P30(5) is running [P30(5), P31(5), P1(30)]
P31(5) is running [P31(5), P32(5), P1(30)]
P32(5) is running [P32(5), P33(5), P1(30)]
P33(5) is running [P33(5), P34(5), P1(30)]
P34(5) is running [P34(5), P35(5), P1(30)]
P35(5) is running [P35(5), P36(5), P1(30)]
P36(5) is running [P36(5), P37(5), P1(30)]
P37(5) is running [P37(5), P38(5), P1(30)]
P38(5) is running [P38(5), P39(5), P1(30)]
P39(5) is running [P39(5), P40(5), P1(30)]
P40(5) is running [P40(5), P41(5), P1(30)]
P41(5) is running [P41(5), P42(5), P1(30)]
P42(5) is running [P42(5), P43(5), P1(30)]
P43(5) is running [P43(5), P44(5), P1(30)]
P44(5) is running [P44(5), P45(5), P1(30)]
P45(5) is running [P45(5), P46(5), P1(30)]
P46(5) is running [P46(5), P47(5), P1(30)]
P47(5) is running [P47(5), P48(5), P1(30)]
P48(5) is running [P48(5), P49(5), P1(30)]
P49(5) is running [P49(5), P50(5), P1(30)]
P50(5) is running [P50(5), P51(5), P1(30)]
P51(5) is running [P51(5), P52(5), P1(30)]
P52(5) is running [P52(5), P53(5), P1(30)]
P53(5) is running [P53(5), P54(5), P1(30)]
P54(5) is running [P54(5), P55(5), P1(30)]
P55(5) is running [P55(5), P56(5), P1(30)]
P56(5) is running [P56(5), P57(5), P1(30)]

// Starvation 발생. P1이 영원히 끝나지 않음

 

3) Aging 스케줄러 클래스

package schedulers;

import jobs.PriorityJob;

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 AgingScheduler {
    private List<PriorityJob> readyQueue = new CopyOnWriteArrayList<>();
    private ExecutorService runningThread = Executors.newSingleThreadExecutor();

    void insert(PriorityJob job) {
        readyQueue.add(job);
        readyQueue.sort(Comparator.comparingInt(j -> j.priority));
        // 우선순위를 기준으로 정렬        
    }

    void interval(int n, int m) {
        for (int i = n; i < m + n; i++) {
            sleep(990); 
            // 오버헤드 고려해서 10msec 빠르게
            
            insert(new PriorityJob(i, 1, 5));
            if (i + 1 == m + n)
                System.exit(0);
        }
    }
    
    void start() {
        runningThread.execute(() -> {
            while (readyQueue.size() != 0) {
                for (PriorityJob job : readyQueue) {
                    int average = 0;
                    for (PriorityJob j : readyQueue) average += j.PID;
                    average /= readyQueue.size();

                    if (job.PID < average) {
                        job.priority--;
                        // Aging 수행
                        // PID가 평균보다 낮으면 (오래 되었으면)
                        // 우선순위를 깎아서 개선해줌.
                    }

                    while (job.remain > 0) {
                        if (!job.equals(readyQueue.get(0)))
                            break;

                        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) {
        AgingScheduler scheduler = new AgingScheduler();
        scheduler.insert(new PriorityJob(1, 1, 30));
        scheduler.insert(new PriorityJob(2, 1, 5));
        scheduler.insert(new PriorityJob(3, 1, 5));
        
        scheduler.start();
        scheduler.interval(4, 55);
    }

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

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

출력 : 

P2(5) is running [P2(5), P3(5), P1(30)]
P3(5) is running [P3(5), P4(5), P1(30)]
P4(5) is running [P4(5), P5(5), P1(29)]
P5(5) is running [P5(5), P6(5), P1(29)]
P6(5) is running [P6(5), P7(5), P1(28)]
P7(5) is running [P7(5), P8(5), P1(28)]
P8(5) is running [P8(5), P9(5), P1(27)]
P9(5) is running [P9(5), P10(5), P1(27)]
P10(5) is running [P10(5), P11(5), P1(26)]
P11(5) is running [P11(5), P12(5), P1(26)]
P12(5) is running [P12(5), P13(5), P1(25)]
P13(5) is running [P13(5), P14(5), P1(25)]
P14(5) is running [P14(5), P15(5), P1(24)]
P15(5) is running [P15(5), P16(5), P1(24)]
P16(5) is running [P16(5), P17(5), P1(23)]
P17(5) is running [P17(5), P18(5), P1(23)]
P18(5) is running [P18(5), P19(5), P1(22)]
P19(5) is running [P19(5), P20(5), P1(22)]
P20(5) is running [P20(5), P21(5), P1(21)]
P21(5) is running [P21(5), P22(5), P1(21)]
P22(5) is running [P22(5), P23(5), P1(20)]
P23(5) is running [P23(5), P24(5), P1(20)]
P24(5) is running [P24(5), P25(5), P1(19)]
P25(5) is running [P25(5), P26(5), P1(19)]
P26(5) is running [P26(5), P27(5), P1(18)]
P27(5) is running [P27(5), P28(5), P1(18)]
P28(5) is running [P28(5), P29(5), P1(17)]
P29(5) is running [P29(5), P30(5), P1(17)]
P30(5) is running [P30(5), P31(5), P1(16)]
P31(5) is running [P31(5), P32(5), P1(16)]
P32(5) is running [P32(5), P33(5), P1(15)]
P33(5) is running [P33(5), P34(5), P1(15)]
P34(5) is running [P34(5), P35(5), P1(14)]
P35(5) is running [P35(5), P36(5), P1(14)]
P36(5) is running [P36(5), P37(5), P1(13)]
P37(5) is running [P37(5), P38(5), P1(13)]
P38(5) is running [P38(5), P39(5), P1(12)]
P39(5) is running [P39(5), P40(5), P1(12)]
P40(5) is running [P40(5), P41(5), P1(11)]
P41(5) is running [P41(5), P42(5), P1(11)]
P42(5) is running [P42(5), P43(5), P1(10)]
P43(5) is running [P43(5), P44(5), P1(10)]
P44(5) is running [P44(5), P45(5), P1(9)]
P45(5) is running [P45(5), P46(5), P1(9)]
P46(5) is running [P46(5), P47(5), P1(8)]
P47(5) is running [P47(5), P48(5), P1(8)]
P48(5) is running [P48(5), P49(5), P1(7)]
P49(5) is running [P49(5), P50(5), P1(7)]
P50(5) is running [P50(5), P51(5), P1(6)]
P51(5) is running [P51(5), P52(5), P1(6)]
P52(5) is running [P52(5), P53(5), P1(5)]
P53(5) is running [P53(5), P1(5), P54(5)]
P1(4) is running [P1(4), P54(5), P55(5)]
P54(4) is running [P54(4), P55(5), P56(5)]
P55(4) is running [P55(4), P56(5), P57(5)]

// Starvation 해결. P54가 수행되어야 할 시간에 P1이 실행되어 끝났음.

 

6. Reference

운영체제