Difference between revisions of "Atomicity"

From CSE231 Wiki
Jump to navigation Jump to search
 
(14 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
=Motivation=
 
=Motivation=
Many [https://en.wikipedia.org/wiki/Race_condition race conditions] can be prevented by proper encapsulation avoiding check-then-write and read-then-modify-then-write in non-[https://en.wikipedia.org/wiki/Linearizability atomically].
+
Many [https://en.wikipedia.org/wiki/Race_condition race conditions] can be prevented by proper encapsulation avoiding check-then-write and read-then-modify-then-write patterns.
  
 
=Background=
 
=Background=
Line 11: Line 11:
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentMap.html ConcurrentMap]
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentMap.html ConcurrentMap]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentMap.html#compute-K-java.util.function.BiFunction- compute]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentMap.html#compute-K-java.util.function.BiFunction- compute]
 +
 +
<youtube>4M9abyUyzxU</youtube>
 +
 +
=Lecture=
 +
<youtube>0jISL5lT7TU</youtube>
  
 
=Song to Recall=
 
=Song to Recall=
 +
[[File:Frère Jacques four voice round.png|thumb]]
 +
{| style="font-style: italic;"
 +
|-
 +
| Frère Jacques, Frère Jacques, || || Get then put is not atomic
 +
|-
 +
| Dormez-vous? Dormez-vous? || || Call [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#compute-K-java.util.function.BiFunction- compute]. Call [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#compute-K-java.util.function.BiFunction- compute].
 +
|-
 +
| Sonnez les matines! Sonnez les matines! || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; || Use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html ConcurrentHashMap]! Use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html ConcurrentHashMap]!
 +
|-
 +
| Ding, dang, dong. Ding, dang, dong. || || Or say shoot. Or say shoot.
 +
|}
  
