Operating System - Multi-Programming - Mutual Exclusion

동기화

 공유되고 있는 변수를 사용해 한 프로세스가 작업을 하고 있을 때, 다른 프로세스가 사용하는 것을 막아주는 상호 배제의 한 방법이에요. 여기서 동시에 여러 프로세스가 한 자원에 접근해 조작할 때, 접근 순서에 따라 값이 변하는 상황이 Race condition이에요.

 

임계영역

 Race condition이 일어날 수 있는 코드/부분/영역이에요.

여기에는 다음의 조건이 필요한데 먼저, 임계 영역을 가지고 있는 프로세스가 여러 개 있을 때, 반드시 하나의 프로세스만 임계 영역에 들어갈 수 있어야 해요.

그리고 임계 영역이 아닌 곳에서 멈춘 프로세스는 다른 프로세스에게 영향을 줘선 안 되죠.

임계 영역에 접근하려는 프로세스는 교착 상태나 기아가 일어나지 않아야 하고 임계영역에 들어간 프로세스가 없을 때, 들어가려고 기다리는 프로세스는 그 즉시 들어갈 수 있어야 하며 거기에 CPU의 개수나 수행 속도에 의한 영향은 없어야 해요.

마지막으로 임계영역에 들어간 프로세스는 일정 시간 안에 나와야 해요.

프로세스 1	프로세스 2	...	프로세스 n
void P1{  while(true){   ...   entercritical(res);   -임 계 영 역-   exitcritical(res);   ...  } }	void P2{  while(true){   ...   entercritical(res);   -임 계 영 역-   exitcritical(res);   ...  } }	void P...{  while(true){   ...   entercritical(res);   -임 계 영 역-   exitcritical(res);   ...  } }	void Pn{  while(true){   ...   entercritical(res);   -임 계 영 역-   exitcritical(res);   ...  } }
상호 배제를 보장하기위해 entercritical-exitcritical(enterysection-exitsection)이라는 함수가 제공되는데 각각 인자는 공유 자원의 이름을 사용해요.

1: parbegin 2:  statement_1; 3:  statement_2; ... n+1:  statement_n; n+2: parend	statment_1~n의 경우 싱글 프로세서 시스템에서는  각 문장의 수행 순서를 임의대로 실행해도 돼요. 멀티 프로세서 시스템에서는  각 문장을 병렬로 실행해요.
하나의 프로세스가 여러 병렬 프로세스로 퍼졌다가 다시 하나로 뭉쳐지는 것을 나타내는 parbegin/parend의 구조이에요. 더 효과적인 병행을 위해 statement_0와 작업이 끝난 후에만 실행가능한 statement_n+1을 추가 시킬 수도 있어요.

 

인터럽트 금지

 프로세스의 계속적인 실행을 보장하기 위해 프로세스가 인터럽트 당하지 않도록 해요.

그러나 멀티 프로세서 시스템에서는 인터럽트가 금지되더라도 다른 CPU가 수행하고 있는 프로세스에서 공유 자원에 접근할 수 있어서 상호 배제를 보장할 수 없어요.

 

하드웨어 명령어

boolean test_and_set(boolean &target){  boolean rv = target; target = true; return rv; } const int n = number_of_processes; boolean lock; void P(int i){  while(1){   while(test_and_set(lock));   -임 계 영 역-   lock = false;   ...  } } void main(){lock = false; perbegin(P(1),P(2),...,P(n));}

void exchange(boolean &r, boolean &m){  boolean temp = r; r = m; m = temp; } const int n = number_of_processes boolean lock; void P(int i){  while(true){   key = true; do exchange(key, lock) while(key);   -임 계 영 역-   lock = false;   ...  } } void main(){lock = false; perbegin(P(1),P(2),...,P(n));}

장점

• 싱글 프로세서 시스템과 멀티 프로세서 시스템 둘 다 사용 가능해요.
• 서로 다른 변수를 사용하면 여러 개의 임계 영역을 지원할 수 있어요.
• 간단해서 검증이 쉬워요.

