Вопрос по c#, multithreading – Threadsafe коллекция без блокировки

14

Я готовлюсь к собеседованию и натолкнулся на следующий вопрос. Я пытался, но не смог найти ничего, что могло бы создать класс, содержащий потокобезопасную коллекцию, без & quot; блокировки & quot ;. Если знаете какое-либо решение, пожалуйста, помогите.

Создайте класс C #, производный от Object, и реализует следующие методы:

AddString – This method should add a given string to an internal collection ToString – Override this method and return a single, comma-delimited string containing all the strings in the internal collection

Требования:

Must be thread-safe Must support multiple concurrent readers Must not use any pre-existing thread-safe collections Bonus: don’t use any type of lock
Этот вопрос требует способности имитировать функциональностьlockВы уверены, что будете проходить собеседование на должность, где это требуется? Henk Holterman

Ваш Ответ

5   ответов
1

Вы можете создать неблокирующий связанный список. Например что-то вродеэтот.

.NET Framework предоставляет такие методы, какCompareExchange(Object, Object, Object) которые позволяют вам писать безопасный код, не блокируя весь список.

10

работая с локальной копией, а затем пытаясь атомарно поменять ее с глобальной коллекцией, одновременно проверяя расы:

public class NonLockingCollection
{
    private List<string> collection;

    public NonLockingCollection()
    {
        // Initialize global collection through a volatile write.
        Interlocked.CompareExchange(ref collection, new List<string>(), null);
    }

    public void AddString(string s)
    {
        while (true)
        {
            // Volatile read of global collection.
            var original = Interlocked.CompareExchange(ref collection, null, null);

            // Add new string to a local copy.
            var copy = original.ToList();
            copy.Add(s);

            // Swap local copy with global collection,
            // unless outraced by another thread.
            var result = Interlocked.CompareExchange(ref collection, copy, original);
            if (result == original)
                break;
        }
    }

    public override string ToString()
    {
        // Volatile read of global collection.
        var original = Interlocked.CompareExchange(ref collection, null, null);

        // Since content of global collection will never be modified,
        // we may read it directly.
        return string.Join(",", original);
    }
}

Edit: С помощьюInterlocked.CompareExchange неявное выполнение нестабильных операций чтения и записи привело к некоторой путанице, поэтому я размещаю ниже эквивалентный код сThread.MemoryBarrier звонки вместо

public class NonLockingCollection
{
    private List<string> collection;

    public NonLockingCollection()
    {
        // Initialize global collection through a volatile write.
        collection = new List<string>();
        Thread.MemoryBarrier();
    }

    public void AddString(string s)
    {
        while (true)
        {
            // Fresh volatile read of global collection.
            Thread.MemoryBarrier();
            var original = collection;
            Thread.MemoryBarrier();

            // Add new string to a local copy.
            var copy = original.ToList();
            copy.Add(s);

            // Swap local copy with global collection,
            // unless outraced by another thread.
            var result = Interlocked.CompareExchange(ref collection, copy, original);
            if (result == original)
                break;
        }
    }

    public override string ToString()
    {
        // Fresh volatile read of global collection.
        Thread.MemoryBarrier();
        var original = collection;
        Thread.MemoryBarrier();

        // Since content of global collection will never be modified,
        // we may read it directly.
        return string.Join(",", original);
    }
}
FWIW,.ToList работает довольно хорошо при использовании на существующемList<T> из-за длительной микрооптимизации. Он эффективно использует Array.Copy, который использует внешнюю нативную реализацию, которая выигрывает от такой оптимизации. «Логический» сложность проблемы не такая же, как производительность в реальной системе, поскольку разные операции приводят к совершенно разному времени выполнения, поэтому не слишком полагайтесь на строго теоретическую нотацию Big-O. Для примера:dzone.com/articles/…
@HenkHolterman: в случае неудачи проверка на равенство ссылокresult == original вернетсяfalse, вызывая повторную попытку всего цикла.
Не совсем; это наиболее распространенный способ принудительного выполнения волатильного чтения. Похоже на неявноеThread.MemoryBarrier().
Да, я должен был прочитать это 2 раза. Эта штука всегда заставляет мою голову болеть. Теперь я думаю, что это может сработать, но я бы не трогал его 3-метровым шестом. И, конечно, ToList () быстро сделает это намного хуже, чем самый тяжелый объект Sync.
Ваш код не очень заинтересован в результатахCompareExchange(), Это может «потерпеть неудачу» ты знаешь.
1

Мое решение. В основном имитируют блокировку с использованием Interlocked.Exchange и AutoResetEvents. Сделал несколько простых тестов и похоже работает.

    public class SharedStringClass
    {
        private static readonly int TRUE = 1;
        private static readonly int FALSE = 0;

        private static int allowEntry;

        private static AutoResetEvent autoResetEvent;

        private IList<string> internalCollection;

        public SharedStringClass()
        {
            internalCollection = new List<string>();
            autoResetEvent = new AutoResetEvent(false);
            allowEntry = TRUE;
        }

        public void AddString(string strToAdd)
        {
            CheckAllowEntry();

            internalCollection.Add(strToAdd);

            // set allowEntry to TRUE atomically
            Interlocked.Exchange(ref allowEntry, TRUE);
            autoResetEvent.Set();
        }

        public string ToString()
        {
            CheckAllowEntry();

            // access the shared resource
            string result = string.Join(",", internalCollection);

            // set allowEntry to TRUE atomically
            Interlocked.Exchange(ref allowEntry, TRUE);
            autoResetEvent.Set();
            return result;
        }

        private void CheckAllowEntry()
        {
            while (true)
            {
                // compare allowEntry with TRUE, if it is, set it to FALSE (these are done atomically!!)
                if (Interlocked.CompareExchange(ref allowEntry, FALSE, TRUE) == FALSE)
                {
                    autoResetEvent.WaitOne();
                }
                else
                {
                    break;
                }
            }
        }
    }
1

Основываясь на этом вопросе, вы сможете добавить в свой объект параллельную коллекцию, которая будет отвечать требованиям безопасности потоков. Они не указали, какой тип внутренней коллекции использовать.

Вы должны быть в состоянии реализовать одну из коллекций из пространства имен concurrentcollection и достичь этого.

http://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx

Лучший ответ, по крайней мере для меня
0

string[], Всякий раз, когда вызывающая сторона хочет добавить строку, создайте новый массив с добавленным новым элементом и замените его на старый.

Эта модель не требует синхронизации. Он не терпит одновременных писателей, но допускает одновременное чтение.

Похожие вопросы