【操作系统/C++】简易的时间片轮转调度/优先级调度算法

#include <iostream>
using namespace std;
#include <iomanip>

typedef struct PCB//进程控制块
{
    char pname[10];//进程名
    int priority;//优先数(优先数越大，优先级越高)
    int btime;//需要运行时间
    int rtime;//已用CPU时间
    int atime;//进程到达时间
    char state;//进程状态(R为就绪状态，C为结束状态)
    bool operator>(const PCB a)const 
    {
        return (priority > a.priority || atime < a.atime);
    }
}PCB;

typedef struct PCBlist//进程链表
{
    PCB data;
    struct PCBlist* next;
}PNODE;

void InsertSort(PNODE** head, PCB x);//插入排序
void InitProcess(PNODE** head);//初始化进程
void ShowProcess(PNODE** head,int a);//展示进程信息
void DropProcess(PNODE** head, PNODE** end);//进程退出就绪队列
void HPF(PNODE** head, PNODE** end);//HPF调度
void RunHPF(PNODE** ready, PNODE** end);//HPF相关处理
void InitRR(PNODE** head);//初始化轮转进程
void InsertTail(PNODE** head, PCB x);//尾部插入
void RR(PNODE** head, PNODE** end,int time);//RR调度
void RunRR(PNODE** head, PNODE** end,int time);//RR调度相关处理
void destroyend(PNODE** end);//销毁结束队列

int main()
{
    int x = 0, y = 1,time = 0;
    PNODE* ready = NULL,* end = NULL;
    cout << "处理机调度实验" << endl;
    while (y)
    {
        cout << "——————请输入————————\n0:最高优先级优先调度\n1:简单轮转法调度" << endl;
        cin >> x;
        if (x == 0) RunHPF(&ready, &end);
        else if (x == 1)
        {
            cout << "请输入时间片大小：";
            cin >> time;
            RunRR(&ready, &end, time);
        }
        else cout << "输入错误!请输入0或1!\n";
        cout << "\n——————要继续进行调度吗？————————\n0:退出\n1:继续" << endl;
        cin >> y;
    }
    cout << "程序结束！" << endl;
    system("pause");
}

