Programmierkonzepte Modul - Fortgeschrittene · In Java, threads are technically user level, since you work with the java.lang.Thread API (and the JVM) rather than directly with the

Modul - FortgeschritteneProgrammierkonzepte

Bachelor Informatik

10 - Parallel Processing pt. 1

Prof. Dr. Marcel Tilly

Fakultät für Informatik, Cloud Computing

© Technische Hochschule Rosenheim

Plan Plan

8:00 -- Introduction into Robocode (R0.03)09:45 -- Start Coding and Testing (S1.31)11:00 -- Tournament starts

16:00 -- last round!

16:30 -- And the winner is? Celebration

17:00 -- End of show

Before we start...

The plan for the 'X-Mas Lecture'Robocode Tournament, Gluehwein and Pizza!

2 / 41© Technische Hochschule Rosenheim

Today in 'Übung 3'Linked List and Maps revisited


Agenda for todayWhat is on the menu for today?

Parallel ProcessingThreadsSynchronizationCommunication


Parallel ProcessingProcesses

Up to now, the programs we wrote were basically a single process in whichinstructions were executed one-by-one, in the order they were written down. Thefollowing code

class MyProgram { String name; MyProgram(String name) { this.name = name; System.out.println("Created MyProgram: " + name); } void printNum(int n) { System.out.println(name + ": " + n); } public static void main(String[] args) { MyProgram mp = new MyProgram("Test"); for (int i = 0; i < 3; i++) mp.printNum(i); }}



Expressed as a sequence diagram, with methods as columns:

OS

OS

main

main

MyProgram

MyProgram

printNum

printNum

println

println

java MyProgram

mp = new MyProgram("Test") "Created MyProgram Test"

mp.printNum(0)

"Test: 0"

mp.printNum(1)

"Test: 1"

mp.printNum(2)

"Test: 2"

end of main()



This is also the behavior you see when using the debugger and going through yourprogram step-by-step, using the step-into action.

A process has a self-contained (and isolated) environment.

A Process has a complete and private set of run-time resources; in particular, eachprocess has its own memory space.


ThreadsConsider this simple class that models a bean counter. It receives a name and allocatesa large array of numbers; a call to .run() sorts the data.

class BeanCounter {

private final String name; private final double[] data;

BeanCounter(String name, int n) { this.name = name; this.data = new double [n]; }

public void run() { System.out.println(name + " is starting..."); Arrays.sort(data); System.out.println(name + " is done!"); }}


ThreadsAnd here is an example program, allocating two bean counters, have them work, andthen print a good bye message:

public static void main(String... args) { BeanCounter b1 = new BeanCounter("Bureaucrat 1", 10000); BeanCounter b2 = new BeanCounter("Bureaucrat 2", 1000);

b1.run(); b2.run();

System.out.println("main() done!");}

What is the expected result?


Bean CountersOS

OS

main

main

b1.run

b1.run

b2.run

b2.run

java BeanCounter

b1 = new BeanCounter(...)


b1.run() Bureaucrat 1 is starting...Bureaucrat 1 is done!

b2.run() Bureaucrat 2 is starting...Bureaucrat 2 is done!

"main() done!"


Threaded BeanCounters

To make the bean counters work in parallel, use the Thread class.It takes an instance of Runnable of which it will execute the .run() method in aseparate thread, once the thread's .start() method is called.First, modify the BeanCounter to implement the Runnable interface

public class BeanCounter implements Runnable { // ...}


https://docs.oracle.com/javase/9/docs/api/java/lang/Thread.html

Thread ExecutionPass instances to the Thread class constructor:

public static void main(String[] args) { BeanCounter b1 = new BeanCounter("Bureaucrat 1", 10000); BeanCounter b2 = new BeanCounter("Bureaucrat 2", 1000);

new Thread(b1).start(); new Thread(b2).start();

System.out.println("main() done!");}

What do we expect now?


Threaded BeanCounters

OS

OS

main

main

b1

b1

b2

b2

java BeanCounter



new Thread(b1).start() Bureaucrat 1 is starting...

new Thread(b2).start() Bureaucrat 2 is starting...

"main() done!"

Arrays.sort(...)

"Bureaucrat 1 is done!"

Arrays.sort(...)

"Bureaucrat 2 is done!"


Thread OutputSo, what is the last line of the output?

a) Bureaucrat 2 is done!

b) Bureaucrat 1 is done!

c) main() done!

Vote on PINGO: https://pingo.coactum.de/007034

ID: 007034


https://pingo.coactum.de/007034

Thread OutputThis will likely produce output similar to this:

Bureaucrat 1 is starting...main() done!Bureaucrat 2 is starting...Bureaucrat 1 is done!Bureaucrat 2 is done!

The three methods (main, b1.run and b2.run) were executed in parallel.If you run the code on your machine, you may get a different order of the output;this is because only one thread can write to System.out at a time, and they mayget to that point at different times depending von your number of CPUs etc.


ThreadsInstead of providing a Runnable to the Thread, you can also extend the Threadclass and overwrite the run method.

Threads are sometimes called lightweight processes; they exist inside processesand have shared resources.

This allows communication but at the same time introduces risks.

From your operating systems class, you may already know that there are user andsystem (or kernel) level threads.

In Java, threads are technically user level, since you work with thejava.lang.Thread API (and the JVM) rather than directly with the operatingsystem.For the JVM, however, threads are typically implemented as kernel level threads,to get the best performance; the VM translates the threading instructions intooperations native to your operating system.


Threading: ExamplesMulti-threaded programming is ubiquitous in modern applications:

browser: loading multiple resources at a time using concurrent connections

rendering multiple animations on a page/screen

handling user interactions such as clicks or swipes

sorting data using divide-and-conquer

concurrent network, database and device connections

ability to control (pause, abort) certain long-lasting processes


Synchronization

JoiningThe example above has one major �aw: the main() routine �nishes before the actualwork is done. Transferred to the real world, this would mean that you delegate thework to your team, but immediately report that all work is done while your team is stillworking hard!


Synchronization

JoiningOne (terrible) way to �x this is to actively wait until a thread is done by checking its.isAlive() method.

public class Joining implements Runnable { @Override public void run() { System.out.println("Sleeping for 15 seconds"); Thread.sleep(15000); } public static void main(String[] args) { Thread t = new Thread(new Joining()); t.start(); while (t.isAlive()) ; // do nothing, but really fast... System.out.println("Done!"); }}


Synchronization

JoiningWhile this works, this is a terrible idea: the check for .isAlive() is really fast, thusthe thread executing main will run "hot" without doing anything useful.

A much better way to solve this is to use the .join() method of Thread:

public static void main(String[] args) throws InterruptedException { Thread t = new Thread(new Joining()); t.start();

t.join(); // block/sleep until t is done System.out.println("Done!");}


Synchronization

JoiningNote that join() (and sleep()) may throw an InterruptedExceptionwhich needs to be appropriately handled.

You can use join() whereever you have access to the reference of a thread.

For example, you could give one thread the reference to another thread, to have itstart after the other thread �nished.


Synchronisation

Shared ResourcesImagine you have a number of bean counters in your team, and they should all add tothe same counter.

This is possible, since threads share the memory:

class Counter { private int c = 0; int getCount() { return c; } void increment() { c = c + 1; }}


Synchronisation

Shared Resources

public class TeamBeanCounter implements Runnable { Counter c; TeamBeanCounter(Counter c) { this.c = c; }

@Override public void run() { for (int i = 0; i < 100000; i++) { c.increment(); } System.out.println("Total beans: " + c.getCount()); }}


Synchronisation

Shared ResourcesSo each TeamBeanCounter receives a reference to the shared counter, and in therun() method, they each increment the counter by one; once they did this 100000times, they print the total count.

Thus, this program:

public static void main(String[] args) { Counter c = new Counter();

new Thread(new TeamBeanCounter(c)).start(); new Thread(new TeamBeanCounter(c)).start(); new Thread(new TeamBeanCounter(c)).start(); new Thread(new TeamBeanCounter(c)).start();}

What is the total value at the end?


Pingo again!What is the total value at the end?

A) < 40.000

B) = 40.000

C) > 40.000

Vote on PINGO: https://pingo.coactum.de/165980

ID: 165980


https://pingo.coactum.de/165980

SynchronisationSo what happened?

All bean counters share the same Counter instance; however, since each threadexecutes its own methods, we need to look at the increment() method carefully:

void increment() { c = c + 1;}

In fact, to execute this assignment, the JVM needs to �rst load the value of c, then add1, and then assign it back to c.

void increment() { int tmp = c; ++tmp; c = tmp;}


Shared Resources:Inconsistent State!That means, two threads can be at different steps of this method, but share thememory. Note that the stack variables are per-thread, whereas the heap variables (thecounter instance) are shared (see Java VM Speci�cations).

# Thread 1 Thread 2 result

1 tmp1 = c tmp1 = 0

2 tmp2 = c tmp2 = 0

3 ++tmp1 tmp1 = 1

4 ++tmp2 tmp2 = 1

5 c = tmp1 c = 1

6 c = tmp2 c = 1 !


https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-2.html#jvms-2.5.2

SynchronizationTo �x this, we need to tell the JVM, which code segment may only entered by onethread at a time;

This is also called locking.

This is done using the keyword synchronized, either as a modi�er to themethod or as a block instruction.

synchronized void increment() { c = c + 1;}

void increment() { synchronized (this) { c = c + 1; }}


