Программный интерфейс прикладных программ с ОС

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

14. Преобразование адресов в вс

Схема преобразования:

Имя →α программный адрес

→β исполнительный адрес

→γ значение, хранящееся по адресу

Функция α - это система программирования. Функция γ – выполняется памятью.

- абсолютный адрес – действительное расположение ячейки основной памяти

- относительный адрес – адрес определяется относительно известной точки (начала программы)

Программный адрес зависит от системы адресации машины.

Существует статическое и динамическое связывание.

Логическое адресное пространство - совокупность программных адресов, которые занимают программы и данные задачи.

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

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

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

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

Достаточно загрузить начальный адрес загрузочного модуля в регистр (N→b), тогда нужный адрес вычисляется добавлением смещения (b)+D.

Программный адрес состоит из (b) и D.

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

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

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

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

16. Загрузочный модуль оверлейной структуры.

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

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

Схема иерархии программы (какие функции из каких вызываются). А – все время в ОП:

ABD

ABE

AC

ACF

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

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

Механизм перекрытия не во всех ОС – в OS360 есть, а в Unix нет. Нужно спланировать структуру оверлейного модуля – в какой сегмент какой кусок писать

17. Загрузочный модуль динамической структуры

Загрузочный модуль динамической структуры использовался в пакетных ОС (OS360, OS370).

Идея:

Пусть A, B, C – модули

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

LOAD, DELETE, LINK, XCTL – команды ядра системы управления программами, представляют собой систему управления внутри области программы.

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

LINK – загружает модуль в ОП, выполняет, получает результат и удаляет

DELETE – вычитает 1 (если не 0) из счетчика загруженных программ – делает память свободной

XCTL – как LINK, Но загрузка идет на место модуля, который ее вызвал.

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

Пример

A: START C: START

1. LOAD B 3. LOAD B

2. LINK C CALL B

4. CALL B DELETE B

5. DELETE B

END

1. Активна программа А

PRB – program required block - блок запросов программы, содержит множество информационных полей.

LOAD B – загружает программу B и возвращает адрес точки входа, к счетчику загруженных программ добавляется 1.

2. B не активна, но известна точка входа

LINK C – загружает C и ему передается управление.

3. Активна программа C.

L OAD B добавляет 1 к счетчику.

DELETE – вычитает из счетчика 1, если счетчик = 0, то память освобождается, B выгружается.

После выполнения модуль C выгружается.

4. = 2.

5. = 1 (После выполнения DELETE B счетчик станет равен 0).

После окончания работы все блоки будут выгружены. Блок строится в области системных очередей SQA (System Queue Area).

18. Однократно используемые, повторно используемые и повторно входимые программные модули

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

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

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

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

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

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

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

19. Сопрограммы

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

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

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

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

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

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

• Командный процессор – обрабатывает и выполняет команды, с помощью которых пользователь управляет работой ВС

• Управление заданиями – используется только в пакетных системах и состоит в планировании заданий различных пользователей

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

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

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

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

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

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

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

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

21. Монолитная и микроядерная архитектуры ос.

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

Типы архитектур:

1. Монолитное ядро

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

• Достоинства: Скорость работы, упрощённая разработка модулей^[1].

• Недостатки: Поскольку всё ядро работает в одном адресном пространстве, сбой в одном из компонентов может нарушить работоспособность всей системы.

Примеры: Традиционные ядра UNIX (такие как BSD), Linux; ядро MS-DOS, ядро KolibriOS.

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

2. Микроядро

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

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

• Недостатки: Передача данных между процессами требует накладных расходов.

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

• Сервисные процессы (в принятой в семействе UNIX терминологии — «демоны») активно используются в самых различных ОС для задач типа запуска программ по расписанию (UNIX и Windows NT), ведения журналов событий (UNIX и Windows NT), централизованной проверки паролей и хранения пароля текущего интерактивного пользователя в специально ограниченной области памяти (Windows NT). Тем не менее, не следует считать ОС микроядерными только из-за использований такой архитектуры.

Примеры: Symbian OS, Windows CE.

22. Оценка времени простоя цп в мультипрограммном режиме

Оценка загруженности ЦП в зависимости от числа задач

Нужны периферийные процессоры, которые занимаются вводом-выводом

N – процессов

S_i – состояние системы, i процессов находятся в ожидании I/0

Можем выделить состояние S₀ – нет процессов, которые ожидают I/0

P_i – вероятность пребывания системы в состоянии S_i

λdt – вероятность блокирования в результате запроса I/O

1/λ – средний интервал м/у запросами I/O

μdt – вероятность завершения I/O

ω= λ/( λ+μ) – ожидание I/O в системе без мультипрограммирования

Условие стационарности.

S_iS_i+1 = S_i+1  S_i

p_i,i+1 – вероятность перехода S_iS_i+1

p_i,i+1*P_i=P_i+1*p_i+1,i

λdt P₀= μdt P₁

λdt P₁= μdt P₂

……….

λdt P_n-1= μdt P_n

∑P_i=1

P₁= λdt/ μdt * P₀

P₂=(λ/μ)²/2 P₀

P_n=(λ/μ)ⁿ/n! P₀

P₀+∑P_i=1

P₀=1-∑P_i=1

P₀=1-∑(λ/μ)ⁱ/i! P₀

P₀ = 1/(1+∑(λ/μ)ⁱ/i! )

P­_n – оценивает время простоя

P­_n= (λ/μ)ⁿ/(n! ∑(λ/μ)ⁱ/i!)

λ/μ= ω/(1- ω)

P­_n= (ω/(1- ω))ⁿ/(n! ∑( ω/(1- ω))ⁱ/i!)

23. Управление памятью, распределенной статическими разделами.

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

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

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

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

Реализация функций

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

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

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

Аппаратные средства

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

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

Защита с помощью регистров осуществляется следующим образом.

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

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

Физическая память выделяется блоками. Так, в IВМ360 размер блока равнялся 2 Кбайт, с каждым блоком памяти связывался четырехразрядный регистр, в который записывался код защиты. Код защиты помещался в слово состояние программы (PSW). При обращении к памяти сравнивались значения, кода защиты, и при несовпадении вырабатывалось прерывание по защите памяти. Таким образом задаче при ее создании присваивался код защиты (1 - 15). Код защиты О имели задачи ОС.

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

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

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

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

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

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

24. Управление памятью, распределенной динамическими разделами.

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

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

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

Реализация функций

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

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

SV

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

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

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

Аппаратные средства

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

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

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

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

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

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

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

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

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

25. Способы уменьшения фрагментации оп.

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

Различают внешнюю и внутреннюю фрагментации.

Внешняя фрагментация создается в ОП между задачами.

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

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

Для борьбы с внешней фрагментацией разрабатывались специальные методы управления ОП:

1. Распределение памяти перемещаемыми разделами.

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

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

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

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

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

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

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

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

26. Управление страничной памятью по запросам.

Физическая память - двухуровневая, делится на физические страницы. Адресное пространство задачи также делится на логические страницы. Размеры логической и физической страниц совпадают. Реально использовались размеры страниц от 256 байт до 4 Кбайт.

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

Таким образом, при вычислении действительного адреса может возникнуть обмен между ОП и внешней памятью. Поэтому организации внешней памяти для свопинга страниц должно уделяться определенное внимание. В первых ОС с виртуальной страничной памятью использовались специально разработанные внешние накопители информации, но с появлением быстродействующих и надежных жестких дисков стали использовать стандартные устройства компьютера. Однако в различных ОС организация области свопинга различна. Так в ОС Unix, Linux во время установки ОС на компьютер выделяется специальный раздел на диске, а в ОС MS WINDOWS используется системный файл pagefile.sys, который располагается на диске С. Конечно его можно переопределить на другой диск, а также задать минимальный и максимальный размеры, которые должны быть кратны 8. Под минимальный размер система выделит определенное количество смежных блоков памяти, а в случае необходимости будет выделять дополнительные блоки до максимального размера. Разумеется, в этом случае файл будет фрагментирован, что увеличивает время доступа к внешним страницам. Чтобы смягчить этот недостаток можно создать раздел в виде логического диска размером 1.5-2 Гбайта с именем отличным от "C". Диск С многие программы используют по умолчанию. А можно просто изменить минимальный размер файла, сделав его равным максимальному.

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

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

Учет состояния памяти.

Необходимы следующие системные таблицы:

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

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

• физическая страница занята,

• физическая страница находится в транзитном состоянии.

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

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

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

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

2) Таблица страниц задачи - одна на задачу. Таким образом, сколько создано в системе задач, столько будет создано и таблиц страниц.

Каждая запись в таблице страниц задачи содержит:

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

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

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

4) Таблица внешних страниц задач! - одна на задачу. Содержит адреса внешних страниц во внешней памяти.

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

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

Выделение памяти.

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

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

Освобождение памяти.

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

27. Методы замещения страниц fifo, lru.

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

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

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

Алгоритм FIFO (first in – first out): удаляется страница, которая дольше всего находится в ОП.

Алгоритм FIFO не учитывает использование страницы. На рис. приведена иллюстрация работы алгоритма на модели при М=3. Параметры модели и оценка производительности для данного случая: |Р|=12, F=9, f=9/12.

Этот алгоритм обладает и принципиальным недостатком - аномалией страниц. При увеличении объема ОП естественно ожидать уменьшение числа страничных прерываний. Во всяком случае, алгоритмы замещения должны давать не худший результат, чем при меньшем объеме ОП. На рис. показана модель производительности алгоритма FIFO для той же траектории, но при увеличении М. Как видно из примера, объем ОП увеличился, а оценка производительности ухудшилась. Параметры модели и оценка производительности для этого случая: |Р|=12, F=10, f=10/12.

Алгоритм LRU (least recently used) : удаляется страница, к которой дольше всего не было обращений.

В основе этого алгоритма лежит предположение о том. что если к странице обращаются в настоящее время, то к ней же обратятся в ближайшем будущем. Это утверждение называется принципом локальности во бремени. Оно основано на опыте конструирования программ. Действительно, программный код и данные группируются в локальных областях памяти, дальние обращения выполняются редко. На рис.1 показано выполнение траектории страниц Р при М=3, а на рис.2 та же траектория для М=4. Параметры модели и оценки производительности ДЛЯ М=3: |Р|=12, F=10, f=10/12, а ДЛЯ М=4 1Р1=12. F=8, f=8/12.

Рис.1

Рис.2

Если сравнить соответствующие столбцы таблиц, то можно заметить что множества страниц, находящиеся в памяти для М=3. включаются в множество страниц при М=4 для соответствующих моментов поступления страниц. Это свойство алгоритма гарантирует, что при увеличении объема ОП оценка производительности не ухудшится. Алгоритмы, обладающие таким свойством, относятся к классу стековых алгоритмов, которые характеризуются отсутствием аномалии.

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

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

28. Явление пробуксовки в страничных системах и стратегия рабочего множества.

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

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

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

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

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

29. Управление памятью с сегментным распределением.

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

Такой способ управления памятью использовался в OS/2.

Программный адрес при сегментной организации логического адресного пространства имеет вид (S, D), где S - номер сегмента, а D - смещение на сегменте. Сегмент имеет переменную длину, поскольку смещение D занимает определенное число разрядов n в адресе, то размер сегмента может быть не более чем 2ⁿ-1, то есть размер сегмента ограничен.

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

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

Учет состояния памяти.

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

• базовый адрес сегмента Bi в ОП,

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

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

• длина сегмента.

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

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

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

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

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

Выделение и освобождение памяти.

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

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

Достоинства метода управления виртуальной сегментной памятью состоят в следующем:

• ликвидация фрагментации,

• большая виртуальная память,

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

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

Недостатки метода:

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

• размеры сегмента ограничены,

• наблюдается явление пробуксовки,

большие размеры сегментов препятствуют эффективному использованию памяти

30. Управление памятью с сегментно-страничным распределением.

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

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

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

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

Учет состояния памяти.

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

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

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

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

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

Достоинства метода управления виртуальной сегментно-страничной памятью состоят в следующем:

1. Большая память, предоставляемая пользователям за счет реализации идеи виртуальной памяти;

1. эффективное использование ОП за счет загрузки только необходимой части адресного пространства;

2. нет ограничений на размер сегмента;

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

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

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

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

31. Понятие процесса. Представление процессов в ос.

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

PCB

программы

данные

Состав блока управления процессом (PCB – Process control bloc)

1. Имя (идентификатор процесса). Статическое или динамическое наименование процесса.

2. Информация о процессоре и полномочиях процесса.

Состояние процессора (1 бит)

- режим управления программой (все программы)

- режим прикладной программы (нельзя вв/выв и др.)

Контекст процесса – содержание счетчика адреса команд, содержимое регистров, маски прерываний.

3. Информация об использовании ОП.

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

4. Информация о ресурсах, выделяемых процессу.

PCB

R

UCB

5. Информация о родственных процессах.

Родственные процессы – один процесс создает другой.

…………..

6. Информация о состоянии процесса.

- активное состояние – занимает ЦП

- ожидание – окончание вв/выв, ждет когда представятся ресурсы

- состояние готовность – нет ЦП, но есть все ресурсы, существует очередь готовых задач.

Пакетная система.

Диалоговая система

А

Г О

Диспетчер – управление очередью готовых процессов

RSX 11 M

7. Приоритет процесса.

Определяется местом в очереди.

М.б. статический – при создании процесса или динамический (н-р UNIX)

32. Понятие ресурса. Виды ресурсов.

Ресурсы – это объекты, которые – запрашиваются, используются, освобождаются или потребляются.

Ресурсы – устройства, файлы, области ОП, программы.

Ресурсы – перехватываемые (могут использ. разные процессы)

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

Ресурсы – разделяемые - совместно-используемые (некотор. обл. памяти)

- повторно-используемые (разделяемые на последовательной основе)

- не разделяемые (используются на монопольной основе)

С точки зрения емкости ресурсы подразделяются на – единичной емкости

- не единичной емкости

Как ресурс предоставляется в системе.

о своб.ресурса запрос процесса

Блок запроса

RCB

RCB

ENQ – запрос ресурса

DEQ – освобождение ресурса.

Программа строит очередь запросов. Как только ресурс освобождается, то программа выводит из очереди и уменьшает на 1 счетчик. Если счетчик=0 – то в сост. готовности

33. Алгоритмы диспетчеризации процессов: fifo, равномерное циклическое квантование.

1. FIFO

ЦП

Очередь без приоритетов.

Приоритет – статический; динамический

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

FIFO характерен для мультипрограммных пакетных систем.

2. Равномерное циклическое квантование.

ЦП

∆t

Задачи работают ∆t и если они не заканчивают работать, то перемещаются в конец очереди.

Существуют две модификации.

1. Модификация Коффмана.

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

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

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

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

1. FB_N (обратная связь с N-очередями)

n =N

ЦП

∆t=q

n=1

Когда процесс переходит из состояния ожидания в состояние готовности он находится в очереди 1.

Сначала обрабатывается очередь с n = 1, задача работает ∆t.

Процесс перемещения в очередь n=n+1, если она не отработает за время ∆t.

Процессы – счетные, много использ. ЦП

- диалоговые, использ. мало ЦП

2. Алгоритм Корбато

n =N

ЦП

∆t=2ⁿq

n=0

Блок анализа определяет номер очереди. Сначала обрабатываются «быстрые» очереди с маленькими номерами. Перестановка осуществляется через блок анализа. Внутри очереди используется RR или FIFO.

34. Алгоритмы диспетчеризации процессов, применяемые в ос реального времени.

Выделяют 16 (32) уровня. Задачи распределяются на эти уровни. Сначала выполняются активные задачи на 2ⁿ-1 уровне, потом на уровень ниже и так далее.

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

36. Взаимодействие и синхронизация процессов. Проблема "критической секции".

Виды параллелизма:

1. Естественный параллелизм.

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

Read – произойдет прерывание. Будет управление передано процессору вв/выв

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

WAIT – ожидание получения тех данных, которые читаются на периферийном процессоре.

WAIT – функция синхронизации.

2. Логический параллелизм.

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

Проблема "критической секции"

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

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

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

Условия взаимного исключения.

1. Если процесс находится в критической секции, то никакой процесс не может войти в свою критическую секцию.

2. Процесс не должен бесконечно находится в своей критической секции.

3. Процесс не может ждать бесконечно долго входа в критическую секцию.

37. Взаимодействие и синхронизация процессов. Проблема "поставщик-потребитель".

Проблема "поставщик-потребитель"

F- очередь полных буферов

E – очередь пустых буферов

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

В начальный момент E=n F=0

P_I0 – процесс вв/выв. P_с – счетный процесс.

P_I0 : M: if E=0 goto M - (*) занятое активное ожидание

E--

<ввести запись>

F++

Goto M

P­­­_c : M: if E=0 goto M

F--

<взять запись>

E++

Goto M

E,F - общие переменные, при работе с которыми возникает проблема критической секции по данным переменным.

При схеме (*) весь квант времени уйдет на ожидание. Необходимо организовать прерывание кванта.

38. Взаимодействие и синхронизация процессов. Проблема "читатели-писатели".

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

Есть некоторое множество процессов.

P_Ri - Писатели – пишут инф-ю в некоторый файл

P_Wj - Читатели – читают инф-ю из файла.

Читатели могут работать все одновременно а писатели – только единолично.

Введем переменную-флаг w = false. Если кто-то пишет файл, то w = true.

Для читателей вводится переменная r = 0 – число работающих с файлом.

P_Wj : L: if w or (r <> 0) then goto L;

w=true;

<Запись в файл>

w=false;

R_i: L: if w then goto L;

r++

<Прочитать >

r--

39. Механизмы синхронизации: активное ожидание, семафоры.

Активное ожидание.

IBM 370: TEST AND SET (проверить и установить)

Записывает FFh

Выдает результат – 0 – предыдущее значение байта 0

1 - перд. значение байта <0

b- булевская переменная.

L: if b then goto L;

TS(b); CS; b=false;

Переменная common (b) является общей для процессов Р1 и Р2. Её первоначальное значение равно нулю. Предположим, что первым начнёт выполняться процесс Р1. Перед тем как войти в свою критическую секцию (CS1), он установит свою переменную local1 в единицу и войдёт в цикл while. Этот цикл Р1 выполнит один раз, так как начальное значение common равнялось нулю. При выполнении цикла common установится в единицу (см. действия команды TS). Затем Р1 войдёт в свой критический интервал (CS1). Если в этот момент управление получит Р2 и захочет войти в свой критический интервал (CS2), то он сначала установит свою переменную local2 в единицу, а затем войдёт в цикл while и зациклится здесь (см. действия команды TS). Если через некоторое время управление получит Р1 и выполнит свой критический интервал до конца, а также установит common в ноль, процесс Р2, при получении управления, сможет войти в свой критический интервал. Другими словами, пока один из процессов находится в своем критическом интервале, другой процесс не может войти в свой критический интервал, т. е. задача взаимного исключения решается

Из инета:

1-ый процесс 2-ой процесс  

While (True) {

While ( BLOCK != 0 )

Critical-region();

BLOCK =1;

Noncritical_region(); }

While (True) {

While ( BLOCK != 0 )

Critical-region();

BLOCK =0;

Noncritical_region(); }

        Изначально целая переменная BLOCK =0, отслеживает чья очередь входит в критическую область. 

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

2-ой процесс также проверяет значение BLOCK, считывает 0, входит в цикл и ждет когда BLOCK станет =1.  

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

Семафоры.

S – семафор ресурса, открытие или закрытие доступа к этому ресурсу.

Операции над семафорами.

P(S) – Если S > 0 – S—

S=0, то процесс который выдал эту функцию переходит в состояние ожидания

V(S) – S++

Свойства P(S) и V(S)

1. Непрерываемые

2. Атрибутивные

3. V – переводит ожидание в состояние готовности

Пример. Решение проблемы критической секции с помощью семафора.

Свяжем семафор S с критическим ресурсов

S = 1

P1: L1: P(S)

<крит.секц>

V(S)

goto L1

P2: L1: P(S)

<крит.секц>

V(S)

goto L1

Таким образом, операция V(S) кроме выполнения S++ должна разбудить все ожидающие после выполнения P(S) процессы.

ИЗ учебника:

(про исключение)

Var s: semaphor;

Begin s:=1;

P1: while true do begin

… P(s); CS1; V(s); …

end;

and

P2: while true do begin

… P(s); CS2; V(s); …

end;

end.

Предположим, что первым начнёт выполняться процесс Р1. Прежде чем войти в свой критический интервал (CS1), он вызовет операцию P(s). После её выполнения значение числового поля семафора станет равным нулю, но Р1 войдёт в свой критический интервал. Если в этот момент процесс Р2 получит управление и захочет войти в свой критический интервал (CS2), он сначала вызовет выполнение операции P(s) и заблокируется по семафору s. Если через некоторое время процесс Р1 опять получит управление и выполнит свой критический интервал до конца, а также вызовет операцию V(s), процесс Р2 деблокируется и сможет войти в свой критический интервал. Задача взаимного исключения будет решена, так как только один из двух процессов будет находиться в своём критическом интервале.

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

40. Механизмы синхронизации: post/wait

OS-360

ECB (блок управления событиями)

W P

0 1 31

флаги информационная часть (RBA)

Функции POST и WAIT – работает с блоком.

Пример:

A – вызывающий процесс. Задача A – создает 3 подзадачи

START A

…………….

ATTACH EP=B ECB=адр1

Создание другого процесса

ATTACH EP=C ECB=адр2

…………….

ATTACH EP=D ECB=адр3

………………..

WAIT 3, ECBLIST=адр1

3 – общее число ожидаемых событий.

Зад B

0 0 адр RB зад A

0 0 адр RB зад A

0 0 адр RB зад A

адр2

адр3

зад С

0 1 код зав. B

0 0 адр RB зад A

0 0 адр RB зад A

0 1 код зав. B

1 0 адр RB зад A

1 0 адр RB зад A

2

адр RB зад A

2 – счетчик ожид. событий

Завершилось задание C. Счетчик ожид событий =1

0 1 код зав. B

0 1 код зав С

1 0 адр RB зад A

…….

POST адр3, код завершения D

………….

0 1 код зав. B

0 1 код зав С

0 1 код зав D

Завершилось задание D. Счетчик ожид событий =0

Постановка А в очередь готовности

41. Синхронизация посредством обмена сообщениями.

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

Сообщение.

заголовок информационная часть

Команды:

1. send – отправить сообщение

Send (id. Buf, Lbuf, rbuf, Lrbuf), id –идентификатор, Buf –буфер, Lbuf – длина буфера, rbuf – буфер для ответного сообщения, Lrbuf-его длина

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

2. Принимающий процесс должен содержать функцию Receive – получить.

Receive (id, buf, Lbuf), id – идентификатор процесса отправителя (0 – любой отправитель)

Эта функция просматривает mail box процесса и ищет сообщение от процесса с id, если оно есть, выдается id? Если не, то процесс ждет это сообщение. Если id = 0, то берется любое сообщение (от любого процесса).

3. Reply(id, buf, Lbuf) – посылает отклик процессу, блокированному по Send и переводит его в состояние готовности. Значение buf – это ответ

4. Crecieve(0, buf, Lbuf) – выдает идентификатор процесса, который послал сообщение, не переводит процесс в состояние ожидания.

42. Тупики в ос. Модель Холта.

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

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

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

П ример 1:

Пример 2:

Никто не освободит ресурс -> все заблокируются.

43. Методы обнаружения, восстановления и предотвращения тупиков.

Задачи:

1. Распознавание тупика

2. Восстановление – как выйти

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

Распознавание (используем модель Холта)

1. Выбираем активный процесс, стираем все стрелки. Например, P1

2. P1 вычеркнут, ресурс перейдет к P3

3. P3 активен – вычеркнули.

Активных процессов нет, граф содержит дуги -> существует тупик. Нет дуг – нет тупиков.

Эта процедура называется процедурой сокращения графа

Восстановление

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

Предотвращение

1) Предварительное построение модели Холта

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

2) Предварительно распределение ресурсов

Есть описание всех ресурсов, необходимых данному процессу. Инициатор завершения процесса заранее распределяет все ресурсы.

3) Стандартная последовательность распределения

Все ресурсы разделены на классы: К1, К2, …, Кi, Ki+1, ... Kn.

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

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

44. Прямой и косвенный ввод-вывод.

Прямой ВВ-В

Шина – разные провода. Группы: передача адресов, данных, управляющих сигналов.

Шина соединена с контроллерами.

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

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

Прямой доступ в память.

Котроллер ПДП освобождает ЦП. Обмен между ОП и к-л устройством. ЦП будет свободен, пока не придет прерывание от устройства.

Косвенный ВВ-В

Чтобы записать файл на диск надо знать: адрес диска, адрес цилиндра, адрес дорожки, адрес записи + системе ВВ-В нужен адрес канала и иногда адрес контроллера

Достоинства: ЦП свободен, система ВВ-В формирует адрес. Если 1 канал сломался, будет работать другой (надежность).

Недостаток: сложнее в исполнении и дороже.

Виды каналов:

- селекторные ( работают с 1м устройством, но быстрые)

-байт-мультиплексные (со многими устройствами, но работают медленнее)

-блок-мультиплексные (работает с блоками). Быстрее, чем байт-мультиплексные.

45. Монопольно используемые, разделяемые и виртуальные устройства.

Все устройства делятся на:

- устройства ВВ-В (не имеют файловой структуры)

- запоминающие устройства (имеют файловую структуру). Их разделяют по времени доступа на:

- ЗУ последовательного доступа. Обладают большой дисперсией. Например, магнитная лента.

-ЗУ прямого доступа (обращение по адресу). Дисперсия меньше.

Функции ОС при работе с ВУ:

1. Отслеживание состояния всех устройств. Создается таблица (Unit Control Block) – хранит информацию об устройстве. Информация может быть постоянная (адрес, тип) и переменная (состояние устройства).

2. Планирование:

- кому выделить устройство

- на какой срок

- в какой момент времени

3. Управление – выделение и освобождение.

Виды устройств:

1) монопольное устройство)

2) Разделяемое устройство

3) Виртуальное устройство (физическое устройство моделируется другим устройством). Например, печать: 1 принтер на много ПК. Создается специальный файл – работа происходит с файлом).

3. Виртуальные устройства

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

Spooler создает файл с заданиями. Reader берет эти данные как если с ВУ.

1. Очередь выходных работ.

System Memory Block, Data Memory Block

Если печатать по порядку – неудобно, все перепутается.

2. VM 370

ОП управляет виртуальными машинами

Реализация функций управления.

1. Монопольное использование устройств. Процесс может только один раз попросить устройство.

Учет: установка флажка в UCB.

Планирование: если есть свободное устройство, то отдать, нет – в очередь.

Выделение и освобождение: поставить и снять отметку о занятости в UCB.

2. Разделяемые устройства.

2.1. Учет (отслеживание состояния):

- таблица каналов (адрес, состояние канала, список процессов, ожидающих канал)

- таблица контроллеров (адрес, состояние, список устройств, список каналов, список процессов, ожидающих освобождение контроллера)

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

2.2. Планирование (см. след билет).

46. Планирование запросов для последовательно-разделяемых устройств

-Очередь (FIFO)

-другие алгоритмы планирования

Виды оптимизации:

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

- оптимизация по времени ожидания записи – упорядочить записи, чтобы находить нужную за 1 поворот диска

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

1. SSTF (Shortest scan time first)

Выбирается запрос, ближайший к положению головки.

Главный недостаток: дискриминация крайних дорожек. Большая дисперсия.

2. SCAN (сканирование)

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

3. N-STEP SCAN

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

4. C-SCAN (циклическое сканирование)

Запросы обслуживаются только при движении головки внутрь.

Используется только для систем с большими нагрузками (много запросов)

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

47. Физическая система вв-в

Функции системы ВВ-В – обмен информацией с устройствами.

Рассматриваем ОС 360-370

Функция EXCP (Execute Channel Program)– выполнить канальную программу. Это и есть физическая система ВВ-В.

- обрабатывает запросы на ВВ-В (от задач; программные синхронные прерывания)

- прерывания ВВ-В (от устройств ВВ-В)

PSW – слово состояние ЦП (Program Status Word). Содержит ключ защиты памяти, байт режима процессора, счетчик адреса команд (адрес следующей команды)

CSW – слово состояние канала (Channel Status Word)

CAW – адресное слово канала (Channel Adress Word)

После запрета на прерывание PSW – адрес входа в EXCP (от задач)

После завершения PSW – адрес входа в EXCP (от прерывания)

Функционирование EXCP пр запросе на ввод/вывод (обр. к SuperVisor (запрос от задач))

1. Проверка корректности ВВ-В блока. Адрес передается как параметр.

2. Создается элемент запроса на ВВ-В

3. Просматриваются управляющие блоки устройств и определяется, доступны ли устройства.

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

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

6. Если операция ВВ-В не может быть начата, запрос становится в очередь. Иначе – выполняется.

Вместо 4-5 можно написать: Start I/O - номер канала, номер устройства – запускает периферийный процессор, который берет из CAW начало канальной программы и начинает ее выполнять, после выполнения загружаем CSW, сообщая о результатах выполнения (есть/нет ошибки) и вызывает прерывание и в тек. PSW меняется состояние на не SuperVisor (пользовательское).

После окончания работы управление передается диспетчеру.

Функционирование EXCP в случае прерывания от ВВ-В (после заверш вв/выв)

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

2. Анализируются биты состояния завершения ВВ-В

3. Если завершена операция ВВ-В – выдается POST (синхронизируется POSTWAIT) Устанавливается ECB.

4. Просматривается очередь запросов на ВВ-В и запускается операция ВВ-В (2 входа)

5. Просмотр сохраненных прерываний. И их обработка (п. 1,2,3)

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

Формирование данных для физической системы ВВ-В

Job Control Table – таблица управления всеми задачами (информация об операторе JOB)

Step Control Table – таблица управления шагом задания

Step IO Table – таблица ВВ-В задачи. Описывает устройство.

Job File Control Block – описывает набор данных (файл)

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

Инициализация завершения – подготовка ресурсов к выполнению шага задания.

Task IO Table – таблица ВВ-В задачи. Помещается в раздел ОП, закрепленный за данной задачей.

Data Set Control Block – блок управления набором данных (дескриптор файла)

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

Data Control Block – 2 параметра: тип набора данных и тип доступа. Описывает данные в файле.

Data Extended Block – расширенный блок данных. Хранит реальный адрес устройства.

IO Block – блок ВВ-В

Метод доступа вызывает EXCP и на вход с прерыванием от В-ВВ подает адрес IOB

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

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

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

(VAX, VMS)

открыть файл

-------------------------------------------------интерфейс файловой системы

закрыть файл

копирование записи из файла; поместить запись в файл;

система работы с записями RNS

программный логический блок

--------------------------------------------------операции с файлами

записи логический блок

файловые примитивы

программный физический блок

--------------------------------------------------------операции с томом

записи физический блок

работа с конкретным -------драйвер устройства------QIO-----операция доступа к устройству

устройством

Физическое устройство: работа системы ВВ-В

С труктура данных

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

UCB (Unit Control Block) – блок управления устройством, содержит характеристики каждого устройства

IRP – пакет (блок) запроса на ВВ-В. Описывает запрос на ВВ-В.

CRB (Canal Request Block) – содержит индикатор устройств, описывающий контроллер

ACB (Adapter Control Block) – блок управления адаптером. Описывает адаптер.

IDB (Interruption Control Block) – блок управления прерываниями. Запоминает информацию о прерывании. Программа может определить, какое устройство закончило ВВ-В

Система ВВ-В:

- Обслуживание очереди ВВ-В. QIO – резидентная программа, находящаяся в ядре.

- Драйвер устройства

- Постпроцессоры ВВ-В

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

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

Запрос из программы пользователя

Контекст процесса Режим процессора

50. Логическая система вв-в

Метод доступа – сочетание способа доступа с определенным типом организации данных.

4 типа организации данных

1. Последовательный (адрес следующего элемента только после предыдущего)

2. Прямой (для каждого элемента нужен адрес)

3. Библиотечный

4. Индексно-последовательный: доступ по ключу.

Пример:

Ключ =1..2000

Главный индекс

Способы доступа

1. Способ доступа с очередями

2. Базисный способ доступа

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

Функции: PUT, GET. Программа задает длину буфера. При чтении при мк-команде OPEN начинается загрузка буферов (буферизация с упреждением).

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

Базисный способ доступа.

Функции: READ, WRITE. Программист осуществляет обмен данными на уровне блоков. Метод доступа подготавливает канальную программу.

QSAM – последовательный с очередями

BSAM – последовательный базисный

BPSAM – базисный библиотечный

QISAM – индексно-последовательный с очередями

BISAM – базисный индексно-последовательный

BDAM – базисный прямой

51. Буферизация

Буферная область – область ОП для временного хранения данных, считанных в ОП, либо данных, подготовленных для передачи на ВУ.

Буфер – часть буферной области для одной операции обмена.

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

Вых НД

РО – рабочая область.

НД – набор данных

Виды буферизации:

- буферизация по требованию

- буферизация с упреждением

Режимы пересылок

1. Перемещение

PUT – пересылка в следующий свободный буфер

2. Режим указания

GET – адрес следующего регистра (может все-таки заполненного буфера?)

PUT – адрес следующего свободного буфера

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

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

52. Простая и обменная буферизация

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

В простой буферизации используется:

- режим перемещения

- режим указания

Простая

1) GET – перемещение, PUT – перемещение

2) GET – указание, PUT – перемещение

3) GET – перемещение, PUT –указание. PUT делается раньше GET.

4) GET – указание, PUT – указание

Обменная

Подстановка

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

53. Функции системы управления данными

Принципы сист. управл:

-Пользователь д.б. изолирован от машино-зависимых объектов.

-Необходима защита информация одного пользователя от другого -Алгоритм управления внеш памятью должен быть централизован

-Необходимо управлять системной информацией

Функции:

1. Учет (где какой файл, сколько места занимает, свободная память на диске)

ОС 360:

Volume Table of Context – индексный файл

Data Set Control Block – дескриптор. Хранит имя, дату создания, дату последней модификации, адрес на диске.

DS – набор данных – файл.

RSX 11 M

Master File Directory – системные файлы (5 штук)

User File Directory – имена пользовательских файлов.

Системные файлы:

- индексный файл. Хранение дескрипторов(заголовки) все файлов.

-BMF (Bit Map File) – каждому блоку на диске соответствует бит в файле. Свободен 0, занят 1.

-Bad block File– перечень блоков, которые при разметке были выявлены как дефектные. испорченные блоки исключаются из адресного пространства.

2. Размещение информации:

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

- общепользовательская

- персональная (обычно на сменных носителях)

3. Выделение информационного ресурса

- получение доступа к файлу

- вычисление действительного адреса нужной инф

- чтение/запись записи

4. Освобождение ресурса (по сути в табл дескрипторов запись затираем вроде как)

54. Организация доступа к информационному ресурсу

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

1. Имя файла (в ОС/2 каталогизация файла, доступ через оператор dd, top)

fp=fopen(<имя>, «r»)

fp – указатель на File Control Block – внутренний дескриптор файла.

FILE*fp

2. Получение действительного адреса

Индексный дескриптор файла существует на диске

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

3. Проверка полномочий доступа

Пользователи: системные, собственники, член группы, остальные. У каждого может быть свои права: Read, Write, Edit, Delete.

4. Непосредственное чтение/запись файла (READ/PUT (буфер)). Здесь работает система ВВ-В.

55. Разграничение полномочий пользователя в ос.

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

UIC = [gr, mem]; gr- группа, member – член группы.

UIC присваивается всем каталогам и файлам, которые относятся к этому пользователю (включая те, которые он создает)

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

1. Системный пользователь (sys)

2. Член группы (gr)

3. Собственник файла (own)

4. Другие (world)

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

В QNX [255,255] – системный пользователь, супер-пользователь.

Если UIC пользователя совпадает с UIC, приписанным к файлу по обоим полям – то own, если совпадают номера групп – то он член группы, если ничего не совпадает – то world.

Для файла можно определить типа атрибуты: Read, Write, Edit, Delete. С файлами связывается код: <rwed, rwed, rwed, rwed > - код доступа к файлу, этот код определяет, какие действия можуг делать с файлом пользователи различных групп: sys,gr,own,world.

Есс-но, может не везде быть rwed.

Процедура определений полномочий доступа:

1. По UIC определяетсягрцппа пользователя.

2. По коду доступа определяются разрешаемые действия.

Код доступа задает Sys.

Осуществление доступа к файлу:

1. Отрытие файла:

Fp = open (<путь к файлу>,<тип файла(бинарный или текстовый)>)

Open Обращается к системе, ищется по индексному файлу активных дескрипторов, открыт ли искомый файл. Если файл еще не открыт, то ищется свободный дескриптор и в него считывается дескриптор файла с диска. Далее проверяются полномочия доступа по UIC. Потом формируется FCB (File Control Block) – указатель на запись.

2. Read, Write

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

56. Управление оп в unix

Существует область свопинга (все логическое адресное пространство переносится на диск).

0 – диспетчерский процесс, создается при загрузке

1 – поиск процесса, требующего загрузки, по таблице процессов. Если такого процесса нет:

return ++;

sleep(&runout,PSwp)

- «засыпание»

Если к-л процесс активизирован, при передиспетчеризации процесса:

If (runout !=0)

{

runout=0;

wakeup(&runout) --------------инициализация процесса

}

Изменен приоритет процессов.

Для каждого процесса подсчитывается время пребывания в ОП (поле в дескрипторе процесса P_time).

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

Если есть ОП – хорошо. Если нет – надо процесс с меньшим приоритетом выгрузить в свопинг и на его место загрузить новый.

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

Если нет таких, у которых приоритет > PZERO, то выгружается тот, у которого больше значение P_time (дольше всех находится в памяти).

Если диспетчер обнаружил процессы, но их перемещать нельзя, он засыпает:

return ++;

sleep(&runout,PSwp)

57. Управление процессами в unix

Процесс – потребитель ресурсов

- единица работы и управления

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

Процесс – кодовый сегмент (файл на диске)

- Сегмент данных (файл на диске)

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

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

Для статических процессов – статический приоритет.

Определить число дескрипторов (гнезда). Новый процесс занимает свободный дескриптор.

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

Проц. сегмДанные ОП

Проц. Сегмент 1,2 – реентерабельный сегмент (используется и 1-м и 2-м процессом)=>это критическая секция=>каждая ф-я ядра – критическая секция=>ядро должно быть устроено таким образом, чтобы оно могло разделятся между процессами.

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

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

Фазы процесса.

- пользовательская фаза

- системная фаза (выполняются функции ядра)

В системной фазе определяется статический приоритет.

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

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

Функция создания процесса fork()

id=fork //(id принимает какое-то значение)

if (fork())

{действия отца}

else {действия сына}

id – значение идентификатора вновь созданного процесса.

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

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

Для программ ОС – статический приоритет, для программ пользователей – динамический приоритет.

PZERO – граничный приоритет, который определяет, может ли быть процесс выведен сигналом (прерывания) из ожидания. Чем меньше значение приоритета – тем более всок приоритет. Если процесс меньше PZERO, то его нельзя прервать.

Дескриптор процесса одеожит:

P_nice – может изменятся пользоваетелм

P_cpu – формируется системой.

Начальное значение p_nice = NZERO (диапазон от NZERO до 2*NZERO-1 для непривилегированных процессов и от 0 до 2*NZERO-1 для привелигированных)

P_cpu>=puser

P_pri – Пользовательский приоритет

P_pri=Puser+Pnice-Nzero+p_cpu/16.

Т.о. через каждые 16 тиков p_pri увеличивается на 1. P_pri вычисляется при загрузке процесса в память.

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

Событие – для системных процессов

Sleep (&runin, prior)

Wakeup(&runin)

Функции синхронизации, доступные процессам только в сист. Фазе.

Для пользовательских процессов служат сигналы (типа что-то вроде прерываний)

kill(id,signal) – сигнал завершения для родственного процесса.

Ф-я signal() определяет реакцию процесса на сигнал:

-игнорировать

-перехватить (написать обработчик)

-завершить процесс

58-59. Структура файловой системы в UNIX, Управление свободной памятью на диске и учет занятой памяти на диске.

Имеет древовидную структуру

Dev (device) –содержит драйверы (уст-ва рассматриваются как спец. Файлы)

0 1 s+2 N N+M

IPL – initial program loader. (программа начальной загрузки)

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

Суперблок – структура с полями:

S_isize – чмсло блоков в индексном файле

S_fsize – max. номер блокадля файлов (N)

S_nfree – число свобоных блоков в s_free

S_free – массив номеров свободных блоков (s_free[NIC_free])

S_ninode – число свобожных инжексных дескрипторов

S_inode[NIC_INOD] – амссив номеров свободных индексных дескрипторов в индексном файле

S_flock – флаг запрета работы со списком свободных блоков.

S_ilock - флаг запрета работы с индексным файлом.

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

S_ronly – файловая система только для чтения

S_time – время последней модификации суперблока.

Если s_nfree=0, то в s_free[0] хранится адрес блока, в котором записаны номера свободных блоков, массив заполняется номерами свободных блоков и все сначала (хуйня какая-то). При освобождение блоков их номера записываются в s_free.

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

Индексный дескриптор файла – структура с полями.

Di_mode – тип файла, привелегии и код доступа. Меня заебало все это писать.

11, 12, 13 – указывают на структуры из 128 блоков, которые содержат адреса блоков, в которых размещен файл. Причем структура имеет несколько уровней в зависимости от номера.

Система подсчитывает число открытий файла. Если =0 (все программы закрыли файл), то дескриптор переписывается на диск.

60. Управление вводом/выводом в unix

Устройство-файл – имеет дескриптор, в котором содержится информация.

Байт-ориентированные устройства – только для передачи, имеются буфера, но сами устройства информацию не хранят. Индекс дескриптор файла устройства содержит поле i_addr[0]:

i_addr[0].d_major – тип устройства и драйве,

i_addr[0].d_minor – номер устройства, кот. Передается драйверу.

Драйвер для байт-ориентированного устройства выбирается из таблицы cdevsw, для блок- ориентированных – bdevsw.

Процесс загружен в память=>создается контекст процесса (устройства). В контексте содержаться поля u_file, куда записывается номер дескриптора файла.

Содержит:

-Признак типа открытия : чтение, запись …

-Счетчик числа ссылок обращений к дескриптору

-указатель позиции в файле.

75