락(lock)의 필요성과 구현

junto·2024년 3월 14일
Operating System
0

operating system

목록 보기
4/13
post-thumbnail

데이터 동기화 기법인 lock이 왜 필요하고, 소프트웨어 또는 하드웨어적으로 어떻게 구현할 수 있는지 살펴본다.

데이터 동기화 문제는 왜 발생하는가?

  • 2개의 쓰레드가 공유 데이터에 접근하는 상황을 생각해보자. counter 변수를 각각의 쓰레드가 100만번 증가시키는 것이다. counter가 0부터 시작한다고 했을 때 200만이 된다고 생각할 수 있다. 아래 코드는 c언어 pthread를 사용하는 간단한 코드다.
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

long long counter = 0;

void* countMillion(void* arg) {
    for (int i = 0; i < 1e6; ++i) {
        counter += 1;
    }
    return NULL;
}

int main() {
    pthread_t thread1, thread2;

    if (pthread_create(&thread1, NULL, &countMillion, NULL)) {
        fprintf(stderr, "Error creating thread\n");
        return 1;
    }
	
    if (pthread_create(&thread2, NULL, &countMillion, NULL)) { 
        fprintf(stderr, "Error creating thread\n");
        return 1;
    }

    if (pthread_join(thread1, NULL)) { // 1번 쓰레드를 기다린다.
        return 2;
    }
    if (pthread_join(thread2, NULL)) { // 2번 쓰레드를 기다린다.
        return 2;
    }

    printf("counter: %lld\n", counter);

    return 0; // 메인 쓰레드가 종료된다.
}
  • 하지만 직접 테스트해보면 2'000'000이 아니라 1'161'199가 나온다. 왜 이런 일이 발생할까?
  • counter = counter + 1; 을 어셈블리어로 확인해보자(gcc -S). 
// x86
mov 0x8121a2c, %eax
add $0x1, %eax
mov %eax, 0x8121a2c

// ARM
adrp	x9, _counter@PAGE
ldr	x8, [x9, _counter@PAGEOFF]
add	x8, x8, #1
str	x8, [x9, _counter@PAGEOFF]
b	LBB0_3
  • 위 어셈블리어에 대한 설명은 다음과 같다.
    1. move 명령어가 명시한 메모리 주소값을 읽어 들인 후 eax 레지스터에 넣는다.
    2. 1을 eax 레지스터의 값에 더하는 연산을 한다.
    3. eax에 저장되어 있는 값을 메모리 원래 주소에 다시 저장한다.
    • ARM 기계어도 메모리를 불러오고 값을 넣고 저장하는 위와 동일한 연산을 한다.

1, 2, 3 과정이 한 번에 진행되지 않고 중간에 문맥 교환(context switch)이 일어나기 때문에 값을 덮어쓰게 되는 문제가 발생하고 있다. 어떻게 해결할 수 있을까?

데이터 공유 문제 해결 방법

1. Sleep

  • 가장 간단한 방법은 1번 쓰레드가 생성된 후 100만 번 연산이 진행될 때까지 충분한 시간을 준다. 예를 들어, sleep()함수를 이용해 1번 쓰레드가 일을 다 할 때까지 메인 쓰레드를 잠들게 할 수 있다. 하지만 무분별한 sleep 사용은 전적으로 CPU 스케줄링에 의존하며 프로그램이 복잡해질수록 제어하기 어렵다. 대표적인 우연에 맡기는 프로그래밍(programming by conincidence)기법 중 하나로 지양해야 한다.

2. Lock

  • 프로그래머에게 CPU 스케줄링에 대한 최소한의 제어권을 제공해 주는 기법이다. 락은 공유 데이터에 접근하기 위해 사용되며 락을 얻은 쓰레드만 공유데이터에 배타적인 접근이 가능하다. 락을 얻지 못한 쓰레드는 공유데이터에 접근할 수 없기 때문에 데이터의 무결성이 보장된다.

3. Atomic(원자적) 연산

  • counter = counter + 1은 어셈블리어로 대략 3개의 명령어로 이루어지며, context switch로 인해 하나의 명령어로 동작하지 않기 때문에 이러한 문제가 발생한 것이다. 하드웨어가 위의 명령어를 한 번에 실행할 수 있게 원자성을 보장해 준다면 공유 데이터 접근 문제가 발생하지 않는다.

  • 구체적으로 보기 전에 먼저 병행성 주요 개념을 알아보자.

병행성 주요 개념

1. 임계 영역(Critical Section)

  • 변수나 자료구조 같은 공유자원에 접근하는 코드의 일부분을 말한다. 위의 예시에서 counter = counter + 1같이 공유 데이터를 다루는 부분을 임계 영역이라고 한다.

2. 경쟁 조건(Race Condtion)

  • 여러 쓰레드가 거의 동시에 임계 영역에 접근할 때 발생한다. Race Condition이 발생하면 데이터의 무결성을 보장하기 어렵다.

3. 비결정적(Indeterminate)

  • 프로그램은 경쟁 조건이 생긴다면 그 실행 결과가 각 쓰레드가 실행된 시점에 의존하므로 매번 프로그램의 실행 결과가 다르다. 이를 비결정적이라고 한다.

4. 상호 배제(Mutual Exclusion)

  • 하나의 쓰레드가 임계 영역 내의 코드를 실행 중일 때는 다른 쓰레드가 실행할 수 없도록 배타적인 접근을 가능하게 한다.

효율적인 락은 어떤 기능을 제공해야 할까? 운영체제가 제공할 수 있는 것과 하드웨어적인 지원을 생각해 보자.

락 구현

  • 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공해야 한다.
  • 락이 제대로 동작하려면 다음 조건을 만족해야 한다.
    1. 상호 배제
      • 락을 획득한 쓰레드는 배타적으로 공유자원을 이용할 수 있어야 한다.
    2. 공정성
      • 모든 쓰레드에 락을 획득할 수 있는 공정한 기회가 주어져야 한다.
    3. 성능
      • 다음의 락 사용 오버헤드를 평가한다.
        1. 하나의 쓰레드가 락을 회득하고 해제할 때 성능
        2. 여러 쓰레드가 단일 CPU에서 락을 가지고 경쟁할 때 성능
        3. 여러 쓰레드가 멀티 프로세서 환경에서 락을 가지고 경쟁할 때 성능

1. 인터럽트 제어

  • 불행하게도 단일 시스템에서도 공유 데이터 접근 문제가 일어난다. 커널 자원을 사용하고 있다가 인터럽트 발생으로 다른 작업을 처리하게 될 때 기존 커널 공유 데이터 무결성을 해치는 문제가 발생한다.
  • 이를 위해 초창기 단일 시스템에서는 상호 배제 지원을 위해 커널 모드에서 수행 중일 때 인터럽트를 비활성화하는 방법을 사용했다.
void lock() {
	DisableInterrupts();
}
void unlock() {
	EnableInterrupts();
}
  • 단순하지만, 여러 단점이 있다.
    • 먼저 쓰레드가 인터럽트를 활성/비활성화하는 특권 연산을 실행할 수 있도록 허가해야 한다. 보안상 굉장히 취약하다.
    • 멀티 프로세서에서는 적용할 수가 없다. 특정 프로세서에서 인터럽트 비활성화는 다른 프로세서에서 전혀 영향을 주지 않기 때문이다. 또한 중요한 인터럽트를 놓칠 수 있는 문제도 발생한다.

2. Perterson 알고리즘 (Software)

int flag[2];
int turn;

void init() {
	flag[0] = flag[1] = 0;
	turn = 0;
} 

void lock() {
	flag[self] = 1;
	turn = 1 - self;
	while ((flag[1-self] == 1 && (turn == 1 - self)) ;
}

void unlock() {
	flag[self] = 0;
}
  • 락을 구현한 것이다. 중간중간 CPU를 빼앗길 수 있다는 가정하에 코드가 복잡하다.
  • 하드웨어적으로 Atomic한 연산이 가능하면 위의 코드는 단순화될 수 있다.

3. TestAndSet (Hardware)

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
	mutex->flag = 0; // 0: 락이 사용 가능함, 1은 불가
}

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

void unlock(lock_t *mutex) {
	mutex->flag = 0;
}
  • 플래그를 이용한 락 구현 코드다. 아쉽게도 flag가 0이 된 순간 여러 쓰레드가 flag를 1로 만들 수 있는 경쟁 조건이 발생한다. 이를 위해선 하드웨어적인 지원이 필요하다. 아래는 c코드를 이용한 TestAndSet 동작이다.
int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // old_ptr 의 이전 값을 가져온다.
    *old_ptr = new;l    // old_ptr에 new 값을 저장한다.
    return old;
}

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
	mutex->flag = 0; // 0: 락이 사용 가능함, 1은 불가
}

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

void unlock(lock_t *mutex) {
	mutex->flag = 0;
}
  • 락의 값을 검사(test)하고 새로운 값으로 설정(set)하는 동작을 원자적 연산으로 만듦으로써 하나의 쓰레드만 락을 획득하게 한다.
    1. lock이 1이라면 이미 다른 스레드가 임계구역에 진입한 것이다. test_and_set 반환값이 1이되어 while 루프에서 기다린다.
    2. lock이 0이라면 락 변수를 true로 변경하고 그 이전 false값을 반환하여 while루프 탈출하여 임계구역에 진입한다.

4. CompareAndSwap (Hardware)

  • 메모리 위치, 예상값, 새로운 값을 인자로 받는다. 특정 메모리 값이 예상값과 일치하는지 확인하는 것이다. 
int CompareAndSwap(int *ptr, int expected, int new) {
	int actual = *ptr;
    if (actual == expected)
    	*ptr = new;
    return actual;
}
  • 실제 값이 기댓값과 다르다면 앞에 방식처럼 계속해서 비교할 수도 있겠지만(BusyWaiting) 그사이에 다른 작업을 수행할 수도 있다. 이름처럼 비교(compare)하고 교체(swap)할 수 있다. 이런 작업을 대기 없는 동기화(wait-free synchronization)라고 하며 CPU를 좀 더 효율적으로 사용할 수 있다.
  • TAS(TestAndSet)방식 보다 강력하지만, ABA 문제가 발생한다. 이는 다른 쓰레드가 특정 메모리 값을 A에서 B로 변경한 후 다시 A로 변경했을 때 데이터가 변경된 사실을 감지하지 못할 수 있다.

5. LoadLinked & Store-Condition (Hardware)

  • CAS의 ABA 문제를 극복하고, 더 일반적이고 안정적인 병행 연산을 제공한다.
int LoadLinked(int *ptr); {
	return *ptr;
}

int StoreConditional(int *ptr, int value) {
	if (no one has update *ptr since the LoadLinked to this address) {
    	*ptr = value;
        return 1;
    }
    else {
    	return 0;
    }
}
  • StoreConditional에서 ABA로 변경된 사실을 감지할 수 있다.
void lock(lock_t *lock) {
	while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))  ;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}
  • LoadLinked로 flag 값을 읽는다. 해당 값이 0이면 락이 해제된 상태로 StoreConditional로 flag 값을 1로 설정한다. 즉, flag값이 0이고 1로 설정했다면 락을 획득하여 임계 영역에 진입한다.
  • 일반적으로 뮤택스나 세마포어 사용하는 방식에 비해 성능상 이점을 제공한다.

6. Fetch-And-ADD (Hardware)

  • 원자적으로 특정 주소 예전 값을 반환하면서 값을 증가시킨다.
int FetchAndAdd(int *ptr) {
	int old = *ptr;
    *ptr = old + 1;
    return old;
}
  • 하나의 변수만을 사용하지만 티켓(ticker)과 차례(turn)조합으로 락을 만들 수 있다.
typedef struct __lock_t {
	int ticket;
    int turn;
} lock_t;

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

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

void unlock(lock_t *mutex) {
	FetchAndAdd(&lock->turn);
}
  • 하나의 쓰레드가 락 획득을 원하면 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다. 결과 값은 해당 쓰레드의 차례를 나타낸다. 전역 공유 변수인 lock->turn을 사용하여 어느 쓰레드의 차례인지 판단한다. 만약 한 쓰레드가 myturn == turn을 충족한다면 임계영역에 진입한다. 언락 동작은 차례 변수를 증가시켜 다음 쓰레드에게 임계 영역 진입 차례를 넘겨준다.

여전히 2가지 문제가 발생한다.
1. 다른 쓰레드가 조건을 만족시켜야 한다면 while문에서 조건이 만족되었는지 계속해서 검사해야 한다.(Busywaiting, Spinlock).
2. 마지막 티켓 락을 제외한 방식에서는 공평성을 보장하지 않으므로 CPU를 할당받기 어려운 쓰레드가 존재할 수 있다(Starvation).
이를 어떻게 해결할 수 있을까? TestAndSet을 기준으로 아래 두 가지 방법을 적용해본다.

1. 무조건 양보하기

void init() {
	flag = 0;
}

void lock() {
	while (TestAndSet(&flag, 1))
    	yield();
}

void unlock() {
	flag = 0;
}
  • 이 방식에서 운영체제는 자신이 할당받은 CPU 시간을 할당하고 다른 쓰레드가 실행될 수 있도록 하는 Yield() 시스템 콜을 지원해야 한다.
  • 단일 시스템에서 쓰레드가 2개가 있다면 위의 코드는 제법 합리적으로 동작한다. 많은 쓰레드(예를 들어 100개)가 락을 획득하기 위해 경쟁하는 상황을 살펴보자. 99개의 쓰레드가 락을 양보하는 일이 벌어진다. 물론 기존의 Busywaiting 방식 보다는 효율적이지만, 여전히 문맥 교환(Context Switch) 비용은 상당하다. 추가로 Starvation 문제도 여전히 남아있다.

2. 공회전(Spin) 대신 잠자기(Sleep)

  • 쓰레드를 명시적으로 제어할 수 있어야 한다. 먼저 락을 기다리는 쓰레드가 머물 수 있는 큐를 준비한다. 추가로 운영체제는 쓰레드가 락을 획득할 수 없다면, 큐에 자신을 추가하고 잠들 수 있는 park() 시스템 콜과 락을 획득할 수 있을 때 특정 쓰레드를 깨우는 unpark(threadId) 시스템 콜을 제공해주어야 한다. 
typedef struct __lock_t {
	int flag;
    int guard;
    queue_t *q;
}

void lock(lock_t *m) {
	while (TestAndSet(&m->guard, 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)) ;
    if (queue_empty(m->q))
    	m->flag = 0;
    else
    	unpark(queue_remove(m->q));
    m->guard = 0;
}
  • 위의 코드에서는 두 개의 락(guard, flag)가 사용된다. guard는 flag와 큐의 삽입과 삭제 동작을 스핀 락으로 보호하는 데 사용된다. Busywaiting을 완전히 배제하지는 못했지만 임계영역이 실행되기까지 기다리는 것이 아닌 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기에 합리적인 접근이다. flag는 임계영역을 하나의 쓰레드만 접근할 수 있도록 한다.
  • lock함수에서 flag 락을 획득할 수 없다면 현재 실행 중인 Thread Id를 큐에 넣고, guard 락을 해제한 후에 CPU를 양보한다. 만약 CPU를 양보(park)한 후에 guard 락을 해제한다면? guard락을 얻을 수 있는 쓰레드가 없게 된다.
  • 위의 코드에서 경쟁 조건이 발생하는 부분이 있다. 바로 park() 호출 직전이다. guard 락을 내려놓고, park()을 호출하기 직전에 락을 가진 쓰레드가 락을 해제했다면, park()를 호출한 쓰레드는 깨어 날 방법이 없다. 이를 위해 Solaris는 setpark() 시스템 콜을 제공하여 park()가 실제로 호출되기 직전에 unpark()이 호출된다면 park()는 잠을 자지 않고 바로 리턴된다.

헷갈렸던 점은 unpark을 수행한 뒤에 flag를 0으로 만드는 부분이 없다. 코드에서 제공되지 않았지만 대기 중인 쓰레드를 깨울 때 해당 쓰레드에게만 flag값을 0으로 알려주어야 한다. 그 이유는 해당 쓰레드가 깨어났다고 해서 guard락이 있는 게 아니기 때문이다. guard락 없이 flag값을 변경할 수는 없다.

Busywaiting vs Block/wakeup

  • critical section의 길이가 긴 경우 Block/wakeup 방식이 더 적당하다.
  • critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 Busywaiting 오버헤드보다 더 커질 수 있다.
  • 물론, 일반적으로 Block/wakeup 방식이 더 좋고 현대 운영체제가 채택하는 방법이다.

참고 자료

  • 2014 이화여대 반효경 운영체제 강의
  • 운영체제, 아주 쉬운 세 가지 이야기
profile
junto
꾸준하게
이전 포스트

CPU 스케줄링

다음 포스트

컨디션 변수와 세마포어

0개의 댓글