Pause a thread until a method and all the threads inside finish their work?

Question

I'm new to threads and I was wondering how to use them to make an evaluation in a non deterministic finite automaton.

I have the method that calls another method:

public bool Evaluate2(string s)
{
    accepted = false;

    ThreadEval(s, StartState);            

    return accepted; 
}

variable accepted is a class member and I'm using it to control when the other threads should stop.

void ThreadEval(string s, State q)
{            
    if (s.Length == 0 && q.IsFinal)
    {
        accepted = true;
        return;
    }

    bool found = true;            
    State current = q;

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                Thread thread = new Thread(new ThreadStart(delegate { ThreadEval(s.Substring(i+1), t.to); }));
                thread.Start();
                found = true;
            }
     }
}

Each of my states has a set of transitions. A transition is composed by a symbol and the state it can go by consuming that symbol. So whenever if find a possible transition, I want to create a new thread and examine the rest of the string (without the current character)...

I'm currently having 2 problems:

• The "return accepted" is being executed before the all the threads created inside ThreadEval finish them. Is there a way to assure it wont return until those threads finish? I've put a Thread.Sleep(200) before the return and it worked but 200 ms might not be enough for big strings and I also don't want to raise the value so small strings will take longer than they should to be processed.

• The code the way it is was leading to some indexing exception... I'm 99.999% sure that it is correct the way it is but it would only stop crash if I call the Substring passing the value i instead of i + 1 ... but if I call with just i it would never get to the end of the string and depending on the automaton configuration might lead ton infinite loop. I don't know exactly how threads work but I suspect that maybe some parallel processing is changing the value of i before the Substring slicing. How can I assure that whenever I call a new thread I'm discarding only the current char?

If anyone have any suggestion in how to use the threads with more elegance I'd be grateful, so far the only way I found to pass parameters in the function the thread was assigned to was to use the delegate.

Answer 1

In order to block until a thread t executes to completion, you could use Thread.Join.

t.Join();

This puts the main thread in an IDLE state until thread t completes. This means you'd have to keep track of all the threads created inside the foreach loop and then join them one by one.

A better way would be to use TPL's Task<T> instead of directly using threads. Your code would go somewhat like this:

Task ThreadEval(string s, State q)
{
    //...

    List<Task> tasks = new List<Task>();

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                tasks.Add(
                    Task.Run(
                        () => await ThreadEval(s.Substring(i+1), t.to)));
                found = true;
            }
     }

    return Task.WhenAll(tasks);
}

await ThreadEval(...);

1. Change the signature to return a Task instead of void
2. Create a list of all running tasks
3. Task.WhenAll will create a new task that will be marked as complete when all tasks inside the tasks list are themselves marked as complete. Return this task.

The caller will then await ThreadEval.

Answer 2

I think the async/await patter will help you here. Then you can do something like:

List<Task> runningEvals = new List<Task>();

async Task ThreadEval(string s, State q)
{            
    if (s.Length == 0 && q.IsFinal)
    {
        Task.WaitAll(runningEvals.ToArray()); // wait for all tasks to finish
        runningEvals.Clear();

        accepted = true;
        return;
    }

    bool found = true;            
    State current = q;

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                // start a task and add it to the "running tasks" list
                var task = Task.Run(async () => await ThreadEval(s.Substring(i+1), t.to));
                runningEvals.Add(task);
                found = true;
            }
     }
}

ATTENTION: This is not tested code (and is definitely not "thread-save" because of the "shared List<Task>), but should only point you into a direction.

This can be called "asynchonous" via:

await ThreadEval(s, StartState);

or if you can not go "async all the way up" (and only then):

ThreadEval(s, StartState).Wait();

Answer 3

Wrote a little example to help you understand how this could be done https://dotnetfiddle.net/2Djdh7

Basically you can use the Join() method to wait for a thread to finish, and by using the ForEach() method on a list of threads you can wait for all threads to finish in a single line.

public class Program
{
    public static void Main(string[] args)
    {
        List<int> list = new List<int>();
        list.AddRange(new int[] {10, 200, 300, 400, 234 });

        // create a bunch of threads
        List<Thread> threads = new List<Thread>();
        list.ForEach(x => threads.Add(new Thread(() => ThreadMethod(x))));

        // start them
        threads.ForEach(x => x.Start());

        // wait for them to finish
        threads.ForEach(x => x.Join());

        // this will not print untill all threads have completed
        Console.WriteLine("Done");
    }

    private static void ThreadMethod(int i)
    {
        Thread.Sleep(i);
        Console.WriteLine("Thread: " + i);
    }
}

Output:

Thread: 10
Thread: 200
Thread: 234
Thread: 300
Thread: 400
Done