05 프로세스 동기화Permalink

• 프로세스의 실행
  • 프로세스의 병행$_{Concurrent}$
    • 한 시스템에서 동시에 여러 프로세스 존재 (다중프로그래밍 시스템)
  • 독립적 실행 또는 협력 실행
• 독립적인 실행
  • 주어진 초기 치에 대해서 항상 같은 결과
  • 다른 프로세스의 영향을 받지 않음
• 협력적 실행
  • 다른 프로세스에게 영향을 주거나 받는 경우
• 프로세스 협력의 장점
  • 정보 공유$_{information \ sharing}$
  • 계산 속도 증가$_{computation \ speedup}$
  • 모듈화$_{modularity}$: 시스템 기능에 따라 프로세스 분리
  • 편의성$_{convenience}$: 개별 사용자가 여러 작업을 동시에 수행하는 환경

  예시) 두 프로세스가 동일한 파일을 사용할 때 프로세스 하나가 파일에서 읽기를 수행하는 동안 다른 프로세스는 해당 파일에 쓰기를 하면 서로 영향을 받는다.

• 프로세스 간 통신과 동기화 메커니즘 필요
  • 자원에 대한 접근이나 공유 데이터에 대한 접근 시에 프로세스 동기화 필요
  • 커널에서 담당
• 협력 프로세스의 자료 및 정보 교환
  • 프로세스 간 통신$_{IPC:\ Interprocess \ communication}$이 필요
    • 공유 메모리$_{shared \ memory}$, 메시지 전달$_{message \ passing}$
  • 대표적인 예: 생산자/소비자 문제
    • 프로세스 동기화

병행 프로세스Permalink

• 병행 프로세스 개념
  • 프로세스 여러 개가 동시에 실행되는 것
    • 독립적으로 작업을 수행
    • 다른 프로세스와 협력하며 특정 기능 수행 → 프로세스 간의 통신이 필요
• 프로세스간 상호 작용 (경쟁과 협력이 동시에 발생 가능)
  • (경쟁)경쟁 관계 유지하는 독립적인 프로세스 - 서로 인식 못하는 경쟁 관계
    • 정보 교환이 없으나
    • 어떤 프로세스의 수행이 나머지 프로세스들의 수행에 영향 줌
    • 두 개의 프로세스가 동일 자원에 대한 접근 시도 - 하나의 프로세스에 자원 할당
    • 경쟁관계에 있는 프로세스들은 상호배제 필요
    • [예] 다중프로그래밍 환경 - 동일한 디스크나 프린터의 접근 조절 필요
  • (협력/공유)입출력 버퍼 등 공유 개체 공유 단계 - 간접적으로 인식하는 관계
    • 다른 프로세스로부터 얻은 정보에 의존
    • 프로세스의 타이밍 영향 받음
    • 프로세스들은 공동 개체를 공유하는데 따른 협력 필요
  • (협력/통신)프로세스들이 서로 인식, 통신 - 기본적인 함수 보유
    • 직접 통신 가능, 서로 함께 동작되도록 설계된 프로세스(협력관계)

비동기 병행 프로세스Permalink

• 비동기적$_{asynchronous}$
  • 각 프로세스들이 다른 프로세스들의 진행 상태 등을 전혀 모름
• 병행적$_{concurrent}$
  • 시스템 내에 다수의 프로세스들이 동시에 존재함
  • 일반적으로 프로세스들은 비동기적으로 병행 수행

    • 병행 수행: 여러 프로세스들이 프로세서를 번갈아 사용

      → 즉, 프로세서가 쉬는 시간 없이 돌아가도록 하는것

병행 프로세스의 해결 과제Permalink

• 결정성$_{determinacy}$ 확보
  • 동시에 수행되는 다른 프로세스들의 실행 속도와 관계없이 주어진 초기 치에 대해 항상 같은 결과를 보장
• 협력 또는 동기화$_{synchronization}$
  • 프로세스의 진행이 다른 프로세스의 진행에 의존
  • 상호배제는 동기화의 한 종류
• 상호 배제$_{mutual \ exclusion}$
  • 어떤(공유) 자원에 대해 한 번에 한 프로세스만이 접근
