处理机调度¶

// 伪代码示例
void FCFS_Scheduler() {
    while (!ready_queue.empty()) {
        Process current = ready_queue.front();  // 取队首进程
        ready_queue.pop();

        execute_process(current);  // 执行到完成
    }
}

// 非抢占式SJF调度算法
void nonPreemptiveSJF(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;
    vector<bool> completed(n, false);

    cout << "Non-preemptive SJF scheduling order:\n";

    for (int i = 0; i < n; i++) {
        // 找到当前时间已到达且未完成的最短作业
        int shortestIndex = -1;
        int shortestTime = INT_MAX;

        for (int j = 0; j < n; j++) {
            if (!completed[j] && 
                processes[j].arrivalTime <= currentTime && 
                processes[j].burstTime < shortestTime) {
                shortestTime = processes[j].burstTime;
                shortestIndex = j;
            }
        }

        if (shortestIndex == -1) {
            // 没有进程到达，等待下一个进程到达
            int nextArrival = INT_MAX;
            for (int j = 0; j < n; j++) {
                if (!completed[j]) {
                    nextArrival = min(nextArrival, processes[j].arrivalTime);
                }
            }
            currentTime = nextArrival;
            i--; // 重新尝试
            continue;
        }

        // 执行选中的进程
        Process& p = processes[shortestIndex];
        p.completionTime = currentTime + p.burstTime;
        p.turnaroundTime = p.completionTime - p.arrivalTime;
        p.waitingTime = p.turnaroundTime - p.burstTime;

        cout << "Process P" << p.id << " execution time: " << currentTime 
             << " - " << p.completionTime << endl;

        currentTime = p.completionTime;
        completed[shortestIndex] = true;
    }
}

// 抢占式SJF调度算法
void preemptiveSJF(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;
    int completed = 0;

    // 初始化剩余时间
    for (auto& p : processes) {
        p.remainingTime = p.burstTime;
    }

    cout << "Preemptive SJF scheduling order:\n";

    while (completed < n) {
        // 找到当前时间已到达且剩余时间最短的进程
        int shortestIndex = -1;
        int shortestTime = INT_MAX;

        for (int i = 0; i < n; i++) {
            if (processes[i].remainingTime > 0 && 
                processes[i].arrivalTime <= currentTime && 
                processes[i].remainingTime < shortestTime) {
                shortestTime = processes[i].remainingTime;
                shortestIndex = i;
            }
        }

        if (shortestIndex == -1) {
            // 没有进程可执行，跳到下一个到达时间
            int nextArrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (processes[i].remainingTime > 0) {
                    nextArrival = min(nextArrival, processes[i].arrivalTime);
                }
            }
            currentTime = nextArrival;
            continue;
        }

        Process& p = processes[shortestIndex];

        // 检查是否有新进程到达并可能抢占
        bool preempted = false;
        for (int i = 0; i < n; i++) {
            if (processes[i].arrivalTime == currentTime + 1 && 
                processes[i].remainingTime < p.remainingTime) {
                // 新进程到达且更短，当前进程被抢占
                cout << "Process P" << p.id << " preempted, execution time: " 
                     << currentTime << " - " << currentTime + 1 << endl;
                p.remainingTime -= 1;
                currentTime++;
                preempted = true;
                break;
            }
        }

        if (!preempted) {
            // 执行到完成
            cout << "Process P" << p.id << " execution time: " << currentTime 
                 << " - " << currentTime + p.remainingTime << endl;

            currentTime += p.remainingTime;
            p.remainingTime = 0;
            p.completionTime = currentTime;
            p.turnaroundTime = p.completionTime - p.arrivalTime;
            p.waitingTime = p.turnaroundTime - p.burstTime;
            completed++;
        }
    }
}

struct Process {
    int id;
    int priority;        // 优先级（数值越小优先级越高）
    int arrivalTime;
    int burstTime;
    int remainingTime;
    int completionTime;
    int turnaroundTime;
    int waitingTime;
};

