Chapter 5: 병행 프로세스와 동기화

5.1 병행 프로세스

• 병행(concurrent): 메모리에 다수의 프로세스가 같이 존재한다는 것
  • 처리기(CPU)의 개수 상관 X
  • 논리적 concurrent - 단일 처리 (실제로는 parallel 아님)
  • 물리적 concurrent - 다중 처리(진정한 parallel)

 

• 병렬(Parallel): 다중처리 시스템의 경우 여러개의 프로세스가 동시에 병렬로 실행
  • 병행(concurrent)전제

 

💡 병행 프로세스 사이의 비동기적(Asynchronous)
다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 전혀 모름. 독립적이다.

 

• 병행 프로세스 사이의 Rule: 공유된 자원에 대해 한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장

 

5.2 상호배제

• 경쟁 상태(Race Condition): 프로세스들이 공유데이터에 서로 접근을 시도하는 상황
  • 상호배제(Mutual Exclusion): 한 번에 하나의 프로세스만이 임계영역에 들어가야 함
  • 교착상태(Deadlock): 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태
    • 라이브락(Livelock): 두 프로세스의 속도가 고묘히 맞물렸을 때 둘 다 임계영역에 진입하지 못하는 현상
  • 기아(Starvation)
    
    

• 임계영역(Critical Section): 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원에 접근하는 코드 부분
  임계영역 앞뒤에 적절하게 코딩을 하면 상호배제 성공
  • enter primitive: 임계영역 앞
  • exit primitive: 임계영역 뒤

 

5.3 상호배제를 위한 소프트웨어 기법들

• parbegin/ parend ⇒ parallel begin parallel end
  • 단일 처리: 각 문장의 수행 순서를 임의로 진행(순서가 상관 없음)
  • 다중 처리: 각 문장을 병렬로 실행
    
    
• 미완성 시도
  • 첫 번째 시도
    • 임계 영역의 첫번째 진입의 고정 (임계영역이 비어있을 때 진입을 원하는 프로세스를 방해해서는 안된다는 원칙을 어김)
    • 번갈아가며 진입이 가능 (누구든 연속해서 두번이상 진입할 수 없다)
    • 실행속도가 느린 프로세스의 속도에 의존적임
  • 두 번째 시도
    • while문과 flag문 사이에 들어가면 둘다 critical section에 접근 가능 (상호배제 어김)
  • 세 번째 시도
    • while문과 flag문 사이에 들어가면 둘다 critical section에 접근 못함 (상호배제 어김)
• 성공적인 기법
  • Petorson의 알고리즘: 프로세스 2개 사이의 해결

void P0() {
	while (true) { 
		flag[0] = true;
		turn = 1;
		while (flag[1] && turn == 1); 
		<critical section>
		flag[0] = false;
		<remainder>
	}
}

• Bakery 알고리즘(Lamport의 알고리즘): n개의 프로세스 사이의 해결

do {
	choosing[i] = true;
	number[i] = max(number[0], number[1], ..., number[n-1])+1;
	// 넘버 값을 순서대로 부여
	choosing[i] = false;
	for (j=0;j<n;j++) {
		while(choosing[j]); //true면 num받는 중, false면 num받았거나 시도X
		while((number[j]!=0) && ((number[j],j) < (number[i],i));
		//j가 끝나지 않았고, j가 i보다 작으면 busy waiting
		<critical section> // num[j]가 0이거나 j가 크면 접근가능
		number[i]=0; //들어간 사람만 들어가는 것을 방지하기 위해서
    // -> exit primitive
		<remainder>;
} while(1);

• 번호 값에 의해 차례가 결정되므로 특정 프로세스의 무한대기는 걱정하지 않아도 된다.
• 그러나 busy wait로 낭비가능성있다.

 

5.4 상호배제를 위한 하드웨어 기법들

• 인터럽트 금지를 사용한 기법
  • 인터럽트를 임계영역의 실행을 완료할 때까지 발생하지 않도록 한다
  • 단점
    1. 시스템의 효율적인 운영을 방해하기 쉽다
    2. 다중처리 시스템에서 다른 처리기에서 실행되는 프로세스로부터의 접근가능성
• 하드웨어 명령어를 사용한 기법
  • tetandset 명령어

  boolean testandset(boolean &target) {
  	boolean rv =  target;
  	target = true; //setting
  	return rv;
  }
  

  • exchange 명령어

  void exchange(boolean &r, boolean &m) {
  	boolean temp = r;
  	r = m;
  	m = temp;
  }
  

• testandset과 exchange를 사용한 상호배제

 

5.5 세마포어

• 세마포어(semaphore): 세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수
• P 명령
• V 명령
• 세마포어를 사용해서 해결할 수 있는 문제들
  • mutual exclusion(상호배제)
  • 공유자원의 풀(Pool)관리
  • syncronization(동기화)

 

5.6 생산자-소비자 문제

• 무한 버퍼용 알고리즘의 경우

 

5.7 Eventcount 와 Sequencer을 사용한 기법

• Eventcount/ Sequencer: 특별한 명령들에 의해서만 접근이 가능한 정수형 변수
  • ticket(s)
  • read(E)
  • advance(E)
  • await(E,v)
• 임계영역의 진입을 시도하는 프로세스들에게 순번 표를 부여함으로써 기다린 순서대로 처리되게 하여 기아를 방지한다.

 

5.8 모니터

• 모니터(monitor): 공유데이터들과 이들에 대한 임계영역들을 관리하는 소프트웨어 구성체
  모니터 내의 변수들은 프로시저들을 통해서만 접근이 가능
  • 진입은 프로시저의 호출로 가능// 진입큐의 개수는 모니터 안의 프로시저의 수
  • 호출될 프로시저 개수만큼 대기큐 있어야함
  • 조건큐도 조건의 개수만큼 있어야함
  • 신호자 대기 큐 있어야함

 

• 상호배제(mutual exclusion)지키기
  모니터의 진입을 한 프로세스로 제한함으로 한번에 하나의 프로세스만이 모니터 내에 있게함

 

• 스풀링(Spooling)
  • spooler: 보조기억장치에 빠른 속도로 출력을 하는 일반적인 프로세스
  • de-spooler: 디스크에 임시로 출력된 내용을 실제로 프린터로 출력하는 프로세스

 

Dinning Philosopher

• 한번에 포크를 두개 집으면 교착상태가 된다.