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

Идеал алгоритм замещение страниц

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

Но этот алгоритм не осуществим, т.к. нельзя знать какую страницу, когда запросят.Алгоритм NRU

Алгоритм NRU (Not Recently Used - не использовавшаяся в последнее время страница)

Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц.Алгоритм FIFO (первая прибыла - первая выгружена)

Не достаток заключается в том, что есть высокая вероятность того, что часто запрашива страница мож быть выгружена. Алгоритм "2-ая попытка" Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.

Алгоритм "часы"

Чтобы избежать перемещения страниц по списку, можно использовать указатель, который перемещается по списку. Алгоритм LRU (Least Recently Used - использовавшаяся реже всего)

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

 

 

7)

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

Когда это важно

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

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

При вызове функций стандартных системных библиотек (например, функций API).

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

8)

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

Эта ошибка случается по двум причинам. 1)переполнения стека— излишне глубокая или бесконечная рекурсия. Простейший пример бесконечной рекурсии на Си:

int foo() {

return foo();

}

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

Многие языки делают оптимизацию, именуемую «хвостовая рекурсия». Рекурсия, находящаяся в конце функции, превращается в цикли не расходует стека.

2) одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке.Пример на Си: int foo() {

double x[1000000];

}

Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.

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

9)

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

При сегмент организац вся виртуал память, использ програм, разбивается на части, называемые сегментами. Это разбиение выполняется либо самим программистом либо компилятором использ языка программир. Размеры сегментов могут быть различ, но в пределах максимал размера, использ в данной архитектуре. Разбиение обычно производится на логически осмысленные части, такие, как сегмент данных, сегмент кода, сегмент стека и т.п. Бол програм может содерж несколько сегментов 1 типа, например, несколько сегментов кода или данных.

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

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

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

 

Селектор сегмента используется для доступа к соответствующей записи таблицы сегментов.

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

В некоторых системах сегменты могут находиться в одном из двух состояний:

·фиксированный сегмент не должен перемещаться в памяти;

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

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

10)Контекст выполнения процесса.

Каждому процс соответс контекст, в котором он выполняется. Этот контекст включает содерж пользоват адрес простр-ва - пользовательский контекст, содержимое аппаратных регистров - регистровый контекст, а также структуры данных ядра связанные с этим процессом. Контекст процесса сист уровня в UN сост из "статич" и "динамич" частей. У кажд процесса имеется 1 статич часть контекста сист уровня и перемен число динамич частей. Статич часть контекста процс сист уровня включает следующее: 1 Описатель процесса, т.е. элемент таблицы описателей существующих в системе процессов (включ инф сост процс; идентификатор процс; физ адрес в сонов или внеш памяти; идентификаторы пользоват) 2 U-область (u-area), индивид для каждого процс обл прост-ва ядра, обладающа тем св-м, что хотя u-область каждого процесса располаг в отдел месте физич памяти, u-области всех процс имеют один и тот же виртуал адрес в адресном пр-ве ядра.(содерж указатель на описатель процесса; идентификаторы пользоват; параметры сист вызова;

Рез-ты системного вызова) Динамич часть контекста проса - это 1 или неск стеков, которые использ процессом при его выполн в режиме ядра.Число яд стеков процс соответст числу уровней прерывания, поддерж конкрет аппаратурой.

 

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

Планирование - это раздел вычислит ресурсов сист-ы между процессами и потоками.

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

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

В-3, когда проц блокируется на операции ввода-вывода, семафоре, или по др причине, необход выбрать и запустить др процесс. Иногда причина блокировки может повлиять на выбор. Например, если А —

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

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

Задачи 17. Алгоритм пларирования FCFS

«Первым пришел — первым обслужен»

Проц-ам предоставл доступ к процессору в том порядке, в кот они его запрашивают. Чаще всего формируется един очередь ждущих проц-ов. Как только появл перв задача, она немедленно запускается и работает столько, сколько необход. Остальн задачи ставятся в конец очереди. Когда текущ проц блокируется, запускается следующ в очереди, а когда блокировка снимается, проц попа­дает в конец очереди.

Алгоритм пларирования SJF

«Кратчайшая задача — первая»

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