교착상태란?
교착상태(deadlock)란, 둘 이상의 프로세스나 스레드가 서로 상대방이 가지고 있는 자원을 기다리면서 무한정 대기 상태에 빠지는 상황을 말합니다.
그리고 이 교착상태를 쉽게 설명하기 위해 ' 식사하는 철학자 문제'를 예로 들 수 있습니다.
식사하는 철학자 문제
식사하는 철학자 문제는 병렬 처리 분야에서 자주 언급되는 문제 중 하나이며, 이 문제는 다섯 명의 철학자가 원탁에 둘러 앉아 젓가락을 사용하여 식사를 하는 상황에서 발생합니다.
각 철학자의 왼쪽과 오른쪽에는 젓가락이 하나씩 놓여 있으며, 철학자는 젓가락 두 개를 동시에 사용하여 식사를 합니다. 그러나, 모든 철학자가 동시에 식사를 하려고 젓가락을 집으면, 젓가락이 충돌하여 둘 다 사용할 수 없는 상황이 발생합니다. 이 문제를 해결하기 위해서는 철학자들이 동기화되어 젓가락을 사용해야 합니다.
교착상태는 상호배제, 점유와 대기, 비선점, 순환 대기라는 4가지 조건이 동시에 성립할 때 발생합니다. 이 조건들이 모두 충족되어야 교착상태가 발생하며, 한 가지 조건만 성립해도 교착상태가 발생할 가능성이 있습니다.
교착상태가 발생하면 시스템의 성능이 떨어지고, 리소스를 효율적으로 활용할 수 없어 프로세스나 스레드의 처리능력이 감소합니다.
- 상호배제(Mutual Exclusion) : 여러 개의 프로세스가 공유 자원을 사용할 때, 한 번에 하나의 프로세스만 접근할 수 있도록 제어하는 메커니즘입니다. 대표적인 예로 세마포어(Semaphore)나 뮤텍스(Mutex)가 있습니다.
- 한명이 포크를 사용하면 나머지는 그 포크를 사용할 수 없음 - 점유 대기(Hold and Wait) : 프로세스가 자신이 가지고 있는 자원을 반납하지 않은 채 다른 자원을 요청하고 대기하는 상태입니다. 이 때, 다른 프로세스가 자원을 점유하고 있기 때문에 대기가 발생하게 됩니다.
- 포크를 하나 지닌 상태 반납하지도 않고, 나머지 한 포크를 기다리기만 함 - 비선점(Non-Preemptive) : 프로세스가 CPU를 점유하고 있을 때, 다른 프로세스가 CPU를 강제로 빼앗을 수 없는 스케줄링 방식입니다. 해당 프로세스가 끝나거나 입출력 등의 이벤트가 발생하면 비로소 다른 프로세스가 CPU를 점유할 수 있습니다.
- 포크를 강제로 뺏을 수 없음. - 순환 대기(Circular Wait) : 여러 개의 프로세스가 자원을 순환하며 대기하는 상황입니다. 예를 들어, 프로세스 A는 프로세스 B가 점유한 자원을 필요로 하고, 프로세스 B는 프로세스 C가 점유한 자원을 필요로 하며, 프로세스 C는 다시 프로세스 A가 점유한 자원을 필요로 하는 상황입니다. 이러한 경우, 프로세스들이 무한정 대기하게 되어 데드락(Deadlock)이 발생할 수 있습니다.
- 식사하는 철학자 문제 처럼 앞의 상황들이 원형으로 이뤄짐.
교착상태를 해결하기 위한 다양한 알고리즘이 존재하며, 대표적으로 Dijkstra가 제안한 상호배제(Mutual exclusion) 알고리즘, Chandy-Misra 알고리즘, Resource hierarchy solution 등이 있습니다.
교착 상태 해결 방법
상호배제 알고리즘은 여러 프로세스가 동일한 자원에 접근할 때, 그 자원을 한 번에 하나의 프로세스만 사용하도록 보장합니다. 대표적으로 Peterson's algorithm, Dijkstra's algorithm 등이 있습니다.
Chandy-Misra 알고리즘은 분산 시스템에서 모든 프로세스 간의 상호배제를 보장합니다. 각 프로세스는 자신이 선정한 다른 프로세스에게 상호배제를 요청하고, 그 요청이 순환하면서 각각의 프로세스는 요청에 대한 응답을 받아 누적합니다. 이 과정이 끝나면 모든 프로세스는 상호배제를 보장하는 메시지 교환을 마칩니다.
Resource hierarchy solution은 자원을 계층화하여 접근 권한을 부여하는 방식입니다. 보다 높은 수준의 자원은 보다 낮은 수준의 자원보다 높은 접근 권한을 가지며, 저수준 자원은 고수준 자원의 사용에 대한 승인을 받아야 합니다. 이 방식은 대부분의 병행성 문제를 해결할 수 있지만, 자원 계층 구조를 구성하는데 필요한 비용이 높은 단점이 있습니다.
상호배제(Mutual exclusion) 알고리즘 Swift 코드
class Lock {
var turn: Int = 0
var interested: [Bool] = [false, false]
func acquireLock(_ me: Int) {
let other = 1 - me
interested[me] = true
turn = me
while (turn == me && interested[other]) {
// 대기
}
}
func releaseLock(_ me: Int) {
interested[me] = false
}
}이 코드는 두 개의 스레드가 공유 자원에 접근할 때 상호배제를 위해 사용할 수 있습니다. acquireLock 메서드는 스레드가 공유 자원에 접근하기 전에 호출되어, interested 배열에서 해당 스레드를 true로 설정하고, turn 변수에 해당 스레드 번호를 할당합니다. 그리고 다른 스레드가 자원을 사용하고 있을 때 대기합니다. releaseLock 메서드는 스레드가 자원 사용을 마치면 호출되어 interested 배열에서 해당 스레드를 false로 설정합니다.
Chandy-Misra 알고리즘 Swift 코드
class Node {
var id: Int
var deferredQueue: [Int]
var state: String
init(id: Int) {
self.id = id
self.deferredQueue = []
self.state = "RELEASED"
}
func receiveToken(from: Node) {
if self.state == "RELEASED" {
self.state = "HELD"
print("Node \(self.id) has the token.")
}
else {
self.deferredQueue.append(from.id)
print("Node \(self.id) defers request from node \(from.id).")
}
}
func releaseToken() -> [Int] {
if self.deferredQueue.isEmpty {
self.state = "RELEASED"
print("Node \(self.id) releases the token.")
return []
}
else {
let firstId = self.deferredQueue.removeFirst()
let deferredNodes = [firstId] + self.releaseToken()
return deferredNodes
}
}
}
class Network {
var nodes: [Node]
init(nodeCount: Int) {
self.nodes = []
for i in 1...nodeCount {
let node = Node(id: i)
self.nodes.append(node)
}
}
func simulateRequest(from nodeId: Int) {
let node = self.nodes[nodeId - 1]
let nextNodeId = nodeId % self.nodes.count + 1
let nextNode = self.nodes[nextNodeId - 1]
nextNode.receiveToken(from: node)
}
func simulateRelease(from nodeId: Int) -> [Int] {
let node = self.nodes[nodeId - 1]
let deferredNodes = node.releaseToken()
for id in deferredNodes {
let nextNodeId = id % self.nodes.count + 1
let nextNode = self.nodes[nextNodeId - 1]
nextNode.receiveToken(from: node)
}
return deferredNodes
}
}Node 클래스는 노드의 상태와 요청 대기열을 관리하고, Network 클래스는 노드들 사이의 상호작용을 시뮬레이션하는 클래스입니다.
Node 클래스의 receiveToken 메소드는 다른 노드로부터 토큰을 수신하면, 자신의 상태가 "RELEASED"인 경우 "HELD"로 변경하고, 그렇지 않은 경우 해당 요청을 대기열에 추가합니다.
Node 클래스의 releaseToken 메소드는 대기열이 비어있는 경우 자신의 상태를 "RELEASED"로 변경하고, 그렇지 않은 경우 대기열의 첫 번째 요소를 처리하고, 처리가 완료되면 다시 releaseToken을 호출하여 다음 요소를 처리하도록 합니다. 이 때 처리된 노드들의 id를 반환합니다.
Network 클래스의 simulateRequest 메소드는 nodeId를 입력받아 해당 노드에서 다음 노드로 토큰을 전송하는 역할을 합니다.
Network 클래스의 simulateRelease 메소드는 nodeId를 입력받아 해당 노드에서 releaseToken을 호출하여 처리된 노드들의 id를 반환하고, 반환된 id를 이용하여 다음 노드로 토큰을 전송하는 역할을 합니다.
이렇게 구현된 코드는 Chandy-Misra 알고리즘의 핵심 논리를 담고 있으며, 여러 노드간의 상호작용을 시뮬레이션하여 알고리즘의 동작을 검증할 수 있습니다.
Resource hierarchy solution Swift 코드
class Process {
let pid: Int
var resourceHierarchy: Int
var resource: Resource?
init(pid: Int, resourceHierarchy: Int) {
self.pid = pid
self.resourceHierarchy = resourceHierarchy
}
func requestResource(resource: Resource) {
if self.resourceHierarchy <= resource.hierarchy {
self.resource = resource
print("Process \(self.pid) granted resource \(resource.rid)")
} else {
print("Process \(self.pid) denied resource \(resource.rid)")
}
}
func releaseResource() {
if let resource = self.resource {
print("Process \(self.pid) released resource \(resource.rid)")
self.resource = nil
}
}
}
class Resource {
let rid: Int
let hierarchy: Int
init(rid: Int, hierarchy: Int) {
self.rid = rid
self.hierarchy = hierarchy
}
}
let r1 = Resource(rid: 1, hierarchy: 1)
let r2 = Resource(rid: 2, hierarchy: 2)
let r3 = Resource(rid: 3, hierarchy: 3)
let p1 = Process(pid: 1, resourceHierarchy: 1)
let p2 = Process(pid: 2, resourceHierarchy: 2)
let p3 = Process(pid: 3, resourceHierarchy: 3)
p1.requestResource(resource: r1) // granted
p2.requestResource(resource: r1) // denied
p2.requestResource(resource: r2) // granted
p3.requestResource(resource: r2) // denied
p3.requestResource(resource: r3) // granted
p2.releaseResource() // released
p3.releaseResource() // released
p2.requestResource(resource: r1) // granted이 구현에서 Process 클래스는 리소스를 요청하고 해제할 수 있는 프로세스를 나타내며, resourceHierarchy 속성은 요청할 수 있는 최대 리소스 계층 구조를 결정합니다. Resource 클래스는 리소스를 나타내며, hierarchy 속성은 해당 리소스의 우선 순위를 결정합니다.
Process 클래스의 requestResource 메서드는 요청한 리소스의 계층이 프로세스의 resourceHierarchy보다 낮거나 같은지 확인합니다. 그렇다면 리소스가 승인되고, 프로세스에게 할당됩니다. 그렇지 않으면 요청이 거부됩니다. releaseResource 메서드는 프로세스에게 할당된 리소스를 해제합니다.
안전상태: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
불안전 상태: 교착 상태가 발생할 수 있는 상황
안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미
타조알고리즘: 교착상태를 아예 무시하는 방법
잠재적 문제를 무시하는 타조알고리즘 Swift 코드
class IgnoringPotentialIssuesPetersonLock {
private var flag: [Bool]
private var turn: Int
init() {
self.flag = [false, false]
self.turn = 0
}
func lock() {
let i = Thread.current == Thread.first ? 0 : 1
let j = 1 - i
flag[i] = true
turn = j
}
func unlock() {
let i = Thread.current == Thread.first ? 0 : 1
flag[i] = false
}
}
extension Thread {
static let first = Thread()
static let second = Thread()
}
class SharedVariable {
private var value: Int
private let lock = IgnoringPotentialIssuesPetersonLock()
init(value: Int) {
self.value = value
}
func increment() {
lock.lock()
value += 1
print("Value after increment: \(value)")
lock.unlock()
}
func decrement() {
lock.lock()
value -= 1
print("Value after decrement: \(value)")
lock.unlock()
}
}
let sharedVariable = SharedVariable(value: 0)
Thread.first.start()
Thread.second.start()
DispatchQueue.global().async {
for _ in 0..<10 {
sharedVariable.increment()
}
}
DispatchQueue.global().async {
for _ in 0..<10 {
sharedVariable.decrement()
}
}
Thread.first.join()
Thread.second.join()
교착 상태 검출 후 회복(교착 상태 발생을 인지하고 사후에 조치하는 방법)
선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복: 프로세스를 모두 종료하거나 교착 상태가 사라질 때까지 프로세스를 하나씩 종료하는 방법