ICCT Wiki

User Tools

Site Tools

Trace:
at-m42:lecture9

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
at-m42:lecture9 [2009/04/15 15:47] – eechrisat-m42:lecture9 [2009/04/15 17:46] – eechris
Line 255: Line 255:
  
 ===== The Demo ===== ===== The Demo =====
-{{  :at-m42:deposit.png?236|Making a deposit}} 
  
-  * Make one instance of Ryan and Monica job+[[http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob.groovy|Example 6]] {{  :at-m42:deposit.png?236|Making a deposit}}
  
-  def theJob = new RyanAndMonicaJob(); +  * Makes one instance of Ryan and Monica job 
- +  * Makes two threads with the same ''Runnable'' 
-  * Make two threads with the same Runnable +  * Name and starts the threads 
- +  * Watches the threads check the balance and attempt withdrawal
-  Thread one = new Thread(theJob); +
-  Thread two = new Thread(theJob); +
- +
-  * Name and start the threads +
- +
-  one.name = 'Ryan'; two.name = 'Monica' +
-  one.start(); two.start() +
- +
-  * Watch the threads check the balance and withdraw+
 <code groovy> <code groovy>
 if (account.balance >= amount) { if (account.balance >= amount) {
Line 281: Line 271:
 </code> </code>
  
-[[Example 6]]+
  
 ---- ----
Line 290: Line 280:
  
  
-Results +===== Results ===== 
-Ryan checks the balance, sees there's enough money, goes to sleep + 
-Monica comes in and checks the balance. See's there enough money (Ryan hasn't withdrawn it yet) but doesn't realise that Ryan is going to withdraw it. +  * Ryan checks the balance, sees there's enough money, goes to sleep 
-Monica falls asleep. +  * Monica comes in and checks the balance. See's there enough money (Ryan hasn't withdrawn it yet) but doesn't realise that Ryan is going to withdraw it. 
-Ryan wakes up and completes the withdrawal. +  * Monica falls asleep. 
-Monica wakes up and completes the withdrawal … but Ryan has already taken the money, and Monica goes overdrawn.+  * Ryan wakes up and completes the withdrawal. 
 +  * Monica wakes up and completes the withdrawal ... but Ryan has already taken the money, and Monica goes overdrawn. 
 + 
 +---- 
 Monica's check was invalid because Ryan was already making a withdrawal. We need a way to prevent Monica starting a withdrawal if Ryan is already making a withdrawal. Monica's check was invalid because Ryan was already making a withdrawal. We need a way to prevent Monica starting a withdrawal if Ryan is already making a withdrawal.
-Need a Lock! 
-Associate a lock with withdraw method. If Ryan or Monica wants to make a withdrawal, he/she must acquire the lock, and keep the key. 
-If Ryan has the key, only he can access the bank account. 
-Lock prevents Monica accessing the bank account. 
-When Ryan has finished the transaction, he unlocks the object and the key becomes available. 
-Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal. 
-Lock ensures that only one Thread has access to shared object at a time. 
-Creating a Lock in Java 
-Object Locks 
-One lock per object for object’s data members 
-One lock per class for class’ static data members 
-Typically data is private, only accessed through methods 
-If a method is synchronized, entering that method acquires the lock 
-No other thread may call that method until the lock is released 
-How Java Shares Resources 
-Only one synchronized method can be called at any time for a particular object synchronized void f() { /* ... */ } synchronized void g(){ /* ... */ } 
-synchronized efficiency 
-Each object has a lock 
-Typical 6x method call overhead, theoretical min 4x 
-Standard Java libraries use synchronized a lot, don’t provide you with alternatives 
-Synchronization efficiency much improved in Java 1.3 and 1.4 
-The "Lost Update" problem 
-Occurs when a two-step (or more-step) process is accessed by another thread before it completes. 
-E.g. 
- public void increment() { int i = balance;   balance = i + 1; } 
-Thread A Runs for a While 
-Put the value of balance into variable i. 
-Balance is 0, so i is now 0. 
-Set the balance to the result of i + 1. 
-Now balance is 1. 
-Put the value of balance into variable i. 
-Balance is 1, so i is now 1. 
-Set the balance to the result of i + 1. 
-Now balance is 2. 
  
