Models for Concurrent Programming


Models for Concurrent Programming Tobias Ivarsson hacker @ Neo Technology tobias@neotechnology.com twitter: @thobe web: http://thobe.org/ http://neo4j.org/ Common misconceptions 2 More threads == More throughput 3 Finite number of cores 4 Other limiting factors f.ex. I/O is only one pipe 5 Locking always impedes performance 6 7 Concurrency on the track, only one in the station Amdahl’s law 8 Speedup ≤ 1 F + 1-F N N: Number of processors F: Serial fraction Throughput with synchronized regions 9 Throughput: 3 Throughput with synchronized regions 9 wait... Throughput: 6 Throughput with synchronized regions 9 wait... wait... Throughput: 9 Throughput with synchronized regions 9 wait... wait... wait... Throughput: 11 10 wait... wait... wait... wait... wait... wait... wait... wait... wait... wait... wait... Throughput: 11 Throughput with synchronized regions 11 wait... wait... wait... wait... wait... wait... wait... Throughput: 11 Throughput with synchronized regions The fundamentals 12 ๏Threads ๏Mutual exclusion synchronization and locks ๏Java Memory Model read/write barriers & publication The Java Memory Model What you need to know ๏ Visibility / Publication of objects/fields ๏ (Un)Acceptable out-of-order behavior i.e. guarantees about ordering ๏ Implementations based on the hardware MM of the target platform 13 JSR 133 Concurrency abstractions 14 Java as we know it 15 Threads 16 ๏ Abstract the line of excution from the CPU(s) ๏ Provided by most (all mainstream) operating systems ๏ CPU execution can continue on another thread if one thread blocks ๏ Increases CPU utilization Monitors 17 synchronized (someMonitor) { // single threaded region } read barrier write barrier Volatile read/write 18 19 class Thing { volatile String name; String getName() { return this.name; } void setName( String newName ) { this.name = newName; } } read barrier write barrier ๏Guarantees visibility: always read the latest value ๏Guarantees safe publication: no re-ordering of pre-write ops with post-write ops Monitors 20 synchronized (someMonitor) { // single threaded region } read barrier write barrier ๏Writes may not be reordered across the end ๏Reads may not be reordered across the start java.util.concurrent 21 ConcurrentMap map = new ConcurrentHashMap(); 22 ๏Adds atomic operations to the Map interface: - putIfAbsent(key, value) - remove(key, value) - replace(key,[oldVal,]newVal) - but not yet putIfAbsent(key, #{makeValue()}) ๏CHM is lock striped, i.e. synchronized on regions List list = new CopyOnWriteArrayList(); 23 ๏Synchronize writers, unrestricted readers ๏Good for: #reads >> #writes ๏Readers get snapshot state: gives stable iteration ๏Volatile variable for immutable state to ensure publication public class CopyOnWriteArrayList private volatile Object[] array = new Object[0]; public synchronized boolean add(T value) { Object[] newArray = Arrays.copyOf(array, array.length+1); newArray[array.length] = value; array = newArray; // write barrier return true; } // write barrier public Iterator iterator() { return new ArrayIterator(this.array); // read barrier } private static class ArrayIterator implements Iterator { // I’ve written too many of these to be amused any more ... } 24 25 ExecutorService executor = new ThreadPoolExecutor(); executor.submit(new Runnable() { void run() { doWork(); } }); ๏Focus on tasks - not threads ๏Mitigate thread start/stop overhead ๏Ensure a balanced number of threads for the target platform java.util.concurrent.locks 26 27 LockSupport.park(); // currentThread LockSupport.unpark(Thread t); ๏The thread will “sleep” until unparked ๏Although unpark-before-park marks the thread as unparked, returning from park immediately ๏... and there’s still the chance of spurious wakeups ... ๏Too low level for most people Lock lock = new ReentrantLock(); ReadWriteLock rwLock = new ReentrantReadWriteLock(); Lock read = rwLock.readLock(); Lock write = rwLock.writeLock(); lock.lock(); try { doWork() } finally { lock.unlock(); } if ( lock.tryLock() ) try { doWork() } finally { lock.unlock(); } else backOffAndTryAgainLater(); 28 // Two related locks java.util.concurrent.atomic 29 30 AtomicReference ref = new AtomicReference(); AtomicReferenceArray array = new AtomicReferenceArray(); 30 AtomicReference ref = new AtomicReference(); AtomicReferenceArray array = new AtomicReferenceArray(); class MyAtomicThingReference { volatile Thing thing; static AtomicReferenceFieldUpdater THING = newUpdater(...); Thing swap( Thing newThing ) { return THING.getAndSet( this, newThing ); } }๏Atomic* gives you compareAndSet() ๏Atomic*Updater saves indirection: ๏One less object header - less memory ๏One read-address-get-object operation: better cache locality Java of Tomorrow (actually Today, JDK7 is already out) 31 ForkJoin 32 ๏More “advanced” Executor ๏Assumes/requires more of the tasks it runs ๏Tasks first split into multiple sub-tasks, push on stack ๏Idle workers “steal” work from the bottom of the stack of other workers Models not in Java today 33 ParallelArray 34 35 ParallelArray students = ... double highestScore = students .filter( #{ Student s -> s.gradYear == 2010 } ) .map( #{ Student s -> s.score } ) .max(); Transactional Memory 36 37 void transfer( TransactionalLong source, TransactionalLong target, long amount ) { try ( Transaction tx = txManager.beingTransaction() ) { long sourceFunds = source.getValue(); if (sourceFunds < amount) { throw new InsufficientFundsException(); } source.setValue( sourceFunds - amount ); target.setValue( target.getValue() + amount ); tx.success(); } } Actors 38 39 class SimpleActor extends Actor { var state def receive = { case Get => self reply state case Set(newState) => state = newState } } val response = simple !! Set( "new state" ) This means “send message” Scala Parallel Collection Framework 40 Efficient Collection splitting & combining 41 Efficient Collection splitting & combining 41 Efficient Collection splitting & combining 41 Efficient Collection splitting & combining 41 Splittable maps 42 15 1745 82 Splittable maps 43 8 5 15 2 174 Hash tries 44 ๏Similar performance to hash tables ๏Splittable (like arrays) ๏Memory (re)allocation more like trees ๏No resizing races Clojure 45 Immutable by default 46 Thread local (and scoped) override 47 48 (def x 10) ; create a root binding (def x 42) ; redefine the root binding (binding [x 13] ...) ; create a thread local override Transactional memory (ref) and (dosync ...) 49 50 (def street (ref)) (def city (ref)) (defn move [new-street new-city] (dosync ; synchronize the changes (ref-set street new-street) (ref-set city new-city))) ; will retry if txn fails due to concurrent change (defn print-address [] (dosync ; get a snapshot state of the refs (printf "I live on %s in %s%n" @street @city))) (atom) easier API for AtomicReference 51 52 (defstruct address-t :street :city) (def address (atom)) (defn move [new-street new-city] (set address (struct address-t new-street new-city))) (defn print-address [] (let [addr @address] ; get snapshot (printf "I live on %s in %s%n" (get addr :street) (get addr :city)))) Explicit asynchronous updates 53 (agent) A simpler cousin to actors 54 55 (def account (agent)) (defn deposit [balance amount] (+ balance amount)) (send account deposit 1000) http://neotechnology.com we’re hiring http://neotechnology.com/about-us/jobs Questions?
还剩63页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

patrick002

贡献于2015-01-03

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf