CPU Scheduling (1) - FCFS (First Come, First Served)

0. 스케줄링 개요

FCFS 스케줄링 기법은 말 그대로 First Come, First Served, 즉 먼저 준비된 프로세스를 먼저 실행시켜주는 스케줄링 기법을 의미한다. 다른 이름으로 FIFO (First In, First Out) 스케줄링이라고도 불린다. FCFS 스케줄링은 아래와 같은 특징들을 가진다.

 

1. FCFS는 간단하고 공정하다.

우선순위, 실행시간 등의 다른 요소는 전혀 고려하지 않고 무조건 먼저 준비되면 먼저 실행시켜준다. 

 

2. 실행시간이 긴 프로세스가 먼저 실행되면 대기시간이 길어진다

예를 들어 세개의 프로세스가 있고 각각 실행시간이 24, 3, 3과 같다고 가정해보자. 만약 P1이 가장 먼저 실행되면 P2는 24msec을 기다려야하고 P3는 27msec을 기다려야한다. 때문에 평균 대기시간 (AWT, Average Waiting Time)은 $\frac{0 + 24 + 27}{3} = 17msec$이다. 즉, 앞선 프로세스의 시간이 길어지면 전체 시스템의 평균 대기시간이 길어진다는 단점이 있다.

 

만약 SJF(Shortest Job First)스케줄링 기법이였다면 P3, P2, P1 순으로 실행하여 평균 대기시간 (AWT)는 $\frac{0+3+6}{3} = 3msec$이였을 것이다. 이러한 결과는 항상 먼저 도착한 프로세스를 먼저 실행시키는 것이 마냥 좋은 것은 아니라는 것을 의미한다.

 

3. Convoy Effect (호위효과)가 발생한다.

호위효과란 앞선 프로세스가 실행시간이 길다면 실행시간이 짧은 프로세스들이 실행되지 못해 마치 부하처럼 뒤따라서 기다리고 있다는 것을 가리키는 효과이다. 만약 사람 3명이 화장실에 들어가려고 하는데 2명은 소변을, 1명은 대변을 누기를 희망한다고 가정해보자. 만약 대변을 누고싶은 사람이 가장 먼저 들어가면 2명의 사람은 매우 오랫동안 소변을 참아야한다. 우리는 이 것이 매우 비효율적이라는 것을 알 수 있다.

 

4. 비선점 (Non - Preemptive) 스케줄링 기법이다.

FCFS 스케줄링은 한 프로세스가 수행 중이라면 그 프로세스가 종료되기 전까지 CPU는 반드시 그 프로세스만 실행 할 수 있는 비선점 스케줄링 기법 중 하나이다.

 

5. 구현

1) Job 클래스

/**
 * @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) FCFS 스케줄러 클래스

package schedulers;

import jobs.Job;

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

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

    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) {
        FcfsScheduler scheduler = new FcfsScheduler();

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

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

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

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

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

위의 경우 실행시간이 긴 Job 1번 기다리기 위해 나머지 Job 2, 3, 4번이 대기해야한다. 이 것은 FCFS 스케줄링 기법의 단점으로 손꼽힌다. 실제로 코드를 실행하면 Job 1번을 위해 많은 Job들이 대기하고 있는 호위효과 (Convoy Effect)가 나타난다.

 

모든 소스코드는 Github에서 확인할 수 있습니다.

gusdnd852/TIL

 

6. Reference

운영체제