임계구역 문제와 그 해결안
•
데이터 정합성 이슈의 발생
◦
동시에 공유 데이터에 접근한다면 데이터 불일치가 발생할 수 있음
◦
데이터 일관성을 유지하려면 협력 프로세스간의 순차적인 실행을 보장하는 매커니즘이 필요
→ Count값을 조정해보자
Buffer에서 항목 조정 ~ count 값 조정
생산자 – 소비자 문제
무한 버퍼 : 버퍼의 크기에 실질적인 한계가 없음
유한 버퍼 : 버퍼 크기 고정
•
버퍼가 비어있으면 → 소비자는 반드시 대기
•
모든 버퍼가 채워져 있으면 → 생산자가 대기
공유 메모리를 사용한 생산자 프로세스
(생산될 때마다 count 증가)
공유 메모리를 사용한 소비자 프로세스
(소비될 때마다 count 감소)
•
count 초기값을 5로 가정
◦
count++ 를 풀어서 표현하면,
register1 = count
register1 = register1 +1
count = register1
C
복사
◦
count-- 를 풀어서 표현하면,
register2 = count
register2 = register2 - 1
count = register2
C
복사
동시에 여러 프로세스가 동일한 데이터에 접근을 해서 조작
→ 누가 언제 접근했냐에 따라서 달라진다
→ 경쟁상황 발생
→ 실행 순서에 따라 결과가 달라지는 race condition 발생 (count가 5가 아닌 4로 표현됨)
임계구역(Critical-Section)
•
각 프로세스에는 임계 구역이라고 하는 코드 세그먼트가 존재
→ 프로세스가 액세스하고, 업데이트하는 데이터, 적어도 하나의 다른 프로세스와 공유됨
•
하나의 프로세스가 임계 구역에서 실행 중일 때, 다른 프로세스들은 해당 임계 구역에 접근할 수 없음
⇒ Mutual Exclusive
•
일반적으로 프로세스는 진입구역/퇴출구역, 나머지구역으로 구성
임계구역 문제 해결을 위한 요구조건
상호배제 (Mutual Exclusion)
•
프로세스 Pi 가 임계구역에서 실행될 때, 다른 어떤 프로세스도 임계 구역에 접근할 수 없음
진행 (Progress)
•
CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안된다.
제한이 있는 대기 시간 (Bounded Waiting)
•
프로세스의 CS 진입은 유한 시간 내에 허용되어야 한다.
운영체제의 lock문제를 해결하기 위한 방법으로 3가지가 있다
1. 소프트웨어적 방법
2. 더 이상 쪼개지지 않는 원자적 명령어로 구현하는 방법 (즉 하드웨어 명령어 이용하는 것)
3. 인터럽트 제어로 해결하는 방법
임계구역 문제와 그 해결안 - Software instruction
피터슨의 해결안 - 해결방법
두 개의 프로세스가 두 개의 데이터 항목을 공유하게 하도록 하여 해결
•
int turn
: 임계구역으로 진입할 순번을 표시
•
Boolean flag[2]
: 프로세스가 임계구역으로 진입할 준비가 되었다는 여부를 표시
if) flag[i] = true
◦
Pi가 임계구역으로 진입할 준비가 되었다는 뜻
p0가 의사를 밝히고 p1에게 turn 양보를 한 후 임계영역에 들어가려고 시도한다
→ 만약 이미 P1이 임계영역에 들어가있다면 Busy waiting loop에 걸려 P1의 flag가 false가 될 때까지 기다리게 된다. ⇒ mutual exclusion을 해결
만약 p1이 임계영역에 없어 CS에 들어갔다가 나올 때 P0의 flag를 False로 해주고 프로세스를 종료한다.
SW solution의 문제점
•
속도가 느림
•
구현이 복잡한
•
Mutual Exclusive primitive 실행 중 preemption 될 수 있음
◦
공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능
▪
Overhead 발생
•
Busy waiting
◦
Inefficient
◦
제한이 있는 대기 시간 위배(bounded waiting)
Synchronization Hardware
1.
Memory barriers
2.
Atomic variables
3.
Hardware instructions
a.
CAS
b.
TAS
memory barrier
(instrunction re-order)
하지만, 이러한 기능은 여러 스레드가 동시에 돌아가는 경우, 코드의 실행 순서가 바뀌어 실행되는 동안 다른 스레드에서 그 부분에 대한 메모리를 접근하여 잘못된 결과를 내놓을 수 있다.
따라서 특정 부분에 대하여 실행 순서를 강제하는 메모리 배리어를 놓아야 한다.
두 명령 사이에 메모리 배리어를 설치함으로써 컴파일러나 CPU가 두 명령의 순서를 지키도록 강제하여 원하는 결과를 얻을 수 있다.
•
Thread 1: may read x before flag → x is not read prior to the value of flag
•
Thread 2: may write flag before x → x is visible to others prior to flag
Atomic Variable
Atomic Variables란 무엇일까?
바로 원자성을 보장하는 변수를 뜻합니다.
멀티 쓰레드 환경에서 동시에 해당 변수에 접근하더라도 race condition 문제를 해결하기 위해서 고안된 방법입니다.
멀티쓰레드 환경에서 동기화 문제를 synchronized 키워드를 사용하여, 락을걸곤하는데
이런 키워드 없이 동기화문제를 해결하기 위해 고안된 방법입니다.
(일반적으로 동기화문제는 synchronzied, Atomic, volatile 세가지 키워드로 해결)
synchronized는 특정 Thead가 해당 블럭 전체를 lock을 하기떄문에
다른 Thread는 아무런 작업을 하지 못하고 기다리는 상황이 될수 있기 때문에 낭비가 심합니다.
그래서 NonBlocking하면서 동기화 문제를 해결하기 위한 방법이 Atomic입니다.
Atomic의 동작 핵심 원리는 바로 CAS 알고리즘입니다 (Compared and Swap)
CAS( Compared And Swap) 알고리즘
swap the contents of two words after comparing
멀티쓰레드환경, 멀티코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는게 아닌,
각 CPU의 캐시 영역에서 메모리를 참조하게 됩니다. (그림 2 참조)
이떄, 메인메모리에 저장된 값과 CPU캐시에 저장된 값이 다른 경우가 있는데 (가시성 문제라 합니다)
이럴 때 사용되는것이 CAS 알고리즘입니다.
1.
현재 쓰레드에 저장된 값과 메인메모리(레지스터)에 저장된 값을 비교하여
2.
일치하는경우 새로운 값으로 교체되고
3.
일치하지 않는다면 실패하고 재시도를 합니다.
이런 방법으로 처리하면, CPU캐시에 잘못된 값을 참조하는 가시성 문제를 해결할 수있습니다.
예시
•
메모리에 저장되어진 값과 현재 CPU에 캐시된
expect 값을 비교하여 동일한 경우만 변경하는 update쓰기를 수행
atomic은 blocking 방식을 사용하는 synchronized에 비해 훨씬 효율적인 방법이라고 할 수 있다.
무한 루프를 돌면서 값을 반영할 수 있는지 물어보는 경우에도 스레드의 상태를 변경하는 작업이 발생하지 않으므로 성능이 더 우수하다.
참고로 synchronized 의 경우,
synchronized 진입 전 메인메모리와 CPU 캐시메모리 값을 동기화 하여 문제가 없도록 처리합니다.
하지만 CAS는 제한된 대기 시간 조건을 만족시키지 못한다.
TAS (Test and Set)
Test and Modify the content of the word
명령어 내에서 수행되는 두 명령어 "bool rv = *target" 과 "target = true"는 동시에 실행되어 둘 다 실행되거나 둘 중 하나가 실행되지 않으면 나머지 하나도 실행되지 않는다.
while (TestAndSet(lock));
C
복사
이렇게 한 라인에 구현하게 되면 낑길때가 없으니까 사이에 인터럽트가 발생되서 꼬일일이 없다
더 이상 쪼개질 수 없이 한 번에 쭉 수행을 해야 한다고 그래서 atomic operation이라고 합니다
mutual-exclusion을 만족시키지만 제한된 대기 시간 조건을 만족시키지 못한다.
인터럽트 제어로 해결하는 방법
뮤텍스와 세마포어
spinlock
스핀 락(Spin lock)은 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락을 가리킵니다.
임계 구역 진입 전까진 루프를 계속 돌고 있기 때문에 busy waiting이 발생
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}
C
복사
스핀 락은 운영체제의 스케줄링 지원을 받지 않기 때문에, 해당 스레드에 대한 문맥 교환(context switch)이 일어나지 않습니다.
짧은 시간 안에 진입할 수 있는 경우 문맥 교환 비용이 들지 않으므로 효율을 높일 수 있지만 그 반대의 경우에는 다른 스레드에 cpu를 양보하지 않기 때문에 오히려 cpu 효율을 떨어뜨리게 됩니다.
스핀 락은 문맥 교환이 일어나지 않기 때문에 멀티 프로세서 시스템에서만 사용할 수 있습니다.
뮤텍스 락
피터슨의 해결안의 한계점, 하드웨어 기반 해결책의 구현 난이도의 문제(응용프로그래머 사용불가)
→ 임계구역 문제를 해결하기 위한 소프트웨어 도구 개발
뮤텍스 락(Mutex Lock)
•
뮤텍스 락을 이용하여 임계영역을 보호, 경쟁 방지
•
프로세스는 임계영역에 진입하기 전 반드시 락을 획득해야함. 임계 영역 사용 종료 시 잠금 해제
•
뮤텍스는 Locking 메커니즘으로 락을 걸은 스레드만이 임계 영역을 나갈 때 락을 해제할 수 있습니다.
•
뮤텍스는 acquire(wait)와 release(signal)이라는 원자적 연산을 사용
•
잠금 사용 가능 여부를 나타내는 Boolean 변수 사용
•
그러나, busy waiting이 존재함
available = True 할 때까지 Loop을 한다.
available
◦
True → 임계 지역을 실행 중인 프로세스 없음
◦
False → 임계 지역을 실행 중인 프로세스 있음
•
잠금 메커니즘이라는 점은 스핀 락과 동일하나 권한을 획득할 때까지 busy waiting 상태에 머무르지 않고 ready queue(sleep) 상태로 들어감
•
sleep 상태로 들어가고 wakeup 되면 다시 권한 획득을 시도하는 sleep lock을 사용합니다.
세마포어(Semaphores)
•
뮤텍스보다 더 정교하게 동기화 할 수 있는 방법이 필요해짐
•
정수 변수(S)
•
wait() - P, signal() - V 연산으로만 접근이 가능
세마포어(Semaphores) 의 종류와 사용법
•
세마포어는 음수가 아닌 정수 값을 가지고 스레드 간에 공유되는 변수입니다.
이 변수는 임계 구역 문제를 해결하고 동기화를 구현하는 데 사용됩니다.
•
세마포어는 signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있습니다.
•
세마포어를 가지고 상호 배제를 구현할 수 있다.
do {
wait(S);
// Critical section
signal(S);
// Remainder section
}while (TRUE);
C
복사
•
세마포어는 자원의 개수를 의미
•
세마포어는 사용할 수 있는 자원의 개수에 따라 두 가지 유형
◦
카운팅 세마포어
▪
도메인이 0이상인 임의의 정수값인 세마포어
▪
유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용
◦
이진 세마포어
▪
0과 1 사이 값만 가능.
▪
뮤텍스락과 유사하게 동작
•
두 연산은 atomic 하게 동작
◦
각 자원을 사용하려는 프로세스는 세마포어에 wait 연산 수행 ⇒ S 감소
◦
프로세스가 자원을 방출할때는 signal 연산 수행 ⇒ S 증가
•
세마포어 역시, busy waiting이라는 단점이 존재
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}
C
복사
◦
자원이 없다면 while 루프 돌면서 기다리는 방식입니다. (= spin lock)
while 루프를 돌며 대기하기 때문에 busy-waiting이 발생합니다.
•
block-wakeup 방식
◦
busy waiting 대신, 자신을 봉쇄하여 단점 상쇄
◦
block ⇒ Sleep(일시 중단) : 프로세스를 해당 세마포어와 연결된 대기큐에 위치시킴
◦
Wakeup : 프로세스를 대기 상태에서 준비 상태로 변경
typedef struct
{
int value; /* semaphore */
struct process *list; /* process wait queue */
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0 ) { // 자원이 없다면
add this process to S->list; // 프로세스를 큐에 넣고
block(); // block 시킴
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { // 자원이 0이하라면 block중인 프로세스가 있다는 의미임.
remove a process P from S->list; // 대기하고 있는 프로세스를 가져옴.
wakeup(P); // 가져온 프로세스를 깨움.
}
}
C
복사
◦
block() : 커널은 block을 호출한 프로세스를 suspend 시키고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣습니다.
◦
wakeup(P) : block된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮깁니다.
•
동기화 (synchronization)
◦
다양한 동기화 문제를 해결하기 위해 세마포어 사용 가능
◦
P1은 S1 명령문을, P2는 S2명령문을 병행하려고 하는 두 프로세스가 존재할 때,
S2는 S1이 끝난 뒤에만 수행되어야 한다고 가정
S = 0;
P1:
S1;
signal(S);
P2:
wait(S);
S2;
C
복사
S가 0으로 초기화되었기 때문에 프로세스 P2는 P1이 signal(S) 호출을 할 때까지 대기하게 됩니다.
세마포어 vs 뮤텍스 차이
•
뮤텍스는 Locking 메커니즘으로 락을 걸은 스레드만이 임계 구역을 나갈 때 락을 해제할 수 있지만
세마포어는 Signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있습니다.
•
이러한 차이 때문에 이진 세마포어는 뮤텍스로 사용할 수 있지만 뮤텍스는 세마포어로 사용할 수 없습니다.
교착상태(Deadlock)와 기아상태(Starvation)
Deadlock
교착상태란 무한 대기 상태를 뜻하며 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 다음 단계로 진행하지 못하는 상태를 말한다.
둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기 에 빠짐
•
P0이 wait(S)를 실행, P1이 wait(Q)를 실행한다고 가정
•
P0이 wait(Q)를 실행할 때, P0은 P1이 signal(Q)를 실행할 때까지 기다려야 함
•
마찬가지로, P1이 wait(S)를 실행할 때는 P0이 signal(S)를 실행할 때까지 기다려야 함
•
→ 이들 시그널 연산들은 실행될 수 없기 때문에 P0과 P1은 교착상태가 됨
교착상태 발생조건
다음 네 가지 조건이 모두 성립할 때 교착상태 발생 가능성이 있다.
•
상호배제(Mutual exclusion)
◦
두 프로세스는 동시에 같은 자원에 접근할 수 없음
◦
다른 프로세스가 그 자원을 요청하면, 요청프로세스는 자원이 해제될 때까지 대기한 뒤 사용 가능
◦
공유 가능한 리소스 설정을 통해 상호 배제 방지
•
점유 대기(Hold and wait)
◦
프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
◦
프로세스가 작업을 수행하기 전에 필요한 자원을 모두 요청하고 획득해야 함 (최대 자원 할당)
◦
단점 : 리소스 활용도가 낮음, 기아 현상 발생 가능
•
비선점(No preemption)
◦
프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다. 이미 할당된 자원 빼았을 수 없다는 말이다.
◦
이미 할당된 자원에는 선점권이 없어야 한다.
◦
높은 우선 순위의 프로세스에게 해당 자원을 선점할 수 있도록 해야한다
•
순환대기(Circular wait)
◦
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
◦
리소스에 고유한 번호를 할당, 번호 순서대로 리소스를 요청하도록 함 (일정한 방향)
◦
작업에 필요한 자원은 오래 전부터 할당 받고 있어야하므로 자원의 낭비 가능성이 생긴다.
→ 따라서 위의 한 조건이라도 성립하지 않으면 교착상태가 일어나지 않도록 할 수 있다.
기아 상태(Starvation)
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말한다.
기아상태는 주로 다음과 같은 방법으로 해결한다.
•
프로세스 우선순위 수시 변경을 통해 각 프로세스 높은 우선순위를 가지도록 기회 부여
•
오래 기다린 프로세스의 우선순위 높이기
•
우선순위가 아닌 요청 순서대로 처리하는 요청큐 사용
Monitor
•
세마포어는 상호배제와 프로세스 사이를 조정하는 유연성 있고 강력한 도구이지만 wait&signal 연산 순서를 바꿔 실행하거나 둘 중 하나 이상을 생략하면 상호배제를 위반하거나 교착 상태가 발생한다.
wait과 signal 연산이 프로그램 전체에 퍼져 있고 이들 연산이 각 세마포어에 주는 영향을 전체적으로 파악하기가 쉽지 않기에 세마포어를 잘못 사용하면 여러 가지 오류가 쉽게 발생하여 프로그램을 작성하기가 어렵다.
(즉, 타이밍 문제가 발생할 수 있다.)
모니터는 이러한 단점을 극복하려고 등장하였다.
•
뮤텍스와 모니터 차이
뮤텍스는 다른 프로세스간에 동기화 할 때 사용할 수 있고, 모니터는 하나의 프로세스 내에서 다른 스레드 간의 동기화에 사용된다.
•
객체 지향 언어(C++, Java)의 클래스와 같은 추상 데이터 타입(abstract data type: ADT)
•
OS가 아닌 programming language가 지원함
•
모니터 구성
◦
공유 데이터 와 Critical section의 집합
◦
condition variable
▪
조건 변수와 관련된 대기 큐
▪
조건 변수와 관련된 프로세스에 wait, signal
▪
모니터 내부에서만 접근 가능
◦
공유 변수들
▪
동기화 되어야 하는 공유 데이터를 다루는 연산들 (= operations)
▪
critical section 존재
▪
만약 두 번째 프로세스가 monitor procedure로 들어가려 할 때 그것은 첫 번째 프로세스가 끝날 때까지 block 된다. ⇒ Mutual exclusion
◦
entry queue
◦
초기화 코드
•
특징
◦
한 번에 하나의 프로세스만 모니터 개체 내에 프로시저를 사용 가능. 모니터에 접근하지 못한 프로세스는 entry queue에서 대기하게 된다. (상호배제) → 중요
◦
모니터 개체 내 공유 자원은 직접 접근할 수 없으며 프로시저를 통해서만 가능 (정보은닉)
◦
프로그래머는 이 동기화를 코딩할 필요 X
◦
초기화 코드는 모니터를 생성할 때 한번 사용됨
•
조건 변수(Condition variable)
기본적인 모니터 구조에서는 고전적인 동기화 문제(식사하는 철학자 문제 등)를 해결하는데 한계가 있다
⇒ 이를 해결하기 위해서 조건변수(condition variable)가 추가
조건 변수에는 wait, signal 두 가지 연산 존재
예를 들어 X라는 조건 변수가 정의되어 있다면 X.wait(), X.signal()로 호출하게 됩니다.
◦
wait() - 쓰레드(프로세스)가 자기 자신을 해당 조건과 관련된 조건 변수의 waiting queue에 넣고 대기 상태로 전환
◦
signal() - waiting queue에서 대기하고 있던 프로세스를 깨운다. 대기중인 프로세스가 없으면 아무 작업도 수행하지 않는다
이 구조는 모니터 내의 프로세스가 signal 함수를 호출하여 다른 프로세스를 깨우면 모니터 내에 두 개의 프로세스가 동시에 실행되게 되는 문제가 있다.
이를 해결하기 위한 두 가지 해결책이 존재.
signal and wait
•
프로세스 P가 signal 함수를 호출하면 프로세스 P는 Q가 모니터를 떠날 때까지 대기를 합니다.
signal and continue
•
P가 signal 함수를 호출하면 Q는 P가 모니터를 떠날 때까지 대기를 합니다.
모니터의 장단점
•
장점
◦
사용이 쉽다
◦
Deadlock 등 error 발생 가능성이 낮음
•
단점
◦
지원하는 언어에서만 사용 가능
◦
컴파일러가 OS를 이해하고 있어야 함
◦
Critical section 접근을 위한 코드 생성