프로세스 동기화 및 임계구역 [운영체제]

1. 프로세스간 통신

 

1.1 파일, 스트림, 프로세스

1.1.1 파일, 스트림, 프로세스

• 파일 : 데이터를 저장하는 가장 기본적인 단위로써 일반 파일, 디렉토리, 디바이스도 파일로 취급
• 스트림 : 데이터의 흐름
  ex) 구현한 프로그램과 참조할 데이터가 저장되어 있는 파일 사이에서 데이터가 이동할 수 있는 다리를 놓는 일
  물론 스트림이라는 것은 운영체제에 의해서 형성되는 소프트웨어적인 상태를 의미하는 것일 뿐, 실제로 다리가 놓여지는 것은 아니다.
• 프로세스 : 프로세서(CPU)를 사용하여 실행중인 프로그램

 

1.2 프로세스 간 통신(inter-process communication, IPC)

1.2.1 pipe

• 같은 컴퓨터 내에 있는 프로세스 간 단방향 통신에 사용됨
  - 따라서, 프로세스 간 양방향 통신을 위해 pipe를 2개 이용해야 함
• 부모 프로세스와 자식 프로세스 사이에서만 통신 가능
• 예) 리눅스에서 pipe(|) 명령어 사용
  - 한 프로세스의 표준출력을 다른 프로세스의 표준입력으로 연결(단방향 통신)

$ ls -al | more	// ls -al 의 표준출력을 한 화면씩 모니터에 출력

[그림 1] pipe 2개를 이용한 프로세스간 양방향 통신

 

 

1.2.2 named pipe(FIFO)

• pipe와 같은 점
  - 같은 컴퓨터 내에 있는 프로세스 간 단방향 통신에 사용됨
• pipe와 다른 점
  - FIFO라는 파일을 거쳐야 프로세스 간 통신 가능
  - 서로 독립된 프로세스간 통신 가능

 

1.2.3 Socket

• 한 컴퓨터 내 또는 다른 컴퓨터 내의 프로세스 간 양방향 통신을 위해 사용됨
• UNIX 도메인 소켓
  - 한 컴퓨터 내의 프로세스간 양방향 통신을 위해 사용됨
  - 프로세스 간의 통신을 위해 소켓 파일을 이용
• BSD 소켓
  - 인터넷에서 TCP/IP 모델을 이용하여 한 컴퓨터 내 또는 다른 컴퓨터 내의 프로세스간 양방향 통신을 위해 사용됨
  - 프로세스 간의 통신을 위해 호스트 IP주소와 프로세스의 포트 번호를 사용
  - 네트워크 프로그래밍의 표준 인터페이스(API)
  > 오늘날 컴퓨터 간의 통신은 일반적으로 인터넷에서 TCP/IP 모델을 사용하므로 네트워크 프로그래밍 또는 TCP/IP 통신 프로그래밍은 BSD 소켓을 기반으로 한 소켓 프로그래밍을 의미함
  > 유닉스 계열 OS(Linux, MacOS)는 BSD 소켓을 지원하며 Windows는 BSD 소켓을 기반으로 한 WinSock(Windows Socket)을 지원함 
• 서로 독립된 프로세스간 통신 가능

[그림 2] socket을 이용한 프로세스간 통신

 

 

2. 임계영역과 프로세스 동기화

 

2.1 경쟁상태(race condition)

2.1.1 공유자원(shared resource)

• 여러 프로세스들 또는 스레드들이 공유하는 자원(공동으로 이용하는 변수, 메모리, 파일)

 

2.1.2 경쟁상태(race condition)

• 여러 프로세스들 또는 스레드들이 공유자원에 동시에 접근하여 읽거나 쓸 때 발생
• 여러 프로세스들 또는 스레드들이 공유자원에 접근하는 순서에 따라 공유자원에 저장되는 값이 달라질 수 있음

ex) 생산자 프로세스와 소비자 프로세스

