Найти ошибки и неточности в рассуждении, пояснить. Процесс – это одна программа. Дескриптор – это идентификатор процесса, а контекст – информация о других, одновременно работающих процессах. Процесс может перейти из очереди готовых в очередь ожидающих, если ему потребовался некоторый ресурс. В очереди ожидающих находятся процессы, ожидающие этот же ресурс.
Процесс (или по-другому, задача) – абстракция, описывающая выполняющуюся программу. Для операционной системы процесс представляет собой единицу работы, заявку на потребление ресурсов. Одна программа может создать несколько процессов.
Дескриптор процесса – это идентификатор процесса, состояние процесса, данные о степени привилегированности процесса (приоритет), номер кодового сегмента в оперативной памяти (адрес в оперативной памяти, с которого расположен код программы), адрес в кодовом сегменте, с которого начинается следующая выполняемая команда процесса и другая информация.
Состояние операционной среды определяется состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых данным процессом системных вызовов и т.д - это контекст процесса. Он необходим для продолжения прерванного процесса.
Процесс может перейти из очереди готовых в очередь ожидающих, если ему потребовался некоторый ресурс. В очереди ожидающих находятся процессы, ожидающие какой-либо занятый ресурс.
2. Найти ошибки и неточности в рассуждении, пояснить. Вытесняющая многозадачность используется в том случае, если требуется организовать одновременную работу процессов с одинаковым приоритетом. Не вытесняющая – когда есть один высокоприоритетный процесс. Проблема одновременного доступа к ресурсам решается путем введения приоритетов: ресурс всегда получает первым процесс с б о льшим приоритетом.
|
|
Понятия вытесняющей и не вытесняющей многозадачности не связаны с приоритетом процессов. Они различаются в степени централизации механизма планирования задач. В не вытесняющей многозадачности планирование задач производят сами приложения, они же решают, когда приостанавливать работу и передавать управление другому приложению. В вытесняющей многозадачности в качестве планировщика задач выступает операционная система. Проблема одновременного доступа к ресурсам может решаться несколькими способами: с помощью блокирующих переменных, семафоров, аппарата событий, мониторов и т.д.
_______________
Какие ошибки может допустить программист при написании программы, если операционная система использует только метод мьютексов (блокирующих переменных). Приведите примеры, поясните, к чему это приведет.
Мью́текс (англ. mutex, от mutual exclusion — «взаимное исключение») — одноместный семафор, служащий в программировании для синхронизации одновременно выполняющихся потоков.
Мьютексы — это один из вариантов семафорных механизмов для организации взаимного исключения. Они реализованы во многих ОС, их основное назначение — организация взаимного исключения для потоков из одного и того же или из разных процессов.
Мьютексы — это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний — отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какой-либо поток, принадлежащий любому процессу, становится владельцем объекта mutex, последний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмеченным.
|
|
Задача мьютекса — защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.
Цель использования мьютексов — защита данных от повреждения в результате асинхронных изменений (состояние гонки), однако могут порождаться другие проблемы — такие, как взаимная блокировка (клинч).
Мьютекс это одна из реализаций спинлок.
Мьютекс отличается от семафора общего вида тем, что только владеющий им поток может его освободить, т.е. перевести в отмеченное состояние.
_______________
Какие ошибки может допустить программист при написании программы, если операционная система использует только метод семафоров. Приведите примеры, поясните, к чему это приведет.
Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:
|
|
V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.
P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.
В частном случае, когда семафор 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(); /* Обработать запись */
}
}
Важно, что введение понятия семафоров иногда позволяют вообще избавиться от критической секции, если дополнительно обеспечить, чтобы всегда работа шла с разными «частями» разделяемого ресурса. В приведенном примере этого можно было бы добиться, если потребовать, чтобы в буфере всегда была, по крайней мере, одна запись. Правда, такое требование может привести к тому, что последняя запись вообще останется не обработанной. Итак, оба процесса могут работать с разделяемым ресурсом одновременно! Не забывайте про относительность одновременности в многопроцессной ОС.
Рассмотрим еще пример. Пусть Вам надо запрограммировать следующую задачу: пусть процесс ВВОД вводит с клавиатуры очередное слово на русском языке, конец слова определяется по символу ENTER. Признаком завершения ввода является ввод подряд двух ENTER. Это слово заносится в некоторый буфер, например, текстовый файл. Процесс ПЕРЕВОД выбирает по одному слова из файла, переводит их на английский язык и показывает на экране пользователя. Запись в файл сделаем ограниченной, то есть разрешим записывать не более чем N слов. Тогда процесс писатель должен приостановиться, если файл уже заполнен. Процесс перевод, выбирающий слова из файла, наоборот, должен приостановиться, если слов в файле не осталось. Таким образом, нам потребуется два семафора: «КВОСЛОВ» (количество слов) и «КВОСВМЕСТА» (количество свободного места).
| Процесс ВВОД: | Процесс ПЕРЕВОД: |
| если не определено КВОСЛОВ то определить семафор КВОСЛОВ КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то определить семафор КВОСВМЕСТА КВОСВМЕСТА = N конец если открыть файл P S = ввод очередного символа с клавиатуры SL =”” повторять повторять пока S<>ENTER SL = SL+S конец повтора ввода символов если SL<>”” то начало_крит_секции уменьшить(КВОСВМЕСТА) увеличить(КВОСЛОВ) перейти в конец файла записать в файл P слово SL конец_крит_секции конец если конец повтора пока SL<>”” закрыть файл P | если не определено КВОСЛОВ то определить семафор КВОСЛОВ КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то определить семафор КВОСВМЕСТА КВОСВМЕСТА = N конец если открыть файл P повторять пока ИСТИНА начало_крит_секции уменьшить(КВОСЛОВ) увеличить(КВОСВМЕСТА) перейти в начало файла прочесть слово передвинуть слова в файле вверх конец_крит_секции перевести слово вывести на экран конец повтора закрыть файл P |
_______________
Какие ошибки может допустить программист при написании программы, если операционная система использует только аппарат событий. Приведите примеры, поясните, к чему это приведет.
Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время, так как, очевидно, что в это время ресурс не может освободиться! Нерациональное использование процессора может происходить в течение одного или нескольких квантов времени. Заметим, что бывают ситуации, при которых ресурс, не занимаемый работающим в данный момент процессом, освобождается. Придумайте такую ситуацию.
Для устранения таких нежелательных потерь может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 4 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса d. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс d, после выхода из критической секции вызывает системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.
Рассмотрим пример. Пусть два процесса пишут поочередно сообщения в «почтовый ящик». Ящик считаем безразмерным. Сообщение может быть и длинным и коротким, очевидно, что два сообщения нельзя перемешивать. Заводим блокирующую переменную «МОЖНОПИСАТЬ», сигнализирующую о том, можно ли писать в настоящий момент в «почтовый ящик» (1 – можно писать, 0 – ящик занят). Процессы вводят сообщения от пользователя. Признаком конца сообщения является нажатие клавиши ENTER. Почтовым ящиком сделаем файл Р. Признаком конца всех сообщений F10.
Описание процессов А и В приведены ниже (они одинаковы!)
| Процесс А (или В): |
| если не определена МОЖНОПИСАТЬ то определить глобальную переменную МОЖНОПИСАТЬ МОЖНОПИСАТЬ = 1 конец если S = ввод очередного символа с клавиатуры SL =”” повторять повторять пока S<>F10 и S<>ENTER SL = SL+S S = ввод очередного символа с клавиатуры конец ввода символов WAIT(МОЖНОПИСАТЬ) открыть файл P записать в файл P сообщение SL закрыть файл P POST (МОЖНОПИСАТЬ) конец повтор пока S<>F10 |
Рисунок 4 - Реализация критической секции с использованием системных функций WAIT(D) и POST(D)
_______________
Для борьбы с тупиками предлагается обеспечить порядок занятия процессами ресурсов. Поясните на примере, в чем заключаются недостатки этого метода.
При использовании данного метода ресурсы могут заниматься даже тогда, когда они не нужны процессу. Например, если установлен следующий порядок: сетевая карта, диск, принтер, то для того, чтобы процессу занять диск, ему сначала необходимо занять сетевую карту, хотя она, возможно, ему не нужна.
_______________
Напишите программу (модель), которую выполняет операционная система в случае, когда работающий процесс освобождает ресурс. Программу необходимо написать на «русском» языке или на VBA, пояснив все используемые объекты.
_______________
Напишите программу (модель), которую выполняет операционная система в случае, когда пользователь желает запустить процесс. Программу необходимо написать на «русском» языке или на VBA, пояснив все используемые объекты.
Supervisor распределяет процессорное время между процессами -> Открытие пользователем исполняемого файла (ИФ) инициирует обработку прерывания -> Обращение к MFT файлу для чтения ИФ с HDD -> Чтение исполняемого файла c HDD в ОП -> Получение
Supervisor-ом данных о приоритете ИФ -> Выполнение кода исполняемого файла блоками, насколько хватает выделенного Supervisor-ом каждый раз процессорного времени с выгрузкой промежуточного состояния операндов и.т.д обратно в ОП.
_______________
9. Пусть на логическом диске расположены следующие файлы данных (в скобках указаны последовательно занимаемые кластеры). Изобразите все системные структуры этого логического диска в предположении, что диск содержит всего 30 кластеров и на нем установлена файловая система FAT16. A(24, 17, 30,2); B(21, 22, 23); C(18), Д(1,15).
Таблица FAT
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ||||||||||||
| # | # | # | |||||||||||||||||||||||||||||
| # | |||||||||||||||||||||||||||||||
| Каталог | ||
| А | ||
| B | ||
| C | ||
| D | ||
Диск
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ||||||||||||
| Д1 | A4 | Д2 | A2 | C | |||||||||||||||||||||||||||
| B1 | B2 | B3 | A1 | A3 | |||||||||||||||||||||||||||
_______________
Пусть на логическом диске расположены следующие файлы данных (в скобках указаны последовательно занимаемые кластеры). Изобразите все системные структуры этого логического диска в предположении, что диск содержит всего 60 кластеров и на нем установлена файловая система NTFS. A(24, 17, 30,2); B(21, 22, 23); C(18), Д(1,15).
| MFT- файл | ||
| A атрибуты дата 24 17 30 2 нет | ||
| B атрибуты дата 21 22 23 нет | ||
| С атрибуты дата 18 нет | ||
| Д атрибуты дата 1 15 нет | ||
_______________
Напишите программу (модель), которую выполняет операционная система в случае, когда работающий процесс записывает новый файл на диск с NTFS. Программу необходимо написать на «русском» языке или на VBA, пояснив все используемые объекты.
В NTFS задание физического расположения файла происходит путем простого перечисления номеров блоков, занимаемых этим файлом. В этом случае в некоторой системной таблице должно быть выделено место под номера всех кластеров файла. Для быстроты поиска системные таблицы обычно имеют фиксированный размер записи, следовательно, если выберем большой размер, то у большинства файлов это место будет просто не использоваться. Если же выберем маленький размер, то не сможем записать на диск файл из большого количества кластеров. Где же выход?
В NTFS принято следующее решение: действительно запись в MFT – файле имеет достаточно большой размер (1 Кб = 1024 байт). Кроме того, различаются начальные записи и записи продолжений, и если файл занимает очень много места, ему может быть выделена одна запись начальная и несколько записей – продолжений. В начальной записи стоит ссылка на запись продолжение. А в записи – продолжении перечисляются номера следующих кластеров файла и стоит ссылка на запись-продолжение (возможно, пустая). Таким образом, информация о занимаемых кластерах может занять несколько записей в файле MFT. Эти записи в общем случае располагаются не рядом (так как они занимаются по мере необходимости).
_______________
Напишите программу (модель), которую выполняет операционная система в случае, когда работающий процесс сохраняет измененный файл на диск с FAT32. Программу необходимо написать на «русском» языке или на VBA, пояснив все используемые объекты.
файловой системе FAT используется системная структура – таблица FAT. С каждым блоком диска (кластером) связывается одна запись таблицы FAT (номер записи = номеру кластера). Если кластер с номером К распределен некоторому файлу, то в К-той записи таблицы FAT содержится номер следующего кластера данного файла (это число является также и номером той записи таблицы FAT, в которой содержится информация о продолжении файла!).
При такой физической организации сохраняются все достоинства предыдущего способа, но снимаются оба отмеченных недостатка. Во-первых, для доступа к произвольному месту файла достаточно прочитать только таблицу FAT (она небольшая), отсчитать нужное количество записей по цепочке и определить номер нужного кластера. И, во-вторых, данные файла занимают кластер целиком, а значит, имеют объем, равный степени двойки.
Итак, FAT – таблица, содержащая столько строк, сколько кластеров на диске. В каждой строке содержатся данные одного из четырех типов: свободный кластер (на рисунке пусто), сбойный кластер (на рисунке отмечен буквой b), ссылка на следующий кластер файла (на рисунке числа), признак конца файла (на рисунке #).
Таблица FAT
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| # | # | # | b |
Диск
| A1 | A2 | B1 | C1 | B2 | A3 | A4 |
| Каталог | ||
| А | ||
| B | ||
| C | ||
_______________
Напишите программы (модель) для процессов «писатель» и «читатель», работающих с ограниченным буфером с применением метода семафоров. Программу необходимо написать на «русском» языке или на VBA, пояснив все используемые объекты.
_______________