Файл: Tannenbaum.pdf

Вопросы и задания  4 3 3

SUB М

MUL М

DIV М

+ двухадресные:

MOV (X=Y)

ADD (X=X+Y)

SUB (X=X-Y)

MUL (X=X*Y)

DIV (X=X/Y)

• трехадресные:

MOV (X=Y)

ADD (X=Y+Z)

SUB (X=Y-Z)

MUL (X=Y*Z)

DIV (X=Y/Z).

8. M — это 16-битный адрес памяти, а X, Y и Z — это или 16-битные адреса, или

4-битные регистры. Безадресная машина использует стек, одноадресная ма-
шина использует регистр-аккумулятор, а оставшиеся две имеют 16 регист-
ров и команды, которые оперируют со всеми комбинациями ячеек памяти и
регистров. Команда SUB X, Y вычитает Y из X, а команда SUB X, Y, Z вычитает Z
из Y и помещает результат в X. Если длина кодов операций равна 8 битам,
а размеры команд кратны 4 битам, сколько битов нужно каждой машине для
вычисления X?

9. Придумайте такой механизм адресации, который позволяет определять в

6-битном поле произвольный набор из 64 адресов, не обязательно смежных.

10. В чем недостаток самоизменяющихся программ, которые не были упомяну-

ты в тексте?

11. Переделайте следующие формулы из инфиксной записи в обратную польскую

запись:

• A+B+C+D+E
• (А+В) х (C+D)+E
• (AxB)+(CxD)+E

• (А-В) х (((C-DxE)/F)/G) xH

12. Переделайте следующие формулы из обратной польской записи в инфикс-

ную запись:

• AB + C + D x
• AB/CD/ +
• ABCDE+xx/
• ABCDExF/+G-H/x+

4 3 4 Глава 5. Уровень архитектуры команд

13. Какие из следующих пар формул в обратной польской записи математичес-

ки эквивалентны?

• АВ + С +  и А В С + +
•  А В - С - и А В С - -
•  А В х С + и А В С + х

14. Напишите три формулы в обратной польской записи, которые нельзя пере-

делать в инфиксную запись.

15. Переделайте следующие инфиксные логические формулы в обратной

польской записи.

• (А И В) ИЛИ С
• (А ИЛИ В) И (А ИЛИ С)
• (А И В) ИЛИ (С И D)

16. Переделайте следующую инфиксную формулу в обратную польскую запись

и напишите код JVM, чтобы выполнить ее.
(2хЗ+4)-(4/2+1)

17. Команда языка ассемблера

MOV REG.ADDR
означает загрузку регистра из памяти компьютера Pentium II. Однако для
UltraSPARC II для загрузки регистра из памяти нужно написать

LOAD ADDR, REG

Почему порядок операндов разный?

18. Сколько регистров содержится в машине, форматы команд которой даны на

рис. 5.16?

19. В форматах команд на рис. 5.16 бит 23 используется для различения форма-

та 1 и формата 2. Однако для определения формата 3 никакого специально-
го бита не предусмотрено. Как аппаратное обеспечение узнает, что нужно
использовать формат 3?

20. Обычно программа определяет местонахождение переменной X в пределах

интервала от А до В. Если бы имелась трехадресная команда с операндами
А, В и X, сколько битов кода условия было бы установлено этой командой?

21. Pentium II содержит бит кода условия, который следит за переносом бита 3

после выполнения арифметической операции. Зачем это нужно?

22. В UltraSPARC II нет такой команды, которая загружает в регистр 32-бит-

ное число. Вместо нее обычно используется последовательность из двух
команд: SETHI и ADD. Существуют ли еще какие-нибудь способы загрузки
32-битного числа в регистр? Аргументируйте.

23. Один из ваших друзей стучится к вам в комнату в 3 часа ночи и радостно

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

Вопросы и задания 435

24. В программировании очень распространены следующие формы проверки:

if (n==0)
if

 O>J).

if (k<4).

Предложите команду, которая будет проверять эти условия эффективно.
Какие поля имеются в вашей команде?

25. Покажите для 16-битного двоичного числа 1001 0101 1100 0011:

+ Сдвиг вправо на 4 бита с заполнением нулями.
• Сдвиг вправо на 4 бита с расширением по знаку.
• Сдвиг влево на 4 бита.
• Циклический сдвиг влево на 4 бита.
• Циклический сдвиг вправо на 4 бита.

26. Как можно в машине, в которой нет команды CLR, очистить слово памяти?
27. Вычислите логическое выражение (А И В) ИЛИ С для:

• А-1101 0000 1010 1101
• В—1111 11110000 1111
• С=0000 0000 0010 0000

28. Придумайте, как поменять местами две переменные А и В, не используя при

этом третью переменную или регистр. Подсказка: подумайте о команде
ИСКЛЮЧАЮЩЕЕ ИЛИ.

29. На некотором компьютере можно перемещать число из одного регистра в дру-

гой, сдвигать каждый из них влево на разное количество байтов и склады-
вать полученные результаты за меньшее время, чем потребовалось бы для
выполнения умножения. При каком условии эта последовательность команд
будет полезна для вычисления произведения «константа х переменная»?

30. Разные машины имеют разную плотность команд (то есть разное число бай-

тов, которое требуется для выполнения определенного вычисления). Транс-
лируйте следующие три фрагмента программы на языке Java на ассемблер

для Pentium II, UltraSPARC II и JVM. Затем посчитайте, сколько байтов

требуется для выполнения каждого выражения для каждой машины (пред-
полагается, что i и j — это локальные переменные памяти):

• i-3;
• i-j;
• i-j-1;

31. В этой главе рассматривались команды цикла для работы с циклами for.

Разработайте команду для обращения с циклами while.

32. Предположим, что ханойские монахи могут перемещать один диск за 1 ми-

нуту (они не торопятся закончить работу, поскольку в Ханое очень мало
вакансий для людей с подобными навыками). Сколько времени им по-
требуется, чтобы решить задачу (то есть переместить все 64 диска)? Ответ
дайте в годах.

4 3 6 Глава 5. Уровень архитектуры команд

33. Почему устройства ввода-вывода помещают вектор прерывания на шину?

Разве нельзя вместо этого сохранить соответствующую информацию в таб-

лице в памяти?

34. Компьютер для считывания информации с диска использует канал прямого

доступа к памяти. Диск содержит 64 сектора по 512 байтов на дорожке. Вре-

мя оборота диска 16 мс. Ширина шины 16 битов. Каждая передача шины

занимает 500 не. В среднем для одной команды процессора требуется два

цикла шины. Насколько скорость работы процессора замедляется из-за пря-
мого доступа к памяти?

35. Почему программам обработки прерываний приписываются определенные

приоритеты, а обычные процедуры приоритетов не имеют?

36. Архитектура IA-64 содержит необычайно большое число регистров (64).

Связано ли столь большое количество регистров с использованием преди-
кации? Если да, то каким образом? Если нет, то зачем тогда их так много?

37. В пятой главе обсуждалось понятие спекулятивной загрузки. Но о коман-

дах спекулятивного сохранения мы не упоминали. Почему? Может быть,

они просто аналогичны спекулятивным загрузкам, или существует какая-то

другая причина, по которой мы не стали о них говорить?

38. Когда нужно связать две локальные сети, между ними помещается мост, свя-

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

39. На рис. 5.24 указатель фрейма указывает на первую локальную переменную.

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

40. Напишите подпрограмму на языке ассемблера для превращения целого дво-

ичного числа со знаком в код ASCII.

41. Напишите подпрограмму на языке ассемблера для превращения инфикс-

ной формулы в обратную польскую запись.

42. «Ханойская башня» — это не единственная рекурсивная процедура, любимая

многими компьютерщиками. Есть еще одна очень популярная рекурсивная
процедура п!, где n!=n(n-l)! Подчиняется ограничивающему условию 01=1.
Напишите на вашем любимом языке ассемблера процедуру для вычисления п!.

43. Попробуйте решить задачу «Ханойская башня» без использования рекур-

сии путем содержания стека в массиве. Предупреждаем, что, вероятно, вы
не сможете найти решения.

Глава 6

Уровень операционной

системы

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

вень и уровень команд. Настало время перейти к следующему уровню — уровню
операционной системы.

Операционная система

 — это программа, которая добавляет ряд команд и осо-

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

Хотя и уровень операционной системы, и уровень команд абстрактны (в том

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

 системными вызовами.

 Они

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

Уровень 3

Уровень операционной системы

Операционная система

Уровень 2 Уровень архитектуры команд

Микропрограмма или

аппаратное обеспечение

Уровень 1 Микроархитектурный уровень

Рис.

  6 . 1 . Расположение уровня операционной системы

Уровень операционной системы всегда интерпретируется. Когда пользователь-

ская программа выполняет команду операционной системы, например чтение дан-
ных из файла, операционная система выполняет эту команду шаг за шагом, точно