Дисциплины диспетчеризации
Дисциплина диспетчеризации (обслуживания) определяет порядок, в котором процессор обслуживает процессы, а так же длительность квантов времени обслуживания для каждого из процессов.
Длительность кванта может зависеть от одного из нижеперечисленных событий или их комбинации:
• выполнение процесса завершено;
• процесс перешел в состояние ожидания;
• процессор потребовался для обслуживания процесса, имеющего более высокий приоритет;
• завершился заранее выделенный процессу квант времени;
• произошла ошибка.
Решение о выборе процесса на обслуживание принимается путем просмотра очереди готовых РСВ в соответствии с принятой дисциплиной обслуживания.
Выделяют следующие подходы к определению порядка передачи процессов на выполнение:
1. Равномерное циклическое квантование.
Длительность обслуживания каждого процесса ограничена величиной стандартного времени.
2. Приоритет по характеру использования предшествующего кванта.
Если процесс полностью использовал свой предшествующий квант времени, он помещается в конец очереди. Если он использовал только половину (например блокировка по вв/выв), он попадает в середину очереди ("справедливая").
Данная дисциплина хороша для обслуживания процессов с интенсивным вводом выводом.
3. Вариант равномерного циклического квантования с многоуровневой обратной связью.
В момент введения нового процесса в систему ему выделяется столько квантов, сколько в этот момент существует других параллельных процессов. После этого продолжается обычное равномерное квантование.
| Требования, предъявляемые к ОС
К операционным системам современных компьютеров предъявляется ряд требований. Главным требованием является выполнение основных функций эффективного управления ресурсами и обеспечения удобного интерфейса для пользователя и прикладных программ. Современная ОС должна поддерживать мультипрограммную обработку, виртуальную память, свопинг, развитый интерфейс пользователя (многооконный графический, аудио -, менюориентированный и т.д.), высокую степень защиты, удобство работы, а также выполнять многие другие необходимые функции и услуги. Кроме этих требований функциональной полноты, к ОС предъявляется ряд важных эксплуатационных требований.
1. Эффективность. Под эффективностью системы понимается степень соответствия системы своему назначению, которая оценивается некоторым множеством показателей эффективности Часто эффективность ОС оценивают ее производительностью (пропускной способностью) – количеством задач пользователей, выполняемых за некоторый промежуток времени, временем реакции на запрос пользователя и др. На все эти показатели эффективности ОС влияет много различных факторов, среди которых основными являются архитектура ОС, многообразие ее функций, качество программного кода, аппаратная платформа (компьютер) и др.
2. Надежность и отказоустойчивость. Операционная система должна быть, по меньшей мере, так же надежна, как компьютер, на котором она работает. Система должна быть защищена как от внутренних, так и от внешних сбоев и отказов. В случае ошибки в программе или аппаратуре система должна обнаружить ошибку и попытаться исправить положение или, по крайней мере, постараться свести к минимуму ущерб, нанесенный этой ошибкой пользователям. Кроме того, важно, чтобы компьютер имел резервные дисковые массивы, источники бесперебойного питания и др., а также программную поддержку этих средств.
3. Безопасность (защищенность). ОС должна защищать пользователей и от воздействия чужих ошибок, и от попыток злонамеренного вмешательства (несанкционированного доступа). С этой целью в ОС как минимум должны быть средства аутентификации – определения легальности пользователей, авторизации – предоставления легальным пользователям установленных им прав доступа к ресурсам, и аудита – фиксации всех потенциально опасных для системы событий.
4. Предсказуемость. Требования, которые пользователь может предъявить к системе, в большинстве случаев непредсказуемы. Запуская свою программу в системе, пользователь должен иметь основанное на опыте работы с этой программной приблизительное представление, когда ему ожидать выдачи результатов.
5. Расширяемость. В отличие от аппаратных средств компьютера полезная жизнь операционных систем измеряется десятками лет. Если программный код модулей ОС написан таким образом, что дополнения и изменения могут вноситься без нарушения целостности системы, то такую ОС называют расширяемой. Операционная система может быть расширяемой, если при ее создании руководствовались принципами модульности, функциональной избыточности, функциональной избирательности и параметрической универсальности.
6. Переносимость. В идеальном случае код ОС должен легко переноситься с процессора одного типа на процессор другого типа и с аппаратной платформы (которые различаются не только типом процессора, но и способом организации всей аппаратуры компьютера) одного типа на аппаратную платформу другого типа. Переносимые ОС имеют несколько вариантов реализации для разных платформ, такое свойство ОС называется также многоплатформенностью. Достигается это свойство за счет того, что основная часть ОС пишется на языке высокого уровня (например С, C++ и др.) и может быть легко перенесена на другой компьютер (машинно-независимая часть).
7. Совместимость. Если ОС имеет средства для выполнения прикладных программ, написанных для других операционных систем, то она совместима с этими системами
8. Удобство. Средства ОС должны быть простыми и гибкими, а логика ее работы ясна пользователю. Современные ОС ориентиров/аны на обеспечение пользователю максимально возможного удобства при работе с ними. Необходимым условием этого стало наличие у ОС графического пользовательского интерфейса и всевозможных мастеров – программ, автоматизирующих активизацию функций ОС, подключение периферийных устройств, установку, настройку и эксплуатацию самой ОС.
9. Масштабируемость. Если ОС позволяет управлять компьютером с различным числом процессов, обеспечивая линейное (или почти такое) возрастание производительности при увеличении числа процессоров, то такая ОС является масштабируемой
Принцип мобильности
Принцип мобильности: операционная система относительно легко должна переноситься с процессора одного типа на процессор другого типа и с аппаратной платформы одного типа, которая включает наряду с типом процессора и способ организации всей аппаратуры компьютера (архитектуру вычислительной системы), на аппаратную платформу другого типа. Заметим, что принцип переносимости очень близок принципу совместимости, хотя это и не одно и то же. Создание переносимой ОС аналогично написанию любого перено-симого кода, при этом нужно следовать некоторым правилам:
- большая часть ОС должна быть выполнена на языке, имеющемся на всех системах, на которые планируется в дальнейшем ее переносить. Это, прежде всего, означает, что ОС должна быть написана на языке высокого уровня, предпочтительно стандартизованном, например на языке С. Программа, написанная на ассемблере, не является в общем случае переносимой.
- важно минимизировать или, если возмож-но, исключить те части кода, которые непосредственно взаимодействуют с аппаратными средствами. Зависимость от аппаратуры может иметь много форм. Некоторые очевидные формы зависимости включают прямое манипулирование регистрами и другими аппаратными средствами. Наконец, если аппаратнозависимый код не может быть полностью исключен, то он должен быть изолирован в нескольких хорошо локализуемых модулях. Аппаратнозависимый код не должен быть распределен по всей системе. Например, можно спрятать аппаратно-зависимую структуру в програмно задаваемые данные абстрактного типа. Введение стандартов POSIX преследовало цель обеспечить переносимость создаваемого программного обеспечения.
Принцип обеспечения безопасности вычислений
Принцип обеспечения безопасности вычислений: обеспечение безопасности при выполнении вычислений является желательным свойством для любой многопользовательской системы. Правила безопасности определяют такие свойства, как защиту ресурсов одного пользователя от других и установление квот по ресурсам для предотвращения захвата одним пользователем всех системных ресурсов таких например как память.Обеспечение защиты информации от несанкционированного доступа является обязательной функцией сетевых операци-онных систем.
3. История развития ОС
0 поколение (40 - 50 годы) - ОС отсутствует. Полный доступ к ресурсам ЭВМ на машинном языке, все программы разрабатываются в двоичном коде. Этот период характеризуется высокой стоимостью приобретения и эксплуатации компьютеров и низкой стоимостью труда программистов. Компьютеры использовались в монопольном интерактивном режиме. Основная цель – максимизировать использование аппаратного обеспечения. Основной режим работы компьютера – простой и ожидание каких-либо действий программиста. При этом наблюдается недостаточное использование дорогостоящего вычислительного оборудования
1 поколение (60-е годы).Возникла система пакетной обработки. В каждый момент времени ЭВМ использовалась для решения одной прикладной программы. Пользователи уже не работают с ЭВМ на физическом уровне. Программы и данные принимает человек-оператор. Задание на обработку формируется в виде пакета, представляющего собой совокупность отдельных программ и данных, разделенных специальными символами. Пакет может быть составлен на перфокартах или МЛ. В машине постоянно находится управляющая программа, которая считывает последовательно пользовательские программы и данные из пакета и загружает их на выполнение. Результаты выводятся на внешнее устройство, и составляют пакет результатов. Управляющая программа должна фиксировать время исполнения каждой программы, реагировать на определенные ситуации по управлению программами по мере их исполнения (прекращать выполнение). Другими словами, она должна выполнять внутрисистемные операции управления, которые пользователь осуществлял ранее на физическом уровне. Дополнительно эта программа должна автоматически переключать машину на исполнение программ из пакета по последовательной схеме (FIFO). Такую системную программу можно назвать простейшей ОС, обеспечивающей обработку программ в однопрограммном пакетном режиме.
Недостатки:
Использование части машинного времени (времени процессора) на выполнение системной управляющей программы.
Программа, получившая доступ к процессору, обслуживается до ее завершения. При этом если возникает потребность в передаче данных между внешними устройствами и ОП, то процессор простаивает, ожидая завершения операции обмена. С другой стороны при работе процессора простаивают внешние устройства. Для персонального компьютера проявление фактора простоя процессора не столь существенно, так как стоимость его не велика, чего не скажешь о больших и дорогих ЭВМ.
Этот недостаток однопрограммного режима был устранен в мультипрограммном пакетном режиме (65-75 г.г.)
2-e поколение. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для этой цели в начале работы формируется пакет заданий, содержащих требования к системным ресурсам. Из этого пакета формируется мультипрограммная смесь из заданий, предъявляющих отличающиеся требования к ресурсам для того, чтобы обеспечить сбалансированную нагрузку всех устройств ЭВМ. Так, например, в мультипрограммную смесь желательно вводить вычислительные задачи и задачи, интенсивно использующие ввод/вывод. В системах пакетной обработки переключение процессов с выполнения одной задачи на другую происходит только в том случае, если активная задача сама отказывается от процессора, например, для выполнения операции ввода/вывода, что делает невозможным выполнение интерактивных задач. Особенностью этого поколения было и то, что ОС создавались как системы коллективного пользования с мультипрограммным режимом работы и как первые системы мультипроцессорного типа. В таких системах несколько пользовательских программ одновременно присутствуют в оперативной памяти компьютера и центральный процессор (ЦП) динамически переключается с решения одной задачи на решение другой задачи. При этом появляется возможность одновременной загрузки ЦП и устройств ввода-вывода. В случае многопроцессорных систем единый вычислительный комплекс (ВК) содержит несколько процессоров, что повышает вычислительную мощность вычислительной системы (ВС). В то же время появились методы, обеспечивающие независимость программирования от внешних устройств. В программе необходимо указывать только тип устройства, а не программировать его физический адрес. Конкретный адрес устройства определялся в процессе выполнения программы. Это было серьезное достижение в развитии ОС.
17, 19 Алгоритм Деккера и Петерсона
Алгоритм Деккера (см. ниже) предполагает только элементарные взаимоисключения на уровне доступа к памяти, т.е. одновременный доступ (чтение и/или запись) упорядочивается при помощи некоторого механизма. Необходимо "навязать" определенный порядок действия двум процессам. Переменная turn указывает, какой из двух процессов имеет право на вход в критическую секцию. Когда процесс p0 намерен войти в критическую секцию, он устанавливает flag[0] в true и проверяет flag[1]. Если flag[1] = false, p0 может немедленно войти в критическую секцию, иначе p0 проверяет turn. Если turn = 0, то сейчас – очередь p0 и p0 периодически проверяет flag[1]. P1, в свою очередь, обнаружив, что сейчас не его очередь, в какой-то момент времени сбрасывает flag[1] в false. По окончанию работы p0 сбрасывает flag[0] в false и присваивает единицу переменной turn.
Алгоритм:
Boolean flag[2];
Int turn;
Void p0 ()
{
While (true)
{
Flag[0] = true;
While (flag[1])
If (turn == 1)
{
Flag[0] = false;
While (turn == 1); //ничего не делать
Flag[0] = true;
}//критический раздел
turn = 1;
flag[0] = false;//остальной код
}
}
void p1()
{
//определение аналогично предыдущему, с заменой всех переменных на противоположные
}
void main ()
{
flag[0] = false;
flag[1] = false;
turn = 1;
parbegin (p0, p1);
}
Алгоритм Петерсона реализации взаимного исключения изобретен в 1981 г. С этого момента алгоритм Деккера считается устаревшим.
#define FALSE 0
#define TRUE 1
#define N 2
int turn; /*чья сейчас очередь*/
int interested[N]; /*изначально все нули - FALSE*/
void enter_region (int process)
{
int other = 1-process; /*противоположный*/
interested[process]=TRUE; /*да, мы хотим войти*/
turn=process;
while(turn==process&&interested[other]==true); /*активное ожидание*/
}
void leave_region(int process)
{
interested[process]=FALSE; /*все, мы уходим*/
}
Примечание: оптимизирующий компилятор может кэшировать переменные в регистрах, тогда код не будет работать. Следует использовать volatile.
Активное ожидание – плохо. Кроме того, возникает проблема инверсии приоритета. Допустим, есть 2 процесса: H и L, причем приоритет Н>>L. Если Н оказался в ожидании, пока L не освободит некий ресурс, то Н в активном ожидании постоянно отнимает процессорное время у низкоприоритетного процесса L, не давая ему выйти из критической секции.
Решение проблемы «обедающих философов»
Хорошее решение:
#define N 5 //количество философов
#define LEFT (i+N+1)%N //номер левого соседа
#define RIGHT (i=N-1)%N //номер правого соседа
#define THINKING 0 //думает
#define HUNGRY 1 //голоден
#define EATING 2 //ест
typedef int semaphore;
int state[N]; //массив для отслеживания
состояний каждого философа
semaphore mutex=1;
semaphore S[N]; //каждому философу по семафору
//--------------------------------------------------------------------------------
void philosopher (int i) //i – номер философа от 0 до N-1
{
while(1)
{
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks (int i)
{
wait(mutex); //вход в CS
state[i]=HUNGRY; //фиксация наличия голодного философа
test(i); //фиксация наличия голодного философа
release(mutex); //выход из CS
wait(S[i]); //блокировка, если вилок не досталось
}
void test (int i)
{
if(state[i]==HUNGRY && state[LEFT)!=EATING)
{
state[i]=EATING;
signal(S[i]);
}
}
Здесь философ как бы сам себя пропускает, открывая семафор. Если же условие ложно, семафор не откроется, и процедура take_forks будет блокирована.
void put_forks (int i)
{
wait(mutex); //вход в CS
state[i]=THINKING; //философ перестал есть
test(LEFT); //проверить, могут ли есть
test(RIGHT); //соседи слева и справа
release (mutex); //выход из CS
}
28. Предотвращение взаимоблокировок. Запрет выделения ресурса
Данная стратегия известна как алгоритм банкира. Пусть существует система с фиксированным количеством процессов и фиксированным количеством ресурсов. Состояние системы представляет собой текущее распределение ресурсов по процессам. Следовательно, состояние представляется как два вектора и две матрицы (см. п. 5.4.2.1).
Безопасным называется такое состояние, в котором имеется хотя бы одна последовательность, не приводящая к взаимоблокировке (т.е. все процессы могут быть выполнены до завершения). Состояние, не являющееся безопасным, называется опасным.
Ниже алгоритм рассмотрен на примере (рис. 7).
Общее количество ресурсов R1, R2, R3 соответственно 9, 3,6 единиц. В результате сделанного к этому моменту распределения ресурсов по процессам доступными оказались по одной единице ресурсов R2 и R3. Безопасно ли это состояние? Для ответа на этот вопрос нужно задаться другим вопросом: может ли какой-либо из четырех процессов быть выполнен до завершения при данных доступных ресурсах. Для P1 – невозможно, но если выделить процессу P2 одну единицу R3, он может быть завершен. Пусть после завершения P2 выполняются требования P1, затем P3 и P4. Следовательно, исходное состояние – безопасное.
Описанная концепция автоматически приводит к стратегии устранения взаимоблокировок, которая гарантирует, что система процессов и ресурсов всегда находится в безопасном состоянии. Когда процесс делает запрос к некоторому множеству ресурсов, предполагается, что запрос удовлетворен, после чего определяется, является ли обновленное состояние безопасным. С другой стороны, опасное состояние не является взаимоблокировкой. Оно лишь может привести к ней. Таким образом, описанная стратегия не занимается точным предсказанием взаимоблокировок, а предвидит их возможность и устраняет её.
Использование метода устранения взаимоблокировок требует выполнения следующих условий:
1) Должны быть заранее указаны максимальные требования каждого процесса к каждому виду ресурса;
2) Рассмотренные процессы должны быть независимы, т.е. порядок их выполнения не должен ограничиваться какими-либо требованиями синхронизации;
3) Должно иметься фиксированное количество распределяемых ресурсов;
4) Ни один процесс не должен завершаться в состоянии захвата ресурса.
31. Виртуальная память. Типы адресов
Уже достаточно давно пользователи столкнулись с проблемой размещения в памяти программ, размер которых превышал имеющуюся в наличии свободную память. Решением было разбиение программы на части, называемые оверлеями. 0-ой оверлей начинал выполняться первым. Когда он заканчивал свое выполнение, он вызывал другой оверлей. Все оверлеи хранились на диске и перемещались между памятью и диском средствами операционной системы. Однако разбиение программы на части и планирование их загрузки в оперативную память должен был осуществлять программист.
Развитие методов организации вычислительного процесса в этом направлении привело к появлению метода, известного под названием виртуальная память. Виртуальным называется ресурс, который пользователю или пользовательской программе представляется обладающим свойствами, которыми он в действительности не обладает. Так, например, пользователю может быть предоставлена виртуальная оперативная память, размер которой превосходит всю имеющуюся в системе реальную оперативную память. Пользователь пишет программы так, как будто в его распоряжении имеется однородная оперативная память большого объема, но в действительности все данные, используемые программой, хранятся на одном или нескольких разнородных запоминающих устройствах, обычно на дисках, и при необходимости частями отображаются в реальную память.
Таким образом, виртуальная память - это совокупность программно-аппаратных средств, позволяющих пользователям писать программы, размер которых превосходит имеющуюся оперативную память; для этого виртуальная память решает следующие задачи:
*размещает данные в запоминающих устройствах разного типа, например, часть программы в оперативной памяти, а часть на диске;
*перемещает по мере необходимости данные между запоминающими устройствами разного типа, например, подгружает нужную часть программы с диска в оперативную память;
• преобразует виртуальные адреса в физические.
Все эти действия выполняются автоматически, без участия программиста, то есть механизм виртуальной памяти является прозрачным по отношению к пользователю.
Наиболее распространенными реализациями виртуальной памяти является страничное, сегментное и странично-сегментное распределение памяти, а также свопинг.
Странично-сегментная
Как видно из названия, данный метод представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов. Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс. На рисунке 7 показана схема преобразования виртуального адреса в физический для данного метода.
Свопинг
Разновидностью виртуальной памяти является свопинг.
На рисунке 8 показан график зависимости коэффициента загрузки процессора в зависимости от числа одновременно выполняемых процессов и доли времени, проводимого этими процессами в состоянии ожидания ввода-вывода.
Из рисунка видно, что для загрузки процессора на 90% достаточно всего трех счетных задач. Однако для того, чтобы обеспечить такую же загрузку интерактивными задачами, выполняющими интенсивный ввод-вывод, потребуются десятки таких задач. Необходимым условием для выполнения задачи является загрузка ее в оперативную память, объем которой ограничен. В этих условиях был предложен метод организации вычислительного процесса, называемый свопингом. В соответствии с этим методом некоторые процессы (обычно находящиеся в состоянии ожидания) временно выгружаются на диск. Планировщик операционной системы не исключает их из своего рассмотрения, и при наступлении условий активизации некоторого процесса, находящегося в области свопинга на диске, этот процесс перемещается в оперативную память. Если свободного места в оперативной памяти не хватает, то выгружается другой процесс.
При свопинге, в отличие от рассмотренных ранее методов реализации виртуальной памяти, процесс перемещается между памятью и диском целиком, то есть в течение некоторого времени процесс может полностью отсутствовать в оперативной памяти. Существуют различные алгоритмы выбора процессов на загрузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.
40 Алгоритмы замещения страниц
NRU, FIFO, “Вторая попытка”
NRU - Не использующиеся в последнее время страницы. Используются биты обращения(R4)изменения (M)в таблицы страниц N. При обращении бит «R»=1. Через некоторое время ОС переведет его в 0. «M» переводиться в 0 только после записи на диск.
Благодаря этим видам можно получить 4 класс страниц.
R=0, М=0 не было обращений и не было изменений.
R=0, М=1 не было обращений, но были изменения.
R=1, М=0 было обращение, но не было изменений.
R=1, М=1 было обращение, были изменения.
Лучше выгрузить измененную страницу, к к-ой было мало обращений, чем часто используемую. Алгоритм легок для понимания, умеренно сложен, удовлетворительная оптимальность.
FIFO – первый прибыл, первый обслужен. Пример с унирсамом(Татенбаум можно и муку с сахаром убрать)
Первая страница в списке страниц является старейшей. Алгоритм FIFO редко используется.
Вторая попытка. Как у FIFO, но у самой старейшей страницы изучается бит R. Если он равен 0, то страница немедленно заменяется новой. Если 1, то R=0 и страница становится в конец очереди. Процесс повторяется. Если у всех страниц R=1, то алгоритм превращается в FIFO. При втором круге у страницы уже будет R=0. Т.о. алгоритм успешно завершает свою работу
41 Алгоритмы замещения страниц.
Алгоритм LRU
NFU – редко используемая страница. Алгоритм LRU редко используется, поэтому используется NFU
Во время каждого прерывания система изучает страницы и бит R для каждой страницы прибавляется к счетчику. Недостаток – алгоритм ничего не забывает. Он может удалять нужные страницы, а те которые уже не нужны оставлять. Модификация: каждый счетчик сдвигается вправо на один разряд перед прибавлением бита R; бит R сдвигается в крайний левый, а не крайний правый разряд счетчика.
Алгоритм старения. Когда происходит страничное прерывание удаляется та страница, счетчик которой имеет наименьшую величину
Отличие от RLU: ограниченное число разрядов (8) не можем сказать, когда к странице последний раз обращались (9 тиков назад или 1000), но на практике если перевалило за 9 разряд, страница скорее всего не нужна
Реализация ФС
Для описания хранящихся в ФС файлов требуется довольно значительный объем информации об их именах, расположении, правах доступа, атрибутах и т.п. Если под данными понимать полезную информацию внутри файлов, то требуются метаданные (или данные о данных).
Единицей хранения данных на диске является не байт, а сектор или блок (кластер). Современные дисковые котроллеры представляют для ОС высокоуровневую абстракцию массива блоков.
Таким образом, поверхность диска размечается на блоки, каждый из которых может быть свободным, либо принадлежать какому-либо файлу.
Элементы метаданных должны содержать для каждого файла, по меньшей мере, имя и номера его блоков.
Способы хранения информации о свободных и выделенных блоках
1. Блоки файлов.
Рис.2
Недостатков очень много:
- неудобство произвольного доступа (требуется считывать все блоки до нужного);
- при повреждении блока теряется остаток файла.
2. Цепочки в памяти.
Расположение файлов на диске представлено цепочкой указателей, но сама это цепочка локализована в специальной структуре, которую для ускорения доступа можно кэшировать в ОП.
Важный недостаток – слишком большой размер карты. Каждый дисковый блок должен быть представлен в карте, и для него должен быть указан либо номер следующего блока, либо признак того, что данный блок – последний в цепочке, либо признак незанятости блока (а еще может быть признак того, что данный блок - директивный). Размер карты зависит от размера диска и размера блока.
50 ФС UNIX
UNIX V7
Имена файлов содержат до 14 символов.
Каждая каталоговая запись содержит 2 поля: имя (14 байт) и номер i-узла (2 байт). В системе не может быть более 64К файлов.
i-узел содержит атрибуты: размер файла, 3 указателя времени (создания последнего доступа, последнего изменения), идентификатор владельца, номер группы, информация о защите и счетчик каталоговых записей, указывающих на этот i-узел (что необходимо для связей – hard links). При добавлении новой связи счетчик увеличивается на 1, при удалении – уменьшается на 1. Когда счетчик достигает 0, i-й узел освобождается, а блоки диска, которые занимал файл возвращаются в список свободных.
Доступ к небольшим файлам (до 10 блоков) очень быстрый – их адреса хранятся прямо в i-узле.
Рис.8
Этапы поиска файла /usr/ast/mbox
Корневой каталог
|
| .
| |
| ..
| |
| bin
| |
| dev
| |
| lib
| |
| etc
| |
| usr
| |
| tmp
|
i – узел №6 содержит данные о каталоге /usr
Блок №132 содержит каталог файлов /usr/*
|
| .
| |
| .
| |
| dick
| |
| eric
| |
| jim
| |
| ast
| |
| bal
| i – узел №26 содержит данные о каталоге /usr/ast
Блок №132 содержит каталог файлов /usr/ast/*
i – узел №60 содержит данные о каталоге /usr/ast/mbox/
Этот узел считывается в память при открытии файла и остается там, пока файл не будет закрыт.
4. Принудительный приоритет.
Выбирается процесс с наивысшим приоритетом из всех готовых. Приоритет назначается исходя из важности соответствующей работы или с учетом дополнительной оплаты.
5. Ограниченное равномерное циклическое квантование.
Процессы обслуживаются способом равномерного квантования некоторое определенное число раз, после чего они обслуживаются только при условии отсутствия в системе других процессов.
6. Сбалансированная загрузка.
Для предотвращения простоя внешних устройств предпочтение отдается процессам, интенсивно использующим вв/выв.
7. Предпочтительное обслуживание интерактивных процессов.
Если при решении задачи осуществляется оперативное взаимодействие с пользователем (интерактивные задачи), обслуживание соответствующего процесса начинается сразу после запроса пользователя. С помощью такой дисциплины удается обеспечить малое время реакции системы.
8. Автоматические приоритеты.
Ответственность за назначение процессам приоритетов возлагается на саму операционную систему:
• ОС может повышать приоритеты коротких заданий;
• автоматическое назначение приоритетов, приводящее к сбалансированной загрузке оборудования (совместное выполнение двух процессов: 1 интенсивно использует вв/выв; другой использует его в малой степени).
При выполнении двух процессов со сходными характеристиками, может возникнуть ситуация перегрузки одного из ресурсов с одной стороны и простоя другого ресурса с другой стороны. Для предотвращения такой ситуации ОС производит постоянную коррекцию приоритетов.
9. Модель типа вертушки (круговорот) и ее варианты.
Процессор последовательно выбирается процессом в течении фиксированного промежутка времени, называемого квантом. Если процесс заканчивается или блокируется до конца кванта, то процессор сразу же передается следующему процессу. Процессы упорядочиваются в последовательную очередь, указатель активации, который перемещается при каждом новом назначении процессора, выделяет избранный процесс.
В модели многоуровневой вертушки дополнительно уменьшается время обслуживания коротких заданий. Она содержит n очередей ожидания F0,…..,Fn-1. С каждой очередью Fi связан квант Qi, величина которого растет с увеличением i. Задание из очереди Fi обрабатывается только в том случае, если все очереди с меньшими номерами i пусты. Когда квант времени израсходован на задание из очереди Fi, а соответствующее задание еще не окончено, оно помещается в очередь Fi+1, задания из очереди Fn-1 возвращаются в эту же очередь. Новые задания попадают в очередь F0.
|
Поиск по сайту:
|