Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 58

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Модель

Продолжение ПЗ-2

 

 

 

Скорость

Объем

 

Объем

Число

Наличие

 

Время

 

передачи

Объем

блоков на

автоматиче­

 

 

модуля в

блока в

Тип З У П Д

оборота,

млсек

информа­

миллионах

дорожки

миллионах

устройство

ского чте­

 

млсек

ции, тыс.

символов

в символах

символов

(канал)

ния и сверки

 

 

 

 

 

символ/сек

 

 

 

управления

записи

261

Диск с подвижной головкой

25,8

78

190

_

9216

150

8

Нет

262

То же

 

с

подвижной

25,8

78

120

—

9216

300

4

Я

273

Пакет дисков

25

50

208

18,4

4 602

18,4

8

„

 

головкой

 

 

25

50

208

18,4

4 602

147,2

1

 

275

То же

 

 

 

 

278

я

я

 

 

 

25

50

416

35

8 760

280

1

 

 

 

 

 

 

 

 

 

 

 

 

 

Т а б л и ц а ПЗ-3

 

 

 

Некоторые запоминающие

устройства прямого доступа фирмы IBM

 

 

 

 

 

 

 

 

 

 

Скорость

 

 

 

Число

Наличие

 

 

 

 

 

 

Время

 

передачи

Объем

Объем

Объем

блоков на

автоматиче­

Модель

 

 

Тип

З У П Д

оборота,

млсек

информа­

модуля,

дорожки,

блока,

устройств

ского чте­

 

 

 

 

 

 

млсек

ции,

Мбайт

байты

Мбайт

(канал)

ния и сверкр

 

 

 

 

 

 

 

 

кбайт/сек

 

 

 

управления

записи

2301

Барабан

с

фиксированной

17,5

 

1 200

 

20 483

4,09

4

Нет

 

головкой

 

 

 

 

 

—

 

 

 

 

1301

Диск с

подвижной головкой

34

120

70,1

2 160

56

5

»

2311

Пакет дисков с

подвижной

25

75

156

7,25

3 625

7,25

8

я

2314

головкой

 

 

25

75

312

29,175

7 294

233,4

8

 

То же

 

 

полосках

я

2321

ЗУ

на магнитных

50

500

55

40

2 000

400

8

в

(Data

 

 

 

 

 

 

.

350*

 

 

 

 

 

Gell)

 

 

 

 

 

 

 

550**

 

 

 

 

 

* Предыдущая

полоска

восстанавливается.

і ѣ Предыдущая

полоска

не воестаиавлввается.

 

Некоторые запоминающие

устройства

прямого доступа

фирмы RCA

Т а б л и ц а

ПЗ - 4

 

 

 

 

 

 

 

Время

 

Скорость

 

 

 

 

Число

Наличие

 

 

 

 

передачи

Объем

Объем

Объем

блоков на

автоматиче­

М о д е ль

Тип З У П Д

оборота

млсек

информа­

м о д у л я ,

дорожки,

блока,

устройство

ского чте­

 

 

 

млсек

 

ции.

 

Мбайт

байты

Мбайт

(канал)

ния и сверки

 

 

 

 

 

кбайті

сек

 

 

 

 

управления

 

записи

567-16,

Барабан с

фиксированной

16,6

 

 

333

 

 

5 161

8,26

 

 

Нет

567-8

головкой

 

 

 

 

 

 

 

 

 

4,13

 

 

 

564

Пакет дисков

25

85

 

156

 

7,25

3 625

7,25

 

 

 

(IBM 2311)

Магазинная

память на маг­

60

508

 

 

 

67

2 048

 

 

 

 

568

 

70

 

536,8

 

 

Да

 

нитных картах (подвижная

 

 

 

 

 

 

 

 

 

 

 

 

 

головка)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Некоторые запоминающие устройства

прямого доступа

фирмы

UNIVAC

Т а б л и ц а

ПЗ-5

 

 

 

 

Время

Модель Тип З У П Д оборота,

млсек млсек

Скорость

 

 

 

Число

Наличие

передачи

Объем

Объем

Объем

блоков на

автоматиче­

информа­

модуля

дорожки,

блока,

устройство

ского чте­

ции,

Мбайт

байты

Мбайт

(канал )

ния и сверки

к байт)сек

 

 

 

управления

записи

FH880

Барабан с фиксированной головкой

34

 

360*

 

6 144**

4,7**

Да

FH432

То же

8,5

57

1 440*

 

4 096**

1,6**

 

FASTRAND

Барабан с подвижной головкой

70

