操作系统实验习题解析 上篇

孤村落日残霞，轻烟老树寒鸦，一点飞鸿影下。

青山绿水，白草红叶黄花。

                                        ————《天净沙·秋》 白朴 【元】

---

目录

实验一：

代码：

解析：

 运行结果：

实验二：

代码解析

1. 类设计

2. 主要功能

3. 主函数

 运行结果：

---

今天带来操作系统的两道实验题目的解析

实验一：

这里对于上述的要求进行编译，其中的第一题我们都知道这里的优先级算法（非抢占）和时间片算法是核心。所以我们先来过一遍这两个核心的基础概念。

优先级算法：所有的进程按照优先级的大小来进行排序，然后运行进程（在队列里）。这种算法比较浪费时间，所以有了下面这个算法。

时间片算法：我们首先定义一个大小合适的时间片，不宜大（如果时间片太大，那么就起不到该有的作用）。然后对于再队列里的进程按顺序进行运行（运行的时间就是时间片规定的），将已经运行结束的进程结束，提出队列；对于没有运行结束的进程放在队列的最后，排在之前最后一个的后面，按顺序等待运行。

代码：

#include <iostream>
#include <string>
#include <cstdlib>  // rand()
#include <Windows.h> // 控制台颜色
#include <queue>
#include <vector>
using namespace std;// 最大进程数量
const int N = 10;
int n; // 用户输入的进程数量// 进程控制块 PCB
struct PCB {string name;   // 进程名字int time;      // 初始需要执行的时间int priority;  // 优先级int status;    // -1: 就绪, 0: 运行中, 1: 完成int runtime;   // 已运行时间int lefttime;  // 剩余执行时间
};// 优先队列比较器 (优先级高的在上, 如果一样则等待时间长的在上)
struct cmp {bool operator()(const PCB& a, const PCB& b) const {if (a.priority == b.priority)return a.time > b.time; // 优先等待时间长的return a.priority < b.priority; // 优先级高的优先}
};// 三个队列
priority_queue<PCB, vector<PCB>, cmp> q1; // 优先级调度就绪队列
queue<PCB> q2; // 时间片轮转就绪队列
queue<PCB> q3; // 完成队列 (两种算法共用)// 控制台颜色
enum ConsoleColor {DEFAULT = 7, GREEN = 10
};// 设置控制台颜色
void setConsoleColor(ConsoleColor color) {HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleTextAttribute(hConsole, color);
}// 恢复默认颜色
void resetConsoleColor() {setConsoleColor(DEFAULT);
}// 初始化优先级队列
void init_priority() {for (int i = 0; i < n; i++) {PCB t;t.name = string(1, 'A' + i); // 名字用大写字母t.priority = (rand() % 20) + 50; // 优先级范围: 50~69t.time = (rand() % 20) + 1; // 执行时间范围: 1~20t.status = -1; // 初始状态为就绪t.lefttime = t.time;t.runtime = 0;q1.push(t);}
}// 初始化时间片轮转法队列
void init_timeturn() {for (int i = 0; i < n; i++) {PCB t;t.name = string(1, 'A' + i);t.time = (rand() % 20) + 1;t.status = -1;t.lefttime = t.time;t.runtime = 0;q2.push(t);}
}// 打印优先级调度中的就绪队列
void print_priority(priority_queue<PCB, vector<PCB>, cmp> q) {cout << "名字\t时间\t优先级\t状态\t运行时间\t剩余时间" << endl;while (!q.empty()) {PCB t = q.top();cout << t.name << '\t' << t.time << '\t' << t.priority << '\t'<< t.status << '\t' << t.runtime + 1 << "\t\t" << t.lefttime - 1 << endl;q.pop();}cout << endl;
}// 打印时间片轮转法中的就绪队列
void print_timeturn(queue<PCB> q) {cout << "名字\t时间\t状态\t运行时间\t剩余时间" << endl;while (!q.empty()) {PCB t = q.front();cout << t.name << '\t' << t.time << '\t' << t.status << '\t'<< t.runtime + 1 << "\t\t" << t.lefttime - 1 << endl;q.pop();}cout << endl;
}// 打印完成队列（优先级调度）
void print_finish1(queue<PCB> q) {cout << "完成队列过程如下:" << endl;cout << "名字\t时间\t优先级\t状态\t运行时间\t剩余时间" << endl;while (!q.empty()) {PCB t = q.front();cout << t.name << '\t' << t.time << '\t' << t.priority << '\t'<< t.status << '\t' << t.runtime << "\t\t" << t.lefttime << endl;q.pop();}
}// 打印完成队列（时间片轮转）
void print_finish2(queue<PCB> q) {cout << "完成队列过程如下:" << endl;cout << "名字\t时间\t状态\t运行时间\t剩余时间" << endl;while (!q.empty()) {PCB t = q.front();cout << t.name << '\t' << t.time << '\t' << t.status << '\t'<< t.runtime << "\t\t" << t.lefttime << endl;q.pop();}
}// 执行优先级调度算法
void run_priority() {while (!q1.empty()) {print_priority(q1);PCB t = q1.top();q1.pop();t.lefttime--;t.runtime++;t.status = (t.lefttime == 0) ? 1 : -1;if (t.lefttime <= 0) {q3.push(t);}else {q1.push(t);}}cout << "所有进程均已执行完毕!" << endl << endl;
}// 执行时间片轮转法
void run_timeturn() {while (!q2.empty()) {print_timeturn(q2);PCB t = q2.front();q2.pop();t.lefttime--;t.runtime++;t.status = (t.lefttime == 0) ? 1 : -1;if (t.lefttime <= 0) {q3.push(t);}else {q2.push(t);}}cout << "所有进程均已执行完毕!" << endl << endl;
}// 主函数
int main() {SetConsoleOutputCP(936); // 支持中文输出setConsoleColor(GREEN);cout << "------------------------------" << endl;cout << "--------- 选择调度算法 : 1.优先级法 2.时间片轮转法 ---------" << endl;cout << "------------------------------" << endl;resetConsoleColor();int select;cout << "请输入选择 (1 或 2) : ";cin >> select;cout << "请输入进程个数 (最多10个) : ";cin >> n;cout << endl;if (n <= 0 || n > N) {cout << "进程个数输入错误, 程序退出!" << endl;return 0;}cout << "NOTICE: -1代表就绪, 0代表运行, 1代表完成" << endl << endl;if (select == 1) {init_priority();cout << "就绪队列初始化完成!" << endl;run_priority();print_finish1(q3);}else if (select == 2) {init_timeturn();cout << "就绪队列初始化完成!" << endl;run_timeturn();print_finish2(q3);}else {cout << "无效选择, 程序退出!" << endl;}return 0;
}

解析：

• 1. 全局变量和常量

• const int N = 10;：定义了最大进程数量。

• int n;：用户输入的进程数量。

• struct PCB：进程控制块，包含进程的基本信息。

• priority_queue<PCB, vector<PCB>, cmp> q1;：优先级调度的就绪队列。

• queue<PCB> q2;：时间片轮转的就绪队列。

• queue<PCB> q3;：完成队列，用于存储已完成的进程。

• 2. 优先级队列比较器
• struct cmp：定义了优先级队列的比较规则。优先级高的进程排在前面，如果优先级相同，则等待时间长的进程排在前面。
• 3初始化函数

• init_priority：初始化优先级调度的就绪队列，随机生成进程的优先级和执行时间。

• init_timeturn：初始化时间片轮转的就绪队列，随机生成进程的执行时间。

• print_priority 和 print_timeturn：分别打印优先级调度和时间片轮转的就绪队列。

• print_finish1 和 print_finish2：分别打印优先级调度和时间片轮转的完成队列。

• run_priority：优先级调度算法。每次从优先级队列中取出优先级最高的进程执行，直到所有进程完成。

• run_timeturn：时间片轮转调度算法。每次从队列中取出一个进程执行，执行完成后将其放回队列尾部，直到所有进程完成。

• 提示用户选择调度算法，并输入进程数量。

• 根据用户选择初始化相应的队列，并调用对应的调度算法。

• 最后打印完成队列。

• run_priority：优先级调度算法。每次从优先级队列中取出优先级最高的进程执行，直到所有进程完成。

• run_timeturn：时间片轮转调度算法。每次从队列中取出一个进程执行，执行完成后将其放回队列尾部，直到所有进程完成。

 运行结果：

  

以上是在VS2022中运行的结果。

实验二：

 

我们这个实验的目的就是测试进程的死锁，也就是我们进程之间分配的资源合理的性。

我们要知道一个进程的最大需求，系统已分配，剩余需求，这三个量，保证之间的一个平衡就没问题。所以这就是关键。然后我们还要设计一个检查系统的进程之间的函数，保证我们可以第一时间了解，防止死锁的出现。

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>using namespace std;class Process {
private:int id;vector<int> max;      // 最大资源需求vector<int> allocated; // 已分配资源vector<int> need;      // 需求资源
public:Process(int id, int resourceTypes) {this->id = id;max.resize(resourceTypes);allocated.resize(resourceTypes, 0);need.resize(resourceTypes);// 随机生成最大需求量和初始已分配资源for (int i = 0; i < resourceTypes; ++i) {max[i] = rand() % 20 + 1; // 最大需求在 1 到 20 之间allocated[i] = rand() % (max[i] + 1); // 已分配资源在 0 到 max[i] 之间need[i] = max[i] - allocated[i]; // 需求 = 最大需求 - 已分配资源}}int getId() const { return id; }const vector<int>& getMax() const { return max; }const vector<int>& getAllocated() const { return allocated; }const vector<int>& getNeed() const { return need; }// 资源分配void allocate(const vector<int>& resources) {for (int i = 0; i < resources.size(); ++i) {allocated[i] += resources[i];need[i] -= resources[i];}}// 资源释放void release(const vector<int>& resources) {for (int i = 0; i < resources.size(); ++i) {allocated[i] -= resources[i];need[i] += resources[i];}}
};class ResourceTracker {
private:vector<int> availableResources; // 系统可用资源vector<Process> processes;       // 系统中的进程
public:ResourceTracker(int resourceTypes, int processCount) {// 随机生成可用资源availableResources.resize(resourceTypes);for (int i = 0; i < resourceTypes; ++i) {availableResources[i] = rand() % 20 + 1; // 可用资源在 1 到 20 之间}// 随机生成进程for (int i = 0; i < processCount; ++i) {processes.push_back(Process(i, resourceTypes));}}void addProcess(const Process& process) {processes.push_back(process);}// 检查系统是否处于安全状态bool isSafeState(vector<int>& safeSequence) {vector<bool> finished(processes.size(), false);vector<int> work = availableResources;int count = 0;while (count < processes.size()) {bool found = false;for (size_t i = 0; i < processes.size(); ++i) {if (!finished[i]) {const Process& process = processes[i];bool canAllocate = true;// 检查进程的需求是否小于或等于当前可用资源for (size_t j = 0; j < work.size(); ++j) {if (process.getNeed()[j] > work[j]) {canAllocate = false;break;}}// 如果可以分配资源if (canAllocate) {for (size_t j = 0; j < work.size(); ++j) {work[j] += process.getAllocated()[j];}finished[i] = true;safeSequence.push_back(i);++count;found = true;}}}// 如果没有找到可以分配的进程，说明系统不安全if (!found) {return false;}}return true;}// 请求资源bool requestResources(int processId, const vector<int>& request) {// 检查进程ID是否有效if (processId < 0 || processId >= (int)processes.size()) {cout << "错误: 无效的进程ID。" << endl;return false;}// 检查请求是否超过可用资源或需求资源for (size_t i = 0; i < request.size(); ++i) {if (request[i] > availableResources[i]) {cerr << "错误: 请求的资源超过了可用资源。" << endl;return false;}if (request[i] > processes[processId].getNeed()[i]) {cerr << "错误: 请求的资源超过了进程的需求资源。" << endl;return false;}}// 临时分配资源for (size_t i = 0; i < request.size(); ++i) {availableResources[i] -= request[i];vector<int> tempReq(1, request[i]);processes[processId].allocate(tempReq);}// 检查系统是否仍处于安全状态vector<int> safeSequence;if (isSafeState(safeSequence)) {cout << "资源分配成功。安全序列: ";for (size_t i = 0; i < safeSequence.size(); ++i) {cout << safeSequence[i] << " ";}cout << endl;return true;}else {// 如果不安全，回滚分配for (size_t i = 0; i < request.size(); ++i) {availableResources[i] += request[i];vector<int> tempReq(1, request[i]);processes[processId].release(tempReq);}cerr << "错误: 资源分配会导致系统进入不安全状态，已回滚。" << endl;return false;}}// 释放资源void releaseResources(int processId, const vector<int>& resources) {// 检查进程ID是否有效if (processId < 0 || processId >= (int)processes.size()) {cerr << "错误: 无效的进程ID。" << endl;return;}// 检查释放量是否合法for (size_t i = 0; i < resources.size(); ++i) {if (resources[i] > processes[processId].getAllocated()[i]) {cerr << "错误: 尝试释放的资源超过已分配量。" << endl;return;}}// 执行释放for (size_t i = 0; i < resources.size(); ++i) {availableResources[i] += resources[i];vector<int> tempRes(1, resources[i]);processes[processId].release(tempRes);}cout << "资源释放成功。" << endl;}// 打印系统状态void printSystemState() {cout << "\n当前系统状态:" << endl;cout << "可用资源: ";for (size_t i = 0; i < availableResources.size(); ++i) {cout << availableResources[i] << " ";}cout << endl;cout << "进程状态 (ID | 最大需求 | 已分配 | 需求):" << endl;for (size_t i = 0; i < processes.size(); ++i) {const Process& process = processes[i];cout << "P" << process.getId() << " | ";// 打印最大需求const vector<int>& max = process.getMax();for (size_t j = 0; j < max.size(); ++j) {cout << max[j] << " ";}cout << "| ";// 打印已分配const vector<int>& allocated = process.getAllocated();for (size_t j = 0; j < allocated.size(); ++j) {cout << allocated[j] << " ";}cout << "| ";// 打印需求const vector<int>& need = process.getNeed();for (size_t j = 0; j < need.size(); ++j) {cout << need[j] << " ";}cout << endl;}}
};// 显示菜单
void displayMenu() {cout << "\n----- 资源管理系统 -----" << endl;cout << "1. 检查系统安全性并显示安全序列" << endl;cout << "2. 请求资源" << endl;cout << "3. 释放资源" << endl;cout << "4. 显示系统状态" << endl;cout << "5. 退出" << endl;
}int main() {srand(time(0)); // 设置随机数种子int resourceTypes = 3; // 资源类型数int processCount = 5; // 进程数ResourceTracker manager(resourceTypes, processCount);while (true) {displayMenu();int choice;cout << "请输入您的选择: ";cin >> choice;switch (choice) {case 1: {vector<int> safeSequence;if (manager.isSafeState(safeSequence)) {cout << "系统处于安全状态" << endl;cout << "安全序列: ";for (size_t i = 0; i < safeSequence.size(); ++i) {cout << safeSequence[i] << " ";}cout << endl;}else {cout << "系统处于不安全状态" << endl;}break;}case 2: {int processId;cout << "请输入进程ID (0-" << processCount - 1 << "): ";cin >> processId;vector<int> request(resourceTypes);cout << "请输入请求的资源 (3种类型，用空格分隔): ";for (int i = 0; i < resourceTypes; ++i) {cin >> request[i];}manager.requestResources(processId, request);break;}case 3: {int processId;cout << "请输入进程ID (0-" << processCount - 1 << "): ";cin >> processId;vector<int> release(resourceTypes);cout << "请输入释放的资源 (3种类型，用空格分隔): ";for (int i = 0; i < resourceTypes; ++i) {cin >> release[i];}manager.releaseResources(processId, release);break;}case 4: {manager.printSystemState();break;}case 5:cout << "退出系统..." << endl;return 0;default:cout << "无效的选择，请重新输入。" << endl;}}return 0;
}

代码解析

1. 类设计

• Process 类：

  • 表示一个进程，包含进程的 id、最大资源需求 max、已分配资源 allocated 和需求资源 need。

  • 提供了资源分配和释放的方法。

• ResourceTracker 类：

  • 管理系统中的资源和进程。

  • 提供了检查系统是否处于安全状态、请求资源、释放资源和打印系统状态的方法。

2. 主要功能

• 随机生成资源和进程：

  • ResourceTracker 的构造函数随机生成可用资源和进程的资源需求。

• 检查安全状态：

  • isSafeState 方法通过银行家算法检查系统是否处于安全状态，并返回安全序列。

• 请求资源：

  • requestResources 方法允许进程请求资源，并检查请求是否会导致系统进入不安全状态。

• 释放资源：

  • releaseResources 方法允许进程释放资源。

• 打印系统状态：

  • printSystemState 方法打印当前系统状态，包括可用资源和每个进程的状态。

3. 主函数

• 提供了一个简单的菜单，允许用户选择不同的操作：

  • 检查系统安全性并显示安全序列。

  • 请求资源。

  • 释放资源。

  • 显示系统状态。

  • 退出系统。

我们检查一下系统是否安全，然后就开始分配资源，成功之后还可以清除之前分配的资源，然后还可以检查一下系统的安全。 灵活运用保证自己分配的资源不会造成死锁。

 运行结果：

 

这就是今天的内容：求一个赞；这对我真的很重要。

下期预告：操作系统实验习题 下篇