3.5 큐를 이용한 스케쥴러 시뮬레이션 [디딤돌 자료구조와 알고리즘 with C++]

3.5 큐를 이용한 스케쥴러 시뮬레이션

이번에는 큐를 이용하는 스케쥴러를 시뮬레이션 형태로 만들어 보아요.

 

여기서 작성할 시뮬레이션은 CPU가 하나 있는 컴퓨터 시스템에서 라운드 로빈 방식의 스케쥴러의 동작을 표현합시다. 스케쥴러는 컴퓨터 내에 여러 개의 프로세스(동작 중인 프로그램)중에서 누가 CPU를 사용할 것인지를 결정하는 운영체제의 핵심 모듈이죠. (참고로 Windows 운영 체제는 스케쥴링 대상이 쓰레드입니다.) 그 중에 라운드 로빈 방식의 스케쥴러는 시스템 내에 정해진 시간(타임 퀀텀)동안 CPU를 사용한 후 다시 대기 큐에 가서 대기하고 맨 앞에 대기하는 프로세스가 CPU를 점유하여 사용하게 운용해요.

 

여기에서는 프로세스의 상태를 Idel(휴먼 상태), Ready(준비 상태), Run(동작 상태)로만 나누기로 할게요. 처음 프로그램을 실행시키면 Idle 상태에서 Ready 상태로 변해요. 그리고 스케쥴러는 해당 프로세스를 대기 큐에 보관하죠. 그리고 큐에서 대기하는 프로세스를 꺼내와서 Ready에서 Run 상태로 전이합니다. Run 상태에서 작업이 끝나면 프로세스는 끝납니다. 만약 Run 상태에서 수행 중에 정해진 시간(타임 퀀텀)이 지나면 다시 Ready 상태로 전이하고 대기 큐에 보관해요. 시뮬레이션에서는 프로세스마다 수행해야 할 전체 작업량과 CPU를 점유했을 때 사용할 수 있는 시간이 정해져 있다는 가정하에서 만들어 보아요.

 

 

 

시뮬레이션은 하드 디스크에 설치한 프로그램을 차례대로 작동해 Idle 상태에서 Ready 상태로 전이하는 것을 초기화 단계에서 수행하게 합시다. 그리고 시뮬레이션은 대기 큐에 남아있는 프로세스가 없을 때까지 진행할 거예요.

 

시뮬레이션에서는 대기 큐에 프로세스를 꺼내와서 Ready 상태에서 Run 상태로 전이시킵니다. 프로세스가 정해진 시간을 수행한 후에 남은 작업량을 반환하게 합시다. 만약 반환 값이 0보다 크면 다시 대기 큐에 보관합니다. 그렇지 않다면 Run 상태에서 Idle 상태로 전이시키고 대기 큐에는 보관하지 않습니다.

 

먼저 프로세스를 정의합시다. 프로세스는 프로그램 이름과 전체 작업량, cpu 점유 시에 수행 가능 작업량, 현재 남은 작업량, 현재 cpu 점유 시에 수행 가능 작업량을 멤버 필드로 캡슐화하세요.

class EHProcess 

{

    string pname; //프로그램 이름

    const int tjob; //전체 작업량

    const int cjob; //cpu 점유 시 수행 가능 작업량

    int ntjob; //현재 남은 작업량

    int ncjob; //현재 cpu 점유 시 수행 가능 작업량

public:

생성자 메서드는 프로그램 이름, 전체 작업량, cpu 점유 시 수행 가능 작업량을 입력 인자로 받게 하세요.

    EHProcess(string pname,int tjob,int cjob);

Idle 상태에서 Ready 상태로 전이하는 메서드도 추가하세요.

    void IdleToReady();//Idle 상태에서 Ready 상태로 전이

대기 큐에서 꺼내온 프로세스가 CPU를 점유하여 동작하는 메서드도 추가하세요.

    int Running();//CPU를 점유하여 실행, 남은 작업량 반환

모든 작업 수행한 후에 프로세스를 종료하는 메서드도 추가하세요.

    void EndProgram(); //프로세스 종료

};

 

생성자 메서드에서는 프로그램 이름과 전체 작업량, cpu 점유 시 수행 가능 작업량을 초기화하세요.

EHProcess::EHProcess(string pname,int tjob,int cjob):tjob(tjob),cjob(cjob)

{

    this->pname = pname;

}

 

IdleToReady 메서드는 프로그램을 메모리에 로딩하여 프로세스를 시작하는 과정을 표현할 것입니다. 현재 남은 작업량을 상수화 멤버 필드 값인 전체 작업량을 대입하세요.

void EHProcess::IdleToReady()//Idle 상태에서 Ready 상태로 전이

{

    cout<<pname<<" 시작"<<endl;

    ntjob = tjob; //프로그램 이미지 메모리에 로딩을 표현

}

 

