1. Монолитное ядро (Monolithic kernel).

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

2. Многоуровневые системы (Layered system).

В этом случае ОС составляют набор модулей, образующих иерархию между интерфейсом пользователя и ПО.

5 интерфейс пользователя

4 управление вводом выводом

3 управление памятью

2 планирование задач

1 hardware

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

3. Микроядерная архитектура (МяА).

Микроядерная схема построений ОС отражает современные тенденции в разработке ОС и состоит в перенесении значительной части ОС на уровень пользования и минимизации ядра, при этом большинство составляющих ОС являются самостоятельными программами, и взаимодействие между ними обеспечивает специальный модуль ядра - микроядро. Микроядро обеспечивает взаимодействие между программами планирования и использования CPU, первичную обработку прерываний операций I/O и базовое управление памятью.

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

МяА ОС менее производительна, из-за необходимости формировать сообщения.

4. Смешанные системы

Из-за того, что рассмотренные подходы имеют свои достоинства и недостатки, современные ОС используют различные комбинации этих подходов. Ядро ОС Linux представляет собой монолитную систему с элементами МяА. При компиляции ядра размещается динамическая загрузка многих компонентов ядра, так называемых модулей .В момент загрузки модуля его код загружается на уровне системы. Другой пример смешанного подхода – это использование монолитного ядра под управлением МяА 4.4 BSD MkLinux. Микроядро обеспечивает управление Виртуальной Памятью и работу низкоуровневых драйверов. Все остальные функции, включая взаимодействие с прикладными программами , осуществляется монолитным ядром. Наиболее тесные элементы МяА элементы монолитного ядра переплетены в ядре Windows NT . Микроядро NT имеет размер > 1 Мб

Компоненты ядра NT располагаются в вытесняемой памяти и взаимодействуют друг с другом путём передачи сообщений, как и положено в микроядрных системах. И то же t компоненты ядра работают в одном адресном пространстве и исполняют общие структуры данных, что характерно для операций систем с монолитным ядром. Причина этого проста - микроядерная схема коммерчески невыгодна, т.к. неэффективна, поэтому NT называют гибридной ОС.

Состояния процесса.

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

Процесс, находящийся в состоянии «процесс исполняется» через некоторое t может быть завершён ОС или приостановлен и снова приведён в сост. «процесс не исполняется». Приостановка процесса происходит по двум причинам: для его дальнейшей работы потребовалось какое-то событие, напр., завершение операции I/O или истёк временной интервал, отведённый ОС для работы этого процесса. После того ОС по определённому алгоритму выбирает на исполнение один из процессов, находящихся в состоянии «процесс не исполняется» и переводит его в состояние «процесс исполняется». Новый процесс, появляющийся в системе первоначально помещается в состояние «процесс не исполняется». Это очень грубая модель и она не учитывает то, что процесс, выбранный для исполнения может всё ещё ждать событие из-за которого он был приостановлен и реально к выполнению не готов., поэтому состояние «процесс не исполняется» разбивается на 2 новых: готовность и ожидание.

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

1. ОС прекращает его деятельность

2. он не может продолжить свою работу, пока не произойдёт некоторое событие и ОС переведёт его в сост. ожидания

3. в результате возникновения прерывания в ОС

Эта новая модель хорошо описывает поведение процесса во t время его существования, но она не акцентирует внимание на появление процесса в системе и его исчезновении. Для полноты картины нужны ещё 2 состояния процессов:

• «рождение»

• «исполнение»

При рождении процесс получает в своё распоряжение адресное пространство, в кот. загружается программа подпроцесса, ему выделяется стек и системные ресурсы. Устанавливается начальные значения программного счётчика этого процесса и т.д. родившийся процесс переводится в сост. «готовность». При завершении своей деятельности процесс из сост. «исполнение» попадает в сост. «закончил исполнение». В конкретных ОС сост. процесса может быть ещё более детализированным, может появляется некоторые новые варианты переходов из 1 в др. сост.(напр. NT-7 различные состояния Linux-9 ), тем не менее все ОС подчиняются изложенной выше модели.

Операции над процессами.

Процесс не может перейти из одного сост. в др. самостоятельно. Изменением состояний процессов занимается ОС, совершая операции над ними. Кол-во таких операций совпадает с кол-вом стрелок на диаграмме состояний. Удобно соединить их в 3 пары:

1. создание процесса - завершение процесса;

2. приостановка (перевод из сост. «исполнение» в сост. «готовность») - запуск (из сост. «готовность» в сост. «исполнение»);

3. блокирование процесса (перевод из сост. «исполнение» в сост. «ожидание»)- разблокирование (ожидание-готовность);

Существует ещё 1 операция, не имеющая пару: изменение приоритета процесса. Операции создания и завершения процесса являются одноразовыми, т. к. применяются к процессу не более 1 раза. Все остальные операции, связанные с изменением сост. процесса (запуск или блокировка), как правило, являются многоразовыми.

Process Control Block и контекст процесса.

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

1. состояние, в котором находится процесс;

2. программный счётчик процесса, т.е. адрес команды, кот. д.б. выполнена следующей;

3. содержимое регистров процессора;

4. данные, необходимые д./планирования и использования процессора и управления памятью; (приоритет процесса, расположение адресного пространства и т.д.)

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

6. сведения об устройствах I/O, связанных с процессом;

Состав этой структуры, ее строение зависят от конкретной ОС. Во многих ОС информация, характеризующая процесс, хранится не в одной, а в нескольких связанных структурах данных. Эти структуры могут иметь различные наименования, содержать дополнительную информацию или наоборот, лишь часть описанной информации. Важно то, что для люб. процесса вся информация, необходимая для совершения операции над ними, доступна ОС. Для простоты считаем, что она хранится в одной структуре данных, называемой process control block, или блоком управления процесса. Он является моделью процесса для ОС. Каждая операция производимая ОС над процессом вызывает определенные изменения РСВ. В рамках принятой модели состояния процессов содержимое РСВ остается постоянным. Информацию в РСВ удобно разделить на две части. Содержимое всех регистров процессора, включая значение программного счетчика, называется регистровым контекстом процесса, а все остальное – системным контекстом процесса. Знание регистрового и системного контекста процесса достаточно для того, чтобы управлять его работой в ОС, совершая над ним операции. Однако, этого недостаточно, чтобы полностью охарактеризовать процесс. ОС не интересуют какими именно вычислениями занимается процесс, т.е. какой код, какие данные находятся в его адресном пространстве. С точки зрения пользователя, наоборот: наибольший интерес представляет содержимое адресного пространства – программы, определяющие последовательность преобразования данных и полученные результаты.

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

Одноразовые операции.

