安全删除并发链表中的节点

Question

我正在阅读 APUE 这本书。当我阅读有关pthread reader/writer-lock的章节时，我对它使用reader/writer-lock.

实现并发队列有疑问

struct queue {
    struct job *q_head;
    struct job *q_tail;
    pthread_rwlock_t q_lock;
};

/*
* Remove the given job from a queue.
*/
void
job_remove(struct queue *qp, struct job *jp)
{
    pthread_rwlock_wrlock(&qp->q_lock);
    if (jp == qp->q_head) {
        qp->q_head = jp->j_next;
        if (qp->q_tail == jp)
            qp->q_tail = NULL;
        else
            jp->j_next->j_prev = jp->j_prev;
    } else if (jp == qp->q_tail) {
        qp->q_tail = jp->j_prev;
        jp->j_prev->j_next = jp->j_next;
    } else {
        jp->j_prev->j_next = jp->j_next;
        jp->j_next->j_prev = jp->j_prev;
    }
    pthread_rwlock_unlock(&qp->q_lock);
}

我的问题是这个实现如何保证一个struct job只从链表中删除一次。根据我的理解，可以安排两个线程，使它们正好位于 pthread_rwlock_wrlock 行之前。然后 struct job *jp 可能会被释放两次。如果 struct job * 是一个动态分配的数据结构，这可能会导致 double-free 错误。有什么建议吗？

Answer 1

您的代码中存在竞争条件。其他更改可能发生在两个线程之间的队列中，这些线程在队列上获得写锁，然后尝试删除同一节点。可以删除其他节点，也可以添加其他节点。因此，如果线程 A 删除了一个节点，发生了更改，然后线程 B 尝试再次删除同一个节点，那么您的队列可能会损坏。

代码需要信息来让它知道该节点已被删除。

查看添加的评论，以及修复竞争条件的代码：

struct queue {
    struct job *q_head;
    struct job *q_tail;
    pthread_rwlock_t q_lock;
};

/*
* Remove the given job from a queue.
*/
void
job_remove(struct queue *qp, struct job *jp)
{
    // we assume here that jp is actually in the queue
    pthread_rwlock_wrlock(&qp->q_lock);

    // at this point, jp may no longer be in the queue,
    // and in fact, the queue may be completely different.
    // thus, any modification to the queue based on the
    // assumption that jp is still part of the queue
    // can lead to corruption of the queue

    // so check if jp has been removed - we'll later set
    // both j_next and j_prev to NULL after jp is
    // removed from the queue - and if they're both
    // NULL here that means another thread already
    // removed jp from the queue
    if ( !(jp->j_next) && !(jp->j_prev) ) {
        // empty statement - jp is already removed
        ;
    }
    else if (jp == qp->q_head) {
        qp->q_head = jp->j_next;
        if (qp->q_tail == jp)
            qp->q_tail = NULL;
        else
            jp->j_next->j_prev = jp->j_prev;
    } // and this brace was missing in your posted code...
    else if (jp == qp->q_tail) {
        qp->q_tail = jp->j_prev;
        jp->j_prev->j_next = jp->j_next;
    } else {
        jp->j_prev->j_next = jp->j_next;
        jp->j_next->j_prev = jp->j_prev;
    }

    // make sure data in jp no longer refers to
    // the queue - this will also tell any other
    // thread that accesses jp that it's already
    // been removed
    jp->j_next = NULL;
    jp->j_prev = NULL;

    pthread_rwlock_unlock(&qp->q_lock);
}

您还需要检查 jp 如何获得 free()d 或 deleted。不允许多个线程这样做。

安全删除并发链表中的节点

Safe removal of a node in a concurrent linked list

c

concurrency

linked-list

readwritelock