[OS] process synchronization

sujin·2023년 6월 2일

Process Synchronization

Process 동기화를 왜 진행해야하는지 그리고 어떻게 동기화를 할 수 있는지 알아보도록하자! 동기화 기법을 이해하고 어떤 운영체제에서 어떤 알고리즘 기법을 사용하고 있는지 알아보도록하자!

Background

concurrent Access(동시접근)으로부터의 일관성 문제가 발생할 수 있다.
동시에 접근할 때 일관성 문제가 발생할 수 있는데 일관성이란 언제 어디서든 어떻게 접근을 하던지 그 값이 동일해야한다는 특성이지만 동시에 접근했는데도 일관되지 않은 값을 가질 수 있다.

공유하고 있는 변수 혹은 데이터에 대해서 동시에 process간에 접근이 간능하다면?
동시에 접근이 가능하다는 것은 synchronization이 적용되지 않았으며 async한 상태를 의미한다.대기 없이 접근을 한다는 것이기 때문이다.

따라서, 동시에 접근을 한다면 data inconsistency problem이 발생할 수 있다.

Orderly execution으로 순서화

동기화를 맞추기 위해서 우리는 어떻게 해야할까? 차례대로 접근을 하게끔 한다면 동시에 접근하지 못할 것이다. 즉, 순서를 부여하는 과정을 거치면 된다는 것이다.
count라는 광역변수(공유변수)를 사용해서 차있는 버퍼 공간의 개수를 담아놓고 실행되면 consumer가 count변수를 1씩 감소하고 producer가 1씩 증가시키는 로직처럼 사용한다.

위의 경우는 예제이고 동기화를 위한 알고리즘은 여러개 존재하는데 밑에서 알아보도록하자!!

Race condition

race condition이란? 실행중에 어떤 작업이 마지막에 실행됐냐에 따라서 변수의 값이 변경되는 것을 의미한다.

예를 들어서 count++과 count--연산이 존재할 때 두개가 count를 공유하고 있는데 이때, 동시에 각 execution이 들어왔고 count=5인 상태였다면?

만약 count++연산이 먼저 실행된 경우에는 5->6 그리고 count--로 인해서 6->5로 그 결과가 5가 나와야한다. 그러나, critical section이 count++의 coutn = register1값을 처리하기 전에 먼저 발생하여서 resigeter2의 count값에 6이 담기는 것이 아니라 5가 담겨서 결국 count--의 결과가 4가 나오게 된다.

count++을 실행하는 도중에, count--가 실행되어서 발생한 문제이다.

이렇게, 동시에 접근을 해서 race condition이 발생할 수 있는 여지가 생기고 어떤 프로세스가 먼저 실행되냐에 따라서 공유변수의 값이 달라져서 일관성 문제가 발생한다.

general structure for process Pi

process는 모두 1. Entry Seciton 2. Critical section3. Exit Section이 존재한다.
critical section이 가장 중요한데, "공유변수"의 값이 접근 혹은 수정하는 로직이 담겨있기 때문이다.
process는 entry section -> critiacl section -> exit section 의 순서대로 실행된다.

그렇다면 경쟁적 조건을 방지하기 위해서 공유변수에 동시에 접근하지 못하도록 해야하고 그렇다는 것은 프로세스별로 critical section이 있을 때 공유변수가 같다면 순서를 부여해서 동시에 critical section에 동시에 접근하지 못하도록 해야할 것이라고 생각을 들었을 것이다.

solution 알아보기

critical section에 하나의 프로세스만 접근하도록하는 3가지 조건이 존재한다.

Mutual Exclusion : 상호 배제

상호배제 조건은 하나의 process가 critical section에 들어갔다면 다른 프로세스는 critical section에 접근이 불가능하다는 것을 의미한다.

Progess : 지속적 스텝 진행

critical section이 비었을 때 특정 프로세스를 선정해서 들어갈 수 있도록 만들어주는 작업이 연기 되어서는 안 된다는 조건이다.
만약 지속적으로 이루어지지 않고 무기한으로 계속 기다리게된다면 deadlock에 빠지게 될 것이다. 따라서 적절한 방법을 활용해서 지속적으로 process가 ciritcal section에 하나씩 들어갈 수있도록 스케줄링을 진행해줘야한다.

Bounded Waiting : 한정된 만큼만 기다리기

n번에 언젠가 한번은 critical section에 process가 실행될 수 있도록 보장되어야한다는 것을 의미한다.
예를 들어서 process 5개가 경쟁한다면? 모든 프로세스들이 5번중에서 1번은 들어갈 수 있어야한다.
그렇지 않는다면 starvation문제에 빠지게 될 것이고 그렇다면 이 역시 deadlock에 걸리게 될 수 있다.

peterson의 솔루션

동기화 솔루션 3가지를 만족하는 방법이다.
다만, 2개의 프로세스 사이에서만 적용이 가능하다는 특징을 가진다.
Load, Store instruction은 automic해서 쪼갤 수 없는 특성을 가지기 때문에 interruption이 들어오지 않는다는 특징을 가진다.

2가지 변수를 활용한다.

turn: 임계 영역에 접근할 차례인 프로세스를 나타내는 변수입니다.
flag: 각 프로세스가 임계 영역에 진입하고자 하는 의사를 표시하는 변수입니다.

critical section에 진입하기 전에는 turn을 사용해서 서로 차례를 기다린다.

section

