这学期刚开始学习操作系统,收到一个作业,百度关于高响应比优先(HRRN,Highest Response Ratio Next)的CPU进程调度模拟算法,基本思想:短作业优先调度算法
+
动态优先权机制;既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务(FCFS,First
Come First Served)和最短作业优先(SJF,Shortest Job
First)两种算法的特点。


#includestdio.h#includestdlib.htypedefstructk{charname[10];floatjr_time;//进入时间floatyx_time;//运行时间floatjs_time;//结束时间floatdd_time;//等待时间floatzz_time;//周转时间intsx;//作业序号floatxyb;//响应比charstate;//进程的状态structk*next;}PCB;PCB*creat(){//模仿数据结构造一个进程链表PCB*h,*tail,*p,*max;inti;h=(PCB*)malloc(sizeof(PCB));h-next=NULL;tail=h;printf(“请输入4个进程.”);for(i=0;i4;i++){p=(PCB*)malloc(sizeof(PCB));printf(“\n请输入进程名:”);scanf(“%s”,p-name);printf(“\n请输入进程进入时间:”);scanf(“%f”,p-jr_time);printf(“\n请输入进程运行时间:”);scanf(“%f”,p-yx_time);p-js_time=0;//初始化进程的结束时间p-dd_time=0;//初始化进程的等待时间p-zz_time=0;//初始化进程的周转时间p-sx=0;p-xyb=0;//初始化进程的响应比p-state=’R’;p-next=NULL;tail-next=p;tail=p;}returnh;}intpd(PCB*h){//该函数判断进程队列中是否还有处于就绪状态的进程,若存在,则返回1PCB*p;for(p=h-next;p!=NULL;p=p-next)if(p-state==’R’)return1;return0;}PCB*cz(PCB*h){//查找响应比最大的进程PCB*p,*max;p=h-next;max=p;while(p!=NULL){if(p-state==’C’)p=p-next;else{if((max-xyb)=(p-xyb))p=p-next;else{max=p;p=p-next;}}}returnmax;}PCB*czMin(PCB*金沙国际官网 ,h){//初始时,查找进程链表中入井时间最短的作业PCB*p,*min;p=h-next;min=p;//初始时设第一个作业入井时间最短while(p!=NULL){if((min-jr_time)=(p-jr_time))p=p-next;else{min=p;p=p-next;}}returnmin;}voidexecute(PCB*h){PCB*p,*max,*min;floattime;inti,n;n=1;p=h-next;//使p指向第一个作业min=czMin(h);//查找作业链表中入井时间最短的作业min-state=’C’;//将入井时间最短的作业状态置为’C’min-sx=n;//此时入井时间最短的作业为第一个执行的作业min-js_time=(min-jr_time)+(min-yx_time);//第一个作业的结束时间time=min-js_time;min-zz_time=(min-js_time)-(min-jr_time);//第一个作业的周转时间while(p!=NULL){while(p!=NULL){//计算响应比if(p-state==’C’)p=p-next;//如果该进程状态为执行时,则看下一个进程else{if(time=p-jr_time){//如果在第一个进程结束之前有其它进程进入,则做如下操作p-dd_time=time-(p-jr_time);//进程的等待时间为前一个进程的结束时间-该进程的进入时间p-xyb=(p-dd_time+p-yx_time)/(p-yx_time);//计算当前进程的响应比p=p-next;}elsep=p-next;//如果进程的进入时间大于前一个进程的结束时间,则暂时不用管}}max=cz(h);//查找响应比最大的进程max-state=’C’;n=n+1;max-sx=n;max-js_time=time+(max-yx_time);//此时进程的结束时间为上一个进程的结束时间+当前进程的运行时间max-zz_time=(max-js_time)-(max-jr_time);//计算当前响应比最高的进程的周转时间time=max-js_time;//更改结束时间i=pd(h);//判断是否所有进程全部执行完,注意:若没有此函数,则不能判断进程是否全部执行完if(i!=1)break;//若进程全部执行完,则跳出这个循环elsep=h-next;//让P回到第一个进程处,目的:为了进行下一次进程的执行}}voidprint(PCB*h){PCB*p;printf(“序号进程进入时间运行时间结束时间周转时间进程状态\n”);for(p=h-next;p!=NULL;p=p-next){printf(“%d\t”,p-sx);printf(“%s\t”,p-name);printf(“%.1f\t”,p-jr_time);printf(“%.1f\t”,p-yx_time);printf(“%.1f\t”,p-js_time);printf(“%.1f\t”,p-zz_time);printf(“%c\t\n”,p-state);}}floatpj(PCB*h){//计算平均周转时间PCB*p;floatsum,pjsum;sum=0;p=h-next;while(p!=NULL){sum=sum+p-zz_time;p=p-next;}pjsum=sum*1.0/4;returnpjsum;}intmain(){PCB*h;floatsum;h=creat();execute(h);print(h);sum=pj(h);printf(“平均周转时间为:%.1f”,sum);}

