Class 18 — Wednesday, October 28

How big a piece of work each thread should take; then two transfers that wait for each other forever, and the order that stops it.

Monday ended at one number at a time. Today starts from there; after the break, money moves between accounts, and two threads can wait for each other forever.

  1. How big a piece? — keyboards down
  2. Pieces of any size
  3. Two transfers, both ways — predict first
  4. Take the locks in order
  5. One lock, or a lock each? — keyboards down
  6. Many accounts

Today’s work has a project of its own, which you copy once and keep:

  1. On https://github.com/cu-cs-labs/cmsc-230-threads, click Use this template, then Create a new repository: under your own account, Private.
  2. In IntelliJ: File, New, Project from Version Control, with your copy’s URL. IntelliJ fetches JUnit by itself.
  3. Before you leave, commit and push: next class you may sit at another computer.

It has Monday’s Numbers and NumberCounter with their tests, and the two files section 3 runs.

1. How big a piece?

Keyboards down.

Monday’s Numbers handed out one number per call to next(). It could hand out a block instead: a run of numbers in one call. With blocks of 100, the first call gives a thread the numbers 0 to 99, the next call gives someone 100 to 199, and so on; a thread checks its whole block by itself, and only then comes back for another. One number at a time is blocks of 1. A quarter each, blocks of 750,000, is four blocks for four threads, Monday’s halves cut in quarters.

The same count as Monday, the primes below 3,000,000, on one machine (JDK 25, three runs each), with four threads taking blocks of different sizes:

time
one thread, every number about 410 ms
four threads, one number at a time about 186 ms
four threads, blocks of 100 about 106 ms
four threads, blocks of 10,000 about 106 ms
four threads, a quarter each (750,000) about 141 ms
four threads, blocks of 1,500,000 about 256 ms

Why is one number at a time slower than blocks of 100? And why does a quarter each lose again?

Now three of those again: one thread, four threads one number at a time, and four threads in blocks of 100. This time they count only the primes below a smaller limit, 1,000,000 or 100,000. Small numbers are quicker to check, so each number is less work:

below one thread four, one at a time four, blocks of 100
3,000,000 about 408 ms about 194 ms about 106 ms
1,000,000 about 88 ms about 80 ms about 23 ms
100,000 about 3.6 ms about 9.4 ms about 1.4 ms

Below 100,000, one number at a time is slower than one thread. Why?

Every piece costs a trip to synchronized next(), and only one thread at a time gets through. One number at a time is 3,000,000 trips, and the threads queue at the door. Blocks of 100 are 30,000 trips, and the cost disappears into the work.

Big pieces cost almost no trips, but the work no longer evens out. A quarter each is Monday’s halves again: the thread with the top quarter finishes last while the others wait. Blocks of 1,500,000 are two pieces for four threads, so two of them do nothing.

The second table is the same trade from the other side. Below 100,000 a number takes less time to check than a trip to next() takes, so four threads queuing for numbers lose to one thread that never asks. Blocks of 100 win at every bound: one trip buys a hundred numbers’ work.

The size of a piece is the work’s granularity. Too fine, and asking costs more than working. Too coarse, and threads sit idle. In between, both costs are small: blocks of 100 ask 30,000 times, a couple of milliseconds in all, and the last block of 10,000 keeps one thread busy a millisecond or two after the others. That is why the two rows match. A size neither tiny nor huge is enough; there is no single right one.

2. Pieces of any size

Pairs. 2.1, then 2.2 to 2.4 if you are done.

2.1 Blocks

A new class beside Numbers, with the same three fields and one more, size: new Blocks(25, 10) hands out the numbers below 25 in blocks of 10.

// the first number of the next block nobody has taken, or -1 when there is none
public synchronized int next()

// the number after the last one in the block that starts at start
public int end(int start)

The constructor throws an IllegalArgumentException when size is 0 or less. new Blocks(limit, 1) is your Numbers again.

Your tests, in test/BlocksTest.java: new Blocks(25, 10) hands out 0, 10 and 20, then -1; end(20) is 25, not 30; and assertThrows for new Blocks(25, 0).

Done when the three tests are green.

2.2 BlockCounter, and the table (if you are done)

BlockCounter is NumberCounter for blocks: it counts the primes from a block’s start up to end(start), then asks again. Four of them on blocks of 10,000 print 216816. Time blocks of 1 and blocks of 100, below 3,000,000 and below 100,000, three times each, and compare with section 1’s tables. Run once untimed first: the first run also warms Java up, and below 100,000 that is most of the time.

2.3 A pile of anything (if you are done)

Pile<T>: a class that holds a List<T> and hands its items out one at a time with synchronized T take(), and null once they are gone. Then a Runnable that takes words from a shared Pile<String> and counts, in a field of its own, how many letters its words had.

Your test: three takers share a pile of "a", "bb", … up to forty letters, 1 + 2 + ... + 40 letters in all, and their counts add up to 820.

2.4 The longest chain (if you are done)

Start from a number; halve it if it is even, otherwise take three times it plus one; stop at 1. From 9 that takes 19 steps. Which number below 1,000,000 takes the most steps? Use long for the number as it climbs. Count in blocks: each counter keeps the best number it has seen and its steps, and main picks the best of the bests.

Your test: below 10, the longest is 9, at 19 steps.

When the section ends: commit and push.

3. Two transfers, both ways

Keyboards down. Write in the Journal first, then run it.

So far every operation touched one shared object. A transfer touches two, taking from one account and giving to another, so it holds both accounts’ locks until it is done. Both files are in your project’s src:

// an account: a name and a balance in whole dollars
public class Account {
    private final String name;
    private int balance;

    public Account(String name, int balance) {
        this.name = name;
        this.balance = balance;
    }

    public String getName() {
        return name;
    }

    public int getBalance() {
        return balance;
    }

    public void add(int amount) {
        balance = balance + amount;
    }
}
// two accounts, two threads, a dollar at a time in opposite directions
public class Transfers {
    // moves amount from one account to the other, holding both locks
    static void transfer(Account from, Account to, int amount) {
        synchronized (from) {
            synchronized (to) {
                from.add(-amount);
                to.add(amount);
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Account alice = new Account("alice", 1000);
        Account bob = new Account("bob", 1000);

        Thread one = new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                transfer(alice, bob, 1);
            }
        });
        Thread two = new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                transfer(bob, alice, 1);
            }
        });

        one.start();
        two.start();
        one.join();
        two.join();
        System.out.println(alice.getBalance() + " + " + bob.getBalance() + " = "
                + (alice.getBalance() + bob.getBalance()));
    }
}

synchronized (from) { ... } takes from’s lock for the code between its braces, and releases it at the closing brace. A synchronized method is the same thing around the whole method, with the lock of the object it is called on. A transfer needs two locks, one for each account, so it takes one and then the other.

What does it print?

Nothing, ever: it does not end. Stop it with the red square. Ten runs here, each stopped after ten seconds, printed nothing at all.

Thread one takes alice’s lock and then wants bob’s. Thread two, at the same moment, takes bob’s lock and then wants alice’s. Each holds the lock the other is waiting for, and neither releases its lock until it gets the other one. That is a deadlock: nothing is wrong with the numbers, and nothing moves.

4. Take the locks in order

Pairs. 4.1 and 4.2, then 4.3 and 4.4 if you are done.

4.1 One order for everybody

Change transfer so that every thread takes the two locks in the same order, whichever way the money goes: first the lock of the account whose name comes first in the alphabet, then the other. compareTo on the two names says which comes first.

Done when main prints 1000 + 1000 = 2000, every run.

4.2 A test that knows a deadlock

Your test, in test/TransfersTest.java, which is in the project with its imports: the same two threads, inside

assertTimeoutPreemptively(Duration.ofSeconds(5), () -> {
    // make, start and join the two threads here
});

and then assertEquals(2000, ...) on the two balances added up. assertTimeoutPreemptively runs the lambda and fails the test if it takes longer than five seconds.

Done when it is green with your ordered transfer, and red, “timed out after 5000 ms”, with the one from section 3.

4.3 Three in a ring (if you are done)

Three accounts and three threads at once: alice to bob, bob to carol, carol to alice, 100,000 dollars each. With section 3’s transfer, does it end? With yours? Write what you saw in a comment above the main, and why the alphabet rule still works with three.

4.4 To yourself (if you are done)

With your ordered transfer, what does transfer(alice, alice, 1) do? It takes alice’s lock and then asks for alice’s lock again. Predict in a comment, then run it.

When the section ends: commit and push.

5. One lock, or a lock each?

Keyboards down.

A hundred accounts, 4,000,000 one-dollar transfers between random pairs, the total checked at the end (JDK 25, three runs each, the middle one):

time
one thread, one lock for the whole bank about 37 ms
four threads, one lock for the whole bank about 290 ms
four threads, a lock for each account, taken in order about 75 ms

Why is one lock for the whole bank so slow with four threads? And why is one thread the fastest of the three?

With one lock for the bank, every transfer queues at the same door, whatever accounts it touches: four threads take turns, and pay for the queue on top. With a lock for each account, transfers between different people go on at the same time, and only transfers that share an account wait.

One thread wins because moving a dollar is almost no work: taking and releasing locks costs more than the move itself, so it is section 1 again, pieces too small to be worth sharing. In a real bank each transfer also checks the balance, writes its history and talks to a database, and then a lock for each account pays off.

6. Many accounts

Pairs. 6.1, then 6.2 and 6.3 if you are done.

6.1 The total stays the same

A main with a hundred accounts of 1,000 dollars each, named a000 to a099 so the alphabet orders them; four threads, each making 1,000,000 one-dollar transfers between two accounts picked with a Random (skip a pair that is the same account twice); start all four, join all four, print the total.

Your test: the same with 100,000 transfers per thread, and assertEquals(100_000, total).

Done when the test is green.

6.2 Against the clock (if you are done)

Time 6.1 with your ordered transfer, then with one lock for the whole bank: a static final Object BANK = new Object(); in Transfers, and synchronized (BANK) around the move instead of the two locks. Three runs each; compare with section 5’s table.

6.3 Order by number (if you are done)

Give every Account a number of its own, private final int id, taken in the constructor from a counter all accounts share: private static int made; and id = made++;. Then order the locks in transfer by id instead of by name.

Accounts may be made by several threads at once, and made++ is Monday’s count++. A static synchronized method takes the lock of the class itself, one lock for all accounts: put made++ in one.

Your test: four threads each make 1,000 accounts into a list of their own; after the joins, the 4,000 numbers are all different.

When the section ends: commit and push.