16 апреля 2009 г.

Задачи на собеседованиях: синхронизация

Предположим, что из доступных средств синхронизации у нас есть только бинарные семафоры (мьютексы). При этом семафоры поддерживают только операции lock() и unlock().

У нас есть разделяемый ресурс, который поддерживает операции чтения и записи. Существует N одновременно выполняющихся потоков, причем N — величина непостоянная. Одним потокам необходимо читать из разделяемого ресурса, другим необходимо записывать в этот ресурс.

Операция чтения может выполняться одновременно несколькими потоками, то есть когда один поток читает из ресурса, другие потоки тоже могут читать из этого ресурса, но писать в него не могут. Операция записи должна выполняться в эксклюзивном режиме, то есть во время записи никакие другие потоки не могут ни читать, ни писать.

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

После решения задачи, попытаться найти в решении недостатки и предложить более продвинутый вариант.

Подсказка:
Другими словами нужно самостоятельно реализовать аналог pthread_rwlock. Поэтому для начала нужно определить методы доступа к механизму синхронизации и отталкиваться уже от них. Например, пусть для потоков записи это будут функции writerLock() и writerUnlock(); для потоков чтения - readerLock() и readerUnlock(). Смысл этих функций аналогичен функциям lock() и unlock() для семафоров.

2 комментария:

  1. А подсказка тоже была в задании, или Вы сами до нее дошли?

    ОтветитьУдалить
  2. Честно говоря, я не очень понял вопрос :) Подсказка - имхо, это всегда часть задания. Просто некоторым она нужна, а некоторым - нет.

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

    Что касается лично меня, то в первый раз мне действительно понадобилась подсказка именно из-за того, что с rwlock'ами я до этого не сталкивался.

    ОтветитьУдалить