Операционные системы (часть 1)

Основные принципы построения ОС:

1.Частотный -- обеспечения быстрого выполнения частоиспользуемых операций;

2.Модульности -- построение системы из независимых компонент;

3.Функциональной избирательности -- выделение ключевых модулей по частотному принципу -- эти модули называют ядром;

4.Генерируемости -- настраиваемость системы под конкретную аппаратуру и под требования решаемых задач и пользователя;

5.Функциональной избыточности -- возможность выполнения одинаковых действий разными средствами (применяется редко);

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

7.Перемещаемости -- отсутствие привязки к адресам в физической памяти;

8.Защиты -- ограждение программ и данных от нежелательных влияний друг на друга;

9.Независимости программ от внешних устройств.

Основные функции ядра ОС

1.Управление памятью, оперативной и виртуальной.

2.Планирование процессов - выделение процессорного времени исполняемым программам. В Linux - fork, clone, ...

3.Файловая система обеспечивает удобную работу с файлами, каталогами, соединителями и т.п. В POSIX - creat, open, read, link, sendfile, ...

4.Сетевой стек - поддержка соответствующей аппаратуры (последовательных линий, ethernet, ...) и протоколов (TCP, UDP, IP, ...).

5.Поддержка работы с драйверами устройств - обеспечение работы с имеющейся аппаратурой. Такие драйверы создают основу для работы функций ядра. Например, драйвер соответствующей ФС (ext4, btrfs, ...) должен обеспечивать работу функций read, write и т.п.

6.Управление доступом. На базовом уровне безопасность работы Linux обеспечивается установкой прав владельца, группы и прочих. Добавочные механизмы включают acl, SELinux и др.

Справку по функциям ядра Linux можно получить по команде man 2 syscalls, по команде man 2 intro можно ознакомиться с основами ОС для пользователя.

Программа sysctl в Linux позволяет получать и менять рабочие параметры ядра, например, sysctl -a распечатает эти параметры.

Хотя ядро Linux монолитное, оно допускает подключение дополнительных модулей. Это удобно для экономии памяти. В базовое ядро входит поддержка только

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

С середины нулевых Linux используется на более чем 90% суперкомпьютеров. Размер текущего ядра - приближается к 20 миллионам строк кода.

Следует различать понятия ОС и операционная оболочки. Операционная оболочка

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

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

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

и обычной прикладной программой. Для DOS стандартная операционная оболочка - это COMMAND.COM, вместо которой (командой SHELL) можно использовать и другие.

Ассемблерное ядро DOS - это функции ROM BIOS. Следующий уровень - это функции DOS, загружаемые с диска. Следующий уровень - операционная оболочка. Между ядром и оболочкой может быть более одного уровня.

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

менее надежно, так как из-за его объема риск попадания ошибочных кодов в ядро довольно велик. Размер кода моноядра Linux превысил 15 миллионов строк. Microsoft Windows и многие другие ОС также используют моноядро. Архитектура микроядра позволяет разделить функции ядра по уровням безопасности (процессоры Intel поддерживают до 4 таких уровней) соответственно их критичности. Микроядро используют системы QNX, Symbian, Minix и другими. Размер микроядра Minix 3 менее 4000 строк. Недостаток микроядра в том, что из-за того, что части ядра оказываются разделенными взаимодействие между ними замедляется.

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

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

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

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

3."Читатели-писатели" - типична для файловых систем: "читатели" могут иметь одновременный доступ к ресурсу (файлу), а "писатели" только исключительный.

4."Обедающие философы" - возникает при необходимости синхронизовать использование пересекающихся групп ресурсов. Например, процессам X, Y, Z доступны ресурсы R1 (HDD), R2 (CD-ROM), R3 (принтер). Для X нужны R1 и R2, для Y - R1 и R3, для Z - R2 и R3. [Круглый стол, N>1 философов и вилок, спагетти, речи и еда.]

Средствами синхронизации являются, в частности, семафоры (Дейкстра, 1965) или системные переменные, позволяющие приостанавливать процессы при их запросе на использование занятого ресурса. Используют также исключающие двоичные семафоры или мьютексы (mutex --- mutual exclusions). Другие средства синхронизации --- это, в частности, рандеву (ада), каналы (оккам-2), мониторы (модула-3, рубин и др.), сигналы (двойствены семафорам). Простейшее средство синхронизации --- операция wait, ожидающая окончание выполнения заданного процесса --- она входит в ядро многих ОС. Она также присутствует в

системе команд процессоров Intel 80x86 для организации работы с сопроцессорами.

Доказано, что любые задачи синхронизации разрешимы, но практически их решение чрезвычайно трудоёмко.

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

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

Рассмотрим реализацию схемы взамодействия потребителя с производителем на языке, похожем на си++. Функции producer и consumer работают параллельно. @#define N 100 //размер буфера

@int count = 0; //кол-во записей в буфере @void producer(void) {

@	int item;
@	for (;;) {
@	item = produce();	//продукция новых данных

@if (count == N) sleep(); //заблокироваться, если буфер полон

@	insert_item(item);	//передача данных в буфер
@	count++;
@ if (count == 1)
@	wakeup(consumer);	//активизировать возможно блокированного потребителя

@}

@}

@void consumer(void) {

@int item;

@for(;;) {

@if (count == 0) sleep(); //заблокироваться, если буфер пуст

@ item = remove();

//извлечение данных из буфера

@count--;

@if (count == N - 1)

@	wakeup(producer);	//активизировать возможно блокированного производителя
@	consume(item);	//использование (распечатка) данных
@ }
@}

Эта схема может привести к взаимоблокировке. Если буфер пуст, то потребитель после проверки значения count собирается вызвать sleep, но в этот момент производитель заносит данные в буфер и, обнаруживая, что потребитель заблокирован, его разблокирует. Но потребитель только собирается заблокироваться, поэтому он окажется заблокированным. Через некоторое время буфер заполнится и производитель также окажется заблокированным.

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

Семафор --- это специальная целочисленная переменная для подсчёта количества активизаций, отложенных на будущее. Значение семафора 0 означает отсутствие таких активизаций, положительное значение означает их наличие. Для семафоров вводятся две операции down (P) и up (V) --- это обобщения соответственно sleep и wakeup. Операция down проверяет, равен ли 0 семафор. Если нет, то уменьшает его значение на 1 и заканчивается. Если да, то down блокируется. Проверка значения и его изменение производятся как неделимое атомарное действие.

Операция up увеличивает значение семафора на 1. Если с этим семафором связаны приостановленные процессы, то она разблокирует один из них, завершая down. Операция up также должна быть неделимой.

Решение задачи любого количества производителей и потребителей с семафорами. @typedef int semaphore;

@semaphore mutex = 1; //управляет доступом к критической области @semaphore empty = N; //количество свободных позиций в буфере @semaphore full = 0; //количество записей в буфере

@void producer(void) {

@int item;

@for (;;) {

@	item = produce();	//продукция новых данных
@	down(&empty);	//уменьшение счётчика пустых мест
@	down(&mutex);	//вход в критическую область

@insert(item);

@	up(&mutex);	//выход из критической области
@	up(&full);	//увеличение счётчика записей

@}

@}

@void consumer(void) {

@int item;

@for(;;) {

@down(&full);

@down(&mutex);

@item = remove();

@up(&mutex);

@up(&empty);

@consume(item);

@}

@}

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

мьютексами используют две процедуры: mutex_lock --- вызывается когда процессу или нити требуется доступ к критической области, если мьютекс незаблокирован, то вызов проходит успешно и мьютекс блокируется, а если блокирован, то вызов приостанавливается, до разблокировки; mutex_unlock вызывается после выхода из критической области.

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

Пример монитора на паскалеподобном языке. @monitor ProducerConsumer;

@full, empty: condition; (* условные переменные *)

@count: integer;

@procedure insert_m(item: integer);

@if count = N then wait(full);

@insert(item);

@count := count + 1;

@if count = 1 then signal(empty)

@end;

@function remove_m: integer;

@if count = 0 then wait(empty);

@remove_m := remove;

@count := count - 1;

@if count = N - 1 then signal(full)

@end;

@count := 0;

@end;

@coprocedure producer;

@while true do

@ProducerConsumer.insert_m(produce) @end;

@coprocedure consumer;

@while true do

@consume(ProducerConsumer.remove_m); @end;

Структура файловой системы Linux (Unix)

Знаком каталога в Unix является наклонная черта, / (slash). Заглавные и строчные буквы различаются. В Linux дерево каталогов имеет стандартную структуру. Оно состоит из четырех частей: корневой файловой системы

