[embedded system software/10주차] 이론

해당 글은 건국대학교 진현욱 교수님의 임베디드 시스템 소프트웨어 수업 내용을 정리한 글입니다. 

 

#include <stdio.h>
#include <pthread.h>

// 공유 자원: 모든 스레드가 접근 가능
static volatile int counter = 0; 

void *mythread(void *arg) {
    int i;
    printf("%s: begin\n", (char *) arg);
    
    // 루프 횟수가 클수록 Race Condition 발생 가능성이 높음
    for (i = 0; i < 1e7; i++) { 
        // 이 부분이 Race Condition이 발생하는 지점 (Critical Section)
        counter = counter + 1; 
    }
    
    printf("%s: done\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin (counter = %d)\n", counter);

    // 두 개의 스레드 생성
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");

    // 각 스레드가 종료될 때까지 대기
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);

    // 이론상으로는 20,000,000이 되어야 하지만, 실제로는 더 작은 값이 나옴
    printf("main: done with both (counter = %d)\n", counter);
    
    return 0;
}

이 코드는 counter 라는 shared data를 통해 race condition이 발생하는 예시를 보여주고 있다. 

 

1e7이라는 for 문 안에 있는 변수가 커지면 커질수록 race condition 이 발생할 가능성이 높아진다. 

 

race condition이 발생하는 부분은 정확히 counter = counter + 1; 이라는 부분인데 코드 한줄로 보이겠지만 사실 어셈블리어로 변환해보면 총 3줄이 나온다.

100 mov 0x8049alc, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

만약 Thread 1에서 105까지 일어난 상황인데 그 때 Context switch가 발생해 Thread2가 들어온다면 +1 하나가 무시가 되는 결과가 발생할 수 있는 것이다. 

 

POSIX Mutex

그래서 이런 나뉘면 안 되는 작업을 하나로 묶기 위해 Mutex를 사용한다.

Initialization

static

• pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

Dynamic

• int rc = pthread_mutex_init(&lock, NULL)

 

이런식으로 초기화를 할 수 있고

 

int pthread_mutex_lock(pthread_mutex_t *m)

int pthread_mutex_unlock(pthread_mutex_t *m)

 

mutex_lock과 unlock을 걸어주면서 하나의 쓰레드만 진입하라고 할 수 있는 것이다.

 

그러면 이러한 뮤텍스의 내부 동작은 어떤 것들로 구현되어 있을까?

• Atomic operation
  • Test-and-set
  • Compare-and-swap
• Process scheduling

이것들을 살펴보도록 하자~

Kernel-Level Synchronization

multi core system들은 이미 embedded system 쪽에서도 많이 사용되고 있다. 

우리는 process context와 interrupt context 사이에서도 동기화 기법을 적용할 줄 알아야 한다.

 

Mutex는 spin-lock 같은 busy-waiting방식보다 critical sections을 보호하는데 더 적합하다. cpu 자원도 덜쓰기 때문에

하지만 interrupt handler 안에는 sleep 방식이기 때문에 들어갈 수가 없어서 그 때에는 spinlock을 쓰도록하자.

그럼 이제 앞에서본 user-level 말고 kernel-level synchronization도 보도록 하자.

 

Mutex

• DEFINE_MUTEX() or mutext_init()
  
  • 초기화 기법
• mutex_lock()
  
  • lock
• mutex_unlock()
  • unlock

(세마포어 없어짐)

 

이제 다양한 상황들에 대해서 알아보도록 하자. 

 

Case 1

CPU 1개에 nonpreemptible kernel을 가지고 있을 때의 상황이다. CPU 1개는 무조건 하던일을 마친 다음에 그 다음일을 하게 되서 locking이 필요없는 경우이다. kernel mode 안에서 실행되고 있느 프로세스는 절대 interrupted 받을 수 없다.

Case2

case 1과 비교하면 Interrupt Handler가 추가되고 나머지 조건은 동일하다. 그러면 Process가 돌 때 interrupt만 막으면 된다는 의미 이다. 

