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

本文使用 C++ 代码实现先来先服务 (FCFS) 进程调度算法，并解释了算法的核心逻辑。代码包含进程结构体定义、输入数据函数、输出数据函数、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升序排序 
}

代码解释

代码60行用于计算进程的开始时间，为什么要取到第i个进程达时间和第i-1个进程完成时间中的较大值？

这是因为在先来先服务调度算法中，进程的调度顺序是按照它们的到达时间确定的，但是如果当前进程的到达时间在前一个进程的完成时间之后，那么它就无法立即开始执行，而需要等待前一个进程完成后才能开始执行。因此，我们需要取到第i个进程达时间和第i-1个进程完成时间中的较大值作为当前进程的开始时间，以确保它不会在前一个进程没有完成之前开始执行。

希望本文能够帮助您更好地理解先来先服务进程调度算法。