Concurrency lecture II

Multi-threaded programs:
- achieve speedup (utilizing multiple CPU cores, do CPU processing and I/O at the same time)

Challenges:
- execution of different interleave in arbitary manner (many lead to incorrect results)
- we need to synchronize among threads to control allowed interleaving.

Synchronization primitives:

* Mutual exclusion (locking)
pthread_mutex_init
pthread_mutex_lock 
pthread_mutex_unlock

Locks protect a critical section  (only one thread is allowed in a CS)
  precondition: invariant holds
  pthread_mutex_lock
  violate invariants
  restore invariants
  pthread_mutex_unlock
  postcondition: invariant holds

In practice, you (mentally) associates a lock with a (set of) shared variables

* Lock granularity

typedef struct {
   char *name;
   int val;
}account;

account *accounts[100];

void transfer(int x, int y, int amount)
{
	accounts[x]->val -= amount;
	acounts[y]->val += amount;
}

int sum(int x, int y)
{
    return accounts[x]->val+accounts[y]->val;
}

If no synchronization, what happens? see the following interleaving

Thread-0 (transfer $10 x to y)              thread-1 (transfer $10 from x to y)
----------------------------------------------------------------------------
read x=100          
                                              read x=100
write x=90             
                                              write x=90
read y=100
write y=110
                                              read y=110
                                              write y=120
-----------------------------------------------------------------------------------

Lack of proper synchronization has resulted in many disasters
Recently, Flexcoin, Poloniex two bitcoin exchanges that got shutdown because of synchronization bug:
In their own words:
 "The attacker successfully exploited a flaw in the code which allows transfers between flexcoin users. 
 By sending thousands of simultaneous requests, the attacker was able to "move" coins from one 
 user account to another until the sending account was overdrawn, before balances were updated."

The easy solution (one big lock):
pthread_mutex_t m;
//pthread_mutex_init(&m,NULL)
void transfer(int x, int y, int amount)
{
	pthread_mutex_lock(&m);
	accounts[x]->val -= amount;
	acounts[y]->val += amount;
	pthread_mutex_unlock(&m);
}

void sum(int x, int y)
{
	int s;
	pthread_mutex_lock(&m);
	s = accounts[x]->val + acounts[y]->val;
	pthread_mutex_unlock(&m);
}
The lock is associated with the entired array of accounts ---> coarse-grained
no concurrency

Fine-grained locking
typedef struct {
   char *name;
   int val;
   pthread_mutex_t m;
}account;

void transfer(...)
{ 
   pthread_mutex_lock(&accounts[x]->m);
   accounts[x]->val -= amount;
   pthread_mutex_unlock(&accounts[x]->m);

   pthread_mutex_lock(&accounts[y]->m);
   accounts[y]->val += amount;
   pthread_mutex_unlock(&accounts[y]->m);
}

int sum(..)
{
   int s = 0;
   pthread_mutex_lock(&accounts[x]->m);
   s += accounts[x]->val;
   pthread_mutex_unlock(&accounts[x]->m);

   pthread_mutex_lock(&accounts[y]->m);
   s += accounts[y]->val;
   pthread_mutex_unlock(&accounts[y]->m);
   return s;
}

Correct?
thread-0: read x=100 write x=90                         read y=100 write y=110

thread-1:                          read x=90 read y=100

void
transfer(int x, int y, int amount)
{
	pthread_mutex_lock(&accounts[x]->m);
	pthread_mutex_lock(&accounts[y]->m);
	accounts[x]->val -= amount;
	acounts[y]->val += amount;
	pthread_mutex_unlock(&accounts[x]->m);
	pthread_mutex_unlock(&accounts[y]->m);
}

Problem: deadlock
T0:transfer(X, Y, 10)
T1:transfer(Y, X, 20)

thread-0:                       thread-1
-------------------------------------------
acquired x's lock                   

                                acquired y's lock             
block waiting for y's lock
                                block waiting for x's lock
