Operating System Ch 06, 07

LeemHyungJun·2022년 10월 28일
0

Operating System

목록 보기
6/20
post-thumbnail

운영체제 수업 + 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일 때 들어올 수 있다.
    • 구현 방식
      • blockwakeup(P)
      • lockunlock으로 구현
    • 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은 스케줄링 문제이다.
    -> 동기화 문제는 아니기 때문에 동기화 문제는 해결한 코드

0개의 댓글