Теория Операционных Систем

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

основной памяти 3. оборудование ввода - вывода4. файлы, хранящиеся во внешней памяти На рисунке приведены основные компоненты ОС как системы разделенияресурсов. Таким образом, основные компоненты ОС 1. управление процессами распределяет ресурс процессорноевремя 2. управление памятью распределяет ресурс адресноепространство основной памяти 3. управление устройствами распределяет ресурсы оборудованиеввода - вывода 4. управление данными распределяет ресурс данные илифайлы

. Функционирование компьютера после включения питания начинаетсяс запуска программы первоначальной загрузки Boot Track. Программа Boot Track инициализируетосновные аппаратные блоки компьютера и регистры процессора CPU , накопитель памяти,контроллеры периферийного оборудования. Затем загружается ядро ОС, то бишьOperating System Kernel. Дальнейшее функционирование ОС осуществляется как реакцияна события, происходящие в компьютере.

Наступление того или иного события сигнализируетсяпрерываниями - Interrupt. Источниками прерываний могут быть как аппаратура HardWare , так и программы SoftWare . Аппаратура сообщает о прерывании асинхронно в любой моментвремени путем пересылки в CPU через общую шину сигналов прерываний. Программа сообщает о прерывании путем выполнения операции

System Call. Примеры событий,вызывающих прерывания 1. попытка деления на 02. запрос на системное обслуживание3. завершение операции ввода - вывода4. неправильное обращение к памяти Каждое прерывание обрабатывается соответственно обработчикомпрерываний Interrupt handler , входящим в состав ОС. Главные функции механизма прерываний это 1. распознавание или классификация прерываний2. передача управления соответственно обработчику прерываний3. корректное

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

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

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

регистров CPU. Таким образом, для одной программы могутбыть созданы несколько процессов, в том случае, если с помощью одной программы вкомпьютере выполняется несколько несовпадающих последовательностей команд. За времясуществования процесс многократно изменяет свое состояние. Различаютследующие состояния процесса 1. новый new, процесс только что создан 2. выполняемый running, команды программы выполняютсяв CPU 3. ожидающий waiting, процесс ожидает завершения некоторогособытия,

чаще всего операции ввода - вывода 4. готовый ready, процесс ожидает освобождения CPU 5. завершенный terminated, процесс завершил свою работу Переход из одного состояния в другое не может выполняться произвольнымобразом. На рисунке приведена типовая диаграмма переходов для состояний процессора. Каждый процесс представлен в операционной системе набором данных,называемых process control block .

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

состояние П3 в PCB3, активизируется PCB1 прерывание. сохраняется состояние П2 в PCB2, активизируется PCB3 ожидаемый, готовый выполняемый ожидаемый time 2. Планирование процессов. Понятие очереди. Система управления процессами обеспечивает прохождение процессачерез компьютер. В зависимости от состояния процесса ему должен быть предоставитьтот или иной ресурс. Например, новый процесс необходимо разместить в основной памяти,следовательно, ему необходимо выделить

часть адресного пространства. Процессу всостоянии готовый должно быть предоставлено процессорное время. Выполняемый процессможет потребовать оборудование ввода - вывода и доступ к файлу. Заголовок Процессы первый PCB7 PCB8 в состоянии готовый последний Очередь к первый магнитной ленте последний Очередь первый PCB3 PCB14 PCB6 к диску 1 последний Очередь к первый

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

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

которая называется планировщик. scheduler Операционная система, обеспечивающая режим мультипрограммирования, обычновключает два планировщика долгосрочный long term scheduler и краткосрочный short term scheduler CPU scheduler . Основное отличие между долгосрочным и краткосрочным планировщикамизаключается в частоте запуска, например краткосрочный планировщик может запускатьсякаждые 100 мс, долгосрочный один раз за несколько минут. Долгосрочный планировщик решает, какой из процессов, находящихсяво входной очереди,

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

быть передан на выполнение в CPU. В некоторыхоперационных системах долгосрочный планировщик может отсутствовать. Например, всистемах разделения времени time sharing system , каждый новый процесс сразу жепомещается в основную память.1.3. Взаимодействие процессов. Пользовательский уровень. Совместно выполняемые процессы могут быть либо независимыми independed processes , либо взаимодействующими cooperating processes . Взаимодействиепроцессов часто понимается в смысле взаимного обмена данными через

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

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

При этом оба процессаиспользуют общий участок памяти, например процесс - производитель и процесс - потребительмогут использовать следующие переменные Var n type item Var buffer array 0 n-1 of item in, out 0 n-1 , где n - количествоадресуемых элементов буфера, Item - имя типа элементов буфера, in, out - указатели,характеризующие заполнение буфера. Буферпредставлен в виде циклически связанного массива адресуемых элементов с двумя указателями- in,

out. Указатель in содержит номер первого свободного элемента буфера, аout - первого занятого элемента буфера. 0 1 2 3 4 5 n-1 1. Пуст. in out. Очевидно, что буфер пуст в том случае,если выполняется это условие.2. Буфер будет полностью заполнен, если выполняется условие in 1 mod n out Процесс - производитель должен выполнять процедуру записи вбуфер типа Repeat продуцируется очередной элемент в Next p while in 1 mod n out dono op buffer in next p in in 1

mod n until falseгде Next p - локальная переменнаяпроцесса - производителя, в которой хранится очередной продуцируемый элементno op - пустой операторПроцесс - потребитель должен выполнятьпроцедуру чтения из буфера типаRepeatwhile in out do no op nextp buffer out out out 1 mod n потребляетсяочередной элемент из Next с until false2. Планирование процессора. Краткосрочный планировщик выбирает процессы из очереди готовыхпроцессов и передает их на выполнение в CPU.

Существуют различны алгоритмы или стратегиирешения этой задачи, отличающиеся отношением к критериям планирования.2.1. Критерии планирования процессора. Используются следующие критерии, позволяющие сравнивать алгоритмыкраткосрочных планировщиков 1. утилизацияCPU использование CPU utilization. утилизация CPU теоретически может находитьсяпределах от 0 до 100 . В реальных системах утилизация CPU колеблется в пределах40 для легко загруженного

CPU, 90 для тяжело загруженного CPU.2. пропускнаяспособность CPU throughput. Пропускная способность CPU может измеряться количествомпроцессов, которые выполняются в единицу времени.3. времяоборота turnaround time для некоторых процессов важным критерием является полноевремя выполнения, то есть интервал от момента появления процесса во входной очередидо момента его завершения. Это время названо временем оборота и включает время ожиданияво входной очереди, время

ожидания в очереди готовых процессов, время ожидания вочередях к оборудованию, время выполнения в процессоре и время ввода - вывода.4. времяожидания waiting time . под временем ожидания понимается суммарное время нахожденияпроцесса в очереди готовых процессов.5. времяотклика response time для сугубо интерактивных программ важным показателем являетсявремя отклика или время, прошедшее от момента попадания процесса во входную очередьдо момента первого обращения к терминалу.

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

FIFO. first come firstserved FCFS . FCFS является наиболее простой стратегией планированияпроцессов и заключается в том, что процессор передается тому процессу, который раньшевсех других его запросил. Когда процесс попадает в очередь готовых процессов, processcontrol block присоединяется к хвосту очереди. Среднее время ожидания для стратегии FCFS часто весьма великои зависит от порядка поступления процессов в очередь готовых процессов.Пример 1 Пусть три процесса попадают в очередь одновременно в момент0 и

имеют следующие значения времени последующего обслуживания в CPU.вариант 1 П1 24 мс П2 3 мс П3 3 мс вариант 2 П2 3 мс П3 3 мс П1 24 мс На рисунке приведены диаграммы Ганга очереди готовых процессоввариант 1 П1 П2 П3 WT 17 мс WT1 0 мс WT2 24 мс WT3 27 мс вариант 2 П2 П3 П1 WT 3 мс WT2 0 мс WT3 3 мс WT1 6 мс Стратегии

FCFS присущ так называемый эффект конвоя . В томслучае, когда в компьютере имеется один большой процесс и несколько малых, то всепроцессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию.Таким образом, эффект конвоя приводит к снижению загруженности как процессора,так и периферийного оборудования.2.2.2. Стратегия наиболее короткая работа вперед к победе коммунизма! SJF SJF Shortest Job First. Одним из методов борьбы с эффектомконвоя является стратегия, позволяющая

процессу из очереди выполняться первым.Пример 2 Пусть четыре процесса одновременно попадают в очередь готовыхпроцессов и имеют следующие значения времени последующего обслуживанияП1 6 мс П2 8 мс П3 7 мс П4 3 мс На рисунке приведена диаграмма Ганга, построенная в соответствиисо стратегией SJF. П4 П1 П3 П2 WT 7 мс WT4 0 мс WT1 3 мс WT3 9 мс WT2 16 мс

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

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

FCFS предполагает, что все процессы предполагает, что всепроцессы имеют одинаковые приоритеты, а стратегия SJF предполагает, что приоритетесть величина, обратная времени последующего обслуживания. Приоритет это целое положительное число, находящееся в некоторомдиапазоне, например от 0 до 7, от 0 до 4095. Будем считать, что чем меньше значениечисла, тем выше приоритет процесса. Пример 3. приоритет П1 10 мс 3 П2 1 мс 1 П3 2 мс 3

П4 1 мс 4 П5 5 мс 2 Нарисунке приведена диаграмма Ганга, располагающая процессы в очереди в соответствиисо стратегией приоритетного планирования П2 П5 П1 П3 П4 WT2 0 мс WT5 1 мс WT1 6 мс WT3 16 мс WT4 18 мс Приоритеты определяются исходя из совокупности внутренних ивнешних по отношению к операционной системе факторов. Внутренние факторы 1. требования к памяти2. количество открытых файлов3. отношение среднего времени

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

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

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

CPU на время, равное одному кванту.Новый процесс добавляется в хвост очереди. Если процесс не завершился в пределахвыделенного ему кванта времени, его работа принудительно прерывается, и он перемещаетсяв хвост очереди.Пример 4П1 24 мс П2 3 мс П3 3 мс q 4 мс.Диаграмма Ганга соответственноRound Robin стратегии для этого случая имеет вид П1 П2 П3

П1 П1 П1 П1 П1 WT1 0 мс 7 10 14 18 22 26 30 Свойства Round Robin стратегии сильно зависят от величины временногокванта q. Чем больше временной квант, тем дольше Round Robin стратегия приближаетсяк FCFS стратегии. для рассмотренного примера, если q gt 24 мс, то - gt FCFS. При очень малых значениях временного кванта Round

Robin стратегия называют разделениемпроцессора processor sharing. Теоретически это означает, что каждый из N процессовработает со своим собственным процессором, производительность процессора равна1 N от производительности физического процессора.2.2.5. ПЛАНИРОВАНИЕ с использованием многоуровневой очереди. Multilevelqueue scheduling Эта стратегия разработана для ситуации, когда процессы могутбыть легко классифицированы

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

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

2.2.6. Программирование с использованием многоуровневой очереди с обратнымисвязями multilevel feedback queue sheduling Обычная многоуровневая очередь не допускает перемещения процессовмежду очередями. Многоуровневая очередь с обратными связями предполагает, что процессыпри определенных условиях могут перемещаться между очередями. Процессыпервоначально попадают в очередь 0, где каждому из них предоставляется квант времени,равный 8 мс. Те процессы, которые не успели выполниться в течение этого времени,перемещаются

в очередь 1. Процессы из очереди 1 начинают обрабатываться только тогда,когда очередь 0 становиться пустой. Те процессы, которые не выполнились в очереди1 q 16 мс перемещаются в очередь 2. Процессы из очереди 2 будут обрабатыватьсятолько в том случае, если становятся пустыми очереди 0 и 1. Рассмотреннаястратегия является наиболее универсальной и сочетает в себе свойства всех рассмотренныхраньше стратегий.1. FCFS2. SJF3. приоритетная 4. Round Robin 5. многоуровневаяочередь 3.

