[운영체제] 6. Race Conditions(2) -Semaphores, Mutex and Monitors

2022.04.11 - [컴퓨터 공학/0 +운영체제] - [운영체제] 5. Race Conditions

[운영체제] 5. Race Conditions(1)

 

앞에서 스핀락에대해서 설명했는데

스핀락은 락이 풀릴때까지 무한 루프를 돌면서 대기하는 것을 의미한다.(busy waiting)

스핀락은 busy waiting을 하는 mutex lock이다.

 

 

그러면 이제 지난 시간에 이어서 Mutex와 Semaphore에 대해서 정리 해보겠다..!!

 

---

 

Semaphore와 Mutex는 producer-consumer problem(생산자-소비자 문제)를 해결하기 위해서 등장 했다.

생산자가 데이터를 생성하여 버퍼에 저장하고, 소비자가 버퍼에서 데이터를 가져와 소비하는 과정에서 발생 할 수 있는 문제이다.

즉, 동기화 과정에서 발생하는 문제이다.

 

 

 

Semaphores

https://velog.io/@conatuseus/OS-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4%EC%99%80-%EB%AE%A4%ED%85%8D%EC%8A%A4

[OS] 세마포어와 뮤텍스

E.W Dijkstra가 구현한 알고리즘이다.

UP과 Down을 이용하여 구현했는데 OS의 도움을 받아서(시스템 호출 형태) lock을 거는 것이다.

세마포어는 상호배제와 동기화 둘다 사용가능한 알고리즘이다.

세마포어는 뮤텍스와 다르게 N개의 프로세스에서 동기화가 가능하다.

또한 뮤텍스와 다르게 down와 up이라는 2개의 atomic operation을 사용한다.

down을 호출하면 세마포어의 카운트 하나를 줄이고, up을 호출하면 세마포어 카운트 하나를 늘린다.

 

struct semaphore {
	int count;
    queueType queue;
}

void down(semaphore s) {
	s.count--;
    if(s.count < 0) {
    	sleep;
    }
}

void up(semaphore s) {
	s.count++;
    if(s.count <= 0) {
    	wakeUp;
    }
}

//s.count가 음수이면 음수의 절댓값 만큼 프로세스가 sleep 중

 

https://heeonii.tistory.com/14

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

 

예를 들어 세카이랜드에 범퍼카 3대가 있고 범퍼카를 타기 위해서는 열쇠가 필요하다.

 

세웅이가 범퍼카를 타기 위해서 열쇠를 갖고 down을 외치고 범퍼카를 이용한다.

그러면 범퍼카 2대를 이용할 수 있다고 전광판이 알려준다.

 

범퍼카가 재미있다는 소문이 나자 신영이와 민혁이가 범퍼카를 타러 온다.

마찬가지로 down을 외친다.!

 

그렇게 세웅이 신영이 민혁이가 셋이 범퍼카를 타고 있는데

용준이가 그 소문을 듣고 범퍼카를 타러 왔지만, 이용할 수 있는 범퍼카가 없다는 것을 알게 되었다.

하지만, 용준이는 자기가 기다리고 있다는 것을 알리기위해  down을 외친다.

전광판에 기다리고 있는 사람의 수를 알려주는 의미로 -1이 표기 된다.

용준이는 이때 대기큐라는 곳에서 기다린다.

 

 

세웅이가 다 즐겼는지(용준이의 압박에😆), 이제 그만 탄다는 의미로 up을 외친다.

 

용준이는 그 말을 듣고 세웅이가 반납한 열쇠를 갖고 재빠르게 범퍼카에 올라탄다.

세웅이가 up을 외쳤기 때문에 범퍼카 이용가능 댓수는 -1에서 0으로 변하게 된다.

 

 

이것이 세마포어가 동작하는 방식입니다.

• 공유자원: 범퍼카
• 사람: 프로세스(또는 스레드)
• 공유자원에 접근 할 수 있는 프로세스 갯수(또는 스레드): 사용가능 범퍼카 대수

 

