Shinjuku: Preemptive Scheduling for μsecond-scale Tail Latency


NSDI 2019

Motivation

u second level의 tail latency를 제공하는 Network시스템을 구축하기 위해서, NIC와 Application의 Data plane을 효율적으로 작성해야 한다.

Main Idea

  • Dune을 사용하였다.
  • Approximate PS (Processor sharing)를 통해서 워크로드를 수행하였다. 기존에 ps를 사용하지 않은 이유는 processor간의 스케쥴링이 매우 느리기 때문이다.
  • PS는 효율적으로 preemption알고리즘을 구현해야 한다. yield와 같은 경우는 ms단위이기 때문에 사용하기 매우 느리다.

기존의 방식들은 polling방식으로는 비효율성이 생기기 때문에, interrupt방식을 채택하되, 어떻게 하면 interrupt방식의 tail latency를 줄일 수 있을까?

Design

Fast Preemption
DUNE을 extend하여서 local APIC register에 직접 접근이 가능하도록 하였다. 그러나 local APIC에 접근하면 VM exit이 발생하는데, Virtualization을 활용해서 posted interrupt(수신만 가능기능 (x86)을 사용해서, vm exit이 없이 IPI를 전송할 수 있도록 하였다. 이 기능을 이용해서 worker들은 posted interrupt을 통해서 입터럽트를 받고, Trust Shinjuku dispatcher는 TCB에 넣어서, real APIC으로 worker들에게 IPI를 dispatch할 수 있도록 하였다. IPI를 매우 매우 Optimize하여서 통신에 있어서의 latency를 줄였다.
Low-Overhead Context Switch
Context switch또한 Optimize하였다. 리눅스 default와 같은 경우 swapcontext와 같은 경우에는 1000 cycle, Dune 2290 cycle정도 걸린다. signal mask나 fp restore처럼 필요없는 (신주쿠에서 사용하지 않는) 기능들을 뺀 것이다.

Conclusion

  • Context switch management를 u second레벨까지 줄여야할 필요가 있다는 것을 보여준다.
  • Optimization기반을 어떻게 하면 좋을 것일가를 보여준다.
  • RR를 극한까지 사용하면 Shortest job first에 근사하는데, 그러한 모델을 보여주었다.