OS ) 동기화 도구 -> 락 (Mutex, 세마포)

 

프로세스가 병렬, 병행 실행될 때의 문제 상황

프로세스는 “메모리”에서 “레지스터”로 데이터를 가져오고, “레지스터”에서 “메모리”로 다시 적재된다.

예시

• 병행 실행되는 프로세스 p1 과 p2 가 있다.
• 두 프로세스 모두 공유 변수 count = 5 를 레지스터로 가져와 사용해야 한다.
• 같은 메모리 주소에 있는 공유 변수를 프로세스가 점유하고 있는 각 코어의 레지스터로 가져온다.
• p1 은 count++ , p2 는 count— 를 실행한다.
  • p1 은 count = 6 , p2 는 count = 4 로 연산하여 메모리에 적재 하려고 한다.
• 이 경우 p1 이 먼저 작업을 끝내고 6으로 메모리를 업로드해도, 그 뒤에 실행된 p2 가 count=4 를 적재하면 p1이 계산한 기대값과 다른 상황이 발생한다.

→ 이 상황을 경쟁 상황 race condition 이라고 한다.

💡 한 순간의 하나의 프로세스만이 변수 count 를 조작하도록 보장하기 위해 프로세스들이 동기화 될 필요가 있다.

임계 구역 Critical-Section

한 프로세스가 자신의 임계구역에서 수행하는 동안 다른 프로세스들은 임계구역에 들어갈 수 없다. 즉, 두 프로세스가 동시에 임계구역 안에서 실행할 수 없다.

• 진입 구역(entry section) : 각 프로세스는 임계 구역으로 진입하려면 진입 허가를 요청해야 하는 구간.
• 임계 구역(critical-section) : 공유 자원을 동시에 수정하지 못하도록 보호된 코드 영역.
• 퇴출 구역(exit section) : 임계 구역에서 나가는 영역.
• 나머지 구역(remainder section) : 그 외 나머지 구역

임계 구역 요구 조건

1. 상호 배제 (mutual exclusion)
   • 프로세스 p1 이 자기의 임계구역에서 실행된다면 다른 프로세스는 임계구역에서 실행될 수 없다.
2. 진행 (progress)
   • 임계 구역에 진입하려는 프로세스들만 진입 결정이 가능하며, 다른 프로세스가 임계 구역 진입을 결정할 수 없다.
   • 결정은 무기한 연기될 수 없다.
3. 한정된 대기 (bounded waiting)
   • 프로세스가 임계 구역에 진입하려는 요청 이후에, 요청이 허용될 때까지 요청 횟수의 한계가 있어야 한다. (요청이 무한 루프되지 않아야 함.)

상호 배제 예시

1. p0 , p1 프로세스가 fork() 를 사용하여 자식 프로세스를 생성한다.
   • 자식 프로세스의 pid 는 부모 프로세스에서 ++ 됨.
2. 상호 배제가 되지 않으면 동일한 pid 번호가 두 개의 다른 프로세스에 배정될 수도 있다…

→ 사실 단일 코어에서는 공유 변수를 수정하는 동안 인터럽트가 발생하는 걸 막을 수 있다면 임계구역 문제는 간단히 해결될 수 있으나..단일 코어 요즘 누가 씀? ㅎㅎ

다중 코어에서 인터럽트를 비활성시킨다면?

다중 코어에서 공유 변수를 수정하는 동안 인터럽트를 비활성 시킨다면

• 인터럽트 비활성 메시지가 모든 프로세서(코어)에 전달되어야 함. → 시간 많이 걸림
• 임계 구역으로 진입 지연 시스템 효율 하락
• 만약 클록이 인터럽트로 업데이트 되면 시스템 클록에 영향을 미칠 수도..

임계 구역을 다루기 위한 커널

• 선점형 커널
  • 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용.
• 비선점형 커널
  • 커널모드에서 수행되는 프로세스의 선점을 허용 X
  • 모든 커널모드 프로세스는
    • 커널을 빠져나갈 때까지
    • block 될 때까지
    • 자발적으로 CPU 제어를 양보할 때까지 계속 수행

💡 선점형 커널을 선호하는 이유

• 한 프로세스가 너무 오랫동안 실행할 위험이 적음.
• 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적당함.

Peterson 의 해결안

load, store 같은 기본적인 기계어 수행 방식때문에 이 해결안이 올바르게 실행된다고 보장할 순 없으나, 임계구역 문제를 해결하기 위한 좋은 설명을 제공한당. 한 마디로 알아볼만 하다는 얘기.

• load() : 메모리에서 레지스터로 load
• store() : 레지스터에서 메모리로 적재

예시

