Экзаменационные вопросы по курсу Операционные системы

Экзаменационные вопросы по курсу
«Операционные системы»

 

1. Общая характеристика понятий «сложность», «система», «модель»

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

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

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

- точка, линия в геометрии

- информация в информатике

- тело в механике

Строго формулируются аксиомы (правила, на основе которых формируются новые структуры рассматриваемой предметной области).

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

Несмотря на раличие предметных областей, они обладают рядом общих черт:

1. Сложность

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

3. Наличие динамики (деятельность, труд (для социальных объектов), функционирование и работа (для технических систем)).

Примечание: категория сложности может относится и к деятельности (функционированию).

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

По-видимому, все суждения при этом можно разделить на две группы:

- судения лиц, находящихся «внутри» объекта

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

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

Такой подход есть, называется системным подходом.

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

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

Абстрагирование – выделение существенных особенностей объета, отличающих его от всех других.

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

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

Модель – некоторая система, исследование которой служит средством для получения информации о другой системе. Это описание систем (математическое, вербальное и т. д.) отображающее определенную группу ее свойств.

Саму проблему сложности удобно обсуждать в рамках системного подхода.

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

Существует много определений системы:

- система – комплекс элементов, находящихся во взаимодействии

- система – это множество объектов вместе с отношениями этих объектов

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

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

 

Исследование объекта как системы, признаки сложности системы

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

Факторные подсистемы сложных систем, принципы системного подхода.

1) решающую, которая принимает глобальные решения во взаимодействии с внешней средой и распределяет локальные задания между всеми другими… 2) информационную, которая обеспечивает сбор, переработку и передачу… 3) управляющую для реализации глобальных решений

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

Операционные системы возникли лишь на определенном этапе развития ЭВМ.

Эволюция ОС тесно переплетена с эволюцией аппаратного обеспечения вычислительных систем.

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

Два главных «источника» развития вычислительных систем, и, как следствие ОС:

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

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

Направление развития: от эффективности работы процессора к эффективности работы программиста (изменились цены). Поскольку критерии эффективности разные, то и системы будут разные.

Разрешение технических «противоречий»

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

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

· многообразие периферийных устройств преодолевается переходом от работы с их физическими параметрами (они перекладываются на драйвера самих устройств) к работе с логическими параметрами (вводится файловая система).

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

Согласно классической фон-неймановской схеме, преобладавшей в ЭВМ 1-2 поколениях, центром архитектуры ЭВМ является процессор.

Устройство вывода

АЛУ - арифметико-логическое

устройство

 

 

Устройства вывода

УУ – управляющее устройство

ПЗУ – постоянно

запоминающее устройство

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

Блок управления отвечает за вызов команд из памяти и определение их типа.

АЛУ выполняет арифметические операции (сложение) и логические операции (логическое и).

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

Основные принципы организации ЭВМ по фон-Нейману:

1. Принцип двоичного кодирования. Электронные машины должны работать не в десятичной, а в двоичной системе счисления.

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

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

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

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

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

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

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

· структурную схему ЭВМ;

· средства и способы доступа к элементам структурной схемы;

· организацию и разрядность интерфейсов ЭВМ;

· набор и доступность регистров;

· организацию и способы адресации памяти;

· способы представления и форматы данных ЭВМ;

· набор машинных команд ЭВМ;

· форматы машинных команд;

· обработку нештатных ситуаций (прерываний)

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

Все современные ЭВМ обладают некоторыми общими и индивидуальными свойствами архитектуры.

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

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

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

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

 

Архитектура процессора с точки зрения программиста

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

Основные этапы эволюции вычислительных систем

1. Первый период (1945-1955). Ламповые машины. Операционных систем нет. 2. Второй период (1955-начало 60-х). Компьютеры на основе транзисторов.… 3. Третий период (начало 60-х-1980). Компьютеры на основе интегральных микросхем. Первые многозадачные ОС,

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

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

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

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

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

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

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

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

Особенности ОС с режимом разделения времени:

1. Хранение заданий в памяти или на диске

2. Откачка и подкачка (swapping). Загрузка заданий с диска в память и их выгрузка из памяти на диск.

3. Поддержка диалогового взаимодействия между пользователем и системой

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

Режим разделения времени, наряду с пакетным режимом, был основным в ОС 1960-х-1970-х годах (в СССР в 1980-х).

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

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

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

ОС в иерархической структуре программного и аппаратного обеспечения компьютера (внешняя среда ОС)

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

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

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

Возможности развития ОС, требования к ОС, средства аппаратной поддержки ОС

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

Классификация операционных систем, две роли ОС, операционная среда, структурные компоненты ОС

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

 

1. По назначению (универсальные, специализированные – управление производством, обучение)

2. По способу загрузки (загружаемые, постоянно находящиеся в памяти)

3. По особенностям алгоритмов управления ресурсами

3.1 Многозадачность: однозадачные (MSDOS), невытесняющая многозадачность (Windows 3и выше, New Ware), вытесняющая многозадачность (Windows NT, Unix)

3.2 Многопользовательский режим: отсутствие (Windows 3, MSDOS), имеется (Windows NT, Unix)

3.3 Многопроцессорная обработка: отсутствие, ассиметричные ОС, симметричные ОС

4. По базовой технологии (Юникс-подобные, Виндовс-подобные)

5. По типу лицензии (проприетарная или открытая)

6. По состоянию развития (устаревшая DOS или современная Linux, Windows)

7. Область использования и форма эксплуатации: пакетная обработка (OS/360); разделение времени; реальное время (VX Works, QNX)

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

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

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

Цель таких библиотек – сделать системный вызов похожим на обычный вызов подпрограммы.

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

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

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

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

Вторая роль. Менеджер ресурсов

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

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

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

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

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

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

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

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

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

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

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

1и 2 пункты представляют по сути функционал управления процессами.

Основные принципы разработки архитектуры ОС

Именно архитектура ОС должна обеспечить: ¾ расширяемость ОС ¾ переносимость ОС

Монолитная архитектура ОС

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

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

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

Микроядерная архитектура ОС, смешанные системы. Классификация ядер ОС.

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

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

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

1. взаимодействие между программами

2. планирование использования процессора

3. первичную обработку прерывания

4. операции ввода-вывода

5. базовое управление памятью

 

 

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

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

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

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

Классификация ядер ОС:

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

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

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

4. Монолитное ядро предоставляет широкий набор абстракций оборудования. Монолитное ядро более производительно, чем микроядро, поскольку работает как один большой процессор.

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

Модель ОС клиент-сервер

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

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

Режим ядра. Достоинства: единообразный интерфейс.

Понятие процесса, состояния процесса, модель процесса

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

Контекст процесса и блок управления процессами

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

Эта структура содержит информацию (контекст процесса), специфическую для данного процесса:

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

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

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

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

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

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

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

Но в любом случае все эти структуры доступны ОС для осуществления действий над процессами.

Далее полагаем, что контекст состоит из одной структуры данных. Она, как правило, называется блоком управления процессом PSB (Process Control Block).

Блок управления процессом является моделью процесса для ОС.

Любая операция, производимая ОС над процессом, вызывает определенные изменения в PCB.

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

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

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

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

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

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

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

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

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

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

Операции над процессами и связанные с ними понятия

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

Количество таких операций совпадает с количеством стрелок, представленных на модели состояний процесса.

Операции удобно объединить в три пары:

· рождение – завершение процесса

· приостановка процесса (перевод из состояния исполнение в состояние готовность) – запуск процесса (перевод из состояния готовность в состояние исполнение)

· блокирование (перевод из состояния исполнение в состояние ожидание) – разблокирование (перевод из состояния ожидание в состояние готовность)

Далее будет рассмотрена еще одна операция, не имеющая парной: изменение приоритета процесса.

Операции создание и завершение процесса являются одноразовыми (т.к. применяются не более одного раза).

Все остальные операции, связанные с изменением состояния процессов, являются многоразовыми.

Одноразовые операции

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

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

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

 

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

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

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

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

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

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

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

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

· во втором случае процесс-ребенок загружается новой программой из какого-либо файла

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

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

После того, как процесс наделен содержанием, в PCB дописывается оставшаяся информация, и состояние нового процесса меняется на готовность.

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

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

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

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

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

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

Многоразовые операции:

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

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

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

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

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

Все данные, необходимые для восстановления контекста, извлекаются из PCB процесса, над которым совершается операция.

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

На этом деятельность железа (hard ware) по обработке прерывания завершается.

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

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

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

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

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

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

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

Процессы могут находиться в 5 основных состояниях: рождение, готовность, исполнение, ожидание, завершение. Из состояния в состояние процесс переводится ОС в результате выполнения над ним операций. ОС может выполнять над процессами следующие операции:

· создание и завершение процесса

· приостановка и запуск процесса

· блокирование и разблокирование процесса

· изменение приоритета процесса

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

 

Планирование процессов. Уровни планирования

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

Критерии планирования и требования к алгоритмам

К числу таких целей можно отнести следующие: ¾ справедливость (не должно быть ситуации, когда один процесс… ¾ эффективность (идеально процессор должен быть занят на 100%, реально – 40-90%)

Параметры планирования

К статическим параметрам ВС можно отнести предельные значения ее ресурсов: · размер ОЗУ · максимальное количество памяти на диске для осуществления свопинга

Вытесняющее и невытесняющее планирование

1. когда процесс переводится из состояния исполнение в состояние закончил исполнение 2. когда процесс переводится из состояния исполнение в состояние ожидание 3. когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера) …

Алгоритм планирования процессов First-Come, First-Served (FCFS)

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

Алгоритм планирования процессов Round Robin (RR)

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

Алгоритм планирования процессов Shortest-Job-First (невытесняющий)

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

Алгоритм планирования процессов Shortest-Job-First (вытесняющий)

Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося, то исполняющийся процесс вытесняется новым. Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд…

Приоритетное планирование процессов (невытесняющий и вытесняющий вариант)

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

Алгоритм SJF представляет собой частный случай приоритетного планирования.

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

Процессы с одинаковыми приоритетами планируются в порядке FCFS.

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

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

К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д.

Алгоритм SJF использует внутренние параметры.

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

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

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

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

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

Давайте рассмотрим примеры использования различных режимов приоритетного планирования

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

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

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

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

Первым для выполнения в момент времени t = 0 выбирается процесс p3, как обладающий наивысшим приоритетом.

После его завершения в момент времени t = 5 в очереди процессов, готовых к исполнению, окажутся два процесса p0 и p1.

Больший приоритет из них у процесса p1, он и начнет выполняться (см. табл.). Затем в момент времени t = 8 для исполнения будет избран процесс p2, и лишь потом – процесс p0.

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

Первым, как и в предыдущем случае, начнет исполняться процесс p3, а по его окончании – процесс p1. Однако в момент времени t = 6 он будет вытеснен процессом p2 и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше, будет исполняться процесс p0.

В рассмотренном выше примере приоритеты процессов с течением времени не изменялись. Такие приоритеты принято называть статическими.

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

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

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

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

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

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

Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования.

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

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

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

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

Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся).

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

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

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

Многоуровневые очереди в планировании процессов (без обратной связи и с обратной связью)

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

Потоки. Мультипрограммирование на уровне потоков

В настоящее время в большинстве операционных систем определены два типа единиц работы. Более крупная единица работы – процесс. С помощью процессов удается обеспечить псевдопараллельное (при однопроцессорной вычислительной системе) или…

Организация взаимодействия процессов. Основные понятия

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

Это означает, что процессы (в идеале) не должны ничего знать даже о существовании друг друга.

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

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

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

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

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

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

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

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

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

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

· обмен данными между процессами.

Набор средств, предназначенных для взаимодействия процессов, часто обозначают аббревиатурой IPC (InterProcess Communication).

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

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

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

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

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

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

2. Процессы косвенно осведомлены о наличии друг друга (например, процессы одного задания).
Эти процессы не обязательно должны быть осведомлены о наличии друг друга с точностью до идентификатора процесса, однако они разделяют доступ к некоторому объекту, например буферу ввода-вывода, к файлу или БД.

Такие процессы демонстрируют сотрудничество при разделении общего объекта

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

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

Общие характеристики связи между процессами

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

Конкуренция процессов в борьбе за ресурсы. Основные понятия и проблемы

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

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

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

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

Между конкурирующими процессами не происходит никакого обмена информацией.

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

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

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

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

О таком ресурсе будем говорить как о критическом ресурсе, а о части программы, которая его использует, - как о критическом разделе (секции) (critical section) программы.

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

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

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

Очень удобно моделировать условия возникновения тупиков, используя направленные графы. Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики. Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется

Рассмотрим, например, два процесса - Р1 и Р2 и два ресурса - R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам R1 и R2.

Тогда возможно возникновение следующей ситуации: ОС выделяет первоначально ресурс R1 процессу Р2, а ресурс R2 - процессу Р1.

 

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

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

Существует еще одна проблема у конкурирующих процессов - голодание.

Предположим, что имеются 3 процесса (P1, P2, РЗ), каждому из которых периодически требуется доступ к ресурсам R.

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

Пусть ОС предоставила доступ к ресурсу процессу РЗ. Пока он работает с ресурсом, доступ к ресурсу вновь требуется процессу Р1. В результате по освобождении ресурса R процессом РЗ может оказаться, что ОС вновь предоставит доступ к ресурсу процессу Р1. Тем временем процессу РЗ вновь требуется доступ к ресурсу R. Таким образом, теоретически возможна ситуация, в которой процесс Р2 никогда не получит доступа к требуемому ему ресурсу, несмотря на то что никакой взаимной блокировки в данном случае нет.

Синхронизация процессов и потоков. Основные понятия и проблемы

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

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

• обмене данными между потоками,

• разделении данных,

• при доступе к процессору

• при доступе устройствам ввода-вывода

• Во многих операционных системах эти средства называются средствами межпроцессного взаимодействия — Inter Process Communications (IPC), что отражает историческую первичность понятия «процесс» по отношению к понятию «поток».

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

• Выполнение потока в мультипрограммной среде всегда имеет асинхронный характер.

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

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

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

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

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

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

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

Рис. Возникновение гонок при доступе к разделяемым данным

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

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

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

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

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

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

Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ.

Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени

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

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

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

После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата.

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

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

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

Или, напротив, все исправления были успешно внесены (рис. в).

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

Поэтому отладка взаимодействующих потоков является сложной задачей.

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

Рис. Влияние относительных скоростей потоков на результат решения задачи

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

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

Организация физической памяти компьютера

Если операционная система и аппаратное обеспечение могут эффективно работать с пользовательскими программами и данными, представленными модулями, то… Модули могут быть созданы и скомпилированы независимо друг от друга, при этом… Разные модули могут получать разные степени защиты (только чтение, только ис­полнение) за счет весьма умеренных…

Адресные пространства и отображения, виртуальное адресное пространство

Функции ОС по управлению памятью

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

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

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

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

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

Распределение памяти фиксированными разделами

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

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

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

2. Использование ОП крайне неэффективно. Любая программа, независимо от ее раз­мера, занимает раздел целиком. При этом могут оставаться неиспользованные уча­стки памяти большого размера. Этот феномен появления неиспользованной памяти называется внутренней фрагментацией (internal fragmentation).

 

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

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

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

 

 

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

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

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

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

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

Примером успешной операционной системы с использованием данной технологии может служить операционная система IBM OS/MFT и ЕС ЭВМ ОС MFT (многопрог­раммная операционная система с фиксированным числом задач - Multiprogramming With a Fixed number of Tasks) [26].

Распределение памяти динамическими разделами

