操作系统进程调度的基本算法，时间片轮转。
假设cpu只有单核，但是进程很多，最简单就是先来先服务，但是会造成后来的进程等待很久，所以有另一种策略就是每个进程都服务一会，这样就不会出现一个进程长时间得不到服务的情况 (饿死现象),在轮流服务一会的方式中，由于cpu一般速度较快，所以我们可能会产生一种错觉就是有多个cpu在给我们服务，我们的多个进程好像都收到反馈了
输入即将到达的进程数还有进程的信息,时间片大小,初始化pcb， 设时间为0
创建3条队列(就绪,未到达,完成) ,各进程按到达时间排序， 入未到达队列
外循环(以是否有进程还没执行好为条件)
{ 内循环(当前时间未到达队列是否有进程到达了 为条件)
{ 送入就绪队列
}
if(就绪队列空)
{ 时间加一，后面不用执行
}
else
{ 就绪队列取进程，状态改’run’
时间片循环(时间片未用完 为条件)
{ 时间加一
循环(当前时间未到达队列是有进程到达)
{ 送入就绪队列
}
if(剩余服务时间==0)
{ 进程状态’finish’
完成时间就是当前时间
插入完成队列
跳出时间片循环
}
}
if(进程状态’run’)
{ 进程状态’wait’
插入就绪队列
}
}
}
打印结果
示例代码如下
#define time_slice 3 //时间片长度
#define N 5 //进程数
#include<iostream>
#include <queue>
using namespace std;
struct pcb
{
char process_name[10]; //进程名字
int arrive_time; //到达时间
int service_time; //需要服务时间
int remain_time; //还差多少时间
int complete_time; //完成时间
char state; //进程状态
}PCB[N + 1]; //0号单元不存数据,直接用作交换
queue<pcb> Wait_queue; //就绪队列
queue<pcb> Coming_queue; //还未到达
queue<pcb> Finish_queue; //已完成
void sort(int n) //按到达时间升序
{
int i, j;
for (i = 1; i < n; i++)
{
for (j = 1; j <= n - i; j++)
{
if (PCB[j].arrive_time > PCB[j + 1].arrive_time)
{
PCB[0] = PCB[j];
PCB[j] = PCB[j + 1];
PCB[j + 1] = PCB[0];
}
}
}
}
int rr(int n)
{
int i, time = 0, t;
cout << "\n请输入各进程的信息\n" << endl;
for (i = 1; i <= n; i++) //输入各进程信息,插入未到达队列
{
PCB[i].state = 'w';
cout << "------\n请输入第" << i << "进程名字: ";
cin >> PCB[i].process_name;
cout << "请输入到达时间: ";
cin >> PCB[i].arrive_time;
cout << "请输入服务时间: ";
cin >> PCB[i].service_time;
PCB[i].remain_time = PCB[i].service_time;
}
sort(n);
for (i = 1; i <= n; i++)
{
Coming_queue.push(PCB[i]);
}
i = 1;
// 进程还有未执行完毕
while (Coming_queue.empty() == false || Wait_queue.empty() == false)
{
while (Coming_queue.empty() == false && time >= Coming_queue.front().arrive_time) //有进程到达
{
Wait_queue.push(Coming_queue.front()); //从未到达队列 放到就绪队列
Coming_queue.pop();
}
if(Wait_queue.empty() == true) //就绪队列空,时间加1，本次不运行进程
{
time++;
continue;
}
else //就绪队列非空
{
cout << "\n第" << i << "次调度执行进程：" << Wait_queue.front().process_name
<< "\t 时间: " << time << endl;
t = time_slice; //t等于时间片
PCB[0] = Wait_queue.front(); //取出就绪队列头
Wait_queue.pop();
PCB[0].state = 'r'; //状态正在运行
while (t-- > 0)
{
time++;
while (Coming_queue.empty() == false && time >= Coming_queue.front().arrive_time) //有进程到达
{
Wait_queue.push(Coming_queue.front()); //插入就绪队列
Coming_queue.pop();
}
if (--PCB[0].remain_time == 0) //剩余服务时间-1，结果已经为0
{
PCB[0].state = 'f'; //进程完成
PCB[0].complete_time = time; //完成时间就是当前时间
Finish_queue.push(PCB[0]); //插入完成队列
break;
}
}
if (PCB[0].state == 'r') //时间片结束还没执行完
{
PCB[0].state = 'w'; //回到就绪队列
Wait_queue.push(PCB[0]);
}
}
i++;
}
return 0;
}
void print()
{
int i = 0;
float round_time[N], //周转时间
force_round_time[N], //带权周转时间
sum = 0; //存放各进程的带权周转时间和
cout << "\n 进程 |" << "到达时间 |" << " 服务时间 |" << " 完成时间 |" << " 周转时间 |" << " 带权周转时间" << endl;
while (Finish_queue.empty() == false)
{
round_time[i] = Finish_queue.front().complete_time - Finish_queue.front().arrive_time;
force_round_time[i] = round_time[i] / Finish_queue.front().service_time;
cout << Finish_queue.front().process_name
<< "\t| " << Finish_queue.front().arrive_time
<< "\t | " << Finish_queue.front().service_time << " \t | " << Finish_queue.front().complete_time
<< "\t | " << round_time[i]
<< "\t | " << force_round_time[i]
<< endl;
Finish_queue.pop();
sum += force_round_time[i];
i++;
}
cout << "\n\n系统平均带权周转时间: " << (sum / i) << endl;
}
int main()
{
cout << "\t\t时间片轮转调度算法" << endl;
rr(N);
print();
return 0;
}
文章出处登录后可见！
已经登录？立即刷新
