Midterm#2 Topics and Promises.doc

Midterm#2 Topics and Promises Topics Notation for concurrency co s1; // s2; // ... // sn; oc : concurrency process name { ... } : background process S; : atomic action; critical section; mutual exclusion; granularity considerations await(B) : conditional synchronization; barrier synchronization await(B) S; : conditional atomic action Java Support for Concurrency Synchronized : specifies critical section using an object as lock Locks are reentrant Locks can be temporarily given up : wait and notify Critical section problem mutual exclusion absence of deadlock and livelock absence of unnecessary delays eventual entry (relates to fairness) Fair Solutions Tie Breaker Ticket Algorithm Barrier Synchronization Shared Counter Flags and Coordinators Symmetric Barriers Data Parallel MasPar Example Parallel Prefix and Parallel Linked List Length Semaphores Abstraction with two services P (wait) and V (signal) Critical section problem and semaphores Java synchronized and semaphores Barriers and semaphores Producer / Consumer Problem; Dining Philosophers Problem; Reader/Writer Problems Monitors monitors and conds wait(cv), wait(cv, rank), signal(cv), signal_all(cv), empty(cv), minrank(cv) signal and wait versus signal and continue queues, priority queues, BPOTs, heaps and analysis monitor examples semaphores, bounded buffers, readers/writers, shortest-job-next, sleeping barber CSCAN/SCAN disk scheduler (bitonic lists) Java synchronized, wait/notify/notify_all Single lane bridge problem using semaphores and monitors Parallelizing Prim’s and Floyd’s Message passing (MPI on Zephyr) Distributed objects; garbage collection issues; synchronous vs asynchronous Low level messaging: TCP/IP; UDP; multicast UDP RMI Request broker discovery, join, lookup packet storm avoidance Tuple spaces read, take, readIfExists, takeIfExists, write eval in pure tuple spaces leases on tuples Oblivious Comparison Exchange Sorts Proof of correctness for 0-1 data implies from for all