время выполнения двух программ, запускаемых отдельно, а затем вместе

Question

Мне недавно задали этот вопрос в одном из интервью, и хотя я хорошо справился с первыми двумя частями [я предполагаю], я немного боролся с третьей. Вот вопрос:

У вас есть две программы для Linux, A и B. При запуске по отдельности A и B каждая занимает одну минуту в системе, которая была только что перезапущена. [то есть: свежая система: вы перезагружаете ее, входите в систему, получаете приглашение оболочки, запускаете программу.]

Что вы можете рассказать о программах, если:

а) когда бегают вместе, они занимают 2 минуты б) когда бегают вместе, они занимают 1 минуту в) когда бегают вместе, они занимают 30 секунд

Я сказал: а) что если они работают вдвое больше времени при совместной работе, они не разделяют взаимное исключение и борются за одни и те же ресурсы, вероятно, не разделяют какие-либо данные или инструкции кэша [и, таким образом, не не помогают друг другу с точки зрения кэша], и каждая программа нуждается в полном использовании указанного ресурса, чтобы ОС не могла их распараллелить.

Что касается б), я сказал, что если они могут работать так же быстро вместе, они, вероятно, разделяют некоторую пространственную / временную локализацию в наличных деньгах и могут быть должным образом распределены по конвейеру таким образом, что пока программа А ожидает что-то, программа B может выполняться между этими этапами, и наоборот - эффективно запускать их оба за 1 минуту.

Для с) я был немного застрял. Оглядываясь назад, я, вероятно, должен был сказать, что, возможно, программы A и B выполняли общую задачу, когда два из них, выполняющихся одновременно, могли выполнить указанное задание быстрее, чем одно, выполняемое в одиночку, например сборщик мусора. Но лучшее, что я смог придумать, это то, что, возможно, они загружались из одного и того же сектора на жестком диске, и это помогло им обоим быстро работать.

Я просто ищу информацию от некоторых умников здесь о вещах, которые я, возможно, пропустил. Позиция была для позиции платформы / системы, которая требует хорошего понимания аппаратного / программного обеспечения и операционных систем, а именно взаимодействия между ними, поэтому [я предполагаю] вопрос был задан.

Я также пытался придумать примеры, которые я мог бы применить к каждой части, чтобы помочь мне показать свои знания в реальных приложениях, но на месте мне не хватало.

Answer 1

Вместе они занимают 2 минуты, чтобы завершить

В этом случае я думаю, что каждая программа полностью связана с процессором и может насыщать 100% процессоров, доступных на машине. Поэтому, когда программы работают вместе, каждая из них работает с половинной скоростью.

Также возможно, что это было бы наблюдаемым поведением, если бы обе программы были способны и желали насытить какой-то другой ресурс, кроме процессора, например, какое-то устройство ввода-вывода. Однако, поскольку на практике обычно производительность устройств ввода-вывода не уменьшается линейно с нагрузкой, прикладываемой к ним, если они перенасыщены, я бы посчитал этот сценарий менее вероятным и пошел бы с привязкой к ЦП как первое предположение.

Вместе они занимают 1 минуту, чтобы завершить

Две программы не оспаривают одни и те же ресурсы, или в системе достаточно ресурсов для удовлетворения потребностей обоих. Поэтому они в конечном итоге не мешают друг другу.

Вместе они занимают полминуты

Программы работают на одном и том же входе, и обе могут сообщать, когда все входы использованы, поэтому каждая из них в итоге выполняет половину работы, которая была бы выполнена, если бы она запускалась одна за половину времени работы. Кроме того, система, очевидно, способна предоставлять вдвое больше ресурсов, чем ограничивают эти программы.

Поскольку в этом случае время выполнения линейно уменьшается с количеством процессов (идеальное масштабирование), представляется более вероятным, что ресурс, ограничивающий программы, является ЦП по тем же причинам, что и в сценарии «2 минуты». Это также хорошо согласуется с предположением об «общем входе», поскольку вряд ли вход будет поступать из одного источника, если бы, например, различные устройства ввода / вывода, обеспечивающие его.

Следовательно, первое предположение в этом случае состоит в том, что каждая программа связана с ЦП и написана так, что она потребляет максимум половину ресурсов ЦП в системе.

Answer 2

Для А, это программы, которые конкурируют за взаимоисключающий ресурс.

Для B, это независимые программы, которые на самом деле не взаимодействуют.

Для C, с которым вы боретесь, кажется, у них обоих одинаковая работа. Например, есть очередь задач, которые нужно выполнить, обе программы способны выполнять задачи, и они знают, какие задачи были выполнены. Так что, если они оба работают одновременно (при условии, что машина многоядерная, но даже не обязательно, все, что важно, это то, что у них нет узкого места в ресурсах), они выполняют работу вдвое.

Answer 3

См. Производительность в многопоточном приложении Java по другой возможной причине, по которой процессы могут работать быстрее, если у вас их больше одного.

Хотя я допускаю, что очередь задач, которые могут выполняться одновременно, являетсягораздо более простая причина объяснить это сокращенное время работы.