操作系统进程调度代码的修正与优化

### 问题分析 原代码在处理进程调度时，虽然整体逻辑基本正确，但可能存在一些细节问题导致 “WA”（Wrong Answer）。下面是对原代码可能存在问题的分析和修正建议： - **内存管理**：原代码使用了 `new` 和 `delete` 手动管理内存，这容易出错，并且可能导致内存泄漏。可以使用更安全的方式，避免手动内存管理。 - **进程切换时的数据更新**：当进程被切换时，需要确保 `processes` 数组中对应的进程信息得到正确更新。 ### 修正后的代码 ```cpp #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; // 定义进程结构体 struct Process { int id; int arrivalTime; int executionTime; int priority; int remainingTime; int endTime; Process(int _id, int _arrivalTime, int _executionTime, int _priority) : id(_id), arrivalTime(_arrivalTime), executionTime(_executionTime), priority(_priority), remainingTime(_executionTime), endTime(0) {} // 重载小于运算符，用于优先队列 bool operator<(const Process& other) const { if (priority != other.priority) { return priority < other.priority; } return arrivalTime > other.arrivalTime; } }; // 模拟进程调度 void processScheduling(vector<Process>& processes) { int currentTime = 0; int index = 0; priority_queue<Process> waitingQueue; int currentProcessIndex = -1; while (index < processes.size() ||!waitingQueue.empty() || currentProcessIndex != -1) { // 将到达的进程加入等待队列 while (index < processes.size() && processes[index].arrivalTime <= currentTime) { waitingQueue.push(processes[index]); index++; } // 如果当前没有进程在执行，从等待队列中取出一个进程 if (currentProcessIndex == -1 &&!waitingQueue.empty()) { currentProcessIndex = waitingQueue.top().id - 1; // 假设进程 id 从 1 开始 waitingQueue.pop(); } // 如果有更高优先级的进程，切换进程 if (!waitingQueue.empty() && waitingQueue.top().priority > processes[currentProcessIndex].priority) { waitingQueue.push(processes[currentProcessIndex]); currentProcessIndex = waitingQueue.top().id - 1; waitingQueue.pop(); } // 执行当前进程 if (currentProcessIndex != -1) { processes[currentProcessIndex].remainingTime--; currentTime++; if (processes[currentProcessIndex].remainingTime == 0) { processes[currentProcessIndex].endTime = currentTime; currentProcessIndex = -1; } } else { // 如果没有进程在执行，时间推进到下一个进程到达的时间 if (index < processes.size()) { currentTime = processes[index].arrivalTime; } } } // 按结束时间排序并输出结果 sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) { return a.endTime < b.endTime; }); for (const auto& process : processes) { cout << process.id << " " << process.endTime << endl; } } int main() { vector<Process> processes; int id, arrivalTime, executionTime, priority; while (cin >> id >> arrivalTime >> executionTime >> priority) { processes.emplace_back(id, arrivalTime, executionTime, priority); } processScheduling(processes); return 0; } ``` ### 代码解释 1. **去除手动内存管理**：使用 `currentProcessIndex` 来记录当前正在执行的进程在 `processes` 数组中的索引，避免了手动使用 `new` 和 `delete` 管理内存。 2. **进程更新**：在进程执行和切换时，直接更新 `processes` 数组中对应的进程信息，确保数据的一致性。 ### 复杂度分析 - **时间复杂度**：$O(n \log n)$，其中 $n$ 是进程的数量。主要是由于优先队列的插入和删除操作的时间复杂度为 $O(\log n)$，以及最后对进程按结束时间排序的时间复杂度为 $O(n \log n)$。 - **空间复杂度**：$O(n)$，主要用于存储优先队列和进程信息。 ### 开发建议 - **边界条件测试**：在提交代码前，使用各种边界条件进行测试，例如只有一个进程、多个进程同时到达等情况。 - **代码可读性**：添加更多的注释来解释关键逻辑，提高代码的可读性。 - **错误处理**：可以添加输入验证，确保输入的合法性，避免因异常输入导致程序出错。 ######[AI写代码神器 | 1159点数解答 | 2026-07-26 14:47:47]