Process Synchronization1 - lock and unlock

컴퓨터 시스템 내에서 데이터가 접근되는 패턴:

1. storage box에 data가 저장되어 있다

2. 연산할 data를 가져온다

3. data 연산

4. 연산 결과를 다시 storage box에 저장한다

 

이럴때 발생할수 있는 문제점:

- count++하는 연산을 하는 도중 count--하는 연산이 들어올 경우, 아직 count++의 결과가 반영되지 않은 상태에서 count--를 한 값이 최종적으로 S-box에 저장되므로 count++의 결과가 누락됨

- 이런 경우를 Race Condition, 경쟁상태라고 함

- CPU가 여러개인 경우 같은 주소공간을 사용할수 있기 때문에 Race Condition이 발생할 수 있음

- 여러 프로세스가 주소공간을 공유하는 경우도 Race Condition이 발생할 수 있음

- 커널 프로그램의 경우 여러 프로세스에 의해 호출되기 때문에 Race Condition이 발생할 수 있음

ex) 커널모드 수행 중 인터럽트로 커멀모드 다른 루틴 수행시

 

OS에서 Race Condition이 일어나는 경우

 

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

- 고급언어에서 count++이 시스템 내부에선 1. 데이터 로드, 2. 연산, 3. 데이터 저장 이 순서대로 수행됨

- 커널에서 count++ 작업을 하던 도중, 1. data load부분까지만 했는데 인터럽트가 들어온 경우 해당 인터럽트를 먼저 수행한다

- 해당 인터럽트에서 count-- 작업을 한다

- 해당 인터럽트가 끝나고 다시 context switch가 일어나면 1. data load하는 작업은 끝났기 때문에 2,3번인 연산 후 데이터 저장하는 로직만 수행한다

- 이 경우 값이 동기화가 되지 않았기 때문에 count-- 작업이 누락된다

- 그래서 중요한 data(변수)를 연산하는 프로세스가 실행중일때는 인터럽트가 들어와도 바로 처리하지 않고 해당 작업을 다 끝내고 인터럽트를 실행하는 방식으로 문제를 해결함(disable interrupt)

 

 

2. Process가 시스템콜을 하여 커널 모드로 수행중인데 context switch가 일어나는 경우

- A, B 두 프로세스는 data를 공유하지 않음, 각자만의 data 주소 공간을 가지고 있음

- 이럴때는 유저 모드일때 preempt 당하는건 아무 상관 없지만, 커널 모드일때 preempt 당하면 Race Condition이 발생함

- 커널모드에 있을때는 preempt를 잠시 연기하고 유저모드로 돌아갔을때 preempt 하는 방법으로 해결한다

- 그래서 어떤 경우는 타이머 시간이 지나도 조금 더 쓰게될수도 있음

 

3. 2개 이상의 CPU를 사용중일때 같은 데이터를 건드리는 경우

- 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 거는 방법으로 해결한다

 

 

정리

- 두 프로세스가 공유하는 데이터가 있을때, 혹은 커널 함수를 실행중일때 race condition이 발생할 수 있음

- 특정 job을 수행중일때는 CPU가 빼앗기는걸 막는 등 실행 순서를 조절해주는 매커니즘으로 문제를 해결해야 함

 

Critical section, 임계구역

- 공유하는 데이터가 있을때 해당 공유 데이터를 수행하는 연산을 Critical section이라고 함

- 여기선 x=x+1이 critical section

- 이미 한쪽에서 critical section이 수행중이면 다른 프로세스에서 critical section을 수행할때 그걸 막아서 접근 못하게 해야됨

 

 

일반적인 프로세스 구조

- 공유 데이터를 접근하는 critical section과 접근하지 않는 remainder section이 있음

- 공유 데이터 이전, 이후에 entry, exit section을 두어 lock, unlock를 한다

 

이렇게 lock, unlock 방식으로 critical section 문제를 해결할때 충족해야할 조건:

1. Mutial Exclusion, 상호배제: 이미 한 프로세스가 critical section에 들어가 있으면 어떠한 프로세스도 그 critical section에 들어가면 안된다

2. Progress, 진행: 아무도 critical section에 들어가 있지 않을경우 무조건 critical section에 들어가게 해줘야 한다

3. Bounded Waiting, 유한대기: critical section에 들어가는 횟수에 제한을 둬 특정 프로세스가 무한대로 기다리지 않게 한다

- critical section이 하나의 인스트럭션이면 이런 문제가 없음, 고급 언어의 하나의 코드가 여러 인스트럭션으로 이루어져 있어 이런 문제가 발생함

 

 

알고리즘1:

- critical section에 들어가기 전에 while문을 돌면서 체크를함

- turn이 0이면 0번 프로세스 차례, 1이면 1번 프로세스 차례

- 이 경우 위에 2번 조건을 충족하지 못함, critical section을 교대로 들어가는 방식인데, p0은 3번 사용해야 하고 p1은 1번만 사용해도 되면 p0는 무한정 기다리는 상황이 발생함

 

알고리즘2:

- flag배열을 만들어 각 프로세스가 critical section에 들어와 있는지를 boolean 값으로 넣는다

- critical section에 들어가려면 우선 자기 자신의 flag를 true로 바꾼다

- while문을 돌면서 상대방의 flag를 체크한다

- 상대방이 사용할 경우 기다리고, 사용하지 않을 경우 내가 사용한다

- 다 사용하고 나서는 flag를 false로 바꿔준다

 

- 이 경우 flag[i] = true 이 상황에서 CPU를 빼껴버리고 j 차례가 오면, j도 flag[j] = true 하고 i를 기다림

- 그럼 다시 i 차례가 와도 j가 true이기 때문에 무한정 기다림

- 이렇게 아무도 안들어가 있어도 서로 들어가 있는줄 알고 무한정 기다릴수 있음

 

알고리즘3(peterson's algorithm):

- 알고리즘1과 알고리즘2를 합친 방식

- flag 처리와 turn 처리를 둘다함

- 상대방 flag가 true이고, turn도 상대방 차례일때만 while문을 써서 기다림

- 그 외 경우는 들어갈수 있음, 아무도 사용 안하면 들어갈수 있고 누군가 사용하면 그때 turn을 따짐

- 다 사용하고 flag를 flase로 바꿔줌

- 이 경우는 중간에 CPU를 빼앗겨도 정상적으로 작동하게끔 동작함

 

- while문을 써서 기다리기 때문에 Busy Waiting(=spin lock) 문제가 생김, 기다리는 동안 CPU를 낭비함

 

 

- 사실 들어가기 전에 lock을 걸고 나올때 lock을 풀기만 하면 되는데 이렇게 복잡한 이유는 고급 언어의 하나의 코드가 여러 인스트럭션으로 구성되어 있기 떄문

- 한줄의 코드가 실행되던 중 하나의 인스트럭션만 실행되고 CPU를 빼앗길수 있음

- 그래서 만약에 하드웨어적으로 데이터를 읽는 작업과 쓰는 작업을 하나의 인스트럭션으로 만들면 이런 문제를 해결할 수 있음

- 대표적인게 Test_and_Set(a), a라는 변수를 읽는것과 1(true)로 바꿔주는 작업을 하나의 인스트럭션으로 실행함