[Chapter 6] Process Synchronization

데이터의 접근

 

storage box의 데이터가 execution box(CPU 역할)로 전송됨

-> execution box는 연산한 결과를 storage box(MAC 주소 공간 역할)로 돌려줌

 

 

Race Condition

 

: 현실과 비슷한, 더 복잡한 상황은 다음과 같은데, 여러 개의 box가 경쟁하는 Race Condition이 발생한다.

 

Race Condition: Execution box들이 storage box를 차지하기 위해 경주하는 것

 

Execution box	Storage box
CPU	Memory
컴퓨터 내부	디스크
프로세스	그 프로세스의 주소공간

 

 

<OS에서 race condition은 언제 발생하는가?> - 이 부분 반교수님꺼 들을 것

 

1, 2는 여러 Execution box가 Storage box를 공유할 때 발생

3은 CPU가 여러 개일 때 발생

 

1. kernel 수행 중 interrupt 발생 시

2. process가 system call 하여 kernel mode로 수행중인데 context switch가 발생하는 경우

* interrupt 걸림 -> context switch 발생(register handler, PC값 바뀜)

3. multiprocessor에서 공유 메모리 내의 kernel data

 

 

 

3. 

CPU가 여러 개일 때

(방법 1) 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

-> 앞 CPU가 끝날 때까지 기다려야 함

(방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock하는 방법

-> unlock될 때까지 기다려야 함

 

=> 방법 1, 2 모두 기다리는 시간이 발생할 때까지 기다려야 하기 때문에 한계를 가짐

 

<예제>

 

 

정리하자면>>

"Race condition의 문제"

: 여러 프로세스가 동시에 데이터를 공유하는 상황이기 때문에 데이터의 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라지는 현상 => 이렇게 interrupt에 의해 context switch가 계속 일어나면 데이터의 일관성(데이터 불일치)이 유지되지 않을 수 있음

"해결책"

일관성 유지를 위해 협력 프로세스 간 실행 순서를 정해주는 synchronizing 매커니즘이 필요

 

Critical-Section Problem

 

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

-> critical-section을 두어 공유되는 부분을 따로 두어서 거기만 조심하도록 함

=> 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 접근할 수 없어야 한다.

예컨대 다음과 같이 P1과 P2는 자신의 중요한 코드를 critical section에 두어 보호할 수 있다.

 

 

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

1. Mutual Exclusion

critical section은 공유하는 공간이기 때문에 한 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가면 안 됨

2. Progress

아무도 critical section이 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 들어갈 수 있도록 해야 함

3. Bounded Waiting

P1이 P2가 critical section에서 나올 때까지 기다리지만, 무한히 기다릴 수는 없다.

 

* 모든 프로세스의 수행속도 > 0

* 프로세스 간 상대적 수행 속도는 가정하지 않음

 

<Initial Attempts to Solve Problem>

두 개의 프로세스 P0, P1이 있다고 가정하자. 프로세스의 일반적인 구조는 다음과 같다.

do {
	entry section //공유 -> synchronization variable
    critical section	//공유x
    exit section //공유
    remainder section	//공유x -> synchronization variable
} while(1);

critical section과 remainder section은 건들면 안 되기 때문에 

프로세스들은 수행의 동기화를 위해 몇몇 변수(entry section과 exit section)를 공유할 수 있다.

=> synchronization variable: entry section & exit section

 

<Algorithm 1>-한계

int turn;
initially turn=0;

A와 B의 알고리즘

 

A와 B가 각자의 알고리즘 수행하여 교대로 들어감(swap-turn)

(-) A는 조금, B는 많이 critical section에 들어가야 한다면,

B는 과잉양보(자신의 turn이 0이 될 때까지 기다려야 하므로 굉장히 비효율적이고 속터지는 상황) -> 2. Progress 만족 못함