-Thread B Runs for a While +===== Need a Lock! =====
-Put the value of balance into variable i. +
-Balance is 2, so i is now 2. +
-Set the balance to the result of i + 1. +
-Now balance is 3. +
-Put the value of balance into variable i. +
-Balance is 3, so i is now 3. +
-Thread A Runs again +
-Picking up where it left off +
-Put the value of balance into variable i. +
-Balance is 3, so i is now 3. +
-Set the balance to the result of i + 1. +
-Now balance is 4. +
-Put the value of balance into variable i. +
-Balance is 4, so i is now 4. +
-Set the balance to the result of i + 1. +
-Now balance is 5.+
  
-Thread B runs gain +<html> 
-And picks up exactly where it left off +<table> 
-Set the balance to the result of i + 1. +<tr> 
-Now balance is 4 !!!!. +<td> 
-Make increment atomic +<ul> 
-public synchronized void increment() {  int i = balance;    balance = i + 1; } +<li class="level1">Associate a lock with withdraw method.</li> 
-Thread A Runs for a While +<li class="level1">If Ryan or Monica wants to make a withdrawal, he/she must acquire the lock, and keep the key.</li> 
-Attempt to enter increment method. +<li class="level1">If Ryan has the key, only he can access the bank account.</li> 
-Synchronized code, so get the key for this object. +<li class="level1">Lock prevents Monica accessing the bank account.</li> 
-Put the value of balance into variable i. +</ul> 
-Balance is 0, so i is now 0. +</td> 
-Set the balance to the result of i + 1. +<td> 
-Now balance is 1. +<ul> 
-Return the key +<li class="level1">When Ryan has finished the transaction, he unlocks the object and the key becomes available.</li> 
-Reenter increment method. Get the key.  +<li class="level1">Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal.</li> 
-Put the value of balance into variable i. +<li class="level1">Lock ensures that only one ''Thread'' has access to shared object at a time.</li> 
-Balance is 1, so i is now 1.+</ul> 
 +</td> 
 +</tr> 
 +</table> 
 +</html>
  
-Thread B is selected to run 
-Attempt to enter increment method. 
-The method is synchronized so we need to get the key. 
-The key is not available 
-Thread B is "blocked" (waiting for key to become available). 
-Thread A Runs again 
-Picking up where it left off 
-Set the balance to the result of i + 1. 
-Now balance is 2. 
-Return the key 
  
