Проектирование гипотетической операционной системы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ, НАУКИ, МОЛОДЕЖИ и СПОРТА УКРАИНЫ

Государственное высшее учебное заведение

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра “Прикладная математика и информатика”

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине «Теория операционных систем »

Тема: «Проектирование гипотетической операционной системы»

Руководитель:

Ст. преп. каф. ПМИ А. В. Чернышева

Отметка о защите  _____________

«____» _____________ 2012 г.

Выполнил:

студент  гр. ЦПИН-11п Н. А. Астафьев

Донецк, 2012 г.

Утверждено

зав. кафедры ПМИ

_________ Башков Е. А.

«____» ________ 2012 г.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

на курсовую работу по дисциплине

«Теория операционных систем»

студента группы ЦПИН-11п

Тема: "Проектирование гипотетической операционной системы"

Задача к варианту № 1:

1. Режим работы ОС: мультипрограммный, многопользовательская защита, интерактивный, пакетный.

2. Управление  процессами: абсолютные приоритеты, статические приоритеты.

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

4. Организация  оперативной памяти: динамические разделы.

5. Перечень  внешних устройств: видеотерминал, НМД.

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

РЕФЕРАТ

Курсовой проект: 43 листа пояснительной записки, 14 рисунков, 8 ссылок.

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

При создании проекта применялся научный и экспериментально-аналитический подход.

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

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

ОПЕРАЦИОННАЯ СИСТЕМА, ФАЙЛОВАЯ СИСТЕМА, БАЗА ДАННЫХ, ФАЙЛЫ, ПОЛЬЗОВАТЕЛЬ, ПРОЦЕССЫ, ПЛАНИРОВЩИК, I-УЗЕЛ, СУПЕРБЛОК.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

1 Структура проектируемой  файловой системы 

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

Часть операционной системы (далее ОС), работающей с файлами, называется файловой системой (далее ФС).

Наиболее важным аспектом ФС с точки зрения пользователя является ее внешнее представление, т.е.:

— именование и защита файлов;

— операции с файлами.

Все современные ОС в качестве имен файлов используют 8-ми символьные текстовые строки. В именах файлов также разрешается использование цифр и специальных символов. Многие файловые системы поддерживают имена файлов до 255 символов.

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

1.1 Общая организация файловой  системы

На диске с файловой системой находится один раздел с проектируемой файловой системой. За ее основу взяты некоторые принципы файловой системы «S5FS». Основными характеристиками ФС являются:

1. Многоуровневость, т.е. иерархическая  организация данных.

2. Контроль свободных  блоков данных на диске с  помощью битовой карты свободных / занятых блоков.

3. Метод индексных дескрипторов  для размещения файлов на диске.

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

Структура разрабатываемой файловой системы изображена на рисунке 1.1.

Рисунок 1.1 - Структура ФС

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

Таблица 1.1

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

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

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

На логическом уровне каталог представляет собой таблицу, каждый элемент которого имеет размер 16 байт. Первые 14 байта хранят имя файла, последние 2 - его номер i-узла.

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

Таблица 1.2

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

Таблица 1.3

После i-узлов следует корневой каталог, содержащий вершину дерева ФС. Остальное место дискового раздела занимают все остальные файлы и каталоги.

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

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

Рисунок 1.2 - Метод последовательных блоков

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

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

Недостаток: со временем диск становится фрагментированным.

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

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

Рисунок 1.3 - Структура многоуровневой ФС

Системные вызовы для работы с каталогами:

Create – создание каталога.

Delete – удаление каталога.

Opendir – открытие каталога.

Closedir – закрытие каталога.

Readdir – чтение следующего элемента открытого каталога.

Rename – переименование каталога.

Link – установление связей.

Unlink – удаление ссылки на файл из каталога.

Флаг «Только чтение»- 0 –для чтения/записи; 1- только чтение

Флаг «Скрытый» - 0 – нормальный, 1 – не отображать в перечне файлов каталога

Флаг «Системный»  0 – нормальный; 1- системный

Флаг «Архивный» - 0 – заархивирован; 1 – требуется архивация

Флаг ASCII/двоичный  - 0 – ASCII; 1- двоичный

Флаг произвольного доступа - 0 – только последовательный доступ; 1 – произвольный доступ

Флаг «временный» - 0 – нормальный, 1- для удаления файла по окончании процесса

Флаги блокировки - 0 – неблокированный; отличный от нуля для блокированного

1.2 Виртуальные страницы 

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

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

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

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

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

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

Для стратегий размещений выработано правило «Правило 50%». Оно предполагает, что система находится в равновесии, если запросы на распределение и освобождение сбалансированы между собой в течение заданного короткого промежутка времени. Иначе говоря, в системе из m слов с распределенными n сегментами будет примерно h пустых участков, где h равно n /2. Это следует из того факта, что для данного сегмента пространство, примыкающее к его правому краю, будет пустим в течение половины данного интервала времени и занятым сегментом в течение другой половины. Вероятность существования пустого участка есть р = 1/2; например, число сегментов, имеющих пустоту по своему правому краю, есть np = n/2 = h.

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

a) Алгоритм оптимального размещения.

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

РАЗМЕР-УЧАСТКА — ТРЕБУЕМЬІЙ-РАЗМЕР —* ОСТАТОК

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

б) Размещение по принципу «первый подходящий».

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

РАЗМЕР-УЧАСТКА> ТРЕБУЕМЬІЙ-РАЗМЕР

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

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

1.3 Команды для работы с файловой системой

В таблице 1.4 предлагается перечень основных команд для работы с файловой системой.

Таблица 1.4

1.4 Системные вызовы для работы с файловой системой

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

Таблица 1.5

1.5 Способы организации  файлов

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

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

1.6 Алгоритмы работы некоторых системных вызовов ФС

Рисунок 1.4 - Алгоритм поиска свободного i-узла

Рисунок 1.5 - Алгоритм поиска файла в каталоге

Рисунок 1.6 - Проверка наличия свободного места для создания объекта

2 Процессы в операционной системе

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

2.1 Команды для работы  с процессами

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

Таблица 2.1

2.2 Системные вызовы управления процессами