MRKT 452 Lecture 9: Notes
11 Jun 2018
School
Department
Course
Professor
©2018 An Li. All rights reserved. 1
COMP 409 Winter 2018
Professor Clark Verbrugge
Some elements from http://www.wikinotes.ca/COMP_409.
Contents
Lecture 1 – Tuesday, January 9, 2018 ......................................................................... 6
Concurrency ............................................................................................................ 6
Processes ................................................................................................................ 6
Threads .................................................................................................................... 6
Threads interactions ............................................................................................. 6
Thread ...................................................................................................................... 7
OS part ................................................................................................................. 7
User part ............................................................................................................... 7
Amdahl’s Law .......................................................................................................... 7
Threads are good for… ............................................................................................ 8
Threads are bad for… .............................................................................................. 9
Programming spectrum ........................................................................................... 9
Example: Single write system .................................................................................. 9
Example: ................................................................................................................ 10
Lecture 2 – Tuesday, January 16, 2018 ..................................................................... 10
Recall from last lecture .......................................................................................... 10
Hardware (very high-level approach) ..................................................................... 10
Basic uniprocessor (UP) ..................................................................................... 10
Multiprocessor .................................................................................................... 10
Symmetric MP (SMP) ......................................................................................... 11
CMP (On-chip MP) ............................................................................................. 11
CMT/FMT (Coarse/fine-grained multi-threaded) ................................................ 12
SMT (Simultaneous multithreading).................................................................... 12
IPC (Instructions per cycle)................................................................................. 13
Atomicity ................................................................................................................ 14
2 ©2018 An Li. All rights reserved.
Lecture 3 – Thursday, January 18, 2018 ................................................................... 15
Mutual exclusion (ME) ............................................................................................ 17
Peterson’s 2-process tiebreaker algorithm ............................................................ 19
What we are looking for… .................................................................................. 20
Java and Pthreads ................................................................................................. 20
POSIX ................................................................................................................. 20
Java .................................................................................................................... 21
Lecture 4 – Tuesday, January 23, 2018 ..................................................................... 22
Java’s model .......................................................................................................... 22
Basic synchronization ............................................................................................ 23
Pthreads ................................................................................................................. 25
Threads .............................................................................................................. 25
Scheduling ............................................................................................................. 25
Mutual exclusion .................................................................................................... 25
Other locks ............................................................................................................. 26
Lecture 5 – Thursday, January 25, 2018 ................................................................... 27
Filter lock ............................................................................................................... 28
Classic locks .......................................................................................................... 28
Ticket algorithm .................................................................................................. 28
Bakery algorithm ................................................................................................ 29
Hardware primitives ............................................................................................... 29
Test and set (TS) .................................................................................................... 30
TS-Lock .............................................................................................................. 30
Fetch and Add (FA) ................................................................................................ 30
Compare and swap (CAS) ...................................................................................... 31
Queue locks ........................................................................................................... 31
MCS ................................................................................................................... 31
Lecture 6 – Tuesday, January 30, 2018 ..................................................................... 32
MCS Properties .................................................................................................. 32
CLH Lock ............................................................................................................... 32
Java’s locks ........................................................................................................... 33
©2018 An Li. All rights reserved. 3
Transition to fat lock ........................................................................................... 34
Semaphores and mutexes ..................................................................................... 34
Semaphores (Dijkstra, 1960s) ............................................................................. 35
Producer/consumer (bounded buffer) .................................................................... 35
Drawbacks of semaphores ................................................................................. 37
Lecture 7 – Thursday, February 1, 2018 .................................................................... 37
Monitors ................................................................................................................. 37
2 operations on condition variables ................................................................... 38
How does it work? ............................................................................................. 38
Atomic operations .............................................................................................. 39
Easy condition variable ...................................................................................... 39
Different semantics for condition variables: ........................................................... 40
Reader-Writer lock ............................................................................................. 40
Termination ............................................................................................................ 41
Priorities ................................................................................................................. 42
Lecture 8 – Tuesday, February 6, 2018 ..................................................................... 42
Barriers................................................................................................................... 43
Sense-reversing barrier ...................................................................................... 44
TSD/TLS ................................................................................................................. 45
In Java (TLS) ....................................................................................................... 46
TSD ........................................................................................................................ 46
Deadlock ................................................................................................................ 46
Lecture 9 – Thursday, February 8, 2018 .................................................................... 48
Deadlock (continued) ............................................................................................. 48
Coffman’s conditions ......................................................................................... 48
Livelock .............................................................................................................. 49
Race condition ................................................................................................... 49
Concurrent programs ............................................................................................. 50
Consensus.......................................................................................................... 51
Consensus problem ........................................................................................ 51
Simple atomic R/W register ............................................................................ 52
Document Summary
Lecture 1 tuesday, january 9, 2018 6. Lecture 2 tuesday, january 16, 2018 10. Lecture 3 thursday, january 18, 2018 15. Lecture 4 tuesday, january 23, 2018 22. Lecture 5 thursday, january 25, 2018 27. Lecture 6 tuesday, january 30, 2018 32. Lecture 7 thursday, february 1, 2018 37. Lecture 8 tuesday, february 6, 2018 42. Lecture 9 thursday, february 8, 2018 48. Lecture 10 thursday, february 15, 2018 53. There are lots of memory models 57. Lecture 11 thursday, february 22, 2018 58. Lecture 12 thursday, march 1, 2018 63. Lecture 13 tuesday, march 13, 2018 67. First, the data race free model 68. Failure of the lock-free stack and the aba problem 70. Lecture 14 tuesday, march 15, 2018 74. Lock free exchanger (2 threads exchange data) 77. Lecture 15 tuesday, march 20, 2018 79. Lecture 16 thursday, march 22, 2018 84. X10 (most popular of these languages) 86. Lecture 17 tuesday, march 27, 2018 89.
