23.07.10 최초작성

1 프로세스 병렬 처리 시 문제점

프로세스(스레드) 병렬처리 시 한 프로세스에서 자원에 대한 사용이 끝나지 않은 상태에서 스케쥴링이 이루어지고 다른 프로세스가 같은 자원을 사용하게 되면 결과값이 오염될 수 있다.
이는 context switching때문에 발생하는데 context switching에 의해register 값이 저장되고 이후 return되기 전에 메모리의 값이 변경되면 context switching 할 때의 register 값과 실제 메모리에 저장되는 값이 달라질 수 있다.
이러한 문제를 race condition이라고 하며 이를 방지하기 위해 하나의 프로세스만 변수를 변경할 수 있도록 해야한다. 이를 방지하기 위한 작업이 Synchronization 이다.

2. Critical Section(임계 영역)

스레드끼리 공유하는 영역이며 한 스레드가 작업을 어떤 영역에서 수행할 때 다른 스레드가 조작할 수 없는 영역

2.1 Lock

Critical Section에 다른 스레드가 접근할 수 없도록 하는 메모리의 개체

void acquire();	// lock이 풀리길 기다리고 풀리면 lock
void release();	// lock을 풀며 acquire()을 기다리는 프로세스를 wake함

2.2 Lock의 성질

1. Correctness

• Mutual Exclusion : 임계구역에 하나의 스레드만 접근 가능해야 함
• Progress : 여러개의 스레드가 임계구역에 접근하려고 할 때 어떤 걸 허용할지 결정해야 함
• Bounded Waiting(Starvation Free) : 한 스레드가 진입 요청 후 받아들여질 때 까지 다른 스레드가 임계영경게 진입하는 횟수는 제한되어야 함(기근 현상 방지)

2. Fairness : 각 스레드는 임계구역에 접근할 공평한 기회를 얻어야 함

3. Performance : lock에 걸리는 시간이 길어서는 안됨

3. Mutex Lock(Mutual exclusive Lock)

임계 영역 문제를 해결하기 위한 방안 중 하나로 임계 영역에 2개의 프로세스가 동시에 접근하지 못하도록 방지하는 방법. 스레드는 임계영역에 접근할 때 반드시 락을 획득하고 빠져나올 때 락을 반환해야 함.
acquire()과 release()를 통해 사용한다. Block, Busy Waiting 형식이 있으며 Busy Waiting형식일 경우 Busy Waiting 상태가 되어 cpu 자원이 낭비될 수 있다.

4. Spinlock

임계영역이 락이 걸려서 진입이 불가능할 때, 임계영역이 언락되어 진입이 가능해질 때까지 루프를 돌면서 재시도하여 스레드가 cpu를 점유하고 있는 상태. cpu를 점유하며 언락되는 것을 확인하기 때문에 Busy Waiting 상태이다.
스케줄링 지원을 받지 않아 Context Switching 이 이뤄지지 않는다. 이에 따른 비용이 들지 않지만 임계영역이 오랜 시간동안 언락되지 않으면 그 시간동안 계속 CPU를 점유하고 있어 다른 스레드가 사용하지 못하기 때문에 오버헤드도 존재한다.
상태가 Lock 과 Unlock 만 존재하며 여러 스레드가 acquire()을 수행할 경우 Mutual Exclusion을 충족시키지 못할 수 있다. 따라서 한 번에 하나의 컴포넌트만 접근이 가능하며, 획득과 해제의 주체는 동일해야 한다.

struct lock {int held = 0;}

void acquire(struct lock *l){
	while(l->held);
   l->held = 1;
}

void release(struct lock l*){
	l->held = 0;
}

만약

5. Synchronization Implementation

5.1 Peterson's Algorithm

int turn;
int interested[2] = {FALSE, FALSE};

void acquire(int my_id) {/* my_id is 0 or 1*/
	int other = 1 - my_id;
    intereseted[my_id] = TRUE;
    turn = other
    while (interested[other] && turn == other);
}

void release(int my_id){
	interested[my_id] = FALSE;
}

Mutual exclusion, Progress, Bounded waiting을 만족한다. 하지만 최신 컴퓨터 구조에서 항상 올바르게 작동한다고 보장할 수 없다. 컴파일러가 코드를 최적화하기 위해 연산 순서를 바꿀 수도 있고 load와 store 과정이 atomic 하지 않을 수 있기 때문에 제대로 된 lock을 구현하는 것이 어렵다.
이를 위해 임계 구역에 진입했을 때 인터럽트를 불가능하게 만들어주어 atomic하게 만들 수 있다(Mutual Exclusion). 하지만 Multi-Threaded 환경의 경우 인터럽트를 불가능하게 만든다면 모든 프로세서에서 인터럽트가 불가능하게 되기 때문에 실용적이지 않다.

