Ответы к вопросам по дисциплине «Операционная система UNIX»

Рассмотрим достаточно популярную в программировании задачу на работу с "длинными" числами. Реально с "астрономическими" или "микроскопическими" числами приходится сталкиваться не так уж и часто. Тем не менее, упражнения, рассматриваемые в этой публикации, могут послужить хорошей тренировкой в области программирования и занять достойное место в классах с углубленным изучением информатики или на кружках по программированию. Алгоритмы, представленные ниже, записаны на Turbo Pascal, версия 7.0. При желании или необходимости они могут легко быть адаптированы к любой другой программной среде.

Диапазон представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (впрочем, для действительных величин это замечание тоже актуально). Поэтому при решении задач всегда приходится действовать с оглядкой, — как бы не допустить возникновения ошибки выхода за диапазон или переполнения. Например, вычисляя факториал (n! = 1 * 2 * 3 * … * n), в диапазоне представления величин типа Integer удастся правильно получить только 7! = 5040, а в диапазоне представления типа LongInt — 12! = 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. Поэтому полезно для получения точных значений при действиях с многозначными числами разработать другие способы представления таких чисел, алгоритмы выполнения арифметических и других операций, процедуры ввода и вывода результатов и т.д.

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

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

Const MNax = 2000;

Type Digit = 0..9;

DlChislo = Array[1..Nmax] Of Digit;

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

1) ввод "длинного" числа;

2) собственно умножение двух "длинных" чисел;

3) вывод "длинного" числа;

4) определение количества цифр в записи числа.

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

{Процедура преобразования длинного числа, записанного

в виде строки, в массив цифр; переменная OK принимает значение True,

если в записи числа нет посторонних символов, отличных от десятичных

цифр, иначе — false}

Procedure Translate(S : String; Var A : DlChislo; Var OK : Boolean);

Var I : Word;

Begin

Zero(A); I := Length(S); OK := True;

While (I >= 1) And OK Do

Begin

If S[I] In ['0'..'9']

Then A[Length(S)- I + 1]:= Ord(S[I]) - 48

Else OK := False; I := I - 1

End

End;

В процедуре вызывается подпрограмма Zero(A), назначение которой — запись нуля в каждый разряд длинного числа. Вот текст этой процедуры:

{Процедура обнуления длинного числа}

Procedure Zero(Var A : DlChislo);

Var I : Integer;

Begin

For I := 1 To NMax Do A[I] := 0;

End;

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

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

{Функция определения количества цифр в записи длинного числа}

Function Dlina(C : DlChislo) : Integer;

Var I : Integer;

Begin

I := NMax;

While (I > 1) And (C[I] = 0) Do I := I - 1;

Dlina := I

End;

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

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

{Процедура умножения длинных чисел.

A, B — множители, C — произведение}

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);

Var I, J : Integer; P : Digit; VspRez : 0..99;

Begin

Zero(C);

For I := 1 To Dlina(A) Do {Цикл по количеству цифр

в первом числе}

Begin

P := 0; {Первоначально перенос равен нулю}

For J := 1 To Dlina(B) Do {Цикл по количеству цифр

во втором числе}

Begin

VspRez := A[I] * B[J] + P + C[I + J - 1];

C[I + J - 1] := VspRez Mod 10; {Очередное значение цифры в

разряде I + J - 1}

P := VspRez Div 10 {Перенос в следующий разряд}

End;

C[I + J] := P {последний перенос может быть отличен от нуля,

запишем его в пока ещё свободный разряд}

End

End;

Сейчас приведем листинг программы целиком.

Program DlUmn;

Const NMax = 2000;

Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;

Var S : String;

M, N, R, F : DlChislo;

I, MaxF : Word;

Logic : Boolean;

{Процедура обнуления длинного числа}

Procedure Zero(Var A : DlChislo);

Var I : Integer;

Begin

For I := 1 To NMax Do A[I] := 0;

End;

{Функция определения количества цифр в записи длинного числа}

Function Dlina(C : DlChislo) : Integer;

Var I : Integer;

Begin

I := NMax;

While (I > 1) And (C[I] = 0) Do I := I - 1;

Dlina := I

End;

{Процедура печати длинного числа}

Procedure Print(A : DlChislo);

