05. 상호배제와 동기화 [1/2]

상호배제와 동기화

상호배제의 개념

• 병행 프로세스에서 프로세스 하나가 공유 자원 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법

• 읽기 연산은 공유 데이터에 동시에 접근해도 문제 발생하지 않음.

동기화

• 변수나 파일은 프로세스별로 하나씩 차례로 읽거나 쓰도록 해야 하는데, 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 기법
  • 동기화는 순차적으로 재사용 가능한 자원을 공유하려고 상호작용하는 프로세스 사이에서 나타남
  • 동기화로 상호배제 보장할 수 있지만, 이 과정에서 교착 상태와 기아 상태가 발생할 수 있음

병행 프로세스 간 상호작용

프로세스는 아래 세 가지 형태로 상호작용 함.

• 프로세스들이 서로 인식하지 못하는 경쟁관계 유지.
  • 다중 프로그래밍 환경에서 운영체제는 자원에 대한 경쟁을 고려, 동일한 디스크나 프린터로의 접근 조절.
  • 프로세스들은 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로의 관계를 인식함.
    • 프로세스들은 공동 개체를 공유하는데 따른 협력이 필요함.
  • 프로세스들은 서로를 인식하고 프로세스끼리 통신할 수 있는 기본 함수를 가짐.
    • 프로세스들이 협력관계일 때, 프로세스 간 직접 통신이 가능, 병행해서 함께 동작할 수 있음.

상호배제의 조건

1. 두 프로세스는 동시에 공유 자원에 진입 불가
2. 프포세스의 속도나 프로세서 수에 영향을 받지 않음
3. 공유 자원을 사용하는 프로세스만 다른 프로세스 차단 가능
4. 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 됨

생산자/소비자 프로세스

• 생산자/소비자, 판독자/기록자(입력기/출력기) 문제
  • 여러 프로세스가 공통 작업 수행을 위해 서로 협동하고, 병행 처리되는 대표적인 예.
  • 상호배제와 동기화가 필요하며 세마포어를 이용해 구현.
  • 운영체제에서 비동기적으로 수행하는 모델로 생산자 프로세스는 소비자 프로세스가 소비하는 정보를 생산.

생산자와 소비자의 공유 버퍼

• 생산자와 소비자 프로세서들을 병행 실행하기 위해 공유 버퍼가 필요함
  • 생산자의 데이터 생산 속도와 소비자의 데이터 소비 속도는 서로 독립적이므로 버퍼가 필요함
    • 생산자와 소비자는 같은 버퍼에 접근하므로 동시에 사용할 수 없음.
• 생산자는 버퍼가 꽉 차면 더 이상 생산 불가, 소비자는 버퍼가 비면 데이터 소비 불가 >> 문제 발생
• 생산자와 소비자의 공유 버퍼의 상태
  

  

무한 버퍼 생산자/소비자 문제

• 버퍼의 크기에 제한을 두지 않으며 항상 버퍼에 빈자리가 존재함

유한 버퍼 생산자/소비자 문제

• 크기가 고정된 버퍼를 사용
  • 버퍼가 비었을 시 소비자가 대기
  • 버퍼가 가득 차면 생산자가 대기
• 공유 버퍼의 저장소를 두개의 논리적 포인터 in과 out을 사용한 순한 배열을 사용하여 해결 가능
  • in과 out은 0으로 초기화.
  • 변수 in은 비어있는 다음 버퍼를 가리킴.
  • 변수 out은 채워진 버퍼의 맨 처음을 가리킴.
  • 소비자는 버퍼에서 데이터를 읽기 전 생산자가 앞서 가는 지, 즉 in > out 인지 확인함.

유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램

1. 공유 데이터의 선언

   #define BUFFER_SIZE 10 //버퍼 크기
   typedef struct{
      DATA data;
   } item;
   item buffer[BUFFER_SIZE];
   int in = 0;
   int out = 0;
   int counter = 0;

2. 생산자와 소비자 프로세스

   생산자 프로세스는 생산하는 새로운 원소를 지역변수 nextProduced에 저장, 소비자 프로세스는 소비하는 원소를 지역변수 nextConsumed에 저장 각 프로세스 구현

   생산자 프로세스

   item nextProduced;
   
   while(true){
       //버퍼가 가득 차 아무 일도 하지 않음
       while(counter == BUFFER_SIZE);
       buffer[in] = nextProduced;
       in = (in + 1) % BUFFER_SIZE;
       counter++;
   }
   

   소비자 프로세스

   item nextConsumed;
   
   while(true){
       //버퍼가 가득 차 아무 일도 하지 않음
       while(counter == 0);
       nextConsumed = buffer[out];
       out = (out + 1) % BUFFER_SIZE;
       counter--;
   }
   

3. counter++와 counter-- 기계어

   두 코드의 동시 수행시 counter 값이 맞는기 기계어로 작성 확인

   count++ 기계어

   rigister1 = counter;
   register1 = register1 + 1;
   counter = register1;
   

   count-- 기계어

   rigister2 = counter;
   register2 = register1 - 1;
   counter = register2;
   

   실행 예

   T1 : 생산자가 register1 := counter를 수행 (register1 = 5)
   T2 : 생산자가 register1 := counter1 + 1을 수행 (register2 = 6)
   T3 : 소비자가 register2 := counter를 수행 (register2 = 5)
   T4 : 소비자가 register2 := register2 – 1을 수행 (register2 = 4)
   T5 : 생산자가 counter := register1을 수행 (counter = 6)
   T6 : 소비자가 counter := register2를 수행 (counter = 4)

경쟁 상태(Race Condition)

• 공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황을 의미
• 여러 프로세스가 공유 데이터를 동시에(병행적으로) 접근(읽기나 쓰기)할 때 공유 데이터에 대한 접근 순서에 따라 실행 결과가 달라지는 상황
• 장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세서가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생하는 오류 발생하므로 적절한 순서에 따라 수행 해야 함
  • 접근 순서화가 필요
  • 병행 프로세서들은 반드시 동기화되어 실행되어야 함.

경쟁 상태의 예방(동기화 실행 방법)

임계 구역

• 공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 함.

상호 배제

• 위의 예에서 counter를 조작하는 부분을 임계구역으로 설정, 상호 배제 함.

임계 영역(Critical Section)

둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하며, 프로그램에서 이를 이용하는 부분.

• 공유 메모리가 참조되는 프로그램의 부분(데이터나 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역(공유 자원의 독점을 보장하는 코드 영역)을 의미.
• 프로세스들이 공유 데이터를 통해 협력 시, 한 프로세스가 임계영역에 들어가면 다른 모든 프로세스는 임계영역으로의 진입 금지.
• 다중 처리 시스템과 단일 처리 시스템(시분할)환경에 적용되는 하나의 실행단위, 실행 구간을 의미.
  • 임계영역 내에서 빠른 속도로 작업을 수행, 한 프로세스가 오랫동안 머무르면 안됨.
  • 프로세스가 무한 루프 등에 빠지지 않도록 관리.

진입 상호 배제

• 프로세스 하나가 임계 영역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것.

• 임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 함.

  • 프로세스가 접근하지 않은 임계 영역은 잠금 상태.
  • 프로세스는 임계 영역에서 작업을 수행하기 전에 키를 얻어 임계 영역의 잠금 상태를 해제해야 함.
  • 프로세스가 키를 반환할 때까지 다른 모든 프로세스에 대해 잠김 상태 유지.

• 임계 영역을 떠나는 프로세스는 출구 상호배제를 수행함으로써 다른 프로세스가 임계 영역에 들어갈 수 있도록 함.

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL