스핀락, 뮤텍스, 세마포어

교착상태

공유 자원을 두고 서로 다른 접근자가 경쟁하는 과정, 서로 자원을 소유하려다 보니 누구도 소유할 수 없는 상황을 교착상태라고 한다.

 

교착 상태가 되기 위한 필수 4가지 조건. 1개라도 해당 사항이 없으면 교착상태가 아니다

• 상호 배제(mutual exclusion)
• 점유 대기
• 비선점
• 순환 대기

 

임계영역

공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행가능한 영역

하나의 프로세스/스레만 진입해서 실행한다는것 = mutual exclusion 이라고 한다.

 

 

스핀락, 뮤텍스, 세마포어

경쟁 조건을 완화하기 위한 방법들 중 상호 배제 방법, 또는 동기화 방법 이라고도 부른다.

 

스핀락

스핀락은 자원을 소유할 수 있을때까지 지속적으로 물어본다.

public class SpinLockExample {
    private static final AtomicInteger lock = new AtomicInteger(0);

    public static void main(String[] args) {
        // Creating multiple threads to demonstrate the spinlock
        Thread t1 = new Thread(SpinLockExample::criticalSection, "Thread 1");
        Thread t2 = new Thread(SpinLockExample::criticalSection, "Thread 2");

        t1.start();
        t2.start();
    }

    private static void criticalSection() {
        //락을 점유할 때까지 계속 시도(busy waiting)
        while (testAndSet(lock) == 1) {
            // Busy-wait until the lock is free
        }

        try {
            // Critical section
            System.out.println(Thread.currentThread().getName() + " is in the critical section");
            // Simulate some work in the critical section
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.set(0); // Release the lock
        }
    }
    //1: 락을 점유, 0: 락을 비점유
    private static int testAndSet(AtomicInteger lock) {
        return lock.getAndSet(1);
    }
}

스핀락의 경우 락을 가질 수 있을 때 까지 반복해서 시도하기 때문에 Cpu 싸이클을 소모하여 결국 Cpu를 낭비한다.

 

 

뮤텍스

뮤텍스는 락을 가질 수 있을때 까지 휴식 하는 방법이다.
하나의 쓰레드만이 자원에 대해서 점유할 수 있으며, 작업이 끝난 쓰레드는 Queue에 잠들어 있는 다음 쓰레드를 깨워서 알려준다.

의사코드

class Mutex {
    int value = 1; //lock을 얻고 반환할때 사용되는 값, 사용중이면 0 아니면 1
    int guard = 0; //value는 여러 쓰레드가 접근하는 공유자원, 때문에 critical section에서 안전하게                         핸들링 하기 위한 장치
}

Mutex::lock(){
    while(test_and_set(&guard));
    if(value == 0){
        ..현재 쓰레드를 큐에 적재한다.
        guard = 0; & go to sleep
    } else {
        value = 0;
        guard = 0;
    }
}

Mutex::unlock(){
    while(test_and_set(&guard));
    if(큐에 하나라도 대기중이라면){
        그 중에 하나를 깨운다;
    } else {
        value = 1;
    }
        guard = 0;
}


void process(){
     mutex->lock();
     ..critical section
     mutex->unlock();
}

lock은 mutex의 내부 value값을 판단해서 얻거나 해지를 한다.

value는 멀티스레드 환경에서의 공유자원이기 때문에 이를 안전하게 핸들링하고자 추가로 guard를 사용한다.

자바코드

public class MutexEX {
    private final Lock lock = new ReentrantLock();

    public void accessData(int threadName){
        System.out.println(threadName+" 접근");
        lock.lock();

        //critical section
        try {
            System.out.println(threadName+" 작업중");
            //작업이 진행되는 가상의 시간
            Thread.sleep(1000);
        }catch (InterruptedException e){
            Thread.currentThread().interrupt();
        }finally {
            System.out.println(threadName+" 작업완료");
            lock.unlock();
        }
    }
}

//이전 쓰레드가 모든 작업이 끝나고 나면 그제서야 다음 쓰레드가 작업할 수 있다.
public class MutexMain {
    public static void main(String[] args) throws InterruptedException {
        final MutexEX mutex = new MutexEX();
        ExecutorService es = Executors.newFixedThreadPool(5);

        for (int i=0; i<5; i++) {
            final int threadName = i;
            es.submit(() -> mutex.accessData(threadName));
        }

        es.shutdown();
        boolean finished = es.awaitTermination(10, TimeUnit.SECONDS);
    }
}

뮤텍스는 순차적으로 쓰레드가 접근하며, 이전 쓰레드가 모든 작업이 끝나고 나면 그제서야 다음 쓰레드가 작업할 수 있다.

 

뮤텍스 vs 스핀락

