Class 19 — Monday, November 2
Quiz 8 first. Then what a lock really protects, which lock a method takes, and a dinner where nobody eats.
- Check, then act — predict first
- One lock for the rule
- Which lock? — keyboards down
- One total, two tallies
- When do threads stop for ever? — keyboards down
- Five philosophers
Today’s work goes in your copy of cmsc-230-threads, from Wednesday. If you have none, make one as Wednesday’s page says: on https://github.com/cu-cs-labs/cmsc-230-threads, Use this template, Private, then clone it in IntelliJ.
1. Check, then act
Keyboards down. Write in the Journal first, then run it.
In your Account, mark getBalance and add synchronized: each now runs under the account’s lock. Then a new file in src:
// 100,000 accounts of $100 each; two threads each take $80 from every one that has it
public class Withdrawals {
public static void main(String[] args) throws InterruptedException {
Account[] accounts = new Account[100_000];
for (int i = 0; i < accounts.length; i++) {
accounts[i] = new Account("a" + i, 100);
}
Runnable work = () -> {
for (Account account : accounts) {
if (account.getBalance() >= 80) {
account.add(-80);
}
}
};
Thread first = new Thread(work);
Thread second = new Thread(work);
first.start();
second.start();
first.join();
second.join();
int below = 0;
for (Account account : accounts) {
if (account.getBalance() < 0) {
below++;
}
}
System.out.println(below + " accounts below zero");
}
}Each account can pay $80 once, not twice.
Will any account end below zero? Why?
Thousands: six runs here printed 3425, 1603, 3700, 2824, 1609 and 3688.
Each method holds the lock only while it runs. Between getBalance returning and add starting, the lock is free, and the other thread can check the same account, see $100 too, and take $80 as well. A lock protects what is inside it. The rule “enough money, then take it” is two calls, so the lock has to cover both.
2. One lock for the rule
Pairs. 2.1, then 2.2 and 2.3 if you are done.
2.1 Check and act under one lock
Change work so that the check and the add happen while the thread holds the account’s lock, with one synchronized block around both.
Your test, in test/WithdrawalsTest.java: the same 100,000 accounts of $100 and two threads, each trying to take $80 from every one; afterwards no account is below zero.
Done when main prints 0 accounts below zero every run, and your test is green, and red with the block taken out.
2.2 The rule inside Account (if you are done)
Give Account a method synchronized boolean takeIfEnough(int amount): it takes the amount and returns true if the balance is enough, and otherwise changes nothing and returns false. Use it in work instead of the block. Why does one synchronized method fix what two did not? Write it in a comment above the method.
Your test: an account of $100; takeIfEnough(80) is true, a second takeIfEnough(80) is false, and the balance is 20.
2.3 How many paid (if you are done)
Count, in main, how many withdrawals went through, with takeIfEnough’s answer. Each thread counts its own, in a field of its own, as last Monday’s NumberCounter did, and main adds the two after the joins: nothing shared, so nothing to lock. With 100,000 accounts it must be exactly 100,000: each account pays once. Run it without the lock (section 1’s work) and compare.
When the section ends: commit and push.
3. Which lock?
Keyboards down.
Every lock belongs to an object. Which object’s lock does each of these take?
synchronized void add(int amount) { ... } // in class Account
static synchronized void reset() { ... } // in class Account
synchronized (account) { ... } // anywhere
synchronized (Account.class) { ... } // anywhereTwo threads run two of these at the same time. Which pairs can run together, and which must take turns?
- A
synchronizedmethod takes the lock of the object it is called on:alice.add(5)takes alice’s lock. - A
static synchronizedmethod has no object, so it takes the lock of the class itself,Account.class: one lock for the whole class. - A
synchronizedblock takes the lock of the object it names.
So alice.add(5) and bob.add(5) run together: two objects, two locks. alice.add(5) and synchronized (alice) { ... } take turns: the same lock. reset() and synchronized (Account.class) { ... } take turns too. And alice.add(5) and reset() run together: alice’s lock is not the class’s.
4. One total, two tallies
Pairs. 4.1, then 4.2 and 4.3 if you are done.
4.1 Two locks for one total
Two new files in src:
// one total for the whole program, added to through any Tally
class Tally {
static int total;
synchronized void add() {
total++;
}
}// two threads, each with a Tally of its own, adding to the one total
public class Tallies {
public static void main(String[] args) throws InterruptedException {
Tally mine = new Tally();
Tally yours = new Tally();
Thread first = new Thread(() -> {
for (int i = 0; i < 100_000; i++) {
mine.add();
}
});
Thread second = new Thread(() -> {
for (int i = 0; i < 100_000; i++) {
yours.add();
}
});
first.start();
second.start();
first.join();
second.join();
System.out.println(Tally.total);
}
}Run it three times. add is synchronized, yet the total comes out short. Write in a comment above add which locks the two threads take, then make them take the same one.
Your test, in test/TallyTest.java: four threads, each with its own Tally, each adding 25,000; the total is 100,000. Set Tally.total = 0 first, since it is shared by every test.
Done when main prints 200000 every run and your test is green.
4.2 The other way (if you are done)
Fix it a second way: keep add an instance method, and use a block that names the one object both threads share. Which object is that?
4.3 One more tally (if you are done)
Add static synchronized void reset() to Tally, setting total to 0. Could a reset in one thread and an add in another ever interleave with your fix from 4.1? With your fix from 4.2? Answer in a comment.
When the section ends: commit and push.
5. When do threads stop for ever?
Keyboards down.
Wednesday’s transfer, with its lines numbered:
static void transfer(Account from, Account to, int amount) {
synchronized (from) {
synchronized (to) {
from.add(-amount);
to.add(amount);
}
}
}Thread 1 runs transfer(alice, bob, 1) and thread 2 runs transfer(bob, alice, 1). One way it can go, time running down:
thread 1: transfer(alice, bob) thread 2: transfer(bob, alice)
---------------------------------- ----------------------------------
1. line 2: takes alice's lock ok
2. line 2: takes bob's lock ok
3. line 3: asks for bob's lock
bob's is held: waits
4. line 3: asks for alice's lock
alice's is held: waits
5. waits, holding alice's waits, holding bob's
... for ever ... for ever
What does each thread hold while it waits, and what is it waiting for? Now take the locks in name order, alice’s always first: draw the same timeline. Why can it not end the same way?
Each holds the lock the other is waiting for, and neither releases its lock until it gets the other one: a circle of waiting, so nobody moves.
With alice’s lock always first (the same lines, taking first and second in place of from and to), both threads ask for alice’s at line 2:
thread 1: transfer(alice, bob) thread 2: transfer(bob, alice)
---------------------------------- ----------------------------------
1. line 2: takes alice's lock ok
2. line 2: asks for alice's lock
alice's is held: waits,
holding nothing
3. line 3: takes bob's lock ok
4. lines 4-5: moves the dollar
5. lines 6-7: releases both
6. line 2: takes alice's lock ok
7. line 3: takes bob's lock ok ...
Whoever gets the first lock gets the second too, because the one left waiting holds nothing anybody needs. The same holds for any number of locks taken in one order: a thread only ever waits for a lock later in the order than every lock it holds, so the waiting can never come round in a circle.
6. Five philosophers
Pairs. 6.1, then 6.2 and 6.3 if you are done.
Five philosophers sit round a table with a fork between each two. To eat, a philosopher takes the fork on the left, then the one on the right. Two new files in src:
// a fork on the table, numbered 0 to 4
class Fork {
final int number;
Fork(int number) {
this.number = number;
}
}// five philosophers, each eating 100,000 times, left fork first, then right
public class Dinner {
static int[] meals = new int[5];
static void eat(int who, Fork left, Fork right) {
synchronized (left) {
synchronized (right) {
meals[who]++;
}
}
}
public static void main(String[] args) throws InterruptedException {
Fork[] forks = new Fork[5];
for (int i = 0; i < 5; i++) {
forks[i] = new Fork(i);
}
Thread[] philosophers = new Thread[5];
for (int i = 0; i < 5; i++) {
int who = i;
Fork left = forks[i];
Fork right = forks[(i + 1) % 5];
philosophers[i] = new Thread(() -> {
for (int meal = 0; meal < 100_000; meal++) {
eat(who, left, right);
}
});
}
for (Thread p : philosophers) {
p.start();
}
for (Thread p : philosophers) {
p.join();
}
System.out.println(java.util.Arrays.toString(meals));
}
}6.1 Dinner, served
Run it, and stop it with the red square when it stops moving. On paper, draw a timeline for it like section 5’s, one column for each philosopher, that ends with every one of them waiting. Then change eat so that every philosopher takes the lower-numbered of its two forks first.
Your test, in test/DinnerTest.java: run the dinner inside assertTimeoutPreemptively(Duration.ofSeconds(5), () -> ...), then check that every philosopher ate 100,000 times.
Done when main prints five 100000s every run and your test is green.
6.2 One left-handed philosopher (if you are done)
Put eat back as it was, and instead make one philosopher take the right fork first. Does the dinner finish? Explain with the picture, in a comment.
6.3 Who gets to eat (if you are done)
Give each philosopher 1,000,000 meals and time the dinner with your 6.1 fix, System.nanoTime() before and after, three runs. Then make each philosopher stop after one second instead of a number of meals, and print how many times each ate. Is it fair?
When the section ends: commit and push.