Re:Basics of Futexes
by Animats on Saturday July 14, 2018 @02:57AM
(#17529181)
Here's the original implementation of that idea, from the early 1970s.[1] UNIVAC EXEC 8 had this. See section 4.3.4, page 148, "Test and Set Queuing".
This OS had threads, decades before UNIX got them. They were called "activities". These were also multiprocessor systems. So it had to have user code synchronization. The UNIVAC mainframes had a "test and set" instruction. This was an atomic operation which set a flag. If the flag was already set, an interrupt occurred, so the OS could reschedule.
This could be used in a spin mode, where hitting a locked lock just rescheduled the activity for later. Or the user could give their threads IDs and manage them with system calls, like UNIX pthreads. The third option, test and set queuing, was added later. There was a list of activities in user space associated with each lock, and when a activity was blocked, it went on the user space queue for that lock. The "clear test and set" operation was an assembly language macro, which took the first waiting activity off the list and told the OS to unblock it.
The normal case of taking the lock without delay did not involve the OS at all. Even pthreads works that way in some implementations, as it should.
This OS had threads, decades before UNIX got them. They were called "activities". These were also multiprocessor systems. So it had to have user code synchronization. The UNIVAC mainframes had a "test and set" instruction. This was an atomic operation which set a flag. If the flag was already set, an interrupt occurred, so the OS could reschedule.
This could be used in a spin mode, where hitting a locked lock just rescheduled the activity for later. Or the user could give their threads IDs and manage them with system calls, like UNIX pthreads. The third option, test and set queuing, was added later. There was a list of activities in user space associated with each lock, and when a activity was blocked, it went on the user space queue for that lock. The "clear test and set" operation was an assembly language macro, which took the first waiting activity off the list and told the OS to unblock it.
The normal case of taking the lock without delay did not involve the OS at all. Even pthreads works that way in some implementations, as it should.
[1] http://bitsavers.trailing-edge.com/pdf/univac/1100/exec/UP-4...