1. Простой алгоритм обслуживания.
Различаются два типа состояния готовности: низкоприоритетное и высокоприоритетное. Процессу присваивается низкоприоритетное состояние, если он полностью использовал выделенный ему предшествующий квант времени, и высокоприоритетное состояние, если он из состояния ожидания переходит в состояние готовности. Для этого случая могут быть применены следующие дисциплины обслуживания:
• выбор на обслуживание процесса из очереди высокоприоритетных готовых процессов.
• если эта очередь пуста, выбор процесса из очереди низкоприоритетных процессов.
2. Альтернативный алгоритм.
Может использоваться в системах с разделением времени и страничной организацией памяти.
Состояние ожидания может быть трех видов:
• блокировка по обмену с терминалами;
• блокировка по обмену с накопителями;
• блокировка по обмену с внешней страничной памятью.
Готовые процессы подразделяются на три группы:
• низкоприоритетные процессы с преимущественным счетом;
• высокоприоритетные процессы с преимущественным вв/выв.;
• среднеприоритетные процессы с преимущественным вв/выв.
Алгоритм обслуживания состоит в выборе процесса из очереди высокоприоритетных готовых процессов, если очередь пуста - из более низких очередей по приоритету.
При обращении к системным вызовам, поддерживаемым ОС, параметры помешаются в строго определенные места, такие как регистры или стек, а затем выполняется специальная команда прерывания, известная как вызов ядра или вызов супервизора. Эта команда переключает машину из режима пользователя в режим ядра, называемый также режимом супервизора, и передает управление ОС. Затем ОС проверяет параметры вызова, для того чтобы определить, какой системный вызов должен быть выполнен. После этого ОС индексирует таблицу, содержащую ссылки на процедуры, и вызывает соответствующую процедуру.
В этот период были разработаны системы с разделением времени (РВ), предоставляющие пользователям возможность непосредственно взаимодействовать с компьютером при помощи терминалов телетайпного типа (электронная пишущая машинка, имеющая интерфейс с ЭВМ), а в последующем и с помощью дисплея. При работе с такими ОС используется диалоговый или интерактивный режим. Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Пользователь вводит запрос, который обрабатывается и ответ выводится на терминал, что позволяет увеличить эффективность и удобство работы пользователя. Пакетный режим обеспечивал увеличение пропускной способности и максимальную загрузку процессора, отлучая пользователя от ЭВМ, в то время как в режиме разделения времени (РРВ) каждый пользователь имеет непосредственный доступ к ЭВМ через свой терминал. Суть разделения времени максимально проста. Каждой программе, готовой к исполнению, для работы выделяется фиксированный, заранее определенный интервал времени, называемый квантом. Программа в течение одного кванта может быть не выполнена до конца, тогда она прерывается в момент окончания кванта и помещается в конец очереди. Из начала очереди извлекается другая программа, которой планируется фиксированный интервал. При этом ни один из пользователей, работающих за дисплеем, параллельно друг с другом, никак не ощущает, что процессор мультиплексируется несколькими программами.
К этому же периоду относится появление первых систем реального времени (СРВ), в которых ЭВМ применяется для управления техническими объектами, такими, например, как станок, спутник, научная экспериментальная установка или технологическими процессами, такими, как гальваническая линия, доменный процесс и т.п. Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная программа, управляющая объектом, в противном случае может произойти авария: спутник сойдет с орбиты, экспериментальные данные могут быть потеряны, толщина гальванического покрытия не будет соответствовать норме. Системное программное обеспечение (СПО) ОС этого периода решало множество проблем, связанных с защитой данных и результатов работы различных программ, защитой данных в оперативной памяти и распределением устройств. Кроме того, ОС должна управлять новыми устройствами, входящими в состав аппаратного обеспечения. Для решения этих задач системное программное обеспечение сформировалось в сложную систему, требующую для реализации своих возможностей значительных вычислительных ресурсов.
ОС третьего поколения (70-80 г.г.) были многорежимными системами, обеспечивающими пакетную обработку, разделение времени, режим реального времени и мультипроцессорный режим. Они были громоздкими, дорогостоящими (монстры операционных систем). Например, фирме IBM разработка ОС/360 стоила 6 млрд. долларов, что соизмеримо с затратами американской программы NASA высадки человека на Луне. Такие ОС, будучи прослойкой, между пользователем и аппаратурой ЭВМ, привели к значительному усложнению вычислительной обстановки. Для выполнения простейшей программы необходимо было изучать сложные языки управления заданием (JCL – Job Control Language). К этому периоду относится появление вытесняющей многозадачности (Preemptive scheduling), и использование концепции баз данных для хранения больших объемов информации для организации распределенной обработки. Программисты перестали использовать перфокарты и магнитные ленты для хранения своих данных. Вводится приоритетное планирование (Prioritized scheduling) и выделение квот на использование ограниченных ресурсов компьютеров (процессорного времени, дисковой памяти, физической (оперативной) памяти). При использовании компьютеров широкое распространение получила концепция распределения времени (time sharing), но ограниченность ресурсов приводила к перегрузке компьютеров и к неприемлемому времени ожидания ответа или результатов работы. Программистам приходилось компенсировать это неудобство работой в ночное время.
20 Семафоры, счетчики событий
Синхронизация задач с помощью семафоров
Семафоры Дейкстры
Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые Р и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:
V(S) или wait(s): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.
P(S) или signal(s): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий Р-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.
В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция Р заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией Р (сравните эти операции с системными функциями WAIT и POST).
Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи.
Введем два семафора: е - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор Ь, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:
// Глобальные переменные
#define N 256
int e = N, f = 0, b = 1;
void Writer ()
{
while(l)
{
PrepareNextRecord(); /* подготовка новой записи */
P(e); /* Уменьшить число свободных буферов, если они есть в противном случае - ждать, пока они освободятся */
Р(Ь); /* Вход в критическую секцию */
AddToBuffer(); /* Добавить новую запись в буфер */
V(b); /* Выход из критической секции */
V(f); /* Увеличить число занятых буферов */
}
}
void Reader ()
{
while(l)
{
P(f); /* Уменьшить число занятых буферов, если они есть в противном случае ждать, пока они появятся
Р(Ь); /* Вход в критическую секцию
GetFromBuffer(); /* Взять запись из буфера
V(b); /* Выход из критической секции
V(e); /* Увеличить число свободных буферов
ProcessRecord(); /* Обработать запись
}
}
24. Проблема «спящего брадобрея» (о паркмахерской)
Описание задачи
В парикмахерской есть один брадобрей, его кресло и n стульев для посетителей. Если желающих побриться нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, а брадобрей спит, клиент будит его. Если же брадобрей занят, то клиент садится на стул или уходит, если все стулья заняты. Необходимо запрограммировать брадобрея и посетителей.
Предлагаемое решение:
Используются три семафора:
Customers – для подсчета ожидающих посетителей (без того, который уже стрижется);
Barbers – количество простаивающих в ожидании брадобреев (0 или 1);
Mutex – для реализации взаимного исключения.
Также используется переменная waiting для подсчета ожидающих посетителей. Она является копией customers и нужна для того, чтобы заглядывающий клиент мог сосчитать количество занятых стульев и уйти, если мест уже нет. При отсутствии неблокирующего ожидания на семафоре копия customers – единственный выход.
Решение
#define CHAIRS 5 //количество стульев
typedef int semaphore;
semaphore customers=0;
semaphore barbers=0;
semaphore mutex=1;
int waiting=0;
void barber(void)
{
while(1)
{
wait(customers); //ждать посетителей
wait(mutex); //вход в CS
waiting--; //ждет уже на одного меньше
signal(barbers); // на одного больше брадобрея доступно
release (mutex); // выход из СS
cut_hair(); //обслуживание – вне CS
}
}
void customer(void)
{
wait(mutex); //вход в CS
if(waiting<CHAIRS)
{
//если есть места
waiting++; //ожидающих на 1 больше
signal(customers); //разбудить брадобрея, если надо
release(mutex); //выход из CS
wait(barbers); //ждать, пока брадобрей не освободится
get_haircut(); //постричься
}
else release(mutex); //много посетителей – уйти, освободить mutex
}
Приходя, клиент запрашивает mutex; если придут сразу два клиента или более, только один из них сможет выполнять процедуру customer.
Если свободный стул есть, посетитель увеличивает число ожидающих и активизирует брадобрея. Но начать стричься он не может, пока брадобрей занят. Брадобрей, приходя на работу, сначала блокируется на семафоре customers. Когда придет клиент и активизирует его, брадобрей захватит mutex и уменьшит число ожидающих, усадив одного клиента в кресло.
Замечание: не смотря на отсутствие передачи данных между процессами, рассмотренные задачи являются задачами межпроцессорного взаимодействия, т.к. они требуют синхронизации действий процессов.
Это в некоторой степени относится и к следующей задаче.
29. Обнаружение взаимоблокировок. Обобщенный алгоритм. Способы устранения взаимоблокировки после ее обнаружения
Алгоритм
Стратегии предотвращения взаимоблокировок консервативны. Они ограничивают доступ процессов к ресурсам и накладывают ограничения на процессы. Их противоположность – стратегия обнаружения взаимоблокировок. Запрошенные ресурсы выделяются процессам при первой возможности. Периодически ОС выполняет алгоритм, который позволяет обнаружить условие циклического ожидания. Проверка может выполняться как при каждом запросе ресурса, так и менее часто.
В обобщенном алгоритме обнаружения используются матрица распределения и вектор доступности. Кроме того, определена матрица запросов Q, такая, что qij – количество ресурсов типа j, затребованных процессом i. Алгоритм работает, помечая незаблокированные процессы. Изначально все процессы не помечены. После этого выполняются шаги:
1. Помечаем все процессы, у которых строки в матрице распределения состоят из одних нулей.
2. Временной вектор W инициализируем значениями вектора доступности.
3. Находим индекс i, такой, что процесс i в настоящий момент не помечен, и i-я строка матрицы Q не превышает W, т.е. для всех k = 1, 2, …, m выполняется Qik £ Wk. Если такой строки нет, алгоритм прекращает работу.
4. Если такая строка имеется, помечаем процесс i и добавляем соответствующую строку матрицы распределения к W: Wk = Wk + Aik для всех k = 1, 2, …, m. Возвращаемся к шагу 3.
Взаимоблокировка имеется тогда и только тогда, когда после выполнения алгоритма существуют непомеченные процессы – каждый непомеченный процесс заблокирован. Этот алгоритм не гарантирует предотвращение взаимоблокировок, а определяет, имеется ли взаимоблокировка в настоящий момент.
Действия после обнаружения взаимоблокировки
1. Прекращение выполнения всех заблокированных процессов (наиболее распространенный подход).
2. Возврат каждого из заблокированных процессов в некоторую ранее определенную точку и перезапуск всех процессов.
Последовательное прекращение выполнения заблокированных процессов по одному до тех пор, пока взаимоблокировка не прекратится.
1. Последовательное перераспределение ресурсов до тех пор, пока взаимоблокировка не прекратится. Процесс, ресурсы которого перераспределяются, должен быть возвращен к состоянию, в котором находился до получения ресурса.
Для случаев 3-4 существуют критерии отбора процесса:
1) потребляющий минимальное время процессора;
2) с минимальным выводом информации;
3) с наибольшим временем ожидания;
4) с минимальным количеством захваченных ресурсов;
5) с минимальным приоритетом.
Типы адресов
Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса.
Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.
Виртуальные адреса вырабатывает транслятор, переводящий программу на машинный язык. Так как во время трансляции в общем случае не известно, в какое место оперативной памяти будет загружена программа, то транслятор присваивает переменным и командам виртуальные (условные) адреса, обычно считая по умолчанию, что программа будет размещена, начиная с нулевого адреса. Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Каждый процесс имеет собственное виртуальное адресное пространство. Максимальный размер виртуального адресного пространства ограничивается разрядностью адреса, присущей данной архитектуре компьютера, и, как правило, не совпадает с объемом физической памяти, имеющимся в компьютере.
Физические адреса соответствуют номерам ячеек оперативной памяти, где в действительности расположены или будут расположены переменные и команды. Переход от виртуальных адресов к физическим может осуществляться двумя способами. В первом случае замену виртуальных адресов на физические делает специальная системная программа - перемещающий загрузчик. Перемещающий загрузчик на основании имеющихся у него исходных данных о начальном адресе физической памяти, в которую предстоит загружать программу, и информации, предоставленной транслятором об адресно-зависимых константах программы, выполняет загрузку программы, совмещая ее с заменой виртуальных адресов физическими.
Второй способ заключается в том, что программа загружается в память в неизмененном виде в виртуальных адресах, при этом операционная система фиксирует смещение действительного расположения программного кода относительно виртуального адресного пространства. Во время выполнения программы при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Второй способ является более гибким, он допускает перемещение программы во время ее выполнения, в то время как перемещающий загрузчик жестко привязывает программу к первоначально выделенному ей участку памяти. Вместе с тем использование перемещающего загрузчика уменьшает накладные расходы, так как преобразование каждого виртуального адреса происходит только один раз во время загрузки, а во втором случае - каждый раз при обращении по данному адресу.
В некоторых случаях (обычно в специализированных системах), когда заранее точно известно, в какой области оперативной памяти будет выполняться программа, транслятор выдает исполняемый код сразу в физических адресах.
34 Двухуровневая таблица страниц
Базовый механизм чтения слова из памяти включает трансляцию виртуального адреса, состоящего из номера страницы и смещения, в физический адрес, представляющий собой номер кадра и смещение, с использованием таблицы страниц. Так как таблица страниц имеет переменную длину, зависящую от размера процесса, её невозможно разместить в регистрах. Поэтому она должна располагаться в основной памяти. При выполнении некоторого процесса стартовый адрес его таблицы страниц хранится в регисте, а номер страницы из виртуального адреса используется в качестве индекса элемента, в котором ищется соответствующий номер кадра. Этот номер объединяется со смещением из виртуального адреса для получения реального физического адреса нужной ячейки памяти.
В большинстве систем для каждого процесса имеется одна таблица страниц. Максимальный размер процесса (объем виртуальной памяти) может быть большим (достигать, в частности, 2 Гбайт в системе VAX). При использовании страниц размером 29 = 512 байт требуется до 222 записей в таблице страниц для каждого процесса. Количество памяти, отводимое таблицам страниц, не может быть так велико. Для преодоления этой проблемы большинство схем виртуальной памяти позволяют хранить таблицы страниц не в основной, а в виртуальной памяти. Таким образом, сами таблицы страниц становятся объектами страничной организации. При работе процесса как минимум часть его таблицы страниц должна находиться в основной памяти. Некоторые процессоры используют двухуровневую таблицу страниц. При такой схеме имеется каталог таблиц страниц, в котором каждая запись указывает на таблицу страниц. Если размер каталога – X, максимальный размер таблицы страниц – Y, процесс может состоять максимум из X´Y страниц. Максимальный размер таблицы страниц определяется условием её размещения в одной странице.
Рассмотрим пример двухуровневой схемы, типичной для 32-ухбитовой адресации. Принимая условие адресации байтов и 4-Кбайтовые страницы, получаем 4-Гбайтовое виртуальное адресное пространство, составленное из 220 страниц. Если каждая из этих страниц отображается с помощью одной 4-байтовой записи в таблице страниц, можно создать таблице страниц процесса, состоящую из 220 записей, общим объемом 4 Мбайт. Такая таблица может быть размещена в 210 страницах виртуальной памяти, которые отображаются корневой таблицей страниц, состоящей из 210 записей, занимающих 4Кбайт основной памяти.
42 Алгоритмы замещения страниц.
Алгоритм Часы и WSClock
Отличается от алгоритма вторая попытка только реализацией. Имеется кольцевой список. По кругу проверяется страницы. Если бит страницы R=0, то она удаляется, если R=1, стрелка идет дальше.
Алгоритм WSClock: используются биты R и M, а также время последнего использования. Кроме бита R информация о текущем времени. При сбрасывании R=0, время последнего использования перезаписывается на текущее. Если R=0 и время больше t, то страница выгружается
Таблица указателей.
Одноуровневая схема показана на рис. 4.
Таблица указателей для каждого файла может находиться:
1) в области метаданных;
2) в дисковом блоке.
Случай 1) используется для малых файлов, 2) – для файлов среднего размера.
Таблица может содержать некоторое фиксированное количество элементов, не все из которых могут быть заняты. Для файлов большого размера указатели на все их блоки не помещаются в пределах одного блока. Поэтому какой-либо элемент таблицы указателей (например, последний) может быть зарезервирован для указателя на блок, в котором продолжается таблица указателей данного файла.
Рис.4
Двухуровневая схема показана на рис. 5.
Как и прежде, для малых файлов таблиц указателей можно хранить либо непосредственно в области его описания, либо в дисковом блоке. За счет того, что некоторое количество элементов таблицы содержит непосредственные указатели на блоки файла, доступ к этим блокам достаточно быстрый, особенно, если таблица указателей кэшируется в ОП при открытии файла. Если же файл имеет значительный размер, в таблице оказываются занятыми те элементы, которые соответствуют косвенным указателям, так что для доступа к оставшимся блокам файла требуется считать с диска блоки, содержащие таблицы второго уровня, а уже затем через них получить непосредственные указатели на блоки данных. (Любая проблема может быть решена на другом уровне косвенности)…
Предложенную схему можно обобщить на случай 3-х и более уровней. Причем, многоуровневые схемы гораздо эффективнее цепочного представления (как если бы последний элемент таблицы указателей содержал адрес следующей «порции» этой таблицы).
Удобно объединять атрибуты файла и таблицу указателей. Такое объединение называют i-узлом.
51 ФС NTFS
В системах Widows 9x, 2000
Используются 64-разрядные дисковые адреса (т.е. могут поддерживаться очень большие). Длина имени <=255 символов Unicode; полная длина пути <=32767 символов. Имена чувствительны к регистру, но для совместимости с Win9x Win32API не полностью это поддерживает (для имен каталогов вообще не поддерживается).
Файл в NTFS – не просто последовательность байт, а состоит из множества атрибутов, каждый из которых представлен последовательностью байт.
Большинство файлов имеет несколько коротких потоков: имя, 64-битный идентификатор, разные атрибуты. Также, как правило имеется один длинный неименованный поток данных. но у файла может быть несколько потоков данных, имена которых указываются через двоеточие foo:stream1. У каждого потока своя длина, каждый из них может блокироваться независимо от остальных. (Идея заимствована у Apple Macintosh).
В NTFS поддерживаются жесткие и символьные связи, сжатие, шифрование.
Структура NTFS.
Каждый том NTFS организован как линейная последовательность блоков (кластеров). Размер кластера от 512 бт до 64 Кбайт, обычно 4 Кбайт. Блоки нумеруются 64-разрядным счетчиком по смещению от начала тома.
Главная структура данных в каждом томе – MFT (Master File Table), главная файловая таблица – линейная последовательность записей фиксированного размера (по 1 Кбайт). Каждая такая запись описывает файл или каталог; она содержит имя, временные штампы, список дисковых адресов. Чтобы вместить список всех блоков (для больших файлов) требуется более одной записи – тогда первая запись указывает на остальные.
Какие из элементов MFT свободны, учитывается в специальном битовом массиве.
Сама MFT представляет собой файл и может располагаться где угодно на диске. Номер первого блока содержится в загрузочном блоке. Первые 16 записей MFT зарезервированы для файлов метаданных NTFS. Их имена начинаются с $. Каждый такой файл имеет атрибуты, данные.
MFT NTFS