Reply to thread

Message: [QUOTE="Arthur J. O'Dwyer, post: 1692258"] Typed "Lamport bakery algorithm," naturally, and then clicked the button labeled "I'm Feeling Lucky." It takes you right to [URL]http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Bakery.html[/URL] Well, you obviously don't need access to UNIX "pids" to do the algorithm, but you *do* need a reliable source of unique integer identifiers for each thread. And that's something that standard C simply cannot give you without specific language support. I agree with Paul that this is a very basic and very obvious fact that shouldn't be too hard to grasp. If you've done any thread-based programming (nothing complicated, just anything that requires a shared resource), you've noticed that every time two threads want access to the same bit of memory at the same time, you need some kind of mutex to block out one of the threads while the other one does its thing, and then block out the other one while the first one does *its* thing. Mutexes cannot be expressed in standard C, because standard C has no way of specifying "this block of data behaves like a mutex." I'm sorry if that sounds circular, but it's hard for me to describe the effect of a mutex except by jargon. Suffice it to say that you can feel free to post snippets illustrating anything you think qualifies as a mutex algorithm written in standard C, and I will be only too glad to poke holes in it. Maybe it's the changing times. Or maybe it's the way that web page explains it -- it's intuitively obvious to me from their description that if Thread A has a lower number than Thread B, then Thread A naturally goes first. It just makes sense. Well, Paul's right and you're wrong. That's all. [re: the rest of the miscellaneous arguments in this subthread] [re stack bounds checking] This proposal sounds both reasonable and possible to me. I do agree that it requires a *lot* more thought, though; and you'll see if you search Google Groups that this topic has been discussed both here and in comp.programming (IIRC) quite a lot before. Of course it's *possible* to create an arbitrary-operator-parsing grammar! But it would require work, and it's not going to make it into C, so IMHO that discussion should move to comp.programming or comp.lang.misc, where someone will no doubt be glad to demonstrate how their magic compiler compiler will handle arbitrary operator syntaxes with ease. Why do you say that? It's not dishonest to use the well-thought-out and publicly-reviewed specification of an x86 operation in this context. I myself am not familiar enough with the MUL opcodes anymore to give a nice description, so here's my proposal, without any x86 jargon, which I think *would* rhyme fairly well with C. It's a library function. #include <math.h> unsigned long lmulu(unsigned long p, unsigned long q, unsigned long *hi, unsigned long *lo); The 'lmulu' function accepts arguments 'p' and 'q', multiplies them using normal integer arithmetic, and stores the high-order bytes of the result in '*hi' and the low-order bytes in '*lo'. Specifically, if ULONG_MAX = 2**N - 1, then mathematically (*hi << N) + *lo == (p * q); but note that this expression invokes undefined behavior as a C expression. 'lmulu' may be implemented as a macro. 'lmulu' returns the value stored in '*hi'. signed long lmuls(signed long p, signed long q, signed long *hi, signed long *lo); The 'lmuls' function accepts arguments 'p' and 'q', multiplies them using normal integer arithmetic, and stores the high-order bytes of the result in '*hi' and the low-order bytes in '*lo'. [Needs someone more familiar with bitwise representations, and more awake, to define exact semantics in mathematical terms.] 'lmuls' may be implemented as a macro. 'lmuls' returns the value stored in '*hi'. It would have been nice to add defined behavior for when 'hi' or 'lo' were NULL, but that would have killed the whole point of making the function in the first place -- the ability to optimize away a lot of code on many popular systems. [And before Paul contradicts that last sentence, I re-iterate: This is *not* about adding functionality to C; it's about giving the compiler better optimization hints. The ability to do wide multiplies already exists in C; language support for them will only make them faster.] That said, I think this thread needs to start splitting up. :) -Arthur [/QUOTE]

Verification