OS? Oh Yes! 책을 바탕으로 학습한 내용입니다.
상호배제(Mutual Exclusion)
상호배제는 경쟁 상태의 병행 프로세스간 임계 자원에 속하는 공유 자원에 대한 문제에 있어서 임계 영역(Critical Section)에 한번에 하나의 프로세스만 진입하도록 하는 것이다.
- 병행 프로세스는 메모리 위에 동시에 존재하는 다수의 프로세스를 의미한다.
- 임계 영역은 두 개 이상의 프로세스가 한 번에 이용할 수 없는 임계 자원에 대해 접근하고 실행하는 코드 영역이다.
상호배제를 위한 소프트웨어 기법
운영체제의 도움 없이 병행하는 프로세스들이 상호배제를 책임지도록 하는 기법, 임계 영역의 앞뒤로 적절한 처리를 해준다.
- 하나의 전역 변수를 두어 병행 프로세스간 진출입을 관리하는 경우
- 임계 영역의 첫 진입이 고정됨
- 임계 영역의 진입이 타 프로세스에 의해 결정되기 때문에 연속 진입이 불가하고 다른 프로세스가 먼저 종료되는 경우 또 다른 프로세스는 진입이 불가하다.
- 각 프로세스의 진입을 허용하는 전역 변수를 두어 진출입을 관리하는 경우
- 두 프로세스의 속도가 교묘히 맞물렸을 때 둘 다 임계영역에 진입하지 못하는 라이브락(Livelock)을 일으킬 수 있다.
- 두 전역 변수를 복합적으로 사용하여 진출입을 관리하는 경우
- 상호배제를 성공적으로 구현할 수 있다.
운영체제의 도움 없이도 상호배제를 성공적으로 구현할 수 있지만 임계영역 앞에서 반복문을 계속해서 돌면서 바쁜 대기(Busy Wait) 또는 스핀락(Spinlock)을 피할 수 없기 때문에 CPU를 낭비하는 결과를 초래하며 개발자의 실수로 인한 오류의 가능성이 있다.
상호배제를 위한 하드웨어 기법
- 인터럽트 금지를 사용한 기법
시스템의 효율적인 운영을 방해하고 다중 처리 시스템에서 다른 처리기에서 실행되는 프로세스로부터의 접근 가능성은 여전히 존재하기 때문에 사용하기 힘든 방법이다. - 하드웨어 명령어를 사용한 기법
명령어가 실행되는 동안 다른 접근 요청이 차단되는 원자적(Atomic)한 명령어를 통해 상호배제를 구현- 바쁜 대기의 발생
- 기아(Starvation) 발생 가능성
- 임계영역 실행 중 CPU를 선점당할 경우 교착 상태의 가능성
세마포어(Semaphore)
세 개의 특수한 명령들(초기화, wait, signal)만 접근할 수 있게 허용되는 보호된 변수로 운영체제 수준에서 병행성을 제공하여 상호배제 명령을 구현할 수 있다. 운영체제 수준에서 임계영역 진입을 기다리는 프로세스들을 대기 상태로 전환시킴으로써 바쁜 대기를 할 때의 CPU 낭비를 없앨 수 있다.(block and wakeup) 하지만 바쁜 대기보다 반응이 즉각적이지 못하며 대기 상태로 만드는 비용을 감수해야하며 기아(Starvation)를 일으킬 수 있다.
- 이진 세마포어
- 정수 세마포어
- 정수 세마포어의 수는 현재 임계영역 진입 가능 프로세스의 수
세마포어는 상호배제의 구현뿐만 아니라 동기화도 쉽게 구현할 수 있다. 상호 의존 관계의 프로세스 사이에서 두 프로세스의 진행을 조정하여 동기화를 구현한다.
Eventcount와 Sequencer를 사용한 기법
임계영역의 진입을 시도하는 프로세스들에게 순번 표를 부여함으로써 기다린 순서대로 처리되게 하여 기아(Starvation)를 방지할 수 있다.
모니터(Monitor)
모니터란 공유 데이터들과 이들에 대한 임계영역들을 관리하는 소프트웨어 구성체다. 호출 대기 큐(진입 큐), 조건 큐, 신호자 대기 큐가 필요하다.
- wait()을 통해 현재 프로세스를 조건 큐에 넣고 다른 프로세스의 모니터 진입을 허가한다.
- signal()을 통해 현재 프로세스를 신호자 대기 큐에 넣고 조건 큐에 대기 중이던 프로세스를 실행한다.
고전적인 문제
-
생산자와 소비자 문제
생산자는 데이터를 만들어 버퍼에 저장하고 소비자는 버퍼에 접근하여 데이터를 소비할 때 버퍼는 공유 자원이므로 버퍼에 대한 접근은 상호배제되어야한다. 또한 버퍼가 가득 찼을 때는 생산자가 기다리고, 버퍼가 비었을 때는 소비자가 기다려야하므로 동기화되어야 한다. -
식사하는 철학자
원형 테이블에서 5명의 철학자가 식사할 때 각 철학자 사이에 포크가 하나 씩 있다. 철학자는 식사를 하려면 양쪽의 포크를 모두 사용해야한다. 모든 철학자가 동시에 왼쪽 또는 오른쪽 포크를 집으면 교착상태에 빠지고 양쪽의 포크를 모두 집도록하면 기아가 발생할 수 있다.- 식탁에 4명만 앉도록 한다. (프로세스를 제한한다.)
- 홀수 번호의 철학자는 왼쪽 포크 -> 오른쪽 포크를 집도록 하고, 짝수 번호의 철학자는 반대로 집도록 한다.
