Разработка операционных систем

Разработка операционных систем

Дагестанский государственный университет.

Математический факультет.

Кафедра информатики и вычислительной техники.

Дипломная работа

на тему

«Разработка

операционных систем».

Руководитель:

Ханикалов Х.Б.

Выполнил:

студент 5 к. 4 гр.

Атаян А.П.

Махачкала 2000 г.

План работы:

Введение.

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

1.1. Понятие Процесс. Состояния процесса.

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

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

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

2.1. Критерии планирования процессора.

2.2. Стратегии планирования процессора.

2.2.1.Первый пришел - первый обслуживается FIFO. First come - first

served (FCFS).

2.2.2. Стратегия - наиболее короткая работа! SJF.

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

2.2.4. “Карусельная” стратегия планирования. RR-Round Robin.

2.2.5. Планирование с использованием многоуровневой

очереди.(Multilevel queue scheduling).

2.2.6. Программирование с использованием многоуровневой очереди с

обратными связями (multilevel feedback queue sheduling).

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

3.1. Своппинг. (swapping).

3.2. Смежное размещение процессов.

3.2.1. Однопрограммный режим.

3.2.2 Мультипрограммный режим с фиксированными границами.

3.2.3. Мультипрограммирование с переменными разделами.

(multiprogramming with a variable number of tasks (MVT).

3.2.4. Мультипрограммирование с переменными разделами и уплотнением

памяти.

3.2.5. Основные стратегии заполнения свободного раздела.

3.3. Страничная организация памяти.

3.3.1. Базовый метод.

3.3.2. Аппаратная поддержка страничной организации памяти.

3.4. Сегментная организация памяти.

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

3.4.2. Разделение сегмента между несколькими процессами.

3.4.3. Фрагментация.

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

4.1. Страничирование по запросу (demand paging).

4.2. Замещение страниц.

4.2.1. FIFO.

4.2.2. Оптимальный алгоритм.

4.2.3. LRU — алгоритм (least recently used).

5. Общие сведения.

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

5.2. Файловая система.

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

5.4. Межпроцессное взаимодействие.

5.5. Графический интерфейс пользователя.

5.6. Объектно-ориентированное ориентирование и операционные системы.

Заключение.

ВВЕДЕНИЕ.

Операционные системы, развиваясь вместе с ЭВМ, прошли длинный путь от

простейших программ в машинных кодах длинной в несколько килобайт до

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

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

обусловлен, главным образом, стремлением разработчиков ’украсить’

операционную систему, расширить ее возможности, добавить возможности,

изначально несвойственные операционным системам, а также сделать интерфейс

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

положительные, и отрицательные (усложнение настройки и программного

интерфейса при упрощении пользовательского).

На сегодняшний день на рынке программного обеспечения для IBM PC-

совместимых компьютеров сосуществуют несколько семейств операционных

систем. Однозадачные однопользовательские ОС MS-DOS и PC-DOS являются

самыми распространенными ввиду своей простоты и ’неприхотливости’, большую

роль здесь играет и то, что подавляющее большинство программ работает

именно под их управлением. MS-DOS и PC-DOS характеризуются минимальным

пользовательским и программным интерфейсами, в тоже время, работая со

всевозможными программными оболочками, интегрированными средами (такими как

Microsoft Windows или DESQview), создают комфортабельную среду для

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

ОС Microsoft Windows NT, ориентированная на работу в разнородных

сетях, высоконадежна, однако, это достигнуто за счет частичной потери

совместимости с MS-DOS.

Операционная система OS/2 стоит особняком: будучи полноправной

многозадачной операционной системой со своим оригинальным графическим

пользовательским и программным интерфейсами, она сохраняет совместимость с

MS-DOS и PC-DOS (начиная с версии WARP 3.0 и с Microsoft Windows).

ОС UNIX - одна из старейших и наиболее простых операционных систем,

изначально была рассчитана на разработку программ (для нее самой и не

только) на мини-ЭВМ и позволяла без больших затрат труда программиста

переносить программу из одной системы ЭВМ на другую. Неудивительно, что

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

UNIX, таких как XENIX, UNIXWARE, SUN-OS, LINUX, BSD.

Теоретически все эти ОС работают примерно одинаково. Рассмотрим теорию

операционных систем.

Операционная система - это программа, которая выполняет функции

посредника между пользователем и компьютером.

ОС, выполняя роль посредника, служит двум целям:

1. эффективно использовать компьютерные ресурсы.

1. создавать условия для эффективной работы пользователя

В качестве ресурсов компьютера обычно рассматривают:

1. время работы процессора

1. адресное пространство основной памяти

2. оборудование ввода – вывода

3. файлы, хранящиеся во внешней памяти

На рисунке приведены основные компоненты ОС как системы разделения

ресурсов.

Таким образом, основные компоненты ОС:

1. управление процессами (распределяет ресурс - процессорное время);

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

памяти);

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

