병행성(Concurrency) : 상호배제와 동기화

운영체제의 핵심 기능 중 하나는 프로세스와 스레드 관리와 연관되어 있다.
대표적으로 다음과 같은 것들이 있다.

• 멀티프로그래밍 : 하나의 CPU로 다수의 프로세스 관리
• 멀티프로세싱 : 다수의 CPU로 다수의 프로세스 관리
• 분산처리 : 다수의 분산된 컴퓨터 시스템에서 수행되는 다수의 프로세스 관리

이러한 분야들에서 핵심은 병행성이다.
병행성은 프로세스를 인터리빙(interleaving, 번갈아가며 수행되지만 사용자들은 동시에 실행되는 것처럼 느낌)한다. 병행성은 프로세스간 통신, 자원에 대한 공유와 경쟁, 동기화, 프로세서 할당 등 다양한 이슈들이 포함된다.

1. 병행성 개요

• 병행 처리의 문제점
  • 전역 자원의 공유가 어렵다.
  • 운영체제가 자원을 최적으로 할당하기 어렵다.
  • 프로그래밍 오류를 찾아내는 것이 어렵다.
• 인터리빙이나 오버래핑으로 인해 발생하는 문제점은 싱글/멀티 프로세서 시스템 모두에서 발생
  • 멀티 프로세서 시스템에서는 병렬 처리로 인한 추가적 문제 발생

2. 병행성의 간단한 예

• 두 개 이상의 스레드(또는 프로세스)들이 동일한 전역 데이터 접근
  
• 공유 함수, 연관된 공유 데이터 집합
  

3. 병행성 관련 용어

• 원자적 연산(atomic operation)

  • 더 이상 분할할 수 없는 단일한 단위로 관리되는 일련의 명령들, 어떤 프로세스도 중간 상태를 볼 수 없고 연산을 중단시킬 수 없다.
  • 명령어들은 수행되거나 되지않거나 둘 중 하나이다.
  • 원자성은 병행 프로세스들에게 고립(isolation)을 보장한다.

• 임계 자원(critical resource)과 임계 영역(critical section)

  • 임계 자원(공유 자원) : 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
  • 임계 영역 : 공유 자원을 접근하는 프로세스 내부의 코드 영역(블록)
  • 만약 어떤 프로세스가 임계영역에서 작업중이라면 즉, 공유 자원을 이용하고 있다면 다른 프로세스는 임계영역에 접근이 불가하다.

• 교착 상태(deadlock)

  • 두 개 이상의 프로세스들이 더 이상 진행할 수 없는 상태
  • 각 프로세스가 다른 프로세스의 진행을 기다리면서 대기할 때 발생한다.

• 라이브락(livelock)

  • 두 개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화시키는 작업만 수행하는 상태
  • 각 프로세스들은 열심히 수행하고는 있지만, 수행하는 작업은 유용한 작업이 아닌 반복적인 상태 변화일 뿐이다.

• 상호배제(mutual exclusion)

  • 한 시점에서 단 하나의 프로세스만이 임계영역에 들어가도록 한다.
    • 한 프로세스가 공유자원을 접근하는 임계영역 코드를 수행하고 있으면,
      다른 프로세스들은 공유 자원에 접근하는 임계영역 코드를 수행할 수 없다는 조건이다.
  • 상호 배제의 보장은 교착상태와 기아문제를 발생시킬 수 있다.

• 경쟁상태(race condition)

  • 두 개 이상의 프로세스가 공유 자원을 동시에 접근하려는 상태
  • 최종 수행 결과는 프로세스들의 상대적인 수행 순서에 따라 달라질 수 있다.

• 기아(starvation)

  • 특정 프로세스가 수행 가능한 상태임에도 불구하고 매우 오랜 기간 동안 스케줄링 되지 못하는 경우

4. 상호 배제 요구조건

• 상호 배제 강제 - 반드시 단 하나의 프로세스만이 임계영역에 진입할 수 있다.
• 임계영역이 아닌 코드에서 수행이 중지된 프로세스는 다른 프로세스의 수행을 간섭해선 안된다.
• 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미뤄져서는 안된다. 즉, 기아 상태, 교착 상태가 발생해선 안된다.
• 임계영역이 비어있고 임계영역에 진입하려고 하는 프로세스가 지연되어서는 안된다.
  (즉시 진입이 가능해야 한다.)
• CPU 개수나 상대적인 프로세스 수행 속도에 대한 가정은 없어야 한다.(예측할 수 없음)
• 임계 영역에 들어간 프로세스는 일정 시간 동안만 임계영역에 존재할 수 있다.
  (일정 시간 후에 임계 영역 밖으로 나와야 한다.)

5. 상호배제 요구조건을 만족시키는 접근 방법들

• 소프트웨어적 방법 : 병행 수행하는 프로세스들이 모든 책임 및 권한을 갖는 방법
• 하드웨어적 방법 : 특별 용도로 설계된 기계어 이용
• 운영체제나 프로그래밍 언어 수준에서 보장하는 방법

1) 상호배제를 보장하기 위한 소프트웨어적 접근 방법

