基于动态优先级的时间片轮调转算法（简单模拟）

实验要求：

模拟操作系统运转，设置时间片轮，进程运行一次，所需运行时间减去时间片轮大小（设为2），优先级减去2，等待系统调用。

相关理论：

时间片轮调度算法中，每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程实现过程。

动态优先级调度算法是指在创建进程之初，先赋予其一个优先级，然后其值随着进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待的时间的正常，使其优先级相应提高。若所有的进程都具有相同的优先级初值，则最先进入就绪队列的进程会因为其优先级变得最高，而优先获得处理机，这相当于FCFS算法。若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。

实现过程：

1、定义结构体

typedef struct pcb
{
    int name;  //进程名
    int status; //进程状态
    int priority; //进程优先级
    int time; //进程所需运行时间
    struct pcb * next;  //指向下一个节点
}pcb;

2、建立头指针

pcb* init_circular_linkedlist(pcb * head)
{

    head = (pcb *)malloc(sizeof(pcb));
    if(head == NULL)
        printf("申请内存空间失败\n");

    head->next = NULL;
    return head;
}

3、创建进程模拟队列

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("输入第%d进程的名字: ", i);
        scanf("%d", &q->name);
        printf("输入第%d进程的优先级: ", i);
        scanf("%d", &q->priority);
        printf("输入第%d进程的运行时间: ", i);
        scanf("%d", &q->time);
        q->status = 1; //默认进程为就绪态
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}

4、链表按优先级排序（priority越小，优先级越高）

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;
   }

}

5、进程调度算法

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);
        if(ptr->priority - 2 >= 0){
            ptr->priority = ptr->priority + 2;
        }else{
            ptr->priority = 0;
        }

        ptr->time = ptr->time - M;
        if(ptr->time >= -1){ //-1：因为时间片大小设为2，某一进程所需时间为1时，运行时间<时间片，将time置0
            if(ptr->time == -1)
                ptr->time = 0;
            Sort1(head);
           ptr = head->next;

        }else{
            ptr->status = 0;
            head->next = ptr->next; //进程结束，删除

        }
        ptr = head->next; //操作系统运行的一直是head->next
    }

    return head;
}

6、打印函数

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;
    }
}

7、主函数

int main(void)
{
    int num;
    pcb * head;
    printf("输入进程个数: ");
    scanf("%d",&num);

    head = creat(num, head);
    printf("没排序打印：\n");
    Print(head);
    Sort1(head);
     printf("打印：\n");
    Print(head);
    printf("\n\n");

    sch(head);

    return 0;
}

结果展示：

基于动态优先级的时间片轮调转算法（简单模拟）

此处显示的time为进程开始时间，优先级为进程开始时。

过程：

后续过程类似（以上优先级和时间显示的是进程当前时间片运行结束后）

基于动态优先级的时间片轮调转算法（简单模拟）

相关推荐