내맘대로 요약정리. 귀찮은 부분은 스킵. 재밌는 부분은 폭풍타자. 잇힝~
*
결정성 : 병행으로 실행되는 프로세스들은 그 순차적 실행의 흐름이 매번 다르지만
같은 조건과 입력이 주어질 때, 같은 결과를 산출해야 한다.
* 프로세스 시스템은 프로세스의 집합과 이들의 선행 제약의 두 가지 요소로 정의된다.
즉, 프로세스의 목록과 이들간의 순서가 정의되어야 한다.
- 선행 그래프 : 프로세스 시스템 내의 프로세스간 선행관계를 Directed Graph로 표현한 것. 물론 사이클이 없어야한다.
- 한 프로세스 시스템에 있어서, 비간섭 관계는 그 시스템이 결정적인가에 대한 필요충분조건이다.
즉, 프로세스들이 비간섭이면 그 시스템은 결정성이 있는 것이고,
결정성이 있는 시스템에서는 프로세스들이 비간섭 관계에 있는 것이다.
* 생산자/소비자 문제 : 유한한 크기의 버퍼에 생산자 프로세스와 소비자 프로세스가 병행으로 자료를 삽입/인출할 때 발생하는 문제.
- 상호 배제의 문제 : 공유 자료에 동시에 접근하여 발생하는 자료의 일관성 문제
- 동기화의 문제 : 버퍼가 full이면 인출하는 소비자가 대기하는 생산자를 깨워주고,
empty이면 삽입하는 생산자가 대기하는 소비자를 깨워주어야 하는 문제.
- 임계구역 : 각 프로세스가 공유변수, 자료구조, 파일등을 베타적으로 읽고 쓸 수 있도록 설정한 코드 세그먼트
상호간에 영향을 미치는 임계 구역은 서로에 대해 원소적 실행이 보장되어야 한다. 즉, 한 프로세스가 임계 구역을 실행하고 있는 동안에 문맥 교환이 발생하여 다른 프로세스가 실행되더라도 선점 당한 임계구역에는 진입하지 못하도록 해야 한다.
- 상호 배제의 요구조건 : 한 프로세스가 임계 구역을 실행 중일 때, 다른 어떤 프로세스도 임계 구역을 실행할 수 없다.
임계 구역을 실행하는 프로세스가 없는 상황에서 여러 개의 프로세스들이 임계 구역이 들어오고자 하는 상황에서는 반드시 하나의 프로세스를 선택하여 진입시키는 올바른 결정 기법이 있어야 한다.
- 제한된 대기 : 한 프로세스가 임계 구역 진입 요청을 보낸 후 수락을 받을때까지의 기간 내에, 다른 프로세스가 임계 구역을 실행할 수 있는 횟수에는 제한이 있어야 한다. 이게 뭔소리야 도대체..
한 프로세스가 결론적으로 '수락을 받는다'는건 지금 임계구역을 사용중인 프로세스가 없단 얘기잖아. 그러니까 수락을 응답 받는거 아냐. 근데 "다른 프로세스"가 임계 구역을 실행하는 횟수가 존재한다고?! 이....이게 무슨 소리요 저자양반....
* 상호 배제의 S/W적 구현
- lock test 함수를 만들어서 하는 경우, 그 안에서 문맥 교환이 일어날 수 있으므로 상호배제가 성립되지 않는다.
- 올바른 방법은 한번 양보를 하고 대기하는 것이다. 대기에서 벗어나는 조건은 상대의 플래그가 0이 되거나 턴이 나에게 있을 때이다. 그렇게 해 놓으면 어느 상황에서 문맥 교환이 일어나더라도 상호배제가 성립된다.
- Bakery 알고리즘 : 여러개의 프로세스를 위한 상호배제 알고리즘
대기하는 각 프로세스는 우선 번호표를 하나씩 뽑는다. 각 프로세스는 자신의 번호가 가장 작은 번호가 될 때까지 기다린다.
* 상호 배제의 H/W적 구현
- Test-and-Set : Lock에 대한 test와 copy를 CPU의 명령어로 제공 ( atomic instruction )
타겟의 값을 1로 만들고, 이전의 타겟 값을 리턴하는 함수.
- Swap : 두 변수의 교체를 CPU의 명령어로 제공.( atomic instruction )
누군가 lock을 0으로 리셋하면 다음 스왑에서 키 값이 0이 되고, 임계구역에 진입한다. 이 때 그 '누군가'는 이미 임계구역에서의 작업을 전부 마친것.
- interrupt-disable/enable : 임계 구역 내의 문맥교환 자체를 방지. 특권 명령어이기 때문에 커널 모드에서만 사용가능.
* 세마포어
- 일종의 객체.
- 정수 변수 1개와 프로세스 대기 큐, 정수에 대한 3가지 연산을 제공한다.
- 프로세스가 임계구역 진입 불가능시에는 대기 상태로 전환한다. 임계구역에서 작업을 마친 프로세스가 대기중인 프로세스를 준비 상태로 깨운다.
- 세마포어의 정수 변수는 양수일 때, 남은 자원의 갯수를 의미하고,
음수일 때, 대기 중인 프로세스 갯수를 의미한다.
- 자원이 여러 개 있을 경우, 자원과 대기자를 동시에 관리할 수 있다.
- 정수 변수의 초기값 n이 1인 경우, 공유변수에 대해 임계구역(mutex)이고,
0인 경우, event에 의한 다중 쓰레드 간의 동기화에 사용된다.
- SW나 HW적인 방법들은 전부 "busy waiting" 알고리즘이다. 임계구역앞에서 대기하는 프로세스마다 busy waiting loop를 실행하는 것은 타임 슬라이스 낭비이다. 세마포어는 wait와 signal을 수행하는 짧은 기간에만 busy waiting loop를 실행한다.
* 병행 읽기/쓰기의 문제
- 공유 변수나 파일에 대해 쓰기 연산을 하는 프로세스는 모든 프로세스에 대해 상호 배제를 필요로 한다.
읽기 연산을 하는 프로세스는 읽기 프로세스들과는 임계구역을 공유하고,
쓰기 프로세스에 대해서는 상호 배제를 필요로 한다.
- 기아 : 무기한 연기 라고도 한다. 읽기 프로세스가 계속 되면 쓰기 프로세스는 계속 기다리기만 한다.
기아의 해결책으로 aging 기법을 사용한다. 대기 시간이 길어지면 우선순위를 높이는 것이다.
- 모니터 : 세마포어를 클래스로 만든 형태. 데이터멤버와 멤버함수들로 구성된다.
"cfile29.uf@171A983B4F8C30972B03D7.jpg"
