Stream API

Life cycle
Thread Optimization

T1
[a1,a2 ... an]
Thread Optimization
the T1 first thread
waits for the other threads
to finish with the executions
T1
THERE ARE 3 THREADS
[a1,a2 ... an]
INVOLVED !!!

T2 T3
[ak,ak+1 ... al] [am,am+1 ... az]
Thread Optimization
the T1 first thread
can do the operation as well

T1 NOW THERE ARE JUST 2

THREADS INVOLVED !!!
[a1,a2 ... an]

T1 T3
[ak,ak+1 ... al] [am,am+1 ... az]
Memory Management
 there are processes and threads (light-weight processes)

„The typical difference is that threads (of the same process) run in a shared
memory space, while processes run in separate memory spaces”

STACK MEMORY HEAP MEMORY

the local variables and method objects are stored on the heap memory
arguments as well as method calls and live as long as it is referenced from
are stored on the stack somewhere in the application.

EVERY THREAD HAS ITS OWN STACK MEMORY BUT ALL THREADS
SHARE THE HEAP MEMORY (SHARED MEMORY SPACE)

 the main purpose of synchronization is the sharing of resources

without interference using mutual exclusion.
Daemon and Worker Threads

Java Virtual Machine (JVM)

main thread daemon threads (gc)

here we can create as many worker

threads as we want
(child threads of the main thread)
Daemon and Worker Threads

 daemon threads are a low priority threads that runs in background

to perform tasks such as garbage collection

 usually we create daemon threads for I/O operations or services

(smartphone services such as NFC or Bluetooth communication)

We can create a daemon thread for a smartphone

application to look for smart-watches to pair with ...

 daemon threads are terminated by the JVM when all other

worker threads are terminated (finish execution)

 so this is the main difference: worker threads are not terminated

while daemon threads are interrupted by the JVM
Memory Management
 there are processes and threads (light-weight processes)

„The typical difference is that threads (of the same process) run in a shared
memory space, while processes run in separate memory spaces”

cache stack thread 1

MAIN
MEMORY
(RAM)
cache stack thread 2
Memory Management

public void increment() { reading the number from memory

incrementing the value
counter++;
writing the number to memory
} return with the variable

These operations seems to be atomic in the sense that

requires only a single operation but this is not the case

 it takes some time to finish with the increment operation

 during this procedure another thread may call this method

as well with the original counter value
Intrinsic Lock (Monitor)
public synchronized void increment() {
counter++;
}

 every object in Java has a so–called intrinsic lock

”A thread that needs exclusive and consistent access to an object's fields

has to acquire the object's intrinsic lock before accessing them, and then
release the intrinsic lock when it's done with them”

 because of the monitor lock: no 2 threads can execute the

same synchronized method at the same time
Intrinsic Lock (Monitor)
 a thread owns the intrinsic lock between the time it has acquired
the lock and released the lock.

 as long as a thread owns an intrinsic lock no other thread can acquire the same lock

 the other thread will block when it attempts to acquire the lock.

THE PROBLEM IS THAT EVERY OBJECT HAS A SINGLE MONITOR LOCK

 if we have 2 independent synchronized methods than

the threads have to wait for each other to release the lock
Intrinsic Lock (Monitor)
public synchronized void increment() {
counter++;
}

public void increment() {

synchronized(this) {
counter++;
}
}

This is called object level locking because we get the

monitor lock (intrinsic lock) associated with the object itself
Intrinsic Lock (Monitor)
public static synchronized void increment() {
counter++;
}

public void increment() {

synchronized([Link]) {
counter++;
}
}

This is called class level locking because we get the

monitor lock (intrinsic lock) associated with the class
Threads Communication
Threads that are locking on the same intrinsic lock (monitor) can
release the lock until the other thread calls notify

cache stack thread 1

wait() notify()

cache stack thread 2

Note: these wait() and notify() methods can be used

and called from synchronized methods or blocks exclusively
Stream API Explained
 streams are supported starting in Java 8
 basically streams introduce functional programming to the Java
programming ecosystem

„In computer science, functional programming is a programming paradigm

where programs are constructed by applying and composing functions”

 streams rely heavily on lambda expressions

 we can construct parallel operations quite easily with streams

„Lambda expressions are similar to methods, but they do not need a

name and they can be implemented right in the body of a method”
Memory Management

thread #1

counter = 0

thread #2
Memory Management

thread #1

counter = 0

thread #2
Memory Management

counter = counter + 1
thread #1

counter = 0

thread #2
Memory Management

counter = counter + 1
thread #1

counter = 0

thread #2
Memory Management

counter = counter + 1
thread #1

counter = 0

thread #2
counter = counter + 1
Memory Management

thread #1

counter = 1

thread #2
counter = counter + 1
Memory Management

thread #1

counter = 1

thread #2
Memory Management

thread #1

counter = 1

thread #2

Note: both of the threads incremented the value of the counter

but the result will be 1 (instead of 2) because they do the same
operation at the same time
Stream API Explained
 streams are supported starting in Java 8
 basically streams introduce functional programming to the Java
programming ecosystem

„In computer science, functional programming is a programming paradigm

where programs are constructed by applying and composing functions”

 streams rely heavily on lambda expressions

 we can construct parallel operations quite easily with streams
Stream API Explained

INTERMEDIATE TERMINAL
SOURCE
OPERATIONS OPERATIONS

the source of the stream returns a stream returns scalar or void

(collection of data) (filtering, sorting etc.) (collect, reduce etc.)
Threads: there are various stages  thread is born, it is started, it runs
and it dies
Threads: there are various stages  thread is born, it is started, it runs
and it dies

new

runnable

running

waiting

dead
Threads: there are various stages  thread is born, it is started, it runs
and it dies

new 1.) NEW when we instantiate a thread

It is in this state until we start it
~ start()
runnable
2.) RUNNABLE after we have started the thread
The thread is executing its task in this state
running
3.) WAITING when a thread is waiting: for example
waiting for another thread to finish its task
When other thread signals  this thread
goes back to the ‚runnable’ state
dead ~ wait() and sleep()

4.) DEAD after the thread finishes its task

Threads: there are various stages  thread is born, it is started, it runs
and it dies

new 1.) NEW when we instantiate a thread

It is in this state until we start it
~ start()
runnable
2.) RUNNABLE after we have started the thread
The thread is executing its task in this state
running
3.) WAITING when a thread is waiting: for example
waiting for another thread to finish its task
When other thread signals  this thread
goes back to the ‚runnable’ state
dead ~ wait() and sleep()

4.) DEAD after the thread finishes its task

Threads: there are various stages  thread is born, it is started, it runs
and it dies

new 1.) NEW when we instantiate a thread

It is in this state until we start it
~ start()
runnable
2.) RUNNABLE after we have started the thread
The thread is executing its task in this state
running
3.) WAITING when a thread is waiting: for example
waiting for another thread to finish its task
When other thread signals  this thread
goes back to the ‚runnable’ state
dead ~ wait() and sleep()

4.) DEAD after the thread finishes its task

Threads: there are various stages  thread is born, it is started, it runs
and it dies

new 1.) NEW when we instantiate a thread

It is in this state until we start it
~ start()
runnable
2.) RUNNABLE after we have started the thread
The thread is executing its task in this state
running
3.) WAITING when a thread is waiting: for example
waiting for another thread to finish its task
When other thread signals  this thread
goes back to the ‚runnable’ state
dead ~ wait() and sleep()

4.) DEAD after the thread finishes its task

MULTITHREADING
ADVANTAGES
Advantages

 We can design more responsive softwares  do several things at the same

time
 We can achieve better resource utilization
 We can improve performance !!!
Downloading images
from the web

IO operations: copying files

and parse the content

Doing heavy calculations

For example: simulations, numerical methods
Downloading images
from the web THREAD #1

IO operations: copying files

and parse the content THREAD #2

Doing heavy calculations

For example: simulations, numerical methods
THREAD #3
MULTITHREADING
DISADVANTAGES
Disadvantages

 Of course there are some costs involved in multithreading

 Multithreading is not always better !!!
 Threads manupulate data located on the same memory area  we have to
take it into consideration
 Difficult to design multithreaded software
 Hard to detect errors
 EXPENSIVE OPERATION: switcing between threads is exspensive !!!
