Средство межпроцессорных взаимодействий IPC 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Средство межпроцессорных взаимодействий IPC



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

1. средства передачи данных: файлы, общие сегменты, каналы, очереди

2. средства синхронизации: события, сигналы, мютексы, семафоры, критические секции

Общие сегменты – сегменты памяти, в которых все взаимодействующие процессы имеют доступ???

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

 

Каналы

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

И на эту область есть 2 указателя: указатель чтения и указатель записи.

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

Существует 2 случая, когда УЧ=УЗ:

1) канал пустой

2) канал переполнен. При попытке записи фиксируется ошибка.

FIFO

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

Именованный канал создается с помощью функции p=CreateNPipe(имя, размер области отводимой под канал). Получить доступ к именованному каналу из других процессов можно с помощью функции p=OpenMPipe(имя), в которой указывается имя существующего канала. Функция также возвращает описатель канала - пару р=(УЧ, УЗ).

Неименованный канал создается с помощью функции p=MakePipe(e), в котором указывается размер области, выделяемый под неименованный канал. Функция также возвращает описатель канала.

Операции чтения и записи в каналах осуществляются с помощью операторов функций ввода-вывода для последовательности файлов Read (УЧ), Write(УЗ).

При записи по УЗ осуществляется запись, после чего УЗ передвигается на начало свободного пространства.

Для завершения работы с каналом необходимо закрыть указатели связи с каналом Close(УЧ, УЗ).

 

Очередь

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

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

2) Очередь поддерживает 3 дисциплины: FIFO, LIFO, приоритет

3) Дисциплина задается при создании очереди и в середине работы изменяться не может.

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

Сервер может:

1) создать очередь q=CreateQueue(имя, l –размер, D-дисциплина)

2) ReadQueue(q)

3) PeekQueue(q) – просмотреть сообщения без удаления

4) QuergQueue(q) – подсчитать количество сообщений

5) PurgeQueue(q) – очистить очередь

6) Close(q) – очистить очередь (уничтожение)

Клиент может:

1) получить доступ к очереди по заданному имени q=OpenQueue(имя)

2) записать сообщения в очередь WriteQueue(q)

3) подсчитать количество элементов в очереди QueryQueue(q)

4) закрыть очередь (но не уничтожать данные) Close(q)

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

 

Средства синхронизации

Делятся на:

- средства сигнализации, т е извещения о наступлении какого-либо события (события, сигналы)

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

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

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

Чтобы избежать взаимных блокировок вместе с главным правилом используют одно из 2х дополнительных:

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

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

События – объект синхронизации, который может находиться в одном из 2х состояний: Set и Clear.

Для работы с событием есть набор функций:

E=CreateEvent(имя[,н.с.])

e=OpenEvent(имя)

SetEvent(e) – установление в заданный режим

ClearEvent(e)

WaitEvent(e) – переводит вызвавший ее поток в ожидание установки события, указанного в качестве параметра, пока она не переведет в установленное состояние

PulseEvent(e) – перевод события в установленное состояние и тут же сбрасывает состояние

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

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

В Unix существуют 2 сигнала, которые ОС может посылать процессам для их завершения: SIGTERM, SIGKILL.

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

Мютекс (mutex) представляет из себя объект синхронизации, который может находиться в одном из 2х состояний: захваченном и свободном. Мютекс создается с помощью специальной функции: m=CreateMutex(имя), в которой в качестве параметров указывается имя, присваемое мютексу. Функция возвращает описатель мютекса, который затем используется в функциях работы с мютексом.

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

1) RequestMutex(m) – захват мютекса: если на момент вызова функции мютекс с описателем m был в свободном состоянии, функция переводит его в захваченное и возвращает управление вызвавшему ее потоку. Если же на момент вызова функции мютекс m был в захваченном состоянии, то функция переводит вызвавший ее поток в состояние ожидания до тех пор, пока мютекс не освободится, после чего переводит его в занятое состояние и возвращает управление.

