Browse Prior Art Database

Scheduling Process Swapping Based on Repaging Rate

IP.com Disclosure Number: IPCOM000106934D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 3 page(s) / 137K

Publishing Venue

IBM

Related People

Auslander, M: AUTHOR [+4]

Abstract

In AIX* 3.1 for the RISC System/6000*, the scheduler is purely a priority-based algorithm. That is, each process in the system has an assigned priority which are ordered in some fashion to allow those processes with the more favored priority to gain the CPU to complete their task. Each process will require a certain amount of memory resident in order for the task to be completed without the delays of page faults. If the number of required pages to be resident reaches a critical point, no process will be able to proceed because of the contention for the memory pages. This is typically called "thrashing" of memory.

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

Scheduling Process Swapping Based on Repaging Rate

       In AIX* 3.1 for the RISC System/6000*, the scheduler is
purely a priority-based algorithm.  That is, each process in the
system has an assigned priority which are ordered in some fashion to
allow those processes with the more favored priority to gain the CPU
to complete their task.  Each process will require a certain amount
of memory resident in order for the task to be completed without the
delays of page faults.  If the number of required pages to be
resident reaches a critical point, no process will be able to proceed
because of the contention for the memory pages.  This is typically
called "thrashing" of memory.

      It is well known that paging systems need to control the number
of processes running simultaneously to avoid thrashing.  Thrashing
occurs when the sum of the required memory for all running processes
exceeds the available main memory.  The set of processes allowed to
run is often called the multiprogramming set.  This will be a subset
of all available processes when thrashing is being controlled.

      Swapping is the process of removing a process from the
multiprogramming set (swap out) or returning it to the
multiprogramming set (swap in). The problem is to determine when
thrashing is, in fact, occurring, and to further determine which
processes should be swapped in or out to control thrashing.

      We will use repaging rate as a measure of I/O directly related
to lack of sufficient memory.  This will provide detection of system
thrashing and selection of processes which need to be swapped to
control thrashing.  A symptom of thrashing is high rates of system
paging I/O.  However, high I/O can also be caused by intrinsically
I/O bound computations.  Similarly, an indication that a process
needs more memory can be a high level paging I/O attributed to the
process.  Again, simple I/O bound processes will also display this
behavior.  Repaging rate is a measure of the number or rate of paging
I/O which consists only of reading pages which have recently be
written.  Thus, repaging I/O distinguishes I/O caused by lack of main
memory from intrinsic I/O.
EXISTING SOLUTIONS:

      Current solutions require the Operating System to guess what
the needs of the system will be in the future and attempt to prevent
the contention by "swapping out" to disk an entire process's pages to
free the memory for other processes to use.  The process to be
"swapped out" could be in any state or mode.
Overview:

      To prevent memory thrashing from occurring, the system must
keep track of the current repaging rate and the per-process repaging
rate.  With this information, the scheduler, a process that runs as a
kernel process in AIX 3.1, can determine which processes will need to
be suspended to reduce the overall contention for memory.

      By suspending some subset of the processes that are involved in
the "thrashing", the other processe...