~ CPU save local data, pointers ... of the current thread
+ loads the data of the other thread
Rule of thumb: for small problems it is unnecessary to use multithreading,
it may be slower than single threaded applications
~ multithreaded sorting is slower for small number of items

running time

#threads
MULTITHREADING
DEADLOCK AND LIVELOCK
Deadlock
“Deadlock occurs when two or more threads wait forever for a lock
or resource held by another of the threads”

 deadlock is a situation in which two or more competing actions are each

waiting for the other to finish, and thus neither ever does

1.) DEADLOCK IN DATABASES:

Deadlock happens when two processes each within its own transaction updates
two rows of information but in the opposite order.

For example: process A updates row 1 then row 2 in the exact timeframe that
process B updates row 2 then row 1
 Deadlock
“Deadlock occurs when two or more threads wait forever for a lock
or resource held by another of the threads”

 deadlock is a situation in which two or more competing actions are each

waiting for the other to finish, and thus neither ever does

2.) DEADLOCK IN OPERATIONG SYSTEMS:

Deadlock is a situation which occurs when a process or thread enters a

waiting state because a resource requested is being held by another waiting process,
which in turn is waiting for another resource held by another waiting process
Livelock
 a thread often acts in response to the action of another thread
 if the other thread's action is also a response to the action of another thread
then livelock may occure
 livelocked threads are unable to make further progress. However, the threads
are not blocked: they are simply too busy responding to each other to
resume work
 like two people attempting to pass each other in a narrow corridor: A moves
to his left to let B pass, while B moves to his right to let A pass. They are still
blocking each other, A moves to his right, while B moves to his left ... still not
good
How to Handle Deadlock and Livelock?
1.) we should make sure that a thread does not block infinitely if it is
unable to acquire a lock

 this is why using Lock interface’s tryLock() method is

extremely convenient and useful

2.) we should make sure that each thread acquires the locks in the same order
to avoid any cyclic dependency in lock acquisition

3.) livelock can be handled with the methods above and some randomness
~ threads retry acquiring the locks at random intervals
Livelock

 A thread often acts in response to the action of another thread

 If the other thread's action is also a response to the action of another thread
 livelock !!!
 Livelocked threads are unable to make further progress. However, the threads
are not blocked  they are simply too busy responding to each other to
resume work
 Like two people attempting to pass each other in a narrow corridor: A moves
to his left to let B pass, while B moves to his right to let A pass. They are still
blocking each other, A moves to his right, while B moves to his left ... still not
good
Parallel versus multithreading

thread #1

thread #2

„parallel execution”

thread #1

thread #2
„multithreaded execution” (with time-slicing)
Volatile Keyword

cache CPU 1 thread 1

MAIN
MEMORY
(RAM)
cache CPU 2 thread 2

Every read of a volatile variable will be read from the RAM so from
the main memory (and not from cache)
 usually variables are cached for performance reasons

 caches are faster. Do not use volatile keyword if not necessary

( + it prevents instruction reordering which is a performance
boost technique )
Volatile

thread 1

counter = 0

thread 2
Volatile

thread 1

counter = 0

thread 2
Volatile

counter = counter + 1
thread 1

counter = 0

thread 2
Volatile

counter = counter + 1
thread 1

counter = 0

thread 2
Volatile

counter = counter + 1
thread 1

counter = 0

thread 2
counter = counter + 1
Volatile

thread 1

counter = 1

thread 2
counter = counter + 1
Volatile

thread 1

counter = 1

thread 2
Volatile

thread 1

counter = 1

thread 2

Counter remained 1 instead of 2

~ we should make sure the threads are going to wait
for each other to finish the given task on the variables !!!
 EXCHANGER

object1
thread #1 thread #2
object2
MULTITHREADING
STUDENT LIBRARY SIMULATION
 b0 b1 b2 b3 b4 b5 b6 b7

s0 s1 s2 s3
MULTITHREADING
DINING PHILOSOPHERS PROBLEM
Dining Philosophers Problem
 it was formulated by Dijkstra in 1965
 5 philopshers are present at a table and there are 5 forks (chopsticks)
 the philsophers can eat and think
 philosophers can eat when they have both left and right chopsticks
 a chopstick can be hold by one philosopher at a given time
 the problem: how to create a concurrent algorithm such that no philosopher
