[Operating System] Process Synchronization 1

Background

서로 다른 process가 shared data에 동시에 접근하게 되는 경우 문제가 발생할 수 있다.

위와 같이 여러 process가 동시에 동일한 데이터에 접근하게 되는 상황을 Race condition이라고 한다.

위의 c언어로 한 줄 짜리 코드를 실행하더라도 assambly어로 여러줄로 번역된다.

따라서 위의 assambly어를 교차로 실행하게 되면 한쪽의 연산 결과가 반영되지 않게 된다.

 

이러한 race conditions을 방지하기 위해 process 간의 synchronization이 필요

• synchronization이란 서로가 상대를 인지한 상태로 동작하는 것을 의미
• 이러한 synchronization은 os의 안정성을 높히지만 효율성은 낮추게 된다.
• 효율성(efficiency/speed)과 안정성(accuracy)의 trade-off 관계가 여럿 존재

위에서 각 process에서 shared memory에 접근하게 되는 코드 부분을 critical section이라고 한다.

critical section에서 발생하는 문제를 critical section problem이라고 한다.

Required properties for process sync

process synchronization을 수행하기 위한 algorithm이 충족시켜야 하는 특성이 존재

1. Mutual Exclusion

특정 process가 critical section에서 수행되고 있으면 다른 process는 critical section에 접근해서는 안된다.

2. Progress

현재 critical section에 실행되고 있는 process가 없다면 critical section을 실행하기를 원하는 process가 즉각적으로 수행될 수 있도록 해야 한다.

3. Bounded Waiting

각 process의 upper bound wait time이 존재해야 한다.

Naive Algorithm

flag 역할을 하는 shared variable을 이용해 현재 critical section의 이용 가능 여부를 확인

Naive 1

1. 현재 자신의 턴인지 확인하고 자신의 턴이라면 critical section을 수행하고 다음 process로 턴을 넘긴다.

위의 algorithm은 mutual exclusion은 만족하지만, progress를 만족하지 못 한다.

 

turn에 지정된 process만이 critical section에 진입할 수 있기 때문에, 현재 turn의 process가 critical section을 수행하지 않더라도 다른 process가 진입할 수 없기 때문에 progress 특성을 만족하지 못 하는 것이다.

위처럼 지정된 자신의 turn에만 process를 실행시킬 수 있는 방식을 Swap-turn이라고 한다.

Naive2

1. 현재 자신이 critical section에 들어가야 하는지를 flag[i]=true로 표시
2. 다른 process에서 critical section을 사용하고 있는지 또는 사용을 원하는지 확인
3. 다른 process에서 critical section을 사용하지 않으면 critical section 실행
4. critical section을 마치고 난 뒤 자신의 flag를 false로 변경

위의 algorithm 역시 mutual exclusion은 만족하지만 progress, bounded waiting은 만족하지 않는다.

만약 위의 코드에서 두 process가 flag[i] = true를 교차로 실행한다면 다음 while(flag[j])에서 두 process가 계속 대기하게 된다.

Peterson’s algorithm

위의 naive algorithm에서 첫 번째 algorithm의 경우 자신의 turn이 정해져 있어 progress를 만족하지 않은 반면, 두 번째 algorithm은 자신의 turn이 정해져 있지 않아 특정 상황에 무한 루프에 빠지게 된다는 문제점이 있었다.

 

peterson’s algorithm은 이러한 문제점을 해결하기 위해 위의 algorithm의 방식을 조합해 사용한다.

process가 2개인 경우를 가정

1. 자신의 flag를 true로 설정해 critical section에 들어가기 위한 의사표시를 한다.
2. 그리고 turn을 다음 process에 넘긴다.
3. 그 후 다음 process가 더 이상 점유하고 있지 않거나, 다음 process의 turn이 끝난 경우 critical section으로 넘어간다.
4. 자신의 critical section이 끝나면 flag를 다시 false로 설정한다.

while(flag[j] and turn==j)

