C语言 链接列表访问多线程应用程序

5lhxktic  于 2023-06-21  发布在  其他
关注(0)|答案(1)|浏览(98)

我有一个多线程应用程序,其中多个线程访问同一个变量-指向一个指针。* volatile * 不会用于确保原子访问(* 不存在 *),而是确保编译不会因为认为一个线程不能影响线程2而进行硬优化,并说 * 没有办法改变... *。
我已经看到了几个 * volatile是无用的 * 在多线程应用程序的职位。我有一个链表,可以在2线程中访问。有效地执行以下操作:
线程1

  • 为结构分配内存
  • 将线程放入链表
  • 处理链表并检查某个值是否设置为xyz

线程2

  • 读取链表
  • 做一些处理
  • 将值设置为xyz

对链表的所有操作都受到系统互斥体(FreeRTOS)的保护,但这并不能确保线程2从开始链表指针看到与线程1相同的值。
在我看来,代码中有2关键部分:

  • 线程从list_starts指针看到什么
  • 线程在指针内的e->data值中看到什么

这是代码,这是做错了-这是一个参考代码,不用于生产。

#include <stdint.h>
#include <stdlib.h>
#include <stdatomic.h>

typedef struct mytype {
    struct mytype* next;
    int data;
} mytype_t;
typedef _Atomic mytype_t mytype_atomic_t;

mytype_t* list_starts;
//mytype_atomic_t* list_starts;

void
thread1() {
    //Start thread2 here...
    //start_thread(thread2);

    //Run the thread here...
    while (1) {
        //mutex_lock();
        /* Create the entry */
        mytype_t* entry = malloc(sizeof(*entry));
        if (entry != NULL) {
            entry->next = list_starts;
            list_starts = entry;
        }
        //mutex_unlock();
        
        //mutex_lock();
start_over:
        for (mytype_t* e = list_starts, *prev = NULL; e != NULL; prev = e, e = e->next) {
            //mutex_unlock();
            //Simply wait to become 3
            while (e->data != 3) {}
            //mutex_lock();

            //Remove from the list
            if (prev == NULL) {
                list_starts = e->next;
            } else {
                prev->next = e->next;
            }
            free(e);
            goto start_over;
        }
        //mutex_unlock();
    }
}

Godbolt与-mcpu=cortex-m4 -O2产生:https://godbolt.org/z/T84K3x3G4

thread1:
        push    {r4, lr}
        ldr     r4, .L12
.L4:
        movs    r0, #8
        bl      malloc
        cbz     r0, .L2
        ldr     r3, [r4]
        str     r3, [r0]
