[Computer Science] CPU Scheduling 시뮬레이터

민지홍·2024년 10월 28일
C++CS운영체제
0

Computer Science

목록 보기
3/3

CPU 스케줄러

운영체제에서 CPU Scheduler는 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원의 배정을 결정한다.
CPU Scheduler는 다양한 스케줄링 알고리즘으로 다음 프로세스를 선택하는데, 이 알고리즘들을 C++을 사용해서 구현해보았다.

개요

CPU 스케줄링 알고리즘 시뮬레이터 구현

  • FCFS, SJF, 비선점형 우선순위, 선점형 우선순위, HRN, RR, SRT

개발 언어

  • C++14

UI

  • CLI(Console)

자료구조 구현

  • C++ STL Queue, Priority Queue

IDE

  • Visual Studio Code

스케줄링 알고리즘 종류

비선점형 스케줄링 알고리즘

  • 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계쏙 실행되는 방식
  • 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적음
    CPU 사용 시간이 긴 프로세스 떄문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 시스템의 처리율이 떨어짐
  • 과거의 일괄 작업 시스템에서 사용하던 방식
  • EX) FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링, 우선순위 스케줄링

선점형 스케줄링 알고리즘

  • 운영체제가 필요하다고 판단하면 실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있는 방식
  • 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합
  • 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용
  • 라운드 로빈(RR) 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링, 우선순위 스케줄링

스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘의 평가 기준

응답 시간(response time)

  • 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간

실행 시간(execution time)

  • 프로세스 작업이 시작된 후 종료되기까지의 시간

반환 시간(turn-around time)

  • 대기 시간을 포함하여 실행이 종료될 때까지의 시간

평균 대기 시간(AWT)

  • 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값

평균 반환 시간(ATT)

  • 모든 프로세스의 반환 시간을 합한 뒤 프로세스의 수로 나눈 값

스케줄링 알고리즘 구현

프로세스 관련 코드

Process.h

Process.h에 Process 클래스를 선언하여 PID, 도착 시간, 실행 시간, 대기 시간, 반환 시간, 우선 순위 등 각 프로세스에 대한 정보들을 저장하는 클래스 구현

#ifndef PROCESS_H
#define PROCESS_H
#include <iostream>
#include <queue>
using namespace std;
class Process
{
public:
    int id;
    int arrivalTime;    //도착 시간
    int executionTime;  //실행 시간
    int waitingTime;    //대기 시간
    int returnTime;     //반환 시간
    double priority;    //우선 순위
    int startTime;      //시작 시간
    int runningTime;    //현재 실행 시간(진행도)
    int status;         // 프로세스의 상태(-1이면 생성, 0이면 대기, 1이면 실행중, 2이면 완료)
    Process(int id, int arrivalTime, int executionTime)
    {
        this->id = id;
        this->arrivalTime = arrivalTime;
        this->executionTime = executionTime;
        this->priority = 0.0;
        this->status = -1;
    }
    Process(int id, int arrivalTime, int executionTime, int priority)
    {
        this->id = id;
        this->arrivalTime = arrivalTime;
        this->executionTime = executionTime;
        this->priority = priority;
        this->status = -1;
    }
    void start(int currentTime) // 프로세스 시작
    {
        //cout << "Time=" << currentTime << " PID " << id << " Start\n";  //프로세스 실행 로그
        status = 1;
    }
    void pause(int currentTime) // 프로세스 중지(Context Switch)
    {
        status = 0;
    }
    void finish(int currentTime) // 프로세스 종료
    {
        //cout << "Time=" << currentTime << " PID " << id << " Finish\n";   //프로세스 종료 로그
        status = 2;
        returnTime = waitingTime + executionTime; // 반환 시간 = 대기 시간 + 실행 시간
    }
};
#endif

ProcessUtil.cpp

ProcessUtil.cpp에 우선순위 큐를 정렬하는 기준들과 대기 시간 추가, 우선순위 큐의 데이터 변경에 따른 큐 업데이트 함수를 구현하였다.

