운영체제 - 6장 동기화 도구들

• 임계 구역 문제가 무엇인지 race condition이 무엇인지

• 하드웨어 솔루션인 memory barriers, compare and swap, atomic variables가 무엇인지

• 소프트웨어적인 툴 mutex lock, semaphore, monitor, condition variable가 무엇인지

• 평가 툴들이 무엇인지 언제 더 유리한지

배경

프로세스들은 동시에 실행된다.

• 실행 중간에 언제든지 인터럽트가 발생해 다른 프로세스가 실행될 수 있다.

이러한 작업들로 인해 공유된 데이터들이 불일치성(inconsistency)이 생긴다

이러한 문제를 동기로 협력하고 있는 프로세스들이 순차적으로 실행시키는 방법을 고민하게 되고 이것이 동기화의 주된 동기가 됐다.

생산자-소비자 문제의 한정된 버퍼 문제에서 in, out 포인터로 같은 메모리를 가르키게 되면 버퍼의 방이 가득 차있는지 비어있는지 알 수 가 없었는데, 이를 counter 변수(비어있으면 0, 차있으면 방의 개수와 일치)로 해결할 수 있다.

counter가 버퍼사이즈 보다 크다면 계속 반복문이 실행되고 (busy waiting), 버퍼 사이즈보다 작아진다면 in 함수를 쓰고 버퍼 사이즈를 추가해서 생산자와 소비자 동기화하게 된다.

소비자 입장에서는 counter가 0이라면 (비어있다면) 계속 반복문을 하고 0보다 크면 out함수를 사용할 수 있다.

race condition, 경쟁 조건
순서가 바뀌면 결과가 바뀌고 이 결과가 개발자가 원하는 상태가 아닐 때 경쟁 조건이라고 한다.

메모리의 값을 바꾸는 것이기 때문에 cpu 레지스터에 값을 추가해서 카운터에 저장하는 방식으로 한다. (감소도 같은 요령)

ex. 감소하고 증가하거나, 증가하고 감소해도 결과는 같은 값이 되어야 되는데 그렇지 않는게 전형적인 race condition이다.

또 다른 race condition 예제

두 개의 다른 프로세스가 fork()를 호출했을 때 커널 변수가 next_available_pid로 pid를 할당해주는데 pid를 증가하기 전에 같은 명령어가 들어오면 같은 pid를 할당해줄수도 있다.
=> 상호베타가 필요하다 (하나가 끝나기 전에 다른 작업을 실행하지 못하게 하는 것)

임계구역(Critical-Section) 문제

임계구역인 일종의 코드 세그먼트이다.

n개의 프로세스들이 공유 자원을 갖고 실행됐을 때 코드가 공유 자원에 접근(변수 업데이트, 데이블, 파일 쓰기 등)하는 영역이 임계구역이다.

그래서 한 개의 프로세스가 임계구역에 있을 때, 다른 프로세스들이 임계 구역에 들어오지 못 하게 하는것이 임계구역 문제이다.

임계구역의 시작점은 entry point 끝나는 지점은 exit section이라고 한다.

임계구역 해결안
1. mutual exclusion : 어떤 프로세스가 임계 구역에서 실행 중이라면 그 어떤 프로세스도 임계 구역에 접근할 수 없다.

2. progress : 임계구역에 아무 프로세스가 없으면 프로세스가 들어갈 수 있는 진행 상황을 만들어 무기한 대기 상황을 방지

3. bounded waiting : 대기중인 프로세스들의 대기 시간이 한정적이어야 한다.

• 프로세스는 항상 non-zero speed이다
• 프로세스들의 상대적인 속도들의 대해서는 고민하지 않는다.

운영체제에서 임계구역 처리
커널이 선점인지 비선점인지에 따라 접근방식이 다르다.

• 프로세스들이 실행 중간에 선점 당해 멈출수도 있는것이 선점 (구현이 어렵다. cpu가 여러개인 SMP 같은 구조)
• 선점이 없어서 실행 중간에 멈추지 않는 경우가 비선점 (실시간 프로그램에서 비유용하다)
  • 단일 코어 구조일 때는 timer interrupt를 차단해서 프로세스 전환이 일어나지 않게 하여 임계 구역 보호를 가능하게 할 수 있다.
  • 보통 현대의 OS는 선점 구조로 되어있다.

Peterson의 해결안

