一、实验目的

通过一个简单的进程调度模拟程序的实现，加深对各种进程调度算法，进程切换的理解。

二、实验内容

1、进程调度算法：采用动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。

2、每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：

进程名----进程标示数ID；

优先数----Priority，优先数越大优先权越高；

到达时间----进程的到达时间为进程输入的时间；

进程还需要运行时间----AllTime，进程运行完毕AllTime =0；

已用CPU时间----CPUTime；

进程的阻塞时间StartBlock----表示当进程在运行StartBlock个时间片后，进程将进入阻塞状态；

进程的阻塞时间StartTime----表示当进程阻塞StartTime个时间片后，进程将进入就绪状态；

进程状态----State；

队列指针----Next，用来将PCB排成队列。

3、调度原则

进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间；

进程的运行时间以时间片为单位进行计算；

进程在就绪队列中带一个时间片，优先数加1；

每个进程的状态可以是就绪R（Ready）、运行R（Run）、阻塞B(Block)、或完成F（Finish）四种状态之一；

就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示；

如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减3，然后把它插入就绪队列等待CPU；

每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查；

重复以上过程，直到所要进程都完成为止。

三、程序代码及运行情况

Ⅰ:函数实现：

创建进程PCB：PCB* CreateProcess(PCB *H,int num)

将进程队列排序：PCB* Ready(PCB *H)

将q结点插入进程队列H：void Insert(PCB *H,PCB *q)

输出正在运行的进程：void Disp1(PCB *H)

输出就绪队列中的进程 ：void Disp2(PCB *H)

进程调度实现PCB* Dispatch(PCB *H)

Ⅱ:主要功能的实现过程:

1.构建进程控制块PCB的数据结构：

根据实验要求构建进程的PCB信息，构建数据结构，分析可知进程名ID、优先数Priority、到达时间Get Time、进程还需要运行时间AllTIme、已用CPU时间CUPTime、进程阻塞时间StartBlock、StartTime、都可用int类型来表示，进程状态选择使用字符指针char *State实现字符串来表示，队列指针使用数据结构本身的指针Struct pcb *Next来表示，具体实现的代码截图如下：

2.创建进程队列：

使用带头结点的链表构建进程队列，根据用户输入的进程数创建多个进程，用户输入进程的ID、优先数以及运行时间，并且询问是否要有阻塞，有输入，没有则默认等于-1（使默认值小于零便于控制），将到达时间和CPU使用时间赋值为0，进程状态赋值为就绪，具体代码截图如下：

3.将进程队列按优先数从大到小排序（使用带头结点的链表交换节点实现冒泡排序）：

创建两个PCB指针变量head和rear分别指向进程队列的第一个元素结点和最后有个元素结点，使用head指针来比较head当前结点的优先数和head后一个结点的优先数大小，每一轮比较都将优先数最小的结点放到链表的最后，多轮循环实现将进程队列按优先数从大到小排序，并返回进程队列的头结点，具体代码截图如下：

4.进程调度的实现过程：

其中包含两个带头结点的链表表示的队列分别为就绪队列和阻塞队列，首先创建就绪队列ready和阻塞队列block，创建一个后期循环调度需要用到的中间进程队列end，首先循环遍历进程队列中各个进程结点，将进程状态为就绪的进程结点插入就绪队列中，将进程状态为阻塞的进程结点插入阻塞队列中。这两个队列总共分为三种情况

1）两个队列均为空，所以不需要任何操作，直接返回。

2）就绪队列不为空，而阻塞队列空或者不空都可过程如下：

将插入完毕的就绪队列按优先数大小进行排序，根据实验要求输出正在运行的进程后该进程的优先数减3，进程CPU使用时间加1，进程还需要运行时间减1，startblock减1。首先判断startblock是否为0，为零将进程状态设为阻塞，其次如果startblock不等于0而运行时间等于0，那么将该进程的进程状态改为完成，如果都不是上述两种状态，那么将进程的进程状态改为运行。之后输出ready的第一个进程，也就是正在运行的进程，然后遍历就绪进程队列，如果状态使就绪那么优先数加1，如果不是就绪状态而是运行状态那么就将状态改成就绪（不加1），当然如果使完成不需要任何操作，然后将ready进程队列插入end队列。遍历block进程队列，starttime减1，如果starttime等于0，那么将进程状态从阻塞改为就绪，并且将每一进程插入到end队列里。