즉, Process Context 간에는 서로 문제가 없고 오직 Interrupts만 disable 시키면 된다는 의미

local_irq_save() 
local_irq_restore()

즉 interrupt를 disable시킬 수 있는 이 2개의 메서드만 이용하면 된다. 

 

주의 사항

근데 interrupt handler에서는 spinlock을 써야만 한데 만약 process context에서도 spinlock을 쓴다면 데드락이 발생할 수도 있다. 

process A에서 shared data에 접근하기위해 spinlock을 쓴 상황에서 그때 Interrupt가 불린다면 우선순위가 더 높기 때문에 preem시키면서 들어온다. 하지만 Lock이 이미 process A가 걸어놨기 때문에 Interrupt handler가 이미 cpu 자원을 뺏겨서 데드락이 발생할 수 도 있는 것이다. 

 

Case 3

위의 상황에서 일단 core가 1개인 것도 같지만 문제는 이제 kernel 이 preemptible kernel이라는 것이다. 

위와 마찬가지로 Interrupt를 disable해주는 것과 Process context간의 context switching을 막아야함

spin_lock_irqsave() 
spin_unlock_irqrestore()

그래서 Interrupt disable 과 spinlock을 한꺼번에 해줄 수 있는 위 메서드를 이용한다.

 

또 다른 방법으로는 Interrupt disable + mutex 를 사용하는 것도 또 하나의 방법이 될 수도 있겠다.

 

Case 4

이제는 위 상황에서 core가 Multi 인 상황이다.

 

여기에서는 주의해야할 것이 interrupt 를 disable 시킨다는 것은 그 local CPU 에서만 막는다는 것이다. -> 즉 다른 코어는 아직 못막음

 

Process context 에서는 

spin_lock_irqsave() 
spin_unlock_irqrestore()

이것들을 사용해서 막아주면 된다.  하지만 이 상황은 Process A가 돌고 있는 코어에서만 interrupt를 diasable해준다는 의미임

문제는 다른 코어에서는 아직 interrupt handler가 아직 발생 가능성이 있다.

 

그래서 동시에 Interrupt context에서 막아줘야하는데 뮤텍스를 사용할 수 없기 때문에

spin_lock()
spin_unlock()

를 사용해서 또 막아야 하는 것이다.(Multi core 상황이라서 써야함)

 

일단 Interrupt handler가 발생했다면 그 Process B는 shared Data에 들어가지 않았다고 가정해야함

왜냐하면 Process B가 만약 들어갔었다면 Process context가 spin_lock_irqsave()로 interrupt를 disable 했을 거기 때문에

그래서 다른 코어에서 돌고 있는 Process context와의 동기화만 해결해주면 되는 것인데 그걸 interrupt handler안에서 spin_lock을 쓰면서 해결한 것임

 

하지만 case2에서 말했던 주의사항은 둘다 spin_lock을 쓰면 deadlock이 걸릴 수도 있다고 하지 않았나요? 라는 질문에는

그 Process A에는 다른 코어를 쓰기 때문에 언젠가는 벗어날 수 있어서 interrupt handler는 잠시 기다릴 뿐이다.

 

그러면 Mutex는 쓰면 안되나요? -> interrupt disable+mutex 는 sleep waiting이기 때문에 불가능하다.

Scalability

core 개수가 들면 위 처럼 성능이 증가하길 원했겠지만 실제 서비스에서는 동기화의 비효율성 때문에 그래프처럼 성능이 내려간다.

Throughtput 도 동기화 때문에 낮아지고 CPU utilization은 busy waiting 때문에 비효율적으로 사용한다. real-time(실시간성)도 보장하기 어렵다.

그래서 해결책은 다음과 같다.

 

• Atomic Operations: 락 없이 하드웨어 수준에서 연산하여 오버헤드 제거.
• Reader-Writer Locks: 읽기 작업은 공유를 허용하여 병렬성 증대.
• RCU (Read-Copy Update): 읽기 작업에 락을 아예 없애버려 멀티코어 환경에서 최고의 성능을 냄.

 

