DOC PREVIEW
CU-Boulder CSCI 5828 - Shared Objects

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1©Magee/Kramer 2nd EditionCSCI 5828: Foundations ofSoftware EngineeringLecture 8: Shared ObjectsSlides created by Magee and Kramer for the Concurrencytextbook02/07/2008Concurrency: shared objects & mutual exclusion 2©Magee/Kramer 2nd EditionChapter 4Shared Objects &Mutual ExclusionConcurrency: shared objects & mutual exclusion 3©Magee/Kramer 2nd EditionShared Objects & Mutual ExclusionConcepts: process interference. mutual exclusion.Models: model checking for interferencemodeling mutual exclusionPractice: thread interference in shared Java objectsmutual exclusion in Java(synchronized objects/methods).Concurrency: shared objects & mutual exclusion 4©Magee/Kramer 2nd Edition4.1 InterferenceGardenWestTurns tileEastTurns tilepeo plePeople enter an ornamental garden through either of twoturnstiles. Management wants to know how many peopleare in the garden at any time.The concurrent program consists of two concurrentthreads and a shared counter object.Ornamental garden problem:Concurrency: shared objects & mutual exclusion 5©Magee/Kramer 2nd Editionornamental garden Program - class diagramThe Turnstile thread simulates the periodic arrival of a visitor tothe garden every second by sleeping for a second and then invokingthe increment() method of the counter object.se tvalue()NumberCanvasAppletinit()g o()GardenThreadTurnstilerun()Counterincrement ()displaydisplayeast,west peopleeastD,westD,counterDConcurrency: shared objects & mutual exclusion 6©Magee/Kramer 2nd Editionornamental garden programprivate void go() { counter = new Counter(counterD); west = new Turnstile(westD,counter); east = new Turnstile(eastD,counter); west.start(); east.start();}The Counter object and Turnstile threads are created by thego() method of the Garden applet:Note that counterD, westD and eastD are objects ofNumberCanvas used in chapter 2.Concurrency: shared objects & mutual exclusion 7©Magee/Kramer 2nd EditionTurnstile classclass Turnstile extends Thread { NumberCanvas display; Counter people; Turnstile(NumberCanvas n,Counter c) { display = n; people = c; } public void run() { try{ display.setvalue(0); for (int i=1;i<=Garden.MAX;i++){ Thread.sleep(500); //0.5 second between arrivals display.setvalue(i); people.increment(); } } catch (InterruptedException e) {} }}The run()method exitsand the threadterminates afterGarden.MAXvisitors haveentered.Concurrency: shared objects & mutual exclusion 8©Magee/Kramer 2nd EditionCounter classclass Counter { int value=0; NumberCanvas display; Counter(NumberCanvas n) { display=n; display.setvalue(value); } void increment() { int temp = value; //read value Simulate.HWinterrupt(); value=temp+1; //write value display.setvalue(value); }}Hardware interrupts canoccur at arbitrary times.The counter simulates ahardware interrupt during anincrement(), betweenreading and writing to theshared counter value.Interrupt randomly callsThread.sleep() to forcea thread switch.Concurrency: shared objects & mutual exclusion 9©Magee/Kramer 2nd Editionornamental garden program - displayAfter the East and West turnstile threads have eachincremented its counter 20 times, the garden peoplecounter is not the sum of the counts displayed. Counterincrements have been lost. Why?Concurrency: shared objects & mutual exclusion 10©Magee/Kramer 2nd Editionconcurrent method activationJava method activations are not atomic - threadobjects east and west may be executing the code forthe increment method at the same time.eastwestincrement: read value write value + 1programcounter programcounterPCPCshared codeConcurrency: shared objects & mutual exclusion 11©Magee/Kramer 2nd Editionornamental garden ModelProcess VAR models read and write access to the sharedcounter value.Increment is modeled inside TURNSTILE since Java methodactivations are not atomic i.e. thread objects east and westmay interleave their read and write actions.value:VARdisplaywriteGARDENwe st:TURNSTILEvalueendgoarriveeast:TURNSTILEvalueendgoarrivegoendreadConcurrency: shared objects & mutual exclusion 12©Magee/Kramer 2nd Editionornamental garden modelconst N = 4range T = 0..Nset VarAlpha = { value.{read[T],write[T]} }VAR = VAR[0],VAR[u:T] = (read[u] ->VAR[u] |write[v:T]->VAR[v]).TURNSTILE = (go -> RUN),RUN = (arrive-> INCREMENT |end -> TURNSTILE),INCREMENT = (value.read[x:T] -> value.write[x+1]->RUN )+VarAlpha.||GARDEN = (east:TURNSTILE || west:TURNSTILE || { east,west,display}::value:VAR) /{ go /{ east,west} .go, end/{ east,west} .end} .The alphabet of sharedprocess VAR is declaredexplicitly as a setconstant, VarAlpha.The TURNSTILEalphabet is extendedwith VarAlpha toensure no unintendedfree (autonomous)actions in VAR eg.value.write[0].All actions in theshared VAR must becontrolled (shared)by a TURNSTILE.Concurrency: shared objects & mutual exclusion 13©Magee/Kramer 2nd Editionchecking for errors - animationScenario checking- use animation toproduce a trace.Is this tracecorrect?Concurrency: shared objects & mutual exclusion 14©Magee/Kramer 2nd Editionchecking for errors - exhaustive analysisTEST = TEST[0],TEST[v:T] = (when (v<N){east.arrive,west.arrive}->TEST[v+1] |end->CHECK[v] ),CHECK[v:T] = (display.value.read[u:T] -> (when (u==v) right -> TEST[v] |when (u!=v) wrong -> ERROR ) )+{display.VarAlpha}.Exhaustive checking - compose the model with a TESTprocess which sums the arrivals and checks against thedisplay value:Like STOP, ERROR isa predefined FSPlocal process (state),numbered -1 in theequivalent LTS.Concurrency: shared objects & mutual exclusion 15©Magee/Kramer 2nd Editionornamental garden model - checking for errors||TESTGARDEN = (GARDEN || TEST).Use LTSA to perform an exhaustive search for ERROR.Trace to property violation in TEST:goeast.arriveeast.value.read.0west.arrivewest.value.read.0east.value.write.1west.value.write.1enddisplay.value.read.1wrongLTSA producesthe shortestpath to reachERROR.Concurrency: shared objects & mutual exclusion 16©Magee/Kramer 2nd EditionInterference and Mutual ExclusionDestructive update, caused by the arbitraryinterleaving of read and write actions, is termedinterference.Interference bugs are extremely difficult tolocate. The general solution is to give methodsmutually exclusive access to shared objects.Mutual exclusion can be modeled as atomicactions.Concurrency:


View Full Document

CU-Boulder CSCI 5828 - Shared Objects

Documents in this Course
Drupal

Drupal

31 pages

Deadlock

Deadlock

23 pages

Deadlock

Deadlock

23 pages

Deadlock

Deadlock

22 pages

Load more
Download Shared Objects
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Shared Objects and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Shared Objects 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?