Всё для Учёбы — студенческий файлообменник
1 монета
doc

Лекция «История развития вычислительной техники и операционных систем» по Операционным системам (Иванько А. Ф.)

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

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

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

История развития вычислительной техники и операционных систем

Историю вычислительной техники начинают с машины, созданной в 1623 г. В. Шикардом, способной суммировать, вычитать и частично умножать и делить числа. Далее в 1642 г. Б. Паскаль создал арифмометр, используемый далее в течение почти 300 лет. Данный прибор выполнял все 4 действия арифметики и изначально был предназначен для облегчения бухгалтерских работ. Собственно, на основе идей, заложенных в арифмометр, и был построен первый компьютер.

Первая программируемая машина была разработана Ч. Бэббиджем. Работа над ней началась в 1823 году. Впервые машина была применена для программирования ткацкого станка. Программа хранилась на изобретенных к тому моменту Жаккаром перфокартах. В зависимости от введенной программы станок ткал ткань с различным рисунком. Первым программистом стала жена Бэббиджа и меценат проекта, графиня Ада Августа Лавлейс. В ее часть в ХХ веке был назван один из языков высокого уровня.

В 1890 году в Америке при переписи населения была использована первая машина на электрических реле. С 30 гг. ХХ века в Германии начались работы над вычислительными машинами на базе ламп.

Начало Второй Мировой войны подхлестнуло процесс создания универсальных вычислительных машин, способных производить сложные арифметические расчеты. Первой универсальной ЭВМ, с которой собственно и принято вести историю ЭВМ, стала ENIAC, разрабатывавшаяся с 1943 по 1947 год. Машина весила 30 тонн и занимала площадь в 200 м2, содержала 18 тыс. ламп и потребляла 140 кВт. Однако ее программирование осуществлялось путем установки переключателей и коммутации разъемов. Наряду с возрастанием скорости расчетов много времени уходило на собственно программирование и отладку. В связи с этим консультант проекта ENIAC Джон фон Нейман предложил записывать алгоритм вместе с данными так, чтобы его можно было модифицировать аналогично данным в соответствии с получаемыми результатами. Этот принцип был назван "принцип хранимой программы" и использовался при проектировании ЭВМ под названием EDVAK, начатом в 1945 г. Создание EDVAK'a было завершено в 1951 г., однако первой ЭВМ, построенной по принципу хранимой программы, стал EDZAK, построенный в 1949 г. в Кембридже (Англия). Первой коммерческой ЭВМ с хранимой программой стала IBM 701, выпущенная в 1952 г.

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

В 1948 г. в компании Bell Laboratories были разработаны транзисторы. Их появление обусловило создание ЭВМ второго поколения. Транзисторы обладали более высокой надежностью, в связи с чем увеличилось непрерывное время их работы. Как следствие встал вопрос о том, каким образом обеспечить непрерывность подачи заданий и максимальную загрузку дорогостоящей ЭВМ.

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

В состав ЦП стали входить блоки работы с числами с плавающей запятой. Появились языки программирования высокого уровня (Алгол, Кобол, Фортран).

Первой транзисторной машиной была созданная в МТИ ТХ-0. Однако первым компьютером, включившим в себя все архитектурные особенности второго поколения, считают ламповую машину IBM 704, выпущенную в 1953 г. Также для нее была выпущена первая операционная система.

В целях решения более крупных задач были созданы первые суперкомпьютеры. В них были применены методы параллельной обработки отдельных команд (конвейеризация) и различных программ на основе применения нескольких процессоров. Первыми суперкомпьютерами стали LARC фирмы UNIVAC и Stretch фирмы IBM (серия 7030).

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

Переход к третьему поколению ЭВМ характеризуется появлением в середине 60-х годов интегральных схем. По степени интеграции их делят на малые ИС (1-10 вентилей на кристалл), средние ИС (~100 вентилей) и большие ИС (100 - неск. тыс. вентилей). Память на сердечниках была заменена полупроводниковой. В центральном процессоре стало использоваться микропрограммирование, предложенное в 1951 г. Уилксом. Это означает, что команда, поступающая на вход ЦП, внутри интерпретируется и разбивается на несколько простейших команд, собственно и выполняемых ЦП. Система команд ЦП становится программируемой и область применения одного процессора существенно возрастает. Это происходит в связи с тем, что процессор становится независимым от системы команд. Для хранения системы команд была использована перезаписываемая управляющая память. Благодаря микропрограммированию облегчается выполнение сложных действий. Машины, выполняющие текст программы на языке высокого уровня, были названы машинами языков высокого уровня.

Машины третьего поколения стали создаваться семействами, внутри которых они были взаимозаменяемы и совместимы снизу вверх. Первой стала серия IBM System/360.

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

В 1963 году фирма DEC выпустила первый миникомпьютер PDP-5. Появление миникомпьютеров приблизило их к ученым и существенно расширило область их применения. Кроме вычислительных методов начали развиваться теория игр, информатика, искусственный интеллект.

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

В борьбе за повышение функциональности калькуляторов появилась идея применения универсально БИС, модификация функций которой была бы возможна путем замены программы. В результате фирмой Intel был в 1971 году создан первый микропроцессор 4004. Микропроцессор 4004 оперировал словами длиной 4 бита и был способен выполнять 45 видов команд. В 1973 г. Intel выпусти 8-ми разрядный процессор 8080, работающий с 72 командами и предназначенный для построения ЭВМ.

На базе усовершенствованного процессора 8088 в августе 1981 г. был выпущен первый массовый персональный компьютер, построенный по модульной архитектуре. Эта архитектура до сих пор является стандартом для ПЭВМ. До выпуска этого компьютера уже делались попытки выпуска ПК фирмами IBM, Apple и другими, но они не имели такого успеха.

Компьютеры начали различать по видам наборов инструкций процессора. Выделяют наборы CISC (Complete Instruction Set Computer) и RISC (Reduced Instruction Set Computer). CISC - это процессоры с полным набором инструкций, включающим в себя специфичные команды, объединяющие в себе набор более простых команд. Процессоры фирмы Intel стали первыми представителями данной архитектуры. Архитектура RISC включает набор простых команд, выполняемых за короткое время. По данной технологии изготавливаются процессоры Texas Instruments, а также других фирм. Обычно процессоры архитектуры RISC показывают более высокую производительность на задачах обработки информации. Последние процессоры фирмы Intel строятся как CISC-процессор с RISC-ядром, выполняющим команды.

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

Рост количества транзисторов на кристалле привел к появлению СБИС (>105 элементов на кристалле) и 4 поколения ЭВМ. Появились 32-разрядные процессоры, для памяти стали использоваться БИС емкостью 256Кбит для статического и 1Мбит для динамического ОЗУ. Объединение компьютеров стали образовывать вычислительные сети. Для передачи данных в них стали разрабатываться собственные стандарты, служащие различным целям. На данный момент используются 64-разрядные процессоры со 128 или 256 разрядными регистрами.

Дальнейшая миниатюризация размеров компонентов ЭВМ привела к появлению носимых компьютеров (Laptop и Notebook). На данный момент создано достаточно большое количество моделей карманных компьютеров и TabletPC, являющихся полнофункциональными устройствами.

Распространение компьютеров обусловило смену задач, стоящих перед ОС. Если раньше она отвечала в основном за контроль за работой различных устройств, то теперь ОС стала более дружественной для пользователя. В связи с этим появились ОС Unix и CP/M. Их пользовательский интерфейс основывается на применении командной строки, в которую пользователь может вводить команды для инициации тех или иных действий: запуска задач, операций над файловой системой и т.д.

Графический интерфейс пользователя (Graphic User Interface, GUI) появился в Xerox Palo Alto Research Center — Xerox PARC на рубеже 60–70 годов. Одной из идей, разработанных в PARC, была и парадигма WIMP (Windows, Icons, Menus, Point-and-click), которая позже переросла в концепцию GUI и продолжает использоваться по настоящее время. В 1975 году в Xerox был начат проект, закончившийся в апреле 1981 года представлением системы Xerox 8010 Professional Workstation, более известной под торговой маркой Xerox Star (в состав которого входил, например, 17” монитор). В этой машине было заложено много передовых идей: от нее ведут свое происхождение GUI, WYSIWYG (what you see is what you get), кодировка Unicode, язык описания страниц PostScript, идея «рабочего стола» и т.п.

Самым быстрым на данный момент является суперкомпьютер BlueGene/L. Его производительность равна 280,6 Тфлопс (1012 операций над числами с плавающей точкой в секунду). Он состоит из 65 тыс. двуядерных процессоров PowerPC 440 с частотой 700 МГц, занимает 760 м2. Его задачей является расчет ядерных реакций, элементов наноструктур и т.д.

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

ТИПОВАЯ СТРУКТУРА МИКРОПРОЦЕССОРНОГО МОДУЛЯ

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

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

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

МП – микропроцессор

СС – система синхронизации

ДШ ПАМ – дешифратор памяти

ДШ в/в – дешифратор ввода/вывода

ПЗУ – постоянное запоминающее устройство (ROM)

ОЗУ – оперативное запоминающее устройство (RAM)

КП – контроллер памяти

КВУ – контроллер внешних устройств

КВнУ – контроллер внутренних устройств

КПДП – контроллер прямого доступа к памяти

В МПС задатчиком является модуль МП. Он формирует команды на трех системных шинах: адреса, данных и управления. Шина адреса в современных МПС имеет разрядность от 16 до 64 бит, данных от 4 до 256 бит. Разрядность этой шины показывает, какой объем информации может быть принят или передан МП за одно обращение к системе.

Шина управления содержит от 2 до 100 линий. По этой шине передаются сигналы, которые определяют направление передачи по шине данных, тип этих передач и т.п. Таким образом, в этом варианте нет различия между устройствами памяти и устройствами ввода/вывода.

Шина адреса и шина управления однонаправлены от МП к пассивным модулям, шина данных двунаправлена. Направление передачи по шине задает сам МП. Каждый пассивный модуль имеет свой адрес. Этот адрес дешифруется 2 дешифраторами - памяти и ввода-вывода. Они формируют сигнал выбор модуля (ВМ(CS)). Таким образом, пассивный модуль имеет право что-то принимать или передавать на шину данных только при получении сигнала CS. В остальное время модуль должен быть отключен, то есть модули должны иметь 3 состояния.

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

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

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

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

- тактовой частоты.

- архитектуры процессора.

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

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

Программируемый интервальный таймер

В состав таймера (ПИТ) входит 3 независимых канала. Каждый из них представляет собой универсальный 16-тиразрядный счетчик, который имеет 2 входа и 1 выход.

CLK - вход от внешнего тактового генератора или внешнего источника сигнала (событий).

GATE - вход управления.

OUT - выходной сигнал в зависимости от режима работы.

D0-D7 - ШД A0-A1 - сигнал на вход внутреннего дешифратора 2х4, позволяют выбрать один из счетчиков или регистр управления, подключается к 2-м младшим разрядам ША.

CS - разрешает работу ШД, идет с дешифратора выбора блока.

В PC базовый адрес таймера = 40h.

CS RD WR A1 A0

0 1 0 0 0 Загрузить С0

0 1 0 0 1 Загрузить С1

0 1 0 1 0 Загрузить С2

0 1 0 1 1 Запись в РУ

0 0 1 0 0 Чтение С0

0 0 1 0 1 Чтение С1

0 0 1 1 0 Чтение С2

0 0 1 1 1 NOP

Программирование режимов работы таймера

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

Формат управляющего слова.

7 0

CS1 SC0 RL1 RL0 M2 M1 M0 BCD

SC1 SC0 0 0 C0

0 1 C1 1 0 C2 1 1 ---

RL1 RL0

0 0 Защелкивание содержимого счетчика

0 1 Чтение, загрузка только ст. байта

1 0 - // - мл. байта

1 1 Чтение , загрузка сначала мл., потом ст. байта

M2 M1 M0 0 0 0 P0

0 0 1 P1 X 1 0 P2

X 1 1 P3 1 0 0 P4

1 0 1 P5

BCD 0 - двоичный 16-тиразрядный счетчик

1- двоично-десятичный счетчик с 4 декадами

Режимы.

Р0 - Формирование сигнала по концу счета. Изначально выход OUT=0. При настройке в счетчик записывается некоторое число. Это число определяет количество переходов входного сигнала CLK после исчерпания которых на выходе OUT появляется 1. Счетчик работает на вычитание.

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

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

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

Р2 - Генератор скоростей передачи. Используется для формирования на выходе OUT периодического сигнала определяющего скорость передачи данных по последовательным каналам связи. Число, загружаемое в счетчик, определяет период следования выходного сигнала OUT.

Р3 - Генератор прямоугольных импульсов. Аналогичен Р2. Используется для формирования звуковых сигналов. Исходная частота - 1,19 МГц.

1 - порт 61h.0

2 - порт 61h.1

3 - порт 62h.5

4 - порт 62h.4

Р4 - Программируемый строб. После программирования режима на выходе OUT выставляется 1. После этого начинается отсчет n периодов сигналов на входе CLK, где n загружаемое в счетчик число. После окончания подсчета на выходе выставляется 0 на время 1 импульса. 0 на входе GATE запрещает счет. Если в ходе счета в счетчик загружается новое число, то счет начинается сначала.

Р5 - аппаратно генерируемый строб. Похож на Р4, но отсчет начинается только после появления 1 на входе GATE. Если на входе GATE сигнал меняется, то после каждого фронта сигнала отсчет ведется вновь.

Чтение содержимого счетчиков

При работе таймера процессор может определить текущее число в счетчике двумя способами.

- Чтение из соответствующего счетчика. Недостатком является большая погрешность в определении текущего содержимого счетчика.

- Способ защелкивания содержимого счетчика. Процессор выдает команду записи в регистр управления. Выполняя эту команду таймер переписывает текущее состояние счетчика в специальный внутренний 16-тиразрядный регистр-защелку. После этого содержимое считывается 1-2 командами чтения.

В IBM PC счетчик 0 используется для формирования сигнала "запрос прерывания". Этот сигнал формируется 18,2 раза в секунду и используется ДОС для отсчета времени суток, вызывая прерывание таймера (IRQ8). 4-байтовый этих импульсов хранится по адресу 0040:006С. Адрес канала - 40h.

Счетчик 1 используется для формирования сигнала "запрос регенерации динамической памяти". Адрес канала - 41h.

Счетчик 2 соединен с внутренним динамиком и используется обычно для генерации звука. Адрес канала - 42h.

Начиная с PC AT, в систему введен второй таймер, все 3 канала которого доступны пользователю.

ОРГАНИЗАЦИЯ ПАМЯТИ В МП-СИСТЕМАХ

Память делят на постоянную (ПЗУ, ROM), оперативную (ОЗУ, RAM), сверхоперативную и внешнюю.

Постоянная память ROM (Read Only Memory), обычно содержит такую информацию, которая не должна меняться в ходе выполнения микропроцессором программы. Постоянная память обладает тем преимуществом, что может сохранять информацию и при отключенном питании. Это свойство получило название «энергонезависимость». Все микросхемы постоянной памяти по способу занесения в них информации (программированию) делятся на масочные, информация в которые заносится непосредственно при изготовлении микросхемы, программируемые изготовителем, однократно программируемые пользователем (Programmable ROM) и многократно программируемые пользователем (Erasable PROM). Последние в свою очередь подразделяются на стираемые электрически и с помощью ультрафиолетового облучения. К элементам EPROM с электрическим стиранием информации относятся и микросхемы флэш-памяти (flash). От обычных EPROM они отличаются высокой скоростью доступа и быстрым стиранием записанной информации.

ОПЕРАТИВНАЯ ПАМЯТЬ В МП-СИСТЕМАХ

По способу работы ОЗУ делят на динамические (DRAM) и статические (SRAM). Статическое ОЗУ строится на основе триггеров и может хранить информацию все время, пока подано питание.

Ячейки памяти динамического ОЗУ строятся на основе конденсаторов и усилителей на выходе. Время хранения информации в такой памяти составляет несколько миллисекунд. Для сохранения информации периодически производится регенерация памяти. Чтение информации из таких ячеек памяти происходит со стиранием. В связи с этим для того, чтобы прочесть информацию из ячейки необходимо вначале прочитать ее содержимое, а затем записать обратно. Для регенерации памяти производится ее считывание. Ответственность за генерацию сигнала регенерации ОЗУ несет 1-й выход системного таймера. Сигнал с него подается на контроллер ПДП.

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

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

В целях экономии числа входов ОЗУ в схеме используется мультиплексор адреса. Полный адрес подается в 2 приема: младшие разряды, сопровождаемые сигналом RAS, а потом стар-шие, сопровождаемые сигналом CAS.

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

ВНЕШНИЕ НОСИТЕЛИ ИНФОРМАЦИИ

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

К магнитным носителям относятся магнитные ленты, магнитные барабаны, гибкие и жесткие магнитные диски.

Магнитные барабаны на использовались лишь в старых моделях вычислительных систем. Магнитная лента используется в носителях трех типов.

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

- Кассетные 1-2-дорожечные магнитофоны, также разработанные специально.

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

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

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

1) Метод без возврата к 0. Записываемый уровень сигнала изменятся (с 1 на 0 или с 0 на 1), если записываемые данные изменяются с 0 на 1 или наоборот. Метод требует дополнительной записи сигнала CLK. Используется при записи на многодорожечный магнитофон.

2) Метод без возврата к 0 с инверсией. Изменение уровня происходит по каждой записываемой 1.

3) Метод двухчастотной модуляции. Низкая частота означает 1, высокая частота – 0. Метод также требует дополнительного сигнала синхронизации.

4) Метод волнового пакета. Наличие сигнала означает 1, отсутствие сигнала – 0.

5) Метод широкоимпульсной модуляции. Широкий отрицательный импульс означает 0, короткий – 1.

6) Метод двойной частоты. 1 короткий положительный импульс означает 0, 2 импульса – 1.

7) Манчестерский код. Уровень сигнала изменяется по каждому фронту сигнала CLK и дополнительно в середине битов со значением равным 1.

8) Метод двухфазного кодирования. Разновидность предыдущего метода. Изменение происходит в середине каждого сигнала CLK. Изменение с 1 на 0 означает 1, с 0 на 1 означает 0. Недостатком метода является возможность прочитать информацию в инвертированном виде. Для устранения этого недостатка вначале записывается контрольная последовательность, позволяющая отследить инверсию.

Методы 5-8 называются методами самосинхронизации и не требуют дополнительной записи сигнала синхронизации.

Накопители на магнитных дисках

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

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

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

- Последовательное назначение секторов. ОС нумерует все сектора с 1 по n. Кроме того, ОС всегда хранит номер последнего занятого сектора. При записи очередного файла на диск ему выделяется место с первого незанятого сектора. Диск разбивается на 2 области: каталоги и файлы. Каталог содержит имя и длину файла, а также номер его первого сектора. Плюсами являются быстрые скорости чтения и записи, простота реализации, уменьшение износа головок и диска. Минус – при удалении файлов образуются «дыры», удаление которых невозможно без дефрагментации.

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

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

Накопители на гибких магнитных дисках (НГМД, FD) – представляет собой дискету малой емкости. На данный момент используются 3” диски объемом 1,44 Мб. Для подключения НГМД к системе требуется специальный контроллер – процессор со своей системой команд. Программное обеспечение контроллера обычно входит в ПЗУ и содержит процедуры для форматирования дорожки, чтения и записи дорожки. При форматировании дорожки МП формирует блок информации, содержащей все заголовки секторов. Посредством ПДП контроллеру передается команда форматирования и адрес блока. При чтении и записи параметрами служат номер дорожки, сектора, стороны и адрес буфера.

Развитием НГМД стала технология ZIP, основывающаяся на тех же принципах. Объем дисков ZIP составляет 100 и 250 Мб при размере 3.5”.

Накопители на жестких магнитных дисках

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

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

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

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

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

В 1990 году фирмой IBM были впервые применены магниторезистивные головки (MR­head). Принцип их действия заключается в использовании материалов, изменяющих свое электрическое сопротивление при изменении напряженности окружающего магнитного поля. Такой подход позволил решить, как минимум, две проблемы: повышение надежности чтения и плотности записи информации. При этом магнитно-резистивные головки используются только для чтения. Для записи используются обычные головки.

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

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

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

Оптические накопители

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

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

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

2. CD-R. Эта технология позволяет однократно записать на носитель некоторую информацию с помощью привода CD, позволяющего запись. Специальный лазер привода выжигает на поверхности диска непрозрачные участки. Так как для записи требуется лазер с длиной волны меньше, чем это оговаривалось первыми стандартами, чтение таких дисков на старых приводах невозможно. Более современные приводы оснащаются двумя лазерами.

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

Первые модели CD-ROM использовали постоянную линейную скорость чтения (CLV). Это требовало изменения скорости вращения диска при перемещении головки. Для устройств 1x (150kb/s) эта скорость лежала в диапазоне 200-530об/мин. Устройства 2x -12x скоростные просто повышали скорость вращения. Однако уже увеличение скорости до 12x требует частоты вращения 2400-6360об/мин что очень велико для сменного носителя (часто также плохо отцентрированного). К тому же разная скорость вращения для разных областей диска повышает время доступа, т.к. при перемещении головки необходимо и соответственно изменять скорость вращения диска. Дальнейшее повышение скорости таким способом очень проблематично, поэтому производители перешли к технологии P-CAV и CAV. Первая предусматривает переход от постоянной линейной скорости к постоянной угловой скорости (CAV) на внешних дорожках диска, а вторая использует постоянную угловую скорость для всего диска. В связи с этим цифры типа 32x немного утрачивают свое значение, т.к. обычно относятся к внешней стороне диска, а информация на CD записывается начиная с внутренних дорожек и на незаполненных полностью дисках эта скорость вообще не достигается. Объем современных CD составляет 640 или 700 Мб для размера дисков – 5.25”.

Развитием технологии CD стала технология DVD. В ней применяется лазер с меньшей длиной волны, за счет чего достигается большая плотность записи данных. Кроме того, формат DVD позволяет производить запись на две стороны диска и на два уровня с каждой стороны. Запись на различные уровни производится за счет фокусировки лазера на разном расстоянии от центра диска. Большинство дисков DVD имеют емкость 4.7GB. Применение схем удвоения плотности и их комбинирования, позволяет иметь диски большей емкости: от 8.5Gb и 9.4Gb до 17Gb.

Магнитооптические накопители

Магнитооптическая технология разрабатывалась фирмой Intel с начала 70-х годов и появилась на рынке в середине 80-х. Запись на такие диски осуществляется при помощи лазера и магнита. Лазер нагревает поверхность до определенной температуры, когда материал теряет магнитную проницаемость, после чего магнит приводит все ячейки в одно состояние, стирая информацию. На второй фазе магнитное поле меняется на противоположное, а лазер включается в те моменты, когда необходимо изменить значение бита. При чтении используется лазерный луч. Проходя через фрагменты материала с различной полярностью луч лазера также поляризуется различным образом, что определяет светочувствительный элемент и система фильтров. Емкость различных накопителей составляет 650 Мб, 1.3 Гб, 2.4 Гб. Размер носителей 3,5 или 5,25”. На данный момент магнито-оптические носители практически не используются, так как их вытеснили более дешевые DVD.

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

Организация ввода-вывода информации в ВС

Для ввода/вывода данных в МПС применяются следующие методы:

- по программному опросу;

- по прерываниям;

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

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

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

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

Работа системы происходит следующим образом. При обнаружении готовности ВУ к обмену КВУ формирует запрос прерывания (IRQ0-IRQ15). Эти сигналы поступают на вход контроллера прерываний (КП). КП анализирует приоритет запроса и определяет разрешен данный запрос или нет. Приоритет запроса определяется номером входа, разрешения задаются при начальной настройке МПС. Если запрос разрешен и имеет наивысший приоритет по сравнению с другими имеющимися прерываниями, то КП формирует сигнал прерывания для МП. МП заканчивает выполнение текущей команды и формирует сигнал подтверждения прерывания INTA для КП. Этот сигнал одновременно запрещает работу памяти и всех остальных КВУ, так как обмен данными должен происходить лишь между МП и КП. После этого КП выдает на ШД код команды вызова подпрограммы, а МП ее выполняет. После этого МП вновь выдает сигнал подтверждения прерывания, по которым считывает из КП адрес подпрограммы обслуживания данного прерывания. Данные адреса записываются во внутренние регистры КП при настройке МПС. После приема прерывания все прерывания могут быть запрещены. В этом случае в конце программы обработки прерывания должна стоять команда разрешения обработки прерываний, гарантирующая нормальную работоспособность системы.

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

Обслуживание ВУ по прямому доступу к памяти

В ряде случае ВУ обеспечивают очень высокие скорости обмена информацией с МП. При этом МП не успевает обслуживать ВУ. Для решения данных задач в состав МПС вводится контроллер прямого доступа к памяти (КПДП). Он содержит регистры адреса и счетчики адреса для 4 каналов ПДП.

Работа системы происходит следующим образом.

При готовности ВУ к обмену КВУ организует сигнал запроса данных DRQ0-DRQ3. КПДП формирует сигнал приостановки работы процессора HOLD. Получив этот сигнал, МП переводит свои ША, ШД, ШУ в 3-е состояние и формирует сигнал подтверждения приостановки HLDA. С этого момента все управление системой берет на себя КПДП. Он выдает сигнал подтверждения данных DACK0-DACK3, который поступает на вход КВУ и является для него сигналом разрешения обмена. В это же время на ШУ выставляется сигнал MEMR или MEMW. На ША КПДП выставляет очередной адрес соответствующий буферу в ОЗУ, с которым производится обмен данными. По ШД передается байт из памяти или в память.

Определение и задачи операционной системы

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

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

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

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

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

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

