📌 병행성(Concurrency)

운영체제의 설계의 핵심은 모두 프로세스와 쓰레드와 연관이 있으며 대표적으로 다음이 있다.

• 멀티프로그래밍: 단일처리기(프로세서) 시스템 상에서 다수의 프로세스 관리
• 멀티프로세싱: 멀티프로세서 시스템 상에서 다수의 프로세스 관리
• 분산처리: 다수의 분산된 컴퓨터 시스템들 상에서 수행되는 다수의 프로세스 관리 (대표적인 예로 클러스터 시스템이 있다)

그리고 운영체제의 설계의 핵심은 병행성(concurrency)이다.
병행성이란 여러 계산을 동시에 수행하는 시스템의 특성으로 프로세스간 통신, 자원에 대한 공유와 경쟁, 프로세스 활동들의 동기화, 프로세스에 대한 처리기 시간 할당 등 다양한 이슈를 포함한다.

병행성 관련 주요 용어

원자적 연산(atomic operation) : 명령어들로 구성된 함수 또는 액션으로 더 이상 분할할 수 없는 단위 어떤 프로세스도 중간 상태를 볼 수 없고 연산을 중단할 수 없다 이 명령어들은 수행되거나 되지않거나 둘중 하나이다.

임계영역(critical section) : 공유 자원을 접근하는 프로세스 내부의 코드 영역, 두개의 프로세스가 임계영역에 들어가서는 안된다.

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

라이브락(livelock) : 두개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화 시키는 작업만 하는 상태,프로세스들이 열심히 일하는 것처럼 보이지만 실제로는 유용하지 않은 작업들을 하고 있다.

상호 배제(mutual exclusion) : 한 프로세스가 공유자원을 접근하는 임계역영 코드를 수행하는 중이면 다른 프로세스들은 공유 자원에 접근하는 임계영역 코드를 수행할 수 없다는 조건이다.

경쟁상태(race condition) : 두개 이상의 프로세스가 공유 자원을 동시에 접근하려는 상태, 최종 수행 결과는 프로세스들의 상대적인 수행 순서에 따라 달라진다.

기아(starvation) : 특정 프로세스가 수행 가능한 상태임에도 매우 오랜 기간 동안 스케줄링 되지 못하는 경우

병렬처리를 위한 기법

인터리빙(interleaving) : 멀티프로그래밍에서 여러개의 프로세스가 번갈아가면서 수행되어 마치 동시에 수행되는 것과 같게 되는것

오버래핑(overlapping) : 여러개의 처리기로 실제로 여러 작업을 처리하는 것

병행성에는 한 가지 문제점이 있다. 각각의 프로세스의 속도를 예측할 수 없다는 것이다.
예측할 수 없는 프로세스들이 동일한 자원을 두고 경쟁하다보니 다음과 같은 문제를 야기한다.

1. 전역 자원의 공유에 어려움이 있다.
   ex) 두개의 프로세스가 같은 전역 변수를 사용
2. 운영체제가 자원을 최적으로 할당하기 어려워진다.
   ex) 자원 할당 후 일시정지
3. 프로그래밍 오류를 찾아내는 것이 어려워진다.
   ex) 특정 실행 순서에 따른 오류

따라서 프로세서간 충돌을 방지할 상호배제가 필요하다.

📌 상호배제(Mutual exclusion)

상호 배제를 보장하기 위해서는 다음의 요구 조건들이 만족되어야 한다.

1. 상호 배제가 강제되어야 한다.
2. 임계영역 외의 코드에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안된다.
3. 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안된다. 즉 기아 상태, 교착 상태가 발생해서는 안된다.
4. 임계영역이 비어있고 임계영역 진입을 원하는 프로세스는 즉시 임계영역에 들어 갈 수 있다.
5. 프로세스 개수나 상대적인 프로세스 수행 속도에 대한 가정은 없어야 한다.
6. 임계영역에 들어간 프로세스는 일정한 시간 내에 임계영역에서 나와야 한다.

📌 상호배제: 소프트웨어적 접근 방법

운영체제나 프로그래밍 언어 차원의 지원 없이 프로세스간 협력을 통해 직접 상호 배제를 보장한다.
수행 부하가 크고, 잘 설계되지 않았을 경우 오동작 가능성이 높다.

🔍 데커(Dekker) 알고리즘

데커의 알고리즘 - 위키백과, 우리 모두의 백과사전

🔍 피터슨(Peterson) 알고리즘

피터슨의 알고리즘 - 위키백과, 우리 모두의 백과사전