Управление невиртуальной памятью.3.1. Своппинг. swapping Своппингом называется метод управления памятью, основанный натом, что все процессы, участвующие в мультипрограммной обработке, хранятся во внешнейпамяти. Процесс, которому выделен CPU, временно перемещается в основнуюпамять swap in roll in . В случае прерывания работы процесса он перемещается обратново внешнюю память swap out roll out .

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

CPU. Вначале каждого временного кванта блок управления памятью выгружает из основной памятипроцесс, работа которого была только что прервана, и загружает очередной выполненныйпроцесс. Метод своппинга влияет на величину временного кванта RoundRobin стратегии. Пример.1. пустьочередной загружаемый в память процесс имеет размер 100Кб.2. диск позволяетчитать данные со скоростью 1 Мб в секунду3. следовательно,100

Кб могут быть загружены за 100 мс.4. будемсчитать, что для первоначального подвода головки чтения - записи потребуется 8 мс5. такимобразом, операция своппинг займет 108 мс, а общее время своппинга - 216 мс. Для эффективной загруженности процессора время своппинга должнобыть существенно меньше времени счета. Следовательно, для рассмотренного примераквант времени должен быть существенно больше, чем 216 мс. Ясно, что это число значительноувеличится, если перемещаемый процесс имеет размер, например,

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

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

3.2.1. Однопрограммный режим. 0 а б Рисунок иллюстрирует смежное размещение contiguousallocation одной программы в основной памяти. При смежном размещении размер загружаемой программы ограничиваетсяразмером накопителя. Для того, чтобы при смежном размещении загружать программы,размеры которых превышают размеры накопителя, используют метод оверлейных сегментов overlay segments . В программе, имеющей древовидную структуру, модули второго уровняработают сугубо последовательно, поэтому

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

0 а б Во время работы прикладной программы все адреса, генерируемыеCPU, сравниваются с содержимым регистра границы. Если генерируется адрес меньшечисла а, работа программы прерывается.3.2.2 Мультипрограммный режим с ФИКСИРОВАННЫМИ границами. Мультипрограммирование с фиксированными разделами Multiprogramming with a fixed number of tasks предполагает разделение адресногопространства на ряд разделов

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

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

необходимы два регистра. Первый регистр верхней границы наименьшийадрес , второй регистр нижней границы наибольший адрес . Прежде чем программа в разделе N начнет выполняться, ее граничныеадреса загружаются в соответствующие регистры. В процессе работы программы все формируемыеею адреса контролируются на удовлетворение неравенстваа lt Адр. lt б При выходе любого адреса программы за отведенные ей границы,работа программы прерывается.3.2.3. Мультипрограммирование с переменными разделами. multiprogrammingwith a variable number

of tasks MVT . Метод Multiprogramming with a Variable number of Tasks предполагаетразделение памяти на разделы и использование загрузочных модулей в перемещаемыхадресах, однако, границы разделов не фиксируются. 0 ОС 90 Кб а Раздел 1 П5 П4 П3 П2 П1 Раздел 2 Раздел 3 Раздел 4 80 Кб Как следует из рисунка, в начальной фазе отсутствует фрагментация,связанная с тем, что размер очередного

процесса меньше размера, занимаемого этимпроцессом раздела. На этой фазе причиной фрагментации является несоответствие размераочередного процесса и оставшегося участка памяти. По мере завершения работы программыосвобождаются отдельные разделы. В том случае, когда освобождаются смежные разделы,границы между ними удаляются и разделы объединяются. 0 ОС 90 Кб а Раздел 1 П7 П6 П5 100 Кб Раздел 4 За счет объединения или слияния смежных разделов образуютсябольшие