Из наиболее важных задач управления ресурсами обычно выделяют следующие.

• Управление процессами. ОС должна предоставлять возможность запускать, останавливать, приостанавливать и возобновить выполнение программы. При запуске программы необходимо выделить ей область памяти, другие необходимые ресурсы вычислительной системы; при остановке – освободить все выделенные ресурсы. В ходе работы ОС должна уметь передавать управление различным процессам, то есть управлять процессорным временем. Здесь следует заметить чем отличается задача и программа от процесса. Программа и задача являются статичными объектами, тогда как процесс – динамическая сущность. Формально процесс – это траектория движения системы в пространстве состояний во времени. Программа (приложение) это откомпилированный алгоритм и данные, хранимые на диске. Задача – это совокупность программ и входных данных, которые необходимо выполнить.

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

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

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

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

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

Классификация операционных систем

Операционные системы можно классифицировать по нескольким признакам.

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

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

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

Рис. Структура монолитной ОС

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

Рис. Структура микроядерной ОС

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

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

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

Гибридные ОС объединяют в себе различные вышеописанные подходы.

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

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

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

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

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

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

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

Структура ОС

В состав операционной системы традиционно входят следующие подсистемы.

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

 Ядро ОС. В задачи ядра ОС входит управление процессами и ресурсами. В связи с этим в состав ядра вводятся менеджеры процессов и ресурсов.

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

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

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

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

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

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

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

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

 API (Application Programmer Interface). API – это набор функций, предоставляемых ОС процессам. Формально пользовательский интерфейс входит в состав API. Кроме того, различные ОС предоставляют различные возможности через API: обращение к файловой подсистеме, передача информации по сети, обращение к аппаратуре, обеспечение безопасности и так далее. Различные ОС предоставляют посредством API разлиную функциональность. Сам API также реализуется различным образом.

Рис. Структура ОС Unix

Задачи, процессы и потоки

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

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

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

Задачи загрузчика были разобраны в предыдущей лекции. Обработчики прерываний работают следующим образом. При возникновении прерывания процессор заканчивает выполнение инструкции и переходит на известный ему адрес обработчика прерываний, предварительно поместив в стек адрес следующей за выполненной инструкцией. В процессоре Intel 8086 по адресу 00000000h хранилась таблица прерываний: массив из 256 4-байтных слов, каждое из которых хранило адрес обработчика прерываний. Каждое из прерываний имеет свой номер, который определял номер ячейки массива. Задачей обработчика прерывания было сохранить состояние регистров и по завершении своей работы восстановить их. Обычно для сохранения значений использовался стек. Возврат из прерывания производился при помощи специальной команды процессора, которая восстанавливала из стека адрес и переходила по нему. Таким образом, выполнение основной программы происходит со следующей инструкции и при том же состоянии регистров (при условии, что обработчик корректно сохранил и восстановил их) и программа не «замечает», что ее работа была прервана.

Рисунок

Серьезную проблему составляли вызовы системных функций. Дело в том, что от версии к версии операционной системы адреса отдельных функций могут меняться. Если мы пишем специализированную встроенную ОС, то мы можем одновременно откомпилировать как ОС, так и те немногие задачи, которые будут под ней выполняться. Зачастую подобная система представляет собой просто единый проект, так что связывание функций и их вызовов производится автоматически. Однако при создании «живой и дышащей» ОС общего назначения, которая развивается и исправляется, разработчики ОС и прикладного ПО – совсем разные люди. Для процессора Intel 8086 системные функции вызывались при помощи прерываний. Таблица прерываний находится в фиксированном месте, большая часть прерываний не используется в связи с бедностью аппаратуры, входящей в состав вычислительной системы, так что свободных адресов прерываний имеется в избытке. Те же методы использовались и драйверами – для вызова функций драйвера вызывалось определенное прерывание. Чтобы сократить количество используемых прерываний, в системную функцию в регистре передавался код функции, по которому ОС определяла, какое именно действие необходимо совершить. Так, например, подавляющее большинство системных функций MS-DOS «сидело» на прерывании 21h. Для вызова прерываний использовалась специальная команда процессора.

Рисунок

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

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

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

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

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

Другой путь присущ ОС общего назначения и схож с методами, используемыми в многозадачных ОС. Например, мы можем решить проводить параллельные вычисления каждые 100 мс в течение 10 мс, то есть отводим себе 10% процессорного времени. В таком случае мы можем написать программу, обладающую следующей структурой. При запуске программа перехватывает прерывание таймера, то есть записывает в него адрес собственной процедуры. Сложность заключается в том, что после завершения работы приложения (мы ведь должны вернуть управление ОС) процедура должна остаться в памяти, а ОС освободит все ресурсы, выделенные нашей программе, в том числе и оперативную память. В связи с этим необходимо расположить процедуру в области памяти, за которую ОС не несет ответственности, например, (на свой страх и риск) в видеопамяти. Следующая сложность – переменные. Так как вся память освобождена, то нам необходимо также, как и с самой процедурой, искать дополнительной памяти. Еще одна особенность – это сам перехват прерывания. Если, например, программа перехватывает клавиатурное прерывание, например для того, чтобы вывести на экран текущее состояние задачи, то она не должна владеть им монопольно, так как до ОС должны доходить сообщения от клавиатуры. Для этого необходимо сохранить старый адрес прерывания и, после выполнения собственных действий, при необходимости вызывать его. За возврат из прерывания при этом будет отвечать вызванный нами обработчик прерывания.

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

Рисунок

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

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

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

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

Еще одним вариантом реализации многозадачности является невытесняющее планирование процессов. Каждая задача обрабатывает сообщения, поступающие от внешней среды. При возникновении некоторого события, ОС генерирует сообщение для процесса и передает ему управление, чтобы процесс смог выполнить процедуру обработки этого сообщения. По окончании обработки, процесс возвращает управление ОС. Данный подход довольно просто реализуем, но плох тем, что если для обработки сообщения потребуются длительные вычисления (например, пользователь выбрал пункт меню, подразумевающий вычисление системы дифференциальных уравнений), то ОС не получит управление в течение длительного времени. Прерывания будут обрабатываться, однако ОС даже не сможет сгенерировать сообщения о них, то есть обработка событий процессами не будет проводиться. Зависший процесс и вовсе приведет к краху системы. Такой подход к реализации многозадачности использовался в Windows 3.1 и Apple Macintosh.

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

Рисунки

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

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

В конкретных операционных системах состояния процесса могут быть еще более детализированы, могут появиться некоторые новые варианты переходов из одного состояния в другое. Так, например, могут появиться такие состояния как порождаемый и удаляемый процесс. Модель состояний процессов для операционной системы Windows NT содержит 7 различных состояний, а для операционной системы Unix – 9. Но так или иначе, все операционные системы подчиняются изложенной выше модели.

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

Рис. Диаграмма состояний процессов в ОС Unix

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

Следует заметить, что наивысший приоритет не всегда означает наивысший номер приоритета. Так в процессорах Intel наивысший приоритет имеет номер 0, а наименьший – 7. На уровне процессора приоритеты задают наборы команд, которые имеет право использовать процесс, и правила их выполнения. На практике могут использоваться не все приоритеты. Windows использует только 2 уровня приоритетов – ОС (0) и приложение (4).

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

На практике применяют один из следующих методов планирования процессорного времени.

First-Come, First-Served (FCFS), Первый пришел, первый обслужен – это алгоритм невытесняющего планирования, предполагающий, что задачи выполняются одна за одной по мере их поступления. То есть для поступающих процессов образуется очередь, в которую и поступает каждый прибывший процесс. Однако если к нам последовательно поступят три задачи, время выполнения которых убывает, то получится, что самая последняя задача будет больше находиться в состоянии ожидания, чем выполняться. При обратном порядке поступления процессов время ожидания резко сокращается, то есть оптимальность алгоритма зависит от порядка поступления процессов.

Рисунки и диаграммы?

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

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

Рисунки и диаграммы?

Shortest-Job-First (SJF), кратчайшая работа первой. Как мы могли видеть, время ожидания процессов существенно зависит от порядка их выполнения. Мы можем сократить его, если обладаем информацией о времени выполнения процесса. Алгоритм SJF может быть реализован как вытесняющий, так и как невытесняющий. При невытесняющем планировании при выборе очередного процесса мы выбираем процесс с самым коротким временем исполнения. При вытесняющем планировании при поступлении нового процесса проверяется, не меньше ли его время выполнения, чем оставшееся время выполнения текущего процесса.

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

Гарантированное планирование. При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N. Для каждого пользователя с номером i введем две величины: Ti – время нахождения пользователя в системе или, другими словами, длительность сеанса его общения с машиной и τi – суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение Ti/N процессорного времени. Если

τi<<Ti/N

то i-й пользователь несправедливо обделен процессорным временем. Если же

τi>>Ti/N

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

τi=N/Ti

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

Приоритетное планирование. Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка времени использования процессора. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет.

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

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

В рассмотренном выше примере приоритеты процессов с течением времени не изменялись. Такие приоритеты принято называть статическими. Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связаны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением работы системы.

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз по истечении определенного промежутка времени значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, присваивается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.

Многоуровневые очереди (Multilevel Queue). Для систем, в которых процессы могут быть легко рассортированы по разным группам, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность. Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue). Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из одной очереди в другую в зависимости от своего поведения.

Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке ниже. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке располагается очередь, тем выше ее приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1. И, наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты. Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым. Планирование процессов внутри очередей 0–2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.

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

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его выполнения меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается – остается в очереди 1. В очереди 2 величина кванта времени составляет 32 единицы. Если для непрерывной работы процесса и этого мало, процесс поступает в очередь 3, для которой квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания. Чем больше значение продолжительности использования процессора, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать. Таким образом, через некоторое время все процессы, требующие малого времени работы процессора, окажутся размещенными в высокоприоритетных очередях, а все процессы, требующие большого счета и с низкими запросами к времени отклика, – в низкоприоритетных.

Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0, после завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1, а после завершения ожидания всех других событий – из очереди 3 в очередь 2. Перемещение процессов из очередей с низкими приоритетами в очереди с высокими приоритетами позволяет более полно учитывать изменение поведения процессов с течением времени.

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

• Количество очередей для процессов, находящихся в состоянии готовность.

• Алгоритм планирования, действующий между очередями.

• Алгоритмы планирования, действующие внутри очередей.

• Правила помещения родившегося процесса в одну из очередей.

• Правила перевода процессов из одной очереди в другую.

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

Реализация многозадачности

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

 состояние, в котором находится процесс;

 программный счетчик процесса или, другими словами, адрес команды, которая должна быть выполнена для него следующей;

 содержимое регистров процессора;

 данные, необходимые для планирования использования процессора и управления памятью (приоритет процесса, размер и расположение адресного пространства, …);

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

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

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

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

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

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

Рисунок

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

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

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

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

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

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

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

Аппаратная поддержка многозадачности

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

Процессор Pentium имеет 32-разрядные шину адреса и шину данных. В состав МП входят 4 регистра общего назначения, 4 регистра указателя и индексации, 6 сегментных регистров, регистр команды и регистр флажков. Все регистры имеют длину 32 разряда.

К регистрам общего назначения относятся: аккумулятор EAX, база EBX, счетчик ECX, данные EDX. Эти регистры могут использовать для проведения арифметико-логических и прочих операций. К регистрам указателя и индексации относятся указатель стека ESP, указатель базы EBP, индекс ESI и индекс получателя EDI.

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

К сегментным регистрам относятся CS - сегмент кода, DS - сегмент данных, SS - сегмент стека, ES - дополнительный сегмент, FS, GS - новые дополнительные сегменты.

Регистр флажков содержит 32 бита. Каждый бит означает некоторое состояние, в котором на данный момент находится МП.

В состав процессора входят также 5 управляющих регистров CR0-CR4. Регистр CR0 отвечает за режимы работы с сопроцессором, разрешения/запреты на работу с различными режимами адресации и кэшем. CR1 зарезервирован, CR2 хранит адрес отката в случае отказа страницы. CR3 хранит 20-битный физический базовый адрес таблицы каталога страниц, биты, отвечающие за вид кэширования страниц. CR4 расширяет возможности обработки страниц памяти, работы с расширенным набором инструкций (MMX, SSE), работы с прерываниями.

Также процессор содержит 8 отладочных регистров DR0-DR8. Регистры DR0-DR3 хранят адреса останова, то есть в случае обращения к этим адресам происходит останов выполнения программы и вызов прерывания. Регистры DR4-DR5 зарезервированы, регистры DR6-DR7 содержат флажки, показывающие необходимо ли производить останов по каждому из регистров DR0-DR3, для всех или только текущей задачи, по какому событию (выполнение команды, чтение, запись), какого вида адрес хранится в регистре.

Для управления памятью процессором в защищенном режиме используются 4 регистра. IDTR регистр дескрипторной таблицы прерываний, адресует таблицу точек входа обработки прерываний. GDTR – регистр глобальной дескрипторной таблицы, содержит дескрипторы сегментов памяти, доступных любой задаче. LDTR – регистр локальной дескрипторной таблицы, содержит дескрипторы сегментов памяти, доступных только текущей задаче. TR – регистр задачи, содержит копию дескриптора текущей задачи и показывает где находится сам дескриптор.

Дескриптор задачи выглядит следующим образом.

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

Средства вызова процедур

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

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

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

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

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

Синхронизация

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

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

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

Рисунки

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

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

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

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

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

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

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

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

Рисунки

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

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

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

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

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

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

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

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

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

Виды памяти

Можно выделить 4 вида памяти.

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

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

 Основная (оперативная) память – память, хранящая команды для процессора и данные. Является относительно быстрой и объемной.

 Внешняя память – самый медленный, объемный и дешевый (на два-три порядка дешевле оперативной) вид памяти.

Виртуальная и физическая память

При адресации переменных в памяти используются три вида адресов:

- символьные имена, присваиваемые пользователем и преобразуемые транслятором в следующие два вида адресов;

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

- физические адреса, также называемые эффективными адресами – номера ячеек памяти, в которых расположены данные.

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

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

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

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

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

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

Алгоритмы распределения памяти

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

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

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

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

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

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

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

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

Адресация памяти в процессоре 80386

В процессоре 8086 память адресовалась при помощи 16-битного регистра сегмента и 16-битного смещения. При этом регистр сегмента сдвигался влево на 4 бита, после чего к нему прибавляется смещение. В результате получался 20-битный адрес.

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

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

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

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

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

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

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

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

Таблицы страниц сами хранятся в оперативной памяти, то есть в некоторых страницах оперативной памяти. Использование страниц размером в 4К требует 4М оперативной памяти для хранения таблицы страниц. Однако так как не все страницы используются можно выгрузить их на диск, в том числе и их дескрипторы. Для ускорения процесса загрузки/выгрузки страниц используется понятие раздела. Раздел – это такое количество страниц, дескрипторы которых умещаются в страницу. В связи с введением разделов усложняется и структура получения адреса. Для каждой задачи формируется таблица разделов, хранящая дескрипторы разделов, аналогичные дескрипторам страниц. Каждая запись таблицы разделов указывает на таблицу страниц. Адрес представляется в виде тройки <номер раздела, номер страницы в разделе, смещение в странице>. При получении физического адреса происходит обращение к таблице разделов, из которой получается адрес соответствующей таблицы страниц. Дальнейшее вычисление адреса происходит по уже описанной схеме.

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

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

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

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

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

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

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

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

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

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

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

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

Показать полностью…
Похожие документы в приложении