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

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

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

      Системы разделения времени обладают меньшей  пропускной способностью, чем системы  пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая «выгодна» системе. Кроме того, производительность системы снижается из-за возросших накладных расходов вычислительной мощности на более частое переключение процессора с задачи на задачу. Это вполне соответствует тому, что критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя. Вместе с тем мультипрограммное выполнение интерактивных приложений повышает и пропускную способность компьютера. Аппаратура загружается лучше, поскольку в то время, пока одно приложение ждет сообщения пользователя, другие приложения могут обрабатываться процессором. 
 

      6. Что такое метод  доступа? Какие функции относятся к методу доступа? 

      Метод доступа (accesse method)- метод, используемый для поиска в файле записи или  множества записей.

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

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

      В некоторых системах ускорение доступа к файлу  обеспечивается конструированием индекса файла. Индекс обычно хранится на том же устройстве, что и сам файл, и состоит из списка элементов, каждый из которых содержит идентификатор записи, за которым следует указание о местоположении данной записи. Для поиска записи вначале происходит обращение к индексу, где находится указатель на нужную запись. Такие файлы называются индексированными, а метод доступа к ним - доступ с использованием индекса.

      7. Обсудите понятие  относительного адреса  на диске. Каким  образом относительный  адрес дорожки  может быть преобразован  в абсолютный адрес? 

      Относительный адрес представляет собой частный случай логического адреса, когда адрес определяется положением относительно некоторой неизвестной точки (обычно — начало программы). В свою очередь, логический адрес представляет собой ссылку на ячейку памяти, не зависящую от текущего расположения данных в памяти, перед тем как получить доступ к этой ячейке памяти, необходимо транслировать логический адрес в физический. Физический или абсолютный адрес представляет собой действительное расположение нужной ячейки основной памяти. Если программа использует относительные адреса, это означает, что все ссылки на память в загружаемом процессе даны относительно начала этой программы. Для корректной работы программы требуется аппаратный механизм, который бы транслировал относительные адреса в физические в процессе выполнения команды, которая обращается к памяти. Когда процесс переходит в состояние выполнения, в специальный регистр процессора, иногда называемый базовым, загружается начальный адрес процесса в основной памяти. Кроме того, используется «граничный» (bounds) регистр, в котором содержится адрес последней ячейки в памяти программы. Эти значения заносятся в регистры при загрузке программы в основную память. При выполнении процесса встречающиеся в командах относительные адреса обрабатываются процессором в два этапа. Сначала к относительному адресу прибавляется значение базового регистра для получения абсолютного адреса. Затем полученный абсолютный адрес сравнивается со значением в граничном регистре. Если полученный абсолютный адрес принадлежит данному процессу, команда может быть выполнена; в противном случае генерируется соответствующее данной ошибке прерывание операционной системы.

      На  рис. 1.2. представлена схема, которая  обеспечивает возможность выгрузки и загрузки программ в основную память в процессе их выполнения, кроме того, образ каждого процесса ограничен адресами, содержащимися в базовом и граничном регистрах, и защищен от нежелательного доступа со стороны других процессов. 

                                                               Относительный адрес

                                                             Абсолютный адрес

                                            Прерывание

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

                                                                                                            Образ процесса в              

                                                                                                            основной памяти

Рис. 1.2. Аппаратная поддержка перемещения 

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

      Рассмотрим  методы, используемые при размещении файлов на диске, так как он оказывает  влияние на метод управления свободным  пространством.

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

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

1. Большие и непрерывные порции переменной длины. Обеспечивают лучшую производительность. Переменный размер помогает избежать наличия неиспользуемых участков, а таблицы размещения файлов имеют небольшой размер. Но при этом трудно организовывать повторное использование дискового пространства.
2. Блоки. Небольшие порции фиксированного размера обеспечивают большую гибкость. При этом могут потребоваться таблицы, имеющие больший размер или сложную структуру. Непрерывность отсутствует, а блоки для файла выделяются по необходимости.

      Существует  три метода размещения файлов: непрерывный, цепочечный и индексированный.

      При непрерывном размещении создаваемому файлу выделяется отдельное непрерывное множество блоков. Для каждого файла таблице размещения необходим только один элемент, определяющий начальный блок и длину файла. Выборка одиночного блока осуществляется так: например, если файл начинается с блока b, а искомый блок — i-й, то его местоположение на внешнем запоминающем устройстве определяется как b+i-1.

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

      При индексированном размещении в таблице  размещения файлов имеется отдельный  одноуровневый индекс для каждого файла. Индекс содержит по одной записи для каждой порции файла. Индексы файла сохраняются в отдельном блоке, и в элементе таблицы размещения файла имеется указатель на этот блок.

      В дополнение к таблице размещения файлов необходима таблица дискового размещения. Существует несколько реализаций.

      1. Битовые таблицы.

      Используется  вектор, содержащий  по одному биту для каждого блока диска. Каждый ноль соответствует свободному блоку, а каждая единица — используемому. Объем памяти в байтах, необходимой для битовой карты, определяется так:

      Размер  диска в байтах/8*Размер блока  файловой системы.

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

      2. Цепочки свободных порций.

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

      3. Индексирование.

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

      4. Список свободных блоков.

      Каждому блоку присваивается порядковый номер, а список номеров всех свободных  блоков содержится в зарезервированной  области диска.

      9. Что такое фрагментация  памяти? 

      При динамическом выделении памяти запросы  на выделение памяти формируются  во время исполнения задачи. Динамическое выделение противопоставляется  статическому, когда запросы формируются  на этапе компиляции программы. В итоге, и те, и другие запросы нередко обрабатываются одним и тем же алгоритмом выделения памяти в ядре операционной системы. Но во многих случаях статическое выделение можно реализовать намного более простыми способами, чем динамическое. Главная сложность здесь в том, что при статическом выделении кажется неестественной возможность отказаться от ранее выделенной памяти. При динамическом же распределении часто требуется предоставить возможность отказываться от запрошенных блоков так, чтобы освобожденная память могла использоваться для удовлетворения последующих запросов. Таким образом, динамический распределитель вместо простой границы между занятой и свободной памятью (которой достаточно в простых случаях статического распределения) вынужден хранить список возможно несвязных областей свободной памяти, называемый пулом или кучей.