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

2019. 12. 15. 21:27

상호배제 방법

수준	방법	종류
고급	소프트웨어로 해결	데커 알고리즘	다익스트라 알고리즘
		크누스 알고리즘	램포트의 베이커리 알고리즘
		핸슨 알고리즘
	소프트웨어가 제공 - 프로그래밍 언어와 운영체제 수준에서 제공	세마포어	모니터
저급	하드웨어로 해결 - 원자 수준의 연산	테스(TES, TestAndSet)

데커 알고리즘

하드웨어의 도움 없이 프로세스 두 개의 상호배제 문제를 해결.

특징

특별한 하드웨어 명령문을 필요로 하지 않는다.
임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역 진입 막지 않는다.
임계영역에 들어가기를 원하는 프로세서로 하여금 무한정 기다리게 하지 않는다.

01     program dekkersalgorithm;
02     var fprocess: (first, second);                                  // 공유 변수
03         P1_enter, P2_enter : boolean;
04     procedure P1;                                                   // 프로세스 P1의 임계영역 진입 절차
05         begin
06             while true do
07                 begin
08                     P1_enter := true;                               // P1이 임계영역 진입 시도
09                     while P2_enter do;                              // P2의 임계영역 진입 여부 확인
10                         if fprocess = second then                   // P2의 진입 차례(기회)라면
11                         begin
12                             P1_enter := false;                      // P2에게 진입 순서 양보
13                             while fprocess = second do;             // 순서 기다림(P2 완료)
14                                 P1_enter := true                    // P1이 임계영역 재진입 시도
15                             end;
16                     criticalsectionone;                             // 임계영역
17                     fprocess := second;                             // P2에게 진입 순서 양보
18                     P1_enter := false;                              // P1의 임계영역 사용 완료 지정
19                     otherstuffone                                   // P1의 잔류영역 수행
20                 end;
21         end;
22     procedure P2;
23         begin
24             while true do
25                 begin
26                     P2_enter := true;
27                     while P1_enter do;
28                         if fprocess = first then
29                             begin
30                                 P2_enter := false;
31                                 while fprocess = first do;
32                                 P2_enter := true;
33                             end;
34                     criticalsectiontwo;
35                     fprocess := first;
36                     P2_enter := false;
37                     otherstufftwo
38                 end;
39         end;
40     begin
41         P1_enter := false;
42         P2_enter := false;
43         fprocess := first;
44         parbegin
45             P1;
46             P2;
47         parend;
48     end.

기타 유용한 상호배제 알고리즘

다익스트라 알고리즘

최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결.
실행 시간이 가 장 짧은 프로세스에 프로세서 할당하는 세마포 방법.
가장 짧은 평균 대기시간 제공

크누스 알고리즘

이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당.
무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 함

램포트 알고리즘

사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘
준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당
‘램포트의 베이커리(빵집) 알고리즘’이라고 함.

핸슨 알고리즘

실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것.
대기시간과 실행 시간을 이용하는 모니터 방법.
분산 처리 프로세서 간의 병행성 제어 많이 발표

TestAndSet

공유 변수 수정하는 동안 인터럽트 발생 억제하여 임계 영역 문제 간단 해결
항상 적용할 수 없고 실행 효율 현저히 떨어짐
소프트웨어적인 해결책은 더 복잡하고 프로세스가 2개 이상일 때는 더 많은 대기 가능성
메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어 명령어
알고리즘이 간단, 하나의 메모리 사이클에서 수행하여 경쟁 상황 해결
기계명령어 2개(원자적연산 명령어 TestAndSet, TestAndSet에 지역변수 lock 설정명령어)
일부 시스템에서 원자 명령어의 하나로, 읽기와 쓰기 모두 제공
해당 주소의 값을 읽고 새 값으로 교체하면서 해당 메모리 위치의 이전 값 반환

TAS 명령어의 원자적 연산 수행

// target을 검사하고, target 값을 true로 설정
boolean TestAndSet(boolean *target){
   boolean temp = *target;    // 이전 값 기록
   *target = true;            // true로 설정
   return temp;                    // 값 반환
}

부울 변수 lock을 사용한 상호배제

do{
   while(TestAndSet(&lock))    // lock을 검사하여 true이면 대기, false이면 임계 영역 진입
      ;                                // 아무것도 하지 않음
   lock = false;                    // 다른 프로세스의 진입 허용 의미로 lock을 false로
}while(true);

TestAndSet 명령어를 사용한 상호배제

do{                                            // 프로세스 Pi의 진입 영역
   waiting[i] = true;
   key = true;
   while(waiting[i] && key)
      key = TestAndSet(&lock);
   waiting[i] = false;
       //임계 영역
       //탈출 영역
   j = (i + 1) % n;
   while((j != i) && !waiting[j])    // 대기 중인 프로세스를 찾음
      j = (j + 1) % n;                    
   if(j == i)                                // 대기 중인 프로세스가 없으면
      lock = false;                        // 다른 프로세스의 진입 허용
   else                                        // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입
      waiting[j] = false;                // Pj가 임계영역에 진입할 수 있도록
       //나머지 영역
}while(true);

TestAndSet 명령어의 장점과 단점

장점

사용자 수준에서 가능하다
- 메인 메모리를 공유하는 다중 프로세서나 단일 프로세서에서 프로세스 수에 관계없이 적용할 수 있다.
- lock 변수 수에 상관없이 구현할 수 있다.
- 구현이 단순하고 확인이 용이하다
- 다중 임계 영역을 지원한다.

단점

바쁜 대기 발생
- 프로세서 시간 소모가 크다
- 대기 프로세스는 비생산적, 자원이 소모되는 대기 루프에 남는다.
기아 상태 발생
- 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상을 대기하는 경우 가능하다.
교착 상태 발생
- 플래그는 우선순위가 낮은 프로세스가 재설정할 수 있지만, 우선순위가 높은 프로세스가 선점한다
- 우선순위가 낮은 프로세스는 lock을 가지고, 우선순위가 높은 프로세스가 이것을 얻어려고 시도할 때 높은 우선순위 프로세스는 무한정 바쁜 대기가 될 것이다.

세마포어 (Semaphore)

세마포어 정의

S : 세마포어를 나타내며 표준 단위연산 P와 V에 의해서반 접근 되는 음이 아닌 정수값을 갖는 플래그 변수

두 가지 연산(P, V)

P 연산

프로세스를 대기시키는 wait 동작으로 임계 영역에 진입하기 위한 연산

P(S) : wait(S)
while S <= 0
;                // 바쁜 대기, S > 0 이 될때까지 대기
S--;
}

V 연산

대기 중인 프로세스를 깨우는 신호를 보내는 signal 동작으로 임계 영역에서 나오기 위한 연산.
```
V(S) : signal(S){
S++;            // 다른 프로세스의 접근 허용
}
```

세마포어 사용

세마포어는 프로세스 n개의 임계 영역 문제를 다루는 데 사용.

세마포어 S에 적용된 두 연산 P, V는 동시에 두 가지 동작이 실행되는 것을 예방하는 상호 배제를 의미함.

n개의 프로세스는 1로 초기화된 공통 세마포어인 mutex(Mutual Exclusion)를 공유.

do{
   wait(mutex);
       //임계영역
   signal(mutex);
       //나머지 영역
}while(true);

세마포어는 여러 가지 동기화 문제를 다루는 데 사용.

예 : 수행 중인 두 개의 프로세스, 문장 S1을 가진 P1과 문장 S2를 가진 P2의 경우

조건 : S2는 S1이 끝난 후에만 수행되도록 구현함.
프로세스P1
```
S1;
signal(synch);
```
프로세스 P2
```
wait(synch);
S2;
```

세마포어의 종류

이진 세마포어

세마포어 S를 상호배제에 사용, 1 또는 0으로 초기화, P와 V의 연산 교대 실행

계수 세마포어

유한한 자원에 접근 제어 가능, 여러 번 획득, 해제할 수 있도록 count 자원의 사용 허가 값으로 사용
사용 가능한 자원 수로 초기화하므로, count를 초기의 세마포 수로 초기화
- 각 프로세스가 자원 사용하려면 P 연산 수행
  - S(count) 감소 (S--)
- 프로세스가 자원 해제할 때 V 연산 수행
  - S(count) 증가 (S++)

세마포어의 구현

