Concurrent ProgrammingWhat is concurrency?Slide 3AssumptionsWhy Use Concurrency?Concurrency Example: Producer / ConsumerProducer / Consumer – OutputSlide 8Critical Section (CS)Mutual ExclusionImplementing Mutual ExclusionMutual Exclusion – Version 1Version 1 – Is Mutual Exclusion Guaranteed?Version 1 – Guarantees mutual exclusionSlide 15Slide 16Slide 17Slide 18Slide 19Version 1 – Are Both Constraints Satisfied?Version 1 – Violates Constraint1Version 1 – Any new problems?Version 1 – Lockstep Synchronization ProblemSlide 24Slide 25Version 1 – AssessmentMutual Exclusion – Version 2Version 2 – Is Constraint1 Satisfied Now?Version 2 – Obeys Constraint1Slide 31Version 2 – Does the Lockstep Synchronization Problem Persist?Version 2 – Resolves Lockstep SynchronizationSlide 34Slide 35Version 2 – Any new problems?Version 2 – Violates Mutual ExclusionSlide 38Slide 39Version 2 – AssessmentMutual Exclusion – Version 3Version 3 – Any new problems?Version 3 – Introduces DeadlockSlide 44Slide 45Version 3 – AssessmentMutual Exclusion – Version 4Version 4 – Any new problems?Mutual Exclusion – Introduces Indefinite PostponementSlide 51Slide 52Slide 53Slide 54Version 4 – AssessmentMutual Exclusion – Dekker’s AlgorithmDijkstra’s development of Dekker’s AlgorithmDekker’s Algorithm – AssessmentPeterson’s AlgorithmSlide 61Mutual Exclusion PrimitivesSlide 63James Adkison Concurrent ProgrammingWorks CitedConcurrentProgrammingJames Adkison02/28/2008What is concurrency?“happens-before relation – A happens before B if A and B belong to the same process and A occurred before B; or A is the sending of a message and B is the receiving of that message” (Deitel)What is concurrency?“concurrent – Two events are concurrent if it cannot be determined which event occurred earlier by following the happens-before relation” (Deitel)AssumptionsUsing a single processor systemWorking with threads, not processesWorking with only two threadsAny level of interleaving is possibleMachine-level instructions are atomic (i.e. are executed indivisibly)Why Use Concurrency?Improved throughputthroughput – Amount of work performed per unit time.Improved responsivenesse.g. responsive GUIAppropriate / Required for problem domainConcurrency Example:Producer / ConsumerProducer:Writes integers 1 – 4 (in order) to a shared buffer and terminatesConsumer:Reads and sums the integers 1 – 4 from the shared bufferDisplay the sum total and terminateProducer / Consumer – OutputCorrect (Desired) Output:Producer writes 1Consumer reads 1Producer writes 2Consumer reads 2Producer writes 3Consumer reads 3Producer writes 4Terminating: Producer.Consumer reads 4Consumer read values totaling: 10.Terminating: Consumer.Producer / Consumer – OutputCorrect (Desired) Output:Producer writes 1Consumer reads 1Producer writes 2Consumer reads 2Producer writes 3Consumer reads 3Producer writes 4Terminating: Producer.Consumer reads 4Consumer read values totaling: 10.Terminating: Consumer.Sample Output:Consumer reads -1Producer writes 1Consumer reads 1Producer writes 2Producer writes 3Consumer reads 3Consumer reads 3Consumer reads values totaling: 6.Terminating: Consumer.Producer writes 4Terminating: producer.Critical Section (CS)“When a thread is accessing shared modifiable data.” (Deitel)Producer / Consumer: the shared mutable bufferint x = 10;Thread1 Thread2Read x Read xWrite 3xWrite -2xCritical SectionMutual Exclusion“Restriction whereby execution by a thread of its critical section precludes execution by other threads of their critical sections.” (Deitel)“Mutual exclusion is crucial to correct execution when multiple threads access shared writable data.” (Deitel)Implementing Mutual ExclusionA purely software solutionConstraint 1:A thread outside of its critical section can not block another thread from entering the critical sectionConstraint 2:A thread must not be indefinitely postponed from entering its critical sectionMutual Exclusion – Version 1// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...// Thread2...while (!done) { // Enter mutual exclusion while ( threadNumber == 1 ); // Critical section threadNumber = 1; // Outside critical section}...int threadNumber = 1; // globally accessible to Thread1 and Thread2Version 1 –Is Mutual Exclusion Guaranteed?// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...// Thread2...while (!done) { // Enter mutual exclusion while ( threadNumber == 1 ); // Critical section threadNumber = 1; // Outside critical section}...int threadNumber = 1; // globally accessible to Thread1 and Thread2Version 1 –Guarantees mutual exclusion// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...// Thread2...while (!done) { // Enter mutual exclusion while ( threadNumber == 1 ); // Critical section threadNumber = 1; // Outside critical section}...int threadNumber = 1; // globally accessible to Thread1 and Thread2Version 1 –Guarantees mutual exclusion// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...// Thread2...while (!done) { // Enter mutual exclusion while ( threadNumber == 1 ); // Critical section threadNumber = 1; // Outside critical section}...int threadNumber = 1; // globally accessible to Thread1 and Thread2Version 1 –Guarantees mutual exclusion// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...// Thread2...while (!done) { // Enter mutual exclusion while ( threadNumber == 1 ); // Critical section threadNumber = 1; // Outside critical section}...int threadNumber = 1; // globally accessible to Thread1 and Thread2Version 1 –Guarantees mutual exclusion// Thread1...while (!done) { // Enter mutual exclusion while ( threadNumber == 2 ); // Critical section threadNumber = 2; // Outside critical section}...//
View Full Document
Unlocking...