ICCT Wiki

User Tools

Site Tools

Trace: • home • lecture13 • external_links • lecture9
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
at-m42:lecture9 [2009/04/15 15:55] – eechrisat-m42:lecture9 [2011/01/14 12:45] (current) – external edit 127.0.0.1
Line 294: Line 294:
 ===== Need a Lock! ===== ===== 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. +<html> 
-If Ryan has the key, only he can access the bank account. +<table> 
-Lock prevents Monica accessing the bank account. +<tr> 
-When Ryan has finished the transaction, he unlocks the object and the key becomes available. +<td> 
-Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal. +<ul> 
-Lock ensures that only one Thread has access to shared object at a time. +<li class="level1">Associate a lock with withdraw method.</li> 
-Creating a Lock in Java +<li class="level1">If Ryan or Monica wants to make a withdrawal, he/she must acquire the lock, and keep the key.</li> 
-Object Locks +<li class="level1">If Ryan has the key, only he can access the bank account.</li> 
-One lock per object for object’s data members +<li class="level1">Lock prevents Monica accessing the bank account.</li> 
-One lock per class for class’ static data members +</ul> 
-Typically data is private, only accessed through methods +</td> 
-If a method is synchronized, entering that method acquires the lock +<td> 
-No other thread may call that method until the lock is released +<ul> 
-How Java Shares Resources +<li class="level1">When Ryan has finished the transaction, he unlocks the object and the key becomes available.</li> 
-Only one synchronized method can be called at any time for a particular object synchronized void f() { /* ... */ } synchronized void g(){ /* ... */ } +<li class="level1">Monica can now take the key and lock the bank account to prevent Ryan making a withdrawal.</li> 
-synchronized efficiency +<li class="level1">Lock ensures that only one ''Thread'' has access to shared object at a time.</li> 
-Each object has a lock +</ul> 
-Typical 6x method call overhead, theoretical min 4x +</td> 
-Standard Java libraries use synchronized a lot, don’t provide you with alternatives +</tr> 
-Synchronization efficiency much improved in Java 1.3 and 1.4 +</table> 
-The "Lost Update" problem +</html>
-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 
-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 +{{ :at-m42:lock.png?245 |a lock}} 
-And picks up exactly where it left off +===== Creating a Lock in Java ===== 
-Set the balance to the result of i + 1. +{{:at-m42:synchronized.png  |}}    
-Now balance is 4 !!!!. +  * ''synchronized'' method runs as an atomic transaction and while running cannot be entered by another thread. 
-Make increment atomic +  * Associated object holds the //lock//. 
-public synchronized void increment() {  int i = balance;    balance = i + 1; } +  * ''Thread'' holds the key. 
-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 +[[http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy|Example 7]] {{  :at-m42:locks_and_threads.png?244|Locks and threads.}}
-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 +----
-Attempt 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: synchronized(syncObject) {   // This code can only be accessed       // by one thread at a time }+
  
-Blocking +<code groovy l| Example 7: Using a lock to control access to a shared resource (at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy)> 
-Four states of a thread: +extern> http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture09/ryanAndMonicaJob2.groovy 
-1. New: the thread object has been created but it hasn’t been started yet so it cannot run +</code>
-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 =====+===== Object Locks =====
  
-<code groovy 1 | Example 1: Everything is an object (at-m42/Examples/lecture02/example1.groovy)> +  * One lock per object for object's data members 
-extern> http://www.cpjobling.org.uk/~eechris/at-m42/Examples/lecture02/example1.groovy+  * 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.1239810940.txt.gz · Last modified: 2011/01/14 12:26 (external edit)