Жизненный путь процесса в ПК начинается с его рождения. Любая ОС, поддерживающая концепцию процесса, должна обладать средствами для их создания. В очень простой системе все процессы могут быть порождены на этапе стандартных систем. Более сложные ОС создают процессы динамически по мере их необходимости. Инициатором могут выступать либо процесс пользователя, совершивший специальный системный вызов, либо сама ОС, т.е. тоже некоторый процесс. Процесс, инициировавший создание нового процесса, называется процессом родительским, а вновь созданный потомком. Процессы потомки могут в свою очередь порождать потомков, образуя в общем случае внутри системы набор генеалогических деревьев процесса – генеалогический лес. Все пользовательские процессы вместе с некоторыми процессами ОС принадлежат одному и тому же дереву этого процесса. Система заводит новый РСВ при рождении с названием «рождение» и начинает его заполнять. Новый процесс получает свой идентификационный номер. Так как для хранения этого номера отводится определенное количество битов, то число одновременно существующих процессов в ОС ограничено. Обычно, для выполнения своих функций, процесс-потомок требует ресурсов (памяти, файлов). Существует два подхода к их выделению. Новый процесс может получить в свое распоряжение, некоторую часть родительских ресурсов, разделяя с процессом-родителем и другими процессами-потомками права на них. Или может получить свои ресурсы непосредственно от ОС. Информация у выделенных ресурсов заносится в РСВ. После наделения их ресурсами необходимо занести в его адресное пространство программный код, значение данных, установить программный счетчик. Здесь также существует два решения:

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

2. потомок загружается новой программой из какого-либо файла

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

VAX/VMS допускает WIN NT – возможны оба варианта.

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

Многоразовые операции.

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

Действия при выполнении многоразовых операций над проц.:

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

2. Приостановка процесса: работа процесса, находящегося в состоянии исполнения, останавливается в результате какого-либо прерывания; процессор автоматически сохраняет программный счетчик и нужные регистры, стеки этого процесса, а затем передает управление по его специальному адресу обработки данного прерывания. По этому адресу располагается одна из частей ОС; она сохраняет динамическую часть системного и регистрового процесса в его РСВ, переводит процесс в состояние «готовность» и приступает к обработке прерывания, т.е к выполнению действий, связанных с возникновением прерывания.

3. Блокирование процесса: процесс блокируется, когда он не может продолжить работу, не дождавшись какого-либо события в вычислительной системе. Для этого он обращается к ОС с помощью определенного системного вызова. ОС обрабатывает системный вызов (инициализирует операцию ввода-вывода, I/O добавляет в очередь процессов и т.д.) и при необходимости, сохранив нужную часть контекста процесса, переводит ее в состояние ожидания.

4. Разблокирования процесса: после возникновения в системе какого-либо события ОС нужно определить какое точно событие произошло. Затем ОС проверит, находится ли некоторый процесс в состоянии ожидания для данного события. Для находящегося переводит его в состояние «готовность»  действие.

Переключение контекста.

Деятельность мультипрограммной ОС состоит из цепочек, выполняемых над различными процессами и сопровождающихся переключением процессов с одного на др. Для корректного переключения процессов с одного на другой необходимо сохранить контекст исполнявшегося процесса и восстановить контекст процесса, на который будет переключен процесс. Такая процедура сохранения и восстановления работоспособности процесса называется переключением контекста. Время, затраченное на ПК, представляет собой накладные расходы, снижающие производительность системы и колеблется от 1 до 1000 мкс. Существенно сократить эти накладные расходы в современных ОС позволяет расширенная модель процесса, включается понятия threads of execution (Потоки (нити) исполнения).

Заключение.

Понятие процесса характеризует некоторая совокупность набора исполняющихся программ, ассоциированных с ним ресурсов и текущего момента его выполнения, находящегося под управлением ОС. В любой момент процесс полностью описывается своим контекстом; состоит из регистровой, системной и пользовательской частей. В ОС процессы представляются в РСВ (регистровый и системный контекст). Процессы могут находится в 5 основных состояниях: рождение, готовность, исполнение, ожидание, закончил исполнение.

Из состояния в состояние процесс переводит ОС в результате выполнения над ними операций. ОС может выполнять след. операции:

• создание процесса

• завершение процесса

• простановка процесса

• запуск процесса

• блокирование процесса

• разблокирование процесса

• изменение приоритета процесса

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

Лекция №3

Планирование процесса.

Существует 2 вида планирования:

• планирование заданий

• планирование использования процесса

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

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

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

Решение о выборе для запуска того или иного процесса оказывает влияние на функционирование ВС на протяжение достаточно длительного времени. Поддержание разумного количества процессов осуществляется за счет ограничения количества пользователей. Планирование использования CPU применяется в качестве краткосрочного планирования процесса. Оно проводится, к примеру, при обращении исполняющегося процесса к устройствам I/O или просто по завершении определенного интервала времени. Поэтому кратковременное планирование осуществляется как правило не реже 1-го раза в 100 м/сек. Выбор нового процесса для использования оказывает влияние на функционирование системы до поступления очередного аналогичного события, т.е. в течении короткого промежутка времени, чем и обусловлено название этого уровня планирования – краткосрочного.

Иногда бывает выгодно для повышения производительности временно удалить какой-либо частично выполнившейся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения. Такая процедура получила название СВОПИНГ.

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

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

2. Эффективность - постараться занять CPU на 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных ВС загрузка CPU колеблется от 40% до 95%.

3. Сокращение полного времени исполнения (turnaround time)- обеспечить минимальное время между стартом процесса и его завершением.

4. Сокращение времени ожиданий (waiting time) – сократить время, которое проводят процессы в состоянии готовность и задание в очереди для загрузки.

5. Сокращение времени отклика (response time) - минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

Независимо от поставленных целей, алгоритмы должны обладать следующими свойствами:

1. Быть предсказуемыми. Одно и тоже задание должно выполняться примерно за одно и то же время. Применение алгоритма планирования не должно приводить к примеру извлечению за сотые доли секунды при одном запуске и за несколько суток при втором запуске.

2. Быть связаны с минимальными накладными расходами. Если на 100 мс на определение того какой именно процесс будет выполнятся, то такой алгоритм очевидно применять не надо.

3. Равномерно загружали ресурсы ВС, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы.

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

Многие из приведенных выше целей и свойств являются противоречивыми.

Параметры планирования.

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

• статические параметры

• динамические параметры

Статические параметры не изменяются в ходе функционирования системы. Динамические параметры подвержены постоянным изменениям.

К статическим параметрам ВС относят предельные значения её ресурсов (размер оперативной памяти, максимальное количество устройств I/O, т.п.). Динамические параметры системы описывают количество свободных ресурсов на данный момент. К статическим параметрам процессов относят характеристики, как правило, присущие заданиям уже на этапе загрузки. Выделяют:

1. владелец процесса – пользователь, запустивший задание

2. приоритет выполнения процесса

3. запрошенное время CPU

4. соотношение времени CPU и времени, необходимого для операции I/O.

5. ресурсы ВС (оперативная память, устройство I/O, специальные библиотеки и системные программы) и их количество, необходимое задаче.

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

Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процесса.

Для среднесрочного планирования в качестве таких характеристик используется следующая информация:

1. сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную память;

2. сколько оперативной памяти занимает процесс;

3. сколько времени CPU уже предоставлено процессу.

Для краткосрочного планирования используется ещё 2 динамических параметра. Деятельность любого процесса можно представить как последовательность циклов использования CPU и ожидания завершения операции I/O.

Промежуток времени непрерывного использования CPU носит название CPU burst.

Промежуток непрерывного ожидания I/O - I/O burst.

Значение продолжительности последних и очередных CPU burst и I/O burst является важным динамическим параметром процесса.

Вытесняющее и невытесняющее планирования.

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

1. Процесс переводится из состояния исполнения в состояние завершил исполнение;

2. Процесс переводится из состояния исполнения в состояние ожидания;

3. Процесс переводится из состояния исполнения в состояние готовность (например после прерывания по таймеру);

4. Процесс переводится из состояния ожидания в состояние готовность(например завершилась операция I/O или произошло другое событие).

