Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

Ст. преп. каф. ПМИ

А. В. Чернышева

Выполнил:

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

Н. А. Астафьев

Донецк, 2012 г.

Содержание

Реферат

Введение

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

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

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

1.3 Команды для работы с ФС

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

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

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

2. Процессы в ОС

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

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

2.3 Диаграмма состояний процесса

2.4 Приоритеты процессов

2.5 Выбор дисциплины обслуживания планировщика процессов. Алгоритм работы планировщика процессов

2.6 Межпроцессное взаимодействие

2.7 Свопинг процессов

3. Режимы работы проектируемой ОС

3.1 Мультипрограммный режим работы ОС

3.2 Многопользовательская защита

3.3 Интерактивный режим работы ОС

3.4 Пакетный режим работы

4. Структура операционной системы

4.1 Общая структура проектируемой ОС

4.2 Структура ядра проектируемой ОС

4.3 Структура управляющих блоков базы данных ОС

4.4 Схема взаимодействия управляющих блоков базы данных операционной системы

Перечень ссылок

Реферат

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

файл мультипрограммный ядро виртуальный

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

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

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

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

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

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

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

Суперблок	Битовая карта	Массив i-узлов	Корневой каталог	Данные

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

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

Таблица 1.1

Название поля	Размер в байтах	Описание
fs_name	3	Название файловой системы
fs_size	2	Размер файловой системы
block_size	2	Размер блока данных
free_ block _count	2	Количество свободных блоков
free_inode_count	2	Количество свободных i -узлов

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

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

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

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

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

Таблица 1.2

Название поля	Размер в байтах	Описание
is_free	1	Состояние i -узла
f_size	2	Размер файла
rights	1	Права доступа к файлу
uid	1	Идентификатор владельца
is_dir	1	Флаг : файл или каталог
create_time	8	Время создания файла
last_mod_time	8	Время последней модификации
addr[1..10]	20	Указатели на блоки данных файла

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

Таблица 1.3

Права	Значения числа
Для владельца файла	Для других пользователей
r	-	0
r	r	1
r	w	2
w	-	3
w	r	4
w	w	5

После 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	2	3
CreateFile	name, data, rights, uid, create_time, pdir_inode_number	Создание файла
CreateDirectory	name, data, rights, uid, create_time, pdir_inode_number	Создание каталога
OpenTextFile	inode_number	Открытие файла
Paste	inode_number, pdir_inode_number	Вставка вырезанного объекта
Rename	inode_number, new_name	Переименование объекта
DeleteDir	inode_number	Удаление каталога
DeleteFile	inode_number	Удаление файла
vdir	inode_number	Просмотр содержимого текущего каталога
vloc	dir_inode_number	Просмотр текущего местоположения
login	name_user	Вход в систему
logout	--	Выход из системы

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

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

Таблица 1.5

Название вызова	Параметры	Возвращаемый результат	Описание
CheckFreeSpace	size	true/false	Проверка возможности создания объекта (свободного места)
CheckReadRights	inode_number	true/false	Проверка прав на выполнение операции чтения
CheckWriteRights	inode_number	true/false	Проверка прав на выполнение операции записи / изменения
FindFreeInode	отсутствуют	inode_number	Поиск свободного i-узла
FindFreeBlocks	size	addr[]	Поиск свободных блоков
FindInDirectory	name, dir_inode_number	true/false	Проверка наличия объекта в каталоге

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

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

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

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

для i: = low (partition.ilist).. high (partition.ilist) do если partition.ilist [i]. is_free = true то выйти из цикла; Result: = i;

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

для i: = low (partition.ilist [dir_inode_number]. addr).. high (partition.ilist [dir_inode_number]. addr) для j: = low (partition.data [partition.ilist [dir_inode_number]. addr [i]]. files).. high (partition.data [partition.ilist [dir_inode_number]. addr [i]]. files) если (Partition.data [partition.ilist [dir_inode_number]. Addr [i]]. Files [j]. Inode_number <> 0) и (Partition.data [partition.ilist [dir_inode_number]. Addr [i]]. Files [j]. Filename = name), то Result: = истина; выйти из функции; Result: = ложь;

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



если ((partition.superblock.free_block_count * (partition.superblock.block_size-2))> = size) и (Size <10 * (partition.superblock.block_size-2)) то Result: = истина; иначе Result:=ложь;

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

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

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

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

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

