单处理器进程调度算法的模拟

骑猪看日落 2022-06-05 03:10 176阅读 0赞

#include <iostream>
    #include <list>
    #include <ctime>
    #include <vector>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    const int MAX_PROCESS_NUMBER = 15;
    
    
    class Process {
    public:
    	int id;
    	int arrival;//到达时间
    	int CPUtime;//所需执行时间
    	int cost;//已执行时间
    	int state;//状态码（0：就绪态，1：运行态，2：阻塞态，3：完成）
    	int end;//完成时间
    	int during_time;//周转时间
    	double response_ratio;
    	Process() {}
    	void set(int id, int arrival, int cpu, int end=0, int during = 0, int state = 0, double ratio=0, int cost=0) {
    		this->id = id;
    		this->arrival = arrival;
    		CPUtime = cpu;
    		during_time = during;
    		this->end = end;
    		this->state = state;
    		response_ratio = ratio;
    		this->cost = cost;
    	}
    	//用于构造优先队列,这里比较的是优先级，CPUtime越小优先级越高
    	bool operator <(const Process that) const {
    		return (this->CPUtime > that.CPUtime);
    	}
    };
    Process processes[MAX_PROCESS_NUMBER+1];
    
    list<Process> rr;
    //声明函数
    void fcfs_algorithm();
    void rr_algorithm();
    void spn_algorithm();
    void srt_algorithm();
    void hrrn_algorithm();
    //hrrn算法中的比较函数
    struct cmp {
    	bool operator()(Process &a, Process &b)const {
    		return a.during_time / a.CPUtime < b.during_time / b.CPUtime;
    	}
    };
    
    int main() {
    	srand((unsigned)time(NULL));
    	//生成我们模拟的进程，初始化设置到达时间0，2，4，6，8...执行时间2-10；完成时间0，周转时间0，状态就绪态。
    	processes[1].set(1, 0, rand() % 10 + 1);
    	for (int i = 2; i <=MAX_PROCESS_NUMBER; i++) {
    		processes[i].set(i, 2*(i-1), rand() % 9 + 2);
    	}
    
    	for (int i = 1; i <= MAX_PROCESS_NUMBER; i++) {
    		cout << "procedure" << i << " 到达时间 = " << processes[i].arrival << " 所需服务时间 = " << processes[i].CPUtime << endl;
    	}
    	//模拟RR调度
    	rr_algorithm();
    	//模拟SRT最短剩余时间
    	srt_algorithm();
    	//模拟FCFS先来先服务
    	fcfs_algorithm();
    	//模拟SPN
    	spn_algorithm();
    	//模拟HRRN
    	hrrn_algorithm();
    
    	return 0;
    }
    
    void fcfs_algorithm() {
    	int cumulative_time = 0;
    	//总周转时间
    	int during = 0;
    	cout << "FCFS：" << endl;
    	for (int i = 1; i <= MAX_PROCESS_NUMBER; i++) {
    		cumulative_time += processes[i].CPUtime;
    		processes[i].end = cumulative_time;
    		processes[i].during_time = processes[i].end - processes[i].arrival;
    		during += processes[i].during_time;
    		processes[i].response_ratio = (double)processes[i].during_time / processes[i].CPUtime;
    		cout << "process" << i << "  完成时间：" << processes[i].end <<
    			"\t周转时间：" << processes[i].during_time << 
    			"\t响应比：" << processes[i].response_ratio << endl;
    	}
    	cout << "平均周转时间：" << (double)during / MAX_PROCESS_NUMBER<<endl;
    }
    
    void rr_algorithm() {
    	cout << "RR调度算法：" << endl;
    	int cumulative_time = 0;
    	int during = 0;
    	int next = 2;//下一个即将被push的process
    	rr.push_back(processes[1]);
    	list<Process>::iterator it = rr.begin();
    	while (!rr.empty()) {
    		++cumulative_time;
    		if (cumulative_time % 2 == 0 && next <= MAX_PROCESS_NUMBER) {
    			rr.push_back(processes[next++]);
    		}
    		if (++it == rr.end())
    			it = rr.begin();
    		++(it->cost);
    		if (it->CPUtime == it->cost) {	
    			it->end = cumulative_time;
    			it->during_time = it->end - it->arrival;
    			during += it->during_time;
    			it->response_ratio = (double)it->during_time / it->CPUtime;
    			cout << "process" << it->id << "  完成时间：" <<it->end <<
    				"\t周转时间：" << it->during_time <<
    				"\t响应比：" << it->response_ratio << endl;
    			
    			list<Process>::iterator temp = it;
    			if (it != rr.begin())
    				--it;
    			else if(rr.size()>1) {
    				while (++it != rr.end());
    				--it;
    			}
    			temp->cost = 0;
    			rr.erase(temp);
    		}
    	}
    	cout << "平均周转时间：" << (double)during / MAX_PROCESS_NUMBER << endl;
    }
    
    void spn_algorithm() {
    
    	int cumulative_time = 0;
    	//总周转时间
    	int during = 0;
    	Process current;
    	current = processes[1];
    	int next = 2;
    	cout << "SPN：" << endl;
    	priority_queue<Process> spn;
    	while (1) {
    		++cumulative_time;
    		if (cumulative_time % 2 == 0 && next <= MAX_PROCESS_NUMBER) {
    			spn.push(processes[next++]);
    		}
    		current.cost++;
    		if (current.cost == current.CPUtime) {
    			current.end = cumulative_time;
    			current.during_time = current.end - current.arrival;
    			during += current.during_time;
    			current.response_ratio = (double)current.during_time / current.CPUtime;
    			cout << "process" << current.id << "  完成时间：" << current.end <<
    				"\t周转时间：" << current.during_time <<
    				"\t响应比：" << current.response_ratio << endl;
    			current.cost = 0;
    			if (!spn.empty()) {
    				current = spn.top();
    				spn.pop();
    			}
    			else
    				break;
    		}
    	}
    	
    	cout << "平均周转时间：" << (double)during / MAX_PROCESS_NUMBER << endl;
    }
    
    void srt_algorithm() {
    	//这个算法中的process中的cost的用法有点变化，CPUtime的用法也有变化。
    	for (int i = 1; i <= MAX_PROCESS_NUMBER; i++) {
    		processes[i].cost = processes[i].CPUtime;
    	}
    	int cumulative_time = 0;
    	//总周转时间
    	int during = 0;
    	Process current;
    	current = processes[1];
    	current.cost = current.CPUtime;
    	int next = 2;
    	cout << "SRT：" << endl;
    	priority_queue<Process> spn;
    	while (1) {
    		++cumulative_time;
    		if (cumulative_time % 2 == 0 && next <= MAX_PROCESS_NUMBER) {
    			spn.push(processes[next++]);
    		}
    		current.CPUtime--;
    		if (current.CPUtime==0) {
    			current.end = cumulative_time;
    			current.during_time = current.end - current.arrival;
    			during += current.during_time;
    			current.response_ratio = (double)current.during_time / current.cost;
    			cout << "process" << current.id << "  完成时间：" << current.end <<
    				"\t周转时间：" << current.during_time <<
    				"\t响应比：" << current.response_ratio << endl;
    			//current.CPUtime = current.cost;
    			if (!spn.empty()) {
    				current = spn.top();
    				spn.pop();
    			}
    			else
    				break;
    		}
    		if (cumulative_time % 2 == 0 && next <= MAX_PROCESS_NUMBER) {
    			spn.push(current);
    			current = spn.top();
    			spn.pop();
    		}
    	}
    
    	cout << "平均周转时间：" << (double)during / MAX_PROCESS_NUMBER << endl;
    	//这个算法中的process中的cost的用法有点变化，CPUtime的用法也有变化。
    	for (int i = 1; i <= MAX_PROCESS_NUMBER; i++) {
    		processes[i].cost = 0;
    	}
    }
    
    void hrrn_algorithm() {
    	int cumulative_time = 0;
    	//总周转时间
    	int during = 0;
    	Process current;
    	current = processes[1];
    	int next = 2;
    	cout << "HRRN：" << endl;
    
    	priority_queue<Process, vector<Process>, cmp> spn;
    	while (1) {
    		++cumulative_time;
    		if (cumulative_time % 2 == 0 && next <= MAX_PROCESS_NUMBER) {
    			spn.push(processes[next++]);
    		}
    		current.cost++;
    		if (current.cost == current.CPUtime) {
    			current.end = cumulative_time;
    			current.during_time = current.end - current.arrival;
    			during += current.during_time;
    			current.response_ratio = (double)current.during_time / current.CPUtime;
    			cout << "process" << current.id << "  完成时间：" << current.end <<
    				"\t周转时间：" << current.during_time <<
    				"\t响应比：" << current.response_ratio << endl;
    			current.cost = 0;
    			if (!spn.empty()) {
    				vector<Process> temp;
    				while (!spn.empty()) {
    					Process temp1 = spn.top();
    					temp1.during_time = cumulative_time - temp1.arrival;
    					temp.push_back(temp1);
    					spn.pop();
    				}
    				while (!temp.empty()) {
    					spn.push(temp.back());
    					temp.pop_back();
    				}
    				current = spn.top();
    				spn.pop();
    			}
    			else
    				break;
    		}
    	}
    	cout << "平均周转时间：" << (double)during / MAX_PROCESS_NUMBER << endl;
    }