文献综述-浅析儿童早期教育中感官体验在益智类玩具设计中的应用.doc

《文献综述-浅析儿童早期教育中感官体验在益智类玩具设计中的应用.doc》由会员分享，可在线阅读，更多相关《文献综述-浅析儿童早期教育中感官体验在益智类玩具设计中的应用.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、江西财经大学现代经济管理学院普通本科毕业设计文献综述设计题目 实时数据库事务调度策略研究 学生姓名 * 学 号 0071489 专 业 计算机科学与技术 届 别 2011届 指导教师 * 职 称 * 完成日期 二0一0年 十二 月 二十 日 文 献 综 述前言实时数据库系统是用来处理具有定时限制的数据库管理系统，其主要目标是要满足事务的定时限制，如截止时间。实时事务调度是实时数据库的重要组成部分，其主要目标是使满足定时限制事务数最大。实时事务调度是针对多个事务的CPU调度，以及与之紧密相关的数据、I/O以及内存等资源的调度。如何正确调度这些资源，对实时数据库系统的功能和性能都有着极大的影响。常

2、用的调度方法是基于事务优先级调度方法。当事务开始运行时，分配一定的优先级，高优先级的事务优先执行。因此，其指导思想是通过一定的优先级分派策略使实时事务在事务调度队列中排队来等待调度。不同的优先级分派策略具有不同的特点。有时，采用一种固定优先级分派策略进行调度不能为实时事务的截止期提供可靠保证，而且采用优先级的调度方法不能准确地指定事务的执行时机。因此，在选用优先级分派策略时，要因地制宜，如进行事务调度时，要考虑事务的要求和特点，如事务的重要性、时间约束、依赖性、紧迫程度等，采取不同的调度策略。正文1 国内外研究现状1.1 最早放行最优先该策略以放行时间(release time)为标准安排事务

3、的优先级，所谓放行时间是指事务真正开始运行的时间3。该策略类似于“先来先服务”，使“可以开始执行时间”最早的事务具有最高的优先级，做法简单易行。对于实时数据库来说，其缺点是显而易见的，由于没有考虑事务的截止时间，可能会使一个刚到达的紧急事务等待一个先到来的并不紧急的事务。在某些情况下，这样的事务处理会给系统带来灾难，通常不用于实时事务处理。1.2 截止期最早最优先该策略以截止时间(deadline time)为标准安排事务的优先级，所谓“截止期”就是实时事务T应该完成的最晚时间3。该策略表达的意思很简单，使“截止期”最早的事务具有最高的优先级，在很多情况下，配上适当的并发控制协议，其处理结果十

4、分理想。它使得最需要处理(截止时间最短)的事务首先获得系统资源，但由于没有考虑到其事务处理所需的时间，可能会将最高优先级分配给一个要过或已过截止期的事务，从而导致有机会能够在截止期内完成的事务也被推迟而超时。1.3 可达截止期最早最优先所谓一个事务T的截止期是当前“可达到”的，其计算表达式如下: (1.1)其中t为系统的当前时间，pretime，runtime分别为事务T的运行估算时间和已执行时间，deadline为其截止期。通过对事务的执行时间进行预分析来判断事务的截止期是否可达,对可达的事务进行截止期最早的优先调度，不仅考虑了事务的截止时间，还考虑了事务的执行时间，仍以截止时间为标准安排事

5、务的优先级，是对“截止期最早最优先”算法的一种改进，有效克服上述策略的缺点3。1.4 剩余时间最短最优先对于一个事务T，其剩余时间sparetime的计算公式如下: (1.2)其中，deadline为截止时间，pretime为运行估算时间，runtime为已执行的时间，t为系统的当前时刻，用定义性语句来描述的话，这样来定义：事务的剩余时间是指事务T的截止期和事务预计能完成时间之间的差3。该策略考虑了事务的截止时间，还考虑了系统的运行时间，以sparetime为标准安排事务的优先级。对于正在执行的事务，如果sparetime0则事务处理可在截止时间前完成，在处理过程中sparetime不变，事务