5.2 Synchronization Hardware

int TestAndSet(int *v, int new){
	int old = *v
    *v = new;
    
    return old;
} 							//하드웨어가 동작하는 방식을 코드로 표현

 struct lock {int held = 0;}
 
 void acquire(struct lock *l){
	while(TestAndSet(&l->held, 1));
 }
 
 void release(struct lock l*){
 	l->held = 0;
 }

6. Semaphore

세마포어는 Critical Section에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나 busy waiting을 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

/*Busy Waiting 형식 Semaphore*/
struct semaphore{
	int S;			//공유 가능한 자원의 수
}

void wait(struct semaphore *sem){
	sem ->S--;
   while(sem->S < 0);
}

void signal(struct semaphore * sem){
	sem->S++;
}
/*Implementing Blocking Semaphore*/
struct semaphore{
	int S;
   struct task Q*;
}

void wait(struct semaphore *sem){
	sem->S++;
   if(sem->5 < 0){
   	add_this_task_to(sem->Q);
       block();
   }
}

void signal(struct semaphore *sem){
	sem->S++;
   if(sem->S <= 0){
   	P = remove_a_task_from(sem->Q);
       wakeup(P);
   }
}

세마포어의 wait(), signal() 내부 코드가 실행되는 도중에 Context Switching이 발생하면 Mutual Exclusion과 Bounded Waiting 조건을 보장하지 못한다. 따라서 P(), V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 한다. 즉, atomicity가 보장되어야 한다.
또한 Semaphore가 global 변수이기 때문에 주의해서 사용해야 한다.

6. Monitor

임계 영역을 보호하는 프로그래밍 언어의 구조체. 모니터는 내부에 사용할 변수와 함수를 선언하고 해당 구조체는 하나의 스레드만 접근 가능하고 모니터 지역 내에서만 사용 가능하다.
Mutual Exclusion을 보장하고 미리 정의되어 있지 않은 접근을 막는다.

monitor my_monitor{
	procedure P1(...){
    }
    
    init_code(...){
    }
}

흐름을 제어하는 기능이 없다. 이 기능을 보완하기 위해 condition variable 을 사용한다. 이것은 스레드가 특정 이벤트의 발생 여부를 판단해 스레드의 진행을 기다리게 하는 기능을 제공한다.

wait() : 스레드가 신호를 기다리게 한다.
signal() : 하나의 wait()상태의 스레드를 깨운다.

7. Synchronization Issues

7.1 Bounded Buffer Problem

Buffer : 공유된 자원들의 집합
Producer : buffer에 자원을 넣는 객체
Consumer : buffer에 들어있는 자원을 제거하는 객체

Producer, Consumer 둘이 다른 속도로 작업을 한다. 따라서 Producer에 의해 Buffer 가 넘치거나 Consumer가 빈 buffer에서 자원을 제거하지 않도록 해야한다(Bounded Buffer을 만들어야 한다).

Ring Buffer(원형 큐) 활용할 경우 count변수가 여러 개의 Producer, Consumer에 의해 조작되어 동기화 문제가 발생할 수 있음.

Mutex를 활용해 개선한 결과 Mutual Exclusion을 보장함.

Semaphore를 활용해 개선한 결과 in 과 out 변수에 동기화 문제가 발생함.

Mutex와 Semaphore를 활용해 해결.

7.2 Readers-Writers Problem

공유된 자원을 두고 다수의 Reader와 Writer에 의한 동기화 문제
-Reader : 데이터를 읽는 객체. 여려개의 Reader가 동시에 값을 읽을 수 있다.
-Writer : 데이터를 쓰는 객체. 오직 하나의 Writer만이 값을 쓸 수 있다.

Reader와 Writer는 동시에 동작할 수 없으며 이를 Reader의 경우 Semaphore, Writer는 Mutex를 활용해 구현했다. Reader 동작 중 rw 변수의 값을 변경시켜 Writer가 동작하지 못하도록 했고

7.3 Synchronization in Linux

• Big kernel lock(Mutex)이 전체 커널을 보호하며 최근 여러 시스템 콜을 처리하기 위해 이를 작게 나눴다.
• Fully Preemptive
• spinlock, atomic operation, semaphores ...

8. Deadlock

모든 스레드가 대기상태에 들어가게 되어 어떠한 자원도 반납이나 점유를 못하는 상태. 하나의 스레드가 2개 이상의 자원을 점유하려고 하거나 여러개의 스레드가 2개 이상의 자원을 동시에 점유하려고 할 때 주로 발생한다.