• 교착$_{deadlock}$ 상태 해결
  • 교착상태: 프로세스들이 서로 다른 프로세스가 점유한 자원을 요구하여, 아무도 진행되지 못하는 상태
    • 커널을 사용해서 자원을 컨트롤 할 수 있음

프로세스 간 통신 (IPC)Permalink

• 프로세스가 통신하고 그들간의 행동을 동기화하는 메커니즘
• 두 가지 기본적인 통신 모델(커널에서 지원)
  • 공유 메모리$_{Shared \ memory}$
  • 메시지 전달$_{Message \ passing}$
• 공유 메모리: 모델에서, 협력프로세스가 공유하는 메모리 영역이
  • IPC는 공유 영역에 데이터를 판독 또는 저장하는 형식으로 수행
• 메시지 전달: 모델에서, IPC는 협력 프로세스간의 메시지 교환을 통하여 수행
  • IPC는 데이터의 전송 또는 수신을 통하여 수행
• 다수의 시스템은 두 가지 모델을 함께 구현

(a) 메시지 전달 메커니즘

• A 프로세스에서 B 프로세스로 정보 공유

(b) 공유 메모리 메커니즘

• A 프로세스가 B에게 정보를 보내기 위해 공유 메모리에 쓰기를 통해 기록
• B 프로세스가 A의 정보를 받기 위해 공유 메모리에서 읽기를 통해 기록을 받아들임

생산자-소비자 문제Permalink

• 생산자 프로세스 / 소비자 프로세스
  • 생산자 프로세스: 정보를 생산
  • 소비자 프로세스: 정보를 소비

• 생산자 프로세스가 우선 정보를 생산해야 소비가 가능하다.

  → 생산이 항상 먼저 되어야 한다.

• 비동기적 작업이다.
• 생산자/소비자 프로세스의 병행 실행을 위해 공유 메모리 필요
  • 생산자/소비자 프로세스들은 동시에$_{concurrently}$ 수행
  • 생산자와 소비자가 공유하는 메모리 영역에 버퍼가 존재
  • 생산자가 먼저 항목을 생산 → 나중에 소비자가 소비: 동기화
  • 버퍼의 종류
    • 무제한 버퍼$_{unbounded \ buffer}$
    • 제한 버퍼$_{bounded \ buffer}$
  • 무제한 버퍼에서는
    • 소비자는 새로운 아이템을 기다려야만 한다
    • 생산자는 언제든지 새로운 아이템을 생산할 수 있다
  • 제한 버퍼에서는
    • 소비자는 버퍼가 비었다면 기다려야 한다
    • 생산자는 버퍼가 꽉 찼다면 기다려야 한다

제한 버퍼 공유 메모리 방법Permalink

• 생산자와 소비자 사이의 공유 데이터

1
2
3
4
5
6
7
#define BUFFER_SIZE 10 // 버퍼 크기
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0; //초기 상태
int out = 0; //비었음

• 공유 버퍼는 두 개의 논리적 포인터를 in과 out을 갖는 원형 배열$_{circular \ array}$로 구현된다
  • (BUFFER_SIZE-1)개 보다 많은 원소를 저장할 수 없다
  • 공백(Empty) when in == out
  • 꽉 참(Full) when (in+1)%BUFFER_SIZE == out

• 생산자 프로세스

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
    item nextProduced;
    while (true) 
    {
    	/* 한 개의 아이템을 nextProduced에 생산한다 */
    	while ( ( (in + 1) % BUFFER_SIZE ) == out ); 
    	/* 빈 버퍼가 없으므로 아무 일도 하지 않는다 */
      
    	/* 새로운 아이템을 버퍼에 삽입한다 */
    	buffer[in] = nextProduced;
    	in = (in + 1) % BUFFER_SIZE ;
    }
  

• 소비자 프로세스

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
    item nextConsumed;
    while (true) 
    {
    	while (in == out); 
    	// 소비할 아이템이 한 개도 없으므로 아무 일도 하지 않는다
      
    	// 버퍼에서 하나의 아이템을 제거한다
    	nextConsumed = buffer[out];
    	out = (out + 1) % BUFFER SIZE;
    	return nextConsumed;
    }
  

