1

I would like to speed up a sorting function by implementing threads to work in parallel. My basic knowledge of pthreads are create, join, and using mutexes to prevent a deadlock.

So my questions are: How do I assign a task to a thread after it it finishes a task? For example, if I were to give half of a list to thread 1 to sort and the other to task 2 to sort, Once task 1 finishes, it should jump over to task two and help it.

If it helps, I'm testing with quick sort.

I've tried to see if there a task assigning function but the ones I stumble upon are in different codes.

user10416282
  • 33
  • 1
  • 7
  • 1
    What do you mean by "jump over to task two and help it"? Usually, you don't. You split the tasks up into different threads as you are doing, let the threads finish, and then merge the results. – MFisherKDX Apr 04 '19 at 01:08
  • @MFisherKDX: Sometimes a pool of enduring threads is used, and threads are assigned tasks dynamically instead of being created and destroyed repeatedly. – Eric Postpischil Apr 04 '19 at 01:41
  • @MFisherKDX that what I assume too, but my someone was suggesting that after a thread (in a pool of thread) is done with its task, it can be "opened up" for a new task or take a split from another thread doing a task and sort that split. Not sure if that makes sense – user10416282 Apr 04 '19 at 01:44

1 Answers1

0

There's nothing particularly complicated about it.

First, you need a waitable queue. That is, a list of things maintained in order that permits a thread to wait if the queue is empty.

Second, you need to write code that pops a job from the waitable queue, waiting if there's no job on the queue. Then it does that job.

Here's some example code that I wrote. It's in C++, but the general idea should be obvious from looking at the code.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • Hi David. Nice ThreadPool implementation. But I don't see how this answers the OPs question. He asks, after giving two threads each half of an array to sort, how to take the thread that finished first and then use it to "help the still running thread" finish its sort. That is a much more complicated question to attempt to answer. – MFisherKDX Apr 04 '19 at 04:23
  • That doesn't help much. In your code, you have jobs_.emplace (std::move (func)); but when I look at the pthread manual page, I couldn't find a C equivalent of emplace function. – user10416282 Apr 04 '19 at 04:27
  • @user10416282 `emplace` is an operation on a container like `std:vector` or `std::queue`. It's not a thread specific operation. – MFisherKDX Apr 04 '19 at 04:39
  • @user10416282 Just thing of it as "move the job onto the queue". You can implement that however you want. – David Schwartz Apr 04 '19 at 04:57
  • @MFisherKDX That's what he wants to do, but the specific issue that's stopping him from doing it is that he doesn't have the answer to this question: "*How do I assign a task to a thread after it it finishes a task?*" So that's what I answered. – David Schwartz Apr 04 '19 at 04:57