pthread_mutex_lock(&mutex); int Lv = vl[philnum];
//определение номера левой вилки по номеру философа int Rv = vp[philnum];
//определение номера правой вилки по номеру философа vil[Lv] = 0;//освобождение вилок
vil[Rv] = 0;
int Lp = fl[philnum];
//определение номера левого соседа по номеру философа int Rp = fp[philnum];
//определение номера правого соседа по номеру философа Lv = vl[Lp]; //определение номеров других вилок
Rv = vp[Rp];
//если другая вилка свободна, левый философ может есть if (vil[Lv] == 0) {
pthread_cond_signal(&philCV[Lp]);
}
//если другая вилка свободна, правый философ может есть if (vil[Rv] == 0) {
pthread_cond_signal(&philCV[Rp]);
}
pthread_mutex_unlock(&mutex);
}
Обратим внимание на следующий фрагмент кода функции Захват_вилок(int philnum):
if ((vil[Lv] == 1)||(vil[Rv] == 1)) { pthread_cond_wait(&philCV[philnum],&mutex);
}
Когда поток будет активизирован, он перейдет к выполнению действий, описанных сразу же за условным переходом, т. е. к захвату вилок. Такой вариант работает корректно, если гарантировано, что будет выполняться именно этот поток, т. е. реализация условной переменной соответствует «семантике Хоара».
В условиях вытесняющей многозадачности нет возможности управлять активизацией конкретных процессов. В этом случае активизация
36
представляет собой перевод процесса из очереди ждущих процессов в очередь процессов, готовых к выполнению.
Выбор процесса для реального выполнения осуществляет ядро ОС.
При такой ситуации нет гарантии, что именно этот процесс единственным подойдет к участку кода с захватом вилок, поскольку пока данный процесс будет перемещаться по очереди готовых процессов, какойнибудь другой процесс может захватить вилку. Другими словами, реализуется семантика Mesa, и перед захватом вилок необходима повторная проверка условия того, что они свободны:
while ((vil[Lv] == 1)||(vil[Rv] == 1)) { pthread_cond_wait(&philCV[philnum],&mutex);
}
Если повторная проверка покажет, что вилки заняты, процесс вернется в состояние ожидания.
Назначение однородных ресурсов
Имеется N задач и M единиц однородных ресурсов. Любая задача может запросить k единиц ресурсов в диапазоне от 1 до M. Если требуемое количество ресурсов имеется в наличии, то они предоставляются задаче и общее число свободных ресурсов уменьшается на k единиц. Если требуемого количества ресурсов нет в наличии, задача блокируется и ждет их освобождения.
Понятие «задача блокируется и ждет их освобождения» означает, что задача ставится в очередь вместе с такими же задачами, которым не хватает ресурсов, при этом количество запрашиваемых ресурсов запоминается. Когда задача завершает работу с ресурсами, она освобождает их и общее число свободных ресурсов увеличивается. Возврат ресурсов в пул свободных ресурсов сопровождается просмотром очереди ждущих задач и активизацией тех из них, которым хватит вновь образовавшихся свободных ресурсов.
В зависимости от реализации правил назначения и освобождения ресурсов может возникнуть бесконечное ожидание, проявляющееся в том, что задача, ждущая некоторого, достаточно большого количества ресурсов, никак не может их получить, поскольку освобождаемое количество ресурсов мало и тут же захватывается задачами, которым такого количества достаточно.
37
Требуется построить программную модель, реализующую рассматриваемую схему из N процессов и M ресурсов, в которой бесконечное ожидание было бы невозможно.
Модель поведения каждой задачи может быть представлена следующим образом:
while (true) {
Работа без ресурсов(); Запрос_ресурсов(nr); Работа с ресурсами(); Освобождение_ресурсов(nr);
}
Возможность избежать бесконечного ожидания будет зависеть от работы функций Запрос_ресурсов(int nr) и Освобождение_ресурсов(int nr).
Рассмотрим запрос ресурсов на простом примере. Предположим, что общее количество ресурсов равно 10, в текущий момент есть 3 единицы свободных ресурсов, и в очереди находится поток, ждущий 6 единиц ресурсов. Может сложиться ситуация, при которой задачи запрашивают по одной единице ресурсов, работают с ними и возвращают в пул. Задача, ждущая 6 единиц ресурса, никогда не будет активизирована.
Чтобы устранить указанное явление, необходимо при запросе ресурсов проверять не только наличие свободных ресурсов, но и наличие задач в очереди, ждущих ресурсы, а также блокировать запрашивающую задачу, если очередь не пуста, даже если свободных ресурсов было достаточно. Это первый шаг к устранению бесконечного ожидания в части запроса ресурсов.
Второй шаг к устранению бесконечного ожидания выполняется в части освобождения ресурсов. Предположим, что первым в очереди ждущих задач находится задача, запрашивающая 6 единиц ресурса, а следующие задачи запрашивают по 1 единице ресурса, и освобождается 3 единицы ресурса. Если задачи, ждущие по 1 единице ресурса, активизировать в обход первой, то первая задача попадет в бесконечное ожидание при повторении данной ситуации.
Устранить бесконечное ожидание в этом случае поможет выполнение следующего условия – всегда выполнять активизацию только с первой задачи. Не активизировать задачи, которые стоят в очереди за первой, даже если общего количества свободных ресурсов достаточно для этого. Предполагается, что при последующих возвратах ресурсов требуемое для
38
активизации первой задачи количество накопится и задача будет активизирована.
Другими словами, в очереди необходимо запоминать не только идентификаторы задач, но и потребности в ресурсах для каждой задачи, и активизировать задачи в строгом соответствии с дисциплиной FIFO.
Далее, определим данные, которые должны быть доступны всем задачам.
Общее количество ресурсов и общее количество задач, пользующихся ресурсами, объявим как int const Nres и int const Nproc соответственно, а текущее количество свободных ресурсов объявим как переменную
int nfree = Nres.
Определим очередь задач, ожидающих ресурсы, как вектор vector <TProc> ProcList, элементами которого будут структуры вида typedef struct _TProc
{
int resnum; //количество запрашиваемых ресурсов int procnum;//номер задачи (0 – Nproc-1)
} TProc;
Очевидно, что функции задач Запрос_ресурсов(int nr) и Освобождение_ресурсов(int nr) должны работать в режиме взаимного исключения, для чего введем мьютекс: pthread_mutex_t mutex.
Для обеспечения ожидания потока при отсутствии нужного количества ресурсов введем условные переменные: pthread_cond_t resCV[Nproc].
Поскольку в очереди будут храниться структуры данных, содержащие номер задачи и количество запрашиваемых ресурсов, модифицируем интерфейсы функций запроса и освобождения ресурсов, включив в них параметр np – номер потока:
Запрос_ресурсов(int nr, int np); Освобождение_ресурсов(int nr, int np).
С учетом приведенных выше рассуждений текст функции Запрос_ресурсов(int nr, int np) каждого потока можно представить следующим образом:
void Запрос_ресурсов(int nr,int np)
{
pthread_mutex_lock(&mutex);
if ((nr > nfree)||(!ProcList.empty())) {
39
//если свободных ресурсов меньше, чем запрашивается, или //есть очередь задач, ждущих ресурсы
do {
//формируем элемент очереди
TProc proc; proc.resnum = nr; proc.procnum = np;
//и помещаем его в очередь
ProcList.push_back(proc);
//блокируем на условной переменной pthread_cond_wait(&resCV[np],&mutex);
//после активизации делаем повторную проверку
} while (nr > nfree);
}
nfree = nfree - nr; pthread_mutex_unlock(&mutex);
}
Текст функции Освобождение_ресурсов(int nr,int np) можно представить следующим образом:
void Освобождение_ресурсов(int nr, int np)
{
pthread_mutex_lock(&mutex); nfree = nfree + nr;
int tmpnfree = nfree; //просматриваем очередь
while (!ProcList.empty()) { //берем первый элемент
TProc proc = ProcList.front();
//если для первой задачи достаточно ресурсов if (proc.resnum <= tmpnfree) {
//то исключаем его из очереди
ProcList.erase(ProcList.begin());
//и активизируем ожидающую задачу pthread_cond_signal(&resCV[proc.procnum]);
40