[운영체제] 병행제어 2

ryun·2023년 4월 4일

운영체제

목록 보기

8/16

크리티컬 섹션 문제

크리티컬 섹션은 공유 데이터를 건드리는 코드
이 예시에서는 공유 데이터를 각 프로세스가 접근하는 코드를 크리티컬 섹션이라고 부른다

공유 데이터에 한 프로세스가 접근할 때는 다른 모든 프로세스가 크리티컬 섹션에 못들어가게 해야한다
- 크리티컬 섹션 들어가기 전에 락을 걸어서 다른 프로세스의 접근을 막는다
- 나갈 때는 lock 풀어서 다른 프로세스가 접근할 수 있게 한다

만약 CPU가 여러 개 있다면 공유 데이터를 여러 CPU에서 접근한다

CPU가 하나있는 환경에서도 동시접근 문제가 생기는가?
데이터를 처리함에 있어서 읽어오고 연산하고 저장하는 과정을 한번에 처리할 수 없기 때문에 생기는 문제
연산하려고 하는데 다른 친구한테 빼앗기면 그 데이터에 또 접근할 수 있었다.

이 문제를 어떻게 해결?

코드는 크리티컬 섹션과 아닌 부분의 연속으로 구성
크리티컬 섹션 들어갈 때 동시 접근했던 부분을 해결해줄 수 있다
- 크리티컬 섹션 전에 코드를 추가하고 빠져나올 때 코드 추가해줘서 동시에 들어가지 못하게 한다
  (= 락을 걸고, 풀고 라는 표현)

race condition을 해결하기 위한 충족 조건

Mutual Exclusion
동시에 들어가면 안되고 상호 배타적으로 크리티컬 섹션에 들어가야 한다
Progress
아무도 크리티컬 섹션에 없는 상황에서 들어가려는 프로세스가 있으면 들어가게 한다
Bounded Waiting (대기 시간이 유한)
starvation(특정 프로세스가 영원히 자원을 못 쓰는 문제)를 막는다
Ex) 아무도 안들어가고 있는데 3번은 여러개가 들어가고 싶은 경합의 상황에서 1, 2 만 번갈아서 들어가고 3은 못들어가는 상황을 방지

해결 알고리즘 1 (Turn)

크리티컬 섹션에 들어가려는 프로세스 2개 존재하는 상황
p0, p1 둘이서 동시접근할 가능성이 있다

Synchronization variable
- 중간에 끊기지 않는다는 가정을 하고 출발
로직
- 들어가기 전에 turn을 체크 (누구 차례인지 확인)
  turn이 0이면 내 차례 / 아니면 상대방 차례
- 내 차례가 아니면 while문을 돌면서 계속 기다리고 만약 turn이 0이면(내 차례)면 크리티컬 섹션에 들어간다
- 내 차례 아니면 while문 돌다가 CPU 시간 다 쓰고 반납, 밑으로 못내려간다
- 차례는 상대방에 의해서 바뀐다
  다 쓰고 나갈 때 turn을 상대방으로 바꿔준다
둘이 동시에 들어가는 경우는 없다
문제점
- 상대방이 들어갔다가 나와서 내차례로 바꿔주기 전까지는 들어갈 수 없다
  Ex) 내 프로그램은 자주 들어가고 싶은 프로그램이고 상대방은 자주 안들어가는 경우 (극단적으로 한 번도 안들어가는 경우라면)
  상대방이 처음 한번 사용하고 크리티컬 섹션 사용안하면 내 차례 안돌아옴 => 불합리
- 꼭 번갈아서 들어가야 한다
  엄격하게 번갈아 들어가도록 하기 때문에 내가 다시 들어가고 싶어도 못들어간다

해결 알고리즘 2 (Flag)

로직
- 프로세스마다 자신의 깃발 보유, 들어가고 싶다고 하면 깃발을 든다
  i라는 프로세스는 깃발을 들어서 들어가고 싶다는 의중을 표시 >
  상대방 깃발 j 확인 >
  상대 깃발이 내려지면 들어갈 수 있다