В случаях 1 и 2 процесс, находящийся в состоянии исполнения, не может дальше исполняться и необходимо выбрать для исполнения новый процесс.

В случаях 3 и 4 планирование может не проводится. Процесс, который исполняется до прерывания может продолжать своё выполнение после обработки прерывания.

Если планирование осуществляется только в случаях 1 и 2, говорят, что имеет место невытесняющее планирование (non preemptive). В противном случае, говорят о вытесняющем планировании.

Термин “вытесняющее планирование” возник т.к. исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнения другим процессом

Невытесняющее планирование используется в ОС Apple Macintosh. При таком режиме планирования процесс может занимать столько времени CPU, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания, завершения операции I/O или по окончании работы). Этот метод планирования процесса относительно просто реализуется и достаточно эффективен, т.к. позволяет до минимума сократить затраты на переключение контекста и выделить большую часть времени CPU для работы самых необходимых процессов. Однако при невытесняющем планировании возникает проблема возможности полного захвата CPU одним процессом, который, вследствие каких-либо причин, например из-за ошибки в программе зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей ВС.

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

Алгоритмы планирования.

First Come First Served (первый пришёл первого обслужил).

Простейшим алгоритмом планирования является алгоритм, который называется FCFS.

Пусть процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, ссылка на его РСВ помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его РСВ. Очередь подобного типа имеет в программировании специальное название – First In First Out (FIFO). Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в своё распоряжение CPU занимает его до истечении текущего времени непрерывного использования (CPU burst). После этого для выполнения выбирается новый процесс из начала очереди. Преимуществом алгоритма FCFS является лёгкость его реализации. Недостатком является то, что среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процесса в очереди.

Если есть процесс с длительным временем непрерывного выполнения (CPU burst), то короткие процессы, перешедшие в состояние готовности, будут долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени, т.к. среднее время отклика в интерактивных процессах получается слишком большим.

Round Robin(RR).

Модификацией алгоритма FCFS является алгоритм RR. По сути это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить всё множество готовых к исполнению процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс, находящийся около CPU в небольшой фиксированный квант времени, обычно 10-100 мс. Пока процесс находится рядом с CPU, он получает CPU в своё распоряжение и может исполнятся.

Реализуется такой алгоритм так же, как и предыдущий (FCFS) с помощью организации процессов, находящихся в состоянии готовность в очереди FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. На производительность алгоритма сильно влияет величина кванта времени. При больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создаётся иллюзия того, каждый из n процессов работает на собственном виртуальном CPU с производительностью 1/N от производительности реального CPU. В реальных условиях при слишком малых величинах кванта времени и, соответственно, слишком частом переключении контекста накладные расходы на переключения резко снижают производительность системы.

Shortest Job First (SJF).

В алгоритмах FSFC и RR существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи, расположенные в очереди ближе к её началу, то общая производительность этих алгоритмов значительно возрастает. При известных длительностях выполнения процессов (CPU burst), находящихся в состоянии готовности, может выбраться для исполнения не процесс из начала очереди, а процесс с минимальной длительностью исполнения (CPU burst). Если таких процессов 2 или больше, то для выбора одного из них может использоваться алгоритм FSFC. Квантование времени при этом не применяется. Описанный алгоритм получил название “кратчайшая работа выполняется первой”. SJF – это алгоритм краткосрочного планирования. Он может быть вытесняющим и невытесняющем. При невытесняющем SJF планировании CPU предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в ВС. При вытесняющем SFJ планировании учитывается появление новых процессов в очереди готовых к исполнению во время работы выбранного процесса. Если CPU burst нового процесса меньше, чем у исполняющегося, то исполняющийся процесс вытесняется новым.

Основная cложность при реализации алгоритма SJF - невозможность точного знания времени, очередного CPU burst для исполняющихся процессов. В пакетных системах количество времени CPU, необходимое для процесса, указывает пользователь при формировании заданий и может брать эту величину для осуществления долгосрочного SJF-планирования. При краткосрочном планировании может делать только прогноз длительности следующего промежутка CPU burst, исходя из предысторий работы процессов. Для подсчёта новой оценки нужно взять старую оценку, сложить с измеренным временем текущего промежутка CPU burst и полученную сумму разделить на 2. Полученная оценка применяется как продолжительность очередных промежутков времени непрерывного использования CPU для краткосрочного SJF планирования.

Гарантированное планирование

При интерактивной работе N пользователей можно применить алгоритм гарантированного планирования, который гарантирует, что каждый из пользователей будет иметь в своем пользовании 1/N части процессорного времени. Для каждого пользователя с номером i вводятся две величины T_i – время нахождения пользователя в системе и τ_i – суммарное время CPU burst, выделенное всем процессам, в течении сеанса данного пользователя.

Справедливо для пользователя было бы получение T_i/N процессорного времени. Если τ_i << T_i/N, то i-й пользователь несправедливо обделен процессорным временем, если неравенство выполняется наоборот, то он получает чрезмерно много процессорного времени.

Для каждого пользователя вычисляется коэффициент справедливости и очередной квант процессорного времени предоставляться процессу с наименьшей величиной этого отношения. Этот алгоритм называется алгоритмом гарантированного планирования.

К недостаткам этого алгоритма можно отнести невозможность предугадать поведение пользователя.

Приоритетное планирование.

При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым, ему выделяется CPU.

Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем выше приоритет процесса. Принципы назначения приоритета могут опираться на внутренние критерии ВС и на внешние по отношению к ним. Внутренние используют различные количественные и качественные характеристики процесса для вычисления его приоритета. Это может быть, например, определенные ограничения по CPU burst, требования к размеру памяти, число открытых файлов и используемых устройств I/O. Внешние критерии исходят из таких параметров, как важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и других политических факторов. Планирование с использованием приоритетов может быть вытесняющем и невытесняющем. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом. В случае невытесняющего планирования он просто ставится в начало очереди готовых процессов. Если приоритеты процессов с течением времени не изменяются, они называются статическими. Механизмы статической приоритетности легко реализовать, однако они не реагируют на изменение ситуации в ВС, которые смогут делать корректировку порядка исполнения процессов. Более гибким являются динамическое планирование приоритетов процессов, изменяющих свои значения по ходу исполнения процессов. Начальные значения динамического приоритета, присвоенное процессу, действуют в течении короткого периода времени, после чего ему назначается новое более низкое значение. Как правило, изменение приоритета процесса проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке и блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примеры алгоритмов с динамическими приоритетами являются алгоритмы SJF и алгоритм гарантированного планирования. Схема с динамической приоритетностью гораздо сложнее в реализации и связывает с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением работы системы.

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределённо долгое время. Решение этой проблемы может быть достигнуто с помощью увеличения со временем приоритета процесса., находящегося в состоянии готовности. Изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз по истечении определенного промежутка времени значение приоритетов готовых процессов уменьшается на единицу. Процессу, побывавшему в состоянии исполнения, присваивается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки буде предоставлено право на исполнение.

Многоуровневые очереди (Multilevel Queue).

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

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

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue).

Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из одной очереди в другую, в зависимости от своего поведения . Пусть процессы в состоянии готовность организованы в 4 очереди. Планирование процесса между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше располагается очередь, тем выше её приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для исполнения, пока есть хоть один процесс в очередях 0 и 1. Если при работе процесса появляется другой процесс какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым. Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в своё распоряжение квант времени размером 8 единиц.

