[ OS ] Locks_slides

1. Evaluating locks

critical sectiond에 여러 스레드기 들어가지 않도록 조심해야한다. lock이 풀리면 모든 스레드가 그것을 얻을 공평한 기회를 얻어야한다. 즉 굶는 스레스다 있으면 안된다. 또, lock으로 인해 over head가 일어나서도 안된다.

 

이 방법은  lock 하면 interrupt를 막고 unlock 하면 interrupt를 받아드리는 방법이다. 이 방법은 단점이 많다.

- interrupt를 막고 받고 하려면 권한이 있어야한다

- 멀티 프로세스 환경에서는 통하지 않는다. (interrupt)

2. Spin locks

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) // 누가 들어있음
			; // spin-wait (do nothing) 
	mutex->flag = 1; // flag 값을 1로 바꾸며 lock 상태가됨
} 

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

이 방법은 lock_t 라는 flag 값만을 갖고있는 구조체를 선언한 뒤 이 값을 통해서 lock상태인지 아닌지를 판단하는 것이다. lock 할 때는 flag 값이 1인지 확인하고, 만약 1이라면 다른 스레드가 unlock 할 때 까지 즉, flag 값이 0이 될때까지 spin-wait 한다. unlock 할 때에는 flag 값을 1로 바꾼다.

하지만 이런방식을 사용하면 다음과 같은 race condiotion이 일어날수있다.

위 상황을 보면 T1이 lock을 호출하고 falg 값으 0임을 확인을 한다. flag를 1로 바꾸려는 그 순간 context switch가 일어나 T2 로 전환되게 한다. T2는 lock을 호출하고 아직 바뀌기 전인 flag값(0)을 확인하고 lock을 걸기위해 flag 값을 1로 바꾸고 다시 context switch가 일어난다. 이미 T2에서 flag 값은 1로 바겼지만 T1 입장에서는 아직 falg 값이 0인것임으로 flag 값을 1로 바꾸게된다. 

이렇게 되면 T1과 T2 모두 mutex 상태가 된다. 

또한, 이 방법은 spin-wait하는 동안 시간을 너무 낭비하고 성능이 저하된다.

 

NO MUTEX, NO FAIR

 

2.1 Test-and-Set

 

int TestAndSet(int *old_ptr, int new) { 
	int old = *old_ptr; // old 값을 기록
	*old_ptr = new; // old자리에 new 값 넣기
	return old; // old 값 리턴
}

spin lock은 위와같은 Test-and-Set과 함께 사용할 수 있다. 

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *lock) { 
	lock->flag = 0; 
} 
void lock(lock_t *lock) { 
	while (TestAndSet(&lock->flag, 1) == 1); //falg 1로 바꾸고 원래 falg 값 리턴
    // 원래 falg 값이 1이었다는건 다른사람이 사용중이라는 것 -> whlie 문
    // 원래 0 이었어야 while문 나옴
}

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

하지만 이도 문제점이 있다. 

- 공평하지 않다 (누가 진입에 성공하고 실패하는지 몰라, 굶은 스레스가 생길 수 있음)

- 단일 CPU일 경우 오버헤드가 크다.

 

MUTEX, NO FAIR

 

2.2 Compare-and-swap

 

이 방법은 Test-and-Set 와 매우 흡사하다.

int CompareAndSwap(int *ptr, int expected, int new) { // falg, 기대값, 새로운값
	int actual = *ptr;  // 현재 값 기록
	if (actual == expected)  // 현재값이 기대값과 같으면
		*ptr = new;  // 새로운값 등록
	return actual;   //기대값 리턴
}

 

 

void lock(lock_t *lock) { 
	while (CompareAndSwap(&lock->flag, 0, 1) == 1); 
}

만약 falg 값이 0(기대값) 이라면 1(new)로 바꾸고, 0이 아니라면 0을 return 하여 while에 머물게된다.

하지만 이도 위와같은 문제를 겪는다.

 

MUTEX, NO FAIR

 

2.3 Ticket locks

 

이 방법은 번호표의 개념과 비슷하게 생각하면 된다.

int FetchAndAdd(int *ptr) { 
	int old = *ptr; 
	*ptr = old + 1; 
	return old; 
}  // 들어온 메모리에 1을 더해주고 원래의 값 리턴

Fetch and Add 함수는 atimic한 함수이다.

따라서 race condition 을 막을 수 있다.

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);  // 번호랑 현재순서랑 같지 않다면 while
}

void unlock(lock_t *lock) {
	lock->turn = lock->turn + 1;  // 한 애가 나올 때 turn ++
}

 

MUTEX,  FAIR

 

but 성능 문제..!

 

spinning 문제 해결해야함

 

2.3 yield()

 

아직 성능문제가 시급하다. 이 함수 cpu 다른 일을 하도록 해주는 함수이다.

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

 

4. Locks with Queues

 

공정성과 mutex 이 두가지는 어떻게 해결을 해도 성능문제를 해결하기는 힘들다.

이 때 OS가 도와줘야한다

 

In Solaris

park(): 호출한 스래드를 재운다

unpark(threadID): PID 를 통해 특정 스레드를 깨운다. (다른 스레스에서 해줘야함)

 

 In Linux 

futex_wait(address, expected): 주소의 값이 예상과 같으면 재움 

futex_wake(address): 대기중인 스레스하나를 깨움

 

typedef struct __lock_t {
	int flag; // 들어오면 1 없으면 0
	int guard; // flag와 queue를 보호하기 위한 방패
	queue_t *q;  // 실패한 애들이 잠드는 큐
} lock_t;

void lock_init(lock_t *m) {  초기화
	m->flag = 0;  
	m->guard = 0;
	queue_init(m->q);
}

void lock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1); // 여기를 탈출했다는 것은 가드 값을 얻었다는 것
	if (m->flag == 0) { // 비어있다면
		m->flag = 1; // lock is acquired
		m->guard = 0;
	} else {  // 비어있지 않다면
		queue_add(m->q, gettid());  // tid를 큐에 넣기
        setpark(); // 이 함수 다음에 unpark()이 호출된다면 다음에 오는 park() 실행 안하고 return
		m->guard = 0;
		park(); // 잠들기 
	}
}

void unlock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1);   // 가드값 쟁취
	if (queue_empty(m->q)) //큐가 비어있다면
		m->flag = 0; 
	else
		unpark(queue_remove(m->q)); // 큐에 자고있는 애 깨워주고 
	m->guard = 0;
}