💡 참고

[IT 기술면접 준비자료] 상호배제(Mutual Exclusion)와 상호배제 알고리즘

데커(Dekker) / 피터슨(Peterson) / 제과점(Bakery) 알고리즘

📌 상호배제: 하드웨어적 접근 방법

상호배제를 보장하기 위한 하드웨어적인 접근 방법을 알아보자

🔍 인터럽트 금지

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

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

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

단, 멀티프로세서 시스템에서는 효과가 없다.
두개 이상의 프로세서를 가지는 컴퓨터 시스템에서는 인터럽트가 금지된 상황에서도 서로 다른 프로세스가 공유 자원을 동시에 접근하는 경우가 가능하기 때문이다.

단점

• 부하가 크다.
  인터럽트 비허용 시, 그 사이 외부에서 발생하는 이벤트에 대한 처리와 다른 프로세스에 대한 스케줄링 등 모든 기능이 중지되어 시스템 수행 효율이 확연하게 감소할 가능성이 높다.
• 멀티프로세서 시스템에서는 올바른 접근 방법이 아니다.

🔍 특별한 기계 명령어

멀티 프로세서 환경에서 여러 프로세서들은 공통의 주기억 장치를 공유하며, 이때 모든 프로세서는 동등한 관계에서 독립적으로 동작한다. (인터럽트 기법으로 상호배제 보장 불가)

하드웨어 수준에서 특정 메모리 주소가 접근되고 있을 때, 같은 위치에 대한 접근 요청은 차단된다는 것에 기반해 상호배제를 보장하기 위한 두 가지 명령어가 구현된다.
이때 기계 명령어는 두 개의 기능을 원자적으로 처리한다.

1. Compare & Swap 명령어

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

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

2. Exchange 명령어

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

실제로 이 함수가 아니고 하드웨어 명령어이다.
이해를 돕기위한 코드라 생각하면 된다.

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

필기가 난잡하고 더럽지만 매우 디테일하게 적어놨다
정녕 자세히 알고싶다면 읽어보자

장점

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

단점

• 바쁜 대기를 사용한다
  임계영역에 진입하는 것을 대기하고 있는 프로세스는 처리기를 계속 사용하게 된다.
  TIP 바쁜 대기란 임계영역에 진입하기 위한 허가를 획득할 때까지 변수를 테스트하는 명령을 반복 실행하며 대기하는 것을 말한다.
• 기아가 발생할 수 있다
  한 프로세스가 임계영역에서 빠져나올 때, 대기하고 있던 다수의 프로세스 중 하나만 다시 임계영역에 진입이 가능한데, 이 때 각 프로세스의 길이나 특성, 대기시간 등을 고려하지 않기 때문에 무한정 기다리는 프로세스가 생길 수도 있다.
• 교착상태에 빠질 수 있다.
  싱글 프로세서 시스템에서 P1 이라는 프로세스가 임계영역에 진입한다.
  그때 P2 라는 P1보다 우선순위가 높은 프로세스가 생겨 운영체제가 P2를 스케줄하여 P2에게 자원을 할당하려 할 때 P2와 P1이 같은 자원을 사용하려 하면 P2는 상호배제조건에 의해 바쁜 대기를 수행한다.
  이때 P2가 계속 프로세서를 점유하고 있기 때문에 우선순위가 높은 P2로 인해 P1은 다시 스케줄링될 수 없다. -> P2가 실행상태에 있기 때문이다.

소프트웨어적 방법과 하드웨어적 방법은 모두 단점을 갖고 있기 때문에 새로운 해결책이 필요하다.

📌 상호배제: 운영체제와 프로그래밍 언어 수준에서 접근 방법

🔍 세마포어(Semaphore)

멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

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

카운팅(범용) 세마포어

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

세마포어는 바쁜대기와 기아를 해결

• OS는 blocked 큐를 갖고 있기 때문에 바쁜 대기 문제가 해결된다.
• 큐에는 순서가 있기 때문에 기아 문제가 해결된다.

세마포어의 특징

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

세마포어 동작 예시

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

한정 버퍼(bounded-buffer) 문제라고도 한다.

유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근한다. 생산자는 데이터를 만들어 버퍼에 저장해나가고, 소비자는 버퍼에 있는 데이터를 꺼내 소비하는(비우는) 프로세스이다.
이때 저장할 공간이 없는 문제가 발생할 수 있다. 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져온다. 이 때는 소비할 물건이 없는 문제가 발생할 수 있다.

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

