Структура процесса Pi для алгоритма булочной приведена ниже
while (some condition) {
choosing[i] = true;
number[i] = max(number[0], ..., number[n-1]) + 1;
choosing[i] = false;
for(j = 0; j < n; j++){
while(choosing[j]);
while(number[j] != 0 && (number[j],j) < (number[i],i));
}
critical section
number[i] = 0;
remainder section
}
20. Семафорные примитивы Дейкстры. Решение проблемы производителя и потребителя с помощью семафора
Семафор – целочисленная не отрицательная перемен доступ любого процесса к которой за исключением момента ее инициализац может осущ только через 2 атамарные операции P V(Proberen Verhogen) (привер\ увелич). При выполнении операции Р, над семафором, сначала проверяется его значение. Если оно больше нуля, то из него вычитают 1 и продолжается работа процесса. Если оно равно 0, то процесс переходит в состояние блокировки или ожидания до тех пор, пока значение не станет больше нуля. После этого из него вычит 1 и продолжается работа процесса. При выполнении операции V к значению семаф прибавляется 1. в момент инициализации, семафору может быть присвоено любое значение. Мьютекс (mutex)- двоичный семафор (только 0 и 1). Семафор принимает значение 0 и 1. 1-свободно, 0-занято. Операция V над мьют не увеличивает его значение не больше чем на 1.
21. Монитор Хоара как примитив синхронизации высокого уровня
Монитор – особый тип данных, обладающий внутренними переменными описывающ (определяющ) его состояние. Значение этих переменных из вне могут быть изменены только с помощью вызова функц методов этого монитора. Монитор представляет собой особые конструкции языка программ и компилятора обрабат методы мониторов специальным образом, добавляя к ним пролог и эпилог, таким образом реализуется взаимоисключение. Достоинство: вероятность ошибок программ значительно меньше. Условные переменные – если функц не может выполняться дальше, пока не наступит некоторое событие. Она выполняет операцию wait над условной переменной. При этом процесс блокируется и в монитор может выйти другой процесс. Когда событие происходит, другой процесс выполняет операц. c.signal от этого ранее заблокированный процесс становится активным. Если на этой перемен блокировалось несколько процессов, то активизируется только один из них. Условные переменные в отличии от семафора не помнят предысторию. Соответ, если произведена операция signal над условн перемен которые которые никто не заблокиров, то данный сигнал будет утерян и никем не использован. Сообщение – используется два примитива. Оба имеют скрытый механизм взаимоисключ и блокировка из чтения пустого буфера и запись в переполнен. Решение задачи произв\потреб с помощью сообщ тривиально.
22. Поняие виртуального и физического адреса.
Оперативная память может быть представлена в виде последовательности бит, каждый из которых имеет свой уникальный физический адрес. Адреса, используемые процессами и ядром не обязательно соответствуют физич. адресам. Можно сказать, что процесс выполняется с собственным виртуальным адресном пространстве. Механизм отображения виртуального адреса в физическом в современных компьютерных системах выполняется на аппаратном уровне. с помощью устройства управления памятью процессора. Современные процессоры поддерживают объединение адресного пространства: размера сегмента и области фиксированного размера- границы. При этом для каждого сегмента или может быть задано собственное отображение виртуальных адресов в физическом адресном пространстве. Размер виртуальной памяти может превышать размер физической памяти засчет вторичной памяти.
23. Назначение и функции подсистемы управления памятью
Для подзадач ОС ресурс памяти ограничен. Данные, которые не могут быть размещены в ОЗУ, располагаются во вторичной памяти, роль которой выполняют дисковые накопители . Распределение памяти в ОС осуществляет подсистема управления памятью, которая для многозадачных С обеспечивает: 1)выполнение задач объем которых > ОП 2)выполнение частично загруженных в ОП задач 3)размещение в ОП сразу нескольких задач 4) размещение задач в произвольном месте ОЗУ 5)размещение задачи в различных частях ОЗУ 6)совместное использование несколькими задачами одних и тех же областей ОЗУ
Функции системы управления памятью 1)учет свободной и занятой памяти 2)принятие решения о распределении памяти 3) выделение памяти процессу и учет информации о ее использовании 4) освобождение памяти и корректировка ее состояния.
При распределении ОЗУ возможны 2 метода 1) статистический (память назначается до выполнения программы) 2)динамический (во время выполнения программы)
24. Статическое распределения памяти.
При статическом распределении вся необходимая оперативная память выделяется процессу в момент его порождения. При этом память выделяется единым блоком необходимой длины, начало которого определяется базовым адресом. Программа пишется в адресах относительно начала блока, а физический адрес команды или операнда при выполнении программы формируется как сумма базового адреса блока и относительного адреса в блоке. Значение базового адреса устанавливается при загрузке программы в оперативную память. Так как в разных программах используются блоки разной длины, то при таком подходе возникает проблема фрагментации памяти, то есть возникают свободные участки памяти, которые невозможно без предварительного преобразования использовать для вычислительного процесса.
25. Динамическое распределение памяти: дисциплины диспетчеризации. Уплотнение.
При динамическом распределении памяти каждой программе в начальный момент выделяется лишь часть от всей необходимой ей памяти, а остальная часть выделяется по мере возникновения реальной потребности в ней.Такой подход базируется на следующих предпосылках.
Во-первых, при каждом конкретном исполнении в зависимости от исходных данных некоторые части программы (до 25% ее длины) вообще не используются. Следует стремиться к тому, чтобы эти фрагменты кода не загружались в ОП.
Во-вторых, исполнение программы характеризуется так называемым принципом локальности ссылок. Он подразумевает, что при исполнении программы в течение некоторого относительно малого интервала времени происходит обращение к памяти в пределах ограниченного диапазона адресов (как по коду программы, так и по данным). Следовательно, на протяжении этого времени нет необходимости хранить в ОП другие блоки программы.
При этом системные средства должны отслеживать возникновение требований на обращение к тем частям программы, которые в данный момент отсутствуют в ОЗУ, выделять этой программе необходимый блок памяти и помещать туда из внешнего ЗУ требуемую часть программы. Для этого может потребоваться предварительное перемещение некоторых блоков информации из ОЗУ во внешнюю память. Данные перемещения должны быть скрыты от пользователя и в наименьшей степени замедлять работу его программы.
Перемещение блоков информации из ОЗУ во внешнюю память с целью освобождения места для новой информации происходит обычно по одному из следующих алгоритмов:
LRU (least recently used) - наиболее давно не использовавшийся;
FIFO - самый давний по пребыванию в ОЗУ;
Random - случайным образом.
Динамическое распределение памяти тесно переплетается с понятием виртуальной памяти.
Уплотнение памяти.
Т.к. задачи появляются в разное время и различны их объемы, возможна сильная фрагментация( объем свободной памяти велик, но нельзя её выделить). Организуется уплотнение памяти – все вычисления приостанавливаются и диспетчер памяти корректирует списки, перемещая все разделы например в начало памяти.
Недостаток: время на уплотнение
Преимущество: можно выделить необходимый размер
26. Сегментная организация памяти. Дескриптор сегмента. Трансляция адресов, основанная на сегментации.
Понятие о сегментированной модели памяти
Память для программы делится на непрерывные области памяти, называемые сегментами.
Сегменты - это логические элементы программы.
Сама программа может обращаться только к данным, которые находятся в этих сегментах.
Сегмент представляет собой независимый, поддерживаемый на аппаратном уровне блок памяти.
Сегментация - механизм адресации, обеспечивающий существование нескольких независимых адресных пространств как в пределах одной задачи, так и в системе в целом для защиты задач от взаимного влияния.
Замечание. Программист может либо самостоятельно разбивать программу на фрагменты (сегменты), либо автоматизировать этот процесс и возложить его на систему программирования.
Для микропроцессоров Intel принят особый подход к управлению памятью. Каждая программа в общем случае может состоять из любого количества сегментов, но непосредственный доступ она имеет только к 3 основным сегментам: кода, данных и стека и к дополнительным сегментам данных (всего 3).
Операционная система (! а не сама программа) размещает сегменты программы в ОП по определенным физическим адресам, а значения этих адресов записывает в определенные места, в зависимости от режима работы микропроцессора:
в реальном режиме адреса помещаются непосредственно в сегментные регистры (cs, ds, ss, es, gs, fs);
в защищенном режиме - в специальную системную дескрипторную таблицу (Элементом дескрипторной таблицы является дескриптор сегмента. Каждый сегмент имеет дескриптор сегмента -8 байт. Существует три дескрипторные таблицы. Адрес каждой таблицы записывается в специальный системный регистр).
Для доступа к данным внутри сегмента обращение производится относительно начала сегмента линейно, т.е. начиная с 0 и заканчивая адресом, равным размеру сегмента. Этот адрес называется смещением (offset).
Таким образом, для обращения к конкретному физическому адресу ОП необходимо определить адрес начала сегмента и смещение внутри сегмента.