Глава 3 управление задачами и памятью

ГЛАВА 3 УПРАВЛЕНИЕ ЗАДАЧАМИ И ПАМЯТЬЮ

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

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

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

3.1 Подсистема управления
процессами и потоками

Подсистема управления процессами и потоками (или система управления задачами) обеспечивает их прохождение через компьютер. В зависимости от состояния процесса ему необходимо выделить тот или иной ресурс. Например, новый процесс нужно разместить в памяти, выделив ему адресное пространство; включить в список задач, конкурирующих за процессорное время.

Операционная система выполняет следующие основные функции, связанные с управлением задачами:

§ создание и удаление задач;

§ планирование и диспетчеризация задач;

§ синхронизация задач, обеспечение их средствами коммуникации.

Хотя потоки возникают и выполняются асинхронно, но при одновременном выполнении в системе нескольких задач у них может возникнуть необходимость во взаимодействии, например, при обмене данными. Поэтому одной из важных функций подсистемы управления процессами и потоками является синхронизация потоков.

Подсистема управления процессами и потоками имеет возможность выполнять над процессами следующие операции:

§ создание (порождение)/уничтожение процесса;

§ приостановка/возобновление процесса;

§ блокирование/пробуждение процесса;

§ запуск процесса;

§ изменение приоритета процесса.

Подсистема управления процессами и потоками ответственна за обеспечение процессов необходимыми ресурсами. ОС поддерживает в памяти специальные информационные структуры, в которые записывает, какие ресурсы выделены каждому процессу. Ресурс может назначаться процессу в единоличное пользование или в совместное пользование с другими процессами. Некоторые из ресурсов выделяются процессу при его создании, а некоторые – динамически по запросам во время выполнения. Ресурсы могут быть приписаны процессу на все время его жизни или только на определенный период. При выполнении этих функций подсистема управления процессами взаимодействует с другими подсистемами ОС, ответственными за управление ресурсами, такими, как подсистема управления памятью, подсистема ввода-вывода, файловая система.

Организация параллельных взаимодействующих процессов

Взаимодействие процессов

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

Два параллельных процесса могут быть независимыми или взаимодействующими.

Независимыми являются процессы, множества переменных которых не пересекаются. Под переменными в этом случае понимают файлы данных, а также области оперативной памяти, сопоставленные определенным в программе переменным. Независимые процессы не влияют на результаты работы друг друга, т.к. не могут изменить значение переменных другого независимого процесса. Они могут только являться причиной задержек исполнения других процессов, т.к. вынуждены разделять ресурсы системы.

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

Взаимодействовать могут либо конкурирующие процессы, либо совместно выполняющие общую работу. Конкурирующие процессы на первый взгляд действуют относительно независимо, но имеют доступ к общим переменным. Процессы, работа которых построена на обмене данными (результат вычислений одного процесса в явном виде передается другому), называют сотрудничающими.

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

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

Взаимодействие сотрудничающих потоков удобно рассматривать в схеме "производитель–потребитель": Подробное описание этой схемы приведено в методических указаниях к лабораторным работам (лаб. работа № 4). Поток-получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился за данными раньше, то он должен быть приостановлен до момента поступления данных.

При отсутствии синхронизации возможны следующие проблемы:

§ Возникновение гонок. Гонками называется такая ситуация, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей потоков.

§ Взаимные блокировки, или тупики (дедлоки, клинчи – разные термины для обозначения одного события). Тупик – это состояние, когда несколько процессов ждут событий, которые могут быть вызваны только одним из этих процессов. Так как все процессы находятся в состоянии ожидания, то эти события не произойдут никогда, следовательно, без вмешательства системы ожидание будет бесконечным.

Например, процесс P1 занимает ресурс X и для дальнейшей работы нуждается в ресурсе Y, а процесс P2 занимает ресурс Y и для дальнейшей работы нуждается в ресурсе X. Возникает ситуация тупика (взаимной блокировки), поскольку ни один из процессов не может завершить работу из-за нехватки ресурса, который, в свою очередь, никогда не освободится.

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

Механизмы синхронизации различаются в зависимости от того, относятся они к потокам одного или разных процессов. Для синхронизации потоков одного процесса можно использовать глобальные блокирующие переменные, которые позволяют контролировать работу потоков в критической секции (мониторы, семафоры). Для потоков разных процессов ОС использует системные семафоры, события, сигналы, таймеры и пр. В распределенных системах, состоящих из нескольких процессоров, синхронизация может быть реализована только посредством передачи сообщений. Рассмотрим несколько более подробно некоторые названные средства синхронизации и связанные с ними понятия.

Семафоры и их применение

Понятия, относящиеся к проблеме взаимоисключения, Дейкстра обобщил в своей концепции семафоров. Семафор – это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: "закрытия" и "открытия", названных соответственно P- и V- операциями. Значение семафора можно опрашивать и менять только при помощи примитивов P и V и операции инициализации. Семафоры могут быть двоичными (принимать значения только 0 или 1) или считающими (принимать целые неотрицательные значения). Может использоваться вариант реализации считающего семафора и с отрицательными значениями. Операции P и V неделимы в своем выполнении и взаимно исключают друг друга. Примитивы P и V значительно упростили синхронизацию процессов.

Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время. При отказе доступа к критическому ресурсу используется режим "пассивного ожидания". Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов, которые реализуются супервизором операционной системы. Находясь в списке заблокированных, процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо этого процессор занимается полезной работой, что повышает эффективность работы системы.

Пусть S – семафор. Операция V над семафором S записывается как V(S) и увеличивает переменную S на единицу одним неделимым действием, т.е. выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время операции V(S). Операция P над семафором S записывается как P(S) и уменьшает переменную S на единицу. Если было S=0, то уменьшение S сделает его отрицательным и процесс, вызвавший P -операцию, ждёт, пока значение S не увеличится. Проверка и уменьшение значения S также являются одним неделимым действием.

Для работы с семафорными переменными необходимо ещё иметь операцию инициализации самого семафора. Обычно эту операцию называют InitSem и она, как правило, имеет два параметра – имя семафорной переменной и её начальное значение. Обращение к ней тогда будет иметь, например, следующий вид: InitSem(S,1).

Рассмотрим вариант реализации семафорных примитивов:

P(S): S:=S-1;

If S<0 Then {остановить процесс и поместить его в очередь ожидания к семафору S}

V(S): If S<0 Then {поместить один из ожидающих процессов очереди семафора S в очередь готовности};

S:=S+1;

Если несколько процессов одновременно запрашивают P- или V- операции над одним и тем же семафором, то эти операции будут выполняться последовательно в произвольном порядке. Аналогично, если несколько процессов ожидают выполнения P- операции и изменяемый семафор становится положительным, то процесс на продолжение выполнения из очереди ожидавших может выбираться по произвольному закону.

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

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Программно они могут быть реализованы с использованием режима активного ожидания, однако это сопряжено с потерей эффективности. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.

Семафорные операции дают простое решение проблемы КС. Участки взаимоисключения по семафору S в параллельных процессах обрамляются операциями P(S) и V(S). Пусть S – семафор, используемый для защиты КС. Тогда примитив P(S) представляет собой вход взаимоисключения, а примитив V(S) – выход взаимоисключения. Рассмотрим пример программы, обеспечивающей взаимоисключение при помощи семафора.

Program example_semaphore1;

Var S: semaphore;

Procedure process_1;

Begin

While true Do

Begin

P(S);

CS1;

V(S);

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

P(S);

CS2;

V(S);

program_2;

End;

End;

Begin

InitSem(S,1);

Parbegin

process_1; process_2;

Parend

End.

Семафор имеет начальное значение, равное 1. Если первый и второй процессы попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них. Предположим, что это сделал первый процесс. Он закрыл семафор, т.е. значение семафора стало S = 0, после чего данный процесс вошел в свой критический интервал. Второй процесс при этом оказывается заблокированным на семафоре – при попытке выполнения операции P(S) он "засыпает". Взаимное исключение гарантировано, т.к. только один процесс может уменьшить значение S до нуля с помощью P -операции. Очевидным образом это решение распространяется на случай n процессов – тогда все другие процессы, пытающиеся войти в свои КС при S = 0, будут вынуждены ожидать по P(S). Взаимное блокирование невозможно, т.к. одновременные попытки войти в свои КС при S = 0 должны, по определению, преобразовываться в последовательные P -операции. После выхода из своей КС процесс выполняет V- операцию, тем самым открывая семафор и предоставляя возможность "пробуждения" блокированным процессам. Тогда один из блокированных процессов переводится в очередь готовности.

При реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V(S):

§ процесс при его активизации вновь пытается выполнить примитив P, считая предыдущую попытку неуспешной;

§ процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив P. Тогда при его активизации управление будет передано не на повторное выполнение примитива P, а на команду, следующую за ним.

При первом способе возможна следующая последовательность событий. Предположим, что начальное значение семафора было равно единице. Пусть процесс2 в какой-то момент времени выполнит операцию P(S), семафор S станет равным нулю, а процесс2 войдёт в свою КС. Далее процесс1 тоже попытается выполнить операцию P(S) и "заснёт" на семафоре, поскольку значение семафора теперь станет равным –1. После выхода из КС процесс2 выполнит V(S), при этом значение семафора станет равным 0, а процесс1 переведётся в очередь готовности. После активизации процесс1 снова выполнит P(S) и опять "уснёт", то же самое произойдёт с процессом2, если он пожелает войти в свою КС. "Пробуждать" процессы станет некому. Таким образом, возможно возникновение тупиковой ситуации.

При втором способе реализации тупиковой ситуации не будет. Действительно, при аналогичном варианте развития событий отличие начнется с момента активизации процесса1. Он сразу войдёт в свою КС. При этом никакой другой процесс не попадёт в критическую секцию, т.к. семафор остаётся закрытым (его значение равно 0). После окончания работы процесса1 в КС в результате выполнения им операции V(S) значение семафора установится в единицу, если другие процессы не совершали попыток попасть в КС. Если процесс2, а также и другие процессы в случае их большего количества, во время работы процесса1 в КС также выполнят примитив P(S), то после выполнения процессом1 V -операции семафор установится в 0. Следовательно, он будет закрыт для всех процессов кроме того, который успел выполнить P -операцию, т.е. сделал заявку на КС. Таким образом, тупик не возникнет, а взаимоисключение гарантировано.

Возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций – с другой (как мы видим в первом способе реализации).

Реализация семафорных примитивов

В однопроцессорной вычислительной системе неделимость P - и V- операций можно обеспечить с помощью простого запрета прерываний. Сам семафор S можно реализовать записью с двумя полями. В одном поле хранится целое значение S, во втором – указатель на список процессов, заблокированных на семафоре S. Рассмотрим схематичное представление одного из программных вариантов реализации рассмотренных примитивов и процедуры инициализации.

Program semaphore_release;

Type Semaphore = Record

счетчик: Integer;

указатель: Pointer;

end;

Var S: Semaphore;

Procedure P(Var S:Semaphore);

Begin

Запретить прерывания;

S.счетчик:= S.счетчик-1;

If S.счетчик<0 Then

WAIT(S); {Поставить обратившийся процесс в список по S.указатель и установить на процессорр готовый к выполнению процесс}

Разрешить прерывания;

End;

Procedure V(Var S:Semaphore);

Begin

Запретить прерывания;

S.счетчик:= S.счетчик+1;

If S.счетчик<=0 Then

RELEASE(S); {Деблокировать первый процесс из списка по S.указатель}

Разрешить прерывания;

End;

Procedure InitSem(Var S:Semaphore, n:Integer);

Begin

S.счетчик:=n;

S.указатель:=nil;

End;

Мониторы Хоара

Несмотря на очевидные достоинства (простота реализации, независимость от количества процессов, отсутствие активного ожидания), семафоры имеют ряд недостатков. Семафорные механизмы являются слишком примитивными, т.к. сам семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы решения задач получаются запутанными и ненаглядными.

Нужны понятные и очевидные решения, которые позволяли бы создавать параллельные взаимодействующие программы. Таким решением являются т.н. мониторы, предложенные Хоаром (Hoare).