Если продолжительность его времени непрерывного выполнения меньше этого кванта времени, процесс остаётся в очереди 0, в противном случае он переходит в очередь 1.

Для процессов из очереди 1 квант времени имеет величину 16, если процесс не укладывается в это время, то он переходит в очередь 2, если укладывается, то остаётся в очереди 1 В очереди 2 величина кванта времени = 32 ед. Если для неправильной работы процесса и этого мало процесс поступает в очередь 3, и для которых квантование времени не применяется. Чем больше значение продолжительности времени непрерывной работы процесса, тем в менее приоритетную очередь он попадет, но тем на большее процессорное время он может рассчитывать. Таким образом через некоторое время все процессы, требующие мало времени и работы процессора окажутся разными в высоко приоритетных очередях, а все процессы требующие большого счёта – низкого приоритета.

Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1-2 и 3 могут перемещаться в очередь 0. После завершения дисковых операций, процессы из очередей 2 и 3 могут перемещаться в очередь 1, а после завершения ожидания всех других событий из очереди 3 в очередь 2.

Перемещение процессов из очереди с низким приоритетом в очередь с высоким приоритетом позволяет более полно учитывать изменение поведения процессов с течением времени.

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

1. Количество очередей для процесса находящихся в состоянии готовности;

2. Алгоритм планирования действий между очередями;

3. Алгоритмы планирования, действующие внутри очередей;

4. Правило помещения родившегося процесса в одну из очередей;

5. Правило перевода процесса из одной очереди в другую.

Заключение.

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

Простейшим алгоритмом планирования является не вытесняющий алгоритм FCFS, который, однако, может существенно задержать короткие процессы, перешедшие в состояние готовности. В системах разделения времени широко применяется вытесняющая версия этого алгоритма (RR).

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

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

Лекция№4

Взаимодействие процессов.

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

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

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

3. Реализация модульной конструкции системы. Примером может служить микроядерный способ построения ОС. Когда различные её части представляют отдельные процессы, взаимодействующие путём передачи сообщений через микроэлемент (микроядро).

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

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

Процессы могут взаимодействовать друг, с другом только обмениваясь информацией. По объёму предаваемой информации и степенью воздействия на поведение другого процесса взаимодействия можно разделить на 3 категории:

1. Сигнальная. Передаётся минимальное количество информации 1 бит, да или нет. Используется, как правило, для извещения процесса о наступлении какого либо события. Степень воздействия на поведение процесса полученного информацию минимальную. Всё зависит от того, знает ли он, что означает полученный сигнал, надо ли на него реагировать и каким образом.

2. Канальная. “Общение” процессов происходит через линии связи предоставленной ОС. Объём передаваемой информации в 1 времени ограничен пропускной способностью линей связи. С увеличением количества информации возрастает и возможность влияния на поведение другого процесса.

3. Разделяемая память. 2 или более процесса могут совместно использовать некоторую область адресного пространства. Созданием разделяемой памятью занимается ОС. Использование разделяемой памяти для передачи и получении информации осуществляется с помощью средств обычных языков программирования, в то время как в сигнальным и канальным средствам коммуникации, для этого необходимы специальные системные вызовы. Разделяемая память представляет собой наиболее быстрый способ взаимодействия процессов в одной ВС.

Логическая организация средств коммуникации, таких как шина данных, прерывания, аппаратно разделяемая память определяет механизм их использования. Для характеристики любого способа связи необходимо знать 2 момента:

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

2. Способ адресации при использовании средств связи. Т.е. необходимо указать, куда передавать информацию и откуда её получать. Различают 2 способа адресации: прямую и непрямую. При прямой адресации взаимодействующие процессы, непосредственно общаются друг с другом, явно указывая номер или имя процесса которому предназначена информация и от какого она должна быть получена.

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

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

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

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

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

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

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

В коммутационных системах принято называть однонаправленную связь симплексной, двунаправленную связь с поочерёдной передачей информации в разных направлениях – полудуплексной, а двунаправленную связь с возможностью одновременной передачи информации в разных направлениях – дуплексной.

Прямая и непрямая адресация не имеет непосредственного отношения к направленности связи.

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

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

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

Существует 2 модели передачи данных по каналам связи, поток I/O и сообщения.

При передачи данных с помощью потоковой модели операции передачи и приема информации не интересуется содержимым данных. Данные представляют собой простой поток байтов без какой-либо интерпретации их со стороны системы. Примеры потоковых каналов связи: PIPE, FIFO.

Один из наиболее простых способы передачи информации между процессами по линии связи является передача информации через PIPE (канал, труба, конвейер).

Информация о расположении каналов в ОС обладает только процесс их создавший. Этой информацией он может поделиться только со своими наследниками – процессами-потомками. Поэтому использовать канал для связи могут только родственные процессы, имеющие общего предка. Однако, если разрешить процессу, создавшему канал, сообщать о его местонахождении в системе другим процессам (например зарегистрировав его в ОС под определенным именем), то полученный объект принято называть именованным каналом – FIFO(named pipe). Именованный канал может использоваться для организации связи между любыми процессами в системе.

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

В ВС используются разнообразные средства связи для передачи сообщений: очереди сообщений, sockets (гнезда).

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

Способ коммуникации называется надежным если при обмене данными выполняются 4 условия:

1. Не происходит потери информации;

2. Не происходит повреждения информации;

3. Не появляется лишней информации;

4. Не нарушается порядок данных в процессе обмена.

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

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

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

Вместо контрольной суммы можно использовать специальное кодирование передаваемых данных с помощью кодов исправляющих ошибки. Такое кодирование позволяет при числе искажений не превышающих некоторое значение восстановить первоначальные неискаженные данные.

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

Для гарантии правильности порядка получения сообщений они нумеруются. При приеме сообщения с номером несоответствующим ожидаемому с ним поступают как с утерянным и ждут сообщения с правильным номером. Подобные действия могут быть возложены на:

1. На ОС;

2. На процессы, обменивающиеся данными;

3. Совместно на ОС и процессы, разделяя их ответственность.

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

Потоки. Нити исполнения.

Логическая реализация относится к средствам связи ориентированным на организацию взаимодействия различных процессов. Однако, усилия, направленные на ускорение решения задач в классических ОС привели к появлению совершенно иных механизмов, к изменению самого понятии процесса.

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

Ввести массив А

Ввести массив В

Ввести массив С

А=А+В

С=А+С

Вывести массив С

При выполнении такой программы в рамках одного процесса этот процесс будет 4 раза блокироваться ожидая окончания операции ввода/вывода. Но этот алгоритм обладает внутренним параллелизмом. Вычисление суммы массивов А+В можно было бы выполнять параллельно с ожиданием окончания операции ввода массива С. Такое совмещение операций можно реализовать использую два взаимодействующих процессов. Для простаты считаем что процессы взаимодействуют через разделяемую память.

Процесс 1 Процесс 2

Создать процесс

Переключение контекста

Выделение общей памяти

Ожидание ввода А и В

Переключение контекста

Выделение общей памяти

Input A

Wait end of i/o

Input b

Wait end of i/o

Input C

Wait end of i/o

Переключение контекста

А=А+В

Переключение контекста

С=А+С

Output C

Wait end of i/o

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

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

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

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

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

