| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | |
| 4 | import heapq |
| 5 | from abc import ABC, abstractmethod |
| 6 | from collections import deque |
| 7 | from collections.abc import Iterable, Iterator |
| 8 | from enum import Enum |
| 9 | |
| 10 | from vllm.v1.request import Request |
| 11 | |
| 12 | |
| 13 | class SchedulingPolicy(Enum): |
| 14 | """Enum for scheduling policies.""" |
| 15 | |
| 16 | FCFS = "fcfs" |
| 17 | PRIORITY = "priority" |
| 18 | |
| 19 | |
| 20 | class RequestQueue(ABC): |
| 21 | """Abstract base class for request queues.""" |
| 22 | |
| 23 | @abstractmethod |
| 24 | def add_request(self, request: Request) -> None: |
| 25 | """Add a request to the queue according to the policy.""" |
| 26 | pass |
| 27 | |
| 28 | @abstractmethod |
| 29 | def pop_request(self) -> Request: |
| 30 | """Pop a request from the queue according to the policy.""" |
| 31 | pass |
| 32 | |
| 33 | @abstractmethod |
| 34 | def peek_request(self) -> Request: |
| 35 | """Peek at the request at the front of the queue without removing it.""" |
| 36 | pass |
| 37 | |
| 38 | @abstractmethod |
| 39 | def prepend_request(self, request: Request) -> None: |
| 40 | """Prepend a request to the front of the queue.""" |
| 41 | pass |
| 42 | |
| 43 | @abstractmethod |
| 44 | def prepend_requests(self, requests: Iterable[Request]) -> None: |
| 45 | """Prepend all requests from another queue to the front of this |
| 46 | queue.""" |
| 47 | pass |
| 48 | |
| 49 | @abstractmethod |
| 50 | def remove_request(self, request: Request) -> None: |
| 51 | """Remove a specific request from the queue.""" |
| 52 | pass |
| 53 | |
| 54 | @abstractmethod |
| 55 | def remove_requests(self, requests: Iterable[Request]) -> None: |
| 56 | """Remove multiple specific requests from the queue.""" |
| 57 | pass |
| 58 | |
| 59 | @abstractmethod |
| 60 | def __bool__(self) -> bool: |
| 61 | """Check if queue has any requests.""" |
| 62 | pass |
| 63 | |
| 64 | @abstractmethod |
| 65 | def __len__(self) -> int: |
| 66 | """Get number of requests in queue.""" |
| 67 | pass |
| 68 | |
| 69 | @abstractmethod |
| 70 | def __iter__(self) -> Iterator[Request]: |
| 71 | """Iterate over the queue according to the policy.""" |
| 72 | pass |
| 73 | |
| 74 | |
| 75 | class FCFSRequestQueue(deque[Request], RequestQueue): |
| 76 | """A first-come-first-served queue that supports deque operations.""" |
| 77 | |
| 78 | def add_request(self, request: Request) -> None: |
| 79 | """Add a request to the queue according to FCFS policy.""" |
| 80 | self.append(request) |
| 81 | |
| 82 | def pop_request(self) -> Request: |
| 83 | """Pop a request from the queue according to FCFS policy.""" |
| 84 | return self.popleft() |
| 85 | |
| 86 | def peek_request(self) -> Request: |
| 87 | """Peek at the next request in the queue without removing it.""" |
| 88 | if not self: |
| 89 | raise IndexError("peek from an empty queue") |
| 90 | return self[0] |
| 91 | |
| 92 | def prepend_request(self, request: Request) -> None: |
| 93 | """Prepend a request to the front of the queue.""" |
| 94 | self.appendleft(request) |
| 95 | |
| 96 | def prepend_requests(self, requests: Iterable[Request]) -> None: |
| 97 | """Prepend all requests from another queue to the front of this |
| 98 | queue. |
| 99 | |
| 100 | Note: The requests will be prepended in reverse order of their |
| 101 | appearance in the `requests` queue. |
| 102 | """ |
| 103 | self.extendleft(requests) |
| 104 | |
| 105 | def remove_request(self, request: Request) -> None: |
| 106 | """Remove a specific request from the queue.""" |
| 107 | self.remove(request) |
| 108 | |
| 109 | def remove_requests(self, requests: Iterable[Request]) -> None: |
| 110 | """Remove multiple specific requests from the queue.""" |
| 111 | requests_to_remove = set(requests) |
| 112 | filtered_requests = [req for req in self if req not in requests_to_remove] |
| 113 | # deque does not support in-place filtering, so we need to clear |
| 114 | # and extend |
| 115 | self.clear() |
| 116 | self.extend(filtered_requests) |
| 117 | |
| 118 | def __bool__(self) -> bool: |
| 119 | """Check if queue has any requests.""" |
| 120 | return len(self) > 0 |
| 121 | |
| 122 | def __len__(self) -> int: |
| 123 | """Get number of requests in queue.""" |
| 124 | return super().__len__() |
| 125 | |
| 126 | def __iter__(self) -> Iterator[Request]: |
| 127 | """Iterate over the queue according to FCFS policy.""" |
| 128 | return super().__iter__() |
| 129 | |
| 130 | |
| 131 | class PriorityRequestQueue(RequestQueue): |
| 132 | """A priority queue that supports heap operations. |
| 133 | |
| 134 | Respects the ordering defined in the Request class, where |
| 135 | requests with a smaller value of `priority` are processed first. |
| 136 | If multiple requests have the same priority, the one with the earlier |
| 137 | `arrival_time` is processed first. |
| 138 | """ |
| 139 | |
| 140 | def __init__(self) -> None: |
| 141 | self._heap: list[Request] = [] |
| 142 | |
| 143 | def add_request(self, request: Request) -> None: |
| 144 | """Add a request to the queue according to priority policy.""" |
| 145 | heapq.heappush(self._heap, request) |
| 146 | |
| 147 | def pop_request(self) -> Request: |
| 148 | """Pop a request from the queue according to priority policy.""" |
| 149 | if not self._heap: |
| 150 | raise IndexError("pop from empty heap") |
| 151 | return heapq.heappop(self._heap) |
| 152 | |
| 153 | def peek_request(self) -> Request: |
| 154 | """Peek at the next request in the queue without removing it.""" |
| 155 | if not self._heap: |
| 156 | raise IndexError("peek from empty heap") |
| 157 | return self._heap[0] |
| 158 | |
| 159 | def prepend_request(self, request: Request) -> None: |
| 160 | """Add a request to the queue according to priority policy. |
| 161 | |
| 162 | Note: In a priority queue, there is no concept of prepending to the |
| 163 | front. Requests are ordered by (priority, arrival_time).""" |
| 164 | self.add_request(request) |
| 165 | |
| 166 | def prepend_requests(self, requests: Iterable[Request]) -> None: |
| 167 | """Add all requests from another queue according to priority policy. |
| 168 | |
| 169 | Note: In a priority queue, there is no concept of prepending to the |
| 170 | front. Requests are ordered by (priority, arrival_time).""" |
| 171 | for request in requests: |
| 172 | self.add_request(request) |
| 173 | |
| 174 | def remove_request(self, request: Request) -> None: |
| 175 | """Remove a specific request from the queue.""" |
| 176 | self._heap.remove(request) |
| 177 | heapq.heapify(self._heap) |
| 178 | |
| 179 | def remove_requests(self, requests: Iterable[Request]) -> None: |
| 180 | """Remove multiple specific requests from the queue.""" |
| 181 | requests_to_remove = requests if isinstance(requests, set) else set(requests) |
| 182 | self._heap = [r for r in self._heap if r not in requests_to_remove] |
| 183 | heapq.heapify(self._heap) |
| 184 | |
| 185 | def __bool__(self) -> bool: |
| 186 | """Check if queue has any requests.""" |
| 187 | return bool(self._heap) |
| 188 | |
| 189 | def __len__(self) -> int: |
| 190 | """Get number of requests in queue.""" |
| 191 | return len(self._heap) |
| 192 | |
| 193 | def __iter__(self) -> Iterator[Request]: |
| 194 | """Iterate over the queue according to priority policy.""" |
| 195 | heap_copy = self._heap[:] |
| 196 | while heap_copy: |
| 197 | yield heapq.heappop(heap_copy) |
| 198 | |
| 199 | |
| 200 | def create_request_queue(policy: SchedulingPolicy) -> RequestQueue: |
| 201 | """Create request queue based on scheduling policy.""" |
| 202 | if policy == SchedulingPolicy.PRIORITY: |
| 203 | return PriorityRequestQueue() |
| 204 | elif policy == SchedulingPolicy.FCFS: |
| 205 | return FCFSRequestQueue() |
| 206 | else: |
| 207 | raise ValueError(f"Unknown scheduling policy: {policy}") |