단점

• 임계 영역에 들어가려는 프로세스는 그 영역이 비어있는지 체크하기 위해 CPU를 계속 사용해요. 즉, 바쁜 대기를 사용해요.
• 대기하던 프로세스 중 하나만 들어갈 수 있는데 이 때 프로세스의 특성이나 대기 시간을 고려하지 않아서 기아가 발생할 수 있어요.
• P1이 임계 영역에 들어가고 난 후 우선순위가 높은 P2가 생성되어 스케줄링이 되었을 때, 그리고 P2가 P1과 같은 자원을 사용하려고 하면 상호 배제 조건에 의해 접근에 실패하고 바쁜 대기를 수행해요. 그러나 P1은 우선순위가 높은 P2가 실행 또는 실행 가능 상태에 있어서 다시 스케줄링될 수 없어서 교착상태에 빠질 수 있어요.

 

Semaphore(세마포어)

 프로그래밍 언어와 운영체제 수준에서 병행성을 위해 제공되는 기법이에요. 프로세스 사이에 신호를 주고받기 위해 사용되는 정수 값인데 이 변수는 0과 1만 갖는 이진 세마포어, 음이 아닌 정수를 가질 수 있는 계수計数(정수) 세마포어가 있어요. 여기서 이진 세마포어는 mutex과 관련 있어요.

 

MUTual EXclusion lock

 객체를 얻거나 반납할 때 사용하는 프로그래밍 플래그이에요. 데이터가 공유될 수 없거나 연산이 동시에 수행될 수 없을 때, mutex가 설정되고 접근을 시도한 프로세스가 블록 되어요. 데이터에의 접근이 필요 없어지거나 연산이 완료되면 mutex의 lock은 해제되죠.

이 lock은 lock을 설정한 프로세스만이 해제할 수 있지만 이진 세마포어는 lock을 설정한 프로세스와 해제하는 프로세스가 다를 수 있어요.

 

세마포어를 위한 특수한 명령은 비분리 명령(각각 분리되지 않고 수행될 수 있도록 구현한 명령)으로 세마포어 초기화, semWait, semSignal 세 가지 원자적인 연산(단 하나만 연산하는 것, 이로 인해 누구의 방해를 받지 않고 하나의 연산을 수행해요.)만을 지원해요.

 

세마포어 초기화

세마포어가 음이 아닌 값으로 초기화되어요.

semWait 연산

if(S > 0) S -= 1;

else 프로세스 블록(큐에서 대기)

semSignal 연산
if(큐에서 대기 중인 프로세스가 존재) 그중에 한 프로세스를 (준비 || 실행) 상태로 바꿈

else S += 1;

 

이때, FIFO 방식으로 깨우는 세마포어가 String semaphore(강성 세마포어)이고 깨우는 방식이 명시되지 않은 세마포어가 Weak semaphore(약성 세마포어)이에요.

const int n = number_of_processes; semaphore s = 1; void P(int i){  while(true){   semWait(s);   -임 계 영 역-   semSignal(s);   ...  } } void main(){perbegin(P(1),P(2),...,P(n));}

세마포어를 활용하면 상호 배제와 서로 인식하고 실행하는데 보조를 맞추는 프로세스 사이의 동기화도 쉽게 구현할 수 있어요. 예를 들어 P0가 실행 중에 P1이 건네는 데이터를 받아야 진행될 수 있을 때, 둘 사이에 sync라는 이진 세마포어를 설정해 P0가 데이터 수신 확인을 semWait(sync)로, P1은 P0에게 데이터를 보내면서 semSignal(sync)를 실행하면 되죠.

 

모니터

위의 세마포어는 매우 오래된 동기화 도구예요. 현재는 모니터라는 동기화 도구를 사용하는데 이는 좀 더 수준 높은(언어적으로) 동기화 기능을 제공해요. 프로그래밍 언어 수준에서 제공하는 모듈인데 이는 사용이 쉽고 Deadlock 등의 에러가 발생할 가능성이 낮아요.

