--------------54376DA95457B99D5F63C91A
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Linus Torvalds wrote:
>
> On Mon, 11 Jan 1999, MOLNAR Ingo wrote:
> >
> > ps. not that it counts too much, but my embarrasing email brought me to
> > really closely check all the semaphore code again, and it seems to be
> > all really cool and accurate. I've 'unfolded' the code into pseudocode
> > by hand:
>
> The not cool part about my implementation of recursive semaphores is:
>
> CPU #1 CPU#2
>
> down()
> ..
> up()
>
> "owner" is P#1, count=1
>
> down() down()
> lock ; decl succeeds
>
> lock ; decl fails
> goto slow part
> slow part sees stale owner
> returns success
>
> "owner" is P#2
>
> BOOM! - both CPU's are now inside the critical region.
>
> The problem is that "owner" can be stale, and can be updated outside the
> semaphore spinlock by a successful down() - which means that there are no
> synchronizing primitives there to guarantee that the slow part sees the
> new owner.
>
> Now, setting the new owner is done in the very next instruction after
> getting the semaphore, so CPU#1 has to be really fast, and CPU#2 has to be
> really slow for the above to happen. But it's still possible, and CPU#2
> taking an interrupt could cause that to happen.
>
> And I don't see any way of getting rid of it without another spinlock. I
> _could_ possibly do it with something like
>
> up(sem) {
> if (!sem.count)
> sem.owner = 0;
> old_up();
> }
>
> but I can't convince myself that that always works either.
>
> Linus
I have attached a figure (I prefer postscript over ascii figures; I
appologize if this means any inconveniences) describing a capability
based automatic serializing semaphore mechanism. It involves self
modifying code (even though I think it can be done without self
modifying code on some architectures), so you may not like it, and
because of various cache issues it may not even work on many
architectures at all. I did look up (hopefully all) the relevant
sections in the x86 architecture specifications though and I think it
should work there (I'm not an x86 expert though).
The cycle of operation is something along the following lines:
- semaphore starts in state 1: the contents of the semaphore is the
'atomic modify' instruction
- the first process(or) enters the semaphore, immediatelly modifies it
to a loop (state 2) and continues to execute the protected code
- the second (and other) process(or) enters the semaphore; because the
modification of the semaphore was atomic, it gets a 'jump' instead of
'atomic modify'; it starts spinning in a busy loop
- the first process(or) exits the protected code and modifies the
semaphore back to the original state (when the contents of the semaphore
was the 'atomic modify' instruction)
- the second (or some other) process(or) hits the 'atomic modify'
instruction and drops out of the loop, then immediatelly modifies the
semaphore back to loop so that others don't escape
- etc
I hope this mail is not a shot in the dark since I haven't been
following this thread all the way (so I don't know whether the 'owner'
stuff that you mentioned is relevant and necessary in the semaphore). If
it is, please ignore it.
Andrej
-- Andrej Presern, andrejp@luz.fe.uni-lj.si--------------54376DA95457B99D5F63C91A Content-Type: application/x-gzip; name="semaphore.eps.gz" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="semaphore.eps.gz"
H4sICJtxmzYAA3NlbWFwaG9yZS5lcHMAtVhtb9vIEf7OX7EFmiIBYof7StKf6nPkqw+xJdhK 0fbSD7REy7pKpEDScQ7G/fc+M0uKomQ5VpHeIfJ4d+aZ95mV3/xpdHN0Oi1usyN1HIrB6Oac iODNm/G8XmQnosqW6eq+KLPjbFXh+KzM0rooT8TdfKam2Vfx96ys5kUu9LESo7Se3C+yr9lC hEe3WZ3qVgIcH9MaeOOHTPyS5kIqIaOTMDxRkZBJkoDxnGDTfFpmv63+WhXT9HiSVvVxNT/O Ho6LcibenvKlGJVZlZX5+/fvbZQcuTB+/w7iw3Ke5TWrOhGjoqzLdF7j/KfiIZ/O89lPxbcT EeJ/pxOhncHVKJ1lFQ6JK5vN85usfljhl0E+bcnLdJbP7+aTBlceh/jPs5wVyyU0VsGHP5+r VfVxPqmFCkMxJWKa3QXd8S2hb/z+YVmX38Qyrcv5N7F6qIMPk2JxJMVTiIDXszL9/Q9xO8+n DEN3Ia5Itdj8rMrZ7Raf7PPJfXyq5ZMv4+k+3148I57ka+yzfb69eK7l+459UZ9vL168HT/r nuVLtvlc8nycdxISq+cZOSNWM4t8wUKpOkQybn+KdcdI1u1nNB0jWbef0W6r3hMd6bZV7wtP tK16X3g4MZ2/+23kzHT+7mVUnJnO3/2Mclv1Hq+V2la9x2ult1Xv8VpxZiyzyJdSqDgzjqtH 2ZcYOTMRs+j4Jcao60C7/nyOMe4YvQH0+Rxj0jF6A+jzuVkSdoxx3H4+xyg3GM0eZ4IsnwZV +jULjmQYY3fBbXxi6ufVAqsmkAIDtZqkiywA6ko8TRZFla3S+n5TXXYnnrLibr5YbJ7OSvE0 w5bBpst65xXOSenmYZWKp+2zEozPyC/E02KeZ3WxebgUT8vi69ZhidNy9zgXT3n2uO0ElFV1 Wfynb9Y9Tu+Lx97ZYoLDrCYjJumqf/Xb+uq3Yp737x7Xd4/z6ZZy5IVv8RPJK8qeG0UNPwqs 5b5tZAalpnc4ZZhpWvXw75ChO/x2V+R1j/2O2XeOJ3cN9s7NI4cJT4EdH2rke105vYsc9k8f VoL+TR7KEgu/9TMQwogjJcpiseB7KbJvk3tRPdwKTcXHF8uHhUin0/8fs28MiGymfrrX6g1k Auj91tNLt9vNyS8YfiqJp63XjfCXg7zOymx6QxkX1BUk+MeGNB5OjWyPtWkWga723PzEGsGS YhYEnd5A8hNpOYfsYo4fQY6A0HyINAb1svnFfy6E1MbYrd+YcSEwEiaL+Sqg8eKaTcE/q0nw Bg/Ixe9U7oG0fvosHgN0P4tQ+wXWYFtIGzrotIbeHpFxgLXaNOctHWvS7fk9PVkFrDr3khr/ WpCYDYUmfvRVApNoVgYwKC3L4vE+S6cs9QrdfN7Sbk2T34Cnmdq+NQWGIPQ0Kjed3/VYJ51W IzutfN7QRnUeN/SWx8p0Lhv1ape/p5yDmXQuN/RBLufCxG0ilviu0CWFabZ84Xka2qN3xj+D xj42aI2/no47tIZ+CW03HSjYdUSc6iLC5y2tu3Q09FY6TNylg+16XTq+p5zPwy4dDf2/V6Cx iUQdxxZaTWQt6t4lFD+Lp5d0sSE6Ip7YOY6rTYgn6rnc5Y5Qkpho6SUN0R4ldkQzehRZ0DJi GojK4BWFYWkiTcLGC+NdroxlJrJEgZVpK0EnbI4DhrJ485KwxeNHIUZsv4GwdYrpENqs9wVI QrmQgYxWoPEiJGFNZjvDAtpBwNmYaQ3NLmKLNAG5mHlUBM30bCVhRSY5b5JSxJSwn1SYKvIV KaPuHJOj4YewVKQhYQ0hWxGzeWFEoBH7HxricWxRiC8NsI4DBqvZbNKsE4ok6pFpTRpUyHRI QFwpOo7gs00UC8ccpCjmC0lBciwcxRRVEzHtKKhaMa2JR3rNkaQLzrN2ZIVhs7VzlGeuIu2A gRQyqFOUZ80+aycpn5I1u67xtSUg2MJ0BAHcehouaJ2wsHUQ1pL9seSzSpSnca64NkFDQBkP ZACqoJGFESuFavYX8EdynkFDWKqkoxuLiKZUeGEIhMZrI6CQUL0GmTSg0CwpFY1FMqGMBN5U fDfx2uCCjGPT+gaD1j7L2KxjIWPpfXbd1OTgyYjLkKOKfjRttLG3ojYLMtLebEqPjCSnh9Im fRlyPtHkus2z9BXG+ZfOerOpMKTTjEoFIx0ve64k6bw7VGHSJqatPEmtyOVJPlufEipVSRFp alhSjza1LX2Fcc1Lmj3UGNQM0rLZ3CTomnX34J9pu0r6KuRuk/Tli1tSbVxQShoB6luAhm0/ S54evs+hOfHDwNFFMwzYCj8MaGJI68cQTRL4bNsJI530/Ww5SJoFKA6IatjOKtlMD5phMvIW 0WyTUTOGaOghhxwYGoYyskk7JWUU6XZ6Iv+63XOve+K8atRbSzZq71TLf+CCEb8m4b8FDqf9 XeM0TQaXaN7bKCIMejLAGZ6M7LPTCLrShoLn0PCgk/6u6TY+b3+JEuBiBq2Itp62oOPmPCHa vxAknTvOE0zQ9OZhVVqTsHLeBAO6eVIgHiZ0Hgi1aUJtvTBaRCdsm6MFh0r3NPzSCU8FZ+gh FUcMhEoA7ZMMhx01mb9APLgRQVN9a78JnAUvOpo1W/77ashz11mraH6wNprXmosWNIpDG56E WF3g8avT0RhBVI0XRo9ijHomWK+189oQQ+1fMo5GjfZvFn+uorARhoDSXhsBKe5+rwHVtNYs fS7ZIhnGXphM5TnauBBq3fqmkkS3PqvEyjYWKgkTHzDcq9hZXy2oolito6qiyLbRVpF3gbKA NerzTOlZlxdtNhfqNp/YeLbNM7acbPOvmjHChYGHB+eTCgbbTLWVhG1m2grDC2b7Rbvdj+LX piv6ffmqtjBKtvu/439NX34Yz5dZdXRdLNNc4Iu/jD0zvtNXd4FJ0C9KI+xL6tXmDzzi7Xgo bsan44FQ7xqge/Lge2CIpYn2g8kDwCy9mhLq8h7W56vR9XA8OBsPPh4KJuWOZaPh9fhieHUo Ej/Df5hd1v0Au3ggctP2kYZXA3E6FqcHQ9ndNF5cDsTgH4OzA7Dc+m3Xx2qK60T88vlyJKhA Bp/OxZe3n4bD0Zd3Byjg1ed28E8/j4eXp+OLMwBfX5x+uvjXxdXPh8LGOyG4GVyejv42vB4c 1BUYDMbumHg5/Hhx/k/Yd3l8EBrtR/mD0Hx6dtGadj1B6QwvEcQO3bsvuvkg/iLOhlfji6vP hwTF75jd9v7y9nrwaXB6M9jQdT68FlTGPw+3KqP941dQVsF/AfL8SQZ2HQAA --------------54376DA95457B99D5F63C91A--
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/