Hi Joe,

Sorry for the delays. Here is the diff.
The replacement of the signal is to prevent false wakeups. It should be
correct, but I can throw it through a modelchecker if you like?

Kind regards,

Steven van der vegt

-----Oorspronkelijk bericht-----
Van: Joe Gooch [mailto:mrwizard(at)k12system.com] 
Verzonden: vrijdag 25 februari 2011 18:25
Aan: pound(at)apsis.ch
Onderwerp: [Pound Mailing List] RE: Queue implementation errors?

I looked at it and I agree, the crux of the problem seems to be the "next"
variable in the tree isn't always populated.

You moved the signal too... Not sure if that's right or not.

Could provide your modified .c file so we could make a proper diff?

Thanks.

Joe
[...]

--
To unsubscribe send an email with subject unsubscribe to pound(at)apsis.ch.
Please contact roseg(at)apsis.ch for questions.

On Wed, 2011-02-16 at 16:40 +0000, Steven van der Vegt wrote:[...]
[...]

1. you have moved the NULL check from the caller in http.c to the getter
in pound.c (a NULL check is required in any case, as the condition
wake-up may occur even when there is no data to be consumed)

2. you have replaced the cond_signal with a cond_broadcast in the
enqueing function

The first change should make no difference (it is just moving the actual
check to another place). The second will cause more threads to wake-up,
quite often more than are required. I must admit am not at all clear how
should this help.[...]

As I see it this is the most important change:[...]


res->next isn't set to null in the 2.6c code.

Joe
[...]

As I see it this is the most important change:[...]


res->next isn't set to null in the 2.6c code.

Joe
[...]

> From what I see, you have made two changes:
[...]

This is true, but why place this responsibility by the caller? This get_thr_arg
is meant to be partial right? Now it is not. Also I think the code is more
clear now, but that's of course a matter of taste :)
[...]
[...]

This will prevent lost-wakeups. So instead of waking-up one thread, You wake
them all up.

I also made an error in my code. After every dequeue() I signaled This is not
necessary. I attached my new pound.c file.

Steven

-----Oorspronkelijk bericht-----
Van: Robert Segall [mailto:roseg(at)apsis.ch] 
Verzonden: maandag 7 maart 2011 9:38
Aan: pound(at)apsis.ch
Onderwerp: Re: [Pound Mailing List] Queue implementation errors?

On Wed, 2011-02-16 at 16:40 +0000, Steven van der Vegt wrote:[...]
[...]

1. you have moved the NULL check from the caller in http.c to the getter
in pound.c (a NULL check is required in any case, as the condition
wake-up may occur even when there is no data to be consumed)

2. you have replaced the cond_signal with a cond_broadcast in the
enqueing function

The first change should make no difference (it is just moving the actual
check to another place). The second will cause more threads to wake-up,
quite often more than are required. I must admit am not at all clear how
should this help.[...]

On Wed, 2011-03-09 at 10:54 +0000, Steven van der Vegt wrote:[...]

As you say, a matter of style and taste.
[...]

No error. Signals are lost if no thread is waiting. If you don't signal
you may well end up with things on the queue and all threads sleeping.
For example:

- assume 8 worker threads
- you get 12 requests in quick succession
	- the first 8 are consumed by the threads
	- the following 4 are enqueued while the threads are busy
- the 8 threads finish working and go to sleep, waiting for a signal
- 4 requests stay in the queue

This is the reason that the broadcast does not help (the signal is
ignored by active threads) and the signal is necessary on dequeue.[...]

On Mon, 2011-03-07 at 14:57 +0000, Joe Gooch wrote:[...]

Thanks, excellent catch. Fixed and will be part of 2.6d[...]

First, I don't want this discussion to become a "Yes it is. No it isn't" one.
As long as you too think this is an interesting conversation, I will try to
explain my code :)
[...]

I think your example is incorrect, because:
[...]

Correct so far...
[...]

The only line which can put a thread to sleep is the following one in the
get_thr_arg():

while (first == NULL)
        (void)pthread_cond_wait(&arg_cond, &arg_mut);

This only happens if the queue is empty, with 4 queued items, this is not the
case.
[...]

The only moment a thread has to be wake-upped is when the queue is empty (thus,
all threads are sleeping) and an item is added. If a item is added and the
queue is not empty, apparently all threads are running. They will check later
for that newly added item.

If you are not sure about the solution, please check it with a verification
tool like SPIN. As far as I can see, it is safe, and more efficient than the
current one.


Kind regards,

Steven

-----Oorspronkelijk bericht-----
Van: Robert Segall [mailto:roseg(at)apsis.ch] 
Verzonden: donderdag 17 maart 2011 17:45
Aan: pound(at)apsis.ch
Onderwerp: RE: [Pound Mailing List] Queue implementation errors?

On Wed, 2011-03-09 at 10:54 +0000, Steven van der Vegt wrote:[...]

As you say, a matter of style and taste.
[...]

No error. Signals are lost if no thread is waiting. If you don't signal
you may well end up with things on the queue and all threads sleeping.
For example:

- assume 8 worker threads
- you get 12 requests in quick succession
	- the first 8 are consumed by the threads
	- the following 4 are enqueued while the threads are busy
- the 8 threads finish working and go to sleep, waiting for a signal
- 4 requests stay in the queue

This is the reason that the broadcast does not help (the signal is
ignored by active threads) and the signal is necessary on dequeue.[...]