Синхронизация дочерних потоков с атомным временем, управляемым родителем

Question

Я пытаюсь написать симуляцию, в которой разные потоки должны выполнять заданные вычисления для определенного для потока интервала (в минимальном примере здесь этот интервал составляет от 1 до 4) на основе атомарного времени моделирования, управляемого родительским потоком..

---

Идея состоит в том, чтобы родительский элемент продвигал моделирование на один временной шаг (в данном случае всегда 1 для простоты), а затем все потоки независимо проверяли, нужно ли им выполнять вычисления икак только они проверили, уменьшают атомный счетчик и ждут следующего шага.Я ожидаю, что после выполнения этого кода число вычислений для каждого потока будет точно равно длине симуляции (то есть 10000 шагов), деленной на интервал, специфичный для потока (поэтому для интервала 4 потока поток должен сделать точно 2500 вычислений.

#include <thread>
#include <iostream>
#include <atomic>

std::atomic<int> simTime;
std::atomic<int> tocalc;
int end = 10000;

void threadFunction(int n);

int main() {
  int nthreads = 4;
  std::thread threads[nthreads];
  for (int ii = 0; ii < nthreads; ii ++) {
    threads[ii] = std::thread(threadFunction, ii+1);
  }

  simTime = 0;
  tocalc = 0;
  while (simTime < end) {
    tocalc = nthreads - 1;
    simTime += 1;
    // do calculation
    while (tocalc > 0) {
      // wait until all the threads have done their calculation
      // or at least checked to see if they need to
    }
  }

  for (int ii = 0; ii < nthreads; ii ++) {
    threads[ii].join();
  }
}

void threadFunction(int n) {
  int prev = simTime;
  int fix = prev;
  int ncalcs = 0;
  while (simTime < end) {
    if (simTime - prev > 0) {
      prev = simTime;
      if (simTime - fix >= n) {
        // do calculation
        ncalcs ++;
        fix = simTime;
      }
      tocalc --;
    }
  }
  std::cout << std::to_string(n)+" {ncalcs} - "+std::to_string(ncalcs)+"\n";
}

Однако выходные данные не согласуются с этим ожиданием, один из возможных выходных данных равен

2 {ncalcs} - 4992
1 {ncalcs} - 9983
3 {ncalcs} - 3330
4 {ncalcs} - 2448

, а ожидаемый -

2 {ncalcs} - 5000
1 {ncalcs} - 10000
3 {ncalcs} - 3333
4 {ncalcs} - 2500

*.1014 * Мне интересно, есть ли у кого-нибудь понимание того, почему этот метод принуждения потоков к ожиданию следующего шага, похоже, дает сбой - возможно, это простая проблема с моим кодом или более фундаментальная проблема с подходомСпасибо за понимание, спасибо.

---

Примечание

Я использую этот подход, потому что накладные расходы для других методов, которые я пробовал (например, используя pipes, присоединяется на каждом шаге)является чрезмерно дорогим, если есть более дешевый способ общения между потоками, я открыт для таких предложений.

Answer 1

Используя аналогичные настройки, я заметил, что не каждый поток достигнет ожидаемого вами значения, но будет отключен только на один.то есть

2 {ncalcs} - 4999
4 {ncalcs} - 2500
1 {ncalcs} - 9999
3 {ncalcs} - 3333

или что-то подобное, на первый взгляд случайное в отношении потока и количества потоков, для которых это происходит.Хотя я не уверен, что является причиной этого, я подумал, что было бы неплохо выдать предупреждение, но вы можете обойти его, проверив, если simTime - fix == 0, а если нет, то сделайте еще один расчет, прежде чем выйти.

Answer 2

Чтобы расширить комментарии, инициализация tocalc до nthreads - 1 означает, что на некоторых итераций все дочерние потоки будут уменьшать tocalc до того, как родительский поток оценивает их - чтение и записьatomic обрабатываются планировщиком памяти.Таким образом, иногда последовательность может выглядеть следующим образом:

• Дочерний 1 декремент tocalc, новое значение 2
• Дочерний 3 декремент tocalc, новое значение 1
• Дочерний4 декремента tocalc, новое значение 0
• Дочерние 2 декремента tocalc, новое значение -1
• Родитель оценивает, если tocalc < 0, возвращает true - авансы моделирования

и другие случаи, когда родительская оценка может быть запланирована до того, как последний поток уменьшится tocalc, т. Е.

• Дочерний 1 уменьшается tocalc, новое значение - 2
• Дочерние 3 декременты tocalc, новое значение 1
• Дочерние 4 декременты tocalc, новое значение 0
• Родитель оценивает, если tocalc < 0, возвращает true - прогресс моделирования
• Дочерние 2 декременты tocalc, новое значение 2

, и в этом случае дочерний поток номер 2 пропустит итерацию.Поскольку это происходит не каждый раз из-за полуслучайности порядка планирования, общее количество пропусков не является линейной функцией от числа потоков, а представляет собой небольшую долю от общего числа итераций.Если вы измените код на приведенный ниже, он даст желаемый результат.

#include <thread>
#include <iostream>
#include <atomic>

std::atomic<int> simTime;
std::atomic<int> tocalc;
int end = 10000;

void threadFunction(int n);

int main() {
    int nthreads = 4;
    simTime = 0;
    tocalc = 0;
    std::thread threads[nthreads];
    for (int ii = 0; ii < nthreads; ii ++) {
        threads[ii] = std::thread(threadFunction, ii+1);
    }

    int wait = 0;
    while (simTime < end) {
        tocalc = nthreads;
        simTime += 1;
        // do calculation
        while (tocalc > 0) {
            // wait until all the threads have done their calculation
            // or at least checked to see if they need to
        }
    }
    for (int ii = 0; ii < nthreads; ii ++) {
        threads[ii].join();
    }
}

void threadFunction(int n) {
    int prev = 0;
    int fix = prev;
    int ncalcs = 0;
    while (simTime < end) {
        if (simTime - prev > 0) {
            prev = simTime;
            if (simTime - fix >= n) {
                // do calculation
                ncalcs ++;
                fix = simTime;
            }
            tocalc --;
        }
    }
    std::cout << std::to_string(n)+" {ncalcs} - "+std::to_string(ncalcs)+"\n";
}

И один из возможных выходных данных будет (порядок завершения потока несколько случайный)

2 {ncalcs} - 5000
3 {ncalcs} - 3333
1 {ncalcs} - 10000
4 {ncalcs} - 2500