1. Понятия ОС

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

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

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

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

В большинстве вычислительных систем операционная система является основной, наиболее важной (а иногда и единственной) частью системного программного обеспечения. С 1990-х годов наиболее распространёнными операционными системами являются системы семейства MicrosoftWindowsи системы классаUNIX(особенноLinuxиMacOS).

2. История создания ОС

1. Первый период (1945–1955 гг.). Ламповые машины. Операционных систем нет

Мы начнем исследование развития компьютерных комплексов с появления электронных вычислительных систем (опуская историю механических и электромеханических устройств).

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

Вычислительная система выполняла одновременно только одну операцию (ввод-вывод или собственно вычисления). Отладка программ велась с пульта управления с помощью изучения состояния памяти и регистров машины. В конце этого периода появляется первое системное программное обеспечение: в 1951–1952 гг. возникают прообразы первых компиляторов с символических языков (Fortran и др.), а в 1954 г. Nat Rochester разрабатывает Ассемблер для IBM-701.

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

2. Второй период (1955 г.–начало 60-х). Компьютеры на основе транзисторов. Пакетные операционные системы

С середины 50-х годов начался следующий период в эволюции вычислительной техники, связанный с появлением новой технической базы – полупроводниковых элементов. Применение транзисторов вместо часто перегоравших электронных ламп привело к повышению надежности компьютеров. Теперь машины могут непрерывно работать достаточно долго, чтобы на них можно было возложить выполнение практически важных задач. Снижается потребление вычислительными машинами электроэнергии, совершенствуются системы охлаждения. Размеры компьютеров уменьшились. Снизилась стоимость эксплуатации и обслуживания вычислительной техники. Началось использование ЭВМ коммерческими фирмами. Одновременно наблюдается бурное развитие алгоритмических языков (LISP,COBOL,ALGOL-60,PL-1 и т.д.). Появляются первые настоящие компиляторы, редакторы связей, библиотеки математических и служебных подпрограмм. Упрощается процесс программирования. Пропадает необходимость взваливать на одних и тех же людей весь процесс разработки и использования компьютеров. Именно в этот период происходит разделение персонала на программистов и операторов, специалистов по эксплуатации и разработчиков вычислительных машин.

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

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

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