세마포어는 카운팅과 이진 방식이 있는데,

위에서 설명한 것은 카운팅 방식의 세마포어이다.

이진방식은 2개의 공유자원을 사용할 때를 의미한다.

 

---

 

728x90

 

Mutex

세마포어와 마찬가지로 병행처리를 위한 동기화 기법 중 하나이다.

이진세마포어과 같이 초기값을 0, 1을 갖는다.

뮤텍스는 2개의 프로세스(또는 스레드)가 동기화 대상이 하나인 공유자원을 사용할 때 사용하는 알고리즘이다.

뮤텍스는 lock과 unlock을 사용한다.

 

mutex = 1;

void lock () {
	while (mutex != 1) {
    	/* mutex 값이 1이 될 때까지 기다립니다.*/
    }
    /* 이 구역에 도착했다는 것은 mutex 값이 1이라는 것입니다.
       따라서 이제 뮤텍스 값을 0으로 만들어 다른 프로세스(혹은 쓰레드)가 접근하지 못하도록 막아야 합니다.
    */
    mutex = 0;
}

void unlock() {
	/* 임계 구역에서 나온 프로세스는 다른 프로세스가 접근할 수 있도록 락을 해제합니다.*/
	mutex = 1;
}

 

뮤텍스는 범퍼카가 1개 밖에 없는 세카이랜드이다.

따라서 열쇠함에 열쇠가 없으면 다른 사람이 범퍼카를 이용하는 것이고, 그 사람이 열쇠를 반납 할때 까지 기다려야 합니다.

열쇠를 반납하면 그 열쇠를 갖고 범퍼카를 이용합니다.

 

세카이랜드에 범퍼카가 1대 있고 세웅이가 범퍼카를 이용하러 왔다.

 

 

열쇠를 챙기고 범퍼카를 이용한다. 

이때 세웅이는 lock을 외친다.!

 

한 발 늦은 민혁이는 이미 세웅이가 범퍼카를 이용하고 있기 때문에 이용 할 수 없다.

세웅이가 범퍼카를 다 타고 나올때 민혁이에게 알려주기 위해 unlock을 외친다..!

 

세웅이가 반납한 열쇠를 이용하여 민혁이가 범퍼카에 탑승한다.

민혁이도 lock을 외친다.

 

 

---

 

세마포어와 뮤텍스의 차이점

• 세마포어의 경우 여러개의 스레드가 접근 할 수 있지만, 뮤텍스의 경우 오직 1개의 스레드만 접근이 가능하다.
• 세마포어는 현재 수행중인 스레드가 아닌 다른 스레드가 세마포어를 해제 할 수 있지만, 뮤텍스의 경우 lock, unlock하는 주체가 동일 해야한다.

 

세마포어 뮤텍스 모두 완벽한 기법은 아니므로 데이터 무결성을 보장 할 수는 없고, 모든 교착상태를 해결하지는 못한다...!😅

 

---

 

반응형

 

Monitors

https://velog.io/@seanlion/monitorsync

Monitor(모니터)에 대해 알아보고 동기화를 이해하기

https://jayhyun-hwang.github.io/2021/08/23/Monitor/

동시성 프로그래밍에서의 모니터(Monitor) - Jays blog

 

세마포어도 프로그램이 복잡해지면 많은 문제가 발생한다.

down, up 쌍이 안맞는 경우가 발생하게 된다.

따라서 이러한 문제를 해결하기 위해 Monitors 기법 등장!

(모니터라고 불리는 이유는 스레드가 리소스에 어떻게 접근 하는지 모니터링 하기 때문.)

 

모니터는 컴파일러에서 상호배제와 동기화 문제를 해결하는 방법인데,

컴파일러에서 동시에 호출해도 동시에 실행하지 않도록 했다.

(procedure producer();와 procedure consumer();를 동시에 호출해도 동시에 실행하지 않는다.)

따라서 개발자가 상호배제를 직접 구현 할 필요가 없다.

즉, 모니터는 프로세스, 스레드가 mutual exclusion, cooperation를 가질 수 있도록 하는 동기화 메커니즘.

• mutual exclusion
  • 하나의 스레드만이 특정한 시점에서 임계영역 실행(lock 기법 사용)
• cooperation
  • 특정 조건이 충족될 때까지 스레드를 대기 시키는 기능

 

monitor example
    integer i;
    condition c;
    
    procedure producer();
    .
    .
    .
    .
    end;
    
    
    procedure consumer();
    .
    end;
end monitor;

 

 

---

 

Producer/Consumer with Hoare's Monitor

Hoare 방식이라고 불리는 모니터 방식이다.

호어는 깨어준 스레드가 멈추고, 깨어난 스레드가 실행해야 한다고 주장 했다.

그 이유는 csignal(notempty);에 의해서 깨어났지만, append()가 csignal(notempty); 이후로 추가적인 구문을 실행한다면

take()에 있는 if조건이 훼손 될수 있기 때문이라고 설명 했다.

 

• cwait
  • 호출한 프로세스를 일시 정지 시킨다.
  • 모니터에는 이제 다른 프로세스가 들어올 수 있다.
• csignal
  • cwait에 의해 중지되었던 프로세스가 수행을 재개 한다.
  • 중지된 프로세스가 없다면 시그널은 소실된다.

 

 

---

 

Producer/Consumer with Lampson & Redell's Monitor

하지만, 효율성을 위해 호어와 반대로 생각한 사람이 있다.

조건 훼손이 문제라면 if문 말고 while문을 사용하면 된다 라고 했다.

 

append();에 cnotify(notempty)에 의해서 깨어나도

take();에 while(count == 0) cwait(notempty);이기 때문에 while문의 조건을 다시 한 번 확인한다.

 

 

java에서는 모니터를 지원한다.

https://ktko.tistory.com/entry/%EC%9E%90%EB%B0%94-synchronized%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC

자바 synchronized에 대하여

 

synchronized를 사용하면 되는데 아래 코드로 설명 하겠다.

synchronize는 두가지 형태로 사용되는데,

1. 블록을 만들어서 사용하는 방식

2. 함수를 만들어서 사용하는 방식

/***
* 임계 영역에 해당하는 코드 블록을 선얼할 때 사용하는 java 키워드(synchronize)
* 해당 코드 블록(임계영역)에는 모니터락을 획들해야 진입이 가능하다.
* 모니터락을 가진 객체 인스턴스를 지정할 수 있다.
* 메소드에 선언하면 메소드 코드 블록 전체가 임계영역
*  -> 이때, 모니터락을 가진 객체 인스턴스는 this 객체 인스턴스이다.
*/

//블록을 만들어서 사용
synchronized (object) {
	//critical section
}


//함수를 만들어서 사용
public synchronized void add() {
	//critical section
}

 

세웅이와 중헌이가 여행을 가기위해 같은 계좌를 사용한다고 가정했을때,

synchronize가 없는 출금 시스템을 이용한다고 가정했을 때를 보자

package com.example.demo;

//계좌
public class Account {

	//잔금
    public int balance = 1000;