Entry Queue

모니터 내의 프로시저(리턴 값이 없는 함수) 수만큼 존재해요.

Mutual Exclusion

모니터 안에는 하나의 프로세스만 진입 가능해요.

Information Hiding

공유 자원은 모니터 내의 프로세스만 접근 가능해요.

Condition Queue

모니터 안에서 어떤 이벤트가 일어나길 기다리는 프로세스가 대기하는 곳이에요.

Signaler Queue

모니터에는 항상 하나의 신호 제공자 큐가 존재하는데 signal() 명령을 실행한 프로세스가 임시로 대기하는 곳이에요.

 

아래는 모니터로 해결할 수 있는 문제들이에요.

 

자원 할당

monitor resourceRiAllocator; boolean R_Available; condition R_Free; //조건 큐 생성 procedure requestR(){  if(R_Available != true) R_Free.wait()  else R_Available = false; } procedure releaseR(){  R_Available = true;  R_Free.signal(); } R_Available = true; //모니터가 생성될 때 설정

위는 간단한 모니터를 이용한 자원 할당 시나리오인데 requestR()과 releaseR()은 각각 공유 자원을 요청하고 반환하는 프로시저이며 이 프로시저를 통해서만 R_Available이라는 공유 자원을 위한 변수에 접근할 수 있어요. 마지막쯤의 잔업 같은 경우 공유 자원이 하나 더 있을 때를 생각하면 이해하기 쉬워요.

 

 

Producer-Consumer(생산자-소비자)

monitor ringbuffer; msg buffer[n]; int in, out, validBuf; //in: 생산자가 데이터를 넣을 곳 out: 소비자가 데이터를 뺄 곳 validBuf: 버퍼에 있는 데이터의 개수 condition bufHasData, bufHasSpace; procedure fillBuf(msg data){ //생산자가 데이터를 만들어 진입하려고 하는 경우  if(validBufs == n) bufHasSpace.wait(); //여유 공간이 없을 때  buffer[in] = data; //여유 공간이 있을 경우에 데이터를 생성  validBufs += 1;  in = (in + 1) % n;  bufHasData.signal(); //생산자가 대기하고 있으면 깨우기 } procedure emptyBuf(msg data){  if(validBufs == 0) bufHasData.with(); //만들어 놓은 것이 없을 때  data = buffer[out]; //데이터를 소모  validBufs -= 1;  out = (out + 1) % n;  bufHasSpace.signal(); //기다리고 있는 소비자가 있으면 깨우기 } validBufs = in = out = 0;

 

Reader-Writer(독자와 작가)

monitor readers_and_wirters; int numReaders; boolean writing; condition readingAllowed, writingAllowed; procedure beginReading{  if(writing || queue(writingAllowed)) readingAllowed.wait();  numReaders += 1;  if(queue(readingAllowed)) readingAllowed.signal(); } procedure finishReading{  numReaders -= 1;  if(numReaders == 0) writingAllowed.signal(); } procedure beginWriting{  if(numReaders > 0 || writing) writingAllowed.wait();  writing = true; } procedure finishWriting{  writing = false;  if(queue(readingAllowed)) readingAllowed.signal();  else writingAllowed.signal(); } numReaders = writing = 0;

 

Dining Philosopher(식사하는 철학자)

do{  pickup(pn);  eating;  putdown(pn);  thinking; }while(forever)

monitor dining_philosophers; int numForks[5]; condition ready[5]; int i; procedure pickup(int me){  if(numForks[me] != 2) ready[me].wait(();  else{   numForks[right(me)] = numForks[right(me)] - 1;   numForks[left(me)] = numForks[left(me)] - 1;  } } procedure putdown(int me){  numForks[right(me)] = numForks[right(me)] + 1;  numForks[left(me)] = numForks[left(me)] + 1;  if(numForks[right(me)] = 2) ready[right(me)].signal();  if(numForks[left(me) = 2) ready[left(me)].signal(); } for(int i = 0; i < 5; i++) numForks[i] = 2;