Mutual Exclustion
- Mutual Exclustion(Mutex)는 Race Condition을 막기 위한 방법이다.
Race Condition: 두 개이상의 Processor나 Thread들이 공유자원을 사용할 때, 예상치 못한 결과를 만드는 현상
Critical Section: 공유자원에 진입하고 수정하는 코드의 부분
- 오직 한 Thread만 Critical Section에 진입 가능하다.
- 다른 Thread는 작업이 완료 될 때까지 기다린다.
- Thread가 Critical Section에 나오면 다른 Thread가 진입한다.
Lock
- void acquire(): lock이 free가 될 때까지 기다리고, lock을 얻는다.
- void release(): lock을 반납한다.
Lock을 구현하기 위해 고려해야할 사항
1. Correctness
- Mutual exclusion: 오직 한 Thread만 진입가능한가?
- progress: 여러개의 Thread가 Crtical Section에 진입하길 원하면, 반드시 하나는 들어가는가?
- Boundary Wating: Starvation이 생기지 않는가?
2. Fairness- Thread마다 공평하게 Lock을 얻을 수 있는가?
3. Performence- Multi-CPU와 Single CPU에서 Time Overhead가 어떻게 도출되는가?
Spinlock
- 초기에 구현된 lock 메커니즘
- Thread가 lock을 얻을 때까지 무한정 루프를 도는(busy-waits) 메커니즘
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#define NR_THREAD 2
typedef struct lock{
int helt;
}Lock;
Lock* l;
int* count;
void acuire(Lock* l){
while(l->helt);
l->helt = 1;
}
void release(Lock* l){
l->helt = 0;
}
void* up_count(void* data){
acuire(l);
for(int i =0;i<10000;i++){
*count = *count+1;
printf("count:%d\n", *count);
}
release(l);
}
int main(){
pthread_t pt[NR_THREAD];
int ptid[NR_THREAD];
l = (Lock*)malloc(sizeof(Lock));
count = (int*)malloc(sizeof(int));
*count = 0;
for(int i =0;i<NR_THREAD;i++){
ptid[i] = i;
pthread_create(&pt[i],NULL, up_count,(void*)&ptid[i]);
}
for(int i =0;i<NR_THREAD;i++){
pthread_join(pt[i],NULL);
}
free(count);
return 0;
}
implements Locks
1. SW
- Dekker's algorithm
- Peterson's algorithm
- HW
- Disable interrupt
- Hardware atomic instructions(Test-And-Set, Compare-And-Swap)
Peterson's algorithm
- 두 개의 프로세스만 상호 배제를 할 수 있는 알고리즘
- 각 프로세스가 진입하려 할 때 flag 변수와 턴turn 변수를 사용해, 진입 순서를 결정하여 mutual exclustion을 만족하게 한다.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#define NR_THREAD 2
int flag[2];
int turn;
int* count;
void acuire(int tid){
flag[tid] = 1;
turn = 1-tid;
while(flag[1-tid]==1 && turn == 1-tid);
}
void release(int tid){
flag[tid] = 0;
}
void* up_count(void* data){
int tid = *(int*)data;
acuire(tid);
for(int i =0;i<10000;i++){
*count = *count+1;
printf("count:%d\n", *count);
}
release(tid);
}
int main(){
pthread_t pt[NR_THREAD];
int ptid[NR_THREAD];
count = (int*)malloc(sizeof(int));
*count = 0;
for(int i =0;i<NR_THREAD;i++){
ptid[i] = i;
pthread_create(&pt[i],NULL, up_count,(void*)&ptid[i]);
}
for(int i =0;i<NR_THREAD;i++){
pthread_join(pt[i],NULL);
}
free(count);
return 0;
}
Disabling Interrupt
-
컴퓨터 시스템에서 모든 Interrupt를 비활성화 하는 것이다. 이를 lock처럼 사용가능하다.
-
Interrupt가 발생하면 Interrupt Service Routine이 실행된다. 이 과정에서 예기치 못한 결과를 초래할 수 있다. 그래서 Disable Interrupt가 필요한 것이다.
-
하지만 Interrupt는 반드시 kernel에서 enable/disable된다. 따라서 모든 Interrupt를 enable/disable하는 것은 시간이 길다.
-
적절한 상황에 사용하는 것이 좋다. 일반적으로 multi-core에서는 적합하지 않고 Kernel level에서 사용하는 것이 좋다.
Test-And-Set
- Atomic Instruction
원자적 연산은 시작되면 중간에 중단되지 않고 완전히 수행되는 연산이다.
연산이 완료되거나 시작되지 않은 것처럼 보장된다. 이는 "모두 아니면 전혀 없음의 특성을 가진다. HW에게 맡긴다.
Atomic Instruction을 쓰는 이유
Lock은 반복적으로 상태를 체크하거나, 대기하는 동안 스레드를 일시 정지시키는 등 추가 오버헤드가 발생할 수 있다. 하드웨어 지원 Lock을 사용하면 이러한 오버헤드를 줄일 수 있다.
- Test-And_Set Instruction
test와 set을 한꺼번에 수행해주는 instruction이다.
int TestAndSet(int *v, int new) {
int old = *v;
*v = new;
return old;
}
void acuire(Lock* l){
while(TestAndSet(&1->helt,1);
}Compare-And-Swap
-
Atomic Instruction
-
Compare-And-Swap Instruction메모리의 특정 위치 값이 예상한 값과 동일할 때만 값을 변경한다.
int CompareAndSwap(int *v, int expected, int new) {
int old = *v;
if (old == expected)
*v = new;
return old;
}
void acquire(Lock *l) {
while(CompareAndSwap(&l->held, 0, 1));
}