《操作系统实验》C++实现时间片轮转调度算法

蔚落 2022-10-28 10:14 178阅读 0赞

**提示：**处理机调度算法之先服务算法（FCFS）、短作业优先算法（SJF）和高响应比优先算法（HRRN）详见[C++实现处理机调度算法][C]。

### 时间片轮转调度算法 ###

*  一、 实验内容
 *  二、 实验要求
 *  三、 实验过程
 *   *  1、 设计思想
     *  2、 数据结构
 *  四、 实验代码
 *  五、实验结果

# 一、 实验内容 #

使用时间片轮转算法模拟实现进程调度功能。

# 二、 实验要求 #

1、模拟时间片轮转调度算法；  
2、能输入进程的基本信息，如进程名、到达时间等；  
3、能够显示各调度算法的调度顺序；  
4、能计算完成调度后进程的周转时间、平均周转时间、带权周转时间、平均带权周转时间。

# 三、 实验过程 #

## 1、 设计思想 ##

(1) 用户输入进程的个数和时间片的大小；  
(2) 每个进程用一个pcb表示，包括进程名、到达时间、服务时间、剩余服务时间、完成时间等信息。其中进程名和到达时间由用户输入，服务时间由随机数生成；  
(3) 按照所有进程到达的先后顺序进行排序，建立等待队列；  
(4) 第一个到达的进程首先进入队列，然后让执行结束时间之前到达的进程进入队列，最后若进程执行完毕则从队列中取出记录结束时间，否则放入队列尾部；  
(5) 执行队列首位的进程，让执行结束时间之前到达的进程进入队列，判断队列首位的进程是否能执行完，若进程执行完毕则从队列中取出并记录结束时间，否则放入队列尾部；  
(6) 重复（5）步，直到所有进程执行完毕；  
(7) 计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。

## 2、 数据结构 ##

1、定义一个描述PCB的类pcb：

class pcb {
        
    	friend void sort(std::vector<pcb>&);
    	friend void RR(std::vector<pcb>&, const float&);
    public:
    	pcb() = default;
    	pcb(char a, float b, float c) :name(a), arrival_time(b), service_time(c), remaining_time(c) {
        }
    private:
    	char name;
    	float arrival_time;      //到达时间
    	float service_time;      //服务时间
    	float remaining_time;    //剩余服务时间
    	float finish_time;       //结束时间
    	float t1;                //周转时间
    	float t2;                //带权周转时间
    public:
    	void display() const;    //显示进程信息
    	char read_name() const;  //读取名称
    	bool crt(float rr);      //计算剩余时间
    	void cft(float time);    //计算结束时间
    	float ct1();             //计算周转时间
    	float ct2();             //计算带权周转时间
    };

2、容器`vector<pcb> pcbs(n)`装入所有进程；  
3、容器`vector<char> order`记录进程执行的顺序；  
4、建立双端队列`deque<pcb> queue`装入到达等待的进程；  
5、变量time记录当前的时刻，变量n记录当前还未执行完的进程数量。

# 四、 实验代码 #

1.  头文件 pcb.h

#ifndef PCB_H
    #define PCB_H
    #include<vector>
    class pcb {
        
    	friend void sort(std::vector<pcb>&);
    	friend void RR(std::vector<pcb>&, const float&);
    public:
    	pcb() = default;
    	pcb(char a, float b, float c) :name(a), arrival_time(b), service_time(c), remaining_time(c) {
        }
    private:
    	char name;
    	float arrival_time;      //到达时间
    	float service_time;      //服务时间
    	float remaining_time;    //剩余服务时间
    	float finish_time;       //结束时间
    	float t1;                //周转时间
    	float t2;                //带权周转时间
    public:
    	void display() const;    //显示进程信息
    	char read_name() const;  //读取名称
    	bool crt(float rr);      //计算剩余时间
    	void cft(float time);    //计算结束时间
    	float ct1();             //计算周转时间
    	float ct2();             //计算带权周转时间
    };
    #endif

1.  文件pcb.cpp

#include"pcb.h"
    #include<iostream>
    
    using namespace std;
    
    //显示进程信息
    void pcb::display() const {
        
    	cout << "名称：" << name << "\t"
    		<< "到达时间：" << arrival_time << "\t"
    		<< "服务时间：" << service_time << endl;
    }
    
    //计算剩余时间，时间不足一个时间片返回false，否则返回true
    bool pcb::crt(float rr) {
           
    	if (remaining_time <= rr)
    		return false;
    	else {
        
    		remaining_time -= rr;
    		return true;
    	}
    }
    
    //计算结束时间
    void pcb::cft(float time) {
        
    	finish_time = time;
    }
    
    //计算周转时间
    float pcb::ct1() {
        
    	return finish_time - arrival_time;
    }
    
    //计算带权周转时间
    float pcb::ct2() {
        
    	return (finish_time - arrival_time) / service_time;
    }
    
    //读取进程名
    char pcb::read_name() const {
        
    	return name;
    }

1.  文件exp3.cpp

#include"pcb.h"
    #include<iostream>
    #include<vector>
    #include<deque>
    #include<random>
    #include<ctime>
    
    using namespace std;
    
    //按到达时间排序
    void sort(vector<pcb>& pcbs) {
        
    	int index;
    	int n = pcbs.size();
    	for (int i = 0; i < n; i++) {
        
    		index = i;
    		for (int j = i + 1; j < n; j++) {
        
    			if (pcbs[j].arrival_time < pcbs[i].arrival_time)
    				index = j;
    		}
    		if (index != i){
        
    			pcb temp;
    			temp = pcbs[i];
    			pcbs[i] = pcbs[index];
    			pcbs[index] = temp;
    		}
    	}
    }
    
    void RR(vector<pcb>& pcbs, const float& rr) {
        
    	vector<char> order;  //记录执行顺序
    	deque<pcb> queue;  //双端队列
    	unsigned i = 1;
    	int n = pcbs.size();
    
    	//按到达时间排序
    	sort(pcbs);
    
    	//第一个到达的进程进入队列
    	queue.push_back(pcbs[0]);
    	float time = pcbs[0].arrival_time;
    
    	while (n!=0) {
        
    
    		//计算当前时间
    		if (!queue.empty()) {
        
    			if (queue[0].remaining_time < rr)
    				time += queue[0].remaining_time;
    			else
    				time += rr;
    		}
    		else {
        
    			time = pcbs[i].arrival_time;
    			queue.push_back(pcbs[i]);
    			i++;
    			if (queue[0].remaining_time < rr)
    				time += queue[0].remaining_time;
    			else
    				time += rr;
    		}
    
    			
    		//在进程结束之前到达的新进程进入队列
    		while (i < pcbs.size() && pcbs[i].arrival_time <= time) {
        
    			queue.push_back(pcbs[i]);
    			i++;
    		}
    		
    		order.push_back(queue[0].name);
    
    		//未执行完的进程放入队尾，否则从队列中删除
    		if (queue[0].crt(rr)) {
         
    			pcb t = queue[0];
    			queue.pop_front();
    			queue.push_back(t);
    		}
    		else {
        
    			for (unsigned j = 0; j < pcbs.size(); j++) {
        
    				if (pcbs[j].name == queue[0].name) {
        
    					pcbs[j].cft(time);
    				}
    			}
    			queue.pop_front();
    			n--;
    		}
    	}
    
    	//打印执行顺序
    	cout << "执行顺序：";
    	for (auto i : order)
    		cout << i << ' ';
    	cout << endl;
    }
    
    int main() {
        
    	int n;
    	float rr;
    
    	//输入进程信息并显示
    	cout << "输入进程数目：";
    	cin >> n;
    	vector<pcb> pcbs(n);
    	cout << "\n输入进程名、到达时间" << endl;
    	char name; float at; float st;
    
    	uniform_int_distribution<unsigned> u(1, 5);  //生成1-5间（包含）均匀分布的随机数
    	default_random_engine e(time(0));
    	for (int i = 0; i < n; i++) {
        
    		cin >> name >> at ;
    		st = float(u(e));
    		pcbs[i] = pcb(name, at, st);
    	}
    	for (int i = 0; i < n; i++) {
        
    		pcbs[i].display();
    	}
    
    	//输入时间片大小，执行RR
    	cout << "\n输入时间片大小：";
    	cin >> rr;
    	cout << "\n";
    	RR(pcbs, rr);
    
    	//计算（平均）周转时间、（平均）带权周转时间
    	float sum1 = 0.0, sum2 = 0.0;
    	for (int i = 0; i < n; i++) {
        
    		cout << "编号：" << pcbs[i].read_name() << "\t"
    			<< "周转时间：" << pcbs[i].ct1() << "\t"
    			<< "带权周转时间：" << pcbs[i].ct2() << endl;
    		sum1 += pcbs[i].ct1();
    		sum2 += pcbs[i].ct2();
    	}
    	cout << "平均周转时间：" << sum1 / float(n) << endl;
    	cout << "平均带权周转时间：" << sum2 / float(n) << endl;
    
    	return 0;
    }

# 五、实验结果 #

![实验结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]

[C]: https://blog.csdn.net/weixin_44197749/article/details/112604405
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]: /images/20221024/de6001c9ee354fcf8959e6061cda1119.png