Process Synchronization: 프로세스 동기화 (1/2)

Concurrency: 병행 제어

프로세스는 각자의 주소 공간에만 접근 가능하다. (3)이 문제 없을 것 같지만 cpu가 여러개인 multiprocessor system이라면 문제 발생 가능

<Race Condition: 경쟁 상태>

1. A.count copy, 2. a.count++ 3. b.count copy 4. b.count-- 5.a.storage count+= 6. b.storage count--(덮어쓰기) 

A가 ++하는 동안 B가 count 가져가서 -1 한다면 -1뺀 결과만 저장된다. 원랜 0 저장되어야 하는데...

S-Box(Memory Address Space)를 공유하는 E-Box(CPU Process)가 여럿 있는 경우 Race condition(경쟁상태)의 가능성이 있다. 즉 여러 주체가 하나의 데이터에 동시 접근 하려고 할 때 경쟁 상태의 가능성이 있는 것이다.

* E - box?

  CPU Process: MultiProcessor System, 공유 메모리를 사용하는 프로세스들. 커널 내부 데이터를 접근하는 루틴들 간 예) 커널모드 수행 중 커널모드로 다른 루틴 수행할 때)

 

<OS에서 race condition은 언제 발생하는가?>

1. 커널 수행 중 인터럽트 발생 시

2. 프로세스가 시스템 콜을 하여 커널 모드로 수행중인데 문맥 교환이 일어나는 경우 (또 커널 데이터를 접근해야 하기 떄문에)

3. 멀티프로세서에서 shared data 내의 kernel data

 

1. 커널 수행 중 인터럽트 발생 시

1번 했는데 인터럽트 들어와서 인터럽트 핸들러로 인터럽트 처리한다. 그런데 인터럽트 핸들러도 커널 코드이므로 count-- 하는 등 count 변수가 변할 수 있다. 근데 이미 레지스터에는 복사해간 count 값 있으니까 그거 ++해서 다시 저장한다. 즉 count --한 것은 반영이 안되고 count++한 것만 반영이 되는 것이다.

※ 커널 모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행 -> 양쪽 다 커널 모드이므로 kernel address space를 공유하게 된다. 따라서 작업이 다 끝난 뒤에 interrupt를 받아들이고 작업중엔 무시하게 된다.

 

2. 프로세스가 시스템 콜을 하여 커널 모드로 수행중인데 문맥 교환이 일어나는 경우 (또 커널 데이터를 접근해야 하기 떄문에)

원래 두 프로세스의 address space 간에는 data sharing이 없다.

그러나 system call을 하게 되면 kernel address space의 data를 access하게 된다(share)

따라서 이 작업 중에 CPU를 선점 당하면 경쟁상태(race condition)이 발생한다.

 

time quantum expire & Pb가 CPU를 필요로 하면 Pa는 cpu를 선점당함(커널모드에서) 

Pa,Pb 둘다 count 1씩 증가시키니까 총 2 증가한 값이 반영되어야 하는데 Pa의 1 증가된 값만 반영된다.

해결책: 커널모드에서 수행중일 때에는 cpu를 preempt 하지 않는다. 커널모드에서 사용자 모드로 돌아갈 때 preempt한다.

 

3. 멀티프로세서에서 shared data 내의 kernel data

어떤 cpu가 마지막으로 count를 store 했는가 -> race condition

멀티 프로세서의 경우 인터럽트를 가능/불가능하게 하는걸로 해결되지 않는다.

해결방법 1: 한 번에 하나의 cpu만이 커널에 들어갈 수 있게 하는 방법

해결방법 2: 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법(카피해가기 전에 데이터에 락을 걸어서 다른 cpu가 변경 못하게 막음)

 

<Process Synchronization 문제>

공유 데이터의 동시 접근(concurrent access)은 데이터의 불일치문제(inconsistency)를 발생시킬 수도 있다.

* 일관성(consistency) 유지를 위해서는 협력 프로세스 (cooperating process)간의 실행 순서를(orderly execution)를 정해주는 메커니즘이 필요하다.

 

* Race Condition(경쟁상태)

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

- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다. 

- 경쟁 상태를 막기 위해서는 concurrent process는 동기화(synchronize) 되어야 한다.

사용자 프로세스p1 수행 중 타이머 인터럽트가 발생해서 문맥 교환 발생된뒤 P2가 cpu를 잡으면? 

그런데 여기서 한가지 주의할 점이, 단순히 프로세스 실행 중 context switch가 발생하는 것이 문제가 아니라, 프로세스는 각자의 주소공간이 잇는데 이를 벗어난 shared data 이거나 커널 주소공간 또는 커널 코드일 경우에 문제가 되는 것이다.

 

<The Critical-Section Problem: 임계구역>

* n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우 

* 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드(critical section)가 존재한다.

 

Problem

 -하나의 프로세스가 critical section에 있을 때 모든 프로세스는 임계구역에 들어갈 수 없어야 한다.

<Initial Attempts to solve Problem>

두 개의 프로세스가 있다고 가정 P0, P1

프로세스들의 일반적 구조

프로세스들은 수행의 동기화(Synchronize)를 위해 몇몇 변수를 공유할 수 있다. -> Synchronization variable

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

* Mutual Exclusion (상호 배제) (배타적)

- 프로세스 Pi가 크리티컬 섹션 부분을 수행 중이면 다른 모든 프로세스들은 그들의 크리티컬 섹션에 들어가선 안된다.

* Progress (진행)

- 아무도 크리티컬 섹션에 있지 않은 상태에서 크리티컬 섹션에 들어가고자 하는 프로세스가 있으면 크리티컬 섹션에 들어갈 수 있게 해줘야 한다.

* Bounded Waiting (유한 대기)

- 프로세스가 크리티컬 섹션에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 크리티컬 섹션에 들어가는 횟수에 한계가 있어야 한다. -> startvation 발생하면 안된다는 소리 프로세스 1,2,3 있는데 1,2만 맨날 들어가면 3은 언제 들어가...

* 가정 

모든 프로세스의 수행 속도는 0보다 크다

프로세스들 간의 상대적인 수행 속도는 고려하지 않는다. 

 

<algorithm 1>

프로세스 1은 turn이 0일때, 프로세스 2는 turn이 1일 때 크리티컬 섹션 진입 가능

이 알고리즘의 문제는 Mutual Exclusion은 만족하나 Progress를 만족하지 않는다는 점이다. 즉 과잉 양보가 발생하게 된다. 반드시 한번씩 교대로 들어가야 한다. 만약 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면?

 

<algorithm 2>

프로세스가 n개라면 n 크기의 flag 배열을 만든다. 둘 다 false로 초기화해주고 flag[0] = true로 본인이 크리티컬 섹션에 들어갈 것을 알림 만약 다른 프로세스가 크리티컬 섹션에 있어서 해당 배열의 인덱스가 true라면 wait 일 끝낸 뒤엔 flag 배열의 본인 인덱스 false 설정

이 알고리즘의 문제점은 Mutual Exclusion은 만족하나 Progress를 불만족 한다. 물 다 2행까지 수행했다면 끊임없이 양보하는 상황이 발생할 수 있다. 만약 flag[0] = true에서 cpu를 뺏겨서(타이머 인터럽트) process 2로 cpu가 넘어갔는데 2도 flag true로 바꿔주고 while문 들어가려니까 flag 0 이 true라서 대기하다가 타이머 인터럽트 걸려서 cpu 빼앗기고 1도 2가 flag 들었으니까 또 무한대기하고 아무튼 이렇게 수행이 이루어지지 않을 수도 있다.

 

<algorithm 3>

1과 2를 모두 합친 알고리즘 일단 나 크리티컬 섹션 들어갈거라고 1라인에서 flag 세팅해주고 turn 변수에다 상대방의 값을 넣어준다. 만약 상대방 turn에다가 상대방이 flag를 들고 있다면 나는 wait 그렇지 않으면 critical section 들어가기

이 방법은 3가지 조건을 모두 만족한다. (Mutual Exclusion, Progress, Bounded Waiting)

근데 단점이 Busy waiting(=spin lock)이다 while문을 계속 체크하면서 기다리다보니 계속 cpu와 메모리 자원을 잡아먹게 되어서 비효율적이다.

 

<Synchronization Hardware>

하드웨어적으로 Test & Modify를 atomic하게 수행될 수 있도록 지원하는 경우 앞의 문제는 간단하게 해결될 수 있다.

 

락 걸었는지(락이 1/true인지) test and set으로 한번에 확인하고 락 안걸렸으면 1로 바꾸고 들어가며 락 걸려있으면 기다리는 걸 한번에 하게 해주는 instrucion 위의 알고리즘들보다 훨씬 간결하다.