Различают ОС поддерживающие нити на уровне ядра и на уровне библиотеки. ОС поддерживающая нити на уровне ядра использует планирование CPU в терминах нити а управление памятью и другими ресурсами остается в терминах процесса. В ОС поддерживающей нити на уровне библиотек пользователей и планирование CPU и управление ресурсами осуществляется в терминах процесс. Распределение использования CPU по нитям в рамках выделенного CPU временного интервала осуществляется средствами библиотеки. В подобных системах блокирование нити приводит к блокированию всего процесса. Т.к. ядро системы не имеет представления о существовании нити, то в таких ВС просто имитируются наличие нитей исполнения.

Управление памятью.

Деятельность ОС по распределению памяти между пользовательскими процессами и компонентами ОС называется управлением памятью, а часть ОС, которая отвечает за управление памятью называется менеджером памяти.

Физическая память.

Запоминающее устройство компьютера разделяют как минимум на 2 уровня:

1. Основную ( главную, оперативную, физическую);

2. Вторичную (внешнюю).

Основная память представляет собой упорядоченный массив однобайтовых ячеек, каждая из которых имеет свой уникальный адрес (номер ячейки). CPU извлекает команду из ОП декодирует ее и выполняет. Для выполнения команды могут потребоваться обращения еще к нескольким ячейкам ОП. Обычно ОП изготавливают с применением полупроводниковых технологий и она теряет свое содержимое при отключении питания.

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

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

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

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

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

Логическая память.

Аппаратная организация памяти в виде линейного набора ячеек не соответствует представлениям программиста о том как организуется хранение программ и данных.

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

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

Оказалось удобным размещать в разных сегментах различные компоненты процесса ( код программы, данные, стэк и т.д.). Контролировать характер работы с конкретным сегментом можно, приписав ему атрибут, например, право доступа или типы операций, которые можно производить с данными, хранящимися в сегменте.

Большинство современных ОС поддерживают сегментную организацию памяти. В некоторых архитектурах, например Intel, сегментация поддерживается оборудованием. Адреса, к которым обращается процесс отличается от адресов реально существующих в ОП. В каждом конкретном случае, использованные программой адреса могут быть представлены различными способами. Например, адреса в исходных текстах обычно символьные. Компилятор связывает эти символьные адреса с перемещаемыми адресами ( такими как n байт от начала модуля).

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

Логическое и физическое адресные пространства не по организации не по размеру не соответствуют друг другу. Максимальный размер логического адресного пространства обычно определяется разрядностью процессора, например 2³² и в современных системах значительно превышает размер физического адресного пространства. Следовательно CPU и ОС должны быть способны отобразить ссылки в ходе программы в реальные физические адреса соответствующие текущему расположению программы в основной памяти. Такое отображение адресов называют трансляцией адреса (привязкой или связыванием адресов).

Связывание логического адреса порожденного оператором программы с физическим должно быть осуществлено до начала выполнения оператора или в момент его выполнения.

Функции системы управления памятью.

Чтобы обеспечить эффективный контроль использования памяти ОС должна выполнять следующие функции:

• Отображение адресного пространства процесса на конкретных областях физической памяти;

• Распределение памяти между конкурирующими процессами;

• Контроль доступа к адресному пространству процесса;

• Выгрузка процессов (целиком или частично) во внешнюю память, когда в ОП недостаточно места;

• Учет свободной и занятой памяти

Схема с фиксированными разделами.

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

Для выбора раздела используются 3 стратегии:

1. Стратегия первого подходящего (First fit). Т.е. процесс помещается в первый подходящий по размеру раздел.

2. Стратегия наиболее подходящего (Best fit) процесс помещается в тот раздел где после его загрузки останется меньше всего свободного места

3. Стратегия наименее подходящего (Worst fit). При помещении в самый большой раздел в нем остается достаточно места для размещения еще одного процесса.

Исследования показали, что доля полезно использованной памяти в первых двух случаях больше, чем в третьем , при этом первый способ несколько быстрее.

Перечисленные стратегии широко применяются и другими компонентами ОС, например для размещения файлов на диске.

Недостатки этой схемы:

1. число одновременно выполняемых процессов ограничено числом разделов

2. схема страдает от внутренней фрагментации – потери части памяти, выделенной процессу но не используемой им. Фрагментация возникает, т.к. процесс не полностью занимает выделенный ему раздел или потому что некоторые разделы слишком малы для выполнения пользовательских программ.

Частный случай схемы с фиксированными разделами это работа менеджера памяти однозадачной ОС. В памяти размещается один пользовательский процесс и остается определить, где будет располагаться пользовательская программа по отношению к ОС, в верхней, нижней или средней части памяти. Главным фактором, влияющим на это решение – это расположение вектора прерывания, который обычно размещен в нижней части памяти, поэтому процесс чаще всего оказывается в нижней части памяти. Пример такой системы MS-DOS.

Защита адресного пространства ОС от пользовательской программы может быть организована при помощи одного граничного регистра содержащего адрес границы ОС.

Оверлейная структура (Overlay).

В случае когда размер логического адресного пространства процесса может быть больше чем размер выделенного ему раздела или больше самого большого раздела, иногда используется техника называемая Overlay или организация структуры перекрытием.

Основная идея - держать в памяти только те инструкции программы которые нужны в данный момент.

Организация структуры с перекрытием:

Program A Subroutine C

…… ……

Call B Call D

…… ……

Call C Call E

Можно поочередно загружать в память ветви АВ, АСD, ACE в программу. Коды ветвей Overlay структуры находятся на диске как абсолютные образы памяти и считываются деревьями Overlay при необходимости.

Для описания Overlay структуры используются специальный язык. (Overlay Description Language (ODL)) Совокупность файлов использующие программы заполняются файлами с расширением *.odl, описывающих дерево вызовов внутри программы A – (B,C) C – (D,Е).

В современных 32-х разрядных системах, где виртуальное адресное пространство измеряется гигабайтами проблемы с нехваткой памяти решаются другими способами.

Динамическое распределение – Swapping.

В системе с разделением времени возможна ситуация, когда память не в состоянии содержать все пользовательские процессы приходиться прибегать к (swapping) перемещение процесса из главной памяти на диск и обратно целиком. Частичная выгрузка процессов на диск осуществляется в системах со страничной организацией (paging). Swapping не имеет непосредственного отношения к управлению памятью, скорее он связан с подсистемой планирования процессов. Время переключения контекста, время выгрузки может быть сокращено за счет организации специально отведенного пространства на диске. Раздел для Swapping. Обмен с дисками осуществляется блоками большего размера, т.е. быстрее чем через стандартную файловую систему. Система Swapping может базироваться на фиксированных разделах. Более эффективной является схема с переменными разделами, которая используется в тех случаях когда все процессы целиком помещены в память, т.е. в отсутствие Swapping. В этом случае вначале вся память свободна и не разделена на разделы. Вновь поступающей задаче выделяется строго необходимое количество памяти. После выгрузки процесса память освобождается. По истечении некоторого времени память представляет собой переменное число разделов разного размера смежные свободные участки могут быть объединены. Этот метод более глубок по сравнению с методом фиксированных разделов однако ему присуща внешняя фрагментация, т.е. наличие большого числа фрагментов не использующих памяти не выделяемой ни одному процессу. Статистический анализ показывает, что пропадает примерно 1/3 памяти.

Страничная память.

