CSE 3302Lecture 19: Concurrency11 Nov 2010Nate NystromUTAToday• Concurrency –!mostly in Java• Some good practices and design principles for using concurrency features of Java• Later: language mechanisms that enforce some of these principlesConcurrent programming in Java• Source: Doug Lea, SUNY OswegoConcurrent programming is hard• Sequential programs:•one path through the program for a given input•relatively straightforward to reason about•Concurrent programs:•multiple, possibly infinite, paths through the programConcurrent programming is hard• Safety issues• race conditions• message ordering problems• transaction violations• Liveness issues• deadlock• starvation• fairness• Composition issues• Higher resource usageSo why do it?So why do it?• parallelism• exploit multiprocessors, overlapping I/OSo why do it?• parallelism• exploit multiprocessors, overlapping I/O• availability• minimize response lag, maximize throughputSo why do it?• parallelism• exploit multiprocessors, overlapping I/O• availability• minimize response lag, maximize throughput• modeling• simulating autonomous objects, animationSo why do it?• parallelism• exploit multiprocessors, overlapping I/O• availability• minimize response lag, maximize throughput• modeling• simulating autonomous objects, animation• protection• isolating activities in threadsApplications• I/O bound tasks• GUIs• Hosting foreign code• Server daemons• SimulationsConcurrent programming•Concurrency is a conceptual property of software•Concurrent programs might or might not...• operate over multiple CPUs• multiple CPUs => parallel programming• share access to resources• distributed programming =>!no sharingWriting concurrent programs• What do you need to consider?• safety • “bad things don’t happen”• liveness• “good things eventually happen”• efficiency, performance• reusability, compositionality• “if A is safe (live, fast) and B is safe (live, fast), are A and B safe (live, fast) together?”Safety• “Bad things do not happen”• Prevent interference between concurrent activities• storage conflicts, race conditions• transaction violationsLiveness• “Good things eventually happen”• Ensure activites make progress• deadlock• livelock• fairnessSystem = objects + activities• Concurrent systems built from objects and activities• Objects• ADTs, monitors, remote objects, components, ...• Activities• messages, call chains, threads, sessions, transactions, workflows, ...Safe objects, live activities• Keep objects safe• ensure objects are consistent• Keep activities live• ensure activities make progressSafe objects• Perform method actions only when in consistent states•Impossible to predict consequences of actions attempted when objects are temporarily inconsistent• read/write, write/write conflicts• invariant failures• random-looking externally visible behavior• Must balance with liveness goals• clients want simultaneous access to servicesState inconsistency examples• Draw a figure while moving• could draw at old x, new y• could draw at location objects was never at• Withdraw from bank account during a transfer• could overdraw account• money could disappear• Read storage location while being written• could read some old bytes, some new• could get a nonsense valueLive activities• Every activity should make progress toward completion• every called method should eventually execute• Related to efficiency• every called method should execute ASAP• Activity might not complete if• object does not accept message• method blocks waiting for condition that never happens• insufficient or unfairly shared resources• failuresExtremes• Safety first• Ensure each class is safe, then try to improve liveness• => slow, deadlock prone code• Liveness first• => buggy code full of racesConcurrent OO programming• Always a part of OO• Simula67 was concurrent• But not a factor in rise of OO in 80s• Reemerged with Java• Models:• active vs. passive objectsActive objects• Every object has a single thread of control•Actions are reactive responses to messages• may delay handling• Messages are one-way• Extensions:• asynchronous vs. synchronous messages• queueing• multicastingPassive objects• Objects are passive data• A thread can invoke a method on an object, method code runs in same thread as the callerJava• Dumb active objects• java.lang.Thread•run() method• Passive objects• participate in multiple threads• can protect themselves from conflicting activities (synchronized)• can create and control new threadsJava concurrency support•Thread class represents state of an independent activity• methods to start, sleep, etc• weak scheduling guarantees• each Thread is a member of a ThreadGroup for control and bookkeeping• code that runs in a thread defined by Runnable•synchronized methods and blocks control atomicity via locks•monitor methods in Object control suspension and resumption• wait, notifyPatterns for safe objects• immutability• avoid interference by avoiding change• locking• guarantee exclusive access• state dependence• containmentImmutability• Avoid interference by avoiding change• Immutable objects never change state• Actions on immutable objects are always safe and live• Applications:• objects representing values• objects providing stateless services• pure functional programming style• Methods dealing with immutable aspects of state do no require lockingStateless server objectsclass StatelessAdder { int addOne(int a) { return a + 1; }}• No special concurrency concerns• no per-instance state => no storage conflicts• no rep invariants => no invariant failures•any number of instances of addOne can run concurrently => no liveness problems• no interaction with other objectsFreezing state on constructionclass ImmutableAdder { private final int offset; ImmutableAdder(int x) { offset = x; } int add(int i) { return i + offset; }}• No safety or liveness concerns• Java finals enforce most senses of immutability• Often uses for values:•java.lang.String, java.lang.Integer, java.awt.Color•not: java.awt.PointLocking•Locking is a simple message accept mechanism• acquire object lock on entry to method, release on return• Precludes storage conflicts,
View Full Document