#include "Process.h"

struct BurstTimeComparator // 실행 시간 우선 순위 큐 정렬
{
    bool operator()(const Process *a, const Process *b)
    {
        return a->executionTime > b->executionTime; // 실행 시간이 짧은 프로세스부터 정렬
    }
};
struct PriorityComparator // 우선 순위 큐 정렬
{
    bool operator()(const Process *a, const Process *b)
    {
        if (a->priority == b->priority) // 우선순위가 같을 때
            return a->arrivalTime > b->arrivalTime; // 먼저 도착한 프로세스가 앞으로 정렬(FIFO)
        return a->priority > b->priority; // 우선순위 높은(숫자가 작은) 순서로 정렬
    }
};
struct RemainTimeComparator // 남은 실행 시간 우선 순위 큐 정렬
{
    bool operator()(const Process *a, const Process *b)
    {
        if (a->executionTime - a->runningTime == b->priority - b->runningTime) // 우선순위가 같을 때
            return a->arrivalTime > b->arrivalTime; // 먼저 도착한 프로세스가 앞으로 정렬(FIFO)
        return a->executionTime - a->runningTime > b->executionTime - b->runningTime; // 남은 실행시간이 작은 순서로 정렬
    }
};

void update_waitingTime(vector<Process *> &process)
{
    for(int i = 0;i<process.size();i++)
        if(process[i]->status == 0) {
            process[i]->waitingTime++;
    }
}
template <typename T>
void update_queue(priority_queue<Process *, vector<Process *>, T> &pq)
{
    int len = pq.size();
    while (len--)
    {
        Process *temp = pq.top();
        temp->priority = double(temp->executionTime) / (temp->waitingTime + temp->executionTime);
        pq.push(temp);
        pq.pop();
    }
}

FCFS(First Come First Served) 스케줄링

FCFS 스케줄링의 동작 방식

  • 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
  • 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
  • 큐가 하나라 모든 프로세스는 우선순위가 동일

FCFS 스케줄링의 평가

  • 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐
  • 특히 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐 (콘보이 효과)

구현

FCFS 스케줄링 알고리즘은 프로세스가 생성되어 레디 큐에 들어온 순서대로 프로세스를 처리하기 때문에 큐 자료구조를 사용했다.

#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    queue<Process *> q; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime); // 새로운 프로세스 생성
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            process[processCount]->status = 0;
            q.push(process[processCount++]);
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            runningProcess = q.front();         // 다음 프로세스 선택
            q.pop();                            // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (q.empty()) // 모든 프로세스 종료 시
            {
                break;
            }   
            runningProcess = q.front();         // 다음 프로세스 선택
            q.pop();                            // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        runningProcess->runningTime++;
        currentTime++;               // 시간 진행
        update_waitingTime(process); // 대기 중인 프로세스 대기 시간 추가
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if(i < 10) {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

SJF(Shortest Job First) 스케줄링

SJF 스케줄링의 동작 방식

  • 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
  • 최단 작업 우선 스케줄링이라고도 함
  • 콘보이 효과를 완화하여 시스템의 효율성을 높임

SJF 스케줄링 평가

  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
  • 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐(starvation - 아사 현상)

Aging(나이 먹기)

  • 아사 현상의 완화 방법
  • 프로세스가 양보할 수 있는 상한선을 정하는 방식
  • 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것

구현

SJF 알고리즘은 실행 시간이 짧은 프로세스 먼저 실행시켜야 하기 때문에 실행 시간을 우선순위로 이용한 우선순위 큐 자료구조를 사용하였다.

위 코드와 같이 실행 시간이 짧은 프로세스가 먼저 pop 될 수 있도록 정렬하였다.

#include "Process.h"
#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    priority_queue<Process *, vector<Process *>, BurstTimeComparator> pq; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {

        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            process[processCount]->status = 0;
            pq.push(process[processCount++]);
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (pq.empty()) // 모든 프로세스 종료 시
            {
                break;
            }
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        runningProcess->runningTime++;
        currentTime++;               // 시간 진행
        update_waitingTime(process); // 대기 중인 프로세스 대기 시간 추가
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if(i < 10) {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << "  Waiting Time=" << process[i]->waitingTime << "  Return Time=" << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

우선순위(Priority) 스케줄링 - 비선점형

우선순위 스케줄링의 동작 방식

  • 프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘

우선순위 스케줄링의 평가

  • 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킴
  • 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨림

구현

우선순위가 높은(숫자가 작은) 프로세스 순서대로 실행되어야 하기 때문에 우선순위 큐 자료구조를 사용하였다.

#include "Process.h"
#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    priority_queue<Process *, vector<Process *>, PriorityComparator> pq; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime, priority);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            process[processCount]->status = 0;
            pq.push(process[processCount++]);
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (pq.empty()) // 모든 프로세스 종료 시
                break;
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        currentTime++; // 시간 진행
        runningProcess->runningTime++;
        update_waitingTime(process);
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if(i < 10)
                    cout << " ";
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
            cout << " ";
    }
    cout << "\n\n";
    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

우선순위(Priority) 스케줄링 - 선점형

우선순위 스케줄링의 동작 방식

  • 프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘

구현

비선점형과 다르게 프로세스가 실행되고 있어도 실행 중인 프로세스보다 레디 큐에 들어 있는 프로세스의 우선순위가 더 높으면 바로 Context switch(문맥 교환)이 일어나야 하기 때문에 우선순위 큐 자료구조를 사용하였다.

#include "Process.h"
#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    priority_queue<Process *, vector<Process *>, PriorityComparator> pq; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime, priority);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            process[processCount]->status = 0;
            pq.push(process[processCount++]);
        }

        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            cout << "|P" << runningProcess->id;
        }
        if (pq.top()->priority < runningProcess->priority) // 실행 중인 프로세스의 우선순위보다 큐에 들어있는 프로세스의 우선순위가 높을 때 Context switching
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->pause(currentTime); // 실행 중인 프로세스 중지
            isRunningExists = false;
            pq.push(runningProcess);            // 큐에 다시 넣기
            runningProcess = pq.top();          // 우선순위가 더 높은 프로세스 선택
            pq.pop();                           // 우선순위가 더 높은 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        if (runningProcess->executionTime == runningProcess->runningTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (pq.empty()) // 모든 프로세스 종료 시
            {
                break;
            }
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        currentTime++; // 시간 진행
        runningProcess->runningTime++;
        update_waitingTime(process);
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if(i < 10) {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

HRN(Highest Response Ratio Next) 스케줄링

HRN 스케줄링의 동작 방식

  • SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
  • 최고 응답률 우선 스케줄링이라고도 함
  • 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식

HRN 스케줄링의 평가

  • 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화
  • 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높임
  • 여전히 공평성이 위배되어 많이 사용되지 않음

구현

대기 시간과 사용 시간을 고려하여 스케줄링해야 하기 때문에 우선순위가 실시간으로 변경되어야 한다. 이를 위해 우선순위 큐를 사용하였는데, C++ STL에서 지원하는 우선순위 큐는 데이터를 실시간으로 정렬해주는 기능이 없기 때문에 큐에 있는 모든 데이터를 pop하고 우선순위를 업데이트 시켜준 뒤, 다시 push하는 방법으로 구현하였다.

#include "Process.h"
#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    priority_queue<Process *, vector<Process *>, PriorityComparator> pq; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            pq.push(process[processCount]);
            process[processCount++]->status = 0;
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (pq.empty()) // 모든 프로세스 종료 시
            {
                break;
            }
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        currentTime++; // 시간 진행
        runningProcess->runningTime++;
        update_waitingTime(process);
        update_queue(pq);
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if (i < 10)
                {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

라운드 로빈(RR : Round-Robin) 스케줄링

라운드 로빈 스케줄링의 동작 방식

  • 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
  • 선점형 알고리즘 중 가장 단순하고 대표적인 방식
  • 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

타임 슬라이스

  • 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
  • 타임 슬라이스가 큰 경우 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음
  • 타임 슬라이스가 작은 경우 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생
  • 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요

구현

프로세스가 레디 큐에 들어온 순서대로 일정한 타임 슬라이스 동안만 프로세스를 실행하고 타임 아웃이 되면 문맥 교환이 일어나야 한다. 타임 슬라이스는 2로 설정하였으며 사용한 자료구조는 큐이다.


#include "Process.h"
#include "ProcessUtil.cpp"
#include <iostream>
#include <queue>
#include <fstream>
#define TIME_QUANTUM 2
using namespace std;
int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    queue<Process *> q; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    int TimeQuantumCount = 0;
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            q.push(process[processCount]);
            process[processCount++]->status = 0;
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            runningProcess = q.front();         // 다음 프로세스 선택
            q.pop();                            // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (q.empty()) // 모든 프로세스 종료 시
            {
                break;
            }
            runningProcess = q.front();         // 다음 프로세스 선택
            q.pop();                            // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            TimeQuantumCount = 0;
            cout << "P" << runningProcess->id;
        }
        if (TimeQuantumCount == TIME_QUANTUM) // 타임 아웃
        {
            cout << "|";
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            runningProcess->pause(currentTime); // 실행 중인 프로세스 중지
            isRunningExists = false;
            q.push(runningProcess);             // 큐에 다시 넣기
            runningProcess = q.front();         // 다음 프로세스 선택
            q.pop();                            // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            TimeQuantumCount = 0;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        TimeQuantumCount++;
        runningProcess->runningTime++;
        currentTime++; // 시간 진행
        update_waitingTime(process);
    }

    // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if (i < 10)
                {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

결과

SRT(Shortest Remaining Time) 우선 스케줄링

SRT 스케줄링의 동작 방식

  • 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택

SRT 스케줄링의 평가

  • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨
  • 가장 대기시간이 짧은 스케줄링 알고리즘이나 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음

구현

#include "Process.h"
#include "ProcessUtil.cpp"
#include <queue>
#include <iostream>
#include <fstream>
#include <vector>
#define TIME_QUANTUM 2

using namespace std;

int main()
{
    vector<int> timeHistory; // 간트 차트를 그리기 위한 타임 라인
    Process *p;
    vector<Process *> process;
    priority_queue<Process *, vector<Process *>, RemainTimeComparator> pq; // Ready queue
    ifstream fin("Processes.txt");
    if (!fin.is_open())
    {
        cout << "File open failed...\n";
        return 1;
    }
    while (!fin.eof())
    {
        int id = 0;
        int arrivalTime = 0;
        int executionTime = 0;
        int priority = 0;
        fin >> id >> arrivalTime >> executionTime >> priority;
        p = new Process(id, arrivalTime, executionTime);
        process.push_back(p);
    }
    int currentTime = 0;            // 현재 시간
    int processCount = 0;           // 프로세스가 도착한 순서대로 큐에 들어갈 때 인덱스
    Process *runningProcess = NULL; // 실행 중인 프로세스
    bool isRunningExists = false;   // 실행중인 프로세스가 있는지
    int TimeQuantumCount = 0;
    cout << "\n";
    while (1)
    {
        if (process.size() > processCount && currentTime == process[processCount]->arrivalTime) // 현재 시간이 다음 프로세스 도착 시간일 때
        {
            // cout << "Time=" << currentTime << " PID " << process[processCount]->id << " Arrive\n";   // 프로세스 도착 로그
            pq.push(process[processCount]);
            process[processCount++]->status = 0;
        }
        if (!isRunningExists) // 현재 실행중인 프로세스가 없을 때
        {
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            timeHistory.push_back(currentTime); // 타임 라인 찍기
            cout << "|P" << runningProcess->id;
        }
        if (runningProcess->runningTime == runningProcess->executionTime) // 프로세스가 작업을 완료하고 종료될 때
        {
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->finish(currentTime); // 프로세스 종료
            isRunningExists = false;
            if (pq.empty()) // 모든 프로세스 종료 시
            {
                break;
            }
            runningProcess = pq.top();          // 다음 프로세스 선택
            pq.pop();                           // 다음 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            TimeQuantumCount = 0;
            cout << "P" << runningProcess->id;
        }
        if (TimeQuantumCount == TIME_QUANTUM)   // 타임 아웃
        {                                       
            cout << "|";
            timeHistory.push_back(currentTime);  // 타임 라인 찍기
            runningProcess->pause(currentTime); // 실행 중인 프로세스 중지
            isRunningExists = false;
            pq.push(runningProcess);            // 큐에 다시 넣기
            runningProcess = pq.top();          // 우선순위가 더 높은 프로세스 선택
            pq.pop();                           // 우선순위가 더 높은 프로세스 꺼내기
            runningProcess->start(currentTime); // 프로세스 실행
            isRunningExists = true;
            TimeQuantumCount = 0;
            cout << "P" << runningProcess->id;
        }
        cout << "-";
        TimeQuantumCount++;
        currentTime++; // 시간 진행
        runningProcess->runningTime++;
        update_waitingTime(process);
        update_queue(pq);
    }

        // 타임 라인 출력
    cout << "\n";
    int historyCount = 0;
    for (int i = 0; i <= currentTime; i++)
    {
        if (i == timeHistory[historyCount])
        {
            if (i != 0)
            {
                if(i < 10) {
                    cout << " ";
                }
                cout << "  ";
            }
            cout << timeHistory[historyCount++];
        }
        else
        {
            cout << " ";
        }
    }
    cout << "\n\n";

    double sumWaitingTime = 0;
    double sumReturnTime = 0;
    for (int i = 0; i < process.size(); i++)
    {
        cout << "PID " << process[i]->id << " Waiting Time = " << process[i]->waitingTime << " Return Time = " << process[i]->returnTime << "\n";
        sumWaitingTime += process[i]->waitingTime;
        sumReturnTime += process[i]->returnTime;
    }
    cout << "Average Waiting Time = " << sumWaitingTime / process.size() << "\n";
    cout << "Average Return Time = " << sumReturnTime / process.size() << "\n";
    delete[] p;
    fin.close();
    return 0;
}

느낀점

  1. 처음엔 알고리즘들을 금방 구현할 수 있을 줄 알았지만 Context switch 하는 타이밍과 같이 고려해야할 점이 꽤 많았고, 알고리즘들을 구현하던 중 이미 구현 완료된 알고리즘들의 아쉬운 점들을 계속 수정하다보니 생각보다 오래걸렸다. 그리고 알고리즘에 중복되는 코드들이 많아서 이를 정리 및 관리하는 방법을 더 생각해봐야 할 것 같다.
  2. HRN 알고리즘에서 우선순위가 계속 바뀌는 상황을 실시간으로 우선순위 큐에 적용(정렬)하는 방법이 떠오르지 않아 시간복잡도가 O(n)인 비효율적인 방법을 사용한 것도 아쉬웠다. 이 것을 해결한다면 Context switch 하는 비용(시간)을 고려하여 각 알고리즘이 프로세스를 처리하는 실제 시간을 측정하여 비교할 수 있을 것 같다.
  3. 알고리즘을 직접 구현해보니 각 알고리즘의 원리를 정확하게 이해할 수 있었다. 그리고 구현하는 과정도 코딩 테스트 문제를 푸는 것 같아서 재밌었다. 나에게는 많은 공부가 된 프로젝트였다.
profile
민지홍
이전 포스트

[Algorithm] C++ 순열 (next_permutation)

0개의 댓글