---------------- SMP, NUMA, etc. UMA - unified memory access: shared bus, or cross-bar switch (or some other variant of switching) difference of multicore chips to multiprocessors: - can have shared caches - fault tolerance is not as good with shared components cache coherence: Read operation should return last value written, independently of which processor executed it; Hyper-threading: one core is divided into two logical ones. Each has its own state of the program (registers, etc.), but the functional units are shared. Good for pipelines, long memory operations etc., but halves the size of the cache... OSes types: - one CPU:one OS instance, memory divided into distinct parts, IO etc. shared - problem with (disk) caches - master-slave: OS is on one CPU - system calls, etc. directed to this one CPU - SMP: one copy of OS in memory, but anyone can run it - big kernel lock or fine grained locking (...deadlocks bait) - TSL: always writes a value (1) => cache ping-pong, remedy: double check lock pattern - first normal read, then TSL - to spin or not to spin (and switch thread) - switching has considerable overhead, but spinning is waste of time - prediction based on benchmarking, dynamically based on last N attempts to lock, ... Scheduling: - priority for threads that hold some spinlock - space sharing vs gang scheduling http://www-cs-students.stanford.edu/~dbfaria/quals/summaries/Culler-chap5.txt https://www.ics.forth.gr/tech-reports/2011/2011.TR418_Directory_based_Cache_Coherence_Protocol.pdf Tanenbaum: chapter on multiprocessing ---------------- NON-BLOCKING: Wait free solution: every process will finish in a finite number of its own steps. The strongest category, bounds on waiting always exist. Lock free solution: guarantees some process will finish in a finite number of its own steps. Weaker category, starvation of all processes will not occur and progress will not stop should any single process block or crash. Example: using compare/exchange to write only if we had a correct value. If we can succeed even if other thread blocks, it’s lock free otherwise it’s basically a spinlock. It’s not wait free, because if the other thread accessed the data with “wrong timing”, the first thread may be still trying compare/exchange.. Obstruction free solution: guarantees every process will finish in a finite number of its own steps provided other processes take no steps. Even weaker category, with the practical implication that progress will not stop should any single process block or crash. ---------------- ATOMIC: Atomicity: which instructions must have indivisible effects. Load-Link/Store-Conditional: two instructions that can be used to implement CAS (compare-and-set). ---------------- MEMORY MODEL: formal sets of rules that define how memory operations behave. At the processor level, a memory model defines necessary and sufficient conditions for knowing that writes to memory by other processors are visible to the current processor, and writes by the current processor are visible to other processors. Sequential Consistency: too strong, inefficient implementation Instructions performed by different processors are arbitrarily interleaved. But all processors see the same interleaving. There is a global order. Happen-before Java Memory model: a partial ordering on memory operations (read field, write field, lock, unlock) and other thread operations (start and join). When one action happens before another, the first is guaranteed to be ordered before and visible to the second. The rules of this ordering are as follows: - Each action in a thread happens before every action in that thread that comes later in the program's order. - An unlock on a monitor happens before every subsequent lock on that same monitor. - A write to a volatile field happens before every subsequent read of that same volatile. - A call to start() on a thread happens before any actions in the started thread. - All actions in a thread happen before any other thread successfully returns from a join() on that thread. Happen-before: can be roughly described as a transitive closure of the program order and the synchronization order. Data-race: two threads access the same memory location, at least one access is write, and there is no happens before relation between them. Correctly synchronized programs have sequentially consistent semantics. Causality loop (?): Initially: A = 0; B = 0; Thread1: tmp1 = A; B = 1; Thread2: tmp2 = B; A = 1; Result: Is tmp1 = 1, tmp2 = 1 possible? Yes: reordering of the read-write... How can final fields appear to change their values? Java String implementation with length and offset: reordering... references: http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html http://d3s.mff.cuni.cz/~ceres/sch/osy/text/ch02s04s03.html http://www.cs.umd.edu/~pugh/java/memoryModel/jsr133.pdf http://preshing.com/20130823/the-synchronizes-with-relation/