순수하게 SW적으로만 임계구역 문제를 해결하기 위한 방안, 모든 운영체제(3개의 프로세스 이상에서는 불가)의 적용되지 않지만 임계구역 문제 알고리즘에 기원이 된다.

load와 store 변수를 atomic하게 만들어서 인터럽트되지 못하게 만든다.

두 개의 프로세스$P_i, P_j$가 두 개의 변수를 공유한다고 하자.

int turn;
boolean flag[2]

• turn 변수는 어떤 프로세스가 임계구역에 들어갈 차례인지 저장한는 변수
• flag 배열은 어떤 프로세스가 임계구역에 들어갈 준비가 되었는지 알려주는 변수

임계구역으로 진입하기 위해서 P는 먼저 flag[i]를 참으로 만들고, turn을 그로 지정한다.

이렇게 함으로써 프로세스 그가 임계구역으로 진입하기를 원한다면 진입 가능 하다는 것을 보장한다.

만일 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 코와 드로 지정될 것이다. 그러나 둘 중 오직 한 배정만이 지속된다.

다른 배정은 발생하기는 하지만 곧바로 겹쳐 쓰이게 된다. turn의 궁극적인 값이 둘 중 누가 먼저 임 계구역으로 진입할 것인가를 결정한다.

아래 3가지 사실이 보장되어야 이 해결책이 올바르게 동작한다는 것을 증명할 수 있다.

• 상호 배제가 제대로 지켜진다는 사실
• 진행에 대한 요구 조건을 만족한다는 사실 (progress)
• 대기 시간이 한 없이 길어지지 않는다는 사실 (bounded waiting)

Peterson의 해결안이 위에 임계구역 해결안을 모두 만족한다.

• Peterson 해결안 현대의 운영체제에서 작동 보장이 되지 않는다. (현대 운영체제는 최적화 때문에 프로그램 실행 순서가 순차적이지 않을 수 있는데 (dependencies가 없을 경우) 이 때문에 작동이 어려울 수 있다.)

동기화를 위한 하드웨어 지원

• uniprocessor : 임계 구역 들어가기 직전에 인터럽트 차단 나오기 전에 인터럽트 차단 해제 하는 방식

• multiprocessor : 인터럽트 차단을 사용할 경우 비효율적이기 때문에 다음 방법들을 사용한다.

  • Memory barriers
  • Hardware instructions
  • Atomic variables

소프트웨어 기반 해결책이 아닌, 임계구역 문제 해결을 위한 세 가지 하드웨어 명령어가 있다.

메모리 장벽, Memory Barriers
메모리 모델이라고도 한다, 컴퓨터 아키텍처가 응용 프로그램에게 제공하느 메모리 접근 시 보장되는 사항을 결정한 방식

• Strongly ordered : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 전파되서 보임

• Weakly ordered : 즉시 전파되지 않는 방식

즉, 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장하는 것이고, 전파시키는 명령어가 메모리 장벽이다.

메모리 베리어가 실행되면 현재 진행중인 load와 store가 종료된 후에 새로운 load와 store가 수행되도록 한다.

하드웨어 명령어, hardware instruction

현대의 많은 기계들은 한 워드(word)의 내용을 검사하고 변경(test-and-modify)하거나, 두 워드의 내용을 원자적으로(atomic) 교환(swap)할 수 있는, 즉 인터럽트 되지 않는(uninterruptibly) 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

• Test-and-Set instruction

명령어가 atomic하게 실행되는 중요한 특징이 있다.

만일 두 개의 test_and_set() 명령어가 동시에 실행된다면(각각 다른 코어에서), 이들은 어떤 임의의 순 서로 순차적으로 실행될 것이다.

만일 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 lock이라는 boolean 변수를 선언하여 상호 배제를 구현할 수 있다.

1. atomic 하게 실행되고,
2. 통과된 파라미터의 원래(origianl)의 값을 반환해준다.
3. 통과된 파라미터의 새로운 값을 true로 설정해준다.

• Compare-and-Swap instruction

test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환에 기반을 둔 다른 기법이다.

CAS는 3개의 피연산자를 대상으로 연산을 하며, 피연산자 value는 오직 (*value == expected) 수식이 참일 때에만 new_value로 지정된다.

어떠한 경우에도 CAS 명령어는 언제나 value의 원래 값을 반환한다.

역시 atomic하게 실행되고, 임의의 순서로 순차적으로 실행된다.

spin-lock : 반복적으로 lock의 상태를 확인하는 것 (CPU를 사용한다고 함)

만약 다른 스레드가 lock을 소유하고 있다면 그 lock이 반환될 때까지 계속 확인하며 기다리는 것이다. "조금만 기다리면 바로 쓸 수 있는데 굳이 컨텍스트 스위칭으로 부하를 줄 필요가 있나?" 라는 컨셉으로 개발된 것으로 크리티컬 섹션에 진입이 불가능할때 컨텍스트 스위칭을 하지 않고 잠시 루프를 돌면서 재시도 하는 것을 말합니다. Lock-Unlcok 과정이 아주 짧아서 락하는 경우가 드문 경우(즉; 적절하게 크리티컬 섹션을 사용한 경우) 유용하다. Spin Lock 은 다음과 같은 특성을 갖는다.

위 두 알고리즘 모두에 들어간다.

• Atomic Variables (원자 변수)

CAS 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않는 경우가 많고, 임계 구역 문제를 해결하기 위한 다른 도구를 구축하기 위한 기본 구성요소로 많이 사용된다.

그 도구 중 하나가 원자 변수이다.

원자적 변수는 카운터가 증 가할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는 데 사용될 수 있다.

즉, 원자 변수란 인터럽트 없이 한 번에 일어날 수 있게 하는 것

Mutex Locks

하드웨어 명령어들을 직접 코딩하는 것은 어려운 작업이다.

mutex lock은 운영체제 설계자들이 임계구역 문제를 해결하기 위해 소프트웨어적으로 상위 수준으로 추상화된 가장 간단한 형태이다.

mutex lock에서는 acquire()(락을 흭득), release()(락을 반환)로 lock을 조절한다. 그리고 이 명령어들은 atomic 해야 한다.

우리가 설명한 mutex 락 유형을 스핀락(spinlock)이라고도 한다. 락을 사용할 수 있을 때까지 프로세스가 “회전”하기 때문이다.

세마포

mutex lock 보다 복잡하고 할 수 있는 것이 많은 툴이다.

wait()와 signal() 함수를 사용하고 atomic하게 연산한다.

세마포 활용

• counting semaphore : 정수 범위를 제한하지 않는다. 만약 3으로 정수를 둔다면 리소스, 프로세스를 3개까지 사용할 수 있다는 뜻

• binary semaphore : 정수(활용할 수 있는 리소스의 갯수)를 0과 1만 사용하는 경우. mutex lock과 같다.

세마포 구현

두 개 이상의 프로세스가 동시에 wait()나 signal()를 실행시킬 수 없게 보장해야 한다.

결국 구현은 임계구역 문제로 귀결된다.

• busy waiting : 프로세스가 CS에 오래 머물러있지 않을 때는 유리한 방법이다.

  • Busy waiting을 사용하지 않는 방법으로는 (cpu를 소모하지 않고, 기다리지 않고) waiting queue에 넣을 스스로를 봉쇄하는 방법이 있다.

  • waiting queue에 들어가는 값으로는 value(정수 타입)과 리스트 안에 다음 리코드에 대한 포인터(대기열)가 들어간다.

  • 두 가지 연산

    • block : 프로세스가 wait 중일 때 세마포가 0보다 크지 않을 시 스스로 block, suspend 상태로 가는 것
    • wakeup : waiting queue에서 세마포를 기다리는 프로세스들을 ready queued에 넣어주는 연산

세마포의 문제

세마포의 초기값에 따라서 mutex값을 넣고 signal(), wait()의 값을 계산하는데 이들의 조합이 생각보다 잘 안 맞을 수도 있다. (실행 이후에 문제가 생긴다.)

모니터

모니터는 프로세스 동기화를 위해 조금 더 높은 수준의 추상화를 실현한 방법이다. 객체의 개념과도 비슷하다.

모니터 내에 공유 변수들이 있고 여러 함수들이 있다. 모니터 내부에 실행할 프로세스만 선택해서 함수를 실행시킬 수 있게할 수 있다.

실행 중인 프로세스가 어떤 이유로 더 진행할 수 없으면 condition variable을 사용하여 스스로 suspend 할 수 있다.

condition variables : 조건 변수는 개념적으로 대기열의 이름이다. ex) x, y;

x.wait() : siganl 때까지 프로세스 스스로가 suspend하는 연산

x. signal() : 대기중인 프로세스를 재개한다.

프로세스(또는 스레드)는 모니터 안에서 함수를 방해받지 않고 실행할 수 있는 것을 보장받는다.

라이브니스

평가

ref

• https://brownbears.tistory.com/45