Home Process synchronization
Post
Cancel

Process synchronization

Posted Jul 17, 2022 Updated Jul 17, 2022
By baekbumsung
19 min read

Inter-Process Communication

  • 프로세스 간 통신이다.
    • 즉 프로세스들이 데이터를 주고 받는 행위와 경로, 방법을 논한다.

IPC의 종류

  1. 프로세스 내부 데이터 통신
    • 하나의 프로세스 내에 2개 이상 쓰레드가 존재할 때
    • 전역변수나 파일을 이용
  2. 프로세스 간 데이터 통신
    • 공용 파일 혹은 OS의 파이프를 이용한다.
  3. 네트워크를 이용한 데이터 통신
    • 여러 컴퓨터가 네트워크로 연결된 경우
    • 소켓을 이용한다.

네트워킹 : 소켓을 이용한 통신

한 컴퓨터 내 에서는 소켓보다는 다른 방법으로 통신한다.

IPC의 분류

통신 방향에 따른 분류

  1. 양방향 통신
    • 양쪽으로 데이터를 동시에 전송 가능한 구조
    • 소켓 방식이 있다.
  2. 반양방향 통신
    • 양쪽으로 전송 가능하나 동시 전송이 불가능하다.
    • 특정 시점에 한 방향으로만 전송 가능하다.
  3. 단방향 통신
    • 한쪽으로만 전송 가능한 구조이다.
    • 프로세스 간 통신에서는 전역 변수, 파이프가 해당한다.

전역변수는 양쪽에서 데이터를 지정할 때 하나만 적용된다.

통신 구현 방식에 따른 분류

busy waiting

  • 받는 쪽에서 보낸 데이터가 있는 지 계속 확인하는 상태를 말한다.
    • 무한 반복으로 수시로 변수 값을 확인한다.
    • 오버헤드가 크다.

synchronization

  • 위 문제를 위해 데이터가 도착했음을 알려주는 동기화가 필요하다.
  • 이는 대기가 있는 지에 따라 동기화 여부를 나눈다.
  1. 대기가 있는 통신 ( 동기화 )
    • 파이프, 소켓
  2. 대기가 없는 통신 ( 비 동기화 )
    • 전역 변수, 파일

IPC의 종류

  • 기본적으로 쓰기, 읽기로 간소화 할 수 있다.

전역 변수를 이용한 통신

  • 직접적인 관련이 있는 프로세스에서 사용한다.
  • 전역 변수를 이용해 읽고 쓰기를 진행한다.
  • 다만 받는 입장에서는 전역변수가 바뀌었는지 계속 확인해야 한다.
    • busy waiting 문제

파일을 이용한 통신

  • 파일을 open, write, read, close 연산을 통해 사용한다.
  • 부모 자식 간 통신에 많이 사용된다.
  • OS가 동기화를 지원하지 않는다.
    • 프로세스 수준에서 wait를 이용하여 동기화를 진행한다.
    • 자식을 기다림

파이프를 이용한 통신

  • 파이프
    • 운영체제가 제공하는 동기화 통신
    • open, close 이용
  • 단방향 통신
  • 파이프의 종류
    • 이름 없는 파이프
      • 부모 자식 간, 형제 사이 등 관련 있는 프로세스 간 통신
    • 이름 있는 파이프
      • FIFO라는 특수 파일 이용, 관련 없는 프로세스 간 통신

소켓을 이용한 통신

  • 소켓을 이용한 통신은 네트워크를 통해 다른 컴퓨터와 연결 가능하다.
  • 동기화를 지원하며 하나의 소켓으로 양방향 통신이 가능하다.

Shared resource & Critical Section

Shared resource

  • 여러 프로세스들이 함께 이용하는 자원을 말한다.
  • 자원은 cpu가 될 수도 있고 메모리가 될 수도 있다. ( 이외 여러가지 )

Race Condition

  • 여러 프로세스가 동시에 자원에 접근해 경쟁 하는 상태를 race condition이라 부른다.
  • 이는 예상치 못한 결과를 야기한다.

