CODEWITHSUNDEEP
javamultithreading
John
John

Reputation: 837

Priority semaphore in Java

I have a multiple threads program, each thread calculates the GCD of two numbers and print out the result. The problem I have right now is I have to print the result in ascending order. I'm not sure how to do this. This is school assignment. we are not allowed to use any extra thread to sort the result and output and cannot do the print out in the main thread too.

Upvotes: 2

Views: 658

Answers (4)

user207421
user207421

Reputation: 310915

By the title of your question, if not its wording, it sounds like you need to use a counting semaphore. You could do something clever using each thread's GCD value as its countdown value. Details left as an exercise for the reader :-)

Upvotes: 0

fge
fge

Reputation: 121720

Since you want the results ordered, one fact is obvious: you cannot do this until you have collected all the results.

What is more, some couple of numbers may return the same GCD (9 and 3, 18 and 3)...

Since it is unclear what you are allowed to use, here is a sample implementation using Java's FutureTask (and Callable, we have to)

Note, no exception checking or anything, therefore unsuitable for any production purposes... It even obeys the constraint that "cannot do the print out in the main thread too".

public final class GCDExcercise
{
    /*
     * Method returning a Callable<Integer>. The .call() implementation returns
     * the GCD of the two numbers given as arguments. Left to implementers.
     *
     * n1 and n2 MUST be declared final, as they are used from an anonymous
     * class returned from that function.
     */
    private static Callable<Integer> gdc(final int n1, final int n2)
    {
        return new Callable<Integer>()
        {
            @Override
            public Integer call()
            {
                // Calculate gdc of n1 and n2 here, return it
            }
        };
    }

    /*
     * One worker. The only thing it does is delegate calculation to the task
     * above, we let FutureTask handle the rest (and there is a lot).
     */
    private static class GCDComputation
        extends FutureTask<Integer>
    {
        GCDComputation(int n1, int n2)
        {
            super(gdc(n1, n2));
        }
    }

    /*
     * IMPLEMENTATION SPECIFIC. Here, Guava's ImmutableList is used to return a
     * very small subset of values. In "real life", will return something from
     * a file or something else. Left as an exercise to the reader.
     */
    private static Collection<GCDComputation> getComputations()
    {
        // Shuffle, add, etc -- results will be consistent anyway
        return ImmutableList.of(
            new GCDComputation(18, 17), // 1
            new GCDComputation(12, 3),  // 3
            new GCDComputation(9, 180), // 9
            new GCDComputation(8921830, 989280), // 10
            new GCDComputation(8723, 982) // 1
        );
    }

    // Main program, with obligatory throws
    public static void main(String... args)
        throws ExecutionException, InterruptedException
    {
        // Our list of threads
        List<GCDComputation> threads = new ArrayList<GCDComputation>();

        /*
         * Add each FutureTask to the list -- and run it. We MUST do so, since
         * those are not daemon threads.
         */
        for (GCDComputation result: getComputations()) {
            threads.add(result);
            result.run();
        }

        /*
         * Collect the list of result: create the list, add elements to it, and
         * sort it.
         */
        final List<Integer> ret = new ArrayList<Integer>();

        for (final GCDComputation result: threads)
            ret.add(result.get());

        Collections.sort(ret);

        /*
         * Print results! In a separate thread since this is what is asked...
         */
        new Runnable() {
            @Override
            public void run()
            {
                for (int i : ret)
                    System.out.println(i);

            }
        }.run();

        // Outta here 
        System.exit(0);
    }
}

Upvotes: 2

Hitman47
Hitman47

Reputation: 421

Calculates the GCD and then sleep the thread by GCD secs

Upvotes: 1

assylias
assylias

Reputation: 328618

I understand that you need to print the GCDs in ascending order.

If that is the case, you can simply spawn as many threads as you need and have them put the result in a shared collection, then print the collection from one of those threads once all the other spawned threads have finished.

For example, have the first thread start the other threads, then join and print. Or you could use a CountDownLatch to know when the collection is full.

Make sure the collection is either thread safe or protected by a lock.

Upvotes: 5

Related Questions