Locks

Locks : The Basic Idea

• Ensure that any critical section executes as if it were a single atomic instruction.

Add some code around the critical section

lock_t mutex; // some globally-allocated lock 'mutex'
...
lock(&mutex);
balance=balance+1;
unlock(&mutex);

• Lock variable holds the state of the lock
  • available (or unlocked or free)
    • No therad holds the lock
  • acquired (or locked or held)
    
    • Exactly one thread holds the lock presumably is in a critical section.

lock은 기본적으로 임계 지점에서 thread간의 충돌을 막기 위해 사용된다.

lock의 상태에는 available( unlocked, free) 그리고 acquired(locked or held)로 나뉜다.

---

The semantics of the lock()

lock()

• Try to acquire the lock
• If no other thread holds the lock, the thread will acquire the lock.
• Enter the critical section
  • This thread is said to be the owner of the lock.
• Other threads are prevented from entering the critical section while the first thread that holds the lock is in there.

lock()이 실행되었을 때 다른 thread가 lock을 hold하지 않는다면, lock을 acquire하고 critical sectioin으로 들어가겠다는 의미이다.

---

Pthread Locks - mutex

• The name that the POSIX library uses for a lock
  • Used to provide mutual exclusion between threads.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

Pthread_mutex_lock(&lock);
balance = balance + 1;
Pthread_mutex_unlock(&lock);

• We may be using different locks to protect different variables -> Increase concurrency (a more fine-grained approach)

---

Building A Lock

• Efficient locks provided mutual exclusion at low cost.
• Building a lock need some help from the hardware and the OS.

---

Evaluating locks - Basic criteria

• Mutual exclusion
  • Does the lock work, preventing multiple threads from entering a critical section?
• Fairness
  • Does each thread contending for the lock get a fair shot at acquiring it once it is free?(Starvation)
• Performance
  • The time overheads added by using the lock

Lock을 평가할 때는 3가지 기준이 있다.

Fairness가 의미하는 것은 특정 thread만이 lock이 되어 starvation 이 오지 않게 구현하라는 것을 의미한다.

---

Controlling Interrupts

• Disable Interrupts for critical sections
  • One of the earliest solutions used to provide mutual exclusion
  • Invented for single-processor systems

    void lock(){
    	DisableInterrupts();
    }
    
    void unlock(){
    	EnableInterrupts();
    }​

• Problem
  • Require too much trust in applications
    • Greedy( or malicious ) program could monopolize the processor.
  • Do not work on multiprocessor. 
  • Code that masks or unmasks interrupts be executed slowly by modern CPUs.

 

위 처럼 코드를 짜게 되면 문제점이 많다.

일단 코드를 전적으로 믿어야 한다. 만약 lock을 걸어 놓고 해당 thread를 block한다고 가정하면 interrupt를 사용할 수 없는 상태에서 thread_block()이 일어나므로 해당 프로그램은 영원히 sleep될 것이다.

---

Why hardware support needed?

• First attempt : Using a flag denoting whether the lock is held or not.

• typedef struct __lock_t {int flag; } lock_t;
  
  void init(lock_t *mutex){
  	// 0 -> lock is available, 1->held
      mutex->flag = 0;
  }
  
  void lock(lock_t *mutex){
  	while(mutex->flag==1) // TEST the flag
      	;	//spin-wait (do nothing)
      mutex->flag = 1; // now SET it !
  }
  
  void unlock(lock_t *mutex){
  	mutex_flag = 0;
  }

위는 flag를 이용하여 만약 flag==1이어서 접근 못하는 경우 while 문을 돌면서 기다렸다가 while이 flag!=1이면 자신이 flag를 1로 만들고 들어가는 식으로 구현하였는데 몇가지 문제가 발생한다.

 

• Problem 1 : No Mutual Exclusion (assume flag=0 to begin)

만약 위에 경우처럼 thread가 lock을 실행하고 flag를 1로 만들기 직전에 interrupt가 걸리는 경우가 계속 발생하면 여러 개의 thread가 임계 지점에 접근할 수 있게 된다.

• Problem 2 : Spin-waiting wates time waiting for another thread.

So, we need an atomic instruction supported by Hardware!

• test-and-set instruction, also known as atomic exchange

위와 같은 문제를 해결하기 위해서는 Hardware의 도움을 받아야한다.

---

Test And set(Atomic Exchange)

• An instruction to support the creation of simple locks

int TestAndSet(int *ptr, int new){
	int old = *ptr;
   	*ptr = new;
    return old;
}

• return(testing) old value pointed to by the ptr.
• Simultaneously update(setting) said value to new.
• This sequence of operations is perfomed atomically.

void lock(lock_t *lock){
	while(TestAndSet(&lock->flag, 1) == 1)
    	; // spin-wait
}

TestAndSet이라는 코드를 만들어서 lock()의 while문 안에 넣어주게 되면 flag만 해주었을 때의 문제를 해결 할 수 있다.

그 이유는 현재 lock의 상태와 while문을 돌지말지를 한줄로 해결했기 때문이다.

 

Note : To work correctly on a single processor, it requires a preemptive scheduler. (while문을 계속 돌기 때문에)

 

• Correctness : yes
  • The spin lock only allows a single thread to entry the critical section.
• Fairness : no
  • Spin locks don't provide any fairness guarantees. Starvation can occur.
  • Indeed, a thread spinning may spin forever. (preemptive scheduler가 없다면)
• Performance :
  • In the single CPU, performance overheads can be quire painful.(계속 while문을 돌아서 그런 것 같다)
  • If the number of threads roughly equals the number of CPUs, spin locks work reasonably well.

---

Compare-And-Swap (SPARC)

Test whether the value at the address(ptr) is equal to expected.

• If so, update the memory location pointed to by ptr with the new value.
• In either case, return the actual value at that memory location.

int CompareAndSwap(int *ptr, int expected, int new){
	int actual = *ptr;
    if (actual == expected)
    	*ptr = new;
    return actual;
}

 

---

Load-Linked and Store-Conditional(MIPS)

int LoadLinked(int *ptr){
	return *ptr;
}

int StoreConditional(int *ptr, int value){
	if( no one has updated *ptr since the LoadLinked to this address) {
    	*ptr = value;
        return 1; // success!
    } else {
    	return 0; // failed to update
    }
}

• The store-conditional only succeeds if no intermittent store to the address has taken place.
  • success : return 1 and update the value at ptr to value.
  • fail : the value at ptr is not updates and 0 is returned.

아무도 ptr의 값을 update하지 않았으면 return 1아니면 return 0.

void lock(lock_t *lock){
	while(1){
    	while(LoadLinked(&lock->flag)==1)
        	; //spin until it's zero
        if(StoreConditional(&lock->flag,1)==1)
        	return; // if set-it-to-1 was a success: all done
            		otherwise : try it all over again
    }
}

void unlock(lock_t *lock){
	lock->flag=0;
}

Using LL/SC To Build a Lock

void lock(lock_t *lock){
	while(LoadLinked(&lock->flag)||!StoreConditional(&lock->flag,1))
    	; //spin
}

A more concise form of the lock() using LL/SC

---

Fetch-And-Add

int FetchAndAdd(int *ptr){
	int old = *ptr;
    *ptr = old + 1;
    return old;
}

• Atomically increment a value while returning the old value at a particular address.

ptr 값을 0과 1로만이 아니라 증가하도록 구현한다.

---

Ticket Lock

typedef struct __lock_t{
	int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock){
	lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t *lock){
	int myturn = FetchAndAdd(&lock->ticket);
    while(lock->turn!=myturn)
    	; //spin
}

void unlock(lock_t *lock){
	FetchAndAdd(&lock->turn);
}

myturn = FetchAndAdd(&lock->ticket)에서 현재 ticket을 부여 받게 된다.

또, unlock을 하게되면 FetchAndAdd(&lock->turn)을 사용하여 lock->turn을 증가시키게 된다.

이렇게 구현을 하면 thread마다 고유의 ticket이 있으므로 ticket을 받은 순서대로 반드시 실행되게 된다. 따라서 fairness가 보장된다.

---

 So Much Spinning

• Hardware-based spin locks are simple and they work.
• In some cases, these solutions can be quite inefficient.
  • Any time a thread gets caught spinning, it wastes an entire time slice doing nothing but checking a value.

while문을 통해 check를 하게되면 해당 thread는 lock이 걸려 아무것도 안할 것이지만 자신이 호출된 time slice를 값을 체크하면서 모두 사용하게 된다. 이를 해결하기 위해서는 OS Support가 필요하다.

---

A Simple Approach : Just Yield

• When you are going to spin, give up the CPU to another thread.
  • OS system call moves the caller from the running state to the ready state.
  • The cost of a context switch can be substantial and the starvation problem still exist.

• void lock(){
  	while(TestAndSet(&flag,1)==1)
      	yield(); // give up the CPU
  }

그냥 lock이 걸려 있을 경우 yield (thread가 CPU를 포기)하는 방식으로 구현을 하면 while문을 돌지 않게 구현을 할 수 있으나, context switch에 많은 비용을 쓸 수도 있고, starvation problem이 해결되지 않는다.