Critical section

  • 둘 이상의 프로세스(쓰레드)가 동시에 접근하면 안되는 공유 자원을 접근하는 코드의 일부를 이야기한다.
  • 즉 병렬 실행 중 한 프로세스(쓰레드)만 유일하게 실행할 수 있는 코드 부분을 이야기한다.

해결 조건

  • 위와 같은 공유 자원을 동시에 접근하는 행위는 문제를 일으킨다.
  • 이를 해결하는 여러 방법이 나왔고, 이때의 조건이 있다.
  1. mutual exclusion
    • 한 프로세스가 임계구역에 들어가면 다른 프로세스는 들어가지 못한다.
  2. bounded waiting
    • 무한 대기가 발생하면 안된다.
    • 데드락 관련 문제
  3. progress flexibility
    • 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

Solutions

H/W

  • 하드웨어 수준에서 Mutual Exclusion을 해결하는 방법이다.
  • 단순한 코드 한 줄을 실행하는 것도 여러 단계의 어셈블리 언어를 통해 작동된다. ( 위에 “왜 문제가 될까?” 글 참고 )
    • 이때 context change가 발생하면 문제가 생긴다.
  • 그래서 이에 대한 해결책으로 기계어를 묶어버리는 것이다.
    • 즉 원자성을 보장함
  • 이를 ‘‘Special Instructions’’ 라고 부른다.
  • 다음과 같은 명령어가 있다.
    • test and set
    • fetch and add
    • compare and swap
    • etc
  • 이를 이용해서 Mutual Exclusion, semaphore를 구현할 수 있다.
  • 문제점
    • busy waiting
    • dead lock

Compare and wait

1
2
3
4
5
6

compare_and_swap(int *word, int testval, int newval){
	int oldval;
	oldval = *word;
	if(oldval == testval) *word = newval;
	return oldval;
}

  • word 값이 testval 과 같으면 newval로 교체함

  • 이를 이용해 mutual exclusion을 구현해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const int  n = number of processes
int bolt; //락 변수 
void p (int i){
	while(1){
		while(compare_and_swap(&bolt, 0, 1) == 1)
			/* do nothing */
		// critical section
		bolt = 0;
		// remainder
	}
}

void main(){
	bolt = 0;
	parbegin(p(1), p(2), ... p(n));
}
  • 하나의 프로세스에서만 while문을 통과한다.
  • 이후 임계 구역을 지나고 다시 bolt를 0으로 수정한다.
  • 이후 하나의 프로세스만 while문을 통과한다.

Exchange

1
2
3
4
5
6

void exchange(int *register, int* memory){
	int temp;
	temp = *memory;
	*memory = *register;
	*register = temp
}
  • 이를 이용해 mutual exclusion을 구현해보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const int  n = number of processes
int bolt; //락 변수 
void p (int i){
	int keyi = 1;
	while(1){
		do exchange(&keyi, &bolt)
		while(keyi != 0)
		
		// critical section
		bolt = 0;
		// remainder
	}
}

void main(){
	bolt = 0;
	parbegin(p(1), p(2), ... p(n));
}
  • 하나의 프로세스에서만 while문을 통과한다.
  • 이후 임계 구역을 지나고 다시 bolt를 0으로 수정한다.
  • 이후 하나의 프로세스만 while문을 통과한다.

Special Instructions

  • atomic instructions

    장점

  • 멀티 프로세스에서도 share resource가 가능하다.
  • simple
  • multiple 임계 구역을 지원한다.
    • 여러 변수 이용

단점

  • busy working
  • starvation
  • dead lock
    • 만약 p1이 임계 구역에 들어갔을 때 interrupted 당하고 p2가 우선순위가 높아 실행되어 버림
    • p2는 mutual exclusion 때문에 loop를 돌게됨
    • 그러나 p1은 낮은 우선순위로 p2를 기다리게됨

Semaphore

  • 뭔가 소프트웨어적 이상적인 구현 방법이 없을까?
    • 다익스트라 등장!
  • 추상적인 세마포어 변수를 이용한 알고리즘
    • V operation (‘signal’)
      • increment the semaphore
    • P operation (‘wait’)
      • decrement the semaphore

