Wikipédia

Író/olvasó lock tervezési minta

Az író-olvasó zár vagy megosztott-kizáró zár a számítástudományban egy szinkronizációs primitív, ami megoldja az egyik író-olvasó problémát. A zár megengedi több olvasó együttes hozzáférését, de az író kizárólagos hozzáférést igényel; így az adatot egyszerre többen is olvashatják, de csak egy írhatja. Ennek használatára példa egy adatszerkezet a memóriában, ami nem frissíthető atomi módon, és érvénytelen, amíg az írás nincs kész.

Általában feltételváltozókkal, mutexekkel vagy szemaforokkal szabályozza a hozzáférést.

Néhány zár lehetővé teszi a változtatást az író és az olvasó zár között.[1]

Prioritás szerkesztés

A zár tervezhető úgy, hogy különböző prioritást adjon az író és az olvasó szálaknak. Lehetnek priorizáltak az olvasók, vagy az írók, de lehet az is, hogy nincs prioritás.

Ha nincs prioritás, akkor nincs garancia az írók vagy az olvasók hozzáférésére. Bizonyos helyzetekben (ritka hozzáférés) előnyös lehet, mert hatékonyabb.

Az olvasók priorizálása maximalizálja a konkurenciát, de az írók kiéheztetéséhez vezethet. Ez ugyanis azt jelenti, hogy az olvasók folyamatosan zárolva tarthatják az objektumot, hiszen egyszerre többen tudnak olvasni. Így amikor egy olvasó végez, lehet még olvasó, aki zárolva tartja az objektumot. Ha A és B olvassa éppen az objektumot, és A végez, akkor jöhet egy C, ami szintén megszerzi az olvasó lockot. Ha B végez, jöhet egy D, és így tovább. Az eddig leírt mód szerint a prioritás gyenge, de lehet erős is, amikor írás után bármelyik blokkoló olvasó megszerezi a zárat a következőben.[1]:76

Az írók priorizálása azt jelenti, hogy ha egy író benyújtja igényét, akkor újabb olvasók nem szerezhetik meg a zárat, és ha minden olvasó befejezte az olvasást, akkor jön az író.[2] Ennek az az előnye, hogy az írók nem lesznek kiéheztetve, hátránya pedig, hogy kisebb konkurenciát enged meg. A zár megszerzése és elengedése is nehezebb, mert két mutexet kell használni. Ezt néha író-elfogult zárnak is nevezik.[3]

Megvalósítás szerkesztés

Az író-olvasó zárat többféleképpen is meg lehet valósítani, és visszavezetni más szinkronizációs primitívekre, amelyekről feltételezhető, hogy léteznek.

Két mutexszel szerkesztés

Raynal megmutatta, hogy hogy lehet két mutex és egy számláló felhasználásával elkészíteni az író-olvasó zárat. A számlálót b jelöli, ez számolja, hány olvasó van. Az egyik mutex r, ezt csak az olvasók használják, ez védi b-t, a másik g, ezt mindenki használja, és ez biztosítja az írók kizárólagos hozzáférését. Ez azt feltételezi, hogy ha egy szál megszerzett egy mutexet, akkor egy másik szál kioldhatja. A megvalósítás az írókat részesíti előnyben.[1]:76 Pszeudokód:

Begin Read

  • Lock r.
  • Increment b.
  • If b = 1, lock g.
  • Unlock r.

End Read

  • Lock r.
  • Decrement b.
  • If b = 0, unlock g.
  • Unlock r.

Begin Write

  • Lock g.

End Write

  • Unlock g.

Egy feltételes változóval és egy mutexszel szerkesztés

A minta megvalósítható egy feltételes változóval és egy mutexszel is, ami használ egy egész számlálót és egy bool flaget is. Az olvasó zárolás a következő:[4][5][6]

  • Input: mutex m, condition variable c, integer r (number of readers waiting), flag w (writer waiting).
  • Lock m (blocking).
  • While w:
  • Increment r.
  • Unlock m.

