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升序排序 
}

算法原理

FCFS 算法是一种简单的进程调度算法，其基本思想是按照进程到达时间的顺序进行调度。即先到达的进程先执行，后到达的进程后执行。

代码详解

数据结构定义:

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

该结构体定义了进程的基本信息，包括进程 ID、到达时间、服务时间和完成时间。

输入函数 input():

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;
	}
}

该函数用于从用户输入进程数和每个进程的到达时间、服务时间。

排序函数 cmp1() 和 cmp2():

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

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

cmp1 函数用于根据到达时间进行升序排序，cmp2 函数用于根据进程 ID 进行升序排序。

FCFS 算法函数 FCFS():

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;
	}
}

该函数实现 FCFS 算法：

首先，根据 cmp1 函数对进程进行按到达时间升序排序。
然后，遍历每个进程，计算每个进程的完成时间。完成时间等于该进程到达时间和前一个进程完成时间的最大值加上该进程的服务时间。

输出函数 display():

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;
	}
}

该函数用于将进程的调度结果输出到控制台，包括进程 ID、到达时间、服务时间、完成时间、周转时间和带权周转时间。

程序变量解释

process 结构体: 表示进程，包含进程 id、到达时间、服务时间和完成时间等信息。
n: 表示进程数。
startTime: 表示当前进程开始执行的时间。

总结

本文详细讲解了 C++ 实现先来先服务 (FCFS) 进程调度算法的步骤，并对代码进行了详细的注释。通过阅读本文，读者可以了解 FCFS 算法的原理，并学习如何使用 C++ 代码实现该算法。