вывода;

1. управление данными (распределяет ресурс - данные или файлы).

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

запуска программы первоначальной загрузки - Boot Track. Программа Boot

Track инициализирует основные аппаратные блоки компьютера и регистры

процессора (CPU), накопитель памяти, контроллеры периферийного

оборудования. Затем загружается ядро ОС, то есть Operating System Kernel.

Дальнейшее функционирование ОС осуществляется как реакция на события,

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

сигнализируется прерываниями - Interrupt. Источниками прерываний могут быть

как аппаратура (HardWare), так и программы (SoftWare).

Аппаратура “сообщает” о прерывании асинхронно (в любой момент

времени) путем пересылки в CPU через общую шину сигналов прерываний.

Программа “сообщает” о прерывании путем выполнения операции System Call.

Примеры событий, вызывающих прерывания:

1. попытка деления на 0

1. запрос на системное обслуживание

1. завершение операции ввода - вывода

1. неправильное обращение к памяти

Каждое прерывание обрабатывается соответственно обработчиком

прерываний (Interrupt handler), входящим в состав ОС.

Главные функции механизма прерываний — это:

1. распознавание или классификация прерываний

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

1. корректное возвращение к прерванной программе

Переход от прерываемой программы к обработчику и обратно должен

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

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

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

вектором прерываний (Interrupt vector) и хранится в начале адресного

пространства основной памяти (UNIX/MS DOS).

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

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

запоминается либо в памяти с прямым доступом либо в системном стеке —

System Stack.

Обычно запрещаются прерывания обработчика прерываний. Однако, в

некоторых ОС прерывания снабжаются приоритетами, то есть работа обработчика

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

прерывание с более высоким приоритетом.

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

ПРОЦЕСС — ЭТО ПРОГРАММНЫЙ МОДУЛЬ, ВЫПОЛНяЕМЫЙ В CPU. ОПЕРАЦИОННАя

СИСТЕМА КОНТРОЛИРУЕТ СЛЕДУЮЩУЮ ДЕяТЕЛЬНОСТЬ, СВяЗАННУЮ С ПРОЦЕССАМИ:

1. создание и удаление процессов

1. планирование процессов

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

1. коммуникация процессов

1. разрешение тупиковых ситуаций

1.1 Понятие Процесс. Состояния процесса.

НЕ СЛЕДУЕТ СМЕШИВАТЬ ПОНяТИя ПРОЦЕСС И ПРОГРАММА. ПРОГРАММА - ЭТО

ПЛАН ДЕЙСТВИЙ, А ПРОЦЕСС — ЭТО САМО ДЕЙСТВИЕ. ПОНяТИЕ ПРОЦЕСС ВКЛЮчАЕТ:

1. программный код

1. данные

1. содержимое стека

1. содержимое адресного и других регистров CPU.

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

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

выполняется несколько несовпадающих последовательностей команд. За время

существования процесс многократно изменяет свое состояние.