entry : turn과 flag를 사용해서 본인의 차례가 아니라면 whlie문을 계속 돌게 되어 상호배제를 만족시킨다.
ciritcal section
entry section : progress조건과 bunded waiting을 처리하기 위해서 flag를 (준비됨을 나타내는 bool값)을 false로 변경하여 상대방의 process가 실핻욀 수 있도록 한다.

Bakery Algorithm

번호표를 부여해서 순서를 제공하는데, 번호표가 동일하다면 process id값을 비교해서 먼저 생성된 것을 먼저 실행시킨다.
(ticket processId) 쌍으로 번호표가 부여된다.
ticket이 더 우선권을 가지고 동일하다면 processId를 활용한다.
따라서, (a,b) < (c,d) 를 만족하게 될 때 먼저실행된다.

choosing, number를 공유한다.

choosing : 번호표를 받는 과정인지 아닌지를 나타내는 Boolean값으로 자기자신이 번호표를 받는 과정에서 번로표를 비교하지 못하도록 번호표가 할당받고 나서 비교를 하도록해줄 때 사용한다.

number : Integer값으로 초기값은 0이다.

section

Entry section

do {
	choosing[ i ] = true;
	number[ i ] = max(number[0], number[1], …, number [n – 1])+1;
	choosing [ i ] = false;
	for ( j = 0; j < n; j++) {
	while (choosing[ j ]) ;
	while ((number[ j ] != 0) && (number[ j ], j) < (number[ i ], i)) ;
}

choosing을 사용해서 true일 때 다른 프로세스와의 번호표를 비교하지 못하도록 설정한다.
number는 지금까지의 number중에서 가장 큰 max값 +1을 할당한다.
process(i)를 기준으로 동작한다고 하면, (number[j],j) 가 더 커야 i가 우선순위가 더 높은 것이기에 entry section을 나와서 critical section에 접근할 수 있게된다.

Critical section
Exit section

number[i]를 0으로 해서 다른 쪽의 프로세스가 while문에 걸리지 않도록한다.

Synchronization Hardware

CPU가 하나일때 interrupt를 끄고 critical section에 들어간다면 문제가 해결될 것이다. 하나의 critical section에 들어간다.
단점 : CPU가 여러개가 있을 때 interrupt를 계속 on, off한다면 too inefficient하다는 특징이 있다. 시스템의 확장성에 문제가 생길 수밖에 없다.

atomic instruction = non interruptable
- Test and Set -> entry section에 활용
- swap
  
  두가지 방법을 사용할 수 있다.
1. Test and Set은 target(lock) 으로 초기값이 false가 설정이 되어있고 그 경우 return값은 false이고 target은 true로 변경된다. target이 true이면 이후에는 return값이 true가 된다.
  이때, return값은 flase여야 while문에 걸리지 않아서 무한 루프를 돌지 않고 정상 수행이된다. 다만, busy waiting처리를 진행한다. lock이 false일 때 풀리게 된다. exit 섹션을 통해서 lock을 false로 변경해 Progress역시 만족한다.
  다만, Bounded Waiting 조건은 만약 프로세스가 2개 이상일 경우에는 실행중이던 것은 lock이 true이 false가 되었을 때 기다리던 것들중에서 재수 좋게 하나만 critical section에 들어간다. 따라서 랜덤으로 그때그때 선택된 프로세스가 실행되기 때문에 순서 보장을 시켜주지 않아서 Bounded 조건은 만족하지 못한다.
2. Swap Instruction
  
  서로의 권한을 변경하는 코드이다. 공유변수는 Lock이고 초기값을 false로 가진다. key는 local 변수로 pi안에서만 인정된다.
  전체 code를 보면,lock이 false이고 key가 true일 때 서로 값이 변경되어 key가 fasle가 되어 while문을 빠져나오고 critical section에 들어가게 된다. 이후, exit section에서 lock이 fasle가 되어 progress조건을 만족시킨다.
  그러나 마찬가지로 2개 이상의 프로세스에서 순서 보장이 되지 않는다.
  2개 이상의 프로세스 : if 4개였다면 lock이 False일 때 바뀌는데 기다리던 3개중에 랜덤(3개에 모두 기회를 준것이기에 순서를 보장하지 않음)으로 하나만 재수좋게 critical section에 들어간다. 따라서 보장은 시켜주지 않기에 Bounded 조건은 만족하지 않는다.
  
  세마포어
  
  가장 일반적인 동기화 알고리즘으로 세마포어를 사용한다.
  가장 큰 특징은 busy waiting이 필요없다는 것이다. busy waiting이란? while문을 사용한 do nothing처리를 의미한다.
wait, signal

wait operation -> s<=0 일때 entry() section에서 막아준다.
signal operation -> s++ loginc으로 exit() section을 처리한다.

signal, wait을 사용하면 "순서부여"가 가능하다.
이때, single CPU의 경우에는 interrupt만 단순히 막으면 되지만, multiple CPU의 경우에는 spinlock을 사용해야한다.

critical section의 작업이 오랫동안 발생한다면? 차라리 busy waiting을 하기보다는 context switching을 하는 것이 낫다고 볼 수 있다. (queue에서 waiting하는 프로세스를 처리하는 과정)
만약에 critical section이 코드가 짧거나 가끔 발생한다면? busy waiting방식이 더 좋을 수 있다.
위의 두가지를 고려하여 더 좋은 것을 사용한다.

세마포어 구현
waiting : queue에 넣어서 block처리를 진행. code는 wait영역에 존재한다.
signal. exit section으로 wakeup -> queue에서 가져오는(remove처리) 이후 동작
value : 1로 시작해서 처음 동작때는 block 처리되지 않는다.