算法:深度优先算法和广度优先算法(基于邻接矩阵)

算法描述:

短作业(进程)优先调度算法(SJF),是指对短作业或短进程优先调度的算法。它们可以分
别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个
估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队
列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完
成,或发生某事件而被阻塞放弃处理机时再重新调度

  之后经过多番揣摩… …决定界面用命令行算了,反正啥也不会…

该算法实际上是一种动态优先调度算法,它以相应比作为作业或进程的动态优先权,其目的是既照顾短作业,又考虑到作业的等待时间,使长作业不会长期等待;但每次调度前,都要进行响应比计算,会增加系统开销。

1.写在前面

  图的存储结构有两种:一种是基于二维数组的邻接矩阵表示法。

            另一种是基于链表的的邻接表。

  在邻接矩阵中,可以如下表示顶点和边连接关系:

    金沙国际官网 1金沙国际官网 2

说明:

  将顶点对应为下标,根据横纵坐标将矩阵中的某一位置值设为1,表示两个顶点向联接。

  图示表示的是 style=”color: #ff0000″>无向图的邻接矩阵,从中我们可以发现它们的 style=”color: #ff0000″>分布关于斜对角线对称

  我们在下面将要讨论的是下图的两种遍历方法(基于矩阵的):

     金沙国际官网 3金沙国际官网 4

  我们已经说明了我们要用到的是邻接矩阵表示法,那么我首先要来构造图:

  矩阵图的数据结构如下表示:

#define MaxVnum 50
typedef double AdjMatrix[MaxVnum][MaxVnum];   //表示一个矩阵,用来存储顶点和边连接关系
typedef struct {
    int vexnum,arcnum;               //顶点的个数,边的个数
    AdjMatrix arcs;                 //图的邻接矩阵
}Graph;

  这样我们可以首先来创建上述图,为了方便,我们直接在代码中书写矩阵,而不用每次调试手动输入了

void CreateGraph(Graph &G)
{
    G.vexnum=8;
    G.arcnum=9;
    G.arcs[0][1]=1;
    G.arcs[0][2]=1;
    G.arcs[1][3]=1;
    G.arcs[1][4]=1;
    G.arcs[2][5]=1;
    G.arcs[2][6]=1;
    G.arcs[3][1]=1;
    G.arcs[3][7]=1;
    G.arcs[3][6]=1;
    G.arcs[4][1]=1;
    G.arcs[4][7]=1;
    G.arcs[5][2]=1;
    G.arcs[5][6]=1;
    G.arcs[5][5]=1;
    G.arcs[6][2]=1;
    G.arcs[6][5]=1;
    G.arcs[7][3]=1;
    G.arcs[7][4]=1;
}

  这样我们就已经完成了准备工作,我们可以正式来学习我们的两种遍历方式了。

代码:

#include <iostream>
#include<iomanip>
#include<queue>
#include<list>
#include<algorithm>

using namespace std;

class PCB
{
public:
    int pid;
    int arrivalTime;
    int needTime;
    int leaveTime;

    PCB()
    {
    }
    PCB(int pid,int arriveTime,int needTime)
    {
        this->pid=pid;
        this->arrivalTime=arriveTime;
        this->needTime=needTime;
        leaveTime=0;
    }

    bool operator < (const PCB &a)const
    {
        return needTime>a.needTime;
    }
    bool operator == (const PCB &a)const
    {
////        if(pid==a.pid){
////            return true;
////        }
////        else
////            return false;
        return pid==a.pid?true:false;
    }
};

class SJF
{
public:
    priority_queue<PCB> pq;
    list<PCB> allNeedList;
    list<PCB> allFinishList;

    void prepareProcess(int pid,int arriveTime,int needTime);
    void schedule();
    void printFinishList();
};
void SJF::schedule()
{
    int currentTime=0,finishTime=-1;
    bool isBusy=false;
    PCB currentProcess;
    while (true)
    {

        if(currentTime==finishTime)  //这里是每秒都做。currentTime++,故==
        {
            isBusy=false;
            currentProcess.leaveTime=currentTime;
            allFinishList.push_back(currentProcess);
            cout<<"已结束 ";
            cout<<"周转时间:"<<finishTime-currentProcess.arrivalTime;
            cout<<"带权周转时间:"<<(finishTime-currentProcess.arrivalTime)/(double)currentProcess.needTime<<endl;
        }
      //从链表中把到达的进程假如有先队列
        for(list<PCB>::iterator i=allNeedList.begin(); i!=allNeedList.end();)
        {
            if((*i).arrivalTime<=currentTime)
            {
                pq.push(*i);
                allNeedList.erase(i++);
            }
            else
            {
                i++;
            }
        }
        if(!isBusy&&!pq.empty())
        {
            currentProcess=pq.top();
            pq.pop();
            finishTime=currentProcess.needTime+currentTime;
            isBusy=true;
            cout<<"进程"<<currentProcess.pid<<"开始占用处理机,到达时间:"<<currentProcess.arrivalTime<<",需要时间:"<<currentProcess.needTime<<",开始时间:"<<currentTime<<"\n";
        }

        currentTime++;
        //最后所有进程结束,退出
        if(allNeedList.empty()&&pq.empty()&&!isBusy)
            break;
    }

}

void SJF::prepareProcess(int pid,int arriveTime,int needTime)
{
    PCB newProcess(pid,arriveTime,needTime);
    allNeedList.push_back(newProcess);
}


void SJF::printFinishList()
{
    allFinishList.sort();
    setiosflags(ios::left);
    cout<<setw(15)<<"进程"<<setw(15)<<"到达时间"<<setw(15)<<"服务时间"<<setw(15)<<"周转时间"<<setw(15)<<"带权周转时间\n";
    for (list<PCB>::iterator i=allFinishList.begin(); i!=allFinishList.end(); i++)
    {
        cout<<setw(15)<<(*i).pid<<setw(15)<<(*i).arrivalTime<<setw(15)<<(*i).needTime<<setw(15)<<(*i).leaveTime-(*i).arrivalTime<<setw(15)<<((*i).leaveTime-(*i).arrivalTime)/(double)(*i).needTime<<"\n";
    }
}


int main()
{
    SJF one;
//    one.prepareProcess(1,1,4);
//    one.prepareProcess(2,2,3);
//    one.prepareProcess(3,3,7);
//    one.prepareProcess(4,4,2);
//    one.prepareProcess(5,5,1);
//    one.prepareProcess(6,6,4);
//    one.prepareProcess(7,7,2);
//    one.prepareProcess(8,8,2);

    one.prepareProcess(1,2,4);
    one.prepareProcess(2,2,3);
    one.prepareProcess(3,1,7);
    one.prepareProcess(4,4,2);
    one.prepareProcess(5,6,1);
    one.prepareProcess(6,8,4);
    one.prepareProcess(7,11,2);
    one.prepareProcess(8,13,2);

    one.schedule();
    one.printFinishList();
    return 0;
}

  关于响应比:

响应比 = 相应时间 / 要求服务时间 = 等待时间 + 要求服务时间 /
要求服务时间

2.深度优先遍历算法

注意事项

1.将程序信息使用PCB的类存储,接近操作系统工作原理
2.程序写的比较顺,但是对基本的语法有些不熟,比如stl中的priority_queue,list。优先队列是从大到小排列,要从小到大排列故重载<运算符,用erase函数,故重载==运算符
3.#include<iomanip> setw \n不一样

    RR =  (预计运行时间 + 等待时间) / 预计运行时间 = 1 +
等待时间/预计运行时间;

  分析深度优先遍历

    从图的某个顶点出发,访问图中的所有顶点且使每个顶点仅被访问一次。这一过程叫做图的遍历。

    深度优先搜索的思想:

      ①访问顶点v;
      ②依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
      ③若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

    比如:

    金沙国际官网 5

    在这里为了区分已经访问过的节点和没有访问过的节点,我们引入一个一维数组bool
visited[MaxVnum]用来表示与下标对应的顶点是否被访问过,

流程:
☐ 首先输出 V1,标记V1的flag=true;
☐ 获得V1的邻接边 [V2 V3],取出V2,标记V2的flag=true;
☐ 获得V2的邻接边[V1 V4
V5],过滤掉已经flag的,取出V4,标记V4的flag=true;
☐ 获得V4的邻接边[V2
V8],过滤掉已经flag的,取出V8,标记V8的flag=true;
☐ 获得V8的邻接边[V4
V5],过滤掉已经flag的,取出V5,标记V5的flag=true;

此时发现V5的所有邻接边都已经被flag了,所以需要回溯。(左边黑色虚线,回溯到V1,回溯就是下层递归结束往回返)
金沙国际官网 6
☐ 回溯到V1,在前面取出的是V2,现在取出V3,标记V3的flag=true;
☐ 获得V3的邻接边[V1 V6
V7],过滤掉已经flag的,取出V6,标记V6的flag=true;
☐ 获得V6的邻接边[V3
V7],过滤掉已经flag的,取出V7,标记V7的flag=true;

此时发现V7的所有邻接边都已经被flag了,所以需要回溯。(右边黑色虚线,回溯到V1,回溯就是下层递归结束往回返)

  响应比高者优先进行调度;

  深度优先搜索的代码

bool visited[MaxVnum];
void DFS(Graph G,int v)
{
    visited[v]= true; //从V开始访问,flag它
    printf("%d",v);    //打印出V
    for(int j=0;j<G.vexnum;j++) 
        if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点
            DFS(G,j); //递归调用,如果所有节点都被访问过,就回溯,而不再调用这里的DFS
}

void DFSTraverse(Graph G) {
    for (int v = 0; v < G.vexnum; v++)
        visited[v] = false; //刚开始都没有被访问过

    for (int v = 0; v < G.vexnum; ++v)
        if (visited[v] == false) //从没有访问过的第一个元素来遍历图
            DFS(G, v);
}

 

 3.广度优先搜索算法

  关于要求中的周转时间、带权周转时间、平均周转时间和平均带权周转时间:

    分析广度优先遍历    

      所谓广度,就是一层一层的,向下遍历,层层堵截,还是这幅图,我们如果要是广度优先遍历的话,我们的结果是V1
V2 V3 V4 V5 V6 V7 V8。

      金沙国际官网 3

      广度优先搜索的思想:

         ① 访问顶点vi ;

         ② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ;

         ③
依次从这些邻接点(在步骤②中访问的顶点)出发,访问它们的所有未被访问的邻接点;
依此类推,直到图中所有访问过的顶点的邻接点都被访问;

   说明:

      为实现③,需要保存在步骤②中访问的顶点,而且访问这些顶点的邻接点的顺序为:先保存的顶点,其邻接点先被访问。
