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

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



НазваниеТеория Операционных Систем
Дата конвертации16.08.2012
Размер286,78 Kb.
ТипРеферат
Теория Операционных Систем


Теория операционных систем Введение. Основные понятия и определения. Операционная система - это программа, которая выполняет функциипосредника между пользователем и компьютером. ОС, выполняя роль посредника, служит двум целям:1. эффективно использовать компьютерные ресурсы.2. создавать условия для эффективной работы пользователя В качестве ресурсов компьютера обычно рассматривают:1. время работы процессора2. адресное пространство основной памяти1. оборудование ввода - вывода2. файлы, хранящиеся во внешней памяти На рисунке приведены основные компоненты ОС как системы разделенияресурсов. Таким образом, основные компоненты ОС:1. управление процессами (распределяет ресурс — процессорное время);2. управление памятью (распределяет ресурс — адресное пространство основной памяти);3. управление устройствами (распределяет ресурсы) — оборудование ввода - вывода;4. управление данными (распределяет ресурс — данные или файлы). Функционирование компьютера после включения питания начинается сзапуска программы первоначальной загрузки — Boot Track. Программа BootTrack инициализирует основные аппаратные блоки компьютера и регистрыпроцессора (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 для переключения процессора с одногопроцесса на другой.|выполняемый |ожидаемый, |готовый |выполняемый | || | | | | || | | | | || | | | | ||готовый |выполняемый |гото |вый | || | | | | || | | | | || | | | | ||ожидаемый, |готовый |выполняемый |ожидаемый | || | | |time | | 1.2. Планирование процессов. Понятие очереди. СИСТЕМА УПРАВЛЕНИя ПРОЦЕССАМИ ОБЕСПЕчИВАЕТ ПРОХОЖДЕНИЕ ПРОЦЕССА чЕРЕЗКОМПЬЮТЕР. В ЗАВИСИМОСТИ ОТ СОСТОяНИя ПРОЦЕССА ЕМУ ДОЛЖЕН БЫТЬ ПРЕДОСТАВИТЬТОТ ИЛИ ИНОЙ РЕСУРС. НАПРИМЕР, НОВЫЙ ПРОЦЕСС НЕОБХОДИМО РАЗМЕСТИТЬ ВОСНОВНОЙ ПАМяТИ, СЛЕДОВАТЕЛЬНО, ЕМУ НЕОБХОДИМО ВЫДЕЛИТЬ чАСТЬ АДРЕСНОГОПРОСТРАНСТВА. ПРОЦЕССУ В СОСТОяНИИ ГОТОВЫЙ ДОЛЖНО БЫТЬ ПРЕДОСТАВЛЕНОПРОЦЕССОРНОЕ ВРЕМя. ВЫПОЛНяЕМЫЙ ПРОЦЕСС МОЖЕТ ПОТРЕБОВАТЬ ОБОРУДОВАНИЕВВОДА - ВЫВОДА И ДОСТУП К ФАЙЛУ.| | |Заголово| | | | | | | || | |к | | | | | | | ||Процессы | |первый | |PCB7 | |PCB8 | | | ||в | | | | | | | | | ||состоянии| | | | | | | | | ||“готовый”| |последни| | | | | | | || | |й | | | | | | | || | | | | | | | | | || | | | | | | | | | ||Очередь к| |первый | | | | | | | ||магнитной| | | | | | | | | ||ленте | |последни| | | | | | | || | |й | | | | | | | || | | | | | | | | | || | | | | | | | | | ||Очередь | |первый | |PCB3 | |PCB14 | |PCB6 | ||к | | | | | | | | | ||диску №1 | |последни| | | | | | | || | |й | | | | | | | || | | | | | | | | | || | | | | | | | | | ||Очередь к| |первый | |PCB5 | | | | | ||терминалу| | | | | | | | | ||№ 1 | |последни| | | | | | | || | |й | | | | | | | || | | | | | | | | | | Распределение процессов между имеющимися ресурсами носит названиепланирование процессов. Одним из методом планирования процессов,ориентированных на эффективную загрузку ресурсов, является метод очередейресурсов. Новые процессы находятся во входной очереди, часто называемойочередью работ - заданий (job queue). Входная очередь располагается во внешней памяти, во входной очередипроцессы ожидают освобождения ресурса — адресного пространства основнойпамяти. Готовые к выполнению процессы располагаются в основной памяти исвязаны очередью готовых процессов или ready queue. Процессы в этой очередиожидают освобождения ресурса процессорное время. Процесс в состоянии ожидания завершения операции ввода - выводанаходится в одной из очередей к оборудованию ввода - вывода, которая носитназвание devices queue. При прохождении через компьютер процесс мигрирует между различнымиочередями под управлением программы, которая называется планировщик.(scheduler) Операционная система, обеспечивающая режиммультипрограммирования, обычно включает два планировщика — долгосрочный(long term scheduler) и краткосрочный (short term scheduler/CPU scheduler). Основное отличие между долгосрочным и краткосрочным планировщикамизаключается в частоте запуска, например: краткосрочный планировщик можетзапускаться каждые 100 мс, долгосрочный — один раз за несколько минут. Долгосрочный планировщик решает, какой из процессов, находящихся вовходной очереди, должен быть переведен в очередь готовых процессов в случаеосвобождения ресурсов памяти. Долгосрочный планировщик выбирает процесс из входной очереди с цельюсоздания неоднородной мультипрограммной смеси. Это означает, что в очередиготовых процессов должны находиться в разной пропорции как процессы,ориентированные на ввод - вывод, так и процессы, ориентированные напреимущественную работу с CPU. Краткосрочный планировщик решает, какой из процессов, находящихся вочереди готовых процессов, должен быть передан на выполнение в CPU. Внекоторых операционных системах долгосрочный планировщик можетотсутствовать. Например, в системах разделения времени (time sharingsystem), каждый новый процесс сразу же помещается в основную память. 1.3. Взаимодействие процессов. Пользовательский уровень. СОВМЕСТНО ВЫПОЛНяЕМЫЕ ПРОЦЕССЫ МОГУТ БЫТЬ ЛИБО НЕЗАВИСИМЫМИ(INDEPENDED PROCESSES), ЛИБО ВЗАИМОДЕЙСТВУЮЩИМИ (COOPERATING PROCESSES).ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ чАСТО ПОНИМАЕТСя В СМЫСЛЕ ВЗАИМНОГО ОБМЕНА ДАННЫМИчЕРЕЗ ОБЩИЙ БУФЕР ДАННЫХ. Взаимодействие процессов удобно рассматривать в схеме производитель -потребитель (produces - consumer). Например, программа вывода на печатьпроизводит последовательность символов, которые потребляются драйверомпринтера или компилятор производит ассемблерный текст, который затемпотребляется ассемблером. Для того, чтобы процесс - производитель и процесс - потребитель моглизаполнять совместно необходимый буфер, заполняемый процессом -производителем и потребляемым процессом - потребителем. Буфер имеет фиксированные размеры, и следовательно процессы могутнаходиться в состоянии ожидания, когда:. буфер заполнен; ожидает процесс - производитель. буфер пуст; ожидает процесс - потребитель Буфер может предоставляться и поддерживаться самой ОС, например спомощью средств коммуникации процессов (IPC — Inter Process Communication),либо организовать прикладным программистом. При этом оба процессаиспользуют общий участок памяти, например процесс - производитель и процесс- потребитель могут использовать следующие переменные: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 do no_op; buffer (in):=next p; in:=(in+1) mod n;until falseгде Next p - локальная переменная процесса - производителя, в которойхранится очередной продуцируемый элементno_op - пустой операторПроцесс - потребитель должен выполнять процедуру чтения из буфера типаRepeatwhile in out do no_op; next p := buffer (out); out:=(out+1) mod n; ... потребляется очередной элемент из Next с ...until false 2. Планирование процессора. КРАТКОСРОчНЫЙ ПЛАНИРОВЩИК ВЫБИРАЕТ ПРОЦЕССЫ ИЗ ОчЕРЕДИ ГОТОВЫХПРОЦЕССОВ И ПЕРЕДАЕТ ИХ НА ВЫПОЛНЕНИЕ В 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 — FIRST SERVED (FCFS). FCFS яВЛяЕТСя НАИБОЛЕЕ ПРОСТОЙ СТРАТЕГИЕЙ ПЛАНИРОВАНИя ПРОЦЕССОВ ИЗАКЛЮчАЕТСя В ТОМ, чТО ПРОЦЕССОР ПЕРЕДАЕТСя ТОМУ ПРОЦЕССУ, КОТОРЫЙ РАНЬШЕВСЕХ ДРУГИХ ЕГО ЗАПРОСИЛ. Когда процесс попадает в очередь готовых процессов, process controlblock присоединяется к хвосту очереди. Среднее время ожидания для стратегии 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>24 мс,то -> FCFS.) При очень малых значениях временного кванта Round Robinстратегия называют разделением процессора — processor sharing. Теоретическиэто означает, что каждый из N процессов работает со своим собственнымпроцессором, производительность процессора равна 1/N от производительностифизического процессора. 2.2.5. ПЛАНИРОВАНИЕ с использованием многоуровневой очереди.(Multilevel queue 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 Robin5. многоуровневая очередь 3. Управление невиртуальной памятью. 3.1. СВОППИНГ. (SWAPPING) СВОППИНГОМ НАЗЫВАЕТСя МЕТОД УПРАВЛЕНИя ПАМяТЬЮ, ОСНОВАННЫЙ НА ТОМ,чТО ВСЕ ПРОЦЕССЫ, УчАСТВУЮЩИЕ В МУЛЬТИПРОГРАММНОЙ ОБРАБОТКЕ, ХРАНяТСя ВОВНЕШНЕЙ ПАМяТИ. Процесс, которому выделен CPU, временно перемещается в основнуюпамять (swap in/roll in). В случае прерывания работы процесса он перемещается обратно вовнешнюю память (swap out/roll out).Замечание: при своппинге из основной памяти во внешнюю (и обратно)перемещается вся программа, а не её отдельная часть. Своппинг иногда используют при приоритетном планировании CPU. В этомслучае с целью освобождения памяти для высокоприоритетных процессов,низкоприоритетные процессы перемещаются во внешнюю память. Основное применение своппинг находит в системах разделения времени,где он используется одновременно с Round Robin стратегией планирования CPU. В начале каждого временного кванта блок управления памятью выгружаетиз основной памяти процесс, работа которого была только что прервана, изагружает очередной выполненный процесс. Метод своппинга влияет на величину временного кванта Round Robinстратегии.Пример.1. пусть очередной загружаемый в память процесс имеет размер 100Кб.2. диск позволяет читать данные со скоростью 1 Мб в секунду3. следовательно, 100 Кб могут быть загружены за 100 мс.4. будем считать, что для первоначального подвода головки чтения - записи потребуется 8 мс5. таким образом, операция своппинг займет 108 мс, а общее время своппинга - 216 мс. Для эффективной загруженности процессора время своппинга должно бытьсущественно меньше времени счета. Следовательно, для рассмотренного примераквант времени должен быть существенно больше, чем 216 мс. Ясно, что эточисло значительно увеличится, если перемещаемый процесс имеет размер,например, 1 Мб. Недостаток “чистого” своппинга в больших потерях времени на загрузкуили выгрузку процессов. Поэтому в современных операционных системахиспользуется модифицированные варианты своппинга. Так, например, во многих версиях операционной системы UNIX своппингвключается только в том случае, когда количество процессов в памятистановится слишком большим. 3.2. Смежное размещение процессов. МЕТОДЫ РАЗМЕЩЕНИя ПРОЦЕССОВ В ОСНОВНОЙ ПАМяТИ ПО ОТНОШЕНИЮ КРАСПОЛОЖЕНИЮ УчАСТКОВ ПАМяТИ, ВЫДЕЛЕННЫХ ДЛя ОДНОЙ И ТОЙ ЖЕ ПРОГРАММЫ ДЕЛяТНА ДВА КЛАССА. ПЕРВЫЙ — МЕТОД СМЕЖНОГО РАЗМЕЩЕНИя, А ВТОРОЙ — МЕТОДНЕСМЕЖНОГО РАЗМЕЩЕНИя. Смежное размещение является простейшим и предполагает, что в памяти,начиная с некоторого начального адреса выделяется один непрерывный участокадресного пространства. при несмежном размещении программа разбивается на множество частей,которые располагаются в различных, необязательно смежных участках адресногопространства. 3.2.1. Однопрограммный режим. РИСУНОК ИЛЛЮСТРИРУЕТ СМЕЖНОЕ РАЗМЕЩЕНИЕ (CONTIGUOUS ALLOCATION) ОДНОЙПРОГРАММЫ В ОСНОВНОЙ ПАМяТИ. При смежном размещении размер загружаемой программы ограничиваетсяразмером накопителя. Для того, чтобы при смежном размещении загружатьпрограммы, размеры которых превышают размеры накопителя, используют методоверлейных сегментов (overlay segments). В программе, имеющей древовидную структуру, модули второго уровняработают сугубо последовательно, поэтому в памяти может находиться толькоодин из них. Оверлейную структуру программы и последовательность загрузкиоверлейных сегментов планирует сам программист. В процессе выполнения программы все её адреса не должны быть меньшечисла а. В противном случае возможна запись какого-либо результата работыпрограммы (поверх операционной системы) и уничтожение некоторых её частей.Защиту операционной системы в случае смежного размещения приоднопрограммном режиме можно осуществить с помощью регистра границы. Во время работы прикладной программы все адреса, генерируемые CPU,сравниваются с содержимым регистра границы. Если генерируется адрес меньшечисла а, работа программы прерывается. 3.2.2 Мультипрограммный режим с ФИКСИРОВАННЫМИ границами. МУЛЬТИПРОГРАММИРОВАНИЕ С ФИКСИРОВАННЫМИ РАЗДЕЛАМИ (MULTIPROGRAMMINGWITH а FIXED NUMBER OF TASKS) ПРЕДПОЛАГАЕТ РАЗДЕЛЕНИЕ АДРЕСНОГОПРОСТРАНСТВА НА РяД РАЗДЕЛОВ ФИКСИРОВАННОГО РАЗДЕЛА. В КАЖДОМ РАЗДЕЛЕРАЗМЕЩАЕТСя ОДИН ПРОЦЕСС. Наиболее простой и наименее эффективный режим MFT соответствуетслучаю, когда трансляция программ осуществляется в абсолютных адресах длясоответствующего раздела. В этом случае, если соответствующий раздел занят, то процесс остаетсяв очереди во внешней памяти даже в том случае, когда другие разделысвободны. Уменьшить фрагментацию при мультипрограммировании с фиксированнымиразделами можно, если загрузочные модули получать в перемещаемых адресах.Такой модуль может быть загружен в любой свободный раздел послесоответствующей настройки. При мультипрограммировании с трансляцией в перемещаемых адресахимеются две причины фрагментации. Первая — размер загруженного процессаменьше размера, занимаемого разделом (внутренняя фрагментация), вторая —размер процесса в очереди больше размера свободного раздела, и этот разделостается свободным (внешняя фрагментация). Для защиты памяти при мультипрограммировании с фиксированнымразделами необходимы два регистра. Первый — регистр верхней границы(наименьший адрес), второй — регистр нижней границы (наибольший адрес). Прежде чем программа в разделе N начнет выполняться, ее граничныеадреса загружаются в соответствующие регистры. В процессе работы программывсе формируемые ею адреса контролируются на удовлетворение неравенства а < Адр. < б При выходе любого адреса программы за отведенные ей границы, работапрограммы прерывается. 3.2.3. Мультипрограммирование с переменными разделами. (multiprogramming with a variable number of tasks (MVT). МЕТОД MULTIPROGRAMMING WITH а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 а VARIABLE NUMBER OF TASKSПОРОЖДАЕТ В ПАМяТИ МНОЖЕСТВО МАЛЫХ ФРАГМЕНТОВ, КАЖДЫЙ ИЗ КОТОРЫХ МОЖЕТ БЫТЬНЕДОСТАТОчЕН ДЛя РАЗМЕЩЕНИя ОчЕРЕДНОГО ПРОЦЕССА, ОДНАКО СУММАРНЫЙ РАЗМЕРФРАГМЕНТОВ ПРЕВЫШАЕТ РАЗМЕР ЭТОГО ПРОЦЕССА. Уплотнением памяти называется перемещение всех занятых разделов поадресному пространству памяти. Таким образом, чтобы свободный фрагментзанимал одну связную область. На практике реализация уплотнения памяти сопряжена с усложнениемоперационной системы и обладает следующими недостатками:1. в тех случаях, когда мультипрограммная смесь неоднородна по отношению к размерам программ, возникает необходимость в частом уплотнении, что расходует ресурс процессорное время и компенсирует экономию ресурса памяти.2. во время уплотнения все прикладные программы переводятся в состояние “ожидание”, что приводит к невозможности выполнения программ в реальном масштабе времени. 3.2.5. Основные стратегии заполнения свободного раздела. РАССМОТРЕННЫЕ МЕТОДЫ МУЛЬТИПРОГРАММИРОВАНИя ПРЕДПОЛАГАЮТ НАЛИчИЕВХОДНОЙ ОчЕРЕДИ/ОчЕРЕДЕЙ К РАЗДЕЛАМ ОСНОВНОЙ ПАМяТИ. В том случае, когда освобождается очередной раздел, операционнаясистема должна выбрать один из процессов для размещения его в памяти.Алгоритм выбора может использовать одну из следующих трех стратегий:1. стратегия наиболее подходящего (best fit strategy) выбирает процесс, которому в освободившемся разделе наиболее тесно (выигрыш в памяти).2. стратегия первого подходящего (first fit strategy) выбирает первый процесс, который может разместить в освободившемся разделе.3. стратегия наименее подходящего (last fit strategy) выбирает процесс, которому в освободившемся разделе наиболее свободно (в этом случае остающийся фрагмент часто достаточен для размещения еще одного процесса) 3.3. Страничная организация памяти. СТРАНИчНАя ОРГАНИЗАЦИя ПАМяТИ (PAGING) ОТНОСИТСя К МЕТОДАМ НЕСМЕЖНОГОРАЗМЕЩЕНИя ПРОЦЕССОВ В ОСНОВНОЙ ПАМяТИ. Основное достоинство страничной организации памяти заключается в том,что она позволяет свести к минимуму общую фрагментацию за счет полногоустранения внешней фрагментации и минимизации внутренней фрагментации. 3.3.1. Базовый метод. АДРЕСНОЕ ПРОСТРАНСТВО ОСНОВНОЙ И ВНЕШНЕЙ ПАМяТИ РАЗБИВАЮТ НА БЛОКИФИКСИРОВАННОГО РАЗМЕРА, НАЗЫВАЕМЫЕ СТРАНИчНЫЕ РАМКИ (FRAMES). ЛОГИчЕСКОЕАДРЕСНОЕ ПРОСТРАНСТВО ПРОГРАММЫ ТАКЖЕ РАЗБИВАЕТСя НА БЛОКИ ФИКСИРОВАННОГОРАЗМЕРА, НАЗЫВАЕМЫХ СТРАНИЦАМИ (PAGES). РАЗМЕРЫ СТРАНИчНЫХ РАМОК И СТРАНИЦСОВПАДАЮТ. ПРОЦЕСС ЗАГРУЖАЕТСя В ПАМяТЬ ПОСТРАНИчНО, ПРИчЕМ КАЖДАя СТРАНИЦАПОМЕЩАЕТСя В ЛЮБУЮ СВОБОДНУЮ СТРАНИчНУЮ РАМКУ ОСНОВНОЙ ПАМяТИ. Каждый адрес, генерируемый процессором, состоит из двух частей: П -номер страницы (page number) и Д - смещение в пределах страницы (off set).Номер страницы может использоваться как индекс для таблицы страниц (pagetable). Таблица страниц содержит начальные адреса f всех страничных рамок, вкоторых размещена программа. Физический адрес определяется путем сложенияначального адреса страничной рамки f и смещения Д.| | |Вторичная | |Таблица | |Основная || | |память | |страниц | |память || | | | |программы | | || | | | |А | | || | |стр. 0 | |1 | |стр. 0 || |программа |стр. 1 | |3 | | || |А |стр. 2 | |4 | |стр. 1 || | |стр. 3 | | |7 | |стр. 2 || | | | | | | || | | | | | | || | | | | | |стр. 3 | | Рисунок показывает, что страничная организация памяти полностьюисключает внешнюю фрагментацию. Внутренняя фрагментация не превышаетвеличины page_size-Q_Elem, где page_size — размер страничной рамки, аQ_Elem — минимальный адресуемый элемент основной памяти. Для ускорения вычисления физического адреса операцию суммированиязаменяют операцией конкатенации.|старшие разряды |младшие разряды | || |2n+|2n | |f || |1 | | | || | | || |2n-| |2n |Д || |1 | | | | На рисунке заштрихованы незаполненные нулевые разряды. Для того,чтобы операция конкатенации была возможна, необходимо, чтобы базовые адресастраничных рамок располагались только в старших разрядах (2n+1), аследующие — только младших разрядов (20, 21, 22). Например, при n=9 базовые адреса страничных рамок — это следующийряд: 512, 1024, 1536. Следовательно, размер страничной рамки равен 512байт. В современных операционных системах типичный размер страницысоставляет 2 Кб или 4 Кб. Каждая операционная система поддерживает свой собственный методработы с таблице страниц. Обычно за каждым процессом, находящимся восновной памяти, закреплена отдельная таблица страниц. В этом случаеуказатель на таблицу страниц хранится в PCB соответствующего процесса. 3.3.2. Аппаратная поддержка страничной организации памяти. ПРЕОБРАЗОВАНИЕ ЛОГИчЕСКОГО АДРЕСА В ФИЗИчЕСКИЕ ОСУЩЕСТВЛяЕТСя ДЛяКАЖДОГО АДРЕСА, ГЕНЕРИРУЕМОГО ПРОЦЕССОРОМ, ПОЭТОМУ чАСТО ДЛя УСКОРЕНИяЭТОГО ПРОЦЕССА ПРИМЕНяЮТСя АППАРАТНЫЕ МЕТОДЫ. НА РИСУНКЕ ПРИВЕДЕНА СХЕМА,ИЛЛЮСТРИРУЮЩАя МЕТОД, ИСПОЛЬЗУЮЩИЙ АССОЦИАТИВНЫЕ РЕГИСТРЫ (ASSOCIATIVEREGISTERS). Каждый ассоциативный регистр кроме операций чтения - записи можетобрабатывать операцию сравнения кода, поступающего на его вход с частьюкода, хранимого в регистре. Матрица ассоциативных регистров хранит частьтаблицы страниц. Номер страницы П подается одновременно на входы всехассоциативных регистров, которые параллельно выполняют операцию сравнения.На выходе матрицы ассоциативных регистров образуется начальный адресстраничной рамки 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




Нажми чтобы узнать.

Похожие:

Теория Операционных Систем iconНаименование дисциплины: «Операционные системы»
Изучение фундаментальных принципов проектирования и функционирования операционных систем, получение навыков практического использования...
Теория Операционных Систем icon1. 4 Особенности современного этапа развития операционных систем
Целью данной работы является погружение в небольшую историю операционных систем для того, чтобы понять, как применяются накопленные...
Теория Операционных Систем iconТехнический университет отчёт о лабораторной работе по предметам теоретические основы построения вычислительных систем метрология, стандартизация и сетрификация на тему применения операционных усилителей
Измерение основных параметров операционных усилителей и исследование работы инвертирующих и неинвертирующих схем их включения
Теория Операционных Систем iconПерспективные разработки Операционных Систем

Теория Операционных Систем iconСравнительная характеристика операционных систем семейства unix

Теория Операционных Систем iconРазвитие сетевых операционных систем. Windows 2000

Теория Операционных Систем iconПримерная рабочая программа по курсу «теория систем и системный анализ» Факультет экономический Профилирующая кафедра каф. Эмис 2009
«Теория систем и системного анализа», ее месте в области современной науки и роли в решении практических задач
Теория Операционных Систем iconПрактикум Тема Основы ip
Предмет работы: ip-адресация, настройка параметров ip операционных систем Windows и Unix, статическая маршрутизация
Теория Операционных Систем iconТехнический университет отчёт о лабораторной работе по предмету теоретические основы построения вычислительных систем на тему применения операционных усилителей

Теория Операционных Систем iconПримерная рабочая программа по курсу "Системное программное обеспечение" Факультет экономический
...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы