Краткая история эволюции вычислительных систем - раздел Компьютеры, КУРС ВВЕДЕНИЕ В ОПЕРАЦИОННЫЕ СИСТЕМЫ СОВМЕСТНО С КОМПАНИЕЙ INTEL Мы Будем Рассматривать Историю Развития Именно Вычислительных, А Не Операцион...
Мы будем рассматривать историю развития именно вычислительных, а не операционных систем, потому что hardware и программное обеспечение эволюционировали совместно, оказывая взаимное влияние друг на друга. Появление новых технических возможностей приводило к прорыву в области создания удобных, эффективных и безопасных программ, а новые идеи в программной области стимулировали поиски новых технических решений. Именно эти критерии удобство, эффективность и безопасность играли роль факторов естественного отбора при эволюции вычислительных систем.
Первый период (1945-1955). Ламповые машины. Операционные систем отсутствовали.
Мы начнем исследование развития компьютерных комплексов с появления электронных вычислительных систем (опуская историю механических и электромеханических устройств).
Первые шаги по созданию электронных вычислительных машин были предприняты в конце второй мировой войны. В середине 40-х были созданы первые ламповые вычислительные устройства, и появился принцип программы, хранимой в памяти машины (John Von Neumann, июнь 1945г). В то время одна и та же группа людей участвовала и в проектировании, и в эксплуатации, и в программировании вычислительной машины. Это была скорее научно-исследовательская работа в области вычислительной техники, а не регулярное использование компьютеров в качестве инструмента решения каких-либо практических задач из других прикладных областей. Программирование осуществлялось исключительно на машинном языке. Об операционных системах не было и речи, все задачи организации вычислительного процесса решались вручную каждым программистом с пульта управления. За пультом мог находиться только один пользователь. Программа загружалась в память машины в лучшем случае с колоды перфокарт, а обычно с помощью панели переключателей. Вычислительная система выполняла одновременно только одну операцию (ввод-вывод, собственно вычисления, размышления программиста). Отладка программ велась с пульта управления с помощью изучения состояния памяти и регистров машины. В конце этого периода появляется первое системное программное обеспечение: в 1951-52 гг. возникают прообразы первых компиляторов с символических языков (Fortran и др.), а в 1954 г. Nat Rochester разрабатывает ассемблер для IBM-701. В целом первый период характеризуется крайне высокой стоимостью вычислительных систем, их малым количеством и низкой эффективностью использования.
Второй период (1955-Начало 60-х). Компьютеры на основе транзисторов. Пакетные операционные системы
С середины 50-х годов начался новый период в эволюции вычислительной техники, связанный с появлением новой технической базы - полупроводниковых элементов. Применение транзисторов вместо часто перегоравших электронных ламп привело к повышению надежности компьютеров. Теперь они смогли непрерывно работать настолько долго, чтобы на них можно было возложить выполнение действительно практически важных задач. Снизилось потребление вычислительными машинами электроэнергии. Проще стали системы охлаждения. Размеры компьютеров уменьшились. Эксплуатация и обслуживание вычислительной техники подешевели. Началось использование ЭВМ коммерческими фирмами. Одновременно наблюдается бурное развитие алгоритмических языков (ALGOL-58, LISP, COBOL, ALGOL-60, PL-1 и т.д.). Появляются первые настоящие компиляторы, редакторы связей, библиотеки математических и служебных подпрограмм. Упрощается процесс программирования. Пропадает необходимости взваливать на одних и тех же людей весь процесс разработки и использования компьютеров. Именно в этот период происходит разделение персонала на программистов и операторов, специалистов по эксплуатации и разработчиков вычислительных машин.
Изменяется сам процесс прогона программ. Теперь пользователь приносит программу с входными данными в виде колоды перфокарт и указывает требуемые для нее ресурсы. Такая колода получает название задания. Оператор загружает задание в память машины и запускает его на исполнение. Полученные выходные данные печатаются на принтере, и пользователь получает их обратно через некоторое (довольно большое) время.
Смена запрошенных ресурсов вызывает приостановку выполнения программ. В результате процессор часто простаивает. Для повышения эффективности использования компьютера задания с похожими требуемыми ресурсами начинают собирать вместе, создавая пакет заданий.
Появляются первые системы пакетной обработки, которые просто автоматизируют запуск одной программы из пакета за другой и, тем самым, увеличивают коэффициент загрузки процессора. При реализации систем пакетной обработки был разработан формализованный язык управления заданиями, с помощью которого программист сообщал системе и оператору, какую работу он хочет выполнить на вычислительной машине. Системы пакетной обработки явились прообразом современных операционных систем, они стали первыми системными программами, предназначенными для управления вычислительным процессом.
Третий период (Начало 60-х - 1980). Компьютеры на основе интегральных микросхем. Первые многозадачные ОС.
Следующий важный период развития вычислительных машин относится к началу 60-х - 1980 годам. В это время в технической базе произошел переход от отдельных полупроводниковых элементов типа транзисторов к интегральным микросхемам. Вычислительная техника становится более надежной и дешевой. Растет сложность и количество задач, решаемых компьютерами. Повышается производительность процессоров.
Повышению эффективности использования процессорного времени мешает низкая скорость механических устройств ввода-вывода (быстрый считыватель перфокарт мог обработать 1200 перфокарт в минуту, принтеры печатали до 600 строк в минуту). Вместо непосредственного чтения пакета заданий с перфокарт в память начинают использовать его предварительную запись сначала на магнитную ленту, а затем и на диск. Когда в процессе выполнения заданию требуется ввод данных, они читаются с диска. Точно так же выходная информация сначала копируется в системный буфер и записывается на ленту или диск, а реально печатается только после завершения задания. Вначале действительные операции ввода-вывода осуществлялись в режиме off-line, то есть с использованием других, более простых, отдельно стоящих компьютеров. В дальнейшем они начинают выполняться на том же компьютере, который производит вычисления, то есть в режиме on-line. Такой прием получает название spooling (сокращение от Simultaneous Peripheral Operation On Line) или подкачки-откачки данных. Введение техники подкачки-откачки в пакетные системы позволило совместить реальные операции ввода-вывода одного задания с выполнением другого задания, но потребовало появления аппарата прерываний для извещения процессора об окончании этих операций.
Магнитные ленты были устройствами последовательного доступа, то есть информация считывалась с них в том порядке, в каком была записана. Появление магнитного диска, для которого не важен порядок чтения информации, то есть устройства прямого доступа, привело к дальнейшему развитию вычислительных систем. При обработке пакета заданий на магнитной ленте очередность запуска заданий определялась порядком их ввода. При обработке пакета заданий на магнитном диске появляется возможность выбора очередного выполняемого задания. Пакетные системы начинают заниматься планированием заданий: в зависимости от наличия запрошенных ресурсов, срочности вычислений и т.д. на счет выбирается то или иное задание.
Дальнейшее повышение эффективности использования процессора было достигнуто с помощью мультипрограммирования. Идея мультипрограммирования заключается в следующем: пока одна программа выполняет операцию ввода-вывода, процессор не простаивает, как это происходило при однопрограммном режиме, а выполняет другую программу. Когда операция ввода-вывода заканчивается, процессор возвращается к выполнению первой программы. Эта идея напоминает поведение преподавателя и студентов на экзамене. Пока один студент (программа) обдумывает ответ на поставленный вопрос (операция ввода-вывода), преподаватель (процессор) выслушивает ответ другого студента (вычисления). Естественно, что такая ситуация требует наличия в комнате нескольких студентов. Точно также мультипрограммирование требует наличия в памяти нескольких программ одновременно. При этом каждая программа загружается в свой участок оперативной памяти, называемый разделом, и не должна влиять на выполнение другой программы. (Студенты сидят за отдельными столами и не подсказывают друг другу.)
Появление мультипрограммирования требует целой революции в строении вычислительной системы. Большую роль, здесь играет аппаратная поддержка, наиболее существенные особенности которой:
- Реализация защитных механизмов. Программы не должны иметь самостоятельного доступа к распределению ресурсов, что приводит к появлению привилегированных и непривилегированных команд. Привилегированные команды, например команды ввода-вывода, могут исполняться только операционной системой. Говорят, что она работает в привилегированном режиме. Переход управления от прикладной программы к ОС сопровождается контролируемой сменой режима. Во-вторых, это защита памяти, позволяющая изолировать конкурирующие пользовательские программы друг от друга, а ОС от программ пользователей.
- Наличие прерываний. Внешние прерывания оповещают ОС о том, что произошло асинхронное событие, например, завершилась операция ввода-вывода. Внутренние прерывания (сейчас их принято называть исключительными ситуациями) возникают, когда выполнение программы привело к ситуации, требующей вмешательства ОС, например, деление на ноль или попытка нарушения защиты.
Не менее важна в организации мультипрограммирования роль операционной системы. Наиболее существенные изменения состояли в следующем:
- Интерфейс между прикладной программой и ОС был организован при помощи набора системных вызовов.
- Организация очереди из заданий в памяти и выделение процессора одному из заданий потребовалипланирования заданий.
- Для переключения процессора с одного задания на другое возникла потребность в сохранении содержимого регистров и структур данных, необходимых для выполнения задания, иначе говоря, контекста, для обеспечения правильного продолжения вычислений.
- Поскольку память является ограниченным ресурсом, оказались нужны стратегии управления памятью, то есть потребовалось упорядочить процессы размещения, замещения и выборки информации из памяти.
- Так как программы могут пожелать произвести санкционированный обмен данными, стало необходимо их обеспечить средствами коммуникации. И, наконец,
- Для корректного обмена данными необходимо предусмотреть координацию программами своих действий, т.е. средства синхронизации.
Мультипрограммные пакетные системы дают окружение, в котором различные системные ресурсы (например, процессор, память, периферийные устройства) используются эффективно. И все же пользователь не мог непосредственно взаимодействовать с заданием и должен был предусмотреть с помощью управляющих карт все возможные ситуации. Отладка программ по-прежнему занимала много времени и требовала изучения многостраничных распечаток содержимого памяти и регистров или использования отладочной печати.
Появление электроннолучевых дисплеев и переосмысление возможностей применения клавиатур поставили на очередь решение этой проблемы. Логическим расширением систем мультипрограммирования стали time-sharing системы или системы разделения времени. В них процессор переключается между задачами не только на время операций ввода-вывода, но и просто по прошествии определенного интервала времени. Эти переключения происходят столь часто, что пользователи могут взаимодействовать со своими программами во время их выполнения, то есть интерактивно. В результате появляется возможность одновременной работы многих пользователей на одной компьютерной системе. У каждого пользователя для этого должна быть хотя бы одна программа в памяти. Чтобы уменьшить ограничения на количество работающих пользователей, была внедрена идея неполного нахождения исполняемой программы в оперативной памяти. Основная часть программы находится на диске и необходимый для ее дальнейшего выполнения кусок может быть легко загружен в оперативную память, а ненужный выкачан обратно на диск. Это реализуется с помощью механизма виртуальной памяти. Основным достоинством такого механизма является создание иллюзии неограниченной оперативной памяти ЭВМ.
В системах разделения времени пользователь получил возможность легко и эффективно вести отладку своей программы в интерактивном режиме, записывать информацию на диск, не используя перфокарты, а непосредственно с клавиатуры. Появление on-line файлов привело к необходимости разработки развитых файловых систем.
Параллельно внутренней эволюции вычислительных систем в этот период наблюдается и внешняя их эволюция. До начала этого периода вычислительные комплексы были, как правило, несовместимы. Каждый имела свою собственную специальную операционную систему, свою систему команд и т.д. В результате программу, успешно работающую на одном типе машин, необходимо было полностью переписать и заново отладить для другого типа компьютеров. В начале третьего периода появилась идея создания семейств программно-совместимых машин, работающих под управлением одной и той же операционной системы. Первым семейством программно-совместимых машин, построенных на интегральных микросхемах, явилась серия машин IBM/360. Построенное в начале 60-х годов это семейство значительно превосходило машины второго поколения по критерию цена/производительность. За ней последовала линия компьютеров PDP, несовместимых с линией IBM, кульминацией которой стала PDP-11.
Сила одной семьи была одновременно и ее слабостью. Широкие возможности этой концепции (наличие всех моделей: от миникомпьютеров до гигантских машин; обилие разнообразной периферии; различное окружение; различные пользователи) порождали сложную и огромную операционную систему. Миллионы строчек ассемблера, написанные тысячами программистов, содержали множество ошибок, что вызывало непрерывный поток публикаций о них и попыток их исправления. Только в операционной системе OS/360 содержалось более 1000 известных ошибок. Тем не менее, идея стандартизации операционных систем была широко внедрена в сознание пользователей и в дальнейшем получила активное развитие.
Четвертый период (1980-настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы.
Следующий период в эволюции вычислительных систем связан с появлением больших интегральных схем (БИС). В эти годы произошло резкое возрастание степени интеграции и удешевление микросхем. Компьютер, не отличающийся по архитектуре от PDP-11, по цене и простоте эксплуатации стал доступен отдельному человеку, а не отделу предприятия или университета. Наступила эра персональных компьютеров. Первоначально персональные компьютеры предназначались для использования одним пользователем в однопрограммном режиме, что повлекло за собой деградацию архитектуры этих ЭВМ и их операционных систем (в частности, пропала необходимость защиты файлов и памяти, планирования заданий и т.п.).
Компьютеры стали широко использоваться неспециалистами, что потребовало разработки "дружественного" программного обеспечения, это положило конец кастовости программистов.
Однако рост сложности и разнообразия задач, решаемых на персональных компьютерах, необходимость повышения надежности их работы привели к возрождению практически всех черт, характерных для архитектуры больших вычислительных систем.
В середине 80-х стали бурно развиваться сети компьютеров, в том числе персональных, работающих под управлением сетевых или распределенных операционных систем.
В сетевых операционных системах пользователи, при необходимости воспользоваться ресурсами другого сетевого компьютера, должны знать о его наличии и уметь это сделать. Каждая машина в сети работает под управлением своей локальной операционной системы, отличающейся от операционной системы автономного компьютера наличием дополнительных средств (программной поддержкой для сетевых интерфейсных устройств и доступа к удаленным ресурсам), но эти дополнения существенно не меняют структуру операционной системы.
Распределенная система, напротив, внешне выглядит как обычная автономная система. Пользователь не знает и не должен знать, где его файлы хранятся на локальной или удаленной машине, и где его программы выполняются. Он может вообще не знать, подключен ли его компьютер к сети. Внутреннее строение распределенной операционной системы имеет существенные отличия от автономных систем.
В дальнейшем автономные операционные системы мы будем называть классическими операционными системами.
Что мы вынесли из истории развития вычислительных систем?
Просмотрев этапы развития вычислительных систем, мы можем выделить пять основных функций, которые выполняли классические операционные системы в процессе своей эволюции:
- Планирование заданий и использования процессора.
- Обеспечение программ средствами коммуникации и синхронизации.
- Управление памятью.
- Управление файловой системой.
- Управление вводом-выводом.
- Обеспечение безопасности
Каждая из приведенных функций обычно реализована в виде подсистемы, являющейся структурным компонентом ОС. В каждой конкретной операционной системе эти функции, конечно, реализовывались по-своему, в различном объеме. Они не были придуманы как составные части деятельности операционных систем изначально, а появились в процессе развития, по мере того, как вычислительные системы становились удобнее, эффективнее и безопаснее. Эволюция вычислительных систем, созданных человеком пошла по такому пути, но никто еще не доказал, что это единственно возможный путь их развития. Операционные системы существуют потому, что на настоящий момент их существование - это разумный способ использования вычислительных систем. Рассмотрение общих принципов и алгоритмов реализации их функций и будет составлять содержание большей части нашего курса.
Все темы данного раздела:
Структура вычислительной системы
Из чего состоит любая вычислительная система? В первую очередь, это то, что в англоязычных странах принято называть словом hardware, или техническое обеспечение: процессор, память, мо
Что такое ОС
Большинство пользователей имеет свой опыт эксплуатации операционных систем, но, тем не менее, затруднятся дать точное определение. Давайте кратко рассмотрим основные точки зрения.
Опера
Системные вызовы
В любой операционной системе поддерживается некоторый механизм, который позволяет пользовательским программам обращаться за услугами ядра ОС. В операционных системах наиболее известной советской вы
Прерывания
Прерывание (hardware interrupt) событие, генерируемое внешним (по отношению к процессору) устройством. Посредством аппаратных прерываний аппаратура либо информирует центральный процессор о т
Исключительные ситуации
Исключительная ситуация (exception) событие, возникающее в результате попытки выполнения программой недопустимой команды, доступа к ресурсу при отсутствии достаточных привилегий или обращени
Монолитное ядро
По сути дела, операционная система это обычная программа, поэтому было бы логичным и организовать его так же, как устроено большинство программ, то есть составить из процедур и функций. В этом случ
Слоеные системы (Layered systems)
Продолжая структуризацию, можно разбить всю вычислительную систему на ряд более мелких уровней с хорошо определенными связями между ними, так чтобы объекты уровня N могли вызывать только объекты из
Виртуальные машины
В начале лекции мы говорили о взгляде на операционную систему как на виртуальную машину, когда пользователю нет необходимости знать детали внутреннего устройства компьютера. Он работает с файлами,
Микроядерная архитектура.
Современная тенденция в разработке операционных систем это перенесение значительной части системного кода на уровень пользователя и одновременной минимизации ядра. Речь идет о подходе к построению
Смешанные системы
Все рассмотренные подходы к построению операционных систем имеют свои преимущества и недостатки. В большинстве случаев современные операционные системы используют различные комбинации этих подходов
Понятие процесса
В первой части книги мы, поясняя понятие “операционная система” и описывая способы построения операционных систем, часто применяли слова “программа” и “задание”. Мы писали: вычислительная система и
Состояния процесса
При использовании такой абстракции все, что выполняется в вычислительных системах (не только программы пользователей, но и, возможно, определенные части операционных систем), организовано как набор
Набор операций
Процесс не может сам перейти из одного состояния в другое. Изменением состояния процессов занимается операционная система, совершая операции над ними. Количество таких операций в нашей модели пока
Process Control Block и контекст процесса
Для того чтобы операционная система могла выполнять операции над процессами, каждый процесс представляется в ней некоторой структурой данных. Эта структура содержит информацию, специфическую для да
Переключение контекста
До сих пор мы рассматривали операции над процессами изолированно, независимо друг от друга. В действительности же деятельность мультипрограммной операционной системы состоит из цепочек операций, вы
Уровни планирования
В первой главе, рассматривая эволюцию компьютерных систем, мы говорили о существовании двух видов планирования в вычислительных системах: планировании заданий и планировании использования процессор
Критерии планирования и требования к алгоритмам
Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы
Параметры планирования
Для осуществления поставленных целей разумные алгоритмы планирования должны опираться на какие-либо характеристики процессов в системе, заданий в очереди на загрузку, состояния самой вычислительной
Вытесняющее и невытесняющее планирование
Процесс планирования осуществляется частью операционной системы, называемой планировщиком. Планировщик может принимать решения о выборе для исполнения нового процесса, из числа находящихся в состоя
First-Come, First-Served (FCFS)
Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First Come, First Served (первым пришел, первы
Round Robin (RR)
Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела это тот же самый алгоритм, тольк
Shortest-Job-First (SJF)
При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов готовых к исполнению. Если короткие задачи расположены в
Гарантированное планирование
При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~ 1/N част
Приоритетное планирование
Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значен
Многоуровневые очереди (Multilevel Queue)
Для систем, в которых процессы могут быть легко рассортированы на разные группы, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, н
Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из очеред
Взаимодействующие процессы
Для достижения поставленной цели различные процессы (возможно, даже принадлежащие разным пользователям) могут исполняться псевдопараллельно на одной вычислительной системе или параллельно на разных
Категории средств обмена информацией
Процессы могут взаимодействовать друг с другом только обмениваясь информацией. По объему передаваемой информации и степени возможного воздействия на поведение другого процесса все средства такого о
Логическая организация механизма передачи информации
При рассмотрении любого из средств коммуникации нас с вами будет интересовать не их физическая реализация (общая шина данных, прерывания, аппаратно разделяемая память и т. д. — мало ли чего придума
Информационная валентность процессов и средств связи
Следующий важный вопрос — это вопрос об информационной валентности связи. Слово валентность здесь использовано по аналогии с химией. Сколько процессов может быть одновременно ассоциировано с конкре
Особенности передачи информации с помощью линий связи
Как мы говорили выше, передача информации между процессами посредством линий связи является достаточно безопасной по сравнению с использованием разделяемой памяти и достаточно информативной по срав
Буферизация
Может ли линия связи сохранять информацию, переданную одним процессом, до ее получения другим процессом или помещения в промежуточный объект? Каков объем этой информации? Иными словами, речь идет о
Надежность средств связи
Одним из существенных вопросов при рассмотрении всех категорий средств связи является вопрос об их надежности. Из житейского опыта мы знаем, как тяжело расслышать собеседника по вечно трещащему тел
Нити исполнения
Рассмотренные выше аспекты логической реализации относятся к средствам связи, ориентированным на организацию взаимодействия различных процессов. Однако усилия, направленные на ускорение решения зад
Interleaving, race condition и взаимоисключения
Давайте временно отвлечемся от операционных систем, процессов и нитей исполнения и поговорим просто об некоторых “активностях”. Под активностями мы будем понимать последовательное выполнение некото
PQ: a b c d e f
Что произойдет при исполнении этих активностей псевдопараллельно, в режиме разделения времени? Активности могут расслоиться на неделимые операции с различным их чередованием, то есть может произойт
Критическая секция
Важным понятием при изучении способов синхронизации процессов является понятие критической секции (critical section) программы. Критическая се
Требования, предъявляемые к алгоритмам
Организация взаимоисключения для критических участков, конечно, позволит избежать возникновения race condition, но не является достаточной для правильной и эффективной параллельной работы кооперати
Запрет прерываний
Наиболее простым решением поставленной задачи является следующая организация пролога и эпилога:
while (some condition) {
запретить все прерывания
Переменная-замок
В качестве следующей попытки решения задачи для пользовательских процессов рассмотрим другое предложение. Возьмем некоторую переменную, доступную всем процессам, и положим ее начальное значение рав
Remainder section
}
К сожалению, внимательное изучение показывает, что такое решение, не удовлетворяет условию взаимоисключения, так как действие while(lock); lock = 1
Флаги готовности
Недостаток предыдущего алгоритма заключается в том, что процессы ничего не знают о состоянии друг друга в текущий момент времени. Давайте попробуем исправить эту ситуацию. Пусть два наши процесса и
Remainder section
}
Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому к входу в критический участок, войти в него сразу после завершения эпилога в другом проце
Алгоритм Петерсона
Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson)
Remainder section
}
При исполнении пролога критической секции процесс Pi заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу прис
Алгоритм булочной (Bakery algorithm)
Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов, который получи
Аппаратная поддержка взаимоисключений
Наличие аппаратной поддержки взаимоисключений позволяет упростить алгоритмы и повысить их эффективность точно так же, как это происходит и в других областях программирования. Мы уже обращались к об
Команда Test-and-Set (Проверить и присвоить 1)
О выполнении команды Test-and-Set, осуществляющей проверку значения логической переменной с одновременной установкой ее значения в 1, можно думать, как о выполнении функции
int Tes
Команда Swap (Обменять значения)
Выполнение команды Swap, обменивающей два значения, находящихся в памяти, можно проиллюстрировать следующей функцией
void Swap (int *a, int *b){
int tmp =
Концепция семафоров
Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две а
Решение проблемы producer-consumer с помощью семафоров
Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ограни
Мониторы
Хотя решение задачи producer-consumer с помощью семафоров выглядит достаточно элегантно, программирование с их использованием требует повышенной осторожности и внимания, чем, отчасти, напоминает пр
Сообщения
Для прямой и непрямой адресации достаточно двух примитивов, чтобы описать передачу сообщений
Реализация мониторов и передачи сообщений с помощью семафоров
Рассмотрим сначала, как реализовать мониторы с помощью семафоров. Для этого нам нужно уметь реализовывать взаимоисключения при входе в монитор и условные переменные. Возьмем семафор mute
Реализация семафоров и передачи сообщений с помощью мониторов
Нам достаточно показать, что с помощью мониторов можно реализовать семафоры, так как, из семафоров получить сообщения мы уже умеем.
Самый простой способ такой реализации выглядит следующим
Реализация семафоров и мониторов с помощью очередей сообщений
Покажем, наконец, как реализовать семафоры с помощью очередей сообщений. Для этого воспользуемся более хитрой конструкцией, введя новый синхронизирующий процесс. Этот процесс имеет счетчик и очеред
Концепция ресурса
Уже говорилось, что одна из основных функций ОС осуществлять распределение ресурсов между процессами, то есть быть менеджером ресурсов.
Как устройства, так и данные могут явл
Условия возникновения тупиков
В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков.
1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному
Алгоритм страуса
Простейший подход - игнорировать проблему тупиков. Различные люди реагируют на подобную стратегию по-разному. Математики находят ее неприемлемой и утверждают, что тупики должны быть предотвращены л
Обнаружение тупиков
Обнаружение тупика это установление факта, что возникла тупиковая ситуация и определение процессов и ресурсов, вовлеченных в эту ситуацию. Как правило, алгоритмы обнаружения применяются, когда выпо
Восстановление после тупиков
Предположим, что алгоритм обнаружения справился со своей задачей и обнаружил тупик. Что дальше. Один из путей - восстановиться и заставить систему работать дальше. В данной секции мы обсудим различ
Восстановление при помощи перераспределения ресурсов
Один из способов восстановления - принудительный вывод некоторого процесса из системы для последующего использования его ресурсов. Для определения того, какой процесс выводить из системы зачастую т
Восстановление через откат назад
Это, по всей вероятности, самый эффективный способ приостановки и возобновления.
В ряде систем реализованы средства рестарта с контрольной точки (сохранение состояния системы в како
Восстановление через ликвидацию одного из процессов
Грубый, но простейший способ устранить тупик - убить один или более процессов. Например, убить процесс, который в цикле. Тогда при удаче остальные процессы смогут выполняться. Если это не помогает,
Способы предотвращения тупиков путем тщательного распределения ресурсов.
При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций.
Система, предоставляя ресурс в распоряжение процесса, должна принят
Предотвращение тупиков и алгоритм банкира.
Можно избежать тупиковой ситуации, если рациональным образом использовать ресурсы, придерживаясь
определенных правил. Наиболее известен среди алгоритмов такого рода - алгоритм банкира, пре
Недостатки алгоритма банкира
У алгоритма банкира имеются серьезные недостатки, из-за которых разработчик может выбрать другой подход для решения проблемы тупиков:
Алгоритм банкира исходит из фиксированного колич
Нарушение условия взаимоисключения
Если в системе отсутствуют выделенные ресурсы, тупиков не будет. Тем не менее, ясно, что обобществление, например, принтера, то есть, разрешение двум процессам писать на один принтер в одно и то же
Hарушение условия ожидания дополнительных ресурсов
Хавендер в 1968 г. предложил следующую стратегию.
Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не бу
Нарушение принципа неперераспределяемости.
В соответствии со вторым принципом Хавендера можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов. Если бы это было всегда возможно, то можно было бы добиться невыполнени
Нарушение условия кругового ожидания
Осталось одно условие. Циклического ожидания можно избежать несколькими путями.
Один из них действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один
Двухфазная локализация
Хотя в общем случае рассмотренные способы предотвращения тупиков не кажутся перспективными, для отдельных специфичных приложений подобные алгоритмы широко используются. Например, во многих СУБД час
Голод (starvation)
Близкая к тупикам проблема - голод. В динамических системах постоянно происходят запросы процессов к ресурсам. Естественно, что должна быть реализована некоторая политика для принятия решения относ
Часть III. Управление памятью.
В данной части изложена идеология построения системы управления памятью в современных ОС. Центральная концепция управления памятью система виртуальной памяти обеспечивает поддержку и защиту больших
Связывание адресов.
Одна из функций управления памятью отображение информации в память. Отображение обычно понимается как преобразование адресных пространств.
Как уже упоминалось в разделе 8.1, адреса, с кото
Простейшие схемы управления памятью.
ОС начали свое существование с применения очень простых методов управления памятью. Применявшаяся техника распространялась от статического распределения памяти (каждый процесс пользователя должен п
Свопинг
Имея дело с пакетными системами можно обходиться фиксированными разделами и не использовать ничего более сложного. В системах с разделением времени возможна ситуация, когда память не в состоянии со
Проблема размещения больших программ. Понятие виртуальной памяти.
Уже давно существует проблема размещения в памяти программ, размер которых превышает размер доступной памяти. Один из вариантов ее решения организация структур с перекрытием рассмотрен в предыдущей
Архитектурные средства поддержки виртуальной памяти.
Очевидно, что невозможно создать полностью машинно-независимый компонент управления виртуальной памятью. С другой стороны, имеются существенные части программного обеспечения, связанного с управлен
Страничная память
В наиболее простом и наиболее часто используемом случае страничной виртуальной памяти виртуальная память и физическая представляются состоящими из наборов блоков или страниц одинакового размера. Ви
Сегментная и сегментно-страничная организации памяти
Существуют две другие схемы организации виртуальной памяти: сегментная и сегментно-страничная. Идеи сегментации изложены во введении к предыдущей главе. При сегментной организации виртуальный адрес
Ассоциативная память.
Поиск нужной страницы в многоуровневой таблице страниц, требующий несколько обращений к основной памяти на пути преобразования виртуального адреса к физическому занимает много времени. В ряде обсто
Иерархия памяти
Все предыдущие рассуждения справедливы и для других пар запоминающих устройств, например, для оперативной памяти и внешней памяти. В этом случае уменьшается среднее время доступа к данным, располож
Размер страницы
Дизайнеры ОС для существующих машин редко имеют возможность влиять на размер страницы. Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальны
Исключительные ситуации при работе с памятью.
Из материала предыдущей главы следует, что ключевая информация о характере отображения адреса хранится в таблице страниц. Помимо сведений о присутствии или отсутствии нужной страницы в оперативной
Стратегии управления страничной памятью
Обычно рассматривают три стратегии:
Стратегия выборки (fetch policy) - в какой момент следует переписать страницу из вторичной памяти в первичную. Выборка бывает по запросу и с упре
Алгоритмы замещения страниц
Итак, наиболее ответственным действием страничной системы является выделение страницы основной памяти для удовлетворения требования доступа к отсутствующей в основной памяти виртуальной странице. Н
FIFO алгоритм. Выталкивание первой пришедшей страницы.
Простейший алгоритм. Каждой странице присваивается временная метка. Реализуется это просто созданием очереди страниц, в конец которой страницы попадают, когда загружаются в физическую память, а из
Аномалия Belady
Интуитивно ясно, что чем больше страничных кадров имеет память, тем реже будут иметь место page fault'ы. Удивительно, но это не всегда так. Как установил Belady с коллегами, определенные последоват
Оптимальный алгоритм
Одно из последствий открытия аномалии Belady - поиск оптимального алгоритма. Этот алгоритм имеет минимальную частоту fault'ов среди всех алгоритмов. Он прост:
замещай страницу, которая не
Выталкивание дольше всего не использовавшейся страницы. LRU (The Least Recently Used) Algorithm .
Исходим из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего.
Ключевое отличие между FIFO и оптимальным алгоритмом в том, что один смо
Выталкивание редко используемой страницы. NFU (Not Frequently Used) алгоритм.
Программная реализация алгоритма, близкого к LRU.
Рассмотренные варианты LRU в принципе реализуемы, но, как уже отмечалось, они требуют специальной аппаратной поддержки, которой большинств
Другие алгоритмы
Для полноты картины можно упомянуть еще несколько алгоритмов.
Например, алгоритм Second-Chance - модификации FIFO, которая позволяет избежать потери часто используемых страниц - анализ бит
Thrashing. Свойство локальности. Модель рабочего множества.
Что делать, если в распоряжении процесса имеется недостаточное число кадров? Следует ли его приостановить с освобождением всех его кадров. Что нужно понимать под достаточным количеством кадров?
Концепция локальности
Суть концепции локальности изложена во введении. Изучая свойства локальности в пейджинговых системах, Деннинг (1968) сформулировал теорию рабочего множества программ (см. ниже).
Модель лок
Модель рабочего множества (Working Set)
В варианте чистого пейджинга процессы стартуют без необходимых страниц в памяти. Первая же машинная инструкции генерирует page fault. Другой page fault происходит при локализации глобальных перемен
Демоны пейджинга
На практике алгоритмы, обеспечивающие поддержку системы в состоянии отсутствия трешинга, реализованы при помощи фоновых процессов (их часто называют демонами или сервисами), которые периодически пр
Аппаратно-независимая модель памяти процесса.
Реализация функций операционной системы, связанных с поддержкой памяти: ведение таблиц страниц, трансляция адреса, обработка страничных ошибок, управление ассоциативной памятью и др., тесно связана
Структуры данных, используемые для описания сегментной модели
Для описания сегментной организации процесса используются структуры, содержащие дескрипторы отдельных сегментов и связанные с аппаратно-зависимой структурой (например, таблицей сегментов), данные к
Отдельные аспекты функционирования менеджера памяти.
Корректная работа менеджера памяти помимо принципиальных вопросов, связанных с выбором абстрактной модели виртуальной памяти и ее аппаратной поддержкой, обеспечивается также множеством нюансов и ме
Часть IV. Файловые системы
Все компьютерные приложения нуждаются в хранении и обновлении информации. Возможности оперативной памяти для хранения информации ограничены. Во-первых, оперативная память обычно теряет свое содержи
Имена файлов
Файлы – абстрактные объекты. Они предоставляют пользователям возможность сохранять информацию, скрывая от него детали того, как и где она хранится и то, как диски в действительности работают. Вероя
Структура файлов
Как уже говорилось, программист воспринимает файл в виде набора логических записей. Логическая запись - это наименьший элемент данных, которым может оперировать программа при обмене с внешним устро
Типы и атрибуты файлов
Важный аспект дизайна файловой системы и ОС - следует ли поддерживать и распознавать типы файлов. Если да, то это может помочь правильному функционированию ОС, например не допустить вывода на принт
Доступ к файлам
Для использования информации, хранимой в файлах, она должна быть считана в память компьютера. Есть несколько способов доступа к файлам.
Ранние ОС давали только один способ доступа – посл
Директории. Логическая структура файлового архива.
Количество файлов на компьютере может быть большим. Отдельные системы хранят тысячи файлов, занимающие сотни гигабайтом диска.
Контроль доступа к файлам
Наличие в системе многих пользователей предполагает организацию контролируемого доступа к файлам. Выполнение любой операции над файлом должно быть разрешено только в случае наличия у пользователя с
Списки прав доступа
Наиболее общий подход к защите файлов от несанкционированного использования - сделать доступ зависящим от идентификатора пользователя, то есть связать с каждым файлом или директорией список прав до
Интерфейс файловой системы.
Как уже говорилось, файловая система должна организовать эффективную работу с данными, хранящимися во внешней памяти и предоставить пользователю возможности для запоминания и выборки данных в нем.
Общая структура файловой системы
Система хранения данных на дисках может быть структурирована следующим образом (см. рис. 12.1).
Нижний уровень - оборудование. Это в первую очередь, магнитные диски с подвижными гол
Методы выделения дискового пространства
Ключевой вопрос реализации способ связывания файлов с блоками диска. В ОС используется несколько методов выделения файлу дискового пространства. Для каждого метода сведения о локализации блоков дан
Управление свободным и занятым дисковым пространством.
В современных ОС используется несколько способов учета используемого места на диске. Рассмотрим наиболее распространенные.
Учет при помощи организации битового вектора.
Час
Размер блока
Размер логического блока играет важную роль. В некоторых системах (Unix) он может быть задан при форматировании. Небольшой размер блока будет приводить к тому, что каждый файл будет содержать много
Структура файловой системы на диске
Рассмотрение методов работы с дисковым пространством дает общее представление о совокупности служебных данных, необходимых для описания файловой системы. Структуры данных типовой файловой системы,
Реализация директорий
Как уже говорилось, директория или каталог это файл, имеющий определенный тип и хранящий список входящих в него файлов или каталогов. Основная задача файлов-директорий поддержка иерархической древо
Поиск в директории
Итак, директория - есть файл, имеющий специальный формат, состоящий из записей фиксированной длины, где каждая запись соответствует одному из обычных файлов или директорий, входящих в состав данной
Монтирование файловых систем.
Как файл должен быть открыт перед использованием, так и файловая система, хранящаяся на разделе диска, должна быть смонтирована, чтобы стать доступной процессам системы.
Функция mount (мон
Кооперация процессов при работе с файлами.
Когда различные пользователи работают вместе над проектом, они часто нуждаются в разделении файлов.
Разделяемый файл является разделяемым ресурсом. Как и в случае любого совместно использу
Целостность файловой системы.
Важный аспект надежной работы файловой системы контроль ее целостности. В результате файловых операций блоки диска могут считываться в память, модифицироваться и затем записываться на диск. Причем,
Управление плохими блоками.
Наличие плохих блоков на диске обычное дело. Под плохими блоками обычно понимают блоки диска, для которых вычисленная контрольная сумма считываемых данных не совпадает с хранимой контрольной суммой
Производительность файловой системы
Наиболее типичная техника повышения скорости работы с диском кэширование. Обращение к диску обычно в 100000 раз медленнее, чем к памяти. (Обращение к памяти - несколько сотен наносекунд, а ч
Системные вызовы, работающие с символическим именем файла.
Системные вызовы, связывающие pathname с дескриптором файла
Это функции создания и открытия файла. Например, в ОС Unix
fd = creat(pathname,modes);
fd = open(pathna
Системные вызовы, работающие с файловым дескриптором
Открытый файл может использоваться для чтения и записи последовательностей байтов. Для этого поддерживаются два системных вызова read и write, работающие с файловым дескриптором (ил
Современные архитектуры файловых систем
Современные ОС предоставляют пользователю возможность работать сразу с несколькими файловыми системами (Linux работает с Ext2fs, FAT и др.). Файловая система в традиционном понимании становится час
Физические принципы организации ввода-вывода.
Существует много разнообразных устройств, которые могут взаимодействовать с процессором и памятью: таймер, жесткие диски, клавиатура, дисплеи, мышь, модемы и т. д., вплоть до устройств отображения
Структура контроллера устройства.
Контроллеры устройств ввода-вывода весьма различны как по своему внутреннему строению, так и по исполнению (от одной микросхемы до специализированной вычислительной системы со своим процессором, па
Опрос устройств и прерывания. Исключительные ситуации и системные вызовы
Построив модель контроллера и, представляя себе, что скрывается за словами “прочитать информацию из порта” и “записать информацию в порт”, мы готовы к рассмотрению процесса взаимодействия устройств
Логические принципы организации ввода-вывода.
Рассмотренные в предыдущем разделе физические механизмы взаимодействия устройств ввода-вывода с вычислительной системой позволяют понять, почему разнообразные внешние устройства легко могут быть до
Структура системы ввода-вывода.
Если поручить неподготовленному пользователю сконструировать систему ввода-вывода, способную работать со всем множеством внешних устройств, то, скорее всего, он окажется в ситуации, в которой наход
Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами.
Как и система видов Линнея, система типов устройств является далеко не полной и не строго выдержанной. Устройства обычно принято разделять по преобладающему типу интерфейса на следующие типы:
Функции базовой подсистемы ввода-вывода.
Базовая подсистема ввода-вывода служит посредником между процессами вычислительной системы и набором драйверов. Системные вызовы для выполнения операций ввода-вывода трансформируются ею в вызовы фу
Блокирующиеся, не блокирующиеся и асинхронные системные вызовы.
Все системные вызовы, связанные с осуществлением операций ввода-вывода, можно разбить на три группы по способам реализации взаимодействия процесса и устройства ввода-вывода.
§ К первой, на
Буферизация и кэширование.
Под буфером обычно понимается некоторая область памяти для запоминания информации при обмене данных между двумя устройствами, двумя процессами или процессом и устройством. Обмен информацией
Spooling и захват устройств.
О понятии spooling мы с вами говорили в первой главе нашего курса, как о механизме, впервые позволившем совместить реальные операции ввода-вывода одного задания с выполнением другого задания. Тепер
Обработка прерываний и ошибок.
Если при работе с внешним устройством вычислительная система не пользуется методом опроса его состояния, а использует механизм прерываний, то при возникновении прерывания, как мы уже говорили раньш
Планирование запросов.
При использовании не блокирующегося системного вызова может оказаться, что требуемое устройство уже занято выполнением некоторых операций. В этом случае не блокирующийся вызов может немедленно верн
Строение жесткого диска и параметры планирования.
Современный жесткий магнитный диск представляет собой набор круглых пластин, находящихся на одной оси, и покрытых с одной или двух сторон специальным магнитным слоем (см. рисунок 13.2.). Около кажд
Алгоритм First Come First Served (FCFS)
Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслужи
Алгоритм Short Seek Time First (SSTF).
Как мы видели, достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко отстоящих. Алгоритм Short Seek Time Fi
Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)
В простейшем из алгоритмов сканирования – SCAN – головки постоянно перемещаются от одного края диска до его другого края, по ходу дела обслуживая все встречающиеся запросы. По достижении другого кр
Резюме.
Функционирование любой вычислительной системы обычно сводится к выполнению двух видов работы: обработке информации и операций по осуществлению ее ввода-вывода. С точки зрения операционной системы “
Политика безопасности
Основополагающие документы содержат определения многих ключевых понятий связанных с информационной безопасностью. Так, например, важность и сложность проблемы обеспечения безопасности требует выраб
Криптография, как одна из базовых технологий безопасности ОС.
Многие службы информационной безопасности, такие как контроль входа в систему, разграничение доступа к ресурсам, обеспечение безопасного хранения данных и ряд других опираются на использование крип
Идентификация и аутентификация
Обычно каждый пользователь в системе имеет уникальный идентификатор. Идентфикаторы пользователей применяются с теми же целями, что и идентификаторы любых других объектов, файлов, процессов. Иден
Пароли, уязвимость паролей
Наиболее простой подход к аутентификации - использование пользовательского пароля.
Когда пользователь идентифицирует себя при помощи уникального идентификатора или имени, у него запрашивае
Шифрование пароля
Для хранения секретного списка паролей на диске многие ОС используют криптографию. Система использует одностороннюю функцию, которую чрезвычайно трудно (дизайнеры надеются, что невозможно) инвертир
Авторизация. Разграничение доступа к объектам ОС
После того, как легальный пользователь вошел в систему необходимо осуществить авторизацию (authorization)- предоставление субъекту прав на доступ к объекту. Средства авторизации контролируют
Домены безопасности
Чтобы развить эту схему мы введем концепцию домена безопасности (protection domain). Процесс оперирует с доменом безопасности, который специфицирует ресурсы, к которым процесс может иметь доступ. К
Список прав доступа. Access control list.
Каждая колонка в матрице может быть реализована как список доступа для одного объекта. Очевидно, что пустые клетки могут не учитываться. В результате для каждого объекта имеем список упорядоченных
Capability list
Если матрицу доступа хранить по строкам, то есть каждый субъект хранит список объектов и для каждого объекта список допустимых операций, то такой способ хранения называется capability list.
Недопустимость повторного использование объектов
Контроль за повторным использованием объекта предназначен для предотвращения попыток незаконного получения конфиденциальной информации, остатки которой могли сохраниться в некоторых объектах, ранее
Аудит, учет использования системы защиты
Аудит - заключается в регистрации специальных данных о различных типах событий, происходящих в системе и так или иначе влияющих на состояние безопасности компьютерной системы. К числу таких событий
Анализ некоторых популярных ОС с точки зрения их защищенности.
Итак, ОС должна способствовать реализации мер безопасности или прямо поддерживать их. Примеры подобных решений в рамках аппаратуры и операционной системы - разделение команд по уровням привилегиров
NetWare, IntranetWare
Замечания об отсутствии изоляции модулей друг от друга справедливо и относительно рабочей станции NetWare. Однако NetWare - сетевая ОС, поэтому к ней возможно применение и иных критериев. Это на да
Новости и инфо для студентов