Параллельное программирование на С++ в действии полностью

  T const& partition_val = *result.begin();

  typename std::list::iterator divide_point = ←(10)

   std::partition(chunk_data.begin(), chunk_data.end(),

    [&](T const& val) {return val < partition_val; });

  chunk_to_sort new_lower_chunk;

  new_lower_chunk.data.splice(new_lower_chunk.data.end(),

   chunk_data, chunk_data.begin(),

   divide_point);

  std::future > new_lower =

   new_lower_chunk.promise.get_future();

  chunks.push(std::move(new_lower_chunk)); ←(11)

  if (threads.size() < max_thread_count) { ←(12)

   threads.push_back(std::thread(&sorter::sort_thread, this));

  }

  std::list new_higher(do_sort(chunk_data));

  result.splice(result.end(), new_higher);

  while (new_lower.wait_for(std::chrono::seconds(0)) !=

   std::future_status::ready) { ←(13)

   try_sort_chunk();            ←(14)

  }

  result.splice(result.begin(), new_lower.get());

  return result;

 }

 void sort_chunk(boost::shared_ptr const& chunk) {

  chunk->promise.set_value(do_sort(chunk->data));←(15)

 }

 void sort_thread() {

  while (!end_of_data) {     ←(16)

   try_sort_chunk();         ←(17)

   std::this_thread::yield();←(18)

  }

 }

};

template

std::list parallel_quick_sort(std::list input) { ←(19)

 if (input.empty()) {

  return input;

 }

 sorter s;

 return s.do_sort(input); ←(20)

}

Здесь функция parallel_quick_sort (19) делегирует большую часть работы классу sorter (1), который объединяет стек неотсортированных блоков (2) с множеством потоков (3). Основные действия производятся в функции-члене do_sort (9), которая занимается обычным разбиением данных на две части (10). Но на этот раз она не запускает новый поток для каждого блока, а помещает его в стек (11) и запускает новый поток, только если еще есть незанятые процессоры (12). Поскольку меньший блок, возможно, обрабатывается другим потоком, нам необходимо дождаться его готовности (13). Чтобы не простаивать зря (в том случае, когда данный поток единственный или все остальные уже заняты), мы пытаемся обработать блок, находящийся в стеке (14). Функция try_sort_chunk извлекает поток из стека (7), сортирует его (8) и сохраняет результаты в обещании promise, так чтобы их смог получить поток, который поместил в стек данный блок (15).

Запущенные потоки крутятся в цикле, пытаясь отсортировать блоки, находящиеся в стеке (17), ожидая, пока будет установлен флаг end_of_data (16). В промежутке между проверками они уступают процессор другим потокам (18), чтобы у тех был шанс поместить в стек новые блоки. Эта программа полагается на то, что деструктор класса sorter (4) разберется с запущенными потоками. Когда все данные будут отсортированы, do_sort вернет управление (хотя рабочие потоки все еще выполняются), так что главный поток вернется из parallel_quick_sort (20) и, стало быть, уничтожит объект sorter. В этот момент деструктор поднимет флаг end_of_data (5) и дождется завершения рабочих потоков (6). Поднятый флаг является для функции потока указанием выйти из цикла (16).