[Operating System] 병행 프로세스와 상호배제

병행 프로세스

프로세서는 한 번에 한 개의 프로세스만 실행시킬 수 있다. 하지만 운영체제가 프로세서를 빠르게 전환하여 프로세서 시간을 나눠서 마치 여러 프로세스가 동시에 실행되는 것처럼 보이는 것을 병행 프로세스라고 한다.

병행과 병렬

병행과 병렬 둘 다 대략적으로 '동일한 시간 동안 여러 프로세스를 동시 실행'이라는 의미를 가진다.
하지만 둘은 전혀 다르다. 병렬을 이용한 병렬 컴퓨팅은 다중 프로세서 시스템에서 동일한 시간대에 별도의 프로세서에서 실행하는 것이다. 반면에 병행을 이용한 동시 컴퓨팅은 프로세스 수명이 겹치는 것이지 꼭 동일한 시간대에 실행될 필요가 없다.

병행 프로세스의 구분

병행 프로세스는 단일 처리 시스템에서 서로 독립적으로 작업을 수행하는 독립 프로세스와 다른 프로세스와 협력하면서 특정 기능을 수행하는 비동기적 병행 프로세스인 협력 프로세스로 구분한다.

• 독립 프로세스: 다른 프로세스에 영향을 주고받지 않으면서 독립적으로 실행한다.
  • 단일, 다중 프로그래밍
• 협력 프로세스: 다른 프로세스에 영향을 주고받으면서 특정 기능을 수행한다.
  • 소켓, 생산자-소비자 방식

상호배제

상호배제는 병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법이다.

동기화

당연하게도 읽기 연산 경우 동시에 접근해도 문제가 발생하지 않지만, 변수나 파일은 프로세스 차례대로 읽거나 쓰도록 해야하는데 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법을 동기화라고 한다. 동기화를 통해 상호배제를 보장할 수 있지만 교착 상태 또는 기아 상태가 발생할 수 있다.

상호배제를 만족하기 위한 조건

• 두 프로세스는 동시에 공유 자원(임계 영역)에 진입할 수 없다.
• 프로세스 속도나 프로세서 수에 영향받지 않는다.
• 공유 자원을 사용하는 프로세스만 다른 프로세스의 접근을 차단할 수 있다.
• 프로세스가 공유 자원을 사용하려고 너무 오래 기다리면 안된다.

임계 영역

다수의 프로세스가 접근할 수 있지만, 어느 한순간에는 프로세스 하나만 사용할 수 있는 영역을 의미한다.
즉, 어떤 프로세스가 임계 영역에 들어가면 다른 프로세스는 임계 영역에 접근할 수 없다 .

임계 영역을 만족하기 위한 조건

• 상호배제: 어떤 프로세스가 임계 영역에서 작업 중이라면 다른 프로세스는 임계 영역으로 들어갈 수 없다.
• 진행: 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때 어떤 프로세스가 진입할지는 적절하게 결정되어야 한다.
• 한정 대기: 다른 프로세스가 임계 영역 진입을 무한정 기다리는 상황을 방지하기 위해 임계 영역에 한 번 진입한 프로세스는 다음 번 임계 영역 접근에 제한을 둔다.

생산자-소비자 문제와 상호배제 해결

생산자와 소비자는 둘 다 동시에 공유 자원(Counter)에 접근할 수 있어 임계 영역의 문제가 발생할 수 있는데 이를 상호배제로 해결할 수 있다.

상호배제 방법

상호배제 방법으로는 보통 고급 수준과 저급 수준으로 구분된다.

• 고급
  • 소프트웨어로 해결: 데커, 크누스, 핸슨, 다익스트라, 램포트의 베이커리 알고리즘
  • 소프트웨어가 제공(프로그래밍 언어, 운영체제 수준에서 제공): 세마포어, 뮤텍스, 모니터
• 저급
  • 하드웨어로 해결: 테스(TAS, TestAndSet)

세마포어

세마포어는 값이 음이 아닌 정수인 플래그 변수로 기차의 진행 가능 여부를 알려주는 차단기가 대표적인 예시다.
운영체제는 세마포를 이용해 여러 개의 프로세스가 동시에 접근할 수 있는 자원으로 공유 자원에 접근할 수 있는 수량을 제어하는데 이는 P연산과 V연산으로 수행된다.

• P연산(wait()): 자원 사용 연산으로 세마포어 값이 1 이상일 경우 세마포어의 값을 1 감소시키며 임계 영역으로 진입한다. 만약 세마포어 값 0이라면 해당 자원이 사용중이므로 임계 영역에 들어갈 수 없어 프로세스는 Block 상태로 전환되며 대기 큐에 들어간다.
• V연산(signal()): 자원 반환 연산으로 세마포어 값 1 증가시키며 임계 영역에서 탈출한다. 만약 대기 큐에 Block 상태의 프로세스가 존재한다면 적절하게 하나를 선택해 임계 영역으로 진입시킨다.

세마포어의 종류

세마포어는 설계에 따라 계수(카운팅) 세마포어와 이진 세마포어로 구분할 수 있다.

• 계수(카운팅) 세마포어
  • 생산자·소비자 문제처럼 상호 배제와 조건부 동기화를 해결하기 위해 설계된 세마포어다.
  • 유한한 자원에 접근하는 제어할 수 있어 여러 번 획득하거나 해제할 수 있도록 count를 자원사용의 허가 값으로 사용한다.
  • 사용 가능한 자원 수로 초기화하므로, count를 초기 세마포 수로 초기화한다.
  • P(S(count)): 자원 사용 연산으로 count가 1 이상일 때 자원을 사용할 수 있다. 자원 사용 시 S(count)--;가 일어난다. 만약, count == 0이라면 사용 불가능 상태를 의미하여 자원을 사용할 수 없다.
  • V(S(count)): 자원 반환 연산으로 자원 반환 성공 시S(count)++;를 수행한다.
• 이진 세마포어
  • 임계 영역처럼 특별히 상호배제를 해결하려고 설계된 세마포어다.
  • 세마포어를 상호배제에 사용하고 0 또는 1으로 초기화시킨다.
  • P(S): 자원 사용 요청으로 S가 양수라면 0으로 재설정한 후 진행하고, 아니면 프로세스를 대기 큐에 되돌린다.
  • V(S): 자원 반환 요청으로 S를 1로 시작하고, 만약 대기 큐에 대기 중인 프로세스가 존재한다면 적절하게 하나를 깨워서 준비 상태로 만든다.

이진 세마포어와 계수 세마포어 둘 다 모든 프로세스가 공유할 수 있는 전역 자원이다.

세마포어에서는 wait()연산 때문에 대기하는 프로세스들이 교착 상태에 빠질 수 있다.
예를들어 프로세스는 한 번에 세마포어 하나만 대기할 수 있어 자원을 할당하는 상황에서 두 프로세스가 각각 자원을 하나씩 보유하고, 상대방의 자원을 사용하려고 대기하는 상황이 발생할 수 있다.

모니터

세마포어는 상호배제와 프로세스 사이를 조정하고 유연성 있는 강력한 도구지만 모든 프로세스가 1로 초기화한 세마포를 공유하고, 임계 영역에 진입하기 전에 signal() 연산 후 wait() 연산을 실행해야 한다.
만약, 이 순서를 지키지 않는다면 상호배제를 위반하거나 교착 상태가 발생하는데, 자칫 여러 가지 오류가 쉽게 발생할 수 있다. 그래서 이런 단점을 극복하고자 모니터가 등장했다.

모니터는 공유 자원과 이것의 임계 영역을 관리하는 소프트웨어 집합체로, 해당 타입의 상태를 정의하는 변수들과 그 변수를 조작하는 함수들로 구성된다.

모니터 타입으로 표현된 구조체는 여러 프로세스가 직접 접근할 수 없고, 모니터 내부에 정의된 함수들만 이 변수와 파라미터에 접근할 수 있다. 즉, 모니터의 지역 변수는 모니터 내부 함수로 모니터 안으로 진입해 공유 데이터에 접근할 수 있다는 것이다. 무엇보다 언제나 한 번에 한 개의 프로세스만 모니터에 진입할 수 있도록 제한하여 상호배제를 실현하는 것이 중요하다.

모니터안으로 진입하지 못하도록 차단된 프로세스들은 준비 큐에서 진압을 기다리게 해 상호배제를 실현한다.
이처럼 모니터는 한 번에 하나의 프로세스만 내부에서 활동할 수 있도록 보장하기 때문에, 프로그래머가 따로 동기화 제약 조건을 코딩할 필요가 없다.

모니터의 조건 변수 추가

기존의 모니터만으로는 모든 동기화 상황을 표현하기엔 부족하다. 그래서 조건 변수라는 추가적인 동기화 메커니즘을 사용한다. 조건 변수은 wait()과 signal() 두 연산으로 변경된다.

• x.wiat(): 해당 연산을 호출한 프로세스를 일시 중단한다. 이를 재개시키기기 위해서는 다른 프로세스가 x.signal();을 호출해줘야 한다.
• x.signal(): 조건 변수 x에서 대기중인 프로세스가 있다면 하나만 재개시키는데 만약 아무도 대기하지 않았다면 아무 일도 일어나지 않는다.

세마포어 signal()과 모니터 signal()

• 세마포어의 signal()은 세마포어 값을 1을 증가시켜 항상 상태 변화가 발생하지만, 모니터 signal()은 아무도 대기하지 않으면 아무일도 일어나지 않아 항상 상태 변화가 일어나지 않는 차이가 있다.

뮤텍스

임계 영역 문제에 대한 고급 수준의 소프트웨어 도구 중 간단한 도구로 임계 영역을 보호하기 위해 사용되면서 경쟁 조건을 방지한다. 프로세스가 임계 영역으로 들어가기 전 락을 획득해야 하고 임계 영역을 탈출할 때 락을 해제해야 한다.

뮤텍스의 락 사용 여부

뮤텍스 락에는 Boolean available이 있는데 이 값을 통해 락 사용 여부를 확인할 수 있다.

• available == true라면 acquire()을 통해 락을 획득할 수 있고 available == false로 전환된다.
• available == false라면 락이 해제될 때까지 block된다.
• 락을 해제할 때는 release()를 통해 해제한다.
• acqurie()와 releas()는 반드시 원자적(atomic)으로 실행되어야 한다.

락 경쟁(Lock Contention)

어떤 스레드가 락을 얻으려다 Blocking되는 경우를 락 경쟁이라고 한다.

• 높은 경쟁 상태: 여러 스레드가 동시에 락 획득을 시도하는 경우
• 낮은 경쟁 상태: 락 획득을 시도하는 스레드가 적은 경우
• 비경쟁 상태 : 락 획득 시도 시 즉시 획득되는 경우

락 경쟁이 심할수록 전체 성능이 저하된다.

스핀 락

락을 획득할 때까지 무한 루프를 돌며 락 획득을 기다리는 방법으로 주로 멀티 프로세서 시스템에서 락을 짧은 시간동안만 유지할 때 적합한 방식이다.

스핀 락 VS 뮤텍스 락

스핀 락과 뮤텍스 락은 속도와 CPU 사이클 측면에서 비교할 수 있다.
먼저 속도 측면에서는 뮤텍스 락은 다른 프로세스가 락을 사용 중이면 Blocking되어 프로세서가 다른 작업을 수행하도록 한다. 이 과정에서 당연하게 컨텍스트 스위칭이 발생하지만 스핀 락은 무한 루프를 돌면서 CPU를 계속 점유하고 있어서 컨텍스트 스위칭이 발생하지 않는다. 즉, 뮤텍스 락이 스핀 락이 비해 속도가 느리다.
하지만 CPU 사이클 측면에서는 앞서 말했듯이 뮤텍스 락은 다른 작업을 수행할 수 있도록 하기 때문에 CPU 사이클이 낭비되지 않지만 스핀 락은 계속 CPU를 점유하므로 CPU 사이클이 낭비된다.

이러한 이유로 짧은 시간에서는 스핀 락이 유리하고, 긴 시간에서는 뮤텍스 락이 유리하다.

멀티코어 환경에서는 하나의 스레드가 락을 기다리는 동안 다른 스레드가 다른 코어에서 임계 구역 작업을 끝낼 수 있기 때문에 바로 락을 획득할 수 있는 스핀 락이 더 효율적일 수 있다.
이러한 이유로 많은 운영체제는 멀티코어 환경에서 락이 짧게 유지될 경유 스핀 락을 선호한다.

학습하며 정리한 글이기 때문에 혼용된 표현 또는 잘못된 내용이 있을 수 있습니다.
만약, 발견하신 경우 댓글을 통해 알려주신다면 진심으로 감사드립니다.