-Thread B is selected to run +{{ :at-m42:lock.png?245 |a lock}} 
-Attempt to enter increment method. +===== Creating a Lock in Java ===== 
-The method is synchronized so we need to get the key. +{{:at-m42:synchronized.png  |}}    
-The key is available, get the key +  * ''synchronized'' method runs as an atomic transaction and while running cannot be entered by another thread. 
-Put the value of balance into variable i. +  * Associated object holds the //lock//. 
-Balance is 2, so i is now 2. +  * ''Thread'' holds the key. 
-Set the balance to the result of i + 1. +
-Now balance is 3. +
-Return the key +
-Synchronizing on other resources +
-Synchronizing on something other than the memory inside an object +
-Using non-synchronized objects +
-Best to wrap everything inside an object and guard it with the object’s own synchronized methods, but you can also: synchronized(syncObject) {   // This code can only be accessed       // by one thread at a time }+
  
-Blocking +[[http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy|Example 7]] {{  :at-m42:locks_and_threads.png?244|Locks and threads.}}
-Four states of a thread: +
-1. New: the thread object has been created but it hasn’t been started yet so it cannot run +
-2. Runnable: thread can be run, when the time-slicing mechanism has CPU cycles available +
-3. Dead: normally after thread returns from its run( ) +
-4. Blocked: the thread could be run but there’s something that prevent it. While a thread is in the blocked state the scheduler will simply skip over it and not give it any CPU time +
-Becoming Blocked +
-Thread is sleeping: sleep(milliseconds) +
-Thread is suspended: suspend( ). It will not become runnable again until the thread gets the resume( ) message +
-Thread is waiting with wait( ). It will not become runnable again until the thread gets the notify( ) or notifyAll( ) message +
-The thread is waiting for some IO to complete +
-The thread is trying to call a synchronized method on another object and that object’s lock is not available +
-Deadlock +
-A chain of threads waiting on each other, looping back to the beginning +
-No language support to prevent it +
-Tough to debug +
-To create a deadlock only need two threads and two objects +
-Thread deadlock +
-Thread deadlock scenario +
-Thread A enters synchronized method of object foo and gets the key. +
-Thread A goes to sleep +
-Thread deadlock scenario +
-Thread B enters synchronized method of object bar and gets the key. +
-Thread B tries to enter a synchronized method of object foo, but can't get that key (A has it). +
-B "blocks" waiting for foo's key to become available. +
-B keeps the bar key. +
-Thread deadlock scenario +
-Thread A wakes up and tries to enter a synchronized method on object bar., but can't get that key because B has it. +
-A "blocks" waiting for bar's key to become available. +
-Thread A can't run until it get's bar key that B is holding. +
-Thread B can't run until it gets the foo key that A is holding. +
-Deadlock! +
-Summary +
-Single-threaded programming: live by yourself, own everything, no contention for resources +
-Multithreading: suddenly you can have collisions and destroy information, get locked up over the use of resources +
-Multithreading makes Java complicated, but that’s not Java’s fault. Multithreading is hard +
-Lab Exercises +
-1. Inherit a class from Thread and override the run( ) method. Inside run( ), print a message, then call sleep( ). Repeat this 3 times, then return from run( ). Put a start-up message in the constructor and override finalize( ) to print a shut-down message. Make a separate thread class that calls System.gc( ) inside run( ), printing a message as it does so. Make several thread objects of both types and run them to see what happens. +
-2. Create two Thread classes, one with a run( ) that starts up, creates and passes its own handle to an object of the second thread class and then calls wait( ). The other classes’ run( ) should cause a notifyAll( ) in the first thread after some number of seconds have passed, so the first thread can print out a message.+
  
-{{:at-m42:deposit.png|}}+----
  
-===== Heading 1 =====+<code groovy l| Example 7: Using a lock to control access to a shared resource (at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy)> 
 +extern> http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy 
 +</code>
  
-<code groovy 1 | Example 1: Everything is an object (at-m42/Examples/lecture02/example1.groovy)> + 
-extern> http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture02/example1.groovy+===== Object Locks ===== 
 + 
 +  * One lock per object for object's data members 
 +  * One lock per class for class' ''static'' data members 
 +  * Typically data is ''private'', only accessed through methods 
 +  * If a method is ''synchronized'', entering that method acquires the lock 
 +  * No other thread may call that method until the lock is released 
 + 
 +===== How JVM Shares Resources ===== 
 + 
 +  * Only one ''synchronized'' method can be called at any time for a particular object  
 +<code groovy> 
 +synchronized f() { /* ... */ }  
 +synchronized g(){ /* ... */ }
 </code> </code>
 +  * ''synchronized'' efficiency
 +    * Each object has a lock
 +    * Typical 6x method call overhead, theoretical minimum 4x
 +
 +===== The "Lost Update" problem =====
 +  * Occurs when a two-step (or more-step) process is accessed by another thread before it completes.
 +  * E.g.
 +<code groovy>
 +def increment() { 
 +  i = balance;
 +  balance = i + 1
 +}
 +</code> 
 +
 ---- ----
  
-Notes ...+Increment ''balance'' by adding 1 to value **AT TIME IT WAS READ** rather than **CURRENT** value. 
 + 
 +===== Thread A runs for a while ===== 
 + 
 +{{ :at-m42:threada.png?171|Thread A}} 
 + 
 +  * ''Thread'' A enters ''increment'' method: 
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 0, so ''i'' is now 0. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 1. 
 +  * ''Thread'' A re-enters ''increment''  
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 1, so ''i'' is now 1. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 2. 
 + 
 +===== Thread B runs for a while ===== 
 + 
 +{{ :at-m42:threadb.png?171|Thread B}} 
 + 
 +  * ''Thread'' B enters ''increment'' method: 
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 2, so ''i'' is now 2. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 3. 
 +  * ''Thread'' B re-enters ''increment''  
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 3, so ''i'' is now 3. 
 +     
 +---- 
 + 
 +Scheduler now makes ''Thread'' B //runnable// (ready to run) rather than running. 
 +Note that this is before ''balance'' has been incremented.   
 +     
 +===== Thread A Runs again ====== 
 + 
 +{{ :at-m42:threada.png?171|Thread A}} 
 + 
 +Picking up where it left off: 
 +  * ''Thread'' A re-enters ''increment''  
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 3, so ''i'' is now 3. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 4. 
 +  * ''Thread'' A re-enters ''increment''  
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 4, so ''i'' is now 4. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 5. 
 + 
 +===== Thread B runs again ===== 
 + 
 +{{ :at-m42:threadb.png?171|Thread B}} 
 + 
 +And picks up //exactly// where it left off: 
 +  * Set the ''balance'' to the result of ''i + 1''. 
 +  * **But balance is //now// 4 !!!!.** 
 +   
 +---- 
 + 
 +''i'' had value 3 when ''Thread'' B was stopped. Value of ''3 + 1 = 4'' passed to ''balance''. Update done by A is completely overridden. Hence "Missing Update". A common problem in distributed systems e.g. database transactions. 
 + 
 +===== Make increment atomic ====== 
 +<code groovy> 
 +synchronized void increment() { 
 +  i = balance 
 +  balance = i + 1 
 +} 
 +</code> 
 + 
 +---- 
 + 
 +The assignment and increment code will run to end. 
 + 
 + 
 +===== Thread A Runs for a While ===== 
 +{{ :at-m42:threada-has-key.png?174|Thread A has the key}} 
 +{{ :at-m42:locked-object.png?230|object is locked}} 
 + 
 +  * ''Thread A'' attempts to enter ''increment'' method. 
 +    - ''synchronized'' code, so **get the key for this object**. 
 +    - put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 0, so ''i'' is now 0. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 1. 
 +    - **Return the key**. 
 +  * Thread A re-enters ''increment'' method. **Gets the key**.  
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - ''balance'' is 1, so ''i'' is now 1. 
 + 
 +===== Thread B is selected to run ===== 
 + 
 +{{ :at-m42:threadb.png?171|Thread B}} 
 +{{ :at-m42:locked-object.png?230|Locked object}} 
 + 
 +  * ''Thread'' B attempts to enter ''increment'' method. 
 +    - The method is ''synchronized'' so we need to get the key. 
 +    - The **key is not available**. 
 +    - ''Thread'' B is "//blocked//" (waiting for key to become available). 
 + 
 +===== Thread A Runs again ===== 
 + 
 +{{ :at-m42:threada.png?171|Thread A}} 
 +{{ :at-m42:key-available.png?236|Key is available}} 
 +  * Picking up where it left off 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 2. 
 +    - **Return the key** 
 + 
 +===== Thread B is selected to run ===== 
 + 
 +{{ :at-m42:threadb.png?171|Thread B}} 
 +{{ :at-m42:key-available.png?236|Key is available}} 
 + 
 +  * ''Thread B'' attempts to enter ''increment'' method. 
 +    - The method is ''synchronized'' so we need to get the key. 
 +    - The **key is available, get the key** 
 +    - Put the value of ''balance'' into variable ''i''. 
 +    - Balance is 2, so ''i'' is now 2. 
 +    - Set the ''balance'' to the result of ''i + 1''. 
 +    - Now ''balance'' is 3. 
 +    - **Return the key** 
 +    
 + 
 +===== Synchronizing on other resources ===== 
 +  * Synchronizing on something other than the memory inside an object 
 +  * Using non-''synchronized'' objects 
 +  * Best to wrap everything inside an object and guard it with the object's own ''synchronized'' methods, but you can also: <code groovy> 
 +synchronized(syncObject) { 
 +     // This code can only be accessed 
 +    // by one thread at a time 
 + } 
 +</code> 
 + 
 +===== Blocking ===== 
 + 
 +Four states of a thread: 
 +  - //New//: the thread object has been created but it hasn’t been started yet so it cannot run 
 +  - //Runnable//: thread can be run, when the time-slicing mechanism has CPU cycles available 
 +  - //Dead//: normally after thread returns from its ''run'' method 
 +  - //Blocked//: the thread could be run but there’s something that prevent it. While a thread is in the blocked state the scheduler will simply skip over it and not give it any CPU time 
 +===== Becoming Blocked ===== 
 + 
 +  * Thread is //sleeping//: ''sleep(milliseconds)''. 
 +  * Thread is //suspended//: ''suspend( )''. It will not become runnable again until the thread gets the ''resume( )'' message. 
 +  * Thread is //waiting// with ''wait( )''. It will not become //runnable// again until the thread gets the ''notify( )'' or ''notifyAll( )'' message. 
 +  * The thread is waiting for some I/O to complete. 
 +  * The thread is trying to call a ''synchronized'' method on another object and that object's lock is not available. 
 + 
 +===== Deadlock ===== 
 + 
 +  * A chain of threads waiting on each other, looping back to the beginning 
 +  * No language support to prevent it 
 +  * Tough to debug 
 +  * To create a deadlock only need two threads and two objects 
 + 
 +===== Thread deadlock ===== 
 + 
 +{{:at-m42:deadlock1.png?768 |Deadlock}}
  
-===== Heading 2 =====+===== Thread deadlock scenario =====
  
-  * [[#Sub head 1]] +{{:at-m42:deadlock2.png?344 | Deadlock 2.}}
-  * [[#Sub head 2]]+
  
 +  * ''Thread'' A enters ''synchronized'' method of object ''foo'' and gets the key.
 +  * ''Thread'' A goes to sleep
  
-===== Summary of this Lecture ==== +===== Thread deadlock scenario =====
-  +
-The ....+
  
 +{{:at-m42:deadlock3.png?455 |}}
  
-  * [[#Heading 1]] +  * ''Thread'' B enters ''synchronized'' method of object ''bar'' and gets the key. 
-  * [[#Heading 2]] +  * ''Thread'' B tries to enter a ''synchronized'' method of object ''foo'', but can't get that key (A has it). 
-  * [[#heading 3]]+  * B "blocks" waiting for ''foo'''s key to become available. 
 +  * B keeps the ''bar'' key.
  
-===== Lab Exercises =====+===== Thread deadlock scenario ===== 
 +{{:at-m42:deadlock4.png?455 |Deadlock1}} 
 +  * ''Thread'' A wakes up and tries to enter a ''synchronized'' method on object ''bar'', but can't get **that** key because B has it. 
 +  * A "blocks" waiting for ''bar'''s key to become available. 
 +  * ''Thread'' A can't run until it gets ''bar'' key that B is holding. 
 +  * Thread B can't run until it gets the ''foo'' key that A is holding. 
 +  * **Deadlock!**
  
-  * [[eg-m42:labs:lab1|Lab 1]] exercises 1-7.+===== Summary ===== 
 +  * Single-threaded programming: live by yourself, own everything, no contention for resources 
 +  * Multi-threading: suddenly you can have collisions and destroy information, get locked up over the use of resources 
 +  * Multi-threading makes programming on the Java Platform complicated. 
 +  * Groovy multithreading easier because of the use of the closure. 
 +  * **Multi-threading is hard**!
  
 ---- ----
at-m42/lecture9.txt · Last modified: 2011/01/14 12:45 by 127.0.0.1