[OS] Synchronization I

Race Condition(경쟁 상태)

• 공유 가능한 자원: 스레드 간에 공유되지 않는 지역 변수와 달리 전역 변수와 동적 할당 객체는 여러 스레드가 접근할 수 있음
• Race condition: 여러 프로세스(또는 스레드)가 공유 데이터에 동시에 접근하고 변경을 시도하여, 프로그램 결과가 실행 타이밍에 따라 달라지는 비결정적인(non-deterministic) 상태를 의미
  • 데이터의 일관성을 해치는 결과를 초래
  • 동기화를 걸지 않는 이상 해결이 불가능
• ex) 은행 입출금 문제
  • 잔고가 1000원인 계좌에 500원 입금과 500원 출금이 동시에 발생할 경우, 최종 잔고는 스케줄링 순서에 따라 500원 또는 1500원이 될 수 있음

 

Critical Section(임계 영역)

• 여러 프로세스가 공유 데이터에 접근하고 변경하는 코드가 포함된 영역
• 동기화의 목표는 한 번에 오직 하나의 프로세스(or thread)만이 Critical Section에 진입하도록 보장하는 것

Process Modeling

• Entry Section: Critical Section에 진입하기 위한 조건 검사 및 락(Lock)을 획득하는 코드
• Critical Section: 공유 데이터에 접근하는 코드
• Exit Section: Critical Section을 빠져나오며 락(Lock)을 해제하는 코드
• Remainder Section: 나머지 코드

 

Critical Section 해결의 3가지 조건

1. Mutual Exclusion(상호 배제)
   • 만약 Process A가 Critical Section에 진입해 있다면, 다른 모른 프로세스는 진입할 수 없어야 함
2. Progress(진행)
   • Critical Section 내에 아무도 없고, 진입하려는 프로세스가 존재할 경우, Remainder Section에서 실행 중이 아닌 프로세스들(진입 대기 중인 프로세스들)만이 누가 진입할지 결정할 수 있어야 함
     • Entry Section에서 코드를 실행 중인 프로세스들만이 다음 순서 결정에 참여할 자격이 있다는 뜻
   • 결정은 무한히 연기될 수 없음(Deadlock-free)
3. Bounded Wating(유한 대기)
   • 프로세스가 Critical Section에 진입하기 위해 기다리는 시간에 상한(Limit)이 존재해야 함(Starvation-free)
     
     • Starvation-free면 무조건 Deadlock-free지만 Deadlock-free라고 해서 Starvation-free인 것은 아님

 

소프트웨어 기반 Critical Section 해결 알고리즘

1. Turn 변수 사용

• int turn=0; (초기화)를 공유 변수로 사용
• turn 값에 따라 P0 또는 P1만이 진입할 수 있음

• 만족 조건: Mutual Exclusion(상호 배제)
• 불만족 조건: Progress, Bounded Waiting
  
  • 두 프로세스 수행 순서가 엄격히 정해져 있어, 순서가 맞지 않으면 진행이 안 됨
  • 수행 순서가 정해진 대로(P0 -> P1 -> P0 -> ...) 진행되지 않으면, 원치 않는 프로세스가 영원히 기다릴 수 있음

 

2. Flag 사용

• flag 변수를 사용하여 임계 영역 진입 의사를 표현하는 알고리즘
• Shared Variables
  • boolean flag[2]; (flag[0]=flag[1]=false로 초기화)
  • flag[i]=true: Pi가 CS 진입을 원함을 나타냄

• 만족 조건: Mutual Exclusion
• 불만족 조건: Progress, Bounded Waiting
  • 두 프로세스가 동시에 flag[]를 true로 할 수 있음 >> 둘 다 진입 불가(Deadlock)

 

3. Peterson Solution

• Attemp 1의 turn과 Attemp 2의 flag를 결합하여 Mutual Excusion, Progress, Bounded Waiting 세 가지 조건을 만족시키는 알고리즘
• Shared Variables
  • int turn;
  • boolean flag[2]; (flag[0]=flag[1]=false로 초기화)

• 만족 조건: 3가지 조건 모두 만족
  • 두 Process가 동시에 수행되더라도, turn 값에 의하여 결정됨
• 한계
  • 3개 이상의 Process에서는 어떻게 구현할 것인가?
  • 어떻게 확장된 알고리즘이 어떤 경우에도 동작함을 증명할 것인가?
    • NP(Non-deterministic Polynomial-time) 문제임
  • 하드웨어로 처리하면 알고리즘이 매우 간단하게 됨
    • 성능 효율이 더 높아짐

 

간단한 방법: Interrupt Disable

• 임계 영역 진입 시 인터럽트를 비활성화(Disable)하여 동기화를 확보하는 매우 단순한 방법
• 작동 방식
  • Critical Section 진입 시: Interrupt Disable
  • Critical Section 탈출 시: Interrupt Enable
• 문제점
  • 바람직하지 않음: 사용자 프로그램이 커널이 제어하는 인터럽트를 제어하는 것은 시스템 안정성 측면에서 바람직하지 않음
  • Scalability(확장성) 부족: 프로세스(CPU)의 숫자가 많아질 때 문제가 발생할 소지가 있음
• 결론: 더 나은 동기화를 위해 Scnchronization Instruction이 도입 됨

 

Synchronization Instruction(하드웨어 지원)

• CPU 수준에서 지원하며 원자적(Atomically, Uninterruptible)으로 수행되는 명령어(Instruction)를 사용하여 동기화 문제를 해결
• 원자적 수행: 명령어가 수행되는 동안 절대 방해받지 않고 한 번에 완료됨을 의미
  
  

Test and Set 명령어

• 주어진 메모리 위치의 값을 확인하고(return rv), 동시에 그 값을 true로 설정하는 동작을 원자적으로 수행

Test-and-set

• boolean rv=*target;
  • 현재 자물쇠 상태(값)를 읽어서 'rv'에 저장(기억)
• *target=true;
  • 자물쇠를 무조건 '잠금(true)'으로 바꿈
• return rv;
  • 기억해둔 자물쇠의 원래 상태(rv)를 반환

Mutual Exclusion with Test-and-set

• Critical Section에 들어가기 위해 자물쇠(lock)을 확인하는 과정
• 상황 A: 아무도 없을 때 (lock == false) 
  1. 프로세스 Pi가 도착해서 while(TestAndSet(&lock))을 실행
  2. TeestAndSet 실행
     1. 현재 lock은 false 상태
     2. 이 false 값을 rv에 저장하고, 즉시 lock을 true(사용 중)로 바꿈
     3. rv에 저장된 false(원래 값) 반환
  3. while(false)가 되므로 반복문을 탈출
  4. Critical Section 진입
• 상황 B: 누가 사용 중일 때 (lock==true)
  1. 다른 프로세스가 와서 while(TestAndSet(&lock))을 실행
  2. TestAndSet 실행
     • 현재 lock이 걸린 상태(true)
     • 이 true 값을 rv에 저장하고, lock을 다시 true로 덮어씀(변화 없음)
     • true(원래 값) 반환
  3. while(true)가 되므로 무한 반복
• 상황 C: B에서 나올 때 (탈출)
  1. lock=false;
• 상황 A 로직이 끝나고 상황 C로직을 수행하면 상황 B의 프로세스가 lock을 점유하게 됨

 

Swap 명령어

Swap

Mutual Exclusion with swap

• lock이 true에서 false로 바뀌면 waiting[i]가 즉시 이를 자신의 값인 true와 바꿔 잠그면서 critical section으로 들어감

 

위와 같은 Instruction의 한계

• 동기화 Instruction을 사용하여 Mutual Exclusion은 해결되지만, Bounded Waiting과 같은 추가 조건은 사용자 프로그램(User Program)에서 제공해야 함
• Bounded Waiting이 주어진 문제마다 조금씩 다르기 때문에, User Program에서 제대로 처리하는 것을 기대하기 어려움
• 좀 더 Comprehensive(포괄적인) 한 동기화 Primitive(도구)가 필요함

ex) Bounded Waiting Solution

1. key가 true면서 waiting[i]도 true면 testAndSet으로 lock을 계속 보내서 lcok이 true 될 때까지 기다림
2. lock이 false가 되면 TestAndSet에서 바로 lock을 true로 바꾸면서 동시에 key로 false값을 줌
3. cirtical section 입장
4. waiting에서 기다리고 있는 것들을 탐색하며 현재 프로세스가 아니면서 waiting[]이 true 인 값(lock 대기중인 프로세스)이 있다면 while문 탈출
   • 만약 한 바퀴 탐색을 마치고 현재 프로세스로 돌아와도 탈출
5. waiting[]에서 기다리는 프로세스가 없다(현재 프로세스로 돌아와 탈출)면 lock을 풀어줌
6. 기다리는 프로세스를 찾았다면 그 프로세스의 waiting[]을 false로 풀어주면서 critical section에 진입시킴

• Starvation을 없애 Bounded-Waiting(한정 대기)를 해결함
  • 내 뒤 인덱스부터 다시 나까지 돌아올 때까지 waiting 배열을 훑는 과정이 공정성을 보장해줌
  • 모든 프로세스가 최대 n-1번만 양보하면 반드시 들어갈 수 있음

 

세마포어(Semaphores)

• 두 개의 원자적 연산을 가지는 정수 변수
• 원자적 연산(Atomic Operation)
  • Wait() or P(): 입장 전 실행
  • Signal or V(): 퇴장 후 실행
• 세마포어는 2개의 원자적인 연산에 의해서만 접근됨
• P와 V 연산은 서로 독립적으로, 그리고 원자적으로 수행됨
  • 하나의 프로세스가 P를 수행하여 세마포어의 값을 수정하는 동안,
    다른 프로세스에서 P나 V를 수행하여 같은 세마포어의 값을 수정하지 못함

단일 세마포어 예시

• Busy Waiting 이용 (Original)

• Busy Waiting: Critical Section에 진입할 조건이 될 때까지 Loop를 돌며 기다림
• 단점
  • 계속해서 연산하기 때문에, CPU Cycle을 낭비할 수 있음
  • 대기 중인 Process 중에서 누가 Criticcal Section에 진입할지 결정하지 않음 (Random)

 

Sleep Queue를 사용한 Semaphores의 구현

• Busy Waiting 방식의 CPU Cycle을 낭비하는 문제 해결
  • Semaphore의 값이 양수가 되어 Critical Section에 진입이 가능하게 되면, Sleep Queue에서 대기 중인 Process를 깨워 실행시킴

• S->value > 0: 사용 가능한 자원의 개수
• S->value == 0: 자원은 모두 사용 중이지만, 대기하는 프로세스는 없음
• S->value < 0: 자원이 모두 사용 중이며, 절댓값이 대기(Sleep) 중인 프로세스의 수

 

세마포어 내부의 test-and-set 활용

• 세마포어의 true: 자원이 존재한다는 것을 의미
• test-and-set의 true: '잠김'을 의미
• 둘은 서로 다른 변수로 저장되며 이를 헷갈리지 않도록 주의해야 함

// 세마포어의 P() 연산 내부 구현
void P(Semaphore *S) {
    
    // [1단계: 하드웨어 레벨 잠금 (TAS)]
    // "S->value"를 건드리기 전에, "S->guard"라는 방문을 먼저 잠급니다.
    // TAS가 True를 반환하면(이미 잠김), 여기서 뺑뺑이(Spin)를 돕니다.
    while (TestAndSet(&S->guard) == true); 
    
    // --- [안전지대 진입] ---
    // 이제 나 혼자만 S->value를 만질 수 있습니다.
    
    // [2단계: 논리 레벨 연산 (세마포어 로직)]
    S->value--; 
    
    if (S->value < 0) {
        // [3단계: 잠들기 전 뒤처리]
        // 나는 이제 잘 거니까, 'guard'는 풀어줘서 다른 애들이 value를 볼 수 있게 해야 함.
        S->guard = false; // TAS용 자물쇠 해제!
        
        sleep(); // 운영체제야 나 재워줘 (Blocking)
    } else {
        // [3단계: 통과 후 뒤처리]
        S->guard = false; // TAS용 자물쇠 해제!
    }
}

 

세마포어의 종류

• 2가지 Semaphore
  • Counting Semaphore
    • Semaphore 값은 범위가 정해져 있지 않음 
    • 초기값은 가능한 자원의 수(N)로 정해짐 >> N개의 동기화  
    • ex) 기차표, 콘서트 예매
  • Binary Semaphore(=mutex)
    
    • Semaphore value가 가질 수 있는 값은 0, 1
    • 구현이 간단함, mutex랑 똑같음
• Binary Semaphore를 이용하여 Counting Semaphore를 구현할 수 있음
• Binary Semaphore는 test-sand-set과 같은 Hardware의 도움을 받아서 구현할 수 있음

 

Binary Semaphore 구현

• Test and Set 명령어를 이용하여 구현
• Semaphore S: 현재 Critical Section에 진입한 Process가 있는지 나타냄 (True or False)
• P(S)
  • while(test_and_set(&S));
    • test_and_set: S의 값이 그대로 return 되는 함수, 근데 S는 return과 상관없이 항상 true로 바뀜
• V(S)
  • S=false;
  • 진입한 process가 없음을 나타내어 wait()에서 대기 중인 Process를 진입 가능하도록 함
• 위 설명은 true가 잠김(사용 중), false가 열림(비어있음)을 나타냄
  • 세마포어(특히 Mutex)를 하드웨어 명령어(test_and_set)로 실제로 구현할 때 쓰는 스핀락 개념

 

Counting Semaphore의 구현

• Binary Semaphore를 이용한 Counting Semaphore 구현
• 아래 로직에선 n or 1이 남은 티켓 수를 말함, 0은 진입 불가 (표준적인 세마포어의 개념) 
  • Counting Semaphore를 CS라 하고, value는 C 
  • 2개의 Binary Semaphore S1, S2를 이용 (S1 for Mutex, S2 for delay)
  • S1=1, S2=0으로 초기화 (C가 양수라고 가정)

Binary Semaphore로 구현된 Counting Semaphore의 동작 과정 (S1은 자원이 1개 남음이 아니라 번호표를 뽑으러 들어가는 열쇠 역할)

• 세마포어의 P와 V 연산은 시스템 호출로 구현되어 커널 내에서 처리하며 커널의 스레드 환경에 따라 구현 방식이 달라짐
  • Kernel이 Single Thread인 경우
    • P/V를 System Call로 구현
    • 커널 내 수행은 Non Preemptive(비선점적)임
    • 한 번 커널에 진입하면 그 자체가 임계 구역에 들어간 것과 동일하게 취급되어 별도의 동기화 메커니즘이 필요 없음
      • 커널 자체가 싱글 스레드
  • Kernel이 Multithread인 경우
    • P/V를 System Call로 구현
    • 커널 내부에도 여러 스레드가 동시에 실행될 수 있음
    • 락(Lock) 같은 기법을 추가하여 커널 내에서 별도로 동기화를 처리해야함
• Semaphores의 단점
  • Deadlock이 발생할 가능성이 존재함 >> 이건 사실 언제나 존재함
    • P/V를 잘못 설정하면 Deadlock 발생 (보통 인간이 설계를 잘 못했을 때)
  • P와 V의 연산이 분리되어 있기 때문에 이를 잘못 사용할 경우에 대한 대책이 없음
    • P(); -> Critical Section -> P();
      • Critical Section 후에 Lock()을 풀어주는 V();가 없으므로 한 프로세스가 Critical Section에 진입하면, 나올 수 없음
      • 다른 프로세스들이 Critical Section에 진입 못하므로 Deadlock 발생
    • V(); -> Critical Section -> P();
      • Critical Section 전에 Lock을 걸어주는 P(); 가 없으므로 여러 프로세스가 동시에 Critical Sectino에 진입할 수 있으므로, Mutual Exclusion을 보장 못함
  • 이러한 단점으로 인해, 프로그래머가 동기화 제약 조건을 직접 명시할 필요가 없는 High-level 언어에서 동기화를 제공하는 방법이 필요해짐

 

Deadlock

• 두 개 이상의 Process들이 끝없이 이벤트를 기다리고 있는 상황
• 이때, 그 이벤트를 발생시킬 수 있는 주체가 바로 기다리고 있는 프로세스 자신임

 

Monitor

• Hige-level 언어에서의 동기화 방법
  • ex) Java의 Thread에서 동기화를 위한 방법으로 적용됨
• 한 순간에 하나의 Process만 Monitor에서 활동하도록 보장
  • 공유 데이터(필드 값)와 공유 데이터를 접근하는 코드(함수)를 하나의 Monitor(객체)에 구성
• Application은 Semaphore와 같은 P와 V 연산에 대한 고려 없이 Procedure를 호출하는 것 만으로 동기화를 해결할 수 있음
  • Programmer는 동기화 제약 조건을 명시적으로 코드화할 필요가 없음

Montior 문법

• Java나 C++의 클래스의 구문과 유사
• Entry Queue(진입 대기열): 모니터를 사용하기 위해 기다리고 있는 프로세스들이 대기하는 곳
• Shared Data 접근: 공유 데이터를 사용하기 위해선 반드시 모니터에 진입하여 제공되는 Operation을 통해서만 접근이 가능
  • 모니터 자체가 내부적으로 락을 관리하여, 한 번에 하나의 프로세스만 내부 Operation을 실행하도록 보장함

공유 변수에 접근하고 싶은 프로세스들이 Entry Queue에서 대기

• 성능은 떨어짐
• Consistency(일관성)는 좀 강하게 보장하면서 Concurrency(동시성)는 조금 떨어뜨림
• ex) Transaction
  • DB 내에 하나의 그룹으로 처리해야 하는 명령문들을 모아놓는 작업 단위
  • 하나의 작업 단위가 반드시 완전히 수행되어야 하며, 어느 하나라도 실패한다면 전체 명령문이 취소 됨