테스트 및 설정

Test-and-set

컴퓨터 과학에서 시험과 설정 지침은 메모리 위치에 1을 기록(설정)하고 그 이전 값을 단일 원자(즉, 무중복) 작업으로 되돌리는 데 사용되는 명령이다.그러면 호출자는 통화에 의해 상태가 변경되었는지 확인하기 위해 결과를 "테스트"할 수 있다.여러 프로세스가 동일한 메모리 위치에 접근할 수 있고 프로세스가 현재 시험 및 설정을 수행하는 경우, 첫 번째 프로세스의 시험 및 설정이 완료될 때까지 다른 어떤 프로세스도 다른 시험 및 설정을 시작할 수 없다.CPU는 이중 포트 RAM과 같은 다른 전자 구성 요소가 제공하는 테스트 및 설정 지침을 사용할 수 있으며, CPU 자체도 테스트 및 설정 지침을 제공할 수 있다.

자물쇠는 다음과 같이 원자 시험 및 설정[1] 명령을 사용하여 만들 수 있다.

함수 잠금(boolean *lock) { while (test_and_set(lock) == 1); }

이 코드는 메모리 위치가 첫 번째 테스트 및 설정 전 어느 시점에서 0으로 초기화되었다고 가정한다.호출 프로세스는 이전 값이 0이면 잠금을 얻고, 그렇지 않으면 잠금을 획득하기 위해 대기하는 동안 회전한다.이것을 스핀록이라고 한다.언제든지 잠금 장치 홀더는 다른 사람이 획득하기 위해 잠금 장치를 해제하기 위해 메모리 위치를 다시 0으로 설정할 수 있다. 이 경우 홀더가 이 메모리 위치를 "소유"하기 때문에 특별한 취급이 필요하지 않다.「시험·시험·설정」도 또 하나의 예다.

모리스 헐리히(1991)는 시험-세트(1비트 비교)의 컨센서스 번호가 유한하며, 최대 두 개의 동시 프로세스에 대해 대기-자유 컨센서스 문제를 해결할 수 있음을 증명했다.[2]이와는 대조적으로 비교-스왑(32비트 비교)은 이 문제에 대한 보다 일반적인 해결책을 제공하며, 일부 구현에서는 비교-이중-스왑(64비트 비교)도 확장 유틸리티에 사용할 수 있다.

테스트 및 세트의 하드웨어 구현

DPRAM 시험 및 설정 지침은 여러 가지 방법으로 작동할 수 있다.여기에는 두 가지 변형이 있는데, 두 가지 모두 정확히 2개의 포트를 제공하는 DPRAM을 설명하며, DPRAM의 모든 메모리 위치에 2개의 개별 전자 구성요소(예: 2개의 CPU)가 접근할 수 있다.

변동 1

CPU 1이 시험 및 설정 명령을 내릴 때, DPRAM은 먼저 메모리 위치의 주소를 특별한 장소에 저장함으로써 이것의 "내부 노트"를 만든다.이때 CPU 2가 우연히 동일한 메모리 위치에 대해 테스트 및 설정 지침을 발행하게 되면, DPRAM은 먼저 "내부 노트"를 확인하고 상황을 인식한 후, CPU 2에 대기하고 재시도해야 한다는 것을 알려 주는 BUSY 인터럽트를 발행한다.이것은 인터럽트 메커니즘을 이용하여 바쁜 대기나 스핀록의 구현이다.이 모든 것이 하드웨어 속도에서 일어나기 때문에, CPU 2가 스핀락에서 벗어나기 위한 기다림은 매우 짧다.

CPU 2가 메모리 위치에 액세스하려고 했든 아니든 간에, DPRAM은 CPU 1이 제공하는 테스트를 수행한다. 테스트에 성공하면, DPRAM은 CPU 1이 제공하는 값으로 메모리 위치를 설정한다. 그러면 DPRAM은 CPU 1이 그곳에 쓰고 있던 "내부 노트"를 지워버린다.이 시점에서 CPU 2는 테스트 앤 세트를 발행할 수 있으며, 이것이 성공할 것이다.

변동2길

CPU 1은 "메모리 위치 A"에 쓰기 위한 테스트 및 설정 지침을 발행한다.DPRAM은 메모리 위치 A에 값을 즉시 저장하지 않고, 대신 현재 값을 특수 레지스터로 동시에 이동시키는 동시에 메모리 위치 A의 내용을 특수 "플래그 값"으로 설정한다.이때 CPU 2가 메모리 위치 A로 테스트 및 설정을 실행하면, DPRAM이 특수 플래그 값을 감지하고 변동 1에서와 같이 BUSY 인터럽트를 실행한다.

CPU 2가 메모리 위치에 액세스하려고 했든 아니든 간에, 이제 DPRAM은 CPU 1의 테스트를 수행한다.테스트에 성공하면 DPRAM은 메모리 위치 A를 CPU 1에서 지정한 값으로 설정하고, 테스트에 실패하면 DPRAM은 값을 특수 레지스터에서 메모리 위치 A로 다시 복사한다.두 작업 중 하나를 수행하면 특수 플래그 값이 지워진다.CPU 2가 지금 테스트 앤 세트를 발행하면 성공한다.

테스트 및 세트의 소프트웨어 구현

일부 명령 집합에는 원자성 테스트 및 설정 기계 언어 명령이 있다.예로는 x86[3] 및 IBM System/360과 그 후계자(z/Architecture 포함)[4]가 있다.여전히 읽기-수정-쓰기 또는 비교-스왑 명령을 사용하여 원자성 시험-세트를 구현할 수 없는 경우.

부울 값과 함께 사용할 경우, 테스트 및 세트 명령은 함수가 원자적으로 실행되어야 한다는 점을 제외하고, 다음 함수에 표시된 것과 같은 논리를 사용한다.즉, 다른 어떤 프로세스도 기능을 중간 실행 중에 중단할 수 없어야 함수가 실행되는 동안에만 존재하는 상태를 볼 수 있다.그것은 하드웨어 지원을 필요로 한다. 보이는 것처럼 구현될 수 없다.그럼에도 불구하고 표시된 코드는 시험과 세트의 행동을 설명하는 데 도움이 된다.참고: 이 예에서 'lock'은 참조(또는 이름)에 의해 전달되는 것으로 가정하지만, 'initial'에 대한 할당은 새로운 값을 생성한다(참조만 복사하는 것이 아님). 

함수 TestAndSet(boolean_ref lock) {부울 초기 = 잠금, 잠금 = true; 초기 반환; }

원자적이 아닌 코드는 시험 및 설정 지침의 의미에서 볼 때 위와 같은 DPRAM 하드웨어 시험 및 설정에 대한 설명과도 다르다.여기서 설정되고 있는 값과 시험의 불변성이 고정되어 있고, 시험의 결과에 관계없이 그 값은 업데이트되는 반면, DPRAM 시험과 설정의 경우, 메모리는 시험이 성공했을 때만 설정되며, 설정값과 시험조건은 CPU에 의해 지정된다.여기서 설정할 값은 1만 될 수 있지만, 0과 1이 메모리 위치에 대한 유일한 유효한 값으로 간주되고, "값이 0이 아닌 경우"가 유일한 시험인 경우라면, 이는 DPRAM 하드웨어에 대해 기술된 사례와 동일하다(또는 보다 구체적으로 말하면, DDRAM 케이스는 이러한 제약조건 하에서 이것까지 감소한다).그러한 관점에서, 이것은 정확하게 그 용어의 전체적이고 전통적인 의미에서 "시험과 세트"라고 불릴 수 있다.주목해야 할 본질적인 지점은 시험과 세트의 일반적인 의도 및 원칙이다: 값은 시험되고 하나의 원자작전에서 설정된다. 즉, 시험하기 전에 다른 프로그램 스레드나 프로세스가 목표 메모리 위치를 변경할 수 없다. (이것은 위치가 현재 특정 값을 가지고 있는 경우에만 설정되어야 하기 때문이다.만약 그것이 조금 더 일찍 그 가치를 가지고 있었다면)

C 프로그래밍 언어에서 구현은 다음과 같다.

#Define LOCKED 1 1  인트로 test_and_set(인트로* 록프랙) {     인트로 oldValue;      // -- 원자 분절의 시작 --     // 이것은 예시를 위한 목적으로만 가성으로 해석되어야 한다.     // 이 코드의 전통적인 컴파일로는 원자성을 보장하지 않는다.     // 공유 메모리 사용(즉, 비사용 값), 컴파일러로부터의 보호     // 최적화 또는 기타 필수 속성.     oldValue = *록프랙;     *록프랙 = 잠긴;     // -- 원자 분절의 끝 --      돌아오다 oldValue; }

이 코드는 또한 실제로 원자 읽기-수정-쓰기 및 시험이라는 두 가지 작업이 있음을 보여준다.읽기-수정-쓰기만 원자적일 필요가 있다.(값 비교를 임의의 시간만큼 지연시키는 것은 일단 시험할 값을 얻은 후에는 시험의 결과가 달라지지 않기 때문에 이것은 사실이다.코드는 일단 초기값을 기록하면, 비록 아직 계산되지 않았더라도, 시험의 결과가 성립된다. 예를 들면 == 연산자에 의해서).

테스트 및 세트를 사용한 상호 제외

상호 배제를 구현하는 한 가지 방법은 다음과 같이 시험 및 설정 기반 잠금을[5][6] 사용하는 것이다.

의사-C 구현

휘발성이 있는 인트로 자물쇠를 채우다 = 0;  공허하게 하다 비판적인() {     하는 동안에 (test_and_set(&자물쇠를 채우다) == 1);     비판적인 단면  // 한 번에 하나의 프로세스만 이 섹션에 포함될 수 있음     자물쇠를 채우다 = 0;  // 중요 섹션을 마치면 잠금을 해제 }

잠금 변수는 공유 변수, 즉 모든 프로세서/스레드에 의해 액세스할 수 있다.휘발성 키워드를 기록해 두십시오.휘발성이 없는 경우 컴파일러 및/또는 CPU는 잠금 및/또는 캐시된 값 사용에 대한 액세스를 최적화하여 위의 코드를 잘못 표시할 수 있다.반대로, 그리고 불행하게도, 휘발성의 존재는 읽기와 쓰기가 기억력에 전념한다는 것을 보장하지는 않는다.일부 컴파일러는 메모리에 전념할 수 있도록 메모리 장벽을 발행하지만, C/C++의 휘발성의 의미론적 의미가 상당히 모호하기 때문에 모든 컴파일러가 그렇게 하지는 않을 것이다.컴파일러 설명서를 참조하여 작동하는지 확인하십시오.

이 기능은 여러 공정에 의해 호출될 수 있지만, 한 번에 하나의 공정만이 중요 섹션에 있을 것으로 보장된다.나머지 과정은 자물쇠가 채워질 때까지 계속 회전할 것이다.어떤 과정은 결코 자물쇠가 허락되지 않을 수 있다.이런 경우 그것은 끝없이 반복될 것이다.이것은 공정성을 보장하지 않기 때문에 이 시행의 단점이다.이 문제들은 성과 부분에 더 상세하게 설명되어 있다.

조립 이행

enter_interval:        ; "점프 대상" 태그, 함수 입력 지점.    tsl 등기하다, 깃발을 꽂다      ; 테스트 및 잠금 설정; 플래그는                      ; 공유 변수, 복사됨                      ; 레지스터 등록 및 플래그 입력 및 플래그 입력                      ; 그 다음 원자적으로 1로 설정한다.    cmp 등기하다, #0        ; entry_region에 0 플래그가 있었는가?    jnz enter_lights   ; 다음 경우 점프하여 enter_region(지역 입력)                      ; reg는 0이 아니다; 즉,                      ; 입장 시 깃발은 0이 아니었다.    되받아치다                ; 종료; 즉, 깃발이 0으로 켜져 있음                      ; 입장.만약 우리가 여기에 온다면, ts.                      ; 0이 아닌 것으로 설정될 것이다. 따라서,                      ; 우리는 자원을 확보했다.                      ; 깃발과 관련된.  leave_message:   움직이다 깃발을 꽂다, #0      ; 플래그에 0 저장   되받아치다                ; 발신자에게 돌아가기

여기tsl원자 명령이고flag잠금 변수.그 과정은 자물쇠를 따지 않으면 돌아오지 않는다.

시험·설정 잠금장치의 성능평가

일반적으로 잠금 장치에 대한 4가지 주요 평가 지표는 고정 취득 지연 시간, 버스 트래픽, 공정성 및 저장이다.[7]

시험과 세트는 그 중 두 가지, 즉 높은 버스 교통량과 불공평한 점수에 대해 낮은 점수를 받는다.

프로세서 P1이 잠금을 획득하고 프로세서 P2도 잠금을 기다리고 있을 때, P2는 잠금을 획득하려고 시도하면서 계속 버스 거래를 하게 된다.프로세서가 잠금을 얻었을 때, 동일한 잠금을 얻기를 원하는 다른 모든 프로세서는 잠금을 잡을 때까지 버스 거래를 반복적으로 개시하여 잠금을 얻으려고 계속 노력한다.이것은 시험과 세트의 버스 교통 요건을 크게 증가시킨다.이것은 캐쉬와 일관성 결여에서 오는 다른 모든 트래픽의 속도를 늦춘다.잠금 획득 시도 실패에 의해 트래픽이 포화 상태가 되기 때문에 전체 구간 속도가 느려진다.시험-시험-설정(Test-and-test-and-set)은 잠금 획득 요청을 지속적으로 개시하지 않기 때문에 TSL에 비해 개선된 것이다.

공정성을 고려할 때 프로세서가 잠금 장치를 해제할 때 잠금을 획득할 수 있는 공정한 기회를 얻을 수 있는지 고려한다.극단적인 상황에서는 프로세서가 굶어 죽을 수 있다. 즉, 해당 시간 동안 잠금이 자유로워졌음에도 장기간 잠금을 획득하지 못할 수 있다.

단 하나의 잠금만 필요하므로 TSL의 스토리지 오버헤드는 거의 없다.원자 명령과 분기가 하나만 필요하기 때문에 비경쟁 대기 시간도 낮다.

참고 항목

참조

  1. ^ Anderson, T. E. (1990-01-01). "The performance of spin lock alternatives for shared-money multiprocessors". IEEE Transactions on Parallel and Distributed Systems. 1 (1): 6–16. doi:10.1109/71.80120. ISSN 1045-9219.
  2. ^ Herlihy, Maurice (January 1991). "Wait-free synchronization" (PDF). ACM Trans. Program. Lang. Syst. 13 (1): 124–149. CiteSeerX 10.1.1.56.5659. doi:10.1145/114005.102808. Retrieved 2007-05-20.
  3. ^ "BTS—Bit Test and Set". www.felixcloutier.com. Retrieved 2016-11-21.
  4. ^ "IBM Knowledge Center". www.ibm.com. Retrieved 2016-11-21.
  5. ^ Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau (2015). Operating Systems: Three Easy Pieces (0.91 ed.). Arpaci-Dusseau Books – via http://www.ostep.org/. {{cite book}}:외부 링크 위치 via=(도움말)
  6. ^ Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. p. 252. ISBN 9780984163007.
  7. ^ Solihin, Yan (2016). Fundamentals of Parallel Architecture. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.

외부 링크