谈操作系统中的死锁问题

进程死锁问题是操作系统的主要问题之一,很多学者专家一直在研究怎样解决这个问题.本文针对操作系统中经常出现的死锁问题进行了讨论,阐述了死锁出现的原因、四个必要条件,以及死锁的处理方法,最后谈论了一个避免死锁的经典算法--银行家算法.     

并发操作系统中基于有色Petri网的死锁检测与避免

1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞     

计算机操作系统中死锁问题研究

死锁问题是计算机操作系统故障中一个十分重要的组成部分,其在对计算机资源使用最优化的实现面前无疑是个亟待解决的问题,当然,就这种计算机操作系统中的死锁问题而言,其绝不是凭空产生的,相反的,其有着自身的一系列必要条件,而这些必要条件和产生原因实际上又可以为相应应对措施的采取指明突破口。本文主要围绕着计算机操作系统中的死锁问题这一中心主题,从死锁问题的具体内涵出发,通过对其产生原因、必要条件的论述和揭示,最后给出可行的死锁解决策略。     

浅谈操作系统中的死锁问题

如何进行合理的资源分配,使操作系统的主要任务之一。本文将着重讨论操作系统在处理资源分配过程中的死锁问题,并给出适当的解决方法。     

浅谈操作系统中的死锁问题

如何进行合理的资源分配,使操作系统的主要任务之一。本文将着重讨论操作系统在处理资源分配过程中的死锁问题,并给出适当的解决方法。     

计算机操作系统中死锁问题研究

死锁是进程并发执行所带来的一个重要问题,也是操作系统乃至并发程序设计中最难处理的问题.讨论死锁的基本概念、死锁的处理方法以及进程数与资源数之间的关系问题.     

死锁的解法

本文主要研究由资源分配引起的死锁,说明资源的各种类型和基于资源分配的系统状态模型,给出了死锁形成的四个必要条件。分别对解决死锁的四个感兴趣的区域:死锁的预防、避免、探测和恢复进行较详细的分析和研究。     

银行家算法的改进与实现

银行家算法是操作系统中避免死锁的经典算法,为提高系统的运行效率,文章对银行家算法进行了研究和改进.通过对银行家算法流程、算法优缺点的分析,以及对现有的银行家改进方法的讨论,提出一种银行家算法的改进思路.使用Java语言实现了改进的银行家算法,并运用Java多线程对操作系统中进程的同步进行模拟,验证了该算法的有效性.     

基于银行家算法的进程安全序列仿真研究

银行家算法是一种应用于操作系统安全的死锁避免方法。本文分析了银行家算法思想,给出了算法描述。在Delphi集成开发环境下进行了仿真实验,得到了进程执行的安全序列。同时文中也对银行家算法提出了改进的意见。     

求解哲学家进餐问题的Petri网模型及实现

为了解决操作系统中的进程间同等互斥问题 ,研究了以 Petri网为系统描述工具来分析经典的哲学家进餐问题 ,提出了避免死锁问题的轮流就餐方案 ,讨论了不同进餐次数之比时的 Petri网模型 ,给出了两种模型的程序实现。此法简洁高效 ,在操作系统的其他类型进程调度中可进行类似推广     

A comparative performance analysis of deadlock avoidance control algorithms for FMS

A deadlock condition for flexible manufacturing systems is characterized by a set of parts, which have been processed but cannot be discharged by a set of machines or buffers. To avoid such problems, it is necessary to adopt suitable control policies which limit the resource allocation in the system, thus affecting the overall system performance. In the present work, we address the problem of evaluating and comparing the performance of deadlock avoidance control policies applied to FMS. The problem is discussed for both untimed and timed models, and for models both with and without deadlock avoidance control policies. Different control algorithms, among the most common in the literature, have been considered. Imperfect deadlock avoidance control policies are also considered. In addition, some indices are proposed to assess the structural properties of FMS with respect to deadlock occurrence and their performance. Two different application examples are analyzed, with the help of a commercial simulation package. Finally, an adaptive algorithm which can learn from system evolution to avoid deadlocks is illustrated.     

DEADLOCK AVOIDANCE FOR FLEXIBLE MANUFACTURING SYSTEMS WITH CHOICES BASED ON DIGRAPH CIRCUIT ANALYSIS

