CPU Scheduling

1. CPU Scheduling

• 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법
• 운영체제는 프로세스들에게 CPU를 적절히 배정함으로써 시스템의 성능을 개선

• Ready Queue에 있는 프로세스를 대상으로 CPU를 할당하는 순서와 방식을 결정

 

2. 스케줄링 유형

• 비선점형 스케줄링(Non-Preemptive)
  • 프로세스 종료 또는 입출력 등의 이벤트 발생 시까지 실행을 보장
    • 모든 프로세스에 공정
    • 응답 시간 예측 가능
    • 짧은 수행시간을 가진 프로세스라도 순서를 기다려야 작업 가능
• 선점형 스케줄링(Preemptive)
  • OS가 CPU의 사용권을 선점할 수 있는 경우에 강제로 회수
    • 높은 우선 순위를 가진 프로세스를 빠르게 처리하려는 시스템에 유용
    • 빠른 응답 시간을 요구하는 시분할 시스템에 유용
    • 높은 우선 순위를 가진 프로세스가 많을 경우 overhead 발생

 

3. 스케줄링 평가 기준(Criteria)

1. CPU 이용률(CPU utilization)  
   • 시간당 CPU를 사용한 시간의 비율
   • 프로세서를 실행상태로 항상 유지하려고 해야함
2. 처리율(Throughput)
   • 시간당 처리한 작업의 비율
   • 단위 시간당 완료되는 작업 수가 많도록 해야함
3. 반환시간(Turnaround Time) 
   • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
   • 작업이 Ready Queue에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합
4. 대기시간(Waiting Time)
   • 대기열에 들어와 CPU를 할당받기 까지 기다린 시간
   • Ready Queue에서 기다린 시간의 총합
5. 반응시간(Response Time)
   • 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
     • 대기시간은 준비 큐에서 기다린 모든 시간을 합친 것이지만, 반응 시간은 CPU를 할당받은 최초의 순간까지 기다린 시간 한번 만을 측정

※ CPU 이용률과 처리율은 극대화하는 것이 좋고 반환시간, 대기시간, 반응시간은 줄이는 것이 일반적으로 좋음

 

4. 스케줄링 알고리즘

1) FCFS(First Come, First Served)

• Queue에 도착한 순서대로 CPU를 할당
• 비선점형
• 할당되었던 CPU가 반환될 때만 스케줄링이 이뤄짐
  • 실행 시간이 긴 프로세스가 먼저 도달할 경우 효율성이 낮아짐

 

code)

#include <iostream>
#include <queue>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
};

void fcfsScheduling(queue<Process>& processes) {
    int currentTime = 0;

    while (!processes.empty()) {
        Process currentProcess = processes.front();
        processes.pop();

        if (currentProcess.arrivalTime > currentTime) {
            currentTime = currentProcess.arrivalTime;
        }

        cout << "Processing Process " << currentProcess.id << " at time " << currentTime << endl;

        currentTime += currentProcess.burstTime;
    }
}

int main() {
    int n;
    cout << "Enter the number of processes: ";
    cin >> n;

    queue<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time and burst time for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime;
        processes.push(p);
    }

    cout << "FCFS Scheduling:" << endl;
    fcfsScheduling(processes);

    return 0;
}

 

2) SJF(Shortest Job First)

• 실행 시간이 가장 짧은 작업을 우선 수행
  • 평균 대기 시간이 짧음
  • Starvation 발생 가능
    • 실행 시간이 긴 프로세스는 CPU를 할당 받지 못할 수도 있음

비선점형 SJF

code)

#include <iostream>
#include <queue>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
};

void fcfsScheduling(queue<Process>& processes) {
    int currentTime = 0;

    while (!processes.empty()) {
        Process currentProcess = processes.front();
        processes.pop();

        if (currentProcess.arrivalTime > currentTime) {
            currentTime = currentProcess.arrivalTime;
        }

        cout << "Processing Process " << currentProcess.id << " at time " << currentTime << endl;

        currentTime += currentProcess.burstTime;
    }
}

int main() {
    int n;
    cout << "Enter the number of processes: ";
    cin >> n;

    queue<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time and burst time for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime;
        processes.push(p);
    }

    cout << "FCFS Scheduling:" << endl;
    fcfsScheduling(processes);

    return 0;
}

선점형 SJF

code)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
};

bool compareArrival(const Process& p1, const Process& p2) {
    return p1.arrivalTime < p2.arrivalTime;
}

bool compareBurst(const Process& p1, const Process& p2) {
    return p1.burstTime < p2.burstTime;
}

void preemptiveSjfScheduling(vector<Process>& processes) {
    int currentTime = 0;
    int n = processes.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (burstTime, processId)

    int idx = 0;
    while (idx < n || !pq.empty()) {
        if (pq.empty()) {
            currentTime = processes[idx].arrivalTime;
        }

        while (idx < n && processes[idx].arrivalTime <= currentTime) {
            pq.push(make_pair(processes[idx].burstTime, processes[idx].id));
            idx++;
        }

        pair<int, int> currentTask = pq.top();
        pq.pop();

        int execTime = min(currentTask.first, processes[idx].arrivalTime - currentTime);
        currentTime += execTime;
        currentTask.first -= execTime;

        cout << "Processing Process " << currentTask.second << " at time " << currentTime << endl;

        if (currentTask.first > 0) {
            pq.push(currentTask);
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of processes: ";
    cin >> n;

    vector<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time and burst time for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime;
        processes.push_back(p);
    }

    sort(processes.begin(), processes.end(), compareArrival);

    cout << "Preemptive SJF Scheduling:" << endl;
    preemptiveSjfScheduling(processes);

    return 0;
}

 

2-1) HRN(Highest Response-ratio Next)