    public void withDraw(int money) {
    	//잔금이 출금 금액보다 커야 출금 가능
        if (balance >= money) {
            try {
                Thread thread = Thread.currentThread();
                balance -= money;
                System.out.println(thread.getName() + " 출금 = " + money+", 잔고 = "+balance);
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

class Task implements Runnable {

    Account Account = new Account();

    @Override
    public void run() {
    	//잔금이 0보다 크면 무한반복
        while(Account.balance > 0) {
            int money = 200;
            Account.withDraw(money);
        }
    }
}

class threadTest {
    public static void main(String[] args) {
        
        Task task = new Task();
        
        Thread thread1 = new Thread(task);
        Thread thread2 = new Thread(task);
        thread1.setName("장세웅");
        thread2.setName("정중헌");

        thread1.start();
        thread2.start();
    }
}

 

결과를 보면 다음과 같다.

 

위를 보면 결과값이 엉망인 것을 확인 할 수 있다.

 

1. 메소드에 synchronize

package com.example.demo;

public class Account {

    public int balance = 1000;

	//synchronized 사용
    public synchronized void withDraw(int money) {
        if (balance >= money) {
            try {
                Thread thread = Thread.currentThread();
                balance -= money;
                System.out.println(thread.getName() + " 출금 = " + money+", 잔고 = "+balance);
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

 

결과를 보면 스레드가 시작하는 순서는 서로 다르지만, 출금과 잔고가 알맞게 계산되는 것을 알수 있다.

 

 

이처럼 메서드에 synchronized하면이 메서드를 가진 인스턴스 기준으로 동기화가 이루어진다.

 그러므로 한 클래스에 synchronized를 사용한 메서드를 가진다면, 여기서 동기화는 인스턴스 기준으로 이루어진다.

오로지 하나의 thread만이 동기화된 인스턴스 메서드를 실행 할 수 있다.

즉, 메서드에 synchronized를 사용하면 그 함수가 포함된 객체가 lock이 걸린 것이다.

 

 

2. 블록에 synchronize

package com.example.demo;

public class Account {

    public int balance = 1000;

    public void withDraw(int money) {
        //블록에 synchronized
        synchronized (this) {
            if (balance >= money) {
                try {
                    Thread thread = Thread.currentThread();
                    balance -= money;
                    System.out.println(thread.getName() + " 출금 = " + money + ", 잔고 = " + balance);
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

 

synchronize(this){ ... }; 에서 this는 자기자신을 가리킨다.

즉 해당 메소드를 호출하는 인스턴스가 락을 거는 것이다.(동기화는 락을 필요로 하며 락은 모든 객체마다 존재한다.)

여기서 객체 스스로 메서드 전체를 감시하여 락을 거는 것이다.

결과를 보면 알수 있듯이 장세웅이 자원을 독점하는 것을 알 수 있다. 정중헌은 기아상태.

 

 

 

---

 

Lock-free Data Structure

https://effectivesquid.tistory.com/62

Lock Free 알고리즘(Non-Blocking 알고리즘)

CPU는 atomic CAS(Compare-and-swap operation)을 지원한다.(기계어)

병목화 현상을 줄이고, 병렬화를 지원한다.

등장한 이유는

lock, unlock을 하는 동안 다른 스레드가 기다려야 하기 때문이다.(멀티코어 환경에서 lock, unlock을 병목현상 없이 실행하기 위함)

즉, lock으로부터 free하기 위해 연구됨.

int AtomicAdd(int* p, int addnd) {
    int x;
    do {
    	x = *p;
    } while(!CAS(p, x, x+addnd));
    return x;
}

CAS(p, x, x+addnd);

현재 p가 가리키는 변수의 값(x)을 보고, 여전히 x이면 x+addnd 연산을 수행하여 x에 대입 한다.(atomic하게 한번에 변경)

만약 p가 가리키는 변수(x)값이 달라지면, 실패... 다른 스레드가 값을 변경한것..!!!

그러면 다시 do로 가서 실행한다.

 

많은 cpu들이 lock-free를 지원한다.

CAS명령을 이용하면 임계구역에 대한 lock, unlock이 사라진다.

 

---

Lock-free push and pop

linkedList을 이요하여 stack자료구조

nodeA, nodeB 사이에 nodeC를 넣는 작업에 대한 예시이다.

 

• push
  • CAS(&head, A, C); 
  • head가 여전히 nodeA를 가리키고 있으면 nodeC로 head를 교체해라.
  • CAS(&head, A, C); 결과가 false이면 누군가 바꾼것이다.
  • 그러면 다시 do문으로 가서 실행한다.
• pop
  • CAS(&head, A, B);
  • head가 여전히 nodeA를 가리키고 있으면 nodeB로 head를 교체해라.
  • CAS(&head, A, B); 결과가 false이면 누군가 바꾼것이다.
  • 그러면 다시 do문으로 가서 실행한다.

 

---

 

Lock-free 자료구조의 ABA Problem

CAS연산과 관련하여 공유자원의 변경을 감지하지 못하는 현상이다.

CAS연산에 메모리 주소 또는 레퍼런스를 사용하는 가운데, 메모리가 재사용되는 경우에 발생한다...

즉, 노드의 재사용시 생기는 문제이다.

thread1은 pop()을 해서 head가 nodeB를 가리키게 할 것이다.

그런데, 중간에 thread2가 pop()을 하면 head가 nodeB를 가리키게 된다.(이때, nodeA는 free, nodeB->nodeC)

그리고 또 pop()을 실행하여 head가 nodeC를 가리키게 한다.(이때 nodeB는 free, nodeC)

마지막으로 push(A)를 실행하여 head가 nodeA를 가리키게 한다.(현재, nodeB free, nodeA->nodeC)

그리고 나서 thread1이 pop()을 수행하게 되면, head는 free상태인 nodeB를 가리키게 된다...

이래서 자료구조가 깨지게 된다..!!🥲

 

---

 

Message Passing

지금까지 생산자, 소비자 프로그래밍에 대해서 살펴보았는데

이때 필요한것은 동기화, 상호배제가 필요하다는 것을 알게 되었다.

메시지는 두 가지가 존재한다.

send(destination, message)

receive(source, message)

이 2가지에 대해서 synchronization, addressing(destination, source)하는 법에 대해서 알아보자..!

 

synchronization

• sender와 receiver는 기다릴수도 안 기다릴수도 있다.
  • (sender and receiver may or not be blocking(waiting for message))
• bocking send, blocking receive
  • sender, receiver 둘다 메시지가 도착하기 전까지(응답을 받기 전까지) 기다린다.
  • called a rendezvous(랑데뷰: 서로 만날때 까지)
  • 보통 receiver는 메시지를 받을 때 까지 기다림(메시지를 안받으면 할것이 없음..)
• Nonblocking send, blocking receive
  • 가장 자연스러운 형태
  • sender는 메시지를 보내고 다른일을 함.
  • receiver는 메시지를 받기 전까지 기다림.
• Nonblocking send, Nonblocking receive
  • sender, receiver 메시지를 보내고 다른일을 함.
  • 다만, 메시지를 보내고 그 메시지를 저장해야함.

 

Addressing

메시지를 보내기위해서 source를 지정해야하는데

한 가지 방법은 processId를 사용하는 방법이다. 이것이 Direct Addressing 방식이다.

• Direct Addressing
  • 기본 전송 대상의 프로세스에 특정 식별자가 포함됩니다.
  • 수신 기본값은 메시지가 예상되는 프로세스를 미리 알 수 있다.
  • 수신 기본값은 수신 작업이 수행되었을 때 소스 매개변수를 사용하여 값을 반환 할 수 있습니다.

 

하지만 이건 프로그램을 실행 할때 동적으로 정해지기 때문에 불가하다.

따라서 Direct Addressing은 불가하다.

 

• Indirect Addressing
  • 메시지는 큐로 구성된 공유 데이터 구조로 전송됩니다.
  • 큐를 mailboxes라고 부른다.
  • 한 프로세스는 큐로 메시지를 보내고 다른 프로세스는 큐에 메시지를 가져온다.

아래 그림은 메일박스를 이용한 것이다.

 

예를 들어 학교 웹서버에 접속하려면

학교 웹서버의 ip와 port번호를 알아야 한다.

 

 

Producer-Consumer Problem with N Message

메시지를 주고 받는것도

논블록킹 send, 블록킹 receive를 이용하면 동기화가 된다.

임계구역은 따로 설정 할 필요가 없다.(메시지 자체로 주고 받기 때문.) 

아래는 예제이다.

 

producer가 받는 큐, 보내는 큐 두 가지가 존재한다.

 

---

 

Barriers(명령어)

process의 실행이 다 끝나고서야 다음 명령을 실행해야 할 때 사용하는 방법이다.

순서가 바껴서 실행되면 안되는 경우 사용한다.