운영체제나 프로그래밍 언어 차원의 지원 없이 프로세스간 협력을 통해 직접 상호 배제를 보장한다.
수행 부하가 크고, 잘 설계되지 않았을 경우 오동작 가능성이 높다. 하지만 이 방법을 앎으로써 병행 처리의 복잡도와 상호배제 윤리를 잘 이해할 수 있다.

Dekker 알고리즘

[1] 첫번째 시도

turn 이라는 전역변수를 선언하여 turn 의 값이 자신의 프로세스 번호와 같다면 임계영역을 수행할 수 있도록 하는 방법으로 바쁜 대기를 사용한다는 점도 단점이지만 느린 프로세스를 기준으로 수행속도가 맞춰지게 된다. 또한 한 프로세스가 실행중에 임계영역 내에서 작업이 중단되면 다른 프로세스는 영구히 기다리게 된다.

[2] 두번째 시도

flag를 정의하여 flag[0]은 P0에, flag[1]은 P1에 대응시키고 임계영역에 진입하려는 프로세스는 flag값을 계속 보다가 값이 false가 되면 자신의 flag값을 true로 만들고 임계영역에 들어가는 방식으로 한 프로세스가 임계 영역 안에서 실패하거나 자신의 flag를 true로 바꾼 후 임계 영역에 들어가기 바로 전에 실패하면 다른 프로세스는 영구히 block된다. 또한 상호배제 역시 갖추어지지 않았다.

ex)

P0는 while 문을 실행하여 flag[1]이 false임을 확인
P1는 while 문을 실행하여 flag[0]이 false임을 확인
P0는 flag[0]을 true로 하고 임계영역에 진입
P1는 flag[1]을 true로 하고 임계영역에 진입
이렇게 되면 둘 다 임계영역에 진입하게 됨 = 상호배제 X

[3] 세번째 시도

만약 P0가 flag[0]를 true로 설정하면, P1이 임계 영역에 들어갔다가 나올 때까지 자신의 임계영역에 있을 수 없다. P0가 자신의 flag를 설정할 때 P1이 이미 자신의 임계영역에 있다면 P0는 P1이 임계영역을 떠날 때까지 while문에서 block되는 방식으로 상호배제를 보장하지만 만약 두 프로세스가 각각 while문을 실행하기 전에 자신들의 플래그를 true로 설정하게 되면 각 프로세스는 상대방이 임계영역에 들어갔다고 판단하고 이로인해 교착상태가 발생한다.

[4] 네번째 시도

좀 더 각 프로세스가 양보하게 하는 방식으로 문제를 해결하기 위해 각 프로세스는 flag에 임계영역에 들어가려는 의도를 나타내지만 다른 프로세스에게 양보하기 위해 플래그를 재설정할 준비가 되어있는 방식으로 올바른 해결책에 가까우나 결점을 가지고 있다.

ex)

P0는 flag[0]을 true로 설정
P1는 flag[1]을 true로 설정
P0는 flag[1]를 검사
P1는 flag[0]를 검사
P0는 flag[0]을 false로 설정
P1는 flag[1]을 false로 설정
P0는 flag[0]를 true로 설정
P1는 flag[1]를 true로 설정

이러한 순차가 무한히 확장될 수 있고, 프로세스도 임계영역에 들어가지 못할 수 있다. 확률은 적지만 즉 라이브락이 생기게 된다.

피터슨 알고리즘

전역 배열 변수 flag가 상호 배제와 관련된 각 프로세스의 위치를 나타내며 전역 변수 turn은 병행 수행에 의한 충돌을 해결해준다. P0를 예로 들어 알고리즘을 돌려보면 P0이 flag[0]을 true로 설정, P1은 자신의 임계영역에 들어갈 수 없다. 반면에, 서로 임계영역에 들어가지 못하도록 방지하는 것도 막을 수 있다. P0가 자신의 while 문에서 블록되어 있다면, 이것은 flag[1]은 true이고 turn = 1임을 의미한다. P0는 flag[1]이 false가 되거나 turn이 0이 되면 자신의 임계영역에 들어갈 수 있게 된다.

2) 상호배제를 보장하기 위한 하드웨어적 접근 방법

인터럽트 금지(Interrupt Disable)

상호 배제를 보장할 수 있는 가장 간단한 방법은 프로세스가 인터럽트 되지 않도록 하는 것이다
싱글 프로세서에서 병행 처리(concurrent processing)되는 프로세스들은 인터리빙되기 때문이다.

또한 프로세스는 운영체제 서비스를 호출하거나 인터럽트 될 때까지 계속 실행하기 때문에 인터럽트가 발생하지 않으면 한 프로세스의 지속적인 실행을 보장 가능하다.
이를 위해 시스템 커널에서 인터럽트를 허용하거나 비허용할 수 있는 기본 인터페이스를 제공한다.

while(true){
// 인터럽트 금지
// 임계 영역
// 인터럽트 허용
// 임계 영역 이후 코드
}

• 멀티프로세서 시스템에서는 효과 없음

단점

• 부하가 크다.
  인터럽트 비허용 시, 그 사이 외부에서 발생하는 이벤트에 대한 처리와 다른 프로세스에 대한 스케줄링 등 모든 기능이 중지되어 시스템 수행 효율이 확연하게 감소할 가능성이 높다.
