假设某单处理机系统采用“基于动态优先权的时间片轮转”调度算法。进程队列采用单向链表组织进程控制块。
过程:假设进入的进程有3个,轮转时间片为5,每经过一个时间片要么优先级发生变化(在我的实验中加2,也就是优先级降低两个等级),要么该进程结束(删除节点)。
运行逻辑如下:
初始化:
根据优先级排序:
第一个时间片轮转后:
第二个时间片轮转后:
第三个时间片轮转后:
第四个时间片轮转后:
第五个时间片轮转后所有节点均被删除。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct pcb
{
int name; //进程名
int status; //进程状态
int priority; //进程优先级
int time; //进程所需运行时间
struct pcb *next; //指向下一个节点
}pcb;
int M;
pcb *creat(int count, pcb *head) //count为进程数
{
pcb *q, *p;
head = (pcb *)malloc(sizeof(pcb)); //头指针
p = head;
int i = 0;
for(i = 0; i < count; i++)
{
q = (pcb *)malloc(sizeof(pcb));
printf("input %d process name: ", i+1);
scanf("%d", &q->name);
printf("input %d process priority: ", i+1);
scanf("%d", &q->priority);
printf("input %d process time: ", i+1);
scanf("%d", &q->time);
q->status = 1; //默认进程为就绪态
p->next = q;
p = q;
}
p->next = NULL;
return head;
}
void Sort1(pcb *head)
{
pcb * q, *p, *tail, *temp;
tail = NULL;
q = head;
while((head->next) != tail)
{
p = head->next;
q = head;
while(p->next != tail)
{
if((p->priority) > (p->next->priority)){
q->next = p->next;
temp = p->next->next;
p->next->next = p;
p->next = temp;
p = q->next;
}
p = p->next;
q = q->next;
}
tail = p;
}
}
void Print(pcb *head)
{
pcb *ptr = head->next;
while(ptr != NULL){
printf("name = %d, pro = %d, status = %d, time = %d\n", ptr->name,ptr->priority, ptr->status, ptr->time);
ptr = ptr->next;
}
}
pcb *sch(pcb *head){
pcb * ptr = head->next;
while(ptr != NULL){
//有进程
printf("name = %d, pro = %d, status = %d, time = %d\n", ptr->name, ptr->priority, ptr->status, ptr->time);
ptr->priority = ptr->priority + 2;
ptr->time = ptr->time - M;
if(ptr->time > 0) {
Sort1(head);
} else {
ptr->time = 0;
ptr->status = 0;
head->next = ptr->next; //进程结束,删除
}
printf("list:\n");
Print(head);
printf("\n\n");
ptr = head->next;
}
return head;
}
int main()
{
int num;
pcb *head;
printf("please enter the size of the time slice:");
scanf("%d", &M);
printf("Number of input processes:");
scanf("%d",&num);
head = creat(num, head);
printf("\n");
Print(head);
printf("\n\nstart:\n");
Sort1(head);
sch(head);
return 0;
}
结果: