운영체제 (15) - Lock, Semaphore

운영체제 수업을 수강하며 정리한 내용을 작성하려고 합니다.

동기화 기법 - Lock (1)

• 임계 영역을 하나의 프로세스만 진입할 수 있도록 변수와 함수를 사용

  

  • 전역 변수와 함수로 flag를 설정하는 방법

• Lock에 사용되는 변수 (lock_t lock1) : lock 관련된 상태 관리

  • available : 해당 영역을 사용 가능함
  • acquired(획득) : 해당 영역을 한 프로세스가 사용중

• lock() : lock 획득을 시도함

  • lock 변수가 available이면 lock()을 호출하는 프로세스가 lock을 획득하고, 임계 영역에 진입하게 됨
  • lock 변수는 획득 상태가 됨
  • 다른 프로세스는 lock()을 호출하더라도 임계 영역에 진입하지 못함

Lock의 구현: (1) interrupt disable

• 초기 : lock 획득 시 interrupt disable
  • lock을 획득 시 어떠한 방해도 받지 않게 함
• 단점 : 효과적이지 않음
  • 사용자 구현에게 너무 많은 권한을 부여함 (trust 필요)
    • 프로그램 자체가 인터럽트를 제어할 수 있음 → lock 중 무한루프 돌 때 인터럽트가 불가능한 문제 + I/O 수행 결과 또한 인터럽트로 오는데, 이 경우 인터럽트가 버퍼에 쌓여 손실이 발생할 수도 있음 = 커널이 프로세스의 동작 중에 개입해서 시스템을 관리할 수 있는 여지를 차단함
  • 거의 사용되지 않음

Atomic instruction for lock

• 많은 시스템은 임계 영역의 lock 처리를 위해 하드웨어의 지원을 받음
• CPU의 atomic instruction을 이용함(CPU가 별도의 instruction을 제공)
  • 원자적(atomically)으로 수행되는 명령어? 명령어가 수행되는 동안 방해 받지 않음
  • 즉, 해당 명령어는 반드시 연속적으로 수행되어야만 함(중간에 끼어들기 불가),
• Interrupt disable과의 차이
  • 임계 영역 내에서의 연산 전체에 대해 타 프로세스의 진입을 막는 게 아니라 임계 영역의 진입 가능 여부(lock 함수)만 원자적 연산을 통해 체크해보고자 함
• TestAndSet : lock 구현을 위해 지원되는 atomic instruction
  • 하드웨어적으로 지원되는 원자적 명령어
  • 특정 변수에 저장된 값을 새로운 값으로 업데이트하고, 기존의 값을 반환
  • 이 모든 과정이 원자적으로 수행됨

Lock의 구현: (2) spin lock

• lock→flag 초기값은 0으로 설정됨(진입 가능한 상태)
• lock() 호출 시
  • 현재 flag가 0이라면, lock→flag에 1을 저장하고, TestAndSet은 0을 반환
    • 0과 1은 서로 다르므로, while문을 그대로 통과함
    • 즉, 임계 영역에 진입하게 됨
  • 현재 flag가 1이라면, lock→flag에 1을 저장하고, TestAndSet은 1을 반환
    • 1과 1은 서로 같으므로, while문을 반복하게 됨(spin)
    • 현재 임계 영역에 진입한 쓰레드가 임계 영역을 벗어나 unlock()을 호출하면 lock→flag는 0이 되고, 임계 영역에 진입함
• unlock() 호출 시
  • lock→flag가 0으로 설정됨
• 문제점: spin 중(루프를 돌며 대기중)인 프로세스가 영원히 spin할 수도 있음
  • 락을 획득할 때까지 CPU 사이클을 소모하면서 spin
  • 만약 싱글프로세서에서 spinning중인 프로세스가 계속 CPU를 점유한다면? → CPU 낭비
• 다만 구현이 간단하고, 실제 리눅스 등 운영체제에서도 많이 사용됨
  • CPU 개수가 많고, 선점형 프로세서이며 임계 영역에서의 연산이 길지 않다는 전제 하에서 오버헤드가 큰 이슈가 아닐 수 있음
• 이러한 방식의 대기를 busy waiting이라고 함
  • CPU를 계속 소모하면서 lock의 진입 여부를 기다리는 것

Lock의 구현: (2) yield 기반의 spin lock

• spin을 하게 될 때 CPU 사용을 포기(yield)하는 것
• CPU를 소모하며 spin하지 않고, 프로세스가 running에서 ready state로 전환
• 문제점:
  • context switching 오버헤드는 여전히 존재
  • 임계 영역 진입에 대한 starvation 문제 : priority가 높은 새로운 프로세스가 계속해서 생성된다면 lock을 대기하는 프로세스의 순서가 오지 않을 수 있다.

Yield 방식의 문제점

• 프로세스가 100개 있고, 모두 임계 영역 진입을 시도함
• 하나의 프로세스가 임계 영역에 진입해 있는 상태라면, 나머지는 계속 CPU 점유 → lock 확인 → yield를 반복함

Lock의 구현: (4) lock queue 기반의 spin lock

• Yield를 하되, 별도의 큐를 통해 lock 진입 대기 중인 프로세스를 관리
  • park() : 호출하는 쓰레드를 잠재움
  • unpark() : 호출하는 쓰레드를 깨움
    • unlock을 하는 시점에 lock queue에 인입된 쓰레드 중 첫 번째 쓰레드를 “바로 깨움”, ready state로 되는 것이 아니라 바로 실행 상태로 바꾸는 경우도 있다

Linux 예시

• Spin lock을 활용할 수 있는 다양한 API를 제공함 (include/linux/spinlock_types.h)

• spin_lock_init : spinlock의 초기화

• spin_lock : spinlock 획득 (임계 영역 진입)

• spin_unlock : 특정 spinlock 해제

• Lock의 한계

  

  • 임계 영역에 하나의 프로세스 또는 쓰레드만 진입하는 상황을 가정함
  • 여러 프로세스, 쓰레드의 진입을 관리하는 보다 복잡한 동기화 원리가 필요해짐 → Semaphore의 등장

Semaphore(세마포어)

• 2가지 원자적 연산을 가지는 정수 변수 → 진입하는 프로세스를 몇 개까지 허용할지 결정
• 세마포어는 사용하기 전 반드시 값의 초기화가 필요
  • Semaphore s를 정의함
  • s의 초기값을 1로 함

세마포어 원자적 연산

• s에 대한 2가지 원자적 연산 (atomic operation)
  • P() 또는 sem_wait() [Lock의 의미]
  • V() 또는 sem_post() [Unlock의 의미]
  • 세마포어 변수는 두 원자적 연산에 의해서만 접근됨
  • sem_wait은 임계 영역에 들어가기 전, sem_post는 임계 영역에서 나와서 수행
• sem_wait과 sem_post는 서로 독립적이고 원자적으로 수행됨
  • 한 프로세스가 sem_wait을 수행하여 세마포어의 값을 수정하는 동안 다른 프로세스에서 sem_wait나 sem_post를 수행해도, 세마포어의 값을 수정하지 못함
• sem_wait
  
  • 세마포어 값 감소
  • 세마포어 값이 음수가 아니면 return, 음수이면 wait
    • 음수가 아니면 임계 영역에 진입할 자리가 남아있다는 의미