Deadlock can be prevented or detected, with several algorithms available. Deadlock prevention
schemes include negation of one of more of the listed preconditions. For example, to prevent the occurrence of a
circular chain, processes can be ordered in their access to resources, with mechanisms such as resource pre-
allocation (which also negates the hold and wait precondition) and timestamps. Alternatively, resources may be
linearly ordered in terms of processes' access, which, however, negates fungibility. Deadlock can also be
prevented by an "avoidance" scheme, which ensures that the system remains in a safe state. Using banker's
algorithm, for example, processes pre-state their maximum needs and the system continuously monitors
allocation, reserving sufficient resources for processes to complete. Serial process execution and resource pre-
allocation are also avoidance algorithms. Heuristics for avoidance are common, such as throttling new processes
to ensure 20-30% of free buffers [10] on the assumption that these are sufficient for currently executing
processes to complete.
Detection schemes find the circular chain. At least one victim is chosen; its partial service is rolled back
and its resources freed, in an attempt to break the deadlock and allow the other processes to complete. The
victim(s) can be restarted later, without alteration, but its rolled back service must be repeated.
Holt [10] provides an example of a single process in deadlock: process Revenge is infinitely suspended
by a wait for an event that never occurs. Similarly, Nutt [16] states that a kernel process is in deadlock if it is
permanently blocked waiting for a resource that will never become available. In accordance with the Halting
Problem, however, this type of dead state is impossible, in general, to prevent or even detect with current
technology. A deadlock cannot occur with only one process (as erroneously stated in [11], [27]). Deadlock is an
anomaly of traffic control (i.e., competition synchronization) and contains at least two competing processes.
Holt [10] also considers deadlock as a circular wait with consumable resources, such as messages, that
can be dynamically created and destroyed. Message deadlocks, however, are controllable neither by serial
execution nor by most of the previously discussed prevention schemes.
Many Operating Systems textbooks provide the above characteristics and handlers in a Deadlock
chapter, but also include incorrect examples. Silberschatz et al. [20] claim that a deadlock exists if two trains on
different tracks approach a crossing and wait for the other to proceed. {Yet neither train is holding a resource
requested by the other. } Similarly, Stallings [21] gives an example of four cars at different stop signs
approaching an intersection, where each gives precedence to the car on its right. [Yet none of the cars (or trains)
have been allocated intersection slots, which are the only resources that are mutually requested. Nor is roll back
required to break the wait. } Davis and Rajkumar [5], as well as Flynn and. McHoes [9], cite a "deadlock"
example of two programs issuing a seek command to reposition the access mechanism. Each is interrupted
before executing its read command, and discovers that the other has moved the disk arm. Each then reissues the
seek command, but is again interrupted by the other. This sequence continually repeats. {This dead state is
indeed an anomaly of traffic control and can be controlled by resource pre-allocation. Processes, however, are
not blocked from resources, which are in fact preempted. In addition, resources are already requested in a linear
order. } Pinkert and Weat [17] include a "deadlock" example similar to the producer/consumer code in our
introduction. They state that a typo in the order of cooperation and competition mechanisms results in the
consumer locking the mutual exclusion semaphore before it blocks on an empty buffer. {We note that linear
orders, resource pre-allocation, and avoidance methods are all ineffective for this dead state. } The above
examples are inconsistent with the material presented in their chapters, even though they appear in multiple
editions of some of the texts.
Researchers in the field of distributed databases typically limit their applications to requests for data
locks, and their treatments are consistent with deadlock material [e.g., 25, 29]. Additional restrictions are
required to obtain a global knowledge of a deadlock, however, and fungible resources (basically OR-requests)
are generally not included in detection algorithms.
Some additional remarks will be useful. Processes in deadlock may be suspended in an inactive wait or
looping endlessly in a busy wait. They may be holding resource buffers, "soft" resources, which are typically
fungible. In an attempt to differentiate between different types of dead states, some of the literature has begun to
use the term resource deadlock [e.g., 21, 25] for the anomaly discussed above (although not always consistently).
In the remainder of this paper, we accede to this terminology, although dead states with resources are obviously
not always resource deadlocks.
In Table 1, we provide a taxonomy of dead states:
56
对deadlock的
错误认识
剩余10页未读，继续阅读
知天易or逆天难
- 粉丝: 113
- 资源: 14
我的内容管理
展开
最新资源
- C++标准程序库：权威指南
- Java解惑：奇数判断误区与改进方法
- C++编程必读：20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程：从入门到精通
- Spring3.0权威指南：JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略：从环境配置到索引创建
- 内存虚拟硬盘技术：提升电脑速度的秘密武器
- Java操作数据库：保存与显示图片到数据库及页面
- ISO14001：2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发：触发器与控制器重定向技术详解
- FPGA开发实战指南：创新设计与进阶技巧
- ShopExV4.8二次开发入门：解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