8.1 Conditions for Deadlock

1. Mutual Exclusion
   하나의 스레드만 자원에 접근할 수 있으며 해당 자원은 반납되기 전까지 누구도 접근할 수 없도록 한다.
2. Hold and wait
   스레드는 자원을 점유한 채, 다른 스레드가 점유하고 있는 자원을 접근하기 위해선 반드시 대기하여야 한다.
3. No Preemption
   자원들을 선점할 수 없다. 자원은 강제적으로 반납할 수 없으며, 스레드에 의해 자발적으로만 반납 가능하다.
4. Circular Wait
   각 스레드가 점유하고자하는 자원이 원형을 유지한다. 예를 들어 p1은 p2가 가진 자원을 요청하고 p2는 p3가 가진 자원을 요청하고 p3는 p1이 가진 자원을 요청한다. p1->p2->p3->p1와 같은 형태로 자원을 대기하는것을 환형대기라고 한다.

8.2 Deadlock Prevention

Deadlock Condition 중 하나의 조건을 충족시키지 않게 해 Deadlock을 방지하는 것

Mutual Exclusion
상호 배제를 하지 않으면(동시 접근 허용) 교착상태를 예방할 수 있다. 하지만 이는 모든 자원이 공유 가능한 자원이 아니기 때문에 근본적인 해결이 어렵다.

Hold & Wait
스레드가 자원을 요청할 때 다른 자원을 보유하지 않도록 한다. 스레드가 작업을 진행하기 전 모든 자원을 요청하고 할당하거나 스레드가 자원을 가지고 있지 않을때만 자원요청을 하도록 하면 된다.
전자의 경우 자원의 할당이 이뤄졌지만 작업을 진행하지 않는 시간이 발생해 성능이 저하되며 후자의 경우 기아 현상이 발생할 수 있다.
만약 두가지 경우가 불가능하다면 모든 자원을 반환하고 재시도한다. \

No Preemption
어떤 스레드가 자원을 점유하기 위해 대기하고 있다면 할당된 상태의 리소스를 반납한다.
또는 스레드가 요구하는 자원이 자원을 대기중인 다른 스레드가 점유하고 있을 경우 해당 자원을 선점한다.
해당 방법은 Mutex와 Semaphore의 경우 사용할 수 없다. cpu 레지스터나 메모리같은 상태가 저장되고 복원될 수 있는 자원에 사용할 수 있다.

Circular Wait
모든 자원에 순서(Total Order)를 부여해 각 스레드가 정해진 순서대로 자원을 요청하도록 하는 방법. 가장 널리 쓰인다.

8.3 Deadlock Avoidance

시스템이 Deadlock으로 진입할 수 있는 Unsafe한 상태로 진입하지 않는 방법.

• Safe State : 모든 스레드에 어떤 순서로든 요청하는 모든 자원을 교착 상태가 되지 않도록 차례대로(Safe Sequence를 만족) 모두 할당할 수 있는 상태.
  스레드가 요청한 자원보다 시스템에서 더 많은 자원을 가지고 있다 하더라고 프로세스가 대기해야할 상황이 발생할 수 있다. 따라서 회피 방법을 사용한 자원의 이용률은 낮다.

  8.3.1 Avoidance Algorithms

  시스템은 스레드가 자원을 얼마나 요청할 지 미리 알고있어야 한다. 또한 자원을 할당하는 것이 안전한가 아닌가를 파악해 안전할 경우에만 할당해야 한다.
  즉 스레드가 요청한 자원보다 시스템에서 더 많은 자원을 가지고 있다 하더라고 프로세스가 대기해야할 상황이 발생할 수 있다. 따라서 회피 방법을 사용한 자원의 이용률은 낮다.

1. Resouce-Allocation Graph
   

Vertices

• Process {P1, P2, P3 ...}
• Resources {R1, R2, R3 ...}

Edges

• Request Edge(요청) P -> R
• Assignment Edge R -> P
• Claim Edge(요청을 암시) P -> R

어떤 자원이 요청되어야 하는지 미리 알고 모든 Claim Edge를 표시해야 한다. 사이클이 있을 경우 Deadlock이 발생할 수도, 발생하지 않을 수도 있다.

2. Banker's Algorithm
   

   Need Table 중에서 Available Table 보다 작은 스레드에 자원을 할당함. 스레드가 자원들을 요청하면 시스템은 계속 안전 상태에 머무르게 되는지 여부를 판단해야 한다.

3. Deadlock Detection and Recovery
   추후 내용 추가

4. Ignore
   추후 내용 추가