Алгоритм 2


Скачать 449.39 Kb.
НазваниеАлгоритм 2
страница1/5
Дата публикации06.05.2013
Размер449.39 Kb.
ТипДокументы
userdocs.ru > Информатика > Документы
  1   2   3   4   5
Блокировки

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

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

Требования, накладываемые на алгоритмы взаимного исключения.

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

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

- Не должны возникать взаимные блокировки и голодания.

- Когда в критическом разделе нет ни одного процесса, любой процесс, запросивший доступ к нему, должен немедленно его получить.

- Алгоритмы должны работать для любого количества процессов и их относительной скорости работы.

- Любой процесс должен оставаться в критическом разделе только в течение ограниченного времени.

Пример: два процесса как потоки, т.е. могут польз. глоб. переменной.

Алгоритм 1.

nTurn – очередь какого раздела наступила

Код процесса 0

while (nTurn != 0)

/* пережидание */;

// критический раздел

nTurn = 1;

// . . .

Код процесса 1

while (nTurn != 1)

/* пережидание */;

// критический раздел

nTurn = 0;

// . . .

Проблемы

- строгое чередование;

- блокировка при сбое другого процесса.

Алгоритм 2


Глоб. перем. – массив из 2х флагов.

^ Глобальные переменные

bool abFlags[2] = { false, false };

Код процесса 0

while (abFlags[1]) // (1)

/* пережидание */ ;

abFlags[0] = true; // (2)

// критический раздел

abFlags[0] = false;

Код процесса 1

while (abFlags[0]) // (1)

/* пережидание */ ;

abFlags[1] = true; // (2)

// критический раздел

abFlags[1] = false;

Проблемы:


В такой ситуации оба войдут в критический раздел

Алгоритм 3


Сначала отмечаем, что хотим войти, потом ожидаем.

Код процесса 0


abFlags[0] = true; // (1)

while (abFlags[1]) // (2)

/* пережидание */ ;

// критический раздел (3)

abFlags[0] = false;

Код процесса 1

abFlags[1] = true; // (1)

//

while (abFlags[0]) // (2)

/* пережидание */ ;

// критический раздел (3)

abFlags[1] = false;

Проблемы:

- могут быть обы навечно заблокированы (взаимная блокировка, true одновременно)




Алгоритм 4


Код процесса 0

abFlags[0] = true; // (1)

while (abFlags[1]) // (2)

{

abFlags[0] = false; // (3)

// задержка

abFlags[0] = true; // (4)

}

// критический раздел

abFlags[0] = false;

Код процесса 1

abFlags[1] = true; // (1)

while (abFlags[0]) // (2)

{

abFlags[1] = false; // (3)

// задержка

abFlags[1] = true; // (4)

}

// критический раздел

abFlags[1] = false;

Проблемы:

Уступают друг другу > Бесконечно уступают друг другу (ленивая блокировка)


  1   2   3   4   5

Похожие:

Алгоритм 2 iconАлгоритм
Ш 55 Разгром Японии и самурайская угроза. — М.: Изд-во Алгоритм; Изд-во Эксмо, 2005. — 512 с, ил
Алгоритм 2 iconРазрешение записи
Для уменьшения объема хранимой видеоинформации в видеорегистраторах применяются различные алгоритмы ее компрессии. В сетевых видеорегистраторах...
Алгоритм 2 iconАннотация Слово «алгоритм»
Слово «алгоритм» не случайно введено в название книги: мне представляется, что есть возможность «разложить по полочкам» самые сложные...
Алгоритм 2 iconСтатья «Алгоритм решения изобретательских задач» в Википедии Это...
Алгоритм решения изобретательских задач[1][2][3][4][5][6][7][8][9][10] раздел теории решения изобретательских задач (триз), разработаной...
Алгоритм 2 iconПрограмма упорядоченное множество ко­манд, реализу­ющих алгоритм решения задачи
Алгоритм упорядоченное множе­ство фор­ма­ль­ных предписаний, выпол­нение которых приводит к решению задачи. Команда элементарная...
Алгоритм 2 iconАлгоритм работы системы

Алгоритм 2 icon6. задача о рюкзаке
Циклический алгоритм целочисленного программирования
Алгоритм 2 iconУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12
Алгоритм 2 iconЗаконодательное обоснование
Алгоритм действий граждан в случае обнаружения несанкционированных раскопок – с. 6
Алгоритм 2 iconПризрак толпы / Карл Ясперс, Жан Бодрийар. М.: Алгоритм, 2007. 272 с. Философский
Призрак толпы / Карл Ясперс, Жан Бодрийар. — М.: Алгоритм, 2007. — 272 с. — Философский
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница