1 of 40

Parallelism & Concurrency

CSE 332 – Section 9 (11/21/24)

Slides by James Richie Sulaeman

2 of 40

Parallel Prefix

3 of 40

Parallel prefix is a type of programming problem where:

  • A given array of elements needs to be processed in parallel
  • Each element is combined with its predecessors through some operation
    • i.e. in parallel prefix sum, each element is summed with its predecessors

Parallel Prefix

Allows for efficient computation of certain operations on large datasets since it enables multiple threads to work simultaneously on different portions of the data.

4 of 40

Problem 0

Parallel Prefix Sum

5 of 40

  1. Divide problem into parallel pieces

cutoff = 1

Problem 0

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

input =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

6 of 40

  • Divide problem into parallel pieces

cutoff = 1

Problem 0

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

input =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

  1. Find sum at cutoff

leaves[i].sum = input[i]

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

7 of 40

  • Divide problem into parallel pieces

cutoff = 1

Problem 0

range: 0,2

sum:

fromLeft:

input =

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

range: 0,8

sum: 44

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  • Find sum at cutoff

leaves[i].sum = input[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

range: 0,2

sum: 17

fromLeft:

range: 2,4

sum: 9

fromLeft:

range: 4,6

sum: 7

fromLeft:

range: 6,8

sum: 11

fromLeft:

range: 0,4

sum: 26

fromLeft:

range: 4,8

sum: 18

fromLeft:

8 of 40

  • Divide problem into parallel pieces

cutoff = 1

Problem 0

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  • Find sum at cutoff

leaves[i].sum = input[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

range: 0,2

sum: 17

fromLeft:

range: 2,4

sum: 9

fromLeft:

range: 4,6

sum: 7

fromLeft:

range: 6,8

sum: 11

fromLeft:

range: 0,4

sum: 26

fromLeft:

range: 4,8

sum: 18

fromLeft:

range: 0,8

sum: 44

fromLeft:

range: 1,2

sum: 9

fromLeft: 8

range: 0,1

sum: 8

fromLeft: 0

range: 3,4

sum: 3

fromLeft: 23

range: 2,3

sum: 6

fromLeft: 17

range: 5,6

sum: 5

fromLeft: 28

range: 4,5

sum: 2

fromLeft: 26

range: 7,8

sum: 4

fromLeft: 40

range: 6,7

sum: 7

fromLeft: 33

range: 0,2

sum: 17

fromLeft: 0

range: 2,4

sum: 9

fromLeft: 17

range: 4,6

sum: 7

fromLeft: 26

range: 6,8

sum: 11

fromLeft: 33

range: 0,4

sum: 26

fromLeft: 0

range: 4,8

sum: 18

fromLeft: 26

range: 0,8

sum: 44

fromLeft: 0

9 of 40

  • Divide problem into parallel pieces

cutoff = 1

Problem 0

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  • Find sum at cutoff

leaves[i].sum = input[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  • output[i] = leaves[i].fromLeft + input[i]

range: 1,2

sum: 9

fromLeft: 8

range: 0,1

sum: 8

fromLeft: 0

range: 3,4

sum: 3

fromLeft: 23

range: 2,3

sum: 6

fromLeft: 17

range: 5,6

sum: 5

fromLeft: 28

range: 4,5

sum: 2

fromLeft: 26

range: 7,8

sum: 4

fromLeft: 40

range: 6,7

sum: 7

fromLeft: 33

range: 0,2

sum: 17

fromLeft: 0

range: 2,4

sum: 9

fromLeft: 17

range: 4,6

sum: 7

fromLeft: 26

range: 6,8

sum: 11

fromLeft: 33

range: 0,4

sum: 26

fromLeft: 0

range: 4,8

sum: 18

fromLeft: 26

range: 0,8

sum: 44

fromLeft: 0

8

17

23

26

28

33

40

44

10 of 40

Problem 1

Parallel Prefix FindMin

11 of 40

  • Divide problem into parallel pieces

cutoff = 1

Problem 1

range: 1,2

min:

fromLeft:

range: 0,1

min:

fromLeft:

range: 0,2

min:

fromLeft:

input =

range: 3,4

min:

fromLeft:

range: 2,3

min:

fromLeft:

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 5,6

min:

fromLeft:

range: 4,5

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 7,8

min:

fromLeft:

range: 6,7

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

12 of 40

range: 1,2

min:

fromLeft:

range: 0,1

min:

fromLeft:

range: 0,2

min:

fromLeft:

input =

range: 3,4

min:

fromLeft:

range: 2,3

min:

fromLeft:

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 5,6

min:

fromLeft:

range: 4,5

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 7,8

min:

fromLeft:

range: 6,7

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

range: 1,2

min: 9

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

  • Divide problem into parallel pieces

cutoff = 1

  • Find min at cutoff

leaves[i].min = input[i]

13 of 40

range: 0,2

min:

fromLeft:

input =

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

range: 1,2

min: 9

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

range: 0,2

min: 8

fromLeft:

range: 2,4

min: 3

fromLeft:

range: 4,6

min: 2

fromLeft:

range: 6,8

min: 4

fromLeft:

range: 0,4

min: 3

fromLeft:

range: 4,8

min: 2

fromLeft:

range: 0,8

min: 2

fromLeft:

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

  • Divide problem into parallel pieces

cutoff = 1

  • Find min at cutoff

leaves[i].min = input[i]

  • Propagate min up

parent.min = min(left.min, right.min)

14 of 40

range: 0,8

min: 2

fromLeft:

range: 0,4

min: 3

fromLeft:

range: 4,8

min: 2

fromLeft:

range: 6,8

min: 4

fromLeft:

  • Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

output =

  • Find min at cutoff

leaves[i].min = input[i]

  • Propagate min up

parent.min = min(left.min, right.min)

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = min(parent.fromLeft, left.min)

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

range: 0,2

min: 8

fromLeft:

range: 2,4

min: 3

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 4,6

min: 2

fromLeft:

range: 1,2

min: 9

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

range: 0,8

min: 2

fromLeft: ∞

range: 0,4

min: 3

fromLeft: ∞

range: 4,8

min: 2

fromLeft: 3

range: 6,8

min: 4

fromLeft: 2

range: 0,2

min: 8

fromLeft: ∞

range: 2,4

min: 3

fromLeft: 8

range: 0,1

min: 8

fromLeft: ∞

range: 4,6

min: 2

fromLeft: 3

range: 1,2

min: 9

fromLeft: 8

range: 3,4

min: 3

fromLeft: 6

range: 2,3

min: 6

fromLeft: 8

range: 5,6

min: 5

fromLeft: 2

range: 4,5

min: 2

fromLeft: 3

range: 7,8

min: 4

fromLeft: 2

range: 6,7

min: 7

fromLeft: 2

​

​

​

​

​

​

​

​

15 of 40

  • Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

  • Find min at cutoff

leaves[i].min = input[i]

  • Propagate min up

parent.min = min(left.min, right.min)

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = min(parent.fromLeft, left.min)

  • output[i] = min(leaves[i].fromLeft, input[i])

8

8

6

3

2

2

2

2

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

range: 0,8

min: 2

fromLeft: ∞

range: 0,4

min: 3

fromLeft: ∞

range: 4,8

min: 2

fromLeft: 3

range: 6,8

min: 4

fromLeft: 2

range: 0,2

min: 8

fromLeft: ∞

range: 2,4

min: 3

fromLeft: 8

range: 0,1

min: 8

fromLeft: ∞

range: 4,6

min: 2

fromLeft: 3

range: 1,2

min: 9

fromLeft: 8

range: 3,4

min: 3

fromLeft: 6

range: 2,3

min: 6

fromLeft: 8

range: 5,6

min: 5

fromLeft: 2

range: 4,5

min: 2

fromLeft: 3

range: 7,8

min: 4

fromLeft: 2

range: 6,7

min: 7

fromLeft: 2

16 of 40

Problem 2

Parallel Pack

17 of 40

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Problem 2 Overview

Given an array input, output an array that contains only the elements that are less than 10

  1. Parallel map to compute bits array where bits[i] = (input[i] < 10)
  • Parallel prefix sum on bits array to compute bitsum array
  • Parallel map to produce output array where output[bitsum[i] - 1] = input[i]

if bits[i] == 1

12

5

-8

34

6

10

2

7

input =

bits =

0

1

1

0

1

0

1

1

bitsum =

0

1

2

2

3

3

4

5

output =

5

-8

6

2

7

18 of 40

Problem 2

  • Parallel map to compute bits array where bits[i] = (input[i] < 10)

input =

12

5

-8

34

6

10

2

7

​

​

​

​

​

​

​

​

bits =

0

1

1

0

1

0

1

1

lo: 0

hi: 8

lo: 0

hi: 4

lo: 4

hi: 8

lo: 6

hi: 8

lo: 0

hi: 2

lo: 2

hi: 4

lo: 0

hi: 1

lo: 4

hi: 6

lo: 1

hi: 2

lo: 3

hi: 4

lo: 2

hi: 3

lo: 5

hi: 6

lo: 4

hi: 5

lo: 7

hi: 8

lo: 6

hi: 7

19 of 40

  • Divide problem into parallel pieces

cutoff = 1

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

bits =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

0

1

1

0

1

0

1

1

​

​

​

​

​

​

​

​

bitsum =

  • Parallel prefix sum on bits array

to compute bitsum array

Problem 2

20 of 40

  • Divide problem into parallel pieces

cutoff = 1

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

​

​

​

​

​

​

​

​

  • Find sum at cutoff

leaves[i].sum = bits[i]

range: 1,2

sum: 1

fromLeft:

range: 0,1

sum: 0

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,7

sum: 1

fromLeft:

  • Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

21 of 40

  • Divide problem into parallel pieces

cutoff = 1

range: 0,2

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

​

​

​

​

​

​

​

​

  • Find sum at cutoff

leaves[i].sum = bits[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

range: 1,2

sum: 1

fromLeft:

range: 0,1

sum: 0

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,7

sum: 1

fromLeft:

range: 0,2

sum: 1

fromLeft:

range: 2,4

sum: 1

fromLeft:

range: 4,6

sum: 1

fromLeft:

range: 6,8

sum: 2

fromLeft:

range: 0,4

sum: 2

fromLeft:

range: 4,8

sum: 3

fromLeft:

range: 0,8

sum: 5

fromLeft:

  • Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

22 of 40

range: 0,1

sum: 0

fromLeft:

range: 0,2

sum: 1

fromLeft:

range: 1,2

sum: 1

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 2,4

sum: 1

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 6,7

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,8

sum: 2

fromLeft:

range: 4,6

sum: 1

fromLeft:

range: 4,8

sum: 3

fromLeft:

range: 0,4

sum: 2

fromLeft:

range: 0,8

sum: 5

fromLeft:

range: 7,8

sum: 1

fromLeft: 4

range: 6,7

sum: 1

fromLeft: 3

range: 5,6

sum: 0

fromLeft: 3

range: 4,5

sum: 1

fromLeft: 2

range: 3,4

sum: 0

fromLeft: 2

range: 2,3

sum: 1

fromLeft: 1

range: 1,2

sum: 1

fromLeft: 0

range: 0,1

sum: 0

fromLeft: 0

range: 0,2

sum: 1

fromLeft: 0

range: 2,4

sum: 1

fromLeft: 1

range: 4,6

sum: 1

fromLeft: 2

range: 6,8

sum: 2

fromLeft: 3

range: 4,8

sum: 3

fromLeft: 2

range: 0,4

sum: 2

fromLeft: 0

range: 0,8

sum: 5

fromLeft: 0

  • Divide problem into parallel pieces

cutoff = 1

​

​

​

​

​

​

​

​

  • Find sum at cutoff

leaves[i].sum = bits[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  • Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

23 of 40

range: 0,8

sum: 5

fromLeft: 0

range: 0,4

sum: 2

fromLeft: 0

range: 4,8

sum: 3

fromLeft: 2

range: 6,8

sum: 2

fromLeft: 3

range: 4,6

sum: 1

fromLeft: 2

range: 2,4

sum: 1

fromLeft: 1

range: 0,2

sum: 1

fromLeft: 0

range: 7,8

sum: 1

fromLeft: 4

range: 6,7

sum: 1

fromLeft: 3

range: 5,6

sum: 0

fromLeft: 3

range: 4,5

sum: 1

fromLeft: 2

range: 3,4

sum: 0

fromLeft: 2

range: 2,3

sum: 1

fromLeft: 1

range: 1,2

sum: 1

fromLeft: 0

range: 0,1

sum: 0

fromLeft: 0

  • Divide problem into parallel pieces

cutoff = 1

​

​

​

​

​

​

​

​

  • Find sum at cutoff

leaves[i].sum = bits[i]

  • Propagate sum up

parent.sum = left.sum + right.sum

  • Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  • bitsum[i] = leaves[i].fromLeft + bits[i]

0

1

2

2

3

3

4

5

  • Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

24 of 40

Problem 2

  • Parallel map to produce output array where output[bitsum[i] - 1] = input[i]

if bits[i] == 1

input =

12

5

-8

34

6

10

2

7

lo: 0

hi: 1

​

​

​

​

​

​

​

​

0

1

2

2

3

3

4

5

bits =

bitsum =

0

1

1

0

1

0

1

1

output =

​

​

​

​

​

lo: 1

hi: 2

lo: 2

hi: 3

lo: 3

hi: 4

lo: 4

hi: 5

lo: 5

hi: 6

lo: 6

hi: 7

lo: 7

hi: 8

lo: 0

hi: 2

lo: 6

hi: 8

lo: 2

hi: 4

lo: 4

hi: 6

lo: 0

hi: 4

lo: 4

hi: 8

lo: 0

hi: 8

5

-8

6

2

7

25 of 40

Problem 3

26 of 40

  1. Define work and span.

​

​

​

  • How do we calculate work and span?

​

​

​

  • Does adding more processors affect the work or span?

​

Work is the runtime of a program on one processor.

Span is the runtime of a program on infinitely many processors.

​

​

Work is the sum of all the work done by all processors

Span is the sum of all the work done by the longest dependence chain / parallel ‘tree’ branch

​

​

Neither. Work is defined for one processor and span is defined for infinitely many processors. Adding more processors will not affect either work or span.

Problem 3

27 of 40

  • What is the work and span of the graph?

Problem 3

T3

work: 2

T2

work: 2

T4

work: 2

T1

work: 1

T6

work: 1

T5

work: 4

T7

work: 1

​

Work = 1 + 2 + 2 + 2 + 4 + 1 + 1

= 13

Span ( T1→T2→T5 ) = 1 + 2 + 4

= 7

28 of 40

Concurrency Errors

29 of 40

A race condition occurs when the result of your program depends on how threads are scheduled/interleaved

Concurrency Errors

x = read(count)

write(count, x+1)

Thread 1

y = read(count)

write(count, y+1)

Thread 2

  • A data race occurs when two threads access the same variable at the same time
    • Write-write: two threads writing to the same variable at the same time
    • Write-read: one thread writing to a variable while another reads from it
    • Note: read-reads do not cause a data race since they do not modify variables
  • A bad interleaving occurs when the interleaving of threads result in bad and unexpected intermediate states
    • e.g. two threads are trying to increment the variable count at the same time

30 of 40

A deadlock occurs when a cycle of threads are waiting on each other

A piece of code is considered to have a concurrency error if there exists any execution sequence that can lead to a race condition or deadlock

  • It is not necessary for the code to always execute in this bad sequence
  • The possibility of such a sequence occurring is sufficient

Concurrency Errors

Thread 1

Thread 2

Resource A

Resource B

waiting for

waiting for

assigned to

assigned to

  • Thread 1 is waiting on a resource held by Thread 2
  • Thread 2 is waiting on a resource held by Thread 1

31 of 40

Problem 4

32 of 40

1 class UserProfile {

2 static int id_counter;

3 int id; // unique for each account

4 int[] friends = new int[9999]; // horrible style

5 int numFriends;

6 Image[] embarrassingPhotos = new Image[9999];

7

8 UserProfile() { // constructor for new profiles

9 id = id_counter++;

10 numFriends = 0;

11 }

12

13 synchronized void makeFriends(UserProfile newFriend) {

14 synchronized(newFriend) {

15 if (numFriends == friends.length

16 || newFriend.numFriends == newFriend.friends.length) {

17 throw new TooManyFriendsException();

18 }

19 friends[numFriends++] = newFriend.id;

20 newFriend.friends[newFriend.numFriends++] = id;

21 }

22 }

23

24 synchronized void removeFriend(UserProfile frenemy) {

25 ...

26 }

27 }

​

​

The constructor has a concurrency error. What is it and how would you fix it?

Problem 4a

  • There is a data race on id_counter
  • Two accounts could get the same id if they are created at the same time by different threads
  • To fix this, you could synchronize on a lock for id_counter

Note: the synchronized keyword on a method locks this object. elsewhere, it locks the specified object

33 of 40

1 class UserProfile {

2 static int id_counter;

3 int id; // unique for each account

4 int[] friends = new int[9999]; // horrible style

5 int numFriends;

6 Image[] embarrassingPhotos = new Image[9999];

7

8 UserProfile() { // constructor for new profiles

9 id = id_counter++;

10 numFriends = 0;

11 }

12

13 synchronized void makeFriends(UserProfile newFriend) {

14 synchronized(newFriend) {

15 if (numFriends == friends.length

16 || newFriend.numFriends == newFriend.friends.length) {

17 throw new TooManyFriendsException();

18 }

19 friends[numFriends++] = newFriend.id;

20 newFriend.friends[newFriend.numFriends++] = id;

21 }

22 }

23

24 synchronized void removeFriend(UserProfile frenemy) {

25 ...

26 }

27 }

​

​

The makeFriends method has a concurrency error. What is it and how would you fix it?

Problem 4b

  • There is a potential deadlock
  • Suppose there are two UserProfile objects called obj1 and obj2
    • One thread calls obj1.makeFriends(obj2)
    • Another thread calls obj2.makeFriends(obj1)
    • Both threads execute line 13 at the same time and deadlock at line 14
  • To fix this, acquire locks in a consistent order (e.g. in order of id fields)

Note: the synchronized keyword on a method locks this object. elsewhere, it locks the specified object

34 of 40

Problem 5

35 of 40

1 public class BubbleTea {

2 private Stack<String> drink = new Stack<String>();

3 private Stack<String> toppings = new Stack<String>();

4 private final int maxDrinkAmount = 8;

5

6 // Checks if drink has capacity

7 public boolean hasCapacity() {

8 return drink.size() < maxDrinkAmount;

9 }

10

11 // Adds liquid to drink

12 public void addLiquid(String liquid) {

13 if (hasCapacity()) {

14 if (liquid.equals("Milk")) {

15 while (hasCapacity()) {

16 drink.push("Milk");

17 }

18 } else {

19 drink.push(liquid);

20 }

21 }

22 }

23

24 // Adds newTop to list of toppings to add to drink

25 public void addTopping(String newTop) {

26 if (newTop.equals("Boba") || newTop.equals("Tapioca")) {

27 toppings.push("Bubbles");

28 } else {

29 toppings.push(newTop);

30 }

31 }

32 }

​

​

​

Does the BubbleTea class have:

a race condition

potential for deadlock

a data race

none of these

a race condition

  • There is the potential for bad interleaving
  • Suppose two threads call addLiquid() at the same time
    • Both threads satisfy the hasCapacity() condition with a value of 7 for drink.size()
    • Both threads then push onto the drink stack, exceeding maxDrinkAmount

Note: a “thread-safe” stack prevents data races on itself since only one thread can modify it at a time

Problem 5a

36 of 40

1 public class BubbleTea {

2 private Stack<String> drink = new Stack<String>();

3 private Stack<String> toppings = new Stack<String>();

4 private final int maxDrinkAmount = 8;

5

6 // Checks if drink has capacity

7 public boolean hasCapacity() {

8 return drink.size() < maxDrinkAmount;

9 }

10

11 // Adds liquid to drink

12 public void addLiquid(String liquid) {

13 if (hasCapacity()) {

14 if (liquid.equals("Milk")) {

15 while (hasCapacity()) {

16 drink.push("Milk");

17 }

18 } else {

19 drink.push(liquid);

20 }

21 }

22 }

23

24 // Adds newTop to list of toppings to add to drink

25 public synchronized void addTopping(String newTop) {

26 if (newTop.equals("Boba") || newTop.equals("Tapioca")) {

27 toppings.push("Bubbles");

28 } else {

29 toppings.push(newTop);

30 }

31 }

32 }

​

​

​

Suppose we made the addTopping method synchronized. Does this modified BubbleTea class have:

Problem 5b

a race condition

potential for deadlock

a data race

none of these

a race condition

  • This does not fix the problem
  • Modifying addTopping() still allows for the same pattern of execution in addLiquid() as described earlier
  • However, this change reduces the effective concurrency in the code, so it makes things slightly worse

Note: a “thread-safe” stack prevents data races on itself since only one thread can modify it at a time

37 of 40

Problem 6

38 of 40

1 public class PhoneMonitor {

2 private int numMinutes = 0;

3 private int numAccesses = 0;

4 private int maxMinutes = 200;

5 private int maxAccesses = 10;

6 private boolean phoneOn = true;

7 private Object accessesLock = new Object();

8 private Object minutesLock = new Object();

9

10 public void accessPhone(int minutes) {

11 if (phoneOn) {

12 synchronized (accessesLock) {

13 synchronized (minutesLock) {

14 numAccesses++;

15 numMinutes += minutes;

16 checkLimits();

17 }

18 }

19 }

20 }

21

22 private void checkLimits() {

23 synchronized (minutesLock) {

24 synchronized (accessesLock) {

25 if (numAccesses >= maxAccesses

26 || numMinutes >= maxMinutes) {

27 phoneOn = false;

28 }

29 }

30 }

31 }

32 }

​

​

​

Does the PhoneMonitor class have:

a race condition

potential for deadlock

a data race

none of these

a race condition

  • There is a data race on phoneOn. By definition, this is also a race condition
  • Thread 1 could be at line 11 reading phoneOn, while Thread 2 is at line 27 writing phoneOn
    • This is a write-read data race

Note: the synchronized keyword is reentrant. The thread holds the lock, not the function call.

Problem 6a

a data race

39 of 40

1 public class PhoneMonitor {

2 private int numMinutes = 0;

3 private int numAccesses = 0;

4 private int maxMinutes = 200;

5 private int maxAccesses = 10;

6 private boolean phoneOn = true;

7 private Object accessesLock = new Object();

8 private Object minutesLock = new Object();

9

10 public void accessPhone(int minutes) {

11 if (phoneOn) {

12 synchronized (accessesLock) {

13 synchronized (minutesLock) {

14 numAccesses++;

15 numMinutes += minutes;

16 checkLimits();

17 }

18 }

19 }

20 }

21

22 private void checkLimits() {

23 synchronized (minutesLock) {

24 synchronized (accessesLock) {

25 if (numAccesses >= maxAccesses

26 || numMinutes >= maxMinutes) {

27 phoneOn = false;

28 }

29 }

30 }

31 }

32 }

​

​

​

Note: the synchronized keyword is reentrant. The thread holds the lock, not the function call.

Problem 6b

Suppose we made the checkLimits method public. Does this modified PhoneMonitor class have:

a race condition

potential for deadlock

a data race

none of these

a race condition

  • Same data race on phoneOn still exists
  • However, there is now also the potential for deadlock
  • Suppose two threads call accessPhone() and checkLimits() at the same time
    • Thread 1 calls accessPhone() and acquires accessesLock
    • Thread 2 calls checkLimits() and acquires minutesLock
    • Now Thread 1 wants to acquire minutesLock, while Thread 2 wants to acquire accessesLock

a data race

potential for deadlock

40 of 40

Thank You!