这里我们就想到了用标准模板库中的queue队列来实现这种先进现出的服务。

      老规矩我们还是走一边流程:

   说明: 

    
☐将V1加入队列,取出V1,并标记为true(即已经访问),将其邻接点加进入队列,则
<—[V2 V3] 

    
☐取出V2,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[V3 V4 V5]

☐取出V3,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[V4 V5 V6 V7]

☐取出V4,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[V5 V6 V7 V8]

☐取出V5,并标记为true(即已经访问),因为其邻接点已经加入队列,则
<—[V6 V7 V8]

☐取出V6,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[V7 V8]

☐取出V7,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[V8]

☐取出V8,并标记为true(即已经访问),将其未访问过的邻接点加进入队列,则
<—[]

    周转时间 =(作业完成的时间 – 作业提交时间);

  广度优先搜索的代码

#include <queue>
using namespace std;
....
void BFSTraverse(Graph G)
{
    for (int v=0;v<G.vexnum;v++) //先将其所有顶点都设为未访问状态
        visited[v]=false;
    queue<int> Q;
    for(int v=0;v<G.vexnum;v++)    
    {
        if(visited[v]==false)   //若该点没有访问
        {
            Q.push(v);    //将其加入到队列中
            visited[v]=true;
            while (!Q.empty())  //只要队列不空,遍历就没有结束
            {
                int t =Q.front();  //取出对头元素
                Q.pop();
                printf(" %d ",t+1);  
                for(int j=0;j<G.vexnum;j++) //将其未访问过的邻接点加进入队列
                    if(G.arcs[t][j]==1&&visited[j]== false)
                    {
                        Q.push(j);
                        visited[j]=true; //在这里要设置true,因为这里该顶点我们已经加入到了队列,为了防止重复加入!
                    }
            }
        }
    }
}

    带权周转时间 = 作业周转时间 / 作业运行时间;

 两种算法的复杂度分析

  深度优先

    数组表示:查找所有顶点的所有邻接点所需时间为O(n2),n为顶点数,算法时间复杂度为O(n2)
  

  广度优先

    数组表示:查找每个顶点的邻接点所需时间为O(n2),n为顶点数,算法的时间复杂度为O(n2)

      

    平均周转时间 = (周转时间1+周转时间2+…+周转时间n)/ n;

    平均带权周转时间
= (带权周转时间1+带权周转时间2+…+带权周转时间n)/ n;

 

  开始,用vector存储提交的作业结构体指针,自己设置一个系统时间,毕竟模拟不可能时间流速一毛一样,接下来就是毫无技术含量的选择了,关于测试数据,想了想好难输,还得自己编,于是用随机函数产生数据;再在主函数参数中提供一个传递生成数据数量的参数。

  说到这里得说一下,关于java老师(没错,java老师)说的关于main()的一些情况:

1 int main(int argc, char** argv){ ////argc为参数个数, argv为接下来传的参数
2     ...
3     return 0;
4 }

 

比如在命令行中调用该函数,***.exe
100,此时有两个参数,一个为”***.exe”,
另一个就是”100″了,分别在argv[0]和argv[1]中。

  首先是数据生成,用为要求格式,所以要小处理一下,感觉这种方法可以在刷ACM题被题目玄学时使用,一个为标准代码,一个为自己的代码,目前未试过:

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 
 4 int ch_to_int(char* s){
 5     int ans = 0, len = strlen(s);
 6     for(int i = 0; i < len; i++) ans = ans*10 + s[i]-'0';
 7     return ans;
 8 }
 9 int main(int argc, char** argv){
10     int k, N, tj/*0~23*/, ys/*0~59*/, tmp;
11     freopen("test.txt", "w", stdout);
12     srand(time(NULL));   //以系统时间为种子生成真正的随机数
13     N = k = ch_to_int(argv[1]);
14     while(k--){
15         tmp = (rand() + 24)%24 * 100 + (rand() + 6)%6*10 + (rand() + 10)%10;
16         printf("%04d %d\n", tmp, (rand() + N)%N + 1);
17     }
18     return 0;
19 }

 

  调度算法:

 1 #include "bits/stdc++.h"
 2 #include "windows.h"
 3 using namespace std;
 4 typedef long long ll; 
 5 
 6 //(所有时间以分钟为单位存储,需要时转化) 
 7 
 8 ll systemTime;    //自定义系统当前时间
 9 