''get then put is not atomic<br>call [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#compute-K-java.util.function.BiFunction- compute]<br>call [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#compute-K-java.util.function.BiFunction- compute]<br>use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html ConcurrentHashMap]<br>use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html ConcurrentHashMap]<br>or say shoot!<br>or say shoot!''
+
=SuspectWordCount=
 
 
=Studio=
 
==SuspectWordCount==
 
 
<youtube>glpqcoTELi0</youtube>
 
<youtube>glpqcoTELi0</youtube>
===Code To Fix: countWords===
+
==Code To Fix: countWords==
 
{{Warning|Do NOT use synchronized here.  ConcurrentMaps are already thread safe.}}
 
{{Warning|Do NOT use synchronized here.  ConcurrentMaps are already thread safe.}}
  
 
fix the code to remove the atomicity race.
 
fix the code to remove the atomicity race.
{{CodeToDebug|SuspectWordCount|countWords|atomicity.wordcount.studio}}
+
{{CodeToDebug|SuspectWordCount|countWords|atomicity.wordcount.exercise}}
 
{{Parallel|public static Map<String, Integer> countWords(Iterable<String> words)}}
 
{{Parallel|public static Map<String, Integer> countWords(Iterable<String> words)}}
==StockPortfolio==
+
=StockPortfolio=
 +
 
 +
note: somewhat out of date video.
 +
 
 
<youtube>z9IvYmvyIh0</youtube>
 
<youtube>z9IvYmvyIh0</youtube>
===Code To Fix: transfer===
 
{{Warning|Do NOT use synchronized here.  ConcurrentMaps are already thread safe.}}
 
  
For this part of the studio we are presented with broken code.  Despite using a thread-safe concurrent map:
+
==Code To Fix==
 +
For this part of the exercise we are presented with broken code.  HashMap is not thread-safe.
 +
 
 +
<syntaxhighlight lang="java">
 +
private final Map<String, Integer> map;
 +
public StockPortfolio() {
 +
this.map = new HashMap<>();
 +
}
 +
</syntaxhighlight>
 +
 
 +
Luckily, ConcurrentHashMap ensures that all of its methods are thread-safe.
  
  <nowiki>private final ConcurrentMap<String, Integer> map;</nowiki>
+
{{Warning|Do NOT use synchronized anywhere in this class. Leverage ConcurrentMap's thread safety.}}
  
it suffers from an atomicity race:
+
Our work is not done here.  ConcurrentHashMap is unable to prevent the read-modify-write atomicity race in transfer.  How will you fix the atomicity race?
  
<nowiki>private int transfer(String listingSymbol, int deltaShareCount) {
+
<syntaxhighlight lang="java">
Integer oldValue = this.map.get(listingSymbol);
+
private int transfer(String listingSymbol, int deltaShareCount) {
 +
Integer oldValue = map.get(listingSymbol);
 
Integer newValue;
 
Integer newValue;
 
if (oldValue != null) {
 
if (oldValue != null) {
Line 44: Line 69:
 
newValue = deltaShareCount;
 
newValue = deltaShareCount;
 
}
 
}
this.map.put(listingSymbol, newValue);
+
map.put(listingSymbol, newValue);
 
return newValue;
 
return newValue;
}</nowiki>
+
}
 +
</syntaxhighlight>
  
{{CodeToImplement|StockPortfolio|transfer|atomicity.stockportfolio.studio}}
+
{{CodeToImplement|StockPortfolio|transfer|atomicity.stockportfolio.exercise}}
  
 
{{ThreadSafe|private int transfer(String listingSymbol, int deltaShareCount)}}
 
{{ThreadSafe|private int transfer(String listingSymbol, int deltaShareCount)}}
  
NOTE: do not be concerned about ConcurrentMap vs ConcurrentHashMap.  The supplier's get method will return an instance of a thread-safe map(It will, in fact, be an instance of ConcurrentHashMap.)
+
=CheckThenActCourse and Course=
 +
For this section we will investigate class <code>CheckThenActCourse</code> which, although thread-safe, presents a check-then-act API which unfortunately leads clients to atomicity racesWe will implement an improved class <code>Course</code> which avoids this issue through better design.
  
==Course==
 
 
<youtube>gtcOC0RdnMA</youtube>
 
<youtube>gtcOC0RdnMA</youtube>
===Code To Investigate: CheckThenActCourse===
+
==CheckThenActCourse==
{{Warning|Although the class below is technically thread-safe, it offers check-then-act usage which leads to atomicity races.}}
+
===Code To Investigate===
 +
{{Warning|Although the class below is technically thread-safe, it offers check-then-act usage which leads clients to atomicity races.}}
  
{{CodeToInvestigate|CheckThenActCourse|isSpaceRemaining<br>add<br>drop|atomicity.course.studio}}
+
{{CodeToInvestigate|CheckThenActCourse|isSpaceRemaining<br>add<br>drop|atomicity.course.demo}}
  
 
  <nowiki>public class CheckThenActCourse {
 
  <nowiki>public class CheckThenActCourse {
Line 93: Line 120:
 
}</nowiki>
 
}</nowiki>
  
===Code To Implement: Course===
+
==Course==
We will build a thread-safe <code>Course</code> class with methods which do not lead clients towards atomicity races.
+
We will build a thread-safe <code>Course</code> class with an <code>addIfSpace(student)</code> method in place of the separate methods isSpaceRemaining() to check and add(student) to act from <code>CheckThenActCourse</code>.  This better design does not lead clients towards atomicity races.
 +
===Code To Investigate===
 +
====drop====
 +
{{ThreadSafe|public boolean drop(Student student)}}
  
{{CodeToImplement|Course|addIfSpace<br>drop|atomicity.course.studio}}
+
Removes the student from the course if the student was enrolled (the remove method returns just the status you need).
 +
 
 +
NOTE: This method is thread safe.
 +
 
 +
<nowiki> public boolean drop(Student student) {
 +
synchronized (this.students) {
 +
return this.students.remove(student);
 +
}
 +
}</nowiki>
 +
 
 +
NOTE: This method synchonizes on the students Collection.
 +
 
 +
===Code To Implement===
 +
====addIfSpace====
 +
{{CodeToImplement|Course|addIfSpace|atomicity.course.exercise}}
  
 
{{ThreadSafe|public boolean addIfSpace(Student student)}}
 
{{ThreadSafe|public boolean addIfSpace(Student student)}}
Line 104: Line 148:
 
NOTE: Must be thread safe.
 
NOTE: Must be thread safe.
  
{{ThreadSafe|public boolean drop(Student student)}}
+
NOTE: This method must synchronize on the same Object as <code>drop(student)</code>.
 
 
Removes the student from the course if the student was enrolled (the remove method returns just the status you need).
 
 
 
NOTE: Must be thread safe.
 
  
 
=Testing Your Solution=
 
=Testing Your Solution=
 
==Correctness==
 
==Correctness==
{{TestSuite|AtomicityTestSuite|atomicity}}
+
{{TestSuite|_AtomicityTestSuite|atomicity}}
  
:{{TestSuite|WordCountAtomicityTestSuite|atomicity.wordcount.studio}}
+
:{{TestSuite|_WordCountAtomicityTestSuite|atomicity.wordcount.exercise}}
  
{{TestSuite|StockPortfolioAtomicityTestSuite|atomicity.stockportfolio.studio}}
+
{{TestSuite|_StockPortfolioAtomicityTestSuite|atomicity.stockportfolio.exercise}}
  
{{TestSuite|CourseAtomicityTestSuite|atomicity.course.studio}}
+
{{TestSuite|_CourseAtomicityTestSuite|atomicity.course.exercise}}

Latest revision as of 17:42, 17 August 2023

Motivation

Many race conditions can be prevented by proper encapsulation avoiding check-then-write and read-then-modify-then-write patterns.

Background

Take a look at the synchronized and lock sections of the reference page

Concurrency Tutorial

Synchronized Methods
Intrinsic Locks

ConcurrentMap

compute

Lecture

Song to Recall

Frère Jacques four voice round.png
Frère Jacques, Frère Jacques, Get then put is not atomic
Dormez-vous? Dormez-vous? Call compute. Call compute.
Sonnez les matines! Sonnez les matines!        Use ConcurrentHashMap! Use ConcurrentHashMap!
Ding, dang, dong. Ding, dang, dong. Or say shoot. Or say shoot.

SuspectWordCount

Code To Fix: countWords

Attention niels epting.svg Warning:Do NOT use synchronized here. ConcurrentMaps are already thread safe.

fix the code to remove the atomicity race.

class: SuspectWordCount.java Debugging icon.png
methods: countWords
package: atomicity.wordcount.exercise
source folder: student/src/main/java

method: public static Map<String, Integer> countWords(Iterable<String> words) Parallel.svg (parallel implementation required)

StockPortfolio

note: somewhat out of date video.

Code To Fix

For this part of the exercise we are presented with broken code. HashMap is not thread-safe.

private final Map<String, Integer> map;
public StockPortfolio() {
	this.map = new HashMap<>();
}

Luckily, ConcurrentHashMap ensures that all of its methods are thread-safe.

Attention niels epting.svg Warning:Do NOT use synchronized anywhere in this class. Leverage ConcurrentMap's thread safety.

Our work is not done here. ConcurrentHashMap is unable to prevent the read-modify-write atomicity race in transfer. How will you fix the atomicity race?

private int transfer(String listingSymbol, int deltaShareCount) {
	Integer oldValue = map.get(listingSymbol);
	Integer newValue;
	if (oldValue != null) {
		newValue = oldValue + deltaShareCount;
	} else {
		newValue = deltaShareCount;
	}
	map.put(listingSymbol, newValue);
	return newValue;
}
class: StockPortfolio.java Java.png
methods: transfer
package: atomicity.stockportfolio.exercise
source folder: student/src/main/java

method: private int transfer(String listingSymbol, int deltaShareCount) Sequential.svg (thread-safe required)

CheckThenActCourse and Course

For this section we will investigate class CheckThenActCourse which, although thread-safe, presents a check-then-act API which unfortunately leads clients to atomicity races. We will implement an improved class Course which avoids this issue through better design.

CheckThenActCourse

Code To Investigate

Attention niels epting.svg Warning:Although the class below is technically thread-safe, it offers check-then-act usage which leads clients to atomicity races.
class: CheckThenActCourse.java DEMO: Java.png
methods: isSpaceRemaining
add
drop
package: atomicity.course.demo
source folder: src//java
public class CheckThenActCourse {
	private final Collection<Student> students;
	private final int limit;

	public CheckThenActCourse(int limit, Supplier<Collection<Student>> collectionSupplier) {
		this.students = collectionSupplier.get();
		this.limit = limit;
	}

	public int getLimit() {
		return this.limit;
	}

	public boolean isSpaceRemaining() {
		synchronized (this.students) {
			return this.students.size() < this.limit;
		}
	}

	public void add(Student student) {
		synchronized (this.students) {
			this.students.add(student);
		}
	}

	public boolean drop(Student student) {
		synchronized (this.students) {
			return this.students.remove(student);
		}
	}
}

Course

We will build a thread-safe Course class with an addIfSpace(student) method in place of the separate methods isSpaceRemaining() to check and add(student) to act from CheckThenActCourse. This better design does not lead clients towards atomicity races.

Code To Investigate

drop

method: public boolean drop(Student student) Sequential.svg (thread-safe required)

Removes the student from the course if the student was enrolled (the remove method returns just the status you need).

NOTE: This method is thread safe.

	public boolean drop(Student student) {
		synchronized (this.students) {
			return this.students.remove(student);
		}
	}

NOTE: This method synchonizes on the students Collection.

Code To Implement

addIfSpace

class: Course.java Java.png
methods: addIfSpace
package: atomicity.course.exercise
source folder: student/src/main/java

method: public boolean addIfSpace(Student student) Sequential.svg (thread-safe required)

Adds the student if there is space under the limit specified to the constructor and returns whether or not the add actually occurred.

NOTE: Must be thread safe.

NOTE: This method must synchronize on the same Object as drop(student).

Testing Your Solution

Correctness

class: _AtomicityTestSuite.java Junit.png
package: atomicity
source folder: testing/src/test/java
class: _WordCountAtomicityTestSuite.java Junit.png
package: atomicity.wordcount.exercise
source folder: testing/src/test/java
class: _StockPortfolioAtomicityTestSuite.java Junit.png
package: atomicity.stockportfolio.exercise
source folder: testing/src/test/java
class: _CourseAtomicityTestSuite.java Junit.png
package: atomicity.course.exercise
source folder: testing/src/test/java