Concurrency

CS2112

 2019/11/07 

Concurrency and Parallelism

Concurrency: multiple threads (java level, can be executed by one core or multiple core)
parallelism: multiple cores (hardware level. can execute one thread or multiple thread)

import java.lang.Thread;

class Thread{
    /** starts a new thread executing run() */
    void start();
    
    /** Effect: anything; but default does nothing*/
    void run();
}

run() 里面就是写的这个thread到底应该干什么

Threads Interference

Best approach: most objects owned by 1 thread

Read-Only sharing ok

Read/Write sharing | Write/Write sharing dangerous

class Account {
  int balance;
  void withdraw(int n) {
   int b = balance - n; // R1
   balance = b;         // W1
  }
  void deposit(int n) {
   int b = balance + n; // R2
   balance = b;         // W2
  }
}

e.g. initial balance: $100, T1 executes witdraw(50), T2 executes deposit(50)

(R1, W1, R2, W2) or (R2, W2, R1, W1), the final balance is indeed $100.
(R1, R2, W2, W1) destroys $50 -> $50
(R2, R1, W1, W2) creates $50 -> $150

We therefore want deposit, withdraw method to be (or at least act to be) atomic (indivisible), as if this sentence cannot be influenced by other threads (reading and writing are happening simultaneously) .

Mutex

(mutual exclusion locks)

Threads can acquire them and release them. At most one thread can hold a mutex at a time. While a mutex is being held by a thread, all other threads that try to acquire it will be blocked until it is released, at which point just one waiting thread will manage to acquire it.

every write and read to a shared mutable variable, mutex must be held

/** Effect: blocks current thread until mutex is held by another thread
			then acquires mutex */
acquire();

/** Effect: release mutex */
release();

synchronized(Object o){
    //acquire o's mutex
    ... // do some operations
    //release o's mutex
}

Take deposit & withdraw as an example:

void withdraw(int n) {
   //do something
   synchronized(this) {
      //acquire o's mutex
      balance -= n;
      //release o's mutex
   }
   //do something else
}

Because the pattern of wrapping entire method bodies in synchronized(this) is so common, Java has syntactic sugar for it:

1
2
3

synchronized void withdraw(int n) {
   balance -= n;
}

Whenever mutex is not held, that variable guarded by the mutex will change unpredictably and the invariant will not hold

as long as we called synchronized someMethodName() or synchronized(this). Everything in this object/class this will be held mutex (?). So we want to write small methods and small classes. As mentioned previously:

Best approach: most objects owned by 1 thread

Conclusion

avoid unnecessary concurrency: slows down the program
limit sharing of mutable state: we don’t have to care about concurrency if its immutable(read only)
guard all accesses to shared mutable state with mutexes: in case of thread interference

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2019-11-07-Concurrency/

Publish date：November 7th 2019, 12:00:00 am

Update date：June 9th 2022, 3:13:34 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

Next Post

Synchronization
Previous Post

Designing and documenting interfaces and implementations

CATALOG

1. Concurrency and Parallelism
2. Threads Interference
3. Mutex
4. Conclusion