1

Topic: Variation of primitives of synchronization

I offer for reviewing a primitive of synchronization Checkpoints: the project github the Description: README At once I will make a reservation that I do not position this primitive as the murderer  but only I offer for reviewing as a theoretical example of a possible variation. If , Checkpoint it is reduced to synchronization on the flags protected global . However it can be considered as a partition of a course of performance of the program on the independent segments which performance is synchronized in points - . In a file test/test2.cpp implementation of many writers / many readers on . I do not know, how programs synchronized before appearance . Probably, in those days were used similar on  methods.

2

Re: Variation of primitives of synchronization

Hello, lpd, you wrote: lpd> If , Checkpoint it is reduced to synchronization on the flags protected global . However it can be considered as a partition of a course of performance of the program on the independent segments which performance is synchronized in points - . And than it in essence differs from condition variables?

3

Re: Variation of primitives of synchronization

Hello, AndrewJD, you wrote: AJD> Hello, lpd, you wrote: lpd>> If , Checkpoint it is reduced to synchronization on the flags protected global . However it can be considered as a partition of a course of performance of the program on the independent segments which performance is synchronized in points - . AJD> And than it in essence differs from condition variables?  and rwlock stop performance of the program before performance there is nobody conditions. Condition variable, on the contrary, continue program performance at performance of some condition. To replace condition variable on  not always it is simple. On  it is possible to implement and that, and that logic (generally, any logic). For example, test2 - rwlock in which it is possible including readlock  to writelock (in semantics normal rwlock such variant misses) + count of simultaneous readers.

4

Re: Variation of primitives of synchronization

Hello, lpd, you wrote: lpd> In a file test/test2.cpp implementation of many writers / many readers on . Implementation rwlock from test2.cpp suggested an idea me about the correct behavior rwlock. Many  that in stl rwlock is impossible  from readlock in writelock. It is made because of simple possibility deadlock: 1 (readlock) 2 (readlock) 1 (writelock) 2 (writelock)-> deadlock However such restriction is inconvenient, if the writer only one, and it sometimes has enough readlock. In checkpoint test2.cpp logic at rwlock another: the writer at first captures readlock. Then if sees that other writers too captured readlock and too wait for an upgrade to writelock, it removes readlock, and there and then again tries to occupy readlock (with the old purpose  to capture writelock). For a case when readlock it is impossible to remove, it is possible to make a special flag at rwlock.writelock (). Thus writers share on "greedy" (which do not remove readlock) and "polite" (which remove readlock). Such logic removes a problem deadlock and works and at one writer, and at one ' greedy ' and many ' polite ' writers. It would be quite good, if std:rwlock and worked.

5

Re: Variation of primitives of synchronization

Hello, lpd, you wrote: lpd> Mjuteksy and rwlock stop performance of the program before performance there is nobody conditions. lpd> Condition variable, on the contrary, continue program performance at performance of some condition. To replace condition variable on  not always it is simple. Mutex it is not necessary as the general-purpose primitive of synchronization because release it that flow which captured it can only. As the general-purpose primitive of synchronization the semaphore suits.

6

Re: Variation of primitives of synchronization

Hello, Pzz, you wrote: Pzz> Mutex it is not necessary as the general-purpose primitive of synchronization because release it that flow which captured it can only. Pzz> as the general-purpose primitive of synchronization the semaphore suits. A semaphore an interesting primitive of synchronization, however it does not replace rwlock. Besides,  it is possible to occupy with some one operation (and it is in stl), and with a semaphore such variant not to implement. The general-purpose primitive of synchronization - .

7

Re: Variation of primitives of synchronization

Hello, lpd, you wrote: lpd> the Semaphore an interesting primitive of synchronization, however it does not replace rwlock. Besides,  it is possible to occupy with some one operation (and it is in stl), and with a semaphore such variant not to implement. It is possible to make of a semaphore rwlock. That to possibility to capture at one stroke, it is some semaphores 1) from the theoretical point of view anything useful does not add 2) from the practical point of view it is not too necessary 3) from the organizational point of view is an implementation singularity. For example, in Sys V IPC such what for is. lpd> the general-purpose primitive of synchronization - . To me is a little lazy to study the description  (it is a pity that it such long), but at first sight  reminds conditional variable. Conditional variable, certainly, general-purpose primitive of synchronization. Though in my opinion, a little elaborate.

8

Re: Variation of primitives of synchronization

9

Re: Variation of primitives of synchronization

Hello, Pzz, you wrote: Pzz> Hello, lpd, you wrote: lpd>> the Semaphore an interesting primitive of synchronization, however it does not replace rwlock. Besides,  it is possible to occupy with some one operation (and it is in stl), and with a semaphore such variant not to implement. Pzz> that to possibility to capture some semaphores at one stroke, is 1) from the theoretical point of view anything useful does not add 2) from the practical point of view it is not too necessary 3) from the organizational point of view is an implementation singularity. For example, in Sys V IPC such what for is. I will add that atomic capture of several  is irreplaceable from the theoretical point of view since it cannot be implemented other means without additional variables.

10

Re: Variation of primitives of synchronization

Hello, lpd, you wrote: lpd> I Will add that atomic capture of several  is irreplaceable from the theoretical point of view since it cannot be implemented other means without additional variables. "Is irreplaceable" is when generally it is impossible to implement. If it is possible to implement with usage of additional variables, it it is not irreplaceable. Manufacture of primitives of synchronization is rather nontrivial process. Before it to undertake, it is necessary to familiarize with a question a little.

11

Re: Variation of primitives of synchronization

Hello, Pzz, you wrote: Pzz> Hello, lpd, you wrote: lpd>> I Will add that atomic capture of several  is irreplaceable from the theoretical point of view since it cannot be implemented other means without additional variables. Pzz> "is irreplaceable" is when generally it is impossible to implement. If it is possible to implement with usage of additional variables, it it is not irreplaceable. Well so it is clear that all can be made on one futex system call and atomic variable, and to replace with it and semaphores. Pzz> manufacture of primitives of synchronization is rather nontrivial process. Before it to undertake, it is necessary to familiarize with a question a little. Contrary to the habits, I familiarized somewhat

12

Re: Variation of primitives of synchronization

13

Re: Variation of primitives of synchronization

14

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Certainly, on  and  it is possible to arrange a spaghetti-code. But good (beautiful, clear, supported) decisions is all the same will be monitors of a different level . lpd>> For example, test2 - rwlock in which it is possible including readlock  to writelock (in semantics normal rwlock such variant misses) + count of simultaneous readers. I will add about the documentation  the chart for rwlock from test2.cpp which drew in the simple editor. I did not result it at once, as I think that it is possible to draw the chart with more evident structure for this purpose, but it can somehow my idea illustrates: the circuit

15

Re: Variation of primitives of synchronization