- 상대 깃발은 들어갔다가 나올 때 내려진다
문제점
- 동시에 들어가는 1번 조건은 해결
- 2번 진행 조건은 해결할 수 없다
  둘다 깃발을 들고 있는 상태에서는 진행되지 못한다
  Ex) 깃발만 들고 들어가기 전에 CPU를 빼앗겼다면,
  상대방이 얻어서 깃발 들고 상대방 깃발을 확인한다
  모두 깃발만 들어놓고 눈치만 보다가 못 들어가는 문제가 생길 수 있다
  (=진행이 더이상 안되는 문제)

해결 알고리즘 3 (Flag, Turn) (피터슨 알고리즘)

로직
- 앞 두개에서 사용햇던 변수(깃발, 턴) 모두 사용
- 깃발로 의중 확인
  둘이 동시에 깃발 들었으면 턴을 이용해서 누구 차례인지 정한다
- 1번 알고리즘은 턴으로 인해 번갈아 들어가는데 문제는 번갈아 간다는 규칙만 있지 원하는 경우에만 들어가는게 아니다. 원하든 원하지 않든 번갈아 들어간다.
- 3번 피터슨 알고리즘은 깃발 드는것에 한해서 턴으로 차례를 정한다
프로세스 i의 관점

들어가기 전에 깃발로 들어가려한다는 의사코드 표시 (flag => true)
턴을 상대방 턴으로 만든다
상대방이 깃발과 턴 두 가지를 체크
(상대가 깃발 안들었고 턴이 내차례면 크리티컬 섹션에 들어간다)
다 쓰고 나오면 깃발 내려서 상대가 들어갈 수 있게 해준다 (flag => false)
과정 끝난 후 턴이 j이기 때문에 j한테 넘어감

문제
- 플래그와 턴 순서 바꾸면 문제가 발생한다
- 비효율적
- 두 프로세스가 임계구역에 동시에 들어갈 수 있는 상황 발생
  내가 크리티컬 섹션에 못들어가는 상황에서 while문을 돌면서 CPU 가지고 있을 때
  플래그 j가 세팅, j 차례라면 크리티컬에 못들어가고 while문 계속 돈다
  이 조건이 바뀌려면 i가 CPU를 놓고 j가 CPU 잡아서 크리티컬을 빠져나가면서 i가 들어갈 수 있게 해주는 부분이 실행되어야 i가 와일문 빠져나감
  CPU만 낭비하는 상황. busy waiting 하면서 계속 기다리기만 하는 상황(스핀락)

뒤에 해결책 등장

Synchronization Hardware

하드웨어적 지원이 있으면 문제를 쉽게 해결할 수 있다
복잡한 코드가 필요했던 이유는 데이터를 읽어가서 연산하고 저장하는게 한번에 이루어지지 않아서 발생했다
하드웨어적으로 atomic하게(원자적으로) 중간에 CPU 빼앗기거나 쪼개질수없고
데이터를 읽거나 바꿔서 저장하는 것을 한꺼번에 실행하면 해결할 수 있다

Test and Set
- 하드웨어적 지원 연산 (원자적인 명령어)
- 위의 복잡한 코드 필요없고 한줄로 간단히 작성
- 크리티컬 들어갈 때 락 걸고 나올 때 락 푸는 역할을 해준다
로직
- lock
  이진 변수 0 또는 1 / False 또는 True
- 락이 0이면 아무도 락을 걸지 않았다는 뜻
- 락이 1이면 누군가가 락을 걸고 크리티컬에 들어갔다는 뜻
  - while문에서 더이상 아래로 못내려감
- 락이 0이었으면 테스트 셋 연산 결과로 원래값인 0이 읽히고 락의 값을 1로 바꿔줌(1이 읽혔는데 또 1 셋팅해도 상관없다)
- 빠져나올 때는 락을 풀어준다
- 값을 읽어내는 것과 1로 본인이 세팅하는 일을 동시에 원자적으로 할 수 있으면서 코드 간단

세마포어

공유자원의 획득과 반납 및 자원 카운팅을 세마포어로 관리
프로그래머가 가져다 쓰는 추상화된 도구

Semaphores
- 일종의 정수 추상 자료형
  - 실제 컴퓨터에 정수가 어떻게 표현되는지 다루지는 않는다
