C++ 实现先来先服务 (FCFS) 进程调度算法

本文通过 C++ 代码演示了先来先服务 (FCFS) 进程调度算法，并详细解释了周转时间和带权周转时间的计算方法。

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <Windows.h>
//#include<bits/stdc++.h>
using namespace std;

struct process{      //进程结构体 
	 int pid;         //进程id 
	 int ArrivalTime; //到达时间 
	 int ServiceTime; //服务时间 
	 int FinishTime;  //完成时间 
};

const int N=100;     //最大进程数 
process p[N];         
int n;               //进程数 

void input();    //输入数据函数 
void display();  //输出数据函数 
void FCFS();     //先来先服务算法 
bool cmp1(process p1,process p2);   //比较函数1，实现按进程到达时间升序排序 
bool cmp2(process p1,process p2);   //比较函数2，实现按进程编号升序排序 

int main(){
	input();
	FCFS();
	display();
	return 0;
}

void input(){   //输入进程数，每个进程的到达时间和服务时间 
	cout<<"请输入进程个数n:";
	cin>>n;
	cout<<"请分别输入每个进程的到达时间和服务时间："<<endl;
	for (int i=0;i<n;i++){
		cin>>p[i].ArrivalTime>>p[i].ServiceTime;
		p[i].pid = i+1;
	}
}

void display(){
	sort(p,p+n,cmp2);
	cout<<"******************************************************"<<endl;
	cout<<"进程相关信息如下："<<endl;
	cout<<setw(10)<<"进程名（ID）"<<" ";  //setw(10)设置输出宽度 
	cout<<setw(10)<<"到达时间"<<" ";
	cout<<setw(10)<<"服务时间"<<" ";
	cout<<setw(10)<<"完成时间"<<" ";
	cout<<setw(10)<<"周转时间"<<" ";
	cout<<setw(10)<<"带权周转时间"<<endl;
	for (int i = 0;i<n;i++){
		cout<<setw(10)<<p[i].pid<<" ";
		cout<<setw(10)<<p[i].ArrivalTime<<" ";
		cout<<setw(10)<<p[i].ServiceTime<<" ";
		cout<<setw(10)<<p[i].FinishTime<<" ";
		cout<<setw(10)<<p[i].FinishTime-p[i].ArrivalTime<<" ";
		cout<<setw(10)<<(p[i].FinishTime-p[i].ArrivalTime)*1.0/p[i].ServiceTime<<" "<<endl;
	}
}

void FCFS(){
	sort(p,p+n,cmp1);    
	int startTime=0;
	for(int i=0;i<n;i++){
		startTime = max(p[i].ArrivalTime,p[i-1].FinishTime);
		p[i].FinishTime = startTime + p[i].ServiceTime;
	}
}

bool cmp1(process p1,process p2){
	return p1.ArrivalTime < p2.ArrivalTime;   //按到达时间升序排序 
}

bool cmp2(process p1,process p2){
	return p1.pid < p2.pid;   //按进程id升序排序 
}

代码解释

结构体定义: process 结构体用于存储每个进程的信息，包含进程 ID (pid)，到达时间 (ArrivalTime)，服务时间 (ServiceTime) 和完成时间 (FinishTime)。
输入函数 input():
- 输入进程数量 n。
- 循环输入每个进程的到达时间和服务时间，并为每个进程分配唯一的 ID。
输出函数 display():
- 使用 sort 函数按照进程 ID 升序排列进程。
- 输出每个进程的详细信息，包括进程 ID、到达时间、服务时间、完成时间、周转时间和带权周转时间。
FCFS 算法 FCFS():
- 使用 sort 函数按照到达时间升序排列进程。
- 循环遍历每个进程：
  - 计算进程开始时间 startTime，取该进程到达时间和上一个进程完成时间中的较大值。
  - 计算进程完成时间 FinishTime，等于开始时间加上服务时间。
周转时间和带权周转时间:
- 在 display() 函数中，p[i].FinishTime-p[i].ArrivalTime 用于计算周转时间，即进程从到达系统到完成的总时间。
- (p[i].FinishTime-p[i].ArrivalTime)*1.0/p[i].ServiceTime 用于计算带权周转时间，即周转时间与服务时间的比值，反映了进程等待时间的比例。

运行结果

例如，输入 4 个进程，其到达时间和服务时间分别为：

程序输出结果如下：

******************************************************
进程相关信息如下：
进程名（ID） 到达时间 服务时间 完成时间 周转时间 带权周转时间
          1          0          3          3          3          1.000000 
          2          2          1          4          2          2.000000 
          3          4          2          6          2          1.000000 
          4          5          5         11          6          1.200000

小结

通过本文的介绍，您已经了解了如何使用 C++ 实现先来先服务 (FCFS) 进程调度算法，并学会了计算周转时间和带权周转时间。FCFS 算法简单易懂，但存在一些缺点，例如可能会造成短进程等待较长时间，导致系统效率降低。在实际应用中，往往需要使用更复杂的调度算法来提高系统效率。