• 멀티프로세서 시스템에서는 올바른 접근 방법이 아니다.
  두 개 이상의 프로세서를 가지는 시스템에서는 인터럽트가 금지되어도 서로 다른 프로세스가 공유 자원을 동시에 접근할 수 있다. 즉, 보장하지 못한다.

특별한 기계 명령어

멀티 프로세서 환경에서 여러 프로세서들은 공통의 주기억 장치를 공유하며, 이때 모든 프로세서는 동등한 관계에서 독립적으로 동작한다. (인터럽트 기법으로 상호배제 보장 불가)
하드웨어 수준에서 특정 메모리 주소가 접근되고 있을 때, 같은 위치에 대한 접근 요청은 차단된다는 것에 기반해 상호배제를 보장하기 위한 두 가지 명령어가 구현된다. 이때 기계 명령어는 두 개의 기능을 원자적으로 처리한다.
원자적 : 명령어 수행 도중 인터럽트 되지 않고 마치 하나의 단위인 것처럼 처리될 수 있다.

1. Compare & Swap 명령어

compare_and_swap() : 테스트하려는 값과 저장된 값을 비교한다.

이 함수는 원자적으로 수행되기 때문에 중간에 중단되는 경우는 없다.
대부분 모든 프로세서에서 지원하며, 대부분의 운영체제에서 병행성을 위해 이 명령어를 사용한다.

2. Exchange 명령어

exchange() : 레지스터 값과 메모리에 들어있던 값을 서로 교체하는 기능 수행

3. Compare & Swap, Exchange 명령어

4. Compare & Swap, Exchange 명령어를 이용한 상호배제 보장

Compare & Swap 명령어를 이용한 상호배제 보장 설명

while(compare_and_swap(bolt, 0, 1) == 1){ // 제일 처음 진입한 프로세스가 bolt를 1로 변경한 뒤
/*임계영역*/; // 임계 영역에서 수행, 이 때 진입을 하려는 프로세스들은 bolt가 1이기 때문에 위의 while문에서 대기해야한다.
bolt = 0; // 수행이 끝나면 bolt를 0으로 바꾸고 임계영역을 나간다.

Exchange 명령어를 이용한 상호배제 보장 설명

key는 1, bolt는 0일 때 exchange를 수행하면 key는 0, bolt는 1로 바뀐다. 임계영역에 진입해 있는 프로세스가 있는 경우, 새로 진입하려는 프로세스가 exchange(&keyi, &bolt)를 수행하고자 하면 수행 결과 key는 1, bolt는 0이 되어 계속 do while문을 돌게 된다. 진입했던 프로세스가 임계영역에서 빠져나올 때 bolt를 0으로 바꾸고 나서야 새로운 프로세스가 다시 임계영역에 진입가능하다.

3. 기계 명령어 접근 방법의 특성

장점

• 싱글/멀티 프로세서에 적용 가능
• 싱글 프로세서 시스템 뿐만 아니라 공유 메모리를 사용하는 멀티 프로세서 시스템에서도 사용가능하다.
• 간단하고 검증이 쉽다.
• 서로 다른 변수를 사용하면 다중 임계 영역을 지원할 수 있다.

단점

• 바쁜 대기를 사용한다.
  -> 임계영역에 진입하는 것을 대기하고 있는 프로세스는 처리기를 계속 사용하게 된다.

  바쁜 대기란 임계영역에 진입하기 위한 허가를 획득할 때까지 변수를 테스트하는 명령을 반복 실행하며 대기하는 것을 말한다.

• 기아가 발생할 수 있다.
  -> 한 프로세스가 임계영역에서 빠져나올 때, 대기하고 있던 다수의 프로세스 중 하나만 다시 임계영역에 진입이 가능한데, 이 때 각 프로세스의 길이나 특성, 대기시간 등을 고려하지 않기 때문에 무한정 기다리는 프로세스가 생길 수도 있다.

• 교착상태에 빠질 수 있다.

  교착상태 발생가능한 시나리오

  1. 싱글 프로세서 시스템에서 P1 이라는 프로세스가 임계영역에 진입한다.
  2. 그때 P2 라는 P1보다 우선순위가 높은 프로세스가 생겨 운영체제가 P2를 스케줄하여 P2에게 자원을 할당하려 할 때 P2와 P1이 같은 자원을 사용하려 하면 P2는 상호배제조건에 의해 바쁜 대기를 수행한다.
  3. 이때 P2가 계속 프로세서를 점유하고 있기 때문에 우선순위가 높은 P2로 인해 P1은 다시 스케줄링될 수 없다. -> P2가 실행상태에 있기 때문이다.

소프트웨어적 방법과 하드웨어적 방법은 모두 단점을 갖고 있기 때문에 새로운 해결책(운영체제, 프로그래밍 언어 수준에서 상호배제를 보장하는 방법)이 필요하다.

3) 운영체제와 프로그래밍 언어 수준에서 상호 배제를 보장하는 방법

1. 세마포어(semaphore)

• 임계영역에 접근하는 프로세스들을 제어하는 데 사용한다.
• block(수면)과 wake up(깨움)을 지원한다.
• 세마포어란 프로세스 간에 시그널을 주고받기 위해 사용되는 정수 값을 갖는 변수로 다음 3가지 인터페이스를 통해 접근할 수 있다.
  • Initialize(초기화 연산) : 최초에 세마포어 값을 음이 아닌 값으로 초기화한다.
  • Decrement(semWait, 대기 연산)
    • 세마포어 값을 하나 감소시킨다.
    • 값이 음수가 되면 semWait를 호출한 프로세스는 block 상태로 바꾼다.
    • 음수가 아니면 해당 프로세스는 임계영역에 접근하여 연산을 계속 수행할 수 있다.
  • Increment(semSignal, 시그널 연산)
    • 연산을 마친 프로세스는 이 함수를 호출해 세마포어 값을 하나 증가시킨다
    • 값이 양수가 아니면(<=0) semWait 연산으로 block된 프로세스를 깨운다.
• 이진 세마포어는 세마포어 값을 0또는 1만 가질 수 있는 세마포어이다.

2. 뮤텍스(Mutex)

• 이진 세마포어와 유사
• 차이점은 뮤텍스에 락을 획득(값을 0으로 설정)한 프로세스가 반드시 그 락을 해제(값을 1로 설정)해야 하는 것이다.

3. 세마포어 종류

1) 카운팅(범용) 세마포어

• 여러 개의 공유 자원에 대한 액세스를 제어할 목적
• Proberen(시도하다), Verhogen(증가시키다) 연산

2) 이진(바이너리) 세마포어

• 이진 세마포어 : mutex 역할

4. 세마포어를 이용한 상호배제

세마포어 이용한 상호배제 동작 예1

• 가정 : 3개의 프로세스 존재
  

5. 세마포어를 구현

6. 세마포어의 단점

• 일반적으로 프로세스가 세마포어를 감소시키기 전까지는 그 프로세스가 block될지 안될지 알 수 없다.
• 싱글 프로세서 시스템에서 프로세스가 세마포어를 증가시키고 block된 프로세스를 까우면, 이 두 프로세스 모두 수행가능 상태가 되어 누가 먼저 수행될 지 알 수 없다.
• 세마포어에 시그널을 보낼 때, 우리는 다른 프로세스가 대기 중인지 여부를 알 필요가 없다. block된 프로세스의 개수가 0또는 1일 수 있다.

7. 생산자/소비자(producer/consumer) 문제

생산자 소비자 문제는 병행 프로세스의 특성과 해결 방법을 논의할 때 자주 사용되는 문제로, 여러 개의 프로세스를 어떻게 동기화할 것인가에 대한 고전적인 문제이다. 한정 버퍼(bounded-buffer) 문제라고도 한다.

생산자가 데이터를 생성하면 소비자는 그것을 사용(소비)한다. 컴퓨터 세계에서의 웹 서버와 웹 클라이언트로 들 수 있다. 웹 서버가 데이터를 생산해 웹에 관련되어 보여주는 작업들을 수행하고, 웹 클라이언트는 웹 주소로 젒고해 화면을 통해 보게 되는 형태의 소비 작용을 한다.

일반적으로 생산하는 속도와 소비하는 속도에 차이가 난다. 실제로 생산되는 속도가 소비하는 속도보다 빠른 경우가 많아서 생산된 데이터는 바로 소비되지 못한다. 이를 보완하기 위해 생산된 데이터를 보관하는 버퍼라는 공간이 존재한다. 그리고 현실 시스템에서는 버퍼의 크기가 유한하다. 이렇게 유한한 크기의 버퍼에 생산자가 데이터를 생산하면 버퍼에 보관을 하게 되는데 이때 저장할 공간이 없는 문제가 발생할 수 있다. 소비자는 버퍼에서 데이터를 빼내어 사용한다. 이 때 소비할 물건이 없는 문제가 발생할 수 있다.

즉, 생산자는 데이터를 만들어 버퍼에 저장해나가고, 소비자는 버퍼에 있는 데이터를 꺼내 소비하는(비우는) 프로세스이다.

이때 버퍼는 공유자원이므로 버퍼에 대한 접근 즉, 저장하고 꺼내는 일들이 상호배제 되어야한다.
또한, 버퍼가 꽉 차있을 때는 생산자가 기다려야하고, 버퍼가 비었을 때는 소비자가 기다려야한다.

1. 생산자/소비자 문제 정의1 (무한 버퍼)

• 병행 수행되는 생산자와 소비자
• 무한 공유 버퍼

1) 이진 세마포어를 이용한 방법(무한 버퍼)

1-1) 부정확한 버전 - 코드

1-2) 부정확한 버전 - 동작 과정

2) 일반(범용) 세마포어를 이용한 해결 방법

만약 소비자가 먼저 실행될 경우, 세마포어 n의 값이 음수가 되면서 block에 걸리고 생산자와 실행되어 버퍼를 채우며 n의 값을 올려 소비자의 block을 푼다.

2. 생산자/소비자 문제 정의 2

• 병행 수행되는 생산자와 소비자
• 유한 공유 버퍼

