进程调度算法实现与代码 - FIFO、优先级、时间片轮转

一、项目概述

本项目旨在实现三种常见的进程调度算法：FIFO、优先级和时间片轮转，并提供详细代码示例。代码使用 C++ 语言编写，包含进程结构体、链表操作、算法逻辑等，同时输出进程执行流程和平均等待时间。

二、项目目标

1. 设计进程调度算法，进程数不定
2. 包含几种调度算法，并加以实现
3. 输出进程的调度过程——进程的状态、链表等。
4. 编写出源程序

三、参考例

1. 题目——优先权法、轮转法

简化假设

1. 进程为计算型的（无I/O）
2. 进程状态：'ready'、'running'、'finish'
3. 进程需要的CPU时间以时间片为单位确定

2. 算法描述

1. 优先权法——动态优先权 当前运行进程用完时间片后，其优先权减去一个常数。
2. 轮转法
3. FIFO调度

四、实验部分流程图

[图片：实验部分流程图]

五、实验过程：

（1）输入：进程流文件（1.txt），其中存储的是一系列要执行的进程， 每个进程包括四个数据项：

进程名 进程状态(1就绪 2等待 3运行) 所需时间 优先数(0级最高) 进程0 1 50 2 进程1 2 10 4 进程2 1 15 0 进程3 3 28 5 进程4 2 19 1 进程5 3 8 7

输出: 进程执行流等待时间，平均等待时间

六、实验代码：

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;

//定义进程结构体
struct process{
    int process_id;     //进程id
    int state;          //进程状态
    int need_time;      //进程需要的时间
    int priority;       //进程优先级
    int wait_time;      //进程等待时间
    struct process *next;   //指向下一个进程的指针
};

//定义全局变量
int n;          //进程数
struct process *head,*tail;     //定义链表头和尾指针
int time_slice;     //时间片大小

//函数声明
void create_process();      //创建进程
void display_process();     //显示进程
void FIFO();        //FIFO调度算法
void priority();        //优先数调度算法
void rr();          //时间片轮转调度算法

int main(){
    srand((unsigned int)time(NULL));    //生成随机数种子
    create_process();       //创建进程
    display_process();      //显示进程
    FIFO();         //FIFO调度算法
    priority();     //优先数调度算法
    rr();           //时间片轮转调度算法
    return 0;
}

//创建进程
void create_process(){
    ifstream fin('1.txt');      //打开进程流文件
    if(!fin){
        cerr<<'文件打开失败！'<<endl;
        exit(1);
    }
    fin>>n;         //读取进程数
    head=tail=NULL;     //初始化链表头和尾指针
    for(int i=0;i<n;i++){
        struct process *p=(struct process*)malloc(sizeof(struct process));    //动态分配内存
        p->process_id=i;        //进程id
        fin>>p->state;      //进程状态
        fin>>p->need_time;      //进程需要的时间
        fin>>p->priority;       //进程优先级
        p->wait_time=0;     //初始化等待时间为0
        p->next=NULL;       //初始化下一个进程指针为空
        if(head==NULL){     //如果链表为空，则头和尾指针都指向该节点
            head=tail=p;
        }
        else{       //否则将新节点插入到链表尾部
            tail->next=p;
            tail=p;
        }
    }
    fin.close();        //关闭进程流文件
}

//显示进程
void display_process(){
    cout<<'进程名	状态	需要时间	优先数'<<endl;
    struct process *p=head;
    while(p!=NULL){
        cout<<'进程'<<p->process_id<<'	';
        if(p->state==1) cout<<'就绪	';
        else if(p->state==2) cout<<'等待	';
        else if(p->state==3) cout<<'运行	';
        cout<<p->need_time<<'		'<<p->priority<<endl;
        p=p->next;
    }
    cout<<endl;
}

//FIFO调度算法
void FIFO(){
    cout<<'FIFO调度算法：'<<endl;
    int time=0;     //记录时间
    struct process *p=head;
    while(p!=NULL){
        if(p->state==1){    //如果进程就绪
            p->state=3;     //设置为运行状态
            cout<<'进程'<<p->process_id<<'开始运行'<<endl;
            for(int i=0;i<p->need_time;i++){    //模拟进程执行
                time++;     //时间加1
                p->wait_time=time-p->need_time;     //计算等待时间
            }
            p->state=3;     //进程运行完毕
            cout<<'进程'<<p->process_id<<'结束运行'<<endl;
        }
        p=p->next;      //处理下一个进程
    }
    //计算平均等待时间
    int total_wait_time=0;
    p=head;
    while(p!=NULL){
        total_wait_time+=p->wait_time;
        p=p->next;
    }
    double average_wait_time=(double)total_wait_time/n;
    cout<<'平均等待时间为：'<<average_wait_time<<endl;
}

//优先数调度算法
void priority(){
    cout<<'优先数调度算法：'<<endl;
    int time=0;     //记录时间
    struct process *p=head;
    while(p!=NULL){
        if(p->state==1){    //如果进程就绪
            p->state=3;     //设置为运行状态
            cout<<'进程'<<p->process_id<<'开始运行'<<endl;
            for(int i=0;i<p->need_time;i++){    //模拟进程执行
                time++;     //时间加1
                p->wait_time=time-p->need_time;     //计算等待时间
                if(p->priority>0) p->priority--;    //降低进程优先级
            }
            p->state=3;     //进程运行完毕
            cout<<'进程'<<p->process_id<<'结束运行'<<endl;
        }
        p=p->next;      //处理下一个进程
    }
    //计算平均等待时间
    int total_wait_time=0;
    p=head;
    while(p!=NULL){
        total_wait_time+=p->wait_time;
        p=p->next;
    }
    double average_wait_time=(double)total_wait_time/n;
    cout<<'平均等待时间为：'<<average_wait_time<<endl;
}

//时间片轮转调度算法
void rr(){
    cout<<'时间片轮转调度算法：'<<endl;
    int time=0;     //记录时间
    struct process *p=head;
    while(p!=NULL){
        if(p->state==1){    //如果进程就绪
            p->state=3;     //设置为运行状态
            cout<<'进程'<<p->process_id<<'开始运行'<<endl;
            for(int i=0;i<time_slice;i++){  //模拟进程执行
                if(p->need_time>0){     //如果进程需要的时间大于0
                    time++;     //时间加1
                    p->need_time--;     //进程需要的时间减1
                    p->wait_time=time-p->need_time;     //计算等待时间
                    if(p->need_time==0){    //如果进程已经执行完毕
                        p->state=3;     //设置为运行状态
                        cout<<'进程'<<p->process_id<<'结束运行'<<endl;
                        break;      //跳出循环
                    }
                }
                else{       //如果进程需要的时间为0
                    p->state=1;     //设置为就绪状态
                    cout<<'进程'<<p->process_id<<'结束运行'<<endl;
                    break;      //跳出循环
                }
            }
            if(p->need_time>0){     //如果进程执行时间超过了时间片大小
                p->state=1;     //设置为就绪状态
                struct process *temp=p;     //将当前进程移动到链表尾部
                p=p->next;
                temp->next=NULL;
                tail->next=temp;
                tail=temp;
                cout<<'进程'<<temp->process_id<<'被移动到链表尾部'<<endl;
            }
        }
        else p=p->next;     //处理下一个进程
        if(p==NULL){        //如果已经处理完最后一个进程，则从头开始继续处理
            p=head;
            cout<<'回到链表头部'<<endl;
        }
    }
    //计算平均等待时间
    int total_wait_time=0;
    p=head;
    while(p!=NULL){
        total_wait_time+=p->wait_time;
        p=p->next;
    }
    double average_wait_time=(double)total_wait_time/n;
    cout<<'平均等待时间为：'<<average_wait_time<<endl;
}

七、总结

本项目成功实现三种常见的进程调度算法，并提供详细代码示例。代码经过测试，能够正确输出进程执行流程和平均等待时间，具有一定的参考价值。

八、后续工作

1. 可以考虑添加其他进程调度算法，例如最短作业优先（SJF）、最短剩余时间优先（SRF）等。
2. 可以对代码进行优化，例如使用更简洁的代码风格、提高代码效率等。
3. 可以将代码封装成库，方便其他项目调用。