Semaphore Reader Writer #1 demo
https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem
Starting off
We have a semaphore that holds 1 process. We the reference to this object semaphoreResource
The whole point of this semaphore is for Readers and Writers to fight over it. If a Reader is holding it, a Writer cannot write.
If a Writer is holding it, Readers cannot read.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class ViewController: UIViewController { var button : UIButton? = nil let dispatchQueue = DispatchQueue(label: "com.prit.TestGCD.DispatchQueue", attributes: .concurrent) //https://developer.apple.com/documentation/dispatch/dispatchsemaphore/1452955-init // value is thestarting value for the semaphore. If its 1, means it can ONLY let 1 in at the same time. // 2 means, 2 can use this semphore at the same time. // Reader and Writers fight the resource semaphore let semaphoreResource = DispatchSemaphore(value: 1) // Readers fight for the reader mutex in order to update readCount. // readCount then decides whether the reader should lock the resource semaphore or not. let semaphoreReaderMutex = DispatchSemaphore(value:1) var readCount = 0 |
Writers fight with Readers for semaphoreResource but will never ever touch semaphoreReaderMutex.
That’s because semaphoreReaderMutex is used between Readers in order to update/change a variable called readCount.
readCount determines whether the first reader will hold the semaphoreResource and also whether the last reader will let go of semaphoreResource.
That’s the whole purpose of semaphoreReaderMutex.
We define two callbacks to simulate reading and writing. Reading takes 3 seconds and writing takes 5 seconds.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
var runReadCodeBlock: ((String)->())? var runWriteCodeBlock: ((String)->())? .... .... 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!") } |
Writer
In the case of Writers, its very straightforward. It grabs the resource semaphoreResource. If its succeeds, it will then do the writing by simply calling the runWriteCodeBlock callback. After the writing, it will let go of the semaphore:
|
1 2 3 4 5 6 |
public func writer(_ name : String) { if grabResource(semaphore: semaphoreResource, processName: name) { runWriteCodeBlock?(name) letGoResource(semaphore: semaphoreResource, name: name) } } |
Readers
The idea is that we grab the reader semaphore (semaphoreReaderMutex) in order to make changes to the resource semaphore (semaphoreResource).
The reader semaphore allows the 1st reader to lock the resource semaphore, and naturally, the last reader to unlock the semaphore.
Any readers after the 1st one, does not need to lock the resource semaphore anymore. They just go on ahead and do their reading.
However, they DO NEED to grab the reader mutex because they are changing the readCount variable. This is to update the number of readers.
Only when the last reader finishes reading (updates the readCount to 0) then it unlocks the resource semaphore so that the writers can write.
|
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 |
public func reader( name : String) { // grab reader mutex so that we can increment the readCount var if grabResource(semaphore: semaphoreReaderMutex, processName: name) { readCount += 1 if readCount == 1 { // if we're the first reader, we must lock the resource mutex from Writers. // the reason why we don't lock from Readers is that this function ensures Readers can go through _ = grabResource(semaphore: semaphoreResource, processName: name) } // we're not the first reader, the resource mutex was already grabbed. So 2nd...n readers simply just read } letGoResource(semaphore: semaphoreReaderMutex, name: name) runReadCodeBlock?(name) // grab reader mutex, because we're gunna decrease the readCount if grabResource(semaphore: semaphoreReaderMutex, processName: name) { readCount -= 1 if readCount == 0 { // we're the last reader, we must release the resource semaphore letGoResource(semaphore: semaphoreResource, name: name) } } letGoResource(semaphore: semaphoreReaderMutex, name: name) } |
However, it may be that other readers will read also. In this solution, every writer must claim the resource individually. This means that a stream of readers can subsequently lock all potential writers out and starve them. As long as future readers keep coming in, the next waiting writer will NEVER be able to write.
This is so, because after the first reader locks the resource, no writer can lock it, before it gets released. All future writers MUST WAIT FOR ALL READERS TO FINISH (readCount back to 0) in order to grab hold of the resource semaphore in order to do its writing.
In other words, a few readers come along, increases the readCount. Then leaves. Then more readers come. And more, and further even into the future such that readCount is always > 0. Hence this is what will starve the writer.
Therefore, this solution does not satisfy fairness.
full source
|
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 |
class ViewController: UIViewController { var button : UIButton? = nil let dispatchQueue = DispatchQueue(label: "com.prit.TestGCD.DispatchQueue", attributes: .concurrent) //https://developer.apple.com/documentation/dispatch/dispatchsemaphore/1452955-init // value is thestarting value for the semaphore. If its 1, means it can ONLY let 1 in at the same time. // 2 means, 2 can use this semphore at the same time. // Reader and Writers fight the resource semaphore let semaphoreResource = DispatchSemaphore(value: 1) // Readers fight for the reader mutex in order to update readCount. // readCount then decides whether the reader should lock the resource semaphore or not. let semaphoreReaderMutex = DispatchSemaphore(value:1) var readCount = 0 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: "readerA") self.reader(name: "readerB") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.reader(name: "readerC") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.writer("writerA") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.reader(name: "readerD") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.reader(name: "readerE") } (DispatchQueue.global(qos: .userInitiated)).async(group: dispatchGroup, qos: .userInitiated, flags: .assignCurrentContext) { () -> Void in self.reader(name: "readerF") self.reader(name: "readerG") } } private func grabResource(semaphore : DispatchSemaphore, processName : String) -> Bool { if semaphore.wait(timeout: .distantFuture) == .success { print("\(processName) grabs the \(semaphore.description) semaphore") return true } else { print("\(processName) waiting for \(semaphore.description) timed out") return false } } private func letGoResource(semaphore : DispatchSemaphore, name : String) { print("\(name) lets go of the \(semaphore.description)") semaphore.signal() } public func writer(_ name : String) { if grabResource(semaphore: semaphoreResource, processName: name) { runWriteCodeBlock?(name) letGoResource(semaphore: semaphoreResource, name: name) } } // the idea is that we grab the reader semaphore in order to make changes to the resource semaphore // the reader semaphore allows the 1st reader to lock the resource semaphore, and naturally, the last reader to unlock the semaphore // Any readers after the 1st one, does not need to lock the resource semaphore anymore. They just go on ahead and read from the resource. // However, they DO NEED to grab the reader mutex because they are changing the readCount variable. This is to update the number of readers. // Only when the last reader finsihes reading, updates the readCount to 0, then it unlocks the resource semaphore so that // the writers can write. public func reader( name : String) { // grab reader mutex so that we can increment the readCount var if grabResource(semaphore: semaphoreReaderMutex, processName: name) { readCount += 1 if readCount == 1 { // if we're the first reader, we must lock the resource mutex from Writers. // the reason why we don't lock from Readers is that this function ensures Readers can go through _ = grabResource(semaphore: semaphoreResource, processName: name) } // we're not the first reader, the resource mutex was already grabbed. So 2nd...n readers simply just read } letGoResource(semaphore: semaphoreReaderMutex, name: name) runReadCodeBlock?(name) // grab reader mutex, because we're gunna decrease the readCount if grabResource(semaphore: semaphoreReaderMutex, processName: name) { readCount -= 1 if readCount == 0 { // we're the last reader, we must release the resource semaphore letGoResource(semaphore: semaphoreResource, name: name) } } letGoResource(semaphore: semaphoreReaderMutex, name: name) } override func didReceiveMemoryWarning() { super.didReceiveMemoryWarning() // Dispose of any resources that can be recreated. } } |