Threads

Problem

Three reports, one at a time

The program downloads three monthly reports from the server. Here the download is a pause: Thread.sleep(ms) stops the program for that many milliseconds. The pause can be interrupted from outside, and then it throws the checked InterruptedException, so download catches it.

Main.java

static void download(String file, int ms) {
    try {
        Thread.sleep(ms);
    } catch (InterruptedException e) {
        return;
    }
    System.out.println("Downloaded " + file);
}

public static void main(String[] args) {
    download("march.pdf", 600);
    download("april.pdf", 200);
    download("may.pdf", 400);
    System.out.println("Done");
}

Output

Downloaded march.pdf
Downloaded april.pdf
Downloaded may.pdf
Done

The pauses are 0.6, 0.2 and 0.4 seconds, 1.2 seconds in total. The whole time, the program only waits for the network. If there were a "Cancel" button, it would not respond. And the three reports do not depend on each other, so they could easily be downloaded at the same time.

The idea

Process and thread

When you start the program, the operating system gives it a process: its own memory, its own open files. Inside the process, one or more threads run. A thread is a sequence of commands that run one after another. So far, each of your programs had one thread: the one that runs main.

The threads in one process share their memory: they see the same objects. That makes them handy (they can easily pass data to each other) and dangerous (they can mess each other up, as you will see in a moment).

• Parallel means really at the same time, on different cores of the processor.
• Concurrent means on one core, taking turns so fast that it looks like the same time.

For the programmer the difference rarely matters: in both cases you do not know which thread will go on when.

More precisely, if you are curious

• The Chrome browser starts a separate process for each tab. That is why one frozen site does not stop the others, and also why the browser uses a lot of memory.
• Every program that does several things at once uses threads: a game plays the sound in one thread and runs the logic in another; a web server serves each client in its own thread.
• The price: each thread has its own stack, and the memory for it is set aside separately. Thousands of threads cost a lot. That is why real programs use a thread pool (the last idea in the lesson).

See it

The first thread

The Thread class is a thread. You pass its constructor what to do: an object of the Runnable interface, which has one method, run(). The shortest way is with a lambda:

Thread worker = new Thread(() -> download("april.pdf", 200));
worker.start();
System.out.println("main does not wait");
worker.join();
System.out.println("The report is downloaded");

Output

main does not wait
Downloaded april.pdf
The report is downloaded

• start() starts the new thread and returns right away. main goes on without waiting, so "main does not wait" is printed first.
• join() makes main wait for the thread to finish.

download is the method from the first card. It is a good thing that it catches InterruptedException itself: run() in Runnable has no throws, so the code in the thread cannot let the checked exception out. join() throws it too, so from here on main is public static void main(String[] args) throws InterruptedException.

More precisely, if you are curious

The lambda is the shortest way, but not the only one. In older code you will come across the other three:

class ReportThread extends Thread {
    @Override
    public void run() {
        System.out.println("1. a subclass of Thread");
    }
}

class ReportJob implements Runnable {
    @Override
    public void run() {
        System.out.println("2. a class that implements Runnable");
    }
}

public static void main(String[] args) throws InterruptedException {
    Thread a = new ReportThread();
    Thread b = new Thread(new ReportJob());
    Thread c = new Thread(new Runnable() {
        @Override
        public void run() {
            System.out.println("3. an anonymous class");
        }
    });
    Thread d = new Thread(() -> System.out.println("4. a lambda"));
    for (Thread t : new Thread[] { a, b, c, d }) {
        t.start();
        t.join();
    }
}

Output

1. a subclass of Thread
2. a class that implements Runnable
3. an anonymous class
4. a lambda

A subclass of Thread is the oldest way. It is more flexible to keep the task (Runnable) apart from the thread: that way the same task can be given to a thread pool, and your class stays free to extend another class.

See it

Three at once

Now the three reports, each in its own thread:

long start = System.currentTimeMillis();
Thread march = new Thread(() -> download("march.pdf", 600));
Thread april = new Thread(() -> download("april.pdf", 200));
Thread may = new Thread(() -> download("may.pdf", 400));
march.start();
april.start();
may.start();
march.join();
april.join();
may.join();
long ms = System.currentTimeMillis() - start;
System.out.println("Done in under a second: " + (ms < 1000));

Output

