Вопрос 10. Управление процессами. Синхр-ция процессов. Семофоры.

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

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

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

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

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

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

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

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

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

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

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

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

Вопрос 12. Общая модель файловой системы. Файловая система – часть ОС, предназначение которой – обеспечение пользовательского интерфейса для работы с файлами, находящимися на диске. Включает:

Совокупность всех данных на диске; Набор структур данных, использующихся для управления файлами; Совокупность систем, управления средствами, реализация управления файлами.

Самый нижний уровень – физический. Далее логический, ещё выше уровень проверки прав доступа, затем базовый. Самый высокий уровень – символьный.

На символьном уровне по символьному уровню файла определяется его уникальное имя. На базовом уровне определяется характеристика (права доступа, размер, местонахождение).Уровень проверки прав доступа определяет, что хочет сделать пользователь. Имена файлов. Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Так в популярной фай­ловой системе FAT длина имен ограничивается известной: 8 символов - собственно имя, 3 символа - расширение имени, а в ОС UNIX имя не может содержать более 14 символов. Windows NT в своей новой файловой системе NTFS устанавливает, что имя файла может содержать до 255 символов, не считая завершающего нулевого символа. При переходе к длинным именам возникает проблема совместимости с ранее созданными приложениями, использующими короткие имена.

Логическая организация файла. Программист имеет дело с логической организацией файла, представляя файл в виде определенным образом организованных логических записей. Логическая запись - это наименьший элемент данных, которым может оперировать программист при обмене с внешним устройством. Даже если физический обмен с устройством осуществляется большими единицами, операционная система обес­печивает программисту доступ к отдельной логической записи. Физическая организация и адрес файла. Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности на диске. Файл состоит из физических записей - блоков. Блок - наименьшая единица данных, которой внешнее устройство обменивается с оперативной памятью. Непрерывное размещение - простейший вариант физической организации, при котором файлу предоставляется последовательность блоков диска, образующих единый сплошной участок дисковой памяти. Для задания адреса файла в этом случае достаточно указать только номер начального блока. Другое достоинство этого метода - простота. Но имеются и два су­щественных недостатка. Во-первых, во время создания файла заранее не известна его длина, а значит не известно, сколько памяти надо зарезервировать для этого файла, во-вторых, при таком порядке размещения неизбежно возникает фрагментация, и пространство на диске используется не эффективно, так как отдельные участки маленького размера (минимально 1 блок) могут остаться не используе­мыми.

Вопрос 13. Файловая система FAT. Организация диска: загрузочный сектор; 2 копии таблицы размещения файлов; корневой каталог; сектора данных. В FAT ровно столько записей, сколько кластеров на диске. Размер кластера – 16 бит. Если в FAT записан 0, то соответствующий кластер пуст. Любое другое значение FAT соответствует номеру следующего кластера FAT, за исключением FFF8, FFFF, которые определяют последний кластер в файле. FFF7 означает сбойный кластер. В секторах, отведенных под..., хранится информация об именах файлов, размерах, датах создания, модификация, ссылка на FAT для первого кластера. Номер начального кластера записи каталога является отправной точкой для отслеживания данных файлов. Длина записи файла – 16 бит. Если всего 500 кластеров, то размер FAT 516 бит. Пусть длина файла 100 бит. Если меньше 512 бит, то значение FFFF. 16 битами можно закодировать 65535 блоков, но не больше. Т.о., диск 32 Мбт. Структура 1 физический сектор содержит: Таблицу описания разделов и программу начальной загрузки, предназначенная для проверки таблиц разделов и передачу управления одному из них. Таблица описания разделов содержит 4 элемента, каждый равен 16 байтам. Разделы расположены в обратном порядке со следующим смещением: 1ВЕ; 1СЕ; 1DЕ; 1ЕЕ. Со смещения 1FF расположен код АА55, который является подписью таблицы разделов. Каждый 16-байтовый код содержит следующую информацию: Смещение 01 бт – индикатор начальной загрузки; Смещение 1 бт – признак; Смещение 21 бт – начальный сектор; Смещение 31 бт – начальный цилиндр; Смещение 41 бт – системный индикатор; Смещение 51 бт – признак конца; Смещение 61 бт – конечный сектор; Смещение 71 бт – конечный цилиндр; Смещение 84 бт – начальный сектор; Смещение 04С бт –количество секторов на диске. Т.о. можно разбить на логические диски. Индикатор начальной загрузки равен 0 для незагрузочного раздела и ……. – для активного раздела. Системный индикатор: 0 – не определено; 1 – 12 бит MS-DOS; Сектор начальной загрузки: идентификатор разработчика; программа-загрузчик; блок параметров

Смещение 3 8 байт – имя и версия системы; Смещение 0В 2 байта – число байт (512) в секторе; Смещение 0D 1 байт – число секторов на устройстве; Смещение 0Е 2 байта – число резервных секторов; Смещение 13 2 байта – общее число секторов на логическом томе; Смещение 15 1 байт – дескриптор носителя данных; Смещение 16 2 байта – число секторов FAT; Смещение 1А 2 байта – число головок; Смещение 1С 2 байта – число невидимых секторов; Смещение 1Е ….байт – программа загрузчика

Формат кода каталога

Структура: имя (с 0 до 0В); атрибуты (0В-0С); резерв (0С-16); время (16-18); дата (18-1А); начальный кластер (1А-1С); размер файла (1С-1F)

Поле атрибутов (1 байт): 0 бит – постоянный файл; 1 бит – скрытный; 2 бит – системный; 3 бит – метка тома; 4 бит – подкаталог; 5 бит – архивный; 6 и 7 бит – резерв; Формат поля времени (2 байта): 0-4 бит – 2-хсекундное превращение значения от 0 до 29; 4-10 бит – минуты от 0 до 59; 10-15 бит – часы от 0 до 23;

Формат поля даты (2 байта): 0-4 бит – день от 0 до 31; 4-10 бит – месяц с 1 по 12; 10-15 бит – год относительно 1980