Browse Prior Art Database

Scheduling Enhancement - Process Locking

IP.com Disclosure Number: IPCOM000118053D
Original Publication Date: 1996-Aug-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 132K

Publishing Venue

IBM

Related People

Browning, LM: AUTHOR

Abstract

Disclosed is a general mechanism for scheduling threads and processes to achieve greater throughput and response time. This method is centered around the use of process locks which allow many scheduling operations to be executed in parallel.

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

Scheduling Enhancement - Process Locking

      Disclosed is a general mechanism for scheduling threads and
processes to achieve greater throughput and response time.  This
method is centered around the use of process locks which allow many
scheduling operations to be executed in parallel.

      Three locks are used to serialize all scheduling
operations.  They are listed below in the order in which they can be
taken:
  o  The sleep_list lock protects global sleep lists.  For
      example, when a thread blocks on a lock, it is put to
      sleep on a list along with other threads that have also
      blocked on the same lock.  Similar lists also exists for
      device events.
  o  The process_lock lock protects thread and process state
      changes.
  o  The runqueue_lock lock protects the global runqueue.  This
      lock can be split into multiple locks if there are multiple
      runqueues, or it can even be eliminated if there are no
      cross processor runqueue operations.

      The following Figure shows how the locks are acquired, given
the major tasks that are involved in the act of going to sleep and
atomically being placed on a list.
  |-----------------------|                 <-- sleep_list
           |--------------------|           <-- process_lock
                    |---------------------| <-- runqueue_lock
  put thread on global sleep lock
                change state of thread and save registers
                               dispatcher chooses another thread to
run.

      These locks are acquired in an overlapping fashion, when
putting a thread to sleep on a global list, and thus guarantees that
a context switch will take place.  It is not necessary to fully
overlap these locks, but it greatly simplifies the code, since
situations such as "almost asleep but just woken" can be avoided.

      The primary benefit of process locking is not that list based
sleeps are handled more efficiently, but rather that non-list based
sleeps can be processed in parallel, assuming that separate processes
are involved.  For example, it is very common for a particular thread
to wait for a bit to be posted.  This paradigm is used when an event
is intended for a single thread as opposed to a group of them.  This
strategy is often used to notify a thread that it should proceed with
some task as opposed to the more general notion of resource
availability.

      For the event bit based sleeps, the process lock is taken,  the
thread  state is changed, its registers are saved, and the dispatcher
is called.  The corresponding wakeup operation acquires the process
and the  runqueue locks.

The following Figure shows the general wakeup strategy.  Here the
locks are fully nested:
  |---------------------------------|  <-- sleep_list
   for each thread on the s...