Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #488 > unrolled thread

Non-deterministic behavior of multithreaded software

Back to article view | Back to comp.programming.threads

Contents

  Non-deterministic behavior of multithreaded software itt ium <ittium@gmail.com> - 2011-08-05 02:42 -0700
    Re: Non-deterministic behavior of multithreaded software "Balog Pal" <pasa@lib.hu> - 2011-08-05 16:20 +0200
      Re: Non-deterministic behavior of multithreaded software ittium <ittium@gmail.com> - 2011-08-09 08:49 +0530
      Re: Non-deterministic behavior of multithreaded software ittium <ittium@gmail.com> - 2011-08-09 08:52 +0530
    Re: Non-deterministic behavior of multithreaded software Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-05 16:17 +0100
      Re: Non-deterministic behavior of multithreaded software ittium <ittium@gmail.com> - 2011-08-09 09:19 +0530
        Re: Non-deterministic behavior of multithreaded software Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-09 14:08 +0100
    Re: Non-deterministic behavior of multithreaded software David Schwartz <davids@webmaster.com> - 2011-08-10 12:37 -0700

#488 — Non-deterministic behavior of multithreaded software

Group,
I have recently modified a software from single threaded to
multithreaded design. In single threaded version, a connection fd was
read by single thread, so event were always delivered in order. Now
since multiple threads handle different events (on the same fd), the
events are sometimes delivered out of order. Please note, on the
connection fd, events are received in proper order and this non-
deterministic behavior is introduced by my software only.

Following are my doubt

1. How to handle such a situation

2. Is it a bad idea to have multiple threads for the same fd. If yes
than how to increase capacity of a software that receives large amount
of data on a single fd only.

Because of the relevance I am posting the message to following groups.

comp.unix.programmer

comp.programming.threads

thanks
Ittium

[toc] | [next] | [standalone]

#489

"itt ium" <ittium@gmail.com>

> I have recently modified a software from single threaded to
> multithreaded design. In single threaded version, a connection fd was
> read by single thread, so event were always delivered in order. Now
> since multiple threads handle different events (on the same fd), the
> events are sometimes delivered out of order.

You mean processed.

> Please note, on the
> connection fd, events are received in proper order and this non-
> deterministic behavior is introduced by my software only.
>
> 1. How to handle such a situation

Go back one square, to your single-threaded design. And only start threading 
when you know to what end.

> 2. Is it a bad idea to have multiple threads for the same fd. If yes
> than how to increase capacity of a software that receives large amount
> of data on a single fd only.

In what you write I see little relevance of the fd. You need processing of 
the events one after the other, waiting to start the next until the previous 
finishes, right? So you shall not try to run them in parallel. And a single 
thread does just that.   (If your problem is not like that, state it 
clearly.)

If reading the fd is really a concern, then you can put that in one thread 
and processing in another. So you have a simplest 1-1 producer-consumer 
queue, one thread rads and posts to the queu, the other processes the events 
in the queue. If the source of events is independent, you will have the 
reading in parallel.

[toc] | [prev] | [next] | [standalone]

#492

On 05-08-2011 PM 07:50, Balog Pal wrote:
> "itt ium" <ittium@gmail.com>
>
>> I have recently modified a software from single threaded to
>> multithreaded design. In single threaded version, a connection fd was
>> read by single thread, so event were always delivered in order. Now
>> since multiple threads handle different events (on the same fd), the
>> events are sometimes delivered out of order.
>
> You mean processed.

Yes, There is another module that receives the processed data and that 
data is delivered to the module out of order.

>
>> Please note, on the
>> connection fd, events are received in proper order and this non-
>> deterministic behavior is introduced by my software only.
>>
>> 1. How to handle such a situation
>
> Go back one square, to your single-threaded design. And only start
> threading when you know to what end.

We want to increase the message processing capacity per second  for the 
software.with a single threaded design, we have reached the maximum 
capacity (in terms of message processed per second). Please note we are 
running the software on a hexacore machine.

>
>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>> than how to increase capacity of a software that receives large amount
>> of data on a single fd only.
>
> In what you write I see little relevance of the fd. You need processing
> of the events one after the other, waiting to start the next until the
> previous finishes, right? So you shall not try to run them in parallel.
> And a single thread does just that. (If your problem is not like that,
> state it clearly.)
>
> If reading the fd is really a concern, then you can put that in one
> thread and processing in another. So you have a simplest 1-1

1-1 is not likely a solution, it will only introduce unnecessary context 
switch. In our solution, there are multiple worker threads, each can 
read from fd, when fd is ready.

> producer-consumer queue, one thread rads and posts to the queu, the
> other processes the events in the queue. If the source of events is
> independent, you will have the reading in parallel.
>

[toc] | [prev] | [next] | [standalone]

#493

On 05-08-2011 PM 07:50, Balog Pal wrote:
 > "itt ium" <ittium@gmail.com>
 >
 >> I have recently modified a software from single threaded to
 >> multithreaded design. In single threaded version, a connection fd was
 >> read by single thread, so event were always delivered in order. Now
 >> since multiple threads handle different events (on the same fd), the
 >> events are sometimes delivered out of order.
 >
 > You mean processed.

Yes, There is another module that receives the processed data and that 
data is delivered to the module out of order.

 >
 >> Please note, on the
 >> connection fd, events are received in proper order and this non-
 >> deterministic behavior is introduced by my software only.
 >>
 >> 1. How to handle such a situation
 >
 > Go back one square, to your single-threaded design. And only start
 > threading when you know to what end.

We want to increase the message processing capacity per second  for the 
software.with a single threaded design, we have reached the maximum 
capacity (in terms of message processed per second). Please note we are 
running the software on a hexacore machine.

 >
 >> 2. Is it a bad idea to have multiple threads for the same fd. If yes
 >> than how to increase capacity of a software that receives large amount
 >> of data on a single fd only.
 >
 > In what you write I see little relevance of the fd. You need processing
 > of the events one after the other, waiting to start the next until the
 > previous finishes, right? So you shall not try to run them in parallel.
 > And a single thread does just that. (If your problem is not like that,
 > state it clearly.)
 >
 > If reading the fd is really a concern, then you can put that in one
 > thread and processing in another. So you have a simplest 1-1

1-1 is not likely a solution, it will only introduce unnecessary context 
switch. In our solution, there are multiple worker threads, each can 
read from fd, when fd is ready.

 > producer-consumer queue, one thread rads and posts to the queu, the
 > other processes the events in the queue. If the source of events is
 > independent, you will have the reading in parallel.
 >

[toc] | [prev] | [next] | [standalone]

#491

itt ium <ittium@gmail.com> writes:

> Group,
> I have recently modified a software from single threaded to
> multithreaded design. In single threaded version, a connection fd was
> read by single thread, so event were always delivered in order. Now
> since multiple threads handle different events (on the same fd), the
> events are sometimes delivered out of order. Please note, on the
> connection fd, events are received in proper order and this non-
> deterministic behavior is introduced by my software only.
>
> Following are my doubt
>
> 1. How to handle such a situation

That's nothing less than one of the basic questions of concurrent
programming -- how to ensure that actions occur in only one of the
(possibly many) permitted orders and never in any of the prohibited
orders.  It's too general a question to be answered here.

> 2. Is it a bad idea to have multiple threads for the same fd. If yes
> than how to increase capacity of a software that receives large amount
> of data on a single fd only.

It can be a bad idea but it can also be a perfectly sound one.  Because
you are not sure I suspect you have a case where it is a bad idea, but I
can't be certain of that.  The key is probably this: if a thread can
determine what it needs to know in order to schedule its actions with
respect to the other threads by looking at the data it reads (and maybe,
in addition, consulting a little shared data too) then having multiple
readers is probably fine.  If the threads can't do this, or they would
need to cooperate in maintaining a lot of shared data in order to do
this, then you are probably better off with one reader which organises
the work of the others.

> Because of the relevance I am posting the message to following groups.
>
> comp.unix.programmer
> comp.programming.threads

That's a bad idea.  Cross posting is generally referred to multi-posting.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#494

On 05-08-2011 PM 08:47, Ben Bacarisse wrote:
> itt ium<ittium@gmail.com>  writes:
>
>> Group,
>> I have recently modified a software from single threaded to
>> multithreaded design. In single threaded version, a connection fd was
>> read by single thread, so event were always delivered in order. Now
>> since multiple threads handle different events (on the same fd), the
>> events are sometimes delivered out of order. Please note, on the
>> connection fd, events are received in proper order and this non-
>> deterministic behavior is introduced by my software only.
>>
>> Following are my doubt
>>
>> 1. How to handle such a situation
>
> That's nothing less than one of the basic questions of concurrent
> programming -- how to ensure that actions occur in only one of the
> (possibly many) permitted orders and never in any of the prohibited
> orders.  It's too general a question to be answered here.
>

