Конечно, планировщики это не вредно?Разве у нас нет лучших API?

Question

Мне интересно, какие API доступны, чтобы избежать следующей проблемы.

Возвращаясь к лекциям по операционной системе на моем старом курсе CS, тема была о многопроцессорном планировании и параллельном вводе-выводе.Вот что дал лектор в качестве примера того, что должно произойти:

Два процесса, X и Y, должны кое-что сделать.Есть один процессор / шина / что угодно, и планировщик наивно распределяет временные интервалы между X и Y следующим образом:

• X получает временной интервал 1
• Y получает временной интервал 2
• X получает временной интервал 3
• ...

Это было описано как "справедливое", однако мне это кажется грубо несправедливым .Рассмотрим два случая по этой схеме

• Если X и Y оба будут занимать по 10 секунд каждый, то теперь оба будут занимать 20 секунд.

• Если X требуется 10 секунд, а Y - 100 секунд, то X займет 20 секунд, а Y - 110 секунд.

Если планировщик просто «сделал все X, то все Y»«тогда в первом случае X потребовалось бы 10 секунд, а Y - 20 секунд;во втором случае X будет принимать 10, а y - 110.

Каким образом система, которая никого не делает лучше, а кому-то хуже, может быть хорошей идеей?Единственный аргумент в пользу «справедливой» системы заключается в том, что если бы мы выполнили все Y раньше, чем какой-либо из X, то небольшая работа X была бы отложена из-за большой работы Y, и мы должны держать обе работы «отзывчивыми».

Во втором случае часть меня видит естественный «лучший» способ сказать: «X в 10 раз меньше, поэтому при отсутствии явных предпочтений он должен получить в 10 раз больше временных интервалов, чем Y».(Это немного похоже на предоставление пешеходам права проезда перед машинами на том основании, что они создают меньшую нагрузку на дороги, но я отступаю.) По этой схеме X завершает работу за 11 секунд, а Y - за 110 секунд.Последствия реального мира: мой mp3 загружается и воспроизводится без заметной дополнительной задержки, даже если в фоновом режиме происходит массивная копия файла.

Очевидно, существует целая вселенная доступных стратегий, и я не хочу спорить о пригодностио каком-то конкретном, моя точка зрения такова: все такие стратегии требуют знания размера задания.

Итак, есть ли API-интерфейсы для ОС (Linux илидаже Windows), которые позволяют указывать намеки на объем работы, которую будет выполнять операция?

(Примечание: вы могли бы утверждать, что дисковый ввод-вывод включает это неявно, но while(not_done){read_chunk();} сделает его бессмысленным - видAPI, о котором я думаю, будет указывать мегабайты во время открытия файла, циклы часов во время создания потока или что-то в этом роде.)

Answer 1

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

Answer 2

В распространенных операционных системах вам, как правило, не безразлична задержка выполнения задачи, но вы пытаетесь максимизировать пропускную способность - через 110 секунд будут выполнены X и Y, точка.Конечно, некоторые процессы могут быть интерактивными, и поэтому ОС берет на себя дополнительные издержки переключения контекста между процессами, чтобы поддерживать иллюзию параллельных вычислений.

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

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

Я предлагаю вам прочитатькое-что о RTOS, ранних сроках Планирование первого и однотонного планирования.

Answer 3

Единственный аргумент в пользу "справедливой" системы заключается в том, что если бы мы выполнили все Y до любого из X, то маленькая работа X была бы отложена из-за большой работы Y, и мы должны держать обе работы "отзывчивыми".

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

Итак, существуют ли API-интерфейсы ОС (Linux или даже Windows), которые позволяютуказать намеки на объем работы, которую будет выполнять операция?

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

(Кроме того, с начала 1970-х годов планировщики Unix динамически повышали приоритет процессов, которые не «съедают» свои куски, поэтому интерактивные процессы получают высокую загрузку ЦПприоритет и оставайся отзывчивым без привязки к ЦП, которые держат все в руках. См. ранние статьи Томпсона и Ричи по Unix.)