фрагменты, в которых можно разместить большие программы из очереди. Таким образом, на фазе повторного размещения действуют те жепричины фрагментации, что и для метода MFT.3.2.4. Мультипрограммирование с переменными разделами и уплотнением памяти. Ясно, что метод Multiprogramming with a Variable number ofTasks порождает в памяти множество малых фрагментов, каждый из которых может бытьнедостаточен для размещения очередного процесса, однако суммарный

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

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

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

достаточен для размещения еще одного процесса 3.3. Страничная организация памяти. Страничная организация памяти paging относится к методам несмежногоразмещения процессов в основной памяти. Основное достоинство страничной организации памяти заключаетсяв том, что она позволяет свести к минимуму общую фрагментацию за счет полного устранениявнешней фрагментации и минимизации внутренней фрагментации.3.3.1. Базовый метод. f

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

Каждый адрес, генерируемый процессором, состоит из двух частей П - номер страницы page number и Д - смещение в пределах страницы off set . Номер страницы может использоваться как индекс для таблицы страниц page table . Таблица страниц содержит начальные адреса f всех страничныхрамок, в которых размещена программа. Физический адрес определяется путем сложенияначального адреса страничной рамки f и смещения

Д. Вторичная память Таблица страниц Основная память программы А 0. стр. 0 0. 1 1. стр. 0 программа стр. 1 1. 3 2. А стр. 2 2. 4 3. стр. 1 стр. 3 0. 7 0. стр. 2 0. f П 1. 2. стр. 3 Рисунок показывает, что страничная организация памяти полностьюисключает внешнюю фрагментацию. Внутренняя фрагментация не превышает величиныpage size-

Q Elem, где page size размер страничной рамки, а Q Elem минимальныйадресуемый элемент основной памяти. Для ускорения вычисления физического адреса операцию суммированиязаменяют операцией конкатенации. старшие разряды младшие разряды 2n 1 2n f 2n-1 2n Д На рисунке заштрихованы незаполненные нулевые разряды. Для того,чтобы операция конкатенации была возможна, необходимо, чтобы базовые адреса страничныхрамок

располагались только в старших разрядах 2n 1 , а следующие толькомладших разрядов 20, 21, 22 . f Основная память Например, при n 9 базовые адреса страничных рамок это следующийряд 512, 1024, 1536. Следовательно, размер страничной рамки равен 512 байт. В современных операционных системах типичный размер страницысоставляет 2 Кб или 4 Кб. Каждая операционная система поддерживает свой собственный методработы с таблице страниц.

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

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

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

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

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

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

S и d, где S номер сегмента, а d смещение в пределах сегмента. Трансформация логического адреса в физический осуществляетсяс помощью таблицы сегментов segment table . Количество строк таблицы сегментов равно количеству сегментовпрограммы S, limit, base. Limit размер сегмента, base начальный адрес сегментав памяти. Номер сегмента S используется в качестве индекса для таблицысегментов.

С помощью таблицы сегментов определяется его начальный адрес base в основнойпамяти. Значение limit используется для защиты памяти. Смещение d должно удовлетворятьнеравенству 0 lt d lt limit. В случае выхода смещения за границы сегмента работапрограммы прерывается. Физический адрес определяется как сумма начального адресаbase и смещения d. В том случае, если таблица сегментов имеет значительные размеры,она располагается в основной памяти,

а е начальный адрес и длина хранятся в специальныхрегистрах STBR segment table base register , STLR segment table lengthregister . Для ускорения трансформации логического адреса в физический операциясуммирования часто заменяется операцией конкатенации для этого необходимо, чтобыначальные адреса сегментов были кратны некоторому числу 2n .Таблица сегментов или е часть располагается в ассоциативной памяти.

Защита сегментной памяти основана на контроле уровня доступак каждому сегменту. Например, сегменты, содержащие только код, могут быть помещеныкак доступные только для чтения или выполнения, а сегменты, содержащие данные, помечаюткак доступные для чтения и записи.3.4.2. Разделение сегмента между НЕСКОЛЬКИМИ процессами. Поскольку сегмент является логически завершенным программныммодулем, он может использоваться различными процессами. Сегмент называется разделяемым,когда его начальный адрес