3）就绪队列为空，阻塞队列为空，只进行如下：

遍历block进程队列，starttime减1，如果starttime等于0，那么将进程状态从阻塞改为就绪，并且将每一进程插入到end队列里。

最后返回end 在下一次的将队列分为就绪和阻塞队列里，状态为完成的进程使不会插入的，如此反复直至进程队列为空程序终止。

进程调度的代码截图如下：

Ⅲ运行结果：

输入：

输入进程数为3，第一个进程的进程ID为1，优先数为3，需要运行的时间为4，时间2之后进入阻塞，阻塞时间为2，第二个进程进程ID为2，优先数为1，需要运行的时间为3，

第三个进程ID为3，优先数为2，需要运行时间为2。

输出：

第一次运行所有进程的状态都是就绪，其中优先级最高的进程1，先运行，优先级减3变成0，运行时间减1变成3，已用时间加1变成1，开始阻塞时间减1变成1，阻塞时间不变，状态为运行，其他两个进程优先数均加1。

第二次运行，由于进程1在第一次运行减3，已经变得很小，测个进程3的优先级最大，先运行，变化如一所示，唯一不同就是进程3没有阻塞过程，只少了这一个过程，其他过程均相同。

第四次运行进程1的startblock时间已为0，进程状态变为阻塞，结果还需要在下一次运行才能看出来。

第五次运行就进程1而言，在上一次运行进入阻塞，此次运行进程1没有运行也没有在就绪队列里，它进入了阻塞队列，如果在他阻塞时间2耗尽后，也就是第七次运行，如果进程1出现在运行或者就绪队列里，证明进程阻塞是没有问题的。当然就进程3而言，运行时间耗尽，状态变成完成，结果要在下一次运行中才能看出。

第六次运行进程3，已经不在运行或者就绪队列里了，也没有进行阻塞，所以进程3被释放，保证了进程运行时间耗尽进程释放的功能。

第七次运行，此刻进程2的情况和第五次运行的进程3的情况相同，就不做过多描述，重要的是进程1在耗尽阻塞时间2之后，回到了就绪队列中，证明阻塞的成功实现。

第八次第九次运行结果都是进程1 运行了2个时间，不做描述。

第十次程序中进程都完成已无进程。

四、实验过程中出现的问题及解决方法

1.在实现将进程队列按优先数由大到小排序时节点交换的指针不清晰导致无法实现对进程队列的排序；通过画图对指针移动过程的调试解决了此问题。

2.进程调度函数中将进程队列插入就绪队列和阻塞队列时因为没有构建相应的头结点导致无法插入；创建相应的就绪队列和阻塞队列的头节点解决了此问题。

3.在无阻塞情况下完成后，将阻塞机制加入时，与原有程序有许多冲突：通过将就绪和阻塞队列分情况，解决了此次问题，还有就是阻塞的加入我刚觉有点像是信号量，一个加锁，一个解锁。

附录

实验完整源代码：

#include <stdio.h>
 
#include <stdlib.h>
 
#include <String.h>
 
#include <stdbool.h>
 
typedef struct pcb{
 
    int ID;     //进程名，进程标示数ID
 
    int Priority;   //优先数，优先数越大优先级越高
 
    int GetTime;    //到达时间，为进程输入时间
 
    int AllTime;    //进程还需运行时间，进程运行完毕AllTime=0
 
    int CPUTime;    //已用CPU时间
 
    int StartBlock;     //进程运行StartBlock时间片后进入阻塞状态
 
    int StartTime;      //进程阻塞StartTime时间片后进入就绪状态
 
    char *State;      //进程状态
 
    struct pcb *Next;   //队列指针
 
}PCB;
 
 
 
