vLLM 스케줄러 한 스텝

vLLM 스케줄러 한 스텝 A workflow diagram generated by Archify. 01 / 1차: RUNNING 큐 순회 (디코드) 02 / 2차: WAITING 큐 순회 (프리필) EX / 블록 부족 시 선점 토큰 예산 · 스텝당 토큰 상한 · 1차: RUNNING 큐 순회 (디코드) 토큰 예산 스텝당 토큰 상한 RUNNING 순회 · 디코드 · 진행 중 프리필 · 1차: RUNNING 큐 순회 (디코드) RUNNING 순회 디코드 · 진행 중 프리필 블록 할당 · allocate_slots() · 1차: RUNNING 큐 순회 (디코드) 블록 할당 allocate_slots() 선점 있었나? · 있으면 프리필 순회 생략 · 1차: RUNNING 큐 순회 (디코드) 선점 있었나? 있으면 프리필 순회 생략 실행 계획 · SchedulerOutput · 1차: RUNNING 큐 순회 (디코드) 실행 계획 SchedulerOutput WAITING 순회 · max_num_seqs · max_loras · 2차: WAITING 큐 순회 (프리필) WAITING 순회 max_num_seqs · max_loras 프리픽스 캐시 · get_computed_blocks() · 2차: WAITING 큐 순회 (프리필) 프리픽스 캐시 get_computed_blocks() 청크 프리필 · 남은 token_budget까지 · 2차: WAITING 큐 순회 (프리필) 청크 프리필 남은 token_budget까지 요청 선점 · 최저 우선순위 블록 해제 · 블록 부족 시 선점 요청 선점 최저 우선순위 블록 해제 status = RUNNING 첫 스케줄이면 히트분 제외 선점 없음 확보 완료 블록 해제 후 재시도 num_new_tokens 산정 allocate_slots() 실패 선점 발생 시 생략 예산 배분 시작 Legend 스케줄 단계 판단 · 게이트 실행 계획 KV 블록

두 번의 순회

  • • token_budget은 max_num_scheduled_tokens에서 시작해 배분할 때마다 차감
  • • RUNNING을 먼저 채우고, 선점이 없었을 때만 WAITING을 순회

블록이 모자랄 때 — 선점

  • • FCFS는 running의 마지막, PRIORITY는 (priority, arrival_time) 최대를 선점
  • • 선점된 요청은 num_computed_tokens=0으로 waiting 맨 앞에 되돌아감

프리픽스 캐시와 청크 프리필

  • • num_computed_tokens==0인 요청만 get_computed_blocks()로 히트를 조회
  • • chunked prefill이 꺼져 있으면 예산을 넘는 프리필에서 순회를 중단