[Chapter-5] Process Synchronization

-이대 반효경 교수님 강의 기반으로 작성되었습니다-

 

Race Condition

= 여러 주체가 하나의 storage에 접근할때 race condition 가능성이 있음

==> 최종 결과가 예상과 다를 수 있다.

 

크게

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

==> sol) 수행 도중에는 인터럽트를 수행하지 않도록 

 

2. ps가 system call 하여 커널모드로 수행 중인데 문맥교환이 일어나는 경우

==> sol) 커널 모드에서 수행 중일 때는 cpu preempt 하지 않음

 

3. mutips에서 shared memory 내의 커널 데이터

==> sol) 한번에 하나의 cpu만 커널접근

==> sol) 커널 내부에 있는 공유 데이터에 접근할 때마다 데이터에 lock, unlock

 

Critical-Section Problem

공유데이터를 접근하는 코드를 말함

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

 

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

1. mutual exclusion : 이미 프로세스가 critical section 부분을 수행중이면 다른 프로세스는 들어가면 안된다.

2. Progress : 아무도 critical section에 없으면 프로세스가 들어가게 해주어야함

3. Bounded waiting : 프로세스가 critical section에 들어가는 횟수에 한계가 있어야 한다.

 

알고리즘

1. 

문제 : 다른 프로세스와 빈도차이 ==> 의존성(다른 프로세스쪽에서 들어갔다 나와야 내차례)

2.

둘 다 끊임없이 while에 갇힘

3. 피터슨 알고리즘

1+2, 조건 모두 만족

but busy waiting 문제 (spin lock)

- 계속 cpu, 메모리를 사용하면서 wait

 

하드웨어 적으로 test&modify 를 atomic 하게 수행할 수 있도록 지원하는 경우 위의 문제는 간단히 해결

 

Semaphores

= 추상화

Semaphore S

= int 변수, atomic 연산에 의해서만 접근(P,V)

==> P연산(변수 값을 획득하는 과정), V 연산(연산 후 내어놓는 연산)

p,v 연산 사용 예시

-busy waiting 방식의 p, v연산

 

S = 자원의 수

- Block / Wakeup 방식의 p, v연산

S가 음수면 누군가 기다리는중(wakeup 할 대상이 있냐 없냐)

 

Types of Semaphores

- counting semaphore : 주로 리소스 카운팅

- Binary semaphore (=mutex) : 0 또는 1값만, 주로 mutual exclusion

 

 

Deadlock

= 둘 이상의 프로세스가 상대방에 의해 충족될 수 있는 event 무한히 기다리는 현상

ex)

하필 P(S); 로 가져간 후 V연산을 못하고 넘어갔을때 deadlock

==> 자원 획득 순서를 맞추면 해결