Downloaded april.pdf
Downloaded may.pdf
Downloaded march.pdf
Done in under a second: true

The threads start in the order March, April, May, but they finish in the order of the pauses: April (0.2 s), May (0.4 s), March (0.6 s). The whole wait is as long as the longest one, 0.6 seconds instead of 1.2.

The operating system decides the order in which the threads reach println. Here the pauses are different enough, so the order is the same. If they were equal, it could be different on every run.

Try it

start or run

What will the program print? (the second argument of Thread is the name of the thread)

Thread t = new Thread(() -> System.out.println("Running in: " + Thread.currentThread().getName()), "downloader");
t.run();
t.start();
t.join();

Answer

Running in: downloader
Running in: main

Running in: main
Running in: downloader

Running in: downloader
Running in: downloader

Check

The idea

The life of a thread

A thread goes through several states, and getState() tells you which one it is in:

Thread t = new Thread(() -> download("may.pdf", 500));
System.out.println(t.getState());
t.start();
Thread.sleep(100);
System.out.println(t.getState());
t.join();
System.out.println(t.getState());

Output

NEW
TIMED_WAITING
Downloaded may.pdf
TERMINATED

State	When
NEW	created, not started with start() yet
RUNNABLE	running or ready to run
BLOCKED, WAITING, TIMED_WAITING	waiting: for a lock, for another thread (join), or for a set time (sleep)
TERMINATED	run() has finished

A thread can be started only once. A second start() on the same thread throws IllegalThreadStateException.

More precisely, if you are curious

More Thread methods:

• interrupt() asks the thread to stop. If it is sleeping or waiting, sleep/join throws InterruptedException. That is why we catch it in download.
• getName(), threadId() (earlier getId()): the name and the number of the thread. Thread.currentThread() gives you the thread the code is running in.
• Thread.yield() hints that the thread can give the processor to another one. You rarely need it.

Problem

The lost visits

The site counts its visits. Two threads serve visitors, and each one calls increment() 100,000 times:

Main.java

class Counter {
    private int count = 0;

    public void increment() {
        count++;
    }

    public int getCount() {
        return count;
    }
}

public static void main(String[] args) throws InterruptedException {
    Counter visits = new Counter();
    Runnable work = () -> {
        for (int i = 0; i < 100_000; i++) {
            visits.increment();
        }
    };
    Thread first = new Thread(work);
    Thread second = new Thread(work);
    first.start();
    second.start();
    first.join();
    second.join();
    System.out.println("Visits: " + visits.getCount());
}

You expect 200,000. Five runs:

Output (different every time)

Visits: 150329
Visits: 138149
Visits: 168862
Visits: 165672
Visits: 157704

Less every time, and different every time. The reason is that count++ is not one step, but three:

int value = count;   // 1. read
value = value + 1;   // 2. add 1
count = value;       // 3. write

class Counter {
    private int count = 5;

    public void increment() {
        count++;   // read, add 1, write
    }

    public synchronized void safeIncrement() {
        count++;
    }

    public synchronized int getCount() {
        return count;
    }
}

Step by step, in words

1. count is 5. Threads A and B call increment() at the same time.
2. A reads count: 5.
3. B reads count before A has written: also 5.
4. A adds 1 in its own copy and writes 6.
5. B writes 6 too. Two calls, and count is 6, not 7: one of the additions is lost.
6. Once more, now with synchronized: A takes the lock, reads 5 and writes 6.
7. B reaches the method and waits until A releases the lock.
8. B takes the lock, reads 6 and writes 7: nothing is lost.

When both threads read the same value before either of them has written, one of the additions is lost. This is called a race condition. Whether it happens depends on when the operating system switches the threads, so the result is different on every run.

The idea

synchronized: one at a time

The solution is for only one thread at a time to do these three steps. The word synchronized in front of the method does exactly that:

class Counter {
    private int count = 0;

    public synchronized void increment() {
        count++;
    }

    public synchronized int getCount() {
        return count;
    }
}

Output

Visits: 200000

Every object has a lock. The thread takes it before it enters a synchronized method and releases it when it leaves. The other thread that wants the same object waits. Now the result is 200,000 on every run. getCount() is synchronized too: that way the thread that reads sees the last value written.

