Шпаргалка по "Операционным системам"

3. Строгое чередование

Вводится переменная, которая идентифицирует номер процесса, который должен войти в КС.

shared int turn = 0;

while (1){

wile (turn != pid);

КС

turn=1-turn;

}

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

18. Способы реализации  взаимоисключения: алгоритм  Деккера, операция  «Проверка и установка» (команда TSL)

1. Алгоритм Деккера

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

shared int turn = 0;

while (1){

ready[pid] = 1;

turn = 1-pid;

while (ready[1-pid] && turn == 1-pid);

КС

ready[pid] = 0;

}

Процесс может  войти в КС только, если флаг готовности другого процесса равен 0 и значение переменной turn = идентификатору текущего процесса.

Доказательство:

Представим, что 2 процесса одновременно находятся  в КС. Значит, флаги готовности у  них обоих равны 1, значит, условие  цикла while у обоих процессов не выполнялось из-за второй части этого условия, т.е. для каждого процесса переменная turn равна идентификатору этого процесса, чего быть не может, что и требовалось доказать.

2. операция «Проверка  и установка» (команда TSL).

Алгоритм Деккера, расширенный на n процессов.

int Test and Set (int *target)

{int tmp = *target; *target = 1;

Return temp;}

shared int lock = 0;

while (1){

while (Test and Set(&lock));

КС

Lock = 0;}. 
 
 
 
 
 
 
 
 
 
 
 
 

19. Примитивы межпроцессного взаимодействия. Решение проблемы производителя и потребителя с использованием примитивов межпроцессорного взаимодействия

Простейшими примитивами  являются sleep  и wakeup. Sleep - системный запрос,  в результате которого процесс блокируется пока его не запустит другой процесс.  Wakeup – в качестве параметра содержит процесс, который следует запустить. Проблема состоит в следующем 2 процесса используют буфер ограниченного размера. Один -производитель помещает данные в этот буфер. Трудность возникает когда производитель хочет поместить в буфер очередную информацию и обнаружив, что он полон и будет ожидать. Другой потребитель будет ожидать пока буфер не будет заполнен в случае если захочет забрать из буфера данные, а буфер пуст.

Для решения  этой проблемы вводим переменную (count)  для отслеживания колич-ва элементов в буфере (N).  Если соunt = N, то производитель уходит в состояние ожидания, в противном случае данные помещаются в буфер и count увеличивается. При соunt =0, потребитель уходит в состояние ожидания. В противном случае оттуда извлекается информация и значение count уменьшается. Производитель может активизировать потребителя с помощью вызова Wakeup в тот момент, когда потребитель не находится в состоянии ожидания.

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

shared enum {false, true} choosing[n];

shared int number[n];

Изначально  элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения

(a,b) < (c,d), если a < c или если a == c и b < d

max(a0, a1, ...., an) — это число k такое, что k >= ai для всех i = 0, ...,n

Структура процесса 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. Сегментная организация памяти. Дескриптор сегмента. Трансляция адресов, основанная на сегментации. 

Понятие о сегментированной модели памяти 

Память для  программы делится на непрерывные  области памяти, называемые  сегментами.

Сегменты - это  логические элементы программы.

Сама программа  может обращаться только к данным, которые находятся в этих сегментах. 

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