Due to existence of concurrent part flows and resource sharing in modern automated flexible manufacturing systems (FMS), deadlock is a common problem and its occurrence causes loss of productivity. When a manufacturing system is modeled by a digraph, existence of circuits in such a graph is a necessary condition for deadlock. Our previous work further showed that the knot and order of a circuit is closely related to impending deadlocks — a type of deadlock that is more difficult to detect. In this paper, we extend our previous work on deadlock avoidance for flexible manufacturing systems to allow choices in process flows (a.k.a., flexible part routing). Due to introduction of choices, part flow dynamics become more sophisticated and our previous results are no longer valid. A systematic circuit analysis is performed in this paper. New concepts such as broken circuit, basic circuit, choice circuit and supremal circuit are introduced to reduce significantly the number of circuits thus improving efficiency of our approach. The extended method is highly permissive with the adjusted effective free space calculation to capture more necessary parts flow dynamics, especially when multiple knots exist in the digraph model. The online policy runs in polynomial time once the set of basic circuits of the digraph is computed offline. Simulation results on selected examples are given.     

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

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

MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection

The message passing interface (MPI) has become a de facto standard for programming models of highperformance computing, but its rich and flexible interface semantics makes the program easy to generate communication deadlock, which seriously affects the usability of the system. However, the existing detection tools for MPI communication deadlock are not scalable enough to adapt to the continuous expansion of system scale. In this context, we propose a framework for MPI runtime communication deadlock detection, namely MPI-RCDD, which contains three kinds of main mechanisms. Firstly, MPI-RCDD has a message logging protocol that is associated with deadlock detection to ensure that the communication messages required for deadlock analysis are not lost. Secondly, it uses the asynchronous processing thread provided by the MPI to implement the transfer of dependencies between processes, so that multiple processes can participate in deadlock detection simultaneously, thus alleviating the performance bottleneck problem of centralized analysis. In addition, it uses an AND⊕OR model based algorithm named AODA to perform deadlock analysis work. The AODA algorithm combines the advantages of both timeout-based and dependency-based deadlock analysis approaches, and allows the processes in the timeout state to search for a deadlock circle or knot in the process of dependency transfer. Further, the AODA algorithm cannot lead to false positives and can represent the source of the deadlock accurately. The experimental results on typical MPI communication deadlock benchmarks such as Umpire Test Suit demonstrate the capability of MPIRCDD. Additionally, the experiments on the NPB benchmarks obtain the satisfying performance cost, which show that the MPI-RCDD has strong scalability.     

应用必需信标的Petri网死锁预防策略

本文提出了表征一个Petri网子类,即S4R网(system of sequential systems with shared resources)中死锁问题的必需信标的概念和一种将混合整数规划算法与必需信标控制相结合的死锁预防策略.在该策略的迭代过程中,混合整数规划算法发现被控的Petri网中是否存在最大的死标识信标,若存在,则通过库所分类和迭代式的信标提取,得到必需信标,添加相应的控制库所,满足必需信标的最大可控性,从而实现被控的Petri网活性的目的.理论分析和算例验证表明了该策略的正确性和有效性.     

一类FMS的最佳活Petri网模型的综合

利用Petri网为一类柔性制造系统建模,并讨论避免系统死锁问题.通过Petri网模 型的结构分析,证明了系统产生死锁的一个充分必要条件.给出了避免死锁的最佳控制器,它 可以通过给系统的Petri网模型增加一些新的位置与相应的弧来实现.从而导出了这类制造 系统的最佳活Petri网模型.     

柔性制造系统中多路径条件下的死锁避免第二部分:控制策略

在第一部分推导出的面向资源的着色Ｐｅｔｒｉ的基础上讨论ＦＭＳ中多路径条件下的死锁避免控制策略问题，给出了无死锁运行的充要条件及其相应的控制策略。     

具有多项式时间复杂性的避免制造系统死锁控制策略

基于系统 Petri 网模型, 研究自动制造系统的避免死锁问题. 对不含中心资源的制造系统, 证明了它只包含安全和死锁两类可达状态. 通过一步向前看的方法, 给出了系统多项式时间复杂性的最佳避免死锁策略. 对一般系统定义了一种辅助 Petri 网. 利用辅助网的最佳避免死锁策略, 提出了综合一般制造系统多项式复杂性的避免死锁策略的方法.     

避免FMS死锁的控制策略

本文利用ＦＭＳ的Ｐｅｔｒｉ网模型讨论系统的死锁问题，给出了系统死锁的必要充分条件，提出了避免系统死锁的反馈控制策略，这种策略对系统的限制小，在许多情形下是最优的。     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。