Update: Deadlocking

As part of the requirements for the project TOS is meant to handle some OS concepts like deadlocking. With the deadline coming quickly I was not sure if I would be able to implement any deadlock related code. What I decided to do was try and come up with a minimal change solution. The plan was to leverage the existing code as much as possible so that if my plan did not work out it would be easy to comment out changes and get back to the working version. The design that I came up with was quite intuitive and did not take too much thinking, luckily on a train track its very easy to spot deadlock. Deadlock only occurs on a train track when there each possible exit of a given section is attempting to enter your section. For example in a section shaped like a U, where the endpoints of the section fall at the tips of the U and one in the middle, a train (A) traveling down the left arm would be headed towards a deadlock if another train (B) were heading down the right arm. If A were headed down the left but B was headed up the right instead of down then B would eventually exit the section and A would be able to proceed. The algorithm for checking for deadlock then is quite easy, when a train enters a new section it must check if all adjacent exit sections are occupied and are heading in the opposite direction to it. I decided that the train that enters last, the one causing the deadlock, should be destroyed to prevent deadlock and allow the other trains to proceed. Below is the whiteboard mock up of the algorithm.

In code the solution proved to be as minimal as I would of liked and was implemented about two hours after the initial algorithm was developed. When a train enters a section the track checks if its the client’s train. If no nothing happens, if deadlock were to be coming the other client would have dealt with it already. If it is our client train then the track checks where the train will be exiting. For each of the potential sections that the train will exit to the track checks if it is occupied, if not then no deadlock. If the exit section is occupied then we check which way it is currently oriented, if it is not towards the endpoint that we are heading towards then no deadlock, that section will clear. If any section reaches the no deadlock threshold then we return happily but if all of them meet deadlocking criteria we remove the client train.