메시지 전달$_{Interprocess \ Communication}$Permalink

• 메시지 전달 시스템
  • 공유 변수들을 사용하지 않고 프로세스들 간의 통신
• 기본 구조
  • 두 가지 연산 제공: send(message)/receive(message)
  • 통신 연결을 설정하고 send와 receive 를 통해 메시지 교환
  • 통신하는 협력 프로세스들이 시스템콜 호출
• 구현 방법
  • 직접통신 또는 간접통신
  • 동기화 또는 비동기화 통신
  • 자동적인 또는 명시적인 버퍼링

직접 통신과 간접 통신Permalink

• 직접 통신
  • 메시지 전송/수신 시 통신의 전송자/수신자 이름 명시
    • Send(P, message): 프로세스 P에게 메시지 전송
    • Receive(Q, message): 프로세스 Q로부터 메시지 수신
  • 연결이 자동으로 이루어짐
  • 각 쌍에 정확히 하나의 연결이 존재
  • 일반적으로 양방향
• 간접 통신
  • 메시지를 메일 박스를 통해 송신하고 수신 → 전송자/수신자를 서로 모름
    • 각 메일 박스는 고유 id를 가짐
      • Send(A, message)
      • receive(A, message)
  • 연결은 한 쌍의 프로세스가 공유 메일박스를 가질 때 이루어짐
  • 연결은 다수의 프로세스들과 연관이 가능
  • 단방향 또는 양방향
  • 문제점
    • 메일 박스를 공유의 예
      • 프로세스 P1, P2, P3이 메일박스 A를 공유
      • P1이 송신; P2와 P3가 수신하는 경우
      • 누가 메시지를 수신하나?
    • 해결 방법 (아래 선택 사항에 따라서)
      • 하나의 링크에 최대한 두 개의 프로세스만 연결
      • 한 번에 하나의 프로세스만 receive() 연산을 수행
      • 시스템이 임의적으로 수신자를 선택

동기화$_{Synchronization}$Permalink

• 메시지 전달의 두 가지 유형
  • 봉쇄형$_{blocking}$ = 동기화$_{synchoronous}$
    • 봉쇄형 송신: 메시지가 수신(배달)될 때까지 송신 프로세스가 차단
    • 봉쇄형 수신: 메시지가 사용 가능할 때까지 수신 프로세스가 차단
  • 비봉쇄형$_{non-blocking}$ = 비동기화$_{asynchronous}$
    • 비봉쇄형 송신: 송신 프로세스가 계속 메시지를 송신 가능
    • 비봉쇄형 수신: 수신 프로세스는 유효한 메시지 또는 빈 메시지를 수신
• 생산자-소비자 문제 해결
  • 봉쇄형 송신/수신을 사용한 쉽게 동기화 해결

버퍼링$_{Buffering}$Permalink

• 버퍼
  • 통신 링크에 붙어있는 메시지 큐
  • 메시지들은 통신 동안 임시적인 큐에 저장
• 메시지 큐의 구현 방법 3가지
  • 무용량$_{Zero \ capacity}$ – 큐에는 0개 메시지
    • 큐의 최대 길이: 0
    • 송신자는 수신자가 메시지를 받을 때까지 대기$_{rendezvous}$
  • 제한 용량$_{Bounded \ capacity}$ – 일정 길이의 n개의 메시지
    • 송신자는 링크가 가득 차 있다면 대기
  • 무제한 용량$_{Unbounded \ capacity}$ – 무제한 길이
    • 송신자는 결코 기다릴 필요가 없음

생산자-소비자 문제 변형Permalink

기존 문제에서 counter 변수를 추가함