will starve? (so the aim is to avoid deadlocks)
Dining Philosophers Problem
Dining Philosophers Problem
p
1

p
2
p
0

p
3
p
4
Dining Philosophers Problem
p
1

p
2
p c
0 0 c
1

c c
2
4

c
3
p
3
p
4
Dining Philosophers Problem
Dining Philosophers Problem
Dining Philosophers Problem
MULTITHREADING
Locks and synchronization
Locks and Synchronized Blocks
A reentrant lock has the same basic behavior as we have seen for
synchronized blocks (with some extrended features)

 we can make a lock fair: prevent thread starvation

Synchronized blocks are unfair by default

 we can check whether the given lock is held or not

with reentrant locks

 we can get the list of threads waiting for the given lock
with reentrant locks

 synchronized blocks are nicer: we do not need the

try-catch-finally block
MULTITHREADING
Parallel sum
5 2 8 1 11 17 9 3
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
5 2 8 1 11 17 9 3

for i in nums
total = total + nums[i]
Parallel sum  with multiple processors or multicore processor
we can assign a task to every processor
~ parallel computing

5 2 8 1 11 17 9 3
Parallel sum  with multiple processors or multicore processor
we can assign a task to every processor
~ parallel computing

5 2 8 1 11 17 9 3

thread #1 thread #2

sum1 = 16 sum2 = 40
MULTITHREADING
FORK-join framework
What is fork-join framework?

Concrete implementation for parallel execution !!!

Fork-join framework

 This framework helps to make an algorithm parallel

 We do not have to bother about low level synchronizations or locks
 Divide and conquer algorithms !!!
 A larger task  it can be divided into smaller ones + the subsolutions can be
combined !!!
 IMPORTANT subtasks have to be independent in order to be executed in parallel
 So the main concept fork-join framework breaks the task into smalles subtasks
until these subtasks are simple enough to solve without further breakups
 For example: parallel merge sort, parallel maximum finding
RecursiveTask<T> it will return a T type

All the tasks we want to execute in parallel is a subclass of this class

We have to override the computer method that will return the
solution of the subproblem

RecursiveAction it is a task, but without any return value

ForkJoinPool

Basically it is a thread pool for executing fork-join tasks

work-stealing a task is not equivalent to a thread !!!

Tasks are lightweight threads  so fork-join will be efficient even when
there are a huge number of tasks

So ForkJoinPool creates a fix number of threads  usually the number of CPU cores

These threads are executing the tasks but if a thread has no task: it can „steal” a task
from more busy threads
~ tasks are distributed to all threads in the thread pool !!!
fork  split the given task into smaller subtasks that can be
executed in a parallel manner

task

task task

task task
fork  split the given task into smaller subtasks that can be
executed in a parallel manner

task

task task

task task
join  the splitted tasks are being executed and after all of them are finished
they are merged into one result

task

task task

task task
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
 PARALLEL
EXECUTION

SEQUENTIAL
EXECUTION
Semaphores and Mutexes
 invented by Dijkstra back in 1962
 semaphores are simple variables (or abstract data types) that are used for
controlling access to a common resource
 it is an important concept in operating systems as wel

„It is a record of how many units of a particular resource are available.

We have to wait until a unit of the resource becomes available again.”

COUNTING SEMAPHORES: allows an arbitrary resource count

BINARY SEMAPHORES: semaphores that are restricted to the

values 0 and 1
Semaphores
 invented by Dijkstra back in 1962
 semaphores are simple variables (or abstract data types) that are used for
controlling access to a common resource
 it is an important concept in operating systems as wel

„It is a record of how many units of a particular resource are available.

We have to wait until a unit of the resource becomes available again.”

COUNTING SEMAPHORES: allows an arbitrary resource count

BINARY SEMAPHORES: semaphores that are restricted to the

values 0 and 1
Semaphores
 suppose a library has 10 identical study rooms (it can be used by a single
student at a time)
 students must request a study room from the front desk
 if no rooms are free: students have to wait for rooms to be available again so
until someone relinquishes a given study room
 when a student finished using the room, the student must return to the front
desk and indicate that one room has become free

THIS PROBLEM CAN BE SOLVED WITH THE HELP OF A

SEMAPHORE
Semaphores

1.) semaphores tracks only how many resources are free – it does not keep
track of which of the resources are free

2.) the semaphore count may serve as a useful trigger for a number of
different actions (web servers)

3.) producer-comsumer problem can be solved and implemented

with the help of semphores (Dijkstra’s approach)
Mutexes (Mutual Exclusion Objects)
„Mutual exclusion is a property of concurrency control which is
instituted for the purpose of preventing race conditions”

 process synchronization plays an important role in maintaining

the consistency of shared data (critical section problem)

 mutex is very similar to a binary semaphore: while binary semaphore can

be used as mutex, a mutex is a more specific use-case
 a Lock is designed to enforce a mutual exclusion concurrency control policy
Mutexes (Mutual Exclusion Objects)
SEMAPHORE
 It is a signaling mechanism

 threads and processes perform wait() and notify() operations to

indicate whether they are acquiring or releasing the resource

MUTEX
 mutex is a locking mechanishm

 threads or processes have to acquire the lock on

mutex object if it wants to acquire the resource
Mutexes (Mutual Exclusion Objects)
SEMAPHORE

 semaphore allows multiple program threads to access the

finite instance of resources (not just a single resource)

MUTEX

 mutex allows multiple program threads to access a

single shared resource but one at a time
Mutexes (Mutual Exclusion Objects)
SEMAPHORE

 the process or thread blocks itself if no resource is free

till the count of semaphore become greater than 0

MUTEX

 if the lock is already acqured by another thread or process then

the thread will wait until the mutex object gets unlocked
Executors
With the increase in the number of the cores available in the processors nowadays,
multithreading is getting more and more crucial

 Java provides its own multi-threading framework

the so-called Executor Framework

 with the help of this framework we can manage worker threads

more efficiently because of thread pools

USING THREAD POOLS MAKES MULTITHREADING EFFICIENT !!!

Executors
Why to use thread pools and the Execturor Framework?

 it will handle everything: schedule and execute the submitted tasks

 creating and managing threads is expensive

 adding a new thread for each process leads to the

creation of a large number of threads

These threads need memory + CPU will spend too much time switching
context when the threads are swapped

USING THREAD POOLS MAKES MULTITHREADING EFFICIENT !!!

Thread pools can resue threads in an extremely efficient manner

by keeping the threads alive and reusing them
(thread pools are usually queues)
 Executors
There are several types of executors:

1.) SingleThreadExecutor

This executor has a single thread so we can execute processes

in a sequential manner. Every process is exectured by a new thread

2.) FixedThreadPool(n)

This is how we can create a thread pool with n threads. Usually n

is the number of cores in the CPU.

 if there are more tasks than n then these taks are

stored with a LinkedBlockingQueue data structure
 Executors
here are several types of executors:

3.) CachedThreadPool

The number of threads is not bounded: if all the threads are busy
executing some tasks and a new task comes the pool will create
and add a new thread to the executor.

 if a thread remains idle for 60 secs then it is removed

 it is used for short parallel tasks

4.) ScheduledExecutor

We can execute a given operation at regular intervals

or we can use this executor if we wish to delay a certain task
 Runnable and Callable Interfaces
unnable and Callable both run on a different threads than the calling thread
but Callable can return a value and Runnable can not

RUNNABLE: a so-called run-and-forget action. We execute a given

operation in the run() method without a return value

CALLABLE<T>: we use Callable interface’s call() method if we want

to return a given value from the given thread

 Callable interface will not return the value: this is

why we need Future<T> object

 calling thread will be blocked till the call() method is

executed and Future<T> returns with the results
 Runnable and Callable Interfaces
The ExecutorService can handle both of the interfaces
(Runnable and Callable interfaces)

[Link]()

This method executes a Runnable interface so it means

there is no return value (void run() method)

[Link]()

This method can handle Runnable interfaces as well as

Callable interfaces

 it can handle a Future<T> return value and we

can get the T vaue with get() on the future object