Shpori_na_ekzamen_OS

41

9. Управление памятью. Управление виртуальной памятью

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

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

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

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

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

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

9.2. Алгоритмы замещения страниц, их анализ и моделирование

Алгоритм FIFO. Выталкивание первой пришедшей страницы

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

Оптимальный алгоритм (OPT)

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

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

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

LRU

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

42

Выталкивание редко используемой страницы. Алгоритм NFU

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

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

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

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

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

9.4.Сегментация, ее реализация

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

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

43

10.Прерывания. Модульный принцип программирования

10.1.Прерывания; механизм обработки прерываний; технология обработки

прерываний

Переривання – це сигнал, який дозволяє центральному пристрою обробки інформації (процесору) змінити свій стан всупереч припису програми користувача. Цей сигнал виробляється апаратно при появі деяких внутрішніх або зовнішніх подій, які вимагають відповідної реакції ЕОМ.

Переривання діляться на 5 типів:

1.Зовнішні переривання (клавіатура, таймер, лінії зв’язку).

2.Виклик супервізора з програми користувача для виконання якоїсь з його функцій (поява в програмі команди INT-SVC).

3.Переривання через особливі ситуації, що виникають в ході виконання програми (порушення захисту пам’яті, помилка в коді операції, арифметичне переповнення та ін.).

4.Переривання через збій ЕОМ (від схем оперативного контролю ЕОМ).

5.Переривання від пристроїв введення-виведення.

Механізм переривання.

Переривання – це припинення послідовного виконання команд активної програми (тої, чиї команди виконує в даний момент процесор) і перехід до спеціальної підпрограми. Цей перехід є тимчасовим – по закінченню підпрограми виконання перерваної програми відновлюється з того місця, де вона була призупинена.

Розглянемо послідовність дій, викликаних сигналом переривання:

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

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

3.Запам’ятовування інформації, необхідної для відновлення виконання перерваної програми.

Як правило, ця інформація містить такі параметри:

1)Лічильник команд, який містить адресу, на якій програма була перервана і до якої повинно відбутись повернення.

2)Внутрішні регістри процесора: суматор, РЗП та ін.

3)Регістри захисту пам’яті та переадресації.

4)Деякі робочі комірки пам’яті.

5)Індикатори типу індикаторів переповнення та переносу.

6)Умови виконання програми, які зберігаються, як правило, в слові стану програми.

4.Виконання під програми переривань. Ця частина містить фазу діагностики для виявлення точної причини переривання і наступне виконання необхідних у цьому випадку дій.

5.Відновлення інформації і поновлення виконання перерваної програми. Ця фаза є оберненою до фаз запам’ятовування інформації, заборони переривань та переходу до підпрограми. Відновлюються параметри перерваної програми. Заборони з переривань знімаються і виконується перехід до того місця, де програма була перервана.

44

Пріоритети.

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

При програмному встановленні пріоритету використовується поняття “маска”. Кожному класу переривань можна поставити у відповідність деякий розряд регістра маски. Якщо деякий розряд цього регістру встановлений в 1, то переривання даного класу обслуговується негайно, в противному разі вони чекають зміну стану регістра маски. Управління регістром маски покладається на супервізор.

Привілейований режим

Складність системи, а також можливість одночасного знаходження в пам’яті ЕОМ кількох програм користувачів приводять до необхідності прийняття деяких запобіжних заходів, які обмежують можливості користувачів шляхом заборони для них ряду функцій. Мета цих заходів – уникнути порушень роботи всієї системи з боку окремих користувачів. При цьому виконання заборонених функцій покладається на супервізор, який має виключне право на виконання таких дій:

1.Управління введенням/ виведенням інформації.

2.Управління зовнішньою пам’яттю.

3.Обробка переривань.

4.Організація послідовного виконання програм та вибір порядку їх виконання.

5.Організація захисту пам’яті.

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

Непривілейований режим призначений для програм користувачів, і для деяких програм ОС, що не мають високого пріоритету. В цьому режимі забороняється виконання (використання при написанні програм) деяких команд: введення – виведення, звертань до лічильника часу, звертань до масок переривань, модифікації регістрів та ключів захисту пам’яті, керування деякими спеціальними пристроями при роботі в реальному часі. Для виконання кожної з цих операцій програма користувача повинна звернутись до супервізора з відповідним запитанням. Супервізор виконує цю операцію, забезпечуючи нормальне функціонування всієї системи. Спроба виконання забороненої команди в непривілейованому режимі викликає негайне переривання типу “Неправильна операція”, яка передає управління супервізору.

В привілейованому режимі дозволяється виконання всіх команд, які є в репертуарі ЕОМ. Перехід в режим супервізора відбувається в першій фазі кожного переривання встановленням відповідної маски в слові стані програми. Перехід в непривілейований режим є останньою операцією кожної підпрограми обробки переривань – завантажують таке ССП користувача, яке містить відповідну маску режиму роботи.

45

10.2. Супервизор; ССП (PSW), структура PSW (на примере IBM/360)

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

Важливу роль в обробці програм має слово стану програми (ССП). Розглянемо ССП IBM360 як найбільш яскравий приклад. Воно займає в пам’яті 64 розряди і має таку структуру:

Розряди 0–7 – це маска системи, розряди 36-39 – це маска програми.

7-й розряд дає змогу відстроїтися від зовнішніх переривань, якщо вони з якихось причин небажані.

13-й розряд може маскувати переривання від схеми оперативного апаратного контролю ЕОМ з метою запобігти зацикленню програми на невдалій спробі обробити переривання, яке виникло через появу якоїсь несправності ЕОМ.

Код переривання відображає причину, з якої мало місце переривання. Можливі випадки, коли одночасно виникає декілька таких причин і надходить декілька сигналів. Саме тут і відбувається реалізація апаратно встановлених пріоритетів, а також фіксація фактів надходження запитів від пристроїв на обслуговування.

Код довжини команди 32-33 відображає той факт, що в репертуарі ЕОМ IBM-360 використовуються команди різної довжини. На цю величину збільшується вміст лічильника команд для знаходження адреси наступної команди (розряди 40-63).

Ознака результату виробляється при виконанні більшості команд. Наприклад, при виконанні команди арифметичного додавання можливі такі значення ознаки результату: 00 – результат нульовий, 01 – результат додатній, 10 - від’ємний, 11 – переповнення.

В процесі виконання програми (знаходження її в активному стані) ССП цієї програми знаходиться в спеціальному службовому регістрі ЕОМ, так званій активній комірці пам’яті. При зміні активної програми в активну комірку заноситься нове ССП.

46

Оскільки в розрядах 40-63 цього нового ССП знаходиться адреса наступної команди для нової програми, то запис в активну комірку нового ССП еквівалентний передачі управління в потрібну точку нової програми.

З кожним з п’яти вище перелічених класів переривань зв’язані двоє ССП, названі “старим” і “новим”, яким зафіксовано дві комірки оперативної пам’яті. Коли має місце переривання, апаратний механізм переривання записує поточне ССП з так званої активної комірки пам’яті – спеціального робочого регістра ЕОМ в ОП на місце старого ССП у відповідності з причиною переривання і завантажує нове відповідне ССП з комірки нового ССП в активну комірку, передаючи таким чином управління відповідній програмі обробки переривання.

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

В ПК сам перехід відбувається також за допомогою однієї команди (CALL, RET, INT, IRET), але при цьому ще потрібні допоміжні дії за допомогою деяких привілейованих команд (LTR – завантаження регістра задачі, CLIS – установка в 0 прапорця перемикання задачі та ін.). Для зберігання інформації про стан перерваної або відновлюваної програми використовується системний стек.

47

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

При розробці програм широко використовується модульний принцип програмування, де кожна програма являє собою модуль. Кілька модулів можуть бути об’єднані і скласти більший модуль, крім того, модулі можуть викликати один одного динамічно. Програма, записана на будь-якій мові програмування, називається початковим модулем (початковою програмою). Початкова програма перетворюється відповідним транслятором в об’єктний модуль (ОМ) – модуль в проміжному форматі, спільному для всіх трансляторів. ОМ повинен пройти ще один етап обробки – редагування. На цьому етапі він обробляється системною програмою “Редактор зв’язків”. В результаті з’являється програма, готова до завантаження її в ОП з настройкою на конкретні адреси. Така програма називається завантажним модулем (ЗМ). ПМ, ОМ та ЗМ є переміщуваними модулями, не зв’язаними з конкретними адресами пам’яті ЕОМ. Завантажні модулі виготовляються безпосередньо транслятором.

Об’єктний модуль складається з тексту програми в машинному коді та двох словників – словника зовнішніх символів та словника переміщення.

Словник зовнішніх символів містить всі посилання даного модуля на інші програмні модулі (їх виклик). Крім того, програмний модуль може мати кілька входів і через ці входи до нього можуть звертатись (посилатись) інші програмні модулі. Кожен вхід позначається міткою і ця мітка також є зовнішнім символом. Словник зовнішніх символів використовується редактором зв’язків для погодження взаємних посилань модулів.

Завантажний модуль крім тексту програми має словник переміщень (в ПК – таблиця настройки адрес). Словник переміщень містить внутрішні адресні посилання, типовим прикладом є адресні константи. Це константи, в яких з якихось причин довелось вказати на конкретні адреси і, при переміщенні такого модуля з одного на інше місце в ОП або при завантаженні, ці константи повинні бути відповідним чином змінені. Це, наприклад, адреси для передачі управління в інший програмний сегмент (JMP FAR) або виклик програми, завантаженої в інший сегмент (CALL FAR), повернення в материнську програму з підпрограми (RET, IRET) та ін.

В ПЕОМ об’єднання модулів можливе або на рівні початкових програм, з погодженням міжпрограмних зв’язків відповідним транслятором, або шляхом динамічного виклику завантажених модулів під час виконання програми.

При програмуванні використовуються такі структури модулів: x Проста. Оверлейна. Динамічна.

У випадку простої структури модуль завантажується в ОП як єдине ціле, хоча сам може складатись з групи модулів, об’єднаних редактором зв’язків або транслятором. Модулі простої структури ефективні за своєю швидкодією, тому до такої структури треба весь час прагнути.

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

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

48

10.4. Соглашения о межпрограммных связях

Вони стосуються збереження та відновлення вмісту регістрів при переході від однієї програми до іншої, використання регістрів зв’язку або стеку при міжпрограмних передачах управління, способів передачі та повернення управління.

При обговоренні цих угод завжди розглядається пара, що складається з викликаючої “материнської” та викликаної “дочірньої” програми. Кожна програма, яка одержує управління при її запуску безпосередньо користувачем ПЕОМ або планувальником процесів (в мультипрограмних ОС) початково є викликаною програмою. Під час виконання цієї програми може стати необхідною робота якоїсь іншої програми і перша з цих програм стає вже викликаючою.

В цілому викликаюча програма зобов’язана:

1.Побудувати список параметрів для програми, що викликається, і адресу цього списку занести в умовлений регістр зв’язку (або використати стек, або записати параметри, якщо їх мало, в регістри).

2.Занести в умовлений регістр зв’язку (стек) адресу повернення (якщо викликається супервізор з програми користувача, то це забезпечується автоматично).

3.Передати управління програмі, що викликається.

Програма, що викликається, зобов’язана:

1.На самому початку своєї роботи зберегти вміст всіх регістрів процесора, які будуть змінюватись в процесі роботи даної програми, в стеку або в області збереження, виділеній материнською програмою і адреса якої знаходиться в умовленому регістрі зв’язку.

2.Перед своїм завершенням відновити вміст регістрів, збережений при вході в дану програму.

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

10.5.Повторное использование модулей

Взалежності від можливості повторного використання одного і того ж тексту вже завантаженого програмного модуля існують 3 типи завантажних модулів:

x Одноразово використовувані.

xПовторно використовувані.

xРеентерабельні.

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

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

49

10.6. Способы вызова модулей

Всього є 6 способів виклику модулів різного типу:

1.Блок BEGIN-END, {}, сформований з метою розмежування області дії імен в програмі в блокових мовах програмування. Цей модуль розміщується або “вручну” шляхом фізичної вставки в потрібне місце програми вже готового, може й чужого програмного модуля, або з’являється в програмі як результат застосування функції include. Всі параметри для такого модуля глобальні.

2.Підпрограма (процедура). Вона активізується (створюється запис активації) програмою, що її викликає і після свого завершення повертає управління материнській програмі в точку, безпосередньо наступну за точкою свого виклику, знищуючи цим запис активації. Параметри в підпрограмі передаються за правилами зв’язування програм.

3.Функція переривання. Вона викликається з активної програми застосуванням виклику супервізора INT або є реакцією у відповідь на якусь обумовлену внутрішню або зовнішню події (переповнення, переривання від зовнішніх пристроїв та ін.). Параметри з материнської програми передаються в регістрах.

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

5.Диспетчерський виклик програм або співпрограм, при якому кожна з них розглядається як окремий процес. Замість виконання команд виклику, повернення чи відновлення, виконується звернення до диспетчера з вимогою виконати певну дію.

6.Паралельне виконання модулів, які відображають паралельні процеси. Ініціюються способом відгалуження – один модуль викликає інший, після цього вони функціонують паралельно, можливо конкуруючи за ресурси ЕОМ.

10.7. Передача-получение параметров

Найбільш загальними є 4 способи передачі та одержання параметрів:

1.Материнська та дочірня програми можуть спільно використовувати для параметрів спільну область даних. Використання пам’яті глобальної для обох програм вимагає, щоб для доступу до параметрів вони використовували одні і ті ж імена або адреси, до яких звертаються як до зовнішніх. Перевага – простота реалізації, недоліки – необхідність знати зовнішні імена, витрата часу на трансляцію або редагування зовнішніх посилань (див. словники зовнішніх символів), іноді в цьому методі існують обмеження на адресацію.

2.Передача параметрів через регістри процесора. Перевага методу – простота.

Використовується, коли параметрів мало. Приклад – застосування в перериваннях для зазначення замовленої функції.

3.Список параметрів – найбільш універсальний спосіб, приклад:

Адреса списку параметрів передається через регістр зв’язку. Варіант – заголовок списку завантажується в стек і тоді не потрібен навіть регістр зв’язку, але доступ до списку параметрів дещо обмежується. Спосіб легко реалізується, не обмежуючи програміста у використанні регістрів, недолік – необхідність передачі параметрів адресою, що створює труднощі для системи захисту інформації.

4. Спільний стек параметрів. Материнська програма передає параметри, розміщуючи їх у стеку, а дочірня вибирає зі стеку, знаючи їх порядок заповнення. Реалізується легко, коли параметри є простими змінними, з масивами складно. Добре те, що параметр передається за значенням.

50

11.Ввод-вывод. Концепции аппаратуры ввода-вывода

11.1.Два типа устройств ввода-вывода: блочные и символьные

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

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

11.2. Диапазон скоростей устройств ввода-вывода и проблемы ПО

11.3. Контроллер устройств ввода-вывода, структура и функционирование

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

Плата контроллера обычно снабжается разъемом, к которому может быть подключен кабель, ведущий к самому устройству. Многие контроллеры способны управлять двумя, четырьмя или даже восемью идентичными устройствами. Если интерфейс между контроллером и устройством является стандартным, то есть официальным стандартом ANSI, IEEE или ISO либо фактическим стандартом, тогда различные компании могут выпускать отдельно контроллеры и устройства, удовлетворяющие данному интерфейсу. Так, многие компании производят жесткие диски, соответствующие интерфейсу IDE или

SCSI.