В современных системах управления памятью не принято размещать процесс в оперативной памяти одним непрерывным блоком. В самом простом и наиболее распространённом случае в страничной организации памяти, как логическое так и физическое адресное пространство представляется состоящим из набора блоков или страниц одинакового размера. При этом образуется логические страницы (Page), а соотношение единицы физической памяти называют (страничными кадрами) (page frames). Страницы и страничные кадры имеют фиксированную длину, являются степенью числа 2. каждый кадр содержит одну страницу данных. При такой организации внешняя фрагментация отсутствует, а потерь из-за внутренней фрагментации ограничиваются последней страницей процесса. Логический адрес в страничной системе это упорядоченная память (p:d), где p – номер страницы в виртуальной памяти, а d – смещение в рамках страницы р на которой размещен адресный элемент.

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

Связь логических и физических адресов при страничной организации файлов.

Система отображения логических адресов в физические сводиться к системе отображения логических страниц в физические и представляет собой таблицу страниц, которая хранится в оперативной памяти. Интерпретация логического адреса …. Если выполняется процесс обращения к логическому адресу V(p:d). Механизм отображения ищет номер страницы р в таблице страниц определяет, что эта страница находиться в страничном кадре р’; формирует реальный адрес из р’ и d. Таблица страниц адресуется при помощи специальных регистров процесса и позволяет определить номер кадра по логическому адресу. Помимо этой задачи при помощи атрибутов записываются в строке таблицы страниц организуется контроль доступа конкретной страницы и её защита. Процесс пользователя не имеет возможности адресовать память за пределами своей таблицы страниц, который включают только его собственные страницы. Для управления физической памятью ОС создаёт таблицу кадров, она имеет одну запись на каждый физический кадр показывающая его состояние.

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

Существует 2 других схемы организации управления памятью:

1) сегментная: может иметь переменный размер (в отличии от страничной). При сегментной организации виртуальный адрес по прежнему является двумерным и состоит из двух полей: номера сегмента и смещение внутри сегмента. Однако, в отличии от страничной организации, где линейный адрес преобразуется в двумерной ОС для удобства отображения здесь двухмерность адреса является следствием представления программиста о процессе не в виде линейного массива байт, а как набор сегментов переменного размера (данные о стеке).

Программисты пишущие на языках низкого уровня должны явным образом менять значения сегментных регистров. Логическое адресное пространство это набор сегментов, каждый сегмент имеет имя, размер и другие параметры (уровень привилегий, разрешенные виды обращений, флаги присутствия). В отличии от страничной схемы, где пользователь задаёт только один адрес, который разбит на номер страницы и смещение в сегментной схеме, пользователь определяет каждый адрес двумя величинами: именем сегмента и смещение. Каждый сегмент это линейная последовательность адресов начиная с нуля. Максимальный размер сегмента определяется разрядностью процессоров. Размер сегмента может изменяться динамически. В элементе таблицы сегментов помимо физического адреса начала сегмента содержится и его длина, если размер смещения виртуального адреса выходит за пределы размера сегмента, возникает прерывание. Логический адрес это упорядоченная пара, номер сегмента и смещение внутри него. Система где сегмент поддерживаются аппаратно эти параметры хранятся в таблице дескриптора сегмента и программа обращается к этим дескрипторам по номерам, эти номера называются селектора. При этом контекст каждого процесса входит набор сегментных регистров, содержащие селекторы текущих сегментов кода, стека и данных. И определено какие сегменты будут использоваться при разных видах обращения к памяти. Это позволяет процессу уже на аппаратном уровне определять допустимость обращений к памяти упрощая реализацию защиты информации от несанкционированного доступа.

Аппаратная поддержка сегментов используется в основном на процессорах Intel. В большинстве ОС сегментация реализована на программном уровне, т. К. хранить сегменты большого размера целиком неудобно, то они разбиваются на страницы.

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

1. Таблица сегмента связывает номер сегмента с таблицей страниц.

2. Отдельная таблица страниц для каждого сегмента.

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

Виртуальная память.

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

1) занимаемая процессом память разбивается на несколько частей, например страниц.

2) логический адрес, т. е. логическая страница к которой обращается процесс динамически транслируется в физический адрес.

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

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

1. Программа не ограничена объемом физической памяти. Это упрощает разработку программы, т.к. можно задействовать больше виртуального пространства, не заботясь о размере используемой памяти.

2. Поскольку появляется возможность частичного помещения программы в память и гибкого перераспределения памяти между программами, можно разместить в памяти больше программ, что увеличит загрузку CPU и пропускную способность системы.

3. Объём I/O для выгрузки части программы на диск может быть меньше чем в варианте классического Swapping. Итоге каждая программа будет работать быстрее.

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

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

В системе виртуальной памяти те адреса, которые генерирует программа, называются виртуальными, и они формируют виртуальное адресное пространство.

Термин виртуальная память означает, что программист имеет дело с памятью отличной от реальной, размер которой потенциально больше чем объём оперативной памяти.

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

Любая из 3-х схем управления памятью: страничная, сегментная и сегментно-страничная, пригодна для организации виртуальной памяти. Чаще всего используется сегментно-страничная модель, которая является синтезом страничной памяти на сегментной идее. Сегментная организация в чистом виде встречается редко.

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

Передача информации между памятью и диском всегда осуществляется целыми страницами. После разбиения менеджером памяти виртуального адресного пространства на страницы, виртуальный адрес преобразуется в пару (p:d). Где p – номер страницы, d – смещение в рамках страницы p.

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

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

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

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

Лекция №5

Стратегия управления страничной памятью.

ПО в подсистемах управления памятью связано с реализацией следующих стратегий:

• выборки

• размещения

• замещения

Выборка - определение в какой момент следует переписать страницу из вторичной памяти в первичную. Существуют 2 основных варианта выборки:

1. По запросу;

2. С упреждением.

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

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

Размещение – определяет в какой именно участок оперативной памяти следует поместить подступающую страницу. В системе со страничной организацией она поступает в любой свободный страничный кадр. В системе с сегментной организацией необходима аналогичная стратегия с динамическим размещением.

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

Алгоритмы замещения страниц.

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

1. Найти некоторую занятую страницу основной памяти;

2. Переместить в случае надобности ее содержимое во внешнюю память;

3. Переместить в этот страничный кадр содержимое нужной виртуальной страницы из внешней памяти;

4. Модифицировать необходимый элемент в соответствии таблице страниц;

5. Продолжить выполнение процесса, которому эта виртуальная страница понадобилась.

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

Существует большое количество разнообразных алгоритмов замещения страниц, все они делятся на локальные и глобальные.

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

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

1. Они делают процесс чувствительным к поведению других процессов;

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

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

Файловая система.

Управление файлами.

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

Хранение информации на магнитном диске требует хорошего знания устройства контроллера диска, особенности работы с его архитектурой. Непосредственное взаимодействие с диском – прерогатива компоненты системы I/O ОС – драйвера диска. Чтобы избавить пользователя от взаимодействия с аппаратурой, была применена ясная абстрактная модель файловой системы, т.к. операции запись/чтение проще, чем многоуровневые операции по работе с устройством.

Основная идея использования памяти: ОС делит память на блоки фиксированного размера, файл, обычно представляющий собой неструктурированную последовательность однобайтовых записей, хранится в виде последовательных блоков, необязательно смежных, каждый блок хранит целое число записей, в некоторых ОС, например, MS Windows, адреса блоков, содержащих данные файла, могут быть организованы в связанный список и вынесены в отдельную таблицу файлов. В других ОС (Unix) адреса блоков данных файла хранятся в отдельном блоке внешней памяти – индексе (индексный узел, файловый дескриптор). Этот приём – индексация, наиболее распространен для приложений, требующих произвольный доступ к записям файла. Индекс файла состоит из элементов, каждый из которых содержит номер блока в файле и сведение о местоположении данного блока. Считывание очередного байта производится с текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, можно вычислить номер блока, содержащего текущую позицию, адрес же нужного блока можно извлечь из индекса файла.

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

Основные функции файловой системы.

• идентификация файлов, связывание имени файла с выделенным ему пространством внешней памяти;

• распределение внешней памяти между файлами, чтобы для работы с конкретным файлом не требовалась информация о местоположении этого файла на внешнем носителе информации;

• обеспечение надежности, отказоустойчивости, поскольку стоимость информации может во много раз превышать стоимость компьютера;

• обеспечение защиты от несанкционированного доступа;

• обеспечение совместного доступа к файлам;

• обеспечение высокой производительности.

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

Общая структура файловой системы:

Логическая подсистема функции: поддержка иерархической древовидной структуры, системные вызовы, работающие с PATHNAME – полным именем файла, защита файлов.

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

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

Непосредственно с дисками взаимодействует часть ОС – система I/O, которая предоставляет в распоряжение файловой системы используемое дисковое пространство в виде непрерывной последовательности блоков фиксированного размера. Система I/O имеет дело с физическими блоками диска, которые характеризуются адресом, например, диск 2, цилиндр 75, сектор 11.

Файловая система имеет дело с логическими блоками, каждый из которых имеет номер от 0 или 1 до N. Размер логических блоков файла совпадает или является кратным размеру физического блока диска и может быть задан кратным размеру страницы виртуальной памяти.

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

Стандартный запрос на открытие или создание файлов поступает от прикладной программы к логической подсистеме. Логическая подсистема, используя структуру директорий, проверяет права доступа и вызывает базисную подсистему для получения доступа к блокам файла, после этого файл считается открытым, он содержится в таблице открытых файлов и прикладная программа получает в свое распоряжение дескриптор этого файла. В MS Windows он называется “handle”.

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

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

Методы выделения дискового пространства.

В ОС используется несколько методов выделения дискового пространства. Символическое имя файла содержит указатель, следуя которому можно найти все блоки данного файла.

1. Выделение непрерывной последовательности блоков.

Простейший способ хранения каждого файла как непрерывную последовательность блоков диска. При непрерывном положении файл характеризуется адресом и длиной. Файл, начинающийся в блоке В, занимает затем блоки В+1, ... В+(n-1). Эта схема имеет 2 преимущества:

• легко реализуется, т.к. выяснение места положения файла сводится к вопросу о том, где находится 1-й блок;

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

Этот тип выделения используется в OS IBM/CMS, RSX-11. Этот способ мало распространен, т.к. в процессе эксплуатации диск представляет собой некоторую совокупность свободных и занятых фрагментов, поэтому не всегда есть подходящий по размеру фрагмент.

2. Связанный список.

Внешняя фрагментация может быть устранена за счет представления файла в виде связанного списка блоков диска. Запись в директории содержит указатель на 1-й и последний блоки файла (иногда используется специальный знак конца файла EOF).

Внешняя фрагментация для данного метода отсутствует. Любой свободный блок может быть использован для удовлетворения запросов. Файлы могут расти неограниченно.

Недостатки метода:

• при прямом доступе к файлу для поиска нужного i-го блока необходимо осуществить несколько обращений к диску, последовательно считывая блоки от 1 до (i-1), что требует много времени;

• данный способ ненадежен. наличие дефекта блока в списке приводит к потере информации в оставшейся части файла и потенциально к потере дискового пространства, отведенного под этот файл;

• наконец, для указателя на следующий блок внутри блока нужно выделять место для, что не всегда удобно. Размер фрагмента становится не кратным степени 2, т.к. указатель отбирает несколько байт.

Этот способ обычно в чистом виде не используется.

3. Таблица размещения файлов.

Одним из вариантов предыдущего способа является хранение указателя не в дисковых блоках, а индексах таблицы памяти, которая называется таблицей размещения файлов (File Allocation Table).

Этой схеме придерживаются много ОС (OS/2, ms-dos, windows).

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

Достоинства метода:

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

Недостатки метода:

• необходимо хранить в памяти довольно большое число таблиц.

Методы работы в дисковом пространстве.

Структура служебных данных типовой файловой систем, например Unix, может состоять из 4-х основных частей:

Суперблок

Свободные индексные дескрипторы

Массивы индексных дескрипторов

Блоки диска

В начале раздела находится суперблок. Он содержит описание файловой системы:

1. тип файловой системы;

2. размер файловой системы в блоках;

3. размер массива индекса дескрипторов;

4. размер логического блока.

Эти структуры данных создаются на диске в результате его форматирования. Например, утилитами makefs, format и др. Их наличие позволяет обращаться к данным на диске как к файловой системе, а не так, как к обычной последовательности блоков. В файловой системе современных ОС для повышения устойчивости поддерживается несколько копий суперблоков.

Массив индексных дескрипторов содержит список индексных дескрипторов, соответствующих файлам данной файловой системы. Его размер определяется администратором при установке ОС. Максимальное число файлов, которое могут быть созданы в файловой системе, определяется числом индексных дескрипторов. В блоках данных хранятся реальные данные файла. Размер блока данных задается при форматировании файловой системы. Заполнение диска информацией предполагает использование блоков хранения данных для файлов директорий и обычных файлов и имеет следствием изменение или модификацию индексных узлов и данных, описывающих пространство диска. Отдельно взятый блок данных может принадлежать одному и только одному файлу файловой системы.

Реализация директорий.

Директория – файл, имеющий вид таблицы и хранящий список входящих в него файлов и каталогов.

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

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

Директории в ОС MS DOS.

В этой ОС типовая запись директории имеет вид:

8	3	1	10	2	2	2	4
Имя файла	Расширение	Атрибуты	Резерв	Время	Дата	№ 1-го блока	Размер

В ОС MS DOS директории могут содержать поддиректории, которые определяются битом атрибутов, что позволяет конструировать произвольное дерево директорий файловой системы. Номер 1-го блока используется в качестве индекса в FAT. Далее по этой таблице могут быть найдены остальные блоки.

Директории в ОС UNIX.

2	14
Номер индексного дескриптора	Имя файла

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

Лекция №6

Целостность файловой системы.

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

Современная архитектура файловой системы.

Современные ОС предоставляют пользователю работать с несколькими файловыми системами. Файловая система в традиционном понимании становится частью более общей многоуровневой структуры.

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

Реализация файловой системы связана с поддержкой понятия логического блока диска, связыванием имени файла и блоков файла и проблемами управления дисковым пространством. Наиболее распространенные способы выделения дискового пространства: непрерывное выделение, организация связанного списка и системы с индексными дескрипторами.

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

Системы управления I/O.

