Два процесса на двух процессорах - возможно ли, что они завершаются в один и тот же момент? - PullRequest
0 голосов
/ 05 апреля 2011

Это странный вопрос, который беспокоил меня в последнее время. В нашем современном мире многоядерных процессоров и многопоточных операционных систем мы можем запускать многие процессы с истинным аппаратным параллелизмом. Допустим, я создал два экземпляра Программы A в двух отдельных процессах одновременно. Не принимая во внимание помехи на уровне ОС, которые могут изменить время выполнения для одного или обоих процессов, возможно ли, чтобы оба этих процесса завершились в точно в один и тот же момент времени? Существует ли какой-либо конкретный аппаратный / операционный механизм, который может это предотвратить?

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

РЕДАКТИРОВАТЬ: под "помехой на уровне ОС" Я имею в виду такие вещи, как прерывания, различные методы для разрешения конфликта ресурсов, который может использовать ОС, и т. Д.

Ответы [ 4 ]

3 голосов
/ 05 апреля 2011

На самом деле, думать о времени в " космическом смысле " - это хороший способ думать о времени в распределенной системе (включая многоядерные системы).Не все системы (или ядра) разгоняют свои часы с одинаковой скоростью, что затрудняет точное определение того, какие события произошли первыми (по времени настенных часов ).Из-за этой неспособности согласиться, системы имеют тенденцию измерять время с помощью логических часов .Два события происходят одновременно (т. Е. «Точно в одно и то же время»), если они не упорядочены путем обмена данными друг с другом или иным образом координируют их выполнение.

Кроме того, вам необходимо определить, когда именно процесс имеет "вышел «.Думая в Linux, это когда он выводит на экран сообщение о выходе?Когда он вернется из main()?Когда он выполняет системный вызов exit()?Когда его состояние процесса запускается, устанавливается "выход" в ядре?Когда родитель процесса получает SIGCHLD?

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

Вам даже не нужно «точно» одновременно.Иногда вы можете быть достаточно близко, чтобы казалось одновременным.Даже на одном ядре без истинного параллелизма могут появиться два процесса одновременно, если, например, два дочерних процесса вышли до того, как был запланирован следующий родительский процесс.Неважно, кто действительно вышел первым;родитель увидит, что через мгновение, когда он не работал, оба ребенка умерли.

3 голосов
/ 05 апреля 2011

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

Конечно, почему бы и нет?За исключением общей памяти (и других ресурсов, см. Ниже), они работают независимо друг от друга.

Существует ли какой-либо конкретный аппаратный или операционный механизм, который может это предотвратить?

Все, что является конфликтом ресурсов:

  • доступ к памяти
  • доступ к диску
  • доступ к сети
  • явное управление параллелизмом через блокировки / семафоры /мьютексы / и т.д..

Если говорить более конкретно: это отдельные ядра ЦП.Это означает, что они имеют вычислительные схемы, реализованные в отдельных логических схемах.Со страницы википедии :

enter image description here

Тот факт, что каждое ядро ​​может иметь свой собственный кэш памяти, означает, что большая часть вычислений вполне может произойтикак взаимодействие каждого ядра со своим кешем.Если у вас есть это, это просто вопрос вероятности.Это не означает, что алгоритмы занимают недетерминированное количество времени, но их входные данные могут поступать из вероятностного распределения, и количество времени, которое требуется для запуска, вряд ли будет полностью независимым от входных данных, если алгоритм не был тщательно спроектирован, чтобы приниматьстолько же времени

1 голос
/ 05 апреля 2011

Ну, я пойду с Я сомневаюсь в этом :

  • Внутренне любая разумная ОС ведет список запущенных процессов.
  • Поэтому нам представляется разумным определить момент, когда процесс завершается, как момент, когда он удален из этого списка.
  • Мне также кажется весьма маловероятным (но не невозможным), что типичная ОС приложит усилия для создания этого списка таким образом, чтобы два потока могли независимо удалить элемент из этого списка на точно в то же время (процессы не завершаются так часто, а удаление элемента из списка относительно недорого - я не вижу никакой реальной причины, по которой они просто не заблокировали бы весь список).
  • Следовательно, для любых двух завершающих процессов A и B (где A заканчивается до B), всегда будет достаточно большой период времени (в космическом смысле), когда A завершился, а B - нет.

Тем не менее, , конечно, возможно создать такой список, и поэтому в действительности это зависит от ОС.

Также я не очень понимаю смысл этого вопроса, в частности, что вы подразумеваете под

компьютер не может отличить

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

0 голосов
/ 05 апреля 2011

Да, без каких-либо помех планирования ОС они могут завершиться в одно и то же время, если у них нет конфликта ресурсов (общая память, внешний ввод, системные вызовы).Когда у одного из них есть блокировка на ресурсе, он заставит другого остановиться в ожидании освобождения ресурса.

...