Лекция 5. Понятия процесса и потока. Ние процессов и потоков. Типы планирования процессора. Тупики. Методы взаимодействия процессов
 Скачать 429.57 Kb.
|
|
долгосрочное планирование; среднесрочное планирование; краткосрочное планирование. Основное отличие между долгосрочным и краткосрочным планированием заключается в частоте запуска. Долгосрочное планирование осуществляется при создании нового процесса и представляет собой решение о добавлении нового процесса к множеству готовых в настоящий момент процессов (в случае освобождения ресурсов памяти). Среднесрочное планирование является частью свопинга и представляет собой решение о добавлении процесса к множеству частично расположенных в основной памяти процессов. Краткосрочное планирование является решением о том, какой из готовых к выполнению процессов будет выполняться следующим. Планирование потоков осуществляется на основе информации, хранящейся в описателях процессов и потоков. При планировании может приниматься во внимание: приоритет потоков время их ожидания в очереди накопленное время выполнения интенсивность обращений к вводу-выводу и другие факторы. В многопоточных операционных системах планирование выполнения потоков осуществляется независимо от того, принадлежат ли они одному или разным процессам. Планирование потоков включает в себя решение двух задач: определение момента времени для системы текущего активного потока; выбор для выполнения потока из очереди готовых потоков. Тупики Тупик (дедлокили клинч) – это ситуация, когда процесс ожидает события, которое никогда не произойдет вследствие занятости необходимого процессу ресурса другим процессом, который также ожидает какого-либо события. Типики приводят к зависаниям системы. Для борьбы с тупиками операционная система должна их обнаруживать и нарушать одно из условий существования тупика или игнорировать тупик. Большинство операционных систем (UNIX, Windows) игнорируют тупики. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе. Системная тупиковая ситуация, или зависание системы, является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками. В общем случае проблема тупиков эффективного решения не имеет. Ресурсами могут быть как устройства, так и данные. Некоторые ресурсы допускают разделение между процессами, то есть являются разделяемыми ресурсами. Например, память, процессор, диски коллективно используются процессами. Другие не допускают разделения, то есть являются выделенными. К взаимоблокировке может привести использование как выделенных, так и разделяемых ресурсов. Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г. 1. Условие взаимоисключения (mutual exclusion). Одновременно использовать ресурс может только один процесс. Процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются. 2. Условие ожидания ресурсов (hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов. 3. Условие неперераспределяемости (no preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса (только процессом, который их удерживает). 4. Условие кругового ожидания (circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи. Для образования тупика необходимым и достаточным является выполнение всех четырех условий. Основные направления борьбы с тупиками: игнорирование проблемы в целом; предотвращение тупиков; обход тупиков; обнаружение тупиков; восстановление после тупиков. При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций. Цель средств обхода тупиков заключается в том, чтобы можно было предусматривать менее жесткие ограничения, чем в случае предотвращения тупиков, и тем самым обеспечить лучшее использование ресурсов. При наличии средств обхода тупиков не требуется такой реализации системы, при которой опасность тупиковых ситуаций даже не возникает. Напротив, методы обхода тупиков учитывают подобную возможность, однако в случае увеличения вероятности конкретной тупиковой ситуации здесь принимаются меры по аккуратному обходу тупика. Методы обнаружения тупиков применяются в системах, которые допускают возможность возникновения тупиковых ситуаций как следствие либо умышленных, либо неумышленных действий программистов. Цель средств обнаружения тупиков — установить сам факт возникновения тупиковой ситуации, причем точно определить те процессы и ресурсы, которые оказались вовлеченными в данную тупиковую ситуацию. После того как все это сделано, данную тупиковую ситуацию в системе можно будет устранить. Методы восстановления после тупиков применяются для устранения тупиковых ситуаций, с тем, чтобы система могла продолжать работать, а процессы, попавшие в тупиковую ситуацию, могли завершиться с освобождением занимаемых ими ресурсов. В большинстве систем восстановление осуществляется путем полного выведения из решения одного или более процессов, попавших в тупиковую ситуацию. Затем выведенные процессы обычно перезапускаются с самого начала, так что почти вся или даже вся работа, проделанная этими процессами, теряется. Существуют различные способы предотвращения тупиков: 1. Алгоритм банкира. Алгоритм банкира для безопасного распределения ресурсов операционной системой (с избеганием тупиков) был предложен Э. Дейкстрой и впервые реализован в операционной системе THE в конце 1960-х гг. Происхождение названия связано с тем, что поведение алгоритма напоминает осторожную стратегию банкира при проведении банковских операций. Принципы алгоритма банкира следующие: каждый процесс должен априорно обозначить свои потребности в ресурсах по максимуму; когда процесс запрашивает ресурс, ему, возможно, придется подождать (выделение ресурсов по запросу не всегда может произойти немедленно); когда процесс получает требуемые ресурсы, он должен их вернуть системе за ограниченный период времени. 2. Предотвращение тупиков за счет нарушения условий их возникновения. Хавендер показал, что возникновение тупика невозможно, если нарушено хотя бы одно из указанных выше четырех необходимых условий. Он предложил следующую стратегию: каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены; если процесс, удерживающий определенные ресурсы, получает отказ в удовлетворении запроса на дополнительные ресурсы, этот процесс должен освободить свои первоначальные ресурсы и при необходимости запросить их снова вместе с дополнительными ресурсами; введение линейной упорядоченности по типам ресурсов для всех процессов. Другими словами, если процессу выделены ресурсы данного типа, в дальнейшем он может запросить только ресурсы более далеких по порядку типов. Каждый из указанных принципов имеет целью нарушить какое-нибудь одно из необходимых условий существования тупика. Для обнаружения тупиков в общем случае необходимо получить граф распределения ресурсов между процессами, и если там есть кольца, то это тупик. Методы взаимодействия процессов Взаимодействие процессов – основа для распараллеленного, эффективного решения задач с помощью группы процессов, координирующих свои действия друг с другом. Независимые и взаимодействующие процессы С точки зрения взаимосвязи, процессы подразделяются на независимые и взаимодействующие. Независимый процесс – процесс, никак не связанный с другими процессами, который не может влиять на исполнение других процессов или испытывать их влияние. Взаимодействующий (совместный) процесс – процесс, который может влиять на исполнение других процессов или испытывать их влияние. Преимущества взаимодействующих процессов очевидны: совместное использование данных - процессы могут работать с общими данными, при условии их синхронизации; ускорение вычислений; модульность - организация взаимодействующих процессов – это метод параллельного решения задачи, декомпозируемой на относительно независимые части, части, каждую из которых решает один из взаимодействующих процессов; удобство. Виды организации взаимосвязи процессов С точки зрения видов взаимосвязи родительского и дочернего процессов, процессы подразделяются на независимые, подчиненные и сопроцессы. Подчиненный процесс – процесс, зависящий от процесса-родителя. Подчиненный процесс уничтожается при уничтожении родительского процесса, как в системах UNIX и операционной систем «Эльбрус». Процесс-родитель перед своим завершением должен ожидать завершения всех своих подчиненных процессов. Независимый процесс – дочерний процесс, выполняемый независимо от процесса-родителя. Типичные примеры: процессы-демоны в UNIX, запускаемые начальным процессом init. Сопроцесс (coprocess, coroutine) – процесс, равноправно взаимодействующий с другими такими же процессами. Коммуникация процессов Рассмотрим возможные механизмы для непосредственной коммуникации процессов и синхронизации их действий. Наиболее распространенный из них - система сообщений. При этом процессы взаимодействуют между собой без обращений к общим переменным. Средства коммуникации между процессами обеспечивают две операции вида: send (message) – отправка сообщения message. Размер сообщения может быть постоянным или переменным; receive (message) – получение сообщения в буфер message. Если процессам P и Q требуется взаимодействовать между собой, им необходимо: установить связь (communication link) друг с другом; обменяться сообщениями вида send/receive. Реализация связи может быть физической (общая память, аппаратная шина) или логической (например, логические свойства). При реализации коммуникационного механизма между процессами необходимо решить следующие вопросы: как устанавливается связь? можно ли установить связь более чем двух процессов? сколько связей может быть установлено между двумя заданными процессами? какова пропускная способность линии связи? является ли длина сообщения по линии связи постоянной или переменной? является ли связь ненаправленной или двунаправленной (дуплексной)? Непосредственная коммуникация процессов При непосредственной коммуникации (direct communication) процессы именуют друг друга явно – по именам или по адресам (указателям), которые указываются в вызовах коммуникационных примитивов, например: send (P, message) – послать сообщение процессу P; receive (Q, message ) – получить сообщение от процесса Q. При данном способе коммуникации свойства линии связи следующие: связь устанавливается автоматически (ее реализуют операционная система или отдельные коммуникационные инструменты); связь ассоциируется только с одной парой взаимодействующих процессов; между каждой парой процессов всегда только одна связь; связь может быть ненаправленной, но она двунаправленная (процесс может получить сообщение от другого явно заданного процесса и принять от него сообщение). Косвенная коммуникация процессов При косвенной коммуникации (indirect communication) сообщения направляются и получаются через почтовые ящики (mailboxes), или порты (ports) – системные структуры, предназначенные для приема, хранения и передачи сообщений. Для определенности будем использовать термин почтовый ящик. Каждый почтовый ящик имеет уникальный идентификатор. Процессы могут взаимодействовать, только если они имеют общий почтовый ящик. Свойства линии связи в этом случае следующие: связь устанавливается, только если процессы имеют общий почтовый ящик; связь одного процесса может быть установлена со многими процессами (которым доступен тот же почтовый ящик); каждая пара процессов может иметь несколько линий связи (так как сообщения могут посылаться через различные почтовые ящики); связь может быть ненаправленной или двунаправленной. При косвенном способе коммуникации процессы используют набор операций вида: создать новый почтовый ящик; отправить (принять) сообщение через почтовый ящик; удалить почтовый ящик. Основные операции коммуникации принимают вид: send (A, message) – послать сообщение в почтовый ящик A; receive (A, message) – получить сообщение из почтового ящика A. В данном случае не используются адреса или имена процессов-корреспондентов, вместо них задаются имена почтовых ящиков. При косвенной связи процессов может оказаться необходимой синхронизация. Дело в том, что передача сообщений может выполняться с блокировкой (синхронно) или без блокировки (асинхронно). Соответственно, основные операции send и receive могут быть с блокировкой или без блокировки. Клиент-серверная взаимосвязь Используются, в частности, следующие ее разновидности, которые мы и рассмотрим: сокеты (sockets); удаленные вызовы процедур (remote procedure calls – RPC); удаленные вызовы методов (remote method invocation – RMI). Сокеты – наиболее распространенный способ связи клиента и сервера в сети. Сокет можно определить как отправную (конечную) точку для коммуникации - endpoint for communication. Сокет создается клиентом для взаимодействия с сервером. Сокет связан с определенным номером порта, через который клиент и сервер обмениваются информацией, используя числовой или последовательный символьный поток. Сервер, со своей стороны, прослушивает порт с заданным номером и создает для этого серверный сокет. Сокет можно представлять как конкатенацию IP-адреса и порта. Удаленный вызов процедуры (RPC) – абстракция вызова процедуры между процессами в сетевых системах. Он основан на следующей идее. В клиентской части создаются заглушка (proxy, stub) – локальная процедура, осуществляющая связь с фактической процедурой, находящейся на сервере. Заглушка в клиентской части находит сервер и выстраивает (marshals) параметры для их передачи на сервер по сети. Проблема здесь в том, что адресация на клиенте и на сервере различная, и передавать адрес в памяти каких-либо данных с одного хоста на другой не имеет смысла. Поэтому приходится использовать особую форму передачи информации в виде последовательного потока байтов. Заглушка в серверной части принимает сообщение, распаковывает параметры, преобразует их к нормальному виду и выполняет процедуру на сервере. Удаленный вызов метода (RMI) – механизм в Java-технологии, аналогичный RPC, но в объектно-ориентированной форме. RMI позволяет Java-приложению на одной машине вызвать метод удаленного объекта. |