• 우선 순위를 계산하여 동작
  • 우선 순위 = (대기시간+실행시간) / (실행시간)
• SJF의 점유 불평등 현상을 해결

code)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
};

bool compareArrival(const Process& p1, const Process& p2) {
    return p1.arrivalTime < p2.arrivalTime;
}

void hrnScheduling(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;

    while (!processes.empty()) {
        int idx = -1;
        double maxResponseRatio = -1;

        for (int i = 0; i < n; ++i) {
            if (processes[i].arrivalTime <= currentTime) {
                double responseRatio = double(currentTime - processes[i].arrivalTime + processes[i].burstTime) / processes[i].burstTime;

                if (responseRatio > maxResponseRatio) {
                    maxResponseRatio = responseRatio;
                    idx = i;
                }
            }
        }

        if (idx == -1) {
            currentTime++;
            continue;
        }

        Process currentProcess = processes[idx];
        processes.erase(processes.begin() + idx);

        cout << "Processing Process " << currentProcess.id << " at time " << currentTime << endl;

        currentTime += currentProcess.burstTime;
    }
}

int main() {
    int n;
    cout << "Enter the number of processes: ";
    cin >> n;

    vector<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time and burst time for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime;
        processes.push_back(p);
    }

    sort(processes.begin(), processes.end(), compareArrival);

    cout << "HRN Scheduling:" << endl;
    hrnScheduling(processes);

    return 0;
}

 

3) Priority

• 프로세스마다 우선순위가 있고, 높은 우선순위 순으로 CPU를 할당
  • Starvation 발생 가능
  • Indefinite Blocking(무기한 봉쇄) 발생 가능
    
    • 실행 준비가 되어 있으나 CPU를 사용하지 못하는 프로세스가 CPU를 무한정 대기하는 상태

code)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
    int priority;    // 우선순위
};

bool compareArrival(const Process& p1, const Process& p2) {
    return p1.arrivalTime < p2.arrivalTime;
}

bool comparePriority(const Process& p1, const Process& p2) {
    return p1.priority < p2.priority;
}

void priorityScheduling(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;

    while (!processes.empty()) {
        sort(processes.begin(), processes.end(), comparePriority);

        int idx = -1;
        for (int i = 0; i < n; ++i) {
            if (processes[i].arrivalTime <= currentTime) {
                idx = i;
                break;
            }
        }

        if (idx == -1) {
            currentTime++;
            continue;
        }

        Process currentProcess = processes[idx];
        processes.erase(processes.begin() + idx);

        cout << "Processing Process " << currentProcess.id << " at time " << currentTime << endl;

        currentTime += currentProcess.burstTime;
    }
}

int main() {
    int n;
    cout << "Enter the number of processes: ";
    cin >> n;

    vector<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time, burst time, and priority for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime >> p.priority;
        processes.push_back(p);
    }

    sort(processes.begin(), processes.end(), compareArrival);

    cout << "Priority Scheduling:" << endl;
    priorityScheduling(processes);

    return 0;
}

 

4) Round-Robin

• 프로세스가 일정 시간만을 수행하고 다시 대기상태로 돌아감
• 그 후 다른 프로세스가 마찬가지로 일정 시간만을 수행
  • 시분할 시스템에서 주로 사용하는 방식
  • 반응 시간이 빨라짐
  • 공정한 스케줄링 방식

code)

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Process {
    int id;          // 프로세스 ID
    int arrivalTime; // 도착 시간
    int burstTime;   // 실행 시간
    int remainingTime; // 남은 실행 시간
};

void roundRobinScheduling(vector<Process>& processes, int quantum) {
    int n = processes.size();
    queue<Process> readyQueue;

    int currentTime = 0;
    int idx = 0;

    while (!readyQueue.empty() || idx < n) {
        while (idx < n && processes[idx].arrivalTime <= currentTime) {
            processes[idx].remainingTime = processes[idx].burstTime;
            readyQueue.push(processes[idx]);
            idx++;
        }

        if (readyQueue.empty()) {
            currentTime++;
            continue;
        }

        Process currentProcess = readyQueue.front();
        readyQueue.pop();

        int executeTime = min(quantum, currentProcess.remainingTime);

        cout << "Processing Process " << currentProcess.id << " at time " << currentTime << endl;

        currentProcess.remainingTime -= executeTime;
        currentTime += executeTime;

        while (idx < n && processes[idx].arrivalTime <= currentTime) {
            processes[idx].remainingTime = processes[idx].burstTime;
            readyQueue.push(processes[idx]);
            idx++;
        }

        if (currentProcess.remainingTime > 0) {
            readyQueue.push(currentProcess);
        }
    }
}

int main() {
    int n, quantum;
    cout << "Enter the number of processes: ";
    cin >> n;

    cout << "Enter time quantum: ";
    cin >> quantum;

    vector<Process> processes;

    for (int i = 0; i < n; ++i) {
        Process p;
        p.id = i + 1;
        cout << "Enter arrival time and burst time for Process " << p.id << ": ";
        cin >> p.arrivalTime >> p.burstTime;
        processes.push_back(p);
    }

    cout << "Round Robin Scheduling:" << endl;
    roundRobinScheduling(processes, quantum);

    return 0;
}

 

5) Multilevel Queue

• 다단계 큐
• Ready Queue가 여러 개로 나뉨
• 큐마다 다른 Time Quantum을 할당해 우선 순위가 낮은 큐들이 실행하지 못하는 현상을 방지
  • 우선 순위가 높은 큐에는 작은 Time Quantum
  • 우선 순위가 낮은 큐에는 큰 Time Quantum
• 각 큐에는 각자의 스케줄링 알고리즘을 가지고 있고, 각 큐 간의 프로세스 이동 불가