[TIL] 20250124 TIL : Synchronization : Problem and Solutions pt.2 (2/3)

Jaeyoung Ko·2025년 1월 24일
TIL

[운영체제 - 동기화]

참고한 자료:
Operating System: Concepts 10th edition BY A.Silberschatz

오늘도 우리와 함께하는 대실버스타츠 교수님의 킹-룡 책




previously on Sync pt.1
https://velog.io/@nuketuna/TIL-Synchronization-Race-Condition

<1> Background
<2> Race Condition
<3> Critical Section
<4> Solution for Critical Section Problem

(1) Mutual Exclusion
(2) Progress
(3) Bounded Waiting

<5> Solution Algorithm

  1. Alternating Algorithm
  2. State Testing Algorithm
  3. Peterson's Solution





<1> Classical Synchronization Problems

A. Producer-Consumer Problem (w. Bounded-Buffer Problem)


Producer-Consumer Problem은 멀티 프로세스 혹은 멀티 스레드 환경에서 shared resource에 대한 접근 제어와 관련하여 발생하는 전통적인 동기화 문제이다.

이 문제에서 producer process는 정보를 생산하고, consumer process가 정보를 소비하는 역할을 하는데, 한편으로는 client-server 패러다임에 대한 은유를 제공한다.

만약 둘 이상의 producer process가 buffer에 동시에 정보를 생산해 넣거나, 둘 이상의 consumer process가 동시에 동일한 buffer 내 데이터를 소비하려고 한다면 문제가 발생할 것이다.

이에 대해 binary semaphore나 mutex lock을 통해 락을 걸어줌으로 해결할 수 있다.



B. Readers-Writers Problem


하나의 데이터베이스가 여러 병행 process 간 공유되는 상황에 관련한 동기화 문제이다. 이 process들은 다음 두 가지 유형으로 나눌 수 있다.

  • Readers : 데이터베이스에 대한 read작업으로 조회를 할 뿐, update를 수행하진 않는다.

  • Writers : 데이터베이스에 대한 write 작업을 통해 update를 수행한다.

여러 reader가 동시에 데이터베이스를 접근하는 것에 대해 conflict는 발생하지 않지만,

writer의 경우에는 다른 writer 프로세스 혹은 reader 프로세스와 동시에 데이터베이스에 접근하게 되면 confusion이 야기될 수 있다.

이러한 문제점을 발생하지 않도록 보장하기 위해 writers의 쓰기 작업 동안은 배타적인 접근 권한을 가지게 할 필요가 있다.


Readers-Writers 문제는 우선순위와 연관되어 여러 변형들이 존재한다.

1) Reader priority

여러 reader는 동시에 접근 가능하나, writer에 관해서는 reader가 없을 때만 접근 가능하도록 하게 한다. 이 방법으로 writer에게 배타적으로 접근하도록 하나, 새로운 reader가 계속 추가될 경우, writer는 계속해서 대기하다가 starve 하게 될 수 있다.

2) Writer priority

접근에 대한 제한을 writer가 아니라 reader에게 검으로서, writer가 자원에 접근하는 동안 reader는 접근하지 못하고 즉시 대기하도록 하는 방식이다. 이 경우, writer가 계속 추가되어 쓰기 작업을 하면 reader들은 기약없이 대기하다가 starve하게 될 수 있다.

3) Fair priority

Reader와 Writer 모두가 공정한 스케줄링 제어를 받도록 하여 semaphore나 monitor를 활용하여 구현하는 방식이다.



C. Dining-Philosophers Problem


Dining-Philosophers Problem은 원탁에 둘러 앉은 철학자들이 thinking()과 eating() 두 작업 상태만 가지게 되는 가정에서 시작한다. 이 때, eating을 수행하려면 철학자는 인접한 철학자와 공유하는 양쪽의 젓가락을 모두 점유해야만 수행 가능하다.


Deadlock 발생 시나리오

철학자들이 모두 오른손잡이라서 오른쪽 젓가락 자원을 점유한다고 가정해보자. 이 경우, 모든 철학자들은 모두가 공유자원을 하나씩 점유하게 되나, 그 어떤 철학자도 식사를 하기에 충분한 자원을 모두 점유하지 못해 모두가 대기하는 상황에 빠져 deadlock이 발생한다.


solutions

이러한 식사하는 철학자 문제는 다양한 방법으로 대응해 볼 수 있다.

  • 철학자는 자신의 양쪽 젓가락이 가용할 때에만 젓가락을 집도록 제한할 수 있다.

  • assymmetric하게, 철학자의 위치 상 홀수번째와 짝수번째가 젓가락을 집는 우선순위를 달리할 수 있다.

  • 동시 식사할 수 있는 최대 개수를 semaphore 를 사용하여 제한한다.





<2> Synchronization Hardware


단일 처리기 환경을 가정한다면, shared variable이 변경되는 동안의 interrupt 발생을 허용하지 않음으로 critical section 문제를 해결할 수 있다. 즉, instruction의 현재 순서가 preemption 없이 순차적으로 실행됨을 확신하여 예측하지 못한 변경이 일어나지 않아 비선점형 커널 같은 경우 이러한 방법의 해결이 가능하다.


반면에 다중 처리기 환경에서는, interrupt는 모든 처리기에 지연을 초래하여 시스템 효율을 떨어뜨리기 때문에 사용하는 것이 권장되지 않는다.

시스템 성능을 고려한다면, 프로세서와 컴파일러는 read와 write 작업에 종속성이 없도록 reorder시켜야 한다.

이를 위해 현대 기계들은 interrupt 되지 않는 하나의 단위로서 word에 대한 내용을 atomic한 swap을 할 수 있는 하드웨어 명령어를 제공한다.


test_and_set() (=TAS)

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

TAS는 주어진 메모리 위치의 값을 읽고, 해당 위치에 새로운 값을 설정하는 일련의 과정을 하는 데에 atomic operation으로 실행된다.


compare_and_swap() (=CAS)

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

TAS는 두 word에 대한 교환에 기반한 매커니즘으로,
메모리의 현재 값을 읽어, 읽은 값이 주어진 기댓값(expected value) 과 동일하면 메모리의 값을 새로운 값으로 업데이트하는 과정을 갖는다.



동기화 조건을 만족시키는 CAS

while(true){
	
    #region Entry code
	waiting[i] = true;
    key = 1;
    
    while (waiting[i] && key == 1)
    	key = compare_and_swap(&lock, 0, 1);
        
    waiting[i] = false;
    #endregion
    
    critical_section();
    
    #region Exit code
    j = (i + 1) % n;
    
    while((j != i) && !waiting[j])
    	j = (j + 1) % n;
        
    if (j == i)
    	lock = 0;
    else
    	waiting[j] = false;
    #endregion
    
    remainder_section();
}

waiting 상태 플래그 변수와 key 값을 cas로 락을 관리하는 것을 통해 동기화 조건들을 만족시킨다.

  • locking을 통해 mutex를 보장하고
  • waiting[i] == false 또는 key == false인 경우에만 critical section을 탈출하는 것이 가능하도록 하여 시스템이 deadlock에 빠지지 않고 항상 적어도 하나의 프로세스가 임계 영역에 진입할 수 있음으로 progress를 보장하고,
  • process p i 수행된 다음에 가장 가까운 process p j를 찾아 수행될 수 있도록 권한을 주는 것으로, 대기하더라도 최대 n - 1 번 대기함으로 finite한 시간 동안의 대기를 보장한다.

<3> Implementation of Sync

앞서 언급한 내용은 하드웨어 기반 해결책들로 비단 복잡하다는 점 뿐만 아니라 application level을 다룰 프로그래머는 사용할 수 없기도 하다. 따라서 동기화를 구현하기 위한 소프트웨어 개발 도구 측면에서 동기화 구현 도구들을 찾아보면 다음과 같다.



1) Mutex Lock


명명 그대로 상호 배제 조건 그대로를 구현하는 락킹을 이용하는 방식이다. critical section을 보호하고 race condition을 방지하기 위해 mutex lock을 사용한다.

// boolean variable인 available 사용
bool available;

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

release() {
	available = true;
}


do {
	/* acquire lock */
    critical_section();
    /* release lock */
    remainder_section();
}
//

가용 상태에 대한 플래그 역할의 bool 변수값으로 available 변수를 이용하여,
lock이 가용할 시에 acquire()를 통해 권한을 획득하여 lock은 사용 불가 상태가 되고,
release()를 통해 lock을 반납하게 된다.

이 mutex lock은 앞서 설명한 하드웨어 기법으로 구현되며, acquire()와 release() 함수 호출은 atomic하게 수행되어야 한다.


다만 mutex lock은 process가 critical section에 들어가 있는 동안 진입하기를 원하는 다른 대기 중인 process들이 acquire() 함수를 호출하는 반복문을 계속 실행하게 되어 Busy waiting을 하게 된다.


cf. Spinlock

위의 형태의 mutex lock은 lock이 가용 상태로 반환되기를 대기하며 process가 회전하고 있기에 Spinlock이라고 불리기도 한다.
이 spinlock은 busy waiting에 의해 process가 더 생산적인 작업에 사용할 CPU cycle을 낭비하게 되지만,
lock을 대기하는 동안 상당한 시간을 소모하는 context switching이 필요로 하지 않는 장점을 가지고 있다.



2) Semaphore


# region Semaphore without suffering from Busy Waiting

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

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0){
        /* process를 S->list에 삽입 */
        block();
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0){
        /* S->list로부터 한 process P 꺼내기 */
        wakeup(P);
    }
}

#endregion

보통, semaphore는

  • 0과 1 로 이분화된 binary semaphore와 (사실상 mutex lock과 유사하게 동작)

  • unlimted domain을 가지는 counting semaphore로 구분된다.


semaphore는 유한한 개수의 자원에 대한 접근 제어를 하는데에 사용되어, 가용한 자원의 개수로 semaphore를 초기화한다.

semaphore는 integer varaible로서, 초기화 선언을 제외하고는

오로지 두 atomic operation인 wait()과 signal()을 통해서만 접근 가능하다.

  • wait()

자원을 사용하려는 프로세스가 wait() 연산을 통해 접근하고 이 때 semaphore 값을 감소시킨다.

  • signal()

프로세스가 자원의 점유를 그만 두려면 signal()연산을 통해 자원을 방출하고 semaphore 값을 증가시킨다.


semaphore는 가용한 자원 개수를 나타내므로, 0이 될 때 모든 자원이 사용 중이므로 0보다 커질 때까지 blocking 된다.



위의 설명만으로 구현되게 되면, semaphore는 mutex lock과 마찬가지로 busy waiting의 고통을 받게 된다. 하지만, 여기서 busy waiting 과 같은 대기 상태로 전환하는 것 대신, process가 자신을 봉쇄시킴(blocking)을 통해 이 문제를 해결할 수 있다.

sleep(also suspend) 연산은 process를 semaphore에 연관된 waiting queue에 넣고 그 상태를 대기 상태로 전환시켜 봉쇄시킨다.
wakeup 연산은 봉쇄 상태를 풀고 process를 재개시킨다.



3) Monitor


semaphore는 물론 편리하고 효과적인 동기화 도구임은 분명하지만 잘못 사용할 시에 발견하기 어려운 timing error를 야기시킨다. 이는 특정 실행 순서로 진행될 때 발생하고 이러한 sequence가 항상 일어나는 것은 아니기에 까다롭다.

semaphore에 대한 wait()과 signal() 연산의 순서가 뒤바뀌거나, wait()과 signal()을 호출할 위치에서 서로 다른 연산을 호출하거나, 심지어는 두 연산에 대한 호출을 누락할 경우 등 이러한 가정들은 mutex 조건을 위반하던지 progress 조건을 위반하고 deadlock에 빠지게 하던지의 결과를 만든다.

Monitor는 high level language constructs로서 고수준의 동기화 도구로,

mutex lock과 condition varaible이 결합한 형태로 동기화 메서드를 통해 자원 상태를 제어한다.


https://learn.microsoft.com/ko-kr/dotnet/api/system.threading.monitor?view=net-8.0

C#의 경우 Monitor 클래스로 제공하고 있다.

using System.Diagnostics.Metrics;
using System.Threading;

/* ... */

try
{
    Monitor.Enter(_lock);
    
    Critical_Section();
    
    if(some_condition)
        return;
}
finally
{
    Monitor.Exit(_lock);
}





previous
https://velog.io/@nuketuna/TIL-Synchronization-Race-Condition
TBC
https://velog.io/@nuketuna/TIL-20250131-TIL-Synchronization-pt3.-Deadlock

profile
Jaeyoung Ko
안녕하세요, 고재영입니다. 언제나 즐겁게 살려고 노력합니다.
이전 포스트

[TIL] 20250123 TIL : Synchronization : Race Condition pt.1 (1/3)

다음 포스트

[TIL] 20250131 TIL : Synchronization : Deadlock pt.3 (3/3)

0개의 댓글