---
# CP Lecture Notes

---
# TO DO 2021

* prepare interactice sessions

- 11 Petri nets
  - update pointer to new Squeak.js implementatiom

- 12 Architecture
  * repair or replace JavaSpaces demo

- Check pending 2017 notes
- Add some notes to Lab solutions slides

# DONE 2021

- migrated PP to squeak.js

---
# 2017 changes

- Added notes to all lectures
- 4 Safety patterns: Added references to software transactional memory for Java
- 12 Petri nets
  - fixed naming of markings -- was sometimes m or mu

## TO DO 2017

* look at new Java 8 concurrent collection implementations 

- 4 Safety patterns
  - CP containment pattern unclear (Students think there is a magical container object) Need a better example ...

- 5 Liveness & Guarded Methods
  - guarded methods (5): add bounded Counter with targeted notifications for just decrementors or incrementors? Replace notifying long example?

- 7 Liveness & Asynchrony
  * short lecture (2017: only 1 hour, including lab solutions!) -- add more on JUC?
  - Add picture to show where we get asynchrony (show threads of Clients, Server, Helpers)
  - Fix future code to use autoboxing
  - rename FutureDemo (FutureTask?) to JUCfutureDemo (JUCFutureTask?); Add an Executer

- 8 Condition Objects
  - short lecture (60") -- need more examples?
  - Building example -- there is no synchronized state of Building
    - can we make it more interesting? (store list of people in building)

- 9 Fairness lecture
  - also short (15")
  - add lock-splitting example?

- 11 Actors
  - Slide 25 should show the message flow
  - Need more figures to explain the code

---
# 2015 changes
- updated SimpleThread Java/LTSA examples -> Tortoise/Hare race

---
# 2012 CHANGES

- Moved Examples to own repo
- Converted all slides to Keynote
- Added Lab solution reminders

## 4. Safety Patterns
- ML added transactional memory slides

* Add some slides on synchronized Singleton?

	http://www.ibm.com/developerworks/java/library/j-dcl/index.html

ML: One place where the double checked locking might fit is the Safety Patterns lecture.
In the same lecture we could also mention the "Don't let {this} escape during construction" rule. If you think  about immutable objects, the only time when their state is not correct is while being constructed. If during their constructor the this pointer can escape, their incomplete state might actually be visible to other threads.

## 5. Liveness
- expanded slide 32 on handling InterruptedException

## 8. Condition Objects
- added comment: where is the deadlock cycle in nested monitors?
- BoundedCounterCondition: explain logic
  - why do we need to sync on notMin? (could lose signals) 

## 9. Fairness
- Added examples for each of the fairness definitions in slide 8
- Cleaned up code of optimistic bounded counter

## 10. Petri Nets
- Remove second EToys implementation slide (leftover draft version?) (DONE)

## 11. Parallelism
Before the lecture:
- Added several introductory slides
- Restructured the outline
- Removed the various charts for the word count problem
After the lecture:
- Added a few more questions in the What you should know! section
- Added the Gophers comics slide. 
- Fixed the slide with Emergent Sorting
- Improved the Amdahl’s Law slide

## 12. Architecture
- Changed Fibonacci Linda example to use BigIntegers

---
# TO DO

## 2. Java and Concurrency
* Why do we do the following in the clock instead of setting a boolean?
  - while(Thread.currentThread() == clockThread) {

## 3. Safety
- Swapped Checking Safety and Conditional Synchronization
* Add safety property to check for conditional synchronization example?

## 7. Asynchrony
* Slide 19 - tail calls - access to state in sendNotification should be synchronized! (via a getter)
* Early replies -- show a simpler example with just a new Thread but no Slot?
* Show Fibonacci example with Thread Pool?

## 8. Condition Objects
* Finished in 60 minutes! -- ADD SOMETHING MORE ON SEMAPHORES! ...

## 11. Lab 2
- Golf exercise has a race condition? Put a player 5 and two players 1 in the queue.  When the player 5 is done, both players 1 get balls but only 1 is hired out!

## 13. Parallelism (notes)
- Ask Cortesi for material from his parallelism course?
- "parallelism" means simultaneous or "physically at the same moment" -- but what does this mean? In physics "simultaneous" is not well-defined due to relativity effects.
- Would be nice to have a high-level description of one of these cluster-based physics simulations!
Alternatively get a real example from the cluster users!
- Steps to create parallel programs: compare to Carriero & Gelernter
- Check out Rodric Rabbah slideware.
- NB: with many kinds of parallelism, total time is often bounded by the slowest process (task and hybrid forms).
- "Stealing queue" for thread pools to steal tasks from other threads?
- Select max in parallel -- can we simplify the code? Split into algorithm and decomposition? Needs a diagram?
- Similarly can we solve mergesort in a way that separates the algorithm from the management o parallelism?
- Problem with word counter: contention due to synchronization (too coarse in original version) leads to slowdown already after 2 threads.
- With word counter tuning see that extra threads may help by ensuring that there is always a thread to do something. With threads equal to cores might be slower due to waiting threads. Optimum is often # cores + 1. Threshold may vary.

Further observations by Mircea:
- There should be an assignment after this lecture!!
- The introduction could be longer and more historical. Something which would have brought on display the first von Neumann machines and slowly come to nowadays.
- The Understand the problem slide is both understand the problem and identify hotspots. Should be split.
- Elaborate on the emergent sorting; maybe show a video
- the data dependencies example is not great. need a better example.
- the ExecutorService slide is missing a discussion on shutting down services
- Should have added a riddle from the Goetz book (e.g. why is a given piece of code deadlocking?)

---
# 2010 CHANGES

- Changed course title to: "Concurrency: State Models and Design Patterns"
  (contrast Pascal Felber's course on foundations and algorithms)

## 2. Java and Concurrency
- FSP syntax: guarded action does not require choice

## 3. Safety
- Added busy-wait logic as note to slide

## 7. Liveness and Asynchrony
- Adapted future sequence diagram to example solution!
- Moved JUC discussion here

## 8. Condition Objects
- Discuss how to fix the slot nested monitor
- Discuss more solutions to Nested Monitors
  - lock just a single object (host or CO)
  - remove host synchronization (if immutable)
- Added example of JUC semaphores

## 12. Architecture
* Simple thread pool example -- do something concrete
- (1) Fibonacci or (2) filling an array with values (one task per array slot)

* Add something on transactional memory?
http://en.wikipedia.org/wiki/Software_transactional_memory
AtomJava, JSTM, Deuce

## 13. Parallelism
* Add a lecture on parallelism (FP and JR)

- See: http://groups.csail.mit.edu/cag/ps3/index.shtml

---
# JCP topics:
- p 35 Stale data; p 37 Volatile variables; p 39 Publication & escape
- p 42 Thread confinement; p 52 Safe publication
- p 94 Synchronizers (Latches, Barriers etc)
- p 101 Efficient caching
* p 113 Thread pools; p 170 Thread pool size
- p 211 Open calls (DL avoidance)
- p 216 Thread dumps; p 218 Avoid thread priorities
- p 225 Amdahl's Law
- p 321 Compare-and-swap; p 329 Lock-free algorithms
- p 337 Java Memory Model

---
# 2009 CHANGES (FS-09)
## General:
- Fixed template (logo)
- Added roadmaps
- Removed transparency & shading
- Typewriter -> Courier
- Migrated examples to svn
- add pointer to svn project name for each example in slides!

## 1. Intro
- updated overview, reading list, schedule

## 2. Java and Concurrency
- simplified Clock (use Date instead of Calendar)
- added AccountBAD to illustrate race condition

## 3. Safety and Synchronization
- merged in safety properties from Liveness lecture
- added UML diagram for Slot classes
- made Slot, Producer, Consumer generic
- added ProducerConsumerTest

## 4. Safety Patterns
- added immutable Complex example
- implemented BalkingBoundedCounter
- added test to provoke race condition if synchronization is missing
- made ExpandableArray generic
- implemented LinkedCell
- implemented and extended ResourceVariable example

## 5. Liveness and Guarded Methods
- moved Safety stuff to lecture 3
- merged rest with old lecture 6 (Guarded methods)
- refactored and updated BoundedCounter examples

## 6. Lab session
- updated to generics

## 7. Liveness and Asynchrony [was 8]
- implemented all examples
- refactored Future to no longer use Slot

## 8. Condition Objects [was 9]
- minor cleanup
- replaced CountCondition by new Permit implementation

## 9. Fairness [was 10]
- revised optimistic bounded counter

## 10. Petri Nets
- updated Petit Petri web page
- added some slides on Petit Petri

## 11. Lab2
- updated to generics
- renamed classes:
	ReadersWriters -> SafeReadersWriters
	ReadWrite -> ReadWritePolicy
	SafeReadWrite -> SafeReadWritePolicy
	WritersPriorityReadWrite -> WritersPriorityPolicy
	FairReadWrite -> FairReadWritePolicy
12. Architecture [was 11]
- use generic Slot and autoboxing for active prime example
- implemented Tuple space example with Fly

---
# 2005 CHANGES (W06-1)
Various cosmetic changes, notes etc.

## 1. Introduction
- Converted UML figures to OmniGraffle

## 2. Java and Concurrency
- Changed Java overview slide
- Moved TwoThreadDemo.main to SimpleThread.main
- Rewrote Clock applet as an application (Frame)
- Added Account example to illustrate wait and notify

## 6. Guarded methods
- fixed and animated race condition example

## 8. Liveness and Asynchrony
- Revised Future and FutureDemo to force some interleaving

## 9. Condition Objects
- Added material from Bowbeer, Goetz, Holmes, Lea and Peierls
  [courtesy Doug lea]

## Labs
- converted all lab applets to applications

---
# 2003 CHANGES

## 1. Intro
- added sequence diagram to OCCAM example

## 2. Java and Concurrency
- Added FSP Syntax Summary
- added call to start() (java.lang.Runnable)
- added clock applet screenshot

## 5. Safety and Liveness Properties
- added note & question about transparency
- added property Ok (Busy-Wait revisited)
- added SAFE COIN property and REPICK property
- added race condition to dining phils table

## 6. Liveness and Guarded Methods
- added notify vs notifyAll race condition

## 8. Liveness and Asynchrony
- fixed race condition in Future implementation!
  - put val back into slot
- added some examples

## 10. Fairness and Optimism
- added notes to explain how RW-PROGRESS *lowers* priority
  of release ops!

## 13. Petri Nets
- made special non-animated version

## Lab 1
- made problems & solutions different packages (for netscape)
- created ant build files for all
- cleaned up some HTML
- moved redundant package imports
- Switched Rotator and Garden exercises
- Added more hints to Rotator exercise

## Lab 2
- Removed thread.stop from Rotatingpanel.java!!!
- Added figures to RW showing how to overlap times!
- fixed layout RW (cuts off writer #4)
- fixed layout of single lane bridge! (cuts off menu choice)

---