[운영체제] 프로세스 동기화

독학사- 운영체제 편을 공부하고 정리한 내용입니다.

공유자원

• 공유 자원은 여러 프로세스 혹은 스레드가 공유하는 변수, 메모리, 파일 등을 말한다.
• 접근 순서에 따라 공유 자원에 대한 데이터가 올바르지 못한 결과가 생길 수 있다.

- 생산자 소비자 문제

 

공유 자원 접근 순서에 따라 결과가 달라지는 예로, 생산자 프로세스가 생산하는 정보를 소비자가 소비하는 형태이다.

생산자	소비자
while(true){          /* produce an item in next produced * /          while(counter == BUFFER_SIZE)                       /* do nothing */          buffer[in] = next produced          in = (in + 1) % BUFFER_SIZE;          counter++; }	while(true){          while(counter == 0)                    /* do nothing */          next consumed = beffer[out];          out = (out + 1) % BUFFER_SIZE;          counter--;        /* consume the item in next consumed */ }
현재 물건이 BUFFER_SIZE 만큼 있다면 생산하지 않고 대기한다. 그보다 적다면 다음 공간에 물건을 채운다. 공유 변수 counter를 증가시킨다.	현재 물건이 비어 있다면 소비하지 않고 대기한다. 물건이 하나라도 있다면 꺼낸다. 공유 변수 counter를 감소시킨다.

• 겉으로 보기에는 문제가 없는 두 프로세스가 생산-소비 기능을 수행하고 있다.
• 문제는 한 프로세스가 타임 아웃 등의 인터럽트로 실행 도중 중단되어 다른 프로세스가 실행될 때 발생한다.

- 기계어 레벨에서 counter++와 counter--의 동작 방식을 살펴보면 다음과 같다.

 

counter++	counter--
reg0 = counter // 대입 reg0 = reg0 + 1 // 증감 counter = reg0 // 대입	reg1 = counter // 대입 reg1 = counter 1 - 1; // 증감 counter = reg1

counter가 3일 때 만약 다음과 같이 counter++와 counter--가 동작하면,

 

1) reg0(3) = counter   //  생산자 프로세스

2) reg0(4) = reg0 + 1 

3) reg1(3) = counter  // 생산자 프로세스 타임아웃으로 소비자 프로세스 시작

4) reg1(2) = reg1 - 1

5) counter(4) = reg0  // 소비자 프로세스 타임아웃으로 생산자 프로세스 시작

6) counter(2) = reg1  // 소비자 프로세스

 

최종 결과로 counter에 2가 대입되는 것을 볼 수 있다. 하지만 실제 counter는 생산 소비 패턴 1번씩 수행했으므로 3을 가리켜야 한다.

• 이와 같이 2개이상의 프로세스가 공유 자원을 병행적으로 읽고 쓰는 상황을 "경쟁 조건" 이 발생했다고 한다.
• 또한 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램 영역을 "임계 구역"이라고 한다.
• 위의 예에서는 두 프로세스에서 counter를 증감하는 라인이 임계 구역이라 할 수 있다.

임계 구역 Critical Section

 

임계 영역이 포함된 프로세스의 구조는 다음과 같을 수 있다.

• 프로세스는 임계 영역을 진입하고 공유 자원에 대한 읽기/쓰기를 수행한다.
• 임계 영역을 빠져나온 후에는 공유 자원과 상관없는 남은 명령을 수행한다.

임계 구역 해결 조건

 

1) Mutual Exclusion 상호 배제

• 한 프로세스가 임계 구역에 진입하면 다른 프로세스는 임계 구역에 진입할 수 없다.
• 따라서 공유 자원에 대한 접근은 한 프로세스에 제한한다.

2) Bounded Waiting 한정 대기

• 어떤 프로세스도 무한 대기하지 않으며 임계 구역에 진입 가능해야 한다.

3) Progress Flexibility 진행의 융통성

• 아무도 공유 자원을 사용하지 않고 임계 영역을 접근하려는 프로세스가 있을 때, 다른 프로세스에 의해
• 진행이 방해되서는 안 된다.

임계 영역을 해결하기 위한 다양한 상호 배제 알고리즘이 있는데  소프트웨어로 혹은 하드웨어로 구현을 통해 해결 가능하다.

 

- 생산자 소비자 문제 해결을 위한 코드 1

	Pi	Pj
