0

I got one main thread that will start up other threads. Those other threads will ask for jobs to be done, and the main thread will make jobs available for the other threads to see and do.

The job that must be done is to set indexes in the a huge boolean array to true. They are by default false, and the other threads can only set them to true, never false. The various jobs may involve setting the same indexes to true.

The main thread finds new jobs depending on two things.

  1. The values in the huge boolean array.
  2. Which jobs has already been done.

How do I make sure the main thread reads fresh values from the huge boolean array?

I can't have the update of the array be through a synchronized method, because that's pretty much all the other threads do, and as such I would only get a pretty much sequential performance.

Let's say the other threads update the huge boolean array by setting many of it's indexes to true through a non-synchronized function. How can I make sure the main thread reads the updates and make sure it's not just locally cached at the thread? Is there any ways to make it "push" the update? I'm guessing the main thread should just use a synchronized method to "get" the updates?

Horse SMith
  • 1,003
  • 2
  • 12
  • 25

4 Answers4

1

For the really complete answer to your question, you should open up a copy of the Java Language Spec, and search for "happens before".

When the JLS says that A "happens before" B, it means that in a valid implementation of the Java language, A is required to actually happen before B. The spec says things like:

  • If some thread updates a field, and then releases a lock (e.g., leaves a synchronized block), the update "happens before" the lock is released,

  • If some thread releases a lock, and some other thread subsequently
    acquires the same lock, the release "happens before" the acquisition.

  • If some thread acquires a lock, and then reads a field, the acquisition "happens before" the read.

Since "happens before" is a transitive relationship, you can infer that if thread A updates some variables inside a synchronized block and then thread B examines the variables in a block that is synchronized on the same object, then thread B will see what thread A wrote.

Besides entering and leaving synchronized blocks, there are lots of other events (constructing objects, wait()ing/notify()ing objects, start()ing and join()ing threads, reading and writing volatile variables) that allow you to establish "happens before" relationships between threads.

It's not a quick solution to your problem, but the chapter is worth reading.

...the main thread will make jobs available for the other threads to see and do...

I can't have the update of the array be through a synchronized method, because that's pretty much all the other threads do, and ...

Sounds like you're saying that each worker thread can only do a trivial amount of work before it must wait for further instructions from the main() thread. If that's true, then most of the workers are going to be waiting most of the time. You'd probably get better performance if you just do all of the work in a single thread.

Assuming that your goal is to make the best use of available cycles a multi-processor machine, you will need to partition the work in some way that lets each worker thread go off and do a significant chunk of it before needing to synchronize with any other thread.

Community
  • 1
  • 1
Solomon Slow
  • 25,130
  • 5
  • 37
  • 57
  • Well, the job I want to split into different threads is the setting of indexes in an array to true. So it would be kind of stupid to synchronize the method that sets the values, because then it would be pretty much sequential. You say wait allow for the "happens before"? :) Could I use CyclicBarrier? – Horse SMith Mar 05 '15 at 06:50
  • In the documentation of CyclicBarrier it says, "Memory consistency effects: Actions in a thread prior to calling await() happen-before actions that are part of the barrier action, which in turn happen-before actions following a successful return from the corresponding await() in other threads.". What is this supposed to mean? – Horse SMith Mar 05 '15 at 07:54
  • @HorseSMith, Assuming that when you say, "...it would be kind of stupid to synchronize..." you mean that you do not see any need for mutual exclusion. It's unfortunate that they chose the keyword `synchronized` for mutual exclusion because they use the phrase "synchronizes with" in the JLS to describe any event that participates in a cross-thread "happens before" situation. (e.g., "A write to a `volatile` variable `v` _synchronizes with_ all subsequent reads of `v` by any thread.") IIRC, they chose `synchronized` before they documented the JLS memory model. – Solomon Slow Mar 05 '15 at 11:54
  • @HorseSMith Re, CyclicBarrier: A "happens before" B if A and B both happen in the same thread, and A comes before B in _program order_. So, if one thread updates a field and then it calls `barrier.await()` and then some other thread subsequently returns from `barrier.await()` and then reads the same field, the other thread will be guaranteed to get the value that the first thread wrote. – Solomon Slow Mar 05 '15 at 12:04
  • Does the same go for wait and notify/notifyall? – Horse SMith Mar 05 '15 at 16:28
  • @HorseSMith It doesn't need to be explicitly said for `o.notify()` and `o.wait()` because of the way those functions interact with locks. `o.wait()` releases and then re-acquires the lock on object `o`, and you can't call `o.wait()` or `o.nofify()` if you don't have the object locked. – Solomon Slow Mar 05 '15 at 18:09
0

I'd use another design pattern. For instance, you could add to a Set the indexes of the boolean values as they're turned on, for instance, and then synchronize access to that. Then you can use wait/notify to wake up.

Joseph Larson
  • 8,530
  • 1
  • 19
  • 36
  • I already pointed out that this would be so redundant that it may as well be sequential, and it probably would perform worse. – Horse SMith Mar 05 '15 at 02:21
  • I think you're going to need to offer more information, then. – Joseph Larson Mar 05 '15 at 02:28
  • There really isn't much more to say. Each job is to set various indexes in the huge array to true. How does it decide the indexes? It's a for loop where it starts and ends where the job tells it to and have steps as big as the job says. – Horse SMith Mar 05 '15 at 02:36
0

First of all, don't use boolean arrays in general, use BitSets. See this: boolean[] vs. BitSet: Which is more efficient?

In this case you need an atomic BitSet, so you can't use the java.util.BitSet, but here is one: AtomicBitSet implementation for java

Community
  • 1
  • 1
lbalazscs
  • 17,474
  • 7
  • 42
  • 50
  • While I totally agree that I should use AtomicBitSet instead, what would be a good way to go about it if I had to solve this using a boolean array? – Horse SMith Mar 05 '15 at 03:58
0

You could instead model this as message passing rather than mutating shared state. In your description the workers never read the boolean array and only write the completion status. Have you considered using a pending job queue that workers consume from and a completion queue that the master reads? The job status fields can be efficiently maintained by the master thread without any shared state concerns. Depending on your needs, you can use either blocking or non-blocking queues.

Ben Manes
  • 9,178
  • 3
  • 35
  • 39