操作系统 - 作业调度实验（FCFS、SJF、HRN）

编写并调试一个单道处理系统的作业等待模拟程序。
作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。
对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。

#include 
#include 
#include 
#include 
#define getpch(type) (type *)malloc(sizeof(type))
struct jcb
{
    char name[10];   //进程的名字
    char state;      //进程状态
    int starttime;   //进程到达时间
    int needtime;    //进程运行时间
    int endtime;     //进程结束时间
    int runtime;     //进程周转时间
    double dqzztime; //带权周转时间
    struct jcb *link;
};
typedef struct jcb JCB;
const int INF = 0x3f3f3f3f;
double aver_runtime = 0, aver_w_runtime = 0;
int num = 0;

void destroy(JCB *p) 
{
    printf("n 进程 [%s] 已完成.n", p->name);
    free(p);
}
int space(JCB *pr)
{
    int l = 0;
    while (pr != NULL)
    {
        l++;
        pr = pr->link;
    }
    return (l);
}
JCB *sort(JCB *ready, JCB *p) 
{
    JCB *first, *second;
    int insert = 0;
    if ((ready == NULL) || ((p->starttime) < (ready->starttime))) 
    {
        p->link = ready;
        ready = p;
    }
    else 
    {
        first = ready;
        second = first->link;
        while (second != NULL)
        {
            if ((p->starttime) < (second->starttime)) 
            {                                         
                p->link = second;
                first->link = p;
                second = NULL;
                insert = 1;
            }
            else 
            {
                first = first->link;
                second = second->link;
            }
        }
        if (insert == 0)
            first->link = p;
    }
    return ready;
}
void disp(JCB *pr) 
{
    printf("n 名称 t 状态 t 到达 t 运行 t 周转 t 带权周转 t 结束 t n");
    printf("|%st", pr->name);
    printf("|%ct", pr->state);
    printf("|%dt", pr->starttime);
    printf("|%dt", pr->needtime);
    printf("|%dt", pr->runtime);
    printf("|%lft", pr->dqzztime);
    printf("|%dt", pr->endtime);
    printf("n");
}
void check(JCB *ready, int T, int state = 0) 
{
    JCB *pr;
    int Rp = 0;
    pr = ready;
    printf("n ****当前就绪队列状态为:n"); 
    while (pr != NULL && pr->starttime <= T)
    {
        if (state == 1)
        {
            Rp = T - pr->starttime + pr->needtime;
            printf("Rp_%s: %dn", pr->name, Rp);
        }
        disp(pr);
        pr = pr->link;
    }
}
JCB *input(JCB *ready) 
{
    printf("n 请输入进程数?");
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
    {
        printf("n 进程号 No.%d:n", i);
        JCB *p = getpch(JCB);
        printf("n 输入进程名:");
        scanf("%s", p->name);
        printf("n 输入进程到达时间:");
        scanf("%d", &p->starttime);
        printf("n 输入进程运行时间:");
        scanf("%d", &p->needtime);
        printf("n");
        p->endtime = 0;
        p->dqzztime = 0;
        p->runtime = 0;
        p->state = 'w';
        p->link = NULL;
        ready = sort(ready, p);
    }
    check(ready, INF);
    char ch = getchar();
    return ready;
}
void F_FCFS(JCB *ready)
{
    int len = space(ready), T = 0, h = 0;
    char ch;
    JCB *p = ready, *temp = NULL;
    while ((len != 0) && (p != NULL))
    {
        ch = getchar();
        h++;
        printf("nThe execute number:%d n", h);
        printf("%s start runing...n", p->name);
        if (T = 0)
        {
            p->runtime = p->needtime;
            p->endtime = p->starttime + p->needtime;
            T = p->endtime;
        }
        else if (p->starttime > T)
        {
            p->runtime = p->needtime;
            p->endtime = p->starttime + p->needtime;
            T = p->endtime;
        }
        else
        {
            p->runtime = p->needtime + T - p->starttime;
            p->endtime = p->starttime + p->runtime;
            T = p->endtime;
        }
        p->dqzztime = p->runtime * 1.0 / p->needtime;
        p->state = 'F';
        disp(p);
        temp = p->link;
        aver_runtime += p->runtime;
        aver_w_runtime += p->dqzztime;
        destroy(p);
        p = temp;
        printf("n 按任一键继续......");
    }
    printf("nn 进程已经完成.n");
    ch = getchar();
}
JCB *NT_MIN(JCB *ready, int T)
{
    if (ready->starttime > T)
    {
        return NULL;
    }
    if (ready->link == NULL || ready->link->starttime > T)
    {
        return ready;
    }
    JCB *p = ready->link, *m = ready;
    JCB *p_F = ready, *m_F = NULL;
    while (p != NULL && p->starttime <= T)
    {
        if (p->needtime < m->needtime)
        {
            m = p;
            m_F = p_F;
        }
        p_F = p;
        p = p->link;
    }
    if (m_F != NULL)
    {
        m_F->link = m->link;
        m->link = ready;
        ready = m;
    }
    return ready;
}
JCB *RP_MIN(JCB *ready, int T)
{
    if (ready->starttime > T)
    {
        return NULL;
    }
    if (ready->link == NULL || ready->link->starttime > T)
    {
        return ready;
    }
    JCB *p = ready->link, *m = ready;
    JCB *p_F = ready, *m_F = NULL;
    double Rp_m = 0, Rp_p = 0;
    while (p != NULL && p->starttime <= T)
    {
        Rp_m = T - m->starttime + m->needtime;
        Rp_p = T - p->starttime + p->needtime;
        if (Rp_p > Rp_m)
        {
            m = p;
            m_F = p_F;
        }
        p_F = p;
        p = p->link;
    }
    if (m_F != NULL)
    {
        m_F->link = m->link;
        m->link = ready;
        ready = m;
    }
    return ready;
}
void F_SJF_HRN(JCB *ready, int state)
{
    int len = space(ready), T = 0, h = 0;
    char ch;
    JCB *p = ready;
    JCB *temp = NULL;
    while ((len != 0) && (p != NULL))
    {
        T++;
        if (p->starttime <= T)
        {
            ch = getchar();
            h++;
            printf("nThe execute number:%d n", h);
            printf("%s start runing...n", p->name);
            if (state == 0)
                p = NT_MIN(p, T);
            else if (state == 1)
                p = RP_MIN(p, T);
            p->runtime = T - p->starttime + p->needtime;
            p->endtime = T + p->needtime;
            T = p->endtime;
            p->dqzztime = p->runtime * 1.0 / p->needtime;
            p->state = 'F';
            disp(p);
            temp = p->link;
            aver_runtime += p->runtime;
            aver_w_runtime += p->dqzztime;
            destroy(p);
            p = temp;
            check(p, T, state);
            printf("n 按任一键继续......");
        }
    }
}