무한공유 버퍼인경우

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

유한공유 버퍼인경우

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

🔍 뮤텍스(Mutex)

뮤텍스는 세마포어와 마찬가지로 병행 처리를 위한 동기화 기법 중 하나입니다.
이진 세마포어와 같이 초기값을 1과 0으로 가집니다.
임계영역에 들어갈 때 락(lock)을 걸어 다른 프로세스(혹은 쓰레드)가 접근하지 못하도록 하고,
임계영역에서 나와 해당 락을 해제(unlock) 합니다.

뮤텍스와 세마포어의 차이는?

세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스(또는 쓰레드)가 접근할 수 있습니다.
반면에 뮤텍스는 오직 1개만의 프로세스(또는 쓰레드)만 접근할 수 있습니다.
현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있습니다.
하지만 뮤텍스는 락(lock)을 획득한 프로세스가 반드시 그 락을 해제해야 합니다.

🔍 모니터

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

📌 데드락(DeadLock)

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.

발생조건 4가지

• 상호 배제 조건(Mutual Exclusion) 입니다. 자원은 한 번에 한 프로세스만 사용 가능하다 는 조건입니다.
• 점유 대기 조건(Hold And Wait) 입니다. 최소한 하나의 자원을 점유(Lock)하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기(Wait) 하는 프로세스가 존재해야 합니다.
• 비선점 조건(No preemption)이 있습니다. 다른 프로세스에 할당된 자원은 해당 프로세스가 사용이 끝날때까지 강제로 빼앗을 수 없습니다.
• 순환 대기 조건(Circular Wait)이 있습니다. 프로세스의 집합에서 순환 형태(사이클)로 자원을 대기(Wait) 하고 있어야 합니다.

이러한 상호 배제, 점유 대기, 비선점, 순환 대기 4가지 조건을 모두 성립해야 데드락이 발생할 수 있습니다.

데드락의 처리방법

데드락을 처리하기 위한 방법으로 예방, 회피, 탐지 및 회복, 무시 가 있습니다.
예방(Prevention) 이란, 데드락 발생 조건 중 하나를 제거하면서 해결하는 방법입니다. 즉, 상호 배제, 점유 대기, 비선점, 순환 대기 4가지 조건 중 하나를 제거합니다.

다음으로, 회피(Avoidance) 는 데드락이 발생할 시 피해가는 방법입니다. 대표적으로, 은행원 알고리즘을 사용하여 피해갑니다.

또, 탐지 및 회복(Detection & Recovery) 은 자원 할당 그래프를 통해 데드락을 감지하며, 만약 데드락을 감지할 경우 이전 상태로 회복하는 방법이죠. 일부러 데드락을 발생하게 놔두고 감지해서 회복하는 경우도 있습니다.

마지막으로, 무시(Ignore) 는 말 그대로 데드락 발생을 무시하고 지나가는 방법입니다.

교착상태 예방

교착상태가 발생하기 위한 4가지 필요충분 조건 중 하나를 설계 단계에서 배제하는 방법이다.

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

교착상태 회피

은행원 알고리즘(Banker Algorithm)을 사용합니다.
데드락을 처리하기 위한 방법 중 회피에 해당하는 알고리즘입니다. 데드락에 빠질 수 있는 상태를 불안전 상태, 데드락에 빠질 수 없는 상태를 안전 상태 라고 가정했을 때, 운영체제는 이러한 안전 상태인 경우에만 요청을 허락하여 자원을 할당해주고, 나머지 요구들은 안전 상태가 될 때 까지 계속 거절하는 알고리즘입니다.

즉, 은행원 알고리즘은 은행은 최소한 한 명에게 대출해줄 수 있는 돈을 가지고 있어야 한다는 뜻에서 나왔으며, 바꿔말하면 운영체제가 최소한 하나의 프로세스가 일을 수행할 수 있는 경우에만 요청을 허락하여 시스템의 자원을 할당해주는 것과 같습니다.

✨ References

• William Stallings, 『운영체제 제8판 : 내부구조 및 설계원리』, 프로텍미디어
• 세종대 운영체제 수업 내용 + 내 필기
• 병행성 내용 요약
  나만의 백과사전 - 병행성 : 상호배제, 동기화, 교착상태, 기아
  
• 데드락 질문 정리
  [OS] 2020.11.16. 오늘의 면접 Q&A
  
• 뮤텍스 세마포어 차이점
  Semaphore(뮤텍스)와 Mutex(세마포어)의 차이점은?