[OS] Operating System(6-2): Mutax lock, Semaphore

🍀 운영체제 전공 수업 정리

이전에 본 하드웨어 기반 해결책들(Test-and-Set,CAS,atomic 변수 등)은 강력하지만 직접 사용하기에는 복잡하고 접근하기가 어렵다!

그래서 이러한 하드웨어 기능을 기반으로 더 높은 수준의 software도구를 제공한다.

그 중 기본적인 것이 Mutex Lock

Mutex Locks

---

📚Mutex Lock: cs 문제를 해결하기 위한 software tool, Mutual Exclusion의 줄임말, 여러 스레드나 프로세스가 공유 자원에 동시에 접근하는 것을 방지

• critical section을 보호하기 위해 먼저 acquire()로 lock을 획득, 나중에 release()로 lock을 해제
  • boolean variable을 사용하여 lock의 가용성을 나타냄
• acquire(), release()는 원자적으로 구현되어야함

Mutex Lock의 구조

while (true) {
    acquire lock
    critical section
    release lock
    remainder section
}

Mutex Lock의 구현

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

release() {
    available = true;
}

이 함수들은 원자적으로 실행 되어야함
→ Test-and-Set, Compare-and-Swap과 같은 하드웨어 명령어를 사용함

• Test-and-Set ```c acquire() { while (test_and_set(&lock)) ; /* busy wait */ }

release() { lock = false; }

* **Compare-and-Swap**
```c
acquire() {
    while (compare_and_swap(&lock, 0, 1) != 0)
        ; /* busy wait */
}

release() {
    lock = 0;
}

위의 Mutex lock 구현에서는 프로세스가 lock을 획득할 수 없을 때 계속해서 CPU를 소비하며 대기한다. 이를 Busy waiting or Spinlock 이라 한다.

✅Spinlock 특징:

• 프로세스가 lock을 기다리는 동안 계속 CPU를 소비
• Context Switching 발생 X
• lock 보유 시간이 짧고 경쟁이 적은 환경에서 효율적
• 다중 코어/프로세서 환경에서 적합

📝Spinlock 유리한 상황:
“lock을 보유하는 시간 < 두 개의 context switching 시간” 의 경우에 Spinlock 유리함 → lock을 얻기 위해 block 되고 다시 꺠어나는 오버헤드보다 짧은 시간 동안 CPU 소비하며 대기하는 것이 더 효율적이기 때문!

Semaphore

---

📚Semaphore: Mutex lock보다 더 정교한 프로세스간 동기화를 제공

• Semaphore S: integer variable - 사용 가능한 자원 수
• 두 가지 원자적 연산:
  • wait(S)=P(): semaphore 값을 감소시키고, 값이 음수면 프로세스를 블록
  • signal(S)=V(): semaphore 값을 증가시키고, 대기 중인 프로세스가 있으면 깨운다

wait(S) operation

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

signal(S) operation

signal(S) {
    S++;
}

Semaphore Usage

---

semaphore는 값의 범위에 따라 두 가지 유형으로 나뉜다.

1. Binary Semaphore
   • 세마포어 값이 0과 1 사이로만 제한됨
   • Mutex lock과 동일한 기능을 제공
   • Mutual exclusion를 구현하는 데 사용됨
   • 초기값은 보통 1로 설정되어, 첫 번째 프로세스가 자원에 접근할 수 있게 함
2. Counting Semaphore
   • 세마포어 값이 제한 없는 영역에서 변할 수 있다
   • 동시에 사용 가능한 자원의 개수를 제어함
   • 예를 들어, 10대의 프린터를 관리하는 세마포어는 초기값이 10이 될 수 있다

Semaphore 활용 예제

세마포어를 활용해 프로세스 간 동기화 문제를 해결하는 예제

• 문제: P1의 S1 실행 후에만 P2의 S2가 실행되도록 보장

// 세마포어 초기화
semaphore sync = 0;  // 초기값 0으로 설정

// 프로세스 P₁
P1:
    S₁;
    signal(sync);  // sync 값을 1로 증가

// 프로세스 P₂
P2:
    wait(sync);  // sync가 양수가 될 때까지 대기
    S₂;

• semaphore sync는 초기값이 0
• P2는 wait(sync)를 호출하면 즉시 블록됨(sync=0이므로)
• P1이 S1을 수행하고 signal(sync)를 호출하면 sync=1이 된다
• 이제 P2는 블록 상태에서 빠져나와 S2를 수행할 수 있게 된다

Semaphore Implementation with no Busy waiting

---

앞의 세마포어 구현에는 buzy waiting 문제가 있다.

이를 해결하기 위해 waiting queue를 사용해 세마포어를 구현!

• semaphore 구조체:

typedef struct {
    int value;             // 세마포어 값
    struct process *list;  // 대기 중인 프로세스 리스트
} semaphore;

✅구조체의 두 가지 요소:

• value: 세마포어의 정수 값으로, 사용 가능한 자원의 수를 나타낸다
• list: 세마포어를 기다리는 프로세스들의 연결 리스트(linked list)

세마포어 구현에는 두 가지 연산이 사용된다

1. block operation:
   • 세마포어를 기다리는 프로세스를 적절한 waiting queue에 넣음
   • 프로세스를 실행 상태 → 대기 상태 로 전환
2. wakeup operation
   • waiting queue에서 프로세스를 하나 제거
   • 제거된 프로세스를 대기 상태 → ready 상태 로 전환

Implementation on single-core system

wait(semaphore *S) {
    disable interrupts;           // 인터럽트 비활성화
    S->value--;                   // 세마포어 값 감소
    if (S->value < 0) {           // 자원을 사용할 수 없는 경우
        add this process to S->list;  // 대기 큐에 추가
        block();                  // 프로세스 블록
    }
    enable interrupts;            // 인터럽트 활성화
}

signal(semaphore *S) {
    disable interrupts;           // 인터럽트 비활성화
    S->value++;                   // 세마포어 값 증가
    if (S->value <= 0) {          // 대기 중인 프로세스가 있는 경우
        remove a process P from S->list;  // 대기 큐에서 프로세스 제거
        wakeup(P);                // 프로세스 깨우기
    }
    enable interrupts;            // 인터럽트 활성화
}

• single core에서는 interrupt disable만으로 원자성을 보장 → 구현이 간단
• S->value:
  • S->value > 0: 사용 가능한 자원의 수

  • S->value <= 0: 대기 중인 프로세스의 수는 **

    S->value

    개**

Implementation on multicore system

multicore 시스템에서는 각 코어가 독립적으로 실행되고, 한 코어에서 인터럽트를 비활성화해도 다른 코어는 실행 된다
→ 인터럽트 비활성화만으로는 원자성을 보장 X

wait(semaphore *S) {
    while (test_and_set(&S->&mutex))  // mutex 획득 시도, 세마포어마다 mutex가 따로 있어야함
        ; /* spinlock */          // 획득할 때까지 스핀
    S->value--;                   // 세마포어 값 감소
    if (S->value < 0) {           // 자원을 사용할 수 없는 경우
        add this process to S->list;  // 대기 큐에 추가
        S->mutex = 0;                // mutex 해제
        block();                  // 프로세스 블록
    }
    else
        S->mutex = 0;                // mutex 해제
    return;
}

signal(semaphore *S) {
    while (test_and_set(&S->&mutex))  // mutex 획득 시도
        ; /* spinlock */          // 획득할 때까지 스핀
    S->value++;                   // 세마포어 값 증가
    if (S->value <= 0) {          // 대기 중인 프로세스가 있는 경우
        remove a process P from S->list;  // 대기 큐에서 프로세스 제거
        S->mutex = 0;                // mutex 해제
        wakeup(P);                // 프로세스 깨우기
    }
    else
        S->mutex = 0;                // mutex 해제
    return;
}

• Spinlock 사용: Test-and-Set과 같은 하드웨어 지원 명령어를 사용한 Spinlock으로 임계영역을 보호
• 다중 코어에서도 스핀락을 통해 한 번에 한 프로세스만 세마포어를 수정할 수 있도록 해서 원자성을 보장
• mutex 변수: 세마포어 연산의 원자성을 보장하기 위한 이진 변수
• 블록 전 mutex 헤제: 프로세스가 블록되기 전에 반드시 mutex를 해제해야 데드락 방지 가능