JCB* COPY(JCB* ready) {
    JCB *head = NULL, *tail = NULL;
    int flag = 1;
    while(ready != NULL) {
        JCB *p = getpch(JCB);
        strcpy(p->name, ready->name);
        p->starttime = ready->starttime;
        p->needtime = ready->needtime;
        p->endtime = ready->endtime;
        p->dqzztime = ready->dqzztime;
        p->runtime = ready->runtime;
        p->state = 'w';
        p->link = NULL;
        if(flag) {
            head = p;
            tail = p;
            flag = 0;
        }
        else {
            tail->link = p;
            tail = p;
        }
        ready = ready->link;
    }
    return head;
}

int main()
{
    printf("实验二 单道处理系统的作业等待模拟程序。nn");
    JCB *ready = NULL;
    ready = input(ready);
    aver_runtime = aver_w_runtime = 0.0;
    printf("n采用先来先服务（FCFS）:n");
    F_FCFS(COPY(ready));
    printf("n该组作业的平均周转时间为%lf、带权平均周转时间为%lfn",aver_runtime/num, aver_w_runtime/num);
    aver_runtime = aver_w_runtime = 0.0;
    printf("n最短作业优先（SJF）:n");
    F_SJF_HRN(COPY(ready), 0);
    printf("n该组作业的平均周转时间为%lf、带权平均周转时间为%lfn",aver_runtime/num, aver_w_runtime/num);
    aver_runtime = aver_w_runtime = 0.0;
    printf("n响应比高者优先（HRN）的调度算法:n");
    F_SJF_HRN(ready, 1);
    printf("n该组作业的平均周转时间为%lf、带权平均周转时间为%lfn",aver_runtime/num, aver_w_runtime/num);
    char ch = getchar();
    return 0;
}