孤村落日残霞，轻烟老树寒鸦，一点飞鸿影下。
青山绿水，白草红叶黄花。
————《天净沙·秋》 白朴 【元】
目录
今天带来操作系统的两道实验题目的解析
实验一：
这里对于上述的要求进行编译，其中的第一题我们都知道这里的优先级算法（非抢占）和时间片算法是核心。所以我们先来过一遍这两个核心的基础概念。
优先级算法：所有的进程按照优先级的大小来进行排序，然后运行进程（在队列里）。这种算法比较浪费时间，所以有了下面这个算法。
时间片算法：我们首先定义一个大小合适的时间片，不宜大（如果时间片太大，那么就起不到该有的作用）。然后对于再队列里的进程按顺序进行运行（运行的时间就是时间片规定的），将已经运行结束的进程结束，提出队列；对于没有运行结束的进程放在队列的最后，排在之前最后一个的后面，按顺序等待运行。
代码：
#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~69
t.time = (rand() % 20) + 1; // 执行时间范围: 1~20
t.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. 主函数
提供了一个简单的菜单，允许用户选择不同的操作：
检查系统安全性并显示安全序列。
请求资源。
释放资源。
显示系统状态。
退出系统。
我们检查一下系统是否安全，然后就开始分配资源，成功之后还可以清除之前分配的资源，然后还可以检查一下系统的安全。 灵活运用保证自己分配的资源不会造成死锁。
运行结果：
这就是今天的内容：求一个赞；这对我真的很重要。
下期预告：操作系统实验习题 下篇