操作系统实验二——进程调度算法（FCFS、RR）

目录

• 进程调度算法

进程调度算法

FCFS算法代码

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

using namespace std;

/* 先来先服务（FCFS） */
// 定义先来先服务结构体、参数
struct fcfs{
    
    char name[10];// 进程名称
    float daodatime;// 到达时间
    float fuwutime;// 服务时间
    float kaishitime;// 开始时间
    float wanchengtime; // 完成时间
    float zhouzhuangtime;// 周转时间
    float daiquantime;// 带权周转时间
};


// 构造一个输入进程信息的函数，定义结构体指针并初始化
void input(fcfs *p, int N)
{
    int i;
    for(i = 0; i <= N - 1; i++)
    {
        printf("输入第%d个进程的名字、到达时间、服务时间(例如：PA 2 1)：\n", i+1);
        // 把输入信息保存到结构体指针所对应的内存中
        scanf("%s %f %f", p[i].name, &p[i].daodatime, &p[i].fuwutime);
        p[i].kaishitime = 0;
        p[i].wanchengtime = 0;
        p[i].zhouzhuangtime = 0;
        p[i].daiquantime = 0;
    }
}

// 构造一个输出函数
void print(fcfs *p, int N)
{
    int k;

    printf("\n进程的相关信息如下：\n");
    printf("\n名字 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
    for(k = 0; k < N; k++)
    {
        printf("%3s\t%-.3f\t%-.3f\t%-.3f\t%-.3f\t%-.3f\t%-.3f\n", p[k].name, p[k].daodatime, p[k].fuwutime,
            p[k].kaishitime, p[k].wanchengtime, p[k].zhouzhuangtime, p[k].daiquantime);
    }

    printf("执行顺序：\n");
    printf("%s", p[0].name);
    for(k = 1; k < N; k++)
    {
        printf("-->%s", p[k].name);
    }
}

// 根据进程到达时间进行排序，从小到大
void sort(fcfs *p, int N)
{
    int i,j;
    for(i = 1; i < N; i++)
    {
        fcfs t = p[i];
        for(j = i - 1; j >= 0 && t.daodatime < p[j].daodatime; j--)
            p[j+1] = p[j];
        p[j+1] = t;
    }
}

// 核心运行阶段
void run(fcfs *p, int N)
{
    int k;
    for(k = 0; k < N; k++)
    {
        // 第一个进程到达
        if(k == 0)
        {
            p[k].kaishitime = p[k].daodatime;
            p[k].wanchengtime = p[k].daodatime + p[k].fuwutime;
        }
        else
        {
            if(p[k].daodatime <= p[k - 1].wanchengtime)
            {
                p[k].kaishitime = p[k - 1].wanchengtime;
                p[k].wanchengtime = p[k].kaishitime + p[k].fuwutime;
            }
            else
            {
                p[k].kaishitime = p[k].daodatime;
                p[k].wanchengtime = p[k].kaishitime + p[k].fuwutime;
            }
            
        }
    }
    // 计算周转时间和带权周转时间
    for(k = 0; k < N; k++)
    {
        // 周转时间 = 完成时间 - 到达时间
        p[k].zhouzhuangtime = p[k].wanchengtime - p[k].daodatime;
        // 带权周转时间 = 周转时间/服务时间
        p[k].daiquantime = p[k].zhouzhuangtime/p[k].fuwutime;
    }
}

// 定义先来先服务函数
void FCFS_MAIN()
{
    int N;
    printf("请输入进程的数量:\n");
    scanf("%d",&N);

    fcfs *p = new fcfs[N];

    input(p, N);// 输入
    sort(p, N);// 根据到达时间从小到大排序
    run(p, N);// 运行
    print(p, N);// 输出
    delete [] p;
}

int main()
{
    FCFS_MAIN();
    return 0;
} 

RR算法代码

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

using namespace std;

/* 时间片调度服务（rr） */
// 时间片调度服务结构体、参数
struct rr{
    
    char name[10];// 进程名称
    float daodatime;// 到达时间
    float fuwutime;// 服务时间
    float run_time;//运行时间
    float kaishitime;// 开始时间
    float wanchengtime; // 完成时间
    float zhouzhuangtime;// 周转时间
    float daiquantime;// 带权周转时间
    int run_flag;          /*调度标志*/
    int start_flag;     //是否为第一次开始调度
};
    int left;//剩余未完成的进程个数
    int pattern;//工作模式
    int time_counter=0;
// 构造一个输入进程信息的函数，定义结构体指针并初始化
void input(rr *p, int N)
{
    int i;
    printf("请选择算法模式（1：时间片固定 0：时间可变）\n");
    scanf("%d",&pattern);
    for(i = 0; i <= N - 1; i++)
    {
        printf("输入第%d个进程的名字、到达时间、服务时间(例如：PA 2 1)：\n", i+1);
        // 把输入信息保存到结构体指针所对应的内存中
        scanf("%s %f %f", p[i].name, &p[i].daodatime, &p[i].fuwutime);
        p[i].run_time = p[i].fuwutime;
        p[i].kaishitime = 0;
        p[i].wanchengtime = 0;
        p[i].zhouzhuangtime = 0;
        p[i].daiquantime = 0;
        p[i].run_flag=0;  //运行是否结束
        p[i].start_flag=0;//是否首次被执行
    }
}

// 构造一个输出函数
void print(rr *p, int N)
{
    int k;

    printf("\n进程的相关信息如下：\n");
    printf("\n名字 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
    for(k = 0; k < N; k++)
    {
        printf("%3s\t%-.3f\t%-.3f\t%-.3f\t%-.3f\t%-.3f\t%-.3f\n", p[k].name, p[k].daodatime, p[k].fuwutime,
            p[k].kaishitime, p[k].wanchengtime, p[k].zhouzhuangtime, p[k].daiquantime);
    }

    printf("执行顺序：\n");
    printf("%s", p[0].name);
    for(k = 1; k < N; k++)
    {
        printf("-->%s", p[k].name);
    }
}

// 根据进程到达时间进行排序，从小到大
void sort(rr *p, int N)
{
    int i,j;
    for(i = 1; i < N; i++)
    {
        rr t = p[i];
        for(j = i - 1; j >= 0 && ((t.daodatime < p[j].daodatime)||t.daodatime == p[j].daodatime&&t.fuwutime < p[j].fuwutime); j--)
            p[j+1] = p[j];
        p[j+1] = t;
    }
}


// 核心运行阶段
void run(rr *p, int N)
{
    float time_temp=0;
    int i;
    int j=0;
    int k=0;
    time_temp=p[0].daodatime;
    while(left)  //时间片运行的主循环代码
        {
            if(pattern==0)
                time_counter=time_counter*(N/left);
            for(i=0; i<N; i++)  //遍历一遍n个进程
            {
                if(p[i].daodatime>time_temp)
                {
                    time_temp=p[i].daodatime;
                }
                if(p[i].run_flag==0)//该进程还未结束
                {
                    if(p[i].start_flag==0)  //该条件成立则说明，该进程是第一次执行，记录开始执行时间
                    {
                        p[i].kaishitime=time_temp;
                        p[i].start_flag=1;
                       // left--;
                    }
                    if(p[i].run_time/time_counter>1)//至少有两倍的时间片未执行
                    {
                        p[i].run_time=p[i].run_time-time_counter;
                        time_temp=time_temp+time_counter;
                    }
                    else if(p[i].run_time-time_counter==0)//恰好在当前时间片结束
                    {
                        time_temp=time_temp+time_counter;
                        p[i].wanchengtime=time_temp;
                        p[i].run_flag=1;
                    //    p[i].run_time=copy_task[i].run_time;
                        left--;
                    }
                    else//仅剩下不足一倍的时间片
                    {
                        time_temp=time_temp+p[i].run_time;
                        p[i].wanchengtime=time_temp;
                        p[i].run_flag=1;
                    //    p[i].run_time=copy_task[i].run_time;
                        left--;
                    }
                }
            }
        }
            // 计算周转时间和带权周转时间
    for(k = 0; k < N; k++)
    {
        // 周转时间 = 完成时间 - 到达时间
        p[k].zhouzhuangtime = p[k].wanchengtime - p[k].daodatime;
        // 带权周转时间 = 周转时间/服务时间
        p[k].daiquantime = p[k].zhouzhuangtime/p[k].fuwutime;
    }
}

// 定义先来先服务函数
void rr_MAIN()
{
    int N;
    printf("请输入进程的数量:\n");
    scanf("%d",&N);
    printf("请输入时间片的长度:\n");
    scanf("%d",&time_counter);
    rr *p = new rr[N];
    left=N;
    input(p, N);// 输入
    sort(p, N);// 根据到达时间从小到大排序
    run(p, N);// 运行
    print(p, N);// 输出
    delete [] p;
}

int main()
{
    rr_MAIN();
    return 0;
}