On Deadlock-Avoidance, Livelock-Avoidance and Performance Improvements in Discrete Event Systems: A Collection of Open Problems

离散事件系统中的死锁避免、活锁避免和性能改进：一系列开放问题

• 批准号: 0000938
• 负责人: Ramavarapu Sreenivas
• 金额: $ 18.36万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0000938&HistoricalAwards=false
• 关键词: Deadlock; Avoidance; Livelock; Performance; Improvements

In this proposal we consider a large class of discrete-state systems such as traffic networks, manufacturing systems, computer networks, distributed/parallel computing. A livelock in such systems is a situation when some process is unable to finish because its clients perpetually create more work for it to do after they have been serviced. This phenomenon is different from that of a deadlock where there is essentially no activity as each process is perpetually in a state of waiting, anticipating the release of resources that are held by other processes. The issue of deadlock- and livelock-avoidance is particularly important to the synthesis of protocols, routing, cache/memory management, computer operating systems, manufacturing systems, traffic management, operations management of large organizations, etc. In this proposal, we present a collection of open-problems in the synthesis of supervisory control policies that guarantee liveness (i.e. absence of deadlock and livelock) in Petri net (PN) models of the discrete-state systems described above. We also present some open-issues in the performance improvement of PN models that are deadlock- and livelock-free under supervision.

在这个建议中，我们考虑了一大类离散状态系统，如交通网络，制造系统，计算机网络，分布式/并行计算。这种系统中的活动锁是指某些进程无法完成的情况，因为它的客户端在服务完成后不断地为它创建更多的工作。这种现象与死锁不同，死锁基本上没有活动，因为每个进程都永远处于等待状态，等待其他进程持有的资源释放。避免死锁和活锁的问题对于协议、路由、缓存/内存管理、计算机操作系统、制造系统、流量管理、大型组织的运营管理等的综合尤为重要。在本建议中，我们提出了在上述离散状态系统的Petri网（PN）模型中保证活动性（即没有死锁和活锁）的监督控制策略综合中的一系列开放问题。我们还提出了在监督下无死锁和无活锁的PN模型的性能改进中的一些开放问题。