공유한 잠금 순서는 명시적인 순환 대기 하나를 없앨 수 있다.
test-and-set 잠금을 모델링하고 두 잠금의 교착 일정을 드러낸 뒤 안정된 계정 id 순서로 잠금을 얻어 보호된 이체를 수행합니다.
생각해 볼 질문
각 자원을 개별적으로 직렬화해도 왜 교착될 수 있으며 어떤 순서 규칙이 그 순환을 없앨까요?
- 성공한 test-and-set 획득과 실패한 획득 모델링하기
- 따로 잡은 잠금 두 개 사이의 순환 대기 알아보기
- 상호 배제와 교착 회피 구분하기
- 안정된 계정 id에서 전역 잠금 순서 고르기
- 한 유한 보호 연산 뒤 얻은 잠금을 모두 해제하기
첫 일정은 왼쪽 연산이 lock a를, 오른쪽 연산이 lock b를 얻도록 합니다. 각 연산이 다른 잠금을 요구하면 실패합니다. 두 자원은 상호 배제되지만 어느 모델 연산도 진행할 수 없어 순환 대기가 생깁니다. 프로그램은 이 엇갈림을 명시적인 순차 상태 전이로 나타냅니다.
이체 프로그램은 계정 잠금 두 개를 잡기 전에 숫자 id로 순서를 정합니다. 호출자가 반대 방향의 이체를 요청해도 두 연산은 같은 잠금 순서를 사용합니다. 유한한 순차 시연은 두 이체를 끝내고 두 셀을 해제하며 선택한 잠금 프로토콜의 전체 상태 변화를 기록합니다.
SICP 코드UTF-8 682 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
실행 추적0 / 0 개 이벤트
교착 모형은 (#t #t #f #f #t #t #t)을 반환합니다. 순서가 있는 이체 모형은 ((90 50) (45 95) 95 45 #f #f)를 반환합니다.
교착 일정에서는 성공한 첫 획득 두 개와 실패한 둘째 획득 두 개를 찾으세요. 이체 모형에서는 요청한 계정 방향과 id 기반 획득 순서를 따로 기록하고 역순 해제와 마지막 두 false 잠금 셀을 확인하세요.
프로그램을 수정하고 결과를 비교해 보세요.
세 번째 계정을 추가하고 잠금 세 개가 필요한 보호 연산을 만드세요. 계정 id를 정렬한 뒤 일부러 순서가 다른 일정 하나를 적고 다시 생긴 순환 대기를 찾으세요.
힌트 보기
상호 배제는 자원을 보호합니다. 교착 회피에는 여러 잠금을 얻는 모든 연산이 하나의 전역 순서에 동의해야 합니다.