// 임계구역으로 진입할 번호, turn == i 일 경우 프로세스 Pi 이 임계 구역에서 실행될 수 있다.
int turn 
// 구역으로 진입을 준비하는 프로세스를 넣은 배열
boolean flag[2];

while(true) {
	flag[i] = true;
	turn = j;
	while (flag[j] && turn == j) {
		/* critical section */
		
		/* 임계 구역이 끝난 이후 */
		flag[j] = false;
		turn = i;
		
		/* remainder section */
	}
}

임계구역으로 진입하기 위해

• Pi 는 flag[i] 를 true 로 만든다.
• turn = j 로 지정한다.
  • Pj 가 임계구역으로 진입하길 원하면 진입 가능하다는 걸 보장.
  • 한 마디로 i 가 진입하고 싶어 flag[i] 는 true 로 만들었지만, i-1 (즉 j) 로 turn 을 줘서 j 의 턴임을 보장.
  • 이 경우 Pj 가 먼저 임계구역에 진입한다.
• 두 프로세스가 동시에 진입하길 원한다면 거의 동시에 turn 이 i 또는 j 로 지정되지만, 둘 중 한 프로세스만 입장 가능하다.
• turn 의 궁극적인 값이 둘 중 누가 먼저 임계구역으로 진입할 것인가를 결정한다.

이는 다음과 같은 사실을 볼 수 있다.

1. 상호 배제가 제대로 지켜지고 있음.
2. progress 에 대한 요구 조건 (임계구역에 진입하려는 프로세스들만 임계 구역 진입을 결정 가능) 을 충족.
3. 대기 시간이 영원히 길어지지 않는다.

단, 멀티 프로세서에서는 이야기가 다르다.

• 서로 동시에 실행될 수 있기 때문에 공유 변수를 두 프로세스가 사용할 수 있고,
• 명령어 실행 순서가 다르다면 반드시 원하는 값이 나온다는 보장을 할 수 없다.

💡 적절한 동기화 도구를 사용하여 해결하자

동기화 하드웨어 지원

추상적인 동기화 기법의 기초 형태로 알아두자. 우린 HW 개발자가 아니니까.. 그래서 가볍게 설명하겠음.

메모리 모델

컴퓨터 아키텍처가 응용 프로그램에게 제공하는, 메모리 접근 시 보장되는 사항(방식) → 메모리 모델

1. 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 “즉시” 보임.
2. 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음.

메모리 장벽 Memory Barriers

메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어, 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 걸 보장한다.

• 메모리 장벽 명령어가 실행되면, 시스템은 후속 적재 또는 연산이 수행되기 전에 모든 적재와 저장이 완료되도록 한다.(다른 프로세서에서 연산되어 적재된 값을 볼 수 있도록 하자.)

→ 메모리 배리어는 매우 낮은 수준의 연산만.. 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다고..

하드웨어 명령어

• TAS(test_and_set()) : 명령어를 원자적(atomically)으로 실행하기 위해 false 로 초기화되는 lock 이라는 변수를 선언하여 상호 배제를 구현한다.
• CAS(compare_and_swap()) : 두 워드의 내용 교환에 기반을 둔 기법. 보통 value 의 원래 값을 반환하다가 (*value == expected) 가 참이면 new_value 로 지정한다. 원자적 실행.

원자적 변수

정수 및 기본 데이터 유형에 대한 원자적 연산 제공.

Mutex Locks (mutual exclusion)

프로세스는 임계 구역에 들어가기 전 반드시 락을 획득해야 하고, 임계 구역을 빠져나올 때 락을 반환해야 한다.

while (true) {
	..acuire lock // true 일 때 lock 획득, false 로 만든다.
	
	..critical section // 임계구역 진입
	
	..release lock // 락 반환, true 로 만듬
	
	..remainder section // 임계구역 이후..
}

• availale 이라는 변수 값으로 락의 가용 여부를 표시한다.
  • true 일 때 false 로 변경하여 락 획득
  • false 라면 다른 프로세스가 busy wait
• 한 번에 한 스레드만 진입 가능하다.

단점

busy wait 을 해야 한다.

• 임계구역에 들어가려는 다른 프로세스들은 acuire() 함수를 계속 반복하여 실행해야 한다.
  • CPU 주기를 낭비한다.

장점

• 락이 유지되는 기간이 문맥교환을 두 번 하는 시간보다 짧은 경우 스핀락(뮤텍스)을 사용한다.
  • 문맥 교환이 필요하지 않다는 장점이 있다. (반복문으로 계속 기다리기만 하면 되니까)
    • 락을 요청했지만 대기하는 상태 (문맥교환 1회)
    • 락이 사용가능 할 때 다시 스레드를 깨우는 상태 (문맥교환 2회)
