Вордовские лекции (1115151), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

while (TRUE) /* бесконечный цикл */

{

down (&mutex); /* получить эксклюзивный доступ к «rc»*/

rc = rc+1; /* еще одним читателем больше */

if (rc==1) down (&db); /* если это первый читатель, нужно заблокировать эксклюзивный доступ к базе */

up(&mutex); /*освободить ресурс rc */

read_data_base(); /* доступ к данным */

down(&mutex); /*получить эксклюзивный доступ к «rc»*/

rc = rc-1: /* теперь одним читателем меньше */

if (rc==0) up(&db); /*если это был последний читатель, разблокировать эксклюзивный доступ

к базе данных */

up(&mutex); /*освободить разделяемый ресурс rc*/

use_data_read(); /* некритическая секция */

}

}

void writer (void)

{

while(TRUE) /* бесконечный цикл */

{

think_up_data(); /* некритическая секция */

down(&db); /* получить эксклюзивный доступ к данным*/

write_data_base(); /* записать данные */

up(&db); /* отдать эксклюзивный доступ */

}

}

В этом примере, первый процесс, обратившийся к базе данных по чтению, осуществляет операцию DOWN над семафором db, тем самым блокируя эксклюзивный доступ к базе, который нужен для записи. Число процессов, осуществляющих чтение в данный момент, определяется переменной rc (обратите внимание! Т.к. переменная rc является разделяемым ресурсом – ее изменяют все процессы, обращающиеся к базе данных по чтению – то доступ к ней охраняется семафором mutex). Когда читающий процесс заканчивает свою работу, он уменьшает rc на единицу. Если он является последним читателем, он также совершает операцию UP над семафором db, тем самым разрешая заблокированному писателю, если такой имелся, получить эксклюзивный доступ к базе для записи.

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

4.2.4.3Задача о «спящем парикмахере»

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

Одно из возможных решений этой задачи представлено ниже. Процедура barber() описывает поведение парикмахера (она включает в себя бесконечный цикл – ожидание клиентов и стрижку). Процедура customer() описывает поведение посетителя. Несмотря на кажущуюся простоту задачи, понадобится целых 3 семафора: customers – подсчитывает количество посетителей, ожидающих в очереди, barbers – обозначает количество свободных парикмахеров (в случае одного парикмахера его значения либо 0, либо 1) и mutex – используется для синхронизации доступа к разделяемой переменной waiting. Переменная waiting, как и семафор customers, содержит количество посетителей, ожидающих в очереди, она используется в программе для того, чтобы иметь возможность проверить, имеется ли свободное кресло для ожидания, и при этом не заблокировать процесс, если кресла не окажется. Заметим, что как и в предыдущем примере, эта переменная является разделяемым ресурсом, и доступ к ней охраняется семафором mutex. Это необходимо, т.к. для обычной переменной, в отличие от семафора, чтение и последующее изменение не являются неделимой операцией.

#define CHAIRS 5

typedef int semaphore; /* некий семафор */

semaphore customers = 0; /* посетители, ожидающие в очереди */

semaphore barbers = 0; /* парикмахеры, ожидающие посетителей */

semaphore mutex = 1; /* контроль за доступом к переменной waiting */

int waiting = 0;

void barber()

{

while (true) {

down(customers); /* если customers == 0, т.е. посетителей нет, то заблокируемся до появления посетителя */

down(&mutex); /* получаем доступ к waiting */

waiting = wating – 1; /* уменьшаем кол-во ожидающих клиентов */

up(&barbers); /* парикмахер готов к работе */

up(&mutex); /* освобождаем ресурс waiting */

cut_hair(); /* процесс стрижки */

}

void customer()

{

down(&mutex); /* получаем доступ к waiting */

if (waiting < CHAIRS) /* есть место для ожидания */

{

waiting = waiting + 1; /* увеличиваем кол-во ожидающих клиентов */

up(&customers); /* если парикмахер спит, это его разбудит*/

up(&mutex); /* освобождаем ресурс waiting */

down(barbers); /* если парикмахер занят, переходим в состояние ожидания, иначе – занимаем парикмахера*/

get_haircut(); /* занять место и перейти п стрижке */

}

else

{

up(&mutex); /* нет свободного кресла для ожидания – придется уйти */

}

}

4.3Управление оперативной памятью

Решение следующих задач:

• распределение физической памяти ОЗУ между процессами

• программная поддержка виртуальной памяти

• подкачка (свопинг)

• защита памяти

Конкретные алгоритмы зависят от свойств конкретной ЭВМ. Для модельной ЭВМ будем рассматривать страничную организацию ОЗУ. Пусть имеется ОЗУ, включающее до N физических страниц. Система команд машины позволяет адресовать до k страниц. Рассмотрим пример частичных действий модельно ОС по управлению ОП.

Операционная система формирует таблицу страниц (ТС):

К аждая строка ТС содержит информацию о статусе соответствующей физической страницы:

• свободна

• принадлежит j-му процессу (в этом случае в строке помещается ссылка на контекст соответствующего процесса)

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

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

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

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

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

СВОППИНГ

ЗАЩИТА ПАМЯТИ

4.4Планирование

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

• планирование очереди процессов на начало обработки процессором;

• планирование распределения времени ЦП между обрабатываемыми в мультипрограммном режиме процессами;

• планирование порядка обработки заказов на обмен с ВУ;

• планирование порядка обработки прерываний;

• планирование использования ОЗУ (организация свопинга).

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

4.4.1Планирование очереди процессов на начало обработки ЦП

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

4.4.2Планирование распределения времени работы ЦП между процессами

Здесь существует несколько проблем:

1. величина кванта времени работы ЦП, выделяемого выполняемому процессу.

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

4.4.3Планирование очереди запросов на обмен

Определение порядка обработки запросов, разрешение проблем взаимосвязанных запросов на обмен.

4.4.4Планирование порядка обработки прерываний

………………………

4.4.5Типы операционных систем

Итак, комплексное решение проблем планирования однозначно определяет основные эксплуатационные характеристики и тип операционной системы.

4.4.5.1Пакетная ОС

Рассмотри следующую модельную ситуацию. Пусть имеется пакет программ - некоторая совокупность программ, обладающих общим свойством – для выполнения каждой из программ необходимо значительное время работы ЦП. Необходимо обработать все программы пакета за минимальное время. Для этой цели используются специализированные пакетные ОС. Для данных ОС не является важным порядок в котором будут выполнены программы пакета и время за которое была выполнена та или иная программа пакета. Критерием эффективности пакетной ОС является минимизация времени, затраченного на выполнение всего пакета за счет минимизации, в свою очередь, непроизводительной работы ЦП. Основной задачей системы планирования пакетной ОС является максимальная загрузка процессора мультипрограммным выполнением программ/процессов пользователей. В частности, должны быть минимизировано время работы ОС. Это достигается за счет стратегии планирования, основанной на переключении выполнения одной программы/процесса на другую только в одном из следующих случаев:

• завершение выполнения программы/процесса;

• возникновение при выполнении программы/процесса прерывания (например, обращение к ВУ);

• фиксация операционной системой факта зацикливания процесса.

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

4.4.5.2Системы разделения времени

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

• исчерпании процессом выделенного кванта времени;

• завершении выполнения программы/процесса;

• возникновении при выполнении программы/процесса прерывания (например, обращение к ВУ);

• фиксации операционной системой факта зацикливания процесса.

Мы можем видеть, что стратегия планирования пакетной ОС может быть сведена к стратегии ОС разделения времени (если считать размер кванта времени ЦП, выделяемого процессам при пакетной обработке равным бесконечности).

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

4.4.5.3ОС реального времени

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

4.5Файловые системы

4.5.1Основные свойства, функции, определения

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

Характеристики

Список файлов лекций