C++/디딤돌 자료구조와 알고리즘 with C++

SJF(Shortest Job First) 스케쥴링 알고리즘, 탐욕(Greedy) 알고리즘 [C++ 소스]

언제나휴일 2016. 6. 12. 23:40
반응형

SJF(Shortest Job First) 스케쥴링 알고리즘

탐욕(Greedy) 알고리즘 [C++ 소스]


Program.cpp




"본문 내용"은 언제나 휴일 본 사이트에 있습니다.



//SJF(Shortest Job First) 스케쥴링

#include <string>

#include <vector>

#include <queue>

#include <iostream>

using namespace std;

 

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;

        start_time = 0;

        end_time = 0;

        wait_time = 0;

    }   

    bool Do()

    {

        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;

    }

};

 

struct JGreater

{

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

    {

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

    }

};

 

 

class SJFAlgorithm

{

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

    Job *doingjob;

    int time;

public:

    SJFAlgorithm()

    {

        doingjob=0;

        time = 0;

        cout<<time<<" ";

    }

    void AddJob(Job *job)

    {

        pq.push(job);

        job->SetStartTime(time);       

    }

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

        if(remain == false)

        {

            doingjob->SetEndTime(time);

            doingjob = 0;

        }       

       

    }

    bool IsEnd()const

    {

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

    }

};

int main()

{

    Job *test_jobs[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);

    SJFAlgorithm *sjf = new SJFAlgorithm();

    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]);

   

    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



프로그래밍 언어 및 기술 학습, 무료 동영상 강의 언제나 휴일

반응형