Reverse restartable sequences for lock polling scalability
An example system includes a memory, at least one processor in communication with the memory, a plurality of threads executing on the at least one processor, and a supervisor. The supervisor is configured to preempt a first thread of the plurality of threads and determine a status of the first thread as either (i) executing in an atomic section or (ii) executing outside of the atomic section. The atomic section is a region of code tagged as atomic, and the atomic section includes instructions that run under a lock. Responsive to determining the status as executing in the atomic section, the supervisor is configured to notify a second thread of the plurality of threads to execute a system call based lock to block execution until the lock is released by the first thread.
1 . A method comprising:
preempting, by a supervisor, a first thread while the first thread is executing in an atomic section to schedule a higher priority task, wherein the supervisor is a privileged software component of an operating system associated with the first thread, and wherein the supervisor handles interrupts;
determining, by the supervisor, a status of the first thread as executing in the atomic section when preempted, wherein the atomic section is a region of code tagged as atomic and involves modifying a protected resource;
responsive to determining the status as executing in the atomic section, notifying, by the supervisor, a second thread to enter a sleep state after polling;
subsequent to notifying the second thread to enter the sleep state, transmitting, by the supervisor, an instruction to resume operation to the first thread after completing the higher priority task to cause the first thread to finish modifying the protected resource by continuing to execute the atomic section from a location in the atomic section at which the supervisor pre-empted the first thread; and
subsequent to transmitting the instruction to resume operation to the first thread and finishing execution of the atomic section by the first thread, waking up, by the supervisor, the second thread from the sleep state.
2 . The method of claim 1 , wherein polling includes using a spinlock.
3 . The method of claim 1 , wherein the second thread is notified to enter the sleep state after a time interval.
4 . The method of claim 1 , wherein the supervisor preempts the first thread by sending an interrupt.
5 . The method of claim 1 , wherein the first thread and the second thread execute on the same processor.
6 . The method of claim 1 , wherein the first thread and the second thread execute on different processors.
7 . The method of claim 1 , wherein the supervisor notifies the second thread to enter the sleep state after polling for a time interval.
8 . The method of claim 1 , wherein each of a plurality of threads, which includes the first thread and the second thread, includes a respective thread identifier, and wherein a notification from the supervisor includes the respective thread identifier of the thread being preempted.
9 . The method of claim 8 , wherein at least one of the first thread and the second thread are configured to compare the thread identifier to an owner identifier.
10 . The method of claim 1 , wherein the supervisor sends an interrupt to the second thread.
11 . A system comprising:
a memory;
at least one processor in communication with the memory;
a plurality of threads executing on the at least one processor; and
a supervisor, wherein the supervisor is a privileged software component of an operating system executing on the at least one processor, and wherein the supervisor is configured to:
preempt a first thread while the first thread is executing in an atomic section to schedule a higher priority task;
handle interrupts;
determine a status of the first thread as executing in the atomic section when preempted, wherein the atomic section is a region of code tagged as atomic and involves modifying a protected resource;
responsive to determining the status as executing in the atomic section, notify a second thread to enter a sleep state after polling;
subsequent to notifying the second thread to enter the sleep state, transmit an instruction to resume operation to the first thread after completing the higher priority task to cause the first thread to finish modifying the protected resource by continuing to execute the atomic section from a location in the atomic section at which the supervisor pre-empted the first thread; and
subsequent to transmitting the instruction to resume operation to the first thread and finishing execution of the atomic section by the first thread, wake up the second thread from the sleep state.
12 . The system of claim 11 , wherein polling includes using a spinlock.
13 . The system of claim 11 , wherein the second thread is notified to enter the sleep state after a time interval.
14 . The system of claim 11 , wherein the supervisor preempts at least one thread by sending an interrupt.
15 . The system of claim 11 , wherein the first thread and the second thread execute on the same processor.
16 . The system of claim 11 , wherein the first thread and the second thread execute on different processors.
17 . The system of claim 11 , wherein the supervisor notifies the second thread to enter the sleep state after polling for a time interval.
18 . A non-transitory computer readable medium storing instructions, which when executed by a processor, causes the processor to:
preempt, by a supervisor, a first thread while the first thread is executing in an atomic section to schedule a higher priority task, wherein the supervisors a privileged software component of an operating system associated with the first thread, and wherein the supervisor handles interrupts;
determine, by the supervisor, a status of the first thread as executing in the atomic section when preempted, wherein the atomic section is a region of code tagged as atomic and involves modifying a protected resource;
responsive to determining the status as executing in the atomic section, notify, by the supervisor, a second thread to enter a sleep state;
subsequent to notifying the second thread to enter the sleep state, transmit, by the supervisor, an instruction to resume operation to the first thread after completing the higher priority task to cause the first thread to finish modifying the protected resource by continuing to execute the atomic section from a location in the atomic section at which the supervisor pre-empted the first thread; and
subsequent to transmitting the instruction to resume operation to the first thread and finishing execution of the atomic section by the first thread, wake up, by the supervisor, the second thread from the sleep state.