Lock-Writer Lock в Haskell

Question

Я реализую веб-приложение, которое хранит некоторые данные в памяти. Некоторые запросы читают эти данные для обработки, а некоторые запросы обновляют эти данные.

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

Стандартные библиотеки Haskell не обеспечивают такую ​​функциональность. Я обнаружил, что concurrency-extra дает эту функциональность, но библиотека, кажется, не поддерживается (и была удалена из stackage после LTS 3.22) - и ее свойства справедливости мне не понятны.

Я нахожу это немного удивительным, что в стандартных библиотеках haskell и в стеллаже нет библиотеки блокировки читателя-писателя - не является ли шаблон чтения-записи распространенным во многих программах? Или существует совершенно другой (возможно, незакрепленный) подход, который предпочтительнее в Haskell?

EDIT: Точнее на собственность справедливости, когда писатель блокируется в ожидании получения блокировки, последующие запросы чтения блокировка должна быть разрешена только после того, как писатель приобретает и освобождает от записи замок - подобный MVar с свойство справедливости - MVars have a FIFO property

Answer 1

Лучшее решение зависит от отношения читателей/писателей, но я думаю, что вы можете решить свою проблему только с помощью MVar.

Пусть

import System.Clock 
import Text.Printf 
import Control.Monad 
import Control.Concurrent 
import Control.Concurrent.MVar 

t__ :: Int -> String -> IO() 
t__ id msg = do 
    TimeSpec s n <- getTime Realtime 
    putStrLn $ printf "%3d.%-3d - %d %s" (s `mod` 1000) n id msg 

reader :: MVar [Int] -> Int -> IO() 
reader mv id = do 
    t__       id $ "reader waiting" 
    xs <- readMVar mv 
    t__       id $ "reader working begin" 
    threadDelay (1 * 10^6) 
    t__       id $ "reader working ends, " ++ show (length xs) ++ " items" 

writer :: MVar [Int] -> Int -> IO() 
writer mv id = do 
    t__       id $ "WRITER waiting" 
    xs <- takeMVar mv 
    t__       id $ "WRITER working begin" 
    threadDelay (3 * 10^6) 
    t__       id $ "WRITER working ends, " ++ show (1 + length xs) ++ " items" 
    putMVar mv (id: xs) 

main = do 

    mv <- newMVar [] 
    forM_ (take 10 $ zipWith (\f id -> forkIO (f mv id)) (cycle [reader, reader, reader, writer]) [1..]) $ \p -> do 
     threadDelay (10^5) 
     p 

    getLine 

с выходом

c:\tmp>mvar.exe +RTS -N20 
486.306991300 - 1 reader waiting 
486.306991300 - 1 reader working begin 
486.416036100 - 2 reader waiting 
486.416036100 - 2 reader working begin 
486.525191000 - 3 reader waiting 
486.525191000 - 3 reader working begin 
486.634286500 - 4 WRITER waiting 
486.634286500 - 4 WRITER working begin 
486.743378400 - 5 reader waiting 
486.852406800 - 6 reader waiting 
486.961564300 - 7 reader waiting 
487.070645900 - 8 WRITER waiting 
487.179673900 - 9 reader waiting 
487.288845100 - 10 reader waiting 
487.320003300 - 1 reader working ends, 0 items 
487.429028600 - 2 reader working ends, 0 items 
487.538202000 - 3 reader working ends, 0 items 
489.642147400 - 10 reader working begin 
489.642147400 - 4 WRITER working ends, 1 items 
489.642147400 - 5 reader working begin 
489.642147400 - 6 reader working begin 
489.642147400 - 7 reader working begin 
489.642147400 - 8 WRITER working begin 
489.642147400 - 9 reader working begin 
490.655157400 - 10 reader working ends, 1 items 
490.670730800 - 6 reader working ends, 1 items 
490.670730800 - 7 reader working ends, 1 items 
490.670730800 - 9 reader working ends, 1 items 
490.686247400 - 5 reader working ends, 1 items 
492.681178800 - 8 WRITER working ends, 2 items 

читателей 1, 2 и 3 выполняются одновременно, когда 4 WRITER working begin следующие запросы ждать его, но 1, 2 и 3 может прекратить.

(порядок вывода STDOUT и процесс входа в FIFO не является точным на этом примере, но количество элементов прочтенных или осевших показывают реальный порядок)

Answer 2

Блокировка считывателя-считывателя проста в применении поверх STM.

data LockState = Writing | Reading Int 
type Lock = TVar LockState 

startReading :: Lock -> STM() 
startReading lock = do 
    s <- readTVar lock 
    case s of 
     Writing -> retry 
     Reading n -> writeTVar (Reading (succ n)) 


stopReading :: Lock -> STM() 
stopReading lock = do 
    s <- readTVar lock 
    case s of 
     Writing -> error "stopReading: lock in writing state?!" 
     Reading n -> writeTVar (Reading (pred n)) 


startWriting :: Lock -> STM() 
startWriting lock = do 
    s <- readTVar lock 
    case s of 
     Reading 0 -> writeTVar Writing 
     _   -> retry 

stopWriting :: Lock -> STM() 
stopWriting lock = do 
    s <- readTVar lock 
    case s of 
     Writing -> writeTVar lock (Reading 0) 
     _  -> error "stopwriting: lock in non-writing state?!" 

Мои основные проблемы с выше, что 1) он выглядит немного избыточна для меня, и 2) мы еще никакого способа, чтобы гарантировать справедливость (живучести) в СТМ.

Думаю, можно было бы реализовать подобную библиотеку поверх MVar, хотя это было бы более сложным, особенно если мы хотим гарантировать справедливость.

У меня возникло бы желание избежать MVar s и вместо этого использовать семафоры, вместо этого вместо этого следует использовать QSem, которые гарантируют семантику FIFO. Используя их, можно реализовать читателей/писателей в стиле Дейкстра.

Answer 3

Действительно concurrent-extradoesn't provide fairness.

chi написал (а), что нет способа гарантировать справедливость в STM. Но мы можем сделать в IO, используя STM. Идея заключается в том, чтобы добавить другое состояние в Чи LockState, что указывает на то, что читатель не может получить блокировку:

data LockState = Writing | Reading Int | Waiting 

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

Here пример реализации: Не на Hackage, но вы можете его поставщику (это является BSD лицензией.)

Реализация оптимизирована для минимизации пробуждения окна. С одиночным TVar, когда блокировка находится в Waiting состоянии, каждый считыватель освобождает ненужные пробуждения всех читателей, ожидающих получения блокировки.Поэтому у меня есть два TVar s, один для состояния блокировки и другие для числа читателей.

ADDED: Here - интересное (и довольно длинное) обсуждение, которое у меня было с пользователем IRC. Cale о проблемах с блокировкой чтения-записи.