队列应用——循环分配器、银行服务模拟

1.循环分配器

  为在客户群体中共享某一资源(比如多个应用程序共享同一CPU),可以借助队列Q实现一个资源循环分配器。

RoundRobin{//循环分配器
    Queue Q(clients);//参与资源分配的所有客户组成队列Q
    while(!serviceClosed()){//在服务关闭之前,反复地
        e=Q.dequeue();//对首的客户出队,并
        serve(e);//接受服务,然后
        Q.enqueue(e);//重新入队
    }
}

  在以上轮值算法中,首先令所有参与资源分配的客户组成一个队列Q。接下来是一个反复轮回式的调度过程:取出当前位于对头的客户,将资源交给该客户使用;在经过固定的时间后,回收资源,并令该客户重新入队。得益于队列”先进先出”的特性,如此既可以在所有客户之间达到一种均衡的公平,也可以使得资源得以充分利用。这里每位客户持续占用资源的时间,对该算法的成败至关重要。一方面,为保证响应速度,这一时间值通常都不能过大。另一方面,因占有权的切换也需要耗费一定的时间,故若该时间值取得过小,切换过于频繁,又会造成整体效率的下降。因此,往往需要通过实测确定最佳值。

2.银行服务模拟

  通常,银行都设有多个窗口,顾客按到达的次序分别在各窗口排队等待办理业务。为此,可首先定义顾客类Customer如下,以记录顾客所属的队列及其所办业务的服务时长。

struct Customer{
    int window;unsigned int time;//顾客类:所属窗口(队列)、服务时长
}

  由simulate函数模拟顾客在银行中接受服务的整个过程:

void simulate{int nWin,int servTime){//按指定窗口数、服务总时间模拟银行业务
    Queue<Customer>* windows=new Queue<Customer>[nWin];//为每一窗口创建一个队列
    for(int now=0;now<servTime;now++){//在下班之前,每隔一个单位时间
        if(rand()%(1+nWin)){//新顾客以nWin/(nWin+1)的概率到达
            Customer c;c.time=1+rand()%98;//新顾客到达,服务时长随机确定
            c.window=bestWindow(windows,nWin);//找出最佳(最短)的服务窗口
            windows[c.window].enqueue(c);//新顾客加入对应的队列
        }
        for (int i=0;i<nWin;i++)//分别检查
            if(!windows[i].empty())//各非空队列
                if(--window[i].front().time()<=0)//队首顾客的服务时长减少一个单位
                    windows[i].dequeue();//服务完毕的顾客出列,由后继顾客接替
    }
    delete [] windows;//释放所有队列
}

  这里,首先根据银行所设窗口的数量相应的建立多个队列。以下以单位时间为间隔反复迭代,直至下班。每一时刻都有以为顾客按一定的概率抵达,随机确定所办业务服务时长之后,归入某一“最优”队列。每经单位时间,各队列最靠前顾客(如果有的话)的待服务时长均相应减少一个单位。若时长归零,则意味着该顾客的业务已办理完毕,故应退出队列并由后一位顾客(如果有的话)接替。可见,顾客归入队列和退出队列的事件可分别由enqueue()和dequeue()操作模拟,查询并修改队首顾客时长的事件则可由front()操作模拟。

  

int bestwindow(Queue<customer> winndows[],int nWin){//为新顾客确定最佳队列
    int minSize=winsows[0].size(),optiWin=0;//最佳队列(窗口)
    for(int i=1;i<nWin;i++)//在所有窗口中
        if(minSize>windows[i].size()){//挑选出
            minSize=windows[i].size();
            optiWin=i;//队列最短者
        }
    return optiWin;//返回
}

  为更好地为新到顾客确定一个队列,这里采用“最短优先”的原则。为此只需遍历所有的队列并通过size()接口比较其规模,即可找到其中的最短者。

原文地址:https://www.cnblogs.com/biwangwang/p/11335314.html