type of semaphore

  1. Binary semaphore
    • 0, 1 (locked, unlocked)
  2. Counting semaphore
    • 임의의 값

def

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

struct semaphore{
	int count; // 이때 count 값은 공유 가능한 자원의 수를 나타낸다. 
	queueType queue;
};

void semWait(semaphore s){
	s.count--;
	if(s.count < 0){ // 남은 자원이 없음
		// place this process in s.queue
		// block this process
	}
}

void semSignal(semaphore s){
	s.count++;
	if(s.count <=0 ){ // 남은 프로세스가 있음
		// remove a process P from s.queue
		// place process P on ready list
	}	
}

만약 프린터가 2개면 세마포어 값은 초기에 2이다.

양의 값을 남은 자원

음의 값을 대기 중인 프로세스라고 생각하면 편한 것 같다.

Ex

mutual exclusion

  • 이를 이용해 mutual exclusion을 구현해보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

const int n = number of process
semaphore s = 1;
void P(int i){
	while(1){
		semWait(s);
		// critical section
		semSignal(s);
		// remainder
	}
}

void main(){
	parbegin(P(1), P(2), ... P(n));
}

  • 세마포어는 하드웨어적으로 구현하기 불가능하다.
    • 하지만 결국 구현 시 atomic instruction을 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

semWait(s){
	while(compare_and_swap(s.flag, 0, 1)==1){}
	// do nothing
	s.count--;
	if(s.count < 0){
		// place this process in s.queue
		// block this process (must also set s.flag to 0)
	}
}

semSignal(s){
	while(compare_and_swap(s.flag, 0, 1)==1){}
	//do nothing
	s.count++;
	if(s.count <= 0){
		// remove a process p from s.queue
		// place process p on ready list
	}
}
  • 소프트 웨어 적으로는 피터슨과 테커 알고리즘으로 구현된다.

데커는 하드웨어 도움이 필요 없지만 피터슨은 필요로 한다.

Producer/Consumer Problem

  • 여러 문제 중 여러 명의 producer와 한 명의 consumer를 가정해보자.
  • producer나 consumer 든 한 사람만이 특정 시간에 버퍼에 접근 가능하다.
  • 빈 버퍼에서 가져오거나 가득 찼는데 채우는 문제를 고려해야 한다.

program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

semaphore n = 0, s = 1; 
// n은 물건 개수, s는 critical section
void producer(){
	while(true){
		produce();
		semWait(s);
		append();
		semSignal(s);
		semSignal(n);
	}
}

void consumer(){
	while(true){
		semWait(n); // n이 0보다 크면 consume 가능
		semWait(s);
		take();
		semSignal(s);
		consume();
	}
}
void main(){
	parbegin(producer, consumer);
}
  • 두 개의 세마포어를 사용한다.
  • 처음에는 n이 0개 이므로 consumer는 실행이 되지 않는다.
  • 이후 생산자에서 n 시그널을 보낸다.
  • consumer는 1차 벽을 통과하지만 만약 producer가 critical section에 있으면 wait한다.
  • 이후 take한다.

Quiz

  1. 만약 producer에서 semSignal의 s와 n의 순서를 바꾸면?
    • 상관 없다.
  2. 만약 producer에서 semWait의 n과 s의 순서를 바꾸면?
    • 데드락이 걸린다.
    • consumer가 먼저 임계 구역에 들어감
    • 하지만 n으로 인해 waiting
    • 그러나 producer또한 s로 인해 waiting

Monitor

semaphore의 단점

  • 세마포어로는 프로그램을 개발하기 어렵다.
    • 프로그래머의 실수로 임계 구역이 보호 받지 못할 수도 있다.
  • 전체 프로그램을 파악하기 어렵다.

monitor

  • 프로그래밍 언어에서 제공하는 기능이다.
    • semaphore 대체 가능하다.
    • 사용자는 걱정을 안해도 된다.
  • 모니터는 기본적으로 하나 혹은 이상의 procedures로 되어있다.
    • 초기화 코드와 지역 변수도 있다.
  • 한번에 하나의 프로세스만 모니터 안에서 실행 가능하다.
    • mutual exclusion
  • 모니터 안에 정의된 변수는 모니터 안에 지정된 procedures로만 접근 가능하다.

