C / C ++ - один семафор типа sem_t для печати чисел в порядке

Question

Проблема: Допустим, у нас есть n потоков, где каждый поток получает случайное уникальное число от 1 до n. И мы хотим, чтобы потоки печатали числа в отсортированном порядке.

Тривиальное решение (используя n семафор / мьютекс): Мы можем использовать n блокировок мьютекса (или аналогично семафорам) там, где ожидаю нитьполучить блокировку мьютекса i и разблокировать номер i + 1. Кроме того, потоку 1 не нужно ждать.

Однако мне интересно, возможно ли имитировать аналогичную логику с использованием одного семафора (типа sem_t) для реализации следующей логики: (i - это число от 1 до n включительно)

Поток с номером i в качестве ввода ожидает получения счетчика (i-1)на семафор и после печати выпускает счетчик i. Само собой разумеется, поток один не ждет.

Я знаю, что в отличие от Java, sem_t не поддерживает произвольное увеличение / уменьшение значения семафора. Более того, написание цикла for (i-1) wait и i release не будет работать из-за асинхронности.

Я так долго искал ответ, но не смог его найти. Возможно ли это в простой C? Если нет, возможно ли в C ++ использовать только одну переменную или семафор? В целом, какой наименее расточительный способ сделать это с ОДНЫМ семафором.

Пожалуйста, не стесняйтесь редактировать вопрос, так как я новичок в многопоточном программировании.

Answer 1

Вы можете сделать это с условной переменной в C ++, которая эквивалентна pthread_cond_t с библиотекой pthreads в C.

То, что вы хотите разделить между потоками, это указатель наcondition_variable, number и mutex для защиты доступа к номеру.

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 ++. Но было бы легко перенести вышеуказанное решение на C, используя pthreads . Но я оставлю это как упражнение для ОП.

Я не уверен, удовлетворяет ли это вашему «требованию одного семафора». Технически мьютекс имеет семафор. Не уверен, что в условной переменной есть семафор для его реализации.

Answer 2

Хотя это хороший вопрос, я боюсь, что у вас может быть проблема с XY, так как я не могу представить себе вескую причину для вашей проблемы. Тем не менее, через 1-2 минуты я придумал 2 решения с плюсами и минусами, но я думаю, что одно идеально для вас:

A. Когда ваши потоки почти завершены в одно и то же время и вам нужно их распечатать как можно скорее, вы можете использовать общую std::atomic<T> с T=unsigned,int,size_t,uint32_t, что вам нравится, или любую целочисленную атомизацию в стандартной библиотеке C при использовании C, инициализируйте ее с помощью0, и теперь каждый занятый мной поток ждет, пока его значение не станет i-1. Если это так, он печатает, а затем добавляет 1 на атомном. Конечно, из-за занятого ожидания у вас будет большая нагрузка на процессор, когда потоки ждут долго, и замедление, когда многие ждут. Но вы получите свой отпечаток как можно скорее

B. Вы просто сохраняете свой результат потока 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 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;
}