3. Третий период (начало 60-х – 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ОС

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

Повышению эффективности использования процессорного времени мешает низкая скорость работы механических устройств ввода-вывода (быстрый считыватель перфокарт мог обработать 1200 перфокарт в минуту, принтеры печатали до 600 строк в минуту). Вместо непосредственного чтения пакета заданий с перфокарт в память начинают использовать его предварительную запись, сначала на магнитную ленту, а затем и на диск. Когда в процессе выполнения задания требуется ввод данных, они читаются с диска. Точно так же выходная информация сначала копируется в системный буфер и записывается на ленту или диск, а печатается только после завершения задания. Вначале действительные операции ввода-вывода осуществлялись в режиме off-line, то есть с использованием других, более простых, отдельно стоящих компьютеров. В дальнейшем они начинают выполняться на том же компьютере, который производит вычисления, то есть в режимеon-line. Такой прием получает названиеspooling(сокращение отSimultaneousPeripheralOperationOnLine) или подкачки-откачки данных. Введение техники подкачки-откачки в пакетные системы позволило совместить реальные операции ввода-вывода одного задания с выполнением другого задания, но потребовало разработки аппарата прерываний для извещения процессора об окончании этих операций.

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

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

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

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

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

• Развитие параллелизма в архитектуре. Прямой доступ к памяти и организация каналов ввода-вывода позволили освободить центральный процессор от рутинных операций.

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

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

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

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

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

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

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

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

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

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

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

Параллельно внутренней эволюции вычислительных систем происходила и внешняя их эволюция. До начала этого периода вычислительные комплексы были, как правило, несовместимы. Каждый имел собственную операционную систему, свою систему команд и т. д. В результате программу, успешно работающую на одном типе машин, необходимо было полностью переписывать и заново отлаживать для выполнения на компьютерах другого типа. В начале третьего периода появилась идея создания семейств программно совместимых машин, работающих под управлением одной и той же операционной системы. Первым семейством программно совместимых компьютеров, построенных на интегральных микросхемах, стала серия машин IBM/360. Разработанное в начале 60-х годов, это семейство значительно превосходило машины второго поколения по критерию цена/производительность. За ним последовала линия компьютеровPDP, несовместимых с линиейIBM, и лучшей моделью в ней сталаPDP-11.

Сила "одной семьи" была одновременно и ее слабостью. Широкие возможности этой концепции (наличие всех моделей: от мини-компьютеров до гигантских машин; обилие разнообразной периферии; различное окружение; различные пользователи) порождали сложную и громоздкую операционную систему. Миллионы строчек Ассемблера, написанные тысячами программистов, содержали множество ошибок, что вызывало непрерывный поток публикаций о них и попыток исправления. Только в операционной системе OS/360 содержалось более 1000 известных ошибок. Тем не менее идея стандартизации операционных систем была широко внедрена в сознание пользователей и в дальнейшем получила активное развитие.

4. Четвертый период (с 1980 г. по настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Виды ОС

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

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

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

однозадачные (MS-DOS);

псевдомногозадачные, то есть одновременно работает только одна программа, а мы переключаясь между ними как-бы пробуждаем другую и усыпляем первую (Windows1 и 2);

многозадачные (Windows95,98);

реально многозадачные (WindowsNT,OS/2 3 и 4,Unix,Be,Linux).

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

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

нет поддержки (MS-DOS,Windows1-2-3);

поддерживается на одном терминале, хранятся различные профили для настройки системы под пользователя (Windows95-98-Me-NT-2000);

реальная многопользовательность, то есть могут одновременно работать несколько человек на разных терминалах, но с одним ПК (WindowsNTTerminalServer,Unix,Linux(?)).

Выделим еще одну группу ОС, для которых не очень важен интерфесй, а важны скоростные и надежностные характеристики работы - серверные ОС. Например, Windows NT Server, OS/2 Advanced Server, Novel Netware/IntranetWare, Banyan Wines.

Ну и последняя группа ОС - встраиваемые ОС. Сюда относятся ОС, которые встраиваются в различные устройства, например, сотовые телефоны, органайзеры и прочие микроэлектронные игрушки. Примером таких ОС можно наpвать:PalmOS,WindowsCE.

4. Архитектура ОС

Перечислим основные типы внутренней архитектуры операционных систем и в качестве примеров рассмотрим архитектуру наиболее распространенных операционных систем – систем UNIXиWindows.

Разливают всего три базовых типа архитектуры операционных систем:

• монолитная архитектура;

• многоуровневая архитектура;

• архитектура типа клиент-сервер на основе микроядра.

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

Монолитная архитектура операционной системы

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

Заметим, что монолитную архитектуру имели самые первые поколения операционных систем.

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

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

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

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

Многоуровневая архитектура

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

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

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

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

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

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

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

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

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

Одной из первых операционных систем, разработанных на основе многоуровневой архитектуры, стала операционная система THE, разработанная профессором Дейк-строй и его студентами в 1968 году. Операционная системаTHEимела 6 уровней, про-нумерованных от 0 до 5:

Уровень 0. Этот уровень выполнял распределение ресурсов процессора и переключал процессы по истечению кванта времени или при возникновении прерывания.

Уровень 1. Этот уровень осуществлял управление виртуальной памятью.

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

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

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

Уровень 5. На этом уровне выполнялся процесс системного администратора.

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

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

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

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

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

Поэтому классическая многоуровневая архитектура в наиболее современных операционных системах вытесняется архитектурой типа клиент-сервер.

Архитектура типа клиент-сервер на основе микроядра

Архитектура типа клиент-сервер в настоящее время является наиболее совершенной с точки зрения расширяемости и переносимости операционных систем.

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

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

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

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

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

Таким образом, архитектура клиент-сервер обеспечивает следующие основные преимущества:

• переносимость операционной системы, т.к. серверы, работающие в пользовательском режиме, аппаратно независимы;

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

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

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

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

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

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

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

5. Процессы (понятие процесса, модель процесса)

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

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

Модель процесса:

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

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

6. Состояния процессов (диаграммы состояний процессов)

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

Модель с пятью состояниями:

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

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

• Блокированный. Процесс, который не может выполняться до тех пор, пока не произойдет некоторое событие, например завершение операции ввода-вывода.

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

• Завершающийся. Процесс, удаленный операционной системой из пула выполнимых процессов.

7. Потоки (модель потока, использование потоков, реализация потоков)

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

Модель потока:

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

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

• Счетчик команд, отслеживающий порядок выполнения действий;

• Регистры, в которых хранятся текущие переменные;

• Стэк, содержащий протокол выполнения процесса.

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

Многопоточность описывает использование нескольких потоков в одном процессе.

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

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

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

Использование потоков:

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

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

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

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

Реализация потоков:

Есть два способа реализации пакета потоков: в пространстве пользователя и ядре. Возможна смешанная реализация.

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

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

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

На уровне ядра:

В программе, работа которой полностью основана на потоках, работающих на уровне ядра, все действия по управлению потоками выполняются ядром. В области приложений отсутствует код, предназначенный для управления потоками. Вместо него используется интерфейс прикладного программирования (application programming interface — API) средств ядра, управляющих потоками. Примерами такого подхода являются операционные системы OS/2, Linux и W2K.

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

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

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

8. Диспетчеризация потоков

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

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

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

9. Приоритеты и механизмы синхронизации

Приоритеты:

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

класса приоритета процесса, в контексте которого выполняется поток, О уровня приоритета потока внутри класса приоритета потока.

Комбинация этих параметров определяет базовый приоритет (base priority) потока. Существует шесть классов приоритетов для процессов:

• IDLE_PRIORITY_CLASS,

• BELOW_NORMAL_PRIORITY_CLASS,

• NORMAL__PRIORITY_CLASS,

• ABOVE_NORMAL_PRIORITY_CLASS,

• HIGH_PRIORITY_CLASS,

• REALTIME_PRIORITY_CLASS

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

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

Потоки:

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

Процессы:

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

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

Семафо́р— объект, позволяющий войти в заданный участок кода не более чем n потокам. Определение введено Эдсгером Дейкстрой.

Семафоры используются при передаче данных через разделяемую память

Мью́текс(англ. mutex, от mutual exclusion — «взаимное исключение») — одноместный семафор, служащий в программировании для синхронизации одновременно выполняющихся потоков.

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

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

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

Каналы и разделяемую память вспоминаем по твп или смотрим в твп: в книжке с лабами, или в лекциях;)

10. Защита от инверсий приоритетов

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

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

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

Другой, несколько менее распространенный метод, называется Протокол Предельного Приоритета (PriorityCeilingProtocol) [6]. Метод этот заключается в добавлении к стандартным свойствам объектов синхронизации параметра, определяемого максимальным приоритетом потока, которые к этому объекту обращаются. Если этот параметр установлен, то приоритет любого потока, обращающегося к этому объекту синхронизации, будет увеличен до указанного уровня, и, таким образом, не сможет быть вытеснен никаким потоком, который может нуждаться в заблокированном им ресурсе. После разблокирования ресурса, приоритет потока понижается до начального уровня. Таким образом, получается нечто вроде предварительного наследования приоритетов. Однако этот метод имеет ряд серьезных недостатков. В первую очередь, на разработчика ложиться работа по «обучению» объектов синхронизации их уровню приоритетов. Во вторых, возможны задержки в запуске высокоприоритетных потоков на время отработки низкоприоритетных потоков. В целом максимально эффективно этот механизм может быть использован в случае, когда имеется один поток жесткого реального времени и несколько менее приоритетных потоков, разделяющих с ним ресурсы.

11.Межпроцессное взаимодействие(англ. Inter-Process Communication, IPC) — набор способов обмена данными между множеством потоков в одном или более процессах. Процессы могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена сообщениями, синхронизации, разделяемой памяти и удаленных вызовов (RPC). Методы IPC зависят от пропускной способности и задержки взаимодействия между потоками и типа передаваемых данных.

IPC наряду с концепцией адресного пространства является основой для разграничения адресного пространства.

Метод	Реализуется (операционной системой или другим окружением)
Файл	Все операционные системы.
Сигнал	Большинство операционных систем; некоторые системы, как например, Windows, только реализуют сигналы в библиотеке запуска Си, но не обеспечивают их полноценной поддержки для использования методов IPC.
Сокет	Большинство операционных систем.
Канал	Все системы, соответствующие POSIX.
Именованный канал	Все системы, соответствующие POSIX.
Семафор	Все системы, соответствующие POSIX.
Разделяемая память	Все системы, соответствующие POSIX.
Обмен сообщениями (без разделения)	Используется в парадигме MPI, Java RMI, CORBA и других.
Проецируемый в память файл	Все системы, соответствующие POSIX; несет риск появления состояния гонки в случае использования временного файла. Windows также поддерживает эту технологию, но использует API отличный от POSIX.
Очередь сообщений	Большинство операционных систем.
Почтовый ящик	Некоторые операционные системы.

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

Проблема обедающих философов

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

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

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

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

Проблема читателей и писателей

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

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

Проблема спящего брадобрея

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

В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.

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

Выгружаемые ресурсы-безболезненно забрать у владеющего им процесса.

Невыгружаемый ресурс-не может быть безболезненно отобран у процесса.

Алгоритм использования ресурсов в общем виде:

1. Запрос ресурсов

2. Использование ресурсов

3. Возврат ресурсов

Пр А	Пр Б
Запрос р-са 1	Запрос р-са 2
Запрос р-са 2	Запрос р-са 1
Использование р-ов	Использование р-ов
Возврат р-са 2	Возврат р-са 1
Возврат р-са 1	Возврат р-са 2

Условие взаимоблокировок:

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

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

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

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

Обнаружение и устранение взаимоблокировок:

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

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

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

Избежание взаимоблокировок:

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

Предотвращение взаимоблокировок:

1. Атака условия взаимного исключения

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

2. Атака условия удержания и ожидания

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

Недостатки данного способа решения:

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

• Ресурсы не будут использоваться оптимально

3. Атака условия отсутствия принудительной выгрузки ресурсов

Не существует нормального способа избежания взаимоблокировки, т.к. принудительное изъятие ресурса у процесса при его работе практически не возможна.

4. Атака условия циклического ожидания

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

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

5. Алгоритм банкира

Безопасное состояние-это такое состояние для которого иметься хотя бы одна последовательности событий которая не приведет к взаиоблокировке.

Суть алгоритма:

• Предположим, что у системы есть «х» устройств.

• Операционная система принимает запрос от пользовательского процесса, если его макс потребность не превышает «х».

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

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

• В соответствии с алгоритмом банкира выделения устройств возможно только если состояние системы остается надежным.

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

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

• Перезагрузка системы

• Рестарт системы с контрольной точки

Контрольная точка - полное состояние ПК сохраненное на внешнем носителе.

14. Выгружаемые ресурсы

См.13й (в интернетах нет нихчего, инфа 146%).

15. Невыгружаемые ресурсы

См.13й.

16.FAT (англ. File Allocation Table — «таблица размещения файлов») — классическая архитектура файловой системы, которая из-за своей простоты всё ещё широко используется для флеш-дисков и карт памяти. В недавнем прошлом использовалась в дискетах, на жёстких дисках и других носителях информации.

Разработана Биллом Гейтсом и Марком МакДональдом (англ.) в 1976—1977 годах. Использовалась в качестве основной файловой системы в операционных системах семейств DOS и Windows (до версии Windows 2000).

Структура FAT следует стандарту ECMA-107 и подробно определяется официальной спецификацией от Microsoft, известной под названием FATGEN.

FAT16	FAT32
Реализована и используется большинством операционных систем (MS-DOS, Windows 95/98/ Me , Windows 2000 и Windows XP , OS/2, UNIX).	На данный момент поддерживается только в Windows 95/98/ Me , Windows 2000 и Windows XP (бородатая статья, даже Висты нет, будьте оптимистами – врите, что все всё реализовали)
Очень эффективна для логических дисков размером менее 256 Мбайт.	Не работает с дисками объемом менее 512 Мбайт.
Поддерживает сжатие дисков, например по алгоритму DriveSpace.	Не поддерживает сжатие дисков.
Обрабатывает максимум 65 525 кластеров, размер которых зависит от объема логического диска. Так как максимальный размер кластеров равен 32 Кбайт, FAT16 может работать с логическими дисками объемом не более 2 Гбайт.	Способна работать с логическими дисками объемом до 2 047 Гбайт при максимальном размере кластеров в 32 Кбайт.
Чем больше размер логического диска, тем меньше эффективность хранения файлов в FAT'16-системе, так как увеличивается и размер кластеров. Пространство для файлов выделяется кластерами, и поэтому при максимальном объеме логического диска файл размером 10 Кбайт потребует 32 Кбайт, а 22 Кбайт дискового пространства пропадет впустую.	На логических дисках объемом менее 8 Гбайт размер кластеров составляет 4 Кбайт.

Максимально возможная длина файла в FAT32 равна 4 Гбайт за вычетом 2 байтов. Win32-приложения могут открывать файлы такой длины без специальной обработки. Остальные приложения должны использовать прерывание Int 21h, функцию 716С (FAT32) с флагом открытия, равным EXTEND-SIZE (1000h).

В файловой системе FAT32 на каждый кластер в таблице размещения файлов отводится по 4 байта, тогда как в FAT16 - по 2, а в FАТ12 - по 1,5.

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

17. Файловые системы (ntfs)

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

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

NTFS(аббревиатураNew Technology File System—Файловая Система Новой Технологии) — стандартная файловая система для семейства операционных систем Microsoft Windows NT.

Представлена 27 июля 1993 вместе с Windows NT 3.1. NTFS разработана на основе файловой системы HPFS (аббревиатура High Performance File System—Высокопроизводительная Файловая Система), создававшейся Microsoft совместно с IBM для операционной системы OS/2.

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

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

Во время установки ОС Windows ХР предлагается отформатировать диск в системе FATилиNTFS. При этом имеется в видуFAT32.

Все файловые системы построены на принципе: один кластер – один файл. Т.е. один кластер хранит данные только одного файла.

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

Рассмотрим на примере одного тома на диске объемом 120Гб и файла размером 10Кб.

Для FAT32 размер кластера будет 32Кб, а дляNTFS – 4Кб.

В FAT32 такой файл займет 1 кластер, при этом останется 32-10=22Кб незанятого места.

В NTFS такой файл займет 3 кластера, при этом останется 12-10=2Кб незанятого места.

Таким образом, переход от FAT32 кNTFS позволяет более оптимально использовать жесткий диск при наличии большого количества мелких файлов в системе.

18. Работа с несколькими файловыми системами Современные архитектуры файловых систем

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

Новая файловая система имеет многоуровневую структуру (рисунок 2.39), на верхнем уровне которой располагается так называемый переключатель файловых систем (в Windows 95, например, такой переключатель называется устанавливаемым диспетчером файловой системы - installable filesystem manager, IFS). Он обеспечивает интерфейс между запросами приложения и конкретной файловой системой, к которой обращается это приложение. Переключатель файловых систем преобразует запросы в формат, воспринимаемый следующим уровнем - уровнем файловых систем.

Рис. 2.39. Архитектура современной файловой системы

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

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

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

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

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