Browse Prior Art Database

Thread Block/Wake Up to Avoid Race Conditions in Multitasking Multithreaded Operating Systems

IP.com Disclosure Number: IPCOM000120818D
Original Publication Date: 1991-Jun-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 139K

Publishing Venue

IBM

Related People

Cook, RL: AUTHOR [+4]

Abstract

This article describes a technique for use in a personal computer (PC) system which changes a 32-bit operating system (OS) kernel to make the performance unblocking of a thread minimal and constant, no matter how many threads are in the operating system.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Thread Block/Wake Up to Avoid Race Conditions in Multitasking Multithreaded
Operating Systems

      This article describes a technique for use in a personal
computer (PC) system which changes a 32-bit operating system (OS)
kernel to make the performance unblocking of a thread minimal and
constant, no matter how many threads are in the operating system.

      Typically, a 16-bit OS is based on a non-preemptible kernel.
Once a thread goes into "kernel mode," it will continue running until
it blocks or completes the operation it began (e.g., system call).
The low-level primitives used by the kernel to control blocking and
unblocking are called ProcBlock and ProcRun.  Both take a 32-bit
identifier that is used as the block-id.  When a thread issues
ProcBlock on a given block-id, it is moved into the blocked state and
is no longer a candidate for the scheduler to choose for running.
When the ProcRun routine is called on a block-id, all threads that
blocked on the block-id are made runnable and will run next time they
are chosen by the scheduler on a priority basis.

      The action of making all threads runnable on a ProcRun has the
side effect of requiring every thread to code its ProcBlock to check
and see if the thread was woken up for the correct reason.  The
16-bit OS semaphores are implemented on top of ProcBlock and ProcRun
and they illustrate the race condition problem this specific wake up
behavior causes.

      When a request to block a thread on a semaphore comes in, the
kernel issues ProcBlock using the address of the semaphore as the
block-id.  If five threads have blocked requesting the same
semaphore, and a clear request comes in, the following occurs.  The
clear operation will cause ProcRun to be called for the block-id (the
address for the semaphore).  All five threads will wake up and be put
in the runnable state.  The first of those five threads that is
selected to run at the next dispatch cycle will gain ownership of the
semaphore.  When the other four threads run they will see the
semaphore is already owned and re-call ProcBlock.  This is a waste of
CPU and scheduling resources and illustrates how several threads
"race" against one another.

      Another situation in this scenario is that the more threads
that there are in the system or waiting on this block-id, the slower
the performance of the system overall, and the more inconsistent the
performance of ProcRun becomes.  This is due to the fact that the
lists of block-ids are searched linearly to figure out which threads
should be woken up.

      The solution to this as disclosed herein is to provide a new
block and run mechanism that supports singe thread wake up.  While
the need for the capability for waking up all the threads waiting on
an event is still necessary functionality, race conditions when a
single thread is woken up no longer exist as a side effect of the
low-level primitives used by the system.  The internal processing...