SynchronisationEach thread trying to enter the critical section �rst has to acquire the lock (here:this), or wait for it to become available. The thread then executes all statementsinside the synchronized section, before it releases the lock again.

Note that for the block instruction, the argument to synchronized de�nes the lockobject; this could be any object, and is implicitly this when using synchronized as amethod modi�er. Using either method, the output of the TeamBeanCounter programis as expected:

Total beans: 400000


SynchronisationSynchronized Methods vs. Lock Objects

The bene�t of synchronized methods is, that it is an easy �x to existing code;the downside is that the whole method is locked.

The bene�t of synchronized (lock) { ... } is that the locking can beapplied to very few (but critical) operations; note that in the above example, asynchronized (this) spanning the whole method body is effectively thesame as making the method synchronized.

While you can use any object as lock, you must use the the same reference in allrelevant places.


CommunicationDeadlock

The synchronized keyword allows us to safely change values which will be read byother threads. However sometimes this basic mechanism is not enough. Consider thefollowing scenario:

threadA

lock2 threadB

lock1

wantstaken by

wants

taken by

This is a classic deadlock, similar to a Mexican stand-off from the movies: threadAwants to acquire lock2, which is currently taken by threadB; threadB wantslock1, which is currently taken by threadA. As a result, nothing happens, thesituation is stuck.


CommunicationWait-Notify

When inside a synchronized section, you can use the methods wait(), notify()and notifyAll() of the lock to wait in a thread until noti�ed by some other thread.You can use this mechanism to have workers only be active when they should be:

threadA

threadA

lock

lock

threadB

threadB

doSomething()

lock.wait()

doOtherThings()

lock.notify()

lock.wait()

doSomething()

lock.notify()

dOtherThings()


CommunicationWait-Notify

These methods are parts of the Java threading API and are de�ned final inObject

notify() will wake up one (random) other thread;

notifyAll() will wake up all other waiting threads.


CommunicationThe Consumer-Producer Problem

The classic example to demonstrate how to use wait() and notify() incombination is the consumer-producer-problem: producers store data in a (ring)buffer and consumers take data out of the buffer. A typical example is a streamingmedia player: the producer is the decoder that reads encoded data and stores decoded(raw) media in the buffer; the media device (e.g. video player) is the consumer,removing ready-to-render data from the buffer.



The buffer provides the basic operations put(T t) and T get(), which should eachblock if full (put) or empty (get).

class Buffer<T> { List<T> buffer = new LinkedList<>(); final int max = 10;

synchronized void put(T obj) throws InterruptedException { // wait until buffer not full while (buffer.size() == 10) wait();

buffer.add(obj);

// wake up other threads waiting for buffer to change notifyAll(); }



... continued

synchronized T get() throws InterruptedException { // wait until there's something in the buffer while (buffer.size() == 0) wait();

T obj = buffer.remove(0);

// wake up other threads waiting for buffer to change notifyAll(); return obj; }}



Now you could have several threads of producers and consumers which call the getand put methods. If somebody calls get on an empty buffer, it will repeatedly waituntil there is something in the buffer. If somebody calls put on a full buffer, it willrepeatedly wait until there is space available.

This works because only one thread at a time is allowed within the critical section; thisis also the case why wait and notify can only be called within a critical section.


Thread LifecycleThis is the complete lifecycle of the thread showing the effects of start(), wait(),sleep() and join().

ready

running

inactive

sleepingwaitingblocked (IO)blocked (sync)

start()

chosen by scheduler to run

scheduler swaps it out

yield()sleep(), wait(), join()

unblocks

notify(), interrupt()


Advanced Aspects ofJava: Atomic AccessIn Java, reads and writes of references and most basic types are atomic, i.e. theyhappen effectively at once. This does not hold for long and double, where the readsand writes are done in two chunks of 32 bit. Thus, two competing threads canread/write corrupted/incomplete data.

Use the volatile keyword to make any variable read/write atomic. In certain cases,this may already be enough to synchronize your threads, i.e. a synchronized mightnot be required anymore, since any change on a volatile variable is immediately visibleto other threads. However, volatile does not extend to the operators, i.e. aincrement or decrement operator may still require synchronization.

Final (final) �elds however, are thread-safe, since their values don't change.


https://docs.oracle.com/javase/specs/jls/se9/html/jls-17.html#jls-17.5

Further ReadingFor more details and examples, refer to the chapter Concurrency of the Oracle Java SETutorial. Chapter 17 of the Java Language Speci�cation describes the full speci�cs ofJava's threads and locks.


https://docs.oracle.com/javase/tutorial/essential/concurrency/

https://docs.oracle.com/javase/specs/jls/se9/html/jls-17.html

Final Thought!


Documents

Programmierkonzepte Modul - Fortgeschrittene · In Java, threads are technically user level, since you work with the java.lang.Thread API (and the JVM) rather than directly with the