• 생산자 프로세스는 공유 버퍼에 생산한 물건을 넣고 소비자 프로세스는 공유 버퍼에서 생산한 물건을 가져옴
• 생산자 프로세스와 소비자 프로세스는 공유 버퍼에 있는 물건의 수를 확인하기 위해 counter이라는 변수를 사용
• 경쟁상태 발생
  - 생산자 프로세스와 소비자 프로세스가 동시에 실행되면 공유자원(counter)에 접근하는 순서에 따라 공유자원(counter)에 저장되는 값이 달라질 수 있음
  > 생산자 프로세스의 counter 연산이 소비자 프로세스보다 먼저 실행된다면 counter = 4
  > 소비자 프로세스의 counter 연산이 생산자 프로세스보다 먼저 실행된다면 counter = 2

[그림 3] 생산자 프로세스와 소비자 프로세스

 

 

2.2 임계영역(critical section)

2.2.1 임계영역

• 경쟁상태가 발생하는 영역
• 경쟁상태를 막기 위해 한 번에 한 프로세스 또는 스레드가 임계영역에 접근해야 함

 

2.2.2 임계영역 문제 해결을 위해 아래의 조건이 모두 보장되어야 함

• 상호 배제(mutal exclusion, mutex)
  - 한 번에 한 프로세스 또는 스레드가 임계영역에 접근해야 함
  - 한 프로세스가 임계영역에서 실행 중일 경우 다른 프로세스는 해당 임계영역에서 실행될 수 없음(비선점)
  - 제일 중요한 조건
• 한정 대기(bounded waiting)
  - 프로세스 또는 스레드가 임계영역에서 실행되기 위해 기다리는 시간은 정해져 있음
  - 프로세스 또는 스레드가 임계영역에서 실행되기 위해 무한정 기다리지 않음
• 진행의 융통성(progress flexibility)
  - 한 프로세스 또는 스레드가 임계영역에서 실행 중이지 않을 경우 다른 프로세서는 임계영역에서 실행될 수 있음

※ 위의 세가지 조건을 모두 보장하는 임계영역 문제 해결 방법

• 피터슨 알고리즘, 데커 알고리즘, 세마포어(semaphore)

 

2.3 프로세스 동기화(process synchronization)

2.3.1 프로세스 동기화

• 한 번에 한 프로세스가 하나의 공유자원에 접근하도록 하는 것
• 상호 배제를 가능하게 하는 것
• 현재는 프로세스의 실제 처리가 스레드 단위로 이뤄지므로 스레드 동기화라고도 함

 

2.3.2 목적

• 여러 프로세스들 또는 스레드들이 공유자원에 접근하는 순서에 따라 공유자원에 저장되는 값이 달라질 수 있음
  -> 프로세스 동기화는 상호 배제를 통해 공유자원에 저장되는 값의 일관성을 보장

 

 

3. 임계영역 문제 해결 방법

3.1.1 임계영역 문제 해결 방법을 설명하기 위한 기본 코드

• 여러 프로세스 또는 스레드를 기반으로 한 병렬 코드가 아닌 하나의 프로세스 또는 스레드를 사용하는 경우의 순차 코드

#include<stdio.h>

typedef enum {false, true} boolean;

extern boolean lock = false;    //전역변수(global variable)
extern int balance;             //전역변수(global variable)

void main() {
    while(lock == true);
    lock = true;
    balance = balance + 10;    //임계영역(critical section)
    lock = false;
}

 

 

3.2 임계영역 문제 해결 조건을 고려한 코드 설계(1)

3.2.1 상호 배제(mutex) 조건을 만족시키지 못하는 경우

• P1은 while(lock == true); 을 실행한 뒤 다음 문장을 실행하려는 순간 자신에게 주워진 CPU 사용시간 (time slice) 를 모두 사용(timeout)하여 문맥교환(P1 -> P2)이 이뤄짐
  - P1 : 실행상태 -> 준비상태, P2 : 준비상태 -> 실행상태
• P2은 while(lock == true); 을 실행한 뒤 다음 문장을 실행하려는 순간 자신에게 주워진 CPU 사용시간(time slice)를 모두 사용(timeout) 하여 문맥교환(P2 -> P1)이 이뤄짐
• P1 은 lock = true; 를 실행한 다음 임계영역에 진입함
• P2 은 lock = true; 를 실행한 다음 임계영역에 진입함
• 문제점
  - 상호 배제를 보장하지 못함

 

