Searching feasible resources to reduce false-positive situations for resolving deadlocks with the Banker's algorithm in railway simulation. Issue 1 (June 2017)

• Record Type: Journal Article
• Authors: Cui, Yong; Martin, Ullrich; Liang, Jiajian
• Is Part Of: Journal of rail transport planning & management. Volume 7:Issue 1/2(2017)
• Page Start: 50
• Page End: 61
• Publication Date: 2017-06
• Subjects: Railway simulation -- Deadlock -- Banker's algorithm -- Reduction of false-positive situations -- Feasible resources; Railroads -- Periodicals; Railroads -- Planning -- Periodicals; Railroads -- Management -- Periodicals; Railroads; Railroads -- Management; Railroads -- Planning; Periodicals; 385.068
• DOI: 10.1016/j.jrtpm.2017.05.001
• Languages: English
• ISSNs: 2210-9706

Abstract

Abstract: The deadlock problem is a well-known challenge in synchronous simulation for railway planning and operations. The Banker's algorithm is a classical solution for deadlock avoidance, and has also been applied in the field of railway simulation. Once a train passes the deadlock-free test with the Banker's algorithm, a deadlock-free situation can be guaranteed. However, any false-positive situation in resolving deadlocks will limit the efficiency and the usability of railway simulation. In a false-positive situation, a request, which may not actually lead to a deadlock, will still be rejected due to a failed deadlock-free test. Hence, waiting time is unnecessarily increased, and the efficiency of the simulated railway operations is reduced. In this paper, a method to determine feasible resources is developed to reduce these false-positive situations. Through applying the Banker's algorithm and feasible resources, the developed method can be conceived as a combination of deadlock prevention and deadlock avoidance. As a complement with limited computational efforts and simple logic, the method to identify feasible resources with deadlock prevention can efficiently decrease the waiting time caused by false-positive situations. Since the developed method using deadlock prevention is only applied from the current position of the tested train to the feasible resources, the inflexibility of being blocked by the entire line with deadlock prevention can be avoided. The implemented case study shows that the applied method can avoid deadlocks and reduce false-positive situations efficiently. Within it, the rate of rejected requests is reduced from an initial value of 38.35%–3.23%, and the rate of reduction of false-positive situations is 22.22% for the total requests of infrastructure resources. Its usability has been proven for a large scale network with a high density of train movements. Highlights: Reduce false-positive situations with the Banker's algorithm. Deadlock avoidance and prevention in railway simulation. A high level of efficiency and usability can be achieved for resolving deadlocks. Its usability has been proven for a large scale network with a high density of train movements.