AI 요약
현대의 클라우드 컴퓨팅 환경은 하드웨어 고장, 점검 주기, 우선순위 작업의 자원 점유 등으로 인해 가용 자원이 실시간으로 변동합니다. 구글 리서치는 이러한 동적인 환경에서 중단 시 모든 진척도가 유실되는 비선점형(non-preemptive) 작업들을 효율적으로 스케줄링하기 위한 연구를 수행했습니다. SPAA 2025에서 발표된 이 연구는 가변적 용량 환경에서도 처리량을 극대화하는 최초의 상수 비율 근사 알고리즘을 제시하여 더 견고한 스케줄러 구축의 이론적 토대를 마련했습니다.
핵심 인사이트
- 클라우드 자원을 정적인 상태가 아닌 시간 가변적인(time-varying) 동적 자원으로 모델링하여 실제 인프라 환경의 복잡성을 반영했습니다.
- 중단 시 복구가 불가능한 비선점형 작업의 특성을 고려해, 작업 시작 시점의 리스크와 대기 기회비용 사이의 최적 균형을 찾는 알고리즘을 제안했습니다.
- 문제 규모에 관계없이 최적해와 일정한 성능 격차를 유지하는 '상수 비율 근사(constant-factor approximation)'를 달성하여 알고리즘의 실효성을 입증했습니다.
주요 디테일
- 자원 변동의 주요 원인에는 하드웨어 장애 및 유지보수뿐만 아니라, 고우선순위 작업이 필요에 따라 자원을 즉시 점유하는 계층형 스케줄링 시스템의 특성이 포함됩니다.
- 비선점형 작업은 처리 도중 용량이 부족해지면 처음부터 다시 시작해야 하므로, 스케줄러는 안전한 실행 창(window)을 확보하는 결정을 내려야 합니다.
- 연구팀은 작업의 총 가중치나 성공적인 작업 수를 최대화하는 여러 변리적 상황에 대해 각각의 최적화 알고리즘을 설계했습니다.
- 본 연구는 "Non-preemptive Throughput Maximization under Time-varying Capacity"라는 제목으로 SPAA 2025 학술대회에서 발표되었습니다.