![]() ![]() Since we have seen above that accessMutex is always collectively taken by readers before they access the resource, the resource is properly protected.įair access is guaranteed through the orderMutex which is taken upon arrival and released only when access to the resource has been granted.Writer’s block-wanting to write and not writing-is a persistent problem that every writer (yes, every writer, even Stephen King) deals with. The resource is never accessed by a writer without accessMutex being taken in an unconditional and exclusive way. Thus those two semaphores cannot interact and cause a deadlock. However, the first situation (line 13) only happens when readers is equal to 0 (first reader to get access to the resource), which can never be the case if another reader is currently trying to execute line 20 as seen above, so those two potentially deadlocking reservations can never occur at the same time. As seen above, it means that no reader will be executing lines 14 to 22 (inclusive) without accessMutex being taken by a reader (possibly gone now), especially line 18 which represents resource access.ĪccessMutex can be requested when readersMutex is held (on line 13), and readersMutex can be requested when accessMutex is held (on line 20). Detection of those raising or falling edges is guaranteed by the use of the readersMutex lock. ![]() It is released at line 23 just after readers goes back to 0. Readers is always strictly greater than 0 if any reader is currently executing lines 15 to 20 (inclusive): the variable is unconditionally incremented at line 14 and unconditionally decremented at line 21 without any other modification, and no modification ever occurs without an exclusive lock granted by readersMutex so the readers integrity is guaranteed.ĪccessMutex is taken at line 13 just before readers goes from 0 to 1. OrderMutex cannot be part of a deadlock since at the time it is requested no other semaphore is ever held by the calling process, so we can forget about it in our deadlock analysis (this property holds if every process only calls reader() or writer() once, but it works in the general case). It can be formally proved correct using for example Petri nets. We can look back the this solution and check if it looks like it fits our requirements. Semaphore accessMutex // Initialized to 1 semaphore orderMutex // Initialized to 1 void reader () Checking the solution for the required properties This semaphore will be taken by any entity that requests access to the resource, and released as soon as this entity gains access to the resource: ![]() To achieve that, we will use a semaphore named orderMutex that will materialize the order of arrival. Those semaphores, being used as locks, are all initialized in the released state (1 available place) those initializations will not appear in code snippets below but will be shown in comments.įirst of all, we said earlier that we want fair-queuing between readers and writers in order to prevent starvation. We will use semaphores for mutual exclusion (mutex). However, this algorithm is very simple once you decompose the problem in smaller steps and properties. As of today, even the wikipedia page on the subject does not have any algorithm for what is called “the third readers-writers problem”. Unfortunately, only the solutions for the first two problems are easily found on the Internet. New readers arriving in the meantime will have to wait. If a writer arrives while readers are accessing the resource, it will wait until those readers free the resource, and then modify it. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |