목차
- 임계구역(Critical Section)
- Peterson's Solution
- 동기화를 위한 하드웨어 지원(메모리 배리어, 하드웨어 명령, 원자적 변수)
- 뮤택스 락
- 세마포
- 모니터
- Liveness
- Lock Free
동기화 툴(Synchronization Tools)
배경(Background)
프로세스는 병행/병렬 실행이 가능합니다. 이때 여러 프로세스가 동시에 공유 데이터에 접근하여 경쟁 상태(race condition)가 발생해 데이터에 불일치가 생겨 데이터 무결성에 문제가 생깁니다.
멀티코어, 멀티 스레드 개발이 중요해지면서 자원 공유 가능성이 높은 여러 스레드를 경쟁 상태가 더 빈번해집니다. 이를 위해 각 스레드를 의도에 맞춰 동기화할 필요가 있습니다.
*경쟁 상태(race condition)란 공유 자원에 대해 여러 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태. 일반적으로 원하지 않는 방향일 경우를 뜻함.
임계구역 (Critical Section)
임계 구역(Critical Section) 혹은 공유변수 영역이란 병렬 컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원(데이터, 장치)을 접근하는 코드의 일부를 뜻합니다. 즉 공유자원에 접근하는 코드 부분입니다.
프로세스 동기화는 임계구역 문제에서 시작됩니다. 임계구역 문제란 프로세스들이 공유 자원에 접근할 때 의도대로 작동하도록 프로세스 자신의 활동을 동기화할 때 사용할 수 있는 프로토콜(약속)을 하는 것입니다.
각 프로세스는 임계구역 진입 전 입장 구역(entry section)에서 허가를 받고, 임계구역을 수행한 후 빠져나오는 퇴장구역(exit section)에서 퇴장 절차를 진행합니다. 이 3가지 구역을 제외한 나머지 부분을 나머지 구역(remainder section)이라 합니다.
임계 구역은 다음 3가지 요구 조건을 충족해야 해결할 수 있습니다.
1. 상호 배제(Mutual Exclusion) : 프로세스 P가 임계구역을 수행하고 있으면, 다른 프로세스들은 들어가면 안됩니다.
2. 진행(Progess) : 임계구역에 아무도 들어가 있지 않다면 진입할 수 있어야하고 이 요청은 무한정 연기되면 안됩니다.
3. 한정된 대기(Bounded Waiting) : 임계구역을 요청하고 허락받는 동안 다른 프로세스에게 양보해야 하는 횟수의 상한선이 있어야 합니다.
운영체제 내에서 임계구역을 다룰때도 선점형 / 비선점형 커널에 2가지 일반적인 접근법이 있습니다.
● 선점형(Preemptive) : 선점형 커널은 프로세스가 커널 모드에서 실행중일 때 선점을 허용합니다.
*SMP 아키텍쳐에서는 디자인이 어려움.
● 비선점형(Non-preemptive) : 비선점형 커널은 커널 모드에서 실행되는 프로세스의 선점을 허용하지 않습니다.
* 순간순간 커널에서 실행중인 프로세스는 하나임으로 동기화가 쉽습니다. 단 실시간 프로그래밍에 안좋습니다.
일반적으로 실시간 프로그래밍에서 이점이 있고, 하나의 프로세스가 오랫동안 실행될 위험이 적은 선점형 커널을 사람들은 선호합니다.
*만약 단일코어 시스템이라면?
단일 코어 시스템에서는 interrupt diabling을 사용하여 임계구역을 보호할 수 있습니다.
여기서 모든 프로세스가 CPU 획득 시 인터럽트를 무조건 차단한다면 비선점형 커널과 동일하게 동작합니다.
하지만 프로세스가 부분적으로 인터럽트를 차단한다면 선점형으로도 사용 가능하여 선점 / 비선점과는 무관합니다.
다중 코어/ 다중 프로세서 환경에서는 인터럽트를 막아버리니 효율성을 떨어트립니다.
Peterson's Solution
피터슨 솔루션은 현재는 쓰이지 않지만 아이디어가 유용한 내용입니다.
피터슨 솔루션은 임계구역과 나머지 구역을 번갈아가며 실행하는 2개의 프로세스로 한정되며 3개 이상에서는 불가능합니다. 피터슨 솔루션은 두 프로세스가 두 개의 데이터 항목을 공유하여 해결하며, 로드/스토어 명령어가 원자적(*atomic)하다 가정합니다.
*atomic : 원자에서 더 이상 깨지지 않는, 다른 조건으로 방해되지 않는 보장된다는 뜻.
int turn; // 임계구역 진입 순번
boolean flag[2]; // 각 프로세스가 임계구역 진입 준비 완료. 요청 표현
while(true) {
flag[i] = true;
turn = j;
while(flag[j] && turn == j)
; //do nothing
/* Critical Section */
flag[i] = false;
/* remainder section */
}
임계구역 진입을 위해 다음 두 프로세스 Pi, Pj는 아래와 같은 과정을 거칩니다.
● Pi는 flag[i]를 참으로 바꿉니다. 이건 Pi가 임계구역에 들어갈 준비가 되어 있음을 나타냅니다.
● turn은 j에게 우선 양보합니다.
● Pi는 flag[j]가 거짓. 즉 Pj가 나머지 구역을 수행중이거나, turn이 i, 즉 Pi가 입장 구역(entry section)에서 대기중이면 임계구역에 들어갈 수 있습니다.
임계 구역에 3가지 조건이 만족하는지 확인해봅시다.
1. 상호 배제(Mutual Exclusion) : flag[2] 와 turn 변수로 하나의 프로세스만 임계구역에 들어갈 수 있음을 알 수 있습니다.
2. 진행(Progress) : 임계구역을 수행하고 있는 프로세스를 제외한 나머지 다른 프로세스들은 while문에서 대기하기에 Progrss가 성립합니다.
3. 한정 대기(Bounded Waiting) : 각 프로세스는 while문에서 유한하게 대기합니다.
피터슨 솔루션은 싱글 스레드에서는 괜찮으나 멀티 스레드인 최신 컴퓨터에서는 잘 작동하지 않습니다. 이유는 멀티 스레드에 *reordering이 일관성을 깨거나 예상치 못한 결과를 발생시킬 수 있기 때문입니다.
*reordering : 재배치란 의미로 컴파일러가 메모리 접근속도를 향상시키기 위해 진행하는 것으로, 최적화를 위해 제한 범위 내 프로그램의 종속성이 없는 명령 위치를 바꿀 수 있습니다. 즉 변수 선언이나 명령이 위치 변경이 될 수 있습니다.
booleand flag = false;
int x = 0;
//1. Thread 1 performs
while(!flag)
;
print x;
//2. Thread 2 performs
x = 100;
flag = true;
1. 컴파일러가 순서를 바꿔 x를 while(!flag) 앞으로 로딩한다면 스레드 2가 순차적으로 실행되도 0을 출력할 수 있습니다.
2. 컴파일러가 비종속적인 두 명령어의 순서를 바꾸면 스레드 1은 0을 출력할 수 있습니다.
즉 2에서 x=100과 flag = true의 순서가 바뀌면 1의 스레드 1은 0을 출력할 수 있습니다.
동기화를 위한 하드웨어 지원
많은 시스템은 임계구역 코드를 구현을 지원하기 위해 하드웨어 명령을 제공합니다. 단일 코어라면 인터럽트를 차단하면 되지만 멀티 코어에서는 성능을 떨어트리기에 다음 3가지 기초적인 하드웨어 명령을 확인해봅니다.
1. 메모리 배리어(Memory Barriers)
메모리 모델이란 메모리를 통한 스레드의 상호작용과 데이터 공유 사용을 설명합니다. 일반적으로 메모리 모델은 아래 2가지 방법 중 하나에 속합니다.
1. 강한 순서(Strong ordered) : 한 프로세서가 메모리 변경을 하면 그 결과를 다른 모든 프로세서가 즉시 반영합니다.
2. 약한 순서(Weakly ordered) : 강한 순서에 반대로, 즉시 반영하지 않습니다.
컴퓨터 아키텍쳐는 메모리의 변경사항이 생기면 다른 모든 프로세서도 즉시 반영시키는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장합니다.
메모리 배리어(or Memory fence)란 CPU나 컴파일러에게 특정 연산의 순서를 강제하도록 하는 기능입니다. 즉 reordering하지 못하게 순서를 고정시키는 방법입니다. 메모리 배리어가 실행되면 현재진행중인 로드/스토어가 종료된 후에 새로운 로드/스토어가 수행하고 다른 프로세서에게 보이도록 합니다.
메모리 배리어는 매우 낮은 레벨의 연산으로 간주되고 커널 개발자가 상호 배제 코드를 특별히 작성할 때만 사용합니다.
2. 하드웨어 명령(Hardware Instructions)
메모리의 한 워드(word)의 내용을 검사/설정 하는 과정이나 두 워드의 내용을 교환(swap)하는 과정을 원자적으로(atomically), 즉 인터럽트 되지 않는(uninterruptibly) 원자적인, 쪼개지지 않는 단위로 실행해주는 특별한 하드웨어 명령어를 제공합니다.
● Test and Set instruction (의미적으로 아래와 같은거고 실제로는 single machine instruction)
boolean test_and_set (boolean *target){
boolean rv = * target; //이전 상태를 저장하고
*target = true //target을 참으로 만들고
return rv; //이전 상태 리턴
}
검사 + 값 설정을 동시에 하는 명령으로 이를 이용해 임계 구역에서 상호 배제를 다음과 같이 해결합니다.
리턴 값이 참이면 다른 프로세스가 임계구역에 있다는 의미입니다.
리턴 값이 거짓이면 임계구역에 아무도 없다는 뜻이고, 이미 lock을 참으로 만들어서 다른 프로세스는 임계구역에 못들어오니 자신이 들어갑니다.
● Compare and Swap (의미적으로 아래와 같은거고 실제로는 single machine instruction)
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if(*value == expected)
*value = new_value;
return temp;
}
value가 예측(expected)값과 같으면 새로운 new_value로 변경하고, 만약 예측과 다르다면 변경하지 않습니다.
항상 value의 original 값을 리턴합니다.
● Compare and Exchange (의미적으로 아래와 같은거고 실제로는 single machine instruction)
bool compare_and_exchange(int *value, int *expected, int new_value){
if(*value == *expected){
*value = new_value;
return true;
}
else{
*expected = *value;
return false;
}
}
value가 예측값과 일치하면 새로운 값으로 바꾸고 true를 리턴합니다.
value가 예측값과 불일치하면 예측값을 value로 수정하고 false를 리턴합니다.
3. 원자적 변수(Atomic Variables)
원자적 변수는 정수, boolean과 같은 기본적인 데이터에 원자적인 연산을 제공합니다. 이 동기화 툴 등을 바탕으로 위 compare_and_swap 명령어가 설계되어있습니다.
Mutex Lock
Mutex Lock은 Mutual exclusion Lock의 줄임말로 임계구역을 해결하기 위한 상위 레벨 해결책입니다. 즉, 상호배타를 위한 락입니다. 임계구역을 보호해 경쟁상태를 방지하기 위해 사용하며 프로세스는 임계구역 입장 전 반드시 락을 획득하고, 퇴장하며 락을 반납합니다.
추가설명(바쁜 대기, 스핀락)
*이 방법은 바쁜 대기(busy waiting) 방법을 씁니다. 바쁜 대기란 어떤 특정 공유자원에 대해 동기화 상황에서 권한 획득을 위해 특정 조건을 만족할 때 까지 대기하는 방식입니다. 스핀락 또한 바쁜 대기 개념을 이용한 방식입니다.
*스핀락 : 임계구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락입니다. while문 안에서 스레드가 빙빙 돌고있다여서 스핀락입니다.
스핀락은 CPU를 소모하지만 context switching이 필요 없어 유리한 면도 있습니다. 락에 대한 경쟁이 낮은 다중 코어 또는 다중 프로세서 환경에서는 스핀락의 성능이 우수합니다.
일반적으로 락을 걸고 있는 시간이 2개의 context switching 시간보다 작으면 스핀락이 유리합니다.
Mutex lock은 다음 3가지 함수가 있습니다.
1. acquire() : 락을 획득합니다.
2. release() : 락을 반환합니다.
3. available() : 락을 얻을 수 있는지 확인합니다.
* 1~2함수는 원자적이어야하며, test_and_set이나 compare_and_swap을 통해 구현될 수 있습니다.
세마포(Semaphores)
세마포는 여러가지 일이 가능한 툴로 한 공유 자원에 수용 가능 일/락이 여러개입니다.
세마포 S는 정수 변수로 S > 0이라면 임계구역에 들어갈 수 있으니 S는 활용 가능 리소스의 개수입니다.
세마포는 초기화와 단 2개의 원자적 연산인 wait(), signal()로만 접근합니다.
wait() 연산은 락을 얻기 위해 대기하고, 락을 얻습니다(S를 감소시킵니다.)
signal()연산은 임계구역에 퇴장하며 락을 놓습니다.(S를 증가시킵니다.)
세마포 사용방법
세마포는 초기화에 따라 2가지로 구분되는데, 세마포 초기화를 1로하여 범위가 0~1로 제한된다면 이진(binary)세마포라고 합니다. 이진 세마포의 경우 mutex lock처럼 1개만 사용할 수 있습니다.
세마포 초기화를 2이상으로 원하는 값으로 하는 경우 카운팅(counting)세마포라고 합니다.
카운팅 세마포의 초기화 값은 활용 가능 리소스 최대 개수로 볼 수 있고 wait(), signal()로 0~초기화 값 사이에서 감소/증가하게 됩니다. 세마포 값이 0이라면 모든 자원이 사용중임을 뜻합니다.
세마포 구현
바쁜 대기(busy waiting)의 경우 반복문으로 계속 대기를 하면서 CPU를 사용하기에 프로세스가 임계구역에서 금방 나올수록 유리합니다. 반대로 오래 머물면 성능이 안좋습니다.
세마포는 바쁜 대기를 피하기 위해 세마포는 waiting queue를 가지고 있고, 각 엔트리는 값과 다음 리스트를 가르키는 포인터를 가지고 있습니다.
세마포는 락을 얻을 수 있을 때까지 계속 기다리는게 아니라 waiting 큐에 들어가고 sleep()상태에 들어갑니다. (block)
락을 얻을 수 있다면 세마포는 waiting 큐에서 꺼내 ready 큐로 갑니다. (wakeup)
*sleep, wakeup은 프로세스를 일시 중지, 재실행 시키는 OS의 기본적인 시스템 콜입니다.
즉, 락을 못얻으면 waiting 큐에 넣어서 sleep()시키고, 이후 락을 얻을 수 있으면 wakeup()시킵니다.
모니터(Monitors)
뮤택스락, 세마포를 써도 오류는 여전히 발생할 수 있습니다. 입장구역, 퇴장구역 함수를 반대로 쓰거나, wait, signal() 연산을 실수로 2번 연속 하는 등이 있습니다.
이러한 오류 해결을 위한 방법 중 하나는 이런 여러 낮은 레벨에 동기화 도구를 통합해 잘만들어 고레벨 추상화 도구를 만들어 제공하는 것입니다. 모니터는 그 중 하나입니다.
모니터
추상화 데이터 타입(abstract data type, ADT)은 데이터와 데이터 연산을 하나의 단위로 묶은 타입으로, 연산은 데이터와 외부 사이 인터페이스 역할을 합니다.
모니터는 상호 배제가 보장되는 일련의 ADT입니다. 모니터는 인스턴스의 상태를 정의하는 변수들과, 이를 조작하는 프로시저/함수들의 본체를 포함하고 있습니다. 따라서 모니터 내에 정의된 함수만으로 모니터 내부 변수 등에 접근할 수 있습니다. 일종의 객체와 유사한 구조입니다(캡슐화) 또한 오직 하나의 프로세스만 한 순간에 모니터에 접근 가능해야합니다.
아래는 모니터 구조입니다.
프로세스(또는 스레드)는 모니터 안에서 함수를 방해받지 않고 실행할 수 있는 것을 보장받습니다. 하지만 위 구조는 다른 프로세스의 병행실행을 제공하지 못합니다. 만일 다른 프로세스의 병행실행을 허용하고 싶으면 조건변수를 추가하여 wait()을 실행함으로써 가능합니다. 즉 프로세스가 선점 위치를 스스로 지정할 수 있음을 뜻합니다.
모니터가 나온 시점은 객체지향이 일반화 되기 전으로, 그 전에도 객체와 유사한 구조를 적용중이었다고 합니다.
Liveness
Liveness는 프로세스가 실행되는 동안 Progress(진행)되는 것을 보장하기 위해 시스템이 충족해야 하는 속성입니다. 즉 프로세스가 락을 얻기 위해 무한정 대기하는 것 등은 Liveness 실패의 예입니다. 여러 형태가 있지만 모두 성능 등에서 부정적입니다.
교착상태(Deadlock)
데드락이란 2개 이상의 프로세스가 락을 얻기위해 대기하다가 무한정 대기하게 되는 상황입니다. 한 집합 내의 모든 프로세스가, 그 집합 내 다른 프로세스가 발생시킬 수 있는 이벤트를 대기중이라 모두 다같이 무한히 대기만 하는 경우 데드락이 걸렸다고 합니다. 이때 이벤트는 뮤택스 락, 세마포에서 자원 획득, 방출입니다.
기아(Starvation)
끊임없이 필요한 자원을 가져오지 못하는 상황으로, 데드락과 같이 무조건 영원히 대기중인 것은 아니지만, 대기 중 락을 얻을 기회를 계속 잃는것과 같은 상태입니다. 프로세스는 일시 중단된 세마포 대기열에서 제거되지 않을 수 있습니다.
우선순위 역전(Priority-Inversion)
우선순위가 낮은 프로세스가 락을 계속 들고있어 높은 우선순위에 프로세스가 접근을 못하는 상태입니다. 이 과정이 반복적으로 섞이면 스케줄링에 어려움을 줍니다.
통상적으로 우선순위 역전은 우선순위 상속 프로토콜(priority-inheritance protocol)을 구현하여 해결합니다. 우선순위 상속 프로토콜은 현재 자원을 소유한 낮은 순위의 프로세스가 자원을 요청한 높은 순위의 프로세스의 우선순위를 할당 받는 행위입니다.
Lock Free Algorithm (Non Blocking Algorithm)
뮤택스 락(스핀락), 세마포어(waiting queue, sleep), 모니터 등 락 기반 방법은 락을 획득한 스레드를 제외한 다른 스레드들이 해당 자원에 접근하지 못하도록 합니다. 이 방법은 굉장히 편한 방법이지만 단점으로 고성능을 요구하는 애플리케이션에서 요구사항을 만족하지 못할 수 있습니다.. 왜냐하면 락을 획득하지 못한 나머지 모든 스레드는 락이 다시 돌아올 때 까지 대기 상태에 있어야 합니다. 만약 락을 들고 있는 스레드가 락을 획득한 상태로 I/O, 메모리 페이징과 같이 시간이 소요되는 작업에 들어가면 나머지 모든 스레드가 그 기간동안 대기 상태에 들어갈 수 있습니다. waiting queue 관리 등이 필요하는 등 문제가 추가로 늘며 락에 대한 경쟁이 심해질수록 작업에 필요한 시간보다 동기화에 필요한 시간이 더 커질 수 있습니다.
Non - blocking algorithm
어떤 스레드의 실패나 대기상태에 들어가는 것이 다른 스레드의 실패나 대기 상태를 일으킬 수 없는 경우 Non - blocking 알고리즘이라고 합니다. 이때, Non - blocking 알고리즘이 시스템 전체 진행에 보장되는 경우, 즉 다른 스레드의 방해가 없을 때 항상 어떤 스레드는 작업을 바로 할 수 있는 경우 Lock - free, 그 중 스레드별 진행도 보장되는 경우, 즉 Lock free + 다른 스레드의 방해가 있어도 모두 일정 상수 시간 안에 작업을 할 수 있는 경우 wait - free라고 합니다.
Lock free는 다른 스레드가 계속 방해하면 기아 상태에 빠질 수 있습니다. 이 기아 상태에 빠지지 않게 더 발전시킨 알고리즘이 wait free입니다.
Non - blocking, Lock free는 compare-and-swap(CAS)와 같이 하드웨어에서 제공하는 저수준 명령을 사용합니다. 이를 통해 만약 둘 이상의 스레드가 충돌한 경우, 하나의 스레드는 승자가 되고, 나머지 스레드는 이 상황에서 탈출할지 계속 기다릴지 등을 정할 수 있습니다.
'강의 > OS' 카테고리의 다른 글
OS - Deadlock (0) | 2023.07.18 |
---|---|
OS - 동기화 예시 (0) | 2023.07.17 |
OS - CPU Scheduling (0) | 2023.07.13 |
OS - Thread (0) | 2023.06.29 |
OS - Processes (0) | 2023.06.27 |