1) 범용 세마포어를 이용한 해결 방법(유한 버퍼)

무한 버퍼와 같은 원리로 작동을 하며 무한 버퍼와는 달리 유한 버퍼이므로 버퍼가 꽉 찰 때를 표시해줄 수 있는 e값이 있다. e가 꽉 찬 상태 즉, e가 음수가 되면 block이 걸리게 되며 소비자만이 작동하게 된다.

7. 모니터

• 모니터란 프로그래밍 언어 수준에서 제공되는 구성체(라이브러리, 클래스)
• 세마포어와 동일한 상호배제 기능을 제공하고 보다 사용하기 쉽다는 장점을 가지고 있다.

1) 시그널 기반 모니터의 특징

• 외부에서 변수에 대한 직접 접근이 허용되지 않으므로 지역 변수는 프로시저(명령문의 집합, 자세히는 쿼리문의 집합)로 접근 해야된다.
• 프로세스는 모니터의 프로시저 중 하나를 호출하여 모니터 내부로 들어간다.
• 한 시점에 단 하나의 프로세스만이 모니터에 접근 가능하다.
  모니터가 이미 사용중이면 그 자리가 빌 때까지 대기한다.
• 구조
  
• 동기화 : 조건 변수(Condition variables)
  • cwiait(c) : 호출한 프로세스를 조건 c에서 일시중지 시킨다.
  • csignal(c) : cwait에 의해서 중지되었던 프로세스를 재개시킨다.

2) 모니터를 이용한 생산자/소비자 문제 해결 방법

2-1) 프리미티브 구현 예

2-2) append()/take() 사용 예

8. 메세지

• 메시지 전달(massage passing) 인터페이스
• 두 가지 기본 기능이 있다.
  • send(destination, message) : 메시지 전송
  • receive(sourve, message) : 메시지 받기
• 기본적으로 정보 교환을 위해 사용 -> mailbox(port)
• 또한 상호배제와 동기화를 위해 사용 가능 -> blocking operation

메시지를 이용한 상호 배제

메시지 전달을 이용한 생산자/소비자 문제 해결 방법

위의 프로그램에서는 mayconsume과 mayproduce라는 두 개의 메일박스를 사용한다. 생산자가 데이터를 만들면 이를 메시지로 mayconsume에 보낸다. 이 메일박스에 적어도 하나의 메시지가 존재하면 소비자는 계속하여 수행될 수 있다. 코드가 시작될 때 mayconsume은 전역 변수 capacity에 의해 용량이 정해지고 mayproduce는 capacity만큼 null로 초기화된다.

메세지를 사용하면 단지 시그널만을 전달하는 것이 아닌 데이터를 전달할 수 있고 또 매우 유연하여 두 개의 메일 박스에 접근만 가능하면 다수의 생산자 소비자도 가능하다. 또한 분산환경에서도 사용이 가능하다.

9. 판독자/기록자(readers/writers) 문제

생산자/소비자 문제와 같이 병행성 기법을 테스트할 때 사용하는 문제이다. 판독자/기록자 문제의 조건을 이러하다.

9-1) 판독자/기록자 문제 정의

• 병행 수행되는 판독자와 기록자
• 공유 자원(파일, 데이터베이스)

9-2) 요구 조건

1. 여러 판독자들이 공유 데이터를 동시에 읽을 수 있다.
2. 한 순간에는 단 하나의 기록자만이 공유 데이터를 변경할 수 있다.
3. 기록자가 데이터를 변경하고 있는 동안에는 판독자가 그 파일을 읽을 수 없다.

9-3) 세마포어를 이용한 판독자/기록자 해결방법 : 판독자(reader) 우선

보기에서는 판독자와 기록자 각각 하나만을 보여주지만 판독자와 기록자가 늘어나도 이 방법을 적용할 수 있다. 기록자가 데이터를 갱신할 때 상호 배제를 위해 wsem을 사용하면, 결국 임의의 한 기록자가 공유 데이터 영역을 사용하고 있는 동안 다른 기록자/판독자는 그 영역을 사용할 수 없게 된다. 기록자와 같이 판독자도 wsem을 사용하지만 다수의 판독자를 허용하기 위해 처음 읽기를 시도한 판독자만 wsem에 대한 semWait를 호출한다. 현재 읽기 중인 판독자가 없을 때는 읽기를 시도하는 최초의 판독자만 wsem을 사용한다는 것이고, 그 이후의 판독자는 wsem에 의한 semWait를 호출하지 않아도 된다는 것이다. 전역 변수 readcount 는 판독자의 수를 관리하는 것에 이용되고, 이 변수에 대한 상호배제를 위해 세마포어 x가 이용된다.

9-4) 세마포어를 이용한 판독자/기록자 해결방법 : 기록자(writer) 우선

x : readcount 보호
rsem : writer가 먼저 들어가 있을 때 첫 번째 reader가 기다리는 세마포어
z : writer가 먼저 들어가 있을 때 두 번째 이후의 reader가 기다리는 세마포어
y : writecount 보호
wsem : reader 건 writer건 먼저 들어온 프로세스가 갖는 세마포어 

9-5) 메시지 전달을 이용한 해결 방법

병행성 : 교착상태와 기아상태

1. 교착상태 정의

• 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.
• 2개 이상의 프로세스들이 공유 자원에 대한 경쟁이나 통신 중에 발생한다.
• block 상태에 놓여 필요한 자원을 이용하기 위해 기다릴 때 발생한다.
• 영속적인 block 상태가 된다.
• 제한된 자원의 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행 처리 기술과 자원 공유에 따른 부작용이다.

2. 교착상태가 발생하기 위한 필요충분조건

• 상호배제 조건(mutual exclusion) : 한 순간에 한 프로세스만이 자원을 사용할 수 있어야 한다.
• 점유대기 조건(hold and wait) : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다려야 한다.
• 비선점 조건(no preemption) : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제로 빼앗을 수 없다.
• 환형 대기 조건(circular wait) : 프로세스들 간에 닫힌 연결이 존재한다. 자원 할당 그래프에서 환형이 만들어지는 것이다.
  

3. 교착상태 예방(deadlock prevention)

교착상태가 일어나는 상호배제, 점유대기, 비선점 조건들을 허용하지 않거나 직접적으로 환형대기가 생기지 않도록 하는 것이다.
즉, 교착상태가 발생하기 위한 4가지 필요충분 조건 중 하나를 설계 단계에서 배제하는 방법이다.

간단 정리

• 상호 배제 : 운영체제에서 반드시 보장해주어야 함
• 점유 대기 : 프로세스가 필요한 모든 자원을 한꺼번에 요청
• 비선점 : 프로세스가 새로운 자원 요청에 실패하면 기존의 자원들을 반납한 후 다시 요청 or 운영체제가 강제적으로 자원을 반납시킴
• 환형 대기 : 자원 할당 순서(자원 유형)를 미리 정해두면 없앨 수 있음

1) 상호 배제

시스템을 설계할 때 상호 배제 조건을 없앨 수는 없으므로 상호 배제가 필요시에 운영체제가 이를 지원해주어야 한다.(반드시 보장해 주어야 한다.)

2) 점유 대기

프로세스는 자신이 사용할 모든 자원을 한순간에 요청하는데, 만일 모든 자원을 할당받을 수 있으면 계속 수행된다.
반면 하나의 자원이라도 할당 받지 못하면, 어떠한 자원도 할당받지 않은 채 대기하도록 하는 것이다.
이 방법을 사용하면 점유 대기는 없앨 수는 있으나 세 가지 비효율성이 생긴다. 첫째는 프로세스가 자원을 할당 받을 때까지 계속 기다려야한다는 것, 둘째는 한꺼번에 받은 자원 중 일부는 프로세스가 끝날 때 쯤에 사용되기 때문에 자원이 효율적으로 사용되지 않는다는 것, 셋째는 프로세스가 미래에 필요로할 자원을 미리하는 것은 어렵다는 것이다.

즉, 점유대기를 없애기 위해서는 모든 수준(모듈, 프로세서, 스레드 등등)이 요구하는 모든 자원을 미리 알아야 한다.

3) 비선점

비선점 조건은 두 가지의 방법으로 없앨 수 있다. 첫째는 자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면, 일단 자신의 점유한 자원을 반납하고 이후 프로세스가 원래 자원과 새로 원하는 자원을 함께 요청하는 것, 둘째는 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면 운영체제가 우선순위에 따라 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에 할당할 수 있다.

비선점을 없애는 것은 자원의 상태를 복구하고 저장하기 쉬운 자원에 사용할 수 있다. ex) 프로세서

4) 환형대기

환형대기 조건들은 자원들의 할당 순서를 정하면 없앨 수 있다. 예를 들어 프로세스가 자원 R을 할당받았다면, 이후 이 프로세스는 자원 R 다음 순서를 갖는 자원들을 요청할 수 있는 것이다. 즉 자원마다 할당순서를 정해 R1 < R2 인 할당 순서를 정했다고 하면 R1을 할당받으면 그 다음 R2가 할당될 수 있게 된다. 만약 P1, P2 프로세스 중 P1가 R1을 할당하고 R2를 요청했다. 여기서 교착상태가 되려면 P2가 R2를 할당하고 R1을 요청해야하는데 이는 운영체제에서 정한 할당 순서에 위배되기 때문에 나타날 수 있다.

환형 대기를 없애는 일은 프로세스의 수행 지연과 불필요한 자원 할당 거부를 생기게 할 수 있다.

4. 교착상태 회피

• 예방과 회피의 차이점
  • 교착상태 예방은 미리 교착상태를 생기게 하는 조건을 없애는 것이지만 이는 자원의 사용과 프로세스 수행에 비효율을 만든다.
  • 교착상태 회피는 상호배제, 점유대기, 비선점을 허용하지만 그렇다고 자원 할당 순서를 미리 정하지도 않는다.
  • 그 대신, 자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려하는 방법이다.

회피 방법

1-1) 프로세스 시작 거부(Process Initialization Denial)

프로세스가 시작하려할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작시키지 않는 것이다.

2) 자원 할당 거부(Resource Allocation Denial)

수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는 것이다.

