하드웨어 동기 화 지원 - TAS 와 CAS 명령

목차

Test and Set

Compare and Swap

CAS 를 사용 하여 스 레 드 안전 을 실현 하 는 데이터 구조.

현재 주류 의 다 중 프로세서 구 조 는 모두 하드웨어 수준 에서 동시 다발 동기 화 에 대한 지원 을 제공 하고 있다.오늘 우 리 는 매우 중요 한 하드웨어 동기 화 명령 두 가 지 를 토론 합 니 다: Test - and - set 과 Compare - and - swap
Test and Set
Test - and - set (TAS) 명령 은 두 가지 절 차 를 포함 하여 주어진 메모리 주 소 를 1 로 설정 한 다음 이전 값 으로 되 돌려 줍 니 다.이 두 단 계 는 하드웨어 에서 하나의 원자 조작 으로 실현 되 며, 실행 기간 동안 다른 프로세서 에 의 해 중단 되 지 않 습 니 다.(하나의 CPU 는 Dual - port RAM 전자 원본 에서 제공 하 는 TAS 명령 을 사용 할 수 있 고 CPU 자체 도 CAS 명령 을 제공 할 수 있 습 니 다) 주의해 야 할 것 은 TAS 명령 은 1 비트 (bit) 에서 이 루어 집 니 다. 이 는 변수 가 0, 1 이 아니 라 다른 값 이 없 으 며 TAS 는 항상 변 량 을 1 로 설정 합 니 다.이 를 통 해 알 수 있 듯 이 TAS 는 자전 자물쇠 로 태 어 났 고 다음은 TAS 를 사용 하여 자전 자 물 쇠 를 실현 하 는 위조 코드 [2] 이다.

lock = 0 //shared state
while(test_and_set(lock)==0){ //try lock
       //do nothing   
}
//      
lock = 0   //release 

첫 번 째 스 레 드 가 이 코드 를 실행 할 때 TAS 명령 은 즉시 lock 을 1 로 설정 하고 0 으로 돌아 갑 니 다. 스 레 드 는 while 순환 을 종료 하고 임계 구역 에 들 어 갑 니 다.다른 스 레 드 가 임계 구역 에 들 어 가 려 고 시도 하면 TAS 는 lock 을 1 로 설정 하지만 1 (첫 번 째 스 레 드 의 TAS 명령 에서 1 로 설정) 을 되 돌려 줍 니 다. 이때 두 번 째 스 레 드 는 while 순환 (바 쁜 대기) 을 합 니 다. 첫 번 째 스 레 드 가 임계 구역 코드 를 종료 할 때 까지 lock = 0 을 실행 합 니 다. 즉, 자 물 쇠 를 풀 었 습 니 다.while - loop 을 통 해 자 물 쇠 를 가 져 오 기 를 기다 리 는 것 을 자 회전 자물쇠 (spin lock) 라 고 합 니 다.
Compare and Swap
compare - and - swap (CAS) 명령 은 TAS 명령 과 유사 하지만 TAS 보다 더 복잡 합 니 다.TAS 에 매개 변수 가 하나 밖 에 없 는 것 과 달리 CAS 명령 은 세 개의 매개 변수 가 필요 합 니 다. 하나의 메모리 위치 (V), 하나의 기대 구 값 (A), 새로운 값 (B) 이 필요 합 니 다.CAS 명령 의 실행 과정:

1.    V     A  ？
2.    ，    B      V   
3.     ，      。
4.      ，CAS     V      。

의사 코드:

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

이상 의 과정 은 CAS 명령 에서 원자 조작 이다.CAS 는 32bit / 64bit 의 데이터 형식 을 지원 하기 때문에 CAS 는 더욱 복잡 한 자 물 쇠 를 실현 할 수 있다.
CAS 를 사용 하여 안전 한 데이터 구 조 를 실현 합 니 다.
우 리 는 CAS 를 사용 하여 동시 다발 적 인 균형 이 진 트 리 를 실현 합 니 다.[1] 기본 적 인 사 고 는 모든 업데이트 작업 이 이 진 트 리 의 사본 에서 이 루어 져 야 한 다 는 것 이다. 업데이트 가 완 료 된 후에 CAS 명령 을 사용 하여 새로운 뿌리 노드 를 인용 하여 오래된 인용 을 교체 하 는 것 이다.

//    
  root = pointer to the root of the tree
//    
do
  old_root = root
  new_root = new Tree
  # copy old_root into new_root
  # do insertion into new_root
until compare_and_swap (root, old_root, new_root) == old_root
    :
do
  old_root = root
  new_root = balanced_copy_of (old_root)
until compare_and_swap (root, old_root, new_root) == old_root

균형 작업 과 삽입 작업 을 병행 하면 삽입 작업 이 완료 되면 이 진 트 리 의 뿌리 노드 를 새로운 참조 로 가 리 킵 니 다.균형 조작 이 완료 되면 compareand_swap 는 실패 할 것 입 니 다. 이 때 루트 노드 가 삽입 작업 으로 인해 발생 하 는 새로운 주 소 를 가리 키 기 때문에 더 이상 old 와 같 지 않 습 니 다.루트, 균형 작업 은 루트 노드 를 성공 적 으로 업데이트 할 때 까지 반복 적 으로 실 행 됩 니 다.마찬가지 로 균형 작업 이 삽입 작업 보다 먼저 완료 되면 작업 을 삽입 하 는 CAS 명령 도 실패 합 니 다 (루트 노드 가 균형 작업 이 발생 하 는 새로운 주 소 를 가리 키 고 있 음). 그리고 작업 이 성공 할 때 까지 반복 순환 을 삽입 합 니 다.
CAS 명령 을 바탕 으로 기본 적 인 신 호 량, 상호 배척 량 을 실현 할 수 있 을 뿐만 아니 라 더욱 복잡 한 lock - free 와 wait - free 알고리즘 도 실현 할 수 있다.
확장 읽 기:
1. 코 넬 대학교 운영 체제 과제: Architectural support for synchronization 2. wiki: Test - and - set 지령 3. wiki: Compare - and - swap 지령 4. TAS vs CAS