Atomic Operations

더이상 쪼개질 수 없는 연산을 의미한다. 예를 들어 count ++은 어셈블리 명령어로 3단계로 쪼개지지만 atomic operation은 이 3단계를 한 번에 실행됨을 하드웨어 수준에서 보장하는 것이다. 

 

실제 활용 사례로는 다음과 같다.

 

• Bumping Counters: 웹 서버의 방문자 수나 패킷 수 등을 셀 때 사용.
• Bit Positions: 플래그 정보를 담은 특정 비트 하나만 안전하게 끄거나 켤 때 유용.
• Lock-free Data Structures: 락을 전혀 사용하지 않고도 안전하게 동작하는 큐(Queue)나 리스트를 만들 때 기초가 됨.

 

매우 가벼운 작업에 최적화가 되어 있고 하드웨어가 직접 연산의 순서를 제어하므로 lock없이도 동기화가 가능하다. -> 오버헤드 감소

Reader-Writer Lock

reader 가 대부분일 상황에서 매우 유용한 락이다. 

 

원리는 읽기는 다 같이 쓰기는 혼자서 하게 하는 것인데, Multiple reader threads들이 동시에 critical region안으로 들어가는 것이 허락되는 것이다. RW lock 사용시 여러 명의 reader가 동시에 작업을 할 수 있어 병렬성이 올라가 처리량이 오른다.

 

• 데이터 타입: rwlock_t
• 초기화: RW_LOCK_UNLOCKED 또는 rwlock_init()
• 읽기 락: read_lock(), read_unlock()
• 쓰기 락: write_lock(), write_unlock()

 

만약 인터럽트 핸들러 내에서도 이 자원에 접근해야 한다면, 이전 스핀락처럼 인터럽트를 제어하는 버전(IRQ variant)을 사용해야 한다.

• read_lock_irqsave() / read_unlock_irqrestore()
• write_lock_irqsave() / write_unlock_irqrestore()

하지만 Writer starvation 이라는 문제가 발생할 수도 있다. 읽기 작업이 끊임없이 들어온다면 writer thread가 무한정 기다려야할 수도 있다는 것인데, 이래서 RCU라는 것이 이 문제를 해결해준다. 

RCU

read-copy Update 의 약자로 락을 안쓰면서 읽기 작업의 성능을 극한으로 올린 기법이다.

RCU는 읽기 작업에 락을 아예 쓰지 않는다. 따라서 writer thread가 무엇을 하든 latency 없이 데이터를 읽을 수 있다.

 

Writer thread

데이터를 직접 수정하는 대신, 다음의 단계를 거친다.

1. 복제 (Copy): 수정하고 싶은 원본 데이터의 복사본을 만든다.
2. 수정 (Update): 복사본의 내용만 수정한다.
3. 교체 (Publish): 원본을 가리키던 포인터를 수정된 복사본으로 '원자적(Atomic)'하게 바꾼다. 이제부터 새로 들어오는 Reader들은 수정된 데이터를 본다.
4. 대기 및 삭제 (Reclaim): 포인터를 바꾸기 전부터 기존 데이터를 읽고 있던 '이전 Reader'들이 모두 끝날 때까지 기다렸다가(synchronize_rcu), 기존 데이터를 안전하게 삭제한다

Reader 사이드:

• rcu_read_lock() / rcu_read_unlock(): 읽기 시작과 끝을 알린다.
  • 실제로는 락을 거는 게 아니라 선점(Preemption)을 방지하는 가벼운 동작임.
  • 시작과 끝의 사이에 block을 사용하지 못한다. 
• rcu_dereference(): RCU로 보호되는 포인터 값을 안전하게 읽어온다

Writer 사이드:

• rcu_assign_pointer(): 새로운 데이터(복사본)의 주소를 원본 포인터에 할당한다.
• synchronize_rcu(): 모든 CPU에서 컨텍스트 스위칭이 한 번씩 일어날 때까지(기존 Reader들이 작업을 마칠 때까지) 기다린다.