23 мая 2019 г.

Waiting time paradox #3: сервера и их очереди


Если происходит что-то странное, значит, где-то рядом автобусная остановка
(Народная мудрость)

(Продолжение серии про парадокс времени ожидания. Персонажи выдуманы, цифры получены из симуляции, формулы выведены специально сделанными людьми. В общем, все не по-настоящему, не пытайтесь повторить)

Представьте себе сервер, на который приходят заявки, и очередь, где заявки могут чуток обождать, пока сервер занят с другими заявками. Не хочется тратить CPU на постоянный опрос очереди busy-loop-ом, поэтому сервер обрабатывает те заявки, которые уже накопились в очереди, а как только заявки в очереди заканчиваются – сервер переключается на какие-то фоновые задачи, а потом на sleep(5). Отоспавшись, сервер возвращается к очереди, и если там что-то накопилось – то все это разгребает, и опять уходит заниматься фоновыми делами + sleep(5), а если ничего не накопилось – так сразу уходит заниматься фоновыми делами и спать. Поддерживает разумный work-life balance:

while( true ){
    task = queue.poll()
    if( task != null ) {
        task.doTheNeedful()
    } else {
        doBackgroundJobs()
        sleep(5)
    }
}
(Полный java-код тут, можно поиграться)

5 мая 2019 г.

Waiting time paradox #2: почему успешный поиск в хэш-таблице дольше не успешного?

…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный

Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.

Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?