운영체제 -2-

동시에 여러 개의 프로세스가 동일한 자원을 획득하기 위해 경쟁하는 것 - 경쟁상황

경쟁 상황에서는 특정 순서에 따라 값이 다르게 나올 수 있으므로 동기화가 필요하다

 

임계구역 - 다른 프로세스와 공유하는 자원

임계구역에서 동기화를 하는 방법

• 상호배제 : 임계구역에서 프로세스가 수행되는 동안 다른 프로세스는 임계구역에 들어갈 수 없다
• 진행: 임계구역을 들어가기 위해 대기한 프로세스들중 적절하게 선택해야 한다
• 한정된 대기 : 기아현상을 막기 위해 임계구역에 들어간 프로세스가 계속해서 임계구역을 점유할 수 없다

 

동기화를 하는 방법

하드웨어 방법

 

메모리 장벽

캐시나 레지스터에 값을 캐싱하는 데 각 코어마다 캐싱하는 데이터의 값이 다를 수 있다. 따라서 스레드 실행 도중 메모리 장벽 연산을 만나면 변경된 값을 메모리에 반영한다 (ex java volatile 변수)

 

하드웨어 명령어

하드웨어 자체적으로 원자적 명령어를 지원해준다. 

 

test and set 

한 워드의 내용을 검사하고, true로 변경한다.

boolean test_and_set(boolean *target){
	boolean rv= *target;
    *target = true;
    return rv;
}

 

 

compare and swap,

두 워드의 내용을 원자적으로 교환

int compare_and_swap(int *value, int expected, int new_value){
	int temp = *value;
  	if(*value == expected)
		*value = new_value;
        
    return temp;
  }

 java atomic 변수도 cas 사용

 

소프트웨어 방법

락을 획득과 반환은 원자적으로 해야 한다.

 

mutex 락

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

 

스핀락과 mutex락

 

스핀락

• 단점 : busy waiting을 해야 한다(반복문을 계속 돌면서 lock 획득 함수를 계속 실행해야 한다), 
• 장점 : 문맥교환이 필요하지 않다

다중 코어 시스템의 특정상황에서는 스핀락이 선호 된다. 

 

mutex락

• 장점 : busy waiting을 하지 않는다. 프로세스가 대기 상태로 바뀌기 때문에 다른 프로세스가 cpu 자원을 활용할 수 있다
• 단점: 문맥 교환이 2번 발생하므로 비효율적 일 수 있다.(대기 상태로 전환 1번, 대기 상태에서 락을 얻어 복원 상태로 2번)

결론 : 문맥교환을 두 번 하는 시간보다 스핀락이 짧을 경우 스핀락을 사용하고 아닐 경우 mutex락을 사용하자

 

세마포 

세마포는 정수 변수로, wait과 signal로만 접근할 수 있다. wait과 signal 연산은 반드시 원자적으로 수행 되어야 한다. wait은 값 감소, signal은 값 증가. 정수 변수는 양수로 사용할 수 있는 자원의 개수를 나타낸다.

• 이진 세마포 : mutex락 과 유사하게 동작
• 카운팅 세마포 : 유한한 개수의 자원 접근 제어 가능

busy waiting을 하는 세마포는 0이하의 값을 가질 수 없다 

 

프로세스 상태 변경 방식은 만약 가용자원의 개수가 0 이하일 경우 프로세스를 대기 큐에 넣고 대기 상태로 변경한다. 이후 signal 연산을 통해 대기하는 프로세스를 깨운다. 이 경우 세마포는 0이하의 값을 가질 수 있으며 음수 세마포의 값은 대기하고 있는 프로세스의 수이다

 

모니터

세마포 또는 mutext 락을 이용하여 임계구역 문제를 해결할 때 프로그래머가 세마포를 잘못 사용하면 오류가 발생하기 쉽다. 따라서 간단한 동기화 도구를 통합해서 제공해 줄 수 있다.

 

