动态优先权算法

1.设计目的与要求

1.1设计目的

通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。

1.2设计要求

本实验要求学生独立地用C或C++语言编写一个简单的进程管理程序，其主要部分是进程调度。调度算法可由学生自行选择，如基于动态优先级的调度算法。通过本实验可加深学生对进程各种状态的转化和各种调度算法的理解，提高系统程序设计能力。

2.设计思想及系统平台

2.1设计思想

1）数据结构

用来标识进程的进程控制块使用结构体pcb来描述，包含以下字段：进程标识数id；进程优先数priority；进程已占用的CPU时间cputime；进程还需占用的CPU时间alltime；进程的阻塞时间startblock；进程被阻塞的时间blocktime；进程状态state，0为就绪,1为阻塞,2为完成。

进程队列有三个，分别为就绪队列Readyqueue、阻塞队列Blockqueue、结束队列Finishqueue，类型为vector<pcb>。

2）算法

基于动态优先级的调度算法。

3）优先数改变原则

进程在就绪队列中呆一个时间片，优先数增加1，进程每运行一个时间片优先数减3。

2.2系统平台及使用语言

CodeBlocks，C++

3.详细算法描述

就绪转结束：当运行进程的alltime<=0时，进程结束；

就绪转阻塞：当运行进程的startblock为0时，进程阻塞；

阻塞转就绪：阻塞进程的blocktime为0时，进程转为就绪状态。

4.源代码

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
struct pcb
{
    int id ;
    int priority;//优先权
    int cputime;//已占用的cpu时间片
    int alltime;//还需要的时间
    int startblock;//运行多少个时间片之后开始进入阻塞队列
    int blocktime;//阻塞的时间
    int state;//状态,0为就绪,1为阻塞,2为完成
};
vector<pcb> Readyqueue; //就绪队列
vector<pcb> Blockqueue;//阻塞队列
vector<pcb> Finishqueue;//结束队列
struct pcb process[5]={
	{0,9,0,3,2,3,0},
	{1,38,0,3,-1,0,0},
	{2,30,0,6,-1,0,0},
	{3,29,0,3,-1,0,0},
	{4,0,0,4,-1,0,0}
};
//排序
void sort()
{
    if(Readyqueue.empty()&&Blockqueue.empty())
        return;
    else
    {
        for(unsigned i=0;i<Readyqueue.size()-1;i++)
        {
            for(unsigned j=i+1;j<Readyqueue.size();j++)
            {
                //优先权低就交换顺序
                if (Readyqueue[i].priority < Readyqueue[j].priority)
                {
                    swap(Readyqueue[i],Readyqueue[j]);
                }
            }
        }
    }
}
void print(vector<pcb> tempqueue)
{
    cout<<"id | priority | cputime | alltime ";
    cout<<"| startblock | blocktime | state"<<endl;
    for(unsigned i=0;i<tempqueue.size();i++)
    {
        printf("%-6d",tempqueue[i].id);
        printf("%-11d",tempqueue[i].priority);
        printf("%-10d",tempqueue[i].cputime);
        printf("%-10d",tempqueue[i].alltime);
        printf("%-13d",tempqueue[i].startblock);
        printf("%-12d",tempqueue[i].blocktime);
        printf("%-6d",tempqueue[i].state);
        printf("\n");
    }
}
void display()
{
    if(!Readyqueue.empty())
    {
        cout<<"正在运行："<<Readyqueue[0].id<<endl;
        cout<<"就绪队列:";
        for(unsigned i=1;i<Readyqueue.size();i++)
        {
            if(Readyqueue[i].state==0)
            {
                cout<<"->"<<Readyqueue[i].id;
            }
        }
        cout<<endl;
    }
    if(!Blockqueue.empty())
    {
        cout<<"阻塞队列:";
        for(unsigned i=0;i<Blockqueue.size();i++)
        {
            if(Blockqueue[i].state==1)
            {
                cout<<"->"<<Blockqueue[i].id;
            }
        }
        cout<<endl;
    }
    if (!Readyqueue.empty())
    {
        cout<<"就绪队列"<<endl;
        print(Readyqueue);
    }
    if (!Blockqueue.empty())
    {
        cout<<"阻塞队列"<<endl;
        print(Blockqueue);
    }
    if (!Finishqueue.empty())
    {
        cout<<"完成队列"<<endl;
        print(Finishqueue);
    }
}
void run()
{
	if(!Readyqueue.empty())
    {
        Readyqueue[0].priority-=3;
        Readyqueue[0].alltime--;
        Readyqueue[0].cputime++;
        //判断是否结束
        if(Readyqueue[0].alltime<=0)
        {
            //就绪转结束队列
            Readyqueue[0].state=2;
            Finishqueue.push_back(Readyqueue[0]);
            Readyqueue.erase(Readyqueue.begin()+0);
        }
        //判断是否进行阻塞
        if(Readyqueue[0].startblock>=0&&Readyqueue[0].blocktime>0)
        {
            Readyqueue[0].startblock--;
            if(Readyqueue[0].startblock==0)//就绪转阻塞队列
            {
                Readyqueue[0].state=1;
                Blockqueue.push_back(Readyqueue[0]);
                Readyqueue.erase(Readyqueue.begin()+0);
            }
        }
        //修改不在运行的线程情况
        for (unsigned i=1;i<Readyqueue.size();i++)
        {
            Readyqueue[i].priority++;
        }
    }
    //阻塞转就绪队列
	if(!Blockqueue.empty())
	{
        for(unsigned i=0;i<Blockqueue.size();i++)
        {
            Blockqueue[i].blocktime--;
            if(Blockqueue[i].blocktime==0)
            {
                Blockqueue[i].state=0;
                Readyqueue.push_back(Blockqueue[i]);
                Blockqueue.erase(Blockqueue.begin()+0);
            }
        }
	}
}
int main()
{
    for(int i=0;i<5;i++)
    {
        Readyqueue.push_back(process[i]);
    }
    int sign=0;
	while(!Readyqueue.empty())
	{
	    sign++;
	    cout<<endl<<endl<<"时间片："<<sign<<endl;
		sort();
		run();
		display();
	}
	cout<<"运行时序为";
	for(int i=0;i<5;i++)
    {
        cout<<Finishqueue[i].id<<"->";
    }
    cout<<"END"<<endl;
    return 0;
}