Advanced Topics in Software Engineering 1,Midterm Review,4:00pm 5:20pm, 11/10/11 Open book and notes Four problems,Advanced Topics in Software Engineering 2,Midterm Review - 1,Overview What, why, concurrent vs sequential computation, models of concurrency (interleaving-based/true concurrency), semantics of correctness (safety & liveness), unique challenges in testing and debugging Shared variables The CS problem, correctness requirements, Petersons algorithm, Bakery algorithm, synchronization operation, SYN-sequence, RW-sequence, version-based tracing & replay,Advanced Topics in Software Engineering 3,Midterm Review - 2,Semaphore & Locks Binary semaphore, counting semaphore, lock, semaphores in Java, common patterns in semaphore-based programming, semaphore-based solutions to classical synchronization problems, fine-grained locking, PV-sequence, Lock/Unlock-sequence, permission-based tracing & replay,Advanced Topics in Software Engineering 4,Midterm Review - 3,Monitor Graphic representation, different signaling disciplines, monitor implementation, Java monitors, monitor-based solutions (dinning philosophers, bounded buffer, reader/writers), tracing/replay monitors (entry-based execution, simple and complete M-sequence) Message Passing Link/port/mailbox, synchronous vs asynchronous, rendezvous, selective wait, happened-before relation, integer/vector timestamps,Homework Problems,Exercises 3.5 Exercises 4.4, 4.11b., 4.18b, 4.24 Exercises 6.6,Advanced Topics in Software Engineering 5,Advanced Topics in Software Engineering 6,Simulating Counting Semaphores,public final class CountingSemaphore private int permits = 0; BinarySemaphore mutex (1); BinarySemaphore delayQ (0); public CoutingSemaphore (int initialPermits) permits = initialPermits; public void P () mutex.P (); (1) - permits; (2) if (permits 0) (3) mutex.V (); (4) delayQ.P (); (5) else mutex.V (); (6) public void V () mutex.P (); (7) + permits; (8) if (permits = 0) (9) delayQ.V (); (10) mutex.V (); (11) ,Advanced Topics in Software Engineering 7,A scenario,T1 T2 T3 T4,(1) (2) (3) (4),(1) (2) (3) (4),(7) (8) (9) (10),(7) (8) (9) *(10),(5),*(10),(5),Exercise 4.4,public void waitC() +numWaitingThreads; threadQueue.VP(mutex); mutex.P(); -numWaitingThreads; public void signalC() if (numWaitingThreads 0) threadQueue.V(); / continue in the monitor; perhaps send more signals ,Advanced Topics in Software Engineering 8,Advanced Topics in Software Engineering 9,Exercises 3.5,public final class CountingSemaphore private int permits = 0; BinarySemaphore mutex (1); BinarySemaphore delayQ (0); public CoutingSemaphore (int initialPermits) permits = initialPermits; public void P () mutex.P (); (1) - permits; (2) if (permits 0) (3) mutex.V (); (4) delayQ.P (); (5) else mutex.V (); (6) public void V () mutex.P (); (7) + permits; (8) if (permits = 0) (9) delayQ.V (); (10) mutex.V (); (11) ,Advanced Topics in Software Engineering 10,Questions?,