ScholarWorks@성균관대학교

초록

In computer systems, fair-share scheduling of resources is essential, and virtual time-based algorithms are widely adopted for their work-conserving nature. These algorithms rely on tracking the minimum virtual time, as they always schedule the entity with the smallest value to ensure fairness. Maintaining this minimum efficiently is crucial for scalable performance, particularly in multi-core systems where contention can be high. Mindicator, a scalable and low-overhead data structure, is well-suited for tracking minimum values and is a natural candidate for monitoring minimum virtual time. However, its use in virtual time management is limited because virtual time grows monotonically and can exceed the 32-bit integer range supported by Mindicator. This leads to incorrect minimum tracking when values overflow, potentially causing fairness violations and even malfunctioning behavior. To overcome these limitations, this paper proposes T-Mindicator (Twin-Mindicator), a scalable approach to virtual time tracking that tolerates integer overflow and supports values with arbitrary bit widths. T-Mindicator uses two Mindicator instances, each managing a 32-bit value, while independently tracking the number of even and odd overflow events. By concatenating the overflow counters with the 32-bit minimum values from each instance, T-Mindicator effectively extends support to 64-bit and larger virtual time representations. Our evaluation demonstrates that T-Mindicator preserves fairness among competing entities and ensures stable workload execution without anomalies when integrated into a state-of-the-art fair I/O scheduler.