Slide 1Summary of Our DiscussionsProgramming StrategyGeneral Programming StrategyCoding Style and StandardsReaders/Writers: A Complete ExampleReaders/Writer: Solution StructureSolution DetailsSelf-criticism can lead to self-understandingReaders/Writer: Using MonitorsSolution Details: ReadersSolution Details: WritersDeadlock Solution Details: ReadersSlide 141Concurrent Programming Issues & Readers/Writers2Summary of Our DiscussionsDeveloping and debugging concurrent programs is hardNon-deterministic interleaving of instructionsSafety: isolation and atomicityScheduling: busy-waiting and blockingSynchronization constructsLocks: mutual exclusionCondition variables: wait while holding a lockTransactions: isolation by conflict detection and rollback, atomicity by bufferingSemaphores: Mutual exclusion (binary) and condition synchronization (counting)How can you use these constructs effectively?Develop and follow strict programming style/strategy3Programming StrategyDecompose the problem into objectsObject-oriented style of programmingIdentify shared chunk of stateEncapsulate shared state and synchronization variables inside objectsDon’t manipulate shared variables or synchronization variables along with the logic associated with a threadPrograms with race conditions always fail.A. True, B. False4General Programming StrategyTwo step processThreads:Identify units of concurrency – these are your threadsIdentify chunks of shared state – make each shared “thing” an object; identify methods for these objects (how will the thread access the objects?)Write down the main loop for the threadShared objects:Identify synchronization constructsMutual exclusion vs. conditional synchronizationCreate a lock/condition variable for each constraintDevelop the methods –using locks and condition variables – for coordination5Coding Style and StandardsAlways do things the same wayAlways use locks and condition variablesAlways hold locks while operating on condition variablesAlways acquire lock at the beginning of a procedure and release it at the endIf it does not make sense to do this  split your procedures furtherAlways use while to check conditions, not if(Almost) never sleep(), yield(), or isLocked() in your codeUse condition variables to synchronizewhile (predicate on state variable) { conditionVariablewait(&lock); };while (predicate on state variable) { conditionVariablewait(&lock); };6Readers/Writers: A Complete ExampleMotivationShared databases accessesExamples: bank accounts, airline seats, …Two types of usersReaders: Never modify dataWriters: read and modify dataProblem constraintsUsing a single lock is too restrictiveAllow multiple readers at the same time…but only one writer at any timeSpecific constraintsReaders can access database when there are no writersWriters can access database when there are no readers/writersOnly one thread can manipulate shared variables at any time7Readers/Writer: Solution StructureBasic structure: two methodsDatabase::Read() { Wait until no writers; Block any writers; Access database; Let in one writer or reader; }Database::Read() { Wait until no writers; Block any writers; Access database; Let in one writer or reader; }Database::Write() { Wait until no readers/writers; Write database; Let all readers/writers in; }Database::Write() { Wait until no readers/writers; Write database; Let all readers/writers in; }8Solution DetailsPublic Database::Read() { dbLock.lock(); while(writer) { dbAvail.wait(); } reader++; dbLock.unlock(); Read database; dbLock.lock(); reader--; if(reader == 0) { dbAvail.singal();} dbLock.unlock();}Public Database::Read() { dbLock.lock(); while(writer) { dbAvail.wait(); } reader++; dbLock.unlock(); Read database; dbLock.lock(); reader--; if(reader == 0) { dbAvail.singal();} dbLock.unlock();}Public Database::Write() { dbLock.lock(); while(reader > 0 || writer){ dbAvail.wait();} writer = true; dbLock.unlock(); Write database; dbLock.lock(); writer = false; dbAvail.signalAll(); dbLock.unlock(); }Public Database::Write() { dbLock.lock(); while(reader > 0 || writer){ dbAvail.wait();} writer = true; dbLock.unlock(); Write database; dbLock.lock(); writer = false; dbAvail.signalAll(); dbLock.unlock(); }Lock dbLock;Condition dbAvail;int reader = 0;bool writer = false;Lock dbLock;Condition dbAvail;int reader = 0;bool writer = false;This solution favors1.Readers2.Writers3.Neither, it is fairThis solution favors1.Readers2.Writers3.Neither, it is fair9Self-criticism can lead to self-understandingOur solution works, but it favors readers over writers.Any reader blocks all writersAll readers must finish before a writer can startLast reader will wake any writer, but a writer will wake readers and writers (statistically which is more likely?)If a writer exits and a reader goes next, then all readers that are waiting will get throughAre threads guaranteed to make progress?A. Yes B. No10Readers/Writer: Using MonitorsBasic structure: two methodsState variablesDatabase::Read() { Wait until no writers; Access database; Wake up waiting writers; }Database::Read() { Wait until no writers; Access database; Wake up waiting writers; }Database::Write() { Wait until no readers/writers; Access database; Wake up waiting readers/writers; }Database::Write() { Wait until no readers/writers; Access database; Wake up waiting readers/writers; }Class RWFairLock { AR = 0; // # of active readers AW = false; // is there an active writer public bool iRead; Condition okToRead; Condition okToWrite; LinkedList<RWFairLock> q; Lock lock;Class RWFairLock { AR = 0; // # of active readers AW = false; // is there an active writer public bool iRead; Condition okToRead; Condition okToWrite; LinkedList<RWFairLock> q; Lock lock;11Solution Details: ReadersPublic Database::Read() { StartRead(); Access database; DoneRead(); }Public Database::Read() { StartRead(); Access database; DoneRead(); }Private Database::StartRead() { lock.Acquire(); iRead = true; q.add(this); while (AW || !q.peek().iRead) {okToRead.wait(&lock); } AR++;