chapter05-2 세마포/교착상태

세마포

mutex 락보다 더 정교한 방식을 제공하는 동기화 도구

세마포 S - integer형 변수가 존재

wait() and signal() 두 원자적 연산에 의해서만 접근 가능

wait () operation의 정의

wait(S) {
			while (s <= 0)//while 문 실행 = critical section에 누가 실행되고 있다
				;// busy wait
			s--;
}

 

사용법

wait(semaphore *s){
	s->value--;
	if(s->value <0){ // 참 - 임계구역에 들어가있다.
	add this process to s->list;
	block();
	}
}

signal (semaphore *s){
	s->value++; // 땡하는 역할
	if(s->value <= 0){
		remove a process P from s->list;
		wakeup(P);
	}
}

• 이진 세마포
  • 0과 1값만을 가질 수 있는 integer형 변수
  • mutex lock과 같음
• 카운팅 세마포
  • 제한 없는 영역에 정의되는 integer형 변수

다양한 동기화 문제를 해결 할 수 있음 - 프로세스의 실행순서를 정하고 싶을때

 

바쁜 대기 없는 세마포 구현

바쁜 대기 대신 프로세스 자신을 봉쇄(블락한다.)

세마포를 기다리는 대기큐를 만드는것 - 프로세스를 대기 큐에 넣고, 상태를 대기 상태(waiting)로 전환

대기큐의 각 항목 : 값(interger 형), 리스트의 다음 레코드를 가리키는 포인터

두가지 연산 :

• block() - 연산을 호출한 프로세스를 적절한 대기 큐에 넣는다.
• wakeup() - 대기 큐의 프로세스 중 하나를 제거하여 준비 큐(레디큐)에 넣는다.

세마포 구현

세마포 대기큐는 FIFO(first in first out)큐로 구현 가능- 기다린 순서대로 실행

두 프로세스가 같은 세마포에 대해 동시에 wait()와 signal()을 호출할 수 없다는 것을 보장 - s값 때문에

• 구현시 wait와 signal 코드를 임계 구역에 두어야한다.
• 단일 처리 환경 - 비선점 방법
• 다중 처리기 환경 - 동기화 하드웨어 기법 적용

 

교착상태와 기아

교착 상태

: 둘 이상의 프로세스가 대기 중이고 이 중 하나만 발생시킬 수 있는 이벤트를 영원히 기다리는 상태

: P0과 P1도 둘다 어쩔줄모르고 더이상 앞으로 나아가지못하고 기다리는 상황

결과 : 무한 봉쇄 또는 기아(내가 원하는 자원을 얻지 못하고 계속 기다리기때문에)

-> 교착 상태는 기아상태를 야기하지만, 기아상태의 원인은 교착상태에만 있는 것은 아니다.

 

고전적인 동기화 문제

• 한정- 버퍼 문제 : 유한 버퍼, 공유 변수에 대한 동기화 문제공유하는 자료 구조
  • semaphore mutex = 1; // 버퍼 자체를 보호
  • semaphore empty = n; // 비어져있는 공간
  • semaphore full = 0; // 차있는 공간, 자체적으로 보호
• size = n인 버퍼

생산자 프로세스

do{
···
/*produce an item in next_produced*/
···
wait(empty);//empty = n-1 감소
wait(mutex);//
···
/*add next produced to the buffer-> 임계구역*/
···
signal(mutex);//
signal(full)://증가 empty와 페어로 움직임
}while(true)

 

소비자 프로세스의 구조

do{
wait(full);/
wait(mutex);//
···
/*remove an item from butter to next_consumed*/
···
signal(mutex);
signal(empty):
···
/*consume the item in next consumed*/
···
}while(true)

 

Readers and Writers Problem : 기록하는 자와 읽으려는 자의 문제

• 다수의 병행 프로세스가 하나의 데이터베이스를 공유
  • reader-동시에 읽을 순 있지만 쓰는 것은 안됨 only read, not write
  • writers - 쓸때 읽을 수 없음, read as well as write
• 동시에 여러 reader가 읽을 수 있다.
• writer는 한 순간에 오직 하나만 공유 데이터를 접근할 수 있다.
• 구성을 어떻게 하느냐에 따라 여러 변형이 가능하다.

문제

writer의 기아 발생 가능 → 우선순위를 부여하는 형태를 가짐으로서 write의 기아현상을 해결할 수도있다.

Semaphore mutex = 1; //read_count 갱신시, 상호배제 위해 사용

int read_count=0;  //현재 몇 개의 프로세스들이 객체를 읽고 있는가

semaphore rw_mutex=1; //writer들을 위한 상호배제 위해 사용

해결 - 공유데이터

writer가 공유 자원을 사용할 수 있는 허가를 얻지 못했다면, 어느 reader도 기다리게 할 수 없다.

즉 writer에게 접근 권한이 없다면 다른 reader들은 자원에 접근할 수 있다.

reader 프로세스의 구조

do{
		wait(mutex);
		read_count++;
		if(read_count == 1)//읽는 사람이 생겼다.
			wait(rw_mutex);//
		signal(mutex);
		···
		/*reading is performed*/
		···//임계구역
		wait(mutex);//
		read count--;
		if(read_count ==0)
			signal(rw_mutex);
		signal(mutex);//
}while(true)

writer 프로세스의 구조

do{
		wait(rw_mutex);//바쁜 대기
		···
		/*writing is performed*/
		···
		signal(rw_mutex);
}while(true)