• 생산자와 소비자가 동시에 수행될 때 다른 결과 발생 가능
  • counter = 5 일 때
    • 생산자와 소비자에서 counter++와 counter–가 동시에 수행되면
    • counter 값이 4, 5, 6이 될 수 있음
  • 기계어 표현 (counter++)
    • register1 = count register1 = register1 + 1 count = register1
  • 기계어 표현 (counter–)
    • register2 = count register2 = register2 - 1 count = register2
  • register1과 register2가 CPU내의 동일한 레지스터이더라도, 인터럽트 핸들러가 해당 레지스터 값을 저장하고 적재하는 과정으로 처리

  counter = 5가 들어가 있는 경우

  T0: producer execute register1=counter {register1 = 5}

  T1: producer execute register1=register1+1 {register1 = 6}

  T2: consumer execute register2=counter {register2 = 5}

  T3: consumer execute register2=register2-1 {register2 = 4}

  T4: producer execute counter = register1 {counter = 6 }

  T5: consumer execute counter = register2 {counter = 4}

  • 이 경우 counter=5 → counter=4
  • 만약 T4와 T5의 순서를 바꾸면, counter=6
  • 즉, 가장 마지막에 실행되는 프로세스가 메모리 값을 결정
  • 상호 배제를 통해 두 프로세스가 동시 접근 못하도록 해야함

경쟁 상태$_{race \ condition}$Permalink

경쟁상태Permalink

• 공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황
• 여러 프로세스가 공유 데이터를 동시에(병행적으로) 접근(읽기나 쓰기)할 때 공유 데이터에 대한 접근 순서에 따라 실행 결과가 달라지는 상황
• 장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세서가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생하는 오류
• 접근 순서화가 필요
• 이를 방지하기 위해 병행 프로세서들은 반드시 동기화 필요
• 동기화 구현 방법
  • 임계영역$_{critical \ section}$을 이용한 상호배제$_{mutual \ exclusion}$

임계영역Permalink

• 프로그램에서 임계자원을 이용하는 코드 부분
  • 임계자원: 둘 이상의 프로세스가 공유할 수 없는 자원
• 공유 기억장치가 참조되는 프로그램의 부분
• 한 순간에 하나의 프로세스만 사용(공유자원의 독점적 사용 보장)
• 공유 데이터에 접근하는 프로그램 세그먼트
• 상호 배제
  • 둘 이상 프로세스가 동시에 임계 영역에 진입을 방지
  • CS 내부: 빠른 속도로 수행, block 금지, 무한루프 방지 만족하는 코드 필요

상호 배제$_{Mutual \ exclusion}$Permalink

• 상호배제
  • 특정한 비공유 자원 : 한 순간에 1개의 프로세스만 사용

  • 공유 데이터 엑세스할 때 다른 프로세스들의 데이터 엑세스 금지

    공통 변수나 파일 - 차례대로 하나의 프로세스만이 읽거나 씀

• 프로세스들 간의 동기화
  • 공유자원을 동시에 사용하지 못하게 실행을 제어하는 기법
  • 순차적으로 재사용 가능한 자원을 공유하기 위하여 상호 협력하는 프로세스 사이에서 나타남
• 상호 배제가 실시되면 교착상태$_{deadlock}$와 기아$_{starvation}$ 상태 발생 가능
• 임계영역 문제를 해결하기 위한 세 가지 조건
  • 상호 배제
    • 프로세스 $P_i$가 임계영역을 수행 중일 때, 다른 프로세스는 임계영역을 수행할 수 없다.
  • 진행$_{progress}$
    • 임계영역을 수행하는 프로세스가 없고, 여러 개의 프로세스가 임계영역에 진입하려면 프로세스 선정 알고리즘에 따라 다음 임계영역에서 수행할 대상을 선정
    • 교착 상태$_{deadlock-free}$다음 임계영역으로 들어갈 프로세스 선택은 무한정 지연할 수 없음
  • 제한된 대기$_{bounded \ waiting}$

    • 한 프로세스가 임계영역을 요청한 후 요청이 수락되기까지 다른 프로세스가 임계영역에 진입할 수 있는 회수를 제한해야 한다.

      → 유한한 대기 시간$_{starvation-free}$

상호 배제 프리미티브$_{Mutual \ Exclusion \ Primitives}$Permalink

