Н.В. Вдовикина, А.В. Казунин, И.В. Машечкин, А.Н. Техехин - Системное программное обеспечение - взаимодействие процессов (1114927), страница 3
Текст из файла (страница 3)
Время его обработки ЦП также определяетсяалгоритмами планирования для конкретной ОС, т.е. процесс можетработать, пока он не завершится, а может возникнуть переключениена другой процесс спустя некоторый квант времени или припоявлении готового на выполнение более приоритетного процесса.Процесс также может остановить свое выполнение, если оножидает некоторого события, например, ввода с внешнегоустройства.
Тогда он попадает в очередь процессов, ожидающихввод/вывод, и будет находится там до тех пор, пока ожидаемоесобытие не произойдет. Если процесс больше не ожидает никакогособытия, и он готов к выполнению, он попадает в очередь готовыхпроцессов и ждет, пока ему будет выделено процессорное время.10Алгоритмы планирования очереди готовых процессов, как впрочеми всех других очередей, также зависят от конкретной операционнойсистемы и во многом определяют ее тип, о чем будет подробнеерассказано ниже.Описанная схема для различных ОС может отличаться какотсутствием некоторых состояний, так и присутствием некоторыхдополнительных.Еще раз подчеркнем, что для любой многозадачнойоперационнойсистемысуществуетпроблемауправленияразличными очередями и временем центрального процессора.Операционная система должна обладать четкими критериями дляопределения того, какому готовому к выполнению процессу и когдапредоставить ресурс процессора, какой процесс взять из очереди икакой поставить.
Некоторыезадачи планирования решаютсяпрограммными средствами, а некоторые аппаратно. Существуетмножество различных алгоритмов планирования, преследующихразличные цели и обеспечивающих различное качествомультипрограммирования1.1Отметим, что детальное рассмотрение многих конкретных алгоритмов планированиявыходит за рамки данного пособия.113 Синхронизация параллельных процессов.В однопроцессорных системах имеет место так называемыйпсевдопараллелизм – хотя в каждый конкретный момент временипроцессор занят обработкой одной конкретной задачи, благодаряпостоянному переключению с исполнения одной задачи на другую,достигается иллюзия параллельного исполнения нескольких задач.Во многопроцессорных системах задача максимально эффективногоиспользования каждого конкретного процессора также решаетсяпутем переключения между процессами, однако тут, наряду спсевдопараллелизмом,имеетместоидействительныйпараллелизм, когда на разных процессорах в один и тот же моментвремени исполняются разные процессы.Процессы, выполнение которых хотя бы частичноперекрывается по времени, называются параллельными.
Они могутбыть независимыми и взаимодействующими. Независимыепроцессы – процессы, использующие независимое множестворесурсов; на результат работы такого процесса не должна влиятьработадругогонезависимогопроцесса.Наоборот–взаимодействующие процессы совместно используют ресурсы ивыполнение одного процесса может оказывать влияние на результатдругого. Совместное использование ресурса двумя процессами, т.е.когда каждый из процессов полностью владеет ресурсом некотороевремя, называют разделением ресурса.
Разделению подлежат какаппаратные, так программные ресурсы. Разделяемые ресурсы,которые должны быть доступны в текущий момент времени толькоодному процессу – это так называемые критические ресурсы.Таковыми ресурсами могут быть как внешнее устройство, так инекая переменная, значение которой может изменяться разнымипроцессами.Процессы могут быть связаны некоторыми соотношениями(например, когда один процесс является прямым потомком другого),а могут быть не связанными друг с другом. Кроме того, процессымогут выполняться в разных узлах сети.
Эти обстоятельства влияютна способ их взаимодействия, а именно – на возможность совместноиспользовать ресурсы, обмениваться информацией, оповещать другдруга о наступлении некоторых событий, а также определяютвозможность одного процесса влиять на выполнение другого.Таким образом, необходимозадачи:12уметь решать две важнейшие1. Распределение ресурсов между процессами.2.
Организациязащитыресурсов,выделенныхопределенному процессу, от неконтролируемого доступасо стороны других процессов.Важнейшим требованием мультипрограммирования с точкизрения распределения ресурсов является следующее: результатвыполнения процессов не должен зависеть от порядка переключениявыполнения между процессами, т.е.
от соотношения скоростивыполнения данного процесса со скоростями выполнения другихпроцессов.В качестве примера ситуации, когда это правило нарушается,рассмотрим следующую. Пусть имеется некоторая простая функция,которая считывает символ, введенный с клавиатуры, и выводит егона экран:void echo(){char in;input(in);output(in)}В данном примере мы используем некоторые условныефункции input() и output(), так как в данный момент для насневажно, как конкретно реализован ввод/вывод в данной системе.Поскольку такой кусок кода будет использоваться практически влюбой программе, его удобно сделать разделяемым, когда ОСзагружает в некоторую область памяти, доступную всем процессам,одну-единственную копию данной программы, и все процессыиспользуют эту копию совместно.
Заметим, что в этом случаепеременная in является разделяемой. Представим теперь ситуацию,изображенную на Рис. 2:XПроцесс Аinput(in);Процесс ВYinput(in);output(in);output(in);YРис. 2 Конкуренция процессов за ресурс.13Y1. Процесс А вызывает функцию echo(), однако в тотмомент, когда входной символ был считан впеременную in, но до того, как он был выведен наэкран, выполнение процесса прерывается и навыполнение загружается процесс В.2.
Процесс В тоже вызывает функцию echo(). Послевыполнения функции echo()переменная inсодержит уж новое значение, считанное склавиатуры.3. Процесс А возобновляет свою работу в той точке, вкоторой он был прерван, и выводит на экран символ,находящийся в переменной in.В рассмотренном случае символ, считанный процессом А, былпотерян, а символ, считанный процессом В, был выведен дважды.Результат выполнения процессов здесь зависит от того, в какоймомент осуществляется переключение процессов, и от того, какойконкретно процесс будет выбран для выполнения следующим.Такие ситуации называются гонками (в англоязычной литературе race conditions) между процессами, а процессы – конкурирующими.Единственный способ избежать гонок при использованииразделяемых ресурсов – контролировать доступ к любымразделяемым ресурсам в системе.
При этом необходимоорганизовать взаимное исключение – т.е. такой способ работы сразделяемым ресурсом, при котором постулируется, что в тотмомент, когда один из процессов работает с разделяемым ресурсом,все остальные процессы не могут иметь к нему доступ.Проблему организации взаимного исключения можносформулировать в более общем виде. Часть программы (фактическинабор операций), в которой осуществляется работа с критическимресурсом, называется критической секцией, или критическиминтервалом.
Задача взаимного исключения в этом случае сводитсяк тому, чтобы не допускать ситуации, когда два процессаодновременно находятся в критических секциях, связанных с одними тем же ресурсом.Заметим, что вопрос организации взаимного исключенияактуален не только для взаимосвязанных процессов, совместноиспользующих определенные ресурсы для обмена информацией.Выше отмечалось, что возможна ситуация, когда процессы, неподозревающие о существовании друг друга, используютглобальные ресурсы системы, такие как, например, устройстваввода/вывода. В с этом случае имеет место конкуренция за ресурсы,14доступ к которым также должен быть организован по принципувзаимного исключения.Важно отметить, что при организации взаимного исключениямогут возникнуть две неприятные проблемы:1. Возникновение так называемых тупиков (deadlocks).Рассмотрим следующую ситуацию (см.
Рис. 3): имеютсяпроцессы А и В, каждому из которых в некоторый моменттребуется иметь доступ к двум ресурсам R1 и R2. ПроцессА получил доступ к ресурсу R1, и следовательно, никакойдругой процесс не может иметь к нему доступ, покапроцесс А не закончит с ним работать. Одновременнопроцесс В завладел ресурсом R2. В этой ситуации каждыйиз процессов ожидает освобождения недостающегоресурса, но оба ресурса никогда не будут освобождены, ипроцессы никогда не смогут выполнить необходимыедействия.Процесс АПроцесс ВR1R2Рис. 3 Возникновение тупиковой ситуации.2.
Ситуация блокирования (дискриминации) одного изпроцессов, когда один из процессов будет бесконечнонаходиться в ожидании доступа к разделяемому ресурсу, вто время как каждый раз при его освобождении доступ кнему получает какой-то другой процесс.Таким образом, любые средства организации взаимногоисключения должны обеспечивать разрешение этих двух проблем.Помимо этого, к организации взаимного исключения выдвигаютсяследующие требования:1.