# 생산자/소비자 문제(producer/consumer) p238
- 생산자와 소비자가 병행 수행 됨
- 생산된 item을 버퍼에 저장
- 소비자는 한 번에 하나씩 버퍼에서 데이터 소비 가능
- 버퍼 중첩 안됨
- 한 순간에 하나의 생산자 또는 소비자만 버퍼에 접근 가능 => 임계 자원(공유 자원)
- 생산자는 가득 찬 버퍼에 저장하면 안됨. 또한 소비자는 빈 버퍼에 서 꺼내면 안됨
# 무한 공유 버퍼, 버퍼를 구성하는 각 원소들이 선형 배열
- 계속 생산함
// 생산자 의사 코드
producer:
while (true) {
/* produce item v */
b[in] = v;
in++;
}
// 소비자 의사 코드
consumer:
while (true) {
while (in <= out)
/*do nothing(대기) */;
w = b[out];
out++;
/* consume item w */
}- in : 저장되는 위치
- out : 꺼내려는 위치
# 무한 버퍼에서 이진 세마포어를 이용한 생산자 소비자 문제 해결 방법 : 부정확한 버전 p240
- s, delay를 세마포어 변수라고 선언하는 게 있음
- 변수 n 사용 : 버퍼에서 유효한 데이터의 수 (in - out)
- s : 상호배제를 보장하기 위하여 사용
- delay : 버퍼가 비어있을 때 소비자가를 블록시키기 위해 사용
- 사용자는 자유롭게 데이터 버퍼에 추가 가능, 추가 하기 전에 상호배제를 위해 semWaitB(s) 호출, 추가한 후에 semSignalB(s) 호출 => 버퍼에 데이터를 추가할 때 소비자가 버퍼 사용하거나 다른 생산자가 버퍼 사용하는 것을 방지하기 위함
- 생산자는 임계영역 내에 있는 동안 n의 값을 증가시킴
- n=1이 되면, 데이터를 버퍼에 추가하기 바로 전에는 버퍼가 비어 있음 => 생산자는 소비자에게 버퍼에 데이터가 채워졌다는 사실 알려줌 (semSignalB(delay)) 호출
- 소비자는 임계영역으로 진입하여 데이터를 꺼내고 n을 감소시킴
- 생산자가 소비자에 비해 먼저 수행될 수 있다면, n이 대부분 양수이기 때문에 소비자가 세마포어 delay에서 블록되는 경우는 매우 드뭄 => 생산자와 소비자 모두 원활하게 수행
- 단점 ) 소비자가 버퍼의 데이터를 모두 소진하면 생산자의 새로운 생산이 있을 때까지 세마포어 delay에 대기하여야함
p241
- s, n, delay(기다려라는 의미) 변화 봄
- n이 0이면 더 이상 가져갈 수 없는데 마이너스 됨 => 시스템 버그
- 8. 버퍼에 있는 데이터 모두 사용 n = 0
- 14. 소비자가 semWaitB(delay) 호출하기전 11. 생산자가 n 증가시킴
- semSingalB는 이전의 semWaitB와 서로 일치하지 않음
- 20. n=-1인 것은 소비자가 버퍼에서 존재하지 않는 데이터를 소비했다는 것 의미
문제해결 )
1. 조건문을 소비자의 임계영역내로 옮김 => 교착상태 발생 (8. 이후부터)
2. 소비자의 임계영역 내에 보조 변수 사용 (5.10)
3. 범용 세마포어 사용 (5.11)
# 무한 버퍼에서 이진 세마포어 이용한 생산자 소비자 문제 해결 방법 : 정확한 방법 p242
- 이전의 문제해결을 위해 소비자 임계영역 내에서 보조변수(m) 사용
- m 은 소비자 임계영역내에서 설정되고, 그 이후에 사용됨
- 없는 값을 마이너스 하는 경우 발생 안함
# 무한 버퍼에서 범용 세마포어를 이용한 생산자 소비자 문제 해결 방법 p243
- n은 세마포어 : 버퍼에 존재하는 유효한 데이터 개수
- 두 개의 세마포어에 대한 연속된 호출 나타남
- 생산자 프로그램에서 semSingal(s)과 semSignal(n)이 서로 바뀌면 세마포어 s에 의해 보호되는 임계영역 내부에서 세마포어 n에 대한 semSignal을 수행하게 됨 => 소비자는 두 세마포어를 기다리기 때문에 수행 과정에는 영향 없음
- 소비자 프로그램에서 semWait(n)과 semWait(s) 연산의 순서가 바뀐 경우 => 세마포어 s에 의해 보호되는 임계영역 내부에서 세마포어 n에 대한 semWait를 수행하게 됨 => 심각한 오류 야기
- 버퍼가 비어있을때(n.count = 0) 소비자가 임계영역에 들어가면 세마포어 s를 확보한 채 세마포어 n에서 블록됨
- 생산자는 세마포어 s에 대한 허가를 얻을 수 없어 버퍼에 데이터를 추가하기 위한 임계영역에 진입하지 못함 => 교착상태 발생
# 유한 공유 버퍼, 환형 큐 p243
// 생산자 의사 코드
producer:
while (true) {
/* produce item v */
while ((in + 1) % n == out)
/* do nothing */;
b[in] = v;
in = (in + 1) % n
}
// 소비자 의사 코드
consumer:
while (true) {
while (in == out)
/* do nothing */;
w = b[out];
out = (out + 1) % n;
/* consume item w */
}- 책에 오타 있음
# 유한 버퍼에서 범용 세마포어를 이용한 생산자 소비자 프로그램 해결 방법
- 세마포어 e(empty)는 버퍼에서 빈 공간의 개수
- append(), take() *** 중요 ***
- semWait와 semSignal은 원자적으로 구현되어야 함
- 하드웨어 또는 펌웨어로 구현 가능
- Dekker’s 또는 Peterson’s 알고리즘 같은 소프트웨어적 인 기법으로도 구현 가능
- 상호 배제를 위해 하드웨어 지원 기법 중에 하나를 사용
# 프리미티브
- 기본 함수 (원시 함수)
- semWait와 semSignal 연산
# 모니터 p245
- 병행처리(동시처리) 지원하는 프로그램 언어에서 지원함 (자바)
- 상호배제를 위한 소프트웨어적인 모듈
- 이런 구조체를 모니터라고 말함
- 컴퓨터 화면은 디스크 하드웨어적인 것
- 상호배제를 위한 소프트웨어 모듈
- 프로그래밍 언어 수준에서 제공되는 구성체(construct)
- 세마포어처럼 상호 배제 기능 제공하면서 사용이 훨씬 쉬움.
- Concurrent-Pascal, Pascal-Plus, Module-2/3, Java 등에서 지원
- 프로그래머는 자신이 보호하고자 하는 어떤 객체에도 모니터 락 (monitor lock) 설정 가능
- 지역 변수, 초기화 루틴, 프로시저로 구성된 소프트웨어 모듈
# 모니터의 주된 특징
- 지역 변수는 모니터 내부에서만 접근 가능 => 외부에서 변수에 대한 직접 접근 허용 안됨
- 프로세스는 모니터 프로시저 중 하나를 호출(invoke) 함으로써 모니터 내부로 진입
- 한 시점에 단 하나의 프로세스만 모니터 내부에서 수행 가능 => 사용중이면 대기 (상호배제 기능 제공)
# 동기화: 조건 변수(Condition variables) 제공
- 조건변수는 모니터 내부에 포함되므로, 모니터 내부에서만 접근 가능
- 모니터에 사용하는 특수한 유형의 데이터 타입
- 두 가지 인퍼테이스에 의해 접근
1) cwait (c):
- 호출한 프로세스를 조건 c에서 일시 중지 시킨다 .
- 모니터는 이제 다른 프로세스에 의해 사용될 수 있음
2) csignal (c):
- cwait 에 의해서 중지되었던 프로세스를 재개 시킨다.
- 만일 중지된 프로세스가 여러 개일 경우 그 중 하나를 선택
- 만일 중지된 프로세스가 없을 경우 아무것도 하지 않음
- 한 시점에 하나의 프로세스만 진입 가능 => 하나의 진입점(entry point) 가짐
- 모니터 내부에서 수행중인 프로세스가 조건 x에서 잠시 대기할 필요가 있으면 cwait(x) 호출 => 조건 x와 연관된 대기 큐에서 블록됨
- 조건이 변하면 블록된 플로세스느 깨어나 모니터에 재진입하고 cwait(x) 이후의 위치에서부터 수행 재개
- 모니터 내부에서 수행중인 프로세스가 조건 x의 변화 발견하면 csignal(x)을 호출함 => 조건 x와 연관된 대기 큐에서 블록된 프로세스 깨움
# 유한 버퍼에서 모니터를 이용한 생산자 소비자 문제 해결 방법 p249
- boundedbuffer : 문자를 저장하고 꺼내갈 떄 사용하는 버퍼 관리
- 버퍼의 접근을 제어하기 위해 두 개의 조건 변수 사용 (cond 데이터 타입)
- notfull : 버퍼에 하나 이상의 문자를 저장할 공간이 남아 있으면 참
- notempty : 버퍼에 하나 이상의 문자가 남아 있을 경우 참
append 프로시저 )
- 생산자는 직접 버퍼 공간을 접근 할 수 없으며 모니터의 append 프로시저를 호출하여 문자를 버퍼에 추가
- notfull 조건 확인
- 버퍼에 여유 공간이 없으면 생산자는 이 조건 변수에서 일시중지
- 다른 프로세스는 모니터로 들어갈 수 있음
- 소비자가 버퍼에서 데이터를 꺼내면 생산자는 일시중지 상태에서 깨어나 중지된 위치에서부터 수행 재개 => 버퍼에 문자 추가
- notempty 조건 변수에 대한 signal 연산 수행
# 모니터와 세마포어 비교
1. 모니터
- 모니터 자체에서 상호배제 보장 => 생산자와 소비자가 동시에 버퍼에 접근할 수 없음
- 동기화 부분만 고려 => cwait과 csignal을 모니터 내부의 적절한 위치에 구현
- 오류 발견 쉬움 (모든 동기화 함수가 모니터 내부에 국한)
2. 세마포어
- 상호배제와 동기화 고려
# 두 개의 프로세스가 모니터 내부의 존재하지 않기 위한 해결 방법
- 모니터에 진입하려는 프로세스들을 위한 큐에 넣음
- 모니터 수행 중에 csignal 호출하고 블록된 프로세스와 새로 진입을 시도하는 프로세스들을 동등하게 처리함
- csingal 을 호출한 프로세스가 블록될 때에는 긴급 큐에 연결
- 모니터는 새로 진입하려는 프로세스보다 긴급 큐에 있던 프로세스를 우선적으로 처리
# 메시지전달 (message passing) p252
- 동기화와 통신 제공
- 단일처리기, 공유 메모리 멀티프로세서, 분산시스템에서 구현 가능
- 주소지정
- send (destination, message)
- receive (source, message) => 가장 기본적인 프리미티브 (메시지 전송을 이용하려는 프로세스에게 필요한 최소한의 연산)
- 프로세스는 전송하려는 정보를 메시지 형태로 만들어 목적 프로세스로 보냄
- source : 메시지를 보낸 프로세스
- primarily used for information exchange => mailbox (port)
- mutual exclusion 과 동기화를 위해 사용 => blocking opertion
# 동기화란 ?
- 프로세스 또는 스레드들이 수행되는 시점을 조절하여 서로가 알고 있는 정보가 일치하는 것
- 상호배제를 보장하기 위해 필요
- 메시지를 받는 쪽은 상대편 프로세스가 메시지를 보내기 전에는 받을 수 없음 => 기본적인 순서 관계 존재
- 블록킹 송신과 블록킹 수신 : 메시지가 전달될 때까지 송신자와 수신자 모두 대기. 랑데부. 프로세스 간 긴밀한 동기화 제공
- 비블록킹 송신과 블록킹 수신 : 메시지 송신자는 계속 수행가능, 수신자는 요청한 메시지가 도착할 때까지 대기. 한 송신자가 다수의 수신자에게 빠르게 하나 이상의 메시지를 보낼 수 있음.
- 비블록킹 송신과 비블록킹 수신 : 송신자, 수진자 모두 대기 안함
# 주소 지정
- 직접 주소 지정 (direct addressing) : PID(프로세스 식별자) 직접 지정
- 간접 주소 지정 (indirect addressing) : 잠시 메시지 보관하는 공유 큐로 보낸다. 큐를 메일박스(공유메모리)라고 함
송신자와 수신자를 나눔으로써 메시지의 사용이 유연해짐
- 프로세스와 메일박스의 관계는 메일박스의 소유권과 연관되어 있음
- 일대일 : 두 개의 프로세스만 연결되는 개인 통신로 => 다른 프로세스의 오류나 간섭에 방해 받지 않음
- 다대일 : 하나의 프로세스가 여러 프로세스에게 서비스를 제공하는 클라이언트/서버 모델 => 메일박스(포트)
- 일대다 : 하나의 송신자와 다수의 수신자 관계. 메시나 정보를 어떤 프로세스 집합에 방송하는 경우 유리
- 다대다 : 여러 개의 서버 프로세스가 동시에 여러 클라이언트에게 서비스를 제공할 때 사용
- 동적으로 프로세스와 메일박스를 연결하고 해제할 때 사용하는 프리미티브 : connect, disconnect
# 메시지 형식 p256
- 헤더가 중요함 => 메시지에 대한 정보
- 본체는 => 메시지의 실제 내용
- 메시지 전달 시스템의 목적에 따라 다름
- 단일 컴퓨터에서 수행될 것인지 분산시스템에서 수행될 것인지에 따라 다름
- 짧고 고정된 길이의 메시지 형식 사용 => 메시지 처리 부하와 저장 공간의 부하 최소화
# 메시지 실행 시 고려사항
- 네이밍 문제
1) 직접 네이밍 방식
- 송신측(sender)이 특정 수신측(recipient)을 설정해야 하고, 반대로 메시지 수신을 희망하는 수신측은 송신측을 설정
2) 간접 네이밍 방식
- 메시지가 특정 목적만을 위하여 사용되는 영역에 송신되고 또 그 영역으로부터 수신
- 이 특정 영역을 우편함(mailbox)이라 함
- 모든 프로세스 간의 메시지 교환은 이 우편함을 이용
# 큐잉 정책
- 선입선출 (FIFO)
- 메시지 타입, 송신자의 선택을 기반으로 메시지 우선순위 명시
- 수신자가 메시지를 검사하여 어떤 것을 받을지 선택
# 메시지 전달을 이용한 상호 배제 p257
- 블록킹 수신과 비블록킹 송신 가정
- 병행 프로세스들의 집합은 box (메일박스) 공유
- 메일박스를 통해 프로세스들은 메시지 전달
- 메일박스는 내용이 비어있는 메시지 하나가 포함되도록 초기화
- 임계영역에 들어가고자 하는 프로세스는 메일박스에서 메시지를 수신해야함
- 메일박스가 비어있을 경우 프로세스는 블록됨
- 인계영역을 빠져나올 때 메시지를 메일박스에 송신
- 메시지는 프로세스 간 전달되는 토큰 역할
하나 이상의 프로세스들이 동시에 receive를 호출하는 경우 )
- 메일박스에 메시지가 있을 경우, 이 메시지는 오직 하나의 프로세스에 전송되고, 다른 프로세스들은 블록됨
- 메일박스가 비어있을 경우 모든 프로세스는 블록됨
- 메일박스에 새로운 메시지가 도착할 때 블록된 프로세스 중 하나만 깨어나서 그 메시지 받음
# 유한 버퍼에서 메시지를 이용한 생산자/소비자 문제 해결 방법 p258
- 2개의 메일박스 : mayconsume, mayproduce
- 생산자가 데이터를 만들면 이를 메시지로 만들어서 mayconsume 에 보냄
- 메일박스에 적어도 하나의 메시지가 존재하면 소비자는 계속하여 수행 가능
- mayconsume 은 버퍼 역할 수행. 버퍼 크기는 전역 변수 capacity에 의해 관리
- mayproduce는 버퍼 용량만큼 널 메시지로 채운 다음, 메시지 수는 메시지가 생성될 때마다 감소하고 소비하면 증가됨
- 단지 시그널을 전달할 수 있는 기능뿐만 아니라 데이터를 전달할 수 있는 기능도 이용
# 판독자/기록자 문제 p259
# 조건
1. 여러 판독자가 공유 데이터를 동시에 읽을 수 있음
2. 한 순간에 단 하나의 기록자만이 공유 데이터를 변경할 수 있음
3. 기록자가 데이터를 변경하고 있는 동안에는 판독자가 그 파일을 읽을 수 있음
=> 판독자는 다른 판독자를 배제시키지 않고 작업 수행 가능
=> 기록자는 다른 기록자나 판독자를 모두 배제시키고 작업 수행해야 함
****************** 과제 *******************
./shm1 & => 하나는 백그라운드로 돌림
- 포그라운드 : 현재 실행 중인 것
- 백그라운드 : 대기 함, 현재 실행 중인 것이 쉴 때 잠깐 잠깐 수행하는 것
- p, v 연산
- 똑같은 프로그램을 하나는 백그라운드, 하나는 포그라운드 두고 실행
- OO와 XX 각 10번 출력
################ 6장. 교착상태와 기아상태 ##################
# 교착상태 p280
- 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태
- 2개 이상의 프로세스들이 공유 자원에 대한 경쟁이나 통신 중에 발생 (다른 블록된 프로세스의 자원을 기다리면서 자신도 블록)
- 시스템 자원에 대한 경쟁 도중에 발생하거나 프로세스 간 통신 도중에 발생
# 결합 진행 다이어그램 (Jonit Progress Diagram) p281, 2
- 프로세스와 컴퓨터 자원 관계에서 교착상태
- P와 Q 라는 두 개의 프로세스가 A와 B라는 자원을 경쟁적으로 사용하며 수행하는 과정
- 동시에 돌고 있음
- 각 프로세스는 일정 기간 동안 두 개의 자원을 동시에 배타적으로 사용해야 함
- P에서 A를 잡고, Q에서 B를 잡음
- 단일처리기의 경우 : 한 시점에 수행되는 프로세스가 하나밖에 없으며 따라서 진행 경로는 수평 또는 수직 방향으로만 움직임
=> 원점에서 출발하여 P가 수행하면 오른쪽 수평 방향으로, Q가 수행하면 위쪽 수직 방향으로 진행
- 대각선 영역 : 진행 경로가 진입할 수 없는 영역 (치명적인 영역(fatal region)) => 교착상태 발생
1. Q가 B를 획득한 후 A를 획득 -> Q가 수행 완료 이후 두 자원 반납 -> P가 수행되면 두 자원 사용 가능
2. Q가 B를 획득한 후 A를 획득, P가 수행 ( A 획득 실패하고 블록됨 ) -> Q가 수행 완료 이후 자원 반납 -> P가 깨어나서 두 자원 사용 가능
3. Q가 B를 획득하고 P가 A 획득 -> Q가 A 획득 시도하다가 블록됨, P가 B 획득 시도하다가 블록됨 => 서로 기다리면 블록되어 있기 떄문에 더 이상 진행 될 수 없음 (교착상태 발생)
4. P가 A를 획득하고 Q가 B 획득 -> P가 B 획득 시도하다가 블럭됨, Q가 A 획득 시도하가가 블록됨 => 교착상태 발생
5. P가 A 획득한 후 B 획득함, P 수행 ( B 획득 실패하고 블록됨) -> P가 수행 완료 이후 자원 반납 -> Q가 깨어나서 두 자원 사용 가능
6. P가 A를 획득한 후 B 획득 -> P가 수행 완료 이후 두 자원 반납 -> Q가 수행되면 두 자원 사용 가능
# 교착상태가 발생하지 않는 예
'전공 공부 > 운영체제' 카테고리의 다른 글
| 운영체제 14주차 강의 (0) | 2021.06.01 |
|---|---|
| 운영체제 11주차 강의 (0) | 2021.05.11 |
| 운영체제 9주차 강의 (0) | 2021.04.27 |
| 운영체제 7주차 강의 (0) | 2021.04.13 |
| 운영체제 5주차 강의 (0) | 2021.04.04 |
