[Operating System] Synchronization Tools (1)

Hardware Support for Synchronization

Memory Barriers

• Memory model : 컴퓨터 아키텍쳐가 application program에게 메모리를 어떻게 줄 지에 대한 방식. 두 가지 유형이 있다.
  1. Strongly ordered : 한 프로세서에서의 메모리 변경이 즉시 다른 프로세서들에게도 visible하다.
  2. Weakly ordered : 한 프로세서에서의 메모리 변경이 다른 프로세서들에게 즉시 보이지 않을 수도 있다.
• processor의 종류마다 memory model이 다르기 때문에, 이 문제를 해결하기 위해 computer architecture는 instruction을 제공하는데, 메모리 변화를 다른 모든 프로세서들에게도 visible하게 만들기 위해 force 한다.
  • visible? : memory 변화가 visible하다는 것은 말 그대로 수정 후의 결과를 다른 프로세스에서도 확인할 수 있다는 것인데, 성능 이슈로 캐시에 데이터가 수정되고 저장된 후에는 다른 프로세스에서 이 바뀐 값에 접근할 수 없다. 이 캐시값을 기존 메모리에 반영 한 후에야 다른 프로세스는 확인할 수 있게 되고, 이 상태를 다른 프로세스에게 visible하다고 한다. 자세히는 모르겠지만 뭔가 추측컨데 변수 2개가 캐시에 존재하고 순서대로 바꾼다고 했을 때, 최적화 과정에서 캐시에 있는 값 2개가 바뀌고, 그 후 캐시를 메모리에 옮기는 과정에서 순서가 바뀌거나 할 수도 있을 것 같다.
• 이 instruction이 memory barriers or memory fences라고 불린다.
• 어쨌든 동작원리는 지금까지 있었던 load나 store가 완전히 끝나고 cache와 memory의 업데이트도 마치는 것이고, 그로 인해 visible하게 된다. 그 후에 뒤의 load나 store가 실행하게 된다.
• memory barrier를 통해 메모리 참조 순서를 보장할 수 있고, 이를 통해 memory barrier가 있기 전 까지의 상태를 visible하게 만들 수 있다.
• 이 원리를 이용해서 코드 사이에 집어넣으면 그 두 코드는 실행 시에 순서가 바뀌지 않는다.
  
  • x값을 load해오기 전에 flag가 먼저 load된다.
    
  • x값에 store하는 것이 flag에 store보다 먼저 실행된다.

Hardware Instructions

• atomic : uninterruptible unit

• machine마다 명령이 다르므로, 추상화된 다음 두 instruction들을 통해 설명한다.

• test_and_set(), compare_and_swap() instructions

  • test_and_set()
    
    • target -> false라면 target -> true로 바꾸고 false 리턴.
    • target -> true라면 true 리턴.
      

• test_and_set()함수의 특징 : atomic하다. 즉, 만약에 서로 다른 core에서 동시에 실행된다면 실제로 동시에 실행되지 않고 특정한 순서대로 실행하게 된다.

• 만약 machine이 atomic한 test_and_set()함수를 지원한다면, boolean변수 lock을 선언해서 false상태로 놓고 mutual exclusion을 구현할 수 있다.

  • compare_and_swap() (CAS)
    
    • 이 함수의 경우에도 atomic하기 때문에 mutual exclusion을 구현하는 데에 사용될 수 있다.
      
    • 위 알고리즘은 mutual exclusion은 만족하지만, bounding-waiting은 만족하지 않는다.
      
    • 여기서 common data structure는 아래와 같다. (나머지는 스레드 별로 별개임)

      boolean waiting[n];
      int lock;

    • 코드를 보면, critical section 이후에 index를 순회하면서 특정 index에 해당하는 스레드가 waiting 상태라면 waiting을 해제해 주고, waiting중인 스레드가 없다면 lock을 0으로 바꾸어 주어 이후에 critical section에 들어오고자 하는 스레드를 바로 들어오게끔 만들어 준다.
    • critical section problem 해결 조건
      1. mutual exclusion
         • 우선 CAS가 atomic이므로 처음 critical section에 들어오는 행위는 한 스레드만 가능.
         • 그 이후 대기중인 프로세스가 있다면 그 프로세스 먼저 실행해 주는데, waiting값이 false로 바뀌는 시점은 critical section 이후이므로 mutual exclusion이 만족됨.
         • 대기중인 프로세스가 없다면 lock을 0으로 설정함. -> 이 동작 또한 critical section 이후에 이루어지므로 mutual exclusion이 만족됨.
      2. progress
         • 1번의 경우와 설명이 동일하다. 그냥 말 그대로 비어있으면 대기중인 스레드를 실행시키거나 다음 요청이 들어오는 스레드를 실행시키므로 만족된다.
      3. bound-waiting
         • index를 순회하면서 다음 기다리는 프로세스가 존재하는지 확인한다 -> 순회하기 때문에 결국 최대 n - 1회 기다리고 나서 실행하게 된다.
         • 반례?? : 만약에 총 스레드 수가 10개 이고, 6번 스레드가 실행된 이후에 idx가 순회하다가 8번을 순회하자마자 7, 8번 스레드가 waiting 상태가 되면 어떻게 되나요?
           • 6번 스레드 내부에서 순회를 하다가 나머지 waiting이 없으므로 6번에서 멈추고 lock을 0으로 바꿈 -> 정말 운 나쁘게도 lock을 0으로 바꾸고 난 뒤에 7번 스레드가 실행되는 것이 아니라 8번 프로세스의 CAS가 실행됨 -> 8번 스레드가 실행되고 나서 다시 순회하면서 7번 스레드가 waiting 중이라는 것을 발견하고 실행하게 해 준다.
           • 결국에 n - 1이 엄격하게 보자면 upperbound가 아니라고 할 수 있다. 하지만 결국 기다리는 횟수는 2n이하로 정해져 있으므로 어쨌든 bounded라고 볼 수 있다.

• test_and_set()과 compare_and_swap() : computer architecture에서 자세히 배울 수 있다.

Atomic Variables

• 일반적으로 compare_and_swap() instruction은 mutual exclusion에 직접적으로 쓰이지 않고 다른 방법들의 기반으로 쓰인다. 그 예시로 atomic variable이 있다.
• atomoic variable?
  • data type에 atomic operations를 지원해 준다.
  • special atomic data types와 atomic variable에 접근하고 값을 바꾸는 함수들을 지원해 준다.
• atomic variable관련 함수 예시
  • increment(&sequence);

    void increment(atomic_int *v)
    {
    	int temp;
        
        do {
        	temp = *v;
        }
        while (temp != compare_and_swap(v, temp, temp + 1));
    }

    • increment() 함수의 목적은 동시에 increment()가 동작했을 경우 순서대로 1씩 더해서 결론적으로 2가 증가하게 만드는 것이 목표이다.
    • 기존에 동시에 더해지는 경우, 예를 들어 두 스레드가 2인 현재 상태를 저장해 놓고 1씩 늘려서 3이라는 값으로 바꾸어 주게 되면 결국 두 스레드 모두 3이라는 값으로 저장하게 된다.
    • 하지만 위 방법을 사용하게 되면, compare_and_swap()에 의해서 둘 중 하나만 실행하게 되고, 처음 실행에 의해 v값은 1이 증가하게 되고 함수를 탈출한다. 그 이후에 두 번째 실행이 이루어지는데, 그 두 번째 실행에서는 v와 temp값이 서로 다르므로 while문을 한 번 더 돌게 되고, 그 이후 업데이트된 temp값을 이용하여 다시 1이 더 증가하게 되어 결론적으로 2가 증가하게 되는 것이다.
• atomic도 무적은 아니기 때문에 모든 race condition이 해결되지는 않는다.
  • section 6.1의 내용을 다시 보면(producer-consumer problem), consumer가 두 명 이상일 경우 atomic variable로 count를 쓴다고 할 지라도 count가 1이 된 순간 두 consumer 모두 소비를 하게 될 것이므로 race condition이 해결되지는 않는다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition