shengqiang's blog

进程调度-短进程优先算法

 
  • 2017年 11月27日

最近在学习操作系统的时候，为了加深自己对进程的了解，于是使用C语言模拟进程调度，首先写的是短进程优先算法。

进程PCB块

进程PCB块包含的成员变量有name作业名，state进程状态,arrivetime到达时间, runtime需要运行的时间， starttime开始时间，endtime完成时间，turnoverTime周转时间。

代码详解

main函数

为了快速了解短进程优先的算法，先展示main函数部分，以便能够知道程序的逻辑顺序。

int main() /*主函数*/
{
    char ch;
    int result;
    input(); //用户输入
    node_number = space(); //取进程个数
    p = ready;
    while( node_number!=0 )
    {
        ch=getchar();
        global_nowtime++;
        printf("\n\n当前时刻:%d\n",global_nowtime);
        result = running();
        if(result == 1)
            break; //所有进程运行完毕
    }
    ch = getchar();
    return 0;
}

用户输入数据

input函数提示用户输入进程个数，以及每个进程的PCB参数，这一块不做多解释。

void input() /* 建立进程控制块函数*/
{
    int i,num;
    char ch;
    system("clear");/*linux清屏函数*/
    printf("\n请输入进程个数:");
    scanf("%d",&num);
    for(i=0;i<num;i++)
    {
        p=getpch(PCB);
        printf("输入进程名:");
        scanf("%s",p->name);
        printf("输入进程到达时间:");
        scanf("%d",&p->arriveTime);
        printf("输入进程需要运行时间:");
        scanf("%d",&p->runTime);
        while( (p->arriveTime) < 0 )
        {
            while( (ch=getchar()) != '\n' && ch!=EOF);/*清除键盘输入缓冲区*/
            printf("进程运行时间必须非负数，请重新输入:");
            scanf("%d",&p->arriveTime);
        }
        printf("\n");
        p->state='W'; //Wait等待标志
        p->link=NULL; //指向空指针
        p->startTime = -999; //-999表示未开始
        p->endTime = -999; //-999表示未开始
        sort(); //调用sort函数
    }
}

running函数

  1. 当用户输入完进程个数以及每个PCB的参数后，程序进入running函数。
  2. 首先检测获取一个状态为未结束的进程，并将其赋值给minPcb。
  3. 然后判断是否存在至少一个未结束的进程，若都结束了，则所有进程运行完毕；否则找到所有满足到达时间<=当前时刻的进程（若当前时刻小于进程的到达时间，就不需要考虑这些还没到达的进程了）。
  4. 对这些所有符合条件的进程进行依次比较，找到一个所需时间最短的进程。 置该进程运行状态为R，并记录开始运行时间。
  5. 判断该进程是否运行结束，若是，则置状态为F，并且记录运行结束时间。
  6. 重复以上步骤
int running() /* 建立进程就绪函数 进程运行时间到,置就绪状态*/
{
    PCB *minPcb = NULL; //最小所需运行时间的进程
    PCB *tmp = p;
    int finishCount = 0;//运行结束进程个数
    
    while( tmp != NULL ) //找到第一个未结束的进程
    {
        if( (tmp->state) != 'F')
        {
            minPcb = tmp;
            break;
        }
        else
        {
            finishCount++;
            tmp = tmp->link;
        }
    }
    
    printf("finishCount:%d\n",finishCount);
    tmp = p;
    if( finishCount != node_number) //存在至少一个进程未运行结束
    {
        while( (tmp != NULL) &&((tmp->arriveTime) <= global_nowtime) ) //返回一个符合条件的最小所需运行时间的进程
        {
            if( (tmp->state != 'F') ) //该进程还未结束
            {
                if( (minPcb->runTime) > (tmp->runTime) ) //与下一个进程比较
                {
                    minPcb = tmp;
                }
            }
            tmp = tmp->link;
        }
        
        if(minPcb->startTime == -999)//判断是否已经记录过开始时间，若未，则记录开始时间
        {
            minPcb->startTime = global_nowtime;
            minPcb->state = 'R'; //Run运行标志
        }
        if( global_nowtime - (minPcb->startTime) >= (minPcb->runTime))//当前时间 - 开始时间 >= 运行时间 表明运行结束
        {
            minPcb->state = 'F'; //Finish完成标志
            minPcb->endTime = global_nowtime;//运行结束时间
            global_nowtime--;
        }
        printf("minarriveTime:%d,globalNowtime:%d\n",minPcb->arriveTime,global_nowtime);
        check(minPcb); //输出正在运行的进程和其余进程
    }
    else
    {
        check(NULL); //输出正在运行的进程和其余进程
        printf("\n所有进程运行完毕");
        return 1;
    }
    return 0;
}