int EHProcess::Running()//CPU를 점유하여 실행, 남은 작업량 반환

{

먼저 CPU를 점유하여 사용 가능량을 설정하세요.

    ncjob = cjob; //ncjob에 CPU 사용할 수 있는 시간 대입

남은 작업량과 CPU 사용 가능량이 모두 참이면 작업을 수행합니다. 수행하는 모습은 프로세스 이름을 출력하기로 할게요.

    //남은 작업량(ntjob)과 CPU 사용할 수 있는 시간(ncjob)이 있다면

    for(  ; ntjob && ncjob ; ntjob--, ncjob--)

    {

        cout<<pname<<" ";//단위 시간 작업 수행을 표현

    }

CPU 점유를 끝난 것을 구분하기 위해 개행을 출력하세요.

    cout<<endl; //CPU를 반납함을 표현

남은 작업량을 반환해야겠죠.

    return ntjob; //남은 작업량 반환

}

void EHProcess::EndProgram() //프로세스 종료

{

EndProgram 메서드에서는 프로세스 종료함을 출력하세요.

    cout<<pname<<"종료"<<endl; //프로세스 종료를 표현

}

 

이제 스케쥴러를 만듭시다. 스케쥴러에는 멤버 필드로 프로그램이 저장된 하드디스크와 대기 상태의 프로세스를 보관하는 큐가 필요합니다. 프로그램을 저장할 자료구조는 vector를 사용합시다.

 

타입 재지정으로 프로세스를 보관하는 vector를 메모리라 정하고 대기 큐 및 반복자를 정의하세요.

typedef vector<EHProcess *> Memory;

typedef queue<EHProcess *> ReadyQueue;

typedef Memory::iterator miter;

 

class Scheduler 

{

스케쥴러에는 하드디스크와 대기 큐를 멤버 필드로 선언하세요.

    Memory hard_disk; // 하드디스크

    ReadyQueue  rq; //대기 큐

public:

    Scheduler();

    virtual ~Scheduler();

private:

시뮬레이션을 초기화하는 메서드를 추가하세요.

    void Init(); //시뮬레이션 초기화- 프로그램 설치 및 실행 명령

시뮬레이션을 시작하는 메서드를 추가하세요.

    void Simulation();//시뮬레이션 시작

시뮬레이션을 종료하는 메서드를 제공하세요.

    void Ending();//시뮬레이션 종료

};

 

스케쥴러의 생성자 메서드에서는 초기화와 시뮬레이션 가동하세요.

Scheduler::Scheduler()

{

    Init();

    Simulation();

}

소멸자에서는 시뮬레이션을 종료하는 메서드를 호출하세요.

Scheduler::~Scheduler()

{

    Ending();

}

 

void Scheduler::Init()

{

시뮬레이션 초기화에서는 프로세스를 생성하여 하드디스크에 설치하는 것을 표현하세요.

    hard_disk.push_back(new EHProcess("A",30,5));

    hard_disk.push_back(new EHProcess("B",24,6));

    hard_disk.push_back(new EHProcess("C",25,4));

그리고 시뮬레이션에 사용할 프로세스를 메모리에서 순차적으로 접근하여 대기 큐에 추가하세요.

    miter seek = hard_disk.begin();

    miter end = hard_disk.end();

    EHProcess *pro=0;

    for( ; seek != end ; ++seek)

    {

        pro = *seek;

        rq.push(pro); //대기 큐에서 기다림

메모리에서 대기 큐에 추가한 프로세스는 Idle 상태에서 Ready 상태로 전이하세요.

        pro->IdleToReady();//Idle 상태에서 Ready상태로 전이

    }

}

void Scheduler::Ending()

{

시뮬레이션이 끝나면 하드디스크에 보관한 프로세스를 순차적으로 소멸하세요.

    miter seek = hard_disk.begin();

    for(   ; seek != hard_disk.end(); ++seek)

    {

        delete (*seek);

    }

}

void Scheduler::Simulation()

{

    EHProcess *process = 0;

    int job=0;

시뮬레이션은 대기 큐가 비어있지 않으면 반복합니다.

    while( !rq.empty() ) //대기 큐가 비어있지 않을 때

    {

가장 먼저 대기한 프로세스를 꺼내오세요.

        process = rq.front();

        rq.pop();

꺼내 온 프로세스는 CPU를 점유하여 실행합니다.

        job = process->Running();//꺼내 온 프로세스를 실행

        if(job) //남은 작업이 있다면

        {

수행 후에 남은 작업이 있으면 대기 큐에 다시 보관합니다.

            rq.push(process); //대기큐에서 기다림

        }

        else

        {

그렇지 않으면 프로세스를 종료하세요.

            process->EndProgram();//프로세스 종료

        }

    }

}

 

진입점에서는 스케쥴러를 생성한 후에 소멸하세요.