멀티 코어 환경이거나, 임계영역 에서의 작업 속도가 컨텍스트 스위칭 속도 보다 빠르다면 스핀락>뮤텍스, 스핀락 승

뮤텍스는 쓰레드가 잠들고 깨는 과정에서 컨텍스트 스위칭이 발생

 

 

세마포어

signal 메커니즘을 가진, 하나 이상의 프로세스/스레드가 Critical section에 접근 가능하도록 하는 장치

)

세마포어는 임계영역에 대해서 여러 쓰레드가 접근할 수 있으며 그 개수를 정할 수 있다.

정한 개수만큼 쓰레드가 임계영역에 들어가 있으면 카운팅은 0을 가르킨다.

그 후에 접근 하려는 쓰레드들은 Queue 에서 대기를 하며 대기하는 쓰레드의 개수만큼 음수 값 카운팅을 한다.

예를 들어서 5명이 Queue에 대기하고 있다면 -5를 카운팅 한다.

semaphore(내부 구현 의사코드) 예제코드

class Semaphore  {
    int value = 1; //0,1,2 등 여러 값을 가질 수 있음
    int guard = 0; //
}

Semaphore::wait(){
    while(test_and_set(&guard)==1);
    if(value == 0){
        ..현재 쓰레드를 큐에 적재한다.
        guard = 0; & go to sleep
    } else {
        value -= 1;
        guard = 0;
    }
}

Semaphore::signal(){
    while(test_and_set(&guard)==1);
    if(큐에 하나라도 대기중이라면){
        그 중에 하나를 깨워서 준비 시킨다.
    } else {
        value += 1;
    }
        guard = 0;
}


void process(){
     semaphore->lock();
     ..critical section
     semaphore->unlock();
}

semaphore 는 Critical section에 여러 스레드가 진입할 수 있도록 내부적으로 Signal의 value를 핸들링한다.

value는 여러 값이 들어가고 증감을 통해 핸들링한다.

value를 1로 설정하여 mutual exclusion을 보장할 수 있으며 이를 이진 semaphore, 1보다 더 많은 값을 가진 value면 counting semaphore 라고 한다.

semaphore는 signal, wait 핸들링으로 내부 순서를 정할 수 있다.

 

 

세마포어의 Sleep Waiting, Busy Waiting 2가지 방식

Sleep waiting

Busy waiting

자바 예시 코드

public class SemaMain {
    public static void main(String[] args) throws InterruptedException {
        final SemaphoreEX semaphoreEX = new SemaphoreEX();
        ExecutorService es = Executors.newFixedThreadPool(10);

        for (int i=0; i<10; i++){
            final int threadName = i;
            es.submit(() -> semaphoreEX.accessData(threadName));
        }

        es.shutdown();
        es.awaitTermination(20, TimeUnit.SECONDS);
    }
}

public class SemaphoreEX {
    private final Semaphore semaphore = new Semaphore(3); //동시에 3개의 쓰레드 접근 가능

    public void accessData(int threadName){
        try {
            System.out.println(threadName+" 접근증");
            // 허가증 획득 시도
            semaphore.acquire();
            System.out.println(threadName+" 작업중");
            //작업이 진행되는 가상의 시간
            Thread.sleep(1000);
        } catch (InterruptedException e){
            Thread.currentThread().interrupt();
        } finally {
            System.out.println(threadName+" 작업완료");
            //작업 완료 됬다는 signal 전송
            semaphore.release();
        }
    }
}

세마포어는 동시에 접근할 수 있는 스레드의 수를 제한한다.

 

 

뮤텍스 vs 세마포어

• 뮤텍스는 세마포어로 사용될 수 없지만, 세마포어는 뮤텍스로 사용될 수 있다. 이진 세마포어를 뮤텍스처럼 사용하기 때문이다.
• Mutex는 lock을 소유한 사람만 lock을 해제 할 수 있지만 semaphore는 그렇지 않다.(signal, wait 핸들링)
• Mutex는 여러 프로세스/스레드가 접근시 cpu에서 컨텍스트 스위칭이 일어나면서 누구를 먼저 실행할지 우선순위 스케쥴링을 하게 된다. 그러나 P2(우선순위가 낮은 것)가 lock을 갖고 있다면 P1(우선순위 높은 것)가 계속 대기를 하는 문제가 발생한다. Mutex는 P2의 우선순위를 P1만큼 높여서 P2를 빠르게 처리하도록 만든다. 이를 priority inheritance 라고 하며 뮤텍스는 priority inheritance 속성을 가진다고 말할 수 있다. 그러나 semaphore에서는 없다.

참고:

https://www.youtube.com/watch?v=oazGbhBCOfU

https://www.youtube.com/watch?v=gTkvX2Awj6g