и файловых систем usr, var и home.

Корневая файловая система содержит все необходимое для загрузки после включения компьютера и подключения затем других файловых систем. Кроме того, она содержит средства для своего восстановления после сбоев, в частности, средства-архиваторы для использования сохраненных ранее своих копий. Физически корневая файловая система может быть жестким диском или разделом на нем, сетевым диском, ROM/Flash-диском. Логически --- это корневой каталог вместе с содержимым каталогов bin, dev, etc, lib, proc, sbin и некоторыми

другими. Содержащиеся в этой системе ресурсы отражают аппаратную специфику компьютера.

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

Таким образом, эту файловую систему можно иметь в единственном числе для всех компьютеров в сети. Для повышения надежности ее можно устанавливать с атрибутом ``только для чтения''.

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

Файловая система home содержит личные каталоги пользователей системы. Логически она состоит из содержимого каталога /home.

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

@	/	;корневой каталог
@	bin	;команды, используемые во время загрузки системы и

@;пользователем (binary)

@ dev

;специальные "файлы", соответствующие аппаратуре,

@;поддерживаемой системой (device)

@ etc

;файлы инициализации конфигурации системы

@home

@ lib

;динамически связываемые библиотеки (DLL, shared),

@;используемые программами при загрузке (library)

@ mnt

;каталог, используемый для присоединения

@;других файловых систем; он либо пуст, либо состоит из

@;пустых каталогов, соответствующих другим файловым системам,

@;например, каталог floppy может быть использован для работы с

@;гибким диском формата MS-DOS, а каталог CDROM --- с

@;лазерным компакт-диском (mount).

@	media	;аналогичен mnt, используется для съёмных устройств
@	proc	;состоит из "файлов", описывающих в текстовом формате текущее

@;состояние системы: памяти, процессов (задач) и т.п. (process)

@	root	;личный каталог администратора системы
@	sbin	;отличается от bin тем, что команды из него предназначены

@;прежде всего администратору системы, хотя их можно

@;использовать и любому пользователю (system binary)

@ tmp

;для временных файлов, уничтожаемых после завершения работы

@;системы (temporary)

@usr

@X11R6 ;файлы X Window System (графический интерфейс)

@	bin ;программы для пользователя

@include;файлы-заголовки для программ на C и C++

@	lib ;не меняющиеся файлы данных для программ, в частности,

@;библиотеки модулей, зависящие от аппаратуры

@local ;файлы, установленные сверх стандартной установки; этот

@;каталог повторяет структуру каталога usr

@	sbin	;программы для администратора, не нужные для корневой
@		;файловой системы
@	share ;отличается от lib независимостью от аппаратуры
@	doc		;документация
@	dict		;словари для программ проверки правописания
@	games
@	info		;сжатая гипертекстная документация в формате GNU info
@	man		;документация в стандартном для Unix формате страниц
@			;руководства
@	src	;исходные тексты программ, в частности, самой ОС

@var

@	lib ;меняющиеся файлы данных для программ

@log ;отчеты

@spool ;данные спулеров

@www ;страницы для www-сервера

Спулер --- программа буферизованной печати, работающая в фоновом режиме.

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

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

как правило, 1КБ, но может быть 2 или 4 КБ. Работа с блоками скрыта от пользователя, которому предоставляется возможность работать с каталогами и файлами. Связь имен каталогов и файлов с блоками осуществляется через i-узлы. Число i-узлов фиксировано для файловой системы, размещенной на одном физическом устройстве. Каждому файлу соответствует i-узел. Каталог --- это файл из списка пар, состоящих из имени файла или подкаталога вместе со ссылкой на соответствующий ему i-узел. В i-узле содержится вся информация об атрибутах, соответствующего ему файла.

Основные атрибуты файла Unix:

-время создания i-узла, т.е. время создания файла;

-время последнего изменения файла;

-время последнего обращения к файлу;

-время уничтожения файла;

-счетчик экземпляров файла (``жестких'' связей, hard links);

-атрибуты защиты;

-ссылка на хозяина;

-ссылка на группу пользователей;

-размер файла в байтах;

-список блоков, выделенных для файла.

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

Если нужно иметь один и тот же файл в разных частях файловой системы, то можно просто скопировать его в эти части, но это привет к ненужному расходу дискового пространства. Unix вместо подобного копирования имеет возможность двумя способами создавать соединители с файлами или каталогами. Первый --- это жесткие соединители (hard links), количество которых для данного файла увеличивается на единицу при добавлении указателя на i-узел, соответствующий данному файлу. Жестких соединители могут связывать имена объектов ФС только в рамках одной физической файловой системы. Как правило, можно создавать жёсткие связи только с файлами, но не с каталогами. Они ведут себя как

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

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

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

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

запрещение на каждую из трех возможных видов операций. Например, атрибуты защиты файла rwxr-x--x (751 --- три 8-е цифры) означают, что хозяин может файл читать, изменять и выполнять, группа --- читать и выполнять, а все остальные пользователи только выполнять. Администратор системы или суперпользователь (обычно имеет имя root) может всегда осуществлять любые операции

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

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

Есть еще три атрибута --- они соответствуют трём старшим битам в первой тройке разрядов атрибутов защиты. Если установлен первый

разряд (s - set user ID), то программа при выполнении получает права своего владельца, а не того, кто ее исполняет. Например, программа passwd позволяет любому пользователю менять свой пароль благодаря установке

этого бита --- эта программа должна иметь право писать в системные файлы, доступ к которым обычным пользователям закрыт. Если установлен второй разряд (g - group user ID), то программа при выполнении получает права своей

группы. Третий разряд (t) для файлов уже не используется

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

может только их владелец или владелец каталога --- это обычно используется с каталогом /tmp. Установка второго бита (группы) для каталога означает, что вновь создаваемые файлы в этом каталоге получают группу от каталога, а не создателя. Все атрибуты, таким образом, это 4-ка 8-ых цифр, например, 5755 означает rwsr-xr-t, т.~е. дополнительные атрибуты совмещаются при распечатке с атрибутом x.

Для более гибкого контроля защиты файлов можно как расширение использовать средства ACL --- Access Control List --- они позволяют для каждого ресурса устанавливать списки пользователей и групп.

При работе с Linux можно работать с практически любыми файловыми системами, в частности,

FAT (File Allocation Table, MS-DOS), VFAT (MS Windows с длинными именами), NTFS (Windows NT),

HPFS (High Performance File System, OS/2),

ISO 9660 (CD/DVD-ROM), UDF (CD/DVD-ROM) и многими другими. Изначально в качестве основной Linux использовала файловую систему Minix (имена

файлов до 14 символов), с середины 1990-х --- ext2 (The Extended 2 File System, имена файлов до 255 символов), ext3 (ext2 с "журналом", медленнее, но устойчива к сбоям), ext4 (резервирование места для файлов для уменьшения фрагментации), реже используются XFS (быстрая, но чувствительная к

сбоям) или ReiserFS (хэш-функции для поиска файлов, запись маленьких файлов непосредственно на i-узлах). Перспективной считается ФС ZFS от

Sun/Oracle для ОС Solaris, где, например, копии создаются жесткими соединителями и можно объединять несколько физических носителей в один логический.

ВZFS очень много внимание уделено надежности. Эта ФС позволяет работать с данными очень большого размера, далеко превосходящими текущие возможности техники, например, размер носителя может быть до 2^64 (более 10^29) байт.

ВZFS можно делать снимки, шифровать и сжимать данные. Лицензия не совместима с возможностью использовать ее как основную в Linux.

Другая перспективная файловая система --- это btrfs (B-tree file system) фирмы Oracle. Ее некоторые возможности.

* объединение разделов (томов)

*изменение размера разделов без потери данных

*может размещать маленькие файлы на i-узле

*подтома - каталоги которые можно монтировать как разделы

*снимки состояния разделов (архивация данных средствами самой системы) - учитываются

только изменения по отношению к последнему снимку

*встроенная поддержка RAID (redundant array of independent disks) - возможность одновременного сохранения данных на нескольких дисках

*встроенное сжатие данных

*макс. длина имени файла 255 байт

Вименах файлов и каталогов не допустимо использование символа наклонная черта (slash).

Простейшие утилиты Linux, опция --help

man, info, apropos (информация по командам, форматам файлов и т.п.) date, df, free, who (справки по ресурсам)

cp, ln, mv, rm, ls, cd, mkdir, rmdir, pwd (манипулирование объектами файловой системы)