• flag[j] 부분을 통해 현재 j process가 사용하지 않는 경우라면 자신의 turn이 아님에도 critical section을 실행함으로써 progress를 만족
• turn==j 부분을 통해 현재 j process가 사용을 원하더라도 자신의 turn인 경우 critical section을 실행함으로써 progress와 bounded waiting을 만족

개선점

1. program code의 모든 critical section에 위의 코드를 넣어야 한다는 단점이 있다.
   ⇒ 코딩의 편의성을 높히는 방법을 고안
2. process가 자신의 turn을 waiting하는 동안에도 cpu를 할당받아 기다리는 busy waiting이 발생
   ⇒ interrupt와 비슷한 방식으로 cpu를 할당받지 않고 필요한 때 동작하도록 하는 방법을 고안

편의성 증가

위의 Peterson’s algorithm의 개선점 중 편의성을 개선하기 위해 Lock을 이용하는 방식이 고안되었다.

lock이라는 shared variable을 이용해 현재 shared memory에 접근할 수 있는지를 나타낸다.

이러한 lock 방식을 이용해 코드를 간소화할 수 있게 된다.

 

하지만 해당 algorithm이 제대로 동작하기 위해서는 acquire lock과 release lock 부분이 오직 한 개의 process만 접근 가능하다는 전제가 필요하다.

⇒ 즉 lock 부분 code에 atomicity가 보장되어야 한다는 것

이러한 lock의 atomicity를 보장하기 위한 여러 방법들이 고안되었다.

Synchronization Hardware

가장 간단하게 atomocity를 보장하는 방법으로 해당 코드에서 interrupt를 disable함으로써 context switching이 발생하지 않도록 하는 것이다.

critical section에서는 I/O request가 발생하지 않으므로 context switching이 발생하는 경우는 timer interrupt에 의해서만 발생할 수 있다.

 

이러한 방식은 간단한 방식이지만 기존 round robin 기반의 cpu scheduling 정책을 무시하는 것이기 때문에 general한 solution이 되기 어렵다.

 

위의 방법 외에 modern machines에서는 hw 자체적으로 atomocity를 보장하는 instruction을 제공한다.

TestAndSet

기존 target값을 그대로 반환하면서 target값을 true로 변경시키는 연산

1. 첫 번째 process는 lock을 true로 변경한 뒤 false를 반환함으로써 critical section에 진입한다. : acquire
2. 다음 process도 동일하게 lock을 true로 변경하지만 true를 반환함으로써 while문을 돌게 된다. : loop
3. 첫 번째 process는 자신의 critical section이 끝나면 lock을 false로 변경한다. : release
4. while문을 돌고 있는 process는 lock이 false로 변경되었기 때문에 false를 반환하고 다시 lock을 true로 만들게 된다. : acquire

Swap

두 변수의 값을 바꾸는 연산

 

1. 첫 번째 process는 lock과 key값을 swap함으로써 lock에 true를, key에 false를 저장하게 된다. : acquire
2. key값이 false이므로 critical section으로 넘어가게 된다. : execute
3. 그 다음 process 역시 lock과 key값을 swap하게 되는데, 이 때 이미 lock값에 true가 저장되어 있기 때문에 key값도 계속 true로 유지되어 while문을 돌게 된다. : loop
4. 첫 번째 process가 critical section을 마치면 lock값을 false로 바꾼다. : release
5. while문을 돌고 있는 process는 lock값이 false로 바뀌면서 key값이 false가 되어 while문을 나와 critical section을 돌게 된다. : acquire

Semaphores

위의 hw를 이용한 lock의 atomicity의 경우 결국 hw 종속적인 기술이다.

semaphores는 software적으로 lock의 atomicity를 얻으려 하였다.

 

semaphore는 wait function P와 signal function V로 이루어져 있으며, P와 V 모두 atomicity가 보장되어야 한다.

 

P에서는 shared variable S의 값이 0이하인 경우 무한 loop를 돌면서 S값이 양수가 되었을 때 S값을 다시 음수로 만들고 종료한다.

V에서는 shared variable S값을 1증가시키고 종료한다.

이처럼 semaphores는 이전 peterson’s algorithm과 다르게 코드의 편의성을 증대시킬 수 있었지만, P,V 함수의 atomicity를 보장해줘야 하는 문제와 busy waiting 문제가 그대로 남아있다.

 

semaphores는 atomicity를 보장해주기 위해 P와 V함수에 peterson’s algorithm을 wrapping하였다.

💡 결국 peterson’s algorithm과 다른 것이 없어보이지만 critical section에 직접 peterson’s algorithm을 적용하는 것이 아니라 P, V 함수 내부에 algorithm을 적용함으로써 코딩할 때 신경을 쓰지 않고 코딩을 할 수 있게 되었다.
⇒ 편의성 증대

 

semaphores에서 busy waiting 문제를 해결하기 위해 Block/wakeup 방식을 적용

Block/wakeup

semaphores algorithm에서 현재 대기 중인 process를 linked-list로 관리함으로써 process들이 cpu를 점유하지 않고 seelping 상태에서 대기할 수 있도록 하였다.

따라서 기존 semaphore integer value만 있던 구조에서 process의 linked list를 위한 포인터를 포함한 구조체를 선언

• block : process를 sleep 상태로 만든 뒤 semaphore 구조체 linked-list에 넣는 연산
• wakeup(process) : semaphore linked-list에서 sleep 중인 process 중 하나를 선택해 wakeup시키는 연산
  ⇒ priority를 줘서 scheduling하는 형식으로 구현하는 것이 일반적

초깃값 S.value = 1

1. 첫 번째 process는 S.value를 1 줄이고 critical section으로 넘어간다.
2. 다음 process부터는 S.value를 1 줄이고 S.value가 0보다 작기 때문에 S의 linked list에 해당 process를 추가한 뒤 block을 한다.
3. 첫 번째 process가 critical section을 끝내면 V(S)를 호출해 S.value를 1증가시킨다.
4. S.value를 1증가시켰음에도 S.value≤0이라면 대기하는 process가 존재한다는 의미이므로 linked-list에서 process 하나를 선택해 wakeup해준다.

위처럼 S.value를 통해 현재 대기 중인 process가 몇 개인지 알 수 있는 semaphores를 counting semaphores 또는 integer semaphores라고 한다.

 

💡 P function 내부에서 각 process가 block되기 때문에 실제 P function에 동시에 접근한 process의 개수는 1개보다 더 많아질 수 있다. 하지만 이러한 경우 실제 runnable한 process는 1개이고, sleep에서 끝나자마자 P 함수를 나온다는 점에서 mutual exclusion하다고 볼 수 있다.

 

위와 같은 critical section problem 또는 race condition은 하나의 application에서 여러 process가 shared memory를 사용하는 경우에 주로 발생할 수 있지만(DBMS ..), 그 외에도 다양한 환경에서 발생이 가능하다.

1. Interrupt Handler and Kernel

interrupt handler와 kernel 연산이 동시에 실행되는 경우에도 critical section problem이 발생할 수 있다.

interrupt handler와 kernel 모두 동일하게 kernel space에서 동작하기 때문에 kernel에서 kernel variable인 count 변수를 증가시키는 도중에 interrupt handler에 의해 count값이 접근되는 critical section problem이 발생할 수 있다.

 

결국 이러한 문제를 방지하기 위해 kernel variable을 수정할 때 앞 뒤로 interrupt disable 코드를 삽입하게 된다.

2. Kernel이 system call을 수행하는 도중 context switching이 발생하는 경우

process A가 system call에 의해 kernel mode에서 kernel 변수 count를 접근하는 와중에 context switching이 발생해 process B가 수행되어 process B에서 kernel 변수 count를 접근하게 되는 경우 critical section problem이 발생할 수 있다.

 

UNIX에서는 이러한 문제를 해결하기 위해 process A의 kernel mode가 종료될 때까지 context switching을 지연시킨다.

3. multiprocessor 환경

multiprocessor 환경에서는 여러 processor에서 하나의 kernel memory에 접근할 수 있기 때문에 critical section problem이 발생하기 쉽다.

이러한 문제를 해결하기 위해 kernel 전체를 atomic하게 만들거나 memory에 접근하는 부분을 atomic하게 만든다.

 

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님