6、优先级也不变；如果sparetime0，则事务处理已经或将会超过截止时间。一个未执行的事务的剩余时间sparetime是逐渐减小的，而一个已执行的事务的剩余时间sparetime是不变的，因而其优先级在增大。但要注意，该策略和前两种策略还是有差别的，它考虑了当前时间与剩余时间的执行时间估算，针对事务T的停止与执行的变化，确定其优先级升降。1.5 价值最高最优先每一事务有一价值函数，其值最大者最优先，取一个函数表达式示例: (1.3)其中t、P、S表示分别是当前时间、已执行时间、事务执行的空余时间，C、ts分别为事务T的危急度、开始时间，Wi为加权因子13。显然，要判断事务的优先级需要构造价值函

7、数，而价值函数构造需要根据事务T的价值大小来进行适配。这种方法也可以看成是构造优先级函数来给事务指派优先级。该策略的优点就是综合考虑了事务的价值，以此作为确定优先级别的标准，比较合理利用了系统资源,使优先级的指派更加公平。缺点就是构造函数比较困难，不容易寻找到合适的优先级函数。1.6 价值比率最高最优先在事务调度队列中进行排队的事务，如果几个事务的优先级相同，那么实时程度最高最优先的处理方式就显得相形见肘了。对有着相同优先级的事务，如果我们考虑对这些事务的价值比率进行考察的话，其排队顺序就能区别。考虑事务进行实时程度最高最优先处理的特殊性，价值比率也会时间t的变化而具有动态性的3，故而其价值比

8、率表达式可以处理为： (1.4)其中t表示当前时间、pretime表示事务T运行的估算时间、runtime表示事务T已执行时间、value表示实时事务T的均衡价值。但该策略同样也面临着如何确定均衡价值value的问题，其优点也是需要综合地考虑了事务的价值，比较合理地确定优先级别，缺点是构造函数同样比较困难。1.7 基于优先级表的优先级计算方法1.7.1 优先级表的定义优先级分派策略可以看成是一个函数，适用于单个任务，事务或一个任务，事务组4。当用于单个任务时，函数的结果就是对应于分派策略所确定的、该任务的优先级；当用于任务组时，函数的结果是这些任务的一个排序表，在实施调度时，优先级最高者排第一

9、，最低者排最后。将任务的相对截止期都d(和空闲时间s)这两个参数的取值范围划分成若干个不同的取值区间。每个区间选择一个典型的值来代表这个区间。不失一般性，考虑相对截止期的m个典型的值，(满足)，和空闲时间的n个典型值(满足)。对于具有不同的典型相对截止期和典型空闲时间的任务，赋予其特定的优先级值，简记为，从而得到事先能够确定的优先级设计表。对于具有任一相对截止期和空闲时间的任务，当和是典型相对截止期之一和典型空闲时间值之一时，则查表可获得该任务的优先级；当和中至少有一个不是典型值时，则通过对优先级设计表进行插值获得该任务的优先级。优先级表的设计如图2.1所示6。图1.1 优先级表插值1.7.2

10、 线性加权综合考虑任务的优先级是是其相对截止期和空闲时间的线性加权平均： (1.5)其中为加权系数，显然当是为EDF调度策略；当时变成LSF策略。此外，若取为任务已完成工作的部分，称为混合(hybrid)方法，此时，任务已完成的工作越多，其相对截止期的权系数就越大。当任务已完成工作不到一半(50)时，取a=0，即此时只考虑空闲时间参数，否则取，此方法称为一半对一半(half-half)方法后两种方法只有在任务的工作量事先知道的前提下才能使用。1.7.3 优先级插值前面对于优先级表的讨论都是针对任务具有特定的相对截止期和特定的空闲时间来进行优先级设计的，对于任一任务其相对截止期或空闲时间不一定是

