Space - Time
The issues of virtual memory center around the needs of a process for memory space and the acceptible limits of execution time. If a process is completely loaded in memory, its execution time will have no delay for paging purposes. A memory that is partitioned may appear to be running many processes at once, but each process will experience delays for paging in parts that were not loaded in the partition when the processing began. This trade-off between space and time leads to the concept of space-time. Space-time is used to analyze the multiprogramming configuration to find the best partition sizes and memory allocation policies.
Definition:
The space-time product of a
process is the integral of its resident
set size over the time it is running or waiting for a missing page
to be swapped into main memory. Space-time can be measured in
page-seconds, the space and time required for the execution of a
process.
As illustrated below, the space-time product, ST, may be
computed as follows:
s(t) the size of the resident set at time t
s(ti) the size of the resident set at the ith page fault
D the time of delay for page swap
The first summation represents the pages used at each time t during the processing. The illustration below represents a four page partition. Once the partition is full, pages must be swapped in to continue processing. The blue area shows is integral of the size over the running time.
The second summation represents the pages being used when a page fault occurs. This part of the concept is represented by the yellow areas in the illustration below. The complete space-time of the process is represented by the colored areas (both yellow and blue) in the illustration below.
Notice how the time axis appears to stretch out in the
space-time illustration. What is happening here? To answer this
question, look at the discussion of
virtual time.
Intuitively, minimizing the space-time of all the processes would maximize the throughput of a multiprogrammed environment. To consider this notion, we need to consider lifetime functions and partitioning.
