A Reduced Reachability Tree for a Class of Unbounded Petri Nets

As a powerful analysis tool of Petri nets, reachability trees are fundamental for systematically investigating many characteristics such as boundedness, liveness and reversibility. This work proposes a method to generate a reachability tree, called ωRT for short, for a class of unbounded generalized nets called ω-independent nets based on new modified reachability trees (NMRTs). ωRT can effectively decrease the number of nodes by removing duplicate and ω-duplicate nodes in the tree, and verify properties such as reachability, liveness and deadlocks. Two examples are provided to show its superiority over NMRTs in terms of tree size.      

Locked discrete event systems: How to model and how to unlock

To model qualitative aspects of discrete event systems, i.e., the order of the events is of sole importance, we use a triple consisting of the set of all possible events (the alphabet), the set of all behavior (possible strings of events), and the set of all tasks (completed behavior). We use this view to model synchronous as well as asynchronous connection of systems. Moreover, it is easy to define notions like deadlock and livelock in this view. We give a method to construct a second system that, in connection with the original system, gets rid of its deadlock and/or livelock. A state-space representation is introduced. In this representation computations can be done effectively.     

LBMBS： A Load-Balanced Moveable Bubble Scheme for Tori Interconnection Networks

Moveable bubble flow control is an efficient technique to avoid deadlock for torus networks. However, it does not take into consideration the load balance feature. Therefore, this leads to inefficient resources utilization. Moreover, packets may be discarded due to the congestion of a network area. On the other hand, there are other algorithms that consider load balancing such as rHALB （r hop adaptive load-balanced）routing technique. Nonetheless, rHALB detects deadlock using the timeout threshold. This concept of deadlock detection may give incorrect responses in case the traffic is high. Therefore, packets are dropped although there is no deadlock. At the end, this affects the whole performance of the network. This paper proposes a new routing algorithm for tori interconnection networks, namely, the LBMBS （load-balanced moveable bubble scheme）. LBMBS integrates both concepts of moveable bubble and rHALB in order to provide at the end a load-balanced efficient deadlock-free algorithm. The protocol details are given and compared against other routing algorithms in the literature.     

一种多粒度集群数据库并发控制新算法

为保证集群系统中全局事务的并发正确执行,采用基于谓词级的多级粒度冲突检测机制,并通过检测谓词冲突图中是否存在环的方法来避免冲突的全局事务可能会产生的全局死锁,不仅减小了死锁检测粒度,而且还提高了全局事务处理的并发度,同时也保持了集群中局部数据库的自治性。此外,还改进了一种以事务提交图为中心的并发事务调度算法来保证全局事务的可串行化提交,实验结果表明,该算法有效地提高了全局事务执行的并发度,增加了事务吞吐率和减少了响应时间。     

一种多线程软件并发漏洞检测方法

多线程软件由于进程间共享使用资源而极易发生死锁这一严重的并发漏洞.通过Petri网模型对多线程软件进行建模,并利用混合整数规划技术检测其漏洞.目前,使用互斥锁的多线程软件可通过Gadara网建模和检测.而使用信号量的多线程软件,虽可用S*PR网建模,但是尚未有理论支撑混合整数规划用于其漏洞检测.定义了S*PR网的一个子类——SEM-S*PR网,它允许资源库所初始标志大于1且分支可对称地使用资源,进而可建模一类使用信号量的多线程软件.依据结构特点,证明了该网保持活性的充分必要条件是网运行过程中所有信标始终非空.此结论是混合整数规划用于SEM-S*PR网建模的多线程软件的并发漏洞检测的理论基础.     

Method to compute the reachability set of S3PR

This paper proposes a novel approach to computing the reachability set by using place invariants and strict minimal siphons for S³PR with specific resource places. First, the set of invariant markings is enumerated. Then a necessary and sufficient condition is developed to decide whether a marking is spurious by analyzing the relationship between the number of tokens in the corresponding places of any strict minimal siphon and their bounds. In addition, the spurious markings are calculated. Finally, the reachability set of the net is generated by removing all the spurious markings from the set of invariant markings. Experimental results show the efficiency of the proposed method.     

一种基于气泡流控的改进多播路由算法

多播通信在片上多核系统中占据很重要的地位,并会对多核系统上并行应用程序的性能产生很大影响。现有的多播路由算法大多存在资源利用不均衡的不足,从而导致片上缓存资源的利用率较低。提出一种新的基于气泡流控的多播路由算法,该方法充分利用了片上网络的缓存资源,并通过向网络注入气泡避免了死锁现象的产生。实验表明,该方法可以有效提高片上网络中多播通信的性能,在合成负载下,该方法相对于均衡自适应多播路由算法可以实现18.1%的网络平均时延的降低以及16.7%的网络饱和吞吐量的增加。     

基于动态滑模的无死锁时间管理算法

基于新一代仿真体系结构HLA的IEEE1516新标准中的最大有效逻辑时间关键值,讨论最大有效逻辑时间在HLA时间管理中的重要意义,分析其在常规时间推进算法中的实现及死锁的产生,研究并证明HLA时间推进中的4个产生死锁的充分条件,即互斥条件、请求保持条件、不剥夺条件和环路等待条件,提出动态滑模的概念,设计了基于动态滑模的无死锁时间管理算法,对Lookahead的合理设置进行了分析。     

基于动态探针的分布式死锁预防策略

数据库系统中事务死锁的检测和预防,对提高系统并发性和整体性能具有重要意义。在研究了现有的分布式数据库系统死锁预防策略的基础上,利用创建动态探针(DP)技术,提出了一种改进的死锁预防策略。该DP方法在创建探针后将其发往可能产生死锁的节点,接收到探针后,根据节点信息与探针所包含信息的比较结果,可以判断是否有死锁发生,从而达到预防死锁的目的。分析表明,该方法提高了死锁预防的有效性和系统资源的利用率。     

并行测试技术及在导弹测试中的应用研究

并行测试技术是将并行处理技术引进自动测试领域形成的一种先进的测试技术和方法,拥有减少测试时间、降低测试成本的强大优势,正成为研究热点之一;首先介绍了并行测试的基本概念,分析对比了几种实现并行测试的软硬件方法及基本结构体系;然后结合导弹传统串行测试方法的不足及未来战场快速测试的要求,设计了一种导弹的网络化并行测试的基本结构;最后,针对并行测试技术在导弹测试中的应用,提出了需要注意的任务调度、死锁预防及并行测试接口设计等几点关键技术和导弹并行测试系统组建原则。