Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 37 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 332 at George Mason University taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/215133/cs-332-george-mason-university in ComputerScienence at George Mason University.
Reviews for Obj
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
The Java 2 Collections Finally Some News You Can Use by Chuck Allison Arrays Algorithms for processing Arrays binarySearch returns the zero based index of the element you39re after if it39s in the array otherwise it returns pos 7 1 where pos is the index of the position it should occupy equals fill sort ascending order only class ArraysTest static void searchint a int n int where ArraysbinarySearcha n if where lt 0 where where 1 if where 2 alength SystemoutprintlnquotAppend quot n quot to end of listquot else Systemoutprintlnquotlnsert quot n quot before quot awhere else SystemoutprintlnquotFound quot n quot in position quot where public static void mainString args Build Array int array 88 17 10 34 27 0 2 Arrayssortarray searcharray 10 Systemoutprintlnquotarray 2 array quot Arraysequalsarrayarray int ones 2 new intarraylength Arraysfillones 1 For descending order use a Comparator an object that implements the following interface public interface Comparator int compare0bject ol Object 02 The compare method must behave like C39s strcmp function by returning a negative number if 01 precedes 02 zero if they are equal or a positive number otherwise class Descending implements Comparator public int compare0bject ol Object 02 Comparable cl Comparable ol Comparable 02 Comparable 02 return clcompareTocZ Integers provide compareToO or simply static Comparator desc Collectionsreverse0rder class ArraysTest2 static Descending desc new Descending static void searchObject a Object n int where ArraysbinarySearcha n desc if where lt 0 where where 1 if where 2 alength SystemoutprintlnquotAppend n to end of list else Systemoutprintln lnsert n before awhere else SystemoutprintlnquotFound n in position where public static void mainString args Build Array lnteger array 2 new lnteger88 new lnteger17 new lnteger 10 new lnteger34 new lnteger27 new lnteger0 new lnteger 2 Arrayssorta1ray desc searcharray new lnteger 10 A Comparable object implements the method int c0mpareT0Object 0 which also behaves like C39s strcmp public class Person implements Comparable Cloneable private String name private int year private int month private int day public PersonString name int year int month int day thisname new Stringname thisyear 2 year thismonth 2 month thisday 2 day public String getName return name public Object clone try Person p 2 Person superclone pname new Stringname return p catch CloneNotSupportedEXception X throw new lnternalErrorXtoString public boolean equals0bject o if 0 instanceof Person Person p 2 Person 0 return nameequalspnameampamp year 2 pyearampampmonthpmonthampampday 2 pday else return false public int hashCode ensure different persons get different results int hval namehashCodeyear hval hval ltlt 4 month hval hval ltlt 4 day return hval public String toString return 3939 name 3939 month 3939 day 3939 year 3939 public int compareToObject o Implement Comparable Person p Persono int result namecompareTopname if result 2 0 result year pyear result result16 month pmonth result result16 day pday return result class ArraysTest3 static void searchObject a Object n same as in Figure 2 public static void mainString args Build Array Person array 2 new Person3 array0 new Person Horatio 1835126 array1 new Person Charles 1897311 array2 new Person Albert 1901120 Arrayssorta1ray searcharray array1clone searcharray new Person Gregory 1582 10 15 Or search on part of name class ByName implements Comparator public int compareObject ol Object 02 Person p1 2 Person 01 Person p2 2 Person 02 return p1getNamecompareT0p2getName class ArraysTest4 static ByName comp new ByName static void searchObject a Object n as before I public static void mainString args Build Array Person array 2 new Person3 array0 new Person Horatio 1835126 array1 new Person Charles 189731 1 array2 new Person Albert 1901120 Arrayssorta1ray comp searcharray array1 Collections Collections are containers that implement the Collection interface Interface Collection boolean addObject o boolean addAllCollection c void clear boolean containsObject o boolean containsAllCollection c boolean equalsObject 0 int hashCodeO boolean isEmptyO Iterator iterator boolean removeObject o boolean removeAllCollection c boolean retainAllCollection 0 int size Object toArray Object toArrayObject a The Collection interface is further refined into List and Set Interface List extends Collection void addint index Object element Object getint index int indexOfObject 0 int lastIndexOfObject o ListIterator listIteratorO ListIterator listIteratorint index Object removeint index Object setint index Object element int size List subListint fromIndex int toIndex Set is identical to Collection but no duplicates are allowed Lists are ordered sequences that support direct indexing and bidirectional traversal Java 2 comes with LinkedList and ArrayList as implementations for List Vector is also there for historical reasons but ArrayList is preferred over Vector in new code LinkedList implements a doubly linked list and is optimized for inserting and removing elements anywhere in a list ArrayList is simply an expandable array and is preferred when you need to use random access to list elements class ListTest public static void testList x Object p xget2 if xcontainsp SystemoutprintlnquotFound p int index xindex0fp Do another if index 1 1 SystemoutprintlnquotFound p in position index Collectionssortx index CollectionsbinarySearchx p if index gt2 0 SystemoutprintlnquotFound p in position index Do a search Systemoutprintln max 2 Collectionsmaxx Systemoutprintln mi 2 Collectionsminx Comparator desc CollectionsreverseOrder Systemoutprintln max desc 2 Collectionsmaxx desc Systemoutprintln min desc 2 Collectionsminx desc Collectionsshuf ex iteratex public static void iterateCollection c lterator i citerator while ihasNext Systemoutprintlninext public static void mainString args ArrayList array 2 new ArrayList Build ArrayList arrayaddnew Person Horatio 1835126 array addnew Person Charles 189731 1 array addnew Person Albert 1901120 testarray arrayaddnew Person ames 1976 8 13 Build LinkedList LinkedList list new LinkedLista1ray List View listsubList13 Viewaddnew Person Gregory 1582 10 15 CollectionsreverseView testlist View is defined as containing the second and third elements of list ie indexes 1 and 2 where list is itself a copy of array Since View is just a wrapper for a subset of list any operations on View affect list Appending Gregory39s instance to View therefore inserts it after James not Charles the latter being outside of View There are more algorithms in Collections Some of the algorithms contain the prefixes unmodifiable and synchronized These methods act as wrappers for existing collections and restrict their use If you call unmodifiableCollection on an existing collection for example the object returned Will throw an UnsupportedOperationEXception if you try to call any of the Collection methods that modify a collection LinkedList includes the following methods among others void addFirstObject o pushifrontO void addLastObject o pushibackO Object getFirstO front Object getLast back Object removeFirst popfront Object removeLast popibackO These methods can be used to simulate Stacks and Queues Iterators lterators like Enumerations facilitate traversing through an ordered sequence Unlike Enumerations you can remove elements via an iterator The order of the traversal depends on the collection itself Interface lterator boolean hasNeXtO Object next void remove The ListIterator interface lets you update an object through an iterator Interface Listlterator void addObject o boolean hasNeXtO boolean hasPrevious Object next int nextlndexO Object previous int previouslndex void remove void setObject o class Modify public static void mainString args ArrayList a new ArrayList aaddneW lnteger1 aaddneW lnteger2 a addneW lnteger3 Systemoutprintlna Modify via iterator Listlterator p Listlterator alistlterator While phasNeXt Integer i Integer pnext psetneW lntegeriintValue 1 Systemoutprintlna Output 1 2 3 2 3 4 Sets The Set interface conforms to the usual notion of a mathematical set Which basically is just an unordered receptacle for elements and provides operations for insertion removal and testing of membership Since these are already part of the Collections interface the Set interface is identical to Collection with the added specification that duplicates are not allowed The SortedSet interface adds methods useful for processing a set ordered by comparator lnterface SortedSet extends Set Comparator comparator Object first SortedS et headSetObj ect toElement Object last SortedS et subS etObject fromElement Object toElement SortedS et tailSetObject fromElement The HashSet class implements Set and TreeSet implements SortedSet HashSets are more efficient since they use hashing algorithms but if order is important TreeSets at least provide logarithmic time algorithms since they store objects in balanced tree structures Ay attempts to insert duplicates into a set are ignored class SetTest public static void testSet X Do a search Person p new Person Albert 1901120 if Xcontainsp SystemoutprintlnquotFound p Systemoutprintln niax 2 Collectionsniaxx Systemoutprintln niin 2 Collectionsniinx iteratex public static void iterateCollection c Systemoutprintlnquotlterating lterator i citerator while ihasNeXt Systenioutprintlninext public static void mainString args Build HashSet HashSet h new HashSet haddnew Person Horatio 1835126 haddnew Person Charles 189731 1 h addnew Person Albert 1901120 The following is ignored h addnew Person Albert 1901120 Systemoutprintlnh testh Systemoutprintln Build TreeSet TreeSet t new TreeSetCollectionsreverseOrder taddAllh Systemoutprintlnt testt Extra TreeSet stuff boolean ctest tcon1paratorequalsCollectionsreverseOrder SystemoutprintlnquotComparator test ctest Systemoutprintlnquotfirst tfirst Systemoutprintlnquotlast tlast Person p new Person Charles 1897311 SystemoutprintlnquotheadSet theadSetpSystemoutprintlnquottailSet ttailSetp For TreeSets headSet returns a View from the beginning up to but not including the specified element and tailSet comprises the rest of the sequence Maps A map is a dictionary or associative array A map stores pairs treating the first element of the pair as a key and the second as its associated value Maps provide fast search times for keys and duplicate keys are not allowed Like Sets there are HashMaps and TreeMaps the former being faster and unordered While instances of the latter are ordered Maps have their own interface and implementation hierarchies lnterface Map void clear boolean containsKeyObject key boolean containsValueObject value Set entrySet boolean equalsObject 0 Object getObj ect key int hashCode boolean isEmpty Set keySet Object putObject key Object value void putAllM ap t Object removeObject key int size Collection values static lnterface MapEntry boolean equalsObject 0 Object getKeyO Object getValue int hashCode Object setValueObject value lnterface SortedMap extends Map Comparator comparator Object firstKey SortedMap headMapObject toKey Object lastKey SortedMap subMapObject fromKey Object toKey SortedMap tailMapObject fromKey A WeakHashMap stores keys as weak references which means that if the only reference to the key object is the key in the map then that object can be garbage collected whereupon the entry is removed from the map The key methods of the Map interface are put and get The put method stores a pair of objects in the map and get retrieves the value for the given key If you want to just see the keys keySet returns them as a Set view and the values method returns the values as a Collection If you want to iterate through the pairs you can call entrySet which returns the pairs as a Set of instances of MapEntrySet class MapTest public static void mainString args HashMap h new HashMap hput Alabama quotMontgomeryquot hput Tennesee quotNashvillequot hput Georgia quotAtlantaquot Alabama is a key Montgomery is a value The following is ignored hput Georgia quotAtlantaquot testh TreeMap t new TreeMapCollectionsreverseOrder tputAllh testt Extra TreeMap Stuff boolean ctest tcomparatorequalsCollectionsreverseOrder SystemoutprintlnquotComparator test ctest SystemoutprintlnquotfirstKey tfirstKey SystemoutprintlnquotlastKey tlastKey SystemoutprintlnquotheadMap theadMap Georgia SystemoutprintlnquottailMap ttaillVIap Georgia public static void testMap m if mcontainsKey Alabama Systemoutprintln Alabama is a key if mcontainsValuequotMontgomeryquot Systemoutprintln Montgomery is a value SystemoutprintlnquotmGeorgia mget Georgia SystemoutprintlnquotmMichigan mget Michigan SystemoutprintlnquotKeys mkeySet SystemoutprintlnquotValues mvalues iteratem public static void iterateMap m Set s mentrySet Iterator i siterator while ihasNeXt MapEntry e MapEntryineXt Systemoutprintlne Note that calling put a second time with the same key replaces its associated value Application a typical cross reference lister which prints each word from a text file with the line numbers where it appears Applying this program to itself yields a 2 28 Add 45 68 addLast 69 already 49 and 45 args 95 98 107 114 115 at 28 boolean 51 BufferedReader 21 102 116 etc This program uses a Map that associates a token with a list of line numbers To make tokens appear in alphabetical order it uses a TreeMap with the default comparator To ignore case in comparisons define a comparator called NOCase that calls Stringc0mpareToIgnoreCase Before inserting a new pair check to see if it is already in the map If not insert it with the statement mapputtoken new LinkedListO Retrieve the list of lines with LinkedList lines LinkedList mapgettoken Then check to see if the current line number has already been added to the list if not append it It would have been simpler to just use a TreeSet but the constant re balancing of the tree would degrade performance and since the lines are entered in the correct order a list suffices A call to entrySet returns the pairs as a Set of instances of MapEntrySet class Xref static class NoCase implements Comparator Comparator to ignore case public int compareObject ol Object 02 String s1 String 01 String s2 String 02 return s1compareToIgnoreCases2 static void processBufferedReader r throws IOException This method does the work TreeMap map new TreeMapnew NoCase String line int lineno 0 while line rreadLine I null Build map reading a line at a time lineno String delim quotamp 739 ltgt quot0123456789quot StringTokenizer tokens new StringTokenizerline delim Read each token while tokenshasMoreTokens String token tokensneXtToken if mapcontainsKeytoken mapputtoken new LinkedList Add to map LinkedList lines LinkedList mapgettoken See if this line is in there already if linesisEmpty IntegerlinesgetLastintValue I lineno linesaddLastnew Integerlinen0 Add line number to list Iterator p mapentrySetiterator Output while phasNeXt MapEntry e MapEntry pnext SystemoutprintegetKey LinkedList lines LinkedList egetValue Iterator lineIter linesiterator while lineIterhasNeXt Integer i Integer lineIterneXt if i I Integer linesgetFirst Systemoutprint Systemoutprinti Systemoutprintln public static void mainString args throws IOException if argslength 2 0 Reader r new InputStreamReaderSystemin Process standard input processnew BufferedReaderr else Process each specified file for int i 0 ilt argslength i if i gt 0 Systemoutprintln Systemoutprintln File argsi FileReader f new FileReaderargsi processnew BufferedReaderf 410 Tracing and Replay for Monitors Outline I simple M sequences of monitor based programs I tracing and replaying simple M sequences during debugging I modifying the SC and SU monitor toolboxes to support tracing and replay I complete M sequences and a technique for using complete M sequences to test monitor based programs I applying reachability testing to monitor based programs 4101 Simple Msequences Let M be a monitor that is implemented using one of the monitor toolboxes An execution of a program that uses M can be Viewed as a sequence of P and V operations on the semaphores in the implementation of M I a simple SYN sequence for M is the collection of simple PV sequences for the semaphores in the implementation of M I we can replay an execution of a program that uses M by applying the replay method that was presented in Chapter 3 for replaying PV sequences of semaphore based programs A simpler method is based on the property of entry based execution I The execution of threads inside an SU monitor is completely determined by the order in Which the threads enter the monitor Via monitor calls and the values of the parameters on these calls I The execution of threads inside an SC monitor is completely determined by the order in Which the threads enter the monitor Via monitor calls the values of the parameters on these calls and the order in Which signaled threads reenter the monitor The execution of threads in a monitor having entry based execution is completely determined by the order in Which the threads reenter the monitor and the values of the parameters on the calls to the monitor Let CP be a concurrent program that uses monitors The synchronization objects in CF are its monitors The synchronization events in a simple SYN sequence of CP depend on the type of monitors being used SC monitors A simple SYN sequence for an SC monitor is a sequence of events of the following types I entry into the monitor by a calling thread I reentry into the monitor by a signaled thread SU monitors A simple SYN sequence for an SU monitor is a sequence of events of the following type I entry into the monitor by a calling thread Simple SYN sequences of monitors are called simple M sequences I An event in a simple M sequence is denoted by the identifier ID of the thread that executed the event I The simple M sequence of a program CP is a collection of simple M sequences for the monitors in CF We can replay an execution of CP by replaying the simple M sequence for each monitor Consider the SC bounded buffer monitor in Listing 43 A possible simple M sequence of boundedBu 39er for a single Producer thread With ID 1 and a single Consumer thread with ID 2 is 21 211 2 2 This sequence is generated when I The Consumer enters the monitor first and executes notEmptywait I The Producer then enters the monitor deposits an item and signals the Consumer I The Consumer then reenters the monitor and consumes an item Note This sequence begins with 2 l 2 since the Consumer generates one event when it enters the monitor the first 2 and one event when it reenters the monitor the second 2 If the same scenario were to occur when boundedBu 39er was an SU monitor then the simple M sequence of boundedBu 39er would be 2 l l l 2 2 In this sequence the Consumer does not generate an event when it reenters the monitor since boundedBu 39er is an SU monitor Thus the sequence begins with 2 l and is followed by a second entry event for the Producer the second 1 and not a reentry event for the Consumer We are making several important assumptions in our definition of simple M sequences 1 All shared variables are accessed inside a monitor and monitor reentry is the only source of non determinism in the program 2 Semaphores with FCFS notifications are used in the implementation of condition variables If notifications wake up waiting threads in an unpredictable order then non determinism is introduced in the implementation of the monitor 3 VP operations are used in the semaphore implementation of a monitor Without VP or some other mechanism context switches can occur between V and P operations which introduces non determinism in the implementation of the monitor Assumptions 2 and 3 are necessary for entry based execution If assumption 1 does not hold then replaying the simple M sequences of an execution may not replay the execution class boundedBuffer extends monitor private int fullSlots 0 number of full slots in the buffer private int capacity 0 capacity of the buffer private int buffer null circular buffer of ints private int in 0 out 0 private conditionVariable notFull new conditionVariableO private conditionVariable notErnpty new conditionVariableO public boundedBufferint bufferCapacity capacity bufferCapacitybuffer new intbufferCapacity public void depositint value while fullSlots capacity notFullwait bufferin value in in l capacity fullSlots notErnptysignal alternativelyif fullSlots 1 notErnptysignal public int withdraw int value while fullSlots 0 notEmptywait value bufferout out out l capacity fullSlots notFullsignal alternativelyif fullSlots capacity l notFullsignal return value Listing 43 Monitor class boundedBu 39er 4102 Tracing and Replaying Simple Msequences SU toolbox semaphore mutex controls entry into the monitor During execution the identifier of a thread that completes a mutexP operation is saved to a trace file SC toolbox semaphore mutex controls entry into the monitor for threads calling the monitor and reentry into the monitor for signaled threads The identifier of the thread that completes a mutexP operation is recorded and saved to a trace file To replay a simple M sequence I Before each mutexP operation a thread calls control requestEntryPermitUD to request permission to enter the monitor I After completing mutexP the thread calls control releaseEntryPermitO to allow the next thread in the simple M sequence to enter the monitor Java monitor class monitorTrdcingAndRepldy in Listing 428 is very similar to the control object in Listing 332 that was used for replaying simple PV sequences Method requestEntryPermitO Threads that try to enter the monitor out of turn are delayed in method requestEntryPermitO on a separate conditionVaridble in the threads array A thread uses its ID to determine which conditioanridble in the threads array to wait on Method releaseEntryPermit increments index to allow the next reentry operation in the simpleMSequence to occur If the thread that is to perform the next entry is blocked in requestEntryPermitO it is awakened class monitorTracingAndReplay extends monitorSU monitorTracingAndReplay input sequence of Integer IDs into vector simpleMSequence and initialize the threads array public requestEntryPerrnitint ID enterMonitor if ID I IntegersimpleMSequenceelernentAtindexintValue threads IDWaitC thread With identifier ID is delayed on exitMonitorO condition variable threadsID public releaseEntryPerrnitO enterMonitor if index lt sirnpleMSequencesize l index if the next thread in the simpleMSequence was delayed in requestEntryPermitO wake it up threads IntegersimpleMSequenceelernentAtindex intValue signalCandexitMonitor return exitMonitor record integer ID of entering thread in trace file public void traceMonitorEntryint ID record integer ID of reentering thread in trace file public void traceMonitorReEntryint ID sirnple M sequence traced during a previous execution private vector simpleMSequence out of order threads are delayed on condition variables private conditionVariable threads index of the next event in simpleMSequence to be replayed private int index 1 Listing 428 Java rnonitor monitorTracingAndReplay for tracing and replaying sirnple M sequences 4103 Other Approaches to Program Replay Another approach to replaying an execution of a multithreaded Java program is to trace and replay the scheduling events of the operating system A thread schedule is a sequence of time slices where a time slice is the interval of time between two context switches A thread schedule of an execution can be replayed by forcing context switches to occur at the exact same points during the execution Since detailed scheduling information is not always available from the operating system a logical thread schedule can be used instead A logical thread schedule of an execution is a record of the number of critical operations that the threads executed during their time slices Critical operations are I read and write operations on shared variables I entering and exiting synchronized methods and blocks I wait and notify operations A logical thread schedule can be replayed my modifying the Java Virtual Machine J VM to count critical operations For example assume Thread 1 executes fifty critical operations during its time quantum This can be represented by l 20 69 Thread 1 executed the fifty operations numbered 20 through 69 The DejaVu system uses logical thread schedules to replay multithreaded Java programs Java applications can be traced and replayed in DejaVu without any modifications to the source code 411 Testing MonitorBased Programs Outline I complete M sequences I determining whether a particular complete M sequence is allowed by a program 4111 Msequences Debugging process I Observe a failure I Replay the simple M sequence of the execution perhaps several times to locate the fault that caused the failure I Modify the program to fix the bug I Test the modification to make sure that the fault has been corrected and that no new faults were introduced by the modification The last step is commonly known as regression testing Regression testing requires that we determine whether or not a particular SYN sequence is feasible I A feasible SYN sequence is a sequence that can be exercised by the program I The SYN sequence may represent an illegal or invalid behavior that was observed when the program failed I A SYN sequence may represent a legal or valid behavior that was exhibited previously then this valid sequence should remain feasible after the modifications We may also want to use test sequences to detect failures I If a test sequence is expected to be feasible but is not feasible or is expected to be infeasible but is not infeasible then we can start the debugging process Selecting sequences and checking their feasibility is part of a general testing technique called deterministic testing Determining the feasibility of a SYN sequence is a problem that is subtly different from the replay problem I Replaying a SYN sequence involves repeating a sequence that is known to be feasible Assuming the sequence was just exercised and the program has not been modified I During regression testing we want to know whether or not a program that is executed with a given input can exercise a particular sequence and produce a particular output For regression testing we need more information than is contained in a simple M sequence Consider the following simple M sequence for a 2 slot bounded buffer with a single Producer with ID 1 and a single Consumer with ID 2 l l l 2 2 This gives the order in which threads entered the monitor but which methods did they call During testing we must check that threads call the expected monitor methods Suppose now that we also specify the name of the method ldepositldeposit l deposit 2withdraw2withdraw I If the third item was deposited into a full buffer then the first item was lost I If the Producer executed notFullwait then a third deposit was not made until after a withdrawl and a failure was avoided We cannot determine from the information in this sequence what happened Even after checking the output we may still be unsure about what happened If the items deposited were C A and C then the items withdrawn are also C A and C even if the first item is overwritten by the third item To more completely characterize the execution of a monitor based program we will consider the following types of monitor events a b the exit of a monitor method V the entry of a monitor method and for SC monitors the reentry of a monitor method c the start of execution of a wait operation d the start of execution of a signal or signalAndExit or signalAll operation What about other events such as the end of execution of a wait or signal operation or the resumption of a monitor method after a wait or an SU signal operation I Their occurrence can be inferred by the occurrence of events of types a through d I It may still be desirable to trace these events to aid in understanding executions A sequence of events of types a through d is called a complete M sequence as opposed to simple M sequences which are used for replay The events of an M sequence have the formatTypeThreadMethodConditionVariable Type the type of this event Thread the ID of the thread executing this event Method the monitor method of this event qualified with the monitor name if there are multiple monitors ConditionVariable the name of the condition variable if this event is a wait signal signalAndExit or signalAll event and NA otherwise Example a possible M sequence of the SC bounded buffer monitor in Listing 43 is enter consumer withdraw NA wait consumer withdraw notEmpty enter producer deposit NA signal producer deposit notEmpty exit producer deposit NA reenter consumer withdraw NA signal consumer withdraw notFull exit consumer withdraw NA Another way to make an M sequence clearer is to allow user level events to appear in the sequence These events label the atomic communication actions that occur inside the monitor A call to method exerciseEvent event generates a communication event labeled event and records it in the M sequence For example the following SC bounded buffer monitor has calls to exerciseEvent to generate communication events labeled deposit and withdraw public void depositint value enterMonitor while fullSlots capacity notFullwaitC bufferin value exerciseEventquotdeposit generate a deposit event in in l capacity fullSlots notEmptysignalC exitMonitor public int withdraw enterMonitor int value while fullSlots 0 notEmptywaitC value bufferout exerciseEvent withdraw generate a withdraw event out out l capacity fullSlots notFullsignalC exitMonitor return value The M sequence shown above with communication events deposit and withdraw added is enter wait enter comm signal exit reenter comm signal exit consumer consumer producer producer producer producer consumer consumer consumer consumer withdraw withdraw deposit deposit deposit deposit withdraw Withdraw withdraw withdraw NA notEmpty NA NA communication event notEmpty NA NA NA notFull NA communication event 3 For each communication event we record its label and the ID of the thread that executed the event A sequence of communication events is useful for understanding what happened ie the communication that occurred among the threads without any details about how the threads were synchronized to achieve that communication comm comm producer consumer deposit NA Withdraw NA When we modify a program to correct a fault we want an answer to the following question If we execute the program with the same the input that detected the fault can the same path be exercised and the same output be produced An M sequence partially identifies the path exercised by a program and helps us answer this question Consider the following monitor method public void FO enterMonitorO39 if conditionwaitC if true part else false part conditionsignalC39 exitMonitorO39 An M sequence for an execution of a program containing method F indicates the order in which threads entered F and whether or not the wait operation in F was executed I This tells us a lot about the path through F that each thread executed I But an M sequence by itself does not indicate whether the threads executed the true part or the false part of the second if statement in F I So a path consists of more than just an M sequence and more than just a sequence of statements executed by the threads Note The output is likely to indicate whether the true part or the false part was executed Thus the M sequence and the output of an execution together describe the execution very well and together are often are enough to determine if a failure has occurred A formal definition of a path for a concurrent program is given in Chapter 7 4112 Determining the Feasibility of an Msequence The feasibility of an M sequence is determined using the same technique that was used for replay I Before a thread can perform a monitor operation it requests permission from a control module I The control module is responsible for reading an M sequence and forcing the execution to proceed according to this sequence I If the M sequence is determined to be infeasible the control module displays a message and terminates the program 41121 Modifying the monitor operations Each monitor operation is modified by adding one or more calls to the controller Below we describe the modifications made to the SC monitor operations Method enterMonitorO public final void enterMonitorString methodName controlrequestMPermitENTRYthreadIDmethodNamequotNA mutexP controlreleaseMPermit For the method name to be available inside the toolbox it must be passed by the user as an argument to enterMonit0r public void depositchar value enterMonitorquotdeposit Method waitCO public void waitCO wait your turn to enter controlrequestMPermitWAITthreadIDmethodNameconditionName numWaitingThreads threadQueueVPmutex wait your turn to reenter controlrequestMPermitREENTRYthreadIDmethodNamequotNA mutexP controlreleaseMPermit allows next event in the M sequence to occur A conditionVariable s name is automatically generated When the conditionVariable is constructed Alternately a more descriptive name can be specified When the conditionVariable is constructed but each name must be unique notFull new conditionVariablequotnotFull signalC public void signalC controlrequestMPermitSIGNALthreadIDmethodNameconditionName if numWaitingThreads gt 0 numWaitingThreads threadQueueV exitMonit0r public void exitMonitor controlrequestMPermitEXITthreadIDmethodNamequotNA mutexV If a monitor contains calls to exerciseEvent then Threads executing exerciseEvent must request permission before executing a communication COMM event public void exerciseEventString eventLabel controlrequestMPermitCOMMthreadIDeventlabelquotNA 41122 The Controller The controller attempts to force a deterministic execution of the program according to the M sequence that it inputs The M sequence is feasible if and only if the M sequence is completely exercised Ideal the controller would display a message if it finds that an M sequence definitely cannot be exercised However the problem of determining whether a concurrent program terminates for a given input and SYN sequence is in general undecidable Practical the controller specifies a maximum time interval that is allowed between two consecutive events I If a timeout occurs then the sequence is assumed to be infeasible I It is always possible that some larger timeout value would give the next event enough time to occur and allow the sequence to complete The controller is implemented in two parts The first part inputs an M sequence and then forces the execution to proceed according to the order of events in the M sequence I This is implemented just like the replay controller I The controller also checks that the attributes of each event match the attributes in the M sequence eg the method names match the condition variable names match I If a mismatch is detected then a diagnostic is issued and the program is terminated At any point in the sequence if an expected request does not arrive within the timeout interval a diagnostic is issued and the program is terminated This timeout function of the controller is handled by a watch dog thread I Monitors the value of the variable index which indicates which event is being exercised I If the value of index does not change within the timeout interval then the M sequence is assumed to be infeasible final class watchDog extends Thread public void run index 139 indicates that execution has proceeded to the ith event While index lt MSequencesize int saveIndex index try Threadsleep2000 two second timeout interval catch InterruptedException e if saveIndex index issue diagnostic and exit program 4113 Determining the Feasibility of a Communicationsequence A Communication sequence is a sequence of communication events A set of Communication sequences can be generated to test a monitor Without knowing the details about the synchronization events in the monitor eg the names of the condition variables and monitor methods comm producer deposit NA comm consumer Withdraw NA comm producer deposit NA comm consumer Withdraw NA The feasibility of a Communication sequence is determined just like an M sequence except that only the thread IDs and event labels of communication events are checked Threads that Wish to reenter a monitor must request permission from the controller first I The controller grants permission for Threadi to enter the monitor only if Thread is the thread expected to execute the next communication event in the sequence I In other words the order in Which threads execute communication events must match the order in Which they reenter the monitor I If this is not possible then the Communication sequence is not feasible Example Consider a boandedBaffer monitor with a capacity of three I Even if we never see a trace with four consecutive deposit operations during non deterministic testing it is possible that boandedBaffer contains a fault that allows a deposit into a full buffer I Likewise it is possible that a withdrawal is allowed from an empty buffer To test these cases we can specify two Communication sequences and check their feasibility A sequence that checks for an invalid withdrawal is comm consumerwithdraw NA withdraw from an empty buffer The following invalid sequence contains four consecutive deposits comm producerdep0sit NA comm producerdep0sit NA comm producerdep0sit NA comm producerdep0sit NA deposit into a full buffer If either of these Communication sequences is feasible then a fault is detected in boandedBa 39er Alternatively use reachability testing to indirectly check the feasibility of these sequences That is if neither of these sequences are exercised during reachability testing then they are infeasible 4114 Reachability Testing for Monitors Reachability testing can also be used to automatically derive and exercise every partially ordered M sequence of a monitor based program I Reachability testing identifies race conditions in an execution trace and uses the race conditions to generate race variants I Recall from Chapter 3 that a race variant represents an alternate execution behavior that de nitely could have happened but didn t due to the way race conditions were arbitrarily resolved during execution I Replaying a variant ensures that a different behavior occurs during the next execution Fig 430a shows an execution trace of a bounded buffer program with two producers P1 and P2 two consumers Cl and C2 and an SC monitor M I A solid arrow from a producer or consumer thread to monitor M indicates that the thread called and entered monitor M I In this execution the producer and consumer threads enter the monitor in the order C1 Pl Cl P2 C2 I The 2nd entry by C1 occurs when Cl reenters the monitor after being signaled by P1 HZ M Q2 2 call exit reenter call enter a Figure 430 Execution trace and a race variant quotwait 7 can enter exit si gnal reenter enter a b Figure 430 Execution trace and a race variant Fig 430a identifies the racing threads called the race set for each entry event I The race set for Cl s reentry event is shown beside the reentry event as P2 C2 This indicates that P2 or C2 could have entered the monitor instead of Cl Note that the monitor calls made by P2 and C2 were concurrent with Cl s call to reenter the monitor This is how the racing monitor calls were identified A race variant is created by changing the calling thread for a monitor reentry event The new calling thread must be a member of the race set for the reentry event Fig 430b shows one of the eight race variants for the trace in Fig 430a In this variant P2 enters the monitor before Cl reenters the monitor When this race variant is replayed the two producers will both deposit their items before either consumer withdraws one The order in which the two consumers will reenter the monitor and withdraw their items after the variant is replayed is non deterministic The complete trace of whichever sequence occurs can be analyzed to derive more variants which can be replayed to generate more traces and so on so that all possible M sequences are exercised during reachability testing Table 42 shows the results of applying reachability testing to several monitor programs I BB is the bounded buffer program in Listing 43 I DPZ is the second solution to the dining philosophers program in Listing 48 I RW is the readers and writers program in Listing 49 For BB and RW we show results for SU and SC monitors programs These results help to quantify the difference between SU and SC monitors I SC monitors generate more M sequences than SU monitors since SC monitors have races between signaled threads that are trying to reenter the monitor and calling threads that are trying to enter the monitor for the first time I SU monitors avoid these races by giVing signaled threads priority over calling threads As we discussed in Chapter 3 the number of sequences exercised during reachability testing can be reduced by considering the symmetry of the threads in the programs I For the bounded buffer program reachability testing considers all the possible orders in which a group of producers can perform their deposit operations or a group of consumers can perform their withdraw operations Producer threads may enter the monitor in the order Producerl Producerz Producer3 or Prodocerz Producerl Producer3 or Producer3 Producerz Producerl etc I Using thread symmetry reduces the number of sequences exercised for the two bounded buffer programs from 720 and 12096 to 20 and 60 respectively 4115 Putting it All Together 41151 Using the Java Toolboxes Extend class TDThread instead of class Thread This ensures that each thread receives a unique ID To trace an execution of program Buffer use java Dmodetrace Buffer This creates three files I file monitor replaytxt contains the simple M sequence of the execution I file monitor testtxt contains the M sequence of the execution I file monitor commtxt contains the Communication sequence of the execution Random delays can be executed during trace mode by setting property randomDelay to the value on java Dmodetrace DrandomDelayon Buffer Deadlock detection is turned on by specifying DdeadlockDetectionon To turn deadlock detection off set deadlockDetection to o 39 this is also the default value If separate sequences are desired for each monitor in the program the controllers property can be used to create one controller per monitor Valid values for this property are single Which is the default value and multiple java Dmodetrace DrandomDelayon Dcontrollersmultiple Buffer The simple M sequence in file monitor replaytxt is replayed using java Dmodereplay Buffer Reachability testing is performed on Bu 39er by setting the mode property to rt and executing a driver process named RTDriver java Dmodert DdeadlockDetection0n RTDriver Buffer The feasibility of the M sequence in file monitor testtxt is determined using java Dmodetest Buffer The feasibility of the Communication sequence in file monitor commtxt is determined using java DmodecommTest Buffer The value used for property controllers during replay and testing must match the value that was used during tracing If the mode is not specified the default value for the mode property turns tracing replay and testing off Specifying Dmodenone has the same effect The M sequence recorded during a program s execution can be used to replay the execution If the program is not modified after the M sequence is recorded then the M sequence remains feasible and checking the feasibility of this feasible M sequence using Dmodetest amounts to replaying the execution 41152 Using the CWin32Pthreads Toolboxes The mode of execution is specified using the environment variable MODE The possible values for MODE are TRACE REPLAY TEST RT for Reachability Testing COMMTEST to determine the feasibility of a Communication sequence and NONE To trace an execution of program Buffer in WindowsDOS execute set MODETRACE Unix setenv MODE TRACE and then executing program Buffer Random delays are controlled by variable RANDOMDELAY set RANDOMDELAYON Unix setenv RANDOMDELAY ON Deadlock detection is controlled by variable DEADLOCKDETECTION set DEADLOCKDETECTIONON Unix setenv DEADLOCKDETECTION ON An execution in TRACE mode creates three trace files I file monitor replaytxt contains the simple M sequence of the execution I file monitor testtxt contains the M sequence of the execution I file monitor commtxt contains the Communication sequence of the execution The value of environment variable CONTROLLERS determines how many sequence files are created set CONTROLLERSSINGLE one simple M sequence and M sequence per program Unix setenv CONTROLLERS SINGLE
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'