• 컨텍스트 스위칭이 필요할 정도가 아닌, 잠깐 동안 락을 유지해야 하는 경우에는 뮤텍스(스핀락)로 만드는 것이 더 낫다.

세마포 Semaphore

락을 획득하지 못하면 대기하기.

/* 이 작업은 인터럽트 없이 실행되어야 한다. */
wait(S) {
	while (S <= 0) // 대기해야 함.
	// busy wait
	S--;
}

signal(S) {
	S++;
}

→ 이 작업은 인터럽트 없이 실행되어야 한다.

• 세마포 S 는 정수 변수로, wait() 과 signal() 로만 접근할 수 있다.
• 세마포의 정수 값(S) 를 변경하는 연산은 반드시 원자적으로 수행되어야 한다.

💡 세마포의 종류는 이진 세마포, 카운팅 세마포가 있는데 이진 세마포는 뮤텍스와 유사하게 작동하기 때문에 여기서는 “카운팅 세마포” 기준으로 설명한다.

카운팅 세마포

유한한 개수를 가진 자원에 대한 접근을 제어할 때 사용한다.

• 가용한 자원의 개수로 초기화되며, 각 자원을 사용하려는 프로세스는 wait() 을 수행한다.
  • wait() 은 세마포 값을 감소시킨다.
• 프로세스가 자원을 방출할 때는 signal() 을 사용한다.
• 세마포 값이 0이면 모든 자원이 사용중이며, 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 Block 된다.
  • S > 0 일 경우에만 작업 가능.

예시

// P1
S1;
signal(synch);

// P2
wait(synch);
S2;

• P1 은 S1 명령 실행.
• P2 는 S2 명령 실행.
• 단, S2 는 S1 이 끝난 뒤에만 수행되어야 한다.
• P2 가 S2 를 수행하는 건, P1 이 S1 을 끝내고 signal(synch) 를 호출한 후에만 가능하다.

세마포 구현

wait()

프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아니라면, 프로세스는 반드시 대기한다.

• 단, busy wait 대신 프로세스를 일시중지 시킨다.
  • 프로세스를 세마포에 연관된 대기 큐에 넣고
  • 프로세스 상태를 대기 상태로 전환.

signal()

세마포 S 를 대기하면서 일시중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다.

• wakeup() 연산에 의해 재시작.
  • 프로세스 상태를 대기 상태에서 준비 완료 상태로 변경.
  • 프로세스는 준비 완료 큐에 넣어진다.

세마포 정의

// semaphore
typedef struct {
	int value; // 락 획득 가능 수.
	struct process *list; // 대기 큐, signal() 로 깨움.
} semaphore;

// wait
wait(semaphore *S) {
	S -> value--;
	if (S -> value < 0) {
		add this process to S -> list;
		sleep(); // 프로세스를 대기 상태로 만듬.
	}
}

// signal
signal(semaphore *S) {
	S->value++;
	if (S->value <= 0) {
		remove a process P from S -> list;
		wakeup(P); // 프로세스 재개
	}
}

• 이들 연산은 운영체제의 기본적인 시스템 콜로 제공 된다.
• 세마포 값이 음수일 때, 그 절댓값은 세마포를 대기하고 있는 프로세스들의 수다.
• 대기하는 프로세스의 리스트는 PCB 에 있는 연결 필드에 구현된다.
  • 각 세마포는 정수 값, PCB 에 리스트에 대한 포인터를 갖고 있다.
  • 리스트는 선입 선출 방식 큐를 사용하지만, 일반적으로 큐잉 전략 사용과는 무관하긴 함.

같은 세마포에 대해 두 프로세스가 동시에 wait() , signal() 연산들을 실행할 수 없도록 반드시 보장해야 한다.

• 어쨌든 원자적으로 사용하기 위해 스핀락 같은 기법을 제공하고, 세마포에서도 busy wait 을 완전히 제거하진 못한다.
• 다만, wait() 이나 signal() 은 임계구역에서만(짧은 작업) 발생하도록 설계했고 busy wait 이 발생해도 CPU 점유 시간이 적다.

→ 임계구역이 매우 길거나 항상 점유된 프로그램을 갖는 환경에서는 busy wait 이 극도로 비효율적이다.

세마포 타이밍 오류

세마포는 발견하기 어려운 타이밍 오류를 야기할 수 있는데, 특정 실행 순서로 진행되었을 때만 발생하고 이런 순서로 항상 일어나는 건 아니어서…ㅠ

문제점

signal(mutex);
...
/*critical section*/
...
wait(mutex);

• 프로그램에 세마포에 대한 wait() , signal() 연산의 순서가 뒤바뀌었다.
  • 여러 프로세스가 동시에 임계 구역 안에서 실행될 수 있으니 상호 배제 요구 조건을 위반
  • 그러나, 이런 오류는 “여러 프로세스가 동시에 자기 임계구역 안에서 실행되었을 때”만 발생하므로 언제나 재현가능한 오류는 아님. → 발견 어려움.

wait(mutex);
...
/*critical section*/
...
wait(mutex);

• signal(mutext) 를 써야할 곳에 wait(mutex) 를 써버렸다.
  • 세마포 사용할 수 없으므로 두 번째 wait() 에서 영구 block
• 프로세스가 wait(), signal(), 둘 다 빠뜨렸을 때
  • 상호 배제 요구 조건 위반 또는 프로세스 영원히 block

모니터

모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 연산자 집합을 포함하는 ADT(Abstract data type, 추상화된 데이터 형) *ADT : 데이터와 이 데이터를 조작하는 함수들의 집합을 하나로 묶어 보호하는 것.

• 모니터 안에 항상 하나의 프로세스만 활성화 된다.
• 모니터 내에 정의된 함수만이 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에만 접근 가능.
  • 자원 액세스 연산 자체가 내부에 있고 모니터 내부에서 관리.
• condition 변수의 wait(), signal() 연산으로 동기화 됨.
• 같은 임계 구역 내에 있는 건 가능하지만, 둘 중 하나만 실행 됨. → 나머진 대기 상태.

모니터 구현

wait(mutex); // 임계 구역 들어가기 위해 대기
...
body of F
...
if (next_count > 0) // next 에서 일시중지되는 프로세스 갯수
	signal(next); // 다음 대기 중인 스레드 깨움
else 
	signal(mutext); // 대기 중인 스레드가 없으면 다른 스레드가 임계 구역에 접근하는 걸 허용

모니터를 세마포로 구현

x.wait {
    x_count++; // 대기 중인 스레드 수 증가 (대기 스레드 추가)
    if (next_count > 0) // 대기 중인 다른 스레드가 있다면
        signal(next); // 다음 대기 스레드를 깨워 실행
    else 
        signal(mutex); // 대기 중인 스레드가 없으면 뮤텍스 잠금 해제
    wait(x_sem); // 자신이 대기 상태로 들어감 (다른 스레드가 깨울 때까지 대기)
    x_count--; // 대기 중인 스레드 수 감소 (현재 스레드 대기에서 해제됨)
}

x.signal {
    if (x_count > 0) { // 대기 중인 스레드가 있다면
        next_count++; // 현재 실행될 스레드 수 증가 (next_count: 실행 대기 중인 스레드 수)
        signal(x_sem); // 대기 중인 스레드 중 하나를 깨움
        wait(next); // 자신의 실행을 중단하고 다른 스레드가 실행되도록 대기
        next_count--; // 실행이 끝난 스레드 수 감소
    }
}

모니터에서 프로세스 수행 재개 순서

x.wait(c) ← ‘c’ 는 우선순위 번호

• wait() 연산이 호출될 때, 일시 중지되는 프로세스 이름과 함께 “우선순위 번호” 를 넘긴다.
• x.signal() 수행 시, 가장 작은 우선순위 번호를 가진 프로세스가 수행 재개 된다.

💡라이브니스 Liveness

• 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 속성들.

요약~!

• 경쟁 조건 : 프로세스가 공유 데이터에 병행하게 접근할 때 발생.
• 임계구역 : 공유 데이터가 조작될 수 있는, 경쟁 조건이 발생할 수 있는 코드 영역.
• 임계 구역 문제(동기화) 해결책
  • 상호 배제 : 한 번에 하나의 프로세스만 임계구역에서 활성화.
  • 진행 : 프로그램들이 다음에 어떤 프로세스가 임계 구역에 들어갈지 결정하는 것.(요청한 프로세스들만 결정할 수 있어야 함.)
  • 한정된 대기 : 프로그램이 자기 임계구역에 들어가기 전, 대기하는 시간을 제한.
• Mutex Lock : 임계구역에 들어가기 전에 락을 획득하고, 임계구역에서 나올 때 락을 해제.
• Semaphore : 뮤텍스처럼 이진 값이 아닌 정수 값을 가지므로 여러 개가 한꺼번에 진입한다.
• Monitor : 프로세스가 특정 조건이 true 가 될 때까지 대기, 조건이 true 가 되면 서로에게 신호를 보낼 수 있게 허용하는 조건 변수를 사용한다.
• 임계 구역 문제에 대한 해결책들은 교착 상태를 포함한 라이브니스 문제를 겪을 수 있다.