[concurrency-interest] j.u.c/backport performance on Windows

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Wed Apr 4 06:22:54 EDT 2007


On 02/04/07, Peter Kovacs <peter.kovacs.1.0rc at gmail.com> wrote:

> From this perspective, I am not sure how I could maintain the required
> semantics whithout the the equivalent of an inputProducerLock. Please,
> let me know, what you think.

I think there are other means as well to establish the semantics you
want. Just for curiosity, I am going to show some other solutions, not
by Java language means, however, but rather by concurrency patterns.

So, your constraint is that the order of items in the beginning should
be the same as the order of the corresponding work packages at the
end.

Now, as far as the processes are concerned, you have N producers
(workers) and one single consumer. Additionally, you have a container
for the items (`I'), and an intermediate queue (`Q'). I would
visualize it like this (please set non-proportional characters to view
it properly):

                      |<---/W1/--->|
|WP|<---/C/--->|Q|<---|<---/W2/--->|--->|I|
                      |<---/W3/--->|

Some hint for the notation: `/P/' denotes a process, `|D|' denotes a
data structure, and `--->' denotes access. Here your problem is that
you have to use a critical region in the workers to ensure the same
order in the data structures `I' and `Q'. The critical region is also
needed for accessing the shared data structure `I' by the concurrent
workers `Wn' via an iterator.

One possible other solution is if you change the arrangement so that
the workers form a pipeline themselves like this:

|WP|<---/C/--->|Q|<---/W3/<--->/W2/<--->/W1/--->|I|

Here, the activity of the workers can be described as follows: Each
worker obtains an element from the right hand side. Workers must know
their position in the pipeline. Each worker forwards as many elements
without processing as many workers are sitting behind it in the
pipeline, and then it processes the next unprocessed element and
forwards it to the left. If the element from the right hand side is
processed already, it simply forwards it to the left. I hope this
works and maintains your constraint.

Another way the same ordering can be maintained between the input and
the output containers is where the worker pool is mediated by a master
process. The master is the one that takes elements from the right
(`I'), assigns a work package to one of the idle workers and forwards
the processed packages to the queue (`Q') in the same order. Workers
can be arranged by the Chain of Responsibility pattern.

|WP|<---/C/--->|Q|<---/M/--->|I|
                       |
                 --------------
                 /W1/ /W2/ /W3/

These solutions I could come up with. What do you think about them?
Perhaps changing the pattern is not an option to you, I just made this
comment to show that some concurrency problems can be avoided by
selecting the appropriate pattern for a given constraint.

Best Regards,
Szabolcs


More information about the Concurrency-interest mailing list