ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12185
Скачиваний: 10
468 Глава 6. Уровень операционной системы
Количество
секторов
Дорожка Сектор в дырке
0
0
1
1
2
2
2
3
3
4
0
6
0
11
1
3
7
0
9
3
5
6
10
1
1
3
5
3
3
8
Дорожка 0
0
1
2
3
4
1 0 1
Сектор
0 1 0
1 0 1 0 1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
Рис. 6.19. Два способа отслеживания свободных секторов: список свободной памяти (а);
битовое отображение (б)
Первый подход позволяет легко находить дырку определенной длины. Однако
у этого метода есть недостаток: по мере создания и уничтожения файлов длина
списка будет меняться, а это нежелательно. Преимущество таблицы битов состоит
в том, что она имеет постоянный размер. Кроме того, для изменения статуса еди-
ничного блока из свободного в занятый нужно поменять значение всего одного
бита. Однако при таком подходе трудно найти блок данного размера. Оба метода
требуют, чтобы при записи файла на диск или удалении файла с диска список раз-
мещения или таблица обновлялись.
Перед тем как закончить обсуждение вопроса о реализации системы файлов,
нужно сказать пару слов о размере единичного блока. Здесь играют роль несколь-
ко факторов. Во-первых, время поиска и время, затрачиваемое на вращение диска,
затормаживают доступ к диску. Если на нахождение начала блока тратится 10 млс,
то гораздо выгоднее считать 8 Кбайт (это займет примерно 1 млс), чем 1 Кбайт
(это займет примерно 0,125 миллисекунды), так как если считывать 8 Кбайт как
8 блоков по 1 Кбайт, нужно будет осуществлять поиск 8 раз. Для повышения про-
изводительности нужны большие единичные блоки.
Чем меньше размер единичного блока, тем больше их должно быть. Большое
количество единичных блоков, в свою очередь, влечет за собой длинные индексы
файлов и большие таблицы в памяти. Системе MS DOS пришлось перейти на мно-
госекторные блоки по той причине, что дисковые адреса хранились в виде 16-бит-
ных чисел. Когда размер дисков стал превышать 64 К секторов, представить их
можно было, только используя единичные блоки большего размера, поэтому чис-
ло таких блоков не превышало 64 К. В первом выпуске системы Windows 95 воз-
никла та же проблема, но в последующем выпуске уже использовались 32-битные
числа. Система Windows 98 поддерживает оба размера.
Маленькие блоки тоже имеют свои преимущества. Дело в том, что файлы очень
редко занимают ровно целое число единичных блоков. Следовательно, практичес-
ки в каждом файле в последнем единичном блоке останется неиспользованное
пространство. Если размер файла сильно превышает размер единичного блока, то
в среднем неиспользованное пространство будет составлять половину блока. Чем
Виртуальные команды ввода-вывода 469
больше блок, тем больше остается неиспользованного пространства. Если сред-
ний размер файла намного меньше размера единичного блока, большая часть
пространства на диске будет неиспользованной. Например, в системе MS DOS
или в первой версии Windows 95 с разделом диска в 2 Гбайт размер единичного
блока составляет 32 Кбайт, поэтому при записи на диск файла в 100 символов
32 668 байтов дискового пространства пропадут. С точки зрения распределения
дискового пространства маленькие единичные блоки имеют преимущество над
большими. В настоящее время самым важным фактором считается быстрота пере-
дачи данных, поэтому размер блоков постоянно увеличивается.
Команды управления директориями
Много лет назад программы и данные хранились на перфокартах. Поскольку раз-
мер программ увеличивался, а данных становилось все больше, такая форма хра-
нения стала неудобной. Тогда возникла идея вместо перфокарт использовать для
хранения программ и данных вспомогательную память (например, диск). Инфор-
мация, доступная для компьютера без вмешательства человека, называется
неав-
тономной. Автономная
информация, напротив, требует вмешательства человека
(например, нужно вставить компакт-диск).
Неавтономная информация хранится в файлах. Программы могут получить
доступ к ней через программы ввода-вывода. Чтобы следить за информацией, за-
писанной неавтономно, группировать ее в удобные блоки и защищать от незакон-
ного использования, нужны дополнительные команды.
Обычно операционная система группирует неавтономные файлы в
директо-
рии.
На рис. 6.20 проиллюстрирован пример такой организации. Обеспечиваются
системные вызовы, по крайней мере, для следующих функций:
1. Создание файла и введение его в директорию.
2. Стирание файла из директории.
3. Переименование файла.
4. Изменение статуса защиты файла.
Применяются различные схемы защиты. Например, владелец файлов может
ввести секретный пароль для каждого файла. При попытке доступа к файлу про-
грамма должна выдавать пароль, который проверяется операционной системой.
Доступ к файлу разрешается только в том случае, если пароль правильный. Для
каждого файла можно создать список людей, программы которых могут получать
доступ к данному файлу.
Все современные операционные системы позволяют хранить более одной дирек-
тории. Каждая директория обычно сама представляет собой файл и как таковая
может быть вставлена в другую директорию, в результате чего можно получить
дерево директорий. Большое количество директорий особенно нужно програм-
мистам, которые работают над несколькими проектами. Они могут сгруппировать
в одну директорию все файлы, связанные с одним проектом. Директории — это
удобный способ делить файлы с членами своих рабочих групп.
4 7 0 Глава 6. Уровень операционной системы
Файл 0
Файл 1
Файл 2
Файл 3
Файл 4
Файл 5
Файл 6
Файл 7
Файл8
Файл 9
Файл 10
Имя файла: Rubber-ducky
Длина: 1840
Тип: Anatidae dataram
Дата создания: 16 марта 1066
Последнее обращение: 1 сентября 1492
Последнее изменение: 4 июля 1776
Общее число обращений: 144
Блок 0: Дорожка 4 Сектор 6
Блок1: Дорожка 19 Сектор 9
Блок 2: Дорожка 11 Сектор 2
Блок 3: Дорожка 77 Сектор 0
Рис. 6.20.
Пользовательская директория (а); содержание одного из элементов директории (б)
Виртуальные команды
для параллельной обработки
Некоторые вычисления удобно производить с помощью двух и более параллель-
ных процессов (то есть как будто бы на разных процессорах). Другие вычисления
можно поделить на части, которые затем выполняются параллельно, что сокраща-
ет общее время вычисления. Чтобы несколько процессов могли происходить
параллельно, нужны специальные виртуальные команды. Мы будем их обсуждать
в следующих разделах.
Интерес к параллельной обработке обусловлен и некоторыми законами физи-
ки. Согласно эйнштейновской теории относительности, скорость передачи элек-
трических сигналов не может превышать скорость света, которая равна примерно
1фут/нс в вакууме, а в медном проводе или оптическом волокне — еще меньше.
Важно учитывать этот предел при разработке компьютеров. Например, если про-
цессору нужны данные из основной памяти, которые находятся на расстоянии
1 фута, потребуется по крайней мере 1 не, чтобы запрос дошел до памяти, и еще
1 не, чтобы ответ венулся к центральному процессору. Следовательно, чтобы
компьютеры могли передавать сигналы быстрее, они (компьютеры) должны быть
совершенно крошечными. Альтернативный способ увеличения скорости компью-
тера — создание машины с несколькими процессорами. Компьютер, содержащий
1000 процессоров с временем цикла в 1 не, будет иметь такую же мощность, как про-
цессор с временем цикла 0,001 не, но первое осуществить гораздо проще и дешевле.
В компьютере с несколькими процессорами каждый из нескольких взаимодей-
ствующих процессов можно приписать к одному определенному процессору, что-
бы выполнять несколько действий одновременно. Если в компьютере имеется толь-
ко один процессор, эффект параллельной обработки можно смоделировать. Для
этого процессы будут выполняться по очереди, каждый понемножку. Иными сло-
вами, процессор будет разделяться между несколькими процессами.
Виртуальные команды ввода-вывода
471
На рис. 6.21 показана разница между реальной параллельной обработкой, когда
присутствует несколько физических процессоров, и смоделированной параллель-
ной обработкой, когда имеется всего один физический процессор. Даже если
параллельная обработка моделируется, удобно считать, что каждому процессу при-
писывается его собственный виртуальный процессор. При моделированной парал-
лельной обработке возникают те же проблемы, что и при реальной параллельной
обработке.
Процесс 3
Процесс 2
Процесс 1
Процесс 3
Процесс 2
Процесс 1
Процесс 3 находится
в состоянии ожидания
I
t
i
[ |
i i
i i
i i
i i
i i
i
i i i i
i
| |
i
Процесс 1 работает
Время
а
Время
б
Рис. 6 . 2 1 . Параллельная обработка с несколькими процессорами (а); моделирование
параллельной обработки путем переключения одного процессора с одного процесса на
другой (в данном случае всего три процесса) (б)
Формирование процесса
Программа должна работать как часть какого-либо процесса. Этот процесс, как и
все другие процессы, характеризуется состоянием и адресным пространством, че-
рез которое можно получить доступ к программам и данным. Состояние включает
как минимум счетчик команд, слово состояния программы, указатель стека и ре-
гистры общего назначения.
Большинство современных операционных систем позволяют формировать и
прерывать процессы динамически. Для формирования нового процесса требуется
системный вызов. Этот системный вызов может просто создать клон вызывающей
программы или позволить исходному процессу определить начальное состояние
нового процесса, то есть его программу, данные и начальный адрес.
В одних случаях исходный процесс сохраняет частичный или даже полный кон-
троль над порожденным процессом. Виртуальные команды позволяют исходному
процессу останавливать и снова запускать, проверять и завершать подчиненные
процессы. В других случаях исходный процесс никак не контролирует порожден-
ный процесс: после того как новый процесс сформирован, исходный процесс не
может его остановить, запустить заново, проверить или завершить. Таким обра-
зом, эти два процесса работают независимо друг от друга.
4 7 2
Глава 6. Уровень операционной системы
Состояние гонок
Во многих случаях параллельные процессы должны взаимодействовать, и их работу
нужно синхронизировать. В этом разделе мы рассмотрим синхронизацию и неко-
торые трудности, связанные с ней. Способы разрешения этих трудностей будут
представлены в следующем разделе.
Рассмотрим два независимых процесса, процесс 1 и процесс 2, которые взаимо-
действуют через общий буфер в основной памяти. Для простоты мы будем называть
процесс 1
производителем
(producer), а процесс 2 —
потребителем
(consumer).
Производитель выдает простые числа и помещает их в буфер по одному. Потреби-
тель удаляет их из буфера по одному и печатает.
Эти два процесса работают параллельно с разной скоростью. Если производи-
тель обнаруживает, что буфер заполнен, он переходит в режим ожидания, то есть
временно приостанавливает операцию и ожидает сигнала от потребителя. Когда
потребитель удаляет число из буфера, он посылает сигнал производителю, чтобы
тот возобновил работу. Если потребитель обнаруживает, что буфер пуст, он при-
останавливает работу. Когда производитель помещает число в пустой буфер, он
посылает соответствующий сигнал потребителю.
В нашем примере для взаимодействия процессов мы будем использовать коль-
цевой буфер. Указатели
in
и
out
будут использоваться следующим образом:
in
ука-
зывает на следующее свободное слово (куда производитель поместит следующее
простое число), a
out
указывает на следующее число, которое должен удалить по-
требитель.
Если
in=out,
буфер пуст, как показано на рис. 6.22,
а.
На рис. 6.22, б показа-
на ситуация после того, как производитель породил несколько простых чисел.
На рис. 6.22,
в
изображен буфер после того, как потребитель удалил из него не-
сколько простых чисел для печати. На рис. 6.22,
г — е
представлены промежуточ-
ные стадии работы буфера. Буфер заполняется по кругу.
Если в буфер было отправлено слишком много чисел и он начал заполняться
по второму кругу (снизу), а под
out
есть только одно слово (например, ш=52, а
out
=53), буфер заполнится. Последнее слово не используется; если бы оно исполь-
зовалось, то не было бы возможности сообщить, что именно значит равенство
in=out —
полный буфер или пустой буфер.
In,
out'
In-
Out-
In-
Out-
In-
Out-
In-*
Out-»
Out-
In-
б в г
Рис. 6.22. Кольцевой буфер