운영체제 9주차 (프로세스 동기화 개념, 임계 구역)

---

프로세스 동기화 (Synchronization)

• 병행 프로세스(동시에 실행되는 프로세스)들이 서로 데이터를 주고 받으면서 수행될 때, 이 프로세스들 간의 동기화가 필요함.
  • e.g. producer vs consumer problem
    • 두 개의 프로세스가 공유 메모리(버퍼)를 사용하여 데이터를 공유함.
    • 생산자 프로세스는 공유 메모리에 데이터를 생산
    • 소비자 프로세스는 공유 메모리의 데이터를 소비

    

    // 생산자 프로세스
    while(1) {
    	// produce an item and put in nextProduced.
    	while(counter == BUFFER_SIZE/*100*/) {
    		 // counter 값이 100이면 cannot produce
    		// do nothing
    	}
    	buffer[in] = nextProduced;
    	// in이 100개가 다 차면 다시 0부터(circular buffer)
    	in = (in + 1) % BUFFER_SIZE; 
    	
    	 // 임계 구역(critical-section)
    	counter++; // 생산자와 소비자가 counter라는 변수 공유
    }

    // 소비자 프로세스
    while(1) {
    	while(counter == 0) {
    		// 버퍼가 비어있기 때문에 소비 불가
    		// do nothing
    	}
    	nextConsumed = buffer[out];
    	out = (out + 1) % BUFFER_SIZE;
    	counter--; // 임계 구역(critical-section)
    	// consume the item in nextConsumed.
    }
    
    // 생산자 프로세스의 counter++; 과
    // 소비자 프로세스의 counter--; 는 동시에 실행되면 절대 안 된다.
    // 반드시 순서화해서 데이터의 일관성을 유지해야 한다.
    // transaction과 똑같다고 생각해라.

    

---

임계 구역(Critical-Section) 문제

• N개의 프로세스가 공유 데이터를 접근한다.

• 각 프로세스는 공유 데이터를 접근하는 코드 세그먼트를 갖고 있는데 이것을 임계 구역이라고 함.

• 임계 구역 문제
  • 임계 구역의 수행을 순서화해서 수행하도록 해야 함 (임계 구역은 시간적으로 상호 배타적임). 즉, 오직 한 프로세스만이 임계 구역을 수행하게 하자. (어떤 하나의 프로세스가

• 문제의 해결
  • 각 프로세스는 임계 구역의 코드를 수행하기 전에 허가를 요청해서 승인받고, 임계 구역을 마친 후에는 이를 알림
  • 진입 구역(entry section): 임계 구역 수행 전에 허가를 요청하는 코드 구역
  • 출구 구역(exit section): 임계 구역 다음에 위치하여 임계 구역 수행을 끝낸다는 것을 알리는 코드 구역

임계 구역 문제의 요구조건

1. 상호 배제(Mutual Exclusion): 프로세스 P_i가 임계 구역에서 실행된다면, 다른 프로세스들은 임계 구역에서 실행될 수 없다.

2. 진행(Progress): 임계 구역에서 실행되는 프로세스가 없고 임계 구역을 수행하려는 프로세스들이 있다면(허가를 요청하고 있는 상태), 임계 구역을 수행할 경우 다음 프로세스의 선택은 잔류 구역에 있지 않은 프로세스들 중에서 선택하되 무한하게 연기되지 않는다. 이게 무슨 말이냐면, 여러 개의 프로세스들이 임계 구역 코드를 수행하기 위해 신청 중인 경우 그 중 하나만 선택를 하기는 한다(여러 개의 프로세스들이 동시에 신청 중이라고 해도 연기하지 않는다)

3. 한계 대기(Bounded Waiting): 프로세스가 임계 구역의 수행에 대한 요청을 하고 요청이 허용될 때까지 다른 프로세스가 임계 구역을 수행하도록 허용하는 횟수에 한계를 두어야 한다. (예를 들어, 먼저 신청을 요청한 프로세스가 중간에 새로운 프로세스가 또 신청을 해서 계속 밀리지 않도록, 신청 횟수 제한, 즉 P1 프로세스는 언젠가 반드시 임계 구역에 접근이 가능하게끔..)

임계 구역 문제의 해결방법

1. 개발자가 직접 해결: 피터슨(Peterson) 알고리즘
   • 오직 두 프로세스만 사용할 수 있음
   • 두 프로세스는 다음 두 변수를 공유한다.
     • int turn;: 임계 구역에 어떤 프로세스가 들어갈 지를 나타냄.
     • bollean flag[2];: 프로세스가 임계 구역에 들어갈 준비가 되었는지를 나타냄. flag[i] == true이면 프로세스 P_i가 준비된 상태.

     // 프로세스 P_i의 알고리즘
     do {
     	flag[i] = TRUE; // entry section
     	turn = j; // entry section
     	while(flag[j] && turn == j); // entry section
     	counter++; // 임계 구역 코드 
     	flag[i] = FALSE; // exit section
     } while(TRUE);

2. 라이브러리 함수 또는 시스템 콜 호출: 세마포어(semaphore)
   • 세마포어 s(보통 변수 이름 s라고 함): 정수 변수로서 오직 두 개의 연산으로만 접근함.
   • 두 개의 연산
     • wait(S) or P(S): 임계 구역에 들어가기 전에 수행하는 연산
     • signal(S) or V(S): 임계 구역에서 나올 때 수행하는 연산

       wait(S) {
       	while(S <= 0) { ; } // S가 0이거나 0보다 작으면 대기. 아니면 S--
       	S--; // S값으로 임계 구역 코드가 실행되던 중 context change가
       	     // 발생하더라도 S<=0 이므로 다른 프로세스에서는 접근 못함. 
       }
       
       signal(S)
       { S++; }
       // 두 연산에서 세마포어 변수의 접근은 원자적(atomic)으로 수행된
       // (변수의 접근 도중에 인터럽트 되지 않는다.

     • binary semaphore: 세마포어 값을 오직 0과 1만 사용
       • 세마포어 초기값을 1로 init.
       • mutex locks(mutual exclusion) 라고 알려져 있음
     • counting semaphore: 제약이 없는 정수 값을 사용.
       • N개 프로세스의 병행 접근을 허용하고자 할 때.
       • 세마포어의 초기값을 N으로 함. 만약 N이 10이면 10개의 프로세스가 동시에 공유 자원에 접근할 수 있음. binary semaphore의 초기값은 1로 했던 이유도 한 개의 오직 한 개의 프로세스만 임계구역에 접근할 수 있다는 의미임. 그러나 일반적으로는 binary semaphore를 사용.
     • semaphore는 라이브러리 함수를 호출함으로써 편리하게 임계구역 문제를 해결할 수 있다는 장점이 있지만 교착상태 (두 개 이상의 프로세스들이 다른 프로세스가 해줘야 하는 일을 무한하게 기다리게 하는 현상) 가 발생할 수 있다. 세마포어를 1개만 사용할 때는 문제가 없으나 2개 이상의 세마포어를 사용할 떄 교착상태 발생!!

     

     만약 P_0의 wait(S)까지는 실행됐고 wait(Q)가 실행되어야 할 타이밍에 인터럽트가 발생해서 context switching이 발생하면, P_1의 wait(Q)가 실행되고 wait(S)가 수행될 때, S가 이미 P_0에 의해서 S가 0인 상태여서 더 이상 진행할 수가 없다. 그래서 다시 context switching 이 발생해서 다시 P_0으로 실행 흐름이 넘어갔다. 이제 P_1에는 wait(Q)를 실행해야 하는데 Q의 값이 이미 P_1에서 Q=0이어서 더 이상의 명령을 수행할 수 없다. 어라? 이건 좀 이상하다. P_0도 대기 P_1도 대기 이러면 무한 대기 상태 아닌가? 이것이 교착 상태(Dead Lock)이다. 위에서는 wait(S)와 wait(Q)의 순서를 바꿔서 코드를 작성했기 때문에 교착상태가 발생한 것이고, 순서를 맞춰준다면 위 두 프로세스에서는 교착상태가 발생하지 않는다.

3. 프로그래밍 언어에서 동기화 기법을 제공: 모니터(monitor)\
   • 동기화를 자동적으로 제공하기 위해서 새로운 언어구조 개발
   • 여러 프로세스들이 추상 데이터 타입(abstract data type)을 안전하고 효과적으로 공유할 수 있도록 한 기법.
   • 모니터 문법은 클래스 구문과 비슷
   • 클래스와 다른 점은, 한 번에 한 프로세스만이 모니터 안에서 수행될 수 있다는 것!!!

   monitor monitor-name {
   	shared variable declarations;
   	procedure(fun) P1(...) { ... } // 공유 변수에 접근하는 함수(프로시저) 1
   	procedure(fun) P2(...) { ... } // 공유 변수에 접근하는 함수(프로시저) 2
   	procedure(fun) initialization(...) {
   		e.g. count = 0 // 공유 변수 초기화 코드
   	} 
   }

   • 따라서, 프로그래머가 직접 동기화 제약을 코딩할 필요가 없다.

4. 기타: 하드웨어적인 지원: CPU 명령어들을 의미
   • Test-and-Set 명령어
   • 이런 명렁어는 원자적(atomic)으로 실행된다. 즉, 인터럽트되지 않고 하나의 단위로 실행됨.

   // Test-and-Set 명령의 정의
   
   boolean TestAndSet(boolean (target) {
   	boolean rv = *target;
   	*target = TRUE;
   	return rv;
   }
   
   do {
   	while(TestAndSet(&lock)) { // do something }
   	lock = FALSE;
   	// 잔류 구역
   } while(TRUE);

Uploaded by Notion2Tistory v1.1.0