Race Condition
- 공유 데이터에 대해 여러 프로세스가 동시에 접근, 변경하는 상황
Critical 섹션
- 여러 프로세스들이 공유하는 데이터에 접근하는 코드 영역
- 한번에 오직 하나의 프로세스만 critical 섹션에 진입해야함
Critical 섹션을 가진 프로세스의 모델링
Entry 섹션
- 다른 프로세스가 크리티컬 섹션에 들갔는지 아닌지 확인(아무도 없어야함으로)
Exit 섹션
- 크리티컬 섹션 끝났음을 알려주는 역할
Critical 섹션 문제 해결 3 조건
상호 배제(Mutual Exclusion)
- 한 프로세스가 Critical 섹션에 진입해 있다면 다른 프로세스는 진입 불가!
진행(Progress)
- 프로그램이 잘 진행되기 위해서는 A가 빠져나와있을때 대기후보 B C D 중에 하나가 바로 바톤터치를 잘 이어받아야함. 흐름이 끊이지 않도록
Bounded Waiting
- 다른 애들에 치여서 못나가는 애들은 기다리는 시간이 너무 길지 않도록 LImit 를 설정해 줘야함. =(우선순위 aging 처럼)
알고리즘
-
shared variables를 두고 작성
-
ABABABAB 순서로 와야하는 문제점 발생
만족조건: 상호 배제(Mutual Exclusion)
불만족 조건: 진행(Progress),Bounded Waiting
(대안) 알고리즘
-
AAABBB 이렇게 와도 실행되게 고침.
-
But, flag[0] 과 flag[1] 을 동시에 바꿔버리면 무한루프 돌아..
만족조건: 상호 배제(Mutual Exclusion)
불만족 조건: 진행(Progress),Bounded Waiting
(대안)Peterson 알고리즘
- turn 과 flag 모두 씀
만족조건: 상호 배제(Mutual Exclusion), 진행(Progress),Bounded Waiting
한계
- 프로세스가 3개 이상일때는...?
- 변수를 늘려서 한다해도 성능이 좋은지 어떻게 알아?
=> 하드웨어로 처리하면 알고리즘 간단하게 풀림
동기화 문제 해결방안
- Critical 섹션에 들어가면서 Interrupt를 disable함
- 유저 프로그램이 Interrupt를 컨트롤하는건 바람직 하지 않음
- Scalable하지 않음(프로세스 수 많이 질때 문제생길 수 있음)
- 동기화를 위한 Instruction 명령어 도입함
동기화 명령어
- 명령어가 수행되는 동안에는 방해받지 않음(하드웨어에서 보장)
- 다른 프로세스들이 절대 접근 못하게
동기화 명령어의 한계점
- 동기화 명령어를 쓰면 Mutual Exclusion은 해결됨.
- But, Bounded Waiting같은 조건은 유저 프로그램에서 해결해야함
- Bounded Waiting이 주어진 문제마다 차이가 있어서 애매함(우선순위를 어떻게 줘야하는지)
- 공정하게 할 수 있는 추가적인 방안이 필요해!
(대안) 세마포어(Semaphores)
- 세마포어: 두개의 정수 변수
Wait() 로 락을 잡음, Signal() 끝났음을 알림
Busy Waiting
단점
- 계속 loop를 도는 방법 => CPU 사이클을 낭비함. =>기다리는 프로세스 수가 많아질수록 낭비 사이클은 더 커짐.
- 누가 Critical 세션에 진입할지 결정되지 않음
Sleep Queue 로 세마포어 강화
- 계속해서 while 문을 돌고있는 상황을 해결하기 위해서 만듬
- 세마포어의 값이 양수가 되서 Critical 섹션에 진입가능하면 -> 슬립 큐에 대기 중인 프로세스를 꺠워서 실행시킴
세마포어의 종류
Counting 세마포어
- 초기값은 가능한 자원의 수로 정해짐
- Lock을 잡기 위한 변수
Binary 세마포어
- 하드웨어의 도움을 받아서 비교적 구현이 간단함
세마포어의 구현
커널이 싱글 쓰레드일때
- P/V는 시스템콜로
- 커널 내에서 처리해 세마포어 동작을 구현. 하나의 프로세스만 시스템콜 할 수 있음으로 P V가 한번에 하나만 실행되는게 보장됨
- 커널 내의 수행이 Non preemptive임
커널이 멀티 쓰레드일때
- P/V는 시스템콜로
- 커널 내에서 별도로 동기화를 해줘야함
세마포어의 단점
- 데드락이 발생할 가능성이 존재함(서로가 서로의 락을 잡고 있어서 아무도 진입하지 못하는 교착상태)
- P와 V의 연산이 분리되어 있기 때문에 이를 잘못 사용할 경우에 대책이 없음
데드락
- 두개 이상의 프로세스들이 끝없이 이벤트를 기다리는 상황
(대안)모니터(java)
- 하이레벨 언어에서 동기화 방법(로우 레벨에서 풀면 너무 어려워...)
- 한 순간에 하나의 프로세스 만 모니터에서 활동하도록 보장
- 어플리케이션은 세마포어처럼 P, V 연산과 상관없이 프로시져를 호출하는 것만으로도 동기화 해결가능
ex) 트랜젝션
