АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой IBM 360 (370) эта команда называлась TS (test and set). Команда TS является двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды. Чтобы использовать команду TS для решения проблемы критического интерва­ла, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет при­нимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная, которая принимает значение, равное единице, если дан­ный процесс хочет войти в свой критический интервал. Операция TS будет при­сваивать значение common локальной переменной и устанавливать common в единицу. Программа решения проблемы критического интервала на примере двух парал­лельных процессов приведена в листинге 6.5.

Листинг 6.5. Взаимное исключение с помощью операции «ПРОВЕРКА И УСТАНОВКА»

var common, locall. local2: integer: begin

common:-0; parbegin

ПР1: while true do begin

local!:-!:

while local!-! do TSdocall, common); CS1; { Критический интервал процеса ПР1) common:-0:

PR1; { ПР1 после критического интервала } end and

ПР2: while true do begin

Iocal2:-l;

while loca!2-l do TS(local2, common); CS2; { Критический интервал процеса ПР2) common:-0:

PR2; { ПР2 после критического интервала } end

parend end.

Предположим, что первым захочет войти в свой критический интервал процесс ПР1. В этом случае значение local 1 сначала установится в единицу, а после цик­ла проверки с помощью команды TSCIocall, common) — в ноль. При этом значение common станет равным единице. Процесс ПР1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свой критический интервал.

Безусловно, мы предполагаем, что в компьютере предусмотрена блокировка па­мяти, то есть операция common:=0 неделима. Команда «ПРОВЕРКА И УСТАНОВ­КА» значительно упрощает решение проблемы критических интервалов. Глав­ное свойство этой команды — ее неделимость.

Основной недостаток использования операций типа «ПРОВЕРКА И УСТАНОВ­КА» состоит в следующем: находясь в цикле проверки переменной common, про­цессы впустую потребляют время центрального процессора и другие ресурсы. Действительно, если предположить, что произошло прерывание процесса ПР1 во время выполнения своего критического интервала в соответствии с некото­рой дисциплиной обслуживания и начал выполняться процесс ПР2, то он войдет в цикл проверки, впустую тратя процессорное время. В этом случае до тех пор, пока диспетчер супервизора не поставит на выполнение процесс ПР1 и не даст ему закончиться, процесс ПР2 не сможет войти в свой критический интервал.

В микропроцессорах i80386 и старше, с которыми мы теперь сталкиваемся по­стоянно, есть специальные команды: ВТС, BTS, ВТК, которые как раз и являют­ся вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА». Рас­смотрим одну из них — BTS.

Команда BTS (bit test and reset — проверка бита и установка) является двухад­ресной [48]. По этой команде процессор сохраняет значение бита из первого опе­ранда со смещением, указанным вторым операндом, во флаге CF¹ регистра фла­гов, а затем устанавливает указанный бит в 1. Значение индекса выбираемого бита может быть представлено постоянным непосредственным значением в ко­манде BTS или значением в общем регистре. В этой команде используется толь­ко 8-битное непосредственное значение. Значение этого операнда берется по мо­дулю 32, таким образом, смещение битов находится в диапазоне от 0 до 31. Это позволяет выбирать любой бит внутри регистра. Для битовых строк в памяти это поле непосредственного значения дает только смещение внутри слова или двойного слова.

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

Однако здесь следует заметить, что некоторые ассемблеры поддерживают значе­ния битовых смещений больше 31, используя поле непосредственного значения в комбинации с полем смещения операнда в памяти. В этом случае ассемблером младшие 3 или 5 битов (3 — для 16-битных операндов, 5 — для 32-битных опе­рандов) смещения бита (второй операнд команды) сохраняются в поле непо-

¹ CF (carry flag) — флаг переноса. Располагается в слове состояния программы. Для про­цессоров i80x86 этот регистр — управляющий регистр CRO.

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

Effective Address + (4 * (BitOffset DIV 32))

для размера операнда 32 бита, или к двум байтам, начинающимся по адресу Effective Address + (2 * (BitOffset DIV 16))

для 16-битного размера операнда. Такое обращение происходит, даже если необ­ходим доступ только к одиночному байту. Поэтому избегайте ссылок к областям памяти, близким к «пустым» адресным пространствам. В частности, избегайте ссылок на распределенные в памяти регистры ввода/вывода. Вместо этого ис­пользуйте команду MOV для загрузки и сохранения значений по таким адресам и регистровую форму команды BTS для работы с данными.

Листинг 6.6. Фрагмент программы на ассемблере с критическим интервалом

L: ВТС МЛ JC L

L; критическая секция AND М. 0В

Несмотря на то что и алгоритм Деккера, основанный только на блокировке памяти, и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой про­цесс, который пытается войти в свою критическую секцию, попадает в цикл про­верки соответствующих переменных-флагов, регламентирующих доступ к кри­тическим переменным. При таком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время, поскольку процесс имеет доступ к тем общим переменным, которые и определя­ют возможность или невозможность входа в критическую секцию. При этом процесс занимает ценное время центрального процессора, на самом деле ничего реально не выполняя. Как результат, мы имеем общее замедление вычислитель­ной системы процессами, которые реально не выполняют никакой полезной ра­боты.

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

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

Вместо того чтобы связывать с каждым процессом свою собственную перемен­ную, как это было в рассмотренных нами решениях, можно со всем множеством конкурирующих критических секций связать одну переменную, которую и рас­сматривать как некоторый ключ. Вначале доступ к критической секции открыт. Однако перед входом в свой критический интервал процесс забирает «ключ» и тем самым блокирует другие процессы. Покидая критическую секцию, процесс открывает доступ, возвращая «ключ» на место. Если процесс, который хочет войти в свою критическую секцию, обнаруживает, что ключ «отсутствует», то он должен быть переведен в состояние блокирования до тех пор, пока процесс, имеющий ключ, не вернет его. Таким образом, каждый процесс, входящий в кри­тический интервал, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным явля­ется то, что эти два действия должны быть неделимыми, чтобы два или более процессов не могли одновременно получить доступ к ключу. Более того, провер­ку того, можно ли войти в критический интервал, лучше всего выполнять не са­мим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию на операционную систему. Таким образом, мы подо­шли к одному из самых главных механизмов решения проблемы взаимного ис­ключения — семафорам Дейкстры.

Дата добавления: 2015-01-18 | Просмотры: 1063 | Нарушение авторских прав