The conceptual
background |
The model train systemThe train control program partitions into four threads which take care of the following jobs:
The data structures or objects needed are those that represent the topology of the track layout, i.e., of the track sections, their interconnections, the switches involved and their actual status (free, occupied), on the one hand and the trains, i.e., actual positions, status (running, stopped, waiting), and the remaining schedules they have to absolve, on the other hand. The track layout is described in terms of three record structures, of which
diagram of the block status structure (pdf version) A record describing a train includes static entries about the train number and the home (or start) siding, the direction in which the train leaves the home siding (which matters with regard to the KH_ST_.. sidings only), minimal and maximal speed levels (the former must be used when approaching a stop signal), and the actual schedule. Variable entries are the trains priority (which may change dynamically), the number of track sections still left to complete the schedule (which may become relevant with regard to preventing deadlocks immediately befor returning to a KH_ST_.. home siding that may be occupied by another train trying to travel in opposite direction), reed contact counters together with a flag indicating the arrival of new contact signals, and a train status entry. Train schedules are represented as linked lists of simple track section (block) records, chained up in the order in which the trains are to pass through, each containing the block number, the direction in which the train has to move, and a pointer to the next record in sequence. The head record of such a list is the one describing the actual train position. Whenever a train has left the actual track section, its record is taken off the head of this list. The schedule is completed once the list is empty. Yet another linked list of up to eight entries is created and subsequently processed during each cycle through the control program. It contains for each train a request for the allocation of the next track section to which it is supposed to move. The main loop executed by the control thread is depicted in the flow diagram below. flow diagram of the main loop of the control program (pdf version) It begins with reading the latest reed contact settings deliverd by the input/output thread, doing various consistency checks to eliminate possible errors (which do occur quite frequently), relating these settings to the trains that must have caused them, and generating from the train data thus updated the list of requests for next track sections to be claimed. Next this list is evaluated step by step and reservations for the next sections are attempted. If successfull, the status of the train is set to (or kept) running, and the output is prepared to have the switches (if any) thrown in the appropriate positions, the signals set, and voltage applied to the succeeding track section. If the reservation fails either because the section is still occuppied or another competing train has been given preference, all measures necessary to stop the train are taken. Once all trains are done, the compiled output is handed over to the input/output thread which turns it into an instruction to be executed by the interbus master, whereupon the control loop completes a full cycle. The next flow diagram shows in more detail how the request list for next track sections is evaluated. flow diagram for processing the request list (pdf version) The intricacies of reserving track sections for train passage are trickier than the flow diagram reveals. The simplest case is that of a train in some main track section, say IC_LN_i, requesting the next section IC_LN_i+1, with no alternatives to be considered. Then, access to section IC_LN_i+1 can simply be permitted if it is free, otherwise the train must be stopped in section IC_LN_i. Slightly more involved is the handling of trains trying to enter or exit from one of the main line switchyards. A train, say, in section IC_ST_0 of the inner main track and trying to move through section IC_ST_1, which is the default option given by the trains schedule, may get alternatively allocated one of the other two sidings, if IC_ST_1 is occuppied by another train. The choice is made by arbitration if both alternative sidings are free, otherwise the single free siding is taken. No choice is possible, if one of the sidings IC_ST_2/3 is the final destination (home siding) of the train. The train must be stopped in section IC_ST_0 if no siding (or not the home siding) can be had. A single train in one of the main track switchyards, say IC_ST_.., may leave immediately through track section IC_ST_4. With more than one train in the switchyard trying to get out, we have a classical conflict situation with regard to the allocation of section IC_ST_4. It may be resolved in favor of the train with the higher priority, the priorities of the loosing trains may (or may not) be stepped up, and a conflict between trains that have the same priority may be resolved by arbitration. Decidedly more difficult is the situation with trains moving about the pass track. Before a train can enter the pass from the KH_ST_ switchyard, say in clockwise direction, two things have to be made sure to prevent deadlocks: (1) there must be no train in the track sections KH_LN_1 or KH_LN_0 moving in the opposite direction, and (2) at least one of the siding sections KH_LN_3, KH_LN_5 must be free so that the train can safely reach this siding. Likewise, a train trying to leave KH_LN_5 toward the KH_ST_ switchyard must ensure that no train is moving in the opposite direction along the piece of track in between and must also be able to make an advance reservation on one of the sidings KH_ST_1/2/3/4/5. Equivalent measures are necessary for trains moving counterclockwise through the pass. This allows for up to two trains going at the same time through the pass in both directions (and with a little trick, there can be even one more train in either one of the directions). Unfortunately, preventing deadlocks between trains moving in opposite directions, though absolutely essential, is not enough to ensure an orderly overall system behavior. The pass may be monopolized by trains going in one direction, while trains trying to go in the other direction are starving. This phenomenon may be avoided by a fairness control mechanism which lets trains going clockwise get ahead of trains going counterclockwise, or vice versa, only by a small integer value - the so-called synchronic distance - after the exhaustion of which train movement in the opposite direction is enforced. To do so simply requires initializing an up/down counter with some integer value k and incrementing or decrementing it upon each train entering the pass clockwise or counterclockwise, respectively. If the counter hits an upper bound of 2k, no more trains may enter clockwise and the right of way is given to a train trying to go counterclockwise. Likewise, if the counter value drops down to a lower bound of zero, no more train is allowed to enter counterclockwise, and a train may go clockwise. For all counter values in between, trains may go either way, provided no deadlocks can occur. There is still one minor problem left, though. Once the synchronic distance of 2k is exhausted by trains going in one direction, but there is no train waiting to enter the pass in the other direction, the fairness control must be overruled to let trains enter in the old direction until the first train trying to go in the other direction arrives in the KH_ST_ .. switchyard. What may look like a rather trivial solution takes quite a number of lines of code to implement. Jürgen Noss 05.08.2003 |