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




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

 

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

Дескриптор процесса – это идентификатор процесса, состояние процесса, данные о степени привилегированности процесса (приоритет), номер кодового сегмента в оперативной памяти (адрес в оперативной памяти, с которого расположен код программы), адрес в кодовом сегменте, с которого начинается следующая выполняемая команда процесса и другая информация.

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

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

 

 

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, пояснив все используемые объекты.

_______________

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: