Locking

Deadlocks

Deadlocks Deadlocks happen when two or more tasks permanently block each other by each having a lock or resource the other tasks are trying to lock.

Causes All of the four conditions have to be met for deadlocks:

Mutual Exclusion: there must exist at least a resource that is meant to be accessed only once at a time
Hold and Wait: a thread is holding a lock and tries to acquire another
No Preemption: a lock can’t be forcibly taken away after a thread acquires it
Circular Wait: A circular chain of two or more processes, each waiting for a resource held by the next process in the chain.

To break deadlocking, try to invalidate any of the conditions above. Usually the “No Preemption” rule cannot be broken but the other 3 are possible to be breached.

An example is

 
void func1(){
	lock(mutex1)
	lock(mutex2)
	//do something
	sleep(1000) //ms
	unlock(mutex2)
	unlock(mutex1)
}
 
void func2(){
	lock(mutex2)
	lock(mutex1)
	//do something
	sleep(1000) //ms
	unlock(mutex1)
	unlock(mutex2)
}
 
int main(){
	thread_create(thread1, func1)
	thread_create(thread2, func2)
	thread_exit(NULL)
}
 
/*
in this program if thread1 and thread2 proceed to their repsective 2nd line they will have to wait for the lock that is held by each other. This is causing a dead lock.
 
To fix it, we ensure the order of locking is consistent across functions to run. We break the Hold and Wait condition here.
*/
 
 
void func1(){
	lock(mutex1)
	lock(mutex2)
	//do something
	sleep(1000) //ms
	unlock(mutex2)
	unlock(mutex1)
}
 
void func2(){
	lock(mutex1)
	lock(mutex2)
	//do something else
	sleep(1000) //ms
	unlock(mutex2)
	unlock(mutex1)
}
 
int main(){
	thread_create(thread1, func1)
	thread_create(thread2, func2)
	thread_exit(NULL)
}

LiveLocks

Definition A livelock is a situation in concurrent programming where two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work. Unlike a deadlock, where processes are stuck and unable to proceed, in a livelock, processes are actively running but unable to make progress.

Chracteristics:

Active State Changes: Processes are actively executing and changing state.
Lack of Progress: Despite activity, no useful work is being accomplished.
Mutual Response: Each process is responding to the action of another process.
Repetitive Behavior: The same sequence of state changes occurs over and over.

DeadlocksVsLivelocks

Aspect	Livelock	Deadlock
Process State	Active, changing	Stuck, unchanging
Resource Usage	May be releasing and re-acquiring	Holding and waiting
System Response	System appears busy	System appears frozen
Detection	Often harder to detect	Easier to detect

Starvation

Starvation Starvation happens when a greedy thread occupies access to resources in critical sections for a very long time. For example, there could lie a huge amount of work in Critical Section and a thread greedily requests the lock right after it releases it for multiple times. This causes other threads to wait in the queue without making any progress for very long time.

Spin Lock

SpinLock A spin lock is the type of locks that uses. the busy-wait method. Other threads will keep themselves in a loop checking whether the lock is available when there is a thread holding it. What sets this kind apart is those threads in the wait queue do not patiently wait. They are aggressive in terms of being actively acquiring the lock.

The problem with this lock is it is not efficient. Threads are waiting a ton of CPU cycles and power just by keeping asking whether the lock is available when the lock is apparently being held. Therefore, to make best use of the lock, the critical section has to be short to mitigate the busy-wait problem.

Read-Write Lock

A read-write lock is a lock that enables reading and writing data with synchronization mechanism. It is used in scenarios where writes to data happens far less than reads to it.

It is designed to ensure the efficiency of reading while writing is kept in mind. Here is its one of its implementations.

typedef struct { 
	int nreader; 
	lock_t guard; 
	lock_t lock;
} rwlock_t;
 
void write_lock(rwlock_t *l) (
  lock(&l->lock);
}
 
void write_unlock(rwlock_t *l) (
  unlock(&l->lock);
}
 
void read_lock(rwlock_t *l) ( 
	lock(&l->guard);  
	++nreader;
	  
	//first reader
	if (nreader == 1) { 
		lock(&l->lock);
	}
	
	unlock(&l->guard);
}
 
void read_unlock(rwlock_t *l) ( 
	lock(&l->guard);  
	--nreader;  
	if (nreader == 0) { 
		//last reader
	    unlock(&l->lock);
	}
	unlock(&l->guard);
}

The guard in read_lock and read_unlock is to make sure the number of readers is synced between threads. In other words, no data race happens between readers.

Lock-type-wise, only one type of threads may get the lock. It can either be a reader or a writer. The lock acts like a mutex between these two kinds.

Within the readers, only one reader can hold the guard lock at a time so no data race is possible. It does not have to worry about the write lock either since the lock lock is held by the first reader.

📖 StudyHub

Explorer