condition variable

-모니터는 동기화를 위해 상태 변수를 사용한다.

  • 다음과 같은 함수로 계산된다.
    • cwait( )
      • 프로세스를 대기 시킴 ( 특정 컨디션까지 )
    • csignal( )
      • blocked 된 프로세스를 깨움 ( 같은 컨디션에서 )
      • 만약 대기 중인 프로세스가 없으면 아무것도 안 함

  • 코드를 보면 이해하기 좋다.

  • 모니터의 코드

    • 모니터 안의 함수를 사용하여 안에서 작업한다.
    • 이 코드 실행은 하나의 프로세스만 가능함을 보장한다.
      • 즉 wait가 걸리면 위 그림처럼 대기 타야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

monitor boundedbuffer; // 모니터 코드
char buffer[N]; // space for N items
int nextin, nextout; // buffer pointers
int count; // number of items in buffer
cond notfull, notempty; // conditional var for synch

void append(char x){
	if(count == N) cwait(notfull); // buffer is full?
	// full -> notfull일때까지 wait
	
	buffer[nextin] = x;
	nextin = (nextin+1)%N;
	count++;
	// one more item in buffer
	csignal(notempty); //resume any waiting consumer
	//누군가 notempty를 기다리면 wake up 시킴
}

void take(char x){
	if(count==0) cwait(notempty); // buffer is empty?
	//count==0 이면 notempty  까지 wait
	x = buffer[nextout];
	nextout =  (nextout+1)%N;
	count--;
	csignal(notfull); // resume any waiting producer
	nextin = 0; nextout = 0; count = 0; // buffer initially empty
}
  • producer와 consumer의 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void producer(){
	char x;
	while(1){
		produce(x);
		append(x);
	}
}

void consumer(){
	char x;
	while(1){
		take(x);
		consume(x);
	}
}

void main(){
	parbegin(producer, consumer);
}

Message passing

  • 가장 일반적이고 쉽다!
    • mutual exclusion
    • synchronization
    • communication
    • 모두 가능
  • shared mem, distributed mem 모두 가능

    Function

  • send (dest, msg)
  • receive (dest, msg)

Communication

  • 둘 간에 동기화가 된다는 것을 의미함
  • 리시버는 다른 프로세스가 보내기 전까지 받지 못한다.

Blocking, nonblocking sender, receiver

  • blocking
    • sender
      • 받을 때까지 기다림
    • receiver
      • 보낼 때까지 기다림
  • non
    • sender
      • 그냥 보내버림
    • receiver
      • 그냥 포기해버림
  • 보통 non send, blocking receive 사용한다.

Addressing

  • direct
    • 명시해서 보내거나 받음
    • 아무한테나 받아서 리턴함
  • indirect
    • 메일 박스에 보내버림 ( 홀드 )

Mutual exclusion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const int n = number of processes;
void p(int i){
	message msg;
	while(ture){
		receive(box, msg); // 메시지는 하나만 받을 수 있음
		// critical section
		send(box, msg);
		// remainder
	}
}

void main(){
	create mailbox box;
	send(box, null);
	parbegin(p(1), p(2),...p(n));
}

Producer Consumer with msg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

const int cap = buffering cap;
const int null = empty msg;
int i;
void producer(){
	message pmsg;
	while(1){
		receive(mayproduce, pmsg); // 못 받으면 blocking
		pmsg = produce();
		send(mayconsume, pmsg);
	}
}

void consumer(){
	message cmsg;
	while(1){
		receive(mayconsume, cmsg);
		consume(cmsg);
		send(mayproduce, null);
	}
}

void main(){
	create_mailbox (mayproduce);
	create_mailbox (mayconsume);
	for(int i=1;i<=cap;i++) send(mayproduce, null);
	parbegin(producer, consumer);
}
CS, OS
os cs summer
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents