<6강>
race condition(경쟁상태)
공유데이터를 쓸 때 프로세스가 어떤 순서로 처리하냐에 따라서 결과가 달라지는 것을 "경쟁상태"라고 함. 즉, 임계구역에 동시에 접근하여 자원의 일관성이 깨지는 것
ex)프로세스 A는 값을 1만큼 증가시키고 프로세스 B는 값을 1만큼 감사시킬때 두 개의 프로세스가 동시에 공유 데이터를 읽고 실행시키면 값이 달라질 수 있다.
critical section(임계구역)
임계구역 : 프로세스가 공유할 수 있는 구역(데이터, 프로그램 등)
Critical Section Problem은 여러 프로세스가 공유 자원에 대한 임계 영역(critical section)에 접근하는 것을 조절하기 위한 프로세스 동기화 문제입니다.
상호배제(mutual exclusion)
- 임계구역에 한 번에 한 프로세스씩 들어가는 것
<임계구역 문제 해결>
1)상호배제(mutaul exclution) - 임계구역에 진입한 프로세스가 있으면 다른 프로세스들이 들어갈 수 없다.
2)실행(process) - 임계구역에 진입한 프로세스가 없으면 들어가려는 프로세스는 임계구역에 들어갈 수 있어야 한다.
3)유한대기(bounded waiting) - 프로세스는 언젠가는 임계구역에 들어갈 수 있어야 한다. 무한대기 x
경쟁상태 예시)producer와 consumer>
producer
consumer
Race condition- 경쟁상태
임계영역 문제해결을 위한 프로토폴(데이터교환방식을 정의하는 규칙체계)
entry section- 임계영역 진입하기 전 허가를 기다리는 구간
critical section - 임계영역
exit section - 다른 프로세스에게 임계영역을 넘겨줄 차례임을 알림
remainder section- 임계영역 이후의 작업
critical section- 임계구역
<커널이 선제적인지?>
선점적(preemtive)
– 커널 모드에서 실행할 때 프로세스를 선점할 수 있습니다. (임계구역 문제 발생 - 메모리안의 프로세스가 커널을 공유하기 때문)
비선점적(non-preemtive)
– 커널 모드를 종료하거나 자발적으로 CPU를 양도하는 방법으로 실행됩니다.
- 경쟁상태로부터 자유로움
<피터슨 해결방식(peterson's solution)>
- 소프트웨어에 의해 동기화 시켜주는 방법
2개의 변수를 공유:
1)int turn : 임계구역에 들어갈 차례를 나타냄(실제로 누구차례인지)
2)boolean flag[2] : 임계구역에 들어갈 준비가 되었는 지를 나타냄(들어가고 싶어! 알리기)
ex)flag[i]=true인 경우 Pi가 준비가 되었음을 나타냄
(while(flag[j]&&turn==j)여기 부분은 cpu가 대기상태에 있는 게 아니라 running 상태)
임계구역(CS) 3가지 조건 [상호배제(flag[j]=false이거나 turn=i인 경우),실행,유한반복] 만족
but 3개 이상의 프로세스에서 올바르게 작동하기 어렵다, 오버헤드 발생
이를 해결하기 위한 하드웨어적 동기화 방법이 있음
일단 ,locking 방법을 이용하는 것이 base임
uniprocessor(단일프로세서) - 인터럽트를 비활성화함으로써 임계영역보호
(cpu가 다른 프로세스로 가려면 인터럽트가 발생해야 하는 데 인터럽트를 막았기 때문에 다른 프로세스로 갈 수 없음)
but 이 방법은 multiprocessor에선 비효율적임
(1)문제가 생기면 인터럽트를 발생시켜 해결해야하는 데 그러지 못해서 cpu는 멈춰있게 됨
(2)인터럽트를 걸어놔도 다른 cpu는 여전히 임계구역 진입가능(즉, 같은 cpu에서 동작하는 프로세스 사이에서만 동기화가 이루어짐)
so 현대에는 원자적(atomic: non-interrputible(인터럽트에 의해 중단되지 않는))하드웨어 구조 제공
원자적 하드웨어 명령어란?
실행되는 동작이 중간에 다른 작업에 의해 중단되지 않고 완전히 실행되는 특성을 가짐
그래서 인터럽트 비활성화가 필요하지 않기때문에 성능저하 없이 임계영역 보호가능
<동기화 하드웨어 lock 명령어를 사용하는 법(소프트웨어처럼 보이지만 사실 하드웨어)>
1)test-and-set
(1)원자적으로 실행
(2)전달된 파라피터의 원래값 반환
(3)파라미터의 값을 true도 설정
공유 변수 lock의 초기값은 false
-(ture를 다시 true로 만드는 과정이 많으면 오버헤드 발생 so compare and swap를 적용해볼 수 있음)
2)compare-and-swap
(1)원자적으로 실행
(2)전달된 파라피터의 원래값 반환
(3)변수 value를 파라미터 new_value로 설정하되 value==expected인 경우에서 이루어짐.
공유 변수 lock의 초기값은 0
test_and_set을 이용한 상호배제, 유한대기(여러 프로세스인 경우)
이런 하드웨어 동기화들:
장점: 속도가 빠르지만
단점:
(1)busy waiting(바쁜 대기) 문제가 있음
(2)임계구역에 못 들어가는 deadlock(교착상태), starvation(기아)문제 발생 문제 발생
*차이점 참고:
기아문제: 언젠가는 일어나지만 그 때가 언제인지 모르거나 매우 늦음
교착상태: 영원히 안 일어남
(임계구역에 들어간 친구가 무한 루프를 돌면 다른 프로세스들도 무한루프를 돌게 됨)
위는 어플리케이션 개발자가 접근할 수 없기때문에 임계구역 문제를 해결하기 위해 소프트웨어 방식을 만들었다
<뮤텍스락(Mutex Locks)>
: 상호배제를 위한 소프트웨어 lock 동기화 도구
acquire()(lock 획득)과 release()(lock 반환)를 이용하여 임계구역 보호
->lock을 사용할 수 있는 지를 나타내는 부울변수 available사용
->하드웨어 atomic(원자적) 구조를 이용하여 구현
그러나 busy waiting(바쁜 대기) 발생 이러한 lock을 spinlock이라고 함
->임계구역이 작을 때 많이 사용됨
<busy waiting, spin lock>
lock상태를 주기적으로 무한루프 돌며 확인하는 거
available 초기값 - true
<세마포어(Semaphore)> - mutex보다 조금 더 정교
세마포어?
공유 자원에 1개 이상의 스레드 또는 프로세스 가 접근할 수 있으며 "접근 스레드나 프로세스의 수"에 한계를 두는 방식
정수 변수 - semaphore S 사용(S= 공유자원의 수)
2개의 분리할 수 없는 atomic(원자)연산을 통해서만 접근 가능
->wait(), signal() (원래는 P(),V()라고 불림)
<세마포어 사용>
Counting semaphore(세마포어 계수): 제한되지 않은 범위에 있을 수 있는 정수
Binary semaphore(이진 세마포어): 정수값의 범위는 0~1(뮤텍스 자물쇠와 동일)
ex)세마포어를 사용한 실행 순서 동기화
세마포어의 변수를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수를 붙이고 실행할 프로세스 뒤에 wait 함수를 붙이면 된다.
<세마포어 구현>
2개 이상의 프로세스가 동시에 wait()나 signal()함수를 호출하면 문제가 생길 수 있음
상호배제가 필요함으로 wait()와 signal()함수는 임계구역에 있음..?
그래서 busy waiting(바쁜 대기)이 필요함
->실행코드 짧을 땐 busy waiting이 유리 (더 빠르게 실행)
->빠르게 실행되어야 할 경우 유리
->임계 구역이 조금 적용된다면 little busy waiting
어플리케이션이 임계구역에서 많은 시간을 할애하기 때문에 좋은 방법이 아님
<바쁜 대기 없이 세모파어 구현>
busy waiting,spin lock
: 무한루프 통해 공유자원의 수(임계구역에 접근가능한 프로세스의 수)를 확인하는 거
해결 방법 :
1)사용할 수 있는 자원이 없는 경우 대기 상태(block함수)로 만듦(프로세스를 대기큐에 삽입)
2) 사용할 수 있는 자원이 생겼을 경우 준비상태(wake up 함수)로 만듦 (대기큐에서 하나의 프로세스를 제거하여 준비큐에 삽입)
->cpu 효율도 좋음
*대기 큐에는 2가지 데이터 항목이 있음
1)정수타입의 값
2)다음 기록을 가리키는 포인터
deadlock
대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때의 상황을 교착상태
(서로 상대방의 작업이 끝나길 기다리는 경우)
starvation - 무기한 차단
프로세스가 무한정으로 차단되어 있는 상태를 나타냅니다.
한 프로세스가 계속해서 필요한 자원을 얻지 못하고 계속해서 차단되는 것을 의미합니다.
우선순위 역전
우선순위가 높은 프로세스가 우선순위가 낮은 프로세스에 의해 cpu를 선점당해서 임계구역에 못 들어가는 현상,
해결방안 : 우선순위 상속 프로토콜(기법)
ex)S,M,L이 있는 경우
임시적으로 우선순위가 낮은 프로세스(S)를 cs에서 빠져나올 때까지 우선순위가 높은 프로세스(L)만큼 높여준다.
<세마포어의 잘못된 사용>
signal (mutex) …. wait (mutex)
모든 프로세스가 임계구역에 들어가는 no 상호배제(mutual exclusion) 문제 발생
wait (mutex) … wait (mutex)
계속 기다리는 deadlock 발생
wait(mutex)와 signal(mutex) 중 하나가 생략되거나 둘다 생략된 경우
->deadlock과 starvation 가능
<모니터>
모니터 내에서는 하나의 프로세스만 활성화할 수 있음
x,y는 모니터 안에서의 조건(condition) 변수
- x.wait - 프로세스가 x.signal()을 호출할 때까지 일시 중단됨.
- x.signal() - x.wait()를 호출한 프로세스 중 하나를 재개, 프로세스가 없다면 영향을 미치지 않음
선택사항
ex) 프로세스Q가 x.wait에 의해 중단되고 프로세스P는 x.signal()을 발생시킨 경우
1) Signal and wait – P는 Q가 모니터를 떠나거나 다른 조건을 기다릴 때까지 대기
2) Signal and continue – Q는 P가 모니터를 떠나거나 다른 조건을 기다릴 때까지 대기
-
P가 나머지를 실행하면서 Q를 block시켰던 조건이 다시 발생하면 Q는 깨어나지 못 함
모두 장단점이 있기 때문에 언어에 따라 다름
이렇땐 P가 signal 이후에 바로 모니터를 빠져나옴, Q가 마저 수행하고 나오면 그때 P가 다시 들어감 -
버퍼가 꽉찬 경우
x.wait - 프로듀서
x.signal - 컨슈머 -
버퍼가 빈 경우
x.wait - 컨슈머
x.signal - 프로듀서
block된 프로세스(Q)가 x.wait부름 , x.signal(P)은 block된 프로세스를 깨운 경우
<모니터 안에서의 프로세스 재개(resume)>
ex)조건 x에서의 여러 프로세스가 대기큐에 있을 때 x.signal()이 발생하면 어떤 프로세스를 시작해야 하나?
FCFS방식이 적합하지 않을 때가 많음
so x.wait(c)구조를 제공해서 (c는 우선순위) 우선순위가 높은 순대로 실행
