Второе издание
 Скачать 3.09 Mb.
|
|
60 Глава 3 Задание завершено настолько, насколько остается возможность передать необхо- димую информацию родительскому процессу. Удаление дескриптора процесса После возврата из функции do_exit () дескриптор завершенного процесса все еще существует в системе, но процесс находится в состоянии TASK_ZOMBIE и не мо- жет выполняться. Как уже рассказывалось выше, это позволяет системе получить информацию о порожденном процессе после его завершения. Следовательно, завер- шение процесса и удаление его дескриптора происходят в разные моменты времени. После того как родительский процесс получил информацию о завершенном порож- денном процессе, структура task_struct порожденного процесса освобождается. Семейство функций wait () реализовано через единственный (и достаточно сложный) системный вызов wait4 (). Стандартное поведение этой функции — при- остановить выполнение вызывающей задачи до тех пор, пока один из ее порожден- ных процессов не завершится. При этом возвращается идентификатор PID завершен- ного порожденного процесса. В дополнение к этому, в данную функцию передается указатель на область памяти, которая после возврата из функции будет содержать код завершения завершившегося порожденного процесса. Когда приходит время окончательно освободить дескриптор процесса, вызывает- ся функция release_task (), которая выполняет указанные ниже операции. • Вызывается функция free_uid () для декремента счетчика ссылок на инфор- мацию о пользователе процесса. В системе Linux поддерживается кэш с инфор- мацией о каждом пользователе, в частности сколько процессов и открытых файлов имеет пользователь. Если счетчик ссылок достигает значения нуль, то пользователь больше не имеет запущенных процессов и открытых файлов, в результате кэш уничтожается. • Вызывается функция unhash_process () для удаления процесса из хеш-табли- цы идентификаторов процессов pidhash и удаления задачи из списка задач. • Если задача была в состоянии трассировки (ptrace), то родительским для нее снова назначается первоначальный родительский процесс и задача удаляется из списка задач, которые находятся в состоянии трассировки (pirate) данным процессом. • В конце концов вызывается функция put_task_struct () для освобождения страниц памяти, содержащих стек ядра процесса и структуру thread_infо, a также освобождается слябовый кэш, содержащий структуру task_struct. На данном этапе дескриптор процесса, а также все ресурсы, которые принадле- жали только этому процессу, освобождены. Дилемма "беспризорного" процесса Если родительский процесс завершается до того, как завершаются вес его потом- ки, то должен существовать какой-нибудь механизм назначения нового родительского процесса для порожденных, иначе процессы, у которых нет родительского, навсегда останутся в состоянии зомби, что будет зря расходовать системную память. Решение этой проблемы было указано выше: новым родительским процессом становится или Управление процессами 61 какой-либо один поток из группы потоков завершившегося родительского процес са, или процесс i n i t . При выполнении функции d o _ e x i t () вызывается функция n o t i f y _ p a r e n t (), которая в свою очередь вызывает f o r g e t _ o r i g i n a l p a r e n t () для осуществления переназначения родительского процесса (reparent), как показано ниже. struct task_struct *р, *reaper = father; struct list_head *list; if (father->exit_signal != -1) reaper = prev_thread(reaper); else reaper = child_reaper; if (reaper == father) reaper = child_reaper; Этот программный код присваивает переменной r e a p e r указатель на другое зада ние в группе потоков данного процесса. Если в этой группе потоков нет другого за- дания, то переменной r e a p e r присваивается значение переменной c h i l d _ r e a p e r , которая содержит указатель на процесс i n i t . Теперь, когда найден подходящий ро- дительский процесс, нужно найти все порожденные процессы и установить для них полученное значение родительского процесса, как показано ниже. list_for_each(list, &father->children) { р = list_entry(list, struct task_struct, sibling); reparent_thread(p, reaper, child_reaper); } list_for_each (list, sfather->ptrace__children) { p = list_entry(list, struct task:_struct, ptrace_list); reparent_thread(p, reaper, child_reaper); } В этом программном коде организован цикл по двум спискам: по списку порож- денных процессов child list и по списку порожденных процессов, находящихся в со- стоянии трассировки другими процессами ptraced child list. Основная причина, по которой используется именно два списка, достаточно интересна (эта новая особен- ность появилась в ядрах серии 2.6). Когда задача находится в состоянии ptrace, для нее временно назначается родительским тот процесс, который осуществляет от- ладку (debugging). Когда завершается истинный родительский процесс для такого задания, то для такой дочерней задачи также нужно осуществить переназначение родительского процесса. В ядрах более ранних версий это приводило к необходимо- сти организации цикла по всем заданиям системы для поиска порожденных процессов. Решение проблемы, как было указано выше, — это поддержка отдельного списка для порожденных процессов, которые находятся в состоянии трассировки, что уменыша- ет число операций поиска: происходит переход от поиска порожденных процессов по всему списку задач к поиску только по двум спискам с достаточно малым числом элементов. Когда для процессов переназначение родительского процесса прошло успешно, больше нет риска, что какой-либо процесс навсегда останется в состоянии зомби. 62 Глава 3 Процесс I n i t периодически вызывает функцию wait () для всех своих порожден- ных процессов и, соответственно, удаляет все зомби-процессы, назначенные ему. Резюме В этой главе рассмотрена важная абстракция операционной системы — процесс. Здесь описаны общие свойства процессов, их назначение, а также представлено сравнение процессов и потоков. Кроме того, описывается, как операционная си- стема Linux хранит и представляет информацию, которая относится к процес- сам (структуры t a s k _ s t r u c t и thread_infо), как создаются процессы (вызовы clone () и fork ()), каким образом новые исполняемые образы загружаются в адрес- ное пространство (семейство вызовов exec ()), иерархия процессов, каким образом родительский процесс собирает информацию о своих потомках (семейство функций wait ()) и как в конце концов процесс завершается (непроизвольно или с помощью вызова exit ()). Процесс — это фундаментальная и ключевая абстракция, которая является осно- вой всех современных операционных систем и, в конце концов, причиной, по кото- рой вообще существуют операционные системы (чтобы выполнять программы). В следующей главе рассказывается о планировании выполнения процессов — из- ящной и интересной функции ядра, благодаря которой ядро принимает решение, какие процессы должны выполняться, в какое время и в каком- порядке. Управление процессами 63 Планирование выполнения процессов В предыдущей главе были рассмотрены процессы— абстракция операционной системы, связанная с активным программным кодом. В этой главе представлен планировщик процессов — код, который позволяет процессам выполняться. Планировщик (scheduler) — это компонент ядра, который выбирает из всех про- цессов системы тот, который должен выполняться следующим. Таким образом, пла- нировщик (или, как еще его называют, планировщик выполнения процессов) можно рассматривать как программный код, распределяющий конечные ресурсы процес- сорного времени между теми процессами операционной системы, которые могут выполняться. Планировщик является основой многозадачных (multitasking) операцион- ных систем, таких как ОС Linux. Принимая решение о том, какой процесс должен выполняться следующим, планировщик несет ответственность за наилучшее исполь- зование ресурсов системы и создает впечатление того, что несколько процессов вы- полняются одновременно. Идея, лежащая в основе планирования выполнения процессов, достаточно про- ста. При наличии готовых к выполнению процессов, для того чтобы лучше исполь- зовать процессорное время, необходимо, чтобы всегда выполнялся какой-нибудь процесс. Если в системе процессов больше, чем процессоров, то некоторые процес- сы будут выполняться не во все моменты времени. Эти процессы готовы к выполне- нию (runnable). Исходя из информации о наборе готовых к выполнению процессов, выбор того процесса, который должен выполняться в следующий момент времени, и есть то фундаментальное решение, которое принимает планировщик. Многозадачные операционные системы— это те, которые могут выполнять по- переменно или одновременно несколько процессов. На однопроцессорной машине такие системы создает иллюзию того, что несколько процессов выполняются одно- временно. На многопроцессорной машине они позволяют процессам действительно выполняться параллельно на нескольких процессорах. На машинах любого типа эти системы позволяют процессам выполняться в фоновом режиме и не занимать про- цессорное время, если нет соответствующей работы. Такие задания, хотя и находят- ся в памяти, но не готовы к выполнению. Вместо этого данные процессы используют ядро, чтобы блокироваться до тех пор, пока не произойдет некоторое событие (ввод с клавиатуры, приход данных по сети, наступление некоторого момента времени в будущем и т.д.). Следовательно, ОС Linux может содержать 100 процессов в памяти, но только один из них будет в исполняемом состоянии. Многозадачные (multitasking) операционные системы бывают двух видов: систе- мы с кооперативной (cooperative) многозадачностью и системы с вытесняющей (preemptive, преемптивной) многозадачностью. Операционная система Linux, так же как и большин- ство вариантов ОС Unix и других современных операционных систем, обеспечивает вытесняющую многозадачность. В системе с вытесняющей многозадачностью реше- ние о том, когда один процесс должен прекратить выполнение, а другой возобно- вить его, принимает планировщик. Событие, заключающееся в принудительном за- мораживании выполняющегося процесса, называется вытеснением (preemption) этого процесса. Период времени, в течение которого процесс выполняется перед тем, как будет вытеснен, известен заранее. Этот период называется квантом времени (timesiice) процесса. В действительности квант времени соответствует той части процессорно- го времени, которая выделяется процессу. С помощью управления величинами кван- тов времени процессов планировщик принимает также и глобальное решение о пла- нировании работы всей системы. При этом, кроме всего прочего, предотвращается возможность монопольного использования ресурсов всей системы одним процессом. Как будет показано далее, величины квантов времени в операционной системе Linux рассчитываются динамически, что позволяет получить некоторые интересные пре- имущества. В противоположность рассмотренному выше типу многозадачности, в системах с кооперативной многозадачностью процесс продолжает выполняться до тех пор, пока он добровольно не примет решение о прекращении выполнения. Событие, связанное с произвольным замораживанием выполняющегося процесса, называется передачей управления (yielding). У такого подхода очень много недостатков: планировщик не мо- жет принимать глобальные решения относительно того, сколько процессы должны выполняться; процесс может монополизировать процессор на большее время, чем это необходимо пользователю; "зависший" процесс, который никогда не передает управление системе, потенциально может привести к неработоспособности систе- мы. К счастью, большинство операционных систем, разработанных за последнее де- сятилетие, предоставляют режим вытесняющей моногозадачности. Наиболее извест- ным исключением является операционная система Mac OS версии 9 и более ранних версий. Конечно, операционная система Unix имеет вытесняющую многозадачность с момента своего создания. При разработке ядер ОС Linux серии 2.5, планировщик ядра был полностью реконструирован. Новый тип планировщика часто называется 0(1)-плаиировщиком (0(1) scheduler) в связи с соответствующим масштабированием времени выполнения алгоритма планирования 1 . Этот планировщик позволяет преодолеть недостатки предыдущих версий планировщика ядра Linux и обеспечить расширенную функцио- нальность, а также более высокие характеристики производительности. В этой главе будут рассмотрены основы работы планировщиков, как эти основы использованы в О(1)-планировщике, а также цели создания 0(1)-планировшика, его устройство, прак- тическая реализация, алгоритмы работы и соответствующие системные вызовы. 1 Обозначение О(1) — это пример обозначения "большого О". Практически, эта запись означает, что планировщик может выполнить все свои действии за постоянное время, независимо от объ- ема входных данных. Полное объяснение того, что такое обозначение "большого О", приведено в приложении В, "Сложность алгоритмов". 66 Глава 4 Стратегия планирования Стратегия (policy) планирования— это характеристики поведения планировщи- ка, которые определяют, что и когда должно выполняться. Стратегия планирования определяет глобальный характер поведения системы и отвечает за оптимальное ис- пользование процессорного времени. Таким образом, это понятие очень важное. Процессы, ограниченные скоростью ввода-вывода и скоростью процессора Процессы можно классифицировать как те, которые ограничены скоростью ввода-вы- вода (I/0-bound), и те, которые ограничены скоростью процессора (processor-bound). К пер- вому типу относятся процессы, которые большую часть своего времени выполнения тратят на отправку запросов на ввод-вывод информации и на ожидание ответов на эти запросы. Следовательно, такие процессы часто готовы к выполнению, но могут выполняться только в течение короткого периода времени, так как в конце концов они блокируются в ожидании выполнения ввода-вывода (имеются в виду не только дисковые операции ввода-вывода, но и любой другой тип ввода-вывода информации, как, например, работа с клавиатурой). Процессы, ограниченные скоростью процессора, наоборот, большую часть вре- мени исполняют программный код. Такие процессы обычно выполняются до того момента, пока они не будут вытеснены, так как эти процессы не блокируются в ожи- дании на запросы ввода-вывода. Поскольку такие процессы не влияют на скорость ввода-вывода, то для обеспечения нормальной скорости реакции системы не требу- ется, чтобы они выполнялись часто. Стратегия планирования процессов, ограни- ченных скоростью процессора, поэтому предполагает, что такие процессы должны выполняться реже, но более продолжительный период времени. Конечно, оба эти класса процессов взаимно не исключают друг друга. Пример процесса, ограниченно- го скоростью процессора, — это выполнение бесконечного цикла. Указанные классификации не являются взаимно исключающими. Процессы мо- гут сочетать в себе оба типа поведения: сервер системы X Windows — это процесс, который одновременно интенсивно загружает процессор и интенсивно выполняет операции ввода-вывода. Некоторые процессы могут быть ограничены скоростью ввода-вывода, но время от времени начинают выполнять интенсивную процессор- ную работу. Хороший пример — текстовый процессор, который обычно ожидает на- жатия клавиш, но время от времени может сильно загружать процессор, выполняя проверку орфографии. Стратегия планирования операционной системы должна стремиться к удо- влетворению двух несовместных условий: обеспечение высокой скорости реакции процессов (малого времени задержки, low latency) и высокой производительности (throughput). Для удовлетворения этим требованиям часто в планировщиках при- меняются сложные алгоритмы определения наиболее подходящего для выполнения процесса, которые дополнительно гарантируют, что все процессы, имеющие более низкий приоритет, также будут выполняться. В Unix-подобных операционных си- стемах стратегия планирования направлена на то, чтобы процессы, ограниченные скоростью ввода-вывода, имели больший приоритет. Использование более высокого приоритета для процессов, ограниченных скоростью ввода-вывода, приводит к уве- Ппэнировэние выполнения процессов 67 личению скорости реакции процессов, так как интерактивные программы обычно ограничиваются скоростью ввода-вывода. В операционной системе Linux для обе- спечения хорошей скорости реакции интерактивных программ применяется опти- мизация по времени оклика (обеспечение малого времени задержки), т.е. процессы, ограниченные скоростью ввода-вывода, имеют более высокий приоритет. Как будет видно далее, это реализуется таким образом, чтобы не пренебрегать и процессами, ограниченными скоростью процессора. Приоритет процесса Наиболее широко распространенным типом алгоритмов планирования является планирование с управлением по приоритетам (priority-based). Идея состоит в том, что- бы расположить процессы по порядку в соответствии с их важностью и необходи- мостью использования процессорного времени. Процессы с более высоким при- оритетом будут выполняться раньше тех, которые имеют более низкий приоритет, в то время как процессы с одинаковым приоритетом планируются на выполнение циклически (по кругу, round-robin), т.е. периодически один за другим. В некоторых операционных системах, включая Linux, процессы с более высоким приоритетом получают также и более длительный квант времени. Процесс, который готов к вы- полнению, у которого еще не закончился квант времени и который имеет наиболь- ший приоритет, будет выполняться всегда. Как операционная система, так и пользо- ватель могут устанавливать значение приоритета процесса и таким образом влиять на работу планировщика системы. В операционной системе Linux используется планировщик с динамическим управ- лением по приоритетам (dynamic priority-based), который основан на такой же идее. Основной принцип состоит в том, что вначале устанавливается некоторое началь- ное значение приоритета, а затем планировщик может динамически уменьшать или увеличивать это значение приоритета для выполнения своих задач. Например, ясно, что процесс, который тратит много времени на выполнение операций ввода-вывода, ограничен скоростью ввода-вывода. В операционной системе Linux такие процессы получают более высокое значение динамического приоритета. С другой стороны, процесс, который постоянно полностью использует свое значение кванта време- ни, — это процесс, ограниченный скоростью процессора. Такие процессы получают меньшее значение динамического приоритета. В ядре Linux используется два различных диапазона приоритетов. Первый — это параметр nice, который может принимать значения в диапазоне от -20 до 19, по умолчанию значение этого параметра равно 0. Большее значение параметра nice со- ответствует меньшему значению приоритета — необходимо быть более тактичным к другим процессам системы (пicе— англ. тактичный, хороший). Процессы с меньшим значением параметра nice (большим значением приоритета) выполняются раньше процессов с большим значением niie (меньшим приоритетом). Значение параметра nice позволяет также определить, насколько продолжительный квант времени полу- чит процесс. Процесс со значением параметра nice равным -20 получит квант вре- мени самой большой длительности, в то время как процесс со значением параметра nice равным 19 получит наименьшее значение кванта времени. Использование пара- метра nice — это стандартный способ указания приоритетов процессов для всех Unix- подобных операционных систем. 68 Глава 4 Второй диапазон значений приоритетов— это приоритеты реального времени (real-time priority), которые будут рассмотрены ниже. По умолчанию диапазон зна- чений этого параметра лежит от 0 до 99. Все процессы реального времени имеют более высокий приоритет по сравнению с обычными процессами. В операционной системе Linux приоритеты реального времени реализованы в соответствии со стан- дартом POSIX. В большинстве современных Unix-систем они реализованы по анало- гичной схеме. |