Multicore Programming Final Review
Outline Intro to Parallelism and Concurrency Parallel Programming – Algorithms and Analysis Concurrent Programming – Mutual Exclusion and Linearizability – Spin Locks – Monitors – Concurrent Data Structures
Intro to Parallelism and Concurrency Java Multi-thread Programming – Start() Join() Parallelism vs. Concurrency – Different concerns
Parallel Programming Sum Array – start(); join(); fork-join framework；Dag – Divide and Conquer Algorithms – Prefix-sum, Filter, Parallel Sorting Work 、Span and Parallelism Programming with Divide and Conquer to solve some practical problems
Concurrent Programming Multi-threads access the shared resources – Correctness and Efficiency How to describe the correctness of concurrent programs – Mutual exclusion – Linearizability – Deadlock-free – Starvation-free – Lock-free – Wait-free
Mutual Exclusion What is mutual exclusion? How to prove mutual exclusion? Peterson lock guarantees mutual exclusion, starvation-free and dead-lock free
Linearizability Why do we need Linearizability? What is Linearizability? How to decide a linearizable execution history? What is Sequential Consistency? What is the difference and relationship between SC and Lin?
Spin Locks Ideal lock implementations are inefficient What is spin? Spin locks implementation depends on the low-level Archi. Local spin is good for cache hit. TAS, TTAS, CLH, MCS etc.
Monitor Spin wait and blocking Condition – await(),signal(),signalAll() Re-check is necessary after being waken. – While(B) {x.await()} To avoid lost-wake-up – Using signalAll() instead of signal() Programming with monitors.
Concurrent Data Structures Linked-list Set – Coarse-grained Synchronization – Fine-grained Synchronization – Optimistic – Lazy – Lock-free Hand-over-hand Locking
考试时间和方式 考试时间： 4 月 27 日 14:30 – 16:30 考试方式：闭卷 参考资料：上课课件、教材、课堂练习和 平时作业
考试题型 简答题 （ 12 题选 10 题回答 共 70 分） – Amdhal 定理、线程创建销毁 Dag 图、 Spin Lock 、 Java 线程同步方法以及 Monitor 的正确使用、可 线性化的判断 编程题 （ 2 题 共 30 分） – Fork-Join Framework 求解具体问题 – 使用锁和条件对象实现具体的共享访问协议
Thanks for learning this course! Hoping it is helpful for your future career!