int main()

{

    Scheduler *pro = new Scheduler;

    delete pro;

    return 0;

}

 

▷ 실행 결과

A 시작

B 시작

C 시작

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

B종료

C C C C

A A A A A

C C C C

A A A A A

A종료

C C C C

C

C종료

 

 

다음은 앞에서 작성한 스케쥴러 시뮬레이션 코드입니다.

//EHProcess.h

#pragma once

#include <iostream>

#include <string>

using namespace std;

 

class EHProcess

{

    string pname; //프로그램 이름

    const int tjob; //전체 작업량

    const int cjob; //cpu 점유 시 수행가능 최대 작업량

    int ntjob; //현재 남은 작업량

    int ncjob; //현재 cpu 점유 시 수행가능 최대 작업량

public:

    EHProcess(string pname,int tjob,int cjob);

    void IdleToReady();//Idle 상태에서 Ready 상태로 전이

    int Running();//CPU를 점유하여 실행, 남은 작업량 반환

    void EndProgram(); //프로세스 종료

};

 

//EHProcess.h

#include "EHProcess.h"

 

EHProcess::EHProcess(string pname,int tjob,int cjob):tjob(tjob),cjob(cjob)

{

    this->pname = pname;

}

void EHProcess::IdleToReady()//Idle 상태에서 Ready 상태로 전이

{

    cout<<pname<<" 시작"<<endl;

    ntjob = tjob; //프로그램 이미지 메모리에 로딩을 표현

}

int EHProcess::Running()//CPU를 점유하여 실행, 남은 작업량 반환

{

    ncjob = cjob; //ncjob에 CPU 사용할 수 있는 시간 대입

 

    //남은 작업량(ntjob)과 CPU 사용할 수 있는 시간(ncjob)이 있다면

    for(  ; ntjob && ncjob ; ntjob--, ncjob--)

    {

        cout<<pname<<" ";//단위 시간 작업 수행을 표현

    }

 

    cout<<endl; //CPU를 반납함을 표현

    return ntjob; //남은 작업량 반환

}

void EHProcess::EndProgram() //프로세스 종료

{

    cout<<pname<<"종료"<<endl; //프로세스 종료를 표현

}

 

//Scheduler.h

#pragma once

#include <vector>

#include <queue>

using namespace std;

#include "EHProcess.h"

 

typedef vector<EHProcess *> Memory;

typedef queue<EHProcess *> ReadyQueue;

typedef Memory::iterator miter;

 

class Scheduler 

{

    Memory hard_disk; // 하드디스크

    ReadyQueue  rq; //대기 큐

public:

    Scheduler();

    virtual ~Scheduler();

private:

    void Init(); //시뮬레이션 초기화- 프로그램 설치 및 실행 명령

    void Simulation();//시뮬레이션 시작

    void Ending();//시뮬레이션 종료

};

 

//Scheduler.h

#include "Scheduler.h"

 

Scheduler::Scheduler()

{

    Init();

    Simulation();

}

void Scheduler::Init()

{

    //하드디스크에 프로그램 설치를 표현

    hard_disk.push_back(new EHProcess("A",30,5));

    hard_disk.push_back(new EHProcess("B",24,6));

    hard_disk.push_back(new EHProcess("C",25,4));

 

    miter seek = hard_disk.begin();

    miter end = hard_disk.end();

    EHProcess *pro=0;

    //하드디스크에 설치한 프로그램을 실행 명령을 표현

    for( ; seek != end ; ++seek)

    {

        pro = *seek;

        rq.push(pro); //대기 큐에서 기다림

        pro->IdleToReady();//Idle 상태에서 Ready상태로 전이

    }

}

 

Scheduler::~Scheduler()

{

    Ending();

}

void Scheduler::Ending()

{

    miter seek = hard_disk.begin();

    for(   ; seek != hard_disk.end(); ++seek)

    {

        delete (*seek);

    }

}

 

void Scheduler::Simulation()

{

    EHProcess *process = 0;

    int job=0;

    while( !rq.empty() ) //대기 큐가 비어있지 않을 때

    {       

        process = rq.front();//가장 먼저 대기한 프로세스를 꺼냄

        rq.pop();

 

        job = process->Running();//꺼낸 프로세스를 실행

        if(job) //남은 작업이 있다면

        {

            rq.push(process); //대기큐에서 기다림

        }

        else

        {

            process->EndProgram();//프로세스 종료

        }

    }

}

 

//Program.cpp

#include "Scheduler.h"

int main()

{

    Scheduler *pro = new Scheduler;

    delete pro;

    return 0;

}

 

▷ 실행 결과

A 시작

B 시작

C 시작

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

C C C C

A A A A A

B B B B B B

B종료

C C C C

A A A A A

C C C C

A A A A A

A종료

C C C C

C

C종료

참고할 내용

3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]

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