I appreciate your thought on it. But I was thinking of getting the help 
from experts so that I am not reinventing the wheel. I have done 
sufficient googling before posting it. Closest solution, is studying the 
software using concurrent sequential processing grammar (CSP). It will 
take sometime for me to learn the grammar.

>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>> than how to increase capacity of a software that receives large amount
>> of data on a single fd only.
>
> It can be a bad idea but it can also be a perfectly sound one.  Because
> you are not sure I suspect you have a case where it is a bad idea, but I
> can't be certain of that.  The key is probably this: if a thread can
> determine what it needs to know in order to schedule its actions with
> respect to the other threads by looking at the data it reads (and maybe,
> in addition, consulting a little shared data too) then having multiple
> readers is probably fine.  If the threads can't do this, or they would
> need to cooperate in maintaining a lot of shared data in order to do
> this, then you are probably better off with one reader which organises
> the work of the others.
>

There are few more inputs here. My software is handing the call session. 
The problem occur, if event for a call are delivered out of order. I 
have modified the software such that message belonging to a call are 
processed by same thread, in this way ordering of events for the call 
state machine is maintained. But this has introduced a pinner thread 
that assign the messages to different worker threads based on a a hash 
function that take input as call ID.

1. Thread ID may not be uniformly distributed, any logic of work 
devision might load few thread.

2. A context switch is introduced because of pinner. Earlier a single 
thread was doing all the work (from reading from socket to delivering it 
to other modules.

>> Because of the relevance I am posting the message to following groups.
>>
>> comp.unix.programmer
>> comp.programming.threads
>
> That's a bad idea.  Cross posting is generally referred to multi-posting.
>

thanks for pointing this out. I was thinking, some of the members of 
comp.unix.programmer might have worked on message processing systems and 
can help me.

[toc] | [prev] | [next] | [standalone]

#498

ittium <ittium@gmail.com> writes:
<snip>
> There are few more inputs here. My software is handing the call
> session. The problem occur, if event for a call are delivered out of
> order. I have modified the software such that message belonging to a
> call are processed by same thread, in this way ordering of events for
> the call state machine is maintained. But this has introduced a pinner
> thread that assign the messages to different worker threads based on a
> a hash function that take input as call ID.
>
> 1. Thread ID may not be uniformly distributed, any logic of work
> devision might load few thread.

One plan would be for the reader to assemble all the data related to one
call into a single "work item".  These are queued, and worker threads
take work items as they (the workers) become free.  This increases the
latency (no work gets done until the complete work item is assembled)
but it will be good for throughput.  So far you have only said that you
want to increase the throughput so this might be acceptable.

> 2. A context switch is introduced because of pinner. Earlier a single
> thread was doing all the work (from reading from socket to delivering
> it to other modules.

Can you explain what you mean by a context switch?  In my (probably
outdated) vocabulary, a context switch occurs with, say, a call to the
kernel.  With that meaning your old code was making context switches all
the time: when it called read.  So what is it that has been added in the
new design that is bad and which you'd like to avoid?

>>> Because of the relevance I am posting the message to following groups.
>>>
>>> comp.unix.programmer
>>> comp.programming.threads
>>
>> That's a bad idea.  Cross posting is generally referred to
>> multi-posting.

Typo: I meant to say "Cross posting is generally *preferred* to
multi-posting".

> thanks for pointing this out. I was thinking, some of the members of
> comp.unix.programmer might have worked on message processing systems
> and can help me.

Yes, there's no problem posting to more than one group (so long as it is
not more than a few groups) but if you cross-post (i.e. you post once
putting both the groups into the "Newsgroups: ..." header) then everyone
sees the messages only once even when they read both groups, and replies
in one group get seen by readers of the other.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#502

On Aug 5, 2:42 am, itt ium <itt...@gmail.com> wrote:
> Group,
> I have recently modified a software from single threaded to
> multithreaded design. In single threaded version, a connection fd was
> read by single thread, so event were always delivered in order. Now
> since multiple threads handle different events (on the same fd), the
> events are sometimes delivered out of order. Please note, on the
> connection fd, events are received in proper order and this non-
> deterministic behavior is introduced by my software only.

Is the concern that the events are being processed out of order? Or is
it only that the results are being delivered out of order?

If the events can be processed out of order and only the results need
to be re-ordered, then reorder the results using an assembly line
approach.

Keep the events in a structure (like a linked list) and don't deliver
the results of any event but the event at the end of the linked list
(after which you remove its structure from the list).

DS

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web