Dr. Pankratz was able to play matchmaker today when he reintroduced me to CCR, my capstone semester project. After a brief discussion in Dr. Pankratz’s office, CCR and I decided it was time to revive our relationship after a long 2-year separation. With stars in our eyes, we found ourselves in that “new love” stage where we are sure to spend countless hours getting reacquainted with each other, finding out what has gone on in each other’s lives over our years apart.

I know there has been someone else in CCR’s life since we were last together. I have been told that a gentleman by the name of Jeremy Vosters spent a considerable amount of time with CCR only a year ago. Already I have begun to see a great maturity that Jeremy was able to bring out of CCR. Although I don’t want to think about separating again this early in our rekindled relationship, I do hope that when we split in May, I will have left a similar mark on CCR.

What can be more terrible for a relationship than to find that it has gone stagnant and cannot move forward? In hopes to avoid or prevent this from happening in my relationship with CCR, I am going to spend the semester working with it to manage the deadlock problem. My first plan of attack will be to lay out the areas in which deadlock can occur. Upon evaluating these problem situations, I hope to find a pattern so that I can better detect deadlock so that it can be avoided or prevented in the future.

top

Today I took my first real glance at the problem at hand. Following the initial meeting, I began running situations of deadlock over and over in my head, but was unable to really appreciate the scale of the problem until I sat down today with a piece of paper and pencil.

I began by looking at my Operating Systems notes from last year to find out what actually constitutes deadlock and the various methods of dealing with it. Seeing as I am a visual learner, my next step was to draw up a map of CCR’s track so that I could start by running two paper trains around it in opposite directions. I primarily looked for situations where the two trains could run into each other if action isn’t taken. While in some situations there is a way to avoid the collision (redirect traffic), there are other situations where they are facing each other head-on and neither train can remain moving. Where traffic could be redirected, I indicated it on my spreadsheet of total possibilities as being a member of one of five different critical regions. Where the trains will hit head-on and there is no way to redirect traffic, I indicated it as being in a state of deadlock. While I’m still not sure I have gone about this in the correct way, it has helped me to at least organize my thoughts into actual vs. potential problems when trains are running in opposite directions. (Currently two trains traveling in the same direction will never be in deadlock, so this situation was not researched.)

Dr. Pankratz and I met today to go over my ideas of deadlock and it seems as though I was on the right track (pun intended). The condition for two trains to be in deadlock is in fact if they are facing each other head-on in hopes to, at one point, be where the other train is. If this is detected, recovery is still possible and in some cases could be avoided all together. Order of operations would tell me that I have to begin by looking at how I can get the system to detect these deadlock situations. That is where I’ll start, however I can’t help but look to the future of where this is going to take me…keeping the big picture in mind.

In the future, once deadlock is detected, it will need to be recovered and we discussed a few ideas as to how that might happen. The solution I like best right now will have the same basic steps for a recovery sequence. The basic idea is a Y-turn. This will have one of the trains pull into the nearest turnout (this may be in front of it or behind) allowing the other to continue on its desired path. The train in the turnout will then be backed out of the turnout and returned to its original path. Thus, both trains will eventually be on the track they began on. (see diagrams)

Diagram 1 – Deadlock Recovery (Caused By Turn Out Status)

Diagram 2 – Deadlock Recovery

The other recovery situations require a detoured in the original route. While this is possible, it doesn’t allow for consistency in recovery patterns.

We also looked at the addition of an additional train and how that would effect deadlock situations.What we found is that you would continue to have a deadlock situation between two of the trains, leaving the other train in a blocked status. (see diagram below)

Diagram 3 – Blocked vs. Deadlocked

Some additional notes that came out of the meeting for me to look into include:

• Difference between batch and interactive modes
• Using batch processing, does each train have its own file?
• When is a turnout locked?
• A turnout is locked when the photocell before it is covered and is not released again until the photocell after it has been covered. (1/24/02)
• How does start up work? (i.e. Are trains detected or is there a standard placement?)
• Currently there is a standard placement that comes from a file. (1/24/02)

