До версии 3BSD большинство систем UNIX основывались на свопинге (подкачке), работавшем следующим образом. Когда загружалось больше процессов, чем могло поместиться в памяти, некоторые из них выгружались на диск. Выгружаемый процесс всегда выгружался на диск целиком (исключение представляли только совместно используемые текстовые сегменты). Таким образом, процесс мог быть либо в памяти, либо на диске.
Перемещением данных между памятью и диском управлял верхний уровень двухуровневого планировщика, называвшийся свопером (swapper). Выгрузка данных из памяти на диск инициировалась, когда у ядра кончалась свободная память из-за одного из следующих событий:
1. Системному вызову fork требовалась память для дочернего процесса.
2. Системный вызов brk собирался расширить сегмент данных.
3. Разросшемуся стеку требовалась дополнительная память.
Кроме того, когда наступало время запустить процесс, уже достаточно долго находящийся на диске, часто бывало необходимо удалить из памяти другой процесс, чтобы освободить место для запускаемого процесса. Выбирая процесс, который необходимо было удалить из памяти, свопер сначала рассматривал блокированные (например, ожиданием ввода с терминала) процессы. Лучше удалить из памяти процесс, который не может работать, чем работоспособный процесс. Если такие процессы находились, из них выбирался процесс с наивысшим значением суммы приоритета и времени пребывания в памяти. Таким образом, подвергались выгрузки процессы, потребившие большое количество процессорного времени или находящиеся в памяти уже достаточно долгое время. Если блокированных процессов не было, тогда на основе тех же критериев выбирался готовый процесс.
Каждые несколько секунд свопер исследовал список выгруженных процессов, проверяя, не готов ли какой-либо из этих процессов к работе. Если процессы в состоянии готовности обнаруживались, из них выбирался процесс, дольше всех находящийся на диске. Затем свопер проверял, будет ли это легкий свопинг или тяжелый. Легким свопингом считался тот, для которого не требовалось дополнительное высвобождение памяти. При этом нужно было всего лишь загрузить выгруженный на диск процесс. Тяжелым свопингом назывался свопинг, при котором для загрузки в память выгруженного на диск процесса из нее требовалось удалить один или несколько других процессов. Затем весь этот алгоритм повторялся до тех пор, пока не выполнялось одно из следующих двух условий: на диске не оставалось процессов, готовых к работе, или в памяти не оставалось места для новых процессов. Чтобы не терять большую часть производительности системы на свопинг, ни один процесс не выгружался на диск, если он пробыл в памяти менее 2 с. Свободное место в памяти и на устройстве перекачки учитывалось при помощи связного списка свободных пространств. Когда требовалось свободное пространство в памяти или на диске, из списка выбиралось первое подходящее свободное пространство. После этого в список возвращался остаток от свободного пространства.
Начиная с версии 3BSD к системе была добавлена страничная подкачка, чтобы предоставить возможность работать с программами больших размеров. Практически во всех версиях системы UNIX теперь есть страничная подкачка по требованию, появившаяся впервые в версии 3BSD. Ниже описывается реализация этого механизма в версии 4BSD. Такая реализация во многом соответствует и версии System V, которая основана на 4BSD.
Идея, лежащая в основе страничной подкачки в системе 4BSD, состоит в том, что процессу для работы не нужно целиком находиться в памяти. Все, что в действительности требуется, – это структура пользователя и таблицы страниц. Если они загружены, то процесс считается находящимся в памяти и может быть запущен планировщиком. Страницы с сегментами текста, данных и стека загружаются в память динамически, по мере обращения к ним. Если пользовательской структуры и таблицы страниц нет в памяти, то процесс не может быть запущен, пока свопер не загрузит их.
Страничная подкачка реализуется частично ядром и частично новым процессом, называемым страничным демоном. Как и все демоны, страничный демон периодически запускается и смотрит, есть ли для него работа. Если он обнаруживает, что количество страниц в списке свободных страниц слишком мало, страничный демон инициирует действия по освобождению дополнительных страниц.
Память в 4BSD делится на три части. Первые две части, ядро операционной системы и карта памяти, фиксированы в физической памяти (то есть никогда не выгружаются). Остальная память машины делится на страничные блоки, каждый из которых может содержать либо страницу текста, данных или стека, либо находиться в списке свободных страниц.
Карта памяти содержит информацию о содержимом страничных блоков. Для каждого страничного блока в карте памяти есть запись фиксированной длины. При килобайтных страничных блоках и 16-байтовых записях карты памяти на нее расходуется менее 2 % от общего объема памяти. Первые два поля записи карты памяти используются только тогда, когда соответствующий страничный блок находится в списке свободных страниц. В этом случае они сшивают свободные страницы в двусвязный список. Следующие три записи используются, когда страничный блок содержит информацию. У каждой страницы в памяти есть фиксированное место хранения на диске, в которое она помещается, когда выгружается из памяти. Еще три поля содержат ссылку на запись в таблице процессов, тип хранящегося в странице сегмента и смещение в сегменте процесса. Последнее поле содержит некоторые флаги, нужные для алгоритма страничной подкачки. При запуске процесс может вызвать страничное прерывание, если одной или нескольких его страниц не окажется в памяти. При страничном прерывании операционная система берет первый страничный блок из списка свободных страниц, удаляет его из списка и считывает в него требуемую страницу. Если список свободных страниц пуст, выполнение процесса приостанавливается до тех пор, пока страничный демон не освободит страничный блок.
Алгоритм замещения страниц выполняется страничным демоном. Раз в 250 мс он сравнивает количество свободных страничных блоков с системным параметром lotsfree (равным, как правило, 1/4 объема памяти). Если число свободных страничных блоков меньше, чем значение этого параметра, страничный демон начинает переносить страницы из памяти на диск, пока количество свободных страничных блоков не станет равно lotsfree. Если же количество свободных страничных блоков больше или равно lotsfree, тогда страничный демон ничего не предпринимает. Если в машине много памяти и мало активных процессов, страничный демон практически все время бездействует.
Страничный демон использует модифицированную версию алгоритма часов. Это глобальный алгоритм, то есть при удалении страницы он не учитывает, чья это страница. Таким образом, количество страниц, выделяемых каждому процессу, меняется со временем. Основной алгоритм часов работает, сканируя в цикле страничные блоки (как если бы они лежали на окружности циферблата часов). На первом проходе, когда стрелка часов указывает на страничный блок, сбрасывается его бит использования. На втором проходе у каждого страничного блока, к которому не было доступа с момента первого прохода, бит использования останется сброшенным, и этот страничный блок будет помещен в список свободных страниц. Страничный блок в списке свободных страниц сохраняет свое содержание, что позволяет восстановить страницу, если она потребуется прежде, чем будет перезаписана.
Изначально в версии UNIX 4BSD использовался основной алгоритм часов, но затем он был заменен более эффективным алгоритмом часов с двумя стрелками. В этом алгоритме страничный демон поддерживает два указателя на карту памяти. При работе он сначала очищает бит использования передней стрелкой, а затем проверяет этот бит задней стрелкой. После чего перемещает обе стрелки. Если две стрелки находятся близко друг от друга, то только у очень активно используемых страниц появляется шанс, что к ним будет обращение между проходами двух стрелок. Если же стрелки разнесены на 359 градусов (то есть задняя стрелка находится слегка впереди передней), то по сути снова получается исходный алгоритм часов. При каждом запуске страничного демона стрелки проходят не полный оборот, а столько, сколько необходимо, чтобы количество страниц в списке свободных страниц было не менее lotsfree.
Если операционная система обнаруживает, что частота подкачки страниц слишком высока, а количество свободных страниц все время ниже lotsfree, свопер начинает удалять из памяти один или несколько процессов, чтобы остановить состязание за свободные страничные блоки. Свопинг в системе 4BSD осуществляется по следующему алгоритму. Сначала свопер проверяет, есть ли процесс, который бездействовал в течение 20 и более секунд. Если такие процессы есть, из них выбирается бездействовавший в течение максимального срока и выгружается на диск. Если таких процессов нет, изучаются четыре самых больших процесса, из которых выбирается тот, который находился в памяти дольше всех, и выгружается на диск. При необходимости этот алгоритм повторяется до тех пор, пока не будет высвобождено достаточное количество памяти.
Каждые несколько секунд свопер проверяет, есть ли на диске готовые процессы, которые следует загрузить в память. Каждому процессу на диске присваивается значение, зависящее от времени его пребывания в выгруженном состоянии, размера, значения, использовавшегося при обращении к системному вызову nice (если такое обращение было), и от того, как долго этот процесс бездействовал, прежде чем был выгружен на диск. Эта функция обычно взвешивается так, чтобы загружать в память процесс, дольше всех находящийся в выгруженном состоянии, если только он не крайне большой. Теория утверждает, что загружать большие процессы дорого, поэтому их не следует перемещать с диска в память и обратно слишком часто. Загрузка процесса производится только при условии наличия достаточного количества свободных страниц, чтобы, когда случится неизбежное страничное прерывание, для него нашлись свободные страничные блоки. Свопер загружает в память только структуру пользователя и таблицы страниц. Страницы с текстом, данными и стеком подгружаются при помощи обычной страничной подкачки.
У каждого сегмента каждого активного процесса есть место на диске, где он располагается, когда его страницы удаляются из памяти. Сегменты данных и стека сохраняются на временном устройстве, но текст программы подгружается из самого исполняемого двоичного файла. Для текста программы временная копия не используется.
Страничная подкачка в версии System V во многом схожа с применяемой в системе 4BSD, но тем не менее между этими версиями операционной системы есть интересные различия. Во-первых, в System V вместо алгоритма часов с двумя стрелками используется оригинальный алгоритм часов с одной стрелкой. Более того, вместо того чтобы помещать страницу в список свободных страниц на втором проходе, страница помещается туда только в случае, если она не использовалась в течение нескольких последовательных проходов. Хотя при таком решении страницы не освобождаются так быстро, как это делается алгоритмом в 4BSD, оно значительно увеличивает вероятность того, что освобожденная страница не потребуется тут же снова. Во-вторых, вместо единственной переменной lotsfree в System V используются две переменные: min и max. Когда количество свободных страниц опускается ниже min, страничный демон начинает освобождать страницы. Демон продолжает работать до тех пор, пока число свободных страниц не сравняется со значением max. Такой подход позволяет избежать неустойчивости, возможной в системе 4DSD, например, в ситуации, когда количество свободных страниц на единицу меньше, чем lotsfree. При этом страничный демон освобождает одну страницу, чтобы привести количество свободных страниц в соответствие со значением lotsfree. Затем происходит еще одно страничное прерывание, и количество свободных страниц опять становится на единицу меньше lotsfree, в результате страничный демон снова начинает работать. Если установить значение max существенно большим, чем min, страничный демон, завершив освобождение страниц, создает достаточный запас для своего бездействмя в течение относительно продолжительного времени.
7.4. Ввод-вывод в системе UNIX
Основные понятия
Подход, применяемый в операционной системе UNIX для доступа программ к устройствам ввода-вывода (таким как диски, принтеры, сетевые устройства и т.п.), заключается в интегрировании всех устройств в файловую систему в виде так называемых специальных файлов. Каждому устройству ввода-вывода назначается имя пути, обычно в каталоге /dev. Например, диск может иметь путь /dev/hd1, у принтера может быть путь /dev/lр, а у сети – /dev/net. Доступ к этим специальным файлам осуществляется так же, как и к обычным файлам. Для этого не требуется никаких специальных команд или системных вызовов, а используются обычные системные вызовы read и write. Программы могут открывать, читать специальные файлы, а также писать в них тем же способом, что и в обычные файлы. Таким образом, для выполнения ввода-вывода не требуется специального механизма.
Специальные файлы подразделяются на две категории: блочные и символьные. Блочный специальный файл – это специальный файл, состоящий из последовательности нумерованных блоков. Основное свойство блочного специального файла заключается в том, что к каждому его блоку можно адресоваться и получить доступ отдельно. Другими словами, программа может открыть блочный специальный файл и прочитать, скажем, 124-й блок, не читая сначала блоки с 0 по 123. Блочные специальные файлы обычно используются для дисков. Символьные специальные файлы, как правило, используются для устройств ввода или вывода символьного потока. Символьные специальные файлы используются такими устройствами, как клавиатуры, принтеры, сети, мыши, плоттеры и т. д.
С каждым специальным файлом связан драйвер устройства, осуществляющий управление соответствующим устройством. У каждого драйвера есть так называемый номер старшего устройства, служащий для его идентификации. Если драйвер одновременно поддерживает несколько устройств, например два диска одного типа, то каждому диску присваивается номер младшего устройства, идентифицирующий это устройство. Вместе номера старшего устройства и младшего устройства однозначно обозначают каждое устройство ввода-вывода.
Другим примером ввода-вывода является работа с сетью, впервые появившаяся в Berkeley UNIX. Ключевым понятием в схеме Berkeley UNIX является сокет. Сокеты образуют пользовательский интерфейс с сетью. Сокеты могут динамически создаваться и разрушаться. При создании сокета вызывающему процессу возвращается дескриптор файла, требующийся для установки соединения, чтения и записи данных, а также разрыва соединения.
Каждый сокет поддерживает определенный тип работы в сети, указываемый при создании сокета. Наиболее распространенными типами сокетов являются: 1) надежный байтовый поток (ориентиро-ванный на соединение), 2) надежный поток пакетов (ориенти-рованный на соединение), 3) ненадежная передача пакетов.
Первый тип сокетов позволяет двум процессам на различных машинах установить между собой эквивалент «трубы» (канала между процессами на одной машине). Байты подаются в канал с одного конца и в том же порядке выходят с другого. Такая система гарантирует, что все посланные байты прибудут на другой конец канала и прибудут именно в том порядке, в котором были отправлены.
Второй тип сокетов отличается от первого тем, что он сохраняет границы между пакетами. Если отправитель пять раз отдельно обращается к системному вызову write, каждый раз отправляя по 512 байт, а получатель запрашивает 2560 байт по сокету типа 1, он получит все 2560 байт сразу. При использовании сокета типа 2 ему будут выданы только первые 512 байт. Чтобы получить остальные байты, получателю придется выполнить системный вызов read еще четыре раза.
Третий тип сокета особенно полезен для приложений реального времени и ситуаций, в которых пользователь хочет реализовать специальную схему обработки ошибок. Сеть может терять пакеты или доставлять их в неверном порядке. В отличие от сокетов первых двух типов, сокет типа 3 не предоставляет никаких гарантий доставки. Преимущество этого режима заключается в более высокой производительности, которая в некоторых ситуациях оказывается важнее надежности (например, для доставки мультимедиа, при которой скорость ценится существенно выше, нежели сохранность данных).
При создании сокета один из параметров указывает протокол, используемый для него. Для надежных байтовых потоков, как правило, используется протокол TCP (Transmission Control Protocol – протокол управления передачей). Для ненадежной передачи пакетов обычно применяется протокол UDP (User Data Protocol – пользовательский протокол данных). Все эти протоколы составляют основу Интернета. Для надежного потока пакетов специального протокола нет.
Прежде чем сокет может быть использован для работы в сети, с ним должен быть связан адрес. Этот адрес может принадлежать к одному из нескольких пространств адресов. Наиболее распространенным пространством является пространство адресов Интернета, использующее 32-разрядные числа для идентификации конечных адресатов в протоколе IPv4 и 128-разрядные числа в протоколе IPv6.
Как только сокеты созданы на машине-источнике и машине-приемнике, между ними может быть установлено соединение (для ориентированной на соединение связи). Одна сторона обращается к системному вызову listen, указывая в качестве параметра локальный сокет. При этом системный вызов создает буфер и блокируется до тех пор, пока не прибудут данные. Другая сторона обращается к системному вызову connect, задавая в параметрах дескриптор файла для локального сокета и адрес удаленного сокета. Если удаленная машина принимает вызов, тогда система устанавливает соединение между двумя сокетами.
Функции установленного соединения аналогичны функциям канала. Процесс может читать из канала и писать в него, используя дескриптор файла для локального сокета. Когда соединение далее не требуется, оно может быть закрыто обычным способом, при помощи системного вызова close.
