How to program critical section for reader-writer systems?
in [Theory]
|
Prev: Fastest DFA recognizer
Next: A A
From: Srinu on 20 May 2010 02:50 Hi, Lets say, I have a reader-writer system where reader and writer are concurrently running. 'a' and 'b' are two shared variables, which are related to each other, so modification to them needs to be an atomic operation. A reader-writer system can be of the following types: 1. rr 2. ww 3. r-w 4. r-ww 5. rr-w 6. rr-ww where [ r : single reader rr: multiple reader w : single writer ww: multiple writer ] Now, We can have a read method for a reader and a write method for a writer as follows. I have written them system type wise. 1. rr read_method { read a; read b; } 2. ww write_method { lock(m); write a; write b; unlock(m); } 3. r-w 4. r-ww 5. rr-w 6. rr-ww read_method { lock(m); read a; read b; unlock(m); } write_method { lock(m); write a; write b; unlock(m); } For multiple reader system, shared variable access doesn't need to be atomic. For multiple writer system, shared variable access need to be atomic, so locked with 'm'. But, for system types 3 to 6, is my read_method and write_method correct? How can I improve? Sincerely, Srinivas Nayak
From: Ben Bacarisse on 20 May 2010 07:57 Srinu <sinu.nayak2001(a)gmail.com> writes: > Lets say, I have a reader-writer system where reader and writer are > concurrently running. 'a' and 'b' are two shared variables, which are > related to each other, so modification to them needs to be an atomic > operation. > > A reader-writer system can be of the following types: > > 1. rr > 2. ww > 3. r-w > 4. r-ww > 5. rr-w > 6. rr-ww > > where > [ r : single reader > rr: multiple reader > w : single writer > ww: multiple writer ] > > Now, We can have a read method for a reader and a write method for a > writer as follows. I have written them system type wise. > > 1. rr > read_method > { read a; read b; } > > > 2. ww > write_method > { lock(m); write a; write b; unlock(m); } > > > 3. r-w > 4. r-ww > 5. rr-w > 6. rr-ww > read_method > { lock(m); read a; read b; unlock(m); } > > write_method > { lock(m); write a; write b; unlock(m); } > > > For multiple reader system, shared variable access doesn't need to be > atomic. Nor do the variables need to be "shared" in any normal sense of the word. This is such a special case that I am not sure there is value in considering it separately. > For multiple writer system, shared variable access need to be atomic, > so locked with 'm'. > > But, for system types 3 to 6, is my read_method and write_method > correct? How can I improve? This is a classic concurrency problem. Pretty much any text on concurrent programming will discuss it and many solutions can be found on the web. The key idea is to permit multiple readers while excluding writers when there is a reader active. Of course, if your problem really involves only two variables there may be no value in permitting multiple readers since the critical section is so very small. Is this coursework? -- Ben.
From: Srinu on 20 May 2010 09:29 > Is this coursework? No, this is not a coursework. Though it seems like homework, it is an attempt to collect all the different algorithms (actually the essence of them, ex. "The key idea is ...") for all possible combinations of reader-writer system. You are correct in saying that "Pretty much any text on concurrent programming will discuss it and many solutions can be found on the web". But many books just discuss only one or two of these types, not all combination. As I have written earlier, it is again an attempt to collect all sort of better algorithms for different types of reader-writer system at a single place through discussion. Sincerely, Srinivas Nayak
From: Ben Bacarisse on 20 May 2010 11:23 Srinu <sinu.nayak2001(a)gmail.com> writes: >> Is this coursework? > > No, this is not a coursework. Though it seems like homework, it is an > attempt to collect all the different algorithms (actually the essence > of them, ex. "The key idea is ...") for all possible combinations of > reader-writer system. Asking "is it correct?" and "can it be improved?" about one combination and one algorithm is not going to get people to tell you all the different algorithms for all the possibilities. > You are correct in saying that "Pretty much any > text on concurrent programming will discuss it and many solutions can > be found > on the web". But many books just discuss only one or two of these > types, not all combination. As I have written earlier, it is again an > attempt to collect all sort of better algorithms for different types > of reader-writer system at a single place through discussion. I missed that and I can't see it in the message I replied to. In general, messages should stand alone: I won't necessarily have read (let alone remembered) all of your posts. It would help if you give some constraints. Do you only want algorithms using locks? What about (counting) semaphores? Condition variables? Monitors? Rendezvous? If all of these, then you are asking a lot and I am not sure this is best group. In fact, there are probably better groups anyway, but I don't know them. Sorry. -- Ben.
From: Srinu on 21 May 2010 02:40
Dear Ben, You seems to be correct. I very much appreciate your polite reply. I am sorry incase I have unknowingly hurt you in any manner. Truly speaking, this question was bit general. The algorithm I have written witeen for the last four type of systems seems to be correct in very strict sence. But are not efficient/suitable in general for all these types. So, if we consider each of them again, we may have some ideas of improvement on top of the basic algorithm. I was looking for those improvement ideas, for example, giving writer a high priority, allowing mutiple reads simultaneously etc. If possible also small psudo codes as given by me with simple locking mechanism, that will be very simple and basic yet elegant. Not about highlevel primitives, (counting) semaphores, condition variables, monitors, rendezvous etc. I was thinking, if question is just "How to program critical section for reader-writer systems?" the question will be too general to answer and a book is needed to write on it. If I ask too specific question, with hardware constraint, OS constraint, language constraint, library constraint, it is again another extereme end. So both the cases, nobody is going to look at it. So I thought, I'll put it in a moderately general, but seems still this didn't help. Any way, I'll try to ask it separately in separate questions. But I always welcome your kind help, in case I have made my expectation clear. Thanks and regards, Sincerely, Srinivas Nayak |