1 2 3 4 5 6	do{      while(turn != i);           critical section      turn = j;           remain section }while(1);	do{      while(turn != j);           critical section      turn = j;           remain section }while(1);
- 특징   while(turn != i); 코드로 자신이 차례가 아닐 경우 while 루프 순환으로 대기한다. (busy waiting)   각 프로세스는 임계 영역을 나온 후 상대방에게 차례를 넘겨준다. - 상호배제 O 2번 라인을 통해 임계 영역 접근은 한 프로세스만 가능하다. - 한정대기와 진행의 융통성 X   Pi가 4번 라인에서 Pj에게 차례를 넘겼다고 하자.   이때 Pi가 다시 임계 영역에 접근하려고 하고 자신의 차례가 아니기 때문에 대기하게 된다.   하지만 Pj는 임계 영역 진입의사가 없고 이에 따라 Pi는 무한히 대기하게 된다.   또한 이는 Pj에 의해 임계 영역 진입을 방해된 것으로 간주된다.

 

- 생산자 소비자 문제 해결을 위한 코드 2

	Pi	Pj
1 2 3 4 5 6 7	do{      flag[i] = true;      while(flag[j]);           critical section      flag[i] = false;           remain section }while(1);	do{      flag[j] = true;      while(flag[i]);           critical section      flag[j] = false;           remain section }while(1);
- 특징   flag라는 2칸짜리 배열을 통해 자신의 진입 의사를 나타낸다.   3번 라인에서 상대방의 의사가 있다면 대기한다. (busy waiting)   각 프로세스는 임계 영역을 나온 후 자신의 진입 의사를 없앤다. - 상호배제 O   3번 라인을 통해 임계 영역 접근은 한 프로세스만 가능하다. - 한정대기와 진행의 융통성 X   2번 라인에서 Pi가 flag[i]=true로 설정하고 타임 아웃되었다고 하자.   Pj는 2번 라인으로 flag[j]=true로 설정하고   두 프로세스는 3번에 의해 아무도 진입을 하지 못하고 무한 대기하게 된다.

 

- 생산자 소비자 문제 해결을 위한 코드 3

	Pi	Pj
1 2 3 4 5 6 7 8	do{      flag[i] = true;      turn = j;      while(flag[j] && turn == j);           critical section      flag[i] = false;           remain section }while(1);	do{      flag[j] = true;      turn = i;      while(flag[i] && turn == i);           critical section      flag[j] = false;           remain section }while(1);
- 특징   자신의 의사를 나타낸다.   turn이라는 공유 변수를 통해 먼저 상대방에게 차례를 넘겨준다.   4번 라인에서 상대방이 의사와 차례가 모두 있다면 대기한다. (busy waiting)   각 프로세스는 임계 영역을 나온 후 자신의 진입 의사를 없앤다. - 상호배제 O   turn이라는 변수는 i 또는 j 값만 가질 수 있으므로 한 프로세스만 진입 가능하다. - 한정대기와 진행의 융통성 O   2번 문제와 같이 Pi는 3번까지 실행되고 타임 아웃, Pj는 3번까지 실행되었다 하자.   turn = i으로 상대방에게 차례를 넘겨준 이후 Pi는 진입 의사와 차례가 모두 있기 때문에 Pj는 바쁜 대기를 한다.   Pj가 타임 아웃되고 Pi는 4번에서 turn == i이기 때문에 임계영역을 수행하고 자신의 의사를 없앤다.   Pj는 4번부터 다시 실행되고 flag[i]==false이기 때문에 임계영역을 수행하고 나오게 된다.

 

- 램 포트의 베이커리 알고리즘

두 프로세스 간 상호 배제를 위한 알고리즘 외에도 N개의 프로세스가 공유 자원을 사용하는 상황에서 문제를 해결할 수 있다.

	Pi = {P0, P1, ... , Pn-1}	특징
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19	/*  (a,b) < (c,d) : if a<c or a==c and b<d, it is true. */ 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]);          while(number[j] != 0 &&            (number[j], j) < (number[i], i) );      }           critical section      number[i] = 0;           remain section }while(1);	1) 번호표 받음 Pi는 번호표를 뽑는 의사를 설정하고 현재 뽑은 번호표의 다음 번호를 받고 의사를 없앤다. 2) 다른 프로세스를 검사 라인 12에서 다른 프로세스가 뽑는 중이라면 기다려 준다. 라인 13에서 Pi보다 먼저 왔거나 (number[i]<number[j]), j가 i 보다 우선순위가 높다면 (j<i) 다른 프로세스가 완료될 때까지 기다린다. 3) 번호표를 반환 다른 우선순위 프로세스가 작업이 완료되었다면 임계 영역 진입후 번호표를 반환한다. - 12라인에서 번호를 뽑고 있는 지 검사하는 이유 검사 유무와 상관없이 베이커리 알고리즘은 7 라인에서 실행 순서에 따라 두 프로세서 Pi와 Pj가 같은 번호를 뽑을 수 있다. 1) j<i으로 Pj가 우선순위가 높을때, 우선순위가 낮은 Pi에 먼저 선점되어 진행된다면, Pj는 아직 번호표를 뽑지 않았으므로 뽑는 중인 것을 무시하고 임계영역에 진입한다. 2) 반대로 Pj는 Pi는 우연히 같은 번호표를 뽑았고 j<i이기 때문에 또한 임계영역에 진입한다. 이는 상호 배제를 위반하게 된다.

 

- 하드웨어적 구현을 통한 문제 해결 (TestAndSet)

•  공유 변수를 수정하는 동안 인터럽트 발생을 억제한다면 임계 영역 문제를 간단히 풀 수 있지만 이는 항상 억제를 해야만 하는 것은 아니므로 실행 효율이 떨어진다.
• 이에 따라 하드웨어적으로 검사와 수정을 한 번에 수행하는 원자적 연산(ex. 1비트 값 수정)을 통해 문제를 해결한다.

TAS 명령어 구성

원자적 명령어 TAS	bool 변수 lock 설정
boolean TestAndSet (boolean *target) {   /* 메모리에서 target 값을 읽어 register에 대입 */   boolean temp = *target;   /* 동시에 target에 1을 쓰기 */   *target = true;   /* register값 temp 반환 */   return temp; }	do{ /* lock을 검사하여 true면 대기, false면 임계영역 진입 */   while(TestAndSet(&lock));            critical section   lock = false;            remain section }while(true);
TAS 명령어는 읽기/쓰기 그리고 반환 행위가 원자적 연산으로 수행되어 중간에 실행이 멈추는 것이 거의 불가능하다.	TAS를 통해 임계영역에 접근하는 프로세스는 lock이 false라면 가능하고 true면 대기하게 되므로 상호 배제 조건이 만족한다. 또한 사용 후 lock을 false로 설정하므로 다른 프로세스가 진입 가능하다.

• 메모리만 공유한다면 프로세스 수, 프로세서 수에 상관없이 모두 지원 가능하다.
• 구현이 단순하다.

- 바쁜 대기 문제 (Busy Waiting)

• 각 프로세스는 다른 프로세스가 공유 자원을 사용하고 있는지 루프를 돌며 체크하므로 CPU 소모가 크다.

세마포어 Semaphore

 

바쁜 대기를 사용하여 CPU 자원을 낭비하는 것을 방지하기 위해 운영체제의 기능을 사용해 동기화를 수행한다.

세마포어라는 객체를 통해 동기화를 위한 프로세스 관리를 할 수 있다.

 

- 세마포어 구조체 예시

typedef Semaphore

{

  int RS; // 공유 자원 수

  process* wait_list // 대기 중인 프로세스를 위한 세마포어 큐   

};

 

- 세마포어 동작 원리

세마포어 사용	Semaphore(n)	P(S)	V(S)
S = Semaphore(n) P(S);     critical section V(S);	// init with declaring n resources are available Semaphore S; S.RS = n; return S;	if S.RS > 0 then S.RS--; else {   add P to S.wait_list   block(); // sleep this thread }	S.RS++; P remove from S.wait_list; wake_up(P); // wake up one of the sleeping ones
P(S)와 V(S) 연산은 한번에 수행되어야 한다.	세마포어를 통해 사용할 수 있는 공유 자원의 수를 설정한다.	사용할 수 있는 자원이 있다면, 자원 수를 줄이고 임계 영역에 진입한다. block() : 만약 자원이 없다면, 현재 프로세스를 세마포어 큐에 대기시킨다.	wake_up(): 자원을 반납하고 세마포어 큐에 대기하고 있는 한 프로세스를 진입 가능하도록 꺼낸다.

• 이진 세마포어: 공유 자원 수가 1개 일 때 사용하는 세마포어로 mutex라고도 한다.
• 카운팅 세마포어: 공유 자원 수에 제한 없이 동기화 기능을 제공하는 세마포어

모니터 Monitor

 

공유 자원을 내부적으로 숨기고 공유 자원에 접근 가능한 인터페이스만 제공한다.

 

- 작동 원리

• 모든 프로세스는 순서대로 모니터가 제공하는 인터페이스를 통해 공유 자원에 대한 작업을 요청한다.
• 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 결과만 프로세스에 알려준다.