[ 운영체제 ] Process Synchronization ( 1 )

 

 

 

데이터의 접근

 

 

컴퓨터 내에서 발생하는 연산은 아래와 같은 과정을 거친다

 

Storage-Box(S-Box)에서 사용할 data를 꺼내오고

Execution-Box(E-Box)에서 꺼내온 data로 연산을 한 뒤

Storage-Box(S-Box)에 다시 넣는다

 

 

이때 E-Box에서 S-Box에 동시에 접근하는 상황이 발생하면

data를 일관되게 유지하는 데에 문제가 생길 수 있다

이러한 문제를 Race Condition이라고 한다

 

E-Box가 S-Box에 동시에 접근하게 되는 경우는 크게 두가지가 있다

-  Multiprocessor(CPU가 여러 개일 때)

    :  서로 다른 CPU의 서로 다른 Process가 동시에 Kernel Memory의 data에 접근한 경우

-  Multiprocess(Process가 여러개일 때)

    :  서로 다른 Process가 Shared Memory를 사용할 때 동시에 Shared Memory 내의 data에 접근한 경우

 

Process는 각자의 독립된 주소 공간을 가지고 그 주소 공간 내에서만 연산하기 때문에

공유되는 메모리 - kernel memory, shared memory에서만 Race Condition이 발생한다

 

 

 

OS에서의 Race Condition

 

1 )  Kernel 수행 중 Interrupt 발생 시

Process에서 kernel의 data를 접근하고 연산할 때

1. load (register에 data 가져오기)  2. 연산  3. store(memory에 연산 결과 저장하기)

위와 같은 과정을 거친다

 

이때 Process A가 1번까지만 수행하고 interrupt에 의해 CPU를 뺏긴 뒤

Process B가 같은 data에 접근 및 연산하면

data의 일관성은 파괴된다

 

해결 방안

Process에서 kernel의 data에 접근하면 interrupt를 disable하고 연산이 끝난 뒤 다시 enable시키기

 

 

2 )  Process가 System Call을 하여 Kernel Mode로 수행 중인데 Context Switch가 발생한 경우

앞서 말한 대로 kernel의 데이터 접근 및 연산은 load>연산>store의 과정을 거치는데

 

Process A에서 System Call을 통해 kernel의 data에 접근하고 load까지만 한 상태로

Context Switch에 의해 CPU를 Process B에게 빼앗긴 뒤

Process B가 또다시 System Call을 통해 동일한 data를 연산하게 되면

이 data의 일관성은 파괴된다

 

해결 방안

Kernel Mode에서 수행 중일 때는 CPU를 preempt 하지 못하도록 함
User Mode로 돌아갈 때 CPU preempt하도록

 

 

3 )  Multiprocessor에서 Shared Memory 내의 Kernel Data

Multiprocessor 환경에서 서로 다른 CPU에서의 서로 다른 Process가 shared memory에 동시에 접근하면

race condition이 발생한다

Multiprocessor 환경에서 발생한 race condition은 CPU가 서로 다른 상황이기 때문에

interrupt나 CPU preempt를 막는 것으로는 해결되지 않는다

 

해결 방안

1.  한번에 하나의 CPU만이 Kernel에 들어갈 수 있도록
    :  but, 과도한 overhead / 비효율적
2.  커널 내부에 있는 각 공유 데이터에 접근할 때마다 해당 데이터에 대한 lock/unlock을 하는 것

 

 

 

Process Synchronization 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 매커니즘 필요

 

Race Condition

: 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황

load > inc > store가 원자적으로 한번에 이루어진다면 문제가 발생하지 않겠지만

보통의 경우 저 과정은 분리되어 일어나기 때문에

중간에 CPU를 빼앗기는 상황이 발생할 수 있다

( ex - load만 하고 CPU 빼앗기기 )

 

 

Critical - Section Problem

 

critical - section : 공유 데이터에 접근하는 코드 부분

race condition이 발생하지 않으려면 이 critical-section에 하나의 Process만 들어가도록 해야 한다

 

프로그램적 해결법의 충족 조건

• Mutual Exclusion (상호 배제)
  :  critical section에 오직 하나의 Process만 들어갈 수 있어야 한다
• Progress(진행)
  :  아무도 critical section에 있지 않을 때 들어가고자 하는 Process가 있으면 critical section에 들어가게 해줘야 한다
• Bounded Waiting(유한 대기)
  :  critical section에 들어가고자 하는 Process가 요청을 보냈을 때 다른 Process들이 critical section에 들어가는 횟수에 제한이 있어야 한다

 

 

Initial Attempt

critical section 전후에 Process가 하나만 들어갈 수 있도록 작업

->  공유 변수(synchronization variable) 사용

 

Algorithm 1

turn(synchronization variable)으로 어떤 프로세스의 차례인지 명시

본인 차례 O

:  critical section 수행 -> 상대방 turn으로 변경

본인 차례 X

:  while 무한 루프 후 CPU 할당 시간 끝나면 빠져나감

 

critical section을 한번씩 순차적으로 주고받는 형태

Mutual Exclusion은 만족하지만 Progress는 만족하지 않음
=>  과잉양보 : 반드시 한번씩 교대로 들어가기 때문에 상대 프로세스가 내 turn으로 교체해줘야만 진입 가능
       만약, Process A가 B보다 훨씬 더 빈번하게 critical section을 사용한다면 낭비 발생

 

 

Algorithm 2

flag를 들어서 내 차례임을 명시

상대 깃발이 올라가있는 경우

:  while문 무한 루프

상대 깃발이 내려가있는 경우

:  critical section 수행 -> 내 깃발 내림

 

 Mutual Exclusion은 만족하지만, Progress는 만족하지 않음
=>  본인 깃발 들고 critical section 수행 전에 CPU 빼앗기면 서로 깃발만 들고 있는 상황 발생

 

 

Algorithm 3(Peterson's Algorithm)

내 깃발 들고 상대방 turn으로 전환

1 ) 상대 깃발이 들려 있고 2 ) 상대방 turn이면 무한 루프

상대 깃발이 내려가 있거나 상대방 turn이 아니면 critical section 수행

 

Mutual Exclusion, Progress, Bounded Waiting 모두 만족

but, Busy Waiting 
=> 내 turn이 아닐 때 while문 무한 루프