If you need to lock only part of a method, there is a synchronized block with an object for the lock. For a counter there is also a ready-made class: AtomicInteger (from java.util.concurrent.atomic), whose incrementAndGet() does the three steps at once, without a lock:

class Counter {
    private int count = 0;
    private final Object lock = new Object();

    public void increment() {
        synchronized (lock) {
            count++;
        }
    }

    public int getCount() {
        synchronized (lock) {
            return count;
        }
    }
}

class Counter {
    private final AtomicInteger count = new AtomicInteger();

    public void increment() {
        count.incrementAndGet();
    }

    public int getCount() {
        return count.get();
    }
}

Output

Visits: 200000

More precisely, if you are curious

• wait() and notifyAll(): a thread in a synchronized method can release the lock and go to sleep until another thread wakes it up. That way the kitchen waits for an order, and the checkout waits for the kitchen to take the previous one (the "producer and consumer" problem):

class OrderBox {
    private String order;

    public synchronized void put(String newOrder) throws InterruptedException {
        while (order != null) {
            wait();
        }
        order = newOrder;
        notifyAll();
    }

    public synchronized String take() throws InterruptedException {
        while (order == null) {
            wait();
        }
        String result = order;
        order = null;
        notifyAll();
        return result;
    }
}

public static void main(String[] args) throws InterruptedException {
    OrderBox box = new OrderBox();
    Thread kitchen = new Thread(() -> {
        try {
            for (int i = 0; i < 3; i++) {
                System.out.println("The kitchen took " + box.take());
            }
        } catch (InterruptedException e) {
            return;
        }
    });
    kitchen.start();
    box.put("pizza");
    box.put("salad");
    box.put("soup");
    kitchen.join();
}

Output

The kitchen took pizza
The kitchen took salad
The kitchen took soup

wait() is in a while, not in an if: the thread can wake up for no reason, so it checks the condition again.

• Deadlock: two threads wait for each other forever. The office holds the printer and waits for the scanner, and the front desk holds the scanner and waits for the printer (pause is sleep with the exception caught):

Object printer = new Object();
Object scanner = new Object();

Thread office = new Thread(() -> {
    synchronized (printer) {
        pause(100);
        synchronized (scanner) { System.out.println("The office is copying"); }
    }
});
Thread reception = new Thread(() -> {
    synchronized (scanner) {
        pause(100);
        synchronized (printer) { System.out.println("The front desk is copying"); }
    }
});

The program hangs and never prints anything. The way to avoid it is for all the threads to take the locks in the same order.

• Priorities: setPriority from 1 to 10 hints how important the thread is. The operating system may ignore it, so do not rely on priorities for the program to be correct:

Thread report = new Thread(() -> download("annual.pdf", 100));
report.setPriority(Thread.MIN_PRIORITY);   // 1; NORM_PRIORITY is 5, MAX_PRIORITY is 10
System.out.println(report.getName() + ", priority " + report.getPriority());

Try it

Two ATMs

Two people each withdraw €80 from one account with €100 at the same moment. Sometimes both of them get the money, and the balance becomes -€60. Which line is the bug on?

Pick the line with the bug.

1class Account {2 private int balance = 100;34 public void withdraw(int amount) {5 if (balance >= amount) {6 balance -= amount;7 }8 }910 public int getBalance() {11 return balance;12 }13}

Check

The idea

Thread pool and Future

Making a thread for every task is expensive, and with a thousand tasks it is dangerous too. A thread pool is a few threads that take tasks from a queue. In Java it is ExecutorService (from java.util.concurrent):

static int sizeOf(String file, int ms) {
    try {
        Thread.sleep(ms);
    } catch (InterruptedException e) {
        return -1;
    }
    return file.length() * 100;
}

String[] files = { "march.pdf", "april.pdf", "may.pdf", "june.pdf" };
ExecutorService pool = Executors.newFixedThreadPool(2);
List<Future<Integer>> sizes = new ArrayList<>();
for (String file : files) {
    sizes.add(pool.submit(() -> sizeOf(file, 300)));
}
for (int i = 0; i < files.length; i++) {
    System.out.println(files[i] + ": " + sizes.get(i).get() + " KB");
}
pool.shutdown();

Output

march.pdf: 900 KB
april.pdf: 900 KB
may.pdf: 700 KB
june.pdf: 800 KB

• Executors.newFixedThreadPool(2) makes a pool of 2 threads. The four tasks take turns in them.
• submit takes a task that returns a result and right away gives you a Future: a promise that the result will come.
• get() waits for the task to finish and returns the result.
• shutdown() tells the pool not to accept new tasks and to stop the threads when they are done. Without it the program does not end: the threads of the pool wait for more work.

main here has throws Exception, because get() also throws ExecutionException if the task threw an exception.

More precisely, if you are curious

If the task does not return anything, there is execute. Then you wait for all of them with awaitTermination after shutdown:

ExecutorService pool = Executors.newFixedThreadPool(2);
for (int i = 1; i <= 5; i++) {
    String file = "report-" + i + ".pdf";
    pool.execute(() -> download(file, 100));
}
pool.shutdown();
pool.awaitTermination(1, TimeUnit.MINUTES);
System.out.println("All done.");

Output of one run

Downloaded report-2.pdf
Downloaded report-1.pdf
Downloaded report-3.pdf
Downloaded report-4.pdf
Downloaded report-5.pdf
All done.

The first two reports run at the same time, so their order changes from run to run. In old examples you will see while (!executor.isTerminated()) { }. That waits too, but it spins the processor for nothing. awaitTermination sleeps until the pool is done.

Try it

Which result comes first?

"archive.zip" takes 0.6 s to download, and "note.txt" takes 0.1 s. What will the program print?

ExecutorService pool = Executors.newFixedThreadPool(2);
Future<Integer> big = pool.submit(() -> sizeOf("archive.zip", 600));
Future<Integer> small = pool.submit(() -> sizeOf("note.txt", 100));
System.out.println("Big: " + big.get());
System.out.println("Small: " + small.get());
pool.shutdown();

Answer

Big: 1100
Small: 800

Small: 800
Big: 1100

It depends on which task finishes first

Check

Exercise

Programs with threads

Solve these in your editor. main can have throws InterruptedException (or throws Exception for Future.get()).

1. Parallel sum. The array sales has 1,000,000 sales, sales[i] = i % 100. Split it into 4 equal parts and sum each one in its own thread. Each thread writes to its own place in the array long[] partial, so you do not need synchronization. Wait for them with join and add up the parts:

Output

Parts: [12375000, 12375000, 12375000, 12375000]
Total: 49500000

2. Downloading with a pool. Download six reports (march.pdf, april.pdf, may.pdf, june.pdf, july.pdf, august.pdf) with a pool of 3 threads. Use sizeOf(file, 300) from the pool card. Print the sizes in the order of the files, the total, and whether it all took under 1.5 seconds (one after another would be 1.8 s):

Output

march.pdf: 900 KB
april.pdf: 900 KB
may.pdf: 700 KB
june.pdf: 800 KB
july.pdf: 800 KB
august.pdf: 1000 KB
Total: 5100 KB
Under 1.5 seconds: true

3. A counter without losses. Four threads, each with 50,000 visits, increase a shared counter. Write the counter so that the result is always 200,000. First try it without synchronization and see how much is lost, then fix it once with synchronized and once with AtomicInteger.

Output

Visits: 200000

More tasks

• A test for the counter. Write a JUnit test that starts 8 threads with 10,000 increases each and checks for 80,000 with assertEquals. Run it against the unsynchronized counter a few times. A test that fails only sometimes is the typical sign of a race condition.
• The deadlock. Run the example with the printer and the scanner from "More precisely" and watch it hang. Fix it so that both threads take the printer first.

Test

Check yourself

1. What is the difference between t.start() and t.run()?

start() runs run() in a new thread, and run() runs it right away in the current onerun() starts a new thread, and start() does notThere is no difference

2. Why does main call join() before it prints the result?

To wait for the thread to finishTo start the threadTo stop the thread right away

3. Two threads each do count++ 100,000 times on a shared field without synchronization. What will count be at the end?

Always 200,000Often less than 200,000, and different on every runAlways 100,000

4. What does a synchronized method guarantee?

That the method is fasterThat only one thread at a time runs the synchronized methods of this objectThat the threads run in the order they were started

5. You submit three tasks to a pool and keep a Future for each one. What does future.get() do?

It waits for the task to finish and returns its resultIt runs the task againIt returns the result right away, even if it is not ready

Check

Start the lesson over