Operating System Ch 06, 07

운영체제 수업 + Operating System Concepts 10E 정리 내용

Operating System Ch06 : Synchronization tool

Synchronization

1. Synchronization

• Synchronization
  • Shared resource를 사용하는 상황에서는 같은 resource에 여러 process의 접근이 발생한다.
  • Synchronization을 통해 문제가 발생하지 않도록 해야한다.
  • Synchronization: time domain에서 여러 개로 분할된 동작들의 순서를 제어하여 동일하게 만드는 것
• Shared resource를 사용하기 위해서는
  • 각 스레드들이 다른 rate를 가지고 공유 데이터에 접근해야 한다.
  • 동기화를 사용하여 cooperation을 제어해야 한다.
  • Thread뿐 아니라 process에도 적용한다.

2. Synchronization Example

• 은행에서 돈을 인출하는 시나리오
  -> 두 개의 atm, 두 개의 인출 카드, 잔고가 10만원인 공유 계좌가 있다고 가정
  -> 동시에 한쪽의 atm에서 2만원 다른 한쪽에서 3만원을 인출한다고 가정
• interleaved schedules
  
  1) 계좌를 불러오기, 1번 사람이 계좌를 불러와서 2만원을 인출하고 context switching 발생
  2) 2번 사람이 계좌를 불러오고 3만원을 인출, 잔고를 업데이트 한 후 context switching -> 잔고는 7만원
  3) 1번 사람이 잔고를 업데이트 -> 잔고는 8만원
  => 잔고는 5만원이 되어야 하지만 8만원이 되버리는 문제가 발생한다.
• Another example
  • Bounded buffer (Producer and Consumer)
  • 후위 연산으로 인한 synchronization 문제가 발생한다.
  • count++ 라는 연산을 어셈블리어로 생각하면 3단계로 나눠진다
    1) Register = count
    2) Register = Register + 1
    3) count = Register
  • 3단계의 연산을 진행하는 도중 context switching이 발생한다면 이전과 같은 예시의 문제가 발생한다.

3. Synchronization problem

• 공유 자원이 오염되는 문제
• 항상 발생하는 것이 아니라 non-deterministic 하게 발생한다.
  -> 그러나 무시할 수 없다.
• 공유 자원이 오염되는 상황 자체를 race condition이라고 하며 상황이 발생하는 코드 지역을 critical section이라고 한다.

4. Requirements for Synchronization Tools

• Mutual Exclusion
  • 동기화 문제 해결에서 가장 중요한 조건
  • 공유 자원에 접근하는 것은 한번에 하나의 process만 가능하다.
  • critical section에 하나의 process가 접근하여 실행 중이라면 어떤 다른 process도 critical section에 접근할 수 없다.
• Progress
  • 공유 자원을 아무도 사용하고 있지 않는 상황에서 공유자원에 접근하려는 process가 있다면, 즉각적으로 이루어져야 한다.
• Bounded waiting
  • 공유 자원을 접근하는 기간(횟수)이 무한하지 않아야 한다.

Synchronization Tools

1. Lock

• Overview
  • Critical section에 진입하기 직전에 lock을 통해 접근하지 못하게 만들고 critical section에서 수행을 마친 후 unlock을 해준다.
  • 한번에 하나의 스레드를 lock할 수 있다.
  • spin lock, mutex 등으로 구현
• Implementing lock (spin lock)
  
  • lock 이라는 구조체 안에 held 변수를 통해 lock과 unlock을 설정해준다.
  • 0이 아닐 때 (lock 상태) 들어와서 일을 수행하려고 하면 while문에 들어가게 되서 무한 루프를 돌게 된다. -> spin lock
  • spin lock은 busy waiting이고 성능상으로 좋지 못한 과정이다.
  • Problem
    • lock 구조체의 held 변수가 또 다시 보호받지 못하는 공유 자원이 되므로 critical section이 된다.
      -> lock과 unlock이 모두 held라는 변수를 조작하는 상황
    • lock과 unlock의 동작이 atomic 하지 않다.
  • Solution
    • Software-only Algorithm 사용
      • Algorithm 1,2,3
      • Bakery Algorithm
      • 해당 방식은 너무 복잡하고 overhead가 커서 성능상의 문제로 인해 사용하지 않는다.
    • Hardware atomic instruction
      
      • lock을 구현하면서 중요한 부분을 한 번에 수행가능한 instruction으로 구현한다.
      • spin lock문제 해결
      • test-and-set() or compare-and-swap() 으로 구현
    • Disable/re-enable interrupts
      
      • Blocking lock
      • 중요 코드 실행 시에는 interrupt를 꺼서 context switching 자체를 방지하는 방법
  • Spin lock problems
    • thread가 spin lock에 들어가면 다른 동작을 수행하지 못하고 기다려야 하므로 낭비가 심하다.
    • critical section이 길수록 spin lock도 길어진다.
    • spin lock을 실제로 사용하지 않고 high-level synchronization을 구현해서 system call로 사용한다.
  • Disable interrupts problems
    • kernel만 사용 가능하다.
    • multiprocessor의 경우 사용 불가능하다
    • 직접 사용하는 것이 아니라 high-level synchronization을 구현해서 사용한다.

2. High-level Synchronization

• motivation
  • spin lock과 disabling interrupts는 매우 짧고 간단한 critical section에서만 기능한다.
  • High-level Synchronization 은 이전의 문제들을 해결하는 방식
• Semaphore
  
  • Shared data object에 접근 가능하며, multi-prcess, threads에서도 사용 가능하다.
  • 사용 방식
    • 정수 값으로 카운트를 센다 (ticket)
    • critical section으로 들어갈 때는 wait()이라는 system call을 통해서 ticket을 하나 가져간다.
    • critical section에서의 동작을 마치면 signal()이라는 system call을 통해서 ticket을 반납한다.
    • ticket이 0일 때 critical section에 들어올 수 없고 1일 때 들어올 수 있다.
  • 구현 방식
    • block과 wakeup(P)
    • lock과 unlock으로 구현
  • example
    • process1이 A까지 진행 후 process2가 B를 수행하기를 원할 때
    • flag 라는 semaphore를 하나 만들고 0으로 초기화
    • process1의 A실행 후 signal(flag), process2의 B 이전에 wait(flag) 를 작성하면 원하는 방식으로 동작하게 된다.
• Mutex Lock
  
  • Semaphore는 ticket의 갯수를 여러 개로 설정할 수 있다.
    -> counting semaphore
  • binary semaphore가 mutex와 같은 동작을 한다.
• Monitor
  • Semaphore의 단점을 개선한 방식
  • 컴파일러 레벨에서 critical section을 관리해준다.
  • java 언어에서 많이 사용하고 지원해주는 방식
  • 사용 방식
    • Monitor안에 shared resource를 선언 & 여러 개의 함수 선언
    • A process가 함수 P1의 동작을 수행한다면 다른 프로세스가 다른 함수를 실행하지 못하게 막는 것
    • P1 실행 도중 P1이 다른 공유자원을 기다려야 한다면 P2, P3 등도 계속해서 실행하지 못하고 기다려야 하는 문제가 발생한다.
    • conditional variables로 해결
• Conditional variables
  • monitor에서 P1이 다른 공유자원을 기다리는 상황이라면 P2, P3등의 다른 함수들은 동작을 할 수 있도록 풀어주는 역할
  • wait()과 signal()로 동작한다.
• Comparison: Monitor and Semaphore
  • semaphore
    • ticket이 0인 상태에서 signal을 보내면 1이 된다.
    • 아무도 기다리지 않는 상황에서도 signal을 보내면 1로 된다.
    • Stateful 하고, history를 가진다.
  • Monitor (conditional variables)
    • 아무도 안 기다릴 때 signal을 호출하면 signal을 무시한다.
    • signal이 중첩되면 무시된다.
    • Stateless하고, 그 순간 처리에 대해 집중한다.

