OS : 프로세스 동기화(process syncronization)

임계 구역 문제

임계구역

공유변수 영역이라고도 부르며 병렬컴퓨팅에서 둘 이상의 스레드가 동시에 접근하면 안되는 공유자원을 접근하는 코드의 영역을 말한다.

스레드가 임계구역에 들어가려고 하면 지정한 시간만큼 대기해야하며, 임계구역에 들어가고 나올 때는 세마포어 같은 매커니즘이 사용된다.

임계 구역 문제

임계구역으로 지정되어야 할 코드 영역이 임계구역으로 지정되지 않았을 때 발생하는 문제를 말한다.(둘 이상의 스레드가 하나의 임계구역에 접근하려고 할 때 발생할 수 있는 문제)

유한 버퍼 문제(bounded-buffer problem)

한정 버퍼 문제라고도 하며 버퍼의 공간이 부족할 때 생기는 문제(세마포어 등으로 해결 가능)

판독자와 기록자 문제(readers and writers problem)

여러 판독자와 기록자가 하나의 저장공간을 공유하며 접근할 때 생기는 문제(세마포어 등으로 해결 가능)

식사하는 철학자들 문제(dining-philosophers problem)

교착상태가 일어나는 원인을 직관적으로 알 수 있다.

임계 구역 문제 해결을 위한 요구조건

- 상호 배제(mutual exclusion) : 한 프로세스만 임계구역 진입할 수 있어야 한다.

- 진행(progress) : 임계구역에 진입하려는 프로세스가 여러개 있다면 어떤 프로세스를 진입시킬 것인지 적절히 결정해주어야 한다.

- 한계 대기(bounded waiting) : 한번 임계구역에 들어간 프로세스는 다음 번 임계구역에 진입할 때 제한을 두어야 한다.

임계 구역 문제 해법

SW : Perterson's algorithm, Dekker's algorithm, lock

Peterson's algorithm : 2개의 프로세스를 위한 해결 방법 3가지 요구조건을 충족한다.

2개의 프로세스가 int turn, boolean flag[2] 두 변수를 공유

turn은 어느 임계구역 진입 순번을 표시

flag는 임계구역 진입 준비됨 표시

if(flag[i]==true) process[i] is ready;

Dekker's algorithm : f0, f1 2개의 플래그를 사용해 구현

lock : 프로세스는 임계구역에 진입할 때 반드시 lock을 획득한다.

리눅스는 locking을 위해 세마포어와 스핀락 제공

세마포어 : 긴 임계구역에 사용

스핀락 : 짧은 임계구역에 사용

monitors : 한 순간에 한 프로세스만 모니터 안에서 활성화 되도록 만들어진 고급 언어 구조체

HW : 하드웨어 명령 이용

원자적으로 실행(executed atomically) : 하나의 기억장치 사이클 내에서 중간에 인터럽트 되지 않는 하나의 단위로 수행된다.

#1 세마포어

두개의 원자적(atomic) 함수로 조작되는 정수 변수로, 철학자들의 식사 문제를 해결하는 고전적인 방법이지만 교착상태를 해결하지는 못한다.

이진 세마포어(binary semaphore) : 0 또는 1

계수 세마포어(counting semaphore) : 무제한

세마포어 값 S는 P와 V명령에 의해서만 접근이 가능하며 P는 임계구역에 들어갈 때, V는 임계구역에서 나올 때 수행된다.

P(S)

// critical section

V(S)

#2 스핀락

임계구역에 진입이 불가능할 때 진입 가능할 때 까지 시도하도록 구현된 락이다.

락을 획들할 때 까지 스레드가 돈다(spin)는 의미.

바쁜대기의 한 종류이다.

스핀락은 운영체제의 스케줄링 지원을 받지 않기 때문에 해당 스레드에 대한 문맥교환이 일어나지 않는다.

SMP 시스템의 기본적인 락킹 기법이다.

장점

임계구역 내에 짧은 시간 안에 진입할 수 있는 경우에 문맥교환을 제거할 수 있다.

단점

스핀에 오랜 시간이 소요된다면 다른 스레드를 진행하지 못하고 대기상태가 된다.

#2-1 문맥교환

cpu가 다른 프로세스를 실행하기 위해 현재 프로세스의 상태(문맥)를 저장하는 작업 문맥은 프로세스 제어 블록에 기록되어 있다.