Var I : Integer;

Begin

For I := Dlina(A) DownTo 1 Do Write(A[I] : 1);

WriteLn

End;

{Процедура преобразования длинного числа в массив цифр}

Procedure Translate(S : String; Var A : DlChislo;

Var OK : Boolean);

Var I : Word;

Begin

Zero(A); I := Length(S); OK := True;

While (I >= 1) And OK Do

Begin

If S[I] In ['0'..'9']

Then A[Length(S) - I+ 1] := Ord(S[I]) - 48

Else OK := False;

I := I - 1

End

End;

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);

Var I, J : Integer; P : Digit; VspRez : 0..99;

Begin

Zero(C);

For I := 1 To Dlina(A) Do

Begin P := 0;

For J := 1 To Dlina(B) Do

Begin

VspRez := A[I] * B[J] + P + C[I + J - 1];

C[I + J - 1] := VspRez Mod 10;

P := VspRez Div 10

End;

C[I + J] := P

End

End;

{Основная программа}

Begin

Repeat {повторяем ввод, пока число не будет введено правильно}

Write('Введите первый множитель: ');

ReadLn(S); Translate(S, M, Logic)

Until Logic;

Repeat

Write('Введите второй множитель: ');

ReadLn(S); Translate(S, N, Logic)

Until Logic;

Multiplication(M, N, R); Print(R)

End.

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

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

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

Begin

MaxF := 810;

Zero(F);

F[1] := 1;

For I := 1 To MaxF Do

Begin

Str(I, S); {преобразование числа I к строковому типу S}

Translate(S, M, Logic);

Multiplication(F, M, F);

Print(F);

WriteLn('Факториал числа ', I : 4, ' содержит ', Dlina(F), ' цифр.')

End

End.

Ответы к вопросам по дисциплине «Операционная система UNIX»

1. Операционная система UNIX

- введение

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

- история создания

· В 1965 году фирма Bell Telephone Laboratories, объединив свои усилия с компанией General Electric и проектом MAC Массачусетского технологического института, приступили к разработке новой операционной системы, получившей название Multics. Перед системой Multics были поставлены задачи - обеспечить одновременный доступ к ресурсам ЭВМ большого количества пользователей, обеспечить достаточную скорость вычислений и хранение данных и дать возможность пользователям в случае необходимости совместно использовать данные. Многие разработчики, впоследствии принявшие участие в создании ранних редакций системы UNIX, участвовали в работе над системой Multics в фирме Bell Laboratories. Хотя первая версия системы Multics и была запущена в 1969 году на ЭВМ GE 645, она не обеспечивала выполнение главных вычислительных задач, для решения которых она предназначалась, и не было даже ясно, когда цели разработки будут достигнуты. Поэтому фирма Bell Laboratories прекратила свое участие в проекте.

· По окончании работы над проектом Multics сотрудники исследовательского центра по информатике фирмы Bell Laboratories остались без "достаточно интерактивного вычислительного средства" [Ritchie 84a]. Пытаясь усовершенствовать среду программирования, Кен Томпсон, Дэннис Ричи и другие набросали на бумаге проект файловой системы, получивший позднее дальнейшее развитие в ранней версии файловой системы UNIX. Томпсоном были написаны программы, имитирующие поведение предложенной файловой системы в режиме подкачки данных по запросу, им было даже создано простейшее ядро операционной системы для ЭВМ GE 645. В то же время он написал на Фортране игровую программу "Space Travel" ("Космическое путешествие") для системы GECOS (Honeywell 635), но программа не смогла удовлетворить пользователей, поскольку управлять "космическим кораблем" оказалось сложно, кроме того, при загрузке программа занимала много места. Позже Томпсон обнаружил малоиспользуемый компьютер PDP-7, оснащенный хорошим графическим дисплеем и имеющий дешевое машинное время.

· Создавая программу "Космическое путешествие" для PDP-7, Томпсон получил возможность изучить машину, однако условия разработки программ потребовали использования кросс-ассемблера для трансляции программы на машине с системой GECOS и использования перфоленты для ввода в PDP-7. Для того, чтобы улучшить условия разработки, Томпсон и Ричи выполнили на PDP-7 свой проект системы, включивший первую версию файловой системы UNIX, подсистему управления процессами и небольшой набор утилит. В конце концов, новая система больше не нуждалась в поддержке со стороны системы GECOS в качестве операционной среды разработки и могла поддерживать себя сама. Новая система получила название UNIX, по сходству с Multics его придумал еще один сотрудник Исследовательского центра по информатике Брайан Керниган.

· Несмотря на то, что эта ранняя версия системы UNIX уже была многообещающей, она не могла реализовать свой потенциал до тех пор, пока не получила применение в реальном проекте. Так, для того, чтобы обеспечить функционирование системы обработки текстов для патентного отдела фирмы Bell Laboratories, в 1971 году система UNIX была перенесена на ЭВМ PDP-11. Система отличалась небольшим объемом: 16 Кбайт для системы, 8 Кбайт для программ пользователей, обслуживала диск объемом 512 Кбайт и отводила под каждый файл не более 64 Кбайт. После своего первого успеха Томпсон собрался было написать для новой системы транслятор с Фортрана, но вместо этого занялся языком Би (B), предшественником которого явился язык BCPL. Би был интер-претируемым языком со всеми недостатками, присущими подобным языкам, поэтому Ричи переделал его в новую разновидность, получившую название Си (C) и разрешающую генерировать машинный код, объявлять типы данных и определять структуру данных. В 1973 году система была написана заново на Си, это был шаг, неслыханный для того времени, но имевший огромный резонанс среди сторонних пользователей. Количество машин фирмы Bell Laboratories, на которых была инсталлирована система, возросло до 25, в результате чего была создана группа по системному сопровождению UNIX внутри фирмы.

· В то время корпорация AT&T не могла заниматься продажей компьютерных продуктов в связи с соответствующим соглашением, подписанным ею с федеральным правительством в 1956 году, и распространяла систему UNIX среди университетов, которым она была нужна в учебных целях. Следуя букве соглашения, корпорация AT&T не рекламировала, не продавала и не сопровождала систему.

· Несмотря на это, популярность системы устойчиво росла. В 1974 году Томпсон и Ричи опубликовали статью, описывающую систему UNIX, в журнале Communications of the ACM, что дало еще один импульс к распространению системы. К 1977 году количество машин, на которых функционировала система UNIX, увеличилось до 500, при чем 125 из них работали в университетах. Система UNIX завоевала популярность среди телефонных компаний, поскольку обеспечивала хорошие условия для разработки программ, обслуживала работу в сети в режиме диалога и работу в реальном масштабе времени (с помощью системы MERT). Помимо университетов, лицензии на систему UNIX были переданы коммерческим организациям. В 1977 году корпорация Interactive Systems стала первой организацией, получившей права на перепродажу системы UNIX с надбавкой8 к цене за дополнительные услуги, которые заключались в адаптации системы к функционированию в автоматизированных системах управления учрежденческой деятельностью. 1977 год также был отмечен "переносом" системы UNIX на машину, отличную от PDP (благодаря чему стал возможен запуск системы на другой машине без изменений или с небольшими изменениями), а именно на Interdata 8/32.

· С ростом популярности микропроцессоров другие компании стали переносить систему UNIX на новые машины, однако ее простота и ясность побудили многих разработчиков к самостоятельному развитию системы, в результате чего было создано несколько вариантов базисной системы. За период между 1977 и 1982 годом фирма Bell Laboratories объединила несколько вариантов, разработанных в корпорации AT&T, в один, получивший коммерческое название UNIX версия III. В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых особенностей, назвав новый продукт UNIX версия V, и эта версия стала официально распространяться корпорацией AT&T с января 1983 года. В то же время сотрудники Калифорнийского университета в Бэркли разработали вариант системы UNIX, получивший название BSD 4.3 для машин серии VAX и отличающийся некоторыми новыми, интересными особенностями.

· К началу 1984 года система UNIX была уже инсталлирована приблизительно на 100000 машин по всему миру, причем на машинах с широким диапазоном вычислительных возможностей - от микропроцессоров до больших ЭВМ - и разных изготовителей. Ни о какой другой операционной системе нельзя было бы сказать того же. Популярность и успех системы UNIX объяснялись несколькими причинами:

