[OS] Mutex Lock과 스핀락(Spin lock), 세마포어(Semaphore)

---

Mutex Locks

---

만들어진 이유?

• 임계구역 문제에 대한 하드웨어 기반 해결책은 복잡하고, 응용프로그래머가 사용 불가능
  → 임계구역 문제 해결을 간단하게 하기 위해 만들어진 소프트웨어 도구를 개발
  
  
• Mutex Locks : 상위 수준 소프트웨어 도구 중 하나로, 가장 간단한 도구
  • 임계 구역 보호를 통해 경쟁 조건 방지를 위해 mutex 락 사용
    • 임계 구역에 들어갈 때 락을 획득하고, 빠져나올 때 락을 반환해야 한다.
    • acquire() : 락 획득
    • release() : 락 반환

 

---

Mutex Lock의 구성

• available이라는 boolean 변수를 가짐 → 이 변수 값이 락의 가용 여부를 표시
  • 락이 사용 가능하면 acquire() 호출은 성공하고, 락은 사용 불가 상태가 됨
  • 사용 불가 상태의 락을 획득하려고 하면 프로세스는 락이 반환될 때까지 봉쇄

 

acquire()과 release() 함수 정의

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

release(){
    available = true;
}

// 사용 구조
while(true){
    acquire()

    /* critical section */

    release()

    /* remainder section */
}

 

• acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 한다.
  → CAS를 사용하여 구현할 수 있음
  
  
• 구현 방식의 단점 → 바쁜 대기(busy waiting)를 해야 한다는 것
  • 프로세스가 임계구역에 있는 동안 진입을 원하는 다른 프로세스들은
    acquire() 함수를 호출하는 반복문을 계속 실행해야 한다.
    
    
    • 하나의 CPU 코어가 여러 프로세스에서 공유되기 때문
      → 다른 프로세스가 생산적으로 사용할 수 있는 CPU 주기를 낭비
      → 실제 다중 프로그래밍 시스템에서는 문제가 됨
      
      

락 경합

• 락은 경합 상태와 비경합 상태로 나뉜다.
  
  
• 경합 상태 : 락을 획득하려고 시도하는 동안 스래드가 봉쇄될 때
  • 높은 경합 상태 : 비교적 많은 수의 스레드가 락을 획득하려고 시도 중
    • 해당 상태는 병행 실행 응용 프로그램의 성능을 전체적으로 저하시킴
  • 낮은 경합 상태 : 비교적 적은 수의 스레드가 락을 획득하려고 시도 중
    
    

• 비경합 상태 : 스레드가 락을 얻으려고 시도할 때 락을 사용할 수 있을 때

 

---

스핀락(spin lock)

• 위의 mutex 락 유형을 스핀락(spin lock)이라고도 함
  • 락을 사용할 수 있을 때까지 프로세스가 회전하기 때문
    
    
• 잠시 락을 유지해야 하는 경우 다른 스레드가 하나의 코어에서 임계구역을 실행하는 동안
  스레드는 다른 처리 코어에서 스핀하고 있을 수도 있다.

 

---

장점

• 스핀락은 프로세스가 락을 기다려야 하고 문맥 교환이 필요하지 않다.
  → 다중 코어 시스템의 특정 상황에서는 락이 필요할 때 스핀락이 선호됨
  
  • 최신 다중 코어 컴퓨팅 시스템에서 스핀락은 많은 운영체제에서 널리 사용

 

---

스핀락에서 짧은 기간이란?

• 락을 기다리는 스레드는 2번의 문맥교환이 필요
  • 첫 번째 → 스레드를 대기 상태로 옮기기 위한 문맥 교환
  • 두 번째 → 락이 사용 가능해지면 대기 중인 스레드를 복원하기 위한 문맥 교환
    
    
• 락이 유지되는 기간이 문맥 교환을 두 번 하는 시간보다 짧은 경우 스핀락 사용

 

 

---

세마포(Semaphores)

• 프로세스의 행동을 더 정교하게 동기화할 수 있는 방법을 제공하는 도구
  • mutex와 유사하게 동작하는 동기화 도구
    
    

wait()와 signal()

• 세마포 S는 정수 변수로서, 초기화 이외에는 원자적 연산인 wait() 와 signal()로 접근할 수 있음
  
  
• wait()와 signal() 연산 시 세마포 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 함.
  • 원자적 → 한 스레드가 세마포 값을 변경하면, 다른 스레드는 동시에 동일한 세마포 값 변경 불가능
    
    

• wait() 정의
  • S의 정수 값을 검사하는 작업(S≤0)과 실행될 수 있는 변경(S--) 작업은 인터럽트 되면 안 됨

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

 

• signal 정의

signal(S){ 
    S++;
}

 

---

세마포 사용법

