PThread question

PThread question

[Sreevathsa]

I have a question on syncing the threads. I have a scenario like this:

5 threads (T1, T2, T3, T4 & T5) are working on this piece of code:

LINE1: 	for(;;) {
LINE2: 		pthread_mutex_lock(&r1_mutex)
LINE3: 		.............
LINE4: 		.............
LINE5: 		pthread_mutex_unlock(&r1_mutex)


			/* some code that does not need protection */
LINE6: 		.............
LINE7: 		.............


LINE8: 		pthread_mutex_lock(&r2_mutex)
LINE9: 		.............
LINE10: 		.............
LINE11: 		pthread_mutex_unlock(&r2_mutex)
LINE12: 	}


r1_mutex is to protect the access to a FIFO queue. I want the 5 threads to
process the queue contents in the same order in which they arrived into the
queue. 

Now, lets assume that a request comes into the queue and thread T1 picks up
and starts processing it. T1 has released r1_mutex lock and is holding
r2_mutex lock and is executing the code in lines 9 and 10.

While T1 is busy executing code on lines 9 and 10, the queue gets 4 more
requests and threads T2, T3, T4 and T5 (in that order) picks each one of
them in the order in which they came into the queue and start processing
them. They come till LINE 8 and wait to lock r2_mutex which thread T1 has
currently locked.

Now, given this scenario, here is my question:
After T1 unlocks r2_mutex, which thread among T2, T3, T4 and T5 gets the
r2_mutex lock? Does pthread scheduler schedule (give the lock to) thread T2
which came to LINE8 first??

FYI: I use Linux 2.6 - Fedora distro. I am not sure if its uses NPTL or the
native Linux threads.

Thanks,
Sreevathsa

RE: PThread question

[krishna.vamsi]

It is not guaranteed..

-Vamsi

-----Original Message-----
From: linux-c-programming-owner@vger.kernel.org
[mailto:linux-c-programming-owner@vger.kernel.org] On Behalf Of
Sreevathsa
Sent: Thursday, March 15, 2007 12:43 PM
To: linux-c-programming@vger.kernel.org
Subject: PThread question

I have a question on syncing the threads. I have a scenario like this:

5 threads (T1, T2, T3, T4 & T5) are working on this piece of code:

LINE1: 	for(;;) {
LINE2: 		pthread_mutex_lock(&r1_mutex)
LINE3: 		.............
LINE4: 		.............
LINE5: 		pthread_mutex_unlock(&r1_mutex)


			/* some code that does not need protection */
LINE6: 		.............
LINE7: 		.............


LINE8: 		pthread_mutex_lock(&r2_mutex)
LINE9: 		.............
LINE10: 		.............
LINE11: 		pthread_mutex_unlock(&r2_mutex)
LINE12: 	}


r1_mutex is to protect the access to a FIFO queue. I want the 5 threads
to
process the queue contents in the same order in which they arrived into
the
queue. 

Now, lets assume that a request comes into the queue and thread T1 picks
up
and starts processing it. T1 has released r1_mutex lock and is holding
r2_mutex lock and is executing the code in lines 9 and 10.

While T1 is busy executing code on lines 9 and 10, the queue gets 4 more
requests and threads T2, T3, T4 and T5 (in that order) picks each one of
them in the order in which they came into the queue and start processing
them. They come till LINE 8 and wait to lock r2_mutex which thread T1
has
currently locked.

Now, given this scenario, here is my question:
After T1 unlocks r2_mutex, which thread among T2, T3, T4 and T5 gets the
r2_mutex lock? Does pthread scheduler schedule (give the lock to) thread
T2
which came to LINE8 first??

FYI: I use Linux 2.6 - Fedora distro. I am not sure if its uses NPTL or
the
native Linux threads.

Thanks,
Sreevathsa

-
To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: PThread question

[Steve Graegert]

On 3/15/07, Sreevathsa <sreevathsa@gmail.com> wrote:
> I have a question on syncing the threads. I have a scenario like this:
>
> 5 threads (T1, T2, T3, T4 & T5) are working on this piece of code:
>
> LINE1:  for(;;) {
> LINE2:          pthread_mutex_lock(&r1_mutex)
> LINE3:          .............
> LINE4:          .............
> LINE5:          pthread_mutex_unlock(&r1_mutex)
>
>
>                         /* some code that does not need protection */
> LINE6:          .............
> LINE7:          .............
>
>
> LINE8:          pthread_mutex_lock(&r2_mutex)
> LINE9:          .............
> LINE10:                 .............
> LINE11:                 pthread_mutex_unlock(&r2_mutex)
> LINE12:         }
>
>
> r1_mutex is to protect the access to a FIFO queue. I want the 5 threads to
> process the queue contents in the same order in which they arrived into the
> queue.
>
> Now, lets assume that a request comes into the queue and thread T1 picks up
> and starts processing it. T1 has released r1_mutex lock and is holding
> r2_mutex lock and is executing the code in lines 9 and 10.
>
> While T1 is busy executing code on lines 9 and 10, the queue gets 4 more
> requests and threads T2, T3, T4 and T5 (in that order) picks each one of
> them in the order in which they came into the queue and start processing
> them. They come till LINE 8 and wait to lock r2_mutex which thread T1 has
> currently locked.
>
> Now, given this scenario, here is my question:
> After T1 unlocks r2_mutex, which thread among T2, T3, T4 and T5 gets the
> r2_mutex lock? Does pthread scheduler schedule (give the lock to) thread T2
> which came to LINE8 first??

Sreevathsa,

I will not ask you why you want to enforce some sort of artificial
"scheduling policy" for your threads with regard to the problem you're
trying to solve.  I'd generally recommend decoupling the comsumer
pattern from the communication pattern.  While a FIFO guarantees items
to be processed in a particular order, the order of execution of
threads is beyond your control, unless you apply a scheduling policy
to each thread, which may require superuser privileges (see SCHED_FIFO
and SCHED_RR).

You may want to create a chain of threads (instead of a tree), each
one waiting for the other to complete (see pthread_join).  Every
controller thread could then create a single worker thread to process
the data, thus the controller thread can relinquish the CPU
afterwards.

Anyhow, I recommend not to rely on the order of items arriving in the
FIFO.  Instead, I'd introduce another layer of abstraction to map
items to particular threads.

	\Steve

--

Steve Grägert <steve@graegert.com>
Jabber    xmpp://graegerts@jabber.org
Internet  http://eth0.graegert.com, http://blog.graegert.com
-
To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: PThread question

[Hendrik Visage]

On 3/15/07, Sreevathsa <sreevathsa@gmail.com> wrote:
> I have a question on syncing the threads. I have a scenario like this:
>
> 5 threads (T1, T2, T3, T4 & T5) are working on this piece of code:
>
> LINE1:  for(;;) {
> LINE2:          pthread_mutex_lock(&r1_mutex)

Include setting up the semaphores as discussed below ;^)

> LINE3:          .............
> LINE4:          .............
> LINE5:          pthread_mutex_unlock(&r1_mutex)
>
>
>                         /* some code that does not need protection */
> LINE6:          .............
> LINE7:          .............
>

Given the explanation below, I'd advise on another critical area here
that will block based on the FIFO. Ie. the FIFO structure will include a
pointer to two semaphores for each entry. The first one to be "READY"
and the second one to be "FINISHED".
The "FINISHED" of the Nth entry, is the "READY" for the (N+1)th entry (The
corner case of the begining/head needs to be considered too).
The initial state for these semaphores should be "down"/0 (except for the
HEAD whose READY should be "up"/1).

Thus before entry the Thread will down(FIFO[entry]->READY), and block until
the previous entry/thread upped it.
> LINE8:          pthread_mutex_lock(&r2_mutex)
> LINE9:          .............
> LINE10:                 .............
> LINE11:                 pthread_mutex_unlock(&r2_mutex)
Here you should then do up(FIFO[entry]->FINISHED)

Actually, in this way, you'll (1) serialize the processing as "Expected"
and (2) you'll do away with the pthread_mutex as you'll only be using the
semaphores in this way.
> LINE12:         }
>
>

> Now, given this scenario, here is my question:
> After T1 unlocks r2_mutex, which thread among T2, T3, T4 and T5 gets the
> r2_mutex lock? Does pthread scheduler schedule (give the lock to) thread T2
> which came to LINE8 first??

What if the threads arrived to r2_mutex in the order: T4, T2, T5, T3??

I recall some settings to the POSIX/SVR4 IPCs which will make all the processes
wake up simultaneously and all trying to regrab, and then there might be a
setting to allow them to be woken in sequence of arival, but then
still, what about
the order T4,T2,T5,T3?? I understood you'll want them processed T2,T3,T4,T5, and
that's the reason for the advice on using the semaphores.

Also check on all the other IPCs out there, as you might be able to (ab)use
the reader/writers type locks to check etc. and use yield etc. to get
the ordering right
without the corner cases and issues WRT the FIFO buffer, and it's
pointers etc. and clearing/releasing the data etc. without memory
leaks etc.

-- 
Hendrik Visage

Re: PThread question

[Neil Horman]

On Thu, Mar 15, 2007 at 12:13:18AM -0700, Sreevathsa wrote:
> I have a question on syncing the threads. I have a scenario like this:
> 
> 5 threads (T1, T2, T3, T4 & T5) are working on this piece of code:
> 
> LINE1: 	for(;;) {
> LINE2: 		pthread_mutex_lock(&r1_mutex)
> LINE3: 		.............
> LINE4: 		.............
> LINE5: 		pthread_mutex_unlock(&r1_mutex)
> 
> 
> 			/* some code that does not need protection */
> LINE6: 		.............
> LINE7: 		.............
> 
> 
> LINE8: 		pthread_mutex_lock(&r2_mutex)
> LINE9: 		.............
> LINE10: 		.............
> LINE11: 		pthread_mutex_unlock(&r2_mutex)
> LINE12: 	}
> 
> 
> r1_mutex is to protect the access to a FIFO queue. I want the 5 threads to
> process the queue contents in the same order in which they arrived into the
> queue. 
> 
> Now, lets assume that a request comes into the queue and thread T1 picks up
> and starts processing it. T1 has released r1_mutex lock and is holding
> r2_mutex lock and is executing the code in lines 9 and 10.
> 
> While T1 is busy executing code on lines 9 and 10, the queue gets 4 more
> requests and threads T2, T3, T4 and T5 (in that order) picks each one of
> them in the order in which they came into the queue and start processing
> them. They come till LINE 8 and wait to lock r2_mutex which thread T1 has
> currently locked.
> 
> Now, given this scenario, here is my question:
> After T1 unlocks r2_mutex, which thread among T2, T3, T4 and T5 gets the
> r2_mutex lock? Does pthread scheduler schedule (give the lock to) thread T2
> which came to LINE8 first??
> 

No the Lock is acquired by whichever thread is chosen by the scheduler to run
next, and that could be any of them.

Given that, I have to ask why you are bothering to use threads at all in the
consumer side of your application.  What you have described here is a system in
which you have multiple consumers of a queue, each of which are forced to run in
a certain order, as defined by the order in which they consume from the queue
protected by the r1 mutex.  If thats the case, why not instead simply create one
consumer thread?  It potentially eliminates the need for the r2 mutex (since you
only have one consumer thread).  Its not like multiple threads in the above
scenario offer any additional speedup anyway, since any thread that dequeues
data will have nothing to do but wait until all preceding data is processed
anyway.

Regards
Neil