153,5*

 

10 752**

132**

 

II

 

 

 

 

 

 

 

 

8411

Пакет дисков с подвижной головкой

25

75

156

7,25

3 625

7,25

Нет

8410

Сменный диск с подвижной головкой

50

ПО

85

3 , 2 -

16 000

 

 

 

 

 

 

 

12,8

 

 

 

*Тысяч символов в секунду .

**Символов.

***На одном комплекте (он может быть заменен другим комплектом такого ж е объема).

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

ству (или

каналу)

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

но,

обеспечивает ли электронное оборудование автоматическое чтение

и

сверку

записи

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

обладающих этим свойством, каждая запись сопровождается чтением, при котором программа сверяет запись. Это означает, что после каж­

дого изменения записи на ЗУПД (такого,

как показано

в табл.

8-11)

требуется дополнительное вращение.

 

 

 

 

 

 

ПРИЛОЖЕНИЕ

4

 

ТЕМЫ ДЛЯ ОБСУЖДЕНИЯ И ЗАДАЧИ

 

 

1. Покажите, каким образом модель

информационной системы,

приведенная на рис.

1-1, применима к библиотеке.

 

 

2. С

помощью

набора схемных

компонентов,

приведенных

з табл.

1-1, постройте несколько информационных систем. Сравните

их по стоимости и опишите их относительные достоинства.

3.Исследуйте элементы сходства и различия между информа­ ционной системой и системой связи.

4.Рассмотрите схемно-программиое соответствие для систем

обработки с произвольным доступом, определенных в гл. 1.

5.Для рис. 1-1, 1-5 и 1-6 с помощью каталога оборудования сконструируйте и оцените схемную конфигурацию системы.

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

дискового пакета с головкой на каждую дорожку против системы

сподвижной головкой.

7.Что вы думаете о роли структуры информации и организации

файла в общесистемііом .проекте, если определить

эти

понятия так,

как это сделано в книге?

 

 

 

 

8. На каком уровне проходит различие между иерархической и

ассоциативной структурами

информации?

Следует

ли их различать

на всех уровнях?

 

 

 

 

9. Приведите другие примеры иерархических

информационных

структур. Можно ли представить себе структуру,

содержащую

циклы?

 

 

 

 

10. Каков, по вашему

мнению, класс

или классы

пользовате­

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

11. Опишите последовательность обработки, соответствующую в реальном масштабе времени следующему запросу.

Условия:

AI (SAL, LT.7500)

