Понятие операционной системы. Эволюция вычислительных систем.

Планирование и диспетчеризация потоков

Планирование

• Определение момента времени для смены текущего активного потока

• Выбор для выполнения потока из очереди

Диспетчеризация

• Сохранение контекста текущего потока

• Загрузка контекста нового потока

• Запуск нового потока на выполнение

Алгоритмы планирования потоков

• Невытесняющие – потоку позволяется выполняться, пока он сам, по собственной инициативе не отдаст управление операционной системе (файл-серверы Net Ware)

• Вытесняющие – решения о смене и выборе активного потока принимаются операционной системой (UNIX, Windows начиная с Windows 95, OS/2)

Алгоритмы, основанные на квантовании

Каждому потоку в порядке очереди предоставляются ограниченные непрерывные периоды процессорного времени – кванты

Кванты могут быть одинаковыми для всех потоков, или различными

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

Синхронизация процессов и потоков

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

Критическая секция всегда определяется по отношению к определенным критическим данным

Механизм синхронизации:

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

 

Семафоры

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

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

• V(S): переменная S увеличивается на 1 единым действием.

• P(S): уменьшение S на 1, если это возможно. Если S=0, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным.

Оверлеи

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

Свопинг

Образы процессов выгружаются на диск и возвращаются в оперативную память целиком

+ Относительно простой способ управления памятью

- Процесс, требующий памяти больше, чем реально есть в системе загрузить нельзя

- Полная загрузка/выгрузка процессов требует много времени

Виртуальная память

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

+ Позволяет защитить процессы друг от друга

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

- Непредсказуемо время доступа к памяти (Частично решается применением алгоритмов, предсказывающих обращения к памяти)

Виртуальная память

• Страничное распределение памяти

• Сегментное распределение памяти

• Сегментно-страничное распределение

 

Страничное распределение

Физическая память делится на части фиксированного размера – страницы

Виртуальное адресное пространство также делится на страницы аналогичного размера

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

Для каждого процесса хранится таблица страниц

Запись таблицы страниц включает следующую информацию:

• номер физической страницы;

• признак присутствия;

• признак модификации страницы;

• признак обращения к странице.

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

Стратегия замещения

1. FIFO алгоритм. Выгрузка самой старой страницы.

+ Просто в реализации

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

2. Выгрузка дольше всего не использовавшейся страницы. LRU (The Least Recently Used)

+ Считается хорошей стратегией

- Сложно в реализации

- Требуется аппаратная поддержка

3. Выгрузка редко используемой страницы. NFU (Not Frequently Used)

+ Считается хорошей стратегией (В некоторых случаях лучше, чем LRU)

- Сложно в реализации

-  Требуется аппаратная поддержка

-  Алгоритм «ничего не забывает»

Стратегия выборки

1. По запросу

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

Сегментное распределение

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

Для каждого процесса хранится таблица сегментов

Запись таблицы сегментов включает следующую информацию:

• базовый физический адрес сегмента;

• размер сегмента;

• правила доступа к сегменту;

• признаки модификации, присутствия и обращения.

Регистры процессора

Являются неотъемлемой частью процессора, обеспечивают очень высокое быстродействие.

Регистры собираются из элементов для хранения информации – триггеров.

Статическая оперативная память с произвольным доступом (SRAM, static random access memory)

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

SRAM

+ Быстрый доступ. Доступ к любой ячейке памяти в любой момент занимает одно и то же время.

+ Простая схемотехника — SRAM не требуются сложные контроллеры.

- Высокое энергопотребление.

- Невысокая плотность записи (шесть элементов на бит).

Вследствие чего — дороговизна килобайта памяти.

Согласование данных

1. Сквозная запись

• Если данные в кэше отсутствуют, то запись выполняется только в основную память

• Если данные находятся в кэше, то запись выполняется одновременно в кэш и основную память.

2. Обратная запись.

• Если данные в кэше отсутствуют, то запись выполняется только в основную память

• Если данные находятся в кэше, то запись производится только в кэш-память, в описателе данных делается специальная отметка

Типы файлов

• Обычные файлы. Содержат информацию произвольного характера

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

• Специальные файлы. Фиктивные файлы, ассоциированные с устройствами ввода-вывода.