и размер указаны в двух и более таблицах сегментов. Например,два процесса могут использовать подпрограмму Sqrt, которая хранится в виде однойфизической копии. На рисунке приведен пример, иллюстрирующий использование разделяемоготекстового редактора. таблица сегментов процесса 1 основная память limit base 0. 25286 43062 43062 1. 4425 68348 68348 редактор 2.

данные 72773 1 таблица сегментов процесса 2 90003 limit base данные 0. 25286 43062 98553 2 1. 8550 90003 2. 3.4.3. Фрагментация. Программа во входной очереди загружается в память посегментнов любые свободные разделы основной памяти. При этом, как правило, используются стратегииbest fit и first fit. Сегментной организации памяти присущи как внутренняя, таки внешняя фрагментации. Внутренняя фрагментация образуется вследствие того, чторазмер загружаемого сегмента меньше размера

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

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

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

Таким образом, страничирование по запросу означает1. программаможет выполняться CPU, когда часть страниц находится в основной памяти, а часть во внешней.2. в процессевыполнения новая страница не перемещается в основную память до тех пор, пока в нейне возникла необходимость. Для уч та распределения страниц между внешней и основной памятьюкаждая строка таблицы страниц дополняется битом местонахождения страницы.Valid invalid bit. логическая таблица физическая вторичная память страниц

память память 0. A. 0. 4 v 0 1. B. 1. i 1 A. 2. C. 2. 6 v 2 B. 3. D. 3. i 3 C. 4. E. 4. i 4 A D. 5. F. 5. 8 v 5 E. 6. G. 6. i 6 C F. 7. H. 7. i 7 8 F 15 В том случае, если процессор пытается использовать страницу,помеченную значением invalid, возникает событие, называемое страничная недостаточность paging fault . Страничная недостаточность вызывает прерывание выполнения программыи передачу управления операционной

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

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

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

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

в swap space, а на е место загружается страница,вызываемая страничной недостаточностью. Обработка страничной недостаточности с учетом замещения осуществляетсяпо следующему алгоритму 1. определяется местонахождение страницы путем анализабита местонахождения2. если значение бита invalid, то разыскивается свободнаястраничная рамка.2.1.если имеетсясвободная страничная рамка, то она используется.2.2.если свободнойстраничной рамки нет, то используется алгоритм замещения, который выбирает страницу жертву.2.3.страница жертва

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

перемещения е содержимое не модифицировалось.В этом случае время замещения уменьшается примерно вдвое. Для учета факта модификации страницы в таблицу страниц вводитсядополнительный бит, который меняет сво значение на противоположное в том случае,если содержимое страницы изменилось. Для практического использования метода страничирования по запросунеобходимо разработать два алгоритма. 1. алгоритмраспределения страничных рамок from allocation algorithm .2. алгоритмзамещения страниц page

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

Для замещения выбирается наиболее старая страница. Учет времени необязателен, когда все страницы в памяти связаныв FIFO-очередь, а каждая помещаемая в память страница добавляется в хвост очереди. поток ссылок на страницы 7 0 1 2 0 3 0 4 2 3 0 3 2 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 0 3 3 3 3 3 страничные рамки. 11 замещений, 14 ссылок Алгоритм учитывает только время нахождения страницы в памяти,но не учитывает используемость страницы. Например, первые страницы программы могутсодержать переменные,

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

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

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

поле время использования . Заменяетсястраница с наименьшим значением в отмеченном поле путем сканирования всей таблицыстраниц. Сканирование отсутствует при использовании подхода на основе стека.2. стек номеровстраниц хранит номера страниц, упорядоченных в соответствии с историей их использования,на вершине стека располагается только что использованная страница, а на днеleast recently used страница. Как только осуществляется ссылка на страницу, онаперемещается на вершину стека, а номера всех страниц

сдвигаются вниз.