New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Vito Kilback

ConcurrentProgramming CS361

Marketplace > Drexel University > ComputerScienence > CS361 > ConcurrentProgramming
Vito Kilback
GPA 3.88


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 60 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS361 at Drexel University taught by BruceChar in Fall. Since its upload, it has received 44 views. For similar materials see /class/212436/cs361-drexel-university in ComputerScienence at Drexel University.

Similar to CS361 at Drexel

Popular in ComputerScienence


Reviews for ConcurrentProgramming


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/23/15
CS 361 Concurrent pro gramming Drexel University Fall 2004 Lecture 21 Bruce Char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use Final exam Tuesday June 8 6pm 8pm location Nesbitt 125 Cumulative closed book 0 Emphasis on concepm and programming techniques with semaphores and monitors 0 Exam will cover distributed computation last part of course although details of lava RMI not heavily emphasized Review of course with sample questions 0 Threads and processes the programming concepm that make concurrency readily feasible 7 What is the relevant hardwareoperating system basis for threads and processes Race conditions 0 Race conditions 7 a big problem with concurrency 7 readwrite of a single variable 7 readwrite of data structures 7 multiple variable updates not read in order written the rationale for Java volatile variables Critical sections and mutual exclusion Prevent program incorrectness by preventing race conditions allow one thread at a time in certain sections of code 0 How do you determine a critical section of a program Can there be more than one Can a critical section of code have pieces in different procedures 0 What is mutual exclusion Implementing mutual exclusion Software 7 Peterson s Dekker s Lamport s algorithms Hardware 7 Test and set 7 Other hardware instructions Correctness criteria for concurrency 0 Identification of critical sections 0 Mutual exclusion for critical sections 0 Deadlock 0 Prevention of starvation in the absence of contention Fairness prevention of starvation in the presence of contention Livelock Correctness criteria 0 Find faults bugs low of situations presented in the course 0 Prove correctness proofs by contradiction Classical concurrency problems 0 Bounded buffer producerconsumer The sleeping barber 0 Dining philosophers 0 Database readerwriter 0 What is the value of studying these problems Theory I Proofs of correctness deadlock avoidance prevention of starvation mutual exclusion guaranteed typically through proofs by contradiction or exhaustive inspection of all scenarios Proofs of equivalence ofpower between semaphores monitors and test and set by construction Avoiding deadlock in using multiple monitors or semaphores through a discipline of use More Theory from Silbershantz Ch 8 Deadlock analysis terminology and techniques 0 Deadlock detection through cycle detection in the resource allocation graph 0 Proofs of deadlock avoidance through counting argurnenm Distributed Computation 0 Quick tour of following concepts 7 Virtual shared memory 7 Message Passing basic distributed operations blocking or nonblocking 7 Remote Procedure Call and Extended Rendezvous as an abstraction on top of message passing 7 Java RMI as an instance of RFC 0 Distributed Mutual Exclusion Algorithm Some sample questions Definitionsmeal 7 Give a complete de mhun ufa signal and exrtmumtur mplete definition ufabmary semaphure What goes u in aremute prunedure eam What dnes atest and setmstmmun am How canrtbe usedtu build nee andpustrpmtuculs furmutual exclusmr somn w 2 What39swmng rfanythmg withthe following concurrent ende 7 CompleteLhepmufbycontradrcmnufthe avmdance nfdeadinekquot Lheurem fur urdered use uf semaphures 7 Cunsrderasystem e srsungufmneresuurcesufthe sametypethatar shared by fuurpmcesses eaen ufwhrch needs atmustthree resuur es What is the least number ufresuurces that would yuu need to pmde fur a srmrlar situation with ve processes needing at musttwu resuurces7 Why 7 Procedural construction 0 Describe how to implement a counting semaphore using test and set 0 Describe a starvationfree fair way of solving the dining philosopher s problem by assigning tickets to each philosopher Sample problems continued I Give de nitions of the following terms extended rendezvous volatile variables in Java N threads Want to share 2 printers They do so by consulting With a printer resource controller r rrequestThread t returns 0 or 1 id of printer to se r releaseintid Thread 039 releases printeri invoker owns printer does nothing otherwise Implement this using monitors Other sample problems 0 Review the exercises and your answers 0 Review questions in the lecture notes Instructor availability Char Instructor will be available during office hours June 8 35pm and by appointment on Friday June 4 Zaychik by appointment only CS 361 Concurrent programming Drexel University Fall 2004 Lecture 16 Bruce char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use pagel Deadlocks revisited Silbershantz ch 8 Deadlock characterization I Necessary conditions for deadlock 7 Mutual exclusion A resource must be protected by a mutual exclusion lock only one thread at a time can access it 7 Hold and wait Athread must acquire oneresource and be waiting for another 7 No preemption a thread cannotpreeempt another for a resource Preeem tion means that a thread holding a resource give up its access to mother even though it has not yet done what it wanted with the resource 7 circularwait There mustbea set ofwaitingthreadsTo 1 T2 Tn such thatTo is waiting forTl Tl forTz and Tn is waiting forTO page 2 Necessary conditions for deadlock I All the conditions must hold for deadlock to occur The Hartley rules about looking down semaphores avoid the 43911 condition hence guarantee deadlock avoidance I The conditions are not independent For example if there is a circular wait there must already be hold and wait Resource allocation graphs I The resourceallocation graph is a way of representing the relationships between resources and the threads that access them I Graph terminology can be used to describe dea ock situations I The graph representation allows people or computer programs doing deadlock analysis to use graph operations to determine if a situation allows deadlock page A Directed graphs I Resource allocation graphs are directed graphs A directed graph is a set of Vertices V sometimes called nodes and a set of edges E I Typically in a directed graph the Vertices are drawn as labeled circles or squares and the edges as lines connecting pairs of Vertices with an arrowhead indicating the direction of the connection as o Resource allocation graphs in a resource allocation ga h the vertices are divided into two subsets R for resourcetypes andT for threads Edges existbetwem nodes ofT and nodes ofR a An edge Ti egt rap is a request edge it is usedto indicate that thread i is type to become available An edge Ki egtTigt isan s fgnmenr edge rtmeansthatThreadihas gotten accessto Resource o type i and is using it type i For orample lfResource l are printers there may be several printers in the stem It may not matter which printer a threa gets accessto as long as it gets access to a Erlnter eventually This wouldbe modeled by a resource allocation gap with several T vertices but only one R Veda page 6 Example Figure 81 Silbershantz p 231 General notes FourResource types Three threads T1 requesting Resource oftype 1 has access to aresource oftype 3 re are two instances of resource type 3 and three of resource type 4 What else Deadlock Theorem I If the resource allocation graph has no cycles a circular path following the arrows then there is no possibility of deadlock I If there is a cycle and there is only one instance of each resource type then there is deadloc If there is a cycle and there is more than one instance of some resource types then there may be deadlock or maybe not page 2 Example graph with unrecoverable deadlock Silbershantz Fig 83 p 232 T1 T2 and T3 are deadlocked Graph has acycle T1gt R1 gt T2 gt R2 gt T3 gt R3 gtT1 T1 wants R1 but is waiting for T2 to give it up T2 wanted R2 but is waiting for T3 to give it u T3 wants R3 but the available supply is being held by T1 and l N o 5 lt o rm 3 U o a o to get the another type ofresource 11 Example graph with recoverable deadlock Silbershantz Fig 84 p 232 Graph has acycle T1 gt R1 gt T3 gt R2 gt T1 T1 andT3 are both blocked but we can avoid pennanent deadlock by releasing the resource currently held by T4 and giving it to T3 and by releasing the resource held by T2 andgiving it to T1 page in How to handle deadlocks I Three techniques exist 7 A protocol that guarantees that the system never enters r Allowing deadlock states to be entered but then have a e Ignore the p r page way ofrecovering from it roblern and pretend that deadlocks never at freeze up because ordeadlock would require you to kill and restart the application ifa s may be economically acceptable even ifit is not correct Deadlock prevention I Deadlock prevention means Writing a program so that none of the necessary conditions for deadlock ever occur during program execution Deadlock prevention methods typically constrain hoW requests for resources can be ma e I The rules for semaphore usage mentioned in the Hartley textbook are a kind of deadlock prevention page 12 Deadlock avoidance Deadlock recovery 0 Techniques for deadlock avoidance If the system does not prevent or avoid typically look at what resources a thread is dealeCk 1t may Stlll be able ti TCCOver likely to ask for during its lifetime before it from dealeCk For example If tVVO threads makes such requesm Requests are denied if are deadlock a thud thread or the user the technique decides that granting it would maydetect this and recover from deadlock by killing one of the deadlocked threads and lead to a deadkmk State restarting it or by forcing one of the threads to release a resource that is part of the cause of the deadlock page 13 page 14 How to think about deadlock More about Java deprecated methods prevention Recall the four conditions You can deadlock proofquot your rogram if ou try to avoid all ofthem from happening 7 Mutual exclusion Perha s it is notnecessary to have mutual exclusion for example i all threads are reading a constant the Constant does not need a mutex o 7 Hold and Walt Perhaps a thread does not need to use two resources at once Iflt uses only one at a time holdrandrwaltwlll never happen Orpem ps a thread can ask for all resources it wants at once and be given them all at the same time Again this avoids holdrandrwaltrthare will be only waiting or there will be holding e silbershantz n testhatthese methods still permit staivation and 0 that they are not eas to do using Java s native concurrency feature ofsynchronize methods 1 m d 1m veDeirecafimr html we is We is More deadlock prevention More deadlock prevention The third condition is that there be no preemption of Avoiding circular wait S bershantz resource that ave already been allocated We can devise twork preemption schemes ha mentions the total ordering of resource 7 fathr 1 ea asks forresources se uentiall holdln them as it attempts to acquire more If it I evemaydeto Waglt then all oflts types techniques that Hartley mentions currently held resources are preempted implicitly released When it resumes it will try to reacqulre all ofthe resources it gave With semaphores up in addition to the ones it has nevebeen ableto getbefore min actively using the resource Once it startsgwaltlng the resources it is holding may be preempted A thread is restarted only when can get all the resources itwas requesting and reacqulres all ofthe resources that lost due to preemption to another d page 17 page l2 Deadlock avoidance Deadlock avoidance algorithms prevent deadlocks by restraining how requesm can be made preventing at least one of the four necessary conditions for deadlock from occurring 7 Side effecw from deadlock avoidance methods an be loW device utilization reduced system throughput and potential starvation page 19 One type of deadlock avoidance algorithm count resources requested 0 Each thread declares the maximum number of resources of each type that it may need Each thread asks for clearance from a central authority before it starts requesting any resource Threads must wait without holding any resource until they are told to proceed by the authority Since there is no holdandwait there can be no deadlock page 2 An algorithm for deadlock avoidance 0 Works in an environment where there is only one instance of each resource type n Threads with In different Resources Only one instance of each resource 0 Before execution of any thread we work out which resources each thread may ask for page 2l Resource allocation graphs with claim edges Asbeforewehavegmphswlth threads nodes lndlcated b clrcles and resources no es ndlcated by squares An edge goes romaresourcetoathreadlf the resource IS allocated held by thethread An edge goes erorna th readt a resource lfthe resource IS requested but not yet held by the thread A new klnd ofedge glven by a dotted llne goes from a thread could ask for the resource R ls held by T1 requested by T2 RZ could be requested by T1 and T2 but yet neltherhas dune su page 22 Algorithm for deadlock avoidance Ifthread Ti requests resource Rj then if putting in an allocation edge would create acycle in the where deadlock might occur We have the gzph darnthe preylnus slide TZ asks for R2 We see that changing the RZrTZ N 23 gaph with a cycle su we deny the E E Using the algorithm in a system when the system IS lnltlallzed all the edges ofthe graph are clalrn edges slncenothlng has been ganted Wlth each resource request we turn one ofthe clalrn edges lnto an asslgnment edge resource gamedquot edge and see whether th5 results In a gaph wlth a cycle Iflt doem t we allow the re uest and keep the h Iflt does we deny the request and the edge when athread IS flmShed wlth a resource we turn the asslgnment edge back lnto the clalrn ed What happens lfa threads request 15 dmled7 It could busyrwalt occaslonally trylng the request agaln Or lt could block and w whenevera relevant resource 15 returned Thls Implles sorne kmd of controller thread that keeps track ofwho wants what and does the wakeup notlfy slgnal to the blocked thread 5 5 page 24 Other algorithms for deadlock avoidance I There are algorithms to handle more complicated situations when the system has several instances of a resource type instead of just one I See Coffman et al System Deadlocks Computing Surveys Vol 3 no 2 June 1971 Pp 6778 page 25 Deadlock detection and deadlock recovery Typically multithreaded application programs do not try to handle de ocks by detecting and recovering from them ey try to avoid dead oc s is is ecause deadlock in an application typically noticeably degrades performance andor functionality in an unaccep able fashion Operating systems however may hand1e several different processes from several different users It may e necessary for OS to rec ver from proces es th are hung due to deadlocks or other problems Deadlock detection and recovery is more important there ve the discussion ofthis sections 8 o and 8 7 to acourse on operating page 25 Deadlock Detection I If there is a process or thread that can monitor resource utilization then deadlock can be detected if that processthread looks at cycle detection of the resource allocation graph I The detector processthread must maintain the resource allocation graph and periodically invoke a cycle detection algorithm on it I How frequently should the detection algorithm be invoked It depends on the frequency of deadlock occurrence and the costs of deadlock related to how many processes can get stuc page 27 Deadlock recovery I The deadlock detection processthread could recover from deadlock through two techniques 7 Processthread termination 7 Resource preemption page 22 Dangers of processthread termination I Not good ifkilling the processthread leaves shared objects or variables in a state that violate their design For example if a processthread is killed in the middle of updating a queue shared by several processes or threads then the queue could be le in a corrupted state Where links are missing or invalid I Recall that Java threads can t be killed safely through use of stopO page 29 Processthread termination I Several policies 7 Kill all involved in a deadlock Potentially aipmslve throWlng away a lot ofcomputation 7 Partial termination Kill one at a time until the deadlock cycle is eliminated ore overhead in that deadloek deteetion algorithm must he reinvoked eaeh tame somethingis killed The standard algorithm is OnquotZ where nis the numher ofproeessesthreads so this can get expensive ifnis large Determine a set to kill to end the deadlock and kill only those Typically the set is chosen so as to minimize cost Cost is a policy issue and is discussed better in the contait ofan operating system course page 3 Resource preernption assumes Resource preemption as a way of eliminating deadlocks that aresonrce can be tak n away 0m aprocess or thread that is blocked waiting for other resources andbe given to another This is not trivial to program but is possible If one can preempt resources then a system must L o the preempted threadprocess Typicaiiy the system state is rolled back to where it was before the preempted entity st rt 01 o e Smrvanan Decide whether it will tolerate stawation in the presence ofcontention through preemption page 31 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 14 Bruce char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use page Database readerwriter solution inpnit Inilities in e m piivate Hinnysemaphnxe nk new ninaiysenaphnietlt public oatabasett cureat Database t Database readerwriter problem The readers and writers problem readers may read a database sirnu1taneous1y as long as no writer writes on1y one writer at atirne may write ifthere are no active readers Attain maximal para11e1isrn readers may read simultaneously ifthere is no writing data integrity only one writer at a tirne ifno readers are reading Possible additional goal avoid writer starvation locked out ofwriting because readers are a1ways coming along to page 2 Reader code public void startkeadint i Pmutex unmeaders if nulnkeader 1 Systemnutprintln age ageo reader i waiting to read nulnkeaders numkeaders Pnk reader Systemnutprintln age ageo i be r nulnkeaders i has gun eading nulnkeaders vnutex public void endkeadint i Pmutex numkeadersquot Systemnutprintln age a e reader i finis ed reading numkeaders numkeaders f nulnkeaders 0 Vnk vnutex Writer code public void startwrit9int i Pnk Systemnutprintln age ageo mums i i has begun Writing public void endwriteint i svst mnutprintln age ageo murals i i has finished Writing new Notes on readerwriter solution 7 Only the rst reader should lock the ok lock The last reader should unlock it When it nishes its read T en the 7 Writers can Write Starvation of Writers might occur page 6 Preventing starvation of writers I Serialization 7 Use a queue for all makes any readerwait who arrives a a a writer Platooning 7 Use a queue for waiting threads and have a separate active groupquot ofthreads 7 While readers in the active goup are working writers wait in the ueue r If a writer is waiting any later reader must wait in the queue 7 After a writer finishes it sweeps all the waiting readers into the active group even ifthey have arrived a er the nert writer 7 Avoids starvation but increases parauehsrn How do you do this I Hint try time stampng a reader s or writer s arrival to keep track of who should proceed or not has 2 A problem to solve I Baboons crossing a canyon I A canyon cuts through the territory of a colony of baboons the baboons use a rope stretching across the canyon to cross from one side to the other the rope is strong enough to permit any number of baboons to cross in the same direction at the same time but is too thin to allow baboons to cross in both directions at once Baboons cont I So ababoon that wanw to cross from west to east must wait until all westward moving baboons have nished and the rope is free and vice versa I If the rope is being used by westwardmoving baboons then other baboons may start to cross from east to west no matter how many eastward moving baboons are waiting page In How to solve it I Firsg write your program without worrying about a series of eastwardmoving baboons holding up the waiting westwardmoving ones ie don t worry about starvation I Then modify your program so that it is fair and there is no starvation Use serialization or platooning to do this or another method of your invention page Deadlock with semaphores 7 Deadlock can happen through a typo 7 Ps critical section Ps page 12 Another way to get into trouble Thread 1 Thread 2 PS PG 1 0quot V0quot shVG Vs Va A PS succeeds B1gtr succeeds A blacks an Pcr B blacks an PS page 13 How to avoid the trouble of interlocking semaphores one my to avoid dead1ock on semaphores is to assign a global order to all semaphores and require that all threads decrement p operation 39 quot lobal order 39 39 quot39 a et of threads to develop in which each thread is blocked waiting for a r i39ii i ii iii u 39 39 semaphore Why Suppose all n threads are blocked They are using semaphores s1 s2 s3 Sn Look at these threads in the total ordering that s 1ast in the total ordering be Sk Then someone else must have caused Sk s value to become zero by doing aPSk operation But if ere But how can that be It must have done aPSk efore the current Ps1 and that vio1ates the ru1e that you do PSk after Ps1 En f proof CS 361 Concurrent programming Drexel University Fall 2004 Lecture 8 Bruce char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use page Peterson s attempt mutual exclusion for two threads public void wantToEnterCS nt r preprotocol desireCSIvalue true last othera while desireCSoLherIvalue ampamp last othera busy wait ThreadcurrentThread0yield0 public void nishedInCS nt r postprotocol desireCSIvalueralse page 2 Proof of correctness I Prove that the algorithm 7 enforces mutual exclusion correctly by showing that it is impossible for two threads to be in the critical section simultaneousl 7 doesn t allow deadlock ie it s impossible Z doesn t allow starvation in the presence of contention Z doesn t allow starvation in the absence ofcontention I A separate proof for each point each done as a proof by contradiction page Proof by contradiction I If you show that assuming p leads you to conclude something which you know to be false then you are forced to conclude that there are no circumstances when p is true Z in other words p must be false all the time p 3 false 3 ip page A Game plan for proof by contradiction I We talk about two threads running Peterson s algorithm We assume that they violate ME call this assumption v We show that assuming v leads to the conditions that contradict the threads programming In particular We conclude s that each thread set a variable last to different values know this vio ates the rules of programming languages in other Words sZ alxe av I Since We have shown vgtfalse We conclude that the two threads cannot violate ME if they follow Peterson s algorithm 2 5 Proof of mutual exclusion property I Some observations on Peterson s code 7 the only values that last can take on are 0 and 1 Z ach thread can enter its critical section only if l desrrec value ntherI l ampamp last Z nther1 That is either desireCS value other 1 is false or last Z Z l I Start ofproofby contradiction Assume that this algorithm does not support mutual exclusion So there must be a scenario Where both threads end up in the CS at once page 6 Proofs by contradiction when the world is divided into two cases I Show each case separately v 2 false 2 VA true 2 false E VAcase1 case2 2 false E v case12 false v case2 2 false Proof of mutual exclusion case 1 I Suppose one thread say 0 gem through the preprotocol evaluates the while condition before the other thread has nished executing any lines of it before it has set its value ag to true It s then easy to see that the second thread will get stuck in the loop until the rst thread does the postprotocol This contradicts the assumption that both threads get into the CS at once I We get a similar contradiction if we assume that thread 1 gets in rst and thread 0 lags I There are actually two subcases caselacase1b 7 Pagegve ye shown casela and the proof for caser is What s false ME violation A rhread 0 gets into cs A A Thread 0 gets into cs rst does 39nto CS An easy toprovefact pAqlAqZAr gt q2 2 false One case down one to go I We ve taken the assumption in casel to prove something that we know is false So we now need to prove that the assumptions in case2 also lead to I Case 2 is not case 1 a scenario where there is overlap in the preprotocol one thread nishes at least the rst instruction before the other thread begins execution of is last one page in Case 2a thread 0 ahead of 1 but both in preprotocol at once public void mntTnEnerSGnt 1 prepmtncni desirecsrrvaiue true A last mhera B whiie desireCSntherrva1ue ampamp last ntherr C busy wait Threadcurrentrhreadyie1do We are assuming thread 1 has dune A b 39nre 0 dues c Sn when thread 0 dues c 1ast0 inther0 nr eise thread 0 will limp instead of get intn e I Thread 1 must have set last a er Thread 0 set it page Case 2a continued I When thread 1 checks its while loop condition we know that desireCS 0value is true because Thread 0 has already done it So the only way that thread 1 can fall out ofthe while loop is if last1 But we know that at that point when Thread 1 does this check it has already done last0 So it must be that Thread 0 has set last a er Thread 1 I We have deduced that if both threads get into the critical section each must have set last last to different values This is false based on what we know about the way programs and variables behave page 12 Proof of mutual exclusion the conclusion I There is a case2b where Thread 1 is ahead of Thread 0 We nd a similar problem then I We assumed that the algorithm failed to provide mutual exclusion From 39s we were led to two kinds cases overlapno overlap of execution of the preprotocol I In both cases we found that assuming that the algorithm allows violations of mutual exclusion leads to something we know is false that both threads get into the CS while one is stuck in the preprotocol or that last has two values at the P Mame time Proof of mutual exclusion the nale I We can conclude that it is impossible for the algorithm to violate mutual exclusion I Avoiding double negatives another way of saying this is that the algorithm guarantees mutual exclusion at most one thread is permitted into the critical section at a time page 14 Proof of starvation in the absence of contention I If thread 0 is not interested in entering its CS then its flag is false and so thread 1 can enter because the while loop will not block it Similar argument for thread 1 page 15 Proof for no starvation in the presence of contention I We prove this by contradiction Assume that thread 0 is frustrated while thread 1 tries and succeeds repeatedly We will show that assuming this leads us to prove a statement we know is false page 16 Proof 1n the presence of contention con t I If thread 0 has entered the preprotocol and has set desireCS 0 to true but is stuc it must be executing its while statement repeatedly Thus desireCS 1 is true and last0 at least while thread 0 is repeating I But this means that thread 1 will enter its critical section if it hasn t already Once it leaves its critical section it will reset desireCS1 to false page 17 Proof in presence of contention con t I What can happen after thread 1 leaves is post protocol 7 Either thread 1 whips aron into its preprotocol and sets desireCS1 to true again before thread 0 notices or 7 Or thread 0 notices that desireCS1 is false before thread 1 tries to reenter the preprotocol It proceeds into the CS which again is a contradiction of our original assumption page 12 What happens when thread 1 enters the preprotocol again I After setting desireCSl to true again thread 1 will then set last to 0 It will hang up in its loop Thread 0 will wake up because of the yield and stop looping because its while condition is no longer true It will proceed into the CS This again contradicts our assumption that thread 0 was hopelessly stuck page 19 Completed proof of no starvation in presence of contention I Thus in all cases assuming that thread 0 is stuck in is loop forever produces a contradiction So it s impossible thread 0 must enter is CS after at most one entry by thread 1 page 2 Conclusion of proof of no starvation I A similar argument can be made for thread 1 being stuck forever We have to check this but it really goes through by a mechanical substitution of 0 for l and vice versa in our original argument I These are all the possibilities for threads getting starved with contention We end up with a contradiction in each case page 21 No deadlock I If both threads are stuck in the critical section then they both must be looping I Once they are looping neither can change the value of last or their desireCS values I For both to loop both threads have set their desireCS values to true I For both to loop last must be both 0 and 1 at the same time This is impossible violates the rules of programming page 22 a 3 Peterson s attempt Hartley s way public void wantToEnteCSint i Prepzotocol desireCSIi value true las i while desizecsothezivalue as last i wait Theadcuzzent39l hzead yieldo public void finishedInCSint i Postpzotocol e desizecs i value als page 23 Peterson s attempt problem 6 of public void wantToEnteCSint i Prepzotocol as i desireCSIiVa1ue true while desireC5otheIvalue as last 1 busy wait Theadcuzzent39l hzead yieldO public void finishedInC5int I Postpzotocol desireCS I value alse page 24 Works for only two threads 0 Note that if there are other threads doing other things the yield loop may not give control to the other thread dealing with this critical section Have to hope that sooner or later the other contending thread gets a chance to do its preprotocol page 25 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 19 Bruce char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use Implementing the client 0 It has to implement the ComputeTask interface 0 During main initialization it has to establish a link to the server and start the computation that eventually leads to a call to the Server Client code part 2 try l stung name quotHquot args quotcanrputequot We re golngto ask the rmlreglstry for a partlcular remote object We need to glve 5 complete narne queen mcs drerel eduCompute Hostnamelscommand llne argument to the chem program when lt IS started u P campute Namlngluukupname RMI system keeps the Compute Engine object alive after main 0 The ComputeEngine is available to accept calls and won39t be reclaimed until its binding is removed from the registry and no remote clienm hold a remote reference to the ComputeEngine object Client code part 1 1mpurt javamat 1mpurt cumpute puhlre class CDmputeP1 l This client will a t e e rver tn campute u uhlre s atre arnltstrrng args t r SystemgetSeeurrtyllanagero null t 5y em et 1tyManagernew aurseeurrtyuanager o l set up default security manager Client code part 3 Set up task must be serlallzab le P1 task new P1 Integer parseIntargs 1 Get server m perfnrm result cast result tu right type rrum Object argueernal pr argueernal comp executeTask task 1gtrlnt answer s ystenr uutpr1ntlnp1 Handle remute excepu39un eateh Exceptan e t Systemerrpr1ntlnquotcumpute1 exeeptren v egetMessage epr1nt tackTraCe rmiregistry is on server machine in this example client server Code for computing Pi impart compute impart vamah public class Pi implements Task t u censtants used in pi camputatiun private stat l signecimal zauo aig ic fi Decimal valueof n H digits of precisiun after the decimal paint private int digits W Censtruct a task ta calculate pi ta tne specified precisien punlic P11nt digits t tnisdigits digits 2 gt Code for computing Pi Calculate pi public Object executeo t re n CDmputeP1d1g1ts gt digits afte decimal pain computed using Machln39s formula piq 4 sctanl5 e arctanl239 ex rctanx ta Cumpute the value of pi to the specified number of r tn t The value is nd a a series pansien ef sufficient precisien public static signecimal computeP11nt digits t int scale digits 5 signecimal arctanli arctanlt5 scale The computePi object contains the method for how to compute 7 The server does not know how to compute Pi until it receives the object 0 The code for computing Pi is transmitted along with other data in the Pi object from the client to the server over the wire computePi is a serializable object Building remote code Three packages bui1t for remote example in Javatutorial e Compute engine c1ierit Create class les for Compute interface Create jar lesforthe computepackage distribute to server at c1ierit developers Compi1e servercode Run rmic compi1er on it too Compi1e c1ierit code p1ace some class les in publicihtml subdirectories so that they can be downloaded at run time Compiling the programs 0 Note that we have a compute package a client package and an engine package The server and the client share the interfaces in the compute package I In a realWorld scenario in which a service like the c mpute engine is deployed a developer Would likely create a JAR Java ARchive le that contains the Compute and Task interfaces for server classes to implement and client program to I The server developer uses the Compute and Task interfaces through the jar e I The client developer uses the Compute and Task interfaces through the jar le How to create a jar file Win32 cd eMy Programsmcs361rmiexample javac computeCompute java javac computeTask java jar cvfcompute jar computew class UNIX cd psebcharmcs361rmiexample javac computeCompute java javac computeTask java jar cvfcompute jar compute class Where to put files for public access I Tutorial suggests putting it into a classes subdirectory of your publicihtml directory so that http servers can get it through URLs such as httpcs drexel eduNbcharclassescompute jar Making use of a jar file in compiling other programs javacclassp ath h0mebcharpublicihtmlclassescompute jar MyComputeEngine 39ava Compiling the server classes UNIX cd psebcharrmiexample Change to root directory engineCumputeEngne j ava Compile programs A quotrd directory of the remit stubs is cwd so stubs go Vito same directory as source mkdir homebcharpublicihtmlclassesengine Copy these Ma a 3 downoadaoie piece 7 Make the interface files downloadable I On Unix I cd homebcharpublicihtmlclasses Go to directory where jar file is I jar xvf computejar Unpack jar file in that directory Building the client classes Let39s assurne that user jones has created the client code in the directory chomejonessrcclient and will deploy the Pi class so that it can be downloaded to the compute engine in the networkaccessible directory chomejonespublic7htmlclasses also available via some web servers as httphostNjonesclasses The two clientside classes are contained in the les Pi java and ComputePi java in the client subdirectory of the class subdirectory ofJones publicghtrnl directory Compile the client classes set putejar ed chumejunessrc jsv c ienmcuni ute 1ava Compilation uses classpath variable instead of command line javac rd chumeju llcihtmlclasses cllentP1java Only the Pi class has to be accessible to the server Compilation also uses classpath variable Running the programs I Create aperrnissions le for the security system I Start the rmiregistry server on the server machine I Start the server I Start the client on another machine possibly I Both the client and server machine should have Web service available Permissions le Here is a general policy file for jdkl 2 that allows downloaded code via Tl P from any code base to do two things Connect to or accept connections on unprivileged pons ports greater than 1024 on any host Connect to port 80 the port for HTTP Start the rmiregistry UNIX unsetenv CLASSPATH rmi registry a start rmiregistryquot on Win By default the registry runs on port 1099 acornrnand line argument will ovenide the default Do not forget to unset your CLASSP TH or else the rrniregistry may not tell clients properly accessible locations for rernote objects grant l l a Start the server Win32 java classpath D39avanni server codebase lechomeannpublic7htmlclasses javarmi server hostnarnezaphod east sun corn Djava security policyjava policy engine CornputeEngine Code base is URL where downloadable les are rmiserverhostname is where rmiregistry is running javapolicy where that security le was put engineComputeEngine is the program being started up 24 Start the server on UmX java Djavanni server codebasehttpzaphodannclasses j rmi serverhostnamezaphod east sun com Djava security policyjava policy engine ComputeEngine Code base is URL where dovmloadable les are rmiserverhostname is where rmiregistry is running javapoicy where that security le was put engineComputeEngine is the program being started up StaIt the client for Unix i java D j ava nni server codebasehttpfordjonesclasses java security policyjava policy client ComputePi zaphod east sun com 20 clientComputePiquot is what s being started up zaphodeastsuncomquot and 20quot are command line arguments to the program giving the location ofthe name service and the number ofdigits to compute to the client program Who s running where on Java RMI example CS 361 Concurrent pro gramming Drexel University Fall 2004 Lecture 10 Bruce char and VeraZaychik All rights reserved by the author C8361 Permission is given to students enrolled in Fall 2004 to reproduce these notes for their own use page Midterm Tuesday May 4 Will coverchapters 173 plus sectionzt 1 ofHartl book Also sections 2172 o 3 1 3 o 3 1415 1545 6 of e silbershantz Applied Operating systems textbook Material up to and including Lecture 10 Group Exercise 9 this lecture closed book Kinds of questions 7 Desenbe eenanos and cunsequences ufrace conditions 7 Analyze eode torproperoes mutual excluslun starvation deadlock etc 7 Assemuns e what must be true at a certain point in a pmgram 7 What e 37 ful Y Desenbe meaning ufcude desenbe cunsequences ufchanglng code page 2 What s wrong With this program public void wamToEnlerCS m I preprotoco1 desireCSIvalue true while desireCSoLherIvalue ir air 1 take turns backing orr desireCSIValue false back off while turn lother busy wail rea curreanhread0yield0 desireCSIvaluetrue end if end while public void nishedInCS nl I postprolocol 39 eCSIValue false 0th I es public int otherint I remrns the ID DI the other thread return 11 quotn 2 Flaws with respect to providing mutual exclusion deadlock preventation prevention nf starvation in the presence or absence Hf C nmntiun It you find a flaw describe it and give a scenario that illustrates the flaw 1r ou dun t find any flaws say so and explain why the zlgirithm avoids starvation in the presence of contention es 4 Semaphores e A counting semaphore is an abstract data type with two atomic uninterruptableoperationspandV T data eld known as the value ofthe semaphore is an integer which is supposed to take on nonnegative values 0 1 2 7 When created the value ofthe semaphore is initialized by the constructor e g Semaphore s new Semaphore 1 7 e sP or Ps is known as down or dutch for passeren to pass 7 orVs is known as up or vrygeven to release Semaphore semantics e The 1 operation decrements s in an atomic non interruptable action ifit is gt 0 Then the thread doing the 1 operation proceeds 7 Otherwise ifthe value ofthe semaphore is already 0 the thread doing the 1 operation waits e Ifathread invokes the V operation then ifno thread is waiting from doing aP then the value ofthe maphore is incremented and the thread doing the V operation proceeds e Ifathread invokes the V operation then if another thread is waiting from doing aP operation with the semaphore then one ofthe waiting threads is released andthe thread doing the V operation is proceeds The value ofthe semaphore is Lot incremented in this c raters Semaphore notes I Remember P and V are atomic uninterruptable operations When a thread blocks in a P it releases the semaphore for use by another thread doing a P0 or VO I Can have several semaphores 1 2 S3 etc in a program Doing a SlPO or SlV doesn t affect operations with 2 S3 etc I Another notation for describing P and V with s holding the value of the semaphore P lt await sgt039 s s1gt V lts s1gt g 7 More semaphore notes I Multiple threads can be blocked waiting on a PO operation A VO operation will release one of the threads But there is no guarantee about the order in which waiting threads are released 7 might be FIFO LIFO or picked at random I This could lead to starvation in the presence of contention with multiple waiting threads page 2 Binary semaphores 7 A binary semaphore is limited to the values 0 and l 7 A V operation applied to a semaphore whose value is already 1 has no effect 7 Binary semaphores are also called mutex locks 7 With some implementations of binary semaphores sometimes P is named lock and V is name unlock Locks I Sometimes the concept ofa lock is re ned to include the idea that only the holder of a lock is allowed to release it I This makes sense when the lock is to give the holder exclusive access to a resource I However sometimes a binary semaphore is used to block a thread until some event caused y another thread has occurred For that reason binary semaphores don t have any restrictions on who does the down and who does the up page in Back to general binary semaphores I Binary semaphores are used for 7 mutual exclusion synchronization enforcing mutual exclusion into critical sections an 7 condition synchronization blocking threads until some condition becomes true or some event occurs as with producerconsumer page How to do mutual exclusion with binary semaphores 7 Shared binary semaphore mutex with initial value 1 mutexPO pre protocol Critical section39 mutexVO post protocol page 12 Do some scenarios Semaphore s new Semaphore1 initialize to 1 sum critical section S v 1 Thread A does S P Decrements semaphore to 0 returns from call to P proceeds into critical section page 13 D0 some scenarios 2 ThreadB does s P0 Blocks 3 Thread c does s p Blocks 4 Thread A nishes cs do s V Instead of incrementing value ofsemaphore it unblocks athread say B A has finished What happens ifthread A does an s p at this point blocks Thread B finished cs does s V Unblocks athread say A A nished does s V unblocks c 304an c nishes cs does s V semaphore is set to 1 page 14 Binary semaphores also handle the producerconsumer problem I In general the Way to do condition synchronization With binary semaphores is I In one thread if condition PS blocks e For example for consumer thread ifbuffer is empty then do aPS which will block ifsemaphore is initially zero e In producer thread as soon as product is placed in buffer VS giving permission to the other thread to unblock I No missed signals We can do PS followed by VS or Vice Versa page is Producerconsumer code with binary semaphores int n count Binazysemaphoze s new Binazyhsemaphoze0 mutex new Binazysemaphoze 1 public void producero while true produceItemO 39 c un n PS block if buffer full enterItemO imutex count vmutex critical section protected for mutual exclusion if count 1 VS page 16 Consumer code with binary semaphores public void consumer while true if count 0 PS delay if buffer empty removeItemO lmutex count vmutex critical section if count n l vs release consumer if it s waiting consumeItemO page 17 Questions about this code 7 Go through a scenario of What happens When the producer produces into an unfull buffer and into a l ffer 7 Why are two and not only one semaphores needed page 12 How to implement semaphores 0 We can implement semaphores via busy waiting if we use something like Lamport s bakery algorithm page 19 Implementation of semaphores class Semaphore private int value public Semaphoreo value 0 public Semaphore int initial va e initial public void PO want39roantercs r Use any viable busywaiting mutex solution while value finishedrnCSO want39roantercs I value finishedInCS page 2 Implementation of V operation public void v0 want39l oantercs valuedt finishedInCS r page 21 Notes on busywaiting implementation Does this have the behavior that we want Ifthe semaphore is 0 then a thread doing aP busywaits unti1 the Semaphore va1ue is greater than 0 then proceeds The value ofthe semaphore is mutex d A thread doing aV operation ifthere are threads blocked whi1e doing ap then as speci ed one is re1eased an allowed to proceed This is because the bakery algorithm prevents starvation in the presence of contention e sooner or 1ater the V will be ab1e to increment the va1ue counter which will then re1ease one ofthe P s page 22 Using hardware interrupts off to implement semaphores PS trap to the operating system kernel Disable interrupts atomic access to semaphore IfSgt0 then S Sl Else queue the thread on S change its state to blocked and schedule another thread Enable interrupw e page 23 Implementation of VS VS trap to the kernel Disable interrupw IfS0 and queue on S is not empty then pick a thread from the queue on S and change its state from blocked to ready else S Sl enable interrupts return page 24 Notes on the intenupts off solution I This disabling interrupm of course doesn t work with a multiprocessor system We d have to lock the memory bus or use a busy waiting loop inside the OS implementation with a test and set or similar instruction page 25 An alternative solution I Let the counting semaphore go negative this indicates the number of waiting threads doing a P that are blocked page 25 Alternative 1mplementatlon s has a luckbeelean and valueinteger data members PS trap to the kernel While Tssleck true busyrwz it until SJnck is false register implicit alue svalue 7 1 schedule anether thread sleck raise 2mm page 27 Implementation V VS trap tn the kernel while TSsleck true busy mit register implicit svalue svalue 1 it svalue lt 0 then pick a thread from the queue an s and change its state rrem blecked to ready Slucklese 2mm page 22 J ava s synchronized feature does binary and counting semaphores I Jumping ahead to chapter 5 abit I Each Java object has a lock associated With it A method can be declared as synchronized I public synchronized void methodA Only one thread can run a synchronized method of an object at a time The lock is set in a mutex kind of Way When a thread starts execution of the synchronized method A thread blocks if the lock is currently held by some other thread running a synchronized method of the object page 29 Static methods versus ordinary methods I For synchronized static methods Java obtains a lock for the class before executing the method I For synchronized nonstatic methods Java obtains a lock for the object before executing the method page zu Java can synchronize on an object too a synchronized expression statement 7 expression is something that must resolve to an object or an array There Will be an internal lock associated With that object or array and the thread must obtain a lock on it before it Will execute the statement Which is regarded as a critical section ofcode page 31 An example of synchronization on objects public static void sortrntArraylt iht a synchronizeltagt do array sort here gets a lock on the array a so some other thread Can39t change the s in a while we re trying to do the sorting page 32 Java s lock is set to l by default a By default the lock for a synchronized method is 1 This is ne for mutual exclusion but if you Want a Thread executing a method to block until another thread gives permission to proceed it s not the rig t 39 g page 33 Book s library classes for semaphores I We can build a true binary semaphore from Java this is discussed in chapter 5 The book gives a BinarySemaphore class in the Synchronization package Whose constructor BinarySemaphoreint initValue Allows us to set things the Way We Want initially It provides P and V operations I There is also a CountingSemaphore class de ned in chapter 5 The constructor CountingSemaphoreint initValue sets this up accordingly It also provides P and V operations page 34 An example using semaphores ICnllnlinq r Hinaly seanaphaxe exaanpie pp 95791 i mu t he antpnt hefnxe any c s 31 antpnt a s and c 5 should aiteanate in the antpnt slxinq the tatai numhex of a s and c 5 th paint eaanaat exceed the mlmhex of n s that have heen antpnt np that paint aanpaat VLilities i aanpaat Synchznnizalinn page 35 at have heen antpnt at any given eiaaa Pa extenaa mac inpieanenta Runnable pnniie void xunH whilettxu napueuntuaanaanunnme Systmnulpxinl1 nh syatenantrinah1 p VlsumH m eiaaa we extend mac inpieanenta Runnable pnniie void xunH while turret nay11inub landmt nh m Ptsuml Systmnulpxinl1 h syateanantrinahm vm m class PC extend mac aanpieanenta itnnnahie uhlic void x lnt while tum nap11intn landmt nh y Plsuml Systmnnlpxinl1 c b syateanantfinahn m mmc class extends Halley s My hjecl class that has nap nauma ll huill in class we extend My hjecl ylnlecled static nal Hinazysemaphnxe n these semaphnxes a new Hinazysemaphnxet b axe static ylnlecled static nal Hinazysemaphnxe c so subclasses a new Hinazysemaphnxetlh Pa ma ylnlecled static nal Cnunlinqsemaphnxe sum and PC shale a new Cnunlinqsemaphnxet b than an n 139 paJlale IiJtaxLH mum stall lhxeads paJlan 5qu pmslan than stur symnnnw ntlnm Systemnulpxinl n1 a n SystemeiN H c sunF sllM page 37 What does this program do I A B must be output before any Cs are output I Bs and Cs must alternate in the output string A er the rst B is output another B cannot be output until a C is output And Vice Versa I The total number of Bs and Cs that have been output cannot exceed the number of As that have been output up to that point page 32 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 3 Bruce Char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use page Summary of last time 0 Java is Object Oriented 0 Java is syntactically similar to C 7 String class builtin 0 Correspondence between class names and file names 0 CLASSPATH determines alternative directories for classes also jar files page 2 More summary 0 Static methods and data members one occurrence of member per program Some De nitions 0 Asynchronous operation occurs because many computer system events happen at unpredictable times and in an unpredictable order As a resulg a program must work correctly for all possible timings in order to be correct page A Some Definitions 0 Concurrency 7 sharing of resources in the same time frame When two programs execute on the same system so that their execution is interleaved in time they share processor resources Multiprograniming Multiprogramming means that more than one process can be ready to execute 0 Can be implemented for both single and multiprocessor systems page 6 Parallelism I Pseudoparallelism 7 rapid switching of the CPU between processes as opposed to the actual use of several CPUs Also called timesharing I Only one process 1111111ng at any one time for a set small period oftime quantum I No assumptions about timing can be made I Each switch from one process to another is called a context switch Time and Speed Item Time Scaled time in human terms processor cycle 05 ns 1 second cache access 1 ns 2 seconds memory access 15 ns 30 seconds context switch 5000 ns 167 minutes disk access 7000000 ns 162 days quantum 100000000 ns 63 years page Naming conventions for classes variables I These are rules borrowed from Reiss Software Design textbook used in cs350 lava does not insist on them ut we recommend following coherent naming rules to reduce software engineering cosm Naming conventions for classes variables constants I Names ofclasses First letter capitalized eg class Movie I Names ofmethods rst letter lower case39 multi word method names capitalized second and successive words ublic int getTime 39 public void clear 0 I Names ofconstznts all caps final int BOARDisIZE page in lO I from command line argumenm I from the terminal I from files page IO stream classes I Compose them together to readwrite tofrom files text binary data other kinds page 12 File input example impunjava in a public class ExampleS lt puuiie stancvmd nnirrsuingar n Lhmws lOExcepnun Filelnputsmm stream newFiieinputStrmunput data lnputStrmmRader Eda new inputsmrnRauensuarn smrukmzatukms new sum ukenizarrauer wnuatukens anukmo l tukens TTiEOF lt TTiEOF unitin fur tukens SysLEm uutpnntirwnteger int taken mal Uriwl bulllrm furtnkms mam dusa exemraieaimim rapaereaeaaaeaaui m Execution results In input data le in cunent working directory Output euy Documentsm15361SpDZgtjava example java example Integer 3 page 14 File output example PrintWriter writer new Printhternew FileOutputStream output data writer printlnlt whatever needs to be written to 1egt page is File input also works with standard input redirection Idea use Systemin stream to do reading By default this reads from the keyboard But if you invoke the program using lt for standard input redirection javac iclasspath Example lt inputFile then Systemin will read from the inputFile instead page 16 Typical Java style is to compose constructors rather than allocating variables for intermediate objects that aren t used directly in the program StreamTokenizer tokens new StreamTokenizer InputStreamReader new FileInputStreani input data page 17 Builtin data types 0 ins oats charsboolean Strings arrays Vectors lists of Objects page 12 Vector example public stetit veid malnl trlng erng throws IOExcept10n Input treamkeader nee r new Inputstneenneedeeistneen St T ken zer tekens new stneenTekenizetineedet v 7 w v art uniieitekensnextrekeni i tokensJ TiEOF w quotrm s 1mm mm 1m x iint tekensnvei tekensnextTekeni 1m y iint tekens rival extrekeni 1m iint tekensnvei tekensnextTekeni Systemuutpr1ntlnlquotread 11 x quot quot y quot 11 z veddizienent inew MeViez lxy z stream tieseu for llnt tedntee u tedntee lt vsizei DDuntEr Systemuutpr1ntlnl iiMeViez lvelementAtchunterrat1ngl Vector elements can be assigned any subclass of Object impart javauti1vectnr class Test purine stetie vnid main5tring argv Vectnr v v new ctnl 0 v3ddElem2ntnew Integer1 creates integer nnjeet v3ddlllemznl1 3110 i m tint i iltvsizem it Systemnulpxinln1 item i ve1enentnt1ii i is Anythingexzqnzprimivjve type lint ninthnnimn char is asuhcim nfChjecl edge 2 Execution In inputZ data 1 1 9 3 z t 1 1 1 O tput e My Documentshmcsil s1 3pm gt3 eve vectDrExample inputzdete java vectDrE mple inputzdete read 4 7 9 read 3 z s t ed 1 1 1 21 9 3 p321 abstract classes 0 Subclasses used in program inherit methods and fields of superclass 0 But you can t create an instance of the superclass page 23 Inheritance to have class B be a subclass of class A write public class B extends A edge 22 Abstract class example public abstract tiess dttnettieni puniit 1m minutes puniit dttnettieni minutes 75 gt public 1m getiviindtesi return ninetesn puniit veid setiviindtes iint d i minutes dgt then class de nitions for Movie and Symphony public Muvle extends dttnettien i and penile synpneny extends neeeeeeien i mm 1 ene inpnun in aprogram edge 24 Interfaces 0 Java does not have general multiple inheritance It does have limited multiple inheritance 0 An interface B is a class that has only class declarations papne erase a anprenenea n c n i means that A inherits the methods of BC and D and can have methods and members of is own page 25 What methods does this class have Which ones did the programmer of the class have to implement public class DrawableScalableRectangle extends DrawableRectangle implements Drawable Scalable gt page 25 De ning an abstract class 0 public abstract class GeometricObject class definition goes here as normal page 27 De ning an interface class De niti0n starts with interface instead of class interface FloatingVessel int navigateP0int from Point to Point is another userde ned class Void dropAnchorO Void WeighAnchorO page 22 What is the UlVlL static class relationship implied by the declaration public class DmvmbleScalableRectangle extends DrawableRectangle implements Drawable Scalable gt page 29 As with C a pointer for the superclass can point to an object of the subclass classAl implementsA classBl extendsB class c public int method1A a B b public method2 int result B1 blObject A1 alObject b1 ject new B1 aIObject newA1 result method1a10bject blObject age 3n Packages package onto javaentertainment public abstract class Attraction Attraction java must be in an ontojavaentertainment subdirectory Ifthis file is in h0mebcharmcs361asmt10ntojavaentertainment The value ofthe CLASSPATH variable should include the value homebcharmcs361asmt1 page 31 Package invocation rc I isinLrl invoke through the full package name java onto javaentertalnment example7 even ifyou re in example7 s directory page 32 Importing classes that belong to packages I import onto java chapter7 entertainment imports entertainment class that belongs to ontojava package I import java io Obj ectInputStream imports Objectlnput class fromjavaio package I import java net imporm any class needed from javanet package page 33 Virtual machines I Operating system features and virtual memo techniques can be used to create the illusion that a process has in own processor with its own I This helps ensure that processes don t accidentally interfere with eac I The processor that the process thinks it has does not have to be identical with the underlying hardware This is the approach taken by Java 7 Java processes run on an abstract Java Virtual Machine page 34 The Java run time environment I Java is designed to run on a Java virtual machine JWVI I The Java compiler j avac produces a binary executable in the class le that is byte code a machine language for the W I The byte code is executed either by a an implementation ofJVM a an Interpreter so ware simulation tailored forthe operating system an hardware ofthe computer tnatt e JVM is running on a or it provides a justintime compiler J39IT that turns bytecodes into native maoliine language page 35 The Java platform I JVM the standard Java class libmries Application Programmer Interface I The Java platform may be invoked as a command j ava on Unix Windows etc or built into a browser N ewcape or IE or by supported by custom hardware I Different machines and 08s may have different implementations of the JVM but the same byte code should run on any Java platform page 35 Supplemental More Java Concurrent Programming Spring 2004 Bruce Char and VeraZaychlk All rights reserved by the author Permission is given to students enrolled in cs361 Spring 2004 to reproduce these notes for their own use page 37 APT 0 Best reference is online page 32 Garbage Collection 0 All memory allocated on the heap that is no longer referenced is freed up by the Garbage Collector 0 There is no telling when that will happen 0 There is a way to force garbage collection if needed Systemgc page 39 Java procedures are mainly call by reference 0 This means that procedures can easily alter objecm passed to them as parameters page 40 Building your own exceptions 0 Class ArgmenWegativeException extends Exception page A Programming with exceptions aiass Faclnxial Public static int aanrpnteunt ht thnms myumznuleqaliveilxceplinn otherexcepnons t if urltnt lhxw new mmentneaauvenxaeptiontt else xeunn 1 tand laterln aprogmnt lly t systsanontpunt1n tvaaaswex is n Faclnxialcmnyllletnn eatentmamntneaamenxaeptson et t Sy Lemexxpxinllnte voopsnt continue page 42 super I used to call the parent class39s constructor With argumenw if desired using the syn ax super argO argl I must be the very rst line in every constructor unless omitted in Which case it Will be automatically inserted Without arguments I super xxx to call methods ofthe parent I only goes one level up no supersuper page 43 Java lacks some C features I No templates But superclass is Object Could s With jects and then cast Exception primitive data types such as int oat are not subclasses of Object However ere are Wrapper classes Integer Doub e etc No overloading of operators although function overloading is okay I No io operators ltlt gtgt I No general multiple inheritance page 44 No environment variables in Java I No such thing as environment variables as there are with CCl t and Unix because this is not OS independent There s a system property setting mechanism that accesses properties declared in the command line invocation called SystemgetProperty read about it in the lava documentation page 45 instanceOf I can upcast and downcast but wrong cast can cause exceptions during runtime I To check whether a certain object is of a particular class use instanceOf page 46 keyword thi 3 To invoke one method from another in the same class an object must send a message to itself this methodName does the job To refer to a field use this fieldName When no ambiguity is possible this is optional private String text public Greetingstring text thistext text page 47 Object I equalsObject e I finalize I hashCode I toString page 42 Java Arrays Objects but not built with new Array 0 C like syntax 0 Size must be known at instantiation Homogeneous all elemenm of same type 0 Can contain primitive types page 49 Array Syntax Idioms declare a initialize allocate from heap int a new int3 stylisn Java int on new into like c less good note scope of i in for loop like c for int lt alength i r r SystemOutpr1ntln a 1 Z ai b a a b reference same array old b can be garbage collected string 1 colors7quotredquotquotbluequotquotgreenquot page 5 Command line arguments class CommandLineArgsDemoj ava c VOld mar lic s a i n stringU args H for int i argslength i Systemoutprlntln39 l 39 argsl 39 l 39 l l a java CommandLineArgsDemo foo lfool lbarl lb ql args0 isn t program name bar quotb qquot page 51 Java 2D Arrays char board new char88 for1nt y0 y lt boardlength y for1nt x0 x lt boardy length x System out1orint boardx y Systemoutprintln page 52 Collections in Java Manipulate grouped data as a single object 7 Java provides List Set Map 7 add contains remove size loop over sort Insulate programmer from implementation 7 array linked list hash table balanced binary tree Like C Standard Template Library STL Can grow as necess Contain only Objects reference types Heterogeneous Can be made thread safe simultaneous access Can be made unmodifiable page 53 List 0 Like an array 7 elements have positions indexed 0 size 1 7 duplicate entries possible 0 Unlike an array 7 can grow as needed 7 can contain only Objecw heterogeneous 7 easy to adddelete at any position 7 API independent of implementation ArrayList LinkedList page 54 Set I Like a List 7 can grow as needed 7 can contain only Objects heterogeneous 7 easy to adddelete 7 API independent of implementation HashS et TreeSet I Unlike a List 7 elements have no positions 7 duplicate entries not allowed page 55 Collection API methods some I int size39 I boolean add Object obj 39 returns true if Collection changes as a result of the add it always will for List may not for Set I boolean contains Object obj 39 I to see the rest study the API warning look at List not List a GUI class page 55 Iterator Interface suppose Collection of Programmer objects Iterator iter engineers iterator while lterhasNext Programmer 10 Programmerlternext pfeedquotplzzaquot I Note cast Programmer since Collection and Iterator manage anonymous objects I When collection has a natural ordering Iterator will respect it I Supports safe removeO of most recent next page 57 StringTokenizer I Like an Iterator for a String I Elements are white space delimited words stringTokenizer st new StrlngTokenlzer now is the time quot while sthasMoreTokens string word st nextToken I I Should implement Iterator interface hasNext next page 52 Map I Table lookup abstraction 7 void put Object key Object value 7 Object get Object key 7 can grow as needed 7 any Objects for key and value keys tested for equality with equals of course 7 API syntax independent of implementation HashMap TreeMap 7 Iterators for keys values key value pairs page 59 Conversions String lt gt Object I String 5 I am obj invokes obj tostring I 5 Stringvalueof0bject Obj ditto and overloaded for primitive types ehari hoolean char int long float double int Integervalueof String 5 r Integer is wrapper class for int Integer IntegerparseIntString 5 page on Equality reminder tesm pointer not contents for objects Object class implements blic boolean equals0bject Obj return this ob public int hashCode probable unique id String class overrides if gequals goodbye not 7 if goodbye equalsg ok too Strings hash as they should for deep copy override Object c1one field by field copy page 51 String matches and searches boolean equalsIgnozecasestring anotherstring in compazeToStrlng anotherstring boolean startswith5trlng prefix boolean endswith5trlng suffix boolean egionmatchesunt toffset string other t ooffset int len lnt indexofhnt ch int indexof5trlng str int indexo int fromlndex in 1astIndexof page l Methods ReturningConstructing New Strings concat5trlng str can also use eplacechar old char new Not in place substzinglnt beglnlndex ew string 139 substzinglnt beginindex int endlndex new string ocale locale ocale locale tim page 63 CkwsStringBuffer mutable size and content stringBuffer str new StringBufferquotWorldquot strinsert0 quotJello quot strappendquot1quot strsetCharAtO39H39 now quotHello Worldlquot now quotldlrow olleHquot string s strtostring strreverse page 64 public class File 0 Information about files not their contents 0 Constructors File5trlng path or string path string name or F e dir string name 0 Methods poolean existsOy isnieo isDizectozyo canxeado canwziteo long 1ength lastModifiedo poolean deleteo mkdizo mkdizso enameToFlle dest string get ameoy Getiazentoy getrathoy getabsoiuteaath 0 page 65 Useful System Constants final static portable Wlndows Uan Fllepathsepazatoz quot quot quot quot Fllesepazatoz quotv w SystemgetProperty quot11nese azatozquot quotnrquot quotn39 SystemgetProperty gets other properties too public static final FileDescriptor in public static final FileDescriptor out public static final FlleDescrlptor err page 65 Keyword finally Keyword final try 0 final class can t be extended final field can t be modified 75 0 final method can t be overrridden finauY I I code here runs whether or not catch runs public final class Integer public static final int MAX7VALUE 2147483647 Wm N252 Optimization HT 0 0 option used to direct compiler to 0 JustlnTime compiler Optimize 15 0 If present can speed things up 0 How does this work page 69 page 7 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 4 Bruce Char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use page Quiz on Tuesday April 13 I 30 minutes or less I Write a simple Java program with computation and io no threads I You should be able to do any kind of simple program you could write in Programming 11 or Data Structures in C but in Java I Be able to state information and answer simple questions about Java compilation classpaths packages I If you did the rst example assignment easily puggtzhfre should be no problems if you can express t Things to try in Java IWrite a program that uses inheritance interfaces Vectors file lO packages IStudy AWT and Java Swing to find out how to use the Java class libraries for GUI construction Our Java programming won t need in however Java facts and questions I How do you handle global variables in Java I Java has automatic garbage collection do new to allocate but never need to do delete I What implications does automatic go have for programming page A Forcing a deallocation of storage int bigiarray10000039 now we don t want to use the storage anymore bigiar ra arbage collector automatically deallocates storage from the heap Another Java fact and question I How do you do a linked list in Java page 6 Java procedures are mainly call by reference I This means that procedures can easily alter objecm passed to them as parameters Building your own exceptions I Class BmcesArgmenWegativeException extends Exception page 2 Programming with exceptions class Factnxial Public static m emuuum kt umm Exileesmqumznuleqalivellxceplinn otherexcepnons if 1kltm than new ExileesmgumznuleqaliveilxceplinntD 91 mm 1 and menu a program my Syslmnulpxinlh mum is Faclnxialmnmyuletnb p catchHxllcesmqmnuleqaliveilxceplinn 9p System exxpxinlln1e Myra continue Java lacks some C features I No templates But superclass is Object Could program a stack class With Objects and then cast into an object of another class I Exception primitive data types such as int oat are not subclasses of Obj ect However there are Wrapper classes Integer Double etc I No overloading of operators although function overloading is okay I No io operators ltlt gtgt I No general multiple inheritance page in No environment variables in Java not system independent I No such thing as environment variables as there are with CCH and Unix because this is not OS independent There s a system property setting mechanism that accesses properties declared in the command line invocation called SystemgetProperty read about it in the lava documentation page What does final mean I public final class FinalCircle extends GraphicCircle I When a class is declared with the final modifier it means that it cannot be extended I It s a way of declaring constanm for a class final int BUFFERSIZE 1039 page 12 Java threads 7 Use the builtin Thread class in Java 7 You need to supply the programming that the thread will follow in order to do multithreaded programming 7 There are two ways to get a new thread in Java Extend subclass the Thread class Provide arun method in the subclass Create aThread object incorporating an object that speci es the Thread s run metho page 13 One way to get a thread extend subclass the builtin Thread class in leAThradJam class Arhread extends Thread public AThrezdString name sup ernzme 39 void run Sysmmnutp rintJn My name is quot getNameO lnnletestiava aiass test pnniaa static naaa naintstaanell alas n l hxead a 7 new mhuadt md ll quotRead name aslazl H Thread Construction I Different Thread constructors accept combinations of arguments supplying 7 A Runnable object in which case Thread 5 tart invokes run ofthe supplied Runnable o ject 7 A String that serves as an identi er Not useful except for tracing and debugging 7 Thre adGroup in which the new Thread should be placed page is An alternative implement Runnable interface use another form of the Thread constructor ln nleAclass Jam class nclass anipienents Runnable pnriaa vnid xunH system nulpxinln1 ny name is e Theadmuxxenl39 nead netnane t t n in letestl java class Lest pantie acacia aaia mintstxinyU alas nclass anajeat new nciaasm I use allexnalive cunslxuclnx in quotRead class rnaeaa arnaeaa new Thxeadtanhject mud taant rnaeaa nane aThxeadJLale page 16 Extend inherit Thread versus implement Runnable I The implementing Rurmable technique allows you to extend another class as well as getting threads I Since Java does not have full multiple inheritance you can t do that with the first method page 17 Starting threads I Invoking is start method causes an instance of class Thread to initiate its run me o I A Thread terminates when is run method completes by either returning normally or throwing an unchecked exception I Threads are not restartable even a er they terminate I i sAlive returns true ifa thread has been started by not has not terminated page l2 Thread States and Scheduling I A lava thread can be in new runnable running blocked and dead states I The Threads class has methods that move the thread from one state to another page 19 Thread states I New state 7 a Thread newly created I Runnable 7 a er being started the Thread can be run It is put into the run queue ofThreads and Waits is turn to run Runnable does not mean running I Runnin 7 the thread is executing is code On a uniprocessor machine at most one thread can run at a time page 2 Threadprocess states start yield 1 e terminated 3 e suspended 2 7 running 4 runnable page 21 More thread states I Blocked 7 the thread is Waiting for something to appen It is Waiting for an io operation it is executing to complete It has been told to sleep for a speci ed period of time through the sleep method It has executed the WaitO method and will block until another thread executes a notifyO or notifyAllO method I It will return to runnable state a er sleeping notifying etc page 22 More thread states I Terminated 7 The nal state A er reaching this state the Thread can no longer execute 7 A thread can reach this state a er the run method is nished or by something executing its stopO method 7 Threads can kill themselves or a thread can kill another thread page 23 The run queue of runnable threads I The Java language speci cation does not specify oW Java is supposed to choose e ea to run if there are several runnable threads of equal priority I One possibility 7 pick a thread and run it until it completes or until it executes a method that causes it to move into a nonrunning state I Another possibility 7 time slicing pick a thread run it for a short period oftime Then ifit is not nished suspend it and pick another thread to run or the same perio o 39 mm The semantics of yield I public static void yield 7 Causes the currently executing thread object to temporarily pause and allow other threads to execute I Java Language Reference In some cases a large number ofthreads could be aiting on the currently running thread to finish executing before they can start executing To make the thread scheduler switch from the current running thread 8 E o s o a a a a a a a E I a a 39 a a a amp a 2 o a o must be at least one thread with an equal or higher priority than the current thread page 25 Java realities I Most implementations of lava typically use timeslicing In older lava versions on Solaris the default was to use green threads which meant that there was no timeslicing manytoone thread model I Currently Solaris uses native threads manytomany thread model page 25 Thread synchronization I twait blocks until tnotify method is called I tsuspend puts it into suspended state I tresurne makes it runnable again suspend and resume are deprecated methods do not use A deprecated method is one whose design has fallen out of favor and may be unsupported in Nefuture Java versions Thread synchronization con t I stopO is also a deprecated method avoid its use in your programming I Most ofthe time you should let a thread nish by having it conclude executing its runO method I stopO causes an untidy conclusion to a thread hich may disrupt correct operation of other threads which may continue to run a er the stopped thread page 22 More Thread methods I Thread currentThread returns a reference to the current Thread I Thread sleep long msecs causes the current thread to suspend for at least msecs milliseconds I Thread interrupt is the preferred method for stopping a thread not Thread stop page 29 Thread Priorities I With multiple threads one can assign priorities a number to each threa an 39 highest priority tsetPriorityint I In some versions ofSolaris multiple threads with the same priority have no timeslicing I The book provides a class library that implemenw time slicing on Solaris You import it and then do new Schedulertime slice amount I This course discusses techniques that avoid the use of priorities in establishing synchronization between threads page zu Why you should not try to achieve Priorities correctness in concurrency problems using priorities I Each Thread has a priority between ThreadMIN7PRIORITY and I A scheduler is generally biased to prefer running ThreadMAX7PRIORITY from 1 to 10 threads with higher priorities depends on IV M a Each new thread has the same Priority as the implementation but there is no ironclad thread that created it guarantee that a thread with a higher priority must I The initial thread associated with a main by run instead of that with a lower priority dafa t has Priority I There are only a small number of different I ThreadlIORM7PRIORITY 5 I I I I priorities If you have a problem with many getpngnty gem Current Thread Priority SEtP OHtY threads you will run out of distinct priorities to Sets Pnonty assign threads page 31 page 2 Java debugging with Concurrent programm1ng goals mult1threaded programs I Yoijb is to W te aprogram that will Work I See what book has to say about it 7 use correctly regardless ofwhether there 1s time 1 d d Shng or not prrnt statements mam y an urnp output The meadas Programming Should use of each thread 1nto a separate frle or at least synchronization methods such as semaphores or Wlth dISthtlve output wait and notifyO to make sure that a particular I jdb is a Java debugger that allows you to thread relinquishes execution if that is needed to StatStop individual threads fgggfg f8 AVOld StOPO SHSPendO I ESIddto control goncurient execgtton of I Priorities 7 o en used as a crutch the algorithm ea S to repro uce a Hg m a e Ugger39 may not scale up to more threads if you have more N 33 threads than priority levels page 24 Race conditions Problems with NNl race I What is a race condition I If two threads did this we could end up I When two threads or processes sharing memory with either N2 or Nl depending on W te and read Sim ta eOHSlY With the EffECt that whether their operations were interleaved or the work that one or the other is doing gets lost not I Example 7 NN1 e in assembly this is load value ofN irito register R ad one to register store value ofR back into memory location forN page 35 page 35 Other situations 0 A husband and wife work in different places At lunch they both go visit an ATM to withdraw money If they withdraw simultaneously what would a race condition do to their bank balance page 37 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 7 Bruce char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own use pagel Pre and post CS protocols I WantToEnterCS e Serves as a gatekeeper 7 only lets one thread through at a time While the rst thread through the gate is in the critical section all the other threads executing WantToEnterCS are prevented from leaving it the gate is closed I FinishedWithCS e Noti es the gatekeeper that the thread in the cs is done will now let another thread executing WantToEnterCS through page 2 Two aspects of the mutual exclusion problem I Implementing the pre and post protocols 7 Correct ironclad mutual exclusion at most one thread in a critical section at a time 7 Works with any number ofthreads 1 2 or more I Using the pre and postprotocols to correctly provide mutual exclusion where they are needed page Other requirements for a mutual exclusion algorithm I No deadlock waiting to get into CS I Avoidance of starvation in the absence of contention one thread trying never gets in page A Other requirements not always insisted upon I Avoidance of starvation in the presence of contention 7 Multiple threads trying to get into cs one thread never I No livelock threads take an excessive amount of time ghting through congestion to get in I Fairness no threads favored repeatedly if there is contention Software providing mutual exclusion I In the book s discussion of solutions to the mutual exclusion problem Hartley assumes 7 Standard loadstore register architecture 7 Multiply executing concurrent threads that share data 7 Single or rnultiple CPUs that may be identical or different in speeds 7 Access to shared variables can be interleaved iftwo time threads get into their critical sections in page 6 More assumptions 0 Threads do not halt or crash in their prepost protocols or in their critical sections but may halt or crash outside of critical sections Hardware support for mutual exclusion 0 Definition of an atomic instruction 7 a machine language instruction that is executed completely without being interruptible 7 no interleaving of other instructions from another thre d 7 no context switching 7 no hardware interrupts page 2 Software solutions for mutual exclusion attempt 1 7 Use busy waiting boolean lockFlag false WantT oEntercsint I thread 1 wants to enter whl1elockFlag busy wait loops until lockFlag is false hopefully other thread will set this false lodFlagtrue nishedInCSlntI lockFlag 7 false Page 7What s wrong with this Problem we can have a race condition 7 ThreadA luadluck agmtuR Comm switch from thradA to a 7 ThreadB luaalue Cumparewlue Sturetruetaluekn Entermumlsecnun kFlagrntu R it s false 2 7 Context swrteh from thread B back to A 7 Thread A cumpareRandwlue rtsnlsesupmeeea Sturetruetalueknag Enter mum seeuun 7 Su huth can be m entreal seetrun at sametrrne page in Attempt 2 7Use a turn variable int turn 0 is either 0 or 1 public void WannuEnmrcsunt i i1 ml i Threadcurrentrhreadoyieldo go from running back to run queue give someone else a chance public void finishedInCSGnt i mm 7 utheri this sets 1 to something other than i page What s the matter with this 0 Hint what happens if there s only one thread that wants to run 0 This is Starvation in the absence of contention page l2 Attempt 3 Use a lag class again class Flag public vulatile buulean value ralse In class that handlesmutual exclusiun private Flagu desireCS new Flagm anay uf rlags fur 0 K2 1 desireCSfI newrlago initialize with new flag ubjects public vnid wantTuEnmcsunt I while desireCSnLherI value Threzdcurren hrezd0yield0 busy mit desireCS lvalue true setynur flag public vnid rinishedrncsunt 1 desireCSfIvzlue raise unset flag page i What s wrong with this 0 Hint race condition 0 If both threads execute the while at the same time neither flag will yet be set so they will both proceed into the critical section So there s no mutual exclusion page 14 Attempt 4 0 Try fixing flags public Void waanoEmerCS m I desireCSIvalue true while des39 eCSotherI Value Threadcurreanhread0yield0 postprotocol FinishedWithCS same as r e o e public vuid finishedInCSGnt 1 desireCSfIvzlue raise unset flag page is Exercise 0 This doesn t work as a way of ensuring mutual exclusion 0 Describe a scenario where the code fails to work properly 0 Can you find more than one kind of scenario where the code fails page 16 Attempt 4 0 Try fixing flags public Void waanoEmerCS m I desireCSIvalue true while desireCSotherI Value hreadcurreanhread0yield0 postprotocol FinishedWithCS same as before public vuid finishedInCSGnt 1 desireCSfIvzlue raise unset flag page 17 Checklist 0 Does this have a starvation in the absence of contention problem 0 Does this have a mutual exclusion problem 0 Deadlock Starvation in the presence of contention Livelock page l2 What s wrong with this 0 Deadlock page 19 Deadlock problem with 4 0 Both threads set their ags at more or less the same time 0 Both threads enter the while loop and see that the other s flag is set They then busy wait forever page 2 Use of volatile setting for ag 0 Book says it s important in how this attempt enforces mutual exclusion Why page 21 Use of volatile setting for ag 0 Without the volatile setting both threads could set their ags but neither would see the other s flag set so both would enter the CS page 22 Attempt 5 public void wantToEnterCSint I desireCSIvalue true while desireCSotherI value 39 CSivalue false back off ThreadcurrentThread0yield0 desireCSivalue true public void finishedInCSint I desireCSIvalue false unset flag Ni What s wrong with this I Livelock both threads back offand try again in lockstep I Hartley claims that this livelock is unlikely certain to last forever due to differences in time slicing and clock speed So this would be considered almost correct but with an ef ciency defect in that the livelock will sometimes slow down entry into the CS page 24 Dekker s attempt public void wantToEnwrCS nt I preprotocol d s39 1v ue true while desireCSoLherIvalue ii turn 11 mke turns backing on desireCSIvalue false back on while turn 11 busy wait readcurrentT read0yield0 desireCSIvaluetrue nd ii end while public void linishedlncscint I postprotocol desire S e false turn othera pagezs What kinds of problems if any does Dekker s algorithm have with I Enforcement of mutual exclusion I Deadlocklivelock I Starvation iii the presence of contention I Starvation iii the absence of contention page 25 The semantics of yield I public static void yield 7 Causes the currently executing thread object to temporarily pause and allow other threads to execute I Java Language Reference In some cases a large number ofthreads could be waiting on the currently running thread to finish executing before they can start executing To make the thread scheduler switch from the current running thread low 0 ers to execute call the yield method on the current thread In order for yield to work there must be at least one t re with an equal or higher priority than the current thread page 27 Correctness I While it is suf cient to nd a scenario to prove that something doesn t Work I To prove that an algorithm is correct you must show that it Works under all possible scenarios I Usually the Way that this is done is to show that it is impossible for it to behave incorrectly I This involves insight using a combination of logic and programming language semantics page 22 Peterson s attempt mutual exclus1on for two threads public void wantToEnterCS nt I preprotocol desireCSIvalue true last other while desireCSoLherIvalue ampamp last otherl busy wait ThreadcurrentThread0yield0 public Void nishedInCS nt I postprotocol desireCSIvaluerslse page 29 Proof of correctness I Prove that the algorithm 7 enforces mutual exclusion correctly by showing that it is impossible for two threads to be in the critical section simultaneously 7 doesn t allow deadlock i e it s impossible 7 doesn t allow starvation in the presence of contention 7 doesn t allow starvation in the absence of contention I A separate proof for each point each done as a proof by contradiction page 3 Proof by contradiction 0 If you show that assuming p leads you to conclude something which you know to be false then you are forced to conclude that there are no circumstances when p is true 7 in other words p must be false all the time p 3 false 3 p page 31 Game plan for proof by contradiction I Here We show that threads following Peterson s algorithm and ending up With a Violation of ME must have impossible false resulw from their programming such as having a Variable being both 0 and 1 simultaneously I From this We conclude that We can t assume that threads following Peterson s algorithm end up Violating ME page 32 CS 361 Concurrent programming Drexel University Fall 2004 Lecture 15 Bruce Char and VeraZaychik All rights reserved by the author Permission is given to students enrolled in C8361 Fall 2004 to reproduce these notes for their own page Counting semaphores from binary 7 If We are given only binary semaphores as a built in operation We can build a counting semaphore class using that 7 The class has two integers value and Waiting Value represents the semaphore count and Waiting is the number ofthreads blocks on S in a down operation We also need a binary emaphore m s utex and a binary semaphore block ed to simulate threads blocking on S Counting semaphores from binary puhlu vurd shunt t P lmutex Th1 15 quotpalm Aquot nenernned 1n the text Plhlucked i else i vsine7 Vlmutex Are counting semaphores more powerful than binary semaphores To prove that they are equivalent 7 Suppose you are given a binary semaphore class Build a counting semaphore class using binary semaphores and prove that it Works correctly 7 Suppose you are given a counting semaphore class Build a binary semaphore class usin bin ary semaphores and prove that it Works correctly page 2 Counting semaphores from binary import Utrlrtres import Synchrunlzat class Countlng emaphure pervsee value pervsee 1m werer pervsee Ernseysen rennmnery extends Myohject t n2 aphure mutex new mnerysenephnreti prlvate mnerysenephnre block puhire cnunerngSenephnrerrnn gt e new mnerysenephnrem mnerytrne n t page A Counting semaphores from binary nn in t ETSSKL n re snug s n t it we Vlhlncked Th1 15 quotperne rquot nenernned 1n ehe text gt Vlmutex page 6 An alternative 7 We can combine value and Waiting into a single integer variable count Where the value of count is equal to the number ofup s that have been performed on S minus the number of doWn s Counting semaphores from binary an alternative impart utiiitiee impart Synchronization cioss Cnuntingsemaphnrei rmn inary extends Myohject private 39nt count 0 te Hinarysemaphnre mutex new Hinarysemaphn 1 rysemphnre blacked new 0 private uin Hinarys emphnr e public Countingenopnonernovninonvunt n count n page 2 Counting semaphores from binary an alternative public void downo P mutex 7 countquot if count lt 0 vmutex This is quotpoint Aquot mentioned in the text E blocked I else vmutex page Counting semaphores from binary an alternative public void up mute P cou H if count lt 0 vblocked I This is quotpoint aquot mentioned in the text v mutex page in The problem with this code I The problem With both of these is that if a context switch occurs at point A between the Vmutex and Pblocked code and if before the down thread resumes several threads do an up then some signals at point B in the up code V blocked are lost because the bin semaphores don t go beyond 1 This means that the doWn s on S Won t Work correctly page Fixing things public Countingempnonernovninonvunt n count n public void ulnwnO P mtex count if count lt 0 Vmutex Ph1mked Vmutex public void upo tax Fixing things We try to prevent the lost signals by moving the else in the down method to the up method since m 39s no released in up when Vblocked is done the effect is to force ablocked down operation to complete for each up d ne preventing the Vblocked signal from getting lost There is still undesirability ifthere are several threads blocked inside ofdown on the binary semaphore blocked then abunch ofup operations waking up the threads cannot be executed sequentially but must be strictly interleaved completing its Pblocked and its down operation Not so good because you have to do context switching in order to do the unblocking We can keep track ofthe number ofVblocked operations N iplicitly Fixing things class Countingsemaphozei zomsinazy extends Myobject private int count 0 p 39 Binazysemaphoze mutex new Binazysemaphoze1 private Binazysemaphoze blocked new Binazysemaphoze 0 private int wakeup new variable public Countingsemaphozei zomsinazyint n count n page 14 Fixing things public void downo Pmute wakeupee if wakeup gt o vblocked vnnitex public void upo Pmutex wakeup vblocked vnnitex page is Really xing things 7 We can avoid both the incorrectness and too muchcontext switching problems by adding one more binary semaphore that serializes execution ofthe down code so that at most nly one thread is at point A page 16 Really xing things import utilities import Synchrnnizatinn class CountinoSemapnorerrombinarv extends nvobject 39 ate int count 0 rivate binarysemapnore nmtex new binarvsemapnorea private binarysemapnore blocked 7 new binarvsemapnorem private binarysemapnore serial new binarvsemapnorea public Countingemapnorerrombinaryunt n count n page 17 Really xing things Vmutex Vserial public void upo P mtex aunt lt 0 Vh1mked Vmutex page 18 Monitors 0 A higher level of abstraction for synchronization 0 Chapter 5 page 19 Components of monitors I A monitor can be thought of as a class 7 service methods 7 datamembers global to all methods in the class 7 condition variables special datamembers with synchronization properties Monitor members share a lock If the monitor is locked when a thread calls one ofthe monitor s methods the thread blocks until the lock is released page 2 Condition variable like a semaphore Each cv has two operations notify like up on a semaphore and wait like down Think of them like signals to the read A thread that waits on a condition variab e temporarily leaves the monitor and blocks releasing the lock and joining the set ofthreads blocked on that condition variable The set is not a queue necessarily Each condition variable can have its own set of blockedt rea s in the same way that distinct semaphores have distinct set of blocked threads Then there are the threads waiting to enterthe monitorthat are blocked because it is in use page What notify signals do Each signal on a condition variable awakens one thread from the condition variables set of blocked threads not necessarily the first last or the one that blocked the longest If the set is empty the signal is not saved and has no effect unlike how counting semaphores work In some variants there is a notifyall which awakens all the threads that are in the set blocked on that condition variable page 22 Kinds of monitors signal and eXit A thread can wait on a condition variable Another thread can signal notify the waiting set but then it must immediatel exit possibly returning a result through the method The resumedsignaled thread gets priority over other threads trying to acquire the lock on the monitor Important point The thread that resumes from the wait finds the condition that led to the signal still true when it resumes execution inside the monitor Not true with other kinds of Pu prigionitors Signal and continue monitors In this d s 39 line the signaling thread does not have to leave the monitor after a signa on a condition variable Nor does the signaled thread have priority to proceed in the monitor over other hreads w ti 0 enter through a service method call ltjust gets woken up This can simplify the writing of applications but it an also complica e i gs since ere is no guarantee that the condition leading to the signal is still true when the signaledresumed thread 5 execution again u ermore there may be the starvation problem of methods using one the service me o s barging aheadquot 0 a pagesignaledresumed thread A problem with barging For example with a signaland continue monitor forthe bounded buffer problem multiple producers and consumers a producer that wants to deposit into a full bufferwaits on a condition variable for a signal from a consumer After getting such a signal it is possible for another producer to barge into the monitor and fill the just emptied slot page 25 Taking care with signal and continue monitors Since we no longer guarantee that the condition leading to the signal is still true when the signaled thread proceeds in the monitor we need to take the precaution of changing the if statement containing the wait rom If condition wait o Whilecondition wait Note that this is not busywaiting because there is not continuous execution only execution resumption after signaling pages Notifyall With signalandcontinue the signaling thread does not have to exit after it sends a signal so we can write code where it signals all waiting threads we d have to keep extra counters to know how many times to send a signal but that s not difficult to do So signaland continue allows broadcast signals page 27 What Java does 0 Java monitors use signal and continue Only one anonymous condition variable page 22 Bounded buffer using real Java class Huunded uffer designed fur a single pradneer thread and a single eansnner thread private pnhiie Huunded ufferint nunsiats ts lt 0 thrgw new if nuniSl 111ega1nrgdmsntaxeeptign numsigtslto s numsigts nulliS n s buffer new dguhlernumsigts System gut printan Huunded uffer alive nulnSlnts Bounded buffer using real Java pnhiie synchrnnized vnid depasitdanhie value while aunt numslnts try wait wait an this mnnitnr s eand var catch Interruptedllxceptinn e r y tenerrprintinuinterrnpted ant nf wait hu errputxn aide putIn putIn 1 ya numSlnts cnunt wake up a thread waiting an this mnnitnr s eand Var the eansnnsr sinee it night he waiting if eaunt es 1 nutifyO Systemnutprintln after depasit caunt e eaunt PutIn puma page in


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.