Монитор (в параллельном программировании) – это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причём в каждый момент им может пользоваться только один процесс.

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

Основные характеристики:

1. Локальные переменные монитора доступны только его процедурам.

2. Процесс входит в монитор путём вызова одной из его процедур.

3. В мониторе в определенный момент времени может находиться только один процесс; любой другой обратившийся будет приостановлен в ожидании доступности монитора.

Пример монитора:

Пусть некоторый ресурс распределяется между процессами планировщиком. Этот планировщик имеет переменные, с помощью которых он отслеживает, занят ресурс или свободен. Для получения ресурса процесс должен обратиться к планировщику, причём процедуру планировщика разделяют все процессы, и такое обращение может произойти в любой момент. Но планировщик не в состоянии обслужить более одного процесса одновременно – он и является монитором.

Т.о., монитор – такой механизм организации параллелизма, который содержит данные и процедуры, необходимые для реализации динамического распределения общих ресурсов.

Процесс, желающий получить доступ к разделяемым переменным, обращается к монитору, который в свою очередь предоставляет доступ или отказывает в нём. Вход в монитор находится под жёстким контролем. Здесь осуществляется взаимоисключение, т.е. в любой момент времени только один процесс может войти в монитор. Остальные обратившиеся процессы вынуждены ждать, причём режимом ожидания автоматически управляет сам монитор. При отказе в доступе монитор блокирует обратившийся процесс и определяет условие, по которому процесс ждёт. При деблокировании сам монитор и проверяет это условие. Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, эта процедура монитора выдает команду WAIT с указанием условия ожидания. Процесс мог бы оставаться внутри монитора, но это противоречит принципам взаимоисключения, если в монитор бы затем вошел другой процесс. Поэтому процесс в режиме ожидания вне монитора ждёт, пока требуемый ресурс освободится.

Доступ ко все внутренним данным монитора возможен только изнутри монитора. При первом обращении монитор присваивает своим переменным начальные значения; при последующих обращениях используются сохранённые от предыдущего обращения значения. Для защиты каких-либо данных нужно просто поместить их в монитор.

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

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

Для ОСРВ можно организовать дисциплину обслуживания на основе абсолютных или динамически изменяемых приоритетов.

Пример монитора Хоара:

Monitor Resource;

condition free; {условие – свободный}

Var busy: Boolean;

Procedure Request; {запрос}

Begin

If busy then WAIT(free);

busy:=true;

TakeOff; {выдать ресурс}

End;

Procedure Release;

Begin

TakeOn; {взять ресурс}

busy:=false;

SIGNAL(free)

End;

Begin

busy:=false;

End

Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам REQUEST и RELEASE.

Если процесс обращается к REQUEST в тот момент, когда ресурс используется, то значение busy=true, и REQUEST выполнит операцию монитора WAIT(free). Обратившийся процесс помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free.

Когда процесс, использующий ресурс, обращается к RELEASE, операция монитора SIGNAL(free) деблокирует процесс из начала очереди. Он готов сразу после операции WAIT(free), которая его и блокировала, возобновить выполнение процедуры REQUEST. Если же SIGNAL(free) выполняется в то время, когда нет ожидающего условия free процесса, то никакие действия не выполняются.

Доступ к разделяемым переменным ограничен телом монитора, а мониторы входят в состав ядра ОС, поэтому разделяемые переменные становятся системными переменными, что автоматически исключает критические интервалы (два процесса никогда не смогут получить одновременного доступа к разделяемым переменным). Процедуры монитора выполняются только по требованиям процесса.

Преимущества монитора перед другими средствами синхронизации:

§ в форме монитора легко реализовать любой механизм;

§ повышается наглядность;

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

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

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

Решение задачи производителя-потребителя при помощи монитора

Рассмотрим задачу производителя-потребителя в той же постановке: буферная память состоит из n буферов одинакового размера, каждый буфер может хранить одну запись, а добавление к буферу и изъятие из него информации образуют критические секции. Пусть считывание из буферной памяти выполняется по принципу FIFO (First In – First Out), а сама буферная память имеет кольцевую организацию. Это означает, что после заполнения (считывания) элемента с номером N соответствующий указатель перемещается на начало буфера. Тогда для контроля за состоянием буфера потребуется два указателя – номер очередного элемента для записи (назовем его NextIn) и номер очередного элемента для считывания – NextOut, а также счетчик количества элементов в буфере Count. Условия обозначим через NotFull и NotEmpty.

Монитор под названием Buffers будет содержать процедуры добавления элемента в буфер и считывания элемента из буфера: Append и Take. Общими переменными являются массив буферных элементов Buf, а также счетчик Count и указатели NextIn, NextOut. Программная реализация задачи с помощью монитора будет иметь вид:

Monitor Buffers;

Condition NotFull, NotEmpty;

Var Buf: Array [1..N] Of Char;

NextIn, NextOut, Count: Integer;

Procedure Append(X: Char);

Begin

If Count = N Then WAIT(NotFull); {буфер полон}

Buf[NextIn]:= X;

NextIn:= NextIn mod N + 1;

inc(Count);

SIGNAL(NotEmpty); {возобновление работы потребителя}

End;

Procedure Take(Var X: Char);

Begin

If Count = 0 Then WAIT(NotEmpty); {буфер пуст}

x:= Buf[NextOut];

NextOut:= NextOut mod N + 1;

dec(Count);

SIGNAL(NotFull); {возобновление работы производителя}

End;

Begin {тело монитора}

NextIn:= 0;

NextOut:= 0;

Count:= 0;

End;

Procedure Producer;

Var X: Char;

Begin

While true Do

Begin

Produce(X); {выработка X}

Append(X);

End;

End;

Procedure Consumer;

Var X: Char;

Begin

While true Do

Begin

Take(X);

Consume(X); {обработка X}

End;

End;

Begin {main}

Parbegin;

Producer;

Consumer;

Parend;

End;

Обмен сообщениями

Передача сообщений – один из способов обеспечения синхронизации процессов. Он пригоден для реализации в различных системах (однопроцессорных, многопроцессорных, распределенных).

Системы передачи сообщений могут быть разных типов. Обычно используются два примитива: SEND(получатель, сообщение) и RECEIVE(отправитель, сообщение). Процесс получает сообщение с помощью примитива RECEIVE, отправляет сообщение с помощью примитива SEND.

Синхронизация

Рассмотрим, что происходит после выполнения примитивов. После выполнения SEND существует две возможности: выполнивший его процесс блокируется или продолжает работу. После примитива RECEIVE. Те же две возможности. Но при этом:

§ если сообщение уже было отправлено ранее, то процесс получает его и продолжает работу;

§ если ожидаемого сообщения нет, то процесс или блокируется до его получения, или отказывается от получения и продолжает работу.

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

1. Блокирующее отправление, блокирующее получение (рандеву) – случай тесной синхронизации процессов.

2. Неблокирующее отправление, блокирующее получение (используется чаще всего). В этом варианте процесс может максимально быстро рассылать сообщения, не ожидая их получения адресатами.

3. Неблокирующее отправление, неблокирующее получение.

Для примитива SEND наиболее естественным является неблокирующий вариант. Например, он может быть использован при запросе операции ввода-вывода. Недостатком является то, что при возникновении ошибки может начаться непрерывная генерация сообщений, в результате чего произойдёт неоправданная загрузка системы. Кроме того, процесс-получатель в таком случае должен посылать уведомление о получении сообщения.

Для примитива RECEIVE наиболее естественной является блокирующая форма, поскольку если процесс просит информацию, то, видимо, она ему действительно нужна. Недостатком является то, что при сбое или потере сообщения процесс окажется заблокированным навсегда. Для избавления от этого недостатка можно указывать несколько возможных отправителей (если ожидаются сообщения от нескольких источников), тогда после получения любого из них процесс может продолжить работу.

Если использовать неблокирующий вариант RECEIVE, то при более позднем отправлении сообщения (чем попытка его получить) оно может быть потеряно. Для того, чтобы исключить такую ошибку, можно перед выполнением RECEIVE проверять, имеется ли уже сообщение (т.е. совершать какие-то дополнительные усилия).

Адресация

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

При прямой адресации:

Примитив SEND() указывает конкретного получателя. Для примитива RECEIVE возможны два варианта. 1) явное указание отправителя, если процессы сотрудничают; 2) неизвестно, откуда может прийти сообщение. Например, когда сервер печати принимает сообщения – запросы на печать, то неизвестно, от какого из процессов они могут поступить. В таком случае используется неявная адресация, т.е. "отправитель" получит конкретное значение только после выполнения операции RECEIVE.

При косвенной адресации:

Сообщения посылаются не прямо от отправителя получателю, а в некоторую совместно используемую структуру данных, предназначенную для временного хранения сообщений (т.н. почтовые ящики). Этот способ отличается эффективностью, т.к. достигается определенная гибкость в использовании сообщений. Могут быть организованы отношения самых разных типов между отправителем и получателем: "один к одному", "один ко многим", "многие к одному", "многие ко многим".

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

Почтовые ящики

Итак, для сохранения посланных, но ещё не полученных сообщений в системах предусмотрено специальное место, называемое буфером сообщений или почтовым ящиком.

Почтовый ящик – это информационная структура, поддерживаемая операционной системой. Она состоит из головного элемента, в котором находится информация о данном почтовом ящике, и из нескольких буферов (гнезд), в которые помещают сообщения. Размер каждого буфера и их количество обычно задаются при создании почтового ящика. Для пользования таким системным объектом процессы обращаются к ОС с соответствующими запросами. Поскольку в системе может быть много почтовых ящиков, необходимо обеспечить доступ процессу к конкретному ящику.

Если объём передаваемых данных велик, то нецелесообразно пересылать их непосредственно. Лучше отправлять в почтовый ящик сообщение, информирующее процесс-получатель о том, где найти эти данные.

Почтовый ящик может быть связан только с отправителем, или только с получателем, или с парой процессов (существует множество различных вариантов). Правила работы почтового ящика могут быть различными в зависимости от его сложности.

Основные достоинства почтовых ящиков:

§ процессу не нужно знать о существовании других процессов до тех пор, пока он не получит сообщения от них;

§ два процесса могут обмениваться более чем одним сообщением за один раз;

§ ОС может гарантировать невмешательство в общение двух процессов;

§ очереди буферов позволяют процессу-отправителю продолжать работу, не обращая внимание на получателя.

Недостатки:

§ Появление ещё одного ресурса, которым нужно управлять;

§ Статический характер этого ресурса.

Были созданы механизмы, подобные почтовым ящикам, но реализованные на принципах динамического выделения памяти.

Управление памятью

Термин "память" используется для обозначения любого устройства, способного хранить информацию. Здесь будем иметь в виду оперативную память компьютера (ОЗУ). Управление памятью – одна из основных задач ОС, и занимается им менеджер памяти, который входит в состав ядра ОС.

Стратегии управления

При использовании свопинга система создает на диске своп-файл. Стратегии управления вталкиванием (выборкой), размещением и выталкиванием (замещением) информации применительно к системам виртуальной памяти используются как при сегментной, так и при страничной организации памяти. Рассмотрим их на примере страниц.

В тот момент, когда процесс обращается к странице, которой нет в оперативной памяти, в действие вступает алгоритм выборки (или алгоритм вталкивания). Он заключается в загрузке страницы с диска в свободную физическую страницу и отображении этой физической страницы в то место, куда было произведено обращение, вызвавшее исключительную ситуацию. Кроме того, необходимо определить, в какой момент следует переписывать страницу (или сегмент) с диска в оперативную память. Вталкивание по запросу производится после появления ссылки и гарантирует необходимость подкачиваемого сегмента или страницы. Существуют модификации алгоритма выборки, которые применяют опережающее чтение (вталкивание с упреждением) – кроме страницы, вызвавшей исключительную ситуацию, в память загружается ещё несколько страниц, к которым наиболее вероятно будет обращаться процесс. Это позволяет уменьшить накладные расходы, связанные с большим количеством исключительных ситуаций, возникающих при работе с большими объёмами данных или кода. Кроме того, оптимизируется работа с диском, поскольку появляется возможность загрузки нескольких страниц за одно обращение. При правильном выборе страниц время выполнения задачи значительно сокращается.