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 16:06] – eechrisat-m42:lecture9 [2009/04/15 17:46] – eechris
Line 299: Line 299:
 <td> <td>
 <ul> <ul>
-<li>Associate a lock with withdraw method.</li> +<li class="level1">Associate a lock with withdraw method.</li> 
-<li>If Ryan or Monica wants to make a withdrawal, he/she must acquire the lock, and keep the key.</li> +<li class="level1">If Ryan or Monica wants to make a withdrawal, he/she must acquire the lock, and keep the key.</li> 
-<li>If Ryan has the key, only he can access the bank account.</li> +<li class="level1">If Ryan has the key, only he can access the bank account.</li> 
-<li>Lock prevents Monica accessing the bank account.</li>+<li class="level1">Lock prevents Monica accessing the bank account.</li>
 </ul> </ul>
 </td> </td>
 <td> <td>
 <ul> <ul>
-<li>When Ryan has finished the transaction, he unlocks the object and the key becomes available.</li> +<li class="level1">When Ryan has finished the transaction, he unlocks the object and the key becomes available.</li> 
-<li>Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal.</li> +<li class="level1">Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal.</li> 
-<li>Lock ensures that only one ''Thread'' has access to shared object at a time.</li>+<li class="level1">Lock ensures that only one ''Thread'' has access to shared object at a time.</li>
 </ul> </ul>
 </td> </td>
Line 319: Line 319:
 {{ :at-m42:lock.png?245 |a lock}} {{ :at-m42:lock.png?245 |a lock}}
 ===== Creating a Lock in Java ===== ===== Creating a Lock in Java =====
 +{{:at-m42:synchronized.png  |}}   
   * ''synchronized'' method runs as an atomic transaction and while running cannot be entered by another thread.   * ''synchronized'' method runs as an atomic transaction and while running cannot be entered by another thread.
   * Associated object holds the //lock//.   * Associated object holds the //lock//.
   * ''Thread'' holds the key.    * ''Thread'' holds the key. 
 +
 +[[http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy|Example 7]] {{  :at-m42:locks_and_threads.png?244|Locks and threads.}}
 +
 +----
 +
 +<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>
 +
  
 ===== Object Locks ===== ===== 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 +  * One lock per object for object's data members 
-Put the value of balance into variable i. +  * One lock per class for class' ''static'' data members 
-Balance is 2, so i is now 2. +  * Typically data is ''private'', only accessed through methods 
-Set the balance to the result of i + 1. +  * If a method is ''synchronized'', entering that method acquires the lock 
-Now balance is 3. +  * No other thread may call that method until the lock is released
-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 +===== How JVM Shares Resources =====
-And picks up exactly where it left off +
-Set the balance to the result of i + 1. +
-Now balance is 4 !!!!. +
-Make increment atomic +
-public synchronized void increment() {  int i = balance;    balance = i + 1; } +
-Thread A Runs for a While +
-Attempt 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 +
-Reenter increment method. Get the key.  +
-Put the value of balance into variable i. +
-Balance is 1, so i is now 1.+
  
-Thread B is selected to run +  * Only one ''synchronized'' method can be called at any time for a particular object  
-Attempt to enter increment method. +<code groovy> 
-The method is synchronized so we need to get the key. +synchronized f() { /* ... */ }  
-The key is not available +synchronized g(){ /* ... */ } 
-Thread B is "blocked" (waiting for key to become available). +</code> 
-Thread A Runs again +  * ''synchronized'' efficiency 
-Picking up where it left off +    * Each object has a lock 
-Set the balance to the result of i + 1. +    * Typical 6x method call overhead, theoretical minimum 4x
-Now balance is 2. +
-Return the key+
  
-Thread B is selected to run +===== The "Lost Update" problem ===== 
-Attempt to enter increment method. +  * Occurs when a two-step (or more-step) process is accessed by another thread before it completes. 
-The method is synchronized so we need to get the key. +  * E.g. 
-The key is available, get the key +<code groovy> 
-Put the value of balance into variable i. +def increment() {  
-Balance is 2, so i is now 2. +  i = balance; 
-Set the balance to the result of i + 1. +  balance = i + 1 
-Now balance is 3. +} 
-Return the key +</code> 
-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 +----
-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|}}+Increment ''balance'' by adding 1 to value **AT TIME IT WAS READ** rather than **CURRENT** value.
  
-===== Heading 1 =====+===== Thread A runs for a while =====
  
-<code groovy 1 | Example 1: Everything is an object (at-m42/Examples/lecture02/example1.groovy)> +{{ :at-m42:threada.png?171|Thread A}} 
-extern> http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture02/example1.groovy+ 
 +  * ''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> </code>
 +
 ---- ----
  
-Notes ...+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