第八章 服务请求排队算法.pdf

计算机系统应用 2009年第8期 服务请求排队算法① Arithmetic Service-RequestQueue 危 达 李建华 李 曼 叶 云 (中南大学信息科学与工程学院湖南长沙410075) 摘要： 当有很多用户请求某一个特定服务提供者(SP)提供的服务，可能造成排队等候现象，已有技术普遍使 用先来先服务(FCFS)的原则对服务请求(SQ)进行排队。提出了一种基于语义匹配的优先级排队算法， 和一种基于语义匹配和先来先服务原则的综合排队算法，协调处理高优先级别SQ和先到SQ。从数理 上对服务请求综合排队算法进行了评估，证明算法只增加了常数时间消耗。描绘出了实现该算法的技 术框架。 关键词：服务提供者服务请求排队算法先来先服务语义匹配 当有很多用户请求某一个特定SP提供的服务，可 FCFS排队算法并没有很大的区别，却能够实现更合理 能造成排队等候现象，已有技术普遍使用FCFS原则 的利用sP提供的服务，因此将会具有实际效益。本文 对SQ进行排队…。当某些后到的SQ，要求在先来的最后论述了SQ综合排队算法的实现机制，描绘出了 SQ之前先得到处理，就需要一种基于优先级的排队算 实现该算法的技术框架。 法来实现此要求。 2 FCFS原则 1 引言 FCFS原则是指一队SQ在等候同一SP提供服务 本文首先提出基于语义匹配的优先级排队算法， 时，先来的SQ排在队列的的前面，而后来的SQ则排 然后同时考虑语义匹配和FCFS原则，提出综合排队在队列的后面。 算法。综合排队算法致力于实现高优先级别SQ和先 服务请求到达顺序位置值：假设SQ队列已有P 到SQ之间的协调，更合理的使用SP提供的服务，提个请求在等待，则这P个请求的到达顺序位置值按照 高资源利用效率。 先后顺序分别为： 基于语义匹配的优先级排队算法，基本思想是通 1_旦，1一上，…．，1-型 P P P 过SQ附加语义信息，SP通过将这些语义信息与其本 身所拥有的标签库中的信息匹配，匹配程度高的SQ 将获得高的优先级【2】。 达顺序位置值分别为： 基于语义匹配和FCFS原则的综合排队算法，基 ，一者，卜击，…‘，卜寺 本思想是在上一种算法的基础上，同时考虑FCFS的 原则，得到一个优先值计算函数。每一个SQ如果不 其中，第(p+1)个SQ的到达顺序位置值为—I_。 p1+l 能即时被SP处理，通过此函数得到一个优先值，然后 根据此优先值排队等候，实现合理有序使用SP提供的 3语义匹配 服务。 SQ的语义描述信息与SP的标签库中的信息匹 本文提出两种SQ排队算法，针对综合排队算法 配，匹配程度高的SQ将获得高的优先级。实现语义 做出评估，论证该算法在时间消耗等方面，与原有的 匹配必须要求SQ消息附带语义信息，SP有标签库， ①收稿时间：2008—11一05 50研究开发Reseatohand Development 万方数据 2009年第8期 计算机系统应用 以下论述了这个两个对象的工作机制。 L一一一一一一 SQ的语义描述信息：SQ消息附加的语义信息，