1.2 Синхронизация потоков, классические задачи

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

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

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

Проблема читателей и писателей моделирует доступ к базе данных. Например, БД бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Вопрос: как запрограммировать читателей и писателей?

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

Постановка задачи «обедающие философы». Задача заключается в следующем: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти скользкие, и поэтому каждому философу нужно две вилки. Между каждыми двумя тарелками лежит одна вилка.

Жизнь философа состоит из периодов поглощения пищи и размышлений. Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления.

«Проблема обедающих философов» — классический пример, используемый в информатике для иллюстрации проблем синхронизации в дизайне параллельных алгоритмов и техник решения этих проблем.

2. Постановка задачи.

Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти с курицей. На столе лежат n вилок и k ножей.

Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит вилку и нож.

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

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