11、特定的相对截止期或特定的空闲时间，这时的优先级可通过对事先确定的优先级表进行线性插值获得。不妨假设，采用二元三点进行Lagrange插值公式来计算的优先级。结论从以上优先级调度方法的分析来看，各种优先级调度策略的选取是各有偏重，但上述优先级调度策略存在以下几个缺陷：没有考虑事务的截止时间，不适用于实时数据库。例如最早放行最优先的方法，它强调的是到达时间的优先，其实现虽然简单，但对事务的紧迫度和重要性等却没有区别开来。最不希望看到的情况是让一个紧迫的事务等待一个截止期要求宽松的事务，其后果往往是灾难性的。优先级的各种调度策略都有其限定范围，一种策略只针对一类事务还比较适用，当不同类型的事务同时进

12、行调度时，往往不能满足截止期的要求，而且无论采用什么策略，以上优先级调度都有一个共同的缺点，即只考虑事务的一个特征参数。单一考虑事务的一个特征值，缺乏对事务整体的，全面的考察，导致优先级分配的不公平11。对剩余时间最短最优先的调度方法来讲的话，优先考虑的是事务的紧迫程度，对事务的重要程度却没有做过多的考虑。又如价值最高最优先的方法，考虑了事务的剩余时间，具有实时性，可是没有考虑事务的截止时间，这样有可能造成截止期长但将要完成的事务具有最高的价值指数，即被分配给了较高的优先级，使得紧迫的事务反而处于低优先级，造成不合理的优先级分配。有的优先级调度策略综合考虑了几个事务特征参数，但是衡量这几个特征

13、参数之间的权重没有给出切实可行的算法，不容易确定。基于优先级表设计与插值方法的优先级分派策略通过综合任务的截止期与空闲时间这两个特征参数，有效地提高了任务调度的成功率。但是事实上事务的截止期和剩余时间很少能正好都符合假设下的经典截止期和剩余时间，这样一来将会进行大量的插值计算，并且随着插值函数本身具有的冗余和不稳定现象，使得计算出来的优先级值不够理想。基于此，本文提出一种能根据新到达事务的特征值来动态分配优先表，以避免插值函数的使用。参考文献1 刘云生, 卢炎生, 王道忠. 实时数据库系统（RTDBS）及特征. 华中理工大学学报, 1994,22(6): 66-702 李国徽, 殷小尧. 一种

14、移动实时事务调度策略. 计算机工程与科学, 2007, 29(5): 135-1373 蔡振, 蔡世洪. 实时数据库的事务调度分析. 计算机宇数字工程, 2007, 35(12): 65-674 刘正涛, 毛宇光. 基于优先级的数据流数据库实时事务调度算法与实现. 小型微型计算机系统, 2006, 27(12):2212-22175 廖国琼, 刘云生, 王丽娜, 王宏庭. 嵌入式实时数据库ARTs-EDB事务调度实现技术. 计算机工程, 2005, 31(16): 37-396 王强, 徐俊刚, 王宏安, 戴国忠. 一种新的基于优先级表的调度算法. 电子学报, 2004, 32(2): 310

15、-3137 谭宁. 实时数据库事务的调度与并发控制. 小型微型计算机系统, 2007, 18(11): 193-1958 何新贵, 唐常杰, 李霖. 特种数据库技术. 北京. 科学出版社, 20009 徐延明. Linux编程指南. 北京: 人民邮电出版社, 200010 施吉林，刘淑珍. 计算机数值方法. 北京: 高等教育出版社, 200311 霍顿. C语言入门经典. 北京: 机械工业出版社, 200712 严蔚敏 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社, 200213 Robert K Abbott, Hector Garcia-Molina, Scheduling R

16、eal-Time Transactions: A Performance Evaluations. ACM Transactions on Database Systems, 1992, 17(3): 513-56014 GiorgioButtazzo, Marco Spuri, Fabrizio Sensini. Value vs. Deadline Scheduling in overload Conditions. Scuola Superiore S. Annavia Carducci:1052-8725/95, 1995, 121-13415 Jayant R. Haritsa, Michael J.Carey, Miron Livny. ValueBased Scheduling in Real-Time Database Systems. VLDB Journal, 1993, 2: 177-152指导教师评分（百分制）： 指导教师： 年 月 日