操作系统 作业（进程）调度实验 C语言版

操作系统实验： 作业（进程）调度 C语言版

一、实验目的与要求

本实验的目的是通过作业或进程调度算法模拟设计，进一步加深对作业或进程调度算法的理解，通过计算平均周转时间和带权平均周转时间，进一步加深对算法的评价方法的理解。

二、实验内容

1、实验预备内容
(1）预习作业或进程调度算法。
(2）预习平均周转时间和带权平均周转时间计算。
2、实验内容
设定一组作业或进程，给定相关参数，对这组进程或作业按调度算法实施调度，输出调度次序，并计算平均周转时间和带权平均周转时间。要求实现的调度算法有:
(1）先来先服务调度算法。
(2）优先级（抢占式）调度算法。
(3）短作业（或进程）优先（非抢占）调度算法。
(4）响应比高优先（非抢占）调度算法。

三、直接上代码

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int id; //作业序号
    char name[8]; //作业名称
    int level; //优先级
    float submit_time; //提交时间
    float run_time; //运行时间
    float intoqueue_time; //进入输入井时间
    float start_time; //开始执行时间
    float remain_time; //尚需运行时间
    float end_time; //执行结束时间
    float Ttime;   //周转时间
    float Wtime; //带权周转时间
    int order; //运行次序
} work;

int menu(); //菜单函数
void input_Data(work* w[],int n); // 数据输入函数
void init(work* w[],int n); // 特定属性初始化函数
void out_Data(work* w[],int n); // 数据输出函数
void FCFS(work* w[],int n); // 先来先服务调度
void Priority(work* w[],int n);//优先级调度 优先级数字大的级别较高
void SJF(work* w[],int n);  // 最短作业调度
void HRRN(work* w[],int n); // 响应比高者优先调度
int sort1(work* a[],int n,int flag); // 返回进入输入井时间最早的未运行进程的下标(且大于flag)
int sort2(work* a[],int n); // 返回优先级最高的未运行进程的下标
int sort3(work* a[],int n); // 返回运行时间最短的未运行进程的下标
int sort4(work* a[],int n,float mark); // 返回响应比最高的未运行进程的下标

int main()
{
    int i,n;
    printf("请输入作业或进程数：n");
    scanf("%d",&n);
    work* job[n];
    input_Data(job,n);

    while(1)
    {
        init(job,n);
        switch(menu())
        {
        case 0:
            printf("程序已退出！");
            return 0;
        case 1: //先来先服务调度
            printf("已选择先来先服务调度算法：");
            FCFS(job,n);
            break;
        case 2: //优先级调度
            printf("已选择优先级(抢占式)调度算法：");
            Priority(job,n);
            break;
        case 3: //短作业调度
            printf("已选择短作业调度算法：");
            SJF(job,n);
            break;
        case 4: //响应比高者优先调度
            printf("已选择响应比高者优先调度算法：");
            HRRN(job,n);
            break;
        }
        out_Data(job,n);
    }
    return 0;
}
void HRRN(work* w[],int n)
{
    int i,r = sort1(w,n,-12);
    w[r]->remain_time=0;
    float MARK = w[r]->intoqueue_time;
    for(i=0; i<n; i++)
    {
        if(i)
        {
            r = sort1(w,n,-12);
            w[r]->remain_time=0;
        }
        if(((MARK == w[r]->intoqueue_time)&&(!i))||((MARK < w[r]->intoqueue_time)&&(i!=0)))
        {
            w[r]->start_time = w[r]->intoqueue_time;
            w[r]->end_time = w[r]->start_time + w[r]->run_time;
            w[r]->Ttime = w[r]->end_time - w[r]->intoqueue_time;
            w[r]->Wtime = w[r]->Ttime / w[r]->run_time;
            w[r]->order = i+1;
            MARK == w[r]->intoqueue_time? (MARK += w[r]->run_time):(MARK = w[r]->intoqueue_time+w[r]->run_time);
        }
        else
        {
            w[r]->remain_time = w[r]->run_time;
            r = sort4(w,n,MARK);
            w[r]->start_time = MARK;
            w[r]->end_time = w[r]->start_time + w[r]->run_time;
            w[r]->Ttime = w[r]->end_time - w[r]->intoqueue_time;
            w[r]->Wtime = w[r]->Ttime / w[r]->run_time;
            w[r]->order = i+1;
            MARK += w[r]->run_time;
        }
    }
}
int sort4(work* a[],int n,float mark)
{
    float Max=-1,MinStart;
    int i,j= -1;
    for(i=0; i<n; i++)
    {
        if((Max < ((mark - a[i]->submit_time)/a[i]->run_time)) && (a[i]->remain_time))
        {
            Max = ((mark - a[i]->submit_time)/a[i]->run_time); // 最短运行时间
            MinStart = a[i]->start_time;
            j = i;
        }
        else if((Max == ((mark - a[i]->submit_time)/a[i]->run_time)) && (a[i]->remain_time) && (MinStart > a[i]->start_time))
        {
            Max = ((mark - a[i]->submit_time)/a[i]->run_time);
            j = i;
        }
    }
    a[j]->remain_time = 0;
    return j;
}
void SJF(work* w[],int n)
{
    int i,r = sort1(w,n,-12);
    w[r]->remain_time=0;
    float MARK = w[r]->intoqueue_time;
    for(i=0; i<n; i++)
    {
        if(i)
        {
            r = sort1(w,n,-12);
            w[r]->remain_time=0;
        }
        if(((MARK == w[r]->intoqueue_time)&&(!i))||((MARK < w[r]->intoqueue_time)&&(i!=0)))
        {
            w[r]->start_time = w[r]->intoqueue_time;
            w[r]->end_time = w[r]->start_time + w[r]->run_time;
            w[r]->Ttime = w[r]->end_time - w[r]->intoqueue_time;
            w[r]->Wtime = w[r]->Ttime / w[r]->run_time;
            w[r]->order = i+1;
            MARK == w[r]->intoqueue_time? (MARK += w[r]->run_time):(MARK = w[r]->intoqueue_time+w[r]->run_time);
        }
        else
        {
            w[r]->remain_time = w[r]->run_time;
            r = sort3(w,n);
            w[r]->start_time = MARK;
            w[r]->end_time = w[r]->start_time + w[r]->run_time;
            w[r]->Ttime = w[r]->end_time - w[r]->intoqueue_time;
            w[r]->Wtime = w[r]->Ttime / w[r]->run_time;
            w[r]->order = i+1;
            MARK += w[r]->run_time;
        }
    }
}
int sort3(work* a[],int n)
{
    float Min=9999,MinStart;
    int i,j= -1;
    for(i=0; i<n; i++)
    {
        if((Min > a[i]->run_time) && (a[i]->remain_time))
        {
            Min = a[i]->run_time; // 最短运行时间
            MinStart = a[i]->start_time;
            j = i;
        }
        else if((Min == a[i]->run_time) && (a[i]->remain_time) && (MinStart > a[i]->start_time))
        {
            Min = a[i]->run_time;
            j = i;
        }
    }
    a[j]->remain_time = 0;
    return j;
}
void FCFS(work* w[],int n)
{
    float START = 0;
    int i;
    for(i=0; i<n; i++)
    {
        int running = sort1(w,n,-12);
        w[running]->remain_time=0;
        if(!i)
            START += w[running]->submit_time;
        START >= w[running]->submit_time?(START=START):(START = w[running]->submit_time);
        w[running]->start_time = START;
        w[running]->end_time = w[running]->start_time + w[running]->run_time;
        w[running]->Ttime = w[running]->end_time - w[running]->intoqueue_time;
        w[running]->Wtime = w[running]->Ttime / w[running]->run_time;
        w[running]->order = i+1;
        START += w[running]->run_time;
    }
}
void Priority(work* w[],int n)
{
    int i=0,Living=1,r0 = sort1(w,n,-12);
    int r = r0,j=0;
    float MARK = w[r0]->intoqueue_time;// 8:00,
        int MAX = sort2(w,n);
    w[r0]->remain_time = w[r0]->run_time;
    while(1)
    {
        if(((w[r0]->remain_time == 0)||(w[r]->remain_time == 0))&&(sort2(w,n) != MAX)/**/)
        {
            r = sort2(w,n);
            r0 = r;
        }
        else 
        {
            r0 = r;
            r = sort1(w,n,r0);// r=r0第二早
        }
        if((r0==-1)&&(r==-1))
            break;
        if((MARK + w[r0]->remain_time <= w[r]->submit_time)||(r0 == sort2(w,n))) //r0可以全部执行
        {
            if(w[r0]->order == 0)
            {
                i++;
                w[r0]->order = i;
                w[r0]->start_time = MARK;
            }
            w[r0]->end_time = MARK + w[r0]->remain_time;
            w[r0]->Ttime = w[r0]->end_time - w[r0]->intoqueue_time;
            w[r0]->Wtime = w[r0]->Ttime / w[r0]->run_time;
            MARK += w[r0]->remain_time;
            w[r0]->remain_time =0;
        }
        else if((MARK + w[r0]->remain_time > w[r]->submit_time)&&(w[r]->remain_time))
        {
                if(w[r0]->order == 0)
                {
                    i++;
                    w[r0]->order = i;
                    MARK < w[r0]->submit_time? (MARK=w[r0]->submit_time):(MARK = MARK);
                    w[r0]->start_time = MARK;
                    w[r0]->remain_time -= w[r]->submit_time - MARK;
                    //printf("n%.2fn",w[r0]->remain_time);
                    MARK = w[r]->submit_time;
                }
            if(r == sort2(w,n))
            {
                w[r]->start_time = MARK;//8:40
                w[r]->end_time = w[r]->start_time + w[r]->run_time;
                w[r]->Ttime = w[r]->end_time - w[r]->intoqueue_time;
                w[r]->Wtime = w[r]->Ttime / w[r]->run_time;
                if(w[r]->order == 0)
                {
                    i++;
                    w[r]->order = i;
                }
                MARK += w[r]->remain_time;
                w[r]->remain_time =0;
            }
        }
    }
}
int sort2(work* a[],int n)
{
    float Max=-999,MinStart;
    int i,j= -1;
    for(i=0; i<n; i++)
    {
        if((Max < a[i]->level) && (a[i]->remain_time))
        {
            Max = a[i]->level; // 最高优先级
            MinStart = a[i]->start_time;
            j = i;
        }
        else if((Max == a[i]->level) && (a[i]->remain_time) && (MinStart > a[i]->start_time))
        {
            Max = a[i]->level;
            MinStart = a[i]->start_time;
            j = i;
        }
    }
    return j;
}
//  */
int sort1(work* a[],int n,int flag) // 返回未运行作业（进程）队列中的提交时间最近的作业标号
{
    float Min=9999,MinStart;
    int i,j=-1;
    for(i=0; i<n; i++)
    {
        if((Min > a[i]->submit_time)&&a[i]->remain_time && (i > flag))
        {
            Min = a[i]->submit_time;
            MinStart = a[i]->level;
            j = i;
        }
        else if((Min == a[i]->submit_time)&&a[i]->remain_time && (i > flag) && (MinStart < a[i]->level))
        {
            Min = a[i]->submit_time;
            MinStart = a[i]->level;
            j = i;
        }
    }
    return j;
}
int menu()
{
    int chioce=0;
    printf("********************************************************n");
    printf(" 0.退出程序 n");
    printf(" 1.调用先来先服务调度程序   2.调用优先级调度程序n");
    printf(" 3.调用短作业调度程序       4.调用响应比高者优先调度程序  n");
    printf("********************************************************n");
    printf("请选择操作（0~4）：");
    while(1)
    {
        scanf("%d",&chioce);
        if(chioce<0||chioce>4)
            printf("输入错误，请选择操作（0~4）：");
        else
            break;
    }
    return chioce;
}

void input_Data(work* w[],int n)
{
    int i;
    printf("请在每行依次输入进程(作业)信息（名称、进程号、到达时间、运行时间、优先级）;n");
    for(i=0; i<n; i++)
    {
        w[i] = (struct node*)malloc(sizeof(struct node));// 申请一个结构体空间
        printf("请输入%d号进程信息：",i+1);
        scanf("%s",&w[i] -> name);
        scanf("%d",&w[i] -> id);
        scanf("%f",&w[i] -> submit_time);
        scanf("%f",&w[i] -> run_time);
        scanf("%d",&w[i] -> level);
        w[i]->intoqueue_time = w[i]->submit_time; //默认作业提交耗时为0，进入输入井时间等于到达时间
        w[i]->remain_time = w[i] -> run_time; //默认的尚需运行的时间
    }
}
void init(work* w[],int n)
{
    int i;
    for(i=0; i<n; i++)
    {
        w[i]->intoqueue_time = w[i]->submit_time;
        w[i]->remain_time = w[i] -> run_time;
    }
}
void out_Data(work* w[],int n)
{
    int i;
    float average_Ttime = 0,average_Wtime = 0;
    printf("n*************************************************调度数据表********************************************************n");
    printf("进程(作业)号  进程名  到达时间(h)  运行开始时间(h)  运行结束时间(h)  优先级  运行次序  周转时间(h)  带权周转时间(h)n");
    for(i=0; i<n; i++)
    {
        printf("    %dtt%st%.2ft        %.2ft  t%.2f           %dt%d        %.2ft       %.2fn",w[i]->id,w[i]->name,w[i]->submit_time,w[i]->start_time,w[i]->end_time,w[i]->level,w[i]->order,w[i]->Ttime,w[i]->Wtime);
        average_Ttime +=w[i]->Ttime;
        average_Wtime +=w[i]->Wtime;
        if(i!=(n-1))
            printf("n");
    }
    printf("%d作业(进程)调度的整体性能评价：平均周转时间：%.3fht平均周转时间：%.3fhnn",n,average_Ttime/n,average_Wtime/n); //计算Ttime和Wtime的平均值
}

四、测试结果

1. 输入数据：

2. 输出结果：