12.2 SJF 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

12.2 SJF 알고리즘

여러 개의 작업을 하나의 CPU에서 수행하는 순서를 결정하는 스케쥴링 알고리즘은 여러가지 방법이 있습니다. 그 중에서 작업을 수행 요청하고 실제 수행이 끝날 때까지 대기하는 평균 시간을 최소로 하는 알고리즘은 SJF(Shortest Job First)알고리즘입니다.

 

SJF 알고리즘은 작업량이 작은 작업을 먼저 수행하는 알고리즘입니다. 동시에 n개의 작업을 수행 요청이 왔다가 가정합시다.

 

n번째 수행할 작업의 길이를 An이라고 한다면 모든 작업을 수행하는데 걸리는 비용은 다음과 같습니다.

A1 + (A1 + A2) + (A1 + A2 + A3) + ... + (A1+A2+A3+...+An) = nA1 + (n-1)A2 + (n-2)A3 + ... +An

 

그리고 대기 시간의 합은 다음과 같습니다.

A2 + (A1 + A2) + ... + (A1+A2+A3+...+An-1) = (n-1)A1 + (n-2)A2 + (n-3)A3 + ... +An-1

 

첫 번째 작업은 작업 요청한 후에 대기 시간은 0, 수행을 완료할 때까지 걸린 시간이 A1입니다.

두 번째 작업이 작업 요청한 후에 대기 시간은 A1, 수행을 완료할 땨까지 걸린 시간은 A1 + A2입니다.

따라서 수행 완료까지 걸린 시간의 합은 Sa = A1 + (A1 + A2) + (A1+A2+A3)+...+(A1+A2+...+An)입니다.

Sa = A1 + (A1 + A2) + (A1+A2+A3)+...+(A1+A2+...+An) = nA1+(n-1)A2+(n-2)A3+...(n-i-1)Ai+...An

 

i>j>0이고 Ai<Aj 인 부분이 있을 때 수행 완료까지 걸린 시간의 평균 비용이 최소라고 가정합시다.

Sa에서 Ai와 Aj의 순서를 바꾼 것이 전체 시간의 합입니다.

Sb = nA1 + (n-1)A2 + ... + (n-(j-1))Ai + ... + (n-(i-1))Aj+...+An

 

Sa - Sb = (i-j)Aj + (j-i)Ai = (i-j)(Aj - Ai)<0 이므로 가정은 거짓입니다.

 

따라서 SJF 알고리즘이 작업 수행 완료까지 걸린 평균 시간을 최소로 할 수 있다는 것을 알 수 있습니다.

 

그리고 평균 대기 시간 = 작업 수행 완료까지 걸린 평균 시간 – 평균 작업 량 이므로 평균 대기시간도 최소라고 말할 수 있습니다.

 

이제 SJF 알고리즘을 코드로 표현해 보아요.

Program.cpp

 

먼저 작업을 Job 클래스로 구현하기로 해요.

class Job

{

작업 이름과 길이와 작업 요청 시간, 대기 시간, 작업 완료에 걸린 시간을 기억하는 멤버를 선언하세요. 여기서 모든 시간은 시뮬레이션을 시작한 시각과의 차이입니다.

    string name;

    int length;

    int start_time;

    int wait_time;

    int end_time;

public:

    Job(string name,int length)

    {

생성자에서는 작업 이름과 길이를 입력 인자로 받아 멤버 필드에 설정합니다.

        this->name = name;

        this->length = length;

그리고 작업 요청한 시간과 대기 시간, 작업 완료한 시간을 0으로 설정하세요.

        start_time = 0;

        wait_time = 0;

        end_time = 0;

    }

 

1Clock 동안 작업을 수행하는 Do 메서드를 구현합시다.

    bool Do()

    {

작업 길이는 1 줄어들겠죠.

        length--;

작업을 수행하고 남은 작업 길이를 출력합시다.

        cout<<name<<" ,"<<length<<" ";

 

스케쥴러가 이 작업을 완료할 것인지 판별할 수 있게 남은 작업이 있는지 반환하세요.

        if(length>0)

        {

            return true;

        }

        else

        {           

            return false;

        }

    }

 

수행 요청한 시간과 대기 시간, 완료에 걸린 시간을 설정하는 메서드를 구현하세요.

    void SetStartTime(int time)

    {

        start_time = time;

        cout<<"<<"<<name<<", "<<length<<" 수행 요청 >>";

    }

 

    void SetWaitTime(int time)

    {

        wait_time = time - start_time;

    }

 

    void SetEndTime(int time)

    {

        end_time = time;

        cout<<" "<<name<<"작업 완료 ";

    }

 

대기 시간과 작업 완료에 걸린 시간, 남은 작업 길이를 구하는 메서드를 제공하세요.

    int GetWaitingTime()const

    {

        return wait_time;

    }

 

    int GetCompleteTime()const

    {

        return end_time - start_time;

    }

 

    int GetLength()const

    {

        return length;

    }

 

시뮬레이션 결과를 출력하는 메서드도 제공하세요.

    void View()const

    {

        cout<<name<<" 대기시간:"<<wait_time<<" 완료시간:"<<GetCompleteTime()<<endl;

    }

};

 

SJF 알고리즘은 작업 길이가 작은 순서로 대기합니다. 우선 순위 큐를 이용하여 이를 표현할 거예요. 먼저 우선 순위를 비교하는 함수 개체를 정의하세요.