void InsertSort(PNODE** head, PCB x)
/*按进程优先级插入排序
head：头指针 x：要插入的结点
*/
{
    PNODE* p1, * p2, * p;
    p = new PNODE;
    p->data = x;
    p->next = NULL;
    if (!*head)//若链表为空
        *head = p;
    else
    {
        p2 = p1 = *head;
        while (p2 != NULL && (p2->data > p->data))//寻找p的插入位置
        {
            p1 = p2;
            p2 = p2->next;
        }
        if (p2 == NULL)//若p的优先级最低
            p1->next = p;//插入至尾部
        else if (p1 == p2)//若p的优先数最高
        {
            p->next = *head;//插入至首部
            *head = p;
        }
        else//否则插入至p1,p2中间
        {
            p->next = p2;
            p1->next = p;
        }
    }
}
void InitProcess(PNODE** head)
/*初始化进程链表*/
{
    int n;
    PCB process = {"None",0,0,0,0,'R'};
    cout << "—————————最高优先级优先调度——————————\n";
    cout << "请输入进程总数:";
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cout << "第" << i + 1 << "个进程的名称、优先数、所需运行时间为:" << endl;
        cin >> process.pname >> process.priority >> process.btime;
        InsertSort(head, process);
    }
    cout << "—————————正在生成就绪队列———————————\n" << endl;
}
void ShowProcess(PNODE** head,int a)
/*显示就绪队列中的进程信息*/
{
    PNODE* p = *head;
    if (p)
    {
        cout << "———————————就绪队列—————————————" << endl;
        if (a == 0)
        {
            cout << "\n进程名\t优先数\t所需运行时间\t已用CPU时间\t进程状态" << endl;
            do
            {
                cout << setw(4) << (p->data).pname
                    << setw(8) << (p->data).priority
                    << setw(10) << (p->data).btime
                    << setw(15) << (p->data).rtime
                    << setw(16) << (p->data).state << endl;
                p = p->next;
            } while (p);
            cout << "\n————————————————————————————" << endl;
        }
        else
        {
            cout << "\n进程名\t到达时间  所需运行时间\t已用CPU时间\t进程状态" << endl;
            do
            {
                cout << setw(4) << (p->data).pname
                    << setw(8) << (p->data).atime
                    << setw(12) << (p->data).btime
                    << setw(14) << (p->data).rtime
                    << setw(15) << (p->data).state << endl;
                p = p->next;
            } while (p);
            cout << "\n————————————————————————————" << endl;
        }
    }
}
void DropProcess(PNODE** head, PNODE** end)
/*进程进入结束队列*/
{
    PNODE* p = *head;
    PNODE* x = new PNODE;
    x->data = p->data;
    if (!*end)//若结束队列为空
    {
        x->next = *end;
        *end = x;
    }
    else//若结束队列不为空
    {
        PNODE* p1 = *end;
        while (p1->next) p1 = p1->next;
        p1->next = x;//插入至尾部
        x->next = NULL;
    }
    *head = (*head)->next;
    delete p;
    p = nullptr;
    PNODE* e = *end;
    cout << "已经结束的进程为：";
    while (e)
    {
        cout << (e->data).pname << " ";
        e = e->next;
    }
    cout << endl;
}
void HPF(PNODE** head, PNODE** end)
/*最高优先级调度*/
{
    while (*head)//若就绪队列不为空
    {
        PNODE* p = *head;//p为当前正在运行的进程
        cout << "当前正在运行的进程为：" << (p->data).pname << endl;
        (p->data).priority--;//优先数减一
        (p->data).rtime++;//已用CPU时间加一
        if ((p->data).btime != (p->data).rtime)//若进程未完成
        {
            cout << "时间片结束，该进程未完成。" << endl;
            *head = (*head)->next;
            InsertSort(head, p->data);//将进程重新加入就绪队列
        }
        else//若进程已完成
        {
            cout << "时间片结束，该进程已完成！" << endl;
            (p->data).state = 'C';//状态置为完成
            DropProcess(head, end);//退出就绪队列，移入结束队列
        }
        ShowProcess(head,0);
    }
    cout << "————————进程已全部完成！————————————" << endl;
}
void RunHPF(PNODE** ready, PNODE** end)
{
    InitProcess(ready);
    ShowProcess(ready,0);
    HPF(ready, end);
    destroyend(end);
}
void InitRR(PNODE** head)
/*初始化轮转进程列表*/
{
    int n;
    PCB process = { "None",0,0,0,0,'R'};
    cout << "—————————简单轮转法调度————————————\n";
    cout << "请输入进程总数:";
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cout << "第" << i + 1 << "个进程的名称、到达时间、所需运行时间为:" << endl;
        cin >> process.pname >> process.atime >> process.btime;
        InsertSort(head, process);
    }
    cout << "—————————正在生成就绪队列———————————\n" << endl;
}
void InsertTail(PNODE** head, PCB x)
{
    PNODE* p;
    p = new PNODE;
    p->data = x;
    p->next = NULL;
    if (!*head)
        *head = p;
    else
    {
        PNODE* p1;
        p1 = *head;
        while (p1->next) p1 = p1->next;
        p1->next = p;
    }

}
void RR(PNODE** head, PNODE** end,int time)
{
    while (*head)//若就绪队列不为空
    {
        PNODE* p = *head;//p为当前正在运行的进程
        cout << "当前正在运行的进程为：" << (p->data).pname << endl;
        if ((p->data).rtime + time > (p->data).btime)//如果进程即将完成
        {
            int nextq = (p->data).rtime + time - (p->data).btime;//但时间片未用完
            if (p->next) ((p->next)->data).rtime += nextq;//则给下一个进程使用
        }
        (p->data).rtime += time;//已用CPU时间加时间片
        if ((p->data).btime > (p->data).rtime)//若进程未完成
        {
            
            cout << "时间片结束，该进程未完成。" << endl;
            *head = (*head)->next;
            InsertTail(head, p->data);//将进程送回就绪队列末尾
        }
        else//若进程已完成
        {
            cout << "时间片结束，该进程已完成！" << endl;
            (p->data).state = 'C';//状态置为完成
            DropProcess(head, end);//退出就绪队列，移入结束队列
        }
        ShowProcess(head,1);
    }
    cout << "————————进程已全部完成！————————————" << endl;
}
void RunRR(PNODE** ready, PNODE** end,int time)
{
    InitRR(ready);
    ShowProcess(ready,1);
    RR(ready, end,time);
    destroyend(end);
}
void destroyend(PNODE** end)
{
    PNODE* p;
    while ((*end))
    {
        p = *end;
        *end = (*end)->next;
        delete p;
    }
}

本文为原创文章，转载请注明出处！

打赏作者