-------------------------------------------------

Solution: ensure locks are acquired in order
e.g. acquire locks in the order based on account numbers
void
transfer(int x, int y, int amount)
{
	if (x < y) {
		pthread_mutex_lock(&accounts[x]->m);
		pthread_mutex_lock(&accounts[y]->m);
	}else{
		pthread_mutex_lock(&accounts[y]->m);
		pthread_mutex_lock(&accounts[x]->m);
	}
	accounts[x]->val -= amount;
	acounts[y]->val += amount;
	pthread_mutex_unlock(&accounts[x]->m);
	pthread_mutex_unlock(&accounts[y]->m);
}

In general: deadlocks are much easier to debug than races
program halts at the moment when deadlocks happens.

* Scheduling shared resources

Locking is a simple kind of resource scheduling -- one thread at a time.
What about more complicated scheduling policy? 
- need a mechanism to block a thread until some condition is true

Conditional variables
pthread_cond_init(pthread_cond_t *c,..);
pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
- atomically unlock m and sleep until conditional variable is signalled
- when this function returns, m is locked.
pthread_cond_signal(pthread_cond_t *c);
- wake up one waiting thread
pthread_cond_broadcast(pthread_cond_t *c);
- wakes up all waiting threads

typedef struct {
	int *val; //can buffer one value
        pthread_mutex_t m;
}channel;

channel c;
void
chan_send(int *v) {
   pthread_mutex_lock(&c.m)
   if (c.val == NULL) {
 	c.val = v;
   }else{
        //wait
   }
   pthread_mutex_unlock(&c.m)
}

int *
chan_recv() {
   pthread_mutex_lock(&c.m)
   int *v = NULL;
   if (c.val) {
       v = c->val;
       c.val = NULL;
   }else {
       //wait
   }
   pthread_mutex_unlock(&c.m)
}


- explain that it's inefficient to use sleep(1) for waiting
- add pthread_cond_wait and signal

void
send(int *v) {
   pthread_mutex_lock(&c.m);
   while (c->val != NULL) 
       pthread_cond_wait(&c.c, &c.m);
   c.val = v;
   pthread_cond_unlock(&c.m);
}

int *
recv() {
   pthread_mutex_lock(&c.m);
   if (c.val) {
       int *v = c.val;
       c.val = NULL;
       pthread_cond_signal(&c.c);
       pthread_mutex_unlock(&c.m);
       return v;
   }else {
       //wait
   }
}


Notes on the above code:
The general pattern is:
T1:
lock(&m);
while (condition != true)
   cond_wait(&c,&m)
... do stuff...
unlock(&m)

T2:
lock(&m)
condition = true
cond_signal(&c)
unlock(&m)

Fist, always use cond_wait in this pattern
while (condition is not true) 
    pthread_cond_wait(&c, &m)

**Always** use "while" instead of "if".
T1:                               T2:                                  T3:
-----------------------------------------------------------------------------------
if (!cond) wait                                                           
                                  cond=true, signal
cond_wait returns
                                                                   set cond=false
continue but cond is false!
---------------------------------------------------------------------------------------
Another advantage of using 'while'--> use cond_broadcast instead of cond_signal would also be correct here.

Second, why the interface for cond_wait take a mutex argument and atomically unlocks it?
Suppose code is:
while (condition != true) {
    mutex_unlock()
    cond_wait()
}

Problem:
T1                                                 T2
--------------------------------------------------------------------------------------
mutex_unlock()                                                                 
                                             cond=true
                                             signal (signal is dropped because noone is waiting)
cond_wait
---------------------------------------------------------------------------------------

Third: code doing cond_signal needs to lock/unlock
suppose code is:
condition = true  //make condition true must be protected by locks
cond_signal

T1                                                 T2
---------------------------------------------------------------------------------------
lock 
while (cond!= true)                         
                                               cond=true
                                               cond_signal //signal is dropped
wait