· Система написана на языке высокого уровня, благодаря чему ее легко читать, понимать, изменять и переносить на другие машины. По оценкам, сделанным Ричи, первый вариант системы на Си имел на 20-40 % больший объем и работал медленнее по сравнению с вариантом на ассемблере, однако преимущества использования языка высокого уровня намного перевешивают недостатки Наличие довольно простого пользовательского интерфейса, в котором имеется возможность предоставлять все необходимые пользователю услуги.

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

· Наличие иерархической файловой системы, легкой в сопровождении и эффективной в работе.

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

· Наличие простого, последовательного интерфейса с периферийными устройствами.

· Система является многопользовательской, многозадачной; каждый пользователь может одновременно выполнять несколько процессов.

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

· Простота и последовательность вообще отличают систему UNIX и объясняют большинство из вышеприведенных доводов в ее пользу.

· Хотя операционная система и большинство команд написаны на Си, система UNIX поддерживает ряд других языков, таких как Фортран, Бейсик, Паскаль, Ада, Кобол, Лисп и Пролог.

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

- версии UNIX

- архитектурные особенности UNIX

- влияние UNIX на эволюцию операционных систем

2. Архитектура UNIX

- структура UNIX

Логическая файловая система - основные каталоги и их назначение

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

Основные каталоги логической файловой системы UNIX

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

Физические файловые системы UNIX - основные компоненты

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

· Имеется много типов физических файловых систем, например FAT16 и NTFS, с разной структурой. Более того, имеется множество типов физических файловых систем UNIX (ufs, s5fs, ext2, vxfs, jfs, ffs и т.д.). Ниже мы рассмотрим основные их общие особенности.

· Физическая файловая система UNIX занимает раздел диска и состоит из таких основных компонентов:

o Суперблок (superblock). Содержит общую информацию о файловой системе.

Массив индексных дескрипторов (ilist). Содержит метаданные всех файлов файловой системы. Индексный дескриптор (inode) содержит информацию о статусе файла и указывает на расположение данных этого файла. Ядро обращается к индексному дескриптору по индексу в массиве. Один дескриптор является корневым для физической файловой системы, через него обеспечивается доступ к структуре каталогов и файлов после монтирования файловой системы. Размер массива индексных дескрипторов является фиксированным и задается при создании физической файловой системы.

o Блоки хранения данных. Данные обычных файлов и каталогов хранятся в блоках. Обработка файла осуществляется через индексный дескриптор, содержащий ссылки на блоки данных.

Суперблок

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

· Суперблок содержит:

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

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

-размер массива индексных дескрипторов;

-количество свободных блоков;

-количество свободных индексных дескрипторов;

-флаги;

-размер логического блока файловой системы (512, 1024, 2048, 4096, 8192).

-список номеров свободных индексных дескрипторов;

-список адресов свободных блоков.

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

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

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

- ядро системы

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

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

· Основные части:

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

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

Управление процессами

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

Драйверы устройств

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

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

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

3. Работа в ОС UINX

- файловая система

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

Особенности файловой системы

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

· Каждый файл в древовидной структуре расположен в определенном хранилище файлов – каталоге, каждый каталог, в свою очередь, также расположен в некотором каталоге. Таким образом, по принципу вложения элементов файловой системы (файлов и каталогов) друг в друга строится дерево, вершинами которого являются непустые каталоги, а листьями – файлы или пустые каталоги. Корень такого дерева имеет название корневой каталог и обозначается каким-либо специальным символом или группой символов (например, «C:» в операционной системе Windows). Каждому файлу соответствует некоторое имя, определяющее его расположение в дереве файловой системы. Полное имя файла состоит из имен всех вершин дерева файловой системы, через которые можно пройти от корня до данного файла (каталога), записывая их слева направо и разделяя специальными символами-разделителями.

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

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

· Таким образом, каждый файл характеризуется одним i-node, но может быть связан с несколькими именами – в UNIX это называют жёсткими ссылками .При этом, удаление файла происходит тогда, когда удаляется последняя жёсткая ссылка на этот файл.

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

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

Специальный файл устройства

· Обеспечивает доступ к физическому устройству. При создании такого устройства указывается тип устройства (блочное или символьное), старший номер – индекс драйвера в таблице драйверов операционной системы и младший номер – параметр, передаваемый драйверу, поддерживающему несколько устройств, для уточнения о каком «подустройстве» идет речь (например, о каком из нескольких IDE-устройств или COM-портов).

Именованный канал

Используется для передачи данных между процессами, работает по принципу двунаправленной очереди (FIFO). Является одним из способов обмена между изолированными .

Символическая ссылка

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

- структура файловой системы

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

· В мире UNIX существует несколько разных видов файловых систем со своей структурой внешней памяти. Наиболее известны традиционная файловая система UNIX System V (s5) и файловая система семейства UNIX BSD (ufs). Файловая система s5 состоит из четырех секций (1,a). В файловой системе ufs на логическом диске (разделе реального диска) находится последовательность секций файловой системы (2,b).

Кратко опишем суть и назначение каждой области диска.

· Boot-блок содержит программу раскрутки, которая служит для первоначального запуска ОС UNIX. В файловых системах s5 реально используется boot-блок только корневой файловой системы. В дополнительных файловых системах эта область присутствует, но не используется.

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

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

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

· Блоки данных - в этой части файловой системы хранятся реальные данные файлов. В случае файловой системы ufs все блоки данных одного файла пытаются разместить в одной группе цилиндров. Размер блока данных определяется при форматировании файловой системы командой mkfs и может быть установлен в 512, 1024, 2048, 4096 или 8192 байтов.

- процессы

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

Контекст процесса

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

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

· Идентификатор процесса (PID)

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

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

· Идентификатор родительского процесса (PPID)

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

Очевидно, что в такой схеме должен присутствовать один процесс с особым статусом: он должен быть порожден ядром операционной системы и будет являться родительским для всех остальных процессов в системе. В UNIX такой процесс имеет собственное имя — init. Подробнее об этом процессе сказано в разделе «Процесс init».

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

Каждый процесс в любой момент времени находится в одном из нескольких определенных состояний: инициализация, исполнение, приостановка, ожидание ввода-вывода, завершение и т. п. (см. 1, «Состояния процесса в UNIX»).

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

· Идентификаторы пользователя

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

· Приоритет процесса

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

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

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

· Наиболее распространенным алгоритмом планирования в системах разделения времени является кольцевой режим (Round Robin). Основной смысл алгоритма состоит в том, что время процессора делится на кванты фиксированного размера, а процессы, готовые к выполнению, выстраиваются в кольцевую. У этой очереди имеются два указателя — начала и конца. Когда процесс, выполняющийся на процессоре, исчерпывает свой квант процессорного времени, он снимается с процессора, ставится в конец очереди, а ресурсы процессора отдаются процессу, находящемуся в начале очереди. Если выполняющийся на процессоре процесс откладывается (например, по причине обмена с некоторым внешним устройством) до того, как он исчерпает свой квант, то после повторной активизации он становится в конец очереди (не смог доработать — не вина системы). Это прекрасная схема разделения времени в случае, когда все процессы одновременно помещаются в оперативной памяти.

Рисунок 2. Схема планирования с кольцевой очередью

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

Рисунок 3. Схема планирования с кольцевой очередью и приоритетами

- устройства

· Любое устройство, подключенное к системной шине (или к шине PCI, или USB), обладает определённым интерфейсом (заранее известными идентификаторами, номерами портов ввода и вывода и т. п.), через который производится обмен данными и сообщениями с устройством. Таким образом, в первую очередь операционная система должна иметь модули, осуществляющее управление шинами, прерываниями, DMA и т. п. Эти модули обычно загружаются при старте системы.

Сами внешние устройства по типу доступа к ним могут быть классифицированы несолькими способами:

· символьные — чтение и запись данных производится побайтно (например, COM-порт);

· блочные — чтение и запись данных производится блоками (например, секторами в жётском диске);

· последовательного доступа — читать и записывать данные можно только последовательно (например, коммуникационные каналы);

· произвольного доступа — возможно обращение к данным по индексу (диски);

· синхронные — передают данные только по команде (например, принтер);

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

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

· В операционной системе UNIX большинство внешних устройств доступно пользовательским программам в виде специальных файлов. Эти файлы могут быть, соответственно, двух типов — символьные и блочные. Традиционно, все файлы устройств располагаются в каталоге /dev и имеют имена, соответствующие назначению устройства. Например, в операционной системе Linux устройства терминала обозначаются как /dev/tty0, /dev/tty2 и т. д. с увеличением порядкового номера, жёсткий диск — /dev/sda, а порт PS/2 — /dev/psaux. Названия однотипных устройств обычно отличаются целым числом. Программы могут открывать, читать и записывать данные в файлы устройств как в обычные файлы, при этом операционная система транслирует пользовательские запросы драйверу соответствующего устройства.

Рисунок 1. Взаимодействие с устройством через файл

· Таким образом, файл устройства является одним из интерфейсов взаимодействия процессов с устройствами. Каждый файл устройства имеет два номера — старший и младший. По этим номерам операционная система определяет, какой драйвер должен использоваться при обращении к этому файлу.

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

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

/dev/console

устройство соответствует активной в данный момент терминальной линии (виртуальной консоли);

/dev/null

«чёрная дыра» — любая информация, записанная в этот файл, пропадает безвозвратно, обычно используется для поглощения ненужного вывода программ;

/dev/random и /dev/urandom

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

/dev/stdin, /dev/stdout и /dev/stderr

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

/dev/zero

устройство генерирует нули — из этого устройства можно прочитать сколько угодно нулевых байт.

- пользователи системы

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

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

Для отслеживания владельцев процессов и файлов используются числовые идентификаторы. Идентификатор пользователя и группы - целое число (обычно) в диапазоне от 0 до 65535. Присвоение уникального идентификатора пользователя выполняется при заведении системным администратором нового регистрационного имени. Значения идентификатора пользователя и группы - не просто числа, которые идентифицируют пользователя, - они определяют владельцев файлов и процессов. Среди пользователей системы выделяется один пользователь - системный администратор или суперпользователь, обладающий всей полнотой прав на использование и конфигурирование системы. Это пользователь с идентификатором 0 и регистрационным именем root.

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

По мере развития ОС среди обычных пользователей выделились так называемые специальные пользователи. Они, как правило, имеют зарезервированные имена (например, guest, bin, uucp и т.п.) и номера UID и GID (например, меньше 100). Хотя в защите UNIX нет никакого особого механизма, отличающего специального пользователя от обычного, можно сказать, что первый имеет еще меньше прав, чем второй. В частности, специальным пользователям обычно нельзя зайти в систему нормальным образом. Самым интересным для нас примером специального пользователя является анонимный пользователь ftp, который так и называется - anonymous, или ftp.

Наконец, условно к категории пользователей можно отнести человека, удаленно подключившегося (обычно по протоколу TELNET) к вашей машине и взаимодействующего с одной из программ-демонов (в современной терминологии такие программы называются серверами). Эти программы обычно стартуют при загрузке машины, чаще всего от имени суперпользователя, и постоянно активны как процессы, что позволяет пользователю в любой момент удаленно подключаться к ним, но при этом он не имеет никаких прав на чтение/запись информации на вашем компьютере и вообще не идентифицируется системой UNIX (команда who). Однако он может исполнять некоторые команды - не программы UNIX, а команды-запросы к тому демону, к которому он подключен. Так, подключившись по протоколу TELNET на 25-й порт, можно вводить команды SMTP-сервера, например mail или ехрn. Последний тип пользователя (назовем его псевдопользователь) оказывается чуть ли не самым важным для нашего рассмотрения, так как, не обладая никакими правами и обязанностями (кстати, от него не требуется аутентификации, учет по нему тоже не ведется), он взаимодействует с демонами, которые практически всегда имеют полномочия суперпользователя.

Итак, условно иерархию пользователей на UNIX-машине можно представить следующим образом:

Суперпользователь - неограниченные права.

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

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

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

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

Таким образом, задачей хакера является несанкционированное получение привилегий более высокого уровня. (Заметим, что необязательно конечной целью хакера является получение именно привилегий суперпользователя - вирус Морриса, например, даже и не пытался сделать этого.) Эту задачу он, очевидно, может попытаться решить различными путями: либо получить сразу требуемые привилегии, либо постепенно наращивать их. Рассмотрим далее типовые сценарии получения привилегий и средства UNIX, делающие их возможными.

"Сразу в дамки" - имея привилегии третьего уровня, хакер получает права суперпользователя. Как уже отмечалось, такой фантастический прыжок возможен благодаря механизму демонов UNIX, отвечающих за обработку удаленных запросов. Так как эти демоны чаще всего выполняются от имени суперпользователя, то все, что нужно псевдопользователю, - это знать существующие "дыры" или ошибки в этих демонах (или найти самому), которые позволят эксплуатировать их нестандартным или запрещенным образом. Обычно это сводится к возможности удаленно выполнить от их имени любую команду на атакуемом хосте, какую конкретно - зависит от намерений и характера хакера. Иногда это может быть создание ошибочной ситуации, приводящей к аварийному завершению демона с выдачей дампа памяти на диск, содержащий весьма полезную для хакера информацию (например, кэшированные пароли). Типичными примерами уязвимых демонов были и остаются sendmail, ftpd, fingerd. Новые демоны (типа httpd или talkd) имеют гораздо меньшую историю эксплуатации, поэтому известно меньшее число их дыр и, соответственно, они перспективнее для поиска новых.

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

"Из специального - в обычного, или выше". Этот сценарий очень похож на предыдущий, с тем исключением, что для хакера требуются начальные привилегии второго уровня (иначе говоря - запущен некоторый дополнительный сервис). Для четкого отличия таких атак от первого типа будем считать, что злоумышленник всегда проходит некую (пусть примитивную) идентификацию и, возможно, аутентификацию. Это не очень серьезное допущение, большинство хостов поддерживают некоторый удобный (например, анонимный ftp) или необходимый (типа tftp для удаленной загрузки бездисковых станций) сервис. Привилегии второго уровня могут дать возможность хакеру читать некоторые файлы (например, из ~ftp/pub) и, что самое главное, записывать свои файлы на ваш компьютер (в каталог типа ~ftp/incoming). С другой стороны, так как пользователь регистрируется на вашем компьютере, в его файлах-протоколах остается некоторая информация о подключении.

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

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

"Маловато будет: из обычного - в суперпользователи". Этот сценарий, пожалуй, наиболее прост и широко распространен. Подавляющее большинство сообщений о так называемых "дырах" в UNIX относится именно к нему. Для его осуществления злоумышленник должен уже быть обычным пользователем (иногда говорят, что он имеет бюджет, или account) на том компьютере, который он собирается взламывать. Это, с одной стороны, серьезное ограничение на масштабность проникновения, с другой стороны - большинство утечек информации происходит через "своих", через подкупленного сотрудника, который пусть и не имеет больших полномочий, но уж входное имя на секретный компьютер у него есть.

Своей осуществимостью атаки данного рода обязаны очередному недостатку безопасности UNIX, который называется механизмом SUID/SGID-процессов. Не будем сейчас подробно останавливаться на необходимости и причинах появления такого механизма в этой операционной системе, отметим лишь, что многим системным программам (которые могут быть запущены любым, в том числе и непривилегированным пользователем) для правильного функционирования необходимы дополнительные полномочия. Приведем хрестоматийный пример изменения пользователем пароля самому себе. Не вызывает сомнения, что пользователь может иметь право на подобную операцию, однако в терминах UNIX это равносильно наличию права на запись в общий для всех пользователей файл /etc/ passwd, что, очевидно, недопустимо. Поэтому программа, осуществляющая смену пароля пользователя, выполняется не от имени запустившего его пользователя, а от имени суперпользователя (который, естественно, имеет право на запись в файл /etc/passwd). Для этого она обладает специальным атрибутом SUID/SGID, означающим смену идентификатора пользователя и/или группы у запущенного процесса.

Такая особенность UNIX, нарушающая, безусловно, исходную модель разграничения доступа, считалась бы "нехорошей", будь она всего у одной программы passwd. Однако оказывается, что этот атрибут необходим целому множеству программ, порой очень сложных. Отсюда ясно, что злоумышленник, найдя ошибку в одной из программ, обладающих атрибутом SUID root, может от ее (то есть суперпользователя) имени произвести некоторые действия. Стандартным приемом считается копирование файла с командным интерпретатором (sh или csh) и установка на него атрибута SUID root. Таким образом, злоумышленник имеет под рукой стандартную программу sh, но все команды в ней он исполняет от имени суперпользователя.

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

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

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

&q