3.2.2 한정 대기 조건을 만족시키지 못하는 경우

• P1 은 lock1 = true; 을 실행한 뒤 다음 문장을 실행하려는 순간 자신에게 주워진 CPU 사용시간(time slice)를 모두 사용(timeout)하여 문맥교환(P1 -> P2)이 이뤄짐
• P2 은 lock2 = true; 을 실행한 뒤 다음 문장을 실행하려는 순간 자신에게 주워진 CPU 사용시간(time slice)를 모두 사용(timeout)하여 문맥교환(P2 -> P1)이 이뤄짐
• P2 가 lock2를 true로 설정하였기 때문에 P1은 while(lock2 == true); 에서 무한루프가 발생하여 임계영역에 진입하지 못함
• P1 가 lock1를 true로 설정하였기 때문에 P2은 while(lock1 == true); 에서 무한루프가 발생하여 임계영역에 진입하지 못함
• 문제점
  - P1과 P2는 무한정 대기 상태(교착상태) 이므로 한정 대기를 보장하지 못함

 

3.2.3 상호 배제와 한정 대기를 보장하지만 진행의 융통성을 보장하지 못하는 경우

• 위의 코드는 P1과 P2가 항상 서로 번갈아 가면서 실행됨
  - 한 프로세스가 두 번 연속으로 임계영역에 진입할 수 없음
  - P2는 임계영역에 진입할 필요가 없는데도 P2가 임계영역에 진입했다가 나와야 P1가 임계영역에 진입할 수 있음
  - P1는 임계영역에 진입할 필요가 없는데도 P1가 임계영역에 진입했다가 나와야 P2가 임계영역에 진입할 수 있음
• 문제점
  - 진행의 융통성을 보장하지 못함
  - busy waiting(상태변화를 확인하기 위해 반복문을 실행하며 기다림)이 존재하므로 계산 자원이 낭비될 수 있음

 

3.2.4 하드웨어적인 해결 방법

• 임계영역 문제 해결 조건을 고려한 코드 설계(1)의 소스 코드를 다음과 같이 수정
  - while(lock == true); 와 lock = true; 를 분리하지 않고 한 번에 처리하도록 하여 timeout이 발생하지 않도록 함
  - 이 경우 하드웨어적으로 두 명령어를 한 번에 처리하는 test-and-set 명령어(atomic operation)사용

• 장점
  - 상호 배제, 한정 대기, 진행의 융통성은 모두 보장
  
• 단점 
  - busy waiting이 존재하므로 계산 자원이 낭비될 수 있음

 

3.3 세마포어(semaphore)

※ 앞서 설명한 임계영역 문제 해결 알고리즘과 차이점

• 임계영역 문제 해결을 위한 조건(상호 배제, 한정 대기, 진행의 융통성)이 모두 보장됨
• busy waiting이 없으며 구현이 간단하고 사용하기 쉬운 일반적인 임계영역 문제 해결 방법

 

3.3.1 의사코드(pseudo code)

• 상호 배제와 프로세스 동기화를 위해 P()와 V()의 내부 코드는 실행 중 다른 코드가 실행되지 않도록 test-and-set 명령어를 사용하여 분리되지 않고 실행(atomic operation)되어야 함

 

3.3.2 GNU C library 를 통해 구현 가능

#include<semaphore.h>

sem_t S;
sem_init(&S, 0, n);   //Semaphore(n); 에 해당됨
sem_wait(&S);    //P();에 해당됨

//임계영역(critical section)
sem_post(&S);    //V();에 해당됨

 

 

3.3.3 종류

• Counting semaphore
  - S의 초기값 >= 1 이며 S >= 0
  > 임계영역에서 동시에 실행가능한 프로세스 또는 스레드 수는 1개 이상
  - 일반적인 semaphore
• Binary semaphore
  - S의 초기값 = 1이며 S = 0.1
  > 임계영역에서 동시에 실행가능한 프로세스 또는 스레드는 1개
  - 상호 배제(mutex)와 프로세스 동기화를 위해 사용됨