Разделение общих процедур

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

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

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

1. Процесс 1 выполняется и вызывает реентерабельную процедуру.

2. Реентерабельная процедура помещает промежуточный результат в ТНМР.

3. Процесс 2 получает управление процессором.

4. Процесс 2 вызывает реентерабельную процедуру.

5. Реентерабельная процедура вновь помещает промежуточный результат в TEMP.

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

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

Рис. 7.7. Реентерабельная процедура, разделяемая двумя процессами

В процессорах, имеющих стек, обычный способ хранения промежуточных результатов заключается в том, чтобы ассоциировать стек с каждым процессом. На рис. 7.7 показано, как два процесса обращаются к реентерабельной процедуре. Когда процесс 1 вызывает реентерабельную процедуру, содержимое регистров SS и SP не изменяется и реентерабельная процедура запоминает любые свои результаты в стеке процесса 1. Когда происходит переключение процессов, содержимое SS и Spизменяется с тем, чтобы адресовать вершину стека, ассоциированного с процессом 2. Когда вновь вызывается реентерабельная процедура, она будет запоминать свои результаты в стеке, ассоциированном с процессом 2, а предыдущие результаты не искажаются.

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

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

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

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

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

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

Распределен. Раздел в данное время распределен заданию.

Свободен.Раздел доступен для использования.

Не используется.Элемент не ассоциирован с разделом.

Третье состояние может возникнуть в том случае, когда два соседних свободных раздела объединены в один.

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

Когда задание завершено, занятая им область возвращается в систему. Процедура управления памятью модифицирует таблицу карты памяти, чтобы отразить возможное слияние соседних свободных разделов, появляющихся при освобождении памяти. Две возможные ситуации, вызывающие слияние, представлены на рис. 7.8. В случае 1 освобожденный раздел оказывается соседним с имеющейся свободной областью. После слияния два свободных раздела объединены в один большой раздел, начальный адрес которого равен меньшему из двух первоначальных свободных адресов. В случае 2 две имеющиеся свободные области разделены освобожденным разделом. В результате слияния три раздела объединяются в один. Слияние необходимо для того, чтобы иметь максимальные размеры свободных разделов.

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

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

Рис. 7.8. Слияние свободных разделов Рис. 7.9. Фрагментация памяти (а)

и загрузка задания (б)

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

Чтобы обеспечить позиционную независимость, сегментными регистрами должна управлять только процедура управления памятью, а программа не должна их модифицировать. Кроме того, все вызовы процедур и переходы должны иметь тип near. В противном случае, если CS был запомнен вызовом до перемещения, а возврат осуществляется после перемещения, CS будет содержать старый сегментный адрес и программа возвратится в неправильное место. Так как переместимой программе не разрешается модифицировать сегментные регистры, задание может иметь максимум четыре сегмента (кода, данных, дополнительных данных и стека) и максимальный размер задания ограничен 4 х 64К= 256K.

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

Контрольные вопросы

1. Назовите и опишите классы МПС по Флинну.

2. Что такое МПС с общей памятью?

3. Что такое МПС с индивидуальной памятью?

4. Что вызывает некорректность вычислений в ВМ с общей памятью?

5. Каковы достоинства и недостатки ВМ с передачей сообщений?

6. Что такое кластер?

7. В чем состоит принципиальное отличие кластеров от систем MPP?

8. В чем заключается основное назначение мультипроцессорных систем?

9. Объясните различия в SIMD и MIMD технологиях.

10. Что такое кластер? Где используются кластеры?

11. Какие языки программирования следует использовать для ВС типа MSIMD?

12. В чем заключаются основные свойства мультипрограммной среды?

13. Что такое пропускная способность МПС?

14. Что такое процесс и в каких состояниях он может находиться?

15. Как и для чего используются семафоры?

16. Поясните работу семафорных операторов.

17. Какими свойствами должна обладать реентерабельная процедура?

18. В чем состоит проблема фрагментации?

19. Как реализуется способ распределения разделов с перемещением?