其余函数

下面这部分的代码不是本算法的核心，所以不作过多的介绍，可以自己看看。

//
//  main.c
//  ShortProcess
//
//  Created by 张小白 on 2017/11/16.
//  Copyright © 2017年 张小白. All rights reserved.
//

#include "stdio.h"
#include <stdlib.h>
#define getpch(type) (type*)malloc(sizeof(type)) //宏定义
int global_nowtime = 0; //当前时刻
int node_number = 0;//进程个数

//结构体定义
struct pcb
{
    char name[10];//作业号
    char state;//状态
    int arriveTime;//到达时间
    int runTime;//需要运行时间
    int startTime;//开始时间
    int endTime;//完成时间
    int turnoverTime;//周转时间
    float useWeightTurnoverTime;//带权周转时间
    struct pcb* link;
}*ready=NULL,*p;

typedef struct pcb PCB;

int sort() /* 建立对进程进行优先级排列函数*/
{
    PCB *first, *second;
    int insert=0;
    if( (ready==NULL) || ( (p->arriveTime) < (ready->arriveTime) ) ) /*所需运行时间最小者,插入队首*/
    {
        p->link=ready;
        ready=p;
    }
    else /* 进程比较优先级,插入适当的位置中*/
    {
        first=ready;
        second=first->link;
        while(second!=NULL)
        {
            if( (p->arriveTime) < (second->arriveTime) ) /*若插入进程比当前进程优先数大,*/
            { /*插入到当前进程前面*/
                p->link=second;
                first->link=p;
                second=NULL;
                insert=1;
            }
            else /* 插入进程优先数最低,则插入到队尾*/
            {
                first=first->link;
                second=second->link;
            }
        }
        if(insert==0) first->link=p;
    }
    return 0;
}



int space()
{
    int l=0; PCB* pr=ready;
    while(pr!=NULL)
    {
        l++;
        pr=pr->link;
    }
    return(l);
}

void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
    printf("\n|进程名\t|进程状态\t|到达时间\t|运行时间\t|开始时间\t|完成时间\t\n");
    printf("|%-7s\t",pr->name);
    printf("|%-7c\t",pr->state);
    printf("|%-7d\t",pr->arriveTime);
    printf("|%-7d\t",pr->runTime);
    printf("|%-7d\t",pr->startTime);
    printf("|%-7d\t",pr->endTime);
    printf("\n");
}

int check(PCB* node) /* 建立进程查看函数 */
{
    PCB* pr = p;
    printf("\n****正运行的进程为:");
    while(pr!=NULL)
    {
        if(pr->state == 'R') //正在运行的进程
        {
            disp(pr);
        }
        pr=pr->link;
    }
    
    printf("\n****已就绪的进程为:");
    pr = p;
    while(pr!=NULL)
    {
        if(pr->state == 'W') //准备就绪的进程
        {
            disp(pr);
        }
        pr=pr->link;
    }
    
    printf("\n****已结束的进程为:");
    pr = p;
    while(pr!=NULL)
    {
        if(pr->state == 'F') //运行结束的进程
        {
            disp(pr);
        }
        pr=pr->link;
    }
    return 0;
}

int destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
    printf("进程 [%s] 已完成\n",p->name);
    free(p);
    return 0;
}
搜索