操作系统实验——进程管理的算法实现
前言
笔者在大学下属的事业单位上班,最近去帮着带下操作系统的实验课,这里随手水点参考代码,欢迎各位领导老师莅临指正
实验目标
编写一个简单的进程调度器
实验内容
- 进程控制块(PCB)的定义与管理
- 进程调度算法的实现
- 进程创建、销毁和切换
- 给定一批进程对比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;
}