Lock의 구현

락: 상호배제를 위한 API

이걸 어떻게 구현할 것이냐?.. 실제로는 하드웨어와 OS의 협업

 

1. 인터럽트로

2. 소프트웨어만 only approach

3. 소프트웨어가 하드웨어와 협업

 

락의 평가 방법

1. 정확성 : 상호 배제가 보장되는가

2. 공정성 : 기아 상태에 빠지는 스레드가 없는가

3. 성능 : 락, 언락에 의한 오버헤드나 낭비가 없는가

 

락 사이즈 이슈. 여러 공유 자원이 있을 때

Coarse-grained lock : 하나의 락으로 보호

- 장점: 심플

- 단점: 병행성이 별로

Fine-grained lock : 각각을 보호하는 락

- 장점: 병행성 굿

- 단점: 복잡

---

실제 락의 구현

1) Disable Interrupt

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

문맥 교환이 발생하지 않으면 문제가 안됨

근데 스케줄링은 타이머 인터럽트에 의해 발생 -> 인터럽트를 끄면 해결

 

장점: 단순

단점:

- 오랫동안 디스에이블하면 문제 발생. 타이머 인터럽트가 너무 오래 꺼지면 주기적인 작업들이 안될 수 있음

- 시스템 오용, 남용 가능. 독점 같은

- 코어 자체가 병렬적인 경우 -> 멀티플 프로세스가 되면 이걸로 해결이 안됨

* 1코어에서 오용되지 않는 경우 OS 내부에서만 사용하는 경우가 남아있음

---

2) Test-and-Set, 소프트웨어적인 방법

typedef struct __lock_t ( int flag; ) lock_t;

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

void lock(lock_t *mutex) {
	while( mutex->flag == 1 )
		;
	mutex->flag = 1;
}

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

flag를 두고 1이면 락 중이라 파악하고 스핀(비지 웨이팅), 0이면 락

 

문제: 애초에 안정확함

스레드 1, 2가 있다고 할 때 1번에서 flag 1로 바꾸기 직전에 2번 스레드로 넘어가면 락이 안됨

=> 락 API가 원자성이 보장이 안됨 => 상호 배제가 보장이 안됨

스핀이라 성능도 별로.. 웨이팅하면서 CPU를 안놔줌

 

굉장히 많은 시도가 있었고, 일부는 성공한게 있긴 함

 

장점: 순수 소프트웨어 솔루션이라 하드웨어 도움이 필요 없음

단점:

1. 이해하기 쉽지 않음

2. 하드웨어의 지원을 받는 것과 비교하면 성능이 별로

3. 성공한 것도 특수한 경우고, 최근에 만들어진 멀티코어 시스템, 제네럴한 시스템에서도 정확하지 않음

---

3) 하드웨어의 도움: atomoc operation

- a) Test-and-Set instruction (atomic exchange)

int TestAndSet(int *old_ptr, int new_num) {
	int old_num = *old_ptr;
	*old_ptr = new_num;
	return old_num;
}

이 명령은 CPU 내부에서 원자적으로 실행이 됨

 

typedef struct __lock_t {
	int flag;
} lock_t;

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

void lock(lock_t *lock) {
	while( TestAndSet(&lock, 1) == 1 )
		;
}

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

while 문을 돌면서 락이 안풀렸으면 대기, 풀리면 다시 락하고 종료

 

1. 정확한가?

- 상호보장 됨

- 한 크리티컬 섹션에 하나의 스레드만 들어감

 

2. 공정한가

- 아니다

- 우선순위가 낮은 스레드는 먼저 들어와서 기다려도 계속 밀릴 수 있다 -> 티켓 락 방식이 있음

3. 성능

- 싱글 CPU : 스핀락이라 슬립 락보다 CPU 낭비가 있음

- 멀티 CPU : 락이 곧 해제된다고 하면 별로 나쁘진 않음

 

- b) Compare and Swap Instruction 

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

예상 값과 실제 값이 동일하면 새로운 값으로 교체

테스트 앤 셋과 거의 비슷한데 테스트 앤 셋은 일단 바꾸고 이거는 조건문 처리

 

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

원래 값이 1이면 락이었다는 거니 스핀

 

- c) Load-Linked and Store-Conditional

MIPS, ARM같은 RISC 아키텍처에서 지원

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

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

포인터에 다른 스레드가 접근한 적이 있으면 락하지 못하도록 하는 방법

 

void lock(lock_t *lock) {
	while(1) {
	while( LoadLinked(&lock->flag) == 1 )
		;
    	if( StoreConditional(&lock->flag) == 1 )
    		return;
    }
}

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

이중반복문,

일단 로드링크드로 락이 걸려있는지 확인하고,

스토어컨디셔널로 플래그가 건드려진 적 없으면 락 (원자성)

건드려졌으면 다시 바깥 while 루프를  타게 될 것

 

- d) Fetch-and-Add = 티켓 락

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

원자적으로 1 더하는 연산

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)
		;
}

void unlock(lock_t *lock) {
	lock->turn = lock->turn + 1;
}

락에 티켓과 락 변수를 둠

 

락: 티켓을 증가시키고 이전 값을 리턴하여 myturn에 저장

=> 부여받은 myturn이 현재 lock 진행중인 turn과 다르면 스핀

 

언락: 턴을 1 증가 시킴 => myturn이 해당하는 작업이 실행될 것

=> 번호표 시스템, 티켓 락이라고도 함

 

장점: 먼저 기다리던 잡이 턴이 작기에 나중에 온 애들보다 먼저 실행되는 것이 보장

기존의 테스트 앤 셋, 컴페어 앤 스왑, 로드 링크드 앤 스토어 컨디셔널 => 순서랄 게 없음 => 기아 상태(starvation)의 가능성

=> 프로그레스 보장, 페어니스 보장

---

락 메커니즘

 

Spin lock

- 비지 웨이팅

- 플래그가 바뀌었는지 계속 체크 (while)

- 심플

- CPU 낭비

 

Sleep lock

- 선점됨(preemptive). CPU를 반납하고 웨이팅

- 락을 할 때 이미 락이 사용 중이면 CPU를 반납하고 웨이트 큐에서 대기

- 문맥 교환을 해야하고 웨이트 큐 관리를 해야해서 더 복잡함

- CPU를 더 효율적으로 사용 가능

 

 

Sleep Lock의 구현

락이 반납되는 평균 대기 시간을 줄일 수 있음

문제는 두개

1. 어디서 슬립할 거냐 => 웨이트 큐

2. 언제 일어나냐 => OS 서포트

 

예) Sloaris의 park(), unpark()

typedef struct __lock_t {
	int flag;
	int guard;
	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;
		m->guard = 0;
	} else {
		queue_add(m->q, gettid());
		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;
	}
}

* park, unpark는 솔라리스에서 쓰는 스레드 관련 API

 

guard를 추가로 사용 => 플래그를 위한 락 변수

가드에 테스트 앤 셋 => 일단 guard는 스핀을 해야 함

플래그가 0이면 수정 가능, 1이면 웨이트 큐에 넣고 슬립, 누군가 언락하면 깨어남

 

언락도 가드에 대해 테스트 앤 셋

큐가 비었으면 플래그를 0으로 바꿔주고,

안비었으면 큐에서 기다리던 잡을 꺼내기

 

슬립 락은 OS와 언어의 협업이 필요