• 운영체제는 카운팅(counting)과 이진(binary) 세마포를 구분
  • 카운팅(counting) 세마포 : 카운팅 세마포의 값은 제한 없는 영역(domain)을 가짐
  • 이진(binary) 세마포 : 이진 세마포 값은 0과 1 사이의 값만 가질 수 있음
    • 해당 특징 때문에 mutex 락과 유사하게 동작
      → 몇몇 시스템에서는 mutex 락 대신 상호 배제를 보장하기 위해 이진 세마포 대신 사용
      

카운팅(counting) 세마포의 동작

• 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용 가능
  • 이때, 카운팅 세마포가 가용한 자원의 개수로 초기화
    
    
• 각 자원을 사용하려는 프로세스는 wait() 연산 수행 → 세마포 값 감소
• 프로세스가 자원을 방출할 때 signal() 연산 수행 → 세마포 값 증가
• 세마포 값이 0 → 모든 자원이 사용 중임을 나타냄
  • 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄(Block)됨

 

동기화 문제 해결을 위한 세마포 사용

• 가정
  • 두 프로세스(P1, P2)가 존재
    • P1은 S1의 명령문을 병행하게 수행하려고 함
    • P2는 S2의 명령문을 병행하게 수행하려고 함
  • S1이 끝난 뒤에만 S2가 수행될 수 있다고 가정
    
    

• 해결법
  • P1과 P2가 세마포 synch를 공유하도록 설정 후, synch를 0으로 초기화
    
    
    • P2의 S2수행은 P1이 signal(synch)를 호출한 후에만 가능
      → synch 값이 0으로 초기화되어 있기 때문에 봉쇄
      → signal(synch)를 수행하기 위해서는 S1을 수행해야 함

// P1에 삽입하는 명령문 
S1; 
signal(synch); 


// P2에 삽입하는 명령문 
wait(synch);
S2;

 

---

세마포 구현

• 위 코드의 세마포 연산은 mutex 락처럼 바쁜 대기(busy wait) 문제를 지님
  → busy wait를 해결하기 위해 wait()와 signal()의 정의를 변경해야 함
  

 

세마포로 바쁜 대기(busy wait) 해결하는 원리 - 일시 중지 연산

• 프로세스가 wait() 연산을 실행하고, 세마포 값이 양수가 아니라면 반드시 대기해야 함
  → 바쁜 대기(busy wait) 대신 프로세스는 자신을 일시중지 시킬 수 있다.
  
  
• 일시 중지 연산 과정
  1. 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환
  2. 이후, 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위해 선택
     
     
• 세마포 S 대기를 위해, 일시 중지된 프로세스는 다른 프로세스가 signal() 연산 시 재시작되어야 함.
  • wakeup()
    1. 프로세스의 상태를 대기 상태에서 준비 완료 상태로 변경
    2. 이후 프로세스는 준비 완료 큐에 넣어짐
       
       
• 프로세스는 wakeup() 연산에 의하여 재시작됨

 

바쁜 대기를 해결하는 세마포 구현

typedef struct{
        int value;
        struct process *list; // 프로세스 리스트
}semaphore;

• 각 세마포는 정수(value)와 프로세스 리스트(list)를 가진다.
  

• wait() 연산 재정의
  • 프로세스가 세마포를 기다려야 하는 경우 → 해당 프로세스가 프로세스 리스트에 추가됨
  • sleep() : 자기를 호출한 프로세스를 일시 중지시키는 연산
    • 운영체제의 기본적인 시스템콜로 제공

wait(semaphore *S)
{     
    S->value--; // value가 0 이하인 경우
    if(S->value < 0){ 
        add this process to S->list; // 프로세스 리스트에 추가 
        sleep(); // 프로세스가 잠듦(대기) 
    } 
}

 

• signal() 연산 재정의
  • 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨움
  • wakeup(P) : 일시 중지된 프로세스 P의 실행을 재개시키는 역할
    • 운영체제의 기본적인 시스템콜로 제공

signal(semaphore *S)
{ 
    S->value++; 
    // 가용할 수 있는 세마포어가 없는 경우(프로세스 리스트에 대기하는 게 있는 경우) 
    if(S->value <= 0)
    { 
        // 프로세스 리스트에서 프로세스를 하나 빼옴 
        remove a process P from S->list; 
        wakeup(P); // 해당 프로세스를 깨움 
    }
}

 

새롭게 구현한 세마포어의 특징

• 바쁜 대기(busy wait)를 하는 고전적인 세마포는 음수를 가질 수 없음
  → But, 새롭게 구현한 세마포어에서는 음수를 가질 수 있음
  
  
• 세마포 값이 음수일 경우 → 그 절댓값은 세마포를 대기하고 있는 프로세스의 수
  • wait() 연산 구현에서 세마포 값의 감소와 검사의 순서를 바꾼 결과

 

프로세스 리스트의 구현

• 대기하는 프로세스 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에 의해 구현 가능
  • 각 세마포는 정수 값과 PCB의 리스트에 대한 포인터를 가지고 있음
    
    
