Synchronizing access to a collection

Question

I have these two pieces of code that could possibly be run at the same time on two different threads:

users = (from user in users
         orderby user.IsLoggedIn descending ,
                 user.Username
         select user).ToList();

and:

users=null;

The second piece of code will run on the main UI thread of the application. How can I prevent users to be set to null before the LINQ operation completes? Encapsulating the user collection in a property with locks on the getter and setter will not be enough methinks...

EDIT: I constructed the following testing classes:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace MultiThreading_Spike
{
    class Program
    {
        private static List<User> users;
        private static Timer timer;
        static void Main(string[] args)
        {

            timer=new Timer(OrderUsers,null,5,5);
            for (int i = 0; i < 10000; i++)
            {
                ResetUsers();
                Thread.Sleep(5);
                users = new List<User>
                            {
                                new User {UserName = "John"},
                                new User {UserName = "Peter"},
                                new User {UserName = "Vince"},
                                new User {UserName = "Mike"}
                            };
                Thread.Sleep(5);
            }
            ResetUsers();
            Thread.Sleep(5)
            Debug.Assert(users==null);
        }

        private static void OrderUsers(object state)
        {
            if(users==null)return;
            Thread.Sleep(2);
            try
            {
                users = (from user in users
                         orderby user.IsLoggedIn descending ,
                             user.UserName
                         select user).ToList();
            }
            catch(Exception e)
            {
                Console.WriteLine("Error: {0}",e.Message);
            }
        }

        private static void ResetUsers()
        {
            users = null;
        }
    }


    public class User
    {
        bool isLoggedIn;
        public bool IsLoggedIn
        {
            get { return isLoggedIn; }
            set { isLoggedIn = value; }

        }

        private string userName;
        public string UserName
        {
            get { return userName; }
            set { userName = value; }
        }
    }
}

This code fails with a null reference exception in the OrderUsers method. Then I implemented the suggested solutions: Solution 1:

//identical code omitted
        private static void OrderUsers(object state)
        {
         lock(syncRoot)
         {
            if(users==null)return;
            Thread.Sleep(2);
            try
            {
                users = (from user in users
                         orderby user.IsLoggedIn descending ,
                             user.UserName
                         select user).ToList();
            }
            catch(Exception e)
            {
                Console.WriteLine("Error: {0}",e.Message);
            }
         }
      }

        private static void ResetUsers()
        {
            lock(syncRoot)
            {
               users = null;
            }
        }
    }

No exceptions!

Solution 2:

   private static void OrderUsers(object state)
    {
        if(users==null)return;
        var tempUsers = users;
        Thread.Sleep(2);
        try
        {
            tempUsers = (from user in tempUsers
                     orderby user.IsLoggedIn descending ,
                         user.UserName
                     select user).ToList();
        }
        catch(Exception e)
        {
            Console.WriteLine("Error: {0}",e.Message);
        }
        users = tempUsers;
    }

No null reference exceptions, but the Assert for users to be null in the end can fail.

Solution 3:

private static void OrderUsers(object state)
        {
            if(users==null)return;
            try
            {
                users.Sort((a, b) => Math.Sign(-2 * a.IsLoggedIn.CompareTo(b.IsLoggedIn) + a.UserName.CompareTo(b.UserName)));
            }
            catch(Exception e)
            {
                Console.WriteLine("Error: {0}",e.Message);
            }
        }

No exceptions. I keep having the nagging feeling that the Sort may be "in place", but that it is not necessarily atomic.

Solution 4: I could not get it to compile. The VolatileRead method has an overload taking an object, but I could not make it accept a List

Answer 1

You need to lock before executing your linq query and before setting to null:

lock(syncRoot) 
{
    users = null;
}

and

lock(syncRoot) 
{
    users = 
        (from user in users
         orderby user.IsLoggedIn descending,
                 user.Username
         select user).ToList(); 
}

where syncRoot:

private static syncRoot = new object();

Answer 2

The LINQ query will complete whether or not the users variable is reset to null because ToList() forces eager evaluation. However, I'm not sure that this will address your issue: if I understand correctly, you want to ensure that a stale collection is not left lying around in users because the set to null happened too early.

In this case, you can probably get away with just declaring a users-lock object and synchronizing on it both in the setter and around the query-and-set statement.

Answer 3

Save the users to a local variable and operator on it, this way you won't have to sync anything.

var tempUsers = users;
if (tempUsers != null)
{
    tempUsers = (from user in tempUsers
             orderby user.IsLoggedIn descending, user.Username
             select user).ToList()
}

Answer 4

It doesn't matter much what you lock, as long as the two threads agree to lock the same thing.

Personally, I would use local variables and lock free operations:

var localUsers = Thread.VolatileRead(ref users);
do
{
  if (null == localUsers)
  {
    break;
  }

  var newLocalUsers = (from user in localUsers 
        orderby user.IsLoggedIn descending ,                 
        user.Username         
        select user).ToList();

  var currentLocalUsers = Interlocked.CompareExchange(ref users, newLocalUsers, localUsers);
  if (currentLocalUsers == localUsers)
  {
    break;
  }
  // bummer, try again
  localUsers = currentLocalUsers;
} while(true);

And the other thread:

Interlocked.Exchange(ref users, null);

I have never tryed using Interlocked with var types, not sure how the compiler accepts it or does it has to be downcasted to object.

Answer 5

The best way to do this is to call List<T>.Sort, which sorts the list in-place and does not require an assignment.

For example:

users.Sort((a, b) => Math.Sign(
    -2 * a.IsLoggedIn.CompareTo(b.IsLoggedIn) + a.UserName.CompareTo(b.UserName)
));

(This example assumes that none of the users are null)

If, while this is executing, another thread executes users = null, the old List<T> will be sorted, but the users variable will not be affected.