1

The problem is simple, but I believe the solution (if one exists) is quite complicated. Anyhow, I am currently developing a distributed application which is supposed to implement simple transaction processing (PRINT, ADD, SLEEP, ASSIGN etc.) in parallel by the use of threads (I am using Pthreads for this assignment). As expected, I had a problem with deadlocks occurring when trying to process multiple conflicting transactions (which can be an amount as high as 20) simultaneously.

Now, I have decided to implement a number of retries for the transaction processing of each thread which is basically generated randomly using srand(time(NULL)) and rand() called in precisely that sequence. The problem is, when working with multiple transactions (on up to 5 different servers), the numbers match since they are basically generated at the same second in time.

So, my question is, is there a way to completely randomly generate integer numbers not using the time() function, but something else instead?

Thank you in advance for any help and sorry for the (too) long description.

alabroski
  • 79
  • 1
  • 8
  • What are you using the result of `rand` for? – ArjunShankar Jun 13 '13 at 21:08
  • 3
    Anyway, (1) Why are you calling `srand` multiple times? It is to be used once to seed the RNG. (2) I don't know if you're using `rand` from multiple threads, but it is not thread-safe. You've got to serialize calls to `rand` with a lock. (3) By the way, Intel's Ivy Bridge CPUs come with a hardware RNG available via the `RDRAND` instruction. – ArjunShankar Jun 13 '13 at 21:10
  • Note that you are not generating numbers (psuedo-)random numbers with `time(0)`, you are *seeding* the PRNG's state from `time(0)`. See http://stackoverflow.com/questions/203382/do-stateless-random-number-generators-exist. – dmckee --- ex-moderator kitten Jun 13 '13 at 21:15
  • This is what basically happens: `srand(time(NULL)); times = ( (rand()%11)+5 );` Times is a an int which is supposed to be randomly generated to control the number of possible retries to lock the database needed mutexes. – alabroski Jun 13 '13 at 22:03
  • The problem is that if `times` is for ex. 14 in one thread which is run at more or less the same milisecond as all the other threads (using a bash script), all other `times` variables will be 14 as well in all other threads. – alabroski Jun 13 '13 at 22:11
  • 1
    Calling `srand()` and `rand()` for each number is NOT generating random numbers, it's just generating a hash of the time at whatever the resolution of your clock is. Call `srand()` ONCE, at the start of your program, then `rand()` as needed. – Lee Daniel Crocker Jun 14 '13 at 00:53

3 Answers3

1

To have independent pseudo random generators PRG between different threads you'd have to be a bit more careful. Basically you'd have to keep the state of the generator in separate variables for each thread, and initialize each state just once with something that is different for each thread. E.g use time and thread id for the initialization.

Since you are on a POSIX system you could jrand48 as a generator function, but any random generator that allows you to pass a state as an argument should be fine.

Jens Gustedt
  • 76,821
  • 6
  • 102
  • 177
0

You should not be calling srand() before every call to rand(). That is the root cause of your problem. Instead, you should call srand() once only, at program startup, before you create your threads.

Additionally, rand() is not required to be thread-safe on POSIX, so you should use a mutex to serialise access to it from different threads.

caf
  • 233,326
  • 40
  • 323
  • 462
  • The problem is that due to system restrictions, I cannot use mutexes serialize access to any of the used variables - and especially not the `times` variable. – alabroski Jun 14 '13 at 06:34
0

As you have observed, using a PRNG to calculate backoff and retry timing does not work when several PRNGs are seeded with the same value. If conflicts are destructive, then both sessions will use the same retry timing and continue to cancel each other indefinitely.

If this is just one task multi-threaded application running on a single computer then you could try using the thread IDs as PRNG seeds.

If distribution can be wider than a single task then you would eventually run into the problem of combining all of the unique identifiers into a single unique identifier which fits into the size of the seed value. While the number of independent threads may be few enough, a predictably unique transform may be difficult.

Perhaps as part of the start-up on each thread, you should connect to the contended resource and acquire a unique session ID. If you can stagger the start-up of different threads then you don't have to deal with contention (simply refuse to start another thread before the first thread confirms that it's got its ID). If that's not possible (eg., in the widely distributed case) you'll have to compute your retry timing from some other random source, like /dev/urandom.

However, if it is possible to service just one of the n simultaneous requests, this problem can resolve itself.

Of n simultaneous requests, one client gets its response and carries on, while n-1 have to retry. The unsuccessful clients will advance their PRNG state, and the others will not. If they all have identical PRNG state then they'll all contend again, but one will get through and the others will try again. Eventually all will pass the conflict (one by one) and will have unique PRNG states.

sh1
  • 4,324
  • 17
  • 30