운영체제 · 프로세스 동기화

프로세스 동기화 (Process Synchronization)

✓ 정의 : 협력하는 프로세스 사이에서 실행 순서 규칙을 정하여 공유 자원의 일관성을 보장하는 것

✓ 프로세스가 서로 협력하며 공유 자원을 사용하는 상황에서, 경쟁 조건이 발생하면 공유 자원을 신뢰할 수 없게 만들 수 있다. 이를 방지하기 위해 프로세스들이 공유 자원을 사용할 때 특별한 규칙을 만드는 것이 프로세스 동기화이다.

✓ 경쟁 조건 (Race Condition) : 여러 프로세스(또는 스레드)가 공유 자원에 동시에 접근할 때, 공유 자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황

✓ 임계 구역 (Critical Section) : 여러 프로세스(또는 스레드)가 자원을 공유하는 상황에서, 하나의 프로세스(스레드)만 접근할 수 있도록 제한해둔 코드 영역

do {
    // Entry Section
    // Critical Section
    // Exit Section
    // Remainder Section
} while (true);

동기화와 관련한 고전적인 문제

✓ 은행 계좌 문제 (Back Account Problem)

부모는 은행 계좌에 입금을 한다. 자식은 은행 계좌에서 출금한다.
입금과 출금 과정이 별도로 이루어져야 한다.
크리티컬 섹션 : 은행 계좌

✓ 독자 저자 문제 (Readers Writers Problem)

독자는 책(공유 데이터베이스)에 쓰여있는 글을 읽는다. 저자는 책에 글을 써서 추가한다.
독자가 글을 읽고 있다면, 독자는 추가적으로 글을 읽을 수 있지만, 저자는 글을 쓸 수 없다.
저자가 글을 쓰고 있다면, 독자는 글을 읽을 수 없으며, 저자 또한 추가적으로 글을 쓸 수 없다.
크리티컬 섹션 : 책 (공유 데이터베이스)

✓ 생산자 소비자 문제 (Producer Consumer Problem)

한정 버퍼 문제(Bounded Buffer Problem)라고도 한다.
생산자는 물건을 생산하여 창고(버퍼)에 넣는다. 소비자는 창고에서 물건을 꺼내서 소비한다.
창고가 가득 차면 생산자는 물건을 넣을 수 없고, 창고가 비어 있으면 소비자는 물건을 소비할 수 없다.
크리티컬 섹션 : 창고 (버퍼)

✓ 식사하는 철학자 문제 (Dining Philosopher Problem)

원형 테이블에 철학자들이 앉아있고 철학자의 수만큼 젓가락이 철학자 사이에 하나씩 놓여있다.
철학자들이 식사를 하기 위해서는 양쪽에 하나씩 놓여있는 젓가락을 둘 다 들어서 사용해야 한다.
어떤 철학자가 젓가락을 사용 중이라면, 다른 어떤 철학자는 식사를 할 수 없다.
크리티컬 섹션 : 젓가락

임계 구역 문제의 해결 조건

✓ 상호 배제 (Mutual Exclusion) : 어떤 프로세스(또는 스레드)가 임계 구역에서 작업 중일 때, 다른 프로세스는 임계 구역으로 접근할 수 없다.

✓ 진행 (Progress) : 임계 구역에서 작업 중인 프로세스가 없다면, 임계 구역으로 진입하려는 프로세스 중 하나를 적절히 선택하여 임계 구역에 진입할 수 있게 해야 한다.

✓ 유한 대기 (Bounded Waiting) : 다른 프로세스의 기아(Starvation)을 방지하기 위해, 임계 구역에 한 번 접근했던 프로세스는 다시 임계 구역에 들어갈 때 제한을 두어야 한다.

임계 구역 문제의 해결 방안

✓ 소프트웨어 동기화 방법

피터슨의 알고리즘 (Peterson's Algorithm) : 피터슨의 해결안(Peterson's Solution)이라고도 하며, 2개의 프로세스만 있을 때 사용할 수 있다.
데커의 알고리즘 (Dekker's Algorithm) : 피터슨의 알고리즘과 비슷하며, 2개의 프로세스만 있을 때 사용할 수 있다.
램포트의 빵집 알고리즘 (Lamport's bakery algorithm) : 2개 이상의 프로세스에서 사용할 수 있다.

* Peterson Algorithm

// Shared data
int turn;
bool flag[2];

// Process i
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    /* Critical Section */
    flag[i] = false;
    /* Remainder Section */
} while (true);

// Process j
do {
    flag[j] = true;
    turn = i;
    while (flag[i] && turn == i);
    /* Critical Section */
    flag[j] = false;
    /* Remainder Section */
} while (true);

✓ 하드웨어 동기화 방법

락(lock)을 이용한 해결 방안이다. 프로세스가 락을 획득해야만 임계 구역에 진입할 수 있고, 임계 구역을 벗어나면 락을 반납하여, 임계 구역 문제를 해결한다.
싱글 프로세서 환경에서는 공유 데이터가 변경되는 동안 인터럽트를 막으면 임계 구역 문제를 해결할 수 있다. 비선점형 커널에서도 이 방법을 사용한다.
하지만, 멀티 프로세서 환경에서는 시스템 효율성 때문에 인터럽트를 막을 수 없다. 멀티 프로세서 환경에서는 동기화 하드웨어로 임계 구역 문제를 해결할 수 있다. 주로 TestAndSet()과 Swap() 명령어로 이를 구현한다.

* TestAndSet
bool TestAndSet(bool *target) {
    bool ret = *target;
    *target = true;
    return ret;
}
do {
    while (TestAndSet(lock));
    /* Critical Section */
    lock = false;
    /* Remainder Section */
} while (true);

* Swap
void Swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}
do {
    key = true;
    while (key == true) Swap(&lock, &key);
    /* Critical Section */
    lock = false;
    /* Remainder Section */
} while (true);

저작자표시 비영리 변경금지

티스토리툴바

운영체제 · 프로세스 동기화

티스토리툴바