• 프로세스 동기화의 기능을 제공
• 프로세스들이 협력하여 자원을 사용
• 상호 배제를 위한 기본적인 연산 호출
• 임계영역에서 일어나는 일을 캡슐화
• enterCS() 프리미티브
  • 임계 영역 진입 전 검사과정
  • 다른 프로세스가 임계 영역 내에 존재하는지의 여부 검사
• exitCS() 프리미티브
  • 임계 영역 벗어날 경우 처리 과정
  • 임계 영역에서 벗어남을 시스템에 알림

상호 배제 프리미티브 구현 방법Permalink

• 소프트웨어적 접근방법
  • 수행 부하가 높고, 논리적 오류의 위험성이 크다.
• 하드웨어 지원
  • 인터럽트 금지
  • 특별한 기계 명령어: Test and Set()
• 세마포어$_{Semaphore}$
  • 상호배제 문제 해결을 위한 정수형 변수
• 모니터$_{Monitor}$
  • 상호배제 문제 해결을 위한 객체
• 프리미티브 버전 1
  • 시스템 내 프로세스가 2개만 존재하는 경우
    • $turn = 0, P_0$이 CS진입
    • $turn = 1, P_1$이 CS 진입

  

  • 상호 배제 보장
  • turn = 0인 경우
    • $P_0$: CS 접근 시도 X

    • $P_1$: CS 진입 시도

      → $P_1$은 진행 조건 위배에 의해 CS 접근 불가능

  • 한 프로세스가 연속으로 두 번 임계 영역에 진입 불가능
• 프리미티브 버전 2
  • flag: 임계영역 진입 상태를 boolean으로 나타냄

  

  • 상호 배제 보장 X
  • flag가 false 되기 전에 프로세스가 진입해서 두 개의 프로세스 실행 될 수 있음
• 프리미티브 버전 3
  • flag = true를 앞에 둬서 버전 2 개선

  

  • 두 프로세스가 flag = true로 설정 시 교착 상태가 됨

상호배제 알고리즘Permalink

• Dekker
  • 두 프로세스에 대한 최초의 상호 배제 알고리듬
  • 프리미티브 모든 버전의 단점 보완
    • flag, turn 사용
  • 두 프로세스가 모두 자신의 flag[] ← true, CS 진입하려면,
    • 그 당시의 turn 값에 따라 진입 순서 결정
  • 한 프로세스가 CS에 진입하기 위해서,
    • 상대 프로세스의 flag값이 false 임을 확인
• Peterson
  • Dekker보다 간단한 상호 배제 알고리즘
  • 각 프로세스가 CS에 진입할 때,
    • 자신의 flag ← true, turn ← 상대방 차례
  • while loop에서 상대방 프로세스의 진입 시도 검사
    • 만약 두 프로세스가 진입시도(flag[0],[1] = true) 경우,

      • turn 값에 따라서 CS에 진입(turn 값은 먼저 설정한 프로세스가 CS에 우선 진입)

        → 나중에 turn 값을 변경한 프로세스가 상대방에게 양보

n-프로세스 상호배제Permalink

• Dijkstra 알고리즘
  • 무기한 연기의 가능성이 있음
• Knuth 알고리즘
  • 무기한 연기의 가능성을 제거
  • 지연 시간이 매우 큼
• Eisenberg 와 McGuire 알고리즘
  • 유한 시간 (n-1 번) 내의 시도 후 임계 영역 진입 보장
• Lamport 빵집 알고리즘
  • 분산 시스템 환경을 위한 상호 배제 기법

하드웨어적 상호 배제 해결법Permalink

• 상호 배제를 위한 소프트웨어적 해결 기법들의 문제
  • 실행 시간이 오래 걸림
  • 프리미티브 실행 중 블럭될 가능성 존재함
• 하드웨어적 상호 배제 해결법
  • 인터럽트 불가능 (프로세스 선점 금지)
    • 임계영역에 접근하기 전에 인터럽트를 금지, 빠져 나온 후 인터럽트 허용
    • 문제점
      1. 특권 모드로 프로세스가 실행되어 루프에 빠진 경우, OS가 제어권을 받을 수 없음.
      2. 다중 프로세서 시스템의 경우 적용 불가 (각각의 CPU는 독립적인 인터럽트 금지 메커니즘을 갖기 때문에 다른 CPU는 임계영역을 실행 가능)
      3. 모드전환 오버헤드가 크다.
  • TS$_{Test \ and \ Set}$ 명령 (기계어 명령)
    • 원자성, 분리불가능의 특성 가짐

