-
개념
-
멀티 스레드 프로그래밍 환경에서 적용 가능한 개념
-
어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이뤄져도 프로그램의 실행에 문제가 없는 것
-
두 개 이상의 스레드가 Race Condition 에 들어가거나 같은 객체에 동시에 접근해도 연산 결과는 정합성이 보장될 수 있도록 메모리 가시성이 확보된 상태
-
Thread Safe한 코드를 작성하는 것은 근본적으로 여러 스레드에서 공유되는 객체나 클래스의 상태에 대한 접근을 관리하는 것
경쟁 상태 (race condition)
두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이뤄졌는지에 따라 그 실행 결과가 달라지는 상황
메모리 가시성 (Memory Visiblity)
Thread에서 변경한 특정 메모리 값이 다른 Thread에서 제대로 읽어지는 지.- 스레드들이 하나의 변수를 공유할 경우, 각각의 프로세서 캐시가 변수의 복사본 소유
- 여러 스레드에 의해 캐시의 공유 변수 값이 변경되고 캐시 불일치 문제 발생할 수 있음
- 스레드가 동일 변수를 다른 값으로 바라보는 문제 발생 가능
-
- 멀티 쓰레드 환경에서 여러 쓰레드가 동시에 접근할 경우 데이터 손상이나 프로그램 오류가 발생할 수 있는 코드 영역.
임계 영역 문제 해결을 위한 필요조건
- 상호배제 (Mutual exclusion)
- 임계영역에 프로세스가 있으면, 다른 프로세스의 진입을 금지
- 진행 (Progress)
- 임계 영역에 접근하려는 프로세스가 무한정 대기하지 않고 결국은 임계 영역에 접근할 수 있어야 함
- 한정대기 (Bounded waiting)
- 임계 영역에 접근하려는 프로세스의 수가 제한되어 있어야 함
1. Re-entrancy (재진입성)
- 스레드 호출과 상관없이 프로그램에 문제가 없도록 작성하는 방법
2. Thread-local storage (쓰레드 지역 저장소)
- 공유 자원의 사용을 최대한 줄이고, 각각의 스레드에서만 접근 가능한 저장소들을 사용함으로써 동시 접근을 막음
- 일반적으로 공유 상태를 피할 수 없을 경우 사용
3. Atomic operation (원자 연산)
- 공유자원에 원자적으로 접근하는 방법
- Atomic
- 공유 자원 변경에 필요한 연산을 원자적으로 분리
- 실제 데이터 변경이 이뤄지는 시점에 Lock 걸기
- 데이터 변경 시간동안 다른 스레드의 접근 막기
4. Mutual exclusion (상호 배제)
-
공유자원 또는 임계영역에 하나의 스레드만 접근할 수 있도록, 세마포어/뮤텍스로 락을 통제하는 방법
- 일반적으로 많이 사용하는 방법
-
primitives
- Mutual exclusion을 구성하는 기본 연산
- enterCS() : 임계영역 집입 전 검사 및 다른 프로세서 존재여부 검사
- exitCS() : 임계영역 벗어날 시 후처리 과정 및 임계영역 벗어남을 알림
-
대표 알고리즘
- 뮤텍스(Mutex)
- 임계 영역에 접근할 수 있는 프로세스를 한 번에 하나만 허용하는 동기화 방법
- 임계 영역을 사용하고 나면 뮤텍스를 해제해야 함
- 세마포어(Semaphore)
- 임계 영역에 접근할 수 있는 프로세스의 수를 제어하는 동기화 기법
- 세마포어 값이 0보다 크면 임계영역에 접근, 값이 0이면 접근을 기다린다.
- 모니터(Monitor)
- 조건 변수를 사용하여 특정 조건이 충족될 때까지 프로세스를 대기시키는 동기화 기법
- Java : synchronized 키워드, wait()/notify() 메서드
- 뮤텍스(Mutex)
-
Lock의 필요성
프로세스는 서로 독립적인 메모리 주소 공간을 부여받음- shared memory 경우가 아닌이상 같은 데이터에 동시에 접근할 일 없음
스레드의 경우 부모 프로세스의 메모리 공간을 공유함- 여러 스레드들이 같은 데이터에 접근할 경우 문제 발생
- 이와 같이 동기화시 공유 자원에 대한 관리 필요
-
개념
- 병렬 프로그래밍에서 동기화를 달성하기 위한 도구
- 여러 스레드의 공유 자원 동시접근 제한
- 스레드의 실행순서 조절로 데이터의 일관성과 안정성 보장
- 락은 크게 뮤텍스와 세마포어로 나뉨
Non-Blocking 알고리즘
-
개념
- 하나의 스레드가 블록되거나 멈추지 않고도 다른 스레드들이 계속 작업을 수행할 수 있도록 하는 알고리즘
-
구현
- 일반적으로 원자성(atomicity)과 적절한 동기화 기법을 사용해 이뤄짐
- 저수준의 하드웨어에서 제공하는 compare-and-swap (CAS연산)등의 명령을 사용하는 알고리즘
-
특징
- 병렬 컴퓨팅 환경에서 높은 성능과 응답성 제공
- 데드락 문제 회피 시 유용
- 운영체제, JVM 프로세스, 스레드 스케줄링 작업, 가비지 컬렉션 작업, 락이나 기타 병렬 자료 구조를 구현하는 부분에서 사용
- 구현이 복잡하고 오류 찾기 어려움
Lock Free 알고리즘
- Non-Blocking 알고리즘에서 각 단계마다 일부 스레드는 항상 작업을 할 수 있는 경우
Lock 기반 알고리즘의 단점
- Lock에 대한 경쟁이 심해질수록, 실제로 필요한 작업을 처리하는 시간 대비 동기화 작업에 필요한 시간이 길어져 성능이 떨어짐
CAS 연산
-
개념
- 병렬 프로그래밍에서 동기화를 위한 기술로, 여러 스레드가 동시에 공유 변수를 수정하는 상황에 사용
- 스레드간 경합 조건을 줄이고 동기화 오버헤드를 최소화하는 방식으로 병렬 프로그래밍 지원
- 일반적으로 원자적 연산을 지원하는 하드웨어에서 지원
- 이를 기반으로 락이나 뮤텍스보다 경량적인 동기화 메커니즘 구현
-
CAS 연산 구조
- 3개의 인자 사용
- 대상 메모리 위치(V) : 값을 변경하려는 변수의 주소나 위치
- 예상 기존 값(A) : 현재 V에 저장된 값과 비교할 값
- 새로 설정할 값(B) : V에 저장될 새로운 값
-
CAS 동작 원리
-
- V의 현재 값을 A와 비교
-
- V의 값이 A와 같을 경우 V의 값을 B로 변경
-
- V의 값이 A와 같지 않을 경우 아무동작하지 않음
-
-
특징
- 원자적 연산
- CAS연산은 단일 연산으로 간주되며, 값을 비교하고 변경하는 동작이 원자적으로 수행
- 즉, CAS연산이 진행되는 동안 다른 스레드가 V의 값을 변경하지 못함
- 성공 및 실패 리턴
- CAS연산 성공 여부와 관계 없이 현재의 V값 리턴
- CAS연산을 성공한 스레드는 새로운 값을, 실패한 경우 현재값(A와 비교한 값)을 얻음
- 경쟁조건과 데드락 회피
- 여러 스레드가 동시에 CAS연산을 시도할 때, 오직 하나의 스레드만 성공하고 나머지 스레드는 실패함
- 실패한 스레드들은 다시 시도 혹은 다른 처리 방법 선택으로 경쟁 조건 회피
- 원자적 연산