• 한정된 대기를 보장하도록 리스트에 프로세스를 추가/삭제하는 방법
  1. 선입 선출 방식 큐 사용 → 세마포가 큐의 머리와 꼬리에 대한 포인터를 모두 가짐
  2. 리스트에 임의의 큐잉 전략을 사용 → 일반적인 방법
     • 세마포를 정확하게 사용하는 것과 특정 큐잉 전략(세마포 리스트를 위한) 사용과는 무관

 

세마포의 원자적 실행과 다중 코어 환경

• 세마포는 원자적으로 실행되어야 하는 것은 굉장히 중요
  → 두 프로세스가 wait()와 signal() 연산을 실행할 수 없도록 보장해야 함
  • 이러한 상황은 임계구역 문제에 해당됨
    
    
• 단일 처리기 환경일 경우, 연산이 실행되는 동안 인터럽트를 금지하여 쉽게 해결 가능
  • 인터럽트를 금지하면, 다른 프로세스들의 명령어들이 끼어들 수 없음
    → 오로지 현재 수행되고 있는 프로세스만 실행
    • 인터럽트가 다시 가능해지고, 스케줄러가 제어를 다시 얻으면 다른 프로세스 실행 가능
      
      
• 다중 코어 환경일 경우 → 모든 처리 코어에서 인터럽트를 금지해야 함
  • 다른 코어에서 실행되는 서로 다른 프로세스들의 명령어가 끼어들 수도 있기 때문
  • 모든 코어에서 인터럽트를 금지하는 것은 매우 어렵고, 성능을 심각하게 감소시킴  
     → SMP(대칭형 다중 처리) 시스템은 연산의 원자적 실행을 위해 다른 기법을 사용해야 함  
    
      (예시 : `compare_and_swap()` 또는 `스핀락(spinLock)`)

 

바쁜 대기(busy wait)와 세마포

• wait()와 signal() 연산의 현재 정의에서 바쁜 대기를 완전히 제거하지 못했음
• 바쁜 대기를 진입 코드에서 응용 프로그램의 임계 구역으로 이동시켰음
• 바쁜 대기를 wait()와 signal() 연산의 임계구역에만 국한시킴
  • 해당 임계구역은 매우 짧음 → 임계 구역은 거의 항상 비어있어 바쁜 대기는 드물게 발생
    • 바쁜 대기가 발생하더라도 그 시간이 매우 짧음
      
      
• 바쁜 대기가 비효율적인 경우
  • 임계구역이 매우 긴 환경일 경우
  • 거의 항상 점유된 응용 프로그램들을 갖는 환경일 경우

 

---

세마포의 한계점

• 세마포는 자칫 잘못 사용하면 발견하기 어려운 타이밍 오류를 일으킬 수 있다.
  • 발견하기 어려운 이유?
    • 타이밍 오류들은 특정 실행 순서로 진행되었을 때만 발생,
      그런데 이러한 순서가 항상 일어나는 것은 아니기 때문
      
      
  • 예시
    • 생산자-소비자 문제에서 count를 사용할 때 발생하는 시간적 오류
      → 시간적 오류 해결을 위해 Mutex 락과 세마포를 도입했지만 타이밍 오류는 여전히 발생

 

세마포 해결책이 타이밍 오류가 발생하는 이유 - 임계 구역 예시로 설명

• 정상적인 세마포 연산
  • 모든 프로세스는 mutex라는 이진 세마포 변수를 공유, 그 초기값은 1이다.
  • 각 프로세스는 임계구역에 진입하기 전에 wait(mutex)를 실행해야 함
  • 각 프로세스는 임계구역에서 나올 때 signal(mutex)를 실행해야 함

wait(mutex);
    …
    critical section // 임계구역 
    … 
signal(mutex);

• 위 같은 순서가 제대로 지켜지지 않을 경우 → 두 프로세스가 동시에 임계구역에 존재할 수 있음
  • 이러한 상황은 순수한 프로그래밍 오류 또는 비협조적인 프로그래머에 의해 발생

 

1. wait()와 signal() 연산의 순서가 뒤바뀐 경우

signal(mutex);
	… 
    critical section // 임계구역 
    … 
wait(mutex);

• 여러 프로세스가 동시에 임계구역 안에서 실행될 수 있음
  → 상호 배제 요구 조건 위반
  
  
• 이런 오류는 여러 프로세스가 동시에 자신의 임계구역 안에서 실행됐을 때만 발견 가능
  → 언제나 발생하는 상황이 아니기 때문에 발견하기 어려움

 

2. signal(mutex)을 써야 할 곳에 wait(mutex)를 사용한 경우

wait(mutex); 
    … 
critical section // 임계구역
    … 
wait(mutex);

• 세마포를 사용할 수 없으므로 프로세스는 두 번째 wait() 호출에서 영구적으로 봉쇄

 

3. 프로세스가 wait(mutex) 나 signal(mutex) 혹은 둘 다 빠뜨린 경우
   • 상호 배제 요구 조건을 위반하거나, 프로세스가 영원히 봉쇄됨