10 struct Task{
11     int Tij; //提交时间 
12     int Ysi; //预计运行时间 
13     ll waitingTime;  //等待时间
14     int id; //作业号
15     
16     ll prior(){
17         return 1 + waitingTime*1.0/Ysi;
18     }
19     
20     Task(int T, int Y){
21         Tij = T;
22         Ysi = Y;
23         waitingTime = 0;
24     }
25     ll aroundTime(){
26         return systemTime - Tij + Ysi;
27     }
28     
29     double priorTime(){
30         return aroundTime()*1.0/Ysi;
31     }
32     void disp(int ord){
33         printf("--调度次序: %d --作业号: %04d --调度时间:%02d%02d --周转时间: %d min(s) --带权周转时间%.2f  ...\n", 
34             ord, id, (systemTime/100 + systemTime/60)%24, systemTime%60, aroundTime(), priorTime());
35     }
36 };
37 
38 int cmp1(const Task* a, const Task* b){
39     return (a->Tij) < (b->Tij);
40 }
41 
42 int main(){
43     vector<Task*> taskArr;    ///以不定长数组存储作业队列
44     
45     int Tij, Ysi, order;
46     ll ave_aroundTime = 0;
47     double ave_prior_aroundTime = 0;
48     
49     freopen("test.txt", "r", stdin);
50     system(".\\生成测试数据.exe 1024");    //调用测试数据生成程序
51     
52     while(cin>>Tij>>Ysi) taskArr.push_back(new Task(Tij%100 + Tij/100*60, Ysi));
53     
54     ////按提交时间进行排序并编号 
55     sort(taskArr.begin(), taskArr.end(), cmp1);
56     std::vector<Task*>::iterator pos;
57     for(pos = taskArr.begin(); pos != taskArr.end(); pos++){
58         (*pos)->id = pos - taskArr.begin();
59     }
60     
61     std::vector<Task*>::iterator willRun;  //指向即将运行程序 
62     systemTime = (*taskArr.begin())->Tij;    ///将系统当前时间设置为最早提交的作业时间 
63     order = -1;
64     while(!taskArr.empty()){
65         bool flag = false; ///判定是否有新的程序提交 
66         willRun = taskArr.begin();
67         for(pos = taskArr.begin(); pos != taskArr.end(); pos++){
68             if((*pos)->Tij > systemTime) break;
69             willRun = (*willRun)->prior() < (*pos)->prior() ? pos : willRun;
70             flag = true;
71         }
72         if(!flag){
73             willRun = taskArr.begin();
74             systemTime = (*willRun)->Tij;
75         }
76         
77         (*willRun)->disp(++order);
78         
79         ave_aroundTime += (*willRun)->aroundTime();  //总周转 
80         ave_prior_aroundTime += (*willRun)->priorTime();  //总带权周转 
81         
82         for(pos = taskArr.begin(); pos != taskArr.end(); pos++){  //更新等待时间 
83             if((*pos)->Tij < systemTime){
84                 (*pos)->waitingTime += (*willRun)->Ysi;
85             }
86         }
87 
88         systemTime += (*willRun)->Ysi;  //系统时间增加 
89 
90         taskArr.erase(willRun); //结束则删除 
91         
92         //Sleep(10);
93     }
94     cout<<ave_aroundTime<<' '<<ave_prior_aroundTime<<endl;
95     printf("\n----平均周转时间: %.2f --平均带权周转时间: %.2f ...\n作业结束..", ave_aroundTime*1.0/order, ave_prior_aroundTime/order);
96 
97     return 0;
98 } 

加油( ̄▽ ̄)”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图