Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Concurrency Patterns

Concurrency Patterns

How to achieve concurrent processing and how to deal with it programmatically in elegant ways? Slides of a presentation given to the students of the software engineering course at U. Nijmegen.

Georgios Gousios

February 26, 2015

Transcript

66 slides
  1. Concurrency and Parallelism 4 Concurrency: doing many things at the

    same time 4 Requests from multiple clients on a server 4 Parallelism: doing one thing on multiple processors 4 Big matrix multiplication on CPUs/GPUs
  2. Common concurrency patterns 4 Processes 4 Threads 4 Event loops

    4 Actors 4 Asynchronous processing 4 Streams and reactive programming
  3. Processes 4 Same code, different memory space 4 Always have

    a parent, that forks(3) them # Shared memory (owned by the parent) children = [] pid = Process::fork if pid == 0 puts pid, a # Child specific memory do_work() else puts pid, a # Parent specific memory children += pid end children.each do |pid| Process.waitpid(pid, 0) end
  4. Processes — when to use 4 Simplest concurrency pattern 4

    fork(3) is expensive 4 Large work units, taking significant time to setup 4 (usually) not per request 4 Can be used in combination with finer- grained options (e.g. event loops)
  5. Threads 4 A self-executing unit of computation within a bigger

    group of computations 4 OS or application based 4 N x M mapping called ‘green threading’ 4 Access same memory with initiator 4 Need concurrency primitives to avoid races
  6. Producer/consumer queue 4 In memory blocking queue 4 Identical work

    items queue = Queue.new producer = Thread.new do 5.times do |i| queue << i end end consumer = Thread.new do while true do |i| value = queue.pop process value end end consumer.join
  7. Thread pool class Pool def initialize(size) @size = size @jobs

    = Queue.new @pool = Array.new(@size) do |i| Thread.new do Thread.current[:id] = i catch(:exit) do loop do job, args = @jobs.pop job.call(*args) end end end end def schedule(*args, &block) @jobs << [block, args] end end
  8. Fork/Join solve(problem): if problem is small enough: solve problem directly

    else: for part in subdivide fork subtask to solve part join all subtasks spawned in previous loop combine results from subtasks
  9. Threads — when to use 4 Reasoning about correctness with

    threads is hard 4 Especially when other isolation primitives (e.g. transactions) are involved 4 When one of the ready made patterns work 4 Better use higher level abstractions
  10. Event loops 4 Basic pattern 4 Wait on a file

    descriptor to emit a result 4 Run list of registered callbacks 4 More advanced 4 Wait on multiple file descriptors 4 Schedule background work in threads 4 An event loop is always single threaded
  11. Basic event loop fd = File.open("/var/log/messages.log") callbacks = [Proc.new{|x| print

    x}] while true do active = select([fd]) data = fd.read_lines callbacks.each{|x| x.invoke(data)} end
  12. Event loops — where is the concurrency? 4 I/O is

    10^4 - 10^6 slower than processing 4 On most systems, most time is spent waiting 4 select(3) or epoll(3) or kqueue(3) can handle thousands of open file descriptors
  13. Event loops — when to use 4 When I/O wait

    >> CPU wait 4 User interfaces 4 Network/Protocol servers 4 Excessive use on the client side leads to “callback hell” 4 Use function composition to streamline callbacks
  14. Actors 4 Unit of computation 4 3 axioms. An actor

    can: 4 Create new actors 4 Send messages to actors it knows about 4 Handle incoming messages
  15. Actors in practice 4 Actors maintain internal state 4 Promise:

    Only one thread can process msgs for a single actor at any time 4 Actors have mailboxes 4 Messages should be immutable 4 Actors are supervised by other actors
  16. Actors in practice 4 Work in a container 4 Actor

    registry 4 Manages assignment of actors to processors 4 Fault tolerance, supervision 4 Can be distributed (explicitly/implicitly) 4 Processing code be hot swapped
  17. A simple actor case class Msg(contents: String) class ActorExample extends

    Actor { def receive = { case Msg(contents) => print(contents) case _ => "Don't know what to do" } }
  18. Actor with state case object Add case object Added class

    ActorExample extends Actor { var state = 0 def receive = { case Add => state += 1 sender ! Added case _ => "Don't know what to do with it" } }
  19. Orchestrating actors val f1 = ask(actor1, msg1) val f2 =

    ask(actor2, msg2) val f3 = for { a ← f1.mapTo[Int] b ← f2.mapTo[Int] c ← ask(actor3, (a + b)).mapTo[Int] } yield c f3 onSuccess { case _ => println(“Result: ” + result) }
  20. Failure management 4 Let it crash 4 Supervisor knows an

    exception is thrown 4 Respawns crashed actor 4 caveat: actor mailbox?
  21. Effects Effects is what computations produce other than the actual

    result 4 State modification 4 Exceptions 4 Latency 4 Nulls Effects complicate reasoning. We must make them explicit.
  22. Monads A type with 3 methods: 4 Type constructor: The

    monad name 4 A unit function: t -> M t 4 A flatMap function: M t -> (t -> M u) - > M u trait Monad[M[_]] { def unit[S](a: S) : M[S] def flatMap[S, T] (m: M[S])(f: S => M[T]) : Monad[T] }
  23. Popular Monads to deal with effects 4 Nulls: Option[T] 4

    Exceptions: Try[T] 4 Latency: Future[T]
  24. Monads — exception handling Exception handling with the Try Monad

    object Converter extends App { def toInt(a: String): Try[Int] = Try{Integer.parseInt(a)} def toString(b: Int): Try[String] = Try{b.toString} val a = toInt("4").flatMap(x => toString(x)) println(a) val b = toInt("foo").flatMap(x => toString(x)) println(b) }
  25. Monads — exception handling Equivalent code in Java public class

    Converter { public Integer toInt(String a) throws NumberFormatException {return Integer.parseInt(a)} public String toString(Integer a) throws NullPointerException {return b.toString();} public static void main(String[] args) { try{ Integer five = toInt('5'); try { return toString(five); } catch(NullPointerException e) { //baaah } } catch(NumberFormatException r) { //ooofff } } }
  26. Futures A placeholder for a value that may become available

    //Blocks val amazon = new Amazon().login(username, password) // Does not block val search : Future[List[Product]] = future { amazon.search("lego") }
  27. Futures class Amazon { def login(a: String, b: String): Amazon

    = ??? def search(s: String): Future[List[String]] = Future {???} } class Main extends App { var amazon = new Amazon().login(username, password) val result = amazon.search("lego") } Quiz: How can we make the code non- blocking?
  28. Future compositions flatMap is our friend class Amazon { def

    login(a: String, b: String): Future[Amazon] = Future{???} def search(s: String): Future[List[String]] = Future {???} } class Main extends App { val amazon = new Amazon() val result = amazon.login("a", "b") .flatMap(a => a.search("foo")) }
  29. Async/Await async/await convert sequential code to Continuation Passing Style class

    AmazonAsync(a: String, b: String) { private def login(a: String, b: String): Future[Amazon] = Future{???} def search(s: String): Future[List[String]] = async { val login = await(this.login(a, b)) searchAPICall(login, s) } }
  30. Without Async/Await class AmazonAsync(a: String, b: String) { private def

    login(a: String, b: String): Future[Amazon] = Future{???} def search(s: String): Future[List[String]] = async { val login = await(this.login(a, b)) searchAPICall(login, s) } // Probably wrong code def searchNotAsync(q: String) : Future[List[String]] = { val login = this.login(a, b) var result : Future[List[String]] = null login.onComplete(l => result = searchAPICall(l.get, q)) Await.result(login, Duration.Inf) result } }
  31. Dealing with errors Make effects explicit in the type system

    class Amazon { def login(a: String, b: String): Future[Try[Amazon]] = Future{Try{throw new Throwable()}} def search(s: String): Seq[Future[Try[String]]] = List(Future{Try{"item1"}}, Future{Try{"item2"}}) }
  32. Dealing with errors class Amazon { def login(a: String, b:

    String): Future[Try[Amazon]] = Future{Try{throw new Throwable()}} def search(s: String): Seq[Future[Try[String]]] = List(Future{Try{"item1"}}, Future{Try{"item2"}}) } Quiz: should search return 4 Seq[Future[Try]] 4 Future[Seq[Try]] 4 Future[Try[Seq]]
  33. Producing multiple values We have seen how we deal with

    asynchrony in functions that produce one value. How do we deal with functions producing multiple values? Is Future[List[T]] the way to go?
  34. Iterables and Iterators trait Iterable[T] { def iterator : Iterator[T]

    } trait Iterator[T] { def next(): T def hasNext(): Boolean }
  35. Iterables and Iterators trait Iterable[T] { def iterator : Iterator[T]

    } trait Iterator[T] { def next(): T def hasNext(): Boolean } next() represents a computation that blocks!
  36. Iterables and Iterators trait Iterator[T] { def next(): T def

    hasNext(): Boolean } Idea: what if we could pass a callback to next()?
  37. Observables and Observers trait Observable[T] { def subscribe(observer: Observer[T]) :

    Subscription } trait Observer[T] { def onNext(value: T): Unit def onError(error: Throwable) : Unit def onCompleted() : Unit }
  38. Rx - Reactive Programming 4 Express computations as a series

    of transformations on Observables 4 Libraries in all programming languages def hello(names: String*) { Observable.from(names).subscribe { n => println(s"Hello $n!") } }
  39. Rx example trait Result case class Open(s: Socket) extends Result

    case class Closed(port: Int) extends Result // Types Observable.from(1 to 65536).flatMap( // Observable[Int] port => // f: Int => Observable[Result] Observable.from( future { try { Open(new Socket(host, port)) } catch { case e: Exception => Closed(port) } } ) //Observable[Result] ).subscribe( res => res match { case y: Open => println("Port " + y.s.getPort + " is open") y.s.close case y: Closed => _ }, err => err.printStackTrace(), () => println("Done.")) } )
  40. Rx zip example val o = Observable.zip( imageService.getUserPhoto(id), imageService.getPhotoMetadata(id), {(photo,

    metadata) => createPhotoWithData(photo, metadata)}) o.subscribe({photoWithData => showPhoto(photoWithData)});
  41. Rx groupBy example Observable(keyboard). groupBy{x : String => x}. subscribe

    { group : Observable[(String, Observable[String])] => var keyPresses = 0 group.subscribe{key : String => println(s"You pressed $key for $keyPresses times") } }
  42. Rx concurrency 4 Concurrency both when subscribing and observing 4

    Concurrency mechanism abstracted as Scheduler imageService.getImage(url) // Returns Observable[Image] .subscribeOn(Schedulers.io) .observeOn(AndroidSchedulers.mainThread) .subscribe{bitmap => myImageView.setImageBitmap(bitmap)};
  43. Further reading 1. P. Walder, Monads for functional programming 2.

    E. Meijer, Your mouse is a database 3. M. Odersky, E. Meijer and R. Kuhn, Reactive Programming MOOC 4. Akka Team, Akka Documentation 5. T. Hughes-Croucher and M. Wilson, Node: Up and Running, Ch3
  44. Acks 4 Event loop figure from SO question 21596172 4

    Latency numbers every programmer should know by Colin Scott 4 All Rx marble diagram figures are from reactivex.io

More Decks by Georgios Gousios

Other Decks in Technology