Функционирование любой ВС сводится к выполнению 2-х видов работ: обработка информации и операция по осуществлению её I/O. С другой точки зрения программиста, под обработкой информации понимается выполнение команд CPU над данными, лежащими в памяти независимо от уровня иерархии в регистрах, КЭШе, оперативной или вторичной памяти. Под операциями I/O программист понимает обмен данными между памятью и внешними устройствами по отношению к памяти и CPU. С точки зрения ОС, обработка информации является только операцией, совершаемой CPU над данными, находящимися в памяти на уровне иерархии не ниже, чем оперативная память. Всё остальное относится к операциям I/O. Чтобы выполнять операции над данными, расположенными во вторичной памяти, ОС сначала производит их подкачку в оперативную память, и лишь затем CPU совершает необходимые действия. В то время как память можно представить в виде последовательности пронумерованных ячеек, локализованных внутри одной микросхемы, то к устройствам I/O подобный подход неприменим. Внешние устройства разнесены пространственно и могут подключаться к локализованной магистрали в одной точке или множестве точек, получивших название портов I/O. Порты I/O могут взаимно однозначно отразить в другое адресное пространство ввод/вывод. При этом каждый порт I/O получает свой номер или адрес в этом пространстве. В некоторых случаях, когда адресное пространство памяти задействовано не полностью, часть портов I/O может быть отражена в адресное пространство памяти (видеопамять, дискет). Тогда эти порты не принято называть портами. Когда порты I/O прямо отображаются в памяти, действия, необходимые для записи информации ничем не отличаются от действий, производимых для передачи информации между оперативной памятью и CPU, и для их выполнения используются те же самые команды. Если порт отображен в адресное пространство ввода/вывода, то процесс обмена информацией выполняется специальными командами I/O и включает в себя следующие действия:

1. на адресной шине CPU должен выставит сигнал, соответствующий адресу порта;

2. на шине данных CPU должен выставить сигналы, соответствующие передаваемой информации;

3. после выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операциям записи и работе с устройствами I/O, что приведет к передаче необходимой информации в нужный порт.

Существует отличие памяти от устройств I/O: занесение информации в память является окончанием операции записи, в то время как занесение информации в порт представляет собой инициализацию реального выполнения операций I/O. Что именно должны делать устройства, приняв информацию через порт и каким именно образом они должны поставлять информацию для чтения из порта, определяется устройством, получившим название контроллер. Контроллер может непосредственно управлять отдельным устройством, а может несколькими, связанных с их контроллерами посредством специальных шин I/O (IDE, SCSI). Современная ОС может иметь разнообразную архитектуру, множество шин и магистралей, мосты для перехода информации от одной шины к другой и т.п. Но всегда выполняется следующие важные моменты:

1. устройство I/O подключается к системе через порты;

2. может существовать 2 адресных пространства: пространство памяти и пространство I/O;

3. порты отображаются в адресном пространстве I/O и иногда непосредственно в адресном пространстве памяти;

4. использование того или иного адресного пространства определяется типом команд, выполняемых CPU, или типом её операндов;

5. физическим управлением устройства I/O, передачей информации через порт и выставлением некоторых сигналов на магистрали занимается контроллер устройств. Именно единообразие подключения внешних устройств к ВС является одной из составляющих идеологий, позволяющей подключать новые устройства без перепроектирования всей системы.

Структура контроллера устройств.

Контроллеры устройств I/O различны как по своему внутреннему строению, так и по использованию, поскольку им приходиться управлять совершенно разными приборами. Тем не менее, каждый контроллер имеет 4 внутренних регистра, называемых регистрами состояния, управления, входящих данных и выходящих данных. Для простоты считается, что каждому регистру соответствует свой блок. Регистр состояния содержит биты, значение которых определяется состоянием устройства I/O и которые доступны только для чтения. Эти биты индуцируют завершение выполнения текущей команды на устройстве (бит занятости), наличие очередных данных в регистре выходных данных (бит готовности данных), возникновении ошибки при выполнении команд (бит ошибки). Регистр управления получает данные, которые записываются ВС для инициализации устройства I/O или выполнения очередной команды, а также изменения режима работы устройств. Часть битов в этом регистре отводиться под код выполняемой команды, часть битов под режим работы устройства, бит готовности команды говорит о том, что следует приступить к её выполнению. Регистр выходных данных служит для размещения данных, предназначенных для чтения ВС, а регистр входных данных предназначен для помещения в него информации, которая должна быть выведена на устройство. Если CPU ожидает освобождения устройства, непрерывно опрашивая вид занятости, то такой способ взаимодействия CPU и контроллера получил название pooling или способ опроса устройств. Если скорость работы CPU и устройства I/O примерно равны, то это не приводит к существенному уменьшению полезной работы, совершаемой CPU. Если скорость работы устройства меньше скорости работы CPU, то эта техника резко снижает производительность системы и необходимо применять архитектурный подход. Для того, чтобы CPU не дожидался состояния готовности устройства в цикле, а мог выполнять в это время другую работу, необходимо, чтобы устройство само умело сигнализировать CPU о своей готовности. Технический механизм, который позволяет внешнему устройству оповещать CPU о завершении команды I/O, получил название механизма прерывания.

В простейшем случае для реализации механизма прерывания необходимо к системной шине добавить ещё одну линию, соединяющую CPU и устройство I/O - линию прерывания. По завершении выполнения операций внешнее устройство поставляет на эту линию специальный сигнал, по которому CPU после выполнения очередной команды изменяет своё поведение. Вместо выполнения очередной команды из потока команд он частично сохраняет содержимое своих регистров и переходит на выполнение программы обработки прерываний, расположенной по заранее оговорённому адресу. В большинстве современных компьютеров CPU стараются полностью освободить от необходимости опроса внешних устройств, в т.ч. и от определения с помощью опроса устройства, сгенерировавшего сигнал прерывания. Устройство сообщает о своей готовности CPU не напрямую, а через специальный контроллер прерываний, при этом для общения с CPU он использует целую шину прерываний. Каждому устройству присваивается свой номер прерываний, который при возникновении прерывания контроллер прерываний заносит в регистр состояния и выставляет на шину прерываний для чтения CPU. Номер прерывания служит индексом специальной таблицы прерываний, хранящейся по адресу, задаваемому при инициализации ВС и содержащий адреса программ обработки прерываний - векторы прерывания. Для распределения устройств по номерам прерываний необходимо, чтобы от каждого устройства контроллера прерываний была специальная линия, соответствующая одному номеру прерывания. При наличии множества устройств такое подключение становится невозможным, и на один проводник (один номер прерывания) подключается несколько устройств. В этом случае CPU при обработке прерываний вынужден заниматься опросом устройств для определения устройства, вызвавшего прерывание. Обычно при установке в системе нового устройства I/O требуется аппаратно или программно определить каким будет номер прерывания, вырабатываемый этим устройством.

Прямой доступ к памяти. Direct Memory Access(DMA).

Использование механизма прерываний позволяет загружать CPU в то время, когда устройство I/O занимается своей работой. Однако запись или чтение большого количества информации из адресного пространства I/O, например с диска, приводит к большому количеству операций I/O, которые должен выполнять CPU. Для освобождения CPU от операций последовательного выбора данных из оперативной памяти или последовательного ввода в неё был предложен контроллер прямого доступа устройств к памяти (DMA). Который управляет потоком битов между Оперативной памятью (ОП) и некоторыми контролерами без вмешательства CPU. CPU обращается к микросхеме DMA, сообщает ей число байтов для передачи, а также адрес устройства и памяти, а также направление передачи данных. По завершении работы DMA инициирует прерывание, которое обрабатывается обычным порядком.

Классификация ОС.

Развитие компьютеров привело к развитию ОС. Сейчас насчитывается более 100 ОС.

По назначению ОС принято делить на семь уровней.