2) ReleaseMutex(m) – освобождение мютекса – освобождает мютекс и переводит его в свободное состояние

3) Close(m) – завершает работу с мютексом. Если Close вызывается в том же процессе, где мютекс был создан, то мютекс уничтожается.

Т о с помощью мютекса очень удобно управлять доступом к ПИРам

Связать ПИР1-m1

...

RequestMutex(m1)

//работа с ПИР

ReleaseMutex(m1)

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

Семафор переводится в захваченное состояние, когда счетчик становится = 0 и в свободное, когда >0. Т о семафор может допустить к одновременной работе с ресурсом столько потоков, сколько указано в начальном значении его счетчика. При значении счетчика = 1, семафор эквивалентен мютексу. Семафор удобен для использования с многоканальными системами массового обслуживания. При этом число каналов задает начальное значение счетчика.

Семафор создается: s=CreateSemaphore(имя, начально значение счетчика m)

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

Получить доступ к семафору из другого процесса можно с помощью функции: s=OpenSemaphore(имя)

Для работы:

- RequestSemaphore(s) – вычитает 1цу из текущего значения счетчика. Если после этого счетчик остался положительным, то функция возвращает управления вызвавшему ее потоку. Если же значение счетчика стало равным 0, функция переводит вызвавший ее поток в состояние ожидания, пока семафор не перейдет в свободное состояние.

- ReleaseSemaphore(s) – увеличивает на 1 счетчик

- Close(s) – завершает работу с семафором или уничтожает семафор.

В Windows нет специальных функций захвата семафора и захвата мютекса. Вместо них используются стандартные функции ожидания объектов синхронизации:

- WaitforSingleObject(описатель)

- WaitforMultipleObject(описатель1, описатель2,..)

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

2я функция выводит поток из состояния ожидания при установке хотя бы одного из перечисленных объектов синхронизации.

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

Критическая секция – участок кода программы, ограниченный 2мя специальными функциями:

EnterCriticalSection

//Работа с ПИР

LeaveCriticalSection

Поток, выполнивший функцию EnterCriticalSection, считается вошедшим в критическую секцию, а выполнивший LeaveCriticalSection – вышедшим. В каждый конкретный момент времени только 1 поток процесса может находиться внутри критической секции. Если 2й поток попытается выполнить функцию Enter, он тут же будет переведен в состояние ожидания до тех пор, пока 1й поток не покинет критическую секцию.

 

Планирование и диспетчеризация потоков(процессов)

Планирование решает 2 следующие задачи:

1) определение момента переключения контекста

2) определение претендента на следующее выполнение

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

Диспетчеризация реализует решение, принятое на этапе планирования и выполняет следующие действия:

1) сохраняет контекст текущей задачи

2) восстанавливает контекст следующей

3) передает в процессор??? задачи

Многозадачность может быть вытесняющей и невытесняющей.

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

В большинстве ОС планирование и диспетчеризация выполняются 1м модулем – планировщик(диспетчер). Алгоритмы планирования, т е выбора следующего претендента на выполнение отличаются в зависимости от типа системы:

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

Этот алгоритм хорош для критерия пропускной способности(максимум задач выполняемых в 1цу времени).

2. Для системы разделения времени - кратчайшая задача в 1ю очередь. Алгоритм предполагает, что с каждой задачей связана некоторая оценка времени ее выполнения. (рис)

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

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

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

Алгоритмы планирования для систем разделения:

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

1) Циклическое планирование

Рисунок 2

При циклическом планировании все задачи в системе выстраиваются в очередь обычно в порядке своего поступления. Время центрального процессора выделяется квантами фиксированной длины. Сначала квант времени процессора получает 1я готовая задача из очереди, после того как выделенный ей план завершится, задача перемещается в конец очереди, а квант времени центрального процессора выделяет следующей готовой задаче из очереди. И т.д. Таким образом все задачи по кругу периодически получают время центрального процессора. Именно поэтому алгоритм называется циклическим. Поскольку размер кванта времени фиксирован, время ответа в этом методе пропорционально количеству выполняемых одновременно задач. Выбор размера кванта времени также представляет из себя не простую задачу. Большой квант времени увеличивает время ответа, с другой стороны – небольшой, слишком маленький квант времени приведёт к частому переключению задач, а переключение задач связано с восстановлением и сохранением процесса (контекста), на что также тратится время процессора. Поэтому если квант времени будет соизмерим со временем переключения контекста, то 50% ЦП тратится на переключение. Реально на практике в различных системах квант времени центрального процессора выбирают в размерах 30-70мл.сек.

 

2) Приоритетное планирование:

При приоритетном планировании всем выполняемым задачам назначаются веса, называемые приоритетами. И время центрального процессора выделяется задачам, соответственно им приоритетам. При реализации приоритетного планирования обычно имеется не одна, а несколько очередей, готовых задать по одной очереди на каждый уровень приоритета. И поиск претендента на следующее выполнение состоит в просмотре очередей готовых задач, начиная с самой приоритетной очереди. Такой порядок просмотра очередей гарантирует, что в первую очередь время центрального процессора будет выделяться самым приоритетным задачам. Если существует несколько готовых задач с одинаковым приоритетом, то они располагаются в очереди в порядке их поступления. В этом случае задача, появившаяся раньше будет пользоваться преимуществом. Такое планирование обладает существенным недостатком: высокоприоритетные задачи могут полностью заблокировать выполнение менее приоритетных задач. Поэтому при приоритетном планировании часто применяют дополнительные правила, позволяющие сделать распределение времени менее жёстким и более справедливым. Одним из таких дополнительных правил является введение динамических приоритетов. Приоритеты, не изменяющиеся за время выполнения задач называют статическими. Приоритеты, которые могут изменяться во время выполнения задачи называют динамическими. При использовании динамических приоритетов, планировщик может временно повышать приоритет задачи, если она долго не получала доступ к процессору ил наоборот – понижать приоритет, если задача слишком долго занимает центральный процессор. Для того, чтобы можно было к различным задачам применять различные правила, уровни приоритетов в современных системах обычно подразделяются на классы. WinNT, 05/2 использует приоритеты:

1) класс реального времени,

2) высокоприоритетный класс,

3) регулярный(нормальный) класс,

4) фоновый класс.

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

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

Задачи фонового класса выполняются только тогда, когда нет готовых задач из других классов приоритетов. По умолчанию, Windows запускает задачи в регулярном классе приоритетов. В Windows всего существует 32 уровней приоритетов, для прикладных задач используются уровни с 1-31. Явно задать приоритет нельзя, можно только отнести свою задачу к тому или другому приоритету. При этом задачи, отнесённые к классу реального времени запускаются с начальным уровнем приоритета=24, высокоприоритетными = 13, регулярными = 7-8, фоновыми = 4. В процессе выполнения задачи могут менять свой приоритет относительно базового в пределах ±2.

3) Гарантированное планирование:

При гарантированном планировании время центрального процессора также как и при циклическом планировании периодически выделяется всем задачам квантами, при этом размер кванта изменяется в зависимости от количества одновременно выполняемых задач. 1/n сек(мсек) Таким образом теоретически время ответа сохраняется примерно одинаковым для любого количества задач.

Системы реального времени.

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

1)Расписание: Для простых систем управления(систем измерения) можно заранее составить расписание и строго в соответствии с этим расписанием запускать нужные задачи.

2) Для периодически запускаемых задач очень часто используют алгоритм планирования, который называется RMS (Rate Monotonic Schedule): Всем периодически запускаемым задачам назначается приоритет, пропорциональный количеству их запусков в единицу времени, то есть чем выше приоритет, тем чаще запускается задача. И в соответствии с этими приоритетами, задачи запускаются на выполнение. Однако не всякая система задач может быть планирована по этому алгоритму, необходимо выполнение следующего условия:

≤ 1

 

n- кол-во периодически запускаемых задач; Ci- время выполнения i-той задачи при каждом запуске, pi – частота перезапускания задач.

3) Используется для задач с определённом сроком завершения EDF (задача с ближайшим сроком выполнения в 1ю очередь).

 

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

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

1) КЭШ, который имеет высоко быстродействие, высокую стоимость и маленький объём, энергозависим.

2) ОЗУ – обладает средним быстродействием, средней стоимостью, имеет достаточный объём и память энергозависима.

3) Диск – низкое быстродействие, низкая стоимость, большой объём, память на диске энергонезависима.

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

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

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

 

 

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

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

Для систем пакетной обработки такое??? было еще допустимо. С появлением??? с разделением времени??? памяти???

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

Так появились системы второго типа.

 

2) Системы управления памяти с вытеснением процессов на диск. Используется загрузка и выгрузка данных на диск и эта загрузка-выгрузка осуществляется на уровне процессов. Такой процесс называется swapping.

Обычно адресное пространство процесса имеет следующий формат:

 

 

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

 

Такая структура называется структурой перекрытия или структурой Оверлея. Согласно этой структуре в памяти всегда находится главный модуль m0 плюс одна из следующих веточек: m1+m2+m3

m1+m2+m4

m20+m10+m11

m10+m12

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

 

3) Система управления памятью, осуществляющая загрузку и выгрузку на уровни страниц. Система со страничной организацией памяти. Paging

Помимо распределения данных по иерархии памяти все эти системы и простые и более сложные осуществляют учёт свободного и занятого пространства памяти.

1) Так появились системы со страничной организацией памяти. В них всё адресное пространство процесса разбивается на страницы фиксированной длины, и этим страницам выделяется страницы физической памяти pageframe. Какой страницы адресного пространства процесса выделена конкретная страница физической памяти, задаётся специальная структура данных – таблица страниц. Для процессоров где общий объём памяти 4гб имеется каталог, который содержит 1024 дескриптора, которые ссылаются на таблицу страниц. См 2ую лекцию. (рис)

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

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

 

 

 

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

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

 

Алгоритмы замещения страниц

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

  1. алгоритм NRU (near recently used - неиспользуемая в последнее время страница). Т е в качестве претендента на выгрузку является страница, которая некоторое время не используется. Этот алгоритм использует биты A и D дескриптора страницы. NRU при определении претендента на выгрузку, просматривает дескрипторы всех расположенных в памяти страниц и разделяет их на 4 класса: 0й A=0,D=0 – страница не использовались и не модифицировались; 1й A=0,D=1 – не использовалась, но была модифицирована, 2й А=1,D=0; 3-й А=1, D=1. NRU просматривает в таком порядке и выбирает 1ю встретившуюся страницу из 1го не пустого класса. Этот алгоритм имеет наибольшее распространение.
  2. FIFO В се страницы при загрузке их в память помещаются в очередь. претендентом на выгрузку является страница в вершине очереди(1я в очереди),страница которая дольше всех остальных находится в памяти. Алгоритм легко реализуется. Недостаток в том что не используется…
  3. LRU (Least recently used – давно не использовавшаяся страница). Этот алгоритм дает самые хорошие результаты, но для его реализации необходимо ввести подсчет времени неиспользования страницы или хотя бы строить оценку этого времени. Без специальной аппаратной поддержки это реализовать очень сложно, поэтому LRU используется довольно редко, в основном в тех системах, где такая поддержка реализована. Например, некоторые процессоры введут специальный счетчик выполненных с момента последней загрузки команд. Этот счетчик в таких системах и используется для оценки времени неиспользования страницы. Для этого в дескрипторе страницы имеется специальное поле, в которое каждый раз при обращении к этой странице копируется счетчик выполненных команд. При определении претендента на выгрузку LRU просматривает это поле у всех расположенных в памяти страниц и выбирает страницу с наименьшим значением этого поля.

 



Поделиться:


Последнее изменение этой страницы: 2017-02-06; просмотров: 237; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.222.82.119 (0.107 с.)