Synchronization

게으른개발자·2021년 5월 30일
0

운영체제

목록 보기
1/1

Synchronous vs Asynchronous

Synchronous(동기)는 메소드를 실행시킬 때 동시에 결과(반환 값)가 주어졌을 때 (혹은 기대되는 경우)를 말한다.

Asynchronous(비동기)는 메소드를 실행시킬 때 결과를 기다리지 않는 경우를 말한다.

동시에라는 말은 실행되었을 때 값이 반환되기 전까지는 blocking되어 있다는 것을 의미한다. 비동기의 경우, blocking되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에게 해당 task 를 위임하고 바로 다음 코드를 실행하기 때문에 기대되는 값이 바로 반환되지 않는다.

동기화의 중요성

동시에 여러 개의 프로세스가 동일한 data에 접근하여 변경하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.

이런 상황을 방지하기 위해 한순간에 하나의 프로세스만이 data를 변경하도록 보장해야 하며, 따라서 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있다.

Critical Section (임계영역)

동일한 자원을 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라 칭한다. (공유 데이터가 접근 되는 코드)

"한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역 안에서 실행할 수 없다"

Critical Section Problem

프로세스들이 Critical Section 을 함께 사용할 수 있는 프로토콜을 설계하는 것이다.

그러기 위해선 다음의 3 가지 요구 조건을 충족시켜야 한다.

  1. Mutual Exclusion(상호 배제)
    프로세스 P1 이 Critical Section 에서 실행중이라면, 다른 프로세스들은 그들이 가진 Critical Section 에서 실행될 수 없다.

  2. Progress(진행)
    Critical Section 에서 실행중인 프로세스가 없고, 별도의 동작이 없는 프로세스들만 Critical Section 진입 후보로서 참여될 수 있다.

  3. Bounded Waiting(한정된 대기)
    P1 가 Critical Section 에 진입 신청 후 부터 받아들여질 때가지, 다른 프로세스들이 Critical Section 에 진입하는 횟수는 제한이 있어야 한다.

해결책

Lock

  • 하드웨어 기반 해결책
  • 프로세스가 critical section에 진입할 때 lock을 걸어버린다.
  • Critical Section 에 진입하는 프로세스는 Lock 을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.
  • Mutex와 Progress 조건 만족

Mutex Lock

  • 소프트웨어 기반 해결책
  • boolean available을 사용해 lock이 잠겨있는지 풀려있는지 결정
  • acquire로 critical section에 진입할 수 있는 lock을 얻고 (available = false가 되어 다른 프로세스들은 못들어 옴) critical section을 탈출하며 자기가 가지고 있는 lock을 풀어 available을 true로 바꾸는 것
  • 단점: 프로세스가 아무것도 안하며 cs에 진입할 수 있을 때까지 계속 입장 여부를 체크하고 있다면 그것을 busy waiting, 또는 spinlock이라고 한다.
    → 쓸데없이 CPU를 점유하고 있다.

Semaphore

  • 다른 소프트웨어 동기화 도구
  • 세마포어는 Block & Wake up 구조로 Spinlock의 문제를 해결하고 있다. Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다.

  1. Counting Semaphore

    • 유한한 개수를 가진 resource에 대한 접근을 제어하는 데 사용되며, 세마포는 그 가용한 자원의 개수 로 초기화 된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가 한다.
    • wait() 연산을 수행하면 sempahore 값이 감소되며, signal() 연산을 수행하면 semaphore 값은 증가한다.
    • semaphore 값이 0이 되면, 모든 자원이 사용 중임을 나타낸다.
  1. Binary Semaphore

    • MUTEX Lock과 똑같은 개념이다.
    • 이름 그대로 0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.
    • MUTEX Lock과 차이점은 busy waiting하던 진입-희망 프로세스가 list에서 잠을 자게 된 것뿐이다.

Semaphore 주의점

1) CS가 매우 짧고 프로세스의 수가 많지 않아 busy waiting 할 시간이 적다면, busy waiting이 block & wake up 보다 유리하다.
- block & wake up의 경우 Overhead가 있기 때문에 busy waiting할 프로세스가 적다면 Overhead를 안만드는게 낫다.

2) CS가 매우 길고 프로세스의 수가 많다면 block & wake up이 유리하다.
- Overhead가 생기더라도 busy waiting 하는 수 많은 프로세스의 CPU 점유로 인한 CPU 활용도 저하가 더 큰 문제이다.

Deadlock (교착상태)

세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.

예를 들어, P(0)와 P(1)이 모두 wait()를 실행하게 되면, P(0)는 P(1)이 signal()을 실행할 때까지 기다리며, P(1)은 P(0)가 signal()을 실행할 때까지 기다리게 된다. 이에 P(0)와 P(1)은 deadlock 상태가 된다.

Monitors

세마포어의 데드락 문제를 해결하기 위해 나온 ADT(Abstract Data Type)의 고급 언어 설계 구조물이다.

모니터는 프로그래머가 정의한 함수에 Mutual Exclusion을 제공한다. 그리고 모니터 안에선 항상 하나의 프로세스만 running할 수 있다.

모니터 안에서 하나의 프로세스가 공유된 함수와 데이터를 가지고 running하고 있으면, 모니터 진입을 원하는 다른 프로세스는 entry queue에 머무르게 된다.


_만약 running 중인 프로세스가 I/O Interrupt를 만나 중단되게 된다면?_

Condition variables

중단된 프로세스를 conditions queue에 넣어 재우다가 다시 running할 준비가 되면 깨워주기 전까지 보관하는 역할을 수행한다.

profile
딩코딩코딩

0개의 댓글