相互排除

相互排除 (相互排除, mutual exclusion, Mutex, 뮤텍스)는 同時 프로그래밍 에서 共有不可能한 資源의 同時使用을 避하기 위해 使用되는 알고리즘 으로, 臨界區域 (critical section)으로 불리는 코드 領域에 依해 具現된다.

共有不可能한 資源의 例로는 同時에 實行되고 있는 프로그램間의 通信에 使用되는 비트 單位의 旗발, 計數器, 큐 等이다. 問題는 스레드 가 언제라도 停止되거나 始作될 수 있다는 것이다.

예) 프로그램의 一部分이 여러 段階를 거치면서 데이터를 읽고 쓰고 있다고 하자. 그런데 豫想치 못한 事件等에 依해 다른 스레드가 動作하기 始作했다. 첫 番째의 스레드가 쓰고 있는 領域에서, 이 두 番째의 스레드가 또 다른 作業을 始作한다면, 該當領域의 값은 不適切하며 豫想할 수 없는 狀態에 놓이게 된다. 게다가 두 番째의 스레드가 값을 덮어 써버리기라도 한다면, 復舊不可能한 狀態로 되고 만다. 그러므로 共有 데이터를 接近하는 프로그램 內部의 이른바 臨界區域 이라는 部分은 홀로 遂行되도록 保護되어야 하며, 다른 스레드가 同一한 部分의 프로그램을 遂行해서 同一한 共有 데이터를 接近하는 것을 막아야 한다.

單一 프로세서 시스템에서, 相互排除를 具現하는 가장 單純한 方法은 인터럽트 를 抑制해서 共有 데이터가 損傷되는 것을 막는 것이다. 性能에 最小限의 影響을 주기 위해 인터럽트가 發生하지 않을 命令語集合의 數는 可能한 最小로 維持시키는 것이 좋다.

相互排除를 처음으로 소프트웨어를 통해 解決한 사람은 네덜란드 數學者 데커 (Dekker)이며 그 알고리즘을 데커의 알고리즘 理라 한다.

相互排除는 膠着狀態 의 4가지 必要條件中 하나이다.

같이 보기 [ 編輯 ]

外部 링크 [ 編輯 ]