# 병행성 (Concurrency)
- 동시에 작동
- 동시에 도는 프로세스들 간에 순서를 어떻게 정할 것인지
# 멀티프로그래밍
- 단일 처리기 시스템 상에서 다수의 프로세스의 관리
- cpu 1개
# 멀티프로세싱
- 멀티프로세서 시스템 상에서 다수의 프로세스 관리
- cpu 여러 개
- 동시 실행 가능 (인터리빙) - 병행적
# 분산처리
- 다수의 분산된 컴퓨터 시스템들 상에서 수행되는 다수의 프로세스 관리
- 클러스터 시스템
# 병행성 발생 상황
- 다수의 응용 : 동시수행 중인 여러 응용들 간에 CPU를 공유하기 위해 멀티프로그래밍이 발전
- 구조화된 응용 : 모듈화된 설계 원칙과 구조적인 프로그램이 발전되면서 일부 응용이 병행 프로세스들로 구현됨
- 운영체제 구조 : 운영체제도 다수의 프로세스와 쓰레드의 집합으로 구현
# 병행 처리의 문제점
- 전역 자원의 공유 어려움
- 운영체제가 자원을 최적으로 할당하기 어려움
- 프로그래밍 오류를 찾아내는 것이 어려움
- 쓰레드는 코드, 데이터, 파일 공유 (전역 자원) => 동시에 write 하면 데이터 깨짐
- 인터리빙(프로세스들이 서로 번갈아가면서 수행), 오버래핑(동시에 두 개가 씀)은 단일처리기 시스템이나 다중처리기 시스템에서 동일
# 원자적 연산 (atomic operation)
- 더 이상 분할할 수 없는 단위
- 하나 또는 여러 개의 명령어들로 구성된 함수 또는 액션
- 병행 프로세스들에게 고립을 보장
- 값이 안바뀌거나 값이 정확히 바뀌거나 (명령어들은 모두 수행되거나 하나도 수행되지 않음이 보장됨)
# 교착 상태 (deadlock) p281
- 두 개 이상의 프로세스가 서로 맞물려서 더 이상 진행 할 수 없는 상태
- 모든 프로세스가 서로 연결되어 다른 프로세스의 진행을 기다리면서 대기하고 있을 때 발생
# 라이브 락 (livelock)
- 두 개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화시키는 작업만을 수행하고 있는 상태
- 각 프로세스들은 열심히 수행하고 있지만 수행하는 작업은 유용한 작업은 유용한 작업이 아닌 반복적인 상태 변화임
- 무한 루프 도는 것
- 쓸데 없는 작업만 계속 함
# 경쟁 상태 (race condition)
- 두 개 이상의 프로세스가 공유 자원을 동시에 접근(읽거나 씀)하려는 상태
- 최종 수행 결과는 프로세스들의 상대적인 수행 순서에 따라 달라질 수 있음
예1) p1과 p2가 전역변수 a 공유
수행 중 p1은 a를 1로 수정, p2는 2로 수정 => 서로 경쟁
경쟁에서 진 프로세스(마지막으로 변수에 접근한 프로세스)의 수정 결과가 전역 변수 a의 최종 저장 값 됨
예2) b=1, c=2로 초기화된 전역 변수를 공유하는 두개의 프로세스 p3, p4
p3 은 b = b+c 연산 수행, p4는 c = b+c 연산 수행
수행 순서에 따라 결과 달라짐
p3이 먼저 수행하면 b = 3, c = 5 이 최종 결과
p4가 먼저 수행하면 b = 4, c = 3 이 최종 결과
# 기아 상태 (starvation)
- 특정 프로세스가 수행가능한 상태임에도 불구하고 매우 오랜 기간 동안 스케줄링되지 못하는 경우
- 특정 프로세스가 오랜 기간 동안 자원을 사용하지 못하는 상태
# 인터리빙(interleaving)
- 단일처리기 멀티프로그래밍 시스템에서 프로세스들은 서로 번갈아가면서 수행됨
- 사용자에게 동시에 수행되는 것과 같은 효과 제공
- 병렬 처리는 아님
- 프로세스들 간에 문맥 교환을 위한 비용 발생
- 시스템의 처리 효율과 구조적인 프로그래밍
# 오버래핑(overlapping)
- 병렬 처리(concurrent processing)
-
# 인터리빙과 오버래핑 문제
- 단일처리기 시스템의 경우, 프로세스들의 수행의 상대 속도 예측할 수 없음
=> 운영체제의 스케줄링 정책과 다른 프로세스들의 활동, 운영체제가 인터럽트를 처리하는 방법 등에 따라 동적으로 변함
1) 전역 자원의 공유에 어려움 발생 => 수행 결과 달라짐
2) 운영체제가 자원을 최적으로 할당하기 어려워짐 => 교착상태 발생
3) 프로그래밍 오류를 찾아내는 것이 어려워짐
=> 멀티프로세서 시스템에서도 발생
# 병행 처리(concurrent processing)의 예와 문제점
void echo()
{
chin = getchar();
chout = chin;
putchar(chout);
}- echo 함수 : 프로그램에서 문자 입력 및 출력 기능을 제공함
- chin : 키보드에서 문자를 하나 입력받아 저장
- chout : chin 변수의 내용을 치환
- putchar : 모니터에 출력
# 단일처리기 기반 멀티프로그래밍 시스템에서 echo 함수의 동작
- 같은 키보드, 같은 스크린 사용
- 공유 라이브러리로 만들고, 모든 응용들이 접근할 수 있는 전역 메모리 공간에 적재
- 장점 : 공간 절약의 효율성, 프로세스들의 긴밀한 상호작용
- 단점 :
1) 프로세스 p1의 echo 함수 호출 => getchar 함수 호출하여 사용자의 문자 입력 대기
사용자가 'x' 입력하면 chin 변수에 저장
이 때 운영체제 p1을 선점하고, 다른 프로세스 p2의 수행을 결정하였다고 가정
2) 프로세스 p2가 활성화됨, echo 함수 호출
사용자가 'y' 입력하면 chin 변수에 저장
3) 프로세스 p1의 수행이 다시 재개되면 chin에 'y' 값 저장되어 있음 => 'y' 출력함
=> 'x' 유실, 'y' 두번 출력됨
=> 전역 변수 chin을 두 개 이상의 프로세스가 공유하기 때문에 문제 발생
=> 한 프로세스가 전역 변수를 갱신할 후 일시중지되고, 다른 프로세스가 같은 전역 변수를 접근하여 수정하면, 기존 프로세스의 값을 잃게 됨
# 한 시점에 오직 한 프로세스만이 그 함수 내부에 존재할 수 있다고 제한
1) 프로세스 p1의 echo 함수 호출 => getchar 함수 호출하여 사용자의 문자 입력 대기
사용자가 'x' 입력하면 chin 변수에 저장
이 때 운영체제 p1을 선점하고, 다른 프로세스 p2의 수행을 결정하였다고 가정
2) 프로세스 p2가 활성화됨, echo 함수 호출
p1이 일시중지된 상태여도 echo 함수 내에 있기 떄문에, p2는 echo 함수로 진입 못함
p2는 echo 함수가 가능할 때까지 일시중지됨
3) p1은 수행 재개되고 echo 실행 완료됨 => 'x' 출력
4) p1이 echo 함수에서 나왔을 때 p2는 일시중지 상태에서 깨어남
p2의 수행이 재개되고, 사용자가 'y' 입력하면 'y' 출력
=> 공유 자원을 접근하는 프로그램 코드 부분을 제어하여 전역 변수 보호
=> 단일처리기 기반 멀티프로그래밍 시스템에서 발생
# 멀티프로세서 시스템의 경우 공유 자원의 보호
1) 두 개의 프로세스 p1과 p2가 각각 서로 다른 처리기에서 동시에 수행됨
p1과 p2는 모두 echo 함수를 호출
2) 위의 순서로 진행
같은 줄에 기술된 이벤트는 병렬적으로 수행되는 것
=> p1에서 입력받은 문자는 화면에 출력되기 전에 손실되고 프로세스 p2에서 입력받은 문자가 두 번 출력
# 멀티프로세서 시스템에서 오직 하나의 프로세스만이 echo 함수 내에 존재할 수 있다는 원칙 적용
1) p1과 p2가 각각 서로 다른 처리기에서 동시에 수행됨
p1이 echo 함수 호출
2) p1이 echo 함수 내부에서 수행하는 동안, p2가 echo 함수 호출
p1이 함수의 내부에 존재하기 때문에(수행 중인 상태이거나 일시중지 상태) p2는 echo 함수로 진입하지 못하고 블록됨
p2는 echo 함수가 사용 가능해질 때까지 대기하며 일시중지됨
3) p1은 echo 함수 실행 완료하여 빠져 나옴
p2는 블록 상태에서 깨어나며 다시 echo 함수의 수행 시도
# 단일처리 시스템의 경우
- 인터럽트가 프로세스의 수행 중 어떤 위치에서라도 명령의 수행을 중지시키며 발생할 수 있기 때문
# 멀티프로세서 시스템의 경우
- 인터럽트의 비동기적인 발생(싱크가 맞지 않다)뿐만 아니라 두 개의 프로세스들이 동시에 수행되면서 같은 전역 변수를 접근하려 하기 때문
=> 두 경우의 해결책 : 공유 자원 동기화 접근 제어
# 운영체제의 고려사항들
1. 모든 프로세스들의 상태와 수행 위치를 추적할 수 있어야 함 => 프로세스 제어 블록(PCB)을 이용하여 구현
2. 활동 중인 각 프로세스에 다양한 자원을 할당하고 해제할 수 있어야 함
자원 : 처리기 시간(어떤 프로세스에 얼마만큼의 cpu 사용을 허용할 것인가, 스케줄링 기법), 메모리(가상 메모리 기법), 파일, I/O 장치
3. 각 프로세스에 할당된 자우너과 데이터들을 다르 프로세스들의 예끼치 못한 간섭으로부터 보호해야 함
(메모리, 파일, I/O 장치들을 다루는 기법)
4. 프로세스의 기능과 수행 결과는 프로세스의 수행 속도 및 동시에 수행되는 다른 프로세스들의 상대적인 수행 속도와 독립적이어야 함
# 프로세스 간 상호작용
- 다른 프로세스들의 존재에 대하여 어느 정도로 인식하고 있는 지를 기준으로 분류
1) 서로를 인식하지 못하는 프로세스들
- 협동 작업을 하지 않는 서로 독립적인 프로세스들
- 다수의 독립적인 프로세스들로 구성된 멀티 프로그래밍 환경
- 각 프로세스들은 일괄 작업 수행 할 수 있음, 대화형 작업 수행 할 수 있음, 두 형태가 혼합 가능
- 프로세스들 간에 자원에 대한 경쟁 고려해야 함
- 예) 서로 다른 두 프로세스가 디스크, 파일, 프린터를 동시에 사용하려고 하면 운영체제가 이들에 대한 접근 조절해야함
2) 서로 간접적으로 인식하고 있는 프로세스들
- 다른 프로세스들의 이름(ID)을 알고 있지는 않지만, 입출력 버퍼와 같은 자원을 공유하는 프로세스들
- 서로 간에 공통 자원 공유를 통한 협력(cooperation)관계를 가짐
3) 서로를 직접적으로 인식하고 있는 프로세스들
- 다른 프로세스들의 이름(ID)을 알고 있음, 이를 이용해 직접 통신함
- 협력 관계 가짐
- 공통된 작업을 함께 수행하기 위해 설계됨
# 자원에 대한 프로세스 간 경쟁
- 운영체제가 한 프로세스에게만 자원 할당, 나머지 하나는 기다림 => 수행 속도 떨어짐, 무한 대기 상태 빠질 수 있음
- 경쟁 관계에 있는 프로세스들이 존재하는 경우 상호 배제, 교착상태, 기아 세 가지 제어 문제 발생
# 상호배제 (mutual exlusion)
- 한 프로세스가 공유 자원을 접근하는 임계영역 코드를 수행하고 있으면, 다른 프로세스들은 공유 자원을 접근하는 임계영역 코드를 수행할 수 없다는 조건
- 한 프로세스가 특정 자원을 사용할 때 다른 프로세스들은 그 자원을 사용할 수 없도록 배제
- 한 시점에 단 하나의 프로세스만이 임계영역에 들어갈 수 있음
- 상호배제의 보장은 교착상태와 기아 발생
# 임계영역 (critical section)
- 공유 자원을 접근하는 프로세스 내부의 코드 영역
- 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원에 접근하는 프로그램 코드의 일부분
- 다른 프로세스가 이 영역에 있을 때 이 영역을 수행할 수 없음
- 임계 자원 : 프린터 (두 개 이상의 프로세스가 동시에 사용할 수 없는 자원, critical resource)
- 임계 영역 : 프린터 명령, 데이터를 보내거나 프린터의 상태를 확인하는 프로그램 코드 부분
# 경쟁에 대한 제어
- 운영체제가 자원을 할당함
- 프로세스는 자신이 요구하는 상호배제의 요구 조건과 위치를 명시해야 함
- 자원 사용 전에 잠금(lock) 설정
- 운영체제는 잠금 설정이나 해제 인터페이스 제공 등을 통해 상호 배제 보장 지원
- 임계영역에는 한 시점에 한 프로세스만이 존재하도록 함
- 상호배제를 보장하기 위해 entercritical 과 exitcritical 함수 제공
- 각 함수는 공유하려는 자원 이름을 인자로 사용함
- 이미 다른 프로세스가 임계영역에 존재하고 있을 때 entercritical 함수를 호출 프로세스는 대기함
# 프로세스 간 협력
1) 공유를 이용한 프로세스 간 협력
1-1) 간접적이 ㄴ협력
- 프로세스들은 서로 명시적으로 알지 못하지만 서로 상호작용 함
- 다수의 포레스들이 공유 변수나 공유 파일, 공유 데이터베이스를 접근하는 것
- 프로세스들은 공유하는 데이터가 적절하게 관리될 수 있또록 서로 협력함
- 공유 데이터의 무결성 보장
- 제어 문제 발생(상호배제, 교착상태, 기아) - 공유되는 데이터가 자원(메모리나 장치)에 저장되기 때문
- 데이터 일관성 유지
2) 통신을 이용한 프로세스 간 협력
- 모든 프로세스들이 서로를 인식함
- 공통의 목표를 위해 결합
- 통신은 프로세스 간 동기화와 협력, 다양한 공통 행위를 수행할 떄 사용
- 특정 유형의 메시지들로 구성됨
- 상호배제 문제 없음
- 교착 상태 , 기아 문제 발생
# 상호배제 요구조건
- 어느 한 순간에는 오직 하나의 프로세스만이 임계영역(critical section)에 진입할 수 있다. => 상호배제 강제
- 임계영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안 된다.
- 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미뤄져서는 안 된다. 즉, 교착상태(deadlock) 및 기아(starvation)가 일어나지 않아야 한다.
- 임계영역이 비어 있을 때, 임계영역에 진입하려고 하는 프로세스가 지연되어서는 안 된다. => 즉시 들어 감
- 프로세서의 개수나 상대적인 프로세스 수행 속도에 대한 가정은 없어야 한다.
- 프로세스는 유한 시간 동안(일정한 시간)만 임계영역에 존재할 수 있다.
# 상호배제의 요구조건을 만족시키는 접근 방법
1) 소프트웨어적인 접근 방법 - 모든 책임을 병행 수행하려는 프로세스들이 담당함
- 프로그래밍 언어나 운영체제의 특별한 지원 없이, 프로세스 간 협력을 통해 직접 상호배제를 보장
- 수행 부하가 크고 잘 설게되지 않을 경우 오동작의 가능성 높음
2) 특별한 용도로 설계된 기계어 이용
- 부하가 적음
3) 운영체제나 프로그래밍 언어 수준에서 상호 배제 보장 제공
# 상호배제 보장하기 위한 하드웨어적인 접근
1) 인터럽트 금지(Interrupt Disable)
- 단일처리기에서 병행 처리되는 프로세스들은 오버래핑이 아니라 인터리빙됨(번갈아 가면서 수행, 동시 아님)
- 프로세스는 운영체제 서비스를 호출하거나 인터럽트될 때까지 계속 실행
- 상호배제를 보장하기 위한 방법은 프로세스가 인터럽트되지 않도록 함
- 시스템 커널은 인터럽트를 허용하거나 허용하지 않도록 하는 기본적인 인터페이스 제공
while (true){
/* 인터럽트 금지 */;
/* 임계영역 */;
/* 인터럽트 허용 */;
/* 임계영역 이후 코드 */;
}- 임계영역에서는 인터럽트가 발생할 수 없음 => 상호배제 보장, 부하가 큼, 시스템 수행 효율 감소
- 멀티프로세서 시스템에서는 올바르게 상호배제 보장 못함
- 멀티프로세서 시스템에서는 인터럽트가 금지된 상황에서도 서로 다른 프로세스가 공유 자원을 동시에 접근 가능하기 때문
2) 특별한 기계 명령어
- 같은 메모리 위치에 대한 읽기와 쓰기, 같은 메모리 위치에 대한 읽기와 테스트를 하나의 명령어 인출 사이클 동안 처리하는 기계 명령어
- 이 기계 명령어가 수행되는 동안 같은 위치를 접근하려는 다른 명령어들은 블록됨
2-1) Compare&Swap 명령어
int compare_and_swap (int *word, int testval, int newval){
int oldval;
oldval = *word;
if (oldval == testval) *word = newval;
return oldval;
}- testval : 테스트하려는 값
- *word : 메모리 위치에 저장된 값
- testval와 *word 값이 동일하면 메모리의 값은 새로운 값(newval)으로 변경됨
- oldval : 기존의 값
- 리턴한 값(oldval)이 testval 와 같으면 메모리의 값은 갱신된 상태
- 1. compare : 메모리에 저장된 값과 테스트하려는 값을 비교하는 부분
- 2. swap : 값을 바꾸는 부분
- compare&swap 함수는 원자적으로 수행되며 중간에 중단되는 경우는 없음
# compare&swap 함수를 이용한 상호배제 프로토콜 p229
- 공유변수 bolt 사용 (0으로 초기화 - 임계영역에 프로세스가 존재하지 않음을 의미)
- bolt가 1이면 프로세스가 임계영역에 진입하여 수행 중임을 의미
- 임계영역에 진입할 수 있는 유일한 프로세스 : bolt가 0일 때 compare&Swap 명령을 호출한 프로세스
- 임계영역에 이미 프로세스가 존재하고 있을 때, 임계영역에 진입하려는 다른 프로세스들은 대기하게 됨
=> 바쁜 대기(busy waiting, spin waiting) 수행
* 바쁜 대기 : 프로세스가 임계영역에 들어가기 위한 허가를 획득할 때까지 변수를 테스트 하는 명령을 반복 실행하는 것
- 대기하고 있는 프로세스들 중 누가 먼저 compare&swap 명령 호출했는가에 의해 결정
2-2) exchange 명령어
void exchange (int *register, int *memory){
int temp;
temp = *memory;
*memory = *register;
*register = temp;
}- 레지스터의 값과 메모리에 들어있던 값을 서로 교체하는 기능 수행
- 공유변수 bolt는 0으로 초기화
- 각 프로세스는 key라는 지역 변수 이용 (1로 초기화)
- 임계영역으로 진입할 수 있는 프로세스는 bolt가 0일 때, exchange 명령어를 수행한 프로세스임
- 다른 프로세스의 진입을 막기 위해 bolt를 1로 설정
- 임계 영역에서 나갈 때 bolt를 0으로 설정
- bolt 가 1이면 단지 하나의 프로세스, key값이 0인 프로세스만 임계영역에 들어감
# p230 코드
- 동시에 10개가 돌고있음
- i가 1 ~ n (n==10)
- 상호배제 프로그램
- 10개가 경쟁함
- 어느 것이 먼저 수행하든 원자적 연산함
- bolt 값이 0 이면, bolt=1 로 바꾸고 0을 return
- bolt값이 0이 아니면,(값이 같지 않으면), bolt 값 달라지지 않고 bolt 값 return
# 상호배제 해결방법
- 어느 한 순간에는 오직 하나의 프로세스만이 임계영역에 진입
- 임계영역에서는 인터럽트가 발생할 수 없어서 상호배제는 보장됨
# 상호배제 구현방법
- 소프트웨어적 접근방법 : 수행 부하가 높고, 논리적 오류의 위험성이 큼
- 하드웨어 지원 : 인터럽트 금지(오버헤드가 큼), 특별한 기계 명령어: Test and Set, Exchange
- 세마포어
- 모니터
- 메시지 전달
# 슈도 코드
- 임시코드
# parbegin
- 병렬적으로 수행
- main 함수 수행 중지
- p1, p2가 동시에 수행
- 모든 함수들의 수행이 완료되면 main 수행 재개
# 기계 명령어 접근 방법의 특성
1) 장점
- 단일처리기 시스템뿐만 아니라 공유 메모리를 사용하는 멀티프로세서 시스템에서도 사용 가능
- 간단하고 검증 쉬움
- 서로 다르 변수를 사용하면 여러 개의 임계영역 지원
2) 문제점
- 바쁜 대기 사용 => 임계영역에 진입하고자 기다리고 있는 프로세스는 처리기를 계속 사용하고 있어야 함
- 기아 발생 => 프로세스가 임계영역을 빠져나오고 대기하던 프로세스가 여러 개이면, 무한정 기다리게 되는 프로세스 발생
- 교착 상태 발생 => 단일처리기 시스템에서, p1이 임계 영역에 있고, 더 높은 우선 순위 p2 생성하고, p2가 같은 자원 접근 시도하면 상호배제 조건에 의해 접근 실패, 바쁜 대기 수행, p1은 우선순위가 높은 p2가 계속 실행 상태이므로 스케줄링 될 수 없음
# 세마포어 **********중요 ***********
- 프로세스 간에 시그널을 주고 받기 위해 사용되는 정수 값
- 프로세스 간에 동기화를 위함
- 공유 변수
- 상호 배제를 운영체제와 프로그래밍 언어 수준에서 지원하는 메커니즘
- 블록(수면)과 깨움을 지원
- 주차장 전광판에 주차가능 대수가 세마포어 변수 s 값 비유
- 블록됐다는 것은 차가 주차장에 못들어가고 대기한다는 것과 같음
- semSignal : 세마포어 s를 통해 시그널을 전송하기 위해 프로세스가 사용 (프리미티브)
- semWait : 세마포어 s를 통해 시그널을 수신하기 위해 프로세스가 사용 (프리미티브)
- 특정 시그널을 받으려는 프로세스에게 아직 그 시그널이 전달되지 않았다면, 전달될 때까지 프로세스의 수행 일시중지됨
# 세마포어에 접근하는 세 가지 연산
1) 세마포어 초기화 연산(Initialize operation) : 세마포어 값을 음이 아닌 값으로 초기화한다.
2) semWait 대기 연산(Wait operation) : 세마포어 값을 감소시킨다
- 값이 음수이면 호출한 프로세스는 블록 된다.
- 음수가 아니면 프로세스는 계속 수행될 수 있다.
3) semSignal 시그널 연산(Signal operation) : 세마포어 값을 증가시킨 다. 값이 양수가 아니면 블록된 프로세스를 깨운다.
- 세마포어는 0 또는 양수 값으로 초기화됨
- 양수이면 그 값은 semWait 을 호출한 후 대기 없이 계속 수행할 수 있는 프로세스의 개수
- 0이면 semWait를 호출하는 프로세스들은 블록되고 세마포어 값은 음수가 됨
- semWait가 더 호출되면 계속 세마포어 값은 감소됨
- 세마포어 값의 절대 값은 블록 상태인 프로세스의 개수
- semSignal이 호출되면 세마포어 값은 증가하고 대기하는 프로세스가 있으면 하나씩 깨어남
# 유지할 수 있는 값의 범위에 따라
1) 이진 세마포어 (binary semaphore) p235
- 세마포어 초기화 : 0이나 1로 초기화
- semWaitB 연산 : 세마포어 값 확인.
0이면 semWaitB 호출한 프로세스 블록됨
1이면 값을 0으로 변경시키고 프로세스는 계속 수행됨
- semSignalB 연산 : 블록되어 있는 프로세스가 존재하는지 확인
존재하면 그 프로세스 꺠움
존재하지않으면 세마포어 값을 1로 설정
- 0또는 1 값 가짐
- 락을 설정한 프로세스와 해제하는 프로세스가 서로 다를 수 있음
# 뮤텍스(mutex)
- 이진 세마포어와 유사, 락을 획득(값을 0으로 설정)한 프로세스가 반드시 그 락을 해제(값을 1로 설정)해야 함
- 객체를 얻거나 반납할 때 사용하는 프로그래밍 플래그
- 사용하려는 데이터가 공유될 수 없거나 연산이 동시에 수행될 수 없는 경우, mutex 설정되고 (보통 0) 접근/연산을 시도한 프로세스들은 블록됨
- 데이터에 대한 접근이 더 이상 필요 없거나 연산이 완료되면, mutex의 락 해제됨
2) 범용 세마포어 (general semaphore, counting semaphore)
- 일반 세마포어 (카운팅 세마포어) p234
- wait : 블록상태로 만들어서 대기시킴
- singal : 준비 큐에 연결
# 큐 (queue) 이용
- 큐에 있는 프로세스들 중 어떤 프로세스를 먼저 깨워야 하는가
- FIFO, 선입선출 => 가장 오래 블록되어 있던 프로세스를 먼저 깨움 : 강성 세마포어 (strong semaphore)
- 큐에서 제거되는 순서를 명시하지 않은 세마포어 : 약성 세마포어 (weak semaphore)
- 강성 세마포어는 기아 상태 발생하지 않음 <=> 양성 세마포어는 기아 상태 발생
# 세마포(semaphore)
- 동기화 도구
- P(wait - 감소)와 V(singal - 증가)연산
# 세마포어를 이용한 상호배제 문제 해결 p237
- 동일한 자원을 접근하려는 n개의 프로세스 존재
- 각 프로세스 i는 P(i)를 수행
- 각 프로세스는 임계영역에 들어가기 직전에 semWait(s) 호출함
- s의 값이 양수가 아니면 프로세스는 블록됨
- s의 값이 1이면 1만큼 감소시킨 후 임계영역에 들어감
- s의 값이 더 이상 양수가 아니므로 다른 프로세스들은 임계영역에 진입할 수 없음
- 세마포어는 1로 초기화.
- 최초로 semWait를 수행하는 프로세스가 s 값을 0으로 바꾸고 임계영역에 들어감.
- 다른 프로세스들은 블록되고 s의 값은 1씩 감소됨
- 임계영역에 들어갔던 프로세스가 빠져나오면 s는 1증가되고 블록되었던 프로세스들 중에서 하나가 블록 큐에서 나와서 준비 큐로 이동
# 세마포어를 이용하여 상호배제를 구현한 프로세스들의 수행 과정 : 3개의 프로세스 존재 P238
- A, B, C는 lock이라는 세마포어 변수에 의해 보호되는 공유 자원을 접근함
- 우선 A가 semWait(lock) 을 실행하면 세마포어가 1로 초기화되어 있으므로 임계영역에 들어가고 0으로 변함.
- A가 임계영역에 있는 동안 semWait(lock) 을 호출한 B, C 는 블록됨
- A가 임예영역을 벗어날 때 semSignal(lock) 수행, 먼저 블록된 B가 깨어나 임계영역으로 들어감
* 임계영역이 아닌 정상적인 실행에서는 프로세스들이 병렬 처리되지만 임계영역에서는 직렬화됨
# 세마포어 변수의 값과 블록된 프로세스 개수와의 관계
- 임계영엑에 여러 개의 프로세스가 들어갈 수 있는 경우에도 상호배제 보장 가능
- 세마포어의 초기값을 임계영역에 동시에 진입하도록 허용하는 최대 프로세스의 개수로 설정 가능
- s.count ≥0 : s.count 는 현재 임계영역에 블록됨이 없이 진입할 수 있는 프로세스 개수
semSignal(s) 없으면 세마포어는 상호배제뿐만 아니라 동기화도 지원함
- s.count <0 : s.count 절대값은 s.queue에 블록되어 있는 프로세스의 개수
# 가정: 프로세스 A,B,C는 프로세스 D가 생산한 데이터를 소비 P236 (큐를 중심으로 표현)
- s=1이면 D가 생산한 데이터가 1개 존재하고
- s=-1이면 D가 데이터 를 생성하기를 기다리며 블록된 프로세스가 1개 존재한다는 의미
- D가 생산하고, A,B,C가 가져다가 씀 => A, B, C는 D의 수행 결과에 의존하여 수행됨
- A가 1이니까 하나 가져갈 수 있음
- s : D의 생성 결과가 존재하는가 여부
1. D가 생성한 데이터 하나 존재(s=1), 모든 프로세스 수행 가능
1. 프로세스 A가 스케줄링됨 => B, C, D는 수행 가능한 프로세스 큐에 연결됨, A는 수행 중
1. A는 D가 생성한 데이터를 소비하기 전에 semWait(s) 호출함 => s=0 (감소), A 실행 계속 가능
2. A는 수행 가능한 큐로 들어감, B가 스케줄링됨
2. B는 데이터 소비 전 semWait(s) 호출함 => s=0이므로 s값만 -1으로 변경, 수행 못하고 블록됨
3. D 스케줄링 됨 => 새로운 데이터 하나 생성, semSignal(s) 호출
4. s=0 (증가), 블록된 B를 수행 가능한 프로세스 큐로 들어감
5. C 스케줄링 됨 => 데이터 소비전에 semWait(s) 호출함 => s=-1 (감소), C 블록됨
6. A, B도 semWait(s) 호출하고 s 감소시키고 블록됨
6. D 수행되면서 새로운 데이터 하나 생성, semSignal(s) 호출함
7. s=-2 (증가), 블록되어있던 C 꺠어나 수행 가능한 프로세스 큐로 이동함
8. A, B도 블록에서 깨어남
'전공 공부 > 운영체제' 카테고리의 다른 글
| 운영체제 14주차 강의 (0) | 2021.06.01 |
|---|---|
| 운영체제 12주차 강의 (0) | 2021.05.18 |
| 운영체제 9주차 강의 (0) | 2021.04.27 |
| 운영체제 7주차 강의 (0) | 2021.04.13 |
| 운영체제 5주차 강의 (0) | 2021.04.04 |