Таблица 2.1

Название команды	Параметры	Описание
backgnd	pname	Перевод процесса в фоновый режим
Необязательные команды (не по варианту)
ps	отсутствуют	Просмотр информации о запущенных процессах
kill	PID	Уничтожение процесса
chpri	pname, pri	Изменение приоритета процесса

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

В таблице 2.2 предлагается перечень основных системных вызовов ОС для управления процессами.

Таблица 2.2

Название вызова	Параметры	Возвращаемый результат	Описание
FindPName	pname	true/false	Проверка существования процесса
KillP	PID	отсутствует	Уничтожение процесса
DoP	PID	отсутствует	Перевод процесса в состояние выполнения
WaitP	PID	отсутствует	Перевод процесса в состояние ожидания
ReadyP	PID	отсутствует	Перевод процесса в состояние готовности
CheckRes	Res	true/false	Проверка занятости ресурса для запуска процесса
PIPE	fd	fd[0], fd[1]	Возвращение дескрипторов чтения и записи (соответственно в fd [0] и fd [1]) для данного канала
POpen	name	0/-1	Создание именованного канала
DelPIPE	dscr	0/-1	Удаление именованного канала
WritePIPE	dscr, addr	0/-1	Записи в именованный канал
ReadPIPE	dscr, addr	0/-1	Чтение с именованного канала
ShmGet	size	addr/-1	Создание новой области памяти, распределяется
ShmAt	id, addr	addr/-1	Присоединение области памяти, распределяется в виртуальное адресное пространство процесса

2.3 Диаграмма состояний процессов

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

Рисунок 2.1 - Диаграмма состояний процесса

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

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

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

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

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

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

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

2.4 Приоритеты процессов

Приоритет - это параметр, который характеризует степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем высший приоритет (низшее значение приоритету), тем выше привилегии.

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

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

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

2.5 Выбор дисциплины обслуживания планировщика процессов. Алгоритм работы планировщика процессов в соответствии с выбранной дисциплины обслуживания

В данном проекте в качестве дисциплины обслуживания планировщика процессов является приоритетное планирование по вытеснению. Алгоритм работы планировщика показан на рисунке 2.2.

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

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

входная информация: отсутствует

исходная информация: отсутствует

{

выполнять пока (не выбран один из процессов)

{

для (каждого процесса из очереди готовых к выполнению)

если есть возможность выбрать процесс с абсолютным приоритетом;

иначе выбрать процесс с наибольшим приоритетом;

если (один из процессов не может быть избран для выполнения)

приостановить машину;

/* Машина выходит из состояния простоя по прерыванию

если в очереди появляется процесс с абсолютным приоритетом то

приостановить выбранный приоритет */

}

удалить выбранный процесс из очереди готовых процессов;

}

Рисунок 2.2 - Алгоритм работы планировщика процессов

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

Таблица 2.3

Процесс	Время появления в очереди	Продолжительность процесса	Приоритет
p0	0	5	4
p1	2	2	3
p2	7	7	2
p3	0	5	1

Во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т. е. наиболее приоритетным в нашем примере является процесс p3, а наименее приоритетным - процесс p0. Первым начнет исполняться процесс p3, а по его окончании - процесс p1. Однако в момент времени t = 7 он будет вытеснен процессом p2 и продолжит свое выполнение только в момент времени t = 14. Последним будет исполняться процесс p0. Пример предоставления процессора процессам в случае вытесняющего приоритетного планирования отображено в таблице 2.4.

Таблица 2.4.

Время

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

p0

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

p1

Г

Г

Г

И

Г

Г

Г

Г

Г

Г

Г

И

p2

И

И

И

И

И

И

И

p3

И

И

И

И

И

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

2.6 Межпроцессное взаимодействие

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

2.6.1 Каналы, именованные каналы

