Class 17 — Monday, October 26
Quiz 7 first. Then Wednesday’s two threads, in your own project this time; after the break, work handed out to whichever thread asks.
- Two threads, and nobody waits for them — predict first
- The count, made right, with a test
- Two halves that take different times — keyboards down
- One number at a time, to whoever asks
Today is in IntelliJ, in the project that holds your Chain.java and the pom.xml from Class 14, which already fetches JUnit. If yours has no pom.xml, Class 14’s section 3.1 makes one.
1. Two threads, and nobody waits for them
Keyboards down.
Wednesday’s race, with a bigger count, 1,000,000 for each thread, and without the two join lines:
public class Race {
public static void main(String[] args) throws InterruptedException {
Counter counter = new Counter();
Thread first = new Thread(() -> {
for (int i = 0; i < 1_000_000; i++) {
counter.increment();
}
});
Thread second = new Thread(() -> {
for (int i = 0; i < 1_000_000; i++) {
counter.increment();
}
});
first.start();
second.start();
System.out.println(counter.get());
}
}Counter is Wednesday’s, with no synchronized. Three answers have been given for programs like this one:
(a) 2000000, (b) a number short of 2000000, as on Wednesday, (c) a number much smaller than that. Which, and why?
2. The count, made right, with a test
Pairs, in your own project. 2.1 and 2.2, then 2.3 to 2.5 if you are done.
2.1 Put the joins back
Race from section 1 in src, and beside it Wednesday’s Counter:
// a count that two threads share
public class Counter {
private int count;
public void increment() {
count++;
}
public int get() {
return count;
}
}Run Race three times as it is; then put back first.join(); and second.join(); before the println, and run it three times again.
Done when you have the six numbers and can say what the joins changed, and what they did not.
2.2 synchronized, and a test that knows
Mark increment synchronized, and run Race three times: 2000000 each time.
synchronized gives the Counter one lock. A thread must hold the lock to run increment, and releases it when increment returns; a second thread that arrives meanwhile waits. So one read, add and write finishes before the next begins. The lock belongs to the object both threads change.
Your test: test/CounterTest.java: four threads, each a lambda adding 1 to one Counter 250,000 times; start all four, join all four, and assertEquals(1_000_000, counter.get()).
Done when it is green, and goes red when you take synchronized off (then put it back).
2.3 synchronized in the wrong place (if you are done)
Take synchronized off increment again. A new class in src, the thread’s work as a class, with synchronized on its run instead:
// adds 1 to its counter, 1,000,000 times
public class Adder implements Runnable {
private final Counter counter;
public Adder(Counter counter) {
this.counter = counter;
}
public synchronized void run() {
for (int i = 0; i < 1_000_000; i++) {
counter.increment();
}
}
}Then a main: one Counter, two threads, each with its own Adder on that Counter; start both, join both, print the count. Before you run it, write in a comment: 2000000, or not?
Done when a comment above main says what three runs printed and why synchronized on run did not help. Then put synchronized back on increment.
Each Adder is a different object, and each object has its own lock. Each thread takes its own Adder’s lock, nobody waits for anybody, and the two count++s still interleave. Five runs here printed 1706962, 1689338, 1924550, 1027744 and 1853174. The lock that matters is the Counter’s, the one object both threads change.
Hand both threads the same Adder and it prints 2000000. But then one thread holds the lock for its whole million while the other waits, so nothing runs at the same time.
2.4 Each thread its own half (if you are done)
Two threads, each adding up its own half of one array. A new class, HalfSum implements Runnable, with four fields: the array, where its half starts, where its half stops, and a long sum, its result. The two halves of an array of 10 are places 0 to 4 and places 5 to 9, so the first HalfSum starts at 0 and stops before 5, and the second starts at 5 and stops before 10. run adds up its half into sum.
Then a main: an array of 10,000,000 numbers, i % 7 in place i, added up in two halves on two threads; after both joins, it prints the two sums added together beside the total of one ordinary loop.
Your test: the two halves of an array of 1 to 100 add up to 5050.
2.5 Any number of parts (if you are done)
Part i of n runs from i * length / n up to (i + 1) * length / n. Keep the threads in a List<Thread>, start them all, then join them all.
Your test: 3 parts of an array of 10 numbers add up to what one loop gives.
3. Two halves that take different times
Keyboards down.
Here is a way to tell whether a number is prime: try every divisor from 2 up to its square root.
// whether n is prime: no divisor from 2 up to its square root
static boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
return false;
}
}
return true;
}Counting the primes below 3,000,000 with it, on one thread, and then in two halves on two threads, each half counting its own (JDK 25, three runs each):
| time | |
|---|---|
| one thread, all of it | about 410 ms |
| two halves, together | about 262 ms |
| the lower half alone | about 155 ms |
| the upper half alone | about 257 ms |
Why does the upper half take longer? And how could two threads share the numbers so that neither one sits finished while the other works?
A big number has more divisors to try before it is called prime, so the upper half is more work, and the lower half’s thread finishes and waits. Halves are shared out before any thread starts. The other way is on demand: each thread asks for the next number nobody has taken, checks it, and comes back for another. A thread that gets quick numbers simply takes more of them.
The numbers are handed out by one object that every thread asks. It is the one thing that changes while they run, so its method is the one that needs synchronized.
4. One number at a time, to whoever asks
Pairs, in your own project. 4.1 and 4.2, then 4.3 and 4.4 if you are done.
4.1 Numbers
A new class in src:
// hands out the numbers below limit, one at a time
public class Numbers {
private final int limit;
private int next;
public Numbers(int limit) {
this.limit = limit;
}
// the next number nobody has taken, or -1 when there is none
public synchronized int next() {
if (next >= limit) {
return -1;
}
int n = next;
next = next + 1;
return n;
}
}Add to it: a limit below 0 makes no sense, so the constructor throws an IllegalArgumentException when limit is negative.
Your tests, in test/NumbersTest.java: new Numbers(3) hands out 0, 1 and 2, then -1, and -1 again. Then a second test:
The lambda is the code that should throw; assertThrows runs it and is green only if it throws that exception.
Done when both tests are green.
4.2 NumberCounter, and four of them
NumberCounter implements Runnable, with the Numbers it shares and two fields of its own: how many primes it found, and how many numbers it took. run asks for a number, checks it with section 3’s isPrime, and asks again, until next() gives -1.
Then a main: one Numbers below 3,000,000; four NumberCounters on it and a thread for each; start all four, join all four; print the primes added up, and how many numbers each counter took.
Your test: four counters share the numbers below 100,000. The primes they found add up to 9592, and the numbers they took add up to 100,000.
Done when your main prints 216816 and your test is green.
4.3 Against the clock (if you are done)
Time it: long start = System.nanoTime(); before, and (System.nanoTime() - start) / 1_000_000 milliseconds after, three runs each: one thread that checks every number itself, then your four counters. How much faster are four?
4.4 Take synchronized off (if you are done)
Take synchronized off next() and run your main three times. What happens to the count of primes, and to the numbers taken added up? Then run your test. Put synchronized back.