[OS] 공룡책_6 동기화 도구들

bin1225·2024년 9월 13일

OS

목록 보기

6/10

6.1 배경

프로세스는 병렬로 실행될 수 있다는 점을 알았다. 이는 특정 프로세스는 어느 지점에서는 인터럽트 되고, 처리 코어는 다른 명령어를 실행하도록 할당될 수 있다.

이 과정에서 동기화 문제가 발생한다.

예를들어, count라는 변수를 공유하는 두 프로세스 a,b가 있다고 하자.

a는 count++를 수행한다.
b는 count--를 수행한다.

각 명령어는 우리 입장에서는 하나의 명령이지만 처리하는 컴퓨터 입장에서는 그렇지 않다.

register1 = count
register1 = count +1
count = register1

결국 명령어를 수행하기 위해서는 메모리에서 레지스터로 데이터를 가져오는 과정이 필요하다. 또 연산 후 다시 메모리에 적재해야 한다.

만약 a프로세스가 메모리에 계산으로 업데이트 된 값을 적재하기 전에 인터럽트가 발생하여 b가 실행된다면, a,b가 각각 한 번씩 실행되어 count값이 그대로 유지되어야 하는데 기대와는 다른 결과값이 나오게 된다.

이렇게 되려면 분명 타이밍이 맞아야하고 그럴 확률은 적다고 볼 수도 있다. 하지만 이러한 오류는 치명적이므로 동기화 문제를 해결할 방법들이 등장한다.

이렇게 여러 프로세스가 동일한 자료를 접근하고 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁상황(race condition)이라고 한다.

6.2 임계구역 문제 (The Critical-Section Problem)

race condition이 발생할 가능성이 있는 코드 영역을 critical-section이라고 부른다.
임계구역 문제에 대한 해결안은 세가지 요구 조건을 충족해야 한다.

상호 배제(mutual exclusion): 임계구역 내에서는 하나 이상의 프로세스가 동시에 실행될 수 없다.
진행(progress): 특정 임계구역 내에 실행되고 있는 프로세스가 없고, 해당 임계구역에 진입하고자 하는 프로세스들이 있다면, 나머지구역에서 실행중이지 않은 프로세스들만 다음에 누가 진입할지에 참여할 수 있으며, 이 선택은 무기한 연장될 수 없다.
한정된 대기(bounded waiting): 임계구역에 진입을 요청한 순간부터 진입하기까지 다른 프로세스들이 해당 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

단일 코어에서는 공유 변수를 수정하는 동안 인터럽트 발생을 막는다면 임계구역 문제를 간단히 해결할 수 있다.
하지만 다중 코어 환경에서는 간단히 해결이 불가능하다. 한 코어에서 인터럽트를 막는다고 해도 다른 코어들을 통제하기엔 비효율적이고 보장되지 않는다.

6.3 Peterson의 해결안

임계구역에 대한 고전적인 해결방안으로, 현재의 컴퓨터 작동 방식에서는 올바른 실행을 보장하지 않는다.
임계구역 문제 해결에 대한 전반적인 이해를 제공한다.

개념

Peterson 해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

	int turn;
    boolean flag[2];

turn은 임계구역으로 진입할 프로세스의 번호를 나타낸다.
flag[i]==true는 i번 프로세스가 임계구역에 진입할 준비가 되었다는 것을 의미한다.
즉 turn==i이고 flag[i]==ture라면 i프로세스가 임계구역에 진입한다.

Peterson 해결안에서 프로세스 구조

	while (true) {
    	flag[i] = true;
        turn = j;
        while (flag[j] && turn ==j);
        
        /* critical section */
        
        flag[i] = false;
        
        /* remainder section */
    }

증명

1. mutual exclusion

임계구역에 진입하기 위해서는 turn==i이고 flag[i]==ture를 만족해야 한다.

turn변수는 동시에 두개의 값을 가질 수 없다. 따라서 임계구역 내에는 하나의 프로세스만 진입할 수 있다는 것이 보장된다.

2,3. progress, bounded waiting

프로세스 구조를 보면 진입 전 turn변수를 다른 프로세스의 값으로 설정한다.
이 변수가 바뀌기 위해서는 임계구역에 들어간 다른 프로세스가 임계구역을 탈출한 후 재진입 전에 turn변수를 변경할 때 뿐이다. 그리고 그때까지 while문을 통해 공회전한다.
이는 특정 프로세스가 한 번 진입했다면 그 다음엔 대기중이던 프로세스도 한 번은 임계구역에 들어갈 수 있다는 것을 의미한다.

최신 컴퓨터 아키텍처에서는 성능 향상을 위해 프로세서 및 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있다. 따라서 Peterson 해결방식이
정상적으로 적용되지 않을 가능성이 존재한다.

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

6.4.1 메모리 장벽

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

강한 순서: 한 프로세스의 메모리 변경 겨로가가 다른 프로세서에 즉시 보임.
약한 순서: 한 프로세스의 메모리 변경 겨로가가 다른 프로세서에 즉시 보이지 않음.

강한 순서 모델을 사용하는 경우 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 실행 중인 스레드에 메모리 변경사항이 보이는 것을 보장한다.
이러한 명령어를 메모리 장벽(memory barriers) 또는 메모리 펜스(memory fences)라고 한다.

6.4.2 하드웨어 명령어

한 워드의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

test_and_set(): 한 워드의 내용을 검사 및 변경

compare_and_swap(): 두 워드의 내용을 교환

일반적으로 compare_and_swap 명령어는 상호배제를 제공하기 위해 직접 사용되기 보다는 다른 임계구역 문제 해결 도구를 구축하기 위한 기본 구성요소로 사용된다.

6.4.3 원자적 변수 (Atomic Variables)

정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다.
원자적 변수를 조작하는 함수는 종종 compare_and_swap()연산을 사용하여 구현된다.

원자적 변수는 모든 상황에서 경쟁조건을 완벽히 해결하지 않는다.
예를 들어, 생산자 소비자 문제에서 count값을 원자적 변수로 선언했을 때 count값 자체는 원자적으로 갱신된다. 하지만 소비자가 여러명이라면 count값이 증가 됐을 때 여러명의 소비자가 동시에 버퍼에 진입할 가능성이 있다.

6.5 Mutex Locks

하드웨어 기반 해결책은 응용 프로그래머가 사용할 수 없다. 따라서 임계구역 문제를 해결하기 위한 상위 수준 소프트웨어 도구가 등장한다. 그 중 가장 간단한 도구가 mutex 락이다.

프로세스는 임계구역 진입 전 acquire()함수를 호출하여 락을 획득해야 한다.
임계구역을 빠져나올 때 release()함수를 호출하여 락을 반환한다.

mutex락의 acquire()함수 구조는 다음과 같다.

	acquire() {
    	while (!available) 
        	; /* busy wait */
        available = false;
    }

이렇게 while loop를 이용해 대기하는 방식을 바쁜 대기라고 한다.
바쁜대기는 대기 중에도 CPU자원을 소모하기 때문에 락 획득을 위해 대기하는 프로세스가 많거나 대기 시간이 길어지는 경우 자원의 낭비를 유발한다.
이러한 방식을 스핀락이라고도 부른다.

반대로 대기 시간이 짧은 경우 스핀락이 유리하다. 여기서 짧다는 것은 대기 시간이 스레드를 대기상태로 옮기고 락이 사용해질 때 다시 준비상태로 복원하는 문맥교환에 소요되는 시간보다 짧은 시간을 의미한다.

6.6 세마포 (Semaphores)

mutex보다 정교하게 동기화할 수 있는 도구이다.
세마포 S는 정수 변수로서, 초기화를 제외하고는 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다.

wait()

	wait(S) {
    	while(S<=0)
        ; /* busy wait */
        S--;
    }

signal()

	signal(S) {
    	S++;
    }

이 두가지 연산은 원자적으로 실행되어야 한다.

6.6.1 세마포 사용법

세마포 값이 1인 경우 mutex와 동일하게 작동한다.
가용 자원의 개수만큼 세마포를 초기화하면, 해당 자원의 개수만큼만 프로세스가 접근할 수 있게 된다.
세마포를 활용하여 프로세스간 실행 순서도 제어할 수 있다.

ex)
synch라는 세마포를 0으로 초기화하고,

S1
signal(synch);

wait(synch);
S2

이런식으로 구성하면 반드시 S1이 실행된 후에 S2가 실행되는 것을 보장한다.

6.6.2 세마포 구현

mutex의 바쁜대기와 달리 대기큐로 프로세스를 이동시켜 임계구역에 진입가능할 때까지 대기하도록 할 수 있다.

	typedef struct {
    	int value;
    	struct process *list;
    } semaphore;

위와 같이 특정 세마포에 대기중인 프로세스 list를 관리한다.

signal()연산을 통해 대기중인 프로세스가 있는 경우 대기큐에서 준비큐로 옮기는 작업을 진행한다.

큐잉 전략을 통해 어떤 프로세스를 먼저 옮길 것인지 결정할 수 있다.

6.7 모니터

세마포와 mutex는 함수 호출 순서에 따라 작동이 달라진다. 잘못 사용하면 발견하기 어려운 오류를 야기한다. (특정 실행순서에서만 발생, 항상 발생하지도 않음)
이러한 프로그래머의 실수를 방지하기 위해 동기화 도구를 통합하여 고급 언어 구조물을 제공한다. 그 중 하나가 모니터(monitors)이다.

6.8 라이브니스

라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야하는 일련의 속성을 말한다.
라이브니스 실패로 이어질 수 있는 두가지 상황을 본다.

6.8.1 교착상태 (Deadlock)

두 개 이상의 프로세스들이, 오로지 대기중인 프로세스들 중 하나에 의해서만 야기될 수 있는 이벤트를 무한정 기다리는 상황을 의미한다.

6.8.2 우선순위 역전 (Priority Inversion)

만약 우선순위가 낮은 프로세스가 자원을 선점하고 있을 때, 우선순위가 더 높은 프로세스가 대기큐에 들어가거나 자원을 이용가능할 때까지 대기하는 현상이다.
이렇게 됐을 때 그 사이에 존재하는 프로세스가 가장 높은 우선순위인 프로세스보다 먼저 CPU자원을 할당받게 되는 현상이 발생한다. (높은 우선순위 프로세스가 대기큐에서 자원 사용을 기다리기 때문)
우선순위 상속 프로토콜을 구현하여 해결한다. 우선순위 상속 프로토콜이란 더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 프로세스들은 자원 사용이 끝날 때까지 더 높은 우선순위를 상속받는다.

bin1225

이전 포스트

[OS] 공룡책_5 CPU 스케줄링

다음 포스트