Concurrent ParadigmsJorge OrtizCS94SIConcurrency is hardParadigm:Shared Memory & LocksMemoryExecutionThreadMemoryThreadsThreadsProblems?Problem #1Race conditionsShared Mutable StateThreadsThreadsRace conditionSegfaultSegfaultChecking whether build environment is sane ... build environment is grinning and holding a spatula. Guess not.Fix #1LocksShared Mutable StateThreadsThreadsRace conditionLockShared Mutable StateThreadsThreadsRace conditionCoarse lockProblem #2Blocking/contentionShared Mutable StateThreadsThreadsRace conditionFine-grainedlocksProblem #3OverheadSolutions #2 & #3??? ... Nothing, reallyIt’s a trade-offProblem #4DeadlockShared Mutable StateDeadlockThreadsThreadsSolution #4Rigorous adherence to complicated lock orderProblem #5Doesn’t composeProblem #6Hard to debugLanguages•Well... very popularParadigm:ActorsActor PrinciplesActor Principles•No shared, mutable state•Actor Principles•No shared, mutable state•All mutable state is private•Actor Principles•No shared, mutable state•All mutable state is private•All shared state is immutable•Actor Principles•No shared, mutable state•All mutable state is private•All shared state is immutable•Communicate via immutable, asynchronous message-passing•Actor Principles•No shared, mutable state•All mutable state is private•All shared state is immutable•Communicate via immutable, asynchronous message-passing•Messages, threads are extremely lightweightActor Components•Actors: Very lightweight threads•Messages: Immutable (hence, lightweight)•Mailboxes: Asynchronous, non-blocking queuesPrivate Mutable StateActorsMailboxesMessagesIn Erlangstart() -> loop(0).loop(Sum) -> receive {increment, Count} -> loop(Sum + Count); reset -> loop(0); {counter, Pid} -> Pid ! {counter, Sum}, loop(Sum); end.In Scala// We need to define our messages firstcase class Increment(count: Int)case object Resetcase class ReportTotal(a: Actor)case class ReportingTotal(sum: Int)In Scalaobject Counter extends Actor { var sum = 0 def act() = while(true) { receive { case Increment(cnt) => sum += cnt case Reset => sum = 0 case ReportTotal(actor) => actor ! ReportingTotal(sum) } }}In Scala// One hundred actors are defined,// each sends one messagefor (i <- (1 to 100)) { actor { Counter ! Increment(i) }}// Ask for the total and print itCounter ! ReportTotal(this)receive { case ReportingTotal(sum) => println(sum)}In Scalaobject Counter extends Actor { var sum = 0 def act() = while(true) { receive { case Increment(cnt) => sum += cnt case Reset => sum = 0 case ReportTotal => reply(sum) } }}In Scala// One hundreds actors are defined,// each sends one messagefor (i <- (1 to 100)) { actor { Counter ! Increment(i) }}// Ask for the total and print itCounter !? ReportTotal match { case sum: Int => println(sum)}Implementation// Subclasses must implement the abstract// “act” methodclass Actor { def !(msg: Any): Unit = ... def !?(msg: Any): Any = ... def act(): Unit}Implementation•Java threads are too heavy (only scales to a few thousand threads)•Scala actors are much lighter weight (scales to millions of actors)•See: “Actors that Unify Threads and Events”, Haller and OderskyLessons•Scala’s flexible syntax allows for a remarkably faithful implementation of Erlang’s concurrency primitives as a Scala library and not a language primitive•We lose some type safety•We can use typed Channels to partly remedy thisAdvantages•Much easier to reason about than locks and shared memory•Proven to be reliable and scale to large systems•Don’t care if actors are local or remote•Implemented as a library, not core part of languageDisadvantages•Overhead•Implemented as a library, not core part of VMLanguages•Erlang•Actalk, Actra (Smalltalk)•SALSA (Java extension)•ScalaParadigm:Fork/JoinFork/Join// PSEUDOCODEdef solve(p: Problem): Result { if (problem.size < THRESHOLD) solveSequentially(p) else { INVOKE-IN-PARALLEL { left = solve(extractLeft(p)); right = solve(extractRight(p)); } combine(left, right); }}Advantages•Easy to reason about•Easy to implementDisadvantages•Primitive framework•Not all tasks are trivially parallelizableLanguages•Java 7•Almost trivial in ScalaIn Scaladef future[A](p: => A): Unit => A = { val result = new SyncVar[A] spawn { result.set(p) } () => result.get}In Scaladef solve(p: Problem): Result { if (problem.size < THRESHOLD) solveSequentially(p) else { left = future(solve(extractLeft(p))) right = solve(extractRight(p)) combine(left(), right) }}Paradigm:Transactional MemoryTransactional Memory•Hardware Transactional Memory•Software Transactional MemoryTransactional Memory// insert a node into a// doubly-linked listatomically { newNode.prev = node newNode.next = node.next node.next.prev = newNode node.next = newNode}Advantages•Easier to reason about•Much more composableDisadvantages•Doesn’t support irreversible operations•Tricky to implementLanguages•Gemstone (Smalltalk)•Haskell•Clojure•coThreads (OCaml)•Scala (unofficial, experimental)•(various C, C++, Java, C# implementations)Paradigm:Join CalculusJoin Calculus// Unbounded bufferclass Buffer { def get(): String & def put(s: String): Async = { s }}Join Calculus// One-place bounded bufferclass OnePlaceBuffer { empty() def put(s: String): Unit & private def empty(): Async = { has(s) } } def get(): String & private def has(s: String): Async = { s }}Languages•JoCaml•Polyphonic C#, Cω•Join Java•Boost.Join•scala.concurrent.jolib?