Проблемы

Задача сформулирована таким образом, чтобы иллюстрировать проблему избежания взаимной блокировки (англ. deadlock) — состояния системы, при котором прогресс невозможен.

Например, можно посоветовать каждому философу выполнять следующий алгоритм:

• Взять либо вилку, либо нож, либо взять оба прибора (если доступны)

• Есть

• Положить вилку

• Положить нож

• Размышлять

• Повторить алгоритм сначала

Это решение задачи некорректно: оно позволяет системе достичь состояния взаимной блокировки, когда один философ взял вилку и ждет ножа, а второй взял нож и ждет вилку.

Проблема ресурсного голодания (англ. resource starvation) может возникать независимо от взаимной блокировки, если один из философов не может завладеть ножом и вилкой из-за проблем синхронизации. Например, может быть предложено правило, согласно которому философы должны класть вилку обратно на стол после пятиминутного ожидания доступности ножа, и ждать ещё пять минут перед следующей попыткой завладеть вилками. Эта схема устраняет возможность блокировки (так как система всегда может перейти в другое состояние), но по-прежнему существует возможность «зацикливания» системы (англ. livelock), при котором состояние системы меняется, но она не совершает никакой полезной работы. Например, если все пять философов появятся в столовой одновременно.

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

Решение задачи. Иерархия ресурсов.

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

Пусть вилка имеет номер 1, а нож – 2, и каждая рабочая единица (философ) всегда берёт сначала вилку, а потом нож из доступных. Далее, философ кладёт сначала нож, потом — вилку.

Данное решение было предложено Дейкстрой.

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

3. ИспользованныеApi-функции

В работе использовались следующие API-функции:

1. CreateSemaphore – создание семафора

function CreateSemaphore (flpSemaphoreAttributes: PSecurityAttributes; llnitialCoimt,iMaximumCount: Longint; IpName: PChar): THandle; stdcall;

• flpSemaphoreAttributes – указатель на запись TSecurityAttributes, значение Nil соответствует согласию на использование стандартных атрибутов защиты.

• llnitialCount представляет собой начальное значение счетчика семафорного объекта. Это число может находиться в диапазоне от 0 до значения IMaximumCount. Семафор доступен, если значение этого параметра больше нуля. Когда поток вызывает функцию WaitForSingleObject() любую другую, ей подобную, значение счетчика семафора уменьшается на единицу. И наоборот, при вызове потоком функции ReleaseSemaphore() зна­чение счетчика семафора увеличивается на единицу.

• IMaximumCount задает максимальное значение счетчика сема­форного объекта. Если семафор используется для подсчета некоторых ресурсов, это число должно представлять общее количество доступных ресурсов.

• IpName содержит имя семафора.

2. ReleaseSemaphore - увеличения значения счетчика семафора

function ReleaseSemaphore(hSemaphore: THandle; IReleaseCount: Longint; IpPreviousCount: Pointer): BOOL; stdcall;

• IReleaseCount задаёт число, на которое будет уменьшено значение счетчика семафора. При этом старое значение счетчика будет сохранено в переменной типа Longint, на которую указывает параметр IpPreviousCount, если его значение не равно Nil,

3. CloseHandle – закрытие дескриптора

function CloseHandle(hObject: THandle): BOOL; stdcall;

function CloseHandle; external kernel32 name 'CloseHandle';

HObject – дескриптор объекта

4. WaitForSingleObject – приостановка выполнения потока до того момента, как заданный объект перейдет в состояние свободно.

function WaitForSingleObject(hHandle: THandle; dwMilliseconds: DWORD): DWORD; stdcall;

function WaitForSingleObject; external kernel32 name 'WaitForSingleObject';

• hHandle - дескриптор объекта, уведомление о свободном состоянии которого требуется получить

• dwMilliseconds - это время, которое вызывающий поток готов ждать. Если dwMilliseconds равно нулю, функ­ция немедленно вернет текущий статус заданного объекта. Таким образом, можно протестировать состояние объекта. Параметру можно также присваивать значе­ние символьной константы INFINITE (= -1), в этом случае вызывающий поток будет ждать неограниченное время.

Функция WaitForSingleObject переводит вызывающий поток в состояние ожидания до того момента, когда она передаст ему свое возвращаемое значение. Возвращаемые значения:

• wait_object_0 - объект находится в состоянии «свободно»;

• WAIT_TIMEOUT - интервал ожидания, заданный dwMilliseconds, истек,

а нужный объект по прежнему находится в состоянии «занято»;

• WAIT_ABANDONED относится только к мьютексу и означает, что объект не

был освобожден потоком, который владел им до своего завершения;

• WAIT_FAILED - при выполнении функции произошла ошибка

5. CreateThread – создание потока.

function CreateThread (psa: PSecurityAttributes; cbStackSize:DWORD, pfnStartAddr: PTHREAD_START_ROUTIME, pvParam: PVOID, dwCreateFlags: DWORD, pdwThreadID: PDWORD): THandle; stdcall;

• psa – Параметр psa является указателем на структуру SECURITY_ATTRIBUTES (аттрибуты защиты)

• cbStackSize - Этот параметр определяет, какую часть адресного пространства поток сможет использовать под свой стек.

• pfnStartAddr - определяет адрес функции потока, с которой должен будет начать работу создаваемый поток

• pvParam – указатель на параметр функции pfnStartAddr.

• dwCreateFlags - Этот параметр определяет дополнительные флаги, управляющие созданием потока. Он принимает одно из двух значений: 0 (исполнение потока начинается немедленно) или CREATE_SUSPENDED.

• pdwThreadID - это адрес переменной типа DWORD, в которой функция возвращает идентификатор, приписанный системой новому потоку.

При каждом вызове функции CreateThread система создает объект ядра «поток». Это не сам поток, а компактная структура данных, которая используется операционной системой для управления потоком и хранит статистическую информацию о потоке.

Система выделяет память под стек потока из адресного пространства процесса. Новый поток выполняется в контексте того же процесса, что и родительский поток. Поэтому он получает доступ ко всем описателям объектов ядра, всей памяти и стекам всех потоков в процессе. За счет этого потоки в рамках одного процесса могут легко взаимодействовать друг с другом.