식사하는 철학자 Problem

전제 조건 - 이웃 철학자와는 대화하지않으며, 배가 고프면 양쪽에 있는 2개의 젓가락을 동시에 집어 음식을 먹는다.

사색과 식사를 번갈아 하며 식사 후에는 2개를 동시에 내려 놓는다.

• 음식이 들어있는 그릇 : 데이터
• 젓가락 : semaphore chopstick[5] = {1};

 철학자 i 의 구조

do{
	wait(chopstick[i]);
	wait(chopStick[(i+1)%5])//각각(양쪽)의 젓가락 획득
	//eating-> 임계구역
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5]);//젓가락 내려놓음
	//thinking
}while(TRUE);

• 해결방법
  • 동시에 최대 4명의 철학자만 테이블에 앉을 수 있도록 허용→젓가락은 n+1개가 되도록
  • 철학자는 양 젓가락이 모두 가용할 때에만 젓가락을 집도록 허용(집기는 임계 구역에서만)
  • 비대칭 해결책 → 철학자들에게 서로다른 해결책 제시
  • 홀수 번호 철학자는 왼편의 젓가락을 먼저 집고 오른편 젓가락을 집고, 짝수 번호 철학자는 오른편 젓가락을 먼저 집고 왼편 젓가락을 나중에 집음
  교착 상태를 해결하는 것이 "기아"를 해결하는것은 아니다.

모니터

• 등장 배경
  • signal(mutex) ··· wait(mutex) → 상호 배제 조건 위반
  • wait(mutex) ··· wait(mutex) → 교착 상태 발생
  • wait(mutex)or signal(mutex)(or both)의 생략 ->상호 배제 조건 위반 및 교착상태
  순수한 프로그래밍의 오류 또는 비협조적인 개발자에 의해 발생: 프로세스 동기화를 위한 편리하고 효과적인 기법을 제공하는 고수준 동기화

모니터

: 프로세스 동기화를 위한 편리하고 효과적인 기법을 제공하는 고수준 동기화

공유자원 + 공유자원 접근 함수, 2개 큐

상호배제 큐 : 공유자원에 하나의 프로세스만 진입하기 위한 큐 →

조건동기 큐 : 이미 공유자원을 사용하고 있는 프로세스가 진입할 수 있는 큐 → 특정한 상황에 대기를 하거나 다시 공유자원을 사용할 수 있게 대기하는

→ wait(),notify(),notifyall()

 

 

 

자바 모니터 - 모니터를 제공하는 대표적 언어

 

다리 건너기 예제

통행은 한 방향으로만 가능, 다리의 각 섹션은 자원

해결책

• 교착상태가 일어나면 한 자동차가 후진하여 문제를 해결할 수 있음(자원 선점과 롤백)
• 교착상태가 일어나면 여러 자동차가 후진해야 할 수도 있음
• 대부분의 운영체제는 교착상태를 예방하거나 처리하지 않음

기아도 발생 가능

교착상태

교착상태 문제

각자 자원을 가지고 있으며 자신이 속한 집합의 다른 프로세스가 가지고 있는 자원의 획득을 기다리며 블록된 프로세스의 집합

→ 자원을 가지고 작업을 하면서도 다른곳에서 사용되고 있는 또 다른 자원을 필요로해서 획득하기 위해서 기다리는것

자원 사용 순서 : 요청 → 사용 → 방출

자원 요청과 방출은 시스템콜

• 장치 : request(),release()
• 파일 : open(),close()
• 메모리 : allocate(),free()

교착상태의 특성

다음 4가지 조건이 동시에 만족될 때 발생

1. 상호 배제 : 한 순간에 오직 하나의 프로세스만이 자원을 사용할 수 있음
2. 점유하며 대기 : 적어도 하나 이상의 자원을 가진 프로세스가 다른 프로세스가 가진 추가의 자원을 획득하기 위해 대기
3. 비선점 : 프로세스가 가진 자원은 오로지 사용이 끝난 후, 자발적으로만 방출
4. 순환대기 : (삼각관계)프로세스 집합이 존재할때 p0→p1기다림, p1→p2, … pn→p0을 기다리고있는 상황

자원활당 그래프

노드의 집합V와 간선의 집함 E.

V는 P ={} 시스템의 모든 프로세스로 구성된 집합

R ={} 시스템의 모든 자원으로 구성된 집합

요청간선 : 프로세스에서 리소스로 Pi→Rj

할당간선 : j라는 자원은 i라는 프로세스에 점유당했다. Rj→Pi

 

그래프 표현

 

 

요청간선 - 자원 큰 테두리에 해도 ok

할당간선

자원의 인스턴스가 여러개있을때에는 어디 인스턴스에서 출발하는지 꼭 표시해야함

 

 

 

 

 

교착상태가 아닌 이유 : P4는 누구를 요청하고 있지 않기 때문에 R2를 사용해서 release 해주면 p3가 사용할 수 있다. 사이클이 존재하지만 교착상태는 아니다.

 

 

 

 

 

 

 

교착상태를 핸들링 하는 방법들

• 시스템이 교착상태로 절대로 들어가지 않는다는것을 보장
  • 교착상태 예방
  • 교착 상태 회피
• 시스템이 교착상태가 되도록 허용하고 교착상태에서 정상 상태로 복구
• 문제를 무시하고 교착상태가 발생하지 않은 것처럼 행동 → UNIX를 포함한 대부분의 운영체제가 이 방법을 사용