1

MPMC FIFO-Queue の二重リンク リストをいじっていました (主にデモンストレーション目的で)。私は今、しばらく自分の間違いを突き止めようとしていますが、実際には進歩していません.

すべての Producer-Threads がすべての値を生成した直後に、デッドロックに遭遇しました。問題を次のように突き止めました。

ロック取得:

<THREAD ID> | <MESSAGE> | <MUTEX ADDRESS>

4460175360 : TRYLOCK HEAD:   0x7fb380c039d0
4460175360 : LOCKED HEAD:     0x7fb380c039d0
4460175360 : RELEASED HEAD: 0x7fb380c039d0

4460175360 : TRYLOCK HEAD:    0x7fb380c039d0
4460175360 : LOCKED HEAD:      0x7fb380c039d0
4460175360 : RELEASED HEAD:  0x7fb380c039d0

4460175360 : TRYLOCK HEAD:    0x7fb380c039d0
4460175360 : LOCKED HEAD:      0x7fb380c039d0
4460175360 : RELEASED HEAD:  0x7fb380c039d0

4460175360 : TRYLOCK HEAD:    0x7fb380c039d0
4459638784 : TRYLOCK TAIL:       0x7fb380c039d0
4460711936 : TRYLOCK TAIL:       0x7fb380c039d0
4460175360 : LOCKED HEAD:      0x7fb380c039d0
4460175360 : RELEASED HEAD:  0x7fb380c039d0

4460175360 : TRYLOCK HEAD: 0x7fb380c039d0   <---- THIS TRY-LOCK-HEAD NEVER GETS CONFIRMED!
4459638784 : LOCKED TAIL:  0x7fb380c039d0 
4459638784 : RELEASE MUTEX: 0x7fb380c039d0 <---- THE PRODUCER THREAD RELEASED 0x7fb380c039d0
Producer-Thread 4459638784 produced: 0

---- NOW ONE ELEMENT IN QUEUE ----

4460711936 : LOCKED TAIL:  0x7fb381800020 <---- ADDRESS OF LOCK HAS CHANGED WHICH IS FINE (because an element has been added)
4460711936 : RELEASE MUTEX AT ADDR: 0x7fb381800020
Producer-Thread 4460711936 produced: 0

---- NOW TWO ELEMENTS IN QUEUE ----

4460711936 : TRYLOCK TAIL: 0x7fb381a00020
4459638784 : TRYLOCK TAIL: 0x7fb381a00020
4460711936 : LOCKED TAIL:   0x7fb381a00020
4460711936 : RELEASE MUTEX AT ADDR: 0x7fb381a00020
Producer-Thread 4460711936 produced: 1

---- NOW THREE ELEMENTS IN QUEUE ----

4459638784 : LOCKED TAIL: 0x7fb380d00060  <---- AGAIN ADDRESS HAS CHANGED -- FINE
4459638784 : RELEASE MUTEX AT ADDR: 0x7fb380d00060
Producer-Thread 4459638784 produced: 1

---- NOW FOUR ELEMENTS IN QUEUE ---- PRODUCERS ARE DONE ----
---- CONSUMER THREAD BLOCKS - STILL TRYING TO LOCK 0x7fb380c039d0 ----

---- BUT NOBODY ELSE HOLDS 0x7fb380c039d0 ---- ALSO NO SELF-DEADLOCK?

GDB は、両方のプロデューサー スレッドが終了し、addr 0x7fb380c039d0 で mutx を待機している唯一のスレッドがスレッド 2 (唯一のコンシューマー スレッド) であることを通知します。

    (gdb) info threads
* 2                         0x00007fff8edc5dfd in pthread_mutex_lock ()
  1 "com.apple.main-thread" 0x00007fff8e715386 in __semwait_signal ()
(gdb) bt
#0  0x00007fff8e715122 in __psynch_mutexwait ()
#1  0x00007fff8edc5dfd in pthread_mutex_lock ()
#2  0x00000001000011a8 in ConcurrentDoublyLinkedList<int>::consumeNode (this=0x1001000e0) at ConcurrentDList.h:142
#3  0x0000000100000bd4 in consumeValues (ctx=0x7fff5fbffa78) at ConcurrentDList.cpp:29
#4  0x00007fff8edc07a2 in _pthread_start ()
#5  0x00007fff8edad1e1 in thread_start ()
(gdb) f 2
#2  0x00000001000011a8 in ConcurrentDoublyLinkedList<int>::consumeNode (this=0x1001000e0) at ConcurrentDList.h:142
142             pthread_mutex_lock(&head_->mutex);
(gdb) info reg
rax            0x200012d    33554733
rbx            0x100281000  4297592832
rcx            0x100280da8  4297592232
rdx            0x100    256
rsi            0x403    1027
rdi            0x1001039f0  4296030704
rbp            0x100280ed0  0x100280ed0
rsp            0x100280e00  0x100280e00
r8             0x2060   8288
r9             0x100280720  4297590560
r10            0xf9d79  1023353
r11            0x206    518
r12            0x1303   4867
r13            0x0  0
r14            0x7fff5fbffa78   140734799805048
r15            0x100000bb0  4294970288
rip            0x1000011a8  0x1000011a8 <ConcurrentDoublyLinkedList<int>::consumeNode()+110>
eflags         0x206    518
cs             0x7  7
ss             0x0  0
ds             0x0  0
es             0x0  0
fs             0x0  0
gs             0x0  0
(gdb) p *(pthread_mutex_t*) 0x1001039f0
$34 = {
  __sig = 1297437784, 
  __opaque = "\000\000\000\000` \000\000\000\000\000\000\000\000\000\000\003\004\000\000\000\002\000\000{?\017\000\000\000\000\000\b:\020\000\001\000\000\000\f:\020\000\001\000\000\000\000\000\000\000\000\000\000"
}

残念ながら、pthread_mutex_t は opaque 型であるため、昆虫を駆除することはできません。（GDB内で不透明な型をオンにしていますが？）。それ以外の場合は、そのミューテックスの現在の所有者が誰であるかを確認することをお勧めします。

私のリストのコードを以下に示します。実装に関する私の考えを説明するために、過度にコメントされています。これは決して優れた、または高性能な実装ではないことに注意してください。これは主に説明目的のためのものです。

CPPコード:

#include <stdlib.h>
#include <iostream>

#include <pthread.h>

template <class T>
class Node
{
    private:
       T value_;

       Node<T> *next_;
       Node<T> *prev_;

    public:

        pthread_mutex_t mutex;

        Node(T value, Node<T>* next, Node<T>* prev)
        {
            value_ = value;

            next_ = next;
            prev_ = prev;

            pthread_mutex_init(&mutex, NULL);
        }

        ~Node()
        {
            pthread_mutex_destroy(&mutex);
        }

        void setNext(Node<T>* next)
        {
            next_ = next;
        }        

        void setPrevious(Node<T>* prev)
        {
            prev_ = prev;
        }

        Node<T>* getNext()
        {
            return next_;
        } 

        Node<T>* getPrevious()
        {
            return prev_;
        }


        virtual bool isSentinel()
        {
            return false;
        } 
};

template <class T>
class SentinelNode : public Node<T>
{
    public:
      SentinelNode(T val, Node<T>* next, Node<T>* prev)
          : Node<T>(val, next, prev)
      {
      }

      virtual bool isSentinel()
      {
          return true;
      }
};

template <class T>
class ConcurrentDoublyLinkedList
{
    private:
        Node<T> *head_;
        Node<T> *tail_;

    public: 
        ConcurrentDoublyLinkedList()
        {
            head_ = tail_ = new SentinelNode<T>(NULL, NULL, NULL);
        }

        void produceNode(Node<T>* n)
        {  
            pthread_mutex_lock(&tail_->mutex);

            Node<T>* old = tail_;

            if(head_->isSentinel())
            {
                head_ = tail_ = n;
                pthread_mutex_unlock(&old->mutex);

                delete old;
                old = NULL;
            }
            else
            {
                n->setNext(tail_);
                tail_->setPrevious(n);
                tail_ = n;

                pthread_mutex_unlock(&old->mutex);
            }
        }

        Node<T>* consumeNode()
        {
            pthread_mutex_lock(&head_->mutex);

            if(head_->isSentinel())
            {
                 /* the head can only be a Sentinel if there is
                  * no element within the list
                  */

                  /* this also means that the list is currently
                   * implicitly fully locked */

                  /* return NULL and let the thread decide what to do */

                  pthread_mutex_unlock(&head_->mutex);

                  return NULL;
            }
            else
            {
                /* the head is not a Sentinel, which implies on of the following:
                 *     - The list has exactly one element, which means:
                 *         => head_ == tail_ && !head_->isSentinel()
                 *     
                 *     OR
                 *     
                 *     - The list has at least two elements, which means:
                 *         => head_ != tail_ && !head_->isSentinel()
                 *
                 *     - The absence of a Sentinel guarantees that the list
                 *       is NOT empty
                 */

                 if(head_ == tail_)
                 {
                      /* single element within the list 
                       * the list is still fully locked, 
                       * implicit because head_ == tail_
                       */

                       /* we replace the only element
                        * with a Sentinel, because
                        * the list is empty afterwards
                        */

                        Node<T>* p = head_;
                        head_ = tail_ = new SentinelNode<T>(NULL, NULL, NULL);

                        pthread_mutex_unlock(&p->mutex);

                        return p;
                 }
                 else
                 {
                      /* at least two elements are in the list
                       * which means that the current head
                       * must have a valid predecessor 
                       */

                       /* Producer and Consumer could
                        * hold a lock on two adjacent
                        * nodes. Thus, the Consumer
                        * must acquire head->prev
                        */

                        Node<T>* p = head_;
                        Node<T>* n = head_->getPrevious();

                        pthread_mutex_lock(&n->mutex);

                        /* head_->prev can now not be owned 
                         * by a producer. 
                         */

                        head_ = n;
                        head_->setNext(NULL);

                        pthread_mutex_unlock(&p->mutex);
                        pthread_mutex_unlock(&n->mutex);

                        return p;
                 } 
            }
        }
};

そのことについてのあなたの考えやアイデアを本当に感謝します. 私はしばらくそれを見ていますが、完全に間違った道を進んでいる可能性もあります。助けていただければ幸いです..

ありがとう、セバスチャン

4

1 に答える 1

0

消費と生成の両方は、ノードがまだ頭と尾であると仮定して、頭と尾のノードをロックします。つまり、スレッドは、もはやヘッド ノードまたはテール ノードではないノードをロックしている可能性があります。ロックする前に「古い」ポインターを保存した場合、少なくともどのノードをロックしたかがわかりますが、ロックされたノードは既に消費されている可能性があり、ロジックの一部が保持されていない可能性があります。

プロデュース メソッドとコンシューム メソッドのみが必要であると仮定すると、実際のノードではなく、ヘッド ポインターとテール ポインターをロックする方が簡単だと思います。もちろん、最も簡単な解決策は、データ構造全体をロックすることです。

于 2013-04-06T13:25:49.087 に答える