[OSTEP 병행성(concurrency)]락

📝서론 

병행성에 대한 소개 이후 병행 프로그램의 근본적인 문제 몇 개를 살펴보았다. 여러 개의 명령어들을 원자적으로 실행해보고 싶지만 단일 프로세스의 인터럽트로 인해서 그렇게할 수 없다. 이 장에서는 임계 구역에서 상호 배제를 할 수 있는 것 중 하나인

락(Lock)에 대해 알아보자

 

📝락 : 기본 개념

예제를 위해 다음과 같은 임계 영역이 있다고 하자. 전형적인 예제인 공유 변수 갱신이다.

banlance = balance + 1;

 

락은 하나의 변수로 사용한다. 이 락 변수는 락의 상태를 나타내며 사용 가능 상태 & 사용 중 상태가 있다.

lock_t mutex; // 글로벌 변수로 선언된 락

lock(&mutex);
balance = balance + 1;
unlock(&mutex);

 

📌 Pthread 락

쓰레드 간에 상호 배제 기능을 제공하는 라이브러리로 mutex라고 부른다.

ptrhead_mutex_lock()이 호출되었을 때 다른 어떤 쓰레드도 락을 가지고 있지 않다면 해당 락을 얻어 임계 영역에 진입하면 락 획득 시도를 막는다.

 

 

📝락의 평가

어떤 락이든 만들기 전에 첫째로 목표를 이해해야 하고 구현 효율을 어떻게 할지 평가해야한다.

평가 기준은 다음과 같다.

1. 상호 배제를 제대로 지원하는가?
2. 공정성 : 락을 전혀 얻지 못해 기아 상태가 발생하는가?
3. 성능 : 락 사용 시간적 오버헤드 효율이 좋은가?

 

📝락 출현 전 해결법

초기에는 단일 프로세서 시스템에서 임계 영역 보호를 위해 인터럽트 비활성화을 통해 상호 배제를 이루었다.

이 방법은 여러 단점이 있고 멀티 프로세스 환경에서는 제대로 동작하지 않기에 문제가 있었다.

주요 장점:

• 단순성: 하드웨어 명령어를 통해 인터럽트를 비활성화하고 활성화하는 방식은 간단하고 직관적입니다.
• 원자적 실행 보장: 인터럽트가 비활성화된 상태에서 임계 영역 내 코드가 실행되므로, 다른 쓰레드나 프로세스가 끼어들지 않아 안전하게 임계 영역을 실행할 수 있습니다.

주요 단점:

1. 특권 연산 필요: 인터럽트를 비활성화하거나 활성화하는 명령어는 특권 연산이므로 이를 허가받은 프로그램만 사용할 수 있습니다. 이를 악용하는 프로그램이 있을 경우 시스템에 위험을 초래할 수 있습니다.
2. 멀티프로세서 환경에서의 문제: 멀티프로세서 시스템에서는 한 프로세서에서 인터럽트를 비활성화해도 다른 프로세서에서는 영향을 받지 않기 때문에, 여러 프로세서가 동시에 임계 영역에 진입할 수 있어 상호 배제를 보장할 수 없습니다.
3. 중요한 인터럽트 놓칠 위험: 인터럽트를 비활성화한 상태가 길어지면, 중요한 인터럽트(예: I/O 완료 시 시스템 제어)가 발생할 수 없게 되어 시스템에 심각한 문제를 일으킬 수 있습니다.
4. 비효율성: 최신 CPU에서는 인터럽트 비활성화 명령이 일반적인 명령어보다 더 느리게 실행될 수 있어, 성능 저하를 초래할 수 있습니다

 

📝멀티 프로세서 시스템에서의 락

멀티 프로세서에서는 인터럽트를 중지시키는 것은 의미가 없기에 락을 지원하기 위해 하드웨어를 설계했습니다.

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체라고 불리는 기법입니다. 

 

1. Test-And-Set

 

