《操作系统实验》C++实现处理机调度算法

r囧r小猫 2023-01-06 11:41 259阅读 0赞

**提示：**本文实现了先来先服务算法（FCFS）、短作业优先算法（SJF）和高响应比优先算法（HRRN）三种处理机调度算法，时间片轮转调度算法详见[C++实现时间片轮转调度算法][C]。

### 处理机调度算法 ###

*  1 实验内容及要求
 *  2 实验环境
 *  3 实验设计
 *   *  3.1 基本思想
     *  3.2 数据结构
 *  4 源代码
 *  5 运行结果

# 1 实验内容及要求 #

1、模拟先来先服务算法（FCFS）、短作业优先算法（SJF）和高响应比优先算法（HRRN）；  
2、能输入进程的基本信息，如进程名、到达时间、服务时间、完成时间等；  
3、能够显示各调度算法的调度顺序；  
4、能计算完成调度后进程的周转时间、平均周转时间、带权周转时间、平均带权周转时间。

# 2 实验环境 #

windows 10,Visual Studio 2019

# 3 实验设计 #

## 3.1 基本思想 ##

Ⅰ 输入进程的个数，调用create()函数记录所有进程的相关信息：进程名、到达时间、服务时间、完成时间；  
Ⅱ 对于每一种算法，分别调用FCFS()、SJF()和HRRN()函数，按照进程的调度顺序进行排序：  
（1）FCFS：按进程到达时间排序即可；  
（2）SJF：首先按进程到达时间排序，再遍历数组，依次计算前一个进程的结束时间，找出在前一个进程结束之前到达的进程，最后找出其中服务时间最短的进程放在后一个；  
（3）HRRN：首先按进程到达时间排序，再遍历数组，依次计算前一个进程的结束时间，找到在前一个进程结束之前到达的进程，最后分别计算它们的响应比，找出其中响应比最高的进程放在后一个。  
Ⅲ 分别计算每个进程的结束时间；  
Ⅳ 调用函数计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。  
![流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]

## 3.2 数据结构 ##

1、定义一个描述每个进程的类work，记录每个进程信息：

class work {
        
    public:
    	char no;            //编号
    	float arrival_time; //到达时间
    	float service_time; //服务时间
    	float finish_time;  //完成时间
    	float t1;           //周转时间
    	float t2;           //带权周转时间
    	float r;            //响应比
    };

2、定义一个描述调度算法的类workspace：  
其中，定义动态数组a，用于记录所有的进程信息，以及相关的算法实现函数。

class workspace {
        
    private:
    	work* a;
    	void exchange(int i, int j);  //交换数组中两个元素
    	void sort(int n);             //按到达时间排序
    	void ct(int n);               //计算（平均）周转时间、（平均）带权周转时间
    public:
    	void create(int n);          //输入进程信息
    	void display(int n);         //显示进程信息
    	void FCFS(int n);            //先入先服务
    	void SJF(int n);             //短作业优先
    	void HRRN(int n);            //高响应比优先
    };

# 4 源代码 #

1.  p.h

#ifndef P_H
    #define P_H
    class work {
        
    	public:
    		char no;              //编号
    		float arrival_time;   //到达时间
    		float service_time;   //服务时间
    		float finish_time;    //完成时间
    		float t1;             //周转时间
    		float t2;             //带权周转时间
    		float r;              //响应比
    };
    
    class workspace {
        
    private:
    	work* a;
    	void exchange(int i, int j);  //交换数组中两个元素
    	void sort(int n);             //按到达时间排序
    	void ct(int n);               //计算（平均）周转时间、（平均）带权周转时间
    public:
    	void create(int n);          //输入进程信息
    	void display(int n);         //显示进程信息
    	void FCFS(int n);            //先入先服务
    	void SJF(int n);             //短作业优先
    	void HRRN(int n);            //高响应比优先
    };
    #endif

1.  p.cpp

#include"p.h"
    #include<iostream>
    
    using namespace std;
    
    //交换数组中两个元素
    void workspace::exchange(int i, int j) {
        
    	work temp;
    	temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    }
    
    //按到达时间排序
    void workspace::sort(int n) {
        
    	int index;
    	for (int i = 0; i < n; i++) {
        
    		index = i;
    		for (int j = i + 1; j < n; j++) {
        
    			if (a[j].arrival_time < a[index].arrival_time)
    				index = j;
    		}
    		if (index == i)
    			continue;
    		else
    			exchange(i, index);
    	}
    }
    
    //计算（平均）周转时间、（平均）带权周转时间
    void workspace::ct(int n) {
        
    	float sum1 = 0, sum2 = 0;
    	for (int i = 0; i < n; i++) {
        
    		a[i].t1 = a[i].finish_time - a[i].arrival_time;
    		a[i].t2 = a[i].t1 / a[i].service_time;
    		sum1 += a[i].t1;
    		sum2 += a[i].t2;
    		cout << "编号：" << a[i].no << "\t"
    			<< "周转时间：" << a[i].t1 << "\t"
    			<< "带权周转时间：" << a[i].t2 << endl;
    	}
    	cout << "平均周转时间：" << sum1 / float(n) << endl;
    	cout << "平均带权周转时间：" << sum2 / float(n) << endl;
    }
    
    //输入进程信息
    void workspace::create(int n) {
        
    	a = new work[n];
    	cout << "输入进程编号、到达时间、服务时间：" << endl;
    	for (int i = 0; i < n; i++) {
        
    		cin >> a[i].no >> a[i].arrival_time >> a[i].service_time;
    	}
    }
    
    //显示进程信息
    void workspace::display(int n) {
        
    	int i = 0;
    	while(i<n) {
        
    		cout << "编号：" << a[i].no << "\t"
    			<< "到达时间：" << a[i].arrival_time << "\t"
    			<< "服务时间：" << a[i].service_time << endl;
    		i++;
    	}
    }
    
    //先入先服务
    void workspace::FCFS(int n) {
        
    	sort(n);
    	//计算结束时间
    	float t = 0;
    	for (int i = 0; i < n; i++) {
        
    		if (i == 0) {
        
    			a[i].finish_time = t + a[i].service_time + a[i].arrival_time;
    			t = a[i].finish_time;
    		}
    		else {
        
    			if (a[i].arrival_time > t)
    				t = a[i].arrival_time;
    			a[i].finish_time = t + a[i].service_time;
    			t += a[i].service_time;
    		}
    	}
    	//显示执行顺序
    	cout << "执行顺序：";
    	for (int i = 0; i < n; i++) {
        
    		cout << a[i].no << " ";
    	}
    	cout << "\n";
    	ct(n);
    }
    
    //短作业优先
    void workspace::SJF(int n) {
        
    	sort(n);
    	float t = 0;
    	unsigned index;
    	for (int i = 0; i < n; i++) {
        
    		//计算前一个进程的结束时间
    		if (i == 0) {
        
    			a[i].finish_time = t + a[i].service_time + a[i].arrival_time;
    			t = a[i].finish_time;
    		}
    		else {
        
    			if (a[i].arrival_time > t)
    				t = a[i].arrival_time;
    			a[i].finish_time = t + a[i].service_time;
    			t += a[i].service_time;
    		}
    		//找到在前一个进程结束之前到达且服务时间最短的进程放在后一个
    		if (i < n - 1) {
        
    			//选出在前一个进程结束前到达的进程
    			int j = i + 1;
    			while (a[j].arrival_time <= a[i].finish_time && j < n - 1) {
        
    				j++;
    			}
    			//筛选出服务时间最短的进程
    			index = i + 1;
    			for (int k = i + 1; k <= j; k++) {
        
    				if (a[index].service_time > a[k].service_time)
    					index = k;
    			}
    			exchange(i + 1, index);
    		}
    	}
    	//显示执行顺序
    	cout << "执行顺序：";
    	for (int i = 0; i < n; i++) {
        
    		cout << a[i].no << " ";
    	}
    	cout << "\n";
    	ct(n);
    }
    
    //高响应比优先
    void workspace::HRRN(int n) {
        
    	sort(n);
    	float t = 0;
    	for (int i = 0; i < n; i++) {
        
    		//计算前一个进程的结束时间
    		if (i == 0) {
        
    			a[i].finish_time = t + a[i].service_time + a[i].arrival_time;
    			t = a[i].finish_time;
    		}
    		else {
        
    			if (a[i].arrival_time > t)
    				t = a[i].arrival_time;
    			a[i].finish_time = t + a[i].service_time;
    			t += a[i].service_time;
    		}
    		//找到在前一个进程结束之前到达且响应比最高的进程放在后一个
    		if (i < n - 1) {
        
    			//选出在前一个进程结束前到达的进程
    			int j = i + 1;
    			while (a[j].arrival_time <= a[i].finish_time && j < n - 1) {
        
    				j++;
    			}
    			//计算响应比
    			for (int k = i + 1; k <= j; k++) {
        
    				a[k].r = (a[i].finish_time - a[k].arrival_time + a[k].service_time) / a[k].service_time;
    			}
    			//筛选出响应比最高的进程
    			unsigned index;
    			index = i + 1;
    			for (int k = i + 1; k <= j; k++) {
        
    				if (a[index].r < a[k].r)
    					index = k;
    			}
    			exchange(i + 1, index);
    		}
    	}
    	//显示执行顺序
    	cout << "执行顺序：";
    	for (int i = 0; i < n; i++) {
        
    		cout << a[i].no << " ";
    	}
    	cout << "\n";
    	ct(n);
    }

1.  exp2.cpp

#include"p.h"
    #include<iostream>
    
    using namespace std;
    
    int main() {
        
    	int n;
    	cout << "输入进程数目：";
    	cin >> n;
    	workspace w;
    	w.create(n);
    	w.display(n);
    	cout << "\n【一】先入先服务算法" << endl;
    	w.FCFS(n);
    	cout << "\n【二】短作业优先算法" << endl;
    	w.SJF(n);
    	cout << "\n【三】高响应比优先算法" << endl;
    	w.HRRN(n);
    }

# 5 运行结果 #

![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70 1]

[C]: https://blog.csdn.net/weixin_44197749/article/details/113704680
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]: /images/20221119/c54e82203da54ee8a3174f63d417351f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/4cba2e38697e48a69727a646d0b41bc7.png