병렬성과 동시성에 대해 쉽고 재미있게 쓴 글

• 용어
  • 지연 시간: 단일 작업을 시작해 끝날 때 까지 걸리는 시간
  • 처리율: 단위 시간 당 시스템이 처리하는 작업의 수
  • 동시성: 여러 작업의 실행 과정이 서로 중첩된 시간에서 특별히 정해진 순서 없이 일어나는 것
    • 임의의 순서로 실행해도 같은 결과를 가지는 독립적 연산이 있다는 것을 전제로 삼는 개념
  • 병렬성: 작업을 물리적으로 동시에 실행하는 것
    • 가장 느린 부분의 속도가 병렬 프로그램의 속도가 된다
  • 시스템 콜: 런타임 시스템인 운영체제가 각종 하드웨어와 상호 작용하기 위해 제공하는 인터페이스
    • 커널 공간에서 운영 체제의 핵심 기능과 함께 동작한다
  • CPU: 다양하고 복잡한 작업의 연속 실행에 적합. MIMD 구조
  • GPU: 단순하고 제한적인 작업의 병렬 실행에 적합. SIMD 구조
  • 포트: 네트워크 상에서 특정 어플리케이션으로 진입하는 진입점
• 다중 프로세스
  • 자식 프로세스: 프로세스가 시스템 콜을 통해 자신이 속한 프로세스를 생성할 수 있다
  • fork(), spawn() 등의 시스템 콜을 통해 생성하며 별도의 주소 공간을 갖는 독립된 복제본이다
  • 스레드
    • 운영체제가 실행을 제어하는 작업의 독립적인 스트림
    • 프로세스는 자원을 할당받는 단위이고, 스레드는 실행하는 단위이다
• 프로세스 간 통신(IPC)
  • 공유 메모리 방식
    • 가상 주소 공간을 공유하는 작업이 마치 지역 변수를 다루듯 정보를 교환하는 방식
    • 매우 빠르나, 수평 확장이 어렵고 충돌이 발생 가능하다
  • 메시지 전달 방식
    • 모든 작업에 고유 식별자를 부여하고 식별자를 향해 메시지를 주고 받는 방식으로 교환
    • 운영체제는 여기에 쓰일 통신 채널을 수립하고 시스템 콜을 통해 메시지를 주고 받는 기능을 제공
    • 방식
      • 파이프: 작업 간의 단방향 데이터 흐름 정의. 유닉스 기준으로는 파일 디스크립터를 이용
      • 메시지 큐: 선입선출의 원칙에 따라 동작하고 여러 작업이 함께 메시지를 주고 받을 수 있다
        • 스레드 풀에서 메인 스레드와 워커 스레드 간 정보 교환에도 이용된다
  • 소켓 방식: 유닉스 도메인 소켓을 말한다
    • 네트워크를 경유하는 양방향 채널인 네트워크 소켓으로 교체가 용이하다
• 멀티태스킹
  • 일정 시간 동안 여러 작업을 동시에 실행하여 여러 작업을 수행하는 개념
  • 선점형 멀티태스킹: 운영체제가 일정 시간만큼 CPU를 할당하고 시간이 끝나면 다른 작업에 할당하는 방식
    • 타임 슬라이스: 한 작업이 실행되는 일정 시간의 정의
      • 타임 슬라이스가 끝나면 스케쥴러가 작업을 인터럽트하고 다음 작업을 실행하도록 한다
    • 컨텍스트 스위칭: 작업 컨텍스트 정보를 실행했을 때 문제가 없도록 모든 데이터를 저장하고 다른 작업의 컨텍스트 정보로 교체하는 물리적 행위
• 동시성 작업을 위한 분해
  • 작업 분해: 동시에 실행할 수 있는 기능으로 문제를 분해하려면 어떻게 할 지를 정의하는 것
    • 파이프라인 패턴: 스레드와 큐를 이용하여 독립적인 작업과 정보 교환을 처리한다
  • 데이터 분해: 한 집합에 담긴 여러 요소를 같은 연산으로 한꺼번에 적용할 때 정의
    • 맵 패턴: 분해된 작업 간의 동기화나 정보 교환이 필요없는 경우 유용
    • 포크/조인 패턴
      • 포크 단계: 데이터를 여러 뭉치로 나눈 후 독립적으로 처리하는 단계
      • 조인 단계: 동기화 지점으로 모든 의존 작업의 결과가 나온 후 최종 합산 처리하는 단계
    • 맵/리듀스 패턴: 포크/조인과 유사하지만 조인 직전인 리듀스 단계를 병렬 처리하여 조인 단계인 동기화 지점을 최대한 작게 만드는 패턴
