L-----+---------+---------------------------------------------D.4 ИСПОЛЬЗОВАНИЕ КОМАНД CAS/CAS2 В СИСТЕМНЫХ ПРОГРАММАХ
Команда CAS позволяет безопасно обновлять системные счетчики, информацию протокольного характера и совместно используемые глобальные указатели. Эта команда представляет собой средство обеспечения защиты в однопроцессорных системах, многозадачных и мультипроцессорных средах. В однопроцессорной системе непрерываемая операция обновления используется для защиты в средах с управлением по прерываниям; в мультипроцессорной системе неделимая операция цикла шины (монополизирующая шину) реализует механизм защиты. Пусть, к примеру, слово SYS_CNTR содержит счетчик числа раз выполнения некоторой операции, которую может выполнить любой процесс или любой процессор системы. Тогда правильное инкрементирование счетчика SYS_CNTR гарантируется выполнением следующей последовательности команд:
MOVE.W SYS_CNTR,D0 считать старое значение счетчика
INC_LOOP MOVE.W D0,D1 скопировать его
ADDQ.W #1,D1 увеличить на единицу
CAS.W D0,D1,SYS_CNTR если значение счетчика не изменилось, то обновить его
BNE INC_LOOP если нет, попытаться снова
Пара команд CAS и CAS2 позволяет безопасно манипулировать системными очередями. Если очередь обслуживается по принципу "последним пришел - первым ушел", то достаточно контролировать единственную переменную HEAD. Если очередь пуста, то HEAD содержит указатель ПУСТО (0). Следующая последовательность команд реализует вставку и удаление из такой очереди. Рис.D-6 и Рис.D7 иллюстрируют, соответственно, обе эти операции:
SINSERT вставить новый элемент (адрес которого находится в A1)
MOVE.L HEAD,D0 передать значение указателя на головной элемент в D0
SILOOP MOVE.L DO,(NEXT,A1) установить ссылку вперед в новом элементе
MOVE.L A1,D1 переслать значение указателя нового элемента в D1
CAS.L D0,D1,HEAD если все еще указывает на вершину стека, то обновить ук-ль
BNE SILOOP если нет, попытаться снова
Перед вставкой элемента:
--------------¬ --------------¬ --------------¬
----> элемент ¦ ---> элемент ¦ -----> элемент ¦
¦ ¦ + NEXT¦ ¦ ¦ + NEXT¦ ... ¦ + NEXT¦
¦ ¦ ------+ ¦ ¦ ------+ ¦ ¦ ------+
¦ ¦ ¦ ? ¦ ¦ ¦ ¦ --+---- ¦ ¦ X ¦
L-------+------ L-------+------ L-------+-----новый HEAD
После вставки элемента:
--------------¬ --------------¬ --------------¬
----> элемент ¦ ---> элемент ¦ -----> элемент ¦
¦ --> + NEXT¦ ¦ ¦ + NEXT¦ ... ¦ + NEXT¦
¦ ¦ ¦ ------+ ¦ ¦ ------+ ¦ ¦ ------+
¦ ¦ ¦ ¦ --+-- ¦ ¦ --+---- ¦ ¦ X ¦
HEAD L-------+------ L-------+------ L-------+-----¦
новый
Рис.D-6. Вставка в однонаправленный список
SDELETE
LEA HEAD,A0 загрузить адрес головного указателя в A0
MOVE.L (A0),D0 передать значение ук-ля в D0
SDLOOP TST.L D0 проверить, не пуста ли очередь
BEQ SDEMPTY если пуста, нечего удалять
LEA (NEXT,D0),A1 загрузить в A1 адрес ссылки вперед
MOVE.L (A1),D1 переслать в D1 значение ссылки вперед
CAS2.L D0:D1,D1:D1,(A0):(A1) если все еще указывает на удаляемый элемент , то обновить ук-ль и заголовок
BNE SDLOOP если нет, попытаться снова
SDEMPTY успешное удаление; адрес удаленного элемента в D0
(возможно, ПУСТО)
Перед удалением элемента:
--------------¬ --------------¬ --------------¬
----> элемент ¦ ---> элемент ¦ -----> элемент ¦
¦ ¦ + NEXT¦ ¦ ¦ + NEXT¦ ... ¦ + NEXT¦
¦ ¦ ------+ ¦ ¦ ------+ ¦ ¦ ------+
¦ ¦ ¦ --+-- ¦ ¦ --+---- ¦ ¦ X ¦
L-------+------ L-------+------ L-------+-----HEAD
После удаления элемента:
--------------¬ --------------¬ --------------¬
¦ элемент ¦ ---> элемент ¦ -----> элемент ¦
¦ + NEXT¦ ¦ ¦ + NEXT¦ ... ¦ + NEXT¦
¦ ------+ ¦ ¦ ------+ ¦ ¦ ------+
¦ ¦ ¦ ¦ ¦ ¦ --+---- ¦ ¦ X ¦
L-------+------ L-------+------ L-------+-----HEAD
Рис.D-7. Удаление из однонаправленного списка
Команда CAS2 может быть использована для обеспечения корректности операций с двунаправленными списками при дисциплине обслуживания "первым пришел - первым ушел". Для работы с таким списком требуется контролировать две переменные, LIST_PUT и
LIST_GET, которые используются как указатели, соответственно, на элемент, включенный в список последним, и на элемент, подлежащий выборке первым. Если список пуст, то оба указателя содержат значение ПУСТО (0). Следующая последовательность команд реализует вставку и удаление из такого двунаправленного списка.
Рис.D-8 и Рис.D-9 иллюстрируют, соответственно, обе эти операции:
DINSERT вставить новый элемент (адрес которого находится в A2)
LEA LIST_PUT,A0 загрузить адрес указателя на первый элемент в A0
LEA LIST_GET,A1 загрузить адрес указателя на последний элемент в A1
MOVE.L A2,D2 загрузить указатель на новый элемент в D2
MOVE.L (A0),D0 загрузить указатель на первый элемент в D0
DILOOP TST.L D0 не пуст ли указатель на первый элемент?
BEQ DIEMPTY если да, то нужно лишь установить указатели
MOVE.L D0,(NEXT,A2) заслать указатель на первый элемент в ссылку вперед у нового элемента
CLR.L D1 заслать пустой указатель в D1
MOVE.L D1,(LAST,A2) заслать пустой указатель в ссылку назад у нового элемента
LEA (LAST,D0),A1 загрузить адрес ссылки назад у прежнего первого элемента в A1
CAS2.L D0:D1,D2:D0,(A0):(A1) если LIST_PUT все еще указывает на прежний первый элемент, обновить указатель на первый и ссылку назад у прежнего первого
BNE DILOOP иначе попытаться снова
BRA DIDONE
DIEMPTY MOVE.L D0,(NEXT,A2) заслать пустой указатель в ссылку вперед у нового элемента
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.