3. Deadlock and Starvation

• Deadlock
  • 특정 상황에 의해 절대로 lock을 풀 수 없는 상황에 놓일 때 발생한다.
  • ch08에서 자세하게 다룬다.
• Starvation
  • starvation 문제는 synchronization 문제가 아니라 스케줄링 문제로 해결해야 한다.

Operating System Ch07 : Synchronization example

Classical Problems of Synchronization

1. Bounded-buffer Problem

• No Synchronization
  
  • critical section이 보호받지 않는 상태
  • count라는 공유 자원을 보호해야 한다.
  • count가 꽉 차거나 0일 때 busy waiting 해야 한다. -> 자원 낭비
• Implementation with Semaphore
  
  • 3개의 semaphore로 구현
  • empty와 full이라는 semaphore를 통해 해당 buffer가 비어있는지 다 찼는지를 확인한다.
  • producer는 empty에 wait 사용 -> 꽉 차있다면 사용 불가
  • consumer는 full에 wait 사용 -> 비어 있다면 사용 불가
• Implementation with mutex lock and conditional variables
  
  • mutex 하나와 conditional variable 두개로 구현

2. Readers-Writers Problem

• 상황
  • 특정 문서를 수정하지 않을 때에는 여러명의 reader가 접근해서 read 수행 가능
  • 특정 문서를 수정하고 있을 때에는 한명의 writer만 수정해야 하며, reader나 다른 writer가 들어올 수 없음
• Implementation with semaphore
  
  • 변수
    • readcount는 reader의 수를 측정
    • mutex는 readcount라는 공유자원을 보호하는 역할
    • wrt writer와 reader를 exclusive하게 만드는 역할
  • 코드
    • reader의 readcount++가 critical section이다.
    • wrt를 통해서 readcount가 0일때 reader가 들어오면 wait을 통해 writer와 exclusive하게 만들고 readcount가 0이 되었을 때 signal을 통해 writer가 공유자원에 접근할 수 있도록 풀어준다.
    • wrt를 통해서 reader는 여러 명의 작업이 가능하다.
  • problem
    • 첫번째 reader가 wrt로 보호되며 다음으로 들어오는 reader들은 wrt에 상관없이 read가 가능하다.
    • 위의 현상으로 여러명의 reader가 들어오면 reader의 우선순위를 정하는 문제가 발생
    • readcount가 0이 되어서 writer가 들어오려고 했지만 reader가 먼저 들어오면서 writer가 계속 기다리는 상황
    • 위의 문제들은 동기화 문제가 아니라 스케줄링 문제로 해결해야 한다.

3. Dining-Philosopher

• 상황
  • 철학자는 생각을 하다가 자신 양쪽에 있는 젓가락을 모두 들어야 먹을 수 있다.
  • 젓가락을 다른 철학자가 사용 중이라면 기다린다. -> 젓가락이 공유자원
• A simple solution
  
  • 왼쪽 들기 -> 오른쪽 들기 -> 먹기
  • 먹은 후 왼쪽 내려두기 -> 오른쪽 내려두기
  • if) 철학자가 왼쪽 젓가락을 들자마자 context switching이 반복되면 deadlock이 발생한다.
  • 해결 방법) 양쪽을 모두 확인하고 가져가는 것을 critical section으로 보호하기
• Deadlock-free version
  
• 젓가락을 공유자원으로 두지 않고 철학자의 상태를 공유자원으로 둔다.
• deadlock 문제는 해결된다.
• if) 양옆의 철학자가 번갈아서 eat을 실행하면, 가운데 끼인 철학자는 starvation문제가 발생한다.
  -> starvation은 스케줄링 문제이다.
  -> 동기화 문제는 아니기 때문에 동기화 문제는 해결한 코드