| Skyloft: A General High-Efficient Scheduling Framework in User Space | |
|---|---|
| Author | Yuekai Jia†∗, Kaifu Tian†∗, Yuyang You†, Yu Chen‡†, Kang Chen†
†Tsinghua University, Beijing, China ‡Quan Cheng Laboratory, Jinan, China Both authors contributed equally to this research(*). |
| Conference | SOSP |
| Year | 2024 |
개요
Skyloft는 General하고 매우 효율적인 User-space scheduling framework를 User-level interrupt(Intel UIPI)를 통해서 구현하였으며, 이를 통해서 SOTA work대비 훨씬 빠른 속도를 보일 수 있었다.
Motivation & Importance
다양한 방식을 이용한 User-level scheduling연구와 Framework들이 존재해 왔지만, micro-second level의 tail latency를 맞출 수 있는 Framework가 존재하지 않았다. 이러한 낮은 레벨의 Latency는 현재 Latency sensitive한 Cloud datacenter을 위해서 필수적이다. 또한 이러한 User-level scheduler는 Multiple application을 Support하는 것이 필수적인데, 이는 Application마다 Latency sensitive, Batch-processing처럼 특성이 달라, Bursty한 시점에는 Latency sensitive에 Core를 더 할당하고, Idle한 상태에서는 Batch-processing application (Throughput)에 더 많은 코어를 할당하는 Balancing이 필요하기 때문이다.
그러나 동시에 microsecond latency와 Multiple application support를 동시에 달성하는 것은 Challenging하다. 이는 Microseond-scale preemption을 위해서는 Context switching overhead와 Scalability issue가 있는 Signal을 뛰어넘는 매커니즘이 필요하고, Multi-application support를 위해서는 여러개의 Isolation domain (Process)을 안전하고 효율적으로 관리할 수 있는 Policy가 필요하기 때문이다.
Main Idea
Skyloft는 다음 3개의 Goal을 가지고 Library를 디자인 하였다. Flexibility, Efficiency, and Compatibility.
- User-space scheduler는 모든 애플리케이션이 공유하는 공용 런큐(shared runqueue)를 유지하며, 다양한 사용자 정의 정책(user-defined policy)을 기반으로 스케줄링 결정을 수행한다.
- 컨텍스트 스위칭이 필요한 경우, 스케줄러는 다음 두 가지 방식 중 하나를 선택한다. 사용자 공간에서 직접 User Thread를 전환하거나,
- 관련된 애플리케이션의 종류에 따라 Kernel 모듈을 호출하여 Kernel Thread를 전환한다.
- User-space scheduler는 User Interrupt를 마이크로초(us) 단위의 **고속 선점(preemption)** 을 가능하게 한다.
- Skyloft LibOS는 Kernel-bypass I/O stack을 커널 경로를 거치지 않고 빠른 입출력을 수행할 수 있도록 설계하였다.
Design
- User-space Preemption
- User-space Preemption을 Intel UIPI로 구현하였다. 여기서 Challenging한 부분은 Timer interrupt를 구현하는 것인데, Timer interrupt가 들어오면, SENDUIPI를 보내서 UIPI를 부를수 있긴 한데, 이러면 IPI가 발생하기 때문이다. 이를 방지하기 위해서 Local에서 Timer interrupt가 들어오면, UPID의 SN을 끄고 SENUIPI를 실행시켜서 다른 코어에 IPI가 가지않고, 스스로에게만 IPI가 가도록 하였다.
- Scheduling Threads Across Applications
- 우선 새로운 프로세스가 생성된면 SkyLoft는 코어개수만큼 Kernel thread를 만들어서 그 Process에 할당하였다. 코어개수만큼 생성된 Kernel thread중에 하나만 Runable로 마킹되어서 실행될 수 있다. 하나의 코어에는 딱 하나의 kernel thread만 Binding할 수 있도록 하는 Single binding rule'을 제시하였다. SkyLoft는 코어에 바인딩된 Application의 개수와 동일한 Kernel-level thread중에서 어떤 Application의 Kernel thread가 동작할지 선택하기만 하면된다. 이를 통해서 Kernel scheduler를 완전히 Bypass하였다. 그후 SkyLoft는 User-level context switching을 수행하였다. 이때, SkyLoft의 관리를 안받는 Thread나 Kernel thread가 Kernel scheduler에 의해서 Preemption될수도 있어서 적절한 Affinity를 설정해 주어야 한다.
- Timer interrupt가 들어오거나 (위에 설명한 Intel UIPI), 아니면 Explicit한 호출이 있으면 SkyLoft는 Runqueue에서 Next thread를 가져온다. 이때 만약 같은 Process이면 그대로 User-level context switch를 진행하고, 만약 아니면, Kernel에 Kernel thread switching을 하도록 SkyLoft Kernel Module이 제공하는 API로 Kernel thread를 context switching하였다.
Conclusion
본 논문은 Intel UIPI를 활용한 효율적인 User-level scheduling 매커니즘과 Policy를 제공하였다는 점에서 의의를 찾을 수 있다.