critical section 내에서 mutual exclusion 기능을 제공하여 race condition을 방지하거나 정확한 실행을 보장하는 메커니즘!!!
Race condition
여러 프로세스/스레드가 동시에 공유 데이터에 액세스하고 이를 조작하는 상황
Critical Section
공유 리소스에 액세스하는 코드
Mutual Exclusion
동시에 하나의 프로세스/스레드만 critical section에 포함되도록 보장해야 하는 요구 사항
Condition variable(다음 정리에서 구체적으로)
프로세스가 특정 작업이 발생할 때까지 대기하도록 허용
3. Mutual Exclusion
1) Mutual Exclusion
모든 프로세스가 동일한 리소스 Ra에 액세스하므로 한 번에 하나의 프로세스만 critical section에 포함되는 것이 좋음
Mutual exclusion을 시행하기 위해 entercritical및 exitcritical 라는 두 가지 함수를 제공
다른 프로세스가 critical section에 있는 동안 동일한 리소스에 대해 critical section으로 들어가려고 하는 모든 프로세스는 wait 상태가 됨
(1) 예시
데이터 a와 b의 두 항목이 a = b로 유지된다고 가정
즉, 한 값을 업데이트하는 모든 프로그램은 관계를 유지하기 위해 다른 값도 업데이트해야 함
이제 두 프로세스가 각 개별 데이터 항목(a 및 b)에 대한 mutual exclusion을 존중하는 다음과 같은 동시 실행 시퀀스를 고려
각 프로세스의 전체 시퀀스를 critical section으로 선언하여 문제를 피할 수 있음
우리는 공유에 의한 작업의 경우 critical section의 개념이 중요하다는 것을 알 수 있음!!!
2) Critical Section Problem
다음 세 가지 조건을 충족해야함
Mutual Exclusion(상호배제)
프로세스 Pi가 critical section에서 실행 중이면 다른 프로세스가 critical section에서 실행될 수 없음
Progress(진행)
critical section에서 실행 중인 프로세스가 없고 critical section에 진입하려는 프로세스가 있는 경우, 다음에 critical section에 진입할 프로세스의 선택을 연기할 수 없음
Bounded Waiting(한정 대기)
프로세스가 critical section에 들어가는 요청을 한 후 다른 프로세스가 critical section에 들어갈 수 있는 횟수에 대한 bound 또는 limit가 존재
4. SW approach - Peterson
1) Naive approach(Incorrect)
Naive solution은 lock의 소유 여부를 추적하기 위한 단순 플래그만 구현할 수 있음
2) SW approach(Incorrect)
Synchronization variable
Boolean flag[2] = {false, false};
mutual exclusion을 충족하지만, progress 요구사항은 만족하지 않는다
3) SW approach - Peterson's
전역 변수 전환을 통해 동시 충돌 해결
Mutual exclusion가 보존됨
flag[0] 및 flag[1] 모두 참일 수 있지만 turn은 0 또는 1만 될 수 있음
Mutual blocking 방지
P1이 critical section에 있으며 P0이 차단되고 P0이 loop(flag[1] is true and turn = 1)하는 동안 차단된다.
flag[0] 과 flag[1]은 모두 true가 될 수 있지만 turn은 0 또는 1로만 될 수 있다.
아래와 같은 알고리즘은 현대 하드웨어에서 작동하지 않음
사람들은 약간의 하드웨어 지원을 가정하는 것이 훨씬 쉽다는 것을 깨달았음
5. Disabling Interrupt and HW support
1) Disabling Interrupts
초기 솔루션 중 하나는 중요한 섹션에 대한 인터럽트를 비활성화하는 것이었음
단일 프로세서 시스템에서 프로세스는 OS 서비스를 호출하거나 중단 interrupt(중단)될 때까지 계속 실행됨
따라서 Mutual exclusion을 보장하기 위해서는 프로세스가 중단되는 것을 방지하기에 충분함
이 접근 방식의 주요 장점은 simplicity(단순성)이다.
불행하게도 부정적인 것들이 많음
인터럽트를 끄면 인터럽트가 손실될 수 있음
이러한 권한 있는 작업은 일부 malicious program(악성 프로그램)에 의해 악용될 수 있음
이 접근 방식은 멀티프로세서에서 적절하지 않을 수 있다.
2) Special Machine Instructions
인터럽트를 비활성하는 것은 여러 프로세서에서 작동하지 않기 때문에 시스템 설계자들은 locking을 위한 하드웨어 지원을 발명하기 시작
HW support
일부 시스템은 lock mechanism을 구현하기 위한 추가 명령어를 제공
Compare and Swap instruction(CAS)
메모리 위치의 내용을 지정된 값과 비교하고 동일한 경우에만 해당 메모리 위치의 내용을 새 지정된 값으로 수정
6. Implementations of Spin Lock
1) A Simple Spin Lock Using CAS
또한 이러한 유형의 lock을 일반적으로 spin lock이라고 하는 이유를 이해할 수 있음
spin lock은 CPU 사이클을 사용하여 간단히 회전하는 가장 간단한 유형의 lock이다. 이것은 preemptive scheduler가 필
parbegin(P1, P2, ..., Pn)은 다음을 의미한다. → main program의 실행을 중지한다. → P1, P2, ..., Pn의 동시 실행을 시작한다. → P1, P2, ..., Pn이 모두 종료되면 main program을 재개한다.
2) Spin Locks
busy waiting 또는 spin waiting이라는 용어는 프로세스가 중요한 섹션에 들어갈 수 있는 허가를 얻을 때까지 아무것도 할 수 없는 기술을 말한다.
Mutual exclusion을 제공합니까? (mutual exclusion)
이는 간단하므로 확인이 쉽다
spin lock 기능은 한 번에 하나의 스레드만 critical section에 들어갈 수 있다.
단일 프로세서 또는 메인 메모리를 공유하는 여러 프로세서의 모든 프로세스에 적용 가능
spin lock을 사용하는 데 드는 비용은 얼마입니까? (performance)
busy waiting가 사용된다.
단일 프로세서 : lock을 유지하는 스레드를 제외한 모든 스레드는 spinning하는 동안 CPU를 낭비해야 함
멀티 프로세서 : lock을 대기하기 위해 spinning하는 것은 많은 사이클을 낭비하지 않는다.
waiting 스레드에 대한 spin lock은 얼마나 공정합니까? (fairness)
waiting process 선택이 임의이다.
Spin lock은 fairness를 보장하지 않으며starvation으로 이어질 수 있다.
7. Binary Semaphore
1) Semaphore
동시 시스템에서 액세스를 제어하는 보다 일반화된 동기화 방법
Semaphore S
정수 값을 가진 object(객체)
값은 현재 사용 가능한 리소스의 단위 수이다.
세마포어 개념은 1965년 Dijkstra에 의해 발명되었음
S를 수정하는 두 가지 표준 작업 : semWait() 과 semSignal()
semWait: 값을 줄임
semSignal: 값을 증가시킴
원래 이름은 P()와 V()이다. P는 proberen("try")를 나타냄 V는 verhogen("increase")를 나타냄
P
semWait (--)
lock
V
semSignal (++)
unlock
2) Semaphore 종류
busy waiting이 없는 구현
busy waiting을 피하기 위해 Semaphore는 semaphore에서 waiting 중인 프로세스의 관련 queue를 사용할 수 있다.
semaphore는 n-process critical section 문제를 처리하는 데 사용됨
Binary semaphore
lock으로 사용할 정수 값은 0과 1사이에서만 사용할 수 있음
0 및 1값으로 제한됨(또는 locked/unlocked, unavailable/available)
mutex lock이라고도 함
Counting semaphore
정수 값은 제한되지 않은 domain에 걸쳐 있을 수 있음
general semaphore라고도 함
3) Binary Semaphore
처음에 value값을 1로 초기화
8. Counting Semaphore
1) 예시
가장 오랫동안 차단된 프로세스가 queue에서 먼저 해제되는 강력한 세마포어(FIFO)
9. Implementations of Semaphores
1) Implementations of Semaphores
2) Deadlocks
waiting queue이 있는 semaphore를 구현하면 deadlock가 발생할 수 있다.
두 개 이상의 프로세스가 각각 다른 프로세스 중 하나가 작업을 수행하기를 기다리고 잇어 진행할 수 없는 경우
S와 Q가 1로 초기화된 두 개의 semaphore라고 함
3) Linux Approach : Two-Phase Locks
리눅스 접근 방식
이제 이를 two-phase lock이라고 함
첫번째 단계에서는 lock을 획득할 수 있기를 바라며 잠시 동안 lock이 spin한다.
Spinning은 특히 lock 해제될 때 유용할 수 있음
두번째 단계에서는 caller가 sleep 모드로 전환되고 나중에 lock이 해제될 때만 sleep에서 해제됨
일반 버전의 Linux 접근 방식은 sleep을 위해 futext support를 사용하기 전에 고정된 시간 동안 루프에서 spin할 수 있다.
4) Pthreads API : Mutual Exclusion
Pthreads API는 critical section에 mutual exclusion 기능을 제공하기 위해 다음과 같은 기능을 제공
#include <pthread.h>
int pthread_mutex_init( pthread_mutext_t *mutex, pthread_mutexattr_t *attr );
int ptrhead_mutex_destroy( pthread_mutex_t *mutex );
int pthread_mutex_lock(pthread_mutex_t *mutex );
int pthread_mutex_trylock(pthread_mutex_t *mutex );
int pthread_mutex_timedlock(pthread_mutex_t *mutex, struct timespec *abs_timeout );
int pthread_mutex_unlock(pthread_mutex_t *mutex );
(1) 예시
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define ITER 1000
void *thread_increment(void *arg);
void *thread_decrement(void *arg);
int x;
pthread_mutex_t m;
int main() {
pthread_t tid1, tid2;
pthread_mutex_init(&m, NULL);
pthread_create(&tid1, NULL, thread_increment, NULL);
pthread_create(&tid2, NULL, thread_decrement, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
if (x != 0)
printf("BOOM! counter=%d\n", x);
else
printf("OK counter=%d\n", x);
pthread_mutex_destroy(&m);
}
void * thread_increment (void *arg) {
int i, val;
for (i=0; i< ITER ; i++) {
pthread_mutex_lock(&m);
val = x;
printf("%u:%d\n",(unsigned int) pthread_self(), val);
x = val + 1;
pthread_mutex_unlock(&m);
}
pthread_exit(NULL);
}
void * thread_decrement (void *arg) {
int i, val;
for (i=0; i< ITER ; i++) {
pthread_mutex_lock(&m);
val = x;
printf("%u: %d\n", (unsigned int) pthread_self(), val);
x = val - 1;
pthread_mutex_unlock(&m);
}
pthread_exit(NULL);
}
5) POSIX Semaphores API : Semaphore
The POSIX semaphores
#include <semaphore.h>
int sem_init(sem_t *s, 0, unsigned int val);} /* s = val */
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */
(1) 예시
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define ITER 1000
void *thread_increment(void *arg);
void *thread_decrement(void *arg);
int x;
sem_t s;
int main() {
pthread_t tid1, tid2;
sem_init(&s, 0, 1);
pthread_create(&tid1, NULL, thread_increment, NULL);
pthread_create(&tid2, NULL, thread_decrement, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
if (x != 0)
printf("BOOM! counter=%d\n", x);
else
printf("OK counter=%d\n", x);
sem_destroy (&s);
}
void * thread_increment (void *arg) {
int i, val;
for (i=0; i< ITER ; i++) {
sem_wait(&s);
val = x;
printf("%u:%d\n",(unsigned int) pthread_self(), val);
x = val + 1;
sem_post(&s);
}
pthread_exit(NULL);
}
void * thread_decrement (void *arg) {
int i, val;
for (i=0; i< ITER ; i++) {
sem_wait(&s);
val = x;
printf("%u: %d\n", (unsigned int) pthread_self(), val);
x = val - 1;
sem_post(&s);
}
pthread_exit(NULL);
}
