Concurrent Programming Issues & Readers/Writers1Summary of Our DiscussionsDeveloping and debugging concurrent programs is hard¾Non-deterministic interleaving of instructions¾Nondeterministic 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, 2y,atomicity by buffering¾ Semaphores: Mutual exclusion (binary) and condition synchronization (counting)How can you use these constructs effectively?¾ Develop and follow strict programming style/strategyProgramming 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 threadP ith diti l f il3Programs with race conditions always fail.¾ A. True, B. FalseGeneral Programming StrategyTwo step processThreads:¾Identify units of concurrencythese are your threads¾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¾C l k/ di i i bl f h i4¾Create a lock/condition variable for each constraint¾ Develop the methods –using locks and condition variables – for coordinationCoding 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 ifwhile (predicate on state variable) {conditionVariableÆwait(&lock); }while (predicate on state variable) {conditionVariableÆwait(&lock); }5(Almost) never sleep(), yield(), or isLocked() in your code¾ Use condition variables to synchronize};};Readers/Writers: A Complete ExampleMotivation¾ Shared databases accesses Examples: bank accounts, airline seats, …Two types of usersTwo 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 time6¾ 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 timeReaders/Writer: Solution StructureBasic structure: two methodsDatabase::Read() {Wait until no writers;Block any writers;Database::Read() {Wait until no writers;Block any writers;yAccess database;Let in one writer or reader; }yAccess 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; 7Let all readers/writers in; }Let all readers/writers in; }Solution DetailsPublic Database::Read() {Public Database::Read() {P bl D b W () {P bl D b W () {Lock dbLock;Condition dbAvail;int reader = 0;bool writer = false;Lock dbLock;Condition dbAvail;int reader = 0;bool writer = false;Public Database::Read() {dbLock.lock();while(writer) {dbAvail.wait();}reader++;dbLock.unlock();Read database;dbLock.lock();reader--;Public Database::Read() {dbLock.lock();while(writer) {dbAvail.wait();}reader++;dbLock.unlock();Read database;dbLock.lock();reader--;Public Database::Write() {dbLock.lock();while(reader > 0 || writer){dbAvail.wait();}writer = true;dbLock.unlock();Write database;dbLock.lock();writer = false;dbAvail signalAll();Public Database::Write() {dbLock.lock();while(reader > 0 || writer){dbAvail.wait();}writer = true;dbLock.unlock();Write database;dbLock.lock();writer = false;dbAvail signalAll();8if(reader == 0) {dbAvail.singal();}dbLock.unlock();}if(reader == 0) {dbAvail.singal();}dbLock.unlock();}dbAvail.signalAll();dbLock.unlock(); }dbAvail.signalAll();dbLock.unlock(); }This solution favors1. Readers2. Writers3. Neither, it is fairThis solution favors1. Readers2. Writers3. Neither, it is fairSelf‐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¾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. No9Readers/Writer: Using MonitorsBasic structure: two methodsDatabase::Read() {Wait until no writers;Access database;Database::Read() {Wait until no writers;Access database;State variablesWake up waiting writers; }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; }10State variablesAR = 0; // # of active readersAW = false; // is there an active writerWR = 0; // # of waiting readersWW = 0; // # of waiting writersCondition okToRead;Condition okToWrite;Lock lock;AR = 0; // # of active readersAW = false; // is there an active writerWR = 0; // # of waiting readersWW = 0; // # of waiting writersCondition okToRead;Condition okToWrite;Lock lock;Solution Details: ReadersPublic Database::Read() {StartRead();Access database;DoneRead(); }Public Database::Read() {StartRead();Access database;DoneRead(); }AR = 0; // # of active readersAW = false; // is there an active writerWR = 0; // # of waiting readersWW = 0; // # of waiting writersCondition okToRead;Condition okToWrite;AR = 0; // # of active readersAW = false; // is there an active writerWR = 0; // # of waiting readersWW = 0; // # of waiting writersCondition okToRead;Condition okToWrite;Private Database::StartRead() {lock.Acquire();while (AW || WW > 0) {WR++;okToRead.wait(&lock);WR--;Private Database::StartRead() {lock.Acquire();while (AW || WW > 0)