// 优先级调度算法实现
void priorityScheduling(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;
    int completed = 0;

    // 初始化剩余时间
    for (auto& p : processes) {
        p.remainingTime = p.burstTime;
    }

    cout << "Priority scheduling order:\n";

    while (completed < n) {
        // 找到当前时间已到达且优先级最高的进程
        int highestPriorityIndex = -1;
        int highestPriority = INT_MAX;

        for (int i = 0; i < n; i++) {
            if (processes[i].remainingTime > 0 && 
                processes[i].arrivalTime <= currentTime && 
                processes[i].priority < highestPriority) {
                highestPriority = processes[i].priority;
                highestPriorityIndex = i;
            }
        }

        if (highestPriorityIndex == -1) {
            // 没有进程可执行，跳到下一个到达时间
            int nextArrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (processes[i].remainingTime > 0) {
                    nextArrival = min(nextArrival, processes[i].arrivalTime);
                }
            }
            currentTime = nextArrival;
            continue;
        }

        // 执行选中的进程
        Process& p = processes[highestPriorityIndex];
        cout << "Process P" << p.id << " (Priority: " << p.priority 
             << ") execution time: " << currentTime 
             << " - " << currentTime + p.remainingTime << endl;

        currentTime += p.remainingTime;
        p.remainingTime = 0;
        p.completionTime = currentTime;
        p.turnaroundTime = p.completionTime - p.arrivalTime;
        p.waitingTime = p.turnaroundTime - p.burstTime;
        completed++;
    }
}

// HRRN调度算法实现
struct Process {
    int id;
    int arrivalTime;
    int burstTime;
    int waitingTime;
    int completionTime;
    int turnaroundTime;
    double responseRatio;
};

void HRRN_Scheduling(vector<Process>& processes) {
    int n = processes.size();
    int currentTime = 0;
    vector<bool> completed(n, false);

    cout << "HRRN scheduling order:\n";

    for (int i = 0; i < n; i++) {
        // 计算所有已到达且未完成进程的响应比
        int bestIndex = -1;
        double highestRatio = -1;

        for (int j = 0; j < n; j++) {
            if (!completed[j] && processes[j].arrivalTime <= currentTime) {
                // 计算响应比
                int waitingTime = currentTime - processes[j].arrivalTime;
                processes[j].responseRatio = (double)(waitingTime + processes[j].burstTime) / processes[j].burstTime;

                if (processes[j].responseRatio > highestRatio) {
                    highestRatio = processes[j].responseRatio;
                    bestIndex = j;
                }
            }
        }

        if (bestIndex == -1) {
            // 没有进程到达，等待下一个进程到达
            int nextArrival = INT_MAX;
            for (int j = 0; j < n; j++) {
                if (!completed[j]) {
                    nextArrival = min(nextArrival, processes[j].arrivalTime);
                }
            }
            currentTime = nextArrival;
            i--; // 重新尝试
            continue;
        }

        // 执行选中的进程
        Process& p = processes[bestIndex];
        p.waitingTime = currentTime - p.arrivalTime;
        p.completionTime = currentTime + p.burstTime;
        p.turnaroundTime = p.completionTime - p.arrivalTime;

        cout << "Process P" << p.id << " (Response Ratio: " << p.responseRatio 
             << ") execution time: " << currentTime << " - " << p.completionTime << endl;

        currentTime = p.completionTime;
        completed[bestIndex] = true;
    }
}

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

struct Process {
    int id;
    int arrival_time;
    int burst_time;
    int remaining_time;
    int completion_time;

    Process(int id, int arrival, int burst) 
        : id(id), arrival_time(arrival), burst_time(burst), 
          remaining_time(burst), completion_time(0) {}
};

void round_robin_scheduling(std::vector<Process>& processes, int time_quantum) {
    std::queue<Process*> ready_queue;
    int current_time = 0;

    // 按到达时间排序
    std::sort(processes.begin(), processes.end(), 
              [](const Process& a, const Process& b) {
                  return a.arrival_time < b.arrival_time;
              });

    int process_index = 0;

    while (process_index < processes.size() || !ready_queue.empty()) {
        // 将到达的进程加入就绪队列
        while (process_index < processes.size() && 
               processes[process_index].arrival_time <= current_time) {
            ready_queue.push(&processes[process_index]);
            process_index++;
        }

        if (!ready_queue.empty()) {
            Process* current_process = ready_queue.front();
            ready_queue.pop();

            // 执行时间 = min(剩余时间, 时间片)
            int execution_time = std::min(current_process->remaining_time, time_quantum);

            // 更新进程状态
            current_process->remaining_time -= execution_time;
            current_time += execution_time;

            // 如果进程未完成，重新加入队列
            if (current_process->remaining_time > 0) {
                ready_queue.push(current_process);
            } else {
                // 进程完成，记录完成时间
                current_process->completion_time = current_time;
            }
        }
    }
}