А2 (AGE, BTW.20, AVERAGE AGE A3 (POSN = SALES) .

Обработка

F I L E = Al U A2 U A3.

204

12.Какие глаголы или функции, помимо указанных в гл. 4, были бы полезны в проблемно-ориентированном языке запроса?

13.Какой справочный декодировщик; по вышему мнению, наибо­ лее эффективен в смысле простоты программирования, скорости де­ кодирования, гибкости, скорости обновления, поясните, почему?

14.Как мог бы быть построен рандомизированный алгоритм пре­ образования единственного ключа записи переменной длины без

использования уровня косвенной адресации, изображенного на рис. 6-4.

15. Выведите формулу декодирующего дерева, использующую параметры табл. 6-3 и время поиска ключа в последовательности, выражающую соотношение между физическим объемом записи (С,—Сг ) и глубиной дерева.

16.Почему в формуле (5-9) исчезает а?

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

19.Обслуживание пространства памяти с помощью формирова­

ния списка свободной памяти представляет собой один из возможных методов управления пространством памяти. Рассмотрите несколько примеров с этим подходом и сравните его г другими методами.

20. Постройте программу управления блоком логической обра­ ботки (см. рис. 7-6) для обработки функции запроса в нормальной дизъюнктивной форме, нормальной конъюнктивной форме, произволь­ ной факторизованной форме.

21.Постройте экономичную, но высокоэффективную систему хра­ нения и выборки для системы, выдающей 5—10 документов (писем, отчетов, заметок) в день. При каком объеме данных спроектирован­ ная система потеряет рентабельность?

22.Постройте и приведите блок-схему системы пакетной обра­ ботки, рассмотренной при описании табл. 7-8.

С П И С О К Л И Т Е Р А Т У Р Ы

'1. Stone P. J. An introduction lo the general inquirer: A computer system for the study of spoken or written material. Nrw York, Simulmatics Corp., 11962.

2.Miller G. A. Penink, a computer program and documentation written for the IBM 7040. Philadelphia, University of Pennsylvania, 1964.

3.Lebley R. S. Digital computer and control engineering. New York, McGraw-Hill Book Co., 1960.

4.Jonker information systems (Manual). Gaithersburg. Maryland, Jonker Corporation, 1967.

5.Hsiao D., Prywes N. S. A system to manage and information system. F. I. D./I. F. I. P. Conference 1967. On mechanized informa­

tion, storage retrieval and 'dissemination. Rome, Italy, June 1967.

6.IDS/COBOL General Electric Information System. CPB-144. August 1966.

7.Newell A. Information processing, Language V manual. Englewood, New Jersey, Prentice^Hall, Inc., 1961.

8.Peril's A. J., Thornton C. Sympot manipulation by threaded

list.— «Communications of the ACM». April

1960, vol. Ill , № 4.

 

9. Weizenbaum J. Knotted List

Structures.— «Communications

of

the ACM, Mardi

1962, vol. V, № 3.

 

 

 

 

 

10. Prywes

N. S., Gray H. J. et

al. The multi-list type

associative

memory.— «Proc. of Symposium on

Gigacycle Computing

Systems»,

AI БЕ Publication, January 1962, № S-13.

 

 

 

 

dl. Landauer W. I. The balanced tree and its utilization in in­

formation

retrieval.— «Transactions

on Electronic

Computer of

the

IEEE». 5 December, 1963, vol. EC - XII, № 5.

 

 

 

12. Johnson L. R. An indirect chaining

method

for addressing

on

secondary

keys.— «Communications

of the

ACM». May 1961, vol. IV,

№ 5.

•IS. Needham R. M., Sparck J. K. Keywords and clumps — recent work on information retrieval at the Cambridge language research unit.— «Journal of Documentation». March 1964, vol. XX, № 1.

 

 

 

 

 

ОГЛАВЛЕНИЕ

 

 

 

 

 

 

Предисловие

к русскому

изданию

 

 

 

 

 

 

 

3

Предисловие

автора

 

 

 

 

 

 

 

 

 

 

4

 

Г л а в а

п е р в а я .

Информационная система

 

 

 

 

7

1-1. Модель информационной системы

 

 

 

 

 

7

Г л а в а

в т о р а я .

Запоминающие

устройства прямого доступа

33

Г л а в а

т р е т ь я .

Структура

информации

и

организация

 

файла

 

 

 

 

 

 

 

 

 

 

 

41

 

3-1.

Функциональные требования к организации файла

.

4

3-2.

Структура

информации

и организация

файла . .

.

4

Г л а в а

ч е т в е р т а я . Язык

запроса

 

 

 

 

 

 

65

Г л а в а

п я т а я .

Классификация

методов

организации файла

87

Г л а в а

ш е с т а я .

Методы декодирования

справочников .

.

98

6-1. Дерево усеченных ключевых слов

постоянной длины

,99

6-2. Дерево однозначно усеченных ключевых слов перемен­

 

ной

длины

 

 

 

 

 

 

 

 

 

 

 

105

6-3. Дерево полных ключевых слов переменной длины .

.

110

6-4. Метод рандомизации

 

 

 

 

 

 

 

 

111

6-5. Требования декодера к объему

памяти и времени до­

 

ступа

 

 

 

 

 

 

 

 

 

 

 

116

 

6-5-1. Формулы для дерева декодера

 

 

 

 

117

6-5-2. Формулы для рандомизатора

 

 

 

 

121

6-5-3. Сравнение требований к объему

памяти . .

.

123

6-6. Скорость

декодирования

 

 

 

 

 

 

129

Г л а в а

с е д ь м а я .

Методы организации

поиска

файла .

.

132

7- 1. Мультисписковая

организация

файла . . . .

.

133

7-2. Организация

файла

по

методу

инвертированного

 

 

списка

 

 

 

 

 

 

 

 

 

 

 

135

 

7-3. Мультисписковая

организация

с управляемой длиной

 

 

списка

 

 

 

 

 

 

 

 

 

 

 

139

 

7-4.

Посекторные

разбиения

 

 

 

 

 

 

 

143

7-5. Автоматическая

классификация

 

 

 

 

 

149

7-6. Автономная

генерация

файлов

со

списковой

структу­

 

 

рой

 

 

 

 

 

 

 

 

 

 

 

 

150

 

7-7. Время выборки из файла

 

 

 

 

 

 

156

Г л а в а

в о с ь м а я .

Обновление

и обслуживание

оператив­

 

ного

файла

 

 

 

 

 

 

 

 

 

 

 

160

 

8- 1. Оперативные обновления мультисписковых файлов . 161

207

Смотрите также файлы