前言

筆者在大學下屬的事業單位上班，最近去幫著帶下操作系統的實驗課，這裡隨手水點參考代碼，歡迎各位領導老師蒞臨指正

實驗目標

編寫一個簡單的進程調度器

實驗內容

1. 進程式控制制塊（PCB）的定義與管理
2. 進程調度演算法的實現
3. 進程創建、銷毀和切換
4. 給定一批進程對比3-4種調度演算法的時間（自選演算法）

實驗參考答案

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

using namespace std;

// 進程式控制制塊（PCB）
struct ProcessControlBlock
{
    // 進程ID
    int processID;
    // 到達時間
    int arrivalTime;
    // 執行時間
    int burstTime;
    // 等待時間
    int waitingTime;
    // 周轉時間
    int turnaroundTime;
};

// 先來先服務 (FCFS) 調度演算法
void FCFS(vector<ProcessControlBlock> &processes)
{
    int currentTime = 0;
    for (int i = 0; i < processes.size(); i++)
    {
        if (processes[i].arrivalTime > currentTime)
        {
            currentTime = processes[i].arrivalTime;
        }

        // 計算等待時間
        processes[i].waitingTime = currentTime - processes[i].arrivalTime;

        // 執行進程
        currentTime += processes[i].burstTime;

        // 計算周轉時間
        processes[i].turnaroundTime = currentTime - processes[i].arrivalTime;
    }
}

// 最短作業優先 (SJF) 調度演算法
void SJF(vector<ProcessControlBlock> &processes)
{
    int currentTime = 0;
    vector<ProcessControlBlock> remainingProcesses = processes;

    while (!remainingProcesses.empty())
    {
        int shortestJobIndex = -1;
        int shortestJobTime = INT_MAX;

        for (int i = 0; i < remainingProcesses.size(); i++)
        {
            if (remainingProcesses[i].arrivalTime <= currentTime && remainingProcesses[i].burstTime < shortestJobTime)
            {
                shortestJobIndex = i;
                shortestJobTime = remainingProcesses[i].burstTime;
            }
        }

        if (shortestJobIndex == -1)
        {
            currentTime++;
        }
        else
        {
            ProcessControlBlock &selectedProcess = remainingProcesses[shortestJobIndex];

            // 計算等待時間
            selectedProcess.waitingTime = currentTime - selectedProcess.arrivalTime;

            // 執行進程
            currentTime += selectedProcess.burstTime;

            // 計算周轉時間
            selectedProcess.turnaroundTime = currentTime - selectedProcess.arrivalTime;
            for (auto& pcb : processes)
            {
                if (selectedProcess.processID == pcb.processID)
                {
                    pcb.waitingTime = selectedProcess.waitingTime;
                    pcb.turnaroundTime = selectedProcess.turnaroundTime;
                    break;
                }
            }
            remainingProcesses.erase(remainingProcesses.begin() + shortestJobIndex);
        }
    }
}
// 輪轉時間片 (Round Robin) 調度演算法
void RoundRobin(vector<ProcessControlBlock> &processes, int timeQuantum)
{
    int currentTime = 0;
    queue<ProcessControlBlock> readyQueue;
    int processIndex = 0;

    while (!readyQueue.empty() || processIndex < processes.size())
    {
        while (processIndex < processes.size() && processes[processIndex].arrivalTime <= currentTime)
        {
            readyQueue.push(processes[processIndex]);
            processIndex++;
        }

        if (readyQueue.empty())
        {
            currentTime++;
        }
        else
        {
            ProcessControlBlock &runningProcess = readyQueue.front();
            readyQueue.pop();

            // 執行進程
            int remainingTime = min(timeQuantum, runningProcess.burstTime);
            currentTime += remainingTime;
            runningProcess.burstTime -= remainingTime;

            if (runningProcess.burstTime > 0)
            {
                readyQueue.push(runningProcess);
            }
            else
            {
                // 計算等待時間
                runningProcess.waitingTime = currentTime - runningProcess.arrivalTime;

                // 計算周轉時間
                runningProcess.turnaroundTime = currentTime - runningProcess.arrivalTime;
                for (auto &pcb: processes)
                {
                    if (runningProcess.processID == pcb.processID)
                    {
                        pcb.waitingTime = runningProcess.waitingTime;
                        pcb.turnaroundTime = runningProcess.turnaroundTime;
                        break;
                    }
                }
            }
        }
    }
}

int main()
{
    vector<ProcessControlBlock> processes = {
        {1, 0, 6, 0, 0},
        {2, 2, 3, 0, 0},
        {3, 4, 1, 0, 0},
        {4, 7, 5, 0, 0}};

    // 先來先服務 (FCFS) 調度演算法
    FCFS(processes);
    cout << "FCFS Scheduling:\n";
    for (const auto &pcb : processes)
    {
        cout << "Process " << pcb.processID << " Turnaround Time: " << pcb.turnaroundTime << endl;
    }

    // 重置進程數據
    for (auto &pcb : processes)
    {
        pcb.waitingTime = 0;
        pcb.turnaroundTime = 0;
    }

    // 最短作業優先 (SJF) 調度演算法
    SJF(processes);
    cout << "\nSJF Scheduling:\n";
    for (const auto &pcb : processes)
    {
        cout << "Process " << pcb.processID << " Turnaround Time: " << pcb.turnaroundTime << endl;
    }

    // 重置進程數據
    for (auto &pcb : processes)
    {
        pcb.waitingTime = 0;
        pcb.turnaroundTime = 0;
    }

    // 輪轉時間片 (Round Robin) 調度演算法
    int timeQuantum = 2;
    RoundRobin(processes, timeQuantum);
    cout << "\nRound Robin Scheduling:\n";
    for (const auto &pcb : processes)
    {
        cout << "Process " << pcb.processID << " Turnaround Time: " << pcb.turnaroundTime << endl;
    }

    return 0;
}