TS() 명령을 사용한 N-프로세스 상호배제 알고리즘Permalink

• TS 명령의 정의

  

  • Atomic 명령: 원자성을 보장하는 명령 즉, 연산이 중간에 중단되지 않고 한 번에 완료된다

• TS(flag[i], active) = TS(a, b)
• 위 그림의 동작 순서
  • TS 명령어 정의대로 동작
  • flag[i] ← true(a ← b)
  • while (flag[i]) do while(true)
  • 임계 영역을 벗어나면 active를 false로 바꿔 초기화 시킴

상호 배제 기법들의 단점Permalink

• 바쁜 대기$_{busy \ waiting}$ (spinlock)
  • 임계영역에 진입할 가능성이 없는 기간 동안 디스패치되어 enterCS() 프리미티브 내에서 loop를 도는 상황
• busy waiting
  • 가정
    • 단일 프로세서 시스템
    • 프로세스 Pi가 CS에 진입, 벗어나기 전에 블록
    • 다른 프로세스 Pj가 디스패치, 같은 CS에 진입시도
  • 문제
    • 상호배제 알고리듬이 Pj가 CS에 진입 불가능하게 함
    • enterCS() 프리미티브 내에서 loop을 돌게 됨
    • 이 loop를 벗어나는 것은 Pi가 실행하여 CS를 벗어날 때까지 불가능
    • Pi가 실행되어 CS를 벗어날 때까지 CS에 진입을 시도하는 다른 프로세스는 프로세서 자원 낭비 초래

세마포어$_{Semaphore}$Permalink

• Dijkstra가 제안
• 정의
  • 일종의 정수형 변수 (S)
  • 세마포어(S)에 접근: P()연산, V() 연산, 초기화 연산에 의해서만 가능
  • 임의의 세마포어 S에는 하나의 대기 큐 $Q_s$가 할당됨
• 장점
  • 바쁜 대기 문제 해결
    • 임계 영역에 즉시 진입할 수 없는 프로세스들을 대기 상태로 전이시킴
  • 응용프로그래머가 사용하기 덜 복잡함
    • 하드웨어 기반 해결법이 아님
• 이진 세마포어$_{binary \ semaphore}$
  • 세마포어 변수: 0과 1
  • 목적: 상호 배제, 프로세스 동기화
• 카운팅 세마포어$_{counting \ semaphore}$
  • 세마포어 변수: 0 이상의 모든 정수
  • 목적: 생산자-소비자 문제 등의 해결
  • 생산자 소비자 변형의 counter 변수가 바로 카운팅 세마포어임
• 세마포어 변수에 대해 접근 가능한 연산
  • 초기화 연산
    • 세마포어 변수에 초기값을 부여하는 연산
  • P() 연산, V() 연산

    • P(S) 연산, 검사(wait)

      1
      2
      3
        S ← S - 1;
        if (S < 0)
        	then wait on the queue Qs;
      

      • 세마포어가 0보다 작다면 대기 상태로 전환 시킴

    • V(S) 연산, 증가(signal)

      1
      2
      3
        S ← S + 1;
        if (S <= 0)
        	then wakeup a process on Qs;
      

      • 세마포어가 0보다 작거나 같다면 큐에서 한개의 우선순위가 높은 프로세스를 깨운다.

    • 분리불가능 연산 (atomic, 상호배제 보장)

상호배제 문제Permalink

• 세마포어, P(), V() 연산을 이용한 상호배제 프리미티브 구현

  

  • 프로세스가 CS에 진입하기 전 P()연산 수행
  • CS를 벗어날 때 V() 연산 수행
  • n-프로세스 상호배제 보장

프로세스 동기화 문제Permalink

• 컴퓨터 시스템 내에 존재하는 프로세스들의 일반적 특성
  • 병행적이고 비동기적으로 수행됨
• 동기화가 필요한 경우

  • Pj가 Lj를 통과할 때까지 Pi는 Li를 통과하지 못하게 하는 경우

    

  • 해결법: 세마포어 변수(S) 이용
    • 세마포어 변수 초기화: S ← 0
    • Pi가 Li 지점에서 P(S) 연산
    • Pj가 Lj 지점에서 V(S) 연산
  • Pi가 먼저 Li에 도착 (S = 0 인 경우)
    • P(S): 세마포어 큐에서 대기
    • Pj가 Lj에 도착, V(S) 수행: Pi는 wakeup 될 수 있음
  • Pj가 먼저 Lj에 도착
    • V(S) 수행: S ← S+1 : Pj 실행
    • 이후 Pi가 Li에 도착: P(S) 수행, S ← 0

교착과 기아Permalink

• 교착$_{Deadlock}$
  • 두 개 이상의 프로세스들이 대기상태의 특정한 프로세스만이 발생시킬 수 있는 이벤트를 무한 대기하는 것

  • 대기 큐를 가진 세마포어의 사용은 교착을 유발할 수 있다

    예) S와 Q 두 개의 세마포어 1로 초기화

• 기아$_{Starvation}$
  • 하나의 프로세스가 정지된 세마포어 큐로부터 제거되지 못할 수도 있다

  • 대기 큐를 가진 세마포어 구현은 기아를 유발할 수도 있다

    예) 큐가 LIFO (last-in, first-out) 순서일 경우

생산자-소비자 문제Permalink

• 구현방법

  • 단일 버퍼

    

    • 공유 메모리 버퍼

      1
      2
      3
        var consumed : semaphore ← 1,
        produced : semaphore ← 0,
        buffer : message;
      

    • 2개의 세마포어 consumed, produced 사용

    • 생산자

      1
      2
      3
      4
      5
      6
      7
      8
        repeat
        ...
        	create a new message M;
        	P(consumed);
        	buffer ← M;
        	V(produced);
        ...
        until(false);
      

    • 소비자

      1
      2
      3
      4
      5
      6
      7
      8
        repeat
        ...
        	P(produced);
        	m ← buffer;
        	V(consumed);
        	consume the message m;
        ...
        until(false);
      

    • 생산자/소비자 프로세스가 번갈아 가며 버퍼에 메시지 적재하고 소비하는 일을 반복함

  • 원형 다중 버퍼

    • 공유 버퍼

      1
      2
      3
      4
      5
        var full : semaphore ← 0,
        empty : semaphore ← N,
        mutex : semaphore ← 1,
        buffer : array[0..N-1] of message,
        in, out : 0..N-1 ← 0, 0;
      

    • 생산자

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
        repeat
        ...
        	create a new message M;
        	P(empty);
        	P(mutex);
        		buffer[in] ← M;
        		in ← (in + 1) mod N;
        	V(mutex);
        	V(full);
        ...
        until(false);
      

    • 소비자

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
        repeat
        ...
        	P(full);
        	P(mutex);
        		m ← buffer[out];
        		out ← (out + 1) mod N;
        	V(mutex);
        	V(empty);
        ...
        until(false);
      

Reader-Writer 문제Permalink

• reader, writer 프로세스가 병행으로 데이터에 접근할 때 데이터 무결성 보 장 방법
• reader 프로세스
  • 임의의 데이터 또는 데이터 집합에 대해 읽기 연산만 수행
• writer 프로세스
  • 임의의 데이터 또는 데이터 집합에 대해 갱신 연산을 수행
• 데이터의 무결성 보장 기법
  • writer 프로세스의 접근시에만 상호 배제 및 동기화 필요
  • reader 프로세스는 데이터 무결성에 상관 X