16

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Hello, lpd, you wrote: It, by the way, one of claims to . Instead of the arbitrary predicate and the arbitrary function - two std:: function <int ()>. get it can be blocked, and can continue performance - in the latter case it will be fulfilled set. To manage one function easily it is impossible (if I correctly understood about what you speak). The first. It is not necessary to use separately a scattering , separately a scattering . It is necessary to use monitors. And the monitor infrastructure is pair from one  and one . In yours  is. One  and one bicycle . Not clearly only, what for it was necessary to write a bicycle? Strategy of dispatching regular  (,  and ) does not arrange? For example, to implement the same polite rwlock or more difficult logic,  to fence the code round classical primitives of synchronization. Or that condition variable  one flow on several notify from different flows at once. The second. Certainly, there is a temptation - to use internal   as user. But there there live dragons. Here to you three pieces: 1) And from what you took, what function get can be fulfilled on arbitrary, and not just native, a flow? The most banal reason why cannot: for example, uses TLS-variables. get and set - should be the simple numerical functions working with variables accessible to them or arrays. I did not register it in the documentation.> 2) Each output from pass is accompanied by running on all predicates of waiting flows. That is, we out of the blue snip off brakes. Yes, is global . However get and set the fastest - much faster the same passage in a kernel mode.> 3) pass clears up no more than one flow for time. (Further each following clears up following for it). If in queue there were 10 flows, last from them wakes up, at the best, through 10 quanta of time. Besides, get and set very fast functions, therefore I do not think that in overwhelming number of cases high-speed performance makes a problem. Here it naive implementations also differ from the advanced.>> I simply did not want to be dug in in waiting strategy. They can be as much as elaborate.>> For example, the writer can allow to overtake to readers it during some time then forbids overtakings: all previous readers should leave, then there should transit the writer, then all new readers. It relieves the writer of starvation. And becomes -  easily to add.>> If some writers wait, they should be built in queue. With priorities or without? The polite writers who have captured readlock, simply release readlock if there are other writers, and at once try  it. The greedy writer does not release read-lock. Thus there can be one greedy writer, many polite writers, and it is a lot of readers.>> If some writers and readers whom leaking (or the first waiting) the writer did not pass forward wait, - as they should be built in queue? In my implementation writers have absolutely  a priority - readers release at once queue at the sight of writers. In my opinion, and should be, since  it is normal less, and they lock logic of the program is more often. In general, the code from condition_variable and mutex too absolutely small. And on a bulkiness level - here it is possible to argue that it is better: to address to  from the outside, or to transfer inside its healthy lambdas. class RWLock {> checkpoint cp;..... public: void reader_lock () {if (cp.pass ([] (this) {...}, [] (this) {.......})) {.......};} void reader_unlock () {if (cp.pass ([] (this) {...}, [] (this) {.......})) {.......};} .....};> Yes, but programming each time of queues of waiting in which each time  flows, in components to logic, extends and complicates the code. Here in the last project the logic polite rwlock of which at me then was not was necessary for me. It was necessary to fence instead sending of messages between flows that complicated the code without what it would be quite good to manage. About convenience of usage, probably I will really add in  methods of standard primitives using it since  for the simple parallel access to one object - it is convenient.

17

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Hello, lpd, you wrote: lpd>> Implementation rwlock from test2.cpp suggested an idea me about the correct behavior rwlock. lpd>> Many  that in stl rwlock is impossible  from readlock in writelock. lpd>> It is made because of simple possibility deadlock: 1 (readlock) 2 (readlock) 1 (writelock) 2 (writelock)-> deadlock lpd>> However such restriction is inconvenient, if the writer only one, and it sometimes has enough readlock. lpd>> In checkpoint test2.cpp logic at rwlock another: the writer at first captures readlock. Then if sees that other writers too captured readlock and too wait for an upgrade to writelock, it removes readlock, and there and then again tries to occupy readlock (with the old purpose  to capture writelock). For a case when readlock it is impossible to remove, it is possible to make a special flag at rwlock.writelock (). Thus writers share on "greedy" (which do not remove readlock) and "polite" (which remove readlock). lpd>> Such logic removes a problem deadlock and works and at one writer, and at one ' greedy ' and many ' polite ' writers. lpd>> it would be quite good, if std:rwlock and worked. The reader: - beforehand: does the request in readers - a condition: there is no writer, there are no earlier requests from (the greedy?) Writers - result: there is the reader a Polite writer: - beforehand: does the request in polite writers - a condition: there are no readers, there is no writer, there are no earlier requests from writers, there are no earlier requests from readers - result: there is the writer a Greedy writer: - beforehand: does the request in greedy writers - a condition: there are no readers, there is no writer, there are no earlier requests from greedy writers - result: there is the writer Here it is logic. And juggling with flags and recaptures is too the low level tangling. It is similar, truth like as we considered that the writer at first can capture readlock, and then  it to writelock. If to speak about : that juggling by flags it is difficult, I agree. Basically you speak simply about other system of flags: for example to the counter of readers to add logic variable. However value of logic variable is equivalent  the counter. For simplification I will add functions equivalent  and rwlock. My calculation that at the documentation it will be possible to operate ' with states ' flows - names checkpoint and to draw the circuit. How to draw on the circuit  and the conditional variables I do not represent. Generally,  I did not anchor to implementation rwlock on , and suggested to consider logic rwlock. In my opinion, polite writers are necessary quite often, however neither std:: rwlock, nor boost:: upgradable_lockable such possibility do not give. Thus to add polite_wlock and greedy_wlock to rwlock it is very easy, and it would be easier and more powerful boost:: upgradable_lockable.

18

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Hello, lpd, you wrote:>> It, by the way, one of claims to . Instead of the arbitrary predicate and the arbitrary function - two std:: function <int ()>. lpd>> get it can be blocked, and can continue performance - in the latter case it will be fulfilled set. To manage one function easily it is impossible (if I correctly understood about what you speak). Not about two functions, and about the strange choice of signatures at these functions. get is bool (). int here the superfluous. set is void (). Or if it would be desirable to return something not through the bound variables, T (), where T - any copyable/moveable type. And at you both of them are nailed in function <int ()>. Out of the blue you overpay, and it is expensive enough. About get you are right. Set I would not began to complicate too. It is desirable to return, since it happens  with wake. In my opinion, it is simple int enough to return. lpd>> For example to implement the same polite rwlock or more difficult logic,  to fence the code round classical primitives of synchronization. Or that condition variable  one flow on several notify from different flows at once. You struggle against spurious wakeup, or what? Because if to reconcile to it, notify_all - quite to itself the decision. We assume that it is necessary to wake one flow in on simultaneous performance of two conditions, which  other two flows. Two serial conditional variables it is impossible to manage, since it is not known, in what order and in what time intervals will be caused notify (). And by the way, there is no need to work with a dynamic storage. List elements can be allocated on stacks of calling threads: all the same there it is guaranteed that lifetime of each element - from an input to an output in unique general critical section pass. With it it agree. Though generally, I the supporter of the least possible  which complicate the code. While it is the small project, I would prefer simplicity of the code to high-speed performance. If it is in , it will be necessary to optimize. Same concerns and storage of lambdas. Quite they can be remembered under the link. And still, to get rid of a tail recursion. lpd>> besides, get and set very fast functions, therefore I do not think that in overwhelming number of cases high-speed performance makes a problem. And here put any more in speed get/set. Namely that for one flow once clears up. Imagine: the multinuclear machine. Some flows at which get became true, and set are trivial. It was quite possible to wake them at one stroke. But is not present. I thought of it: to learn that set are trivial uneasy; and if set are nontrivial, everyone set () can affect on subsequent get (), therefore it is impossible to awake at one stroke. Besides, here this statement that it is necessary to give a priority to writers, - it is doubtful. Imagine the device by which permanently something measures. If to give a priority to readers, - they will lock a label at copying, and at worst, on the screen there will be out-of-date data. If to give a priority to the writer, - it  and freezes a user interface flow. Loading equalization is necessary, or very short operation came running-read/wrote down-escaped. But in this case it is not necessary rwlock, normal  suffices. I recognize that readers normally more, and they do not update a program state. At the same time the flow of readings can block update, and the logic of the program stops. Though probably yes, equalization - the best variant. With  it is just easy to implement it.

19

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Hello, lpd, you wrote: I Will add about an upgrade the Polite writer from the reader (1): - beforehand: does the request in polite writers - a condition: there are no other readers, there is no writer, there are no earlier requests from writers, there are no earlier requests from readers - result: ceases to be the reader and there is the writer a Polite writer from the reader (2): - beforehand: does the request in polite writers and simultaneously ceases to be the writer - a condition: there are no readers, there is no writer, there are no earlier requests from writers, there are no earlier requests from readers - result: there is the writer>> a Greedy writer:>> - beforehand: does the request in greedy writers>> - a condition: there are no readers, there is no writer, there are no earlier requests from greedy writers>> - result: the writer it becomes similar, two variants. It so, only counters of writers and readers all the same are necessary. Though the approach to documenting the interesting. They differ with that other readers can or cannot climb through forward. And a question in what behavior is more desired.>> Here it is logic. And juggling with flags and recaptures is too the low level tangling. lpd>> it is similar, truth like as we considered that the writer at first can capture readlock, and then  it to writelock. lpd>> If to speak about : lpd>> that juggling by flags it is difficult, I agree. Basically you speak simply about other system of flags: for example to the counter of readers to add logic variable. However value of logic variable is equivalent  the counter. I do not speak about system of flags. It is More than that: I suspect that correct operation with the requests arranged on time, demands lists. At least, on lists it is possible to construct naive, but certainly correct implementation of these checks. And on flags there will be something unobvious. Arrays are quite admissible in get (). And lists too. lpd>> In my opinion, polite writers are necessary quite often, however neither std:: rwlock, nor boost:: upgradable_lockable such possibility do not give. Thus to add polite_wlock and greedy_wlock to rwlock it is very easy, and it would be easier and more powerful boost:: upgradable_lockable. I do not know, it is how much rare they are necessary. On data domain, likely, depends. And what for data domain in which some readers and some writers compete, moreover and with different priorities, and such, what they cannot be expressed by means of priority numbers? To me such rwlock it was necessary in the server processing connections from many clients which could change the data each other or  other session under the same security account. A widespread situation. Priorities certainly it is possible to solve, but they are not present in stl and boost. I here that else thought. It is all - artfully camouflaged cooperative multitasking at which the manager code is fulfilled not in a separate flow (and, especially, in a kernel), and as God willing.... I not absolutely understood your terminology, but is valid approximately so all and is fulfilled, under one .

20

Re: Variation of primitives of synchronization

Hello, Kodt, you wrote: Hello, lpd, you wrote: it is natural that at first we pronounce words, without going into details. And then already we reflect, as though easier to implement all. Therefore I also did not hurry up to concretize. Suddenly it is necessary to go a difficult way, to run under lists, and I already in the technical project about counters nailed up. It agree that flags it is not especially convenient to synchronize in simple cases. I will try to make of the project also something like a basis for implementation of any primitives of synchronization, in components to direct usage. Not absolutely my main objective, but too it is quite good. And if the platformo-dependent code to add, expose through thread:: native_handle and corresponding  (, ) priorities? I think, there could turn out lock writelock in one hundred read-lockov if to remove readlock before writelock manually and to deliver a priority write-lockam through adjustments rwlock.>> I here that else thought. >> It is all - artfully camouflaged cooperative multitasking at which the manager code is fulfilled not in a separate flow (and, especially, in a kernel), and as God willing. lpd>> I not absolutely understood your terminology, but is valid approximately so all and is fulfilled, under one . The first optimization: the flow not always falls asleep, and the first check does itself (instead of the manager answering a question:" The following suitable flow is I "). Can even  twist. And only after that leaves in waiting. So lungs , in particular (CRITICAL_SECTION and futex) are arranged. That so can make to make sense I agree, but not on optimization at me focus at the given stage. In , probably, it also is useful, if reaches usage in any projects. Here you went further, - dragged all code of the manager in a client flow. By the way, in it there is a certain vulnerability: if the client is forced out, also dispatching happens much later. Normally after all the manager works with very high priority. Of it did not think. To such problem are subject also normal stl primitives, as far as I understand.