Lecture 18

2023-06-05 | Week 10 | edited by Matt Wang

(originally written 2022-11-28 by Carey Nachenberg and Ashwin Ranade)

Table of Contents

Introduction to Concurrency

Concurrency is when we decompose a program into simultaneously executing tasks.

The tasks can:

  • run in parallel on multiple cores, OR run multiplexed on a single core
  • operate on independent data, OR operate on shared mutable data/systems
  • be launched deterministcally through program flow, OR be lanuched to due external event (button click in UI)

Concurrency can make our programs more efficient!

Question: If a concurrent program only runs on a single core, why would it be any faster than a program that runs serially? Answer: Some tasks involve lots of waiting, not a lot of CPU. During that waiting time, a concurrent program can use the CPU for other useful tasks! For example, downloading multiple photos.

Concurrency With Shared Mutable State

Race Conditions

Question: What will the value of karma be if I run both functions concurrently until completion? Why?

int karma = 0;

void do_good_deeds() {
  for (int i=0;i<100000;++i)
    karma++;
}

void be_naughty() {
  for (int i=0;i<100000;++i)
    karma--;
}

Answer: Answer: Given that each “thread” of execution can be interrupted at any time to run the other, it’s impossible to know!

The undefined behavior is due to both threads using a shared mutable state; karma is a mutable variable that’s shared between multiple threads. (Race Condition)

  • a key goal of concurrency is determinism; code should produce the same result every time, regardless of how its tasks are scheduled.

Safe Concurrency With Shared Mutable State

Most modern languages now have built-in language features to make it safer to use shared mutable state.

For example, Java’s synchronized keyword can be used to limit access to a mutable variable to a single thread at a time.

Models for Concurrency

Two approaches for implementing concurrency:

Multi-threading model: a program creates multiple “threads” of execution that run concurrently (potentially in parallel).

The programmer explicitly “launches” one or more functions in their own threads, and the OS schedules their execution across available CPU cores.

// Multi-threaded program (pseudocode)
void handle_user_purchase(User u, Item i) {
  if (bill_credit_card(u) == SUCCESS) {
    create_thread(schedule_shipping(u, i));
    create_thread(send_confirm_email(u, i));
  }
}

Event Driven Model: a program consists of a queue of functions to run, and an infinite loop (called the event loop) that dequeues and runs each function from the queue, one after the other.

When an event occurs (e.g., user clicks a button) the event results in a new function f() being added to the queue which eventually runs and handles the event.

// Event-driven program (pseudocode)
function process_payment() { ... }

setup_event_associations() {
 button = create_new_button("Pay Now!");
 button.set_func(ON_CLICK, process_payment);
}

Introducing Fork-Join

The “fork-join” pattern is basically a concurrent version of divide and conquer:

  1. first, we “fork” one or more tasks so they execute concurrently…
  2. second, we wait for all those tasks to complete (aka “join”) and then proceed.

If you’re following at home … this also sounds like a map-fold or map-reduce. Interesting…

Example: A parallel sort would be a good example of a problem suitable for fork-join.

function sort_in_parallel(array, n) {
  t1 = run_background(sort(array[0:n/3]));
  t2 = run_background(sort(array[n/3:n*2/3));
  t3 = run_background(sort(array[n*2/3:n]));

  wait_for_all_tasks_to_finish(t1, t2, t3);
  merge_sorted_subarrays(array);
}

function task1(param) { ... }
function task2(param) { ... }
function task3(param1, param2) { ... }

function launch_in_parallel() {
  t1 = run_background(task1(42));
  t2 = run_background(task2("suss"));
  t3 = run_background(task3(3.14, 2.71));

  wait_for_all_tasks_to_finish(t1, t2, t3);
  print("All tasks completed, proceeding...");
}

Fork-join is often used recursively! For huge datasets, we may choose to split a data source in two (forking). But, if it’s still too big, we can split it again! You can imagine this repeating until each chunk is small enough to deal with independently.

Fork-Join In Different Languages 

// C++
#include <thread>

void task1(int n)  { ... }
void task2(int n)  { ... }
void task3(int n)  { ... }

int main() {
  std::cout << "Forking threads!\n";
  //To launch a function in the background, we simply create a new thread object.

  std::thread t1(task1, 10);
  std::thread t2(task2, 20);
  std::thread t3(task3, 30);

  // do other processing here...

  t1.join(); //To join, we simple call the thread.join() method. This blocks the caller until the thread finishes.

  t2.join();
  t3.join();
  std::cout << "All threads joined!\n";
}

// C#
using System;
using System.Threading;
using System.Threading.Tasks;

class Program {
  static int task1(int param) { ... }
  static int task2(int param) { ... }
  static int task3(int param) { ... }

  public static void Main(string[] args) {
    int r1 = 0, r2 = 0, r3 = 0;
    Console.WriteLine("Forking threads!");
    var t1 = Task.Run(() => r1 = task1(10));
    var t2 = Task.Run(() => r2 = task2(20));
    var t3 = Task.Run(() => r3 = task3(30));
    Task.WaitAll(t1, t2, t3);
    Console.WriteLine("Joined: {0}, {1}, {2}",
                      r1, r2, r3);
  }
}

# Python
import threading

def task(n):
  while n > 0:   # do some computation
    n = n - 1

print("Forking threads!")

#In Python, we must create a thread object, and then do thread.start() before it runs.

t1 = threading.Thread(target=task, args=(100000000,))
t2 = threading.Thread(target=task, args=(100000000,))
t3 = threading.Thread(target=task, args=(100000000,))
t1.start()
t2.start()
t3.start()

# do other processing here...

t1.join()
t2.join()
t3.join()
print("All threads joined!")

“Multi-threading” in Python

Question for the Python program: Assuming looping 100 million times takes 5s, how long will this program take to run on a multicore PC?

Answer: 15s We’d expect all three tasks to run in parallel… taking 5s total. But it takes 15s! Why? Because when each Python thread runs, it claims exclusive access to Python’s memory/objects.

So only one thread generally does computation at a time!

Why? Python’s garbage collection system was never designed to be thread-safe!

Python has something called a “Global Interpreter Lock” or GIL.

The GIL is like a hot potato – it can only have one owner at a time.

Once a thread takes ownership of the GIL it’s allowed to read/write to Python objects.

After a thread runs for a while, it releases the GIL (tosses the potato) to another thread and gives it ownership.

If a thread is waiting for the GIL, it simply falls asleep until it gets its turn.

Question: So why even support multiple threads? Are there any cases where multithreading speeds things up?

Answer: Answer: I/O operations like downloading data from the web or saving a file to disk DON’T need the GIL to run! So these kinds of operations can still make progress if launched in the background!

UI Programming and Concurrency

Let’s spend a bit of time to see the other approach – event-driven programming!

Event-driven programming is built on callback functions. These are functions that are called after an event occurs: after the click of a button, a timer expiring, or a payment completing. Generally, these are used as higher-order functions.

Here’s a JS-like pseudo-code example:

function set_up_ui() {
  payment_button = new Button("Pay now!");
  payment_button.set_callback(ON_CLICK, call_upon_click);
  add_button_to_ui(payment_button);
}

function call_upon_click() {
  pay_obj = new PaymentProcessor();
  pay_obj.set_callback(call_upon_payment_done);
  pay_obj.initiate_payment_in_background();
}

function call_upon_payment_done(result) {
  if (result == SUCCESS) update_ui("Payment accepted!");
                    else update_ui("Card denied!");
}

Here, we’ve added call_upon_click and call_upon_payment_done as callback functions: they are called only once an event occurs. Note that when we pass them to set_callback, we’re not calling the functions — we’re passing in the function itself as the argument.

Example: Web Browsers in a Slide

Consider this overly-simplifed web page.

<html>
<body>
<h1>Fortune Teller</h1>
<p id="fort">What does the future hold?</p>
<button onclick="callbk();">Get Fortune</button>

<script>
  set_background_color(BLACK);
  play_mp3("spooky_music.mp3");

  function callbk() {
    set_element("fort", "You'll ace CS131!");
  }
</script>

</body>
</html>

Here, callbk() is yet again a callback! The onclick property for the <button> element allows you to set a callback. When the button is clicked, it calls that function!

But … how does this work? Overall, browsers work differently than traditional top-down programs. We want the browser to respond to events from the user: clicks, buttons, etc.

We can sketch out a Python browser:

class Browser:
  def __init__(self, page):
    self.objs_on_page = self.get_all_objs(page)
    self.run_queue = self.extract_stmts(page)

  def event_loop(self):
    while True:
      self.handle_events()
      self.run_next_statement()

  def handle_events(self):
    for obj in self.objs_on_page:
      if obj.event_occurred():
        func = obj.get_handler()
        self.run_queue.append(func)

  def run_next_statement(self):
    if len(self.run_queue) > 0:
      func = self.dequeue()
      func()

The browser keeps track of:

  • all objects on the page
  • a “run queue”

The key observation here is the event_loop() function: it’s an infinite loop that runs forever! Every time, it:

  1. checks if the user has done anything (handle_events()); if so, it adds the event to the queue
  2. then, it runs the next statement in the queue!

Prolog and Logic Programming

Logic programming is a paradigm where we express programs as a set of facts (relationships which are held to be true), and a set of rules (i.e. if A is true, then B is true).

A program/user then issues queries against this these facts and axioms:

Logic programming is declarative – programs specify “what” they want to compute, not “how” to do so.

Examples:

Facts:

  • Martha is Andrea’s parent
  • Andrea is Carey’s parent

Rules: If X is the parent of Q, and Q is the parent of Y, then X is the grandparent of Y

Queries:

  • Is Martha the grandparent of Carey?
  • Who is the grandparent of Carey?

Introduction to Prolog

Prolog is used for theorem-proving (type checking is one such use case; it’s in the Java compiler!) and has also been used to implement natural language processing and expert systems.

Prolog mostly leans on declarative programming: you specify what you want, but now how you should get there; Prolog is responsible for figuring that out!

When given a query, Prolog tries to find a chain of connections between the query and the specified facts and rules that lead to an answer.

Every Prolog program is comprised of facts about the world, and a bunch of rules that can be used to discover new facts.

Prolog Facts

A “fact” is a predicate expression that declares either…

  • An attribute about some thing (aka an atom); you can think of this as being “always true”
    • outgoing(ren)
  • A relationship between two or more atoms or numbers:
    • parent(alice, bob)
    • age(ren, 80)
    • teaches(carey, course(cs, 131))

Implicitly, we’re defining some terms:

  • an “atom” is a “thing”. In the above examples, this includes ren, alice, and bob. They must be lowercase.
  • a “functor” is like a function (or relationship). In the above examples, this includes outgoing, parent, and age. They must be lowercase.

If a fact isn’t explicitly stated, it is false. For example, in the above case, since we didn’t explicitly state it, alice is not outgoing.

Prolog Rules

A rule lets us define a new fact in terms of one or more existing facts or rules.

Each rule has two parts…

  • A “head” which defines what the rule is trying to determine
  • A “body” which specifies the conditions (aka subgoals) that allow us to conclude the head is true

Rules can be defined with atoms, numbers, or variables. Variables like X and Y are like placeholders which Prolog will try to fill in as it tries to answer user queries. Variables must always be capitalized.

% Facts:
outgoing(ren).
silly(ren).
parent(alice, bob).
age(ren, 80).
parent(bob, carol).

% Rules:
comedian(P) :- silly(P), outgoing(P).
grandparent(X, Y) :- parent(X,Q), parent(Q,Y).
old_comedian(C) :- comedian(C),
age(C, A), A > 60.

Rules and facts might seem very different, but I (Matt) argue that they aren’t! You could think of a fact as a rule that has no body. Then, it is vacuously true (and thus, always true).

Recursive Rules

Rules can also be recursive and can have multiple parts!

Similar to recursion and pattern matching in Haskell, Prolog processes rules from the top to the bottom. So, the base case(s) should always go first!

% Recursive rules:
ancestor(X, Z) :- parent(X,Z).
ancestor(X, Z) :- parent(X,Y), ancestor(Y,Z).

Explanation of the above code block:

X is the ancestor of Z if:

  • X is Z’s parent
  • OR if X is some person Y’s parent AND Y is an ancestor of person Z

Prolog uses something called the “closed-world assumption” (CWA). Basically, this means that only things that can be proven true by the program are true; everything else is false.

Negation in Rules

Rules can also use negation – but be careful!

In Prolog, not(something) works as follows:

  1. Prolog tries to prove something is true using all of the program’s facts and rules
  2. If something can’t be proven as true, then not(something) is found to be true.
% Rules with negation:
serious(X) :- not(silly(X)).

For example, the query serious(alice) is true, since the closed-world assumption says that silly(alice) is false.

Prolog Queries

We can create queries to answer true/false questions:

  • A query can match a simple fact…
  • Or it can execute a rule.
?- outgoing(alice)
true
?- grandparent(brenda, ned)
true

We can also create queries to fill-in-the-blanks:

  • The query will find ALL possible matches.
  • The query can specify multiple unknowns.
  • And Prolog will find ALL consistent combinations of answers!
?- parent(alice , Who)
Who = bob
Who = brenda
?- grandparent(A, B)

%answers to queries below
A = alice, B = caitlin
A = brenda, B = ned

Resolution: How Prolog Answers Queries

Example facts/rules:

parent (nel, ted).
parent (ann, bob).
parent (ann, bri).
parent (bri, cas).
gparent( X ,  Y )  :-
  parent(X,Q), parent(Q,Y).

Example query:

gparent(ann, W)

Algorithm:

  1. Add our query to a goal stack
  2. Pop the top goal in our goal stack and match it with each item in our database, from top to bottom
  3. If we find a match, extract the variable mappings, and create a new map with the old+new mappings
  4. Create a new goal stack, copying over existing, unprocessed goals and adding new subgoals
  5. Recursively repeat the process on the new goal stack and the new mappings

So initially, our goal stack is simply gparent(ann,W), and our mappings are {}. Then, after matching the last rule, our goal stack becomes:

parent(X,Q)
parent(Q,Y)

And our mappings are {X->ann,W<->Y}

Then, pop the top rule off our goal stack. We have a potential match with parent (nel, ted). So our goal stack becomes:

parent(Q,Y)

With the mappings: {X->ann,W<->Y, Q->bob}

We pop the top rule off the stack again. There’s no rule that matches parent(bob,Y), which means the set of mappings we discovered were not valid.

So we’ll back-track one level up and continue searching for alternative mappings.

If our goal stack is empty, we output variables from our mapping that were explicitly queried; in this case, our final mapping is: { X ->ann, W <-> Y <-> cas, Q ->bri }

So we return cas, since W=cas.