• Ярлык – файл, служащий указателем на объект (например, файл, который требуется определённым образом обработать), программу или команду и содержащий дополнительную информацию.

• Символическая ссылка – специальный файл в UNIX-подобных ОС, для которого в файловой системе не хранится никакой информации, кроме одной текстовой строки. Эта строка трактуется как путь к файлу, который должен быть открыт при попытке обратиться к данной ссылке.

• Жесткая ссылка – структурная составляющая файла — описывающий его элемент каталога.

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

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

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

Монтирование

Работа одновременно с несколькими файловыми системами:

•  Автономное существование файловых систем. В этом случае необходимо указывать логическое имя устройства:

C:\windows\system32\kernel32.dll

•  Монтирование. Объединение всех файловых систем в единое дерево.

15. Физическая организация FAT.

Физическая организация FAT

• Загрузочный сектор. Содержит программу начальной загрузки ОС.

• Основная копия FAТ. Содержит информацию о размещении файлов и каталогов на диске.

• Резервная копия FAT.

• Корневой каталог. Занимает фиксированную область, позволяет хранить 512 записей о файлах и каталогах

• Область данных. Предназначена для хранения всех файлов и каталогов кроме корневого. Пространство области данных поделено на кластеры – участки одинакового размера. Файл всегда занимает целое количество кластеров

FAT поддерживает два типа файлов: обычный файл и каталог

Таблица FAT состоит из массива индексных указателей. Указатель может принимать значения:

• Кластер свободен (не используется);

• Кластер используется файлом и не является последним кластером файла. В этом случае индексный указатель содержит номер следующего кластера;

• Последний кластер файла;

•  Дефектный кластер;

Выбор размера кластера

• Большой размер кластера – потери дискового пространства, так как последний кластер файла может использоваться только частично

• Небольшой размер кластера – возрастают накладные расходы, так как файл занимает больше кластеров, которые не обязательно являются «соседними»

В зависимости от размера диска,размер кластера выбирается от 512 байт до 64 Кбайт.

Размер кластера выбирается так, чтобы он занимал целое число секторов. Кластер может занимать от 1 до 128 секторов.

Разрядность указателя FAT

• FAT 12 12-разрядные указатели. Поддерживается не более 4096 кластеров.

• FAT 16 16-разрядные указатели. Не более 65536 кластеров.

• FAT 32 32-разрядные указатели. Более 4 миллиардов кластеров.

Удаление файла в FAT

• В первый байт записи каталога заносится специальный признак «файл удален»

• В индексные указатели заносится признак «кластер свободен»

• Физически данные не удаляются, поэтому во многих случаях файл может быть восстановлен

+ Простота реализации

- Проблемы с поддержкой длинных имен файлов

- Отсутствие поддержки специальных файлов

- Фрагментация и связанное с ней уменьшение производительности

- При сбоях и отключении питания – нарушение целостности файловой системы:

• Файлы, не принадлежащие ни одному каталогу.

• Потерянные фрагменты файлов, занимающие место на диске.

• Файлы, для которых «нет» кластеров

16. Избыточные дисковые подсистемы RAID.

RAID (Redundant Array of Inexpensive Disks, дословно — «избыточный массив недорогих дисков»)

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

Различают несколько вариантов RAID-массивов, называемых также уровнями: RAID-0, RAID-1, RAID-2, RAID-3, RAID-4, RAID-5 и некоторые другие.

При оценке эффективности RAID-массивов чаще всего используются следующие критерии:

• степень избыточности хранимой информации (или тесно связанная с этим критерием стоимость хранения единицы информации);

• производительность операций чтения и записи;

• степень отказоустойчивости.

RAID-0

Данные расщепляются на блоки (например по 64 Кб.)и записываются параллельно на все диски

(-) Отказоустойчивость меньше, чем у одного диска

(+) RAID 0 позволяет «склеить» несколько небольших дисков в один большой

(+) Увеличивается производительность при чтении/записи

 

RAID-1

Реализует подход, называемый зеркальным копированием. Логическое устройство в этом случае образуется на основе одной или несколько пар дисков, в которых один диск являются основным, а другой диск дублирует информацию, находящуюся на основном диске. Позволяет ввести запись одновременно на два диска. Если основной диск выходит из строя, зеркальный продолжает сохранять данные, тем самым обеспечивается повышенная отказоустойчивость логического устройства. За это приходится платить избыточностью – все данные хранятся на логическом устройстве в двух экземплярах, в результате дисковое пространство используется лишь на 50%. Удвоение количества операций записи снижает производительность дисковой подсистемы, поэтому во многих случаях наряду с дублированием дисков дублируется и их контроллеры. Такое дублирование повышает скорость операций записи и обеспечивает большую надежность системы – данные на зеркальном диске останутся доступными не только при сбое диска, но и в случае сбоя дискового контроллера.

RAID-2

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

Минимум – три диска. Оптимальное - 32 диска и 3 диска для записи кода коррекции.

RAID-3

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

Минимальное количество дисков равно трем.

RAID-4

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

RAID-5

Аналогично RAID-4, но данные о контроле четности распределяется по всем дискам массива.

Наибольшей выигрыш в производительности достигается при операциях чтения. Высокая скорость чтения. Повышается скорость записи по сравнению с RAID-4, но ниже по сравнению со скоростями RAID-1 или RAID-3.

 

Понятие операционной системы. Эволюция вычислительных систем.

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

Основные функции ОС:

• Планирование заданий и использования процессора.

• Обеспечение программ средствами коммуникации и синхронизации.

• Управление памятью.

• Управление файловой системой.

• Управление вводом-выводом.

• Обеспечение безопасности

Классификация ОС

- многозадачные (Unix, OS/2, Windows)

- однозадачные (например, MS-DOS)

По числу одновременно работающих пользователей ОС можно разделить на:

- однопользовательские (MS-DOS, Windows 3.x);

- многопользовательские (Windows NT, Unix).

По числу поддерживаемых процессоров:

- однопроцессорные (MS-DOS, Windows 3.x);

- многопроцессорные (Windows NT, Linux, Solaris).

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

Первое поколение ЭВМ (1945–1955)

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

Операционные систем отсутствовали. Система выполняла одновременно только одну операцию. Программирование осуществлялось исключительно на машинном языке.

Второе поколение ЭВМ (1955–1965)

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

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

Третье поколение ЭВМ (1965–1973)

Элементная база ЭВМ – малые интегральные схемы (МИС), содержавшие на одной пластинке сотни или тысячи транзисторов. Управление работой этих машин происходило с алфавитно-цифровых терминалов. Для управления использовались языки высокого уровня и Ассемблер. Данные и программы вводились как с терминала, так и с перфокарт и перфолент. Машины предназначались для широкого использования в различных областях науки и техники (проведение расчетов, управление производством, подвижными объектами и др.). Благодаря интегральным схемам удалось существенно улучшить технико-эксплуатационные характеристики ЭВМ и резко снизить цены на аппаратное обеспечение. Например, машины третьего поколения по сравнению с машинами второго поколения имеют больший объем оперативной памяти, увеличенное быстродействие, повышенную надежность, а потребляемая мощность, занимаемая площадь и масса уменьшились.

Четвертое поколение ЭВМ (1974–1982)

Элементная база ЭВМ – большие интегральные схемы (БИС). Наиболее яркие представители четвертого поколения ЭВМ – персональные компьютеры (ПК). Связь с пользователем осуществлялась посредством цветного графического дисплея с применением языков высокого уровня.

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

Пятое поколение ЭВМ (1982 – настоящее время)

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

 

11. Понятие процесса и потока. Алгоритмы планирования потоков. Синхронизация потоков.

Процесс – заявка на потребление всех видов ресурсов, кроме процессорного времени

Поток – последовательность команд, работающих в рамках некоторого процесса

Процесс – память, файлы, сокеты, семафоры

Поток – квант процессорного времени, контекст

Планирование и диспетчеризация потоков

Планирование

• Определение момента времени для смены текущего активного потока

• Выбор для выполнения потока из очереди

Диспетчеризация

• Сохранение контекста текущего потока

• Загрузка контекста нового потока

• Запуск нового потока на выполнение

Алгоритмы планирования потоков

• Невытесняющие – потоку позволяется выполняться, пока он сам, по собственной инициативе не отдаст управление операционной системе (файл-серверы Net Ware)

• Вытесняющие – решения о смене и выборе активного потока принимаются операционной системой (UNIX, Windows начиная с Windows 95, OS/2)