동기화, 세마포 : Synchronization, Semaphores [운영체제]

 

많은 쇼프트웨어적 동기화 도구들이 있지만

 

우선

Semaphores, 세마포를 알아보자

 

이 글은 프로세스와 동기화, 임계구역에 대한 이해를 바탕으로 쓰는 글이다.

[CS Interview] - Process, 프로세스란?

[컴퓨터(Computer Science)/운영체제(Operation System)] - Critical Section, 임계구역이란? [운영체제]

[컴퓨터(Computer Science)/운영체제(Operation System)] - 프로세스에서의 동기화 (Process Synchronization) [운영체제]

**추가예시

[컴퓨터(Computer Science)/시스템 프로그래밍(System Programming)] - 세마포어,Semaphores 그 쓰임과 예시

 

 

---

 

 

Semaphores, 세마포

 

세마포 S는 정수 변수다.

S = 10이라면 사용가능한 자원이 10개 있다는 말과 같다.

초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait() 와 signal()로만 접근할 수 있다.

 

추상 자료형 S가 있다고 생각하고 

해당 자료형으로 연산할 수 있는 것은 P(wait), V(signal) 밖에 없다고 생각하면 된다.

 

**초기에는 P, V 연산으로 불렸다.

 

 

wait()과 signal()의 정의는 이렇다.

 

위의 2개의 연산은 세마포의 정수 값을 변경하는 연산은 반드시 원자적(atomic)으로 수행되어야 한다.

즉, 한 스레드가 세마포 값을 변경하면 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.

 

** 원자적 수행이란 방해없이 반드시 수행되고 동시가 아닌 따로 수행된다고 생각하면 되겠다.

 

유저는 해당 연산에 대해 직접 구현을 하기보다는해당 시스템에서 제공하는 세마포어를 사용하는 것이다.

 

 

---

 

우선 기본적으로 Semaphores, 세마포어는 

Mutex, Mutual Exclusion을 해결한다.

 

 

세마포어는 또한 ordering을 할 수 있다.

프로세스의 실행 순서를 원하는 순서로 설정할 수 있다는 말이다.

 

 

 

 

---

 

 

세마포는 2가지 종류가 있다.

 

1. 카운팅 세마포, Counting

2. 이진 세마포, binary

 

카운팅 세마포의 값은 제한 없는 영역을 가진다.

도메인이 0 이상인 임의의 정수값을 사용한다.

주로 resource counting에 사용된다.

**자원의 개수가 여러개 일 때

 

 

이진 세마포는 mutex lock과 유사하게 동작한다. 

0 과 1의 값만 가질 수 있다.

 

 

카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.

 

각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소한다.

프로세스가 자원을 방출 할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다. 

즉, 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다. 

 

**세마포 값이 0보다 커질 때까지 자원을 사용하려는 프로세스는 봉쇄된다.

 

그리고 예를 하나 들자면

 

 

 

---

 

그 다음에는

세마포 구현에 대해서 알아보자

 

• Thus, the implementation becomes the critical section problem where the wait and signal code are placed in the critical section

    Could now have busy waiting in critical section implementation

        But implementation code is short
        Little busy waiting if critical section rarely occupied

• Note that applications may spend lots of time in critical sections and therefore this is not a good solution

 

• With each semaphore there is an associated waiting queue
• Each entry in a waiting queue has two data items:
1. value (of type integer)
2. pointer to next record in the list

 

• Two operations:
• block – place the process invoking the operation on the appropriate waiting queue
• wakeup – remove one of processes in the waiting queue and place it in the ready queue

 

 

 

세마포 연산 wait() signal() CPU를 점유하면서 대기하는 문제(busy waiting)를 가지고 있다.

문제를 해결하기 위해서 연산의 정의를 또 바꿀 수 있다.

 

 

프로세스가 wait()을 실행하고 세마포 값이 양수가 아닌 것을 발견하면, 프로세스는 반드시 대기해야 한다.

그렇지만 바쁜 대기(busy waiting) 대신에 프로세스는 자신을 일시 중지시킬 수 있다. (block)

CPU를 점유하면서 기다리는 비효율적인 상황을 막는 것이다.

즉, 일시중지 연산(block)은 프로세스를 세마포에 연관된 대기 큐(wait queue)에 넣고, 프로세스의 상태를 대기 상태로 전환한다.

그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위하여 선택한다.

 

 

세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작 되어야 한다. 

프로세스는 wakeup() 연산에 의하여 재시작되는데

이것은 프로세스의 상태를 대기 상태에서 준비 완료 상태로 변경한다.

그리고 프로세스는 준비 완료 큐(ready queue)에 넣어진다. 

 

 

 

---

 

 

다시 위와 같은 정의로 세마포를 구현하기 위해서 재정의하자면?

 

 

 

 

각 세마포는 한 개의 정수 value와 프로세스 리스트 list 포인터를 가진다.

프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가시킨다.

signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워준다.

 

다시 wait() 그리고 signal() 을 재정의 하자면

 

 

**sleep() 연산은 자기를 호출한 프로세스를 일시중지시킨다.

커널은 block을 호출한 프로세스를 suspend시키고 해당 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.

 

**wakeup(p) 연산은 일시중지된 프로세스 P를 다시 실행시킨다.

block된 프로세스 P를 wakeup 시키고 해당 프로세스의 PCB를 ready queue로 옮긴다.

 

 

바쁜 대기를 하는 세마포의 고전적 정의에서는 세마포의 값은 음수를 가질 수 없지만

재정의하면 음수 값을 가질 수 있다.

세마포 값이 음수일 때, 그 절댓값은 세마포를 대기하고 있는 프로세스들의 수이다  

++wait() 연산의 구현에서 세마포의 값의 감소와 검사의 순서를 바꿔서 그렇다.

 

 

대기하는 프로세스들의 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에 의하여 쉽게 구현될 수 있다. 

각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 포인터를 가지고 있다.

 

한정된 대기를 보장하도록 리스트에 프로세스를 추가하고 삭제하는 한 가지 방법은

선입 선출 큐를 사용하는 것으로 세마포가 큐의 머리와 꼬리에 대한 포인터를 모두 가지게 된다.

 

 

같은 세마포에 대해서 두 프로세스가 동시에 wait() 과 signal() 연산들을 실행할 수 없도록 보장해야 한다.

이는 임계구역 문제를 해결해야한다는 뜻인데

코어 모두에 인터럽트를 막는 것은 성능이 떨어지므로 

SMP시스템(Symmetric MultiProcessing System)은 wait()과 signal() 연산이 원자적으로 실행되게 만들기 위하여 compare_and_swap() 이나 스핀락 같은 다른 기법을 사용한다.

 

 

** wait()과 signal()에서 busy waiting를 제거하지 못하는 것은 사실이다.

**busy waiting은 CPU와 메모리를 불필요하게 점유하면서 대기하는 것이다.

 

---

 

하지만 항상 busy waiting이 나쁜 것만은 아닌데

Critical section의 길이가 긴 경우에는 Block/Wakeup이 더 효율적이지만

Critical section의 길이가 짧은 경우에는 Block/Wakeup을 하는 오버헤드가 더 클 수 있어서

해당 프로그램의 특징마다 다를 수 있다.

 

일반적으로는 Block/Wakeup이 더 좋다고 말할 수 있다.

 

---

 

또한 Deadlock 과 Starvation이 발생할 수 있다.

 

Deadlock이란

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상을 말한다.

 

 

예를 들어

P0에서 S를 점유하고 CPU 제어가 P1으로 넘어갔다고 하자.

P1은 Q를 얻을 수는 있지만 S를 얻을 수는 없다.

P1는 CPU를 점유하고 있어도 자원S를 얻을 수 없고 Q는 가지고 있다.

다시 P0로 CPU가 넘어갔을 때도 자원 Q는 P1이 가지고 있기에 P0도 진행될 수 없다.

P1이 Q를 놓으려면 S까지 확보 후 반환할 수 있는데 P0가 가지고 있고

P1이 S를 놓으려면 Q까지 확보후 반환할 수 있는데 P1이 가지고 있다.

 

이렇게 서로가 끝나길 기다리면서 무한하게 대기하는 상태를 교착상태라고 한다.

 

** 위의 상황자체는 자원획득 순서를 동일하게 맞춰주면 해결이 된다.

 

---

 

마지막으로 세마포의 단점을 말하면서 끝내겠다.

세마포의 단점

1. 구현하기 힘듬

2. 정확성(correctness)입증 어려움

3. 자발적 협력(voluntary cooperation)필요

4. 한 번의 실수가 치명적임

-> Monitor라는 기법이 생기는 이유

[컴퓨터(Computer Science)/운영체제(Operation System)] - 동기화, 모니터 : Synchronization, Monitor

 

 

---

 

Starvation은 배고픈 철학자 얘기하면서 설명하겠다.

[컴퓨터(Computer Science)/운영체제(Operation System)] - Dining philosopher problem(식사하는 철학자 문제) 동기화[운영체제]