Today we took a tour of the train. There have been some additions since the last time I had visited – they look nice! Anyway, while we were there, we discovered a problem that I will have to address. Two trains were running in the same direction in the figure eight. The two trains collided into each other in the center (turn out 6). I will need to look into how the inner loop is treated in Jeremy’s operating system to see if there is a flaw in logic that might have caused that to happen. We also looked at the log file that was generated during the session and found that it had documentation for a train 0 although there isn’t a train 0. I might also have to look into how this log file is generated. However, if I’m really good I might be able to get Jeremy back here to fix the problems in his portion of the OS…ok, so maybe that is wishful thinking.

Today I sat down with Dr. McVey to go over Jeremy’s OS (VOS as I like to call it – Vosters’ OS as well as Jeremy’s nickname) that he built last year for his semester project. Upon looking for the reason the two trains might have collided during my tour the day before, I took a deeper look into the resource manager and its functions. I was specifically looking at the order in which arrivals and departures were handled (arrivals are in fact handled before departures) as well as the function calls within these events. I also took a look at the log file that was generated from the crash. From the understanding I took away from the few hours I spent looking at the code, I didn’t feel the log file gave us any indication as to why the trains might have collided. I forwarded the log file on to dcp and bmv hoping that their better understanding of Jeremy’s logic might give them insight into the problem. One suggestion made on Friday was that an array might have overlaid another thus destroying accurate information about the trains’ positions. The other suggestion made alluded to a pointer possibly being in limbo…anyone want to go chasing pointer?!? We still only have theories, so I will be doing more research this coming week as to what the problem might be.

top

I received a response to my e-mail from Jeremy today discussing his hypotheses for the collision. Here is what he thought.

“ If you have not run the train since, my best suggestion is to look at the log created by the trains and look at the status of all the managers. The first thing that came to mind when you said that was that somehow there is a racing condition. I do not use threads, however, I always wondered whether or not using MFC and timers didn't automatically begin using threads, because I remember an error occurring in a file called thread or something. (This was a long time ago, I may be mistaken) Note that if threads are used there is a huge racing condition in the arrival and departure methods. Second, check to make sure that all the photocells are working and that it actually allocated and deallocated the correct photocells. I have seen the trains "miss" a photocell before because of a bad sunlight ray or not deallocate a photocell because of a lack of sunlight. Third - Keep in mind that that polling the photocells status is on a timer that clicks every half-second I think. If two trains where to hit the right photocells by infinite at almost exactly the same time, it may be possible that (without threads) it could miss an arrival or departure. ” – Jeremy Vosters

I talked to Dr. McVey later today, showing her Jeremy’s response. We both agree with Jeremy’s first suggestion that it was probably a racing condition, and we are currently pursuing this theory. I found a glitch in the resource manager’s ReleaseBlockedTrains function. The first if statement is correct if this is occurring at a three-way turnout. If it is a four-way intersection, such as the infinity on our track layout, this can become dangerous and could be the racing condition we were looking for. (Investigation continues…)

Today I met with Dr. Pankratz to discuss and go over VOS. Dr. McVey has provided us with diagrams describing Jeremy's functions and how they relate to the Resource and Train Managers. While these remain useful tools, it seems as though the Managers still need another form of pictorial organization. I plan to put together a flow diagram with how the functions interact with each other as well as a current index as to where the functions found. This will allow navigation in this section to move much smoother.

While we were decoding the current code, we did find what seems to be an area of code that could lead to a racing condition. Every time a timer is processes to check the photocell status, it sequetially checks to see if the status of that photocell has changed to signify an arrival or a departure. In either of those cases, it processes the respective event while the other trains continue running. This can prove to be especially dangerous around the infinity mark of the inner figure-eight. While the lower number photocells are processing events, the trains over the larger number photocells continue, and unless processed quickly, could cause a collision similar to the one we saw earlier. One suggestion to possibly help this situation would be to check for arrivals/departures from all photocells before processing the events. Some may argue that this just changes the order of events and does nothing for cutting down the processing time. Then in both cases, the code simply needs to be fast so that this racing condition doesn't yeild many collision occurances.

top

I spent this evening building an index for the resource manager as well as creating a diagram that describes the relationship among functions within the resource manager (let me know if you would like to view this). This should prove to be not only an organizational tool, but will also act as a guide to the relationships that will arise when I insert deadlock functions. Already upon looking through the functions in this light, I gained insight as to where the sections of code are that will prove essential in future deadlock discussions. Also in laying out the diagram, I noticed that there was a recursive loop between HandleDeparture, DeallocateResources, and ReleaseBlockedTrains. I will have to investigate this a little further.

Dr. McVey stopped by while I was organizing the Resource Manager. We discussed the idea of a timer and what affect that has on the event queue. She told me that each object could have one timer in the queue at a time. We also talked about how the user screen, in addition to the resource manager, has an array structure for photocells. We will need to locate in the code how that array is filled, by copying the array structure from the resource manager or by poling the sensors directly on a timer as in the resource manager. If the sensor status is polled on a timer from the user screen, there could be issues with the effectiveness of resource manager's timer since the resource manager is an object of the user screen. This will also be investigated further.

During a meeting with Dr. Pankratz this afternoon, I realized that a picture is worth at least a thousand words...if not more! My diagram of how the functions within the resource manager communicate with each other is really proving to be quite helpful. As a visual learner now looking at other sections of code, I wish that there had been more diagrams describing various data structures as I attempt to understand the book of code. Once a picture had been drawn, the comments seemed to made perfect sense to me. An important lesson was learned for future documentation.

The section of the diagram we focused the most attention to was the recursive loop between HandleDeparture, DeallocateResources, and ReleaseBlockedTrains. In a later discussion with Dr. McVey, she revealed to me that this section could be the main cause for the train collision that had occurred earlier. She took me through the log file that was generated during a similar (more recent) crash. It seems as thought a train can pass over multiple photocells in the time it takes to finish a recursive call to HandleDeparture. Dr. McVey and Dr. Pankratz are going to spend time trying to eliminate the recursive call while I focus my attention more toward the deadlock problem ahead of me. We are going to be meeting early next week to go over the critical sections of code and discuss my ideas for detecting deadlock.

top

Today I put together a function that will check the linked list of blocked trains for deadlock. I have also noted the place in the function ActiveToBlocked where it will be called. I still have a few questions as to how my new functions will fit into the existing resource manager, but that will be discussed in our meeting later this week. I have not compiled the code yet to test its effectiveness. I hope to talk with Dr. Pankratz about the integration of this into the existing code tomorrow. Then, go on to test it on the working OS.

I met with Dr. Pankratz this afternoon to discuss the function I had written yesterday. Although the function would probably work for the two-engine set-up we currently are running, it doesn't allow for expansion for additional engines. After the meeting, I reworked the original function to look for deadlock among multiple trains. In doing so, I created an array that will hold train ids and the resources associated with them (current photocell and requested/blocked photocell). I created a simulator that will allow me to enter this information (processes and their resources) locally to be checked for deadlock. Once I ironed out the bugs in the simulator, I modified the function that fills the array to allow the array to be filled with information in the linked list 'BlockedTrains'. The independent functions are on the g-drive as well as the modified ResourceManager.h file. (Since the Resource Manager is a class, all resource manager functions must be defined in the header file along with the object definition.)

top

During a previous meeting, Dr. Pankratz and I looked over my code that checks the system for deadlock. He suggested that my original array data structure be modified into an indexed array structure, using the current photocell as the index. I implemented that today and it really cleaned up the code nicely. (This code is currently on the train's computer only... it will be moved to the g-drive shortly.) I then tried to test the code on the layout, but when I went to rebuild the project, the computer ran out of memory and I was never able to see it work. Earlier today, Dr. McVey and I sat down to order a new hard-drive for the computer and it should be arriving shortly. Hopefully we can get that installed soon so I can see the code in action!

top

I started to organize my thoughts this weekend for my own sanity as well and for the walk-through this next week. I won't bore you with the details of previous work seeing as you can read about it in the entries above. I did start to look to the future of deadlock however and have come up with a few ideas, all of which have their positive and negative sides. I am putting my thoughts together and am going to incorporate them into my walk-through presentation so that I might get the class' ideas as to what might work better than anther. I will add this information to the site on my walk-through entry to keep everything together.

top

Today I met with Dr. Pankratz to go through my ideas on recovering from deadlock. We discussed the idea of having a single repetitive solution that would work in all cases. For instance, when trains are participating in deadlock, one train (possibly the one who ultimately caused the deadlock) would back up until it passed a turnout in which it could travel down a side path in hopes that the other trains could then resolve to their original path.

We also discussed the issues involved with interactive vs. batch processing. We concluded that interactive processing was much too difficult to recover from since the user can continually change the status of the turnouts while trains are trying to resolve deadlock. Thus, we looked at the batch processing option. Patch files could be called when deadlock occurs. The patch file would resolve the deadlock and then return the processing back to the original file for processing.

Today I began to diagram the deadlock situations and the recovery options. When trying to move one train out of the way of deadlock, there are two situations that it can encounter, one where it is coming from the branch of the 'Y' having to get to the other branch and the other is coming from the stem of the 'Y' going to the empty branch.

In situation 1, the train can simply move to the available branch thus out of the way of other trains when put back into motion. Situation 2 however requires the train to move past the turnout, stop, change the turnout and train direction, then follow the empty branch to get out of the way for the other trains to pass by. To return the displaced trains to their original position, the steps will be reversed. Thus, situation 2 will ultimately have more steps to process than situation 1 for recovery. In my mind, that makes situation 1 more optimal than situation 2.

In either situation however, to choose only one for a recovery pattern could cause problems. In some cases, you will need to pass many available turnouts to get one that will put the train in the correct position. If there are other trains on the track however, you may not have the privilege of going that far before confronting another train, thus possibly creating another situation of deadlock. This new situation of deadlock could have been avoided had one of the other available turnouts that was passed had been used.

Today I gave my walk through presentation to the class. There was a great suggestion to stack the situations of deadlock as they occur (this may have been discussed in my meeting with dcp earlier this week). This could make the idea of a single solution possible.

In listening to suggestions and applying them to the different situations of deadlock, I realized that the patches applied to batch processing will need to be unique for each train position (commands from a batch file are particular down to exact photocell number). Now, looking at the problem in that light, the patch can be created for each specific turnout using the steps for the situation the train is in.

top

I made my way over to the train a number of times today. Over spring break, the new motherboard was installed into CCR's PC. My first attempt at trying to make the trains move since the new instillations failed miserably. Not having much of a hardware background, I had no idea where to start looking for problems. I found myself back in Cofrin later that afternoon to get back-up for my next attempt at getting the trains to move via the operating system.

Dr. Pankratz took a look at the system and realized the train was connected to the wrong comm port. With a flip of a cord, the train was back in business (almost... there were some bugs in the enhancements Dr. McVey has made to the original OS that I am currently running...I'll be talking with her about this tomorrow if DCP hasn't beaten me to it!). I was able to test my deadlock code. The preliminary bugs were worked out after critical information was dumped into the log file for later viewing. There is still an issue of getting the correct deadlock returned, but that will be saved for the next day.

I found my way over to the train again this morning. Dr. McVey came with and looked at the problems DCP and I were experiencing the day before. I also took another look at my deadlock code. The night before, I had made a few changes to the code after looking at the log file output, however I had forgotten to make this correction to one of the function calls, thus returning an incorrect number and throwing off the entire deadlock search. Once that was pointed out to me, the functions worked like a dream! The code was tested in every situation we had trains to simulate. Deadlock has been detected!

top

Today, Dr. McVey and I started our road trip down to visit grad schools. During the rather lengthy car ride, we discussed my problem of deadlock and some of the issues I am having with solving it. She had offered an idea to me that I could visualize an implementation for. As discussed in my walk through, it would be a fairly easy set of instructions to recover from deadlock if there existed a turnout between the participating trains. Looking at our track in specific, I know that this doesn't always happen, that is why I was trying to come up with alternate ways of recovery. She suggested that instead of moving just one train in search of a turnout, I might move both simultaneously until that situation occurred. After thinking about how that would play out and running it through different cases in my head, I realized that it had great possibilities for many reasons. It brought deadlocked trains into a uniform situation, thus a single recovery algorithm could be devised. I also looked at the implementation for a loop of trains (rather than two trains facing each other in deadlock) and although track-specific, there is always a turnout between each of the maximum of three trains that could create that loop. Less track-specific, unless the track is a single loop, somewhere there will be a turnout between two trains participating in the circle of deadlock.

top

I started out this afternoon looking at the implementation of this past weekends brainstorm. I worked out the code at a high level and came up with a few things I wanted to test before I met with dcp later in the afternoon. I was looking at the patch function that would be used once the trains were between a turnout and realized I wasn't sure how to reverse a train. I had a few ideas, but until tested, would remain just that. I slipped over to the train for an hour before my meeting and discovered that in batch mode, you cannot reverse a train! I tried manipulating the batch file for a single train to go back and forth between two photocells. One attempt left the train blocked, while another had the train in deadlock with itself! I copied over the batch file as well as the log file it generated so I could take a closer look at it with dcp.

After talking with dcp, we realized the weekend solution was a bit track specific and he is looking for a more general algorithm. He suggested a simple solution to start out with, plan A if you will. In plan A, a train would back up to the photocell it came from and then resume the trains again (resuming the train that was backed up last so that you weren't faced with the exact same situation of deadlock again). We took a look at how this could be implemented and discovered that the way the operating system is currently designed, this is not possible. The train wishing to back up still owns the resources behind it, thus if you were to manipulate a command so that it might retrace its steps without first releasing the resources it owns, you would have put that train in deadlock with itself. Looking at how to solve this new problem, we realized that resources must be released before an arrival as it currently is coded can be executed. So now that on a high level that was decided, we went back to the drawing boards for the implementation of solution. A great solution was devised if a train stopped on top of a photocell, but there are instances where trains going at higher speeds (who would run the trains at high speeds?) would slide past the photocell and then the general solution that worked before needed to be modified with a case statement.

I have a number of things to look into before the next meeting and I am going to put together and elaborate on the notes gathered from today's meeting so the next meeting we can continue on to the next problems... (Oh yeah, Plan B will come later with "the rest of the story!")

Today I spent some time putting together a high level plan for deadlock recovery. DCP and I had discussed in our last meeting a simple way, in theory, of recovery. I put down the sequence of steps that the operating system would need to take in order for recovery to be possible. Later in my meeting with DCP, we looked closer at the current operating system code to see how it will be integrated and how feasible recovery will be given the current OS tools. We examined a few of the key functions' design. While they work on the current system, we realized that they might need to be altered for my project and for a more robust system in general.

I spent this afternoon working at getting a train to oscillate between two photocells under batch processing. I was having some difficulties with values assigned to the train variables, and the resource log became a great resource for problem solving. When I left, I had a train going back and forth between two photocells.

I spent the afternoon over by the train again. I first cleaned up the code I had written the day before. I had left variable names alone although they were being used for a different purpose, so I renamed variables in the functions dealing with retrieving and manipulating the batch commands. I then looked at reading the initialization of a train from a file. I included the option to include max speed, the direction around the track (clockwise or counterclockwise), and the train direction (forward or reverse). I had tried to write a function that would return the direction a train was going around the track give the current and next photocells, but was having linking error problems that I didn't know how to resolve. I will ask about these on Monday. After looking at those things, I tried to get a train to go from one branch of a turnout to the other and then back to the original branch, which is essentially what I would like to have happen down the road. There were a few glitches, but by the end of the afternoon, I had a train running in the proposed pattern. It was quite exciting to see it work and be that next step closer to a working solution!

top

Today,dcp and I met to discuss the weekend advancements on the train and discuss the next step. Now that one train is able to change direction and manipulate turnouts under batch control, a second train should be added. The addition of other trains creates an issue for blocking which has not been tested for batch processing thus far. There is also an issue of trains rolling past their said photocell while changing direction or having to stop for blocking purposes. These are the next building blocks for solving deadlock.

I spent the afternoon over with the trains attempting to run two engines simultaneously. There was an issue with blocking trains because of how the functions are currently set up. When a train is blocked, it is sent to the linked list of blocked trains. When a resource becomes available, the list is checked for trains waiting for that specific resource and is reissued an arrival. The arrival function under batch control however, grabs the next command from the array of instructions, rather than grabbing the last instruction issued. Thus, the blocking functions needed to be altered to accommodate this under batch processing. Two trains are now running around under batch control, blocking each other, and then continuing on from the correct place in the array of instructions.

I again went to play with the trains this afternoon. I was having many issues however with the sun coming in from the windows. The sun was falsely triggering photocells making them think there were trains in places they were not. Also because of the nice weather, I was driving the trains a little faster than usual (the track was also cleaned since the last time they ran, thus what use to be a slow pace into a sprint). The trains were sliding past on the change of direction command and I saw first hand how important it is to have this situation corrected before I continue on with recovery details. I began looking through existing code and started writing down code. Dr. McVey, dcp, and I discussed later this afternoon my plan for trains sliding past their mark, and we agreed on a way that would work regardless of what direction the train was going. Putting that code into action will be this weekend’s project.

Today I inserted some code into a number of the resource manager and train functions. The train object needed another attribute, an integer that would keep track of the last photocell it had departed from. Thus, if a train departed from a photocell that an arrival was never successfully executed from, one would know that it had slid past in the process of changing directions or blocking. Code was inserted into the handle arrival function, but has not proved successful yet. Will try it again tomorrow.

I again spent the afternoon in PAC. I made some modifications to the code for sliding past photocells and currently have it working like a dream. I increased the speed on the train that is changing directions and allowed the two trains to run together. They blocked each other and the train with higher speeds did in fact slid past a number of photocells. The function is now working like a dream! The next step is to look at sliding past on a stop issued from a block train function. This shouldn’t be much work since the real grunt work was done for changing directions. Once that is taken care of, the building blocks should be in place for recovery!

top

Today I worked on a variety of different parts of my project. I first tested a few more cases of trains sliding by on the code I had running Saturday. I let the trains run their batch processes, and then manually altered their turnarounds so that they would slide by the pc on the turn-around. I also let the trains run a little faster than usual to test the real case at hand. I took a closer look at the function ReleaseBlockedTrains to make sure that it supported a slide by as well...it does! The rest of the afternoon, I spent planning for recovery. I cleaned up some functions and began writing code on a high level and mapping its position in the current OS.

I spent the day making pseudo code a reality. The basic logic was introduced into the system, but there was still a small bug when I left in the afternoon. I took printouts of the code and log file to trace the trains' steps and see where in the code I missed a piece of logic.

I was able to sit down this afternoon, away from the computer and discover where my error was in the recovery code. In doing so, I not only found the bug, but also found a way to simplify another section of code...sounds like a good day right! There was only one small problem. I had the train that was causing the deadlock be the train that tried to fix it. While I thought this was good logic, it lead to trains oscillating back-and-forth like a pendulum, for when one train backed up to relieve deadlock thus allowing the other train to continue, the train that was moved back to active caused the next instance of deadlock. Thus, the trains took turns causing deadlock. I realized there needed to be a pre-emptive priority put into effect. By prioritizing trains, it creates an order for trains to be used in recovery.

A third train also appeared on the tracks this afternoon! :) I tried placing three trains on the track to test my code and finally realized that with the alterations made for deadlock recovery, it would take six engines to create a visual circular deadlock. Six trains and quite a bit of maneuvering...who would have thought it would be that difficult to create deadlock!

I had a quick chat with dcp this morning to go over the idea of prioritizing trains and he agreed that this needed to happen. This afternoon, I implemented the pseudo code that I had put together last night and ran it through some tests. It worked great with two trains, but when I added a third (thus allowing deadlock to occur and have one train blocked), I realized that having the train with the smallest id number move first, would not work the way I had hoped because of the way blocked trains are released. Blocked trains are released by increasing id numbers. Thus, when I had the three trains (two in deadlock and one blocked) two would again take turns being the train to cause deadlock. After watching this play out, I realized that given the way trains are released from the blocked list, the train with the highest id number needed to be the train that would start deadlock recovery. It has been asked, why I chose to chose a train's priority by the id number rather than its position on the track. I have a few answers for this, although I'm told some don't hold as much weight as others. Dr. McVey informed me that in the real world, a train's id represents their pre-emptive priority. Thus, freight trains would have different id numbers than passenger trains. I mentioned that the code I was given at the start of this project supported priority by id number, pre-empting by id number fit best with the current system. Although this might not be the best answer, it does lead to some interesting conclusions. If priority were to be determined by a train's position on the track, additional data structures, cases statements, and track specific code would need to be added. In trying to keep with a general solution, priority based on id number appears to be the best solution.

This morning I met with dcp to go over my idea for avoiding deadlock that I put down on paper last night. My original idea was to not only allocate the next photocell and turnout on an arrival, but also the turnout and photocell(s) in front of that. Thus, there is always a way to 'avoid' deadlock. After our discussion, we realized that what I was doing was not avoidance, but rather prevention (virtually impossible). Although the idea was not correct for avoidance, it made dcp remember a conversation he had had with a few men from the National Railroad Society. They had also mentioned marking the track ahead of what is allocated. After further discussion, we worked out an algorithm for deadlock avoidance. On arrival, a train not only tries to allocate the next resources, but will also mark the photocells following it as "proceed with caution." Thus, if a train arrives and wants to allocate a pc that has been marked "proceed with caution" by another train, it would be blocked and only sent back to the active list when the resource is no longer marked by another train. Granted, this solution might still lead to deadlock, but many situations of deadlock will be avoided by leaving that extra space. This afternoon I put together the pseudo code for this algorithm and this evening I inserted the actual code from my room. I'll go over to PAC tomorrow to try it out. Cross your fingers!

I spent the afternoon testing the code I put together the night before. While it appeared to be working for the first loop around the track, the program would always die when it came full circle. After many attempts at debugging this problem, we found that I was over-writing the pointer to the list of blocked trains with the train id of the engine I was currently running. I had forgotten to check for the -1 case and inadvertantly clobbered a variable outside the boundaries of the array I was attempting to update. Once we finally corrected the section of code that made the program come to a halting stop, the code ran successfully for a single train running around the track. Tomorrow I will test multiple trains.

I spent a few hours over by the train this afternoon testing the new avoidance code on multiple trains. There are a few problems that need to be ironed out. My parents stopped by to see the trains in action thus leaving me trying to fix the errors on the fly. We all know this doesn't work, so I will have to sit down with the code tomorrow and iron out where the problems are occurring. I don't think I'm too far off on logic, so hopefully better news will come in the next journal entry!

top

This afternoon I sat down with the avoidance code and discovered a number of the issues that were causing me difficulty yesterday. I was not too far off...I made a few adjustments and then ran a quick test before I had another meeting.

I again spent the afternoon and evening over by the train. I ran a number of tests on the code I had updated the day before. It seems as though the avoidance code is working as planned, but with the additional testing, I have found a few errors with the deadlock recovery code. I made some minor modifications and ran a few more tests. I left with code in hand to again look over the logic again tonight.

I really broke my code today. I had three trains going around the track and found a sequence that put my code into an infinite loop of deadlock. Two trains were recovering from deadlock, when another train came from behind to block one of the two trains participating in deadlock. Once this happened though, the train that was sandwiched by the other two tried to reverse and recover from deadlock, however in changing directions, it introduced a new instance of deadlock. While that is not usually a problem, in trying to recover from that instance of deadlock, the train still sandwiched between the other trains, again tried to change directions and found itself in the same instance of deadlock it first tried to recover from. The train continued to change directions, each time creating a new instance of deadlock that could not be solved. It was stuck in an infinite loop! After a discussion with Dr. Pankratz and Dr. McVey, we decided that it was necessary to check for a train's recovery potential before actually putting it into action. Thus, the possibility of infinite deadlock will be prevented.

This morning I went to make the modifications I wrote down the night before and tested this new way of recovery. I ran a number of tests and the algorithm is working like a charm! I went back later in the afternoon to run a few more tests and found that a train was out of commission, so the rest of the afternoon went into repairing the train.

I quick went in this morning to run the few tests that I had wanted to look at yesterday. Everything appears to be working...yippee! I did some cleaning in the room while they were running so that moving the train this afternoon would go a little more smoothly. With the help of a number of people, the train was successfully moved down to the auditorium. There seemed to be an issue with lighting, so with the assistance of Jon Russo, we built a structure that will bring a direct light source above the train removing the issue of shadows.

Today I put together my presentation for Tuesday. I had a difficult time deciding what should be included. I would like to go into some detail, but to get to some of that detail would take longer than the time I have allotted. I described my algorithms at a high level, and hopefully went into just enough detail that people could ask questions if they wanted to hear more in depth about any particular algorithm.

I spent the afternoon in PAC's auditorium running through my presentation. It seems as though I gauged the time correctly and my presentation seems to be taking shape. I have asked a CS student to listen to my presentation tomorrow, so that I have given it to someone else before the actual presentation and will hopefully get some feed back as to the depth of the material in the presentation.

top

This morning I had a quick meeting with dcp. We discussed the idea that my current recovery algorithm cannot recover from all instances of deadlock. I discovered yesterday an instance with four trains where it wouldn't be possible to recover from deadlock with the current algorithm. The situation includes two trains facing each other in deadlock and each blocked by another train behind. Thus for the trains in deadlock to be moved, the blocked trains must first be pealed away from the instance of deadlock. While conditional code could be added to fix this instance, more problems then occur when a 5th or 6th train are added to the scenario, blocking the two trains in deadlock. This general algorithm I use would not support this situation of deadlock, and dcp agreed that there is only so much one can do, only so much track available to move trains around on, etc.

This afternoon, before the presentations, I practiced my speech in front of another CS student to not only give me practice in front of an audience, but to also check the level and content of my presentation. He gave me the thumbs up, so now I just have to wait for tomorrow!

Today I gave my final presentation. I made a few modifications to my presentation with ideas from yesterday's presentations, and walked through my presentation a few times before the actual run. The presentation seemed to go smoothly, despite my nervousness and parents surprise visit, and I'm finally able to breath!

These past few days I have been commenting code and putting together my final documentation that will be handed in on Monday. I have been putting together a few instructional documents and trying to come up with an organized format to put all this information in. I think I'm ready to hit the printers after this!

Today I handed in the final documentation for review. I hope you have enjoyed these journal entries and I encourage you to view the rest of my documentation I have placed on this website.

top