3.3 세마포
Semaphores
- 동기화 문제 해결을 위한 소프트웨어 도구 → 상호배타를 만족시킬 수 있음
- 구조
- 정수형 변수 + 두개의 동작
- 스택과 비슷하게 동작함: push(), pop()
- P: Proberen → acquire()
-
V: Verhogen → release()
void acquire() { value–; if (value < 0) { add this process/thread to list; block; } } void release() { value++; if (value <= 0) { remove a process P from list; wakeup P; } }
전체구조
- 정수값: 임계구역에 들어갈 수 있는 쓰레드의 수
- 상호배타 목적
- acquire() 명령을 통해 정수값을 1 감소키기고 임계구역에 A 쓰레드가 존재함 → 만약 B 쓰레드가 acquire() 명령을 하는 경우 이미 임계구역에 A 쓰레드가 있기 때문에 block 당함 → block 된 B 쓰레드는 세마포 큐에서 대기하고 있음 → A 쓰레드가 releae() 라는 명령을 수행하면 임계구역에서 나감 → 정수값이 0보다 커지게 되고 쓰레드가 wakeup을 통해 세마포에서 B 쓰레드 탈출
- Ordering
- 세마포는 프로세스 실행 순서를 원하는대로 제어하는 역할로도 사용가능함
- 예시: 항상 출금을 먼저 하고 싶은 경우
- 정수를 0으로 설정
- 입금 코드에 acquire() 명령을 실행하면 세마포 정수 값이 1감소되어 -1 → 입금 스레드는 세마포 큐에 block 당하게 됨 → 출금을 실행 → 출금이 끝나면 releae() 를 실행 → 그럼 입금이 진행될 것임
- 참고: https://copycode.tistory.com/62
3.4 생산자 - 소비자 문제
전통적 동기화 문제
- Producer and Consumer Problem
- Readers - Writher Problem
- Dining Philosopher Problem
Producer and Consumer Problem
- 생산자가 데이터를 생산하면 소비자는 이를 소비
- bounded buffer (유한 버퍼)
- 생산된 데이터는 버퍼에 저장됨
- 생산자는 버퍼가 가득 차면 더 넣을 수 없다.
- 소비자는 버퍼가 비면 뺄 수 없다.
- 코드
- 내용: 생산자가 생산하고 소비자가 이를 소비하는 코드임 결과적으로 버퍼는 0 이어야함
- 결과: 실행불가, 혹은 생산된 숫자와 소비된 숫자가 다름
- 이유
- 생산되는 속도와 소비하는 속도가 다른 경우가 있음
- 공통변수를 동시에 업데이트
- 공통변수 업데이트 구간 = 임계구역에 동시 진입
- 해결법
- 임계구역에 동시접근 방지 = 상호배타 → 세마포를 이용
-
Busy-wait
- 생산자: 버퍼가 가득 차면 기달려야함
- 생산자 버퍼 제어 세마포는 저수의 초기값을 버퍼 size 로 가짐
- empty.aquire(); 생산; full.release()
- 소비자: 버퍼가 비면 기달려야함
- 소비자 버퍼 제어 세마포는 0으로 설정 → 비어있을때 block 되야해서
- full.aquire(); 소비; empty.relese()
- 생산자 스레드의 작업을 마칠 때 까지 기다려야 하는 소비자 스레드가 있다. 소비자는 생산자가 끝 날 때까지 아무 일도 하지 않고 기다리는데 이를 Busy wait 이라 한다.
- 생산자: 버퍼가 가득 차면 기달려야함
3.5 Readers - Writher Problem
- 공통 데이터베이스에 여러 접근을 하여 발생되는 문제 → 모두 공통 사용 “임계구역”
- Reader: 데이터를 오직 읽기만
- Writer: 데이터를 읽고 수정 가능
- 효율성 제고
- 상호배타를 만족하기 위해 한번에 한개의 스레드만 접근 가능하게 만드는 경우 해당 문제에서 비효율이 문제
- Reader 1 이 데이터베이스에 접근하였을 때 Reader2 도 접근하는 경우 → 동시 접근하더라도 데이터 변형을 주지 않아서 문제 발생을 일으키지 않음
- 그러나 Writer 의 경우엔 데이터 변경이 있기 때문에 동시 접근이 어려움
- 여러명의 Reader 를 허용하는 경우
- 여러명의 Reader 를 허용하는 경우 Writer 가 무한히 대기하는 경우가 발생할 수 있음
- 정리
- Reader가 데이터베이스(임계구역) 들어갈 경우, 다른 Reader는 접근할 수 있으나 Writer는 접근할 수 없다.
- Writer가 데이터베이스(임계구역) 들어갈 경우, Reader와 Writer 모두 접근할 수 없다
- 우선권을 주어서 Reader 혹은 Writer 를 먼저 실행 할 수 있음 ex) First R/W problem, Second R/W problem, Third R/W problem = 아무에게도 우선권 주지 않음
Dining Philosopher Problem
- 생각 → 식사 → 생각 → 식사 ….
- 젓가락: 세마포
- 문제
- 만약 5명 철학자 모두 배고파서 왼쪽 젓가락을 들고있음 → 오른쪽 젓가락을 얻지 못해서 모두가 굶는 상황 = 교착상태 (Dead Lock)
3.7 교착 상태 (Dead Lock)
- 상호 배제에 의해 발생되는 문제점
- 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여 무한정 기다리는 현상
교착상태 필요조건
-
Mutual exclusion = 상호배타
한번에 한개의 프로세스만이 공유 자원을 사용가능
-
Hold and wait = 보유 및 대기
최소한 하나의 자원을 점유하고 있으며 다른 프로세스에 할당되어 사용되고 있는 자원을 추가적으로 점유하기 위해 대기하는 프로세스가 있어야함
-
No Preemption = 비선점
다른 프로세스에 할당된 자원이 끝날때까지 강제로 뺏을 수 없음
-
Circular Wiat = 환형대기
각 프로세스가 원형으로 꼬리를 문 상태 = 순환구조가 만들어졌음
-
위 네가지 조건을 만족하면 교착상태가 발생 할 수도 있다
자원
- 동일 형식 자원이 여러개 있을 수 있다 = Instance
- 요청 → 사용 → 반납
자원할당도
- 어떤 자원이 어떤 프로세스에 할당되었는가?
- 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리는가?
