Browse Prior Art Database

Detecting Discrepant Segments in a Paging Environment

IP.com Disclosure Number: IPCOM000078646D
Original Publication Date: 1973-Feb-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Kruskal, VJ: AUTHOR

Abstract

The algorithm described herein comprises a very efficient method for substantially improving the reliability of time-sharing systems. Using this method, a system can recover from total failures in its primary storage by utilizing naturally occurring backup copies of data on secondary storage. The major error which can occur when such a backup is used is described and an efficient detection mechanism set forth.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 3

Detecting Discrepant Segments in a Paging Environment

The algorithm described herein comprises a very efficient method for substantially improving the reliability of time-sharing systems. Using this method, a system can recover from total failures in its primary storage by utilizing naturally occurring backup copies of data on secondary storage. The major error which can occur when such a backup is used is described and an efficient detection mechanism set forth.

Many time-sharing systems use a strategy of storage management called paging. Under this strategy the system divides a user's memory into arbitrary pieces called pages. These pages do not correspond to any data structure known to the user.

The data structure which is known to both the user and the system is often called a segment. A segment is analogous to a file or data set and is usually some fixed size, which is a large multiple of the page size. The user writes his programs as though all his segments were in some huge directly addressable memory, and the system automatically transfers the pages he needs from secondary storage to primary storage and back again.

Although paging is a very powerful concept, it introduces a large number of new problems. When the system crashes, the contents of primary storage will, in general, be lost. When a page is transferred to primary storage, it is left on secondary storage as well; therefore, most pages which had been in primary storage at the time of the system crash have a possibly obsolete copy on secondary storage. It is desirable to be able to warn users that these segments may be obsolete.

Unfortunately, a bunch of obsolete pages do not necessarily add up to a bunch of obsolete segments. Since pages must be transferred out of primary storage in a different order than the user modified them, it might be found that a segment which contains obsolete pages appears to the user not as having an obsolete value, but rather as having an impossible value. Such a segment is called discrepant.

It is imperative for the system to detect discrepant segments for the user. There is no way for him to do it himself since, by definition, such a segment makes no sense to him.

There are really two separate problems in detecting discrepant segments. First, given that a segment's discrepancy is suspected, how can it be determined one way or the other? Secondly, since the above determination can be rather time consuming, how can it be determined whether to suspect the discrepancy of a segment?

A segment is discrepant when the following sequences of events occur: the user modifies page A of a segment; the user modifies page B of the same segment; the system transfers page B from primary to secondary storage; and the system crashes. To detect this sequence it is possible to remember the relationship between page B and pages such as A. If for each page the time it

1

Page 2 of 3

was last transferred out of primary storage is remembered, it can be determin...