4 ms·

Are you sure? Aren't you talking about the average wait time for all tasks combined (sum of wait times) instead of the wait time for any one task. Obviously the

Are you sure? Aren't you talking about the average wait time for all tasks combined (sum of wait times) instead of the wait time for any one task. Obviously the optimal wait time any one task is 0, if you start right away. Intuitively i'd say if you sort the queue by size and always process the shortest task, you may indefinitely stall some long tasks.

isaacg 7y ago
You're right, it's average wait time over all tasks. However, processing the shortest tasks first doesn't delay the long tasks much, if length is reasonably variable, because the short tasks are almost negligible to the long tasks, and the long take don't need to wait on even longer tasks. If long tasks are stalling indefinitely under this policy, then under FCFS the queue length with grow without bound, and that's not really much better.
hinkley 7y ago
Yes, the average wait time, full stop. Now that I'm rereading, I'm not even sure what 'average wait time for one task' was supposed to mean. Averages are aggregate data about multiple samples.
hinkley 7y ago
I think that depends on whether your queue is a fixed data set or a stream of new entries. I learned queuing theory in a class about multimedia, and I came away with a good theoretical understanding but my practical understanding was rubbish. When synchronizing two streams of tasks, the queue is not finite, but the pattern is fixed. For A/V it might be 22 frames per second, best effort, and exactly one second of audio per second. But any queue with even a vague notion of deadlines will only let so many tasks 'cut in line'. At some point the undesirable task gets scheduled, even in the face of a constant stream of other work. Or it gets dropped. From what I understand, in a realtime system a low priority, long task might just be aborted. Because it's never a good time to run it.

isaacg 7y ago

You're right, it's average wait time over all tasks. However, processing the shortest tasks first doesn't delay the long tasks much, if length is reasonably variable, because the short tasks are almost negligible to the long tasks, and the long take don't need to wait on even longer tasks. If long tasks are stalling indefinitely under this policy, then under FCFS the queue length with grow without bound, and that's not really much better.

hinkley 7y ago

Yes, the average wait time, full stop. Now that I'm rereading, I'm not even sure what 'average wait time for one task' was supposed to mean. Averages are aggregate data about multiple samples.

hinkley 7y ago

I think that depends on whether your queue is a fixed data set or a stream of new entries. I learned queuing theory in a class about multimedia, and I came away with a good theoretical understanding but my practical understanding was rubbish. When synchronizing two streams of tasks, the queue is not finite, but the pattern is fixed. For A/V it might be 22 frames per second, best effort, and exactly one second of audio per second. But any queue with even a vague notion of deadlines will only let so many tasks 'cut in line'. At some point the undesirable task gets scheduled, even in the face of a constant stream of other work. Or it gets dropped. From what I understand, in a realtime system a low priority, long task might just be aborted. Because it's never a good time to run it.