ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Transactional Memory #1
    Tech/Computer 2013.11.12 14:58

    들어가는 말 : Transactional Memory은 왜 등장하게 되었나?

    Parallel Computing은 Single Core의 한계를 극복하는 차세대 컴퓨팅 기술이지만, 이러한 컴퓨터 시스템 위에서 동작하는 Parallel Programming은 아직 원론적인 문제로 고통받고 있다. 바로 공유되는 자원을 어떻게 관리하는가 하는 문제다.

    Parallel Programming에서 공유자원은 어떻게 동기화하는가?

    똑같은 메모리를 이 Thread도 쓰고, 저 Thread도 쓴다면 누구 장단에 따라 움직여야하는가? 먼저 잡은 놈이 임자라고, 먼저 접근한 Thread에게 우선권을 주면 될 것 같지만, 모든게 Parallel하게 돌아가는 시스템에서는 이 "누가 먼저"를 알아내기가 쉽지 않다. 중앙에 막강한 관리자가 있어서 교통 정리를 해주면 좋겠지만, 하지만 Parallel Computing이 Parallel이 아니게 돼! 그래서 흔히 2가지 방법을 쓴다.

    Pessimistic Solution: Lock

    최대한 비관적으로 생각해보자. 내가 이 메모리에 접근할 때 항상 다른 녀석도 접근할 것 같다. 그래서 내가 차지하게 되면, Lock을 걸어서 일단 막고보는 방법이다. Pessimistic Solution은 그 이름처럼 공유 자원이 항상 여러 Thread에 의해 동시에 접근될 수 있다는 생각에 기반한다. 그래서 공유 자원에 접근하는 Thread는 항상 Lock을 통해서 다른 Thread의 접근을 차단한다. 가장 안전한 방법 같지만, 여기에는 몇가지 문제점이 존재한다.

    Dead Lock

    아래와 같은 2개의 Thread가 있다고 하자. 두 프로그램은 모두 자원 A와 B를 사용한다.

    2개의 Thread는 독립적으로 자기 일을 시작할 것이다. 각 Thread는 A와 B에 대해서 접근한다. 이 때, Pessimistic하게 동작함을 기억하자. 각 Thread는 자기가 다루는 자원 A와 B를 다른 이가 접근하지 못하도록 잠근다. (Lock)

    그런데 해당 일을 마무리하려면, Thread 1은 자원 B가 필요하다. 하지만 Thread 2가 자원 B를 잠궈놓았기 때문에 접근할 수가 없다. Thread 2가 하고 있는 일이 끝나야 접근할 수가 있으니까 기다려야 한다. 그런데, Thread 2는 일을 끝내려면 자원 A가 필요하다. 자원 A는 Thread 1이 잠궈놓았다. Thread 2는 그 일이 끝나길 기다려야한다. ?!

    이러한 현상을 Deadlock이라 한다. Lock을 통해 Parallel Computing을 제어하게 되면 이러한 Deadlock에 빠지기 쉽다. 이 Deadlock을 피하도록 Thread Programming을 하는 것은 프로그램이 커질수록 더 더 쉽지 않다.

    Priority Inversion

    뿐만 아니라 Thread간 우선 순위가 뒤집히는 문제점도 발생한다. Lower-Priority가 먼저 공유자원을 점유하고 있으면, 조금 늦게 시작한 Thread는 우선순위가 높더라도 (Higher-Priority) 공유자원이 Lock걸려 있기 때문에 진행할 수가 없다.

    즉, 우선 순위에 상관없이 먼저 공유자원을 점유한 Thread가 실행된다는 것으로 Priority가 무시된다는 단점이 있다.

    Convoying

    공유 자원을 점유하고있는 Thread가 OS-level의 Interrupt를 받아 정지하게 된다면 문제가 발생한다. Page Fault 혹은 기타 이유로 인해 Interrupt가 발생해서, 공유 자원을 점유 중인 Thread가 정지된다면, 이 Thread를 기다리고 있는 다른 모든 Thread도 기다릴 수 밖에 없다.

    또한, 공유 자원에 대한 Lock을 사용하기 위해서는 OS-level Service를 사용해야하기 때문에 수시로 Kernel Instruction을 사용하게 되고 성능이 저하될 수 밖에 없다. 위 문제를 해결하기위해서는 Thread에서 Lock을 호출하는 부분을 최대한 적게 가져가는 것이 좋지만, 이럴수록 앞서 이야기한 Lock관리를 위한 Overhead가 증가하고 시스템 성능이 저하된다.

    Optimistic Solution: Transactional Memory

    이러한 문제점으로 인해서 Lock을 사용하지 않는 Parallel Programming에 대해 연구가 진행되었다. 그리고 제안된 방법이 바로 Transactional Memory다. 간단히 설명하면 이렇다. 현재 공유자원을 사용하는 Thread는 나 하나뿐이겠지, 하는 생각 아래 일단 그냥 사용한다. 마지막에 변경된 내용을 적용할 때에서야 혹시 다른 Thread가 접근해서 충돌이 발생했는지 확인해본다. 만약 충돌이 있었다면 처음부터 새로 한다. 일단 해보고 안되면 다시 해보지 뭐가 바로 이 방식의 철학이다.

    이 Transactional Memory는 아래 논문에서 최초로 제안되었다.

    M. Herlihy, J. Eliot, and B. Moss, “Transactional Memory: Architectural Support For Lock-free Data Structures,” presented at the Computer Architecture, 1993., Proceedings of the 20th Annual International Symposium on, 1993, pp. 289–300.

    다음 포스팅에서는 이 Transactional Memory의 동작에 대해서 좀 더 자세히 알아보자.

    댓글 0

Designed by Tistory.