数据库系统并发控制的扩展有色Petri网方法

加锁与可串行化是并发控制中采取的2个主要措施.两段锁协议(two-phase locking protocol,简称2PL)是解决可串行化调度较好的方法之一,但满足可串行化的调度可能会出现死锁.为此建立了多个事务并发访问数据库的扩展有色Petri网模型,该模型可使并发事务的调度符合两段锁协议.利用该模型的可达标识图,给出了判断满足两段锁协议的调度是否死锁的充分必要条件,并由此构造出并发事务的无死锁的可串行化调度.     

可定制Tcore处理器指令调度设计

基于传输触发体系结构可定制Tcore处理器具有理想的性能/价格比.但由于大量数据传输细节在体系结构一级可见导致了过低的编译效率.为此,提出了一种基于MACHSUIF中间格式的可重定目标编译器架构,将表调度与关键路径算法相结合以实现高效指令调度,从而大幅度提高编译质量.此外,通过基于操作的调度方法解决指令调度过程中功能单元的死锁问题.通过在4个DSP应用上进行测试,指令级并行度比传统的MoveFramework提高40%左右.     

带驻留约束的多机械手制造单元的调度算法

为了有效地解决多机械手制造单元适应带驻留约束的多品种调度问题,提出了基于瓶颈的推拉式算法.首先,进行了调度问题域的描述,以最小Makespan为目标,建立了数学模型.在此基础上,提出了一种以瓶颈工作站为界,通过逐级回溯和递推来优化机械手动作组合,同时降低产品在机器上的驻留时间的启发式调度算法;该算法结合时间缓冲概念,有效地解决了共享工作站的机械手冲突问题,防止了死锁现象的发生.最后,通过仿真实验对提出的基于瓶颈的推拉式算法进行验证并与拉式算法进行比较,结果表明,该算法能够有效地实现多品种、带驻留约束的多机械手制造单元的调度,且性能优于拉式算法.     

支持缓存划分的全局EDF实时系统调度策略

由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题,现代处理器引入了缓存划分技术,通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是,这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞,而传统的实时调度算法与分析方法无法有效应对这种情况.因此,提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca,并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析,提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法,进一步提高了分析方法的性能.随机生成任务的仿真实验表明,提出的可调度性判定方法具有较高的效率.同时,优化算法提高了算法可调度性.     

基于统计信道状态信息的多小区下行协作调度算法

小区间干扰是制约无线蜂窝网络边缘区域容量的主要因素.为了提高小区边缘吞吐量,传统的预编码矩阵指示(precoding matrix indicator,PMI)协作调度方案能够有效抑制小区间干扰,但该方案需要较多的信道反馈信息.为了有效减少信道反馈开销,提出一种利用统计信道状态信息(statistical channel state information,SCSI)的多小区下行协作调度算法,该算法利用SCSI提取特征方向确定最佳的PMI或PMI集合.仿真结果表明,在强相关信道场景下,基于SCSI的协作调度算法可以使边缘用户保持较为理想的性能,并且对反馈时延和多普勒扩展导致的非理想信道信息具有较强的鲁棒性.     

一种Linux内核自旋锁死锁检测机制的设计与实现

在操作系统内核中,自旋锁是一种应用非常广泛的锁机制,能大幅提高系统性能和吞吐量;另一方面,自旋锁的使用不当,会立即将系统锁死,直至人工重启才能解锁,是危害性最大的死锁原因.从检测死锁发生的角度出发,提出一种自旋锁死锁检测机制,可迅速检测到Linux内核中死锁的发生,报告死锁相关信息供管理员分析使用,在可能的情况下重启系统,降低系统宕机时间,提高系统稳定性.     

基于信道统计相关性OFDM系统资源分配算法

在正交频分复用(OFDM)系统中,对信道相关及信道独立的子载波和功率分配调度算法进行了研究,提出了一种新的基于信道参数统计相关性的子载波和功率分配算法.这种算法利用信道统计信息来减少信道反馈,由于最优解的高度非线性,转化成离散模型的求解可以降低算法的复杂度.仿真结果显示:相对于传统的信道相关调度算法,基于信道统计相关性的调度算法在系统总容量上有微小降低,但算法复杂度大大降低,信道反馈信息的减少节省了控制信令带宽;同时在性能上优于基于路径损耗等信道独立的调度算法.     

一种有界Petri网的可诊断性验证方法

离散事件系统满足可诊断性是设计故障诊断算法的前提,因此研究可诊断性验证方法具有重要意义.故障发生后无死锁是研究可诊断性问题常见的假设之一,限制了可诊断性验证方法的应用范围.本文在去掉故障发生后无死锁假设的基础上,首先提出了标签可达图的概念和构建算法,其次提出了一种新的可诊断性验证算法来验证有界Petri网是否满足可诊断...     

Web服务集成协调框架中的基于语义锁的死锁检测与解除

为了保证Web服务集成时的一致性和可靠性,IBM和Microsoft发布了Web服务协作(Web Services Coordination)规范以及Web服务事务(Web Services Transaction)规范,它们负责协调整个业务流程中多个Web服务的协调与合作.但是由WS-Coordination和WS-Transaction所定义的框架并没有对Web服务环境中多个事务并发执行时所出现的死锁问题提供相应的解决方案.因此我们设计了一种适合于Web服务环境的语义锁模式,这种锁模式能够极大地提高Web服务环境中事务间的并发度,提高企业的经济效益,并提出了一种能够根据语义锁中的语义信息最大限度地减少企业经济损失的死锁解除方法.     

一种基于语法扩展的自动互斥锁实现机制

针对多道程序开发过程中存在的互斥锁标准不统一、使用复杂、易造成死锁等不足,提出扩展C/C++标准语法,增加临界资源定义及操作关键字的方案,通过隐藏互斥锁的概念及实现从而降低开发复杂度、实现平台无关.在扩展语法基础上,提出采用分支栈检查算法在代码进行临界资源访问顺序合法化及配对完整性检查,可有效地减少死锁隐患、增强系统的可靠性.     

Research on efficient edge-chasing deadlock detection/resolution for distributed systems

Numerous edge-chasing deadlock detection algonthms were developed lor the cycle detection in distributed systems, but their detections had the n steps speed limitation and n （ n- 1） overhead limitation to detect a cycle of size n under the one-resource request model. Since fast deadlock detection is critical, this paper proposed a new algorithm to speed up the detection process. In our algorithm, when the running of a transaction node is blocked, the being requested resource nodes reply it with the waiting or being waited message simultaneously, so the blocked node knows both its predecessors and successors, which helps it detecting a cycle of size 2 directly and locally. For the cycle of size n （ n 〉 2）, a special probe is produced which has the predecessors information of its originator, so the being detected nodes know their indirect predecessors and direct successors, and can detect the cycle within n - 2 steps. The proposed algorithm is formally proved to be correct by the invariant verification method. Performance evaluation shows that the message overhead of our detection is （ n^2 - n - 2）/2, hence both the detection speed and message cost of the proposed algorithm are better than that of the existing al gorithms.     

深入解析银行家算法

银行家算法是操作系统中采用避免死锁策略来解决死锁问题的一种算法。本文首先讲述了银行家算法流程,然后深入解析了银行家算法的根本原理。这在国内外操作系统教材中是第一次揭示银行家算法的根本原理。     

基于优先级动态分配的分布式死锁探测方法

本文采用动态优先级分配策略,提出分布式事务死锁探测的有效方法。该方法所使用的优先级分配策略改进了传统的分配方法,它能更为准确地反映事务的运行特性,以较少的通讯开销来探测分布式死锁,且具有更短的死锁探测时延。     

离散事件动态系统的一种新仿真方法

本文针对离散事件动态系统,提出了一种新的仿真方法,它由异步仿真运行、仿真死锁检测、解除仿真死锁三部分组成。文中详细讨论了这种方法的原理及特性,并应用此方法对—FMS进行了仿真研究。     

整体式半导体自动物料搬运系统解死锁算法

为了有效地解决300mm晶圆制造中整体式自动物料搬运系统的设备缓冲约束引起死锁的问题,构建了基于图论的两阶段解死锁算法.首先对问题域进行了形式化描述,在此基础上,证明了死锁产生和解除的充分条件,以关键设备死锁解除时间最小化为目标,建立了数学规划模型,并构造了解死锁算法.该启发式算法使用存储柜转存晶圆批来释放死锁的小车资源,并应用图论理论构造了多个并行路径来解除死锁.最后,对算法进行了仿真实验,结果表明该算法能有效求解设备缓冲约束引起的死锁问题.与其他解死锁方法相比,上述算法能有效减少解死锁时间,提高了关键设备的可用率.     

基于Petri网的工作流模型合理性研究

针对难以建立合理的工作流模型问题,将工作流管理联盟(WFMC)定义的工作流模型映射为工作流网络(WF-net).在定义并证明两种不破坏原工作流网络结构特性和系统行为的调整映射的基础上,将该工作流网络调整为完全的扩展自由选择网(EFC-net).通过证明扩展自由选择网与自由选择网(FC-net)的最小死锁有相同的特征.通过引入获取最小死锁的算法,结合秩定理,给出了验证工作流合理性的算法.     

基于路径频率树的XML流数据剪切分片技术

与传统数据库对XML数据的处理不同,对XML流数据的处理不仅受实时性的约束,还受存储空间的限制.在Hole-Filler模型的基础上,首先利用XML的查询统计信息,定义了路径频率树,提出了基于兄弟关系的XML流数据剪切分片策略及其算法.在此基础上,提出了基于父子关系的XML流数据剪切分片策略及算法.这两个基于路径频率树的剪切算法有效地提高了XML片段的利用率,增强了XML片段的内聚性.实验结果表明,基于路径频率树的XML剪切算法在剪切时间、查询时间、空间消耗等方面都表现出较好的性能.     

一种基于并行技术的死锁检测算法

在介绍基于资源分配图的、传统的死锁检测算法基础上，提出一种新的基于并行技术的死锁检测算法，并用1个实例说明该算法的执行过程。新的死锁检测算法是基于矩阵表示方法，在最坏情况下，运行时间复杂度是O(min(m，n))，其中m和n分别是进程和资源的数量。新的死锁检测算法与传统的算法相比，执行时间大大减少，需要内存也比较小，系统能够很好地检测死锁的发生，并且释放占有资源。     

一种新的分布式死锁探测与解除方法

为了有效地解决分布式环境下的死锁探测与解除问题,本文提出了一种基于请求路径双向探测的方法,此方法较以前各类方法具有更好的分布性、可靠性和更短的死锁探测时间。     

移动机器人路径规划的一种改进蚁群算法

提出了一种复杂静态环境下的移动机器人避碰路径规划的改进蚁群算法。基于栅格法的工作空间模型,模拟蚂蚁觅食行为,并针对移动机器人的路径规划的需要,将一些特殊功能赋予常规的蚁群算法。为了避免移动机器人的路径死锁,在路径搜索过程中,当蚂蚁探索到一个死角时,建立了相应的死角表,同时用惩罚函数来更新轨迹强度。仿真研究表明:该算法能明显改善路径规划性能,并且算法简单有效。