- 구현은 논의할 바 아니고 오브젝트와 오퍼레이터로 구성된 것
- 공유자원의 획득과 반납 및 자원 카운팅을 세마포어로 관리
p연산
- 자원을 획득하는 과정 및 락을 거는 과정
- 자원의 여분이 없으면 p연산 못하고 while 문에서기다린다
v연산
- 자원을 반납하는 과정 및 락 풀어주는 과정
- 자원 하나 내어놓는 것
- 변수값이 양수면 자원이 있으므로 v연산으로 감소시키고 자원을 쓰는 코드 실행
세마포어 변수값이 5면 자원이 5개 있는것을 의미
p연산과 v연산 사이에는 자원 사용하는 코드가 있다
세마포어가 지원되면 싱크로나이제이션이나 크리티컬 문제를 쉽게 해결할 수 있다

세마포어 변수를 1로 초기화
하나만 크리티컬에 들어갈 수 있다
들어가기 전에 p연산 나올 때 v연산해서 값을 1로 복원

busy waiting 문제
만약 누군가가 이미 크리티컬에 들어가서 뮤텍스가 0인 상황에서 p연산 시도한다면 와일문 을 돌면서 빠져나가지 못한다
다른 프로세스가 크리티컬 빠져나가면서 v연산으로 값을 1로 복원시키지 전까지는 p연산 해도 계속 0인 상태로 와일문을 빠져나가지 못핝다 (본인 시피유 시간 다 쓰면서)
busy waiting 해결법
누군가 이미 크리티컬 섹션에 들어가서 세마포어가 0이면 굳이 와일문을 돌면서 체크할 필요가 없다
즉, 더이상 CPU 있어봐야 소용이 없다
CPU 반납 후, 블락 상태에 들어가서 누군가 v연산을 해줄 때까지(자원이 생길 때까지) CPU 가지고 있지 않는 것이 효율적

Block / Wakeup 구현

세마포어를 구조체처럼 정의
- 값과 세마포어를 줄세우는 리스트 구조 제공
- 만약 자원 여분이 없어서 기다려야 하면 변수 L에 대해서 프로세스를 잠재우고 기다리게하게 한다
- 누군가 자원을 반환하면 기다리는 프로세스 중에 하나를 깨운다
  디스크 I/O 작업에서(오래걸리는 작업) 공유데이터를 쓰고 있으면 계속 CPU를 쓰면서 busy waiting 하지 않고 블럭되면서 큐에 줄 세운다
  나중에 공유데이터 다 쓰고 나갈 때 하나를 밖으로 내보내서 공유데이터 쓸수 있게 한다

스핀 락
- 락을 걸 때 진입이 가능할 때까지 루프를 돌면서 락을 체크
슬립 락
- 블럭앤 웨이팅 자원여분 없을 때 블럭 시켜버리는 방식(락이 걸려잇을 때 슬립시키는 것)

Block / wakeup 방식 구현

세마포어는 구조체 안에 값이 잇고 잠들게 하는 연결리스트가 존재
세마포어 값 S.value / 리스트는 L

앞의 코드와 다르게 세마포어 변수 값 일단 1 감소 (이미 세마포어 자원이 모두가 사용중이라 0이거나 심지어 음수라도 1 뺀다)
리스트에 프로세스 블럭시킨 후 잠들게 한다
- 누군가가 자원을 내어놓을 때 일어난다
자원 내어놓을 때 세마포어 변수 값 증가 (양수가 된다는 보장 없음)
자원반납 했더라도 양수일 수도 음수일 수도 있다
- 반납해도 0이하면 누군가가 세마포어 기다리면서 잠들어 있다는 뜻
- 이런 상황에서 리스트에서 하나 깨워서 꺼내는 작업 필요
- 상식과 달라서 어려움
변수 값으로 양수와 0, 음수가 자원 여분의 개수를 세는 것이 아니다
- 자원이 없어 잠들어 있다, 자원이 남아돌고 있다 등을 의미

Busy-wait VS Block / wakeup

일반적으로 블락/웨이크업이 훨씬 좋다

여분없는 상황에서 CPU를 낭비하는 비지웨이팅은 비효율적
자원 여분없을 때는 블럭, 생기면 웨이크업 해주면 된다
- 하지만 프로세스 상태를 블럭으로 바꾸고 웨이크로 바꾸는 것도 오버헤드
- 크리티컬이 길면 효과적일 텐데 자주 있지 않고 길이도 짧으면 그닥
따라서 상황에 따라 비지 웨이팅이 효과적일 수도 있다
- 한산하면 비지웨이팅으로 해도 괜찮다