PCB* CreateProcess(PCB *H,int num){
    PCB *q,*r;
 
    int a;
 
    H=(PCB *)malloc(sizeof(PCB));
 
    H->Next=NULL;
 
    r=H;
 
    for(int i=0;i<num;i++){
 
        q=(PCB *)malloc(sizeof(PCB));
 
        printf("请输入第%d个进程信息:\n",i+1);
 
        printf("请输入个进程ID:");
 
        scanf("%d",&q->ID);
 
        printf("请输入进程优先数:");
 
        scanf("%d",&q->Priority);
 
        printf("请输入进程运行时间:");
 
        scanf("%d",&q->AllTime);
 
        printf("是否有阻塞是输入1否输入0：");
 
        scanf("%d",&a);
 
        if(a==1){
 
        printf("请输入StartBlock的值:");
 
        scanf("%d",&q->StartBlock);
 
        printf("请输入StartTime的值:");
 
       scanf("%d",&q->StartTime);
 
}
 
else{
 
q->StartBlock=-1;
 
q->StartTime=-1;
 
}
 
        q->GetTime=0;
 
        q->CPUTime=0;
 
        q->State="就绪";
 
        r->Next=q;
 
        r=q;
 
        printf("------------------------------\n");
 
    }
 
    r->Next=NULL;
 
    return H;
 
}
 
PCB* Ready(PCB *H){
    PCB *head,*rear,*s,*t;
 
    head=H->Next;
 
    if(head==NULL){
 
        return 0;
 
    }
 
    rear=H;
 
    while(rear->Next!=NULL){
 
        rear=rear->Next;
 
    }
 
    while(rear!=H->Next) {
 
        s=H;
 
        while (head != rear) {                    
 
            if (head->Priority < head->Next->Priority) {
 
                if(head->Next!=rear){
 
                    t=head->Next;
 
                    s->Next=t;
 
                    head->Next=t->Next;
 
                    t->Next=head;
 
                    head=t;
 
                } else{
 
                    t=head->Next;
 
                    s->Next=t;
 
                    head->Next=t->Next;
 
                    t->Next=head;
 
                    head=t;
 
                    rear=t->Next;
 
                }
 
            }
 
            if(head->Next==rear){
 
                rear=head;
 
                break;
 
            }
 
            s=s->Next;
 
            head = head->Next;
 
        }
 
        head=H->Next;
 
    }
 
    return H;
 
}
 
void Insert(PCB *H,PCB *q){
 
    PCB *p,*s;
 
    p=H;
 
    while(p->Next!=NULL){
 
        p=p->Next;
 
    }
 
    s=(PCB *)malloc(sizeof(PCB));
 
    s->ID=q->ID;
 
    s->State=q->State;
 
    s->StartTime=q->StartTime;
 
    s->StartBlock=q->StartBlock;
 
    s->CPUTime=q->CPUTime;
 
    s->AllTime=q->AllTime;
 
    s->GetTime=q->GetTime;
 
    s->Priority=q->Priority;
 
    s->Next=NULL;
 
    p->Next=s;
 
}
 
 
 
void Disp1(PCB *H){
 
    if(H->Next==NULL){
 
        printf("没有正在运行的进程!\n");
 
    } else{
 
        printf("正在运行的进程的进程名为:%d  ",H->Next->ID);
 
printf("优先数:%d  ",H->Next->Priority);
 
    printf("到达时间:%d  ",H->Next->GetTime);
 
    printf("进程还需要运行时间:%d  ",H->Next->AllTime);
 
    printf("已用CPU时间:%d  ",H->Next->CPUTime);
 
    if(H->Next->StartBlock>=0)
 
    printf("StartBlock:%d ",H->Next->StartBlock);
 
    if(H->Next->StartTime>0)
 
    printf("StartTime:%d ",H->Next->StartTime);
 
    printf("进程状态:%s\n",H->Next->State);
 
        
 
    }
 
}
 
void Disp2(PCB *H)   //输出就绪队列中的进程
 
{
 
    PCB *p;
 
    if(H->Next==NULL){
 
        printf("就绪队列中无进程!\n");
 
    } else{
 
        p=H;
 
        p=p->Next;
 
        printf("就绪队列中的进程如下\n");
 
        while(p!=NULL){
 
            printf("进程名:%d  ",p->ID);
 
            printf("优先数:%d  ",p->Priority);
 
            printf("到达时间:%d  ",p->GetTime);
 
            printf("进程还需要运行时间:%d  ",p->AllTime);
 
            printf("已用CPU时间:%d  ",p->CPUTime);
 
            if(p->StartBlock>=0)
 
            printf("StartBlock:%d  ",p->StartBlock);
 
            if(p->StartTime>0)
 
            printf("StartTime:%d  ",p->StartTime);
 
            printf("进程状态:  %s\n",p->State);
 
            p=p->Next;
 
        }
 
        printf("\n");
 
    }
 
}
 
PCB* Dispatch(PCB *H){
    PCB *ready,*block,*p,*end;
 
    ready=CreateProcess(ready,0);
 
    block=CreateProcess(block,0);
 
    end=CreateProcess(end,0);
 
        p=H->Next;
 
        while(p!=NULL){
 
            if(strcmp(p->State,"就绪")==0){
 
                Insert(ready,p);
 
            }
 
            if(strcmp(p->State,"阻塞")==0){
 
                Insert(block,p);
 
            }
 
            p=p->Next;
 
        }
 
        if(ready->Next==NULL&&block->Next==NULL){
 
     printf("已无进程\n");
 
}
 
else if(ready->Next!=NULL){
 
ready=Ready(ready);
 
        ready->Next->Priority-=3;  
 
        ready->Next->CPUTime+=1;
 
        ready->Next->AllTime-=1;
 
        ready->Next->StartBlock-=1;
 
        if(ready->Next->StartBlock==0){
 
         ready->Next->State="阻塞";
 
}
 
        else if(ready->Next->AllTime==0){
 
            ready->Next->State="完成";
 
        }
 
else{
 
            ready->Next->State="运行";
 
        }
 
        Disp1(ready);
 
        printf("------------------------------------------------------------------------------------------------------------\n");
 
        p=ready;
 
        while(p->Next!=NULL){
 
         if(strcmp(p->Next->State,"就绪")==0)
 
         p->Next->Priority+=1;
 
            else if(strcmp(p->Next->State,"运行")==0)
 
            p->Next->State="就绪";
 
            Insert(end,p->Next);
 
            p=p->Next;
 
        }
 
        p=block;
 
        while (p->Next!=NULL){
 
         p->Next->StartTime--;
 
         if(p->Next->StartTime==0)
 
         p->Next->State="就绪";
 
            Insert(end,p->Next);
 
            p=p->Next;
 
        }
 
        ready->Next=ready->Next->Next;
 
        Disp2(ready);
 
}
 
else{
 
p=block;
 
while (p->Next!=NULL){
 
         p->Next->StartTime--;
 
        
 
         if(p->Next->StartTime==0)
 
         p->Next->State="就绪";
 
            Insert(end,p->Next);
 
            p=p->Next;
 
        }
 
}
 
 printf("-----------------------------------------------------------------------------------------------------------------------\n\n\n");
 
    return end;
 
}
 
int main() {
 
 
 
    int num,i;
 
    i=1;
 
    bool flag=true;
 
    PCB *pcb,*ready;
 
    printf("请输入进程数:");
 
    scanf("%d",&num);
 
    pcb=CreateProcess(pcb,num);
 
    while(pcb->Next!=NULL){
 
        printf("第%d次执行结果:\n",i++);
 
        printf("-----------------------------------------------------------------------------------------------------------------------\n");
 
        pcb=Dispatch(pcb);
 
    }
 
    return 0;
 
}