dispatch_apply 留下一个线程 "hanging"

Question

我正在按照 Apple 的并发编程指南试验多线程。替换 for 循环的多线程函数 (dispatch_apply) 看起来很简单，并且可以通过简单的 printf 语句正常工作。但是，如果块调用更 cpu 密集的计算，程序永远不会结束或执行超过 dispatch_apply，并且一个线程（主线程？）似乎停滞在 100%。

#import <Foundation/Foundation.h>

#define THREAD_COUNT 16

unsigned long long longest = 0;
unsigned long long highest = 0;

void three_n_plus_one(unsigned long step);

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
        dispatch_apply(THREAD_COUNT, queue, ^(size_t i) {
            three_n_plus_one(i);
        });
    }
    return 0;
}

void three_n_plus_one(unsigned long step) {
    
    unsigned long long start = step;
    unsigned long long end = 1000000;
    unsigned long long identifier = 0;

    while (start <= end) {

        unsigned long long current = start;
        unsigned long long sequence = 1;

        while (current != 1) {
        
            sequence += 1;
            if(current % 2 == 0)
                current = current / 2;
            else {
                current = (current * 3) + 1;
            }

            if (current > highest) highest = current;
        }

        if (sequence > longest) {
            longest = sequence;
            identifier = start;
            printf("thread %lu, number %llu with %llu steps to one\n", step, identifier, longest);
        }

        start += (unsigned long long)THREAD_COUNT;
    }
}

不过，循环似乎已经结束了。据我了解，这应该是相当简单的，但我仍然对我在这里做错了什么一无所知。

Answer 1

您调用的 step 是循环的索引。它在您的代码中从 0 到 THREAD_COUNT-1。由于您将 start 指定为 step，这意味着您的第一次迭代尝试计算从零开始的 Colatz 序列。计算 0/2 == 0 无限循环也是如此。

你想写的是：

unsigned long long start = step + 1;

将您的块大小称为“THREAD_COUNT”具有误导性。问题不在于创建了多少线程（可能不创建线程；这取决于系统）。问题是把工作分成多少块。

请注意，在没有同步的情况下在多个线程上读取和写入 longest 和 highest 是未定义的行为，因此这段代码可能会做出令人惊讶的事情（特别是在优化时）。不要假设它仅限于在最长和最高中获得错误的值。允许优化器假定在它运行时没有其他线程触及这些值，并且可以基于此显着地重新排列代码。但这不是这个特定问题的原因。

Answer 2

与 (+1) 一样，一个线程“挂起”的原因是因为在提供零时出现无限循环，而不是因为 dispatch_apply 有任何问题（称为 concurrentPerform 在 Swift).

但是，更微妙的问题（以及使并发代码不那么“直截了当”的原因）是此代码不是线程安全的。存在“数据竞赛”。您正在从多个线程同时访问和更改 highest 和 longest。我鼓励在测试并发代码时使用 Thread Sanitizer (TSAN)，它非常适合识别这些数据竞争。

例如，编辑您的方案并暂时打开线程清理程序：

然后，当您运行时，它会警告您数据竞争：

您可以通过同步对这些变量的访问来修复这些竞争。锁是一种简单的机制。如果可以的话，我也会避免在内部 while 循环中进行同步。在这种情况下，您甚至可以将其从外部 while 循环中删除。在这种情况下，我可能会建议使用局部变量来跟踪当前“最长”序列、“最高”值以及该最高值的标识符，然后仅在完成后才与共享变量进行比较和更新，在两个循环之外。

例如也许：

- (void)three_n_plus_one:(unsigned long) step {
    unsigned long long start = step + 1;
    unsigned long long end = 1000000;
    unsigned long long tempHighest = start;
    unsigned long long tempLongest = 1;
    unsigned long long tempIdentifier = start;

    while (start <= end) {
        unsigned long long current = start;
        unsigned long long sequence = 1;

        while (current != 1) {
            sequence += 1;

            if (current % 2 == 0)
                current = current / 2;
            else {
                current = (current * 3) + 1;
            }

            if (current > tempHighest) tempHighest = current;
        }

        if (sequence > tempLongest) {
            tempLongest = sequence;
            tempIdentifier = start;
        }

        start += (unsigned long long)THREAD_COUNT;
    }

    [lock lock];   // synchronize updating of shared memory

    if (tempHighest > highest) {
        highest = tempHighest;
    }

    if (tempLongest > longest) {
        longest = tempLongest;
        identifier = tempIdentifier;
    }

    [lock unlock];
}

我使用了 NSLock，但使用任何你想要的同步机制。但想法是（a）确保将所有交互与共享内存同步； (b) 将必要的同步次数减少到最低限度。（在这种情况下，天真的同步方法比上面的方法慢 200 倍，这将同步次数降至最低。）

完成数据争用修复后，您可以关闭 TSAN。

dispatch_apply 留下一个线程 "hanging"

dispatch_apply leaves one thread "hanging"

multithreading

objective-c

grand-central-dispatch