• Test-And-Set 명령어는 원자적으로 값을 검사하고 설정하는 연산으로, 이를 통해 락을 구현할 수 있습니다.
• TestAndSet은 주어진 포인터의 값을 확인하고, 동시에 새 값을 설정합니다. 이 동작은 원자적으로 수행되므로 다른 쓰레드가 동시에 동일한 값을 설정하는 일이 없게 보장됩니다.
• 예시 코드에서는 flag 값이 0인 경우 락을 설정하고, 다른 쓰레드는 TestAndSet을 사용하여 락이 해제될 때까지 대기하게 됩니다
• 문제 : 동시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정할 수 도 있음, 성능 낭비

    private static boolean lock = false;

    public static synchronized void lock() {
        while (lock) {
            try {
                SimpleLock.class.wait();  // 잠금 상태에서 대기
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        lock = true;  // 잠금 설정
    }

    public static synchronized void unlock() {
        lock = false;  // 잠금 해제
        SimpleLock.class.notify();  // 대기 중인 쓰레드 하나를 깨운다
    }

어렵게 설명되어 있지만 간단한 boolean(0 & 1) 변수를 통해서 검사하고 설정하는 것입니다.

 

2. 스핀 락

 

• 스핀 락은 락을 획득할 때까지 계속해서 대기하는 방식입니다. 단일 CPU에서는 효율적이지 않지만 멀티 CPU 시스템에서는 락을 획득하려는 쓰레드가 다른 CPU에서 대기할 수 있어 비교적 효율적입니다.
• 스핀 락은 공정성을 보장하지 않으며, 대기 중인 쓰레드가 영원히 대기할 수 있기 때문에 "굶주림" 현상이 발생할 수 있습니다.

 

3. Compare-And-Swap

 

• Compare-And-Swap은 메모리 값을 비교하고 일치할 경우 값을 변경하는 명령어입니다. 이 기법은 Test-And-Set과 유사하게 락을 구현하는 데 사용될 수 있습니다.
• Compare-And-Swap은 락을 획득하려는 쓰레드가 flag 값이 0일 때만 원자적으로 1로 변경하여 락을 획득할 수 있게 합니다.

4. 큐의 사용 : 스핀 대신 잠자기

이전 방법들은 근본 문제가 너무 많은 부분을 운에 맡긴다는 것입니다. 스핀 락의 경우 스케줄러가 다음 실행될 쓰레드를 선정하는데 만약 안 좋은 선택을 진행하면 회전을 하면서 다시 대기하거나 기아 상태를 막지 못합니다.

 

그렇기에 어떤 스레드가 다음 락을 획득할지를 명시적으로 제어할 수 있어야 합니다. 

이를 위해서 운영체제는 큐를 이용한 대기 쓰레드를 관리하며 스핀 대신에 호출 함수를 잠재우는 방식을 사용합니다.

 

이를 통해 기아 상태나 불필요한 CPU 낭비를 방지할 수 있습니다.

 

 

📝요약 

병행성 문제와 락의 필요성

병행 프로그램에서는 여러 명령어를 원자적으로 실행하고 싶지만, 단일 프로세스 인터럽트로 인해 어려움이 있습니다. 이를 해결하기 위해 락(Lock)을 사용하여 임계 구역에서의 상호 배제를 구현할 수 있습니다.

락의 기본 개념

락은 공유 자원에 대한 동시 접근을 방지하고, 한 번에 하나의 프로세스만 해당 자원에 접근할 수 있도록 합니다. 예를 들어, balance = balance + 1; 같은 공유 변수 갱신 시 락을 사용하여 충돌을 방지합니다.

락의 구현: Pthread

Pthread 라이브러리에서는 mutex를 사용하여 쓰레드 간 상호 배제를 지원합니다. pthread_mutex_lock()을 통해 락을 얻고, 락이 걸려 있으면 다른 쓰레드는 대기합니다.

락의 평가 기준

락을 구현할 때 중요한 평가 기준은:

1. 상호 배제: 락이 정상적으로 동작하는지
2. 공정성: 기아 상태를 방지하는지
3. 성능: 락 오버헤드가 효율적인지

락의 이전 해결법

초기에는 단일 프로세서에서 인터럽트를 비활성화하여 상호 배제를 구현했습니다. 그러나 멀티 프로세서 시스템에서는 이 방법이 제대로 동작하지 않으며, 성능과 안전성 문제를 일으킬 수 있습니다.

멀티 프로세서 환경에서의 락

멀티 프로세서 시스템에서는 인터럽트를 중지시킬 수 없기에, 락을 지원하기 위한 하드웨어 설계가 필요합니다.

1. Test-And-Set: 원자적 교체 기법으로 락을 구현합니다. 주어진 값이 0일 때만 락을 획득할 수 있도록 보장합니다.
2. 스핀 락: 락을 얻을 때까지 계속 대기하는 방식으로, 멀티 CPU 환경에서는 비교적 효율적입니다. 그러나 공정성을 보장하지 않으며 기아 상태가 발생할 수 있습니다.
3. Compare-And-Swap: 값을 비교하고 일치하면 값을 변경하는 기법으로, 락을 획득하려는 쓰레드가 원자적으로 락을 얻을 수 있도록 합니다.
4. 큐 사용: 스핀 락 대신 큐를 이용해 대기 중인 쓰레드를 관리하고, 불필요한 CPU 낭비와 기아 상태를 방지합니다.