Blocking vs Non-Blocking
Introduction
많은 분들이 Non-Blocking 알고리즘이 빠르다는 것을 들어서 알고 있지만,
1. Non-Blocking I/O와 혼용해 사용하는 경우가 많고
2. 정확히 Non-Blocking 알고리즘이 어떤 것인지 모르고
3. Blocking보다 어떤 이유에서 빠른지 모르기 때문에
본 포스팅에서 해당 내용을 확실하게 정리해보려고 합니다.
Interrupt
내가 interrupt를 잘 알고 있다 확신하면 다음 장으로 건너뛰셔도 됩니다.
interrupt는 processor가 현재 실행 중인 코드를 중단시키는 요청입니다.
interrupt가 accept되면, 프로세서는 현재 활동을 중단하고, 해당 활동의 state를 저장하고, interrupt를 핸들링하기 위해 interrupt handler라 불리는 함수를 실행시킵니다.
인터럽트들은 흔히 real-time computing에서 computer multitasking을 구현하기 위해 사용됩니다.
이를 위해 인터럽트를 사용해 구축된 시스템을 interrupt-driven 하다고 합니다.
Interrupt signal은 hardware나 software 이벤트의 응답으로 발생됩니다. 이는 각각 hardware interrupt와 software interrupt로 구분됩니다.
Hardware interrupt
hardward interrupt는 외부 하드웨어 디바이스로 부터 signal 된 hardware state와 관련된 상태입니다.
하드웨어 인터럽트는 process clock과 async 하게 도착할 수 있고, instruction 실행 도중 임의의 시간에 들어올 수 있습니다. 해당 인터럽트들은 processor의 clock cycle로 synchronize 해야지 각 인터럽트 signal들이 instruction execution boundary 하에 실행될 수 있습니다.
이를 효율적으로 여러 처리 방법들이 연구되고 구현됐지만 굳이 다루지 않겠습니다. hardware interrupt도 instruction execution boundary하에 실행되는 점만 이해하면 됩니다.
Software interrupt
software interrupt는 프로세서 그 자체로 부터 특정 instruction을 실행 하에 요청되거나 특정 상태가 충족되었을 때 요청됩니다. 모든 소프트웨어 인터럽트 signal은 특정 interrupt handler와 연관되어 있습니다.
softeware interrupt는 실행시 interrupt를 발생시키도록 디자인된 특별한 instruction을 실행시킴으로써 발생됩니다. 이이런 instruction function은 OS 서비스들에 요청하는 것과, device driver들과 interacting 하는 것 같은 다양한 목적으로 사용됩니다. Software interrupt들은 프로그램 실행 에러나 Virtual memory system으로부터도 트리거 될 수 있습니다.
보통 OS의 kernel이 그러한 interrupt를 캐치하고 핸들링 합니다.
몇 인터럽트들은 프로그램이 인식 못하는 선에서 핸들링됩니다. 예를 들어 page fault의 일반적인 해결은 필요한페이지를 physical memory에서 접근 가능하게 만드는 것입니다.
seg fault와 같은 나머지 경우, OS는 process callback을 실행합니다. Unix 기반 OS는 SIGSEGV, SIGBUS, SIGILL, SIGFPE와 같은 signal을 보내고, 윈도우에서는 STATUS_ACCESS_VIOLATION이나 STATUS_INTEGER_DIVIDE_BY_ZERO와 같은 exception code를 포함해 callback을 호출합니다.
커널 프로세스에서, 몇 software interrupt는 일어나지 않을 것을 상정하는 경우가 많습니다. 만약 그런 인터럽트들이 발생한다면, OS crash가 발생할 수 있습니다.
Processor Architecture별 Interrupt 구분
(* 해당 챕터는 syscall이 interrupt를 통해 구성된다는 부분을 이야기하기 위해 작성되었습니다. 해당 부분을 안다면 다음으로 넘어가셔도 됩니다.)
x86 아키텍처에서는 interrupt를 interrupts (하드웨어), softeware exception으로 구분하고, exception을 fault, trap, abort로 구분합니다. interrupts (하드웨어)는 I/O device로부터 async 하게 발생하고, 프로그램이 연속성을 잃지 않으며 다시 시작될 수 있게 허용합니다. fault도 재시작이 가능하지만, sync하게 실행되는 instruction과 연관되어 있으며, 반환 주소는 fault가 발생한 instruction을 가리킵니다. trap을 fault와 비슷하지만, 반환 주소가 trap을 발생시킨 명령어 다음에 실행될 명령어를 가리킵니다. trap의 주요 사용 예 중 하나는 syscall을 구현하는 것입니다. abort는 하드웨어 오류나 system tables에서 접근 불가능한 값과 같은 심각한 오류에 사용되고, 종종 프로그램이 재시작되지 않게 합니다.
Arm 아키텍처에서는 exception이라는 용어로 모든 종류의 interrupt를 정의합니다. 그리고 exception을 interrupts, aborts, reset, exception-generating instruction으로 구분합니다. Aborts는 x86의 exception에 대응됩니다. Arm architecture에서 abort는 prefetch abort일 수도 있고, data abort일 수도 있고, sync 할 수도 있고, async 할 수도 있습니다. abort가 sync 한 경우, instructinon stream의 실행 또는 시도된 실행의 결과로 생성되며, return address가 그 원인이 된 명령에 대한 세부 정보를 제공하는 경우입니다. abort가 async 한 경우, instruction들을 실행함으로써 생성되지 않으며, return address가 항상 abort 원인에 대한 세부 정보를 제공하지는 않을 수 있습니다. ARMv7 architecture은 precise, imprecise async abort를 구분합니다. 예를 들어 MMU abort (page fault)는 sync 합니다. async abort의 구현 방법은 Types of exception을 참고하세요.
Asynchronous I/O (=Non-sequential I/O)
Asynchronous I/O는 I/O 연산이 끝나기 전에 다른 processing이 계속되도록 실행하는 I/O processing의 형태입니다. windows api에서는 overlapped I/O로 표현됩니다.
컴퓨터에서의 I/O 연산은 데이터 처리에 비하면 굉장히 느립니다. I/O로의 간단한 접근 방식은 access를 시작하고, 연산이 끝날 때까지 기다리는 것입니다. synchronous I/O 혹은 Blocking I/O라 불리는 이러한 방식은 communication이 진행 중일 때 시스템 리소스를 idle 상태로 두며 실행 중인 프로그램을 block 시킵니다. 프로그램이 많은 I/O 연산을 만든다면, 이는 프로세서가 대부분의 시간을 I/O연산이 끝날 때까지 기다리며, idle 상태로 보내는 것을 의미합니다.
blocking I/O를 처리 방식 대신 I/O communication을 시작되더라도, I/O에 종속되지 않은 처리들을 실행하는 것은 가능합니다. 이 접근은 async I/O라 불립니다. I/O에 종속된 임의의 task는 여전히 I/O 연산이 끝날 때 까지 기다릴 필요가 있고, block 되어야 합니다. 하지만 I/O에 종속되지 않은 다른 처리들은 계속될 수 있습니다.
많은 OS function들은 asynchronous I/O를 많은 수준에서 구현되어 존재합니다. Interrupt에서 언급한 대로 hardware로부터의 interrupt는 async 하게 오지만, instruction execution boundary에 맞추기 위해 polling 하는 방식을 채택했습니다. 이는 user-space에서는 안 보이지만, kerner-space에서 확인할 수 있습니다.
Linux의 I/O 모델
Linux 상에서 IO 모델은 Blocking I/O vs Non-Blocking I/O / Sync I/O vs Async I/O로 구분됩니다. 각 I/O 모델은 특정 application에 이점이 있는 사용 패턴들을 갖고 있습니다.
Synchronous + Blocking I/O
sync + blocking I/O 모델은 가장 흔한 모델 중 하나입니다. 이 모델에서, user-space application은 application을 blocking 시키기 위해 syscall을 실행합니다. 이는 application이 syscall이 완료될 때까지 block 됨을 의미합니다. read를 요청한 application은 어떤 CPU 자원도 사용하지 않고, response를 단순히 기다립니다. 따라서 이는 processing관점에서 효율적입니다.
위 이미지는 오늘날 application에서 가장 흔히 사용되는 전통적인 blocking I/O 모델을 나타냅니다. `read` syscall이 실행되었을 때, application은 block 되고, 커널로 context switch 됩니다. read는 시작되고, respnose가 return 되었을 때, 데이터는 user-space buffer로 이동됩니다. 그 후 application은 unblock 됩니다. (그리고 그 데이터는 read call의 return으로 주어집니다.)
application의 관점에서, read call은 실행시간이 깁니다. 하지만 사실, read 연산이 kernel에서 다른 일들과 multiplexing 되는 동안, application은 block 되어 있습니다.
Synchronous + Non-blocking I/O
Synchronous + non-blocking I/O는 Sync+Blocking I/O보다 덜 효율적인 변형입니다. Sync+Non-blocking I/O 모델에서 device는 non-blocking 하게 open 됩니다. 이는 I/O를 즉시 완료할 수 없을 때 에러코드 (EAGAIN, EWOULDBLOCK)를 반환할 수 있으며, 위 그림과 같습니다.
Non-blocking의 의미는 I/O command가 즉시 만족되지 않을 수 있다는 것입니다. 따라서 application이 완료를 기다리기 위해 syscall을 여러 번 호출해야 합니다. 대부분의 경우에서 application이 data가 유효해질 때까지 busy-wait 해야 하거나 다른 작업을 수행해야 하는데, 이는 interrupt가 많아서 context switching이 자주 일어나고, kernel에 많은 syscall이 호출되게 합니다. 즉 비효율적입니다. 또한 이 방법은 I/O에 지연을 초래할 수 있습니다.
Asynchronous + Blocking I/O
다른 blocking 패러다임은 non-blocking I/O를 blocking notification과 함께 사용하는 것입니다. 이 모델에서, non-blocking I/O가 설정되고, blocking 하게 동작하는 "select()" syscall이 I/O descriptor을 위한 임의의 activity가 있을 때를 결정하는데 사용됩니다. select 호출이 흥미로운 점은 하나의 descriptor 뿐 아니라, 여러 개에 대한 알림을 제공할 수 있다는 것입니다. 각 descriptor에 쓰기, 읽기, 에러 발생 여부에 대한 notification을 요청할 수 있습니다.
select call에 주된 문제는 효율적이지는 않다는 것 입니다. 이 모델은 asyncronous notification이 편리한 모델이지만, 고성능 I/O 케이스에 사용하는 것이 권장되지 않습니다.
Asynchronous + Non-blocking I/O (AIO)
마지막으로, async+non-blocking 모델은 I/O와 처리방식을 동시에 처리하는 방법 중 하나입니다. read 요청은 즉시 반환되며, read가 성공적으로 시작되었음을 나타냅니다. 이후 application은 background read operation이 완료되는 동안 다른 처리를 수행할 수 있습니다. read response가 도착하면, signal이나 다른 thread base callback이 생성되어 I/O transaction을 완료할 수 있습니다.
여러 I/O 요청이 있을 수 있는 단일 프로세스에서 computation과 I/O processing을 동시에 처리하는 능력은 processing 속도와 I/O 속도 사이의 간격을 최대한 활용할 수 있습니다. 하나 이상의 I/O 요청이 팬딩 되어 있는 동안, CPU는 다른 task들을 수행하거나 다른 I/O가 시작되는 동안 이미 완료된 I/O들을 연산할 수 있습니다.
Non-Blocking Algorithm
이제 sync, async, blocking I/O, non-blocking I/O에 대해 이해했습니다. 앞 개념과 많이들 헷갈리는 개념인 Non-Blocking algorithm에 대해 이야기해보려고 합니다.
non-blocking algorithm은 어떤 스레드의 실패나 중단이 다른 스레드의 실패나 중단을 일으킬 수 없을 때 해당 알고리즘은 non-blocking 하다고 합니다. 몇몇 케이스에 대해, non-blocking 알고리즘들은 전통적인 blocking implentation(lock)을 효과적으로 대체할 수 있습니다. non-blocking algorithm은 system-wide progress에 대해 non-blocking이 보장된다면 lock-free 합니다. 또한 per-thread progress에 대해 non-blocking이 보장된다면 wait-free 합니다.
단일 writer와 여러 reader로 구성된 Read-copy-update와 같은 synchronization 메커니즘이 Non-Blocking algorithm에 해당됩니다.
Blocking algorithm vs Non-Blocking Algorithm
thread를 blocking 하는 것은 가능하면 피해야 합니다.
이에 대한 가장 명확한 이유는 thread가 block 되어 있는 동안 아무것도 수행할 수 없습니다. thread가 매우 중요하거나 real-time 한 task를 진행하고 있다면, 해당 스레드의 진행을 중단하는 것은 바람직하지 않습니다.
또한 lock기반 구현체는 deadlock, livelock, priority inversion과 같이 error-prone해지게 됩니다. (Lock#Disadvantages)
따라서 개발 난이도가 올라가고, 해당 문제들을 주의하기 위한 오버헤드가 발생하기 때문에, 생산성과 성능 모든 점에서 손해를 보게 됩니다.
blocking algorithm과 다르게 non-blocking algorithm은 이러한 단점에서 자유로우며, interrupt handler에서도 안전하게 사용할 수 있습니다. 즉 선점된 스레드가 재개될 수 없더라도, 그것 없이 진행이 가능합니다. 반면 lock 기반 스레드는 interrupt handler에서 실행되기 어렵습니다. 이유는 선점된 스레드가 lock을 보유하고 있을 수 있기 때문입니다.
(* critical section동안 interrupt를 masking 함으로써 처리할 수 있긴 합니다.)
Nodejs의 Event loop
우선 Nodejs Application은 non-blocking algorithm을 따를까요?
우선 per-thread progress의 관점에서는 nodejs는 각 이벤트 루프들은 single thread로 동작합니다. 즉, wait-free 하기 때문에, non-blocking 하다고 볼 수 있습니다.
system-wide progress의 관점에서는 대부분의 유즈케이스의 경우 non-blocking algorithm을 따른다고 볼 수 있지만, system-wide 공유 자원에 대한 I/O 접근이 필요할 때는 그렇지 않을 수 있습니다.
nodejs는 single threaded 하고, async+non-blocking I/O를 사용합니다. single threaded를 채택함으로써 shared memory에 대한 race condition 걱정이 사라지게 되었고, wait-free 하게 됩니다.
Nodejs의 core 로직도 single threaded로 동작하는 것으로 알고 있는 분들이 많은데, 실제로는 nodejs의 core 로직은 single thread로 동작하지 않습니다.
우선 nodejs의 이벤트루프는 위 그림과 같이 single thread + async+non-blocking I/O를 통해 동작합니다. 각 phase는 FIFO 큐를 갖고 있습니다. 각 콜백 함수들이 실행이 끝나거나 async 함수의 경우 await 되기까지 실행을 이어나갑니다. 따라서 nodejs의 애플리케이션은 각 콜백 혹은 async function이 연속성이 보장되기 때문에 shared memory에 대한 동시 접근에 대한 고민을 최소화할 수 있습니다.
하지만 실제 I/O의 경우 libuv가 OS별 async+nonblocking I/O에 해당되는 syscall을 이용해 multi thread로 처리하게 됩니다. libuv의 I/O를 담당하는 스레드가 실질적으로 OS와 통신하고, 적절히 user-space의 버퍼를 이벤트루프의 polling queue에 넣어줍니다. 따라서 공유 자원에 대한 읽기, 쓰기가 동시에 일어나면 race condition을 피하기 힘듭니다. 이런 경우 primitive를 활용해 접근 순서를 적절히 queueing 해주어야 합니다.
맺음말
lock은 비싼 연산입니다. 생산성 측면에서도 코드에 과도한 복잡성을 부여하고, 성능에도 단점이 있고, 코드가 error prone 하게 됩니다.
적절한 core 로직을 구현해 각 스레드가 non-blocking 하게 동작할 수 있도록 하는 것은 성능 및 생산성에 큰 도움이 됩니다.
Reference
https://en.wikipedia.org/wiki/Interrupt
https://www.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-software-developers-manual-volume-1-basic-architecture.html
https://developer.arm.com/documentation/den0013/d/Exception-Handling/Types-of-exception?lang=en
https://developer.ibm.com/articles/l-async/
https://en.wikipedia.org/wiki/Asynchronous_I/O
https://en.wikipedia.org/wiki/Lock_(computer_science)
https://en.wikipedia.org/wiki/Non-blocking_algorithm
https://nodejs.org/en/docs/guides/event-loop-timers-and-nexttick
https://medium.com/@salil.kumar2093/learn-node-js-under-the-hood-37966a20e127
https://chathuranga94.medium.com/nodejs-architecture-concurrency-model-f71da5f53d1d