Parallel and Concurrent Programming Part 2
CSCI 334: Principles of Programming Languages
Williams College�Spring 2023
Deterministic Parallelism
Nondeterministic Concurrency
Thread 1
Thread 2
data
Amazon.com
network
Thread 3
Thread 4
Shared-Memory Concurrency
Account Monitor [Hoare]
class Account {
private int balance;
public synchronized void add(int n) {
balance += n;
}
public synchronized String toString() {
return "balance = " + balance;
}
}
acquire lock of
receiver object
Thread States
New
Runnable
Running
Done
run() ends
start
scheduled
descheduled
Self control
JVM Scheduler
External control
Blocked
join
lock acquire
wait
sleep
join complete
lock released
notifyAll
sleep
interrupted
interrupted
interrupted
Safe Buffer Ops
class Buffer<T> {
private T[] elementData;
private int elementCount;
private int start;
private int end;
synchronized void insert(T t) throws InterruptedException {
while (elementCount == elementData.length) wait();
end = (end + 1) % elementData.length;
elementData[end] = t;
elementCount++;
notifyAll();
}
synchronized T delete() throws InterruptedException {
while (elementCount == 0) wait();
T elem = elementData[start];
start = (start + 1) % elementData.length;
elementCount--;
notifyAll();
return elem;
}
}
...
Concurrency Control
Deadlock
class Account {
int balance;
synchronized void add(int n) {
balance += n;
}
synchronized void transfer(Account other,
int n) {
balance -= n;
other.add(n);
}
acquire(a)
acquire(b)
b.bal -= n
Thread 1
Thread 2
a.bal -= n
wait for b
wait for a
Atomic As a Language Feature
class Account {
int balance;
atomic void add(int n) {
balance += n;
}
atomic void transfer(Account other, int n) {
balance -= n;
other.add(n);
}
Atomicity Demo
Go Language
Goroutines and Pipelines
var done = make(chan bool)
var msgs = make(chan int)
func produce () {
for i := 0; i < 1000; i++ {
msgs <- i
}
done <- true
}
func consume(c string) {
for {
msg := <- msgs
fmt.Printf("%s %d\n", c, msg)
}
}
func main () {
go produce()
go consume("A")
go consume("B")
<- done
}
A
B
C
Network
Simple Actor
class SimpleActor(val verb: String) extends Actor {
def act() = {
for (i <- 1 to 5) {
println("I'm " + verb + "ing");
Thread.sleep(1000);
}
}
start();
}
Note: the default scala in lab does not support actors – see HW 10 handout for details...
Parroting Actor
class Parrot extends Actor {
def act() = {
loop {
react {
case msg => println("Received: " + msg);
}
}
}
start();
}
...
val p = new Parrot();
p ! “moo”;
Matching Messages
abstract class Message { }
case class Hello() extends Message { }
case class Num(val n : Int) extends Message { }
class FussyParrot extends Actor {
def act() = {
loop {
react {
case Hello => println("Hello to you too");
case Num(n) => println("Number " + n);
}
}
}
start();
}
Bank Account
abstract class Message { }
case class DepositAmt(n : Int) extends Message;
case class GetBalance() extends Message;
class Account(var balance : Int) extends Actor {
def act() = {
loop {
react {
case DepositAmt(i) => balance = balance + i;
case GetBalance() => sender ! balance;
}
}
}
start();
}
Bank Account
val a = new Account(0);
a ! DepositAmt(100);
val balance = a !? GetBalance();
Receive, sender, rendezvous...
class PickANumber extends Actor {
def act() = {
var done = false;
println("Send me an upper bound...");
val num = receive { case n : Int => Random.nextInt(n); }
while (!done) {
receive {
case i : Int if (i == num) => sender ! "You Win."; done = true;
case i : Int if (i < num) => sender ! "Too Low.";
case i : Int if (i > num) => sender ! "Too High.";
}
}
println("Done...");
}
start()
}