CS499-Mobile Application Development
CS499 – Mobile Application
Development
Fall 2013
Threads & Android – Part 1
Carnegie Mellon
Concurrent Programming
•
Multiple processes – each logical control flow
is a process. Some form of IPC (InterProcess
Communication) needed
•
Multiple threads – multiple logical control
flows within a single process. Shared address
space
•
I/O multiplexing – event driven concurrency.
Shared address space
Threads
•
What is a thread?
–
Conceptual View
•
Parallel computations running in a process
–
Implementation View
•
Each thread has a program counter and a stack
•
The heap and static areas are shared across threads
Computation Abstractions
Concurrent Threads
Processes vs. Threads
Process vs. Threads
•
Process = process context + code, data, and stack
shared libraries
run-time heap
0
read/write data
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
Code, data, and stack
read-only code/data
stack
SP
PC
brk
Process context
Kernel context:
VM structures
Descriptor table
brk pointer
Process with Two Threads
shared libraries
run-time heap
0
read/write data
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
Code, data, and kernel context
read-only code/data
stack
SP
PC
brk
Thread 1
Kernel context:
VM structures
Descriptor table
brk pointer
Program context:
Data registers
Condition codes
Stack pointer (SP)
Program counter (PC)
stack
SP
Thread 2
Android Threads
•
Activities have a main thread – the UI thread
•
App components in the same process use the
same main thread
•
User interaction, system callback & lifecycle
methods are handled in the UI thread
•
It is essential that the UI remains responsive
•
UI toolkit not thread-safe.
–
A piece of code is
thread-safe
if it only manipulates
shared data structures in a manner that guarantees
safe execution by multiple threads at the same time.
Java Thread Programming
•
Threads and synchronization supported
at the language level
•
Threads managed by the JVM (or DVM
in our case)
Basic Java Thread Use Case
•
Instantiate a Thread
object
•
Invoke the Thread’s
start() method
–
Thread will invoke its
own run()
•
Thread terminates
when run() returns
Simple Example: Using Runnable
public class BytePrinter
implements Runnable
{public void
run()
{for (int b = -128; b < 128; b++)
System.out.println(b);
}
}
public class ThreadTest { public static void main(String[] args) {Thread bp1 = new Thread(new BytePrinter());
Thread bp2 = new Thread(new BytePrinter());
Thread bp3 = new Thread(new BytePrinter());
bp1.start();
bp2.start();
bp3.start();
System.out.println(“I am the main thread”);
}
}
start threads
create thread instances
Pros and Cons of Thread-Based Designs
+ Easy to share data structures between threads
–
e.g., logging information, file cache
+ Threads are more efficient than processes
–
Unintentional sharing can introduce subtle and
hard-to-reproduce errors!
The ease with which data can be shared is both the
greatest strength and the greatest weakness of
threads
Carnegie Mellon
Thread Programming is Hard!
•
Thinking about all possible sequences of events in
a computer system is at least error prone and
frequently impossible
•
Classical problem classes of concurrent programs:
–
Races:
outcome depends on arbitrary scheduling
decisions elsewhere in the system
–
Deadlock:
improper resource allocation prevents
forward progress
–
Livelock / Starvation / Fairness:
external events and/or
system scheduling decisions can prevent sub-task
progress
Deadlock
•
In a multi-programmed
environment,
processes/threads
compete for (exclusive) use
of a finite set of resources
•
Deadlock occurs when we
have a cycle of
dependencies.
•
A is waiting on B and B is
waiting on A – deadlock!
Race Conditions
•
Situations where multiple processes are writing or reading
some shared data and the final result
depends on who runs
precisely when
are called
race conditions
.
•
A serious problem for most concurrent systems using shared
variables! Maintaining data consistency requires mechanisms
to ensure the orderly execution of cooperating processes.
•
We must make sure that some high-level code sections are
executed
atomically
.
•
Atomic operation means that it completes in its
entirety
without worrying about interruption by any other potentially
conflict-causing process.
Concurrent Access to Shared Data
•
Suppose that two threads A and B have
access to a shared variable “Balance”.
THREAD A: THREAD B:
Balance = Balance - 100 Balance = Balance + 200
Concurrent Access to Shared Data
•
The statement “
Balance = Balance – 100
” is
implemented by
several
machine level instructions
such as:
movl (%ecx),%eax
subl %eax,%edx
movl %eax, (%ecx)
•
Similarly, “
Balance = Balance + 200
” can be
implemented by the following:
movl (%ecx),%eax
addl %eax,%ebx
movl %eax,(%ecx)
Race Conditions
•
Scenario 1:
m
o
v
l
(
%
e
c
x
)
,
%
e
a
x
s
u
b
l
%
e
a
x
,
%
e
d
x
m
o
v
l
%
e
a
x
,
(
%
e
c
x
)
C
o
n
t
e
x
t
S
w
i
t
c
h
m
o
v
l
(
%
e
c
x
)
,
%
e
a
x
a
d
d
l
%
e
a
x
,
%
e
b
x
movl %eax,(%ecx)
•
B
a
l
a
n
c
e
i
s
i
n
c
r
e
a
s
e
d
b
y
1
0
0
Observe:
In a
time-shared
system the
exact instruction
execution
order
cannot be predicted
Scenario 2:
movl (%ecx),%eax
subl %eax,%edx
Context Switch
movl (%ecx),%eax
addl %eax,%ebx
movl %eax,(%ecx)
Context Switch
movl %eax, (%ecx)
Balance is
decreased
by
100
Ornamental Garden Problem
People enter an ornamental garden through either of two
turnstiles. Management wish to know how many are in the
garden at any time.
The concurrent program consists of two concurrent threads and
a shared counter object.
from Concurrency: State Models & Java Programming, by J. Magee, J
Kramer
Turnstile class
class
Turnstile
extends
Thread {NumberCanvas display;
Counter people;
Turnstile(NumberCanvas n,Counter c)
{ display = n; people = c; }public
void run() {try
{display.setvalue(0);
for
(int i=1;i<=Garden.MAX;i++){Thread.sleep(500);
//0.5 second between arrivals
display.setvalue(i);
people.increment();
}
}
catch
(InterruptedException e) {}}
}
The
run()
method exits
and the thread
terminates after
Garden.MAX
visitors have
entered.
Counter class
class
Counter {int value=0;
NumberCanvas display;
Counter(NumberCanvas n) {display=n;
display.setvalue(value);
}
void increment() {int temp = value;
//read value
Simulate.HWinterrupt();
value=temp+1;
//write value
display.setvalue(value);
}
}
Hardware interrupts can
occur at
arbitrary
times.
The
counter
simulates a
hardware interrupt during
an
increment()
,
between reading and
writing to the shared
counter
value
. Interrupt
randomly calls
Thread.sleep()
to
force a thread switch.
ornamental garden program
private
void go() {counter =
new
Counter(counterD);
west =
new
Turnstile(westD,counter);
east =
new
Turnstile(eastD,counter);
west.start();
east.start();
}
The
Counter
object and
Turnstile
threads are created
by the
go()
method of the Garden applet:
ornamental garden program - display
After the East and West turnstile threads have each
incremented its counter 20 times, the garden people counter
is not the sum of the counts displayed. Counter increments
have been lost.
Why?
concurrent method activation
Java method activations are not atomic - thread objects
east
and
west
may be executing the code for the increment method at the
same time.
east
west
increment:
read value
write value + 1
program
counter
program
counter
shared code
Solution? Synchronization
•
Synchronization
–
Most synchronization can be regarded
as either:
•
Mutual exclusion (making sure that only one
process is executing a CRITICAL SECTION
[touching a variable or data structure, for
example] at a time),
or as
•
CONDITION SYNCHRONIZATION, which
means making sure that a given process
does not proceed until some condition holds
(e.g. that a variable contains a given value)
Competition
Cooperation
critical section
Code segment that needs to execution atomically (i.e. only one thread
at a time, running to completion).
If increment is a critical section, west is forced to wait for east to
complete the increment.
east
west
increment:
read value
write value + 1
program
counter
program
counter
shared code
Mutual Exclusion
Mutual exclusion in Java
class
SynchronizedCounter extends Counter {SynchronizedCounter(NumberCanvas n)
{super(n);}synchronized
void increment() {super.increment();
}
}
We correct
COUNTER
class by deriving a class from it
and making the increment method
synchronized
:
Concurrent activations of a method in Java can be made mutually
exclusive by prefixing the method with the keyword
synchronized
, which uses a lock on the object.
acquire
lock
release
lock
mutual exclusion - the ornamental
garden
Java associates a
lock
with every object. The Java compiler
inserts code to acquire the lock before executing the body of
the synchronized method and code to release the lock before
the method returns. Concurrent threads are blocked until the
lock is released.
Java Locks and Synchronization
•
Every object has an intrinsic lock associated with it.
•
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.
•
A thread is said to
own
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.
Java Locks and Synchronization
•
When a thread invokes a synchronized method, it
automatically acquires the intrinsic lock for that
method's object and releases it when the method
returns (even if it returns via an exception)
•
Statements inside a method can by synchronized
as well. This is useful in cases where the methods
of other objects are invoked.
synchronized(this) {lastName = name;
nameCount++; }
nameList.add(name);
}
Java synchronized statement
Access to an object may also be made mutually exclusive by
using the
synchronized
statement:
synchronized
(
object
) { statements
}
A less elegant way to correct the example would be to modify
the
Turnstile.run()
method:
synchronized
(people) {people.increment();}Why is this “less elegant”?
Creating Lock Objects
public class DualCounters {private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object();
private Object lock2 = new Object();
public void inc1() {synchronized(
lock1
) { c1++; }}
public void inc2() {synchronized(
lock2
) { c2++; }}
}
Must be done with care!
Java Collections
java.util.concurrent package includes a number of additions to
the Java Collections Framework.
•
BlockingQueue
defines a first-in-first-out data structure that
blocks or times out when you attempt to add to a full queue,
or retrieve from an empty queue.
•
ConcurrentMap
is a subinterface of
java.util.Map
that defines
useful atomic operations. These operations remove or replace
a key-value pair only if the key is present, or add a key-value
pair only if the key is absent. Making these operations atomic
helps avoid synchronization. The standard general-purpose
implementation of ConcurrentMap is
ConcurrentHashMap
,
which is a concurrent analog of
HashMap
.
Atomic Variables
class SynchronizedCounter {private int c = 0;
public synchronized void increment() { c++; } public synchronized void decrement() { c--; } public synchronized int value() { return c; }}
import java.util.concurrent.atomic.AtomicInteger;
class AtomicCounter {private AtomicInteger c = new AtomicInteger(0);
public void increment() { c.incrementAndGet(); } public void decrement() { c.decrementAndGet(); } public int value() { return c.get(); }}
Condition Synchronization
public class checkpoint {boolean here_first = true;
synchronized void meet_up () {if (here_first) {here_first = false;
wait();
} else {notify();
here_first = true;
}
};
};
Condition Synchronization
•
wait(), notify(), notifyall()
•
We can call the wait() method of any Java object,
which suspends the current thread. The thread is
said to be "waiting on" the given object.
•
Another thread calls the notify() method of the
same Java object. This "wakes up" one of the
threads waiting on that object.
•
notifyall() methods “wakes up” all of the threads
waiting on that object.
Producer/Consumer Problem
Producer
Consumer
bounded size buffer (N)
Producer and Consumer execute concurrently but only one
should be accessing the buffer at a time.
Producer puts items to the buffer area but should not be allowed
to put items into a full buffer
Consumer process consumes items from the buffer but cannot
remove information from an empty buffer
Competition
Cooperation
Bounded Buffer
public class BufferImpl<E> implements Buffer<E> {protected E[] buf;
protected int in = 0; protected int out= 0;
protected int count= 0; protected int size;
public BufferImpl(int size) { this.size = size; buf = (E[])newObject[size];}
public
synchronized
void put(E o) throws InterruptedException {while (count==size) wait();
buf[in] = o; ++count;
in=(in+1) % size;
notifyAll();
}
public
synchronized
E get() throws InterruptedException {while (count==0) wait();
E o = buf[out];
buf[out]=null; --count;
out=(out+1) % size;
notifyAll();
return (o);
}
}
Bounded Buffer
class Producer implements Runnable {Buffer<Character> buf;
String alphabet=
"abcdefghijklmnopqrstuvwxyz";
Producer(Buffer<Character> b)
{buf = b;} public void run() { try {int ai = 0;
while(true) {ThreadPanel.rotate(12);
buf.put(alphabet.charAt(ai));
ai=(ai+1)%alphabet.length();
ThreadPanel.rotate(348);
}
}catch (InterruptedException e){}}
}
class Consumer implements
Runnable {Buffer<Character> buf;
Consumer(Buffer<Character> b)
{buf = b;} public void run() { try { while(true) {ThreadPanel.rotate(180);
Character c =
buf.get();
ThreadPanel.rotate(180);
}
}catch(InterruptedException
e){}}
}
Bounded Buffer
public class BoundedBuffer extends Applet {ThreadPanel prod;
ThreadPanel cons;
public void init() {super.init();
// Set up Display
prod = new ThreadPanel("Producer",Color.blue); cons = new ThreadPanel("Consumer",Color.yellow);…
}
public void start() {Buffer<Character> b = new DisplayBuffer(buffDisplay,5);
// Create Thread
prod.start(new Producer(b)); cons.start(new Consumer(b));
}
public void stop() {prod.stop(); cons.stop();
}
}
Semaphore Object
public class Semaphore {private int value ;
Semaphore(int n) { value = n;}public
synchronized
void v() {value = value + 1;
notifyAll();
}
public
synchronized
void p()
throws InterruptedException
{while (value == 0)
wait();
value = value - 1;
}
}
Semaphores were invented by
Edsger Dijkstra. p() & v() came from
the Dutch words for wait & signal.
Useful for mutual exclusion.
Reader/Writer –
Version 1
public class ReaderWriter { public static void main(String[] args) {Semaphore mutual_exclusion = new Semaphore(1);
Reader r1 = new Reader(1,
mutual_exclusion
);
Reader r2 = new Reader(2,
mutual_exclusion
);
Writer w1 = new Writer(1,
mutual_exclusion
);
r1.start();
r2.start();
w1.start();
}
}
Multiple readers & writers to a shared
object. Must ensure:
1 – writers can’t overlap
2 – readers & writers can’t overlap
3 – allow multiple readers
RW – Version 1
public class Reader extends Thread {int id;
Semaphore mutex;
Reader(int c,
Semaphore s
) {id = c; mutex = s
;}
public void run() {int i = 0;
while (i < 10) { try { mutex.p();
} catch (InterruptedException e) {}System.out.println(id + " start Reading");
try { Thread.sleep(500); } catch (InterruptedException e) {}System.out.println(id + " stop Reading");
mutex.v();
try {Thread.sleep(500); } catch (InterruptedException e) {}i = i + 1;
}
}
}
Writer.java is similar…
Version 1 notes
•
Mutual exclusion achieved.
•
However, this means only one reader at a
time…
•
Continuing on the semaphore approach, can
create a counter (for number of readers) and
second semaphore…
•
Writer unchanged
RW – Version 2
public class ReaderWriter { public static void main(String[] args) {Semaphore mutual_exclusion = new Semaphore(1);
Semaphore reader_mutex = new Semaphore(1);
Counter num_readers = new Counter(0);
Reader r1 = new Reader(1,
mutual_exclusion,
reader_mutex,num_readers
);
Reader r2 = new Reader(2,
mutual_exclusion,
reader_mutex,num_readers
);
Writer w1 = new Writer(1,
mutual_exclusion
);
r1.start();
r2.start();
w1.start();
}
}
RW – Version 2
public class Reader extends Thread {int id;
Semaphore mutex;
Semaphore read_mutex;Counter readers;
Reader(int c,
Semaphore s,
Semaphore r,Counter num_r
) {id = c;
mutex = s
;
read_mutex=r; readers = num_r;
}
public void run() {int i = 0;
while (i < 10) {read_mutex.p();
readers.incr(); if (readers.get() == 1)
mutex.p();
read_mutex.v();
System.out.println(id + " start Reading");
Thread.sleep(500);
System.out.println(id + " stop Reading");
read_mutex.p();
readers.decr(); if (readers.get() == 0)
mutex.v();
read_mutex.v();
Thread.sleep(500);
i = i + 1;
}
}}
Writer.java as in Version 1
Reader/Writer Monitor Soln
class ReadWriteSafe implements ReadWrite {private int readers =0;
private boolean writing = false;
public synchronized void acquireRead() throws
InterruptedException {while (writing) wait();
++readers;
}
public synchronized void releaseRead() {--readers;
if(readers==0) notifyAll();
}
Multiple readers & writers to a shared
object. Must ensure:
1 – writers can’t overlap
2 – readers & writers can’t overlap
3 – allow multiple readers
public synchronized void acquireWrite()
throws InterruptedException {while (readers>0 || writing) wait();
writing = true;
}
public synchronized void releaseWrite() {writing = false;
notifyAll();
}
}
Reader/Writer Monitor Soln
class ReadWritePriority implements ReadWrite{private int readers =0;
private boolean writing = false;
private int waitingW = 0; // no of waiting Writers.
public synchronized void acquireRead()
throws InterruptedException {while (writing || waitingW>0) wait();
++readers;
}
public synchronized void releaseRead() {--readers;
if (readers==0) notifyAll();
}
RW WritePriority Monitor Soln
public synchronized void acquireWrite()
throws InterruptedException {++waitingW;
while (readers>0 || writing) wait();
--waitingW;
writing = true;
}
public synchronized void releaseWrite() {writing = false;
notifyAll();
}
}
RW WritePriority Monitor Soln
class ReadWriteFair implements ReadWrite {private int readers =0;
private boolean writing = false;
private int waitingW = 0; // no of waiting Writers.
private boolean readersturn = false;
synchronized public void acquireRead() throws
InterruptedException {while (writing || (waitingW>0 && !readersturn))
wait();
++readers;
}
synchronized public void releaseRead() {--readers;
readersturn=false;
if(readers==0) notifyAll();
}
RW Fair Monitor Soln
synchronized public void acquireWrite() throws
InterruptedException {++waitingW;
while (readers>0 || writing) wait();
--waitingW;
writing = true;
}
synchronized public void releaseWrite() {writing = false;
readersturn=true;
notifyAll();
}
}
RW Fair Monitor Soln
Thread Joining
A thread can wait for the completion of a thread by using the
join()
method
class Worker2 implements Runnable { public void run() {System.out.println(“Worker thread.”);
}
}
public class Second { public static void main(String args[]) {Thread thrd = new Thread(new Worker2());
thrd.start();
System.out.println(“Main thread.”);
try {thrd.join();
} catch (InterrruptedException) ie) { }}
Learn about the concepts of threads, processes, and concurrency in mobile application development. Understand the differences between multiple processes and threads, shared address space, and the implementation view of threads. Explore the importance of concurrent programming, managing multiple logical control flows, and ensuring responsiveness in Android applications. Dive into the essentials of handling UI threads, system callbacks, and lifecycle methods to create efficient and responsive mobile apps.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CS499 Mobile Application Development Fall 2013 Threads & Android Part 1
Carnegie Mellon Concurrent Programming Multiple processes each logical control flow is a process. Some form of IPC (InterProcess Communication) needed Multiple threads multiple logical control flows within a single process. Shared address space I/O multiplexing event driven concurrency. Shared address space
Threads What is a thread? Conceptual View Parallel computations running in a process Implementation View Each thread has a program counter and a stack The heap and static areas are shared across threads
Process vs. Threads Process = process context + code, data, and stack Code, data, and stack stack Process context Program context: Data registers Condition codes Stack pointer (SP) Program counter (PC) SP shared libraries brk run-time heap read/write data read-only code/data Kernel context: VM structures Descriptor table brk pointer PC 0
Process with Two Threads Thread 1 Program context: Data registers Condition codes Stack pointer (SP) Program counter (PC) Code, data, and kernel context shared libraries brk run-time heap read/write data read-only code/data stack PC SP 0 Thread 2 Kernel context: VM structures Descriptor table brk pointer Program context: Data registers Condition codes Stack pointer (SP) Program counter (PC) stack SP
Android Threads Activities have a main thread the UI thread App components in the same process use the same main thread User interaction, system callback & lifecycle methods are handled in the UI thread It is essential that the UI remains responsive UI toolkit not thread-safe. A piece of code is thread-safe if it only manipulates shared data structures in a manner that guarantees safe execution by multiple threads at the same time.
Java Thread Programming Threads and synchronization supported at the language level Threads managed by the JVM (or DVM in our case)
Basic Java Thread Use Case Instantiate a Thread object Invoke the Thread s start() method Thread will invoke its own run() Thread terminates when run() returns
Simple Example: Using Runnable public class BytePrinter implements Runnable { public void run() { for (int b = -128; b < 128; b++) System.out.println(b); } } public class ThreadTest { public static void main(String[] args) { Thread bp1 = new Thread(new BytePrinter()); Thread bp2 = new Thread(new BytePrinter()); Thread bp3 = new Thread(new BytePrinter()); bp1.start(); bp2.start(); bp3.start(); System.out.println( I am the main thread ); } } create thread instances start threads
Pros and Cons of Thread-Based Designs + Easy to share data structures between threads e.g., logging information, file cache + Threads are more efficient than processes Unintentional sharing can introduce subtle and hard-to-reproduce errors! The ease with which data can be shared is both the greatest strength and the greatest weakness of threads
Carnegie Mellon Thread Programming is Hard! Thinking about all possible sequences of events in a computer system is at least error prone and frequently impossible Classical problem classes of concurrent programs: Races: outcome depends on arbitrary scheduling decisions elsewhere in the system Deadlock: improper resource allocation prevents forward progress Livelock / Starvation / Fairness: external events and/or system scheduling decisions can prevent sub-task progress
Deadlock In a multi-programmed environment, processes/threads compete for (exclusive) use of a finite set of resources Deadlock occurs when we have a cycle of dependencies. A is waiting on B and B is waiting on A deadlock!
Race Conditions Situations where multiple processes are writing or reading some shared data and the final result depends on who runs precisely when are called race conditions. A serious problem for most concurrent systems using shared variables! Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes. We must make sure that some high-level code sections are executed atomically. Atomic operation means that it completes in its entirety without worrying about interruption by any other potentially conflict-causing process.
Concurrent Access to Shared Data Suppose that two threads A and B have access to a shared variable Balance . THREAD A: THREAD B: Balance = Balance - 100 Balance = Balance + 200
Concurrent Access to Shared Data The statement Balance = Balance 100 is implemented by several machine level instructions such as: movl (%ecx),%eax subl %eax,%edx movl %eax, (%ecx) Similarly, Balance = Balance + 200 can be implemented by the following: movl (%ecx),%eax addl %eax,%ebx movl %eax,(%ecx)
Race Conditions Observe: In a time-shared system the exact instruction executionorder cannot be predicted Scenario 2: movl (%ecx),%eax subl %eax,%edx Context Switch movl (%ecx),%eax addl %eax,%ebx movl %eax,(%ecx) Context Switch movl %eax, (%ecx) Balance is decreased by 100 Scenario 1: movl (%ecx),%eax subl %eax,%edx movl %eax, (%ecx) Context Switch movl (%ecx),%eax addl %eax,%ebx movl %eax,(%ecx) Balance is increased by 100
Ornamental Garden Problem People enter an ornamental garden through either of two turnstiles. Management wish to know how many are in the garden at any time. Garden East Turnstile people West Turnstile The concurrent program consists of two concurrent threads and a shared counter object. from Concurrency: State Models & Java Programming, by J. Magee, J Kramer
Turnstile class class Turnstile extends Thread { NumberCanvas display; Counter people; The run() method exits and the thread terminates after Garden.MAX visitors have entered. Turnstile(NumberCanvas n,Counter c) { display = n; people = c; } public void run() { try{ display.setvalue(0); for (int i=1;i<=Garden.MAX;i++){ Thread.sleep(500); //0.5 second between arrivals display.setvalue(i); people.increment(); } } catch (InterruptedException e) {} } }
Counter class class Counter { int value=0; NumberCanvas display; Hardware interrupts can occur at arbitrary times. Counter(NumberCanvas n) { display=n; display.setvalue(value); } The counter simulates a hardware interrupt during an increment(), between reading and writing to the shared counter value. Interrupt randomly calls Thread.sleep() to force a thread switch. void increment() { int temp = value; //read value Simulate.HWinterrupt(); value=temp+1; //write value display.setvalue(value); } }
ornamental garden program The Counter object and Turnstile threads are created by the go() method of the Garden applet: private void go() { counter = new Counter(counterD); west = new Turnstile(westD,counter); east = new Turnstile(eastD,counter); west.start(); east.start(); }
ornamental garden program - display After the East and West turnstile threads have each incremented its counter 20 times, the garden people counter is not the sum of the counts displayed. Counter increments have been lost. Why?
concurrent method activation Java method activations are not atomic - thread objects east and west may be executing the code for the increment method at the same time. west PC east PC shared code increment: program counter program counter read value write value + 1
Solution? Synchronization Synchronization Most synchronization can be regarded as either: Mutual exclusion (making sure that only one process is executing a CRITICAL SECTION [touching a variable or data structure, for example] at a time), or as CONDITION SYNCHRONIZATION, which means making sure that a given process does not proceed until some condition holds (e.g. that a variable contains a given value) Competition Cooperation
critical section Code segment that needs to execution atomically (i.e. only one thread at a time, running to completion). If increment is a critical section, west is forced to wait for east to complete the increment. west PC east PC shared code increment: program counter program counter read value write value + 1
Mutual exclusion in Java Concurrent activations of a method in Java can be made mutually exclusive by prefixing the synchronized, which uses a lock on the object. method with the keyword We correctCOUNTERclass by deriving a class from it and making the increment method synchronized: class SynchronizedCounter extends Counter { SynchronizedCounter(NumberCanvas n) {super(n);} acquire lock synchronized void increment() { super.increment(); } } release lock
mutual exclusion - the ornamental garden Java associates a lock with every object. The Java compiler inserts code to acquire the lock before executing the body of the synchronized method and code to release the lock before the method returns. Concurrent threads are blocked until the lock is released.
Java Locks and Synchronization Every object has an intrinsic lock associated with it. 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. A thread is said to own 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.
Java Locks and Synchronization When a thread invokes a synchronized method, it automatically acquires the intrinsic lock for that method's object and releases it when the method returns (even if it returns via an exception) Statements inside a method can by synchronized as well. This is useful in cases where the methods of other objects are invoked. synchronized(this) { lastName = name; nameCount++; } nameList.add(name); }
Java synchronized statement Access to an object may also be made mutually exclusive by using the synchronized statement: synchronized (object) { statements } A less elegant way to correct the example would be to modify the Turnstile.run() method: synchronized(people) {people.increment();} Why is this less elegant ? Relying on the user to act responsibly. To ensure mutually exclusive access to an object, allobject methods should be synchronized.
Creating Lock Objects public class DualCounters { private long c1 = 0; private long c2 = 0; private Object lock1 = new Object(); private Object lock2 = new Object(); public void inc1() { synchronized(lock1) { c1++; } } public void inc2() { synchronized(lock2) { c2++; } } } Must be done with care!
Java Collections java.util.concurrent package includes a number of additions to the Java Collections Framework. BlockingQueue defines a first-in-first-out data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue. ConcurrentMap is a subinterface of java.util.Map that defines useful atomic operations. These operations remove or replace a key-value pair only if the key is present, or add a key-value pair only if the key is absent. Making these operations atomic helps avoid synchronization. The standard general-purpose implementation of ConcurrentMap is ConcurrentHashMap, which is a concurrent analog of HashMap.
Atomic Variables class SynchronizedCounter { private int c = 0; public synchronized void increment() { c++; } public synchronized void decrement() { c--; } public synchronized int value() { return c; } } import java.util.concurrent.atomic.AtomicInteger; class AtomicCounter { private AtomicInteger c = new AtomicInteger(0); public void increment() { c.incrementAndGet(); } public void decrement() { c.decrementAndGet(); } public int value() { return c.get(); } }
Condition Synchronization public class checkpoint { boolean here_first = true; synchronized void meet_up () { if (here_first) { } else { } }; }; here_first = false; wait(); notify(); here_first = true;
Condition Synchronization wait(), notify(), notifyall() We can call the wait() method of any Java object, which suspends the current thread. The thread is said to be "waiting on" the given object. Another thread calls the notify() method of the same Java object. This "wakes up" one of the threads waiting on that object. notifyall() methods wakes up all of the threads waiting on that object.
Producer/Consumer Problem Producer Consumer bounded size buffer (N) Competition Producer and Consumer execute concurrently but only one should be accessing the buffer at a time. Producer puts items to the buffer area but should not be allowed to put items into a full buffer Consumer process consumes items from the buffer but cannot remove information from an empty buffer Cooperation
public class BufferImpl<E> implements Buffer<E> { protected E[] buf; protected int in = 0; protected int out= 0; protected int count= 0; protected int size; public BufferImpl(int size) { this.size = size; buf = (E[])new Object[size];} public synchronized void put(E o) throws InterruptedException { while (count==size) wait(); buf[in] = o; ++count; in=(in+1) % size; notifyAll(); } public synchronized E get() throws InterruptedException { while (count==0) wait(); E o = buf[out]; buf[out]=null; --count; out=(out+1) % size; notifyAll(); return (o); } } Bounded Buffer
Bounded Buffer class Producer implements Runnable { Buffer<Character> buf; String alphabet= "abcdefghijklmnopqrstuvwxyz"; Producer(Buffer<Character> b) {buf = b;} public void run() { try { int ai = 0; while(true) { ThreadPanel.rotate(12); buf.put(alphabet.charAt(ai)); ai=(ai+1)%alphabet.length(); ThreadPanel.rotate(348); } }catch (InterruptedException e){} } } class Consumer implements Runnable { Buffer<Character> buf; Consumer(Buffer<Character> b) {buf = b;} public void run() { try { while(true) { ThreadPanel.rotate(180); Character c = buf.get(); ThreadPanel.rotate(180); } }catch(InterruptedException e){} } }
Bounded Buffer public class BoundedBuffer extends Applet { ThreadPanel prod; ThreadPanel cons; public void init() { super.init(); // Set up Display prod = new ThreadPanel("Producer",Color.blue); cons = new ThreadPanel("Consumer",Color.yellow); } public void start() { Buffer<Character> b = new DisplayBuffer(buffDisplay,5); // Create Thread prod.start(new Producer(b)); cons.start(new Consumer(b)); } public void stop() { prod.stop(); cons.stop(); } }
Semaphore Object public class Semaphore { private int value ; Semaphore(int n) { value = n;} public synchronized void v() { value = value + 1; notifyAll(); } public synchronized void p() throws InterruptedException { while (value == 0) wait(); value = value - 1; } } Semaphores were invented by Edsger Dijkstra. p() & v() came from the Dutch words for wait & signal. Useful for mutual exclusion.
Reader/Writer Version 1 public class ReaderWriter { public static void main(String[] args) { Semaphore mutual_exclusion = new Semaphore(1); Reader r1 = new Reader(1,mutual_exclusion); Reader r2 = new Reader(2,mutual_exclusion); Writer w1 = new Writer(1,mutual_exclusion); r1.start(); r2.start(); w1.start(); } } Multiple readers & writers to a shared object. Must ensure: 1 writers can t overlap 2 readers & writers can t overlap 3 allow multiple readers
public class Reader extends Thread { int id; Semaphore mutex; Reader(int c,Semaphore s) {id = c; mutex = s;} public void run() { int i = 0; while (i < 10) { try { mutex.p(); } catch (InterruptedException e) {} System.out.println(id + " start Reading"); try { Thread.sleep(500); } catch (InterruptedException e) {} System.out.println(id + " stop Reading"); mutex.v(); try {Thread.sleep(500); } catch (InterruptedException e) {} i = i + 1; } } } RW Version 1 Writer.java is similar
Version 1 notes Mutual exclusion achieved. However, this means only one reader at a time Continuing on the semaphore approach, can create a counter (for number of readers) and second semaphore Writer unchanged
public class ReaderWriter { public static void main(String[] args) { Semaphore mutual_exclusion = new Semaphore(1); Semaphore reader_mutex = new Semaphore(1); Counter num_readers = new Counter(0); Reader r1 = new Reader(1,mutual_exclusion, reader_mutex,num_readers); Reader r2 = new Reader(2,mutual_exclusion, reader_mutex,num_readers); Writer w1 = new Writer(1,mutual_exclusion); r1.start(); r2.start(); w1.start(); } } RW Version 2
public class Reader extends Thread { int id;Semaphore mutex; Semaphore read_mutex;Counter readers; Reader(int c,Semaphore s,Semaphore r,Counter num_r) { id = c; mutex = s; read_mutex=r; readers = num_r;} public void run() { int i = 0; while (i < 10) { read_mutex.p(); readers.incr(); if (readers.get() == 1) mutex.p(); read_mutex.v(); System.out.println(id + " start Reading"); Thread.sleep(500); System.out.println(id + " stop Reading"); read_mutex.p(); readers.decr(); if (readers.get() == 0) mutex.v(); read_mutex.v(); Thread.sleep(500); i = i + 1; } }} RW Version 2 Writer.java as in Version 1
class ReadWriteSafe implements ReadWrite { private int readers =0; private boolean writing = false; public synchronized void acquireRead() throws InterruptedException { while (writing) wait(); ++readers; } public synchronized void releaseRead() { --readers; if(readers==0) notifyAll(); } Multiple readers & writers to a shared object. Must ensure: 1 writers can t overlap 2 readers & writers can t overlap 3 allow multiple readers Reader/Writer Monitor Soln
public synchronized void acquireWrite() throws InterruptedException { while (readers>0 || writing) wait(); writing = true; } public synchronized void releaseWrite() { writing = false; notifyAll(); } } Reader/Writer Monitor Soln