세마포어는 제어된 변수로, P와 V의 초기 작업 때만 값이 변할 수 있음.
이진 세마포어는 0, 1 값만 가짐.
한 프로세스가 임계 영역에 있을 때, 임계영역에 들어가기를 원하는 다른 프로세스가 진입코드를 계속 순환하여 프로세스 시간 낭비함.
- 이를 극복하기 위해 세마포어의 wait, signal 동작을 수정
  - 프로세스가 wait 동작을 실행하고 세마포어의 값이 양수가 아닐 경우 프로세스는 대기함.
  - 다음 제어는 프로세서 스케줄러에 넘기고 프로세서는 준비 큐에서 다른 프로세스를 선택.
  - 세마포어 S에 의해 블록/대기 중인 프로세스는 다른 프로세스가 signal 동작을 실행해야 재시작 가능.
  - 프로세스는 wakeup 동작에 의해 재시작되고, 대기상태에서 준비 상태로 변경, 준비 큐에 놓임.
- 세마포어는 block/wakeup 동기화를 구현하는 메커니즘으로도 사용됨.
  - 하나의 프로세스가 자신을 보류시켜 사건이 발생할 때까지 기다리면 다른 프로세스가 사건 발생 때보류된 프로세서를 깨움.

세마포어의 구조

struct semaphore{
   int count;
   queueType queue;
}
semaphore S;

세마포어의 wait와 signal 연산

wait 연산

wait(S){
   S -> count--;
   if(S->count < 0){
      add this process to S -> queue;    // 프로레스를 준비 큐에 추가
      block();                                    // 프로세스 중단(일시정지)
   }
}

signal 연산

signal(S){
   S->count++;
   if(S->count <= 0){
      remove a process P from S -> queue;    // 준비 큐에서 P 프로세스를 제거
      wakeup(P);                                    // 신호를 보내 프로세스를 실행
   }
}

프로세스 리스트는 각 프로세스 제어 블록(PCB)의 링크 필드(Link Field)의 정보를 이용해 구현 가능
- 각 세마포어는 정수값과 PCB 리스트의 포인터를 포함.
- 리스트에서 LIFO(Stack)을 이용하여 프로세스를 추가, 제거 가능하나 기아상태를 발생시킬 수 있음.

두 프로세스의 동기화 문제 해결 방법

단일 프로세서

P와 V 연산을 수행하는 중에 인터럽트를 금지함
- 인터럽트를 금지하면 다른 프로세서의 명령어 실행이 중간에 끼어들지 않음.

다중 프로세서

인터럽트 금지할 수 없어, 다른 프로세스의 명령어가 임의의 방법으로 끼어들 수 있음.
- 모든 프로세서에서 인터럽트 비활성화 곤란, 이는 심각한 성능 저하로 이어질 수 있음.
하드웨어가 특별한 명령을 제공하지 않으면, 소프트웨어적 해결 방법을 사용해야 함.
- wait와 signal 연산으로는 바쁜 대기를 완전히 제거 할 수 없음.
응용 프로그램의 진입 영역에서 임계 영역까지 바쁜 대기 제거 해야 함.
- 결국 바쁜 대기의 시기를 이동해야 하는 것.
- wait와 signal 연산이 임계 영역의 바쁜 대기 제한할 수 있으므로 임계 영역은 항상 비어 있고 바쁜 대기가 거의 일어나지 않는 것처럼 보임.
바쁜 대기는 아주 짧은 기간 동안만 일어나지만, 어떤 응용 프로그램에서는 임계 영역 이 아주 길거나 항상 점유되어 있는 상황이 발생할 수 있음.
- 이때는 바쁜 대기가 매우 비효율적임

모니터 (Monitor)

세마포어의 P, V 연산이 프로그램 전체에 퍼져 있으며, 이들 연산이 미치는 영향을 전체적으로 파악하기 쉽지 않아 프로그램 작성이 어려운 단점을 극복하기 위함.
- 세마포어와 동일한 기능을 제공하지만 세마포어보다 제어가 손쉬운 고수준의 동기화구문이다.
다수의 병행 프로그래밍 언어에서 구현되어 있다.
- Concurrent-Pascal, Pascal-Plus, Module-2/3, Java 등에서 지원

모니터의 구조

하나 이상의 프로시저와 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈로 이루어진 객체.

모니터의 특징

지역(공유) Data는 모니터의 프로시저를 통해 접근이 가능하다.
- 즉, 외부에서 변수에 대한 직접 접근은 허용되지 않는다.
프로세스는 모니터의 프로시저 중 하나를 호출함으로써 모니터로 들어간다.
한 순간에 오직 하나의 프로세스만이 모니터 내에 존재할 수 있다.
- 즉, 모니터가 이미 사용 중일 경우 다른 프로세스들은 모니터가 이용가능해질 때까지 대기한다.

모니터는 3번째 특징에 의해 상호배제기능을 제공하게 된다.

모니터의 조건 변수

동기화를 위해 사용된다.
모니터 내부에 포함되며, 모니터 내부에서만 접근이 가능함
다음의 두 인터페이스에 의해서만 접근이 가능하다.
- wait 연산
  - 어떤 프로세스가 signal을 호출할 때까지 wait를 호출한 프로세스는 연기/중단된다는 의미.
- signal 연산
  - 중단된 프로세스 중에서 한 개만 재개하며, 호출 시 해당 조건 변수와 연관된 큐에서 대기 중인 프로세스 하나를 큐에서 꺼내 모니터로 진입할 수 있도록 함.
  - 중단된 프로세스가 없으면 효과가 없으며 연산이 전혀 실행되지 않는 것과 같음.

유한 버퍼에서 모니터를 이용한 생산자/소비자 문제 해결방법

/* 생산자/소비자 프로그램 */
monitor boundedbuffer; 
char buffer [N];                    /* N개의 문자가 저장될 수 있는 버퍼 */
int nextin, nextout;                /* 버퍼 포인터 */
int count;                          /* 버퍼 내부에 추가된 문자수 */
cond notfull, notempty;             /* 동기화를 위한 조건 변수 */

void append(char x)
{
   if (count == N)                  /* 버퍼에 문자가 가득 찬 경우, 오버플로 방지 */
     cwait(notfull);
   buffer[nextin] = x;
   nextin = (nextin + 1) % N;
   count++;                         /* 버퍼에 문자 하나를 추가 */
   csignal(notempty);               /* not empty 조건 변수에서 대기하고 있는 프로세스를 꺠움 */
}
void take(char x)
{
   if (count == 0)                  /* 버퍼가 빈 경우, 언더플로 방지 */
      cwait(notempty);
   x = buffer[nextout];
   nextout = (nextout + 1) % N;
   count--;                         /* 버퍼에서 문자 하나를 삭제 */
   csignal(notfull);                /* not full 조건 변수에서 대기하고 있는 프로세스를 깨움 */
}
{                                   /* 모니터 몸체(body) */
   nextin = 0;                      /* 버퍼 변수 초기화 */
   nextout = 0;
   count = 0;
}
void producer()
{
   char x;
   while(true)
   {
      produce(x);
      append(x);
   }
{
void consumer()
{
   char x;
   while (true)
   {
     take(x);
     consume(x);
   }
}
void main()
{
   parbegin(producer, consumer);
}

Reference

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

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

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

'OS' 카테고리의 다른 글

07. CPU 스케줄링 개요 (0)	2019.12.22
06. 교착상태 (0)	2019.12.16
05. 상호배제와 동기화 [1/2] (0)	2019.12.15
04. 병행 프로세스 (0)	2019.12.15
03. 스레드(Thread) (1)	2019.12.15

연

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

상호배제 방법

데커 알고리즘

특징

기타 유용한 상호배제 알고리즘

다익스트라 알고리즘

크누스 알고리즘

램포트 알고리즘

핸슨 알고리즘

TestAndSet

TAS 명령어의 원자적 연산 수행

부울 변수 lock을 사용한 상호배제

TestAndSet 명령어를 사용한 상호배제

TestAndSet 명령어의 장점과 단점

장점

단점

세마포어 (Semaphore)

세마포어 정의

두 가지 연산(P, V)

P 연산

V 연산

세마포어 사용

세마포어는 프로세스 n개의 임계 영역 문제를 다루는 데 사용.

세마포어는 여러 가지 동기화 문제를 다루는 데 사용.

예 : 수행 중인 두 개의 프로세스, 문장 S1을 가진 P1과 문장 S2를 가진 P2의 경우

세마포어의 종류

이진 세마포어

계수 세마포어

세마포어의 구현

세마포어의 구조

세마포어의 wait와 signal 연산

wait 연산

signal 연산

두 프로세스의 동기화 문제 해결 방법

단일 프로세서

다중 프로세서

모니터 (Monitor)

모니터의 구조

모니터의 특징

모니터의 조건 변수

유한 버퍼에서 모니터를 이용한 생산자/소비자 문제 해결방법

Reference

'OS' 카테고리의 다른 글

티스토리툴바