Программный канал в операционных системах представляет собой одно из средств взаимодействия между процессами с ограниченным объемом. Каналы позволяют передавать данные между процессами в порядке поступления FIFO («первым пришел -- первым ушел»), а также синхронизировать выполнение процессов. Их использование дает процессам возможность взаимодействия между собой даже в случае, когда неизвестный процесс на другом конце канала. Традиционная реализация каналов использует файловую систему для хранения данных. Различают два вида каналов: именованные каналы и неименованные каналы, которые идентичны между собой во всем, кроме способа первоначального обращения к ним процессов. Для именованных каналов процессы используют системную функцию open, а неименованные используют pipe. Впоследствии, при работе с каналами процессы пользуются обычными системными функциями для файлов, такими как read, write и close. Разделять доступ к неименованным каналам могут только связанные процессы, которые являются потомками того процесса, который вызвал функцию pipe. Алгоритм реализации функции создания неименованного канала представлен на рисунке 2.3.

pipe (int w, int r)

{

i = 0; j = 0;

пока (i <количество процессов)

{

если (process [i]. pid == w)

{

j = 0;

пока (j <количество процессов)

{

если (process [j]. ppid == process [i]. pid && process [j]. pid == r)

{

если (канал не открыт на запись)

{

печать ("Не удалось создать канал! \ n");

вернуть -1;

}

иначе

вернуть 0;

}

j + +;

}

иначе

{

печать ("Процесс, который записывает данные не найден!")

вернуть -1;

}

i + +;

}

вернуть 0;

}

Рисунок 2.3 - Алгоритм создания неименованного канала

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

Все системные функции для работы процессов с каналами описаны в таблице 2.2.

2.6.2 Память распределяемая

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

2.7 Свопинг процессов

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

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

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

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

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

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

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

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

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

2.7.1 Схема с переменными разделами

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

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

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

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



Рисунок 2.4 - Динамическое распределение. Свопинг

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

Когда в результате подкачки процессов с диска в памяти появляется множество неиспользованных фрагментов, их можно объединить в один большой участок, передвинув все процессы в сторону младших адресов настолько, насколько это возможно. Такая операция называется уплотнением или сжатием памяти. Обычно ее не выполняют, потому что на нее уходит много времени работы процессора. Например, на машине с 256 Мбайт оперативной памяти, которая может копировать 4 байта за 40 нс, уплотнение всей памяти займет около 2,7 с.

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

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

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

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

Рисунок 2.5 - Предоставление пространства для роста области данных (а); предоставление пространства для роста стека и области данных (б)

2.7.2 Рекомендации по размещению файла подкачки

Одним из способов выделения места для swap-файла (раздела) является кратное выделение памяти, когда объём этого файла равен объёму оперативной памяти, умноженному на константу от 0,5 до 2 или 3.

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

3. Режимы работы проектируемой ОС

3.1 Мультипрограммный режим работы ОС

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

Рисунок 3.1 Пример выполнения двух программ

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

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

3.2 Многопользовательская защита ОС

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

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

3.3 Интерактивный режим работы ОС

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

3.4 Пакетный режим работы

Пакетный режим -- режим работы ОС, при котором основными источниками команд являются специальные пакетные файлы, предварительно подготовленные пользователями. В пакетном режиме время исполнения конкретной команды не столь существенно как в интерактивном. Главный критерием работы пакетной ОС является, как правило, максимальная загрузка оборудования. Для достижения этой цели в системах пакетной обработки используются следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие отличающиеся требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины; так, например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается "выгодное" задание.

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

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

4. Структура операционной системы

4.1 Общая структура проектируемой ОС

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

Размещено на http://www.allbest.ru/

Рисунок 4.1 - Структура проектируемой ОС

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

Уровень оборудования представляет собой собственно саму аппаратуру, на которой функционирует ОС.

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

4.1.1 Внешние устройства (НМД)

Магнитные диски организованы в цилиндры, каждый из которых содержит столько дорожек, сколько есть у устройства головок, установленных вертикально. Дорожки делятся на секторы, их количество обычно варьируется от 8 до 32 у гибких дисков и до нескольких сот у жестких дисков. Число головок варьируется от 1 до 16.

У некоторых магнитных дисков мало электроники, они предоставляют на выходе простой поток битов. На этих дисках контроллер выполняет совсем немного работы. На других дисках, в частности на IDE-дисках (IDE, Integrated Drive Electronics -- встроенный интерфейс накопителей), само устройство содержит микроконтроллер, выполняющий значительный объем работ, и позволяющий собственно контроллеру обращаться к нему с набором команд высокого уровня.

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

4.1.2 Внешние устройства (видеотерминалы)