Hasonló az író zárolás is:

  • Input: mutex m, condition variable c, integer r (number of readers waiting), flag w (writer waiting).
  • Lock m (blocking).
  • While (w or r > 0):
    • wait c, m
  • Set w to true.
  • Unlock m.

Mindkettőnek megvan az inverz művelete is. Az olvasó zár elengedéséhez fogni kell az m mutexet, és csökkenteni kell r-t, és jelezni c-ben, ha r nullává vált. Ekkor a c-re várakozó szálak közül valamelyik megszerezheti a zárat. Az író zár elengedéséhez fogni kell az m mutexet, a w-t hamisra kell állítani, és jelezni c-ben.[4][5][6]

Alternatívák szerkesztés

Az olvasás-másolás-frissítés (RCU) algoritmus egy másik megoldás az író-olvasó problémára, ami nem várakoztatja meg az olvasókat.

A Linux rendszermag egy speciális megoldást, a szekvenciális zárat használja, ami kevés írót feltételez.

Programnyelvi támogatás szerkesztés

  • pthread_rwlock_t POSIX szabvány a hozzá tartozó műveletekkel[7]
  • a ReadWriteLock[8] interfész és ReentrantReadWriteLock[3] zár Java 5-től kezdve
  • Microsoft System.Threading.ReaderWriterLockSlim a .NET nyelvei számára[9]
  • std::shared_mutex a C++17-hez[10]
  • a Boost programkönyvtárban a boost::shared_mutex és boost::upgrade_mutex[11]
  • SRWLock a Windows API-jában a Vistától kezdve[12]
  • sync.RWMutex a Go programozási nyelvhez[13]
  • Phase fair zár, ami váltogat az írók és az olvasók között[14]
  • std::sync::RwLock zár a Rustban[15]
  • a POCO programkönyvtárban a Poco::RWLock
  • a txrwlock.ReadersWriterDeferredLock a Twistedben[16]

Megjegyzések szerkesztés

  1. ↑ This is the standard "wait" operation on condition variables, which, among other actions, releases the mutex m.

Jegyzetek szerkesztés

  1. ↑ a b Raynal, Michel. Concurrent Programming: Algorithms, Principles, and Foundations. Springer (2012) 
  2. ↑ Advanced Programming in the UNIX Environment. Addison-Wesley, 409. o. (2013) 
  3. ↑ a b java.util.concurrent.locks.ReentrantReadWriteLock Java readers–writer lock implementation offers a "fair" mode
  4. ↑ a b The Art of Multiprocessor Programming. Elsevier, 184–185. o. (2012) 
  5. ↑ a b PThreads Programming: A POSIX Standard for Better Multiprocessing. O'Reilly, 84–89. o. (1996) 
  6. ↑ a b Butenhof, David R.. Programming with POSIX Threads. Addison-Wesley, 253–266. o. (1997) 
  7. ↑ The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy. The IEEE and The Open Group. (Hozzáférés: 2011. május 14.)
  8. ↑ java.util.concurrent.locks.ReadWriteLock
  9. ↑ ReaderWriteLockSlim Class (System.Threading). Microsoft Corporation. (Hozzáférés: 2011. május 14.)
  10. ↑ New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm. Standard C++ Foundation
  11. ↑ Anthony Williams: Synchronization – Boost 1.52.0. (Hozzáférés: 2012. január 31.)
  12. ↑ Alessandrini, Victor. Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming. Morgan Kaufmann (2015) 
  13. ↑ The Go Programming language - Package sync. (Hozzáférés: 2015. május 30.)
  14. ↑ Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems
  15. ↑ std::sync::RwLock - Rust. (Hozzáférés: 2015. december 10.)
  16. ↑ Readers/Writer Lock for Twisted. (Hozzáférés: 2016. szeptember 28.)

Fordítás szerkesztés

Ez a szócikk részben vagy egészben a Readers–writer lock című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Író/olvasó_lock_tervezési_minta&oldid=26662317”