모니터 구조물에서 모니터 안에 항상 하나의 프로세스만이 활성화 되도록 보장해 준다. 

 

모니터는 공유 자원 + 공유 자원 접근함수로 이루어져 있고, 2개의 큐를 가지고 있다. 각각 mutual exclusion(상호배타) queue, conditional synchronization(조건동기) queue이다.

 

• 상호배타 큐는 말그대로 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐이다.
• 조건동기 큐는 이미 공유자원을 사용하고 있는 프로세스가 특정한 호출 wait()을 통해 조건동기 큐로 들어갈 수 있다.

조건동기 큐에 들어가 있는 프로세스는 공유자원을 사용하고 있는 다른 프로세스에 의해 깨워줄 수 있다.

 

자바는 모니터를 제공하는 대표적인 언어이며, 자바의 모든 개체는 모니터가 될 수 있다. 

 

synchronized 키워드는 배타동기를 수행하는 함수를 말한다. 즉, 해당 함수에는 단 하나의 쓰레드만 접근할 수 있다.

 

조건동기는 특정한 메서드 호출로 사용할 수 있다.

• wait(): 호출한 쓰레드를 조건동기 큐에 삽입한다.
• notify(): 조건동기 큐에 있는 하나의 쓰레드를 깨워준다.
• notifyAll(): 조건동기 큐에 있는 모든 쓰레드를 깨워준다.

라이브니스

프로세스가 실행 수명 주기 동안 진행을 보장하기 위한 시스템을 위한 속성, 무기한 대기등은 라이브니스 실패

 

교착 상태

서로 자원을 점유한채 서로 상대방의 자원을 요구 함으로써 무한정 기다리는 상태 

 

우선 순위 역전

 

 

• task3이 공유 자원 접근 위해 바이너리 세마포어 (binary semaphore) 획득
• 스케줄러에 의해 task1이 수행됨 
• task1은 task3이 갖고 있는 세마포어를 획득하기 위해 기다림 (waiting)
• 스케줄러에 의해 task3이 다시 실행됨
• 이 때 세마포어와 관련 없는 task2가 task3보다 우선순위가 높아 스케줄러에 의해 실행됨.
• 그러면서 task3의 완료가 뒤로 밀리며, 우선순위가 가장 높은 task1이 결국 가장 늦게 수행됨 (우선순위 역전)

해결 : 우선 순위 상속 프로토콜을 구현해서 해결한다.

 

우선 순위 상속 프로토콜

더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 포로세스는 문제가 된 자원의 사용이 끝날 때 까지 더 높은 우선순위를 상속 받는다.

 

* CAS

락 없는 알고리즘( non-blocking)을 구현 하기 위해 cas 명령어를 사용한다. 

 

낙관적락, 비관적락

• 낙관적락 : CAS 기반 접근 방식, 낙관적으로 자신이 변수 갱신이 가능하다고 생각하고 충돌 없이 성공적으로 갱신할때 까지 반복적으로 다시 시도한다
• 비관적락 : 이미 다른 스래드가 변수를 갱신하는 중이라고 가정하고 변수를 갱신하기 전에 락을 얻는다. 상호 배제 락킹 방식(락을 획득하는 방식)

 

ABA Problem

CAS연산에서 공유 객체에 대한 변화를 감지하지 못할 때 발생하는 현상을 ABA현상이라고 한다.

 

• 스레드 1에서 A를 POP하려 한다 B를 가리킴
• 이때 스레드 2에서 A와 B를 POP한다
• 스레드 3에서 A를 다시 PUSH 한다
• 이후 cas 연산이 실행된다. A값을 일치하므로 문제 없이 수행된다

 

이러한 ABA문제의 해결책으로는 double check CAS 이 있다. pop의 Count를 포함한 double check를 통해서

주소값을 CAS해주고, pop한 count 또한 CAS해주면서 일관성을 보장해준다.