.L6:
        //Critical part - loaded once
        ldr     r3, [r0, #4]
.L5:
        //Comparison and BNE between self -> no reload
        cmp     r3, #3
        bne     .L5
        ldr     r3, [r0]
        str     r3, [r4]
        bl      free
        ldr     r0, [r4]
        cmp     r0, #0
        bne     .L6
        b       .L4
.L2:
        ldr     r0, [r4]
        cmp     r0, #0
        beq     .L4
        b       .L6
.L12:
        .word   .LANCHOR0
list_starts:

如果我们通过在for循环中使用mytype_atomic_t*类型来更改原始代码,如下所示

for (mytype_atomic_t* e = list_starts, *prev = NULL; e != NULL; prev = e, e = e->next) {
    while (e->data != 3) {}
}

然后godbolt产生:https://godbolt.org/z/94an17x1G

thread1:
        push    {r3, r4, r5, lr}
        ldr     r4, .L13
        ldr     r5, [r4]
.L4:
        movs    r0, #8
        bl      malloc
        cbz     r0, .L2
        str     r5, [r0]
        str     r0, [r4]
.L6:
        adds    r2, r0, #4
.L5:
        //Barrier
        dmb     ish
        //Load first...
        ldr     r3, [r2]
        dmb     ish
        cmp     r3, #3
        //Jump back to pre-load
        bne     .L5
        dmb     ish
        ldr     r3, [r0]
        dmb     ish
        str     r3, [r4]
        bl      free
        ldr     r0, [r4]
        cmp     r0, #0
        bne     .L6
.L7:
        movs    r5, #0
        b       .L4
.L2:
        cmp     r5, #0
        beq     .L7
        mov     r0, r5
        b       .L6
.L13:
        .word   .LANCHOR0
list_starts:

最后的问题-是否足够简单:

  • 使用_Atomic关键字声明自定义类型?
  • 在这种情况下不要使用 * volatile *?
2wnc66cl

2wnc66cl1#

最后的问题-是否足够简单:

  • 使用_Atomic关键字声明自定义类型?

不,这不符合你的目的。不允许您访问原子结构的成员(未定义的行为结果)。你所能做的就是读取或写入它的整个(结构)值。
如果你没有执行删除,那么声明 members_Atomic和列表头指针就足够了:

struct mytype {
    struct mytype * _Atomic next;
    _Atomic int data;
};

struct mytype * _Atomic list_starts;

(如果你觉得必须使用typedef,尽管作为一般规则,我建议避免使用它们。

  • 在这种情况下不要使用 volatile

您不需要volatile,即使使用它也是不够的(根据C语言规范判断;实现方式可以提供更强的保证)。
但是,涉及到从列表中删除,特别是free s,将需要执行某种锁定。任何线程都不能在分配的对象被释放后访问它,并且您不能确保释放列表节点之一是安全的,而不参与某种可修改的状态,建议(或强制)其他线程等待-这就是锁的定义。
我可以理解为什么在这里要避免互斥锁,尤其是要避免整个列表使用一个互斥锁。您可能需要考虑使用结构的一个额外的_Atomic成员滚动您自己的锁,与执行原子比较和交换的忙碌循环一起使用,以执行锁定和解锁。也许是这样的:

struct mytype {
    struct mytype * _Atomic next;
    _Atomic int data;
    _Atomic _Bool is_locked;
};

void lock_mytype(struct mytype *x) {
    _Bool locked;
    do {
        locked = 0;
    } while (!atomic_compare_exchange_weak(&x->is_locked, &locked, 1));
}

void unlock_mytype(struct mytype *x) {
    _Bool locked = 1;
    if (!atomic_compare_exchange_weak(&x->is_locked, &locked, 0)) {
        // attempted to unlock a mutex that is not locked
        abort();
    }
}

当然,这是相当简单的。至少,您可以考虑对它进行扩充,以识别哪个线程持有锁,并在另一个线程试图解锁时失败。
首先,每个线程都需要在访问其成员(除了is_locked)之前锁定每个节点。这意味着其他成员是原子的。要安全地执行删除,必须同时锁定前置任务和要删除的节点,前置任务优先。在持有两个锁的同时更新前任的next成员,则前任的锁可能会被释放。不需要释放已删除节点的锁。
还应注意,用伪头节点而不是裸头指针来构造链表往往通过消除对特殊情况的需要来提供更简单的代码。你可能会发现这在这里特别有用,产生类似于下面的内容:

struct mytype {
    struct mytype* next;
    int data;
    _Atomic _Bool is_locked;
};

struct mytype dummy_list_head;

void thread1() {
    while (1) {
        mytype_t* entry = malloc(sizeof(*entry));
        if (entry == NULL) {
            abort();
        }
        lock_mytype(&dummy_list_head);
        entry->next = dummy_list_head.next;
        dummy_list_head.next = entry;
        unlock_mytype(&dummy_list_head);
        
        while (1) {
            struct mytype *e;
            lock_mytype(&dummy_list_head);
            e = dummy_list_head.next;
            unlock_mytype(&dummy_list_head);
            if (e == NULL) break;

            int data;
            do {
                lock_mytype(e);
                int data = e->data;
                unlock_mytype(e);
            } while (data != 3);

            lock_mytype(&dummy_list_head);
            lock_mytype(e);
            dummy_list_head.next = e->next;
            unlock_mytype(&dummy_list_head);
            free(e);
        } 
    }
}

您可以根据线程1是唯一执行删除操作的线程这一点,对这一点进行一些调整。这可能涉及使data成员成为原子成员。但同样,这里需要某种形式的锁定。

相关问题