C/C++ - sem_t 类型的单个信号量按顺序打印数字

Question

问题： 假设我们有 n 个线程，每个线程接收一个介于 1 和 n 之间的随机唯一数字。我们希望线程按排序顺序打印数字。

简单的解决方案（使用 n semaphore/mutex）： 我们可以使用 n 个互斥锁（或类似的信号量），其中线程 i 等待获取第 i 个互斥锁并解锁编号 i + 1。另外，线程 1 没有等待。

但是，我想知道是否可以使用单个信号量（sem_t 类型）模拟类似的逻辑来实现以下逻辑：(i是 1 到 n 之间的数字）

Thread with number i as input, waits to acquire a count of (i-1) on the semaphore, and after printing, releases a count of i. Needless to say, thread one does not wait.

我知道与Java不同，sem_t不支持信号量值中的任意increase/decrease。而且，写一个for循环做(i-1) wait and i release因为异步是行不通的。

我一直在寻找答案，但一直找不到。这在普通 C 中可能吗？如果不是，是否可以在 C++ 中仅使用一个变量或信号量？总的来说，用一个信号量做这件事最不浪费的方法是什么。

请随时编辑问题，因为我是多线程编程的新手。

Answer 1

这是一个很好的问题，但我担心您可能遇到 XY 问题，因为我无法想象您的问题场景的充分理由。尽管如此，在 1-2 分钟后，我想出了 2 个各有利弊的解决方案，但我认为其中一个最适合您：

一个。当您的线程几乎同时完成或需要尽快打印时，您可以使用共享 std::atomic<T> 和 T=unsigned,int,size_t,uint32_t 任何你喜欢的东西，或者使用 C 时 C 标准库中的任何整数原子，用 0 初始化它，现在我忙的每个线程都在等待，直到它的值为 i-1。如果是这样，它打印然后在原子上加 1。当然，由于繁忙的等待，当线程等待很长时间时，你会有很多 CPU 负载，而当许多线程等待时，你会变慢。但是你尽快得到你的印刷品

乙。你只需将线程 i 的结果存储在一个容器中，可能连同它的索引一起，因为我猜你想要更多只打印 i，并且在所有线程完成或定期完成后，对这个容器进行排序，然后打印它。

A.:

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
#include <functional>

void thread_function(unsigned i, std::atomic<unsigned>& atomic) {
    while (atomic < i - 1) {}
    std::cout << i << " ";
    atomic += 1;
}

int main() {
    std::atomic<unsigned> atomic = 0;

    std::vector<std::thread> threads;
    for (auto i : {3,1,2}) {
        threads.push_back(std::thread(thread_function, i, std::ref(atomic)));
    }
    for (auto& t : threads) {
        t.join();
    }
    std::cout << "\n";
}

也适用于 C，只需使用那里的原子。

Answer 2

您可以使用 C++ 中的 condition_variable 来执行此操作，这等同于使用 C 中的 pthreads 库的 pthread_cond_t。

您想要在线程之间共享的是一个指向 condition_variable 数字的指针，以及一个用于保护对数字的访问的互斥锁。

struct GlobalData
{
    std::condition_variable cv;
    int currentValue;
    std::mutex mut;
};

每个线程简单地调用一个等待其编号被设置的函数：

void WaitForMyNumber(std::shared_ptr<GlobalData> gd, int number)
{
    std::unique_lock<std::mutex> lock(gd->mut);
    while (gd->currentValue != number)
    {
        gd->cv.wait(lock);
    }

    std::cout << number << std::endl;
    gd->currentValue++;
    gd->cv.notify_all(); // notify all other threads that it can wake up and check
}

然后一个程序来测试它。这个使用 10 个线程。您可以修改它以使用更多，然后拥有您自己的数字列表随机化算法。

int main()
{
    int numbers[10] = { 9, 1, 0, 7, 5, 3, 2, 8, 6, 4 };
    std::shared_ptr<GlobalData> gd = std::make_shared<GlobalData>();
    // gd->number is initialized to 0.

    std::thread threads[10];

    for (int i = 0; i < 10; i++)
    {
        int num = numbers[i];
        auto fn = [gd, num] {WaitForMyNumber(gd, num); };
        threads[i] = std::move(std::thread(fn));
    }

    // wait for all the threads to finish
    for (int i = 0; i < 10; i++)
    {
        threads[i].join();
    }

    return 0;
}

以上都是C++。但是使用 pthreads 将上面的解决方案转置到 C 中会很容易。但我会把它留作 OP 的练习。

我不确定这是否满足您的 "one semaphore requirement"。互斥量在技术上有一个信号量。不确定 condition_variable 本身是否有用于其实现的信号量。

Answer 3

以下代码使用 pthread_cond_t 并在 C 中工作。

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define n 100

int counter = 0;
int used[n];

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void foo(void *given_number){
    int number = (int)given_number;
    pthread_mutex_lock(&mutex);
    while(counter != number){
        pthread_cond_wait(&cond, &mutex);
    }
    printf("%d\n", number);
    counter++;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
}

int get_random_number(){
    while(1){
        int x = rand()%n;
        if(!used[x]){
            used[x] = 1;
            return x;
        }
    }
}

int main(){
    pthread_t threads[n];
    for(int i = 0; i < n; i++){
        int num = get_random_number();
        pthread_create(&threads[i], NULL, foo, (void *)num);    
    }
    for(int i = 0; i < n; i++){
        pthread_join(threads[i], NULL);
    }
    return 0;
}

C/C++ - sem_t 类型的单个信号量按顺序打印数字

C/C++ - Single semaphore of type sem_t to print numbers in order

c

c++

multithreading

mutex

semaphore