Различают следующие состояния процесса:

1. новый (new, процесс только что создан)

1. выполняемый (running, команды программы выполняются в CPU)

1. ожидающий (waiting, процесс ожидает завершения некоторого события, чаще

всего операции ввода - вывода)

1. готовый (ready, процесс ожидает освобождения CPU)

1. завершенный (terminated, процесс завершил свою работу)

Переход из одного состояния в другое не может выполняться

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

состояний процессора.

|Выполняемый |ожидаемый, готовый |Выполняемый | |

| | | | | |

| | | | | |

| | | | | |

|готовый |Выполняемый |готовый | |

| | | | | |

| | | | | |

| | | | | |

|ожидаемый, готовый |Выполняемый |ожидаемый | |

| | | |time | |

Каждый процесс представлен в операционной системе набором данных,

называемых process control block . В process control block процесс

описывается набором значений, параметров, характеризующих его текущее

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

процесса через компьютер.

На рисунке схематически показано, каким образом операционная система

использует process control block для переключения процессора с одного

процесса на другой.

| | |Заголово| | | | | | |

| | |к | | | | | | |

|Процессы | |первый | |PCB7 | |PCB8 | | |

|в | | | | | | | | |

|состоянии| | | | | | | | |

|“готовый”| |последни| | | | | | |

| | |й | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

|Очередь к| |первый | | | | | | |

|магнитной| | | | | | | | |

|ленте | |последни| | | | | | |

| | |й | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

|Очередь | |первый | |PCB3 | |PCB14 | |PCB6 |

|к | | | | | | | | |

|диску №1 | |последни| | | | | | |

| | |й | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

|Очередь к| |первый | |PCB5 | | | | |

|терминалу| | | | | | | | |

|№ 1 | |последни| | | | | | |

| | |й | | | | | | |

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

СИСТЕМА УПРАВЛЕНИя ПРОЦЕССАМИ ОБЕСПЕчИВАЕТ ПРОХОЖДЕНИЕ ПРОЦЕССА чЕРЕЗ

КОМПЬЮТЕР. В ЗАВИСИМОСТИ ОТ СОСТОяНИя ПРОЦЕССА ЕМУ ДОЛЖЕН БЫТЬ ПРЕДОСТАВИТЬ

ТОТ ИЛИ ИНОЙ РЕСУРС. НАПРИМЕР, НОВЫЙ ПРОЦЕСС НЕОБХОДИМО РАЗМЕСТИТЬ В

ОСНОВНОЙ ПАМяТИ, СЛЕДОВАТЕЛЬНО, ЕМУ НЕОБХОДИМО ВЫДЕЛИТЬ чАСТЬ АДРЕСНОГО

ПРОСТРАНСТВА. ПРОЦЕССУ В СОСТОяНИИ ГОТОВЫЙ ДОЛЖНО БЫТЬ ПРЕДОСТАВЛЕНО

ПРОЦЕССОРНОЕ ВРЕМя. ВЫПОЛНяЕМЫЙ ПРОЦЕСС МОЖЕТ ПОТРЕБОВАТЬ ОБОРУДОВАНИЕ

ВВОДА - ВЫВОДА И ДОСТУП К ФАЙЛУ.

Распределение процессов между имеющимися ресурсами носит название

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

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

ресурсов. Новые процессы находятся во входной очереди, часто называемой

очередью работ - заданий (job queue).

Входная очередь располагается во внешней памяти, во входной очереди

процессы ожидают освобождения ресурса — адресного пространства основной

памяти.

Готовые к выполнению процессы располагаются в основной памяти и

связаны очередью готовых процессов или 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). Например, программа вывода на печать

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

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

потребляется ассемблером.

Для того чтобы процесс - производитель и процесс - потребитель могли

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

производителем и потребляемым процессом - потребителем.

Буфер имеет фиксированные размеры, и, следовательно процессы могут

находиться в состоянии ожидания, когда:

1. буфер заполнен; ожидает процесс - производитель

2. буфер пуст; ожидает процесс - потребитель

Буфер может предоставляться и поддерживаться самой ОС, например с

помощью средств коммуникации процессов (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. Очевидно, что буфер пуст в том случае, если выполняется

это условие.

1. Буфер будет полностью заполнен, если выполняется условие

(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 - пустой оператор

Процесс - потребитель должен выполнять процедуру чтения из буфера типа

Repeat

while 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.

1. пропускная способность CPU throughput. Пропускная способность CPU может

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

1. время оборота (turnaround time) для некоторых процессов важным критерием

является полное время выполнения, то есть интервал от момента появления

процесса во входной очереди до момента его завершения. Это время названо

временем оборота и включает время ожидания во входной очереди, время

ожидания в очереди готовых процессов, время ожидания в очередях к

оборудованию, время выполнения в процессоре и время ввода - вывода.

1. время ожидания (waiting time). Под временем ожидания понимается

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

1. время отклика (response time) для сугубо интерактивных программ важным

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

попадания процесса во входную очередь до момента первого обращения к

терминалу.

Очевидно, что простейшая стратегия краткосрочного планировщика должна

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

способности, времени ожидания и времени отклика.

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

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

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

времени отклика.

2.2. Стратегии планирования процессора.

2.2.1.ПЕРВЫЙ ПРИШЕЛ - ПЕРВЫЙ ОБСЛУЖИВАЕТСя FIFO. FIRST COME -

FIRST SERVED (FCFS).

НА РИСУНКЕ СХЕМАТИчЕСКИ ПОКАЗАНО, КАКИМ ОБРАЗОМ ОПЕРАЦИОННАя СИСТЕМА

ИСПОЛЬЗУЕТ PROCESS CONTROL BLOCK ДЛя ПЕРЕКЛЮчЕНИя ПРОЦЕССОРА С ОДНОГО

ПРОЦЕССА НА ДРУГОЙ.

FCFS является наиболее простой стратегией планирования процессов и

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

всех других его запросил.

Когда процесс попадает в очередь готовых процессов, process control

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 мс)

|П4 |П1 |П3 |П2 |WT=7 мс |

|WT4=0 мс |WT1=3 мс |WT3=9 мс |WT2=16 мс | |

На рисунке приведена диаграмма Ганга, построенная в соответствии со

стратегией SJF.

Легко посчитать, что при использовании 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. требования к памяти

1. количество открытых файлов

1. отношение среднего времени ввода - вывода к среднему времени CPU и так

далее

Внешние факторы:

1. важность процесса

1. тип и величина файлов, используемых для оплаты

1. отделение, выполняющее работы и так далее

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

назначения приоритетов самой операционной системой, а внешние для

принудительного, с помощью оператора.

Главный недостаток приоритетного планирования заключается в

возможности блокирования на неопределенно долгое время низкоприоритетных

процессов.

Известен случай, когда в 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. FCFS

1. SJF

1. приоритетная

1. Round Robin

1. многоуровневая очередь

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

3.1. СВОППИНГ. (SWAPPING).

СВОППИНГОМ НАЗЫВАЕТСя МЕТОД УПРАВЛЕНИя ПАМяТЬЮ, ОСНОВАННЫЙ НА ТОМ,

чТО ВСЕ ПРОЦЕССЫ, УчАСТВУЮЩИЕ В МУЛЬТИПРОГРАММНОЙ ОБРАБОТКЕ, ХРАНяТСя ВО

ВНЕШНЕЙ ПАМяТИ.

Процесс, которому выделен CPU, временно перемещается в основную

память (swap in/roll in).

В случае прерывания работы процесса он перемещается обратно во

внешнюю память (swap out/roll out).

Замечание: при своппинге из основной памяти во внешнюю (и обратно)

перемещается вся программа, а не её отдельная часть.

Своппинг иногда используют при приоритетном планировании CPU. В этом

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

низкоприоритетные процессы перемещаются во внешнюю память.

Основное применение своппинг находит в системах разделения времени,

где он используется одновременно с Round Robin стратегией планирования CPU.

В начале каждого временного кванта блок управления памятью выгружает

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

загружает очередной выполненный процесс.

Метод своппинга влияет на величину временного кванта Round Robin

стратегии.

Пример.

1. пусть очередной загружаемый в память процесс имеет размер 100Кб.

1. диск позволяет читать данные со скоростью 1 Мб в секунду

1. следовательно, 100 Кб могут быть загружены за 100 мс.

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

потребуется 8 мс

1. таким образом, операция своппинг займет 108 мс, а общее время своппинга

- 216 мс.

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

существенно меньше времени счета. Следовательно, для рассмотренного примера

квант времени должен быть существенно больше, чем 216 мс. Ясно, что это

число значительно увеличится, если перемещаемый процесс имеет размер,

например, 1 Мб.

Недостаток “чистого” своппинга в больших потерях времени на загрузку

или выгрузку процессов. Поэтому в современных операционных системах

используется модифицированные варианты своппинга.

Так, например, во многих версиях операционной системы UNIX своппинг

включается только в том случае, когда количество процессов в памяти

становится слишком большим.

3.2. Смежное размещение процессов.

МЕТОДЫ РАЗМЕЩЕНИя ПРОЦЕССОВ В ОСНОВНОЙ ПАМяТИ ПО ОТНОШЕНИЮ К

РАСПОЛОЖЕНИЮ УчАСТКОВ ПАМяТИ, ВЫДЕЛЕННЫХ ДЛя ОДНОЙ И ТОЙ ЖЕ ПРОГРАММЫ ДЕЛяТ

НА ДВА КЛАССА. ПЕРВЫЙ — МЕТОД СМЕЖНОГО РАЗМЕЩЕНИя, А ВТОРОЙ — МЕТОД

НЕСМЕЖНОГО РАЗМЕЩЕНИя.

Смежное размещение является простейшим и предполагает, что в памяти,

начиная с некоторого начального адреса выделяется один непрерывный участок

адресного пространства.

при несмежном размещении программа разбивается на множество частей,

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

пространства.

3.2.1. Однопрограммный режим.

РИСУНОК ИЛЛЮСТРИРУЕТ СМЕЖНОЕ РАЗМЕЩЕНИЕ (CONTIGUOUS ALLOCATION) ОДНОЙ

ПРОГРАММЫ В ОСНОВНОЙ ПАМяТИ.

При смежном размещении размер загружаемой программы ограничивается

размером накопителя. Для того чтобы при смежном размещении загружать

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

оверлейных сегментов (overlay segments).

В программе, имеющей древовидную структуру, модули второго уровня

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

один из них.

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

оверлейных сегментов планирует сам программист.

В процессе выполнения программы все её адреса не должны быть меньше

числа а. В противном случае возможна запись какого-либо результата работы

программы (поверх операционной системы) и уничтожение некоторых её частей.

Защиту операционной системы в случае смежного размещения при

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

Во время работы прикладной программы все адреса, генерируемые CPU,

сравниваются с содержимым регистра границы. Если генерируется адрес меньше

числа а, работа программы прерывается.

3.2.2 Мультипрограммный режим с ФИКСИРОВАННЫМИ границами.

МУЛЬТИПРОГРАММИРОВАНИЕ С ФИКСИРОВАННЫМИ РАЗДЕЛАМИ (MULTIPROGRAMMING

WITH A FIXED NUMBER OF TASKS) ПРЕДПОЛАГАЕТ РАЗДЕЛЕНИЕ АДРЕСНОГО

ПРОСТРАНСТВА НА РяД РАЗДЕЛОВ ФИКСИРОВАННОГО РАЗДЕЛА. В КАЖДОМ РАЗДЕЛЕ

Страницы: 1, 2