 |
Description  |
|
|
TECHNICAL FIELD
This invention relates to new and useful improvements in the methods of
operating general purpose digital computing systems on one or more
programs at the same time. More specifically, the present invention
relates to dynamically controlling access to and maintaining the integrity
of resources shared by different programs executing on one or more central
electronic complexes while minimizing communication of sharing control
parameters between different central electronic complexes.
BACKGROUND ART
In large data base systems where many work units or subtasks have a need to
share access to the same records, there is a need to manage concurrent
access to maintain integrity of the data.
One prior art approach to data sharing is illustrated by the concurrent
accessing of a VSAM (Virtual Sequential Access Method) data set by two or
more subtasks within a single partition, by two or more job steps
(partitions), and by any number of users (cross-system sharing). As is
explained in VSAM Primer and Reference, IBM Publication G320-5774-01
(1979), at pages 95-97, various options are available for opening a data
set for either read or write.
In VSAM cross-partition/region sharing the option is defined by the SHARE
OPTIONS parameter of the DEFINE command when the VSAM data set is defined.
By a first option, a data set may be opened by only one user for output
processing (to update or add records), or by multiple users for read
operations only. By this option, full read and write integrity is
provided. In a second option, a data set can be opened by one user for
output processing and by multiple users for read-only processing. In this
option, write integrity is provided, but read integrity is not, as users
can read a record that is in the process of being updated. In a third
option, a data set can be opened by any number of users for both read and
write operations, and no integrity (read or write) is provided by VSAM.
In VSAM cross-systems sharing, by a first option, a data set can be opened
by any number of users for both read and write operation, and no integrity
is provided by VSAM. In a second option, a data set can be opened by any
number of users for both read and write operations--however, VSAM provides
a new buffer for each direct processing request, and RESERVE and RELEASE
macros must be issued by users to maintain data set integrity.
In each of the above options, except the first, the user of VSAM must
maintain data set integrity, issuing the required ENQ/DEQ or
RESERVE/RELEASE macros.
In the prior art IBM IMS/VS product, the issuance of such macros is a
function of the Program Isolation facility. (See IMS/VS Version 1 Primer,
Program Number 5740-XX2, IBM Publication SH 20-9145-0, pages 3.12-3.14,
G320-5771-02, pages 41-46, and S320-5767-01, pages 3.12-3.13; and IMS/VS
Version 1 Recovery/Restart, IBM Publication GG24-1515-00, pages 6.1-6.4,
B.1-B.21.) However, this facility does not provide for multiple concurrent
access to common data by users executing on different central electronic
complexes (CEC's), resulting in a significant impediment to the efficient
use of data bases by large organizations.
One prior art approach to enabling multiple concurrent access to common
data is S. B. Behman, et al, U.S. patent application Ser. No. 280,648,
filed July 6, 1981, a continuation of U.S. patent application Ser No.
965,810, filed Dec. 4, 1978 (abandoned), for External Enqueue Facility for
Access to Sharable Data Facilities. Behman, et al, is a concurrency
notification facility. External Enqueue Facility (EEF) 5 maintains for
each member CPU and congruence class an interest bit. When set, the
interest bit indicates that the CPU holds or is waiting for a lock on a
data resource of the corresponding concurrence class. Each CPU includes an
Internal Enqueue Facility (IEF), which maintains for each congruence class
a lock bit. Request for access to data resource is granted by the CPU if
the corresponding lock bit in the IEF is set; but if not set, the request
must be communicated first to the EEF and thence to other CPU's showing in
the EEF an interest in the congruence class of the request. The Behman
system is, in effect, a concurrency notifier, there being no structure
described for controlling concurrent access. Furthermore, the EEF
structure is implemented either in a separate hardware device or in one of
the CPU's. A failure in the EEF effectively prevents communication between
the CPU's and processing of any data resource access request by any of the
CPU's: there being no provision in each CPU for maintaining locks held by
failed CPU's or the EEF for subsequent recovery.
SUMMARY OF THE INVENTION
It is, therefore, an object of the invention to provide an improved method
and structure for controlling concurrent access to data resources by
multiple users on the same and/or different central electronic complexes
(CEC's).
It is a further object of the invention to provide a locking structure
which enables recovery from subsystem, communication, and lock manager
failures.
It is a further object of the invention to provide an improved
communication protocol for optimizing the communication of lock data
between CEC's concurrently accessing data resources.
It is a further object of the invention to provide a method for operating a
general purpose computing system to control the allocation of data,
communication, and computing resources among plural users in a
multiprogramming and multiprocessor environment.
According to this invention, a computing system, including plural central
electronic complexes, processes one or more programs concurrently. Access
to resources shared by programs executing on one or more central
electronic complexes is controlled with minimum communication of sharing
control parameters between central electronic complexes by the method of:
maintaining within each said complex the interest state of each complex
with respect to each resource congruence class, with a complex having an
interest in a congruence class if it has previously granted access to a
resource within the congruence class;
generating within a first complex a request for access to a resource having
a resource key and a resource congruence class;
determining the interest state of said first complex and of a second
complex in the resource congruence class of the access request;
responsive to the determination that the first complex has an interest and
the second complex does not have an interest in the resource congruence
class of the access request, processing the access request within the
first complex without communication with the second complex;
responsive to the second complex having an interest in the resource
congruence class of the access request, communicating the access request
to the second complex for additional processing;
responsive to neither complex having an interest in the resource congruence
class of the access request, communicating the new interest state of the
first complex in the resource congruence class of the access request to
the second complex, and processing the access request within the first
complex; and
the processing of the access request selectively granting, denying, or
waiting access to the resource.
By a further aspect of the invention, the processing of a request for
access to a resource having a resource name and resource congruence class
is further characterized by operating a central electronic complex
according to the steps of:
responsive to the determination of the complex has an interest in the
congruence class of the access request, accessing a congruence class file
having the resource keys of all resources within the congruence class
previously accessed and not yet released, and searching for the resource
key of access request to determine the lock state of the resource to which
access is sought;
responsive to the determination that the resource key of the access request
has a null lock state, granting access to the resource and adding the
resource key to the congruence class file with a held lock state;
responsive to the determination that the resource of the access request has
a held lock state which is compatible with the access request, granting
access to the resource;
responsive to the determination that the resource of the access request has
a held lock state which is incompatible with the access request,
selectively denying access, or waiting access to the resource by adding a
wait access state to the congruence class file for the resource key.
By a further aspect of the invention, a prior request for access to a
resource having a resource key is processed by operating a first central
electronic complex according to the steps of:
responsive to release of a held lock state logged for another request for
access to the same resource key, determining if a waited access request
exists for the same resource key;
responsive to the existence of a waited access requeste logged by the first
complex, granting access to the resource to the prior request clearing the
wait access state, and logging a corresponding held lock state to the
congruence class file for the resource key;
responsive to existence of a waited access request logged by a second
complex, clearing the wait access state from the congruence class file and
communicating to the second complex the availability of the resource of
the prior request for accessing.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagrammatic representation of typical computing system
configuration for operation according to the invention.
FIG. 2 is a block diagrammatic view of resource lock manager of FIG. 1.
DISCLOSURE OF THE INVENTION
The invention provides a computer structure and method for operating a
general purpose computer for sharing data resources while maintaining
integrity and recoverability from failures, all with optimum utilization
of such computing resources as storage, communication, and computing
facilities.
The invention is substantially embodied in a resource lock manager module,
structured to operate a general purpose computing system according to the
method of the invention. The resource lock manager functions include the
following procedures:
______________________________________
Table
______________________________________
LOCK 4
UNLOCK 8
INQUIRY 6
INQRESP 7
GHTUPD 10
GRANT 9
PTB 5
IDENT 11
QUIT 12
VERIFY 13
PURGE 14
FAIL 15
RECONNECT 16
______________________________________
These procedures will be described in connection with the pseudocode
representation of the invention in Tables 4 through 16, below. The above
procedures use the following data objects:
______________________________________
MCB Master Control Block
RHT Resource Hash Table
GHT Global Hash Table
RGHT Retained Locks Global Hash Table
RHB Resource Header Block
RLB Resource Lock Block
WHB Work Header Block
SIDB Subsystem Identify Block
ISL Identified Subsystem List
RLPL Resource Lock Request Parameter
List
______________________________________
These data objects will be described in connection with FIG. 2, which sets
forth a typical configuration of an IRLM 61, 62 and is useful in
explaining the relationships between these data structures for various
data sharing and failure modes. The RHB, RLB, WHB, and SIDB chains are
dynamically structured within each central electronic complex (CEC), as
will be more fully described.
FIG. 1 is a representation of a typical system with plural central
electronic complexes (CEC's) 11, 12 sharing access to data stored in
Direct Access Storage Devices (DASD) 13 and 14. Within each complex 11, 12
is a real or virtual address space, including a number of data storage and
program areas. Those pertinent to the operation of the system according to
the method of the invention are illustrated in FIG. 1 and include a host
operating system 21, 22; one or more information management systems (IMS)
31-34; a buffer pool 41-44 for each IMS; a data base recovery control
(DBRC) system 51, 52; and an IMS resource lock manager (IRLM) 61, 62.
Each IMS 31-34 is adapted for communication with one of transaction log
tapes 71-74. Complexes 11, 12 are interconnected by communications
controller 27 (or, alternatively, by a channel-to-channel adapter) and are
loosely coupled through shared DASD's 13, 14 and control data set 57.
Each central electronic complex 11, 12 comprises a general purpose central
processing unit--together with main storage and virtual storage devices,
and the necessary channels and peripheral equipment, such as the IBM
System/360 or IBM System/370, the architecture of which is described in
U.S. Pat. No. 3,400,371 by G. M. Amdahl, et al, entitled, "Data Processing
System", and in IBM System/370 Principles of Operation, IBM Publication
GA22-7000-6.
Each complex 11, 12 operates under control of an operating system 21, 22,
such as the IBM System/360 and 370 Operating Systems, IBM Publications GS
22-6534, GC 28-0661, and GC 20-1800. IMS's 31-34 execute under control of
their respective operating systems 21, 22--and utilize these operating
system facilities for interfacing communications controller 27, which may
be, for example, an IBM 3705 Communications Controller. An implementation
of this invention enhances the IBM IMS/VS, program product number 5740-XX2
as described in IBM Publication SH20-9145-0, to provide a new and useful
method for sharing of data on DASD devices 13, 14 between IMS's 31-34
executing on the same or different CEC's 11, 12.
Data base recovery control (DBRC) modules 51, 52 on each CEC share a
control data set 57, which may reside on a direct access storage device,
such as an IBM 3350. An example of a DBRC is the IBM IMS/VS Data Base
Recovery Control Feature, program number 5740-XX2, described in IBM
Publication SH35-0027-1, as modified to operate a computing system
according to the invention, described in C. A. Carr, et al, "Method and
Means for the Retention of Locks Across System, Subsystem, and
Communication Failures in a Multiprocessing, Multiprogramming, Shared Data
Environment", U.S. patent application Ser. No. 194,506, filed Oct. 6,
1980.
Referring further to FIG. 1, the operation of a typical computing system,
including two CEC's 11, 12, will be described. Assuming that no failure
conditions exist, one or more application programs (not shown) execute in
a multiprogramming environment on each CEC, each one under control of one
of IMS's 31-34.
When an application work unit executing under IMS 31, for example, requires
access to a data resource residing, for example, on DASD 13, IMS 31 will
generate a lock request for communication to IRLM 61, as is represented by
control path 35. A lock request includes the information in Table 1.
TABLE 1
______________________________________
Lock Request Format
______________________________________
##STR1##
______________________________________
The Key field gives the name of the data base record, or resource, to which
access is required. The Hash field gives the hash class, or congruence
class of the resource--which is determined by any one of a number of
hashing techniques available in the prior art, such as described in
Behman, et al, U.S. patent application Ser. No. 965,810, filed Dec. 4,
1978 (abandoned), supra. The State field specifies one of eight lock
states and is used to determine resultant state and compatibility when a
data resource is being locked by more than one work unit. In order to
permit a data resource to be locked more than once by a given work unit,
when a work unit locks a resource for a second time, specifying a
different state than for the first lock request, the state in which the
lock is finally held should be one that carries the privileges of the
second state without losing those conferred by the first. This permits a
nonhierarchical privilege order, where each higher state does not
necessarily include all the privileges of the preceding one.
The state value from the lock request State field, and that of the prior
lock request by the same work unit for the same resource, are used to
enter the following resultant state matrix to obtain a third state. The
lock request is then processed in IRLM 61 as a request for the third
state.
TABLE 2
______________________________________
Resultant State Matrix (Third State)
Requested
Held 1 2 3 4 5 6 7 8
______________________________________
1 1 2 3 4 5 6 7 8
2 2 2 3 4 5 6 7 8
3 3 3 3 6 5 6 7 8
4 4 4 6 4 5 6 7 8
5 5 5 3 5 5 6 7 8
6 6 6 6 6 6 6 7 8
7 7 7 7 7 7 7 7 8
8 8 8 8 8 8 8 8 8
______________________________________
When more than one work unit is accessing the same resource, the following
matrix is used to determine if the lock request states are compatible (x
indicates incompatibility).
TABLE 3
______________________________________
Compatibility Matrix
Requested
Held 1 2 3 4 5 6 7 8
______________________________________
1 X
2 X X
3 X X X X X
4 X X X X
5 X X X X X
6 X X X X X X
7 X X X X X X X
8 X X X X X X X X
______________________________________
Returning to Table 1, Lock Request, the SIDB Addr field specifies the
location in memory of the system identifier block and is used to access
the work header block (WHB) chain in IRLM 61, as will be described more
fully hereafter. The Option field specifies whether the lock request is
conditional or unconditional. If the "conditional" option is specified and
the IRLM determines that the resource was previously locked in an
incompatible state (as determined by Table 3), the work unit will be
notified that the lock cannot be granted. However, if the "unconditional"
option is specified, the lock requested will be waited, and the work unit
only notified when the incompatible state is released and the waited
request granted.
In processing the lock request, IRLM 61 may communicate with IRLM 62 along
the control/data path 25, 21, 22, 23, 27, 24, 26. The conditions under
which such communication is necessary or avoided will be more fully
described hereafter, as will be the structure and steps for granting the
locks.
Once the lock is granted by IRLM 61 to IMS 31, it accesses the desired data
in DASD 13 over line 81, and reads the data into its buffer pool 41. At an
appropriate commit point in the processing of the data by the application
work unit, the data is written back out to DASD 13 and IRLM 61 notified to
release the locks.
In a similar manner, IMS's 31-34 cooperate with IRLM's 61, 62 to access
data on DASD's 13, 14 and operate on the data stored in buffer pools
41-44.
Each IMS 31-34 maintains a log of all transactions on log tapes 71-74,
respectively, for recovery in the event of a failure. Data base recovery
control facilities 51, 52 share access to control data set 57, and
cooperate with IMS's 31-34 to control the recovery of a data base in the
event of a system or other failure.
Referring now to FIG. 2, a description of IRLM 61 will be given, defining
the primary data objects used in operating the computing system according
to the method of the invention.
Resource Lock Request Parameter List (RLPL) 110 is used by IMS 31, 33 to
submit a request to IRLM 61. It includes, in accordance with the preferred
embodiment, a 32-bit resource hash value 210, a 32-byte resource name, a
4-byte SIDB address 211, an 8-byte work unit ID, a 1-byte requested lock
state, and an option indicator (conditional or unconditional).
Master Control Block (MCB) 112 provides address pointers 201-205, 261 to
the following structures and chains: RHT 114, GHT 116, RGHT 118, ISL 120,
SIDB 122 (the first in the SIDB 122, 124 chain 212), and RLB 161 (the
first in the chain 262-263 of wait RLB's 161, 165, 167 corresponding to
requests from the other IRLM 62).
Resource Hash Table (RHT) 114 contains herein 512 entries. Each entry is 8
bytes long and includes a 32-bit mask (4 bytes) and a 4-byte pointer (such
as 220, 222) to the first RHB (140 and 144, respectively) in the
corresponding RHT hash class (also referred to as a hash group or a
congruence class). Each bit in the RHT bit mask corresponds to one of the
16,384, entries in the GHT, infra, and, when set, serves as the private
use indicator discussed more fully hereafter.
Global Hash Table (GHT) 116 contains herein 16,384 entries, each entry
being one byte long, with each bit thereof assigned to correspond to one
IRLM identifier (IRLMID). In the best mode description of the invention
provided herein, only two bits are utilized, however, corresponding to
IRLMID=1 for IRLM 61, and IRLMID=2 for IRLM 62. A bit on in a GHT 116
entry means that the IRLM 61, 62 with the corresponding IRLMID is holding
and/or waiting for a lock on at least one resource that hashes into that
GHT 116 entry.
Retained Locks Global Hash Table (RGHT) 118 contains herein 16,384 entries.
As with GHT 116, each entry in RGHT 118 is one byte long, with two bits (0
and 1) utilized in this embodiment and bit 0 corresponding to IRLMID=1 for
IRLM 61, and bit 1 corresponding to IRLMID=2 for IRLM 62. A bit on in a
RGHT 118 entry means that the IRLM 61, 62 with the corresponding IRLMID
was holding and/or waiting for a lock on at least one resource that hashed
into the GHT entry corresponding to this RGHT entry at the time that IRLM
failed (abnormally terminated). No new lock requests may be granted
against locks that hash into a RGHT entry that has any bit on.
Identified Subsystem List (ISL) 120 provides a list of entries defined by
the IDENT procedure. Each IRLM 61, 62 contains a copy of ISL 120, which
shows all IMS's 31-34 associated with both IRLM's. An entry contains:
(1) an 8-byte IMS 31-34 name
(2) the IRLMID of the IRLM 61, 62 to which the IMS 31-34 is or was last
connected.
(3) a one byte "retained by QUIT RETAIN" mask, with each bit assigned to an
IRLM in the same manner as in a GHT entry, and a bit on in this mask
meaning the corresponding IRLM 61, 62 has locks retained for this IMS
31-34 due to an explicit QUIT RETAIN request.
(4) a one byte "retained due to IRLM or communications failure" mask
(ISLFMSK), with each bit assigned to an IRLM as in a GHT entry, and a bit
on in this mask meaning the corresponding IRLM was holding locks for this
IMS and then an IRLM, system or communications failure occurred.
(5) a four-byte pointer 223 to a dummy WHB 130 from which retained lock
RLB's 156, 153 are chained 251, 252. This exists only for the QUIT RETAIN
case and then only in the ISL 120 of the IRLM 61, 62 to which the IMS
31-34 was connected when the QUIT request was issued, as will be more
fully described hereafter.
An IMS Subsystem Identify Block (SIDB) 122, 124 is built by IRLM 61 or 62
when an IMS subsystem 31-34 is identified to the IRLM. The WHB's for this
IMS's work units are chained from this block. Herein, by way of example,
SIDB 122 is chained 213 to WHB 132 and SIDB 124 is chained 214, 215 to
WHB's 134, 136.
Each Work Header Block (WHB) 132, 134, 136 represents an IMS work unit that
holds and/or waits for locks, and contains a chain of all hold and wait
RLB's associated with the WHB. By way of example, wait RLB's 166, 163, 160
and hold RLB's 151, 154 are chained 231, 232, 233, 234, 235 to WHB 136;
and hold RLB's 155, 152, 150 are chained 241, 242, 243 to WHB 132,
respectively.
Resource Header Blocks (RHB) 140, 142, 144 are created for each unique
resource name for which a lock is requested and/or held, with all RHB's
that hash into one of the plurality of hash groups corresponding to one
RHT entry forming an RHB chain. Each RHB contains:
(1) the resource hash value (32 bits)
(2) the resource name (32 bytes)
(3) an IRLM interest mask, which is used in the same manner as a GHT entry.
A bit on in this mask means the corresponding IRLM is currently holding a
lock on this resource,
(4) an RHB chain word, used to maintain a chain of RHB's that hash into the
same RHT entry. By way of example, RHB 140 is chained 221 to RHB 142 and
anchored 220 to an entry in RHT 114. RHB 144 is anchored 222 to a
different entry in RHT 114.
(5) a wait RLB chain word, and a hold RLB chain word, chaining the RHB to
chains of lock holder RLB's and lock waiter RLB's. By way of example, RHB
140 is chained 156 to lock holder RLB's 150-151 and chained 168 to lock
waiter RLB's 160-161; RHB 142 is chained 157 to lock holder RLB's 152-154
and chained 169 to lock waiter RLB's 163, 165; and RHB 144 is chained 158
to lock holder RLB's 155, 156 and chained 170 to lock waiter RLB's 166,
167.
Each Resource Lock Block (RLB) represents a lock holder or a request
waiting to acquire a lock. Each RLB includes, inter alia, the lock state.
The data structure configuration of FIG. 2 represents a typical
configuration for one IRLM, say 61, and a similar structure will exist for
the other IRLM 62. Some data objects are maintained in sync (that is,
substantially identical), allowing for communication delays during normal
processing--and these include the GHT, RGHT, and ISL.
The Resource Lock Manager IRLM 61, 62 provides lock services used by the
IMS 31-34 Data Sharing Function. | | |