• 자원을 할당할 때 교착상태가 발생할 가능성이 있는지 여부를 동적으로 판단
• 교착상태의 가능성이 없을 때 자원을 할당한다.
  즉, 안전한 상태를 계속 유지할 수 있을 때에만 자원을 할당한다.

자원할당을 거부하는 방법 : 은행원 알고리즘

은행원 알고리즘에서의 시스템 상태 구분

• 안전 상태(safe state)
  : 교착상태가 발생하지 않도록 프로세스들에게 자원을 할당할 수 있는 할당 경로(진행 경로)가 존재
• 불안전 상태(unsafe state) : 할당 경로(진행 경로)가 없음

먼저 (a) 상태를 보자.
프로세서 1~4가 각각 R1~3에 대한 자원 요구를 “요구 행렬 C”에서 볼 수 있다. 그리고 현재 P1~4 가 각각 할당받은 자원을 “할당 행렬A”에서 볼 수 있고, 아직 할당 받지 못해서 필요한 자원을 “C-A”에서 볼 수 있다.
R1~3에 대한 총 자원은 R표에서 볼 수 있다. 그리고 R1~3에서 사용가능한 벡터가 V표에 나와있다.

그럼 여기서 과연 이 상태가 안전한지 불안전한지 살펴보면,
먼저 A상태에서 가용 가능한 자원으로 끝낼 수 있는 프로세서는 P2 이므로, P2에게 부족한 R3 자원을 1 주면 P2는 끝나고 자신이 가진 자원을 반납하고 B 상태로 넘어간다.
B에서는 P1을 완료하여 P1을 끝내고 C상태로 넘어간다.
C에서는 P3을 끝낼 수 있으므로 P3을 끝내고 D상태로 넘어간다. D상태에서 P4를 끝내면 수행이 끝난다. 결론적으로 모든 프로세서를 모두 무사히 끝내게 되므로 안전한 상태이다.

위의 경우에서 불안전 상태로 판별나려면?

만약 초기상태에서 P2가 아닌 P1에게 자원을 할당시켰다면, 교착상태가 일어나게 되어 불안전한 상태가 되었을 것이다.
이처럼 미리 어떠한 프로세서에 자원을 할당해야 안전한 상태를 유지할 수 있을지 볼 수 있다.

3) 교착상태 회피의 장단점

장점

• 교착상태 예방에 비해서 자원 할당이 훨씬 자유롭기 때문에 시스템에서 자원 효율이 높아진다.

단점

• 각 프로세스들이 사용할 최대 자원 요구량을 운영체제에게 미리 알려줘야 한다
• 프로세스들은 서로 독립적으로 수행 순서 같은 종속 관계가 없어야 한다
• 자원 개수가 고정적이여야 한다
• 자원을 선점한 상태로 종료되는 프로세스가 없어야 한다

5. 교착상태 발견(deadlock detection)

교착상태 발견은 자원 할당이 요구될 때마다 매번 수행할 수 있고, 주기적으로 가끔씩 수행될 수도 있다.

교착상태 발견 알고리즘

1) 할당 행렬 A에서 행의 값이 모두 0인 프로세스를 우선 표시한다.
2) 임시 벡터 W를 만든다. 그리고 현재 사용 가능한 자원의 개수(결국 가용 벡터 V의 값)를 벡터 W의 초기값으로 설정한다.
3) 표시되지 않은 프로세스들 중에서 수행 완료 가능한 것이 있으면 (요청 행렬 Q에서 특정 행의 값이 모두 W보다 작은 행에 대응되는 프로세스)이 프로세스를 표시한다. 만일 완료 가능한 프로세스가 없으면 알고리즘을 종료한다.
4) 단계 3의 조건을 만족하는 행을 Q에서 찾으면, 할당 행렬 A에서 그 행에 대응되는 값을 임시 벡터 W에 더한다.그리고 3단계를 다시 수행한다.

쉽게 설명
1. P4는 할당 받은 자원이 없다. 따라서 P4에 마킹을 한다.
2. 가용벡터 V는 (0 0 0 0 1)로 초기화 된다.
3. P3의 요청을 만족할 수 있으므로 P3에 마킹한다. 가용벡터 V가 (0 0 0 1 1)이 된다.
4. 마킹이 되지 않은 프로세스들 중에서 가용벡터로 끝낼 수 있는 프로세스가 존재하지 않으므로 알고리즘이 종료된다.

알고리즘 종료 후에도 P1과 P2는 마킹되지 않은 상태로 남아 있으며 이는 P1과 P2가 교착상태임을 뜻한다.

6. 교착상태 회복 알고리즘(deadlock recovery)

교착상태가 발견되면 그것을 해결하기 위한 기법이 필요하다.

회복 알고리즘 종류

