Part 1: PAS 알고리즘 소개 — 시스템최신기술 2026

← 전체 실습 안내로 돌아가기 English

1. I/O Completion이란?

애플리케이션이 스토리지에 I/O 요청을 보낸 후, 디바이스가 처리를 완료할 때까지 어떻게 기다리는가를 결정하는 메커니즘입니다. 이 "기다리는 방법"에 따라 I/O 지연시간과 CPU 사용률이 크게 달라집니다.

Interrupt (INT)

I/O 요청 후 CPU를 양보하고 sleep. 디바이스가 완료하면 인터럽트로 깨움.

장점: CPU 효율적 — sleep 중 다른 작업 가능

단점: 인터럽트 처리 오버헤드, 컨텍스트 스위치 지연

Interrupt 기반

Classic Polling (CP)

I/O 요청 후 완료될 때까지 CPU가 계속 확인 (busy-wait).

장점: 최소 지연 — 완료 즉시 감지

단점: CPU 100% 점유, 다른 작업 불가

Polling 기반

Linux Hybrid Polling (LHP)

예측된 시간만큼 sleep한 후 polling. Epoch 단위로 sleep 시간을 조정.

장점: sleep 중 CPU 양보 + polling으로 빠른 감지

단점: Epoch 기반 → 느린 적응, latency shelving 문제

Hybrid

PAS (Per-I/O Adaptive Sleep)

매 I/O마다 binary feedback으로 sleep 시간을 즉시 조정.

장점: 빠른 수렴, I/O별 적응, shelving 없음

단점: 개별 I/O 노이즈에 민감할 수 있음

Hybrid (Per-I/O)

핵심 trade-off I/O completion은 지연시간(latency)과 CPU 효율(utilization)의 trade-off입니다. Polling은 지연이 최소지만 CPU를 독점하고, Interrupt는 CPU 효율적이지만 지연이 큽니다. Hybrid 방식은 이 사이에서 균형을 찾으려는 시도이며, PAS는 그중 가장 세밀한(per-I/O) 접근입니다.

2. LHP의 문제: Latency Shelving

LHP는 epoch 단위로 평균 I/O 지연시간을 측정하고, 다음 epoch의 sleep 시간을 평균 지연시간 × attenuation으로 설정합니다.

이때 oversleep이 발생하면 (sleep 시간 > 실제 디바이스 완료 시간), 애플리케이션이 관측하는 I/O 지연시간은 "sleep 시간 + 컨텍스트 스위치"가 됩니다. 이 부풀려진 지연시간이 다시 다음 epoch의 sleep 계산에 입력되면서, 양의 피드백 루프가 발생합니다:

oversleep → 관측 지연시간 증가 → sleep 시간 증가 → 더 많은 oversleep → ...

이 현상을 latency shelving이라 합니다. 한번 shelving이 시작되면 epoch이 끝날 때까지 복구되지 않으며, 이 기간 동안 성능이 interrupt 수준 이하로 저하될 수 있습니다.

Part 3에서 직접 확인 LHP 에뮬레이터에서 step 패턴 trace를 실행하면 latency가 갑자기 감소할 때 shelving이 발생하는 것을 눈으로 확인할 수 있습니다.

3. PAS 알고리즘

핵심 아이디어: Binary Feedback

PAS는 각 I/O 완료 후 하나의 질문만 확인합니다:

wake_time = sleep_duration + context_switch_overhead

if (device_completion_time > wake_time)
    결과 = UNDER   // 너무 일찍 깨어남 → busy-wait 발생
else
    결과 = OVER    // 너무 늦게 깨어남 → 불필요한 대기

이 UNDER/OVER 판정을 기반으로 sleep duration을 매 I/O마다 조정합니다.

4가지 업데이트 규칙

PAS는 직전 I/O와 현재 I/O의 결과 조합 (2-bit history)으로 조정 계수(adj)를 결정합니다. Sleep duration은 dur = dur_last × adj로 계산됩니다:

직전 결과	현재 결과	해석	adj 업데이트
UNDER	UNDER	연속 undersleep → sleep이 확실히 부족	누적 가속: `adj += UP`
UNDER	OVER	방향 전환 → 적정선 근처	리셋 + 소폭 감소: `adj = 1 − DN`
OVER	UNDER	방향 전환 → 적정선 근처	리셋 + 소폭 증가: `adj = 1 + UP`
OVER	OVER	연속 oversleep → sleep이 확실히 과다	누적 가속: `adj −= DN`

핵심 설계:

같은 방향 연속 (UU, OO): adj에 UP/DN을 누적합니다. 연속될수록 조정이 가속됩니다.
방향 전환 (UO, OU): adj를 1 근처로 리셋합니다. 적정선에 도달했으므로 큰 조정이 불필요합니다.

// 의사 코드
wake_time = dur + cs_overhead

if (device_latency > wake_time)  sr = UNDER
else                             sr = OVER

switch (sr_prev, sr_curr):
    (UNDER, UNDER): adj += UP        // 누적 → 1+UP, 1+2UP, 1+3UP, ...
    (UNDER, OVER):  adj = 1 - DN     // 리셋 (약간 줄임)
    (OVER, UNDER):  adj = 1 + UP     // 리셋 (약간 늘림)
    (OVER, OVER):   adj -= DN        // 누적 → 1-DN, 1-2DN, 1-3DN, ...

dur_next = dur_current * adj

LHP와의 차이

LHP: epoch (수백~수천 I/O) 단위 조정, 실제 지연시간을 입력으로 사용 → shelving 취약
PAS: 매 I/O 단위 조정, binary (UNDER/OVER) 판정만 사용 → 실제 지연시간을 입력으로 쓰지 않으므로 shelving 면역

4. 다음 단계

알고리즘을 이해했다면, 시뮬레이터/에뮬레이터에서 동작을 직접 확인해 보세요.

Part 2: PAS 시뮬레이터 / 에뮬레이터로 이동 → 시뮬레이터(트래킹)와 에뮬레이터(피드백 반영)의 차이를 비교하며 PAS 동작을 확인합니다

DPAS가 궁금하다면 PAS의 한계와 이를 해결하는 DPAS의 런타임 모드 전환 메커니즘은 Part 4: DPAS 소개에서 자세히 다룹니다.

논문 원문: DPAS: A Prompt, Accurate and Safe I/O Completion Method for SSDs (USENIX FAST '26, Seo et al.)