基于优先级的时间片轮转调度算法（C语言实现）

立即下载用AI写一个

发布时间：2019-05-04

15人 | 浏览：7383次 | 收藏 |

技术：C + 数据结构

运行环境：gcc + make + Linux

概述

操作系统调度实验

详细

# 基于优先级的时间片轮转调度算法

###1. PCB结构（Block）

![pcb](/contentImages/image/jianshu/13373683-6513891de67a304a.png)

由此定义如下结构体：

```
typedef struct Block
{
	int processID; // 进程号
	int priority; // 优先级
	int status; // 状态
	double arrivalTime; // 到达时间
	double serviceTime; // 服务时间
	double runTime; // 已运行时间

struct Block *next; // Next Block
} Block;
```

###2. 数据结构（队列）

![队列![流程图.png](/contentImages/image/jianshu/13373683-fc06e9117b622d3e.png)
](/contentImages/image/jianshu/13373683-ad1ac427688c2f40.png)

```
typedef struct Link
{
	struct Block *first;  // 指向队头
	struct Block *last;   // 指向队尾
} Link;
```

队列操作函数：

- initLink：初始化队列

```
void initLink(Link *l)
{
	// 分配空间并检测是否成功
	l->first = l->last = (Block *)malloc(sizeof(Block));
	if (!l->first)
	{
		fprintf(stderr, "Malloc Error!\n");
		exit(-1);
	}

// 空队列
	l->first->next = NULL;
	l->last->next = NULL;
}

```

- isEmpty：判断队列是否为空

```
int isEmpty(Link *l)
{
	return l->first->next == NULL? 1: 0;
}
```

- printLInk：输出队列中所有元素的信息

```
void printLink(Link *l)
{
	Block *p = l->first->next;

// 遍历队列并输出
	printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
	while (p != NULL)
	{
		printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
			p->processID, p->priority, p->arrivalTime, \
			p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
		p = p->next;
	}
}
```

- removeFirst：将队列中第一个元素中的数据复制到给定参数中（用于返回），并删除

```
void removeFirst(Link *l, Block *b)
{
	Block *t;

// 空队列则直接返回
	if (isEmpty(l))
	{
		return ;
	}

// t指向第二个Block，用于之后将队列接上
	t = l->first->next->next;
	// 将第一个Block中的内容复制到b中，用于返回
	b->processID = l->first->next->processID;
	b->priority = l->first->next->priority;
	b->arrivalTime = l->first->next->arrivalTime;
	b->serviceTime = l->first->next->serviceTime;
	b->runTime = l->first->next->runTime;
	b->status = l->first->next->status;
	// 释放第一个Block，并把队列接上
	free (l->first->next);
	l->first->next = t;
}
```

- append：将新的元素添加到队尾

```
void append(Link *l, Block *b)
{
	Block *t;

// 分配空间，并检测是否成功
	t = (Block *)malloc(sizeof(Block));
	if (t == NULL)
	{
		fprintf(stderr, "Malloc Error!\n");
		exit(-1);
	}

// 将b中的内容复制到t中
	t->processID = b->processID;
	t->priority = b->priority;
	t->arrivalTime = b->arrivalTime;
	t->serviceTime = b->serviceTime;
	t->runTime = b->runTime;
	t->status = b->status;
	// 将t接到队尾
	t->next = NULL;
	l->last->next = t;
	l->last = t;
}
```

- deleteLinkItem：删除队列中指定的元素

```
void deleteLinkItem(Link *l, Block *target)
{
	Block *p, *t;

// 遍历队列，寻找目标Block
	p = l->first;
	while (p != NULL && p != target)
	{
		t = p;
		p = p->next;
	}

// 若存在，则释放
	if (p != NULL)
	{
		t->next = p->next;
		free(p);
	}
}

```

- sortByArrivalTime：根据进程到达时间将队列排序（从小到大）

```
void sortByArrivalTime(Link *l, int order)
{
	Block *p, *q, *tp, *tq;
	Block *temp, *min, *tmin;
	int minArrivalTime;

// 这里使用了选择排序
	tp = tq = l->first;
	p = q = l->first->next;
	while (p != NULL)
	{
		// 这个数字可以修改的大一点。。。
		minArrivalTime = 9999;
		while (q != NULL)
		{
			// 寻找最小到达时间的Block
			if (q->arrivalTime < minArrivalTime)
			{
				minArrivalTime = q->arrivalTime;
				tmin = tq;
				min = q;
			}

tq = q;
			q = q->next;
		}

// 若寻找的Block与当前Block不是同一个则交换
		if (p != min)
		{
			tp->next = min;
			tmin->next = p;
			temp = min->next;
			min->next = p->next;
			p->next = temp;
		}

tp = tq = p;
		p = q = p->next;
	}
}
```

###3. 基于优先级的时间片轮转调度算法

- 流程图

![流程图](/contentImages/image/jianshu/13373683-2fe7f272fc060e3f.png)

- 算法

```
void RR(Link *l, Link *r)
{
	Block *p, *t;
	double maxPriority;
	double currentTime = 0;
	int selected, timeSlice;

// 种下随机种子
	srand((unsigned)time(NULL));

// 遍历队列
	t = p = l->first->next;
	while (p != NULL)
	{
		// 输出在当前时间已到达的进程Block信息
		printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
		selected = 0;
		maxPriority = 9999;
		while (p != NULL && currentTime >= p->arrivalTime)
		{
			selected = 1;
			printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
				p->processID, p->priority, p->arrivalTime, \
				p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
			// 寻找优先级最高的进程
			if (p->priority < maxPriority)
			{
				maxPriority = p->priority;
				t = p;
			}
			p = p->next;
		}

// 生成随机时间片
		timeSlice = rand() % 10;
		if (selected)
		{
			// 运行进程（模拟）
			printf("Current time: %.0lf, Selected process: %d\n", currentTime, t->processID);
			t->runTime += timeSlice;
			t->priority += 2;
			// 若进程已经结束，则将该进程添加到完成队列，并从当前队列中删除
			if (t->runTime >= t->serviceTime)
			{
				t->status = 1;
				currentTime += t->serviceTime - (t->runTime - timeSlice);
				t->runTime = t->serviceTime;
				append(r, t);
				deleteLinkItem(l, t);
			}
		}
		else
		{
			currentTime += timeSlice;
		}
		// 打印完成队列
		printLink(r);

t = p = l->first->next;
	}
}
```

###4. 测试与结果

- 测试数据

![测试数据](/contentImages/image/jianshu/13373683-afd32ad937a4c740.png)

- 测试结果

![1](/contentImages/image/jianshu/13373683-8c11fb7ec9847d65.png)

![2](/contentImages/image/jianshu/13373683-742e9b3dccea8e38.png)

![3](/contentImages/image/jianshu/13373683-aec320f7a9356d95.png)

![4](/contentImages/image/jianshu/13373683-212f86e6a359fc1c.png)

![5](/contentImages/image/jianshu/13373683-76578780f0880199.png)

###5.项目结构图
> 项目结构图
![](/contentImages/image/20190504/vU6zZtROdyxiS25Smv9.jpg)

本实例支付的费用只是购买源码的费用，如有疑问欢迎在文末留言交流，如需作者在线代码指导、定制等，在作者开启付费服务后，可以点击“购买服务”进行实时联系，请知悉，谢谢

感谢

手机上随时阅读、收藏该文章？请扫下方二维码

基于优先级的时间片轮转调度算法（C语言实现）

概述

详细

相似例子推荐

评论

作者

评分详细

作者例子