struct JGreater

{

    bool operator()(const Job *j1, const Job *j2) const

    {

두 개의 작업 길이를 비교하여 앞쪽 작업의 길이가 큰 지 판별합니다.

        return j1->GetLength() > j2->GetLength();

    }

};

 

 

SJF 알고리즘을 구현합시다.

class SJFAlgorithm

{

멤버로 우선 순위 큐와 현재 수행 중인 작업 및 시뮬레이션 소요 시간 기억하는 멤버를 선언하세요.

    priority_queue<Job *, vector<Job *>,JGreater>  pq;

    Job *doingjob;

    int time;

public:

    SJFAlgorithm()

    {

생성자에서는 수행 작업 중인 작업을 0으로 시간을 0으로 설정하고 시간을 출력하세요.

        doingjob=0;

        time = 0;

        cout<<time<<" ";

    }

 

특정 작업을 수행 요청하는 메서드를 구현하세요.

    void AddJob(Job *job)

    {

우선 순위 큐에 작업을 추가하고 작업 수행 요청 시간을 설정하세요.

        pq.push(job);

        job->SetStartTime(time);       

    }

 

1 Clock이 지났을 때 수행할 메서드를 구현하세요.

    void Clock()

    {

시간을 증가하고 출력하세요.

        time++;

        cout<<endl<<time<<" ";

현재 수행 중인 작업이 없는지 확인합니다.

        if(doingjob==0)

        {

만약 우선 순위 큐가 비어있다면 아무 작업도 하지 않습니다.

            if(pq.empty())

            {

                return;

            }

우선 순위 큐에서 작업을 꺼내오고 대기 시간을 설정하세요.

            doingjob = pq.top();

            pq.pop();

            doingjob->SetWaitTime(time);

        }

 

수행 중인 작업을 진행합니다.

        bool remain = doingjob->Do();

 

남은 작업 길이가 없으면 종료 시간을 설정하고 현재 수행 중인 작업을 0으로 리셋합니다.

        if(remain == false)

        {

            doingjob->SetEndTime(time);

            doingjob = 0;

        }

    }

 

시뮬레이션이 끝났는지 판별하는 메서드를 구현하세요.

    bool IsEnd()const

    {

우선 순위 큐가 비어있고 현재 진행하는 작업이 없으면 시뮬레이션은 끝난 것입니다.

        return pq.empty() && (doingjob==0);

    }

};

 

이제 테스트 코드를 작성합시다.

int main()

{

테스트에 사용할 작업을 생성하세요.

    Job *test_jobs[6];

 

여기에서는 A~F까지 6개의 작업을 테스트에 사용할게요.

    test_jobs[0] = new Job("A",5);

    test_jobs[1] = new Job("B",6);

    test_jobs[2] = new Job("C",9);

    test_jobs[3] = new Job("D",8);

    test_jobs[4] = new Job("E",7);

    test_jobs[5] = new Job("F",6);

 

SJF 알고리즘을 생성합니다.

    SJFAlgorithm *sjf = new SJFAlgorithm();

 

적당하게 작업을 추가하고 Clock을 발생하세요.

    sjf->AddJob(test_jobs[0]);

    sjf->Clock();

    sjf->AddJob(test_jobs[1]);

    sjf->Clock();

    sjf->Clock();

    sjf->AddJob(test_jobs[2]);

    sjf->Clock();

    sjf->AddJob(test_jobs[3]);

    sjf->AddJob(test_jobs[4]);

    sjf->Clock();

    sjf->AddJob(test_jobs[5]);

 

시뮬레이션이 끝날 때까지 Clock을 발생합니다.

    while(sjf->IsEnd() == false)

    {

        sjf->Clock();

    }

    delete sjf;

 

시뮬레이션이 끝나면 모든 작업을 출력하고 소멸하세요.

    cout<<"시뮬레이션 종료"<<endl;

    for(int i = 0; i<6; i++)

    {

        test_jobs[i]->View();

        delete test_jobs[i];

    }

    return 0;

}

 

▷ 실행 결과

0 <<A, 5 수행 요청 >>

1 A ,4 <<B, 6 수행 요청 >>

2 A ,3

3 A ,2 <<C, 9 수행 요청 >>

4 A ,1 <<D, 8 수행 요청 >><<E, 7 수행 요청 >>

5 A ,0  A작업 완료 <<F, 6 수행 요청 >>

6 B ,5

7 B ,4

8 B ,3

9 B ,2

10 B ,1

11 B ,0  B작업 완료

12 F ,5

13 F ,4

14 F ,3

15 F ,2

16 F ,1

17 F ,0  F작업 완료

18 E ,6

19 E ,5

20 E ,4

21 E ,3

22 E ,2

23 E ,1

24 E ,0  E작업 완료

25 D ,7

26 D ,6

27 D ,5

28 D ,4

29 D ,3

30 D ,2

31 D ,1

32 D ,0  D작업 완료

33 C ,8

34 C ,7

35 C ,6

36 C ,5

37 C ,4

38 C ,3

39 C ,2

40 C ,1

41 C ,0  C작업 완료 시뮬레이션 종료

A 대기시간:1 완료시간:5

B 대기시간:5 완료시간:10

C 대기시간:30 완료시간:38

D 대기시간:21 완료시간:28

E 대기시간:14 완료시간:20

F 대기시간:7 완료시간:12