chapter05. 프로세스 / 임계구역 /

배경

프로세스는 병행 또는 병렬도 실행

→ 언제든지 실행 중 인터럽트 당할 수 있고 부분적으로 완료될 수 있다. : 데이터의 비일관성

문제 상황

• 협력적인 순차적 프로세스(논리적인 공유공간 ) 또는 스레드로 구성된 시스템
• 비동기적으로 수행하면서 데이터 공유※ 비동기적 실행 : 생산자가 생산할때마다 공유공간에 던짐, 소비자가 필요할때 꺼냄→ 문제 : 공간이 꽉참
• ※ 동기적 실행 : A가 B에게 데이터를 줄 것이 있을때 B는 기다리고있다가 받고 실행, 모든 일의 순서가 주고받음이 명확 → 비효율적

Producer

//in → 프로듀서 생산자가 다음에 채울 공간을 체크 
//out → 어디서부터 뺄지 체크

while (true){ 
/produce an item in next produced / 
while (((in+1) % BUFFER SIZE)== out);// 내가 넣을려고 하는 다음 칸이 버퍼사이즈를 모듈레이션한 값이 아웃일경우 -> 버퍼가 꽉찼다를 의미 
/ do nothing///넣을 공간이 없다면 아무것도 하지 않음 
buffer[in] = next_produced; in = (in + 1)% BUFFER_SIZE; 
}

Consumer

//in → 프로듀서 생산자가 다음에 채울 공간을 체크 
//out → 어디서부터 뺄지 체크

while (true){
while (in== out);// 버퍼가 비어있다.
/* do nothing*///비었다면 아무것도 하지 않음 
next_consumed = buffer[out];//버퍼에 아웃위치에있는것은 next conumer로 보냄
out = (out + 1) % BUFFER_SIZE;//다음번에 꺼내갈 아이를 증가 
}

→ 문제 동기화를 위해 (BUFFERSIZE-1)개 까지만 버퍼 사용

 

                                                                               couter 추가 후

경쟁 상황

counter++ → register1 = counter

             register1 = register1 + 1 

        counter = register1

counter라는 변수는 메모리 공간 안에 있다.

이 값을 1증가하기위해서 메모리에 있는 값을 cpu내부 레지스터에 옮겨놓고 register값을 산술연산을 통해 1을 증가

→ 증가된 값을 다시 메모리에 저장

생산자와 소비자는 하나의 독립적인 프로세스이다.

cpu입장에서 3단계가 다 실행되지못한 상태에서 타임아웃등으로 cpu를 빠져나오는 상황 발생

→ counter는 생산자와 소비자가 서로 사용할 수 있는 공유 변수이기때문에 경쟁을 하다보니까 일관되지않은 데이터의 사용이 나타난다.

 

임계구역

공유 변수 조작, 테이블 갱신, 파일쓰기 등과 같은 작업 수행

동기화 문제를 일으킬 수 있는 영역

문제

n개의 프로세스마다 코드 중에 임계 구역 세그먼트를 가진다.

임계 구역에 하나의 프로세스가 존재하면 다른 프로세스들은 임계 구역에 절대 진입할 수 없다.

각 프로세스는 진입구역 : 임계 구역에 집입하기 위해서는 허가를 요청, 퇴출구역 : 비었다는 표시를 하는 것, 나머지 구역 : 임계구역 외의 자기의 업무,의 코드 영역

임계구역문제의 해결책의 요구 조건

1. 상호 배제
2. n개의 프로세스 중에 단 하나라도 자기 자신의 코드중 임계구역에 들어가서 작업중이라면 그 하나 이외의 프로세스는 자신의 임계구역에 들어갈 차례임에도 기다려야한다. 단 하나만 들어갈 수 있다.
3. 진행세개 중 하나는 반드시 들어가야한다.
4. 세개가 동시에 임계구역에 들어가고자할때, 지연 없이 그중 하나를 선택
5. 한정된 대기Peterson's solution(피터슨의 솔루션)두 프로세스는 두 변수를 공유Boolean flag[2] // 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 나타냄
6. int turn; // 어느 프로세스가 임계 구역에 진입할 차례인지 나타냄
7. 고전적인 소프트웨어 기반 해결책
8. 세개의 프로세스가 임계구역에 들어가고자 경쟁하고 그중 하나가 선택되어 임계 구역에 들어가있는동안 추가 지원자가 발생하는 경우 처음부터 임계 구역에 진입하려고 요청하는 프로세스에게 몇번째 내에 들어갈 수 있다는 것을 보장해줘야한다.

Process pj

do { flag[j] = true;
turn = i;
while (flag[i]&&turn==i);

flag[j]=false;

동기화 하드웨어

이후 설명하는 모든 해결책은 락킹(locking)이라는 아이디어에 기반

단일 처리기 환경에서는

• 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음 → cpu가 아예 인터럽트를 못걸게함
• 비선점형 커널
• 다중처리기 시스템에서는 적용 불가

현대 기기는 특별한 원자적 하드웨어 명령을 제공

※ 원자적(atomic) = 인터럽트 될 수 없는

 

test_and_set 명령어

boolean test_and_set (boolean *target)
{
		boolean rv = *target;
		*target = TRUE;
		return rv:
}

1. 원자적으로 실행된다.
2. 전달된 매개변수의 현재 값을 반환한다.
3. 변환된 매개변수의 새 값을 "TRUE"로 세팅한다.

do {
		while (test_and_set(&lock));// lock을 세팅하는 방법
		/* do nothing*/

			/*critical section*/

		lock = false; //  lock을 해제하는 방법
	 		/* remainder section*/
}while (true);

 

 

compare_and_swap를 사용한 구현

do {
			while (compare_and_swap(&lock,0,1)!=0);//lock을 획득하는 부분
		/* do nothing*/

			/*critical section*/
		lock = 0;   //lock을 내보내는 
 		/* remainder section*/
}while (true);

 

 

 

 

한정대기를 만족시키는 구현(with test_and_set)

do{
waiting[1] = true;
key = true;
	while (waitingp[i] && key) 
			key = test_and_set(&lock);//계속 실행되는구간
		waiting[i] = false;
/*critical section*/
j = (i+1)$n;
while((j!=1) && !waiting[i])
	j = (j + 1) % n;
if (j==1)
	lock = false;
else
	waitihg[j]= false;
/*remainder section*/
}while (true)

i=p3일때 waiting = false가 되면서 while문을 탈출하게됨

waiting = false 로 바꾸고 critical section에 들어감

 

Mutex 락

이전의 피터슨 하드웨어와 동기화 경우 개발자에게 알려져있지 않은 부분이다.

os 설계자들이 임계 구역 문제를 해결하기 위한 소프트웨어 툴 설게 → mutex 락

• 먼저 락을 얻고, 임계구역, 락을 해제하여 임계 구역을 보호
• acquire() 및 release()호출은 원자적
• 문제점 : 바쁜 대기(busy waiting)
  • 임계구역에 들어가기위해서 엔트리 섹션부분을 계속 실행 : 스핀락
  • 동기화 하드웨어도 동일한 문제 → CPU 낭비

acquire() and release()

acquire(){
	while (!availavle);//다른 누군가가 임계구역에 있다. 기다려라
		/*busy wait*/
	available = false;;// 내가 획득함(다른사람 못들어옴)
}

release() {
			avilable = true;
}

do {
		acquire lock
			critical section
		release lock
			remainder section
} while (true);