CPU 스케줄링 (4) - 라운드 로빈 스케줄링

0. 스케줄링 개요

Time Sharing System에서는 주기적으로 Context Switching을 진행한다. Running 상태의 프로세스가 I/O 작업을 수행하지 않더라도 일정시간이 되면 Ready 상태로 만드는데, 이 때 사용하는 스케줄링 방법이 라운드로빈 스케줄링이다. 라운드로빈이라는 이름처럼 뱅뱅 돌면서 프로세싱을 수행하게 된다.

 

1. Time Slice (Time Quantum)

라운드로빈 스케줄링에서는 일정시간만다 프로세스가 강제로 교체되는데, 이 때 사용되는 일정시간이 바로 Time Slice (타임 슬라이스, Δ 델타로 표시)이다. 다른말로 Time Quantum (타임 퀀텀)이라고도 한다. 라운드로빈의 ATT(Average Turnaround Time)은 Time Slice에 매우 큰 영향을 받게 되는데, 그럼 양 극한인 무한대와 0으로 Time Slice를 보내면 어떻게 될까?

 

 

Time Slice → 무한대 :

FCFS 스케줄링과 동일해진다. 해당 프로세스가 끝나야만 전환된다

 

Time Slice → 0 :

Processor Sharing 상태이다. 사실상 3개의 프로세스가 동시에 수행된다.

그러나 Context Switching의 Overhead가 너무 커지게 된다 (디스패쳐 등)

 

2. 라운드로빈 스케줄링은 반드시 선점 스케줄링이다.

해당 프로세스가 Time Slice만큼 작업을 수행하면 프로세스가 진행중이여도 강제로 다른 프로세스에게 작업을 넘겨줘야한다. 때문에 라운드로빈은 가장 대표적인 선점 스케줄링 기법이다.

 

3. ATT (Average Turnaround Time) 계산

※ Δ = 1인 경우

PID	실행 시간	반환 시간
P1	6초	15초
P2	3초	9초
P3	1초	3초
P4	7초	17초
총 계		(15+9+3+17) / 4 = 11초

1 : P1(6) is running [P1(6), P2(3), P3(1), P4(7)]
2 : P2(3) is running [P1(5), P2(3), P3(1), P4(7)]
3 : P3(1) is running [P1(5), P2(2), P3(1), P4(7)] ← P3 Turnaround(3)
4 : P4(7) is running [P1(5), P2(2), P4(7)]
5 : P1(5) is running [P1(5), P2(2), P4(6)]
6 : P2(2) is running [P1(4), P2(2), P4(6)]
7 : P4(6) is running [P1(4), P2(1), P4(6)]
8 : P1(4) is running [P1(4), P2(1), P4(5)]
9 : P2(1) is running [P1(3), P2(1), P4(5)] ← P2 Turnaround(9)
10 : P4(5) is running [P1(3), P4(5)]
11 : P1(3) is running [P1(3), P4(4)]
12 : P4(4) is running [P1(2), P4(4)]
13 : P1(2) is running [P1(2), P4(3)]
14 : P4(3) is running [P1(1), P4(3)]
15 : P1(1) is running [P1(1), P4(2)] ← P1 Turnaround(15)
16 : P4(2) is running [P4(2)]
17 : P4(1) is running [P4(1)] ← P4 Turnaround(17)

 

※ Δ = 5인 경우

PID	실행 시간	반환 시간
P1	6초	15초
P2	3초	9초
P3	1초	8초
P4	7초	17초
총 계		(15+9+8+17) / 4 = 12.25초

1 : P1(6) is running [P1(6), P2(3), P3(1), P4(7)]
2 : P1(5) is running [P1(5), P2(3), P3(1), P4(7)]
3 : P1(4) is running [P1(4), P2(3), P3(1), P4(7)]
4 : P1(3) is running [P1(3), P2(3), P3(1), P4(7)]
5 : P1(2) is running [P1(2), P2(3), P3(1), P4(7)]
6 : P2(3) is running [P1(1), P2(3), P3(1), P4(7)]
7 : P2(2) is running [P1(1), P2(2), P3(1), P4(7)]
8 : P2(1) is running [P1(1), P2(1), P3(1), P4(7)] ← P2 Turnaround(8)
9 : P3(1) is running [P1(1), P3(1), P4(7)] ← P3 Turnaround(9)
10 : P4(7) is running [P1(1), P4(7)]
11 : P4(6) is running [P1(1), P4(6)]
12 : P4(5) is running [P1(1), P4(5)]
13 : P4(4) is running [P1(1), P4(4)]
14 : P4(3) is running [P1(1), P4(3)]
15 : P1(1) is running [P1(1), P4(2)] ← P1 Turnaround(15)
16 : P4(2) is running [P4(2)]
17 : P4(1) is running [P4(1)] ← P4 Turnaround(17)

 

4. 소스코드

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) Round Robin 스케줄러 클래스 : 

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 RoundRobinScheduler {
    private List<Job> readyQueue = new CopyOnWriteArrayList<>();
    private ExecutorService runningThread = Executors.newSingleThreadExecutor();
    private int timeSlice;

    public RoundRobinScheduler(int timeSlice) {
        this.timeSlice = timeSlice;
    }

    void insert(Job job) {
        readyQueue.add(job);
    }

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

    void start() {
        runningThread.execute(() -> {
            while (readyQueue.size() != 0) {
                for (Job job : readyQueue) {
                    int countTimeSlice = timeSlice;

                    while (job.remain > 0) {
                        if (countTimeSlice == 0)
                            break;

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

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

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


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

        scheduler.insert(new Job(1, 10));
        scheduler.insert(new Job(2, 5));
        scheduler.insert(new Job(3, 8));
        scheduler.insert(new Job(4, 11));

        scheduler.start(); // time : 0 sec.
    }

    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();
        }
    }
}

 

※ Time Slice = 1인 경우

출력 : 

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

 

※ Time Slice = 2인 경우

출력 : 

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

 

5. Reference

운영체제