https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem
Readers won’t starve Writers anymore
Due to readTry, if additional future reads come in, these future reads wait FCFS with future writes via readTry. Thus, this line gives
fair chance for future writes to grab readTry and do its writing.
Another very important thing is that once a future write grabs readyTry, no future reads will be able to grab readTry. This causes existing reads to eventually finish reading, decreasing readCount back to 0. Once this future write finishes, then the next waiting Read can start again.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public func reader(name : String) { // reader and writer will try to hold readTry. If not, they wait FIFO. if grabResource(semaphore: readTry, processName: name, semaphoreName: "readTry") { if grabResource(semaphore: readerMutex, processName: name, semaphoreName: "readerMutex") { readCount += 1 if readCount == 1 { _ = grabResource(semaphore: resource, processName: name, semaphoreName: "resource") } letGoResource(semaphore: readerMutex, name: name, semaphoreName: "readerMutex") } letGoResource(semaphore: readTry, name: name, semaphoreName: "readTry") } |
Writers may starve Readers
The very first writer has a hold on readyTry so that no other “additional” readers can come in.
When we’re done writing, we decrement. IF WE’RE THE LAST WRITER, make sure to let go of readyTry, so other readers can come in.
However, this starves readers because reader’s first execution is to try to grab readTry. Since its already been held by the first
writer, the reader will fail.
Furthermore, future writers come in and do not need to grab readTry again. It was already held by the first
writer and thus, future writers will simply wait for the resource to do its writing, then decrement writeCount.
ONLY the last writer can let go of readTry. And this is where it starves readers.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public func writer(_ name : String) { if grabResource(semaphore: writerMutex, processName: name, semaphoreName: "writerMutex") { writeCount += 1 if (writeCount == 1) { // if you're the first writer, must lock the other Readers out via ReadTry. _ = grabResource(semaphore: readTry, processName: name, semaphoreName: "readTry") } letGoResource(semaphore: writerMutex, name: name, semaphoreName: "writerMutex") } ... ... } |
Let’s see what happens when a reader X and writer C get executed.
output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
reader X grabs the readTry <-- reader X has readTry writerC grabs the writerMutex // writerC then tries to grab readTry, but reader X has it, so it waits reader X grabs the readerMutex reader X grabs the resource <-- X has resource reader X lets go of the readerMutex reader X lets go of the readTry <-- reader X releases readTry reader X reading stuff.. writerC grabs the readTry // writerC can now grab readTry since reader X just released it writerC lets go of the writerMutex // writerC then tries to grab resource, but reader X has it, so it waits reader X done... reader X grabs the readerMutex reader X lets go of the resource <-- reader X releases resource reader X lets go of the readerMutex writerC grabs the resource // writerC can now grab resource since reader just released resource writerC writing stuff....please wait writerC all done! writerC lets go of the resource writerC grabs the writerMutex writerC lets go of the readTry writerC lets go of the writerMutex |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
import UIKit class ViewController: UIViewController { var button : UIButton? = nil let dispatchQueue = DispatchQueue(label: "com.prit.TestGCD.DispatchQueue", attributes: .concurrent) let resource = DispatchSemaphore(value: 1) let readerMutex = DispatchSemaphore(value:1) var readCount = 0 let writerMutex = DispatchSemaphore(value:1) var writeCount = 0 let readTry = DispatchSemaphore(value: 1) var runReadCodeBlock: ((String)->())? var runWriteCodeBlock: ((String)->())? override func viewDidLoad() { runReadCodeBlock = { processName in print("\(processName) reading stuff..") Thread.sleep(forTimeInterval: 3) print("\(processName) done...") } runWriteCodeBlock = { processName in print("\(processName) writing stuff....please wait") Thread.sleep(forTimeInterval: 5) print("\(processName) all done!") } } override func viewDidAppear(_ animated: Bool) { super.viewDidAppear(animated) let dispatchGroup = DispatchGroup() (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.reader(name: "reader X") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.writer("writerC") } } private func grabResource(semaphore : DispatchSemaphore, processName : String, semaphoreName : String) -> Bool { if semaphore.wait(timeout: .distantFuture) == .success { print("\(processName) grabs the \(semaphoreName)") return true } else { print("\(processName) waiting for \(semaphoreName) timed out") return false } } private func letGoResource(semaphore : DispatchSemaphore, name : String, semaphoreName : String) { print("\(name) lets go of the \(semaphoreName)") semaphore.signal() } // due to both writers and readers trying to grab the readyTry semaphore, writers will have a fair chance of getting the semaphore, instead of // bothersome future readers that just keeps coming in. Writers will finally come in, wait and grab for the readTry. Once it succeeds, it will // naturally grab the resource semaphore, does its writing, and let's go after its done. // Then it will grab writerMutex in order to decrement writeCount. Once there's no more writers, we let go of readTry. // say a writer has readTry. It does its write, and more writers come in. public func writer(_ name : String) { if grabResource(semaphore: writerMutex, processName: name, semaphoreName: "writerMutex") { writeCount += 1 if (writeCount == 1) { // if you're the first writer, must lock the other Readers out via ReadTry. _ = grabResource(semaphore: readTry, processName: name, semaphoreName: "readTry") } letGoResource(semaphore: writerMutex, name: name, semaphoreName: "writerMutex") } // reserve the resource for yourself to write if grabResource(semaphore: resource, processName: name, semaphoreName: "resource") { runWriteCodeBlock?(name) letGoResource(semaphore: resource, name: name, semaphoreName: "resource") } // The very first writer has a hold on readyTry so that no other "additional" readers can come in. // when we're done writing, we decrement. IF WE'RE THE LAST WRITER, make sure to let go of readyTry, so other readers can come in. // however, this starves readers because reader's first execution is to try to grab readTry. Since its already been held by the first // writer, the reader will fail. However, future writers come in and do not need to grab readTry again. It was already held by the first // writer and thus, future writers will simply wait for the resource to do its writing, then decrement writeCount. // ONLY the last writer can let go of readTry. And this is where it starves readers. if grabResource(semaphore: writerMutex, processName: name, semaphoreName: "writerMutex") { writeCount -= 1 if writeCount == 0 { letGoResource(semaphore: readTry, name: name, semaphoreName: "readTry") } letGoResource(semaphore: writerMutex, name: name, semaphoreName: "writerMutex") } } public func reader(name : String) { // reader and writer will fight for readTry if grabResource(semaphore: readTry, processName: name, semaphoreName: "readTry") { if grabResource(semaphore: readerMutex, processName: name, semaphoreName: "readerMutex") { readCount += 1 if readCount == 1 { // if we're the first reader, we must lock the resource mutex so we can read. This is also for additional Readers to read from the resource. That way, while all readers are reading, no writers can write. // Due to readTry, if annoying future reads come in, these future reads MUST FIGHT with future write via readTry. Thus, this gives // fair chance for future writes to grab readTry and do its writing. Once a future write grabs readyTry, No future reads will // be able to grab readTry, and thus, each existing read will eventually finish reading, decreasing readCount back to 0. // This releases the resource for the next waiting Writer to use. _ = grabResource(semaphore: resource, processName: name, semaphoreName: "resource") } letGoResource(semaphore: readerMutex, name: name, semaphoreName: "readerMutex") } letGoResource(semaphore: readTry, name: name, semaphoreName: "readTry") } // So the writer will wait for the reader to release the readtry and then the writer will immediately lock it for itself and all subsequent writers. // However, the writer will not be able to access the resource until the current reader has released the resource, which only occurs after the reader is finished with the resource in the critical section. This is shown below when the readCount == 0, and the last reader let's go // of resource. runReadCodeBlock?(name) // reading is performed // grab reader mutex, because we're gunna decrease the readCount if grabResource(semaphore: readerMutex, processName: name, semaphoreName: "readerMutex") { readCount -= 1 if readCount == 0 { // we're the last reader, we must release the resource semaphore letGoResource(semaphore: resource, name: name, semaphoreName: "resource") } } letGoResource(semaphore: readerMutex, name: name, semaphoreName: "readerMutex") } override func didReceiveMemoryWarning() { super.didReceiveMemoryWarning() // Dispose of any resources that can be recreated. } } |