Time limiting a method in C#

Question

I have a Game framework where there is a list of Bots who implement IBotInterface. These bots are custom made by user with the only limitation that they must implement the interface.

The game then calls methods in the bots (hopefully in parallel) for various events like yourTurn and roundStart. I want the bot to only spend a limited amount of time handling these events before being forced to quit computing.

An example of the kind of thing i'm trying is : (where NewGame is a delegate)

Parallel.ForEach(Bots, delegate(IBot bot)
                {
                    NewGame del = bot.NewGame;
                    IAsyncResult r = del.BeginInvoke(Info, null, null);
                    WaitHandle h = r.AsyncWaitHandle;
                    h.WaitOne(RoundLimit);
                    if (!r.IsCompleted)
                    {
                        del.EndInvoke(r);
                    }
                }
            );

In this case I am forced to run EndInvoke() which might not terminate. I cant think of a way to cleanly abort the thread.

It would be great if there was some kind of

try { 
 bot.NewGame(Info);
} catch (TimeOutException) {
 // Tell bot off.
} finally {
 // Compute things.
}

But I dont think its possible to make such a construct.

The purpose of this is to gracefully handle AI's who have accidental infinite loops or are taking a long time to compute.

Another possible way of tackling this would be to have something like this (with more c# and less pseudocode)

Class ActionThread {
    pulbic Thread thread { get; set; }
    public Queue<Action> queue { get; set; }

    public void Run() {
        while (true) {
            queue.WaitOne();
            Act a = queue.dequeue();
            a();
        }
    }

Class foo {
    main() {
        ....
        foreach(Bot b in Bots) {
            ActionThread a = getActionThread(b.UniqueID);
            NewGame del = b.NewGame;
            a.queue.queue(del);
        }
        Thread.Sleep(1000);
        foreach (ActionThread a in Threads) {
            a.Suspend();
        }
    }
}

Not the cleanest way but it would work. (I'll worry about how to pass paramaters in and take return values out later).

[Further Edit]

I'm not too sure what an appdomain is, from the looks of it I could do so, but it cant see how it would help

I hope not to expect malicious code. Trying to kill the other bots threads is not a valid way to win the game. I just wanted to give every bot a second to compute then move on with the gameflow so mainly expecting slow or bugged code here.

I'm trying to see what I can do with Task, getting somewhere slowly.

I'll read into what CAS can do, thank you guys

[More Edit]

My head hurts, I can't seem to think or code anymore. I'm setting up a message pass system to a dedicated thread per bot and will suspend/sleep those threads

I have decided that I will use a fully socketed server client system. So that the client can do whatever it wants and I'll just ignore if it refuses to reply to server messages. Pity it had to come to this.

Answer 1

A .NET 4.0 Task gives you considerably flexibility with regard to cancelling.

Run the delegate in a Task that you've passed a CancelationToken into, like this.

There's a fuller example here.

edit

In light of the feedback, I believe that the right answer is to follow this plan:

1. Limit the AI using CAS, so that it can't access threading primitives or mess with files.

2. Give it a heartbeat callback that it is morally obligated to call from inside long loops. This callback will throw an exception if the thread has taken too long.

3. If the AI times out, log a weak move for it, and give it a short amount of time to call that callback. If it doesn't, just put the thread to sleep until its next turn. If it never does snap out of it, it will keep logging weak moves until the process kills it for being a background thread.

4. Profit!

Answer 2

One option is certainly to spin up a new Thread yourself, rather than relying on BeginInvoke. You can implement the timeout via Thread.Join and (unceremoniously) kill the thread, if necessary, via Thread.Abort.

Answer 3

Unfortunately there is no 100% safe way to terminate a thread cleanly, as you seem to want.

There are many ways you can try to do it though, but they all have some sideeffects and downsides that you might want to consider.

The only clean, safe, and approved, way to do this is to get the cooperation of the thread in question and ask it nicely. However, this is only a 100% guaranteed way if you're in control of the code. Since you're not, it won't be.

Here's the problem.

• If you do a Thread.Abort, you risk leaving the appdomain in an unsafe state. There could be files left open, network or database connections left open, kernel objects left in an invalid state, etc.
• Even if you place the thread into its own appdomain, and tear down the appdomain after aborting the thread, you can't be 100% safe that your process won't have problems in the future because of it.

Let's look at why cooperation isn't going to be 100% either.

Let's say the thread in question often needs to call into your library code, in order to draw on screen, or whatnot. You could easily place a check into those methods, and throw an exception.

However, that exception could be caught, and swallowed.

Or the code in question could go into an infinite loop that doesn't call your library code at all, which leaves you back to square one, how to cleanly kill the thread without its cooperation.

Which I already said you can't.

There is, however, one method that might work. You could spawn the bot into its own process, then kill the process when it times out. This would give you a higher chance of success because at least the operating system will take care of all resources it manages when the process dies. You can of course have the process leave corrupted files on the system, so again, it's not 100% clean.

Here's a blog entry by Joe Duffy that explains a lot about these problems: Managed code and asynchronous exception hardening.

Answer 4

As I mentioned on @Lasse's answer, you really should consider using Code Access Security to limit what the bots are allowed to do on the system. You can really restrict what the bots are allowed to do execution wise (including removing their ability to access threading APIs). It might be worth considering treating each bot as if it was a virus since you aren't in control of what it could do to your system and I'm assuming that your game will be running as a full-trust application.

That said, if you restrict what each bot does with CAS, you may be able to terminate the thread without fear of corrupting your system. If a bot is stuck in an infinite loop, I suspect that your only recourse will be to terminate the thread since it will, programatically, never be able to reach any code that would check for a Thread.Abort signal.

This MSDN article may give you some guidance on how to more effectively terminate a run-away thread using a TerminateThread function.

You really have to try all of these things out and prove to yourself which may be the best solution.

Alternatively, if this a competitive game and the bot authors have to play fair, have you considered having the game give each bot a "turn token" that the bot has to present with each action that it wants to invoke and when the game flips turns, it gives all the bots a new token. This may allow you to now only have to worry about run-away threads and not robots who take to long on their turn.

Edit

Just to add a place for people to go look Security Permission Flag Enumerations will give you a sense of where to start. If you remove the SecurityPermissionFlag.ControlThread permission (as an example, only giving the code permission to execute and excluding ControlThread) you will remove their

Ability to use certain advanced operations on threads.

I don't know the extent of the operations that are inaccessible, but it will be an interesting exercise for the weekend to figure that out.

Answer 5

another design option may be to allow each bot to be its own process, then use an IPC mechanism to exchange data. You can usually terminate a process without any terrible repercussions.

Answer 6

I think the only problem is an inverted conditional. You should call EndInvoke only if the task completed successfully.

Rough suggestion:

var goodBots = new List<IBot>();
var results = new IAsyncResult[Bots.Count];
var events = new WaitHandle[Bots.Count];
int i = 0;
foreach (IBot bot in Bots) {
    NewGame del = bot.NewGame;
    results[i] = del.BeginInvoke(Info, null, null);
    events[i++] = r.AsyncWaitHandle;
}
WaitAll(events, RoundLimit);
var goodBots = new List<IBot>();
for( i = 0; i < events.Count; i++ ) {
    if (results[i].IsCompleted) {
        goodBots.Add(Bots[i]);
        EndInvoke(results[i]);
        results[i].Dispose();
    }
    else {
        WriteLine("bot " + i.ToString() + " eliminated by timeout.");
    }
}
Bots = goodBots;

Even better would be to explicitly spin up a thread for each bot, that way you could suspend the misbehaving bots (or dial down their priority) so that they don't continue to steal CPU time from the good bots.