Попытка реализовать связанный список - PullRequest
Новая
       20

Попытка реализовать связанный список

0 голосов
/ 24 апреля 2020 
        public void Push(Node newNode)
    {
        while (true)
        {
            Node tmp = this.head;
            newNode.next = tmp;
            if (Interlocked.CompareExchange(ref this.head, newNode, tmp) == tmp)
            {
                break;
            }
        }
    }

    public Node Pop()
    {
        Node pop=null;

        while (this.head != null)
        {
            pop = this.head;
            var oldcount = this.popcount;
            var newcount = oldcount + 1;

            if (Interlocked.CompareExchange(ref this.popcount, newcount, oldcount) == oldcount)
            {
                pop = Interlocked.CompareExchange(ref head, head.next, head);
                break;
            }
            pop = null;
        }
            return pop;
    }
    //---------------------------------------------------------
    while (count < 10000) // 4 thread run this code
        {
            for (int i = 0; i < 2; i++)
            {
                Node temp;
                if (freelist.head != null)
                {
                    temp = freelist.Pop();
                    headlist.Push(temp);
                }
            }
            for (int j = 0; j < 1; j++)
            {
                Node temp;
                if (headlist.head != null)
                {
                    temp = headlist.Pop();
                    freelist.Push(temp);
                }
            }
            count++;
            Console.WriteLine(count);
        }

Я пытаюсь реализовать свободный список ссылок. Я добавляю popcount, чтобы избежать проблемы. И я реализую Push и Pop, используя CAS. Когда я запускаю этот код, он не работает так, как я думаю. 

    class Node
{
    public int data;
    public Node next;

    public Node(int data)
    {
        this.data = data;
    }

}

Когда я запускаю код, Node.next указывает на себя. Например, Node.data = 99720 и Node.next = Node Итак, когда я go до Node.next, это все равно 99720 узлов. Не могу понять, почему это произошло ...

1 Ответ

1 голос
/ 25 апреля 2020

Похоже, вы пытаетесь создать стек без блокировки. Я не уверен, какой (псевдо) код вы использовали в качестве основы для своей реализации, но ваша попытка решить проблему ABA с помощью popcount не может сработать. Когда вы используете тег версии для предотвращения ABA, он должен быть объединен с указателем, т. Е. Указатель и тег должны быть обновлены в операции single atomi c . Java предоставляет AtomicStampedReference именно для этой цели, но, к сожалению. NET не предоставляет ничего подобного.

Однако, поскольку вы работаете с NET, вы можете позволить себе роскошь сборщик мусора, так что вам не нужно беспокоиться о проблеме ABA, если вы не используете узлы повторно.

Кстати: ваша функция pop отсутствует al oop.

...