• 경쟁 조건과 동기화
  • 경쟁 조건: 공유 자원이나 공통 변수에 동시에 접근하면서 연산의 상대적 순서에 의존하는 프로그램의 동작이 부정확해지는 현상
    • 스레드 안전: 실행되는 순서나 환경에 상관없이 여러 작업이 접근해 사용해도 의도하는 대로 동작하는 함수나 연산의 성질
  • 동기화: 여러 작업 간에 공유 자원에 대한 접근을 제어하는 수단
    • 임계 구역: 공유 자원을 접근하면서 여러 자원이 함께 실행될 가능성이 있는 부분
    • 락: 임계 구역을 보호하는 수단
      • 뮤텍스(상호 배제) 방식: 자원에 락을 걸어둔 상태라면 해제될 때까지 대기하는 방식
      • 세마포어 방식: 뮤텍스와 유사하지만 락을 걸 수 있는 남은 횟수를 가진 계수기가 존재한다
        • 뮤텍스는 사실 이진 세마포어에 해당한다
      • 원자적 연산 방식: 해당 연산의 중간 단계를 다른 스레드가 볼 수 없는 연산
  • 메시지 전달 IPC도 경쟁 조건을 해소하는데 유용하다
• 교착 상태와 기아 상태와 해결책
  • 작업이 2개 이상의 락을 필요로 하는 상황에서 발생한다
  • 데드락: 2개 이상의 작업이 각자 서로 필요한 자원을 1개씩만 소유하여 서로의 자원을 대기하는 상태
    • 중재인 패턴: 중재인을 두어 락을 걸기전에 시도 가능 여부를 확인하는 패턴
      • 락을 해제 할 때는 중재인을 통할 필요는 없다
    • 우선순위 패턴: 락에 우선 순위를 두어 항상 우선 순위의 락을 먼저 걸게 만드는 패턴
      • 첫 번째 락만 경합이 발생하여 데드락을 방지하나 라이브락을 막을 수는 없다
  • 기아 상태: 스레드가 필요한 자원을 아예 얻지 못해 일하지 못하는 상태
    • 에이징 기법: 대기 시간의 길이를 우선 순위 계산에 산입하여 스레드가 언제가는 필요한 자원을 얻을 수 있도록 하는 스케쥴링의 한 방법
    • 라이브락: 두 번째 락을 얻으려 할 때 첫 번째 락이 해제되면서 대기하는 현상
      • 기아 상태의 한 종류이다
  • 프로듀서-컨슈머 문제: 뮤텍스와 세마포어를 이용하여 동기화 문제를 해결한다
  • Read-Write 락: 공유 데이터의 동기화 문제를 해결하는 한 방법
    • 리더는 제한 없이 언제라도 공유 데이터를 읽을 수 있다
    • 동시에 한 개의 라이터만 공유 데이터를 변경 할 수 있다
    • 라이터가 데이터를 변경하고 있다며 모든 리더를 데이터를 읽을 수 없다
• 논 블록킹 I/O
  • 블록킹 I/O의 문제점: 서버에서 I/O 연산을 기다리며 여러 접속을 처리하기 위해 스레드를 늘리는 방식은 타임 슬라이스 및 컨텍스트 스위칭에 의해 매우 성능이 저하
  • 논 블록킹 I/O: 적은 스레드로 I/O 연산을 처리하기 위해 일을 시작하는 즉시 제어를 호출 측에 바로 반납하고 다른 작업을 수행할 수 있도록 처리
  • 무식한..구현 방법
    • 바쁜 대기: 입출력 연산을 반복 호출하는 무한 루프를 두어 완료된 연산이 있다면 처리하는 방식
• 이벤트 기반 동시성
  • 어떤 이벤트가 일어날 때까지 대기하다가 이벤트 발생 시 동작하는 방식
  • 이벤트 루프: 이벤트를 제어하고 추적하고 각 이벤트에 맞는 콜백을 실행하는 역할
  • 이벤트 큐: 새로운 이벤트가 발생하면 순차적으로 이벤트를 저장하는 큐.
    • 이벤트 루프가 큐에서 이벤트를 꺼내 콜백을 호출한다
  • I/O 멀티플렉싱: 운영체제의 이벤트 알림 하위 시스템.
  • 리액터 패턴: 이벤트가 발생하기 까지 대기하다가 발생한 이벤트를 처리하는 반복문 패턴
  • 입출력 모델
• 비동기 통신

• 할 일과 수행 시점을 분리하는 방법은 어플리케이션의 내부 구조를 개선하며 성능,확장성,신뢰성 달성에 유리해 진다
• 프로그램의 속도를 가장 크게 제한하는 요소는 입출력 중심의 연산(I/O) 이다
• 운영 체제의 스레드(특히 프로세스)는 비교적 적은 수로 오랫동안 동작하는 작업에 적합
• 웹 워커: 웹 어플리케이션의 주 스레드와 격리된 백그라운드 스레드에서 여러 작업을 수행할 수 있도록 만들어진 기술