1

I'm working on rearchitecting a game engine in which multiple concurrent scripts run in parallel threads, which unfortunately occasionally gives rise to race conditions. I'm trying to set it up so that all the game logic will run in the same thread, and any blocking call will run as async.

Rendering needs to absolutely have the highest priority, to maintain the frame rate. After rendering, there will be so many milliseconds left in a frame. So what I need is some sort of Task scheduler that will run scripts in this time while preserving the invariant. From a bit of research, it appears that a custom SynchronizationContext might be part of the solution, but I don't know enough about the nitty-gritty details of async to work it all out.

What I need it to be able to do:

  • Keep track of all scheduled Tasks that are not currently blocked on an await and are ready to run.
  • When the Run(int time) method is called, it has time milliseconds to run as many of these Tasks with outstanding work as possible.
  • Return once the time is up, or when there are no more non-blocked Tasks to work on, whichever comes first.

Does anyone know how I would go about writing such a thing?

  • I have a suspicion you might not be able to enforce bullet point two entirely in userland, as you need kernel mode access to halt a thread and switch contexts. If you can guarantee/assume your scripts will play nice you might be OK though. – whatsisname May 21 '17 at 5:52
  • @whatsisname Yes, I'm aware of CPU task-switching and the overhead involved there, and I've measured it under different conditions to see how big of a distortion it will create. Let's just say that, for the purposes of this question at least, that's not relevant. – Mason Wheeler May 21 '17 at 9:20
  • How will the scheduler know how much time Task A needs to execute? What will the scheduler do if Task A consistently needs more time than what is left in the frame time? What should happen if the time is up right in the middle of a modifying operation on a variable that is shared with the rendering context? – Bart van Ingen Schenau May 21 '17 at 10:15
  • @BartvanIngenSchenau Because any blocking call runs asynchronously, it's reasonably safe to assume that each individual script call will take a negligible amount of time to either run to completion or hit an await. So subtracting a small amount of time from the time limit should keep the script runner safe. I'll have to profile this to find out for sure about the timing involved, but I'm guessing that 1-2 ms should be enough. (Yes, a malicious or particularly stupid script that goes into an infinite loop could hang the whole thing, but there's not much I can do about that, so why worry?) – Mason Wheeler May 21 '17 at 10:21
  • @MasonWheeler: i'm not talking about the performance of the switch, but that the tasks have to provide places for execution to stop and trade off. In otherwords, you need to do cooperative multitasking, and have everyone play nice, because I don't believe you can do preemptive multitasking, e.g. you can't halt your thread in any old place, only the OS can do that. – whatsisname May 21 '17 at 21:25
3

Requirements

Let us see what you want:

I'm working on rearchitecting a game engine in which multiple concurrent scripts run in parallel threads, which unfortunately occasionally gives rise to race conditions.

This tells me that you already have some form of parallelism in place. I am working blind because I don't know how well will my solution fit your code.

I'm trying to set it up so that all the game logic will run in the same thread, and any blocking call will run as async

This means that we will need a loop where this thread takes the tasks. I will assume this is main your game loop, it does not have to be.

Keep track of all scheduled Tasks that are not currently blocked on an await and are ready to run.

This is trivial, because the SynchronizationContext will get a call on each await once it is ready to continue.

When the Run(int time) method is called, it has time milliseconds to run as many of these Tasks with outstanding work as possible.

I assume this is what you want to call on the loop. We will have to make the Run method on the SynchronizationContext.

Return once the time is up, or when there are no more non-blocked Tasks to work on, whichever comes first.

The Run method will have to keep track of time.


Implementation

As others has pointed out in the comments, a method could run for longer than the given time, and there is no way to tell beforehand how long it will take. You cannot fix this without the cooperation of the async code.

In addition, it is very likely that the time taken by Run will overshoot due to overhead.


With that said, the code is trivial:

public class CustomSynchronizationContext : SynchronizationContext
{
    // Keeps track of the Tasks that are are ready to run
    private readonly ConcurrentBag<Action> _tasks = new ConcurrentBag<Action>();

    // Gets called on to continue after await to schedule the continuation
    public override void Post(SendOrPostCallback d, object state)
    {
        // If you want to know, state is the actual Task
        // The callback is an internal method that executes it
        var callback = d;
        _tasks.Add(() => callback(state));
    }

    // Executes Tasks on the current Thread until the time has been exceeded
    // Return true if it finished because there were no more Tasks
    public bool Run(int milliseconds)
    {
        var start = DateTime.Now;
        while ((DateTime.Now - start).TotalMilliseconds < milliseconds)
        {
            if (_tasks.TryTake(out Action action))
            {
                action.Invoke();
            }
            else
            {
                return true;
            }
        }
        return false;
    }
}

In order to use it, you need to set the CustomSynchronizationContext as current.

You can do so with the following code:

var syncContext = new CustomSynchronizationContext();
SynchronizationContext.SetSynchronizationContext(syncContext);

Now, I have to warn you (you probably know, yet, just in case), there are some easy ways to shot yourself in the foot:

  1. You need to set the SynchronizationContext before any await. If you do it after, who knows on what thread you are setting it (probably one from the ThreadPool). It is possible to set SynchronizationContext in an async method (that you don't await) and have it work correctly (I tested), just do it before any await.

  2. Awaiting in the loop where you call Run. If you await before Run, the code will not get to Run. Similarly if you await after Run, because the code will not continue until the next call to Run, and since it is awaiting, it will not loop to call Run again. In the loop, you have to call async methods without awaiting them.

  3. Starting an async method that you do not await (because of the previous point) with a long operation before any await. The code before the first await will run synchronously. So you probably want to start the async method with await Task.Yield();.

  4. Awaiting async methods that take a long time (in particular those that block the thread waiting on something external, such as network, file system, user input, etc...). Remember that this solution is to schedule the continuations on a single thread. So those async methods that take a long time will ultimately run on that single thread, blocking that single thread. Instead, await on Task.Run for anything that has that problem. I talked more about this problem in Confusion regarding threads and if asynchronous methods are truly asynchronous in C#.


A hidden problem

I did try async code cooperation. My idea here was to have something a long running task can check to see if it needs to await Task.Yield().

This is my solution:

public class CustomSynchronizationContext : SynchronizationContext
{
    // Time at which control must be returned to the caller
    private readonly ThreadLocal<DateTime> _dueTime = new ThreadLocal<DateTime>();
    // Keeps track of the Tasks that are are ready to run
    private readonly ConcurrentBag<Action> _tasks = new ConcurrentBag<Action>();

    // Gets called on to continue after await to schedule the continuation
    public override void Post(SendOrPostCallback d, object state)
    {
        // If you want to know, state is the actual Task
        // The callback is an internal method that executes it
        var callback = d;
        _tasks.Add(() => callback(state));
    }

    // Executes Tasks on the current Thread until the time has been exceeded
    // Return true if it finished because there were no more Tasks
    public bool Run(int milliseconds)
    {
        var dueTime = DateTime.Now + new TimeSpan(TimeSpan.TicksPerMillisecond * milliseconds);
        try
        {
            _dueTime.Value = dueTime;
            while (DateTime.Now < dueTime)
            {
                if (_tasks.TryTake(out Action action))
                {
                    action.Invoke();
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        finally
        {
            _dueTime.Value = DateTime.MaxValue;
        }
    }

    // Returns true if it is time to yield
    public bool NeedsYield()
    {
        if (_dueTime.IsValueCreated)
        {
            var dueTime = _dueTime.Value;
            if (DateTime.Now > dueTime)
            {
                Task.Yield();
                return true;
            }
        }
        return false;
    }
}

I have used ThreadLocal just in case that you want to call Run from more than one thread at a time. I have not added any precations against calling Run recursively.

The way to use this code is as follows:

var context = SynchronizationContext.Current as CustomSynchronizationContext;
// ...
if (context != null && context.NeedsYield())
{
    await Task.Yield();
}

Yet, as my title suggests, there is a problem. Run always takes the first task from the bag, and I found that often the first task from the bag is the continuation of the long running Task, resulting in starving all other tasks. We do not want this!

Because of that, I have rewritten the code to run the oldest task, preventing starvation.

public class CustomSynchronizationContext : SynchronizationContext
{
    private readonly ThreadLocal<DateTime> _dueTime = new ThreadLocal<DateTime>();
    private int _last = int.MinValue;
    private readonly ConcurrentDictionary<int, Action> _tasks = new ConcurrentDictionary<int, Action>();

    public override void Post(SendOrPostCallback d, object state)
    {
        var callback = d;
        _tasks.TryAdd(Interlocked.Increment(ref _last), () => callback(state));
    }

    public bool Run(int milliseconds)
    {
        var dueTime = DateTime.Now + new TimeSpan(TimeSpan.TicksPerMillisecond * milliseconds);
        try
        {
            _dueTime.Value = dueTime;
            while (DateTime.Now < dueTime)
            {
                int? key = null;
                foreach (var first in _tasks.Keys)
                {
                    key = first;
                    break;
                }
                if (key.HasValue && _tasks.TryRemove(key.Value, out Action action))
                {
                    action.Invoke();
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        finally
        {
            _dueTime.Value = DateTime.MaxValue;
        }
    }

    public bool NeedsYield()
    {
        if (_dueTime.IsValueCreated)
        {
            var dueTime = _dueTime.Value;
            if (DateTime.Now > dueTime)
            {
                Task.Yield();
                return true;
            }
        }
        return false;
    }
}

Demo code

The following is the code I wrote while experimenting with this CustomSynchronizationContext. It might be useful for reference:

Note: I'm using GC.KeepAlive to call async method without awaiting because static analysis isn't happy with doing that and not using the return value.

class Program
{
    private static bool _done;

    private static async Task AsyncRunAsync()
    {
        var tid = Thread.CurrentThread.ManagedThreadId;
        Console.WriteLine("AsyncRun Thread Id: {0}", tid);
        await WriteHelloWorldAsync();
        if (tid != Thread.CurrentThread.ManagedThreadId)
        {
            tid = Thread.CurrentThread.ManagedThreadId;
            Console.WriteLine("AsyncRun Thread Id: {0}", tid);
        }
    }

    private static async Task DotMakerAsync()
    {
        await Task.Yield();
        var context = SynchronizationContext.Current as CustomSynchronizationContext;
        var tid = Thread.CurrentThread.ManagedThreadId;
        Console.WriteLine("DotMaker Thread Id: {0}", tid);
        while (!_done)
        {
            Thread.Sleep(40);
            Console.Write(".");
            if (context != null && context.NeedsYield())
            {
                await Task.Yield();
                if (tid != Thread.CurrentThread.ManagedThreadId)
                {
                    tid = Thread.CurrentThread.ManagedThreadId;
                    Console.WriteLine("AsyncRun Thread Id: {0}", tid);
                }
            }
        }
    }

    private static void Main()
    {
        var mcguffin = new CustomSynchronizationContext();
        SynchronizationContext.SetSynchronizationContext(mcguffin);
        GC.KeepAlive(AsyncRunAsync());
        GC.KeepAlive(ReadKeyAsync());
        GC.KeepAlive(DotMakerAsync());
        Console.WriteLine("Main Thread Id: {0}", Thread.CurrentThread.ManagedThreadId);
        do
        {
            mcguffin.Run(1000);
        } while (!_done);
        Console.WriteLine("Done");
    }

    private static async Task ReadKeyAsync()
    {
        await Task.Run(
            () =>
            {
                Console.WriteLine("ReadKey Thread Id: {0}", Thread.CurrentThread.ManagedThreadId);
                Console.ReadKey();
            }
        );
        _done = true;
    }

    private static async Task WriteHelloWorldAsync()
    {
        Console.WriteLine(" {0}:Hello", Thread.CurrentThread.ManagedThreadId);
        await WriteWorld();
        Console.WriteLine(" {0}:!", Thread.CurrentThread.ManagedThreadId);
    }

    private static async Task WriteWorld()
    {
        await Task.Delay(1000);
        Console.WriteLine(" {0}:World", Thread.CurrentThread.ManagedThreadId);
    }
}

If you run the code, you should see that everything is running on the same Thread except Console.ReadKey() because that would block the Thread.

Once you hit any key Console.ReadKey() completes its execution and then _done is set to true. There is no need to worry about thread visibility because _done is only ever accessed from a single Thread (I did not output the Thread id there, but you can do so and verify it).

When _done is true the main loop will end, and thus the application will end.

I'm using Run(1000) you can tweak that value to something larger and see the delays it introduces. For smaller values, it is hard to tell without profiling. If you put Run(0) then none of the scheduled tasks will run.


I would advise to measure what overhead Run has and take it into account. IN particular when selecting (or computing) the value you pass as parameter or alternatively you may anticipate the overhead by subtracting some amount from dueTime. Doing this it has the advantage that it will result in NeedsYield returning true earlier. Yet, it may result in Run executing nothing. Perhaps it would work better with a do...while. I am leaving how to mitigate the overhead up to you.


Even if this code does not work for you, I hope it serves as reference for how to create a custom SynchronizationContext for async and await. You do not have to override any of the other methods. In fact, regular async and await code only ever result in calls to Post.

  • I suggest using Environment.TickCount to keep track of time in infrastructure loops. It doesn't depend on the machine's clock, timezone and DST (better yet, it never decreases) and it's about as fast as DateTime.Now and DateTime.UtcNow. Stopwatch has more precision, but it's slower. Also, TickCount is the most commonly used time measure across all of .NET methods that take a timeout. – acelent May 26 '17 at 22:16
  • As for the approach, I believe an actual TaskScheduler would fit the bill much better. SynchronizationContext's use is contextual, i.e. you set a value somewhere and it has effects later on, while you'd use a TaskScheduler explicity either in Task.Factory.StartNew or when creating a TaskFactory. Also, the actions themselves should receive a CancellationToken to poll from time to time, to know when there's no need to continue. When the timeout elapses, the last running action may stop sooner if its results or effects won't be used or worthwhile anymore. – acelent May 26 '17 at 22:28
  • @acelent for the time there are other ways to go about it, such as DateTime.Ticks (which I have used more frequently) or even using Stopwatch and looking at elapsed time. I didn't think too much about it when writing the answer, in part because there will be some overhead and some error anyway. I went for SynchronizationContext because it is what OP was looking for. I agree that TaskScheduler is capable of the same result. CancellationToken wasn't on OP requirements, they can be worked in. In case it wasn't clear, the millisenconds parameter is to pause the task not to cancel it. – Theraot May 26 '17 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.