Для преодоления сложностей, связанных с фиксированным распределением был раз­работан альтернативный подход, известный как динамическое распределение. В свое время этот подход был использован фирмой IBM в операционной системе для мэйнфреймов в OS/MVT (мультипрограммирование с переменным числом задач - Multiprogramming With a Variable number of Tasks). Позже этот же подход к распределению памяти был использован в ОС ЕС ЭВМ [24,26].

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

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

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

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

 

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

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

· Коррекция таблиц свободных и занятых областей.

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

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

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

 

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

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

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

Методы структуризации виртуального адресного пространства

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

Страничная организация виртуальной памяти

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

Сегментация виртуальной памяти

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

Программная поддержка механизмов виртуальной памяти

Внешние устройства, выполняющие операции ввода-вывода, можно разделить на три группы: · устройства, работающие с пользователем. Используются для связи пользователя… · устройства, работающие с компьютером. Используются для связи с элект­ронным оборудованием. К ним можно отнести…

Назначение и задачи подсистемы ввода-вывода

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

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

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

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

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

Драйверы устройств ввода вывода

· входит в состав ядра ОС, работая в привилегированном режиме; · непосредственно управляет внешним устройством, взаимодействуя с его… · обрабатывает прерывания от контроллера устройства;

Многослойная модель подсистемы ввода-вывода

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

Задачи файловой системы. Основные понятия

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

Поле – основной неделимый элемент данных. Характеризуется длиной и типом данных. Длина может быть фиксирована или переменна внутри файла. Из полей формируется структура, которая называется записью.

Запись представляет набор связанных полей. Запись воспринимается прикладной программой как единое целое; при обработке записи возможно изменение тех или иных ее полей.

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

Файловая система является частью ОС системы и включает:

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

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

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

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

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

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

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

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

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

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

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

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

 

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

  На нижнем уровне драйверы устройств непосредственно связаны с периферийными устройствами или их контроллерами, либо…

Логическая организация файлов

Метод доступа Наиболее близкий пользователю уровень файловой системы. Он обеспечивает… Различные методы доступа отражают различные структуры файлов и различные пути доступа и обработки данных.

Каталоговые системы

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

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

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

Адресация блоков данных диска

способ c – h – s :

с – номер цилиндра,

h – номер головки,

S – номер сектора

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

Физическая организация и адресация файла

· скорость доступа к данным; · объем адресной информации файла; · степень фрагментированности дискового пространства;

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

· загрузочные сектора главного и дополнительных разделов; · загрузочные сектора логических дисков (разделов); · корневой каталог;

Основные этапы развития операционных систем корпорации Microsoft.

В 1981 году корпорация IBM создала персональный компьютер IBM PC, основанный на процессоре Intel 8088. Персональный компьютер был оснащен… Эта ОС поставлялась крохотной начинающей фирмой Microsoft, известной как… Два года спустя была выпущена более мощная ОС MS DOS 2.0, состоящая из 24 Кбайт резидентного кода. Она содержала…

Общая характеристика структуры ОС Windows 2000,основные изменения в ней по сравнению с ОС Windows NT.

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

Основные функции, выполняемые уровнем HAL ОС Windows 2000.

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

Общая характеристика исполняющей подсистемы ОС Windows 2000.

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

Общая характеристика объектов ОС Windows 2000 м возможностей их использования

Основные особенности файловой системы NTFS 5 по сравнению с предыдущими файловыми системами Microsoft.

Размер кластера фиксирован для каждого тома и варьируется в пределах от 512 байт до 64 Кбайт в зависимости от размера тома (чаще всего 4 Кбайт). Обращение к блокам осуществляется по их смещению от начала тома, для которого… Все файлы на томе NTFS идентифицируются номером файла, который определяется позицией файла в MFT (Master File Table) -…

Средства достижения безопасности в ОС Windows 2000

Windows 2000 унаследовала от NT множество свойств безопасности, включая следующие: 1. Безопасная регистрация в системе с мерами предосторожности… 2. Дискреционное управление доступом. 3. Управление привилегированным доступом.

Основные принципы работы шифрующей файловой системы в ОС Windows 2000

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

Набор API для Win 32.

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