1. Общее описание операционных систем. Основные функции и методы построения, структура операционной системы.

Основные задачи, решаемые ОС: управление процессами и ресурсами, управление файлами, организация работы с оперативной памятью, организация работы с устройствами. Основная задача операционной системы заключается в том, чтобы обеспечить работу всей аппаратуры компьютера как единого вычислительного комплекса, правильно организовать работу нескольких приложений с несколькими ресурсами так, чтобы не возникало конфликтов. Операционная система – набор программ, обеспечивающих функционирование центрального процессора и периферийных устройств ЭВМ как единого комплекса, служащего для разработки и выполнения программ. Функции или подсистемы ОС:система управления процессами, система распределения ресурсов, система распределения оперативной памяти, система управления вводом – выводом, файловая система, интерфейс с пользователем. Процесс – некоторая логически связанная последовательность действий, не обязательно линейная. Ресурс – средство вычислительной техники, которое может быть выделено процессу на некоторое время. Виды ОС: DOS, Windows (версии), UNIX, MAC OS, Novel NetWare и т.п. Общие черты ОС: модульность, наличие ядра, функциональная избыточность, защита, привилегированный и непривилегированный режим работы процессора, применение паролей, принцип независимости программ от внешних устройств. Особенности методов построения При описании операционной системы часто указываются особенности ее структурной организации и основные концепции, положенные в ее основу. К таким базовым концепциям относятся: Способы построения ядра системы - монолитное ядро или микроядерный подход. Большинство ОС использует монолитное ядро, которое компонуется как одна программа, работающая в привилегированном режиме и использующая быстрые переходы с одной процедуры на другую, не требующие переключения из привилегированного режима в пользовательский и наоборот. Альтернативой является построение ОС на базе микроядра, работающего также в привилегированном режиме и выполняющего только минимум функций по управлению аппаратурой. При таком построении ОС работает более медленно, так как часто выполняются переходы между привилегированным режимом и пользовательским, зато система получается более гибкой - ее функции можно наращивать, модифицировать или сужать, добавляя, модифицируя или исключая серверы пользовательского режима. Кроме того, серверы хорошо защищены друг от друга, как и любые пользовательские процессы. Построение ОС на базе объектно-ориентированного подхода дает возможность использовать все его достоинства, а именно: аккумуляцию удачных решений в форме стандартных объектов, возможность создания новых объектов на базе имеющихся с помощью механизма наследования, хорошую защиту данных за счет их инкапсуляции во внутренние структуры объекта, что делает данные недоступными для несанкционированного использования извне, структурированность системы, состоящей из набора хорошо определенных объектов. Наличие нескольких прикладных сред дает возможность в рамках одной ОС одновременно выполнять приложения, разработанные для нескольких ОС. Распределенная организация операционной системы позволяет упростить работу пользователей и программистов в сетевых средах. В распределенной ОС реализованы механизмы, которые дают возможность пользователю представлять и воспринимать сеть в виде традиционного однопроцессорного компьютера. Характерными признаками распределенной организации ОС являются: наличие единой справочной службы разделяемых ресурсов, единой службы времени, использование механизма вызова удаленных процедур (RPC) для прозрачного распределения программных процедур по машинам,

2. Однозадачные операционные системы, принципы многозадачной операционной системы. Метод разделения оперативной памяти на фрагменты, закрепляемые за процессами. Распределение времени процессора.

По числу одновременно выполняемых задач операционные системы могут быть разделены на два класса: однозадачные (например, MS-DOS, MSX) и многозадачные (OC EC, OS/2, UNIX, Windows 95-98). Под задачей можно понимать некоторую прикладную программу, приложение (например, MSWord, Excel и т.п.)Однозадачные ОС в основном выполняют функцию предоставления пользователю виртуальной машины, делая более простым и удобным процесс взаимодействия пользователя с компьютером. Однозадачные ОС включают средства управления периферийными устройствами, средства управления файлами, средства общения с пользователем. Многозадачные ОС, кроме вышеперечисленных функций, управляют разделением совместно используемых ресурсов, таких как процессор, оперативная память, файлы и внешние устройства (то есть решают вопрос о предоставлении ресурса той или иной задаче во временное пользование). Важнейшим разделяемым ресурсом является процессорное время. Способ распределения процессорного времени между несколькими одновременно существующими в системе процессами (или нитями) во многом определяет специфику ОС. Среди множества существующих вариантов реализации многозадачности можно выделить две группы алгоритмов: Не вытесняющая многозадачность (NetWare, Windows 3.x); вытесняющая многозадачность (Windows NT, OS/2, UNIX). Основным различием между вытесняющим и не вытесняющим вариантами многозадачности является степень централизации механизма планирования процессов. В первом случае механизм планирования процессов целиком сосредоточен в операционной системе, а во втором - распределен между системой и прикладными программами. При не вытесняющей многозадачности активный процесс выполняется до тех пор, пока он не закончится, ему потребуется занятый в настоящее время ресурс или он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению процесс. При вытесняющей многозадачности решение о переключении процессора с одного процесса на другой принимается операционной системой, а не самим активным процессом. Многозадачные ОС подразделяются на три типа в соответствии с использованными при их разработке критериями эффективности: системы пакетной обработки (например, OC EC)( Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используются следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие отличающиеся требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины), системы разделения времени (UNIX, VMS)( Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Так как в системах разделения времени каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым. . Критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя), системы реального времени (QNX, RT/11)( критерием эффективности для систем реального времени является их способность выдерживать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия).

3. Проблема распределения ресурсов. Метод блокирующих переменных.

Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) - абстракция, описывающая выполняющуюся программу. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов.Проблема может заключаться в одновременной потребности в одном и том же ресурсе. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами. Критическая секция - это часть программы, в которой осуществляется доступ к некоторым разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Для обеспечения взаимного исключения можно использовать блокирующие переменные. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 3 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к некоторому разделяемому ресурсу блокирующую переменную РЕСУРС_1. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс РЕСУРС_1. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной РЕСУРС_1 устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом, значение переменной РЕСУРС_1 снова устанавливается равным 1.

Процесс А (правильный способ – пользуемся системной операцией ПРОВЕРКА_ЗАНЯТИЕ:

если не определена РЕСУРС_1 то

определить глобальную переменную РЕСУРС_1

РЕСУРС_1 = 1

конец если

повторять пока не ПРОВЕРКА_ЗАНЯТИЕ (РЕСУРС_1)

конец повтора

Критическая секция: работа с разделяемым ресурсом

РЕСУРС_1 = 1

Рис. 3. Реализация критических секций с использованием блокирующих переменных

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

4. Очередь. Метод разделения ресурсов на основе очередей.

Очевидно, что процессы не могут выполняться одновременно (процессор-то один), но подсистема управления процессами старается распределить процессорное время между процессами. В соответствии с состоянием процессов ОС поддерживает два списка-очереди: очередь готовых процессов и очередь ожидающих процессов. Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки. Часто это - однонаправленный список. Таким образом, каждый дескриптор, кроме всего прочего, содержит, по крайней мере, один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое. операционной системе для реализации планирования процессов требуется следующая информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса (приоритет), номер кодового сегмента в оперативной памяти (адрес в оперативной памяти, с которого расположен код программы), адрес в кодовом сегменте, с которого начинается следующая выполняемая команда процесса и другая информация. Информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса.

очередь - это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Она возникает тогда, когда ресурс недоступен в данный момент, но через некоторое время он освобождается, и процесс продолжает свое выполнение

5. Семафоры, мониторы доступа.

P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P. Применение семафоров необходимо тогда, когда требуется определить степень занятости некоторого ресурса, а не просто получить ответ на вопрос «занят ресурс или свободен».

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

методы решения проблемы синхронизации:

запрет прерываний процесса во время работы с ресурсом;

блокирующие переменные;

функции WAIT(ресурс) POST(ресурс);

семафоры;

мониторы

6. Вытесняющая и не вытесняющая многозадачность. Приоритетные дисциплины организации работы многопроцессной операционной системы.

Важнейшим разделяемым ресурсом является процессорное время. Способ распределения процессорного времени между несколькими одновременно существующими в системе процессами (или нитями) во многом определяет специфику ОС. Среди множества существующих вариантов реализации многозадачности можно выделить две группы алгоритмов: Не вытесняющая многозадачность (NetWare, Windows 3.x); вытесняющая многозадачность (Windows NT, OS/2, UNIX). Основным различием между вытесняющим и не вытесняющим вариантами многозадачности является степень централизации механизма планирования процессов. В первом случае механизм планирования процессов целиком сосредоточен в операционной системе, а во втором - распределен между системой и прикладными программами. При не вытесняющей многозадачности активный процесс выполняется до тех пор, пока он не закончится, ему потребуется занятый в настоящее время ресурс или он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению процесс. При вытесняющей многозадачности решение о переключении процессора с одного процесса на другой принимается операционной системой, а не самим активным процессом. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока не произойдет одно из указанных событий: процесс завершился, процесс передал управление ОС, произошла ошибка, процесс потребовал некоторый ресурс, который в настоящее время занят другим процессом, закончился квант времени. В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.

7. Тупики. Причины возникновения тупиков. Пример. Методы предотвращения тупиков. Способы выхода из тупика: на уровне пользователя, на уровне ОС. Программы распознавания тупиков.

Проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. И пусть после того, как процесс А занял принтер, он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго. Важно, что если процессам требуется один ресурс (а не два и более), то тупик никогда не возникает. Проблема тупиков подразумевает решение следующих задач: предотвращение тупиков, распознавание тупиков, восстановление системы после тупиков. Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. Например, можно потребовать от всех программистов, чтобы в их программах ресурсы занимались только в заранее заданном порядке. Например, установим, следующую очередность занятия ресурсов: диск, модем, принтер, сетевая карта, … Тогда процесс А и процесс В из примера запрашивали бы ресурсы в этой заданной последовательности, и тупик был бы в принципе невозможен (формировались бы обычные очереди). Второй подход к предотвращению тупиков называется динамическим и заключается в использовании определенных правил при назначении ресурсов процессам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех процессов. То есть те же правила должна обеспечивать ОС. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, и эти процессы перейдут в очередь готовых. Можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика. Очевидно, это точки перед занятием ресурсов. Для того чтобы облегчить написание корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором. Монитор - это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору. Компилятор обрабатывает вызовы процедур монитора особым образом. Обычно, когда процесс вызывает процедуру монитора, то первые несколько инструкций этой процедуры проверяют, не активен ли какой-либо другой процесс по отношению к этому монитору. Если да, то вызывающий процесс приостанавливается, пока другой процесс не освободит монитор. Таким образом, исключение входа нескольких процессов в монитор реализуется не программистом, а компилятором, что делает ошибки менее вероятными.

8. Задания, процессы, нити. Многопроцессорные системы.

Многозадачность является важнейшим свойством ОС. Для поддержки этого свойства ОС определяет и оформляет для себя те внутренние единицы работы, между которыми и будет разделяться процессор и другие ресурсы компьютера. Эти внутренние единицы работы в разных ОС носят разные названия - задача, задание, процесс, нить. В некоторых случаях сущности, обозначаемые этими понятиями, принципиально отличаются друг от друга. Говоря о процессах, мы отмечали, что операционная система поддерживает их обособленность: у каждого процесса имеется свое виртуальное адресное пространство, каждому процессу назначаются свои ресурсы - файлы, окна, семафоры и т.д. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ресурсы машины, конкурируют друг с другом. В общем случае процессы принадлежат разным пользователям, разделяющим один компьютер, и ОС берет на себя роль арбитра в спорах процессов за ресурсы. При мультипрограммировании повышается пропускная способность системы, но отдельный процесс никогда не может быть выполнен быстрее, чем если бы он выполнялся в однопрограммном режиме (всякое разделение ресурсов замедляет работу одного из участников за счет дополнительных затрат времени на ожидание освобождения ресурса). Однако задача, решаемая в рамках одного процесса, может обладать внутренним параллелизмом, который в принципе позволяет ускорить ее решение. Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой "ветви" процесса.

Для этих целей современные ОС предлагают использовать сравнительно новый механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл. Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в традиционной многозадачной системе, между ними легко организовать тесное взаимодействие. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования. Однако различные нити в рамках одного процесса не настолько независимы, как отдельные процессы. Все такие нити имеют одно и то же адресное пространство. Это означает, что они разделяют одни и те же глобальные переменные. Поскольку каждая нить может иметь доступ к каждому виртуальному адресу, одна нить может использовать стек другой нити. Между нитями нет полной защиты, потому что, во-первых, это невозможно, а во-вторых, не нужно. Все нити одного процесса всегда решают общую задачу одного пользователя, Итак, нити имеют собственные: программный счетчик, стек, регистры, нити-потомки, состояние. Нити разделяют (то есть имеют в общем пользовании): адресное пространство, глобальные переменные, открытые файлы, таймеры, семафоры, статистическую информацию. Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой. Многопроцессорные ОС могут классифицироваться по способу организации вычислительного процесса в системе с многопроцессорной архитектурой: асимметричные ОС и симметричные ОС. Асимметричная ОС целиком выполняется только на одном из процессоров системы, распределяя прикладные задачи по остальным процессорам. Симметричная ОС полностью децентрализована и использует все множество процессоров, разделяя их между системными и прикладными задачами. Многопроцессорные системы требуют от операционной системы особой организации, с помощью которой сама операционная система, а также поддерживаемые ею приложения могли бы выполняться параллельно отдельными процессорами системы. Параллельная работа отдельных частей ОС создает дополнительные проблемы для разработчиков ОС, так как в этом случае гораздо сложнее обеспечить согласованный доступ отдельных процессов к общим системным таблицам, исключить эффект гонок и прочие нежелательные последствия асинхронного выполнения работ.

9. Файловые системы, назначения, виды, сравнение.

Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие "файловая система" включает: совокупность всех файлов на диске, наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске, комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами. В MSDOS файловая система носит название FAT, в операционной системе Unix файловая система называется NFS, хотя эта ОС допускает одновременную работу нескольких файловых систем, в Windows может быть установлена одна из файловых систем – NTFS, FAT32, в Windows 2000 можно установить EFS.Общая модель файловой системы. Функционирование любой файловой системы можно представить многоуровневой моделью (рисунок 8), в которой каждый уровень предоставляет некоторый интерфейс (набор функций) вышележащему уровню, а сам, в свою очередь, для выполнения своей работы использует интерфейс (обращается с набором запросов) нижележащего уровня.

запрос к файлу (заданы имя файла, номер записи файла, операция, пользователь)
символьный уровень	по символьному имени определяется его уникальное имя (идентификатор)
базовый уровень	в системных таблицах находятся характеристики файла
уровень проверки прав доступа	проверка прав пользователя на проведение заданной операции с заданным файлом
логический уровень	по системным таблицам определяется логическое расположение файла
физический уровень	определяется физическое расположение записей файла
обращение к подсистеме ввода-вывода

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. В файловой системе FAT16 (MS-DOS) длина имен ограничивается: 8 символов - собственно имя, 3 символа - расширение имени, а в ОС UNIX System V имя не может содержать более 14 символов. Windows NT в своей файловой системе NTFS устанавливает, что имя файла может содержать до 255 символов, не считая завершающего нулевого символа. В разных файловых системах могут использоваться в качестве атрибутов разные характеристики, например: информация о разрешенном доступе, пароль для доступа к файлу, владелец файла, создатель файла, признак "только для чтения", "скрытый файл", «системный файл», "архивный файл", "двоичный/символьный", "временный" (удалить после завершения процесса), признак блокировки, длина записи, указатель на ключевое поле в записи, длина ключа, времена создания, последнего доступа, последнего изменения, текущий размер файла, максимальный размер файла. В FAT16 корневой каталог не является обычным файлом, он всегда расположен в начале диска и размер его фиксирован. Но уже в FAT32 придумали, как разрешить изменять размер корневого каталога, хотя он по-прежнему располагается в начале диска. В файловой системе FAT используется системная структура – таблица FAT. С каждым блоком диска (кластером) связывается одна запись таблицы FAT (номер записи = номеру кластера). Если кластер с номером К распределен некоторому файлу, то в К-той записи таблицы FAT содержится номер следующего кластера данного файла. В NTFS принято следующее решение перечисление всех занимаемых файлом кластеров: действительно запись в MFT – файле имеет достаточно большой размер (1 Кб = 1024 байт). Кроме того, различаются начальные записи и записи продолжений, и если файл занимает очень много места, ему может быть выделена одна запись начальная и несколько записей – продолжений. В начальной записи стоит ссылка на запись продолжение. А в записи – продолжении перечисляются номера следующих кластеров файла и стоит ссылка на запись-продолжение (возможно, пустая). Таким образом, информация о занимаемых кластерах может занять несколько записей в файле MFT. Эти записи в общем случае располагаются не рядом (так как они занимаются по мере необходимости). полная информация о файлах в NFS (файловая система в UNIX) содержится в таблице индексных дескрипторов. Одна запись этой таблицы в два раза меньше от записи MFT – файла: 0.5 кб.

10. Структура жесткого диска: MBR, BR. Процесс загрузки компьютера. Утилиты поиска ошибок, разбиения диска на разделы, форматирования.

Физически жесткий диск представляет из себя «слоеный пирог»: несколько дисков-пластин собраны в пакет. Минимальная адресуемая единица диска – сектор. Его размер определяется физическими характеристиками: шаг перемещения читающей головки, качеством диска (дискеты) и системными ограничениями. На дискете каждый сектор имеет заголовок, на жестком диске возможны два варианта: заголовок вместе с сектором или заголовки вынесены на отдельный цилиндр (определяется аппаратно). Кластер равен 2ⁿ (степень двойки) секторов. n - константа для логического диска. Значение n может выбираться автоматически и задаваться вручную при форматировании диска. BR- область данных. Рассмотрим подробнее содержимое BR. Для этого вернемся к вопросу о последовательности загрузки компьютера. Итак, при включении электричества начинает работать BIOS – программа на микросхеме. Эта программа выбирает из специальной памяти CMOS некоторые характеристики компьютера. Если в CMOS задано, что загрузочным является диск «С:», то BIOS должна найти ОС на диске «С:». Следовательно, она должна знать, в какую часть диска обратиться и как прочесть то, что там написано. Очевидно, что простейшим решением является следующее: в самом начале диске всегда храним специальную запись - MBR (master boot record). Эта запись состоит из двух частей: таблицы разделов (Partition table) и начального загрузчика (IPL Initial Program Loader). BIOS передает управление IPL. Таблица разделов представляет собой таблицу из четырех строк (!), в каждой из которых написан адрес начала раздела и адрес конца раздела, а также некоторые характеристики раздела. Важнейшая характеристика раздела - является ли он загружаемым. Обычно загружаемым является один раздел диска, но могут быть и несколько. Загрузчик IPL начинает работу по загрузке ОС. Для этого он отыскивает в таблице разделов загружаемый раздел и передает управление загрузчику из BR – записи загружаемого раздела. Структура BR похожа на структуру MBR. Только в ней вместо таблицы разделов хранится таблица характеристик текущего раздела, а вместо начального загрузчика – просто загрузчик. Загрузчик в BR - операционно-зависимый загрузчик, он «знает», какая ОС установлена в текущем разделе, то есть он «знает», какие файлы представляют собой ядро ОС, кому передавать управление. Последовательность программ, работающих при загрузке компьютера, и отметим данные, с которыми эти программы работают:BIOS – CMOS, IPL – Partition Table, PL – BR, ОС. Разбиение диска на разделы. Это делается несколькими программами. В списке стандартных программ находим FDISK – программа, разбивающая диск на разделы. Основной ее недостаток в том, что она не может изменить границы ранее заполненных разделов. Несколько больше возможностей у программы PARTM. Обе они могут разбить диск на разделы, то есть создать и заполнить MBR. Одну из этих программ следует запустить на вновь купленном диске. Затем следует запустить программу FORMAT. Она продолжит структурирование. Программы форматирования могут, кроме того, переписывать заголовки секторов, что повышает надежность работы диска. Рекомендуется неустойчиво работающую дискету отформатировать заново. Format затирает всю информацию на диске!

Есть программы, совмещающие оба действия по структурированию диска. Такова PQMagic, она и разбивает диск на разделы и сразу форматирует эти разделы. Более того, она делает это аккуратно, поэтому ее можно запускать даже на диске с информацией (данные будут сохранены

11. Файловые системы FAT.

Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие "файловая система" включает: совокупность всех файлов на диске, наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске, - комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами. Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие "файловая система" включает: совокупность всех файлов на диске, наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске, комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами. В файловой системе FAT используется системная структура – таблица FAT. С каждым блоком диска (кластером) связывается одна запись таблицы FAT (номер записи = номеру кластера). Если кластер с номером К распределен некоторому файлу, то в К-той записи таблицы FAT содержится номер следующего кластера данного файла (это число является также и номером той записи таблицы FAT, в которой содержится информация о продолжении файла!). FAT – таблица, содержащая столько строк, сколько кластеров на диске. В каждой строке содержатся данные одного из четырех типов: свободный кластер, сбойный кластер, ссылка на следующий кластер файла, признак конца файла. Т.к. нам надо записать в строку FAT номер кластера, то количество бит, выделяемых под номер должно быть достаточным для представления самого большого возможного на данном диске номера. Было принято решение выделять под адрес на диске 16 бит, позволивший адресовать 65532 кластера. Так родилась FAT16. На дискетах принято выделять под адрес 12 бит (FAT12). С течением времени емкость жестких дисков возрастала, и потребовалось адресовать большее количество кластеров. И потому появилась FAT32, адресующая 2³²=4,294,967,296 кластеров. FAT – содержит информацию, без которой доступ к диску становится невозможным. Для того, чтобы надежнее хранить эту информацию, было решено хранить на диске и копию FAT, расположенную следом за оригиналом. Кроме того, нужно еще где-то записать данные о самой FAT (например, о ее разрядности!). С этой целью выделили в начале диска один сектор, в который поместили так называемую boot record (загрузочную запись). Таким образом, получаем следующую структуру:

FAT1

FAT2

Корн.

каталог

02 – n

n –2n

2n – m-1

m+1

m+2

m+3

m+4

m+5

m+6

m+7

m+8

m+9

m+10

m+11

1кластер

2 кластер

3 кластер …

12. Файловая система NTFS.

Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие "файловая система" включает: совокупность всех файлов на диске, наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске, комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами. В NTFS принято следующее решение: действительно запись в MFT – файле имеет достаточно большой размер (1 Кб = 1024 байт). Кроме того, различаются начальные записи и записи продолжений, и если файл занимает очень много места, ему может быть выделена одна запись начальная и несколько записей – продолжений. В начальной записи стоит ссылка на запись продолжение. А в записи – продолжении перечисляются номера следующих кластеров файла и стоит ссылка на запись-продолжение (возможно, пустая). Таким образом, информация о занимаемых кластерах может занять несколько записей в файле MFT. Эти записи в общем случае располагаются не рядом (так как они занимаются по мере необходимости).NTFS является 32-разрядной файловой системой

NTFS фрагмент MFT- файла
31	…
32	имя атрибуты дата время 37 38 … 57 112…190 начальная 33
33	191 192 235 2 3 4 5 300 301 302 303 304…503 продолжение нет
34	…

Как и любая другая система, NTFS делит все полезное место на кластеры - блоки данных, используемые единовременно. NTFS поддерживает почти любые размеры кластеров - от 512 байт до 64 Кбайт. Диск NTFS условно делится на две части. При форматировании первые 12% диска отводятся под так называемую MFT зону - пространство, в которое растет метафайл MFT (об этом ниже). Запись каких-либо данных в эту область невозможна. MFT-зона всегда держится пустой - это делается для того, чтобы самый главный, служебный файл (MFT) не фрагментировался при своем росте. Остальные 88% диска представляют собой обычное пространство для хранения файлов.

MFT –зона

данные

Самый главный файл в NTFS называется MFT, или Master File Table - общая таблица файлов. Именно он размещается в MFT зоне и представляет собой централизованный каталог всех остальных файлов диска, включая себя самого. Первые 16 файлов NTFS (метафайлы) носят служебный характер. Каждый из них отвечает за какой-либо аспект работы системы. Каталог в NTFS представляет собой специфический файл, хранящий ссылки на другие файлы и каталоги, создавая иерархическое строение данных на диске. Файл каталога поделен на блоки, каждый из которых содержит имя файла, базовые атрибуты и ссылку на элемент MFT, который уже предоставляет полную информацию об этом файле.

Системы, её поддерживающие NT4, NT5, Максимальный размер тома- практически неограничен, Безопасность- да (начиная с NT5.0 встроена возможность физически шифровать данные), Сжатие-да, Устойчивость к сбоям- полная - автоматическое восстановление системы при любых сбоях (не считая физические ошибки записи, когда пишется одно, а на самом деле записывается другое, Экономичность- максимальна. Очень эффективная и разнообразная система хранения данных, Быстродействие-система не очень эффективна для малых и простых разделов (до 1 Гбайт), но работа с огромными массивами данных и внушительными каталогами организована как нельзя более эффективно и очень сильно превосходит по скорости другие системы

13. Анализ быстродействия файловых систем.

Сравнение быстродействие FAT и NTFS.

Самое фундаментальное свойство любой файловой системы, влияющее на быстродействие всех дисковых операций - структура организации и хранения информации. Любая файловая система хранит данные файлов в неких объемах - секторах, которые используются аппаратурой и драйвером как самая маленькая единица полезной информации диска. Размер сектора в подавляющем числе современных систем составляет 512 байт, и все файловые системы просто читают эту информацию и передают её без какой либо обработки приложениям. Исключений здесь практически нет. Если файл хранится в сжатом или закодированном виде - как это возможно, к примеру, в системе NTFS - то, конечно, на восстановление или расшифровку информации тратится время и ресурсы процессора. В остальных случаях чтение и запись самих данных файла осуществляется с одинаковой скоростью, какую файловую систему вы не использовали бы. Скорость чтения сектора с диска не зависит от файловой системы, а зависит только от диска.

	FAT	FAT32 (vFAT)	NTFS
Быстродействие	высокое для малого числа файлов, но быстро уменьшается с появлением большого количества файлов в каталогах. Результат - для слабо заполненных дисков - максимальное, для заполненных - плохое	полностью аналогично FAT, но на дисках большого размера (десятки гигабайт) начинаются серьезные проблемы с общей организацией данных	система не очень эффективна для малых и простых разделов (до 1 Гбайт), но работа с огромными массивами данных и внушительными каталогами организована как нельзя более эффективно и очень сильно превосходит по скорости другие системы

14. Системы распределения памяти. Кэширование. Дисковый кэш. Кэш оперативной памяти.

Принцип кэширования Принцип кэширования состоит в следующем. Пусть есть два способа получения информации: первый быстрый, а второй – медленный. Причем часто требуется информация, которая была уже выбрана ранее. Первичный источник информации – тот, доступ к которому затруднен. Очевидный способ ускорения получения информации – хранение ее в некотором буфере с высокой скоростью доступа. Такой скоростной буфер называют кэш. Физически это может быть и аппаратное средство, и программный способ хранения данных. Ускорение доступа к информации происходит за счет того, что она сначала ищется в кэш, и только если ее там нет, осуществляется более длительный поиск в первичном источнике. Очевидно, что в случае, если информация не требуется повторно, использование кэш не только не полезно, но и вредно, так как замедляет поиск. Кэш оперативной памяти.

Память вычислительной машины представляет собой иерархию запоминающих устройств (внутренние регистры процессора, различные типы сверхоперативной и оперативной памяти, диски, ленты), отличающихся средним временем доступа и стоимостью хранения данных в расчете на один бит. Пользователю хотелось бы иметь и недорогую и быструю память. Кэш-память представляет некоторое компромиссное решение этой проблемы. Иерархия запоминающих устройств:регистры процессора, кэш – память,оперативная память, дисковый кэш, жесткий диск, гибкий диск (дискета), магнитные ленты. Кэш-память – это способ организации совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования в «быстрое» ЗУ наиболее часто используемой информации из «медленного» ЗУ. Кэш-памятью часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств – «быстрое» ЗУ. Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. В современных компьютерах кэш – память встроена в процессор. Важно, что механизм кэш-памяти является прозрачным для пользователя, который не должен сообщать никакой информации об интенсивности использования данных и не должен никак участвовать в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами. Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных. Каждая запись об элементе данных включает в себя адрес, который этот элемент данных имеет в оперативной памяти, и управляющую информацию: признак модификации и признак обращения к данным за некоторый последний период времени, и конечно, собственно данные. Сами записи кэш-памяти не нумеруются. Дисковый кэш. Дисковый кэш используется для ускорения обмена данными между оперативной памятью и внешней памятью (диском). В этом случае уменьшается среднее время доступа к данным, расположенным на диске, и роль кэш-памяти выполняет фрагмент оперативной памяти, который используется особым образом.

15. Физическая и логическая адресация оперативной памяти.

Основная задача процессора – производить некоторые вычисления. Условно это происходит так: на специальные контакты (регистры) подаются двоичные значения, задается операция, операция выполняется, и в другой регистр помещается результат. Для того чтобы что-то посчитать, необходимо извлечь значение из некоторой ячейки ОП, следовательно, процессор должен работать и с адресом, как со значением.

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

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

С появлением процессора i80286, способным работать не только в реальном, но и в защищенном режиме, появилась возможность создать более совершенные системы управления памятью. В это же время вырос объем доступной ОП, что поставило задачу ее адресации.

В защищенном режиме программа не оперирует непосредственно физическими адресами памяти, она работает с так называемыми логическими адресами. Задача ОС – во время работы программы преобразовать логический адрес в физический. Чтобы провести это преобразование операционной системе требуется таблица дескрипторов. Эту таблицу снабдили дополнительными полями, которые позволяют ОС контролировать правильность использования выделенной памяти: вид сегмента, поле доступа и т.п. Вид использования сегмента поясняет, что за информация расположена в этом сегменте – код программы (кодовый) или данные программы (переменные, массивы и т.д.) или это системный сегмент (ОС). Поле доступа определяет вид использования сегмента: только для чтения, только для записи, чтение – запись.

Логический адрес состоит из двух частей: селектора и смещения. Селектор служит индексом (номером строчки) в таблице дескрипторов. Дескриптор описывает сегмент памяти и содержит базовые адреса, а также некоторые характеристики.

Селектор (16 разрядов)	Таблица дескрипторов	Смещение (16 разрядов)

	Базовый адрес – номер сегмента оперативной памяти	+

		Физический адрес

Такая схема адресации использовалась в ранних версиях ОС IBM OS/2, MS Windows 3.x.

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

Вид доступа – это максимальный номер кольца защиты программы, которой разрешается доступ к данному сегменту. Три уровня защиты, называются кольцами защиты. Самым привилегированным является 0 кольцо защиты, в котором могут находиться только ядро ОС и драйверы. В 1 и 2 кольце защиты могут располагаться менее критичные системы такие, как программы обслуживания, программы, работающие с портами аппаратуры, системы управления базами данных и т.п. Обычные программы работают в 3 кольце защиты.

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

16. Организация работы с виртуальной памятью в Windows.

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

Размер страницы памяти определяется аппаратной реализацией процессора.

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

Такая схема неплохо работает в многопользовательских операционных системах.В однопользовательской же операционной системе, которой преимущественно является Windows, такой алгоритм работы оказывается неоптимальным. Цель, стоящая перед Windows 95/98, совсем иная: не обеспечение максимальной загрузки процессора для наиболее полного использования его вычислительной мощности, а создание наибольших удобств для пользователя, то есть в первую очередь минимизация времени, требующегося на переключение между задачами, естественно, не за счет существенного замедления работы задач.

Особенности работы с виртуальной памятью в Windows:

1. Размер файла подкачки динамически увеличивается и уменьшается во время, когда компьютер не загружен работой.

2. Страницы с измененными данными копируются в файл подкачки (не выгружаются, а переписываются, оставаясь в памяти) во время, когда компьютер не загружен другой работой.

3. LE (Linear Executable) – задачи. Их запуск начинается не с загрузки программного кода в память, а с распределения памяти и сопоставления страниц виртуальной памяти участкам файла программы.

4. Windows 98 же может выполнять программный код непосредственно из кэш.

5. Windows 98 увеличивает файл подкачки ступенями по 4 МБ, стремясь при этом, чтобы каждый такой участок был непрерывным.

6. Windows 95 при завершении работы уменьшает размер файла подкачки до минимума, а после запуска вновь его увеличивает. Windows 98 этого не делает.

7. Windows 95 выжидает 45 секунд, а Windows 98 - две минуты, прежде чем уменьшить размер файла подкачки.

17. CMOS и BIOS, драйверы в Windows. Управление операциями ввода-вывода. Уровни организации операций ввода-вывода. Разделяемые и выделенные устройства. Синхронные и асинхронные передачи.

BIOS, CMOS

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

CMOS – микросхема полупроводниковой памяти с очень низким потреблением электроэнергии, в ПК она питается от маленькой батареи. Объем ее невелик – 64 байт, в ней содержатся данные, сохраняющиеся даже при отключении компьютера.

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

На современных компьютерах сохранность данных в CMOS обеспечивается применением никель-кадмиевых аккумуляторов, постоянно подзаряжаемого при работе компьютера. Раньше выход из строя батареи мог привести к катастрофическим последствиям. Но и аккумулятор может сломаться. Обязательно нужно сохранять копию всех данных, записанных в CMOS.

Содержащаяся в CMOS информация используется базовой системой ввода-вывода BIOS (Basic Input/Output System). Имеется несколько видов BIOS. Например, видео - BIOS обеспечивает интерфейс между процессором и видеоадаптером. Однако наиболее важные задачи обеспечивает системная BIOS. Физически она записана на микросхеме ROM (ПЗУ), расположенной на материнской плате, и копируется во время загрузки в сегмент верхней памяти ОЗУ объемом 64 Кбайт для быстрого доступа. В функции системной BIOS входят загрузка системы, распознавание имеющихся аппаратных устройств, поиск и запуск ОС. Когда ОС загружена, BIOS обеспечивает ей доступ к аппаратуре.

Сразу после включения компьютера BIOS начинает процедуру тестирования, затем проверяет и инициализирует аппаратные устройства системы. За исключением устройств с собственными BIOS (например, видеоадаптеров и контроллеров SCSI) инициализация остальных устройств производится на основании данных, сохраняемых в CMOS.

Пока идет тестирование, BIOS предоставляет доступ к небольшой утилите, обычно называемой Setup, которая дает возможность определить и изменить текущие параметры CMOS. Утилита Setup предлагает несколько меню, конкретный вид которых зависит от используемой BIOS, но всегда есть нечто общее: меню стандартных параметров CMOS и меню (одно или несколько) расширенных (дополнительных) параметров.

В CMOS можно произвести установку системного времени и даты, задать тип монитора.

Синхронные и асинхронные передачи. Разделяемые и выделенные устройства.

Большинство операций физического ввода-вывода выполняется асинхронно - процессор начинает передачу и переходит на другую работу, пока не наступает прерывание. Пользовательские программы намного легче писать, если операции ввода-вывода блокирующие(синхронные) - после команды READ программа автоматически приостанавливается до тех пор, пока данные не попадут в буфер программы. Асинхронные(блокирующие) обращения к устройствам тоже доступны программам.

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

Последняя проблема состоит в том, что одни устройства являются разделяемыми, а другие - выделенными. Наличие выделенных устройств создает для операционной системы некоторые проблемы.

Для решения поставленных проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя:

· Обработка прерываний,

· Драйверы устройств,

· Независимый от устройств слой операционной системы,

· Пользовательский слой программного обеспечения.

Уровни организации операций ввод-вывод.

Обработка прерываний

Прерывания должны быть скрыты как можно глубже в операционной системе, чтобы как можно меньшая часть ОС имела с ними дело. Наилучший способ состоит в разрешении процессу, инициировавшему операцию ввода-вывода, блокировать себя до завершения операции и наступления прерывания. При наступлении прерывания процедура обработки прерывания выполняет разблокирование процесса, инициировавшего операцию ввода-вывода, используя вызовы UP, SIGNAL или посылая процессу сообщение. В любом случае эффект от прерывания будет состоять в том, что ранее заблокированный процесс теперь продолжит свое выполнение.

Драйверы устройств

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

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

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

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

Независимый от устройств слой операционной системы

Большая часть программного обеспечения ввода-вывода является независимой от устройств. Точная граница между драйверами и независимыми от устройств программами определяется системой, так как некоторые функции, которые могли бы быть реализованы независимым способом, в действительности выполнены в виде драйверов для повышения эффективности или по другим причинам.

Типичными функциями для независимого от устройств слоя являются:

обеспечение общего интерфейса к драйверам устройств,

именование устройств,

защита устройств,

обеспечение независимого размера блока,

буферизация,

распределение памяти на блок-ориентированных устройствах,

распределение и освобождение выделенных устройств,

уведомление об ошибках.

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

Пользовательский слой программного обеспечения

Хотя большая часть программного обеспечения ввода-вывода находится внутри ОС, некоторая его часть содержится в библиотеках, связываемых с пользовательскими программами. Системные вызовы, включающие вызовы ввода-вывода, обычно делаются библиотечными процедурами. Форматирование ввода или вывода выполняется библиотечными процедурами. Примером может служить функция printf языка С, которая принимает строку формата и, возможно, некоторые переменные в качестве входной информации, затем строит строку символов ASCII и делает вызов write для вывода этой строки. Стандартная библиотека ввода-вывода содержит большое число процедур, которые выполняют ввод-вывод и работают как часть пользовательской программы.

Другой категорией программного обеспечения ввода-вывода является подсистема распределения выделенного устройства в мультипрограммной системе. Рассмотрим типичное разделяемое устройство – строчный принтер. Хотя технически легко позволить каждому пользовательскому процессу открыть специальный файл, связанный с принтером, такой способ опасен из-за того, что пользовательский процесс может монополизировать принтер на произвольное время. Вместо этого создается специальный процесс - монитор, который получает исключительные права на использование этого устройства. Также создается специальный каталог, называемый каталогом спулинга. Для того чтобы напечатать файл, пользовательский процесс помещает выводимую информацию в этот файл и помещает его в каталог спулинга. Процесс-монитор по очереди распечатывает все файлы, содержащиеся в каталоге спулинга.

18.Драйверы устройств. Технология "Plug and Play". Контроллеры устройств. распределение функций между контроллером и драйвером. Контроль и обработка ошибок. Синхронные и асинхронные передачи.

Драйверы устройств

Если вы вставили в компьютер устройство, поддерживающее технологию Plug-and-Play то при следующей загрузке, ОС определит тип и вид устройства, попытается найти драйвера на него установит и настроит их для нормальной работы устройства. Если устройство не найдено последует предложение его установить.

Контроллеры устройств. распределение функций между контроллером и драйвером. Контроль и обработка ошибок.

Внешнее устройство обычно состоит из механического и электронного компонента. Электронный компонент называется контроллером (ударение на втором слоге, а не на третьем!) устройства или адаптером. Механический компонент представляет собственно устройство. Некоторые контроллеры могут управлять несколькими устройствами. Если интерфейс между контроллером и устройством стандартизован, то независимые производители могут выпускать совместимые как контроллеры, так и устройства.

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

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

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

Синхронные и асинхронные передачи.

· Обработка прерываний,

· Драйверы устройств,

· Независимый от устройств слой операционной системы,

· Пользовательский слой программного обеспечения.

19.Операционная система UNIX. Основные характеристики. Процессы - демоны. Взаимодействие процессов.

Основные характеристики

В операционной системе UNIX административное управление отделено от общепользовательского доступа. Привилегированный пользователь – это пользователь, который имеет доступ ко всем ресурсам системы без всяких ограничений.

У каждого файла в UNIX-like системах есть владелец и группа. Владелец имеет только одну привилегию, которая другим пользователям системы не доступна: он может изменять права доступа к файлу. Владелец файла – это всегда один человек. Группа – один или несколько. Важной особенностью является то, что владелец файла может не являться членом группы, владеющей файлом. Это дает большую гибкость в организации доступа к файлам.

UNIX отслеживает не символьные имена владельцев и групп, а их идентификаторы. Идентификаторы пользователей (UID) и соответствующие им имена пользователей хранятся в файле /etc/passwd, а идентификаторы групп (GID) и соответствующие им имена – в файле /etc/group. Символьные имена, соответствующие UID и GID, определяются исключительно для удобства пользователя.

Ядро назначает каждому процессу 4 идентификатора: реальный и эффективный UID, реальный и эффективный GID. Реальные ID используются для учета системных ресурсов, а эффективные – для определения прав доступа. Владелец процесса может посылать в процесс сигналы, а также понижать приоритет процесса. Повышать же приоритет процесса может только привилегированный пользователь.

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

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

В операционной системе UNIX существует восемь типов файлов:

· обычные файлы;

· каталоги;

· байт-ориентированные устройства;

· блок-ориентированные устройства;

· доменные гнезда UNIX;

· именованные каналы (FIFO);

· жесткие ссылки (“прямая связь”);

· символические ссылки (“косвенная связь”);

Каждому файлу в ОС UNIX соответствует набор, состоящий из девяти битов кода прав доступа для пользователя, который определяет, какие пользователи имеют право читать файл, записывать в него некие данные или выполнять его. Дополнительные 3 бита задают коды прав доступа для выполняемых файлов. Эти 12 бит образуют код прав доступа к файлу. Еще 4 бита отводится для хранения информации о типе файла. Эти 4 бита типа файла устанавливаются при его создании и изменению не подлежат.

Биты с восьмеричными значениями 4000 и 2000 – это биты смены идентификатора пользователя и идентификатора группы. Эти биты позволяют программам получать доступ к файлам и процессам, к которым имеет доступ владелец или группа, владеющая данной программой.

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

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

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

Новый процесс в операционной системе UNIX создается путем клонирования одного из уже существующих процессов, после чего текст клона заменяется текстом программы (т.е. последовательностью машинных кодов, выполняемых центральным процессором), которую должен выполнять процесс. Процесс, с которого был клонирован новый процесс в терминологии ОС UNIX называют родительским, а его клон – порожденным. Процесс, помимо собственного идентификатора имеет атрибут PPID – идентификатор своего родительского процесса.

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

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

GID – это реальный идентификатор группы, равный идентификатору GID его родительского процесса.

Эффективный идентификатор группы EGID аналогичен по своему предназначению эффективному идентификатору пользователя.

В UNIX-like системах существует такое понятие, как значение nice. Значение nice подсказывает ядру, как следует относиться к данному процессу по сравнению с другими процессами, борющимися за время центрального процессора. Сигнал – это способ сообщить процессу о каких-либо изменениях и заставить его поступить надлежащим образом. В ОС UNIX определено свыше 30 различных видов сигналов.

Процессы - демоны

Демоны – не интерактивные процессы, запускающиеся обычным образом – путем загрузки в память соответствующих им выполняемых файлов, и предназначенные для выполнения в фоновом режиме. Демоны обеспечивают работу самых различных подсистем UNIX: системы терминального доступа, система печати, системы сетевого доступа и сетевых услуг и многое-многое другое. Обычно демоны запускаются при загрузке системы (после инициализации ядра) и находятся в памяти все время до ее останова. Демоны не связаны с пользовательским сеансом работы и не могут непосредственно управляться пользователем. Большую часть своего времени демоны ожидают пока тот или иной процесс запросит определенную услугу.

Взаимодействие процессов.

ОС UNIX с самого рождения является многозадачной. Это означит, что одновременно в системе может выполняться несколько процессов, причем часть процессов могут быть образцами одной программы. Выполнение процесса заключается в точном следовании набору инструкций, который никогда не передает управление набору инструкций другого процесса. Процесс считывает и записывает информацию в раздел данных и в стек, но ему не доступны данные и стеки других процессов. Однако процессы в UNIX-like системах могут обмениваться между собой информацией с помощью межпроцессного взаимодействия. В системах UNIX существует набор средств взаимодействия между процессами, таких как сигналы, каналы, разделяемая память, семафоры, сообщения и файлы, но в остальном процессы гарантированно изолированы друг от друга. Именно так реализованы все UNIX-like системы.

20. Реестр. Назначение, структура, хранение на диске.

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

Операционной системе требуется управлять большим набором оборудования и программного обеспечения. В ранних версиях Windows вся информация об этом хранилась в разбросанных по всему диску файлах с расширением ini. Это могла легко привести к неработоспособности ОС. Поэтому, начиная с W95 все данные, необходимые ОС при загрузке и конфигурировании были собраны и помещены в единую базу данных, называемую реестром.

Разделы реестра называются ключами, подразделы – подключами. Нижние элементы этой иерархии называются значениями.

Для каждого ключа нижнего уровня имеется специальное значение Default (по умолчанию), хотя часто оно не заполнено. Значения могут быть нескольких типов: целое число, длинное целое, однострочный текст, многострочный текст, текст с возможностью макроподстановки, двоичное значение и т.п.

Ключ HKEY_LOCAL_MACHINE и его подключи

Этот ключ содержит информацию об аппаратном и программном обеспечении.

HARDWARE - здесь содержится множество подключей, в которых хранится вся информация об аппаратном обеспечении, о драйверах, которые управляют аппаратурой компьютера. Важно, что эта информация формируется на лету менеджером устройств plug-and-play во время загрузки компьютера. Поэтому это - динамическая временная информация, и она не хранится на диске.

SAM - администратор учетных данных в системе безопасности (Security Account Manager) хранит имена пользователей, групп пароли, а также другую информацию об учетных записях пользователей, необходимую для регистрации в системе. Раздел недоступен для просмотра в программе REGEDIT.

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

SOFTWARE - это место, в котором производители программного обеспечения хранят настройки программ. Причем традиционно, подключ этого ключа - имя фирмы-производителя, а еще ниже располагаются подключи с именами программ. Записи в этих подключах - некоторые параметры настройки программы, такие как номера версии и сборки, сведения о драйверах и т.п. Специфическая для отдельных пользователей информация приложений хранится в реестре в ключе HKEY_USERS.

SYSTEM - содержит главным образом информацию о запуске системы, например, список драйверов, которые следует загрузить. Также содержится список служб (демонов в терминологии UNIX), которые должны быть запущены после загрузки, и сведения об их конфигурации.

Ключ HKEY_USERS.

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

Подключи HKEY_USERS.

USER-name-ID Информация о пользователях, по одному на каждого пользователя. После слова USER идет имя пользователя, затем его идентификатор SID. Ниже располагаются подключи, описывающие настройки для только что указанного пользователя.

AppEvents - Профиль пользователя.

Console - какой звук, когда издавать.

Control - установка командного режима (цвета, шрифты, история, ...)

Panel - внешний вид рабочего стола, заставка, чувствительность мыши, ...

Environment - переменные окружения.

KeyBoardLayout - раскладка клавиатуры.

Printers информация об установленных принтерах.

SoftWare - настройки пользователя для программного обеспечения Microsoft и других корпораций.

Ключ HKEY_PERFORMANCE_DATA.

Этот ключ не содержит данных, считываемых диска или собираемых менеджером plug-and-play. Это - окно в операционную систему. Сама система содержит сотни счетчиков для мониторинга производительности системы. К таким счетчикам можно получить доступ только через этот ключ реестра. При обращении к подключу запускается специальная процедура, собирающая и возвращающая информацию (возможно, считывающая один или несколько счетчиков и объединяющая их информацию). В редакторах REGEDIT и REDEDT32 этот ключ не виден. Вместо редактора нужно воспользоваться одной из утилит измерения производительности, таких как pfmon, perfmon, pview. Существует множество подобных программ.

Ключ HKEY_CLASSES_ROOT.

Остальных трех ключей верхнего уровня (CLASSES_ROOT, CURRENT_CONFIG, CURRENT_USER) на самом деле не существует. Каждый из них представляет собой символическую ссылку на определенный подключ реестра и вынесенный наверх с ускорения доступа к нему.

HKEY_ CLASSES_ROOT.

Этот ключ управляет объектами COM (Common Object Model), устанавливает соответствие между расширением файлов и вызываемыми программами.

HKEY_CURRENT_CONFIG

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

HKEY_CURRENT_USER

Настройки текущего пользователя.

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

Хранение реестра на диске.

Когда система выключается, большая часть данных реестра сохраняется на диске в файлах, называемых ульями. Большинство этих файлов располагаются в каталоге winnt\system32\config.

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

21. Структура сетевой операционной системы. Схема взаимодействия компонент.

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

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

Распределенная организация операционной системы позволяет упростить работу пользователей и программистов в сетевых средах. В распределенной ОС реализованы механизмы, которые дают возможность пользователю представлять и воспринимать сеть в виде традиционного однопроцессорного компьютера. Характерными признаками распределенной организации ОС являются: наличие единой справочной службы разделяемых ресурсов, единой службы времени, использование механизма вызова удаленных процедур (RPC) для прозрачного распределения программных процедур по машинам, многонитевой обработки, позволяющей распараллеливать вычисления в рамках одной задачи и выполнять эту задачу сразу на нескольких компьютерах сети, а также наличие других распределенных служб.

Сетевая ОС имеет в своем составе средства передачи сообщений между компьютерами по линиям связи, которые совершенно не нужны в автономной ОС. На основе этих сообщений сетевая ОС поддерживает разделение ресурсов компьютера между удаленными пользователями, подключенными к сети. Для поддержания функций передачи сообщений сетевые ОС содержат специальные программные компоненты, реализующие популярные коммуникационные протоколы, такие как IP, IPX, Ethernet и другие.

22. Пользователи системы, регистрация пользователей в системе, формирование групп пользователей, назначение прав доступа.

В Windows 2000,XP существует разделение ресурсов по пользователям. Согласно этому принципу каждый пользователь должен иметь свои учетные записи в системе. В этой учетной записи находится след. набор данных:

1. логин (имя пользователя)

2. пароль пользователя

3. набор прав (т.е. разрешения на определенные действия с ресурсами (чтение, запись, создание))

4. настройки (рабочего стола, главного меню)

С помощью инструментов администратора можно создавать группы, назначать им права и ресурсы. Это позволяет при добавлении нового пользователя в группу, назначать ему те же права, которые указаны для группы. Существуют след. встроенные группы:

1. Администратор

2. Гость

3 Опытный пользователь

4. Агент репликации

Администратор обладает самым широким набором прав. Гость - минимальным. Если пользователь находится в нескольких группах, то для него действуют эффективные права (самые широкие). При запуске Windows появляется окно с вопросами: имя пользователя, пароль, домен сети.

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

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

· Другие глобальные группы в том же домене

· Отдельные учетные записи из того же домена

Локальная в домене область действия

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

· Другие локальные в домене группы того же домена

· Глобальные группы из любого домена

· Универсальные группы из любого домена

· Отдельные учетные записи из любого домена

Универсальная область действия

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

· Другие универсальные группы

· Глобальные группы

· Отдельные учетные записи

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

23. Опишите данные и алгоритм распознавания тупиков в операционной системе.

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

Важно, что если процессам требуется один ресурс (а не два и более), то тупик никогда не возникает. При этом формируется обычная очередь к разделяемому ресурсу. Обычная очередь может возникнуть и при потребности в двух ресурсах (как видно из примера).

Проблема тупиков подразумевает решение следующих задач: предотвращение тупиков, распознавание тупиков, восстановление системы после тупиков.

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. Например, можно потребовать от всех программистов, чтобы в их программах ресурсы занимались только в заранее заданном порядке. Например, установим, следующую очередность занятия ресурсов: диск, модем, принтер, сетевая карта, … Тогда процесс А и процесс В из примера запрашивали бы ресурсы в этой заданной последовательности, и тупик был бы в принципе невозможен (формировались бы обычные очереди).

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

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

Таблица распределения ресурсов (какой процесс, какие ресурсы занимает)

Таблица запросов к ресурсам (какой процесс, какой ресурс ожидает)

MS WORD

Outlook Express

MS EXEL

Explorer

Win Commander

файл А

сетевая карта

файл В

Принтер

дисковод а:

Access

MS WORD

MS EXEL

Explorer

сетевая карта

файл В

Принтер

файл А

1. Берем первый процесс из таблицы ожидания. Access ожидает освобождения сетевой карты. Теперь по таблице распределения ресурсов отыскиваем процесс, который занимает сетевую карту. Это - Outlook Express. Теперь проверяем, какой ресурс ожидает Outlook Express. Поскольку его нет в таблице ожидания, делаем вывод о том, что он просто ожидает своей очереди, чтобы занять процессор, выполнить некоторые действия, после которых он освободит сетевую карту. Следовательно, тупика здесь нет. Кстати, если бы в таблице распределения не нашелся процесс, занимающий сетевую карту, то это говорило бы об ошибке в ОС. По-видимому, в таком случае ОС может распределить Access сетевую карту и перевести его в очередь готовых.

2. Теперь точно так же рассуждаем для следующего процесса из очереди ожидания - MS WORD. MS WORD ожидает файл В. В таблице распределения отыскиваем процесс, занимающий файл В. Это - MS EXEL. Теперь ищем MS EXEL в таблице запросов. Оказывается, он ждет принтер. Далее ищем в таблице распределения, кто занимает принтер. Это – Explorer. Снова по таблице ожидания ищем, что ожидает Explorer. Он ждет файл А. Наконец, по таблице распределения смотрим, какой процесс занимает файл А и обнаруживаем, что это - MS WORD. Так как вернулись к исходному процессу, делаем вывод о наличии тупика.

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

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Применение семафоров необходимо тогда, когда требуется определить степень занятости некоторого ресурса, а не просто получить ответ на вопрос «занят ресурс или свободен». Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул (список) в конец, а другой считывает их из буферного пула с первой записи списка и удаляет. Пусть буферный пул состоит из N записей. Процесс "писатель" должен приостанавливаться, когда все записи буфера оказываются занятыми, и активизироваться при освобождении хотя бы одной записи. Напротив, процесс "читатель" приостанавливается, когда все записи пусты, и активизируется при появлении хотя бы одной записи.

Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

#define N 256 /* Глобальные переменные

int e = N, f = 0, b = 1;

void Writer (){

while(1){

PrepareNextRecord(); /* подготовка новой записи */

P(e); /* Уменьшить число свободных буферов, если они есть */

/* в противном случае - ждать, пока они освободятся */

P(b); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

V(b); /* Выход из критической секции */

V(f); /* Увеличить число занятых буферов */

}

void Reader (){

while(1){

P(f); /* Уменьшить число занятых буферов, если они есть */

/* в противном случае ждать, пока они появятся */

P(b); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

V(b); /* Выход из критической секции */

V(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

}

Введение понятия семафоров иногда позволяют вообще избавиться от критической секции, если обеспечить, чтобы всегда работа шла с разными «частями» разделяемого ресурса. В приведенном примере этого можно было бы добиться, если потребовать, чтобы в буфере всегда была, по крайней мере, одна запись. Правда, такое требование может привести к тому, что последняя запись вообще останется не обработанной. Итак, оба процесса могут работать с разделяемым ресурсом одновременно!