Concurrent Programming
From the first day of the semester forward we expect students (you) to visit this page once per 24 hours.
Wednesday, April 24th, 2024 2:12:00pm
I pushed a couple small fixes/improvements to the E3 and E4 test harnesses. Make sure to pull periodically to ensure you are using the most up-to-date version.
Monday, April 22nd, 2024 11:53:00am
The test harness for milestone E4 is available for your use on github. The repo includes some fresh json configurations in the json-tests directory. Please see the Readme in the repo for instructions on their use.
Tuesday, April 16th, 2024 3:39:00pm
The test harnesses for milestones E2 and E3 are available for your use on github. Please see the Readme in each repo for instructions on their use.
Also, the input configurations for milestone E3 didn’t make it into your test results, so (Fixed) here they are.
Sunday, April 14th, 2024 9:43:00pm
You may wish to use the provided unit tests as a basic check
of your milestone E4 —
Friday, April 12th, 2024 9:03:00am
In class we will be taking a look at the language Syndicate. For students that wish to try their hand or play with examples, the instructions below should suffice to get up and running:
Install Racket.
Install Syndicate ("Classic") from a terminal with the command raco pkg install syndicate-classic.
Peruse the (limited) documentation.
Wednesday, April 10th, 2024 9:13:00pm
The next milestone is now available—
Saturday, April 6th, 2024 2:27:00pm
You may wish to use the provided unit tests as a basic check of
your milestone E3 —
Saturday, April 6th, 2024 9:28:00am
I created a repo on the enterprise github with the code from yesterday’s class that you should be able to access here.
Thursday, April 4th, 2024 2:27:00pm
The test results for milestone E2 —
Sunday, March 31st, 2024 9:13:00pm
The next milestone is now available—
Tuesday, March 26th, 2024 2:04:00pm
I created a repo on the enterprise github with the code from class, that you should be able to access here.
Sunday, March 24st, 2024 3:53:00pm
The next milestone is now available—
Friday, March 22nd, 2024 1:18:00pm
iex --erl "+P 10000000" -S mix |
The code from today’s class is below:
defmodule ConcurrentMapRedux do |
# create a concurrent map server and return its PID |
def new do |
spawn fn -> run_server() end |
end |
|
# send a request to the server and wait for its response |
def map(server, list, function) do |
send server, {:run_map, list, function, self()} |
receive do |
{:result, result} -> result |
end |
end |
|
# Receive map requests and create "middle man" workers to process them |
def run_server do |
receive do |
{:run_map, list, function, reply_to} -> |
spawn fn -> run_map(list, function, reply_to) end |
run_server() |
end |
end |
|
# Create workers for applying the function, |
# collect the results, |
# and send them to reply_to |
def run_map(list, function, reply_to) do |
parent = self() |
for {elem, idx} <- Enum.with_index(list) do |
spawn fn -> worker_fun(elem, idx, function, parent) end |
end |
result = assemble_list length(list), [] |
send reply_to, {:result, result} |
end |
|
# Receive :ok messages, accumulating the results |
# expected_results - number of :ok messages to receive |
# accum: results received so far, with their index |
# returns: the resulting list |
def assemble_list expected_results, accum do |
if expected_results == 0 do |
accum |
|> Enum.sort_by(fn {elem, idx} -> idx end) |
|> Enum.map(fn {elem, idx} -> elem end) |
else |
receive do |
{:ok, elem, idx} -> |
assemble_list(expected_results - 1, [{elem, idx} | accum]) |
end |
end |
end |
|
def worker_fun(elem, idx, function, parent) do |
send parent, {:ok, function.(elem), idx} |
end |
end |
Tuesday, March 19th, 2024 3:56:00pm
A few followups to today’s lecture:
I updated the IntelliJ setup info (—
Students interested in learning more about the basics of Elixir concurrency may wish to read chapter 15 (specifically, 16.1) of Programming Elixir (Readings). The Elixir section on processes in the Elixir guide is also a useful reference, as well as the additional functions in the standard library’s Process module.
Finally, the bank account module from today’s lecture is reproduced below.
defmodule BankAccount do |
|
def new_account(initial_balance) do |
spawn fn -> run_account(initial_balance) end |
end |
|
def run_account(balance) do |
receive do |
{:get, reply_to} -> |
send reply_to, {:balance, balance} |
run_account(balance) |
{:deposit, amount} -> |
run_account(balance + amount) |
end |
end |
|
def get(account) do |
send account, {:get, self()} |
receive do |
{:balance, balance} -> |
balance |
end |
end |
|
def deposit(account, amount) do |
send account, {:deposit, amount} |
end |
|
def run_client(account, tell_done) do |
for _i <- 1..1000 do |
deposit(account, 1) |
end |
send tell_done, :done |
end |
|
def new_client(account, tell_done) do |
spawn fn -> run_client(account, tell_done) end |
end |
|
def run_demo() do |
account = new_account(0) |
_client1 = new_client(account, self()) |
_client2 = new_client(account, self()) |
receive do |
:done -> receive do |
:done -> nil |
end |
end |
get account |
end |
|
end |
Sunday, March 17st, 2024 9:37:00pm
The first Elixir milestone is now available—
Friday, March 1st, 2024 6:17:00pm
Students interested in learning more about the Java Memory Model may wish to read chapter 16 (specifically, 16.1) of Java Concurrency in Practice (Readings). This blog post also provides a nice introduction to memory models.
It turns out the Linus quote I was thinking of in class today is from 2002! You can read the thread starting here.
Wednesday, February 28th, 2024 12:18:00pm
The description for Milestone 6 —
Monday, February 26th, 2024 2:09:00pm
The description for Milestone 6 —
Saturday, February 24th, 2024 1:10:00pm
The interface archive for Milestone 6 —
Friday, February 23rd, 2024 12:13:00pm
Students interested in learning more about concurrency and parallelism with respect to performance may wish to read chapter 11 (specifically, 11.1, 11.2, and 11.3) of Java Concurrency in Practice (Readings).
Friday, February 23rd, 2024 9:46:00am
The following starter code may come in handy during today’s lecture:
import java.util.Arrays; |
import java.util.Comparator; |
import java.util.Random; |
import java.util.stream.IntStream; |
|
public class SeqMergeSort { |
|
public static <T> void sort(T[] items, Comparator<T> comp) { |
sortBetween(items, comp, 0, items.length); |
} |
|
public static <T> void sortBetween(T[] items, Comparator<T> comp, int start, int end) { |
if (end - start <= 1) { |
return; |
} |
var mid = start + (end - start) / 2; |
sortBetween(items, comp, start, mid); |
sortBetween(items, comp, mid, end); |
merge(items, comp, start, mid, end); |
} |
|
public static <T> void merge(T[] items, Comparator<T> comp, int start, int mid, int end) { |
var current1 = start; |
var current2 = mid; |
T[] tmp = (T[]) new Object[end - start]; |
for (int i = 0; i < tmp.length; i++) { |
if (current1 == mid) { |
tmp[i] = items[current2++]; |
} else if (current2 == end) { |
tmp[i] = items[current1++]; |
} else if (comp.compare(items[current1], items[current2]) <= 0) { |
tmp[i] = items[current1++]; |
} else { |
tmp[i] = items[current2++]; |
} |
} |
System.arraycopy(tmp, 0, items, start, tmp.length); |
} |
|
public static void main(String[] argv) { |
var random = new Random(); |
var size = 10_000_000; |
var items = new Integer[size]; |
IntStream.range(0, size).forEach(i -> items[i] = random.nextInt(50)); |
var startTime = System.nanoTime(); |
sort(items, Comparator.naturalOrder()); |
var endTime = System.nanoTime(); |
var elapsedMillis = (endTime - startTime) / 1e6; |
System.out.println(elapsedMillis); |
} |
} |
Wednesday, February 21st, 2024 4:33:00pm
Milestone 6 —
Tuesday, February 20th, 2024 2:03:00pm
The linked archive includes files for testing the producer/consumer queue from today’s lecture:
CheckSumRandom.java: an implementation of the test case where each producer uses a shared instance of the Random class to produce data on the fly, introducing a synchronization bottleneck.
CheckSumTLR.java: a revision of the CheckSumRandom test to use ThreadLocalRandom as the source of test data, avoiding synchronization between clients.
OrderingTestData.java: a class that annotates an arbitrary value with the identity of its producer and a timestamp.
OrderingMetadata.java: a test case that uses a ProducerConsumerQueue of OrderingTestData<Integer> to check the property that for every producer P, all items received by a consumer C stemming from P are in order.
PCQWithMetaData.java: an implementation of the concurrent data structure we are testing that annotates each entry with a timestamp and provides a public "whistleblower" checkTimestamps method.
InternalChecks.java: a version of the test case that uses a PCQWithMetaData and regularly calls its checkTimestamps method.
Friday, February 16th, 2024 5:02:00pm
The linked archive includes files for testing the producer/consumer queue from today’s lecture:
ProducerConsumerQueue.java: an implementation of the concurrent data structure we are testing.
UnsynchronizedStartup.java: a property-based test case for the queue that does not synchronize between the two initial phases of the test (initializing the test producers/consumers and running them).
StartupSyncer.java: a synchronization mechanism for some number of parties (threads) to arrive and wait until they all have done so.
SynchronizedStartup.java: a modified version of the testcase that uses a StartupSyncer to make all test threads wait to perform any work until they have all been initialized.
Note: Java’s standard library provides the same functionality as our StartupSyncer in the form of a CountDownLatch. You may also be interested in a more general variation, the CyclicBarrier
Wednesday, February 7th, 2024 8:25:00pm
Milestone 5 —
Tuesday, February 6th, 2024 12:24:00pm
Students interested in learning more about cancelling tasks and threads may wish to read chapter 7 of Java Concurrency in Practice (Readings).
Tuesday, February 6th, 2024 9:51:00am
The following starter code may come in handy during today’s lecture:
public class FileCrawler { |
// search for the needle in each of the passed directories, recursively. |
// the contents of each non-directory file should be searched as a separate (concurrent) task. |
// print the name of the first file found that has a line containing needle. |
// Take care that only one such file name is printed. |
// If no such files are found, print "None found" |
// the program should stop the search as soon as such a file is found. |
// Don't use global variables (i.e. static fields) for communication. |
public static void main(String[] argv) { |
var needle = argv[0]; |
// argv[1] ... argv[length - 1] are directory names to search |
for (int i = 1; i < argv.length; i++) { |
var startDir = new File(argv[i]); |
... start searching in startDir ... |
} |
} |
} |
You may find the isDirectory and listFiles methods of the File class.
To read the lines in a file, I suggest wrapping a FileReader with a BufferedReader and calling the lines method.
Friday, February 2nd, 2024 5:04:00pm
Students interested in learning more about thread pools in Java may wish to read section 6.2 and chapter 8 of Java Concurrency in Practice (Readings).
Friday, February 2nd, 2024 3:32:00pm
As mentioned in lecture today, the interfaces and
Updated Initialization requirements (method signature) for 4 —
Friday, February 2nd, 2024 9:42:00am
The following starter code may come in handy during today’s lecture:
public class ConcurrentMapper { |
private final ExecutorService executorService; |
|
public ConcurrentMapper(ExecutorService executorService) { |
this.executorService = executorService; |
} |
|
public <T,U> Collection<U> map(Collection<T> values, Function<T,U> mapper) { |
} |
|
public static void main(String[] argv) { |
// example usage: |
var mapper = ??; |
var nums = IntStream.range(0, 50).boxed().toList(); |
System.out.println(mapper.map(nums, i -> i + 1)); |
} |
} |
Thursday, February 1st, 2024 6:25:00am
The test results for milestone 3 —
Monday, January 29th, 2024 9:08:00pm
The interfaces interfaces for milestone 4 have been updated for some minor fixes.
Saturday, January 27th, 2024 10:29:00pm
Milestone 4 —
Friday, January 26th, 2024 8:57:00am
This file for using a ProducerConsumerQueue may come in handy in today’s lecture.
Wednesday, January 24th, 2024 1:53:00pm
The provided interfaces for 3 —
Tuesday, January 23nd, 2024 2:21:00pm
Below is the implementation of the correct (but gross and horrible) implementation of Account::withdraw from the end of today’s lecture:
public void withdraw(int amount) { |
lock.lock() |
while (balance < amount) { |
lock.unlock(); |
Thread.yield(); |
lock.lock(); |
} |
balance -= amount; |
lock.unlock() |
} |
Monday, January 22nd, 2024 11:55:00am
Now that the results of the first programming assignment are available, please
see —
Sunday, January 21th, 2024 2:47:00pm
I added some clarifications concerning the intended interactions between client
and PetViewer to Milestone 3 —
Saturday, January 20th, 2024 1:13:00pm
Milestone 3 —
Friday, January 19th, 2024 9:10:00am
The following starter code may come in handy during today’s lecture:
public class Philosopher implements Runnable { |
|
private final String name; |
private final Fork left, right; |
private final int rounds; |
|
private static final int SLEEP_TIME = 0; |
|
public Philosopher(String name, Fork left, Fork right, int rounds) { |
this.name = name; |
this.left = left; |
this.right = right; |
this.rounds = rounds; |
} |
|
private void think(Random random) throws InterruptedException { |
log("starts thinking"); |
Thread.sleep(SLEEP_TIME); |
} |
|
private void log(String message) { |
System.out.println("Philosopher " + name + " " + message); |
} |
|
@Override |
public void run() { |
var random = ThreadLocalRandom.current(); |
try { |
for (int i = 0; i < rounds; i++) { |
think(random); |
log("gets hungry"); |
eat(random, left, right); |
} |
System.out.println("Philosopher " + name + " finished"); |
} catch (InterruptedException ignored) { |
} |
} |
|
protected void eat(Random random, Fork left, Fork right) throws InterruptedException { |
grab(left); |
grab(right); |
Thread.sleep(SLEEP_TIME); |
log("finishes eating"); |
release(left); |
release(right); |
} |
|
private void grab(Fork fork) { |
log("reaches for fork " + fork.getName()); |
fork.pickUp(); |
log("picks up fork " + fork.getName()); |
} |
|
private void release(Fork fork) { |
log("puts down fork " + fork.getName()); |
fork.putDown(); |
} |
} |
public class Fork { |
private final String name; |
|
public Fork(String name) { |
this.name = name; |
} |
|
public String getName() { |
return name; |
} |
|
private final Lock lock = new ReentrantLock(); |
|
public void pickUp() { |
lock.lock(); |
} |
|
public void putDown() { |
lock.unlock(); |
} |
} |
public class Main { |
private static final int SIZE = 5; |
private static final int ROUNDS = 10; |
public static void main(String[] argv) { |
var forks = IntStream.range(0, SIZE) |
.mapToObj(i -> new Fork(Integer.toString(i))) |
.toArray(Fork[]::new); |
var philosophers = IntStream.range(0, SIZE) |
.mapToObj(i -> new OrderedPhilosopher(Integer.toString(i), forks[i], forks[(i + 1) % SIZE], ROUNDS) { |
}) |
.toArray(Philosopher[]::new); |
var threads = Arrays.stream(philosophers) |
.map(Thread::new) |
.toList(); |
var startTime = System.currentTimeMillis(); |
threads.forEach(Thread::start); |
try { |
for (var t : threads) { |
t.join(); |
} |
} catch (InterruptedException ignored) { |
} |
var finishTime = System.currentTimeMillis(); |
System.out.println("Elapsed: " + ((double) (finishTime - startTime)) / 1000); |
} |
} |
Thursday, January 18th, 2024 1:46:00pm
If you are using gson, make sure you are enabling the serializeNulls option of a GsonBuilder when serializing the output.
Thursday, January 18th, 2024 10:38:00am
The previous sample tests incorrectly used "CAT" and "DOG" as values for a PetType. The fixed tests can be found at this link.
Wednesday, January 17th, 2024 5:12:00pm
You may wish to run your homework solution on these sample tests. Each test case is a pair of files: a JSON input configuration and the expected JSON output.
Tuesday, January 16th, 2024 8:02:00am
The following starter code may come in handy during today’s lecture:
public class Account { |
private long balance = 0; |
|
public long getBalance() { |
return balance; |
} |
|
public void deposit(long amount) { |
balance += amount; |
} |
} |
|
public class Client { |
private String name; |
private Account account; |
|
public Client(String name, Account account) { |
this.name = name; |
this.account = account; |
} |
|
public void work() { |
account.deposit(1); |
} |
|
} |
|
public class Main { |
public static void main(String[] argv) throws InterruptedException { |
var checking = new Account(); |
var teacher = new Client("Sam", checking); |
var sideHustle = new Client("halp.com", checking); |
var t1 = new ClientThread(teacher); |
var t2 = new ClientThread(sideHustle); |
t1.start(); |
t2.start(); |
System.out.println(checking.getBalance()); |
} |
} |
|
class ClientThread extends Thread { |
private Client client; |
|
public ClientThread(Client client) { |
super(); |
this.client = client; |
} |
|
@Override |
public void run() { |
client.work(); |
} |
} |
Wednesday, January 10th, 2024 1:37:00pm
Milestone 2 —
Monday, January 1st, 2024 2:19:59pm
Welcome to Building Extensible Systems, Spring 2024.
See Abstract for a concise course description.
If you choose to take the course, familiarize yourself with the web site as
quickly as possible. —
