Principles and Practices of Interconnection Networks

CHAPTER 14

Deadlock and Livelock

Deadlock occurs in an interconnection network when a group of agents, usually pack-

ets, are unable to make progress because they are waiting on one another to release

resources, usually buffers or channels. If a sequence of waiting agents forms a cycle,

the network is deadlocked. As a simple example, consider the situation shown in

Figure 14.1. Connections A and B traversing a circuit-switched network each hold

two channels, but cannot proceed further until they acquire a third channel, cur-

rently held by the other connection. However, neither connection can release the

channel needed by the other until it completes ...