상호 배제(mutual exclusion)에 대해

 

상호배제는 컴퓨터 프로그램의 실행에서 여러 프로세스가 사용할 수 있는 공유 자원에 대해 여러 프로세스에서 동시에 액세스하여 충돌 이 발생하는 경우 프로세스에 자원을 독점적으로 이용하고 있는 동안 다른 프로세스가 사용할 수 없도록 함으로써 일관성을 처리하는 것을 말한다. 최대 k 개의 프로세스가 공유 자원에 액세스하여 좋은 경우를 k-상호배제라고 한다.

 

다르게 표현하면 하나의 크리티컬 섹션에 여러 프로세스 (또는 스레드)가 동시에 들어가는 것을 방지하기 위한 것이다. 크리티컬 섹션은 프로세스가 공유메모리와 같은 공유자원에 액세스하는 부분을 말한다. 상호배제 문제는 1965 년 에츠 허르 데이크스트라가 Solution of a problem in concurrent programming control (병행 프로그래밍 제어에 있어서 문제의 해법)이라는 제목의 논문에서 다룬 것이 최초이다.

상호배제의 중요성을 보여주는 예로서 단방향 연결리스트가 있다. 이러한 연결리스트에서 노드를 제거하려면 1 이전 노드의 다음 노드를 가리키는 포인터를 삭제하려는 노드의 다음 노드를 가리키도록 갱신해야 한다. (예를 들어, 노드 i 을 제거하려면 노드 i-1의 next 포인터를 노드 i + 1을 가리키도록 갱신) 이 때 그 연결리스트를 여러 프로세스가 공유하고 있다면 두 프로세스가 서로 다른 노드를 제거하려고 다음과 같은 문제를 일으킬 수 있다.

두 프로세스는 각각 노드 i 와 i + 1을 동시에 제거하려고 한다. 두 노드가 연결리스트의 중간에 위치해 선두로 마지막 꼬리도 아니라고 한다.

노드 i-1의 next 포인터는 노드 i + 1을 가리키도록 갱신 된 노드 i 의 next 포인터는 노드 i + 2를 가리키도록 수정한다.

모두 삭제 처리가 완료된 상태를 보면 노드 i-1 노드 i + 1을 가리키도록 재 작성했기 때문에, 노드 i + 1 은 연결 목록에 남아 버린다.

이 문제는 상호배제를 실시하고 여러 상태 업데이트가 동시에 발생하지 않도록 하면 해결한다.