Лекция 1. Введение в сетевые ОС (стр. 8 )

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

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

Переключение контекстов процессов возникает если:

· текущий процесс блокируется в ожидании ресурса или завершает работу;

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

· текущий процесс или обработчик прерываний разбудил более приоритетный процесс.

К ограничениям традиционного планировщика можно отнести следующие особенности:

· не слишком хорошо масштабируется (если общее количество процессов велико, он неэффективно пересчитывает приоритеты каждую секунду);

· не существует способов гарантированного предоставления части процессорного времени как ресурса определенной группе процессов или конкретному процессу;

· не существует никакого гарантированного времени реакции приложений, имеющих свойства реального времени, так как ядро невытесняющее;

· приложения имеют скудные возможности для управления собственным приоритетом, механизм, работающий через значение «любезности», является слишком примитивным и не отвечающим поставленным требованиям;

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

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

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

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

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

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

Изначально в UNIX-системах применялась поддержка виртуальной памяти на основе перемещения процессов между памятью и диском (свопинг). Выгрузка процессов инициировалась в следующих случаях:

· cистемному вызову fork не хватало памяти для дублирования адресного пространства родителя;

· происходило обращение к системному вызову brk для увеличения размера сегмента данных;

· возникало страничное прерывание при заполнении сегмента стека;

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

При поиске процесса, подлежащего выгрузке, сначала анализировались заблокированные процессы (ожидающие наступления какого-либо события) и из них выбирался тот, у которого было максимальное значение (приоритет + время нахождения в памяти). Если заблокированные процессы отсутствовали, то на основании того же критерия выбирался один из готовых к выполнению. Один раз в несколько секунд исследовался список выгруженных процессов на предмет наличия процессов, находящихся в состоянии готовности к выполнению. Из них выбирался тот, который дольше всех находился на диске. Процесс повторялся до тех пор, пока: (1) на диске не оставалось процессов, готовых к работе, (2) в памяти не оставалось места для новых процессов. Чтобы избежать слишком частого перемещения процессов из памяти на диск и обратно, процессы не выгружались на диск, если их время пребывания в памяти было менее 2 с.

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

Страничный демон просыпается каждые 250 мс, сравнивает количество страниц с заданным пороговым значением (так реализован страничный демон в 4.4 BSD), если в системе обнаружена нехватка страниц, то он начинает вытеснять их на диск (без учета принадлежности страниц процессам, т. е. применяется глобальная стратегия). Отличием в реализации SV является то, что вместо одного порогового значения используется пара (min, max). Как только количество свободных страниц становится меньше min, страничный демон начинает освобождать страницы, пока их количество не сравняется с max.

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

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

Организация ввода-вывода

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

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

· надежный, ориентированный на соединение поток байтов;

· надежный, ориентированный на соединение поток пакетов;

· ненадежный, не ориентированный на соединение поток пакетов.

Организация ФС

UNIX-системы характеризуются разнообразием поддерживаемых ФС, начиная с V7 до сетевой файловой системы NFS.

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

ФС Berkley Fast

Для этой системы характерны следующие особенности:

1) По сравнению с V7 имена файлов были увеличены до 255 символов. Структура каталогов была реорганизована, записи каталога имеют различные размеры и не отсортированы внутри него. Каждая запись содержит четыре фиксированных поля (номер i-узла, размер записи каталога в байтах, поле типа – файл или каталог, длина имени файла) и поле переменной длины (имя файла, заканчивающееся нулевым байтом и дополненное до 32-битной границы);

2) поскольку поиск файла в каталоге может занять много времени, то при анализе имен файлов ФС применяет кэширование;

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

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

ФС Linux Ext2 основывалась на ФС ОС MINIX, совместимой с V7, поэтому допускалась длина файлов до 14 символов, а размер файла был ограничен 64 Мбайт.

В ФС Ext длина имени была увеличена до 255 символов, а размер файла до 2 Гбайт, но полученная система оказалась медленнее, чем оригинал, поэтому исследования продолжились, и результатом их явилась ФС Ext2.

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

Размер каждого битового массива – один блок. Если размер блока 1 Кбайт, то в группе максимум – 8 192 блока и 8 192 узла. Размер каждого узла – 128 байт. Вместо десяти прямых и трех косвенных адресов в ФС Ext2 используется двенадцать прямых и три косвенных. Длина адресов дисковых блоков составляет 4 байта.

ФС NFS

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

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

Протокол доступа к файлам. Данный протокол обеспечивает работу с удаленными файлами после того, как часть ФС удаленного компьютера была смонтирована в качестве локальной. Вызовы open и close не поддерживаются, вместо этого есть lookup, который возвращает дескриптор файла. После этого каждое сообщение read и write является самодостаточным. Отслеживание состояния записи / чтения файла должно производиться на стороне клиента, серверы не хранят информации о клиентах, т. е. являются серверами без состояний.

Реализуется NFS чаще всего в виде трех уровней (рис. 9.2).

Рис. 9.2. Структура уровней NFS

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

Задачей уровня VFS является поддержание таблицы виртуальных узлов (v-узел), используемых для различения локальных и удаленных файлов. Уровень VFS взаимодействует с рядом локальных файл-серверов (разных систем) и клиентом NFS. Для удаленных файлов предоставляется информация, достаточная для доступа к ним. Для локальных – сведения о ФС и i-узле. Для удаленных узлов клиент NFS создает r-узлы (удаленные узлы) для хранения дескрипторов файлов. V-узлы указывают на r-узлы для удаленных файлов и на i-узлы для локальных.

Список используемых сокращений

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

ФС – файловая система

ИВС – информационно-вычислительная система

ПО – программное обеспечение

АО – аппаратное обеспечение

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

GUI – графический интерфейс пользователя

ОЗУ – оперативное запоминающее устройство

ПЗУ – постоянное запоминающее устройство

ВАП – виртуальное адресное пространство

ВП – виртуальная память

Содержание

Лекция 1. Введение в сетевые ОС........................................................ 3

Лекция 2. Структура ОС................................................................... 10

Лекция 3. Процессы и потоки в ОС.................................................. 20

Лекция 4. Управление памятью в ОС............................................... 31

Лекция 5. Организация виртуальной памяти в ОС.......................... 38

Лекция 6. Организация ввода-вывода в ОС..................................... 49

Лекция 7. Файловые системы ОС...................................................... 60

Лекция 8. Примеры ФС..................................................................... 70

Лекция 9. Операционная система UNIX........................................... 78