1) 교착상태에 포함된 모든 프로세스들을 종료시키는 것
→ 생각보다 많은 운영체제가 사용한다.
2) 교착상태에 포함된 각 프로세스의 수행을 일정 체크포인트 시점으로 롤백한 후 다시 수행시키는 것
→ 교착상태가 다시 발생할 가능성이 존재한다.하지만 병행처리의 비결정 특성으로 인해 확률이 낮기는 하다.
3) 교착상태가 없어질 때까지 교착상태에 포함된 프로세스들을 하나씩 종료시키는 것
→ 종료시키는 프로세스는 비용이 가장 적은 것부터 종료된다. 하나씩 종료시키면서 발견 알고리즘을 실행 시킨다.
4) 교착상태가 없어질 때까지 교착상태에 포함된 자원을 하나씩 선점시키는 것
→ 자원은 비용이 가장 적은 것부터 선택한다.
자원을 선점시키고 발견 알고리즘을 통해 교착상태가 사라지면 그 프로세스를 자원을 할당 받기 전으로 되돌린다.
5) 종료(또는 선점될) 프로세스 선택 기준

• 지금까지 사용한 프로세서 시간이 적은 프로세스부터
• 지금까지 생산한 출력량이 적은 프로세스부터
• 이후 남은 수행시간이 가장 긴 프로세스부터
• 할당 받은 자원이 가장 적은 프로세스부터
• 우선 순위가 낮은 프로세스부터

7. 통합적인 교착상태 전략

• 교착상태 예방, 회피, 발견
  

8. 식사하는 철학자 문제 : 교착상태를 다루는 문제

이 문제는 병행 프로그래밍의 어려움을 다시금 느끼게 될 수 있는 공유 자원을 통한 협동의 대표적인 문제이다.

문제 정의

• 원탁 테이블 가운데에는 스파게티가 담긴 큰 그릇이 하나있다.
• 철학자가 개인적으로 사용하는 접시가 5개 있고, 접시 양쪽에는 포크가 있다. (결국 테이블 위에는 5개의 포크가 존재한다.)
• 철학자는 배가 고프면 자신의 정해진 위치로 가서 큰 그릇에 담긴 스파게티를 자신의 접시에 담아 먹는다.
• 철학자들은 스프게티를 먹기 위해 반드시 포크 2개를 사용해야 한다.
• 고려되어야 할 것
  • 임계영역이 지켜져야 한다 : 여러 철학자가 동시에 같은 포크를 사용할 수 없다. (상호 배제)
  • 교착상태나 기아에 빠져서는 안된다 : 어떤 철학자도 굶어 죽어서는 안된다
  • 즉, 교착상태도 없어야 하고, 굶어 죽지도 않아야 한다.

1) 세마포어를 이용한 해결 방법 - 교착상태 발생

1. wait(fork[i]) : 철학자는 우선 왼쪽에 있는 포크를 집는다.
2. wait(for[i+1]) : 이후 오른쪽에 있는 포크를 집는다.
3. eat() : 식사를 한다.
4. sigal(fork[i+1]), signal(fork[i]) : 식사 이후, 철학자는 두 개의 포크들을 식탁에 다시 내려놓는다.

이러한 방법은 교착상태를 유발한다는 문제점이 있다.
즉, 모든 철학자들이 동시에 식탁에 앉고 동시에 왼쪽 포크를 집었다고 가정하면, 오른쪽 포크를 집으려 해도 거기에는 포크가 없게 된다. 결국 아무도 식사를 하지 못하게 되는 것이다.

그 외 방법

• 교착상태를 피하기 위해 포크를 5개 더 구입하는 방법
• 포크 하나로 스파게티 먹는 법을 가르치는 방법
• 한 번에 최대 4명까지만 식탁에 앉을 수 있게 제한하는 방법

2) 세마포어를 이용한 다른 해결 방법 - 교착상태 발생하지 않음

• 한 번에 최대 4명까지만 식탁에 앉을 수 있게 제한하는 방법

3) 모니터를 이용한 해결 방법

4) 병행성 기법 사례 - 유닉스, 리눅스

유닉스 병행성 기법

• 프로세스 간 통신 (IPC : InterProcess Communication)
  • 시그널(Signal)
  • 파이프(Pipe)
    
  • 메시지 전달(Message passing)
    
  • 공유 메모리(Shared Memory)
    
  • 세마포어(Semaphore)

5) 리눅스 병행성 기법

• 유닉스 병행성 기법 지원
• 원자적 연산 : 중단/간섭없이 실행되는 작업이다.
• 스핀락(spinlock)
  • 한 번에 하나의 스레드만 스핀락을 획득할 수 있다.
  • 다른 스레드는 lock을 획득할 수 있을 때까지 계속 시도(spinning)한다.
  • 기본 스핀락, 읽기-쓰기 스핀락
• 세마포어
  • 이진 세마포어, 카운팅 세마포어, 판독기/작성기(reader-writer) 세마포어
• 장벽(barrier)
  • 명령이 실행되는 순서를 강제로 시행하기 위해
    
    
    
    

참고
https://sunday5214.tistory.com/7
https://leeys96.github.io/os/concurrency_mands1/
http://mm.sookmyung.ac.kr/~bigrain/class/2011/mmso/StallingsOS6e-Chap05.pdf
http://mm.sookmyung.ac.kr/~bigrain/class/2011/mmso/StallingsOS6e-Chap06.pdf
https://chelseashin.tistory.com/40
https://copycode.tistory.com/67
https://daekyojeong.github.io/posts/OSCourse3/