12.3.3.1 Выделение буфера

12.3.3.1 Выделение буфера

Обратимся еще раз к алгоритму getblk, рассмотренному нами в главе 3. Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостанова, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения.

алгоритм getblk /* многопроцессорная версия */

входная информация:

 номер файловой системы

 номер блока

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

{

 do while(буфер не будет обнаружен) {

  P(семафор хеш-очереди);

  if (блок находится в хеш-очереди) {

   if (операция CP(семафор буфера) завершается неудачно) { /* буфер занят */

    V(семафор хеш-очереди);

    P(семафор буфера); /* приостанов до момента освобождения */

    if (операция CP(семафор хеш-очереди) завершается неудачно) {

     V(семафор буфера);

     continue; /* выход в цикл "выполнять" */

    }

    else if (номер устройства или номер блока изменились) {

     V(семафор буфера);

     V(семафор хеш-очереди);

    }

   }

   do while(операция CP(семафор списка свободных буферов) не завершится успешно);

   /* "кольцевой цикл" */

   пометить буфер занятым;

   убрать буфер из списка свободных буферов;

   V(семафор списка свободных буферов);

   V(семафор хеш-очереди);

   return буфер;

  }

  else

   /* буфер отсутствует в хеш-очереди здесь начинается выполнение оставшейся части алгоритма */

 }

}

Рисунок 12.14. Выделение буфера с использованием семафоров

На Рисунке 12.14 показана первая часть алгоритма getblk, реализованная в многопроцессорной системе с использованием семафоров. Просматривая буферный кеш в поисках указанного блока, ядро с помощью операции P захватывает семафор, принадлежащий хеш-очереди. Если над семафором уже кем-то произведена операция данного типа, текущий процесс приостанавливается до тех пор, пока процесс, захвативший семафор, не освободит его, выполнив операцию V. Когда текущий процесс получает право исключительного контроля над хеш-очередью, он приступает к поиску подходящего буфера. Предположим, что буфер находится в хеш-очереди. Ядро (процесс A) пытается захватить буфер, но если оно использует операцию P и если буфер уже захвачен, ядру придется приостановить свою работу, оставив хеш-очередь заблокированной и не допуская таким образом обращений к ней со стороны других процессов, даже если последние ведут поиск незахваченных буферов. Пусть вместо этого процесс A захватывает буфер, используя операцию CP; если операция завершается успешно, буфер становится открытым для процесса. Процесс A захватывает семафор, принадлежащий списку свободных буферов, выполняя операцию CP, поскольку семафор захватывается на непродолжительное время и, следовательно, приостанавливать свою работу, выполняя операцию P, процесс просто не имеет возможности. Ядро убирает буфер из списка свободных буферов, снимает блокировку со списка и с хеш-очереди и возвращает захваченный буфер. Предположим, что операция CP над буфером завершилась неудачно из-за того, что семафор, принадлежащий буферу, оказался захваченным. Процесс A освобождает семафор, связанный с хеш-очередью, и приостанавливается, пытаясь выполнить операцию P над семафором буфера. Операция P над семафором будет выполняться, несмотря на то, что операция CP уже потерпела неудачу. По завершении выполнения операции процесс A получает власть над буфером. Так как в оставшейся части алгоритма предполагается, что буфер и хеш-очередь захвачены, процесс A теперь пытается захватить хеш-очередь[34]. Поскольку очередность захвата здесь (сначала семафор буфера, потом семафор очереди) обратна вышеуказанной очередности, над семафором выполняется операция CP. Если попытка захвата заканчивается неудачей, имеет место обычная обработка, требующаяся по ходу задачи. Но если захват удается, ядро не может быть уверено в том, что захвачен корректный буфер, поскольку содержимое буфера могло быть ранее изменено другим процессом, обнаружившим буфер в списке свободных буферов и захватившим на время его семафор. Процесс A, ожидая освобождения семафора, не имеет ни малейшего представления о том, является ли интересующий его буфер тем буфером, который ему нужен, и поэтому прежде всего он должен убедиться в правильности содержимого буфера; если проверка дает отрицательный результат, алгоритм запускается сначала. Если содержимое буфера корректно, процесс A завершает выполнение алгоритма.

Оставшуюся часть алгоритма можно рассмотреть в качестве упражнения.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

3.1 ЗАГОЛОВКИ БУФЕРА

Из книги Архитектура операционной системы UNIX автора Бах Морис Дж

3.1 ЗАГОЛОВКИ БУФЕРА Во время инициализации системы ядро выделяет место под совокупность буферов, потребность в которых определяется в зависимости от размера памяти и производительности системы. Каждый буфер состоит из двух частей: области памяти, в которой хранится


3.3 МЕХАНИЗМ ПОИСКА БУФЕРА

Из книги Защита вашего компьютера автора Яремчук Сергей Акимович

3.3 МЕХАНИЗМ ПОИСКА БУФЕРА Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые ядром для подсистемы управления файлами, инициируют выполнение алгоритмов управления буферным кешем. При выборке блока алгоритмы верхнего уровня устанавливают логический


Переполнение буфера

Из книги Компьютер на 100. Начинаем с Windows Vista автора Зозуля Юрий

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


Использование буфера обмена

Из книги Советы по Delphi. Версия 1.0.6 автора Озеров Валентин

Использование буфера обмена Последовательность копирования ячеек с помощью буфера обмена следующая.1. Сделайте активной нужную ячейку или выделите их диапазон.2. Щелкните на кнопке Копировать, которая находится в группе Буфер обмена вкладки Главная. Выбранные ячейки


Просмотр буфера обмена

Из книги UNIX: взаимодействие процессов автора Стивенс Уильям Ричард

Просмотр буфера обмена Пример на основе простого модуля-класса, осуществляющего просмотр буфера обмена.unit ClipboardViewer;interfaceuses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs;type TForm1 = class(tform) procedure FormCreate(Sender: TObject); procedure FormDestroy(Sender: TObject);private FNextViewerHandle : THandle; procedure WMDrawClipboard(var message: TMessage);


Пример: вычисление размера буфера

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

Пример: вычисление размера буфера В предыдущем примере мы выделяли буфер размера BUFFSIZE (определенного в файле unpiрс.h в листинге В.1), и этого было достаточно. К сожалению, не существует простого способа вычислить объем памяти, нужный XDR для кодирования конкретных данных.


6.20.2 Использование буфера

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

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


8.2. Использование буфера обмена

Из книги Видеосамоучитель создания реферата, курсовой, диплома на компьютере автора Баловсяк Надежда Васильевна

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


3.6. Менеджеры буфера обмена

Из книги 19 смертных грехов, угрожающих безопасности программ автора Ховард Майкл

3.6. Менеджеры буфера обмена Во время работы с текстом вы наверняка что-то копируете в буфер обмена. Текстовый редактор Word умеет хранить несколько таких фрагментов. Однако такие данные находятся там недолго – стоит выключить компьютер или просто скопировать другой текст,


Глава 8 Переполнение буфера

Из книги Linux глазами хакера автора Флёнов Михаил Евгеньевич

Глава 8 Переполнение буфера В этой главе обсуждаются следующие темы: • Стек • Стековый фрейм функции • Основы переполнения буфера • Пример программы, уязвимой к переполнению буфера • Современные способы переполнения буфера • Новаторские принципы построения


Основы переполнения буфера

Из книги Программирование для Linux. Профессиональный подход автора Митчелл Марк

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


14.2. Переполнение буфера

Из книги UNIX: разработка сетевых приложений автора Стивенс Уильям Ричард

14.2. Переполнение буфера Это одна из самых популярных и в то же время наиболее сложная в использовании уязвимость. Для начала определимся, почему программисты допускают такие ошибки, при которых возможно выполнить переполнение буфера?В таких языках, как С++, для работы с


10.6.1. Переполнение буфера

Из книги автора

10.6.1. Переполнение буфера Почти псе основные Internet-демоны, включая демоны таких программ, как sendmail, finger, talk и др., подвержены атакам типа переполнение буфера. О них следует обязательно помнить при написании программ, которые должны выполняться с правами пользователя root, а