• 문제의 코드
  • 공유 변수

  1
  2
    var wmutex, rmutex : semaphore := 1, 1,
    nreaders : integer := 0 //동시 독자 수
  

  • Reader

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
    repeat
    ...
    	P(rmutex);
    	if (nreaders = 0) then //첫 독자
    		P(wmutex);
    	endif;
    	nreaders ← nreaders + 1;
    	V(rmutex);
    	Perform read operations;
    	P(rmutex);
    	nreaders ← nreaders - 1;
    	if (nreaders = 0) then //끝 독자
    		V(wmutex);
    	endif;
    	V(rmutex);
    ...
    until(false);
  

  • Writer

  1
  2
  3
  4
  5
  6
  7
    repeat
    ...
    	P(wmutex);
    	<mark>**Perform write operations**</mark>
    	V(wmutex);
    ...
    until(false);
  

  • 코드 분석
    • wmutex: 쓰기자가 쓰기 작업을 수행할 때 사용되는 세마포어 1이면, 어떤 쓰기자도 쓰기 작업을 시작할 수 있다.
    • rmutex: 읽기자들이 동시에 읽기 작업을 수행할 때 사용되는 세마포어 1이면, 어떤 읽기자도 읽기 작업을 시작할 수 있다.
    • nreaders: 현재 동시에 읽기 작업을 수행 중인 독자의 수를 나타내는 정수
    • Reader 코드
      1. 읽기자는 먼저 rmutex 세마포어 대기
      2. 만약 현재 독자가 없다면(첫 독자), wmutex 세마포어를 기다려서 쓰기자들이 쓰기 작업을 못하게 함.
      3. 읽기자 수를 증가
      4. rmutex 세마포어를 통해 읽기 작업을 수행
      5. 읽기 작업 완료 후, 다시 rmutex 세마포어를 사용하여 독자 수를 감소
      6. 만약 현재 독자가 더 이상 없다면(끝 독자), wmutex 세마포어를 통해 쓰기자들이 쓰기 작업을 시작할 수 있도록 함.
    • Writer 코드
      • wmutex 세마포어를 기다려 쓰기 작업을 수행한 후, 다시 세마포어를 해제.

식사하는 철학자 문제Permalink

• 문제 조건
  • 5명의 철학자: 삶에 대한 생각 또는 식사만 함
  • 철학자들은 원탁에 앉아 있음
  • 테이블 가운데는 밥을 담은 그릇이 존재
  • 테이블에는 5개의 젓가락이 존재
  • 생각하는 동안, 다른 철학자와 상호작용 없음
  • 배가 고프면, 양 옆에 있는 두 개의 젓가락을 집으려 함
    • 한 번에 한 개의 젓가락만을 집을 수 있음
  • 철학자는 이웃이 사용하는 젓가락은 사용 불가
  • 두 개의 젓가락으로 식사 (계속 젓가락을 들고)
  • 식사 종료 후, 두 개의 젓가락을 내려 놓고 다시 생각함
• 동시에 수행되는 프로세스에서 어떻게 교착과 기아가 발생하지 않고 구현할 수 있는가?

• 해결 방안
  • 밥공기 (데이터 집합)
  • 세마포어 chopstick [5]은 1로 초기화

• 철학자 i의 구조

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
    do 
    {
    	wait ( chopstick [i] ); // 왼쪽 젓가락 집음
    	wait ( chopstick [ (i+1)%5 ] ); //오른쪽 젓가락 집음
    	…
    	// 식사
    	…
    	signal ( chopstick [i] );//왼쪽 놓음
    	signal ( chopstick [ (i+1)%5 ] );//오른쪽 놓음
    	…
    	// 생각
    	…
    } while (TRUE);
  

• 그러나, 위 해결 방안은 교착 상태를 유발할 수 있다.
  • 단순 무식한 알고리즘으로 5명의 철학자가 전부 왼쪽 젓가락을 들면 모든 젓가락을 사용하게 된다.
  • 즉, 오른쪽 젓가락을 들 수 없어 영원히 기다려야 한다.
• 교착 상태 해결 방안
  • 철학자 숫자를 5 → 4로 조정
  • 철학자가 양쪽 젓가락을 모두 사용 가능한 경우만 젓가락을 집도록 함
  • 비대칭 해결방안으로, 홀수는 왼쪽 젓가락을, 짝수는 오른쪽 젓가락을 먼저 집도록 함