Multics Technical Bulletin MTB-558 DM: Lock Manager Design To: Distribution From: John J. Bongiovanni Date: 06/27/84 (Original date unknown) Subject: Data Management: Lock Management Functional Design 1 INTRODUCTION This MTB contains the functional design which implements the concurrency control described in MTB-514, "Data Management: Concurrency Overview", A. Bensoussan. The functional design means the description of the lock management subsystem as it would appear to a user of the subsystem. As used throughout this document, a user of the subsystem is a Data Management application programmer or the designer of another subsystem in the Data Management Architecture which uses Concurrency Control (e.g., the Container Manager). The description of Lock Management is at the level of design. That is, all interfaces are described generally in terms of their functions, the information they need to accomplish their functions, and the information they return. Precise calling sequences are not defined; these will be the subject of a later MTB on the detailed design of Lock Management. Following a statement of functional objectives, this MTB describes a functional decomposition of Lock Management into three levels: supervisor support, per-system lock management, and per-transaction (or per-process) lock management. In this decomposition, the functions of each level are described briefly. Following this, lock objects are discussed, and their relationship to the lock identifier used by Lock Management is defined. Next, a functional description of each level is presented. For a given level, this description includes all functions performed by that level which are invoked directly by a user of that level, the parameters required by each function, and the action perfomed by each function. Finally, an example is constructed to illustrate the use of lock management by an applications programmer. _________________________________________________________________ Multics project internal working documentation. Not to be reproduced or distributed outside the Multics project without the consent of the author or the author's management. MTB-558 Multics Technical Bulletin DM: Lock Manager Design Send comments on this MTB by one of the following means: By Multics Mail, on MIT or System M: Bongiovanni.Multics By Telephone: HVN 261-9314 or (617)-492-9314 CONTENTS Page 1 Introduction . . . . . . . . . . . . i 2 Functional Objectives . . . . . . . 1 3 Functional Decomposition . . . . . . 2 3.1 Supervisor Support . . . . . . 3 3.2 Per-System Lock Management . . 3 3.3 Per-Process Lock Management . . 4 4 Lock Identifier . . . . . . . . . . 4 5 Functional Description - Supervisor Support . . . . . . . . . . . . . . . 5 5.1 Services Provided . . . . . . . 5 5.2 Implementation Notes . . . . . 6 6 Per-System Lock Support . . . . . . 6 6.1 Static Decision Tables . . . . 6 6.2 Data Structures . . . . . . . . 7 6.3 Services . . . . . . . . . . . 8 6.4 Implementation Notes . . . . . 11 7 Per-Process Lock Support . . . . . . 11 7.1 Static Decision Tables . . . . 11 7.2 Data Structures . . . . . . . . 13 7.3 Services . . . . . . . . . . . 13 7.4 Implementation Notes . . . . . 16 8 Example . . . . . . . . . . . . . . 16 Multics Technical Bulletin MTB-558 DM: Lock Manager Design 2 FUNCTIONAL OBJECTIVES The objective of the Lock Manager is to provide Concurrency Control in the manner described in MTB-514, referenced earlier. That is, an application availing itself of the services of the Lock Manager has established one or more non-intersecting hierarchical structures for accessing data, and follows a locking protocol with respect to this hierarchy. The nature of the hierarchy is not meaningful to the Lock Manager, but a typical hierarchy might be the following: Data Base => File => Record => Field An hierarchical structure can be viewed as an inverted tree, where each element of the tree has at most one parent, and one element of the tree has no parent. An application may access any number of such trees, but they must be non-intersecting in the sense that any object of interest may belong to at most one such tree. The locking protocol which must be followed by the applications programmer is as follows: 1. Associated with each object of interest (i.e., an object which may be read or modified by the applications program) is a unique element of the tree. 2. Associated with each element of the tree (and, hence, with each object of interest) is a unique lock identifier, constructed according to rules given below. 3. Each element of the tree may be locked in one of the following modes: S - Share X - Exclusive IS - Intend Share IX - Intend Exclusive SIX - Share with Intend Exclusive These modes are described fully in MTB-514, referenced earlier. For most applications using the Lock Manager described herein, only S and X modes are relevant. The remaining modes are used internally by Lock Management to implement the hierarchical protocols described in the referenced MTB in a manner transparent to the applications programmer. They are available for more sophisticated applications, however. MTB-558 Multics Technical Bulletin DM: Lock Manager Design 4. Prior to reading an object of interest, the corresponding element in a hierarchy must have been locked in S, SIX, or X mode; or at least one of its parents must have been locked in S, SIX, or X mode. 5. Prior to modifying an object of interest, the corresponding element an a hierarchy must have been locked in X mode, or at least one of its parents must have been locked in X mode. 6. Accesses to objects within an application instance are grouped into sets of consecutive accesses called transactions. Transactions are atomic in the sense that all modifications to objects from within a given transaction occur (as viewed by other applications accessing the same set of objects) at the same time or not at all. This concept is defined in greater detail in MTB-512, "Data Management: Transaction Management Overview". All locks acquired during a transaction are held until the end of the transaction (the Commit), when they are released as a unit. If a transaction aborts, modifications made to objects from within the transaction are backed-out to a previous point, either the beginning of the transaction or an earlier Checkpoint (refer to MTB-513, "Data Management: Recovery Management Overview" for a description of this process). Similarly, if a transaction aborts, all locks acquired since a previous point (either the beginning of the transaction or an earlier Checkpoint) are released as a unit. Following this protocol, an applications programmer can do locking very simply, by locking objects in S mode before reading, and locking object in X mode before writing. If larger lock granularity is desired, a node of a hierarchy can be locked in S mode before reading any objects belonging to the subtree represented by that node; similarly, a node can be locked in X mode before modifying any objects belonging to the subtree. 3 FUNCTIONAL DECOMPOSITION Lock Management consists of three levels: supervisor support, per-system lock management, and per-transaction lock management. The general functions of each level are described in this section. Multics Technical Bulletin MTB-558 DM: Lock Manager Design 3.1 Supervisor Support The supervisor will provide primitives to control the synchronization of processes (representing transactions) which are competing for locks. These primitive functions are as follows: o Suspend a process which is waiting for a lock currently held by another process in an incompatible mode. o Reactivate a process which had been waiting for a lock which is now available to it. o Allow a process to specify a time-out value when it is suspended. If it has not been reactivated within the time specified, it will be reactivated automatically by the Supervisor. o The supervisor will have no knowledge of either locks or transactions. The above functions will be requested explicitly by the per-system lock management routines when a process requests a lock or releases a lock. 3.2 Per-System Lock Management The routines at this level will maintain the knowledge of all locks held by any transaction in the system. They will perform the following functions: o Handle requests from higher level routines for locking specified objects in specified modes. This includes validating the access of the requesting process to the object. Conflict with locks held by other processes to the specified object is checked. If none is found, the lock is assigned. Otherwise, the requestor is made to wait for the lock. o Maintain lists of all locks currently held by any process. The data maintained includes the lock identifier, the process and transaction identifiers of all lockers, and the corresponding lock mode for each. o Maintain queues of processes waiting for locks. o Direct the supervisor in synchronization. That is, when a lock becomes available, the routines at this level select a waiting process, award the lock to the waiting process, and direct the supervisor to remove the process from the suspended state. MTB-558 Multics Technical Bulletin DM: Lock Manager Design o When a process must wait for a lock, determine whether deadlock exists. If it does, signal this to the process to trigger rollback to the beginning of the transaction or to a Checkpoint. o Maintain per-process lists of locks acquired and checkpoints. These lists are used to release locks when the recovery management routines reqeust back-out to a Checkpoint. 3.3 Per-Process Lock Management These routines maintain the hierarchical locking protocol in a manner invisible to the application programmer. They perform the following functions: o Maintain cognizance of the locking hierarchy. o Handle requests for locks to specific objects in specific modes. When such a request is received, these routines maintain the hierarchical locking protocol. For example, no object is locked in S mode without first locking some parent in S, X, IS, IX, or X mode. o When a lock request is received, these routines lock the minimum number of objects necessary to satisfy the request. For example, if a lock is requested in S mode for an object whose parent is already locked in S mode, no locking is done. o Maintain lists of locks acquired by this transaction and Checkpoints. These lists are used to back-out locks acquired since a prior Checkpoint, when requested to do so by Recovery Management routines. 4 LOCK IDENTIFIER To all levels of lock management, an object to be locked is specified by means of an object identifier. The purpose of this identifier is to specify the object in a manner common to all users who might lock that object. Since arbitrary objects may be locked, the assignment of identifiers is largely a convention established by the designer of the applications system. However, the lock management routines must be able to verify that the requester is allowed to hold a given lock. If a user were allowed to pass an arbitrary, unvalidated lock identifier, user data security could be compromised. To preclude this, the lock Multics Technical Bulletin MTB-558 DM: Lock Manager Design identifier is composed of two parts, as follows: o A logical identifier of a file known to the system. Initially, this is a file in the Storage System. After the implementation of large files, either a file in the Storage System or a large file is acceptable. This file is used to validate the requestor's access to the object represented by the lock identifier, for the purposes of locking only. It is used only for this purpose. The object represented by the lock identifier need have no relation to the file chosen. o A string of bits which is not interpreted semantically by lock management. This string serves to identify the object uniquely among those whose identifier is related to the same file. The semantics of this string are at the discretion of the applications system designer, subject to the obvious constraint that each object which might be locked must be identifier uniquely. An example of constructing Lock Identifiers is given in the section "Example", below. 5 FUNCTIONAL DESCRIPTION - SUPERVISOR SUPPORT 5.1 Services Provided The following services will be provided by the supervisor to support lock management: Suspend - allows a process to suspend activity at a control point until another process directs that it be reactivated. Reactivate - a facility for one process to activate a suspended process at the control point where it was suspended. Time-Out - specify a time interval after which the process will be reactivated automatically, even if no other process has directed its reactivation. This can be a parameter to the Supervisor call to suspend the process, or it can be a separate facility. MTB-558 Multics Technical Bulletin DM: Lock Manager Design 5.2 Implementation Notes Several facilities exist within the current Supervisor which could be used for this purpose, possibly with some modification. These facilities are IPC (Block/Wakeup) and Event Wait/Notify. The choice of a suitable facility depends on the following considerations: o Performance - Event Wait/Notify is more responsive than IPC for individual interactions. o System Impact - Event Wait/Notify is considerably more expensive in resources than IPC. o Race Conditions - IPC is race-free, when used properly. Event Wait/Notify requires the development of race-free protocols. These points must be considered in the design of the lock manager. The choice is not relevant in the present context, as the Supervisor interface is not visible to the user of the lock manager. 6 PER-SYSTEM LOCK SUPPORT 6.1 Static Decision Tables The following decision tables describe various important functions of the Per-System Lock Management Routines: 1. Conflict Matrix This matrix is used to determine whether a requested lock may be granted for a specified object. A lock may be granted only if there is no conflict (conflict value = N) with with any other process holding a lock to the same object. Multics Technical Bulletin MTB-558 DM: Lock Manager Design Lock Mode Held by Other Process Null S X IS IX SIX +----+----+----+----+----+----+ S | N | N | Y | N | Y | Y | +----+----+----+----+----+----+ Mode X | N | Y | Y | Y | Y | Y | +----+----+----+----+----+----+ Requested IS | N | N | Y | N | N | N | +----+----+----+----+----+----+ IX | N | Y | Y | N | N | Y | +----+----+----+----+----+----+ SIX | N | Y | Y | N | Y | N | +----+----+----+----+----+----+ 2. Lock Conversion Matrix This matrix is used to determine the effective mode requested by a process to an object. This mode depends on the mode requested and on the mode of the lock currently held by that process to the object (if any). Current Mode Held Null S X IS IX SIX +----+----+----+----+----+----+ S | S | S | X | S | SIX| SIX| +----+----+----+----+----+----+ Mode X | X | X | X | X | X | X | +----+----+----+----+----+----+ Requested IS | IS | S | X | IS | IX | SIX| +----+----+----+----+----+----+ IX | IX | SIX| X | IX | IX | SIX| +----+----+----+----+----+----+ SIX | SIX| SIX| X | SIX| SIX| SIX| +----+----+----+----+----+----+ 6.2 Data Structures The following data structures are maintained by the Per-System Lock Management Routines. 1. Global Lock Table This table has one entry for each object currently locked by any process. Each entry contains the following data: o A list of all processes currently holding a lock to this object, and the mode of each lock. MTB-558 Multics Technical Bulletin DM: Lock Manager Design o A list of all processes waiting for this lock, and the effective mode requested by each. Note that a process can be in both of these lists. An example of this case is a process which owns a lock in S mode to an object, requests a lock in X mode to the same object, but cannot obtain the lock immediately because another process owns a lock in S mode to the object. 2. Per-Process Lock Tables The following data will be maintained for each process which has invoked the Per-System Lock Management routines: A list of actions requested by the process since the beginning of the current transaction, in order of request. The actions of interest are the following: o Locks granted; for each, the granted mode and the previous mode. o Checkpoints, with the Checkpoint Identifier of each. 6.3 Services The following services are provided by the Per-System Lock Management routines. For each service, the information required by that service is presented, along with a general description of the service. 1. Lock Object This service is called to lock a single object. The information required is the lock identifier, the mode requested, and a time-out value. The information returned is a status code indicating successful lock acquisition and the current mode of lock held to the object. The function performed is as follows: o Validate the process' access to the lock object. If insufficient access, return an error status code. o Determine the effective mode requested to the lock object, using the current mode, the mode requested, and the Lock Conversion matrix. If the effective mode is identical to the current mode, then return with a successful status code. Multics Technical Bulletin MTB-558 DM: Lock Manager Design o Check for conflict with all other processes currently holding a lock to the same object, using the Conflict Matrix. o If conflict is found and the time-out is zero, return with an error code. o If a conflict is found and the time-out value is non-zero, determine whether a deadlock would occur if this process were to wait for the lock. If no deadlock would result, enter the process and effective mode into the list of processes waiting for the lock and call the Supervisor to suspend the process. Supply the time-out value to the Supervisor appropriately. On return from the Supervisor, attempt to lock the object again, adjusting the time-out value for the time elapsed since the original call. If a deadlock would result, signal this to the process. As a parameter in the signal, pass the identifier of the latest Checkpoint to which the process can roll-back in order to break the deadlock. o If no conflict is found, either add the process to the list of lock holders (with the effective mode) or change the the mode of the lock for this process is the list, as appropriate. Append an entry to the per-process action list, indicating the lock identifier, previous mode, and effective mode. 2. Unlock All This service unlocks all locks acquired by this process. It does this by scanning the list of locks acquired in the per-process table for this process in reverse-chronological order. For each lock found in the table, unlock it as follows: o If this process does not own the lock, ignore it. o Otherwise, remove this process from the list of locking processes associated with the lock object. o For each process waiting for this lock, do the following: - Check for conflict with all processes holding locks on the object, except for the process being examined, using the Conflict Matrix. MTB-558 Multics Technical Bulletin DM: Lock Manager Design - If there is no conflict, award the lock to the process and reactivate the process. 3. Checkpoint This service is called by the Recovery Management routines following completion of a Checkpoint. The information required is the Checkpoint identifier. The Checkpoint is noted by appending the Checkpoint identifier to the per-process action list. No other action is taken. 4. Unlock to Checkpoint This service is called by the Recovery Management routines following a data roll-back to a Checkpoint. Its function is to release all locks acquired since that Checkpoint. To this service, a Checkpoint can be the beginning of a transaction. The information required is the Checkpoint identifier. The information returned is a list of locks released; for each lock, the lock identifier, prior lock mode, and current lock mode is indicated. This service examines the per-process action list in reverse-chronological sequence until it reaches the specified Checkpoint identifier. For each lock found on this list, it does the following: o Change the mode of the lock for this process in the Global Lock Table to the previous mode. o For each process waiting for this lock, do the following - Check for conflict with all processes holding locks on the object, except for the process being examined, using the Conflict Matrix. - If there is no conflict, award the lock to the process and reactivate the process. o Remove the entry from the per-process action list. 5. Status This service returns to the caller information on locks owned. This information includes what locks are owned and in what modes. Queries against specific locks will also be supported. 6. Privileged Services The following services will be provided for suitably privileged users and routines: Multics Technical Bulletin MTB-558 DM: Lock Manager Design o Extended Status - returns information on all locks in the system. o Manipulate Single Lock - allows a lock to be unlocked or marked out-of-service. This service is intended to allow an administrator or salvaging routines to correct unusual unforseen circumstances. To ensure integrity, a non-privileged process will not be allowed to unlock a single lock. o Adopt Locks - allows a process to adopt all locks held by a specified process. This service is intended for recovery routines activated by abnormal process termination, which are performing recovery for the terminated process. 6.4 Implementation Notes The Per-System Lock Management routines require some synchronization mechanism to protect the integrity of the global lock management tables. A single lock-like object to protect these tables is probably adequate. This mechanism, however implemented, will not use the Lock Management mechanisms described here. Instead, more primitive mechanisms will be used. A salvager will be required to validate the lock management tables following a system crash, since the crash could occur while the Per-System Lock Manager was modifying these tables. This salvager will be invisible to users of the Lock Manager, but will interface with the Recovery Manager. The deadlock detection/resolution mechanism described above is rather crude, but it is believed adequate for initial implementation. The design is based on the premise that deadlock is a rare event, and that more intelligent selection of a lock/process pair to pre-empt is not useful. Should this prove not to be the case in practice, more intelligent mechanisms can be designed. The mechanism for one process to signal a pre-emption to another process exists (viz., IPS signals). Users of the Lock Manager would handle such a pre-emption identically to a deadlock signalled from within the same process. MTB-558 Multics Technical Bulletin DM: Lock Manager Design 7 PER-PROCESS LOCK SUPPORT 7.1 Static Decision Tables The following tables describe important functions of Per-Process Lock Support. 1. Parent Transform This transform is used to determine the lock mode required for all ancestors in the lock hierarchy prior to obtaining a lock on the child. Note that the mode indicated is the mode which must be requested for the ancestor lock objects. The mode of lock actually held may be different, depedning on the mode already held on the ancestor objects (reference the Conversion Matrix, above). Requested Mode Mode for Required for Child All Ancestors S IS X IX IS IS IX IX SIX IX This transform has the property that Parent Transform (Parent Transform (M)) = Parent Transform (M) for any lock mode M. 2. Need-to-Lock Matrix This matrix is used to determine whether it is necessary to obtain a lock for a lock object, given the requested mode of the lock for the object and the modes of locks held by ancestor objects. It is not necessary to obtain the lock if the value of this matrix is N for any ancestor of the object. Multics Technical Bulletin MTB-558 DM: Lock Manager Design Mode of Ancestor S X IS IX SIX +----+----+----+----+----+ S | N | N | Y | Y | N | +----+----+----+----+----+ X | Y | N | Y | Y | Y | +----+----+----+----+----+ Mode IS | N | N | Y | Y | N | +----+----+----+----+----+ Requested IX | Y | N | Y | Y | Y | +----+----+----+----+----+ SIX | Y | N | Y | Y | N | +----+----+----+----+----+ 7.2 Data Structures The following data structures are maintained by the Per-Process Lock Management Routines: 1. Lock Hierarchy This is a list of pairs of the form (Child, Parent), where Child and Parent are both lock identifiers, and the pair defines the obvious relationship between the lock identifiers in the lock hierarchy. 2. Lock List A list of lock identifiers of objects currently locked by the process, and the mode held for each. 7.3 Services The following are services provided by the Per-Process Lock Management routines. 1. Define Hierarchy This service is used to define a parent-child relationship in the lock hierarchy. The information required is the lock identifiers of the two objects concerned. This service validates the information provided, and enters it into the hierarchy tables. The rules for using this service are as follows: o Before calling this service for a (Child, Parent) pair of lock identifiers, the Parent must have been defined as a Child in a previous call. This is not required if MTB-558 Multics Technical Bulletin DM: Lock Manager Design the Parent is Null (i.e., the Child lock object is a root object in the locking hierarchy). o No non-root object may be locked in any mode unless its parent has been defined as a Child in a call to this service. A root object is an object in the locking hierarchy which has a null parent. o No object may have more than one parent object in the lock hierarchy. 2. Lock Object This service locks a specified object in a specified mode. The information required is the lock identifier of the object, the lock identifier of the parent of the object (this may be Null, but only for a root object), the mode requested for a lock, and a time-out value indicating how long the process should wait for the lock. The information returned by this service is a status code indicating successful locking, and the mode of the lock acquired. The mode acquired can be different from the mode requested in two cases. First, it may be unnecessary to lock the object because of a lock currently held on an ancestor of the lock in the locking hierarchy. Second, the process may currently hold a lock on the object, necessitating a different lock than requested. An example of the latter is the case where a process holds an S lock on an object and requests an IX lock on that object. The object will then be locked in SIX mode, as indicated by the Lock Conversion Matrix, above. The functions performed by this service are as follows: o If the object is a root object (null parent), validate that it is not defined in the hierarchy as otherwise. Then acquire the lock, as described below. o If the object is not a root object, walk the lock hierarchy from the root for this object to the parent of this object, in that order. The goal of this walk is to acquire a lock in mode Transform (M) for each ancestor object, where M is the mode requested for the object. For each ancestor encountered, do the following: - If M' is the mode of the lock currently held on the ancestor, then no additional lock on the ancestor is required in the case that Conversion Matrix (Transform (M), M') = M Multics Technical Bulletin MTB-558 DM: Lock Manager Design - Otherwise, acquire a lock on the ancestor object in mode Conversion Matrix (Transform (M), M') - If any ancestor is found with a lock in mode M', and the value of Need-to-Lock (M, M') is N, then no further action is required. In this circumstance, the Per-Process Lock Manager returns to its called with a successful status code and null mode. o A lock is acquired as follows: - If M' is the mode of the lock currently held for the object (this may be Null), return to the immediate caller with a successful status mode and M' mode if Conversion Matrix (M, M') = M' (i.e., lock is already held in the required state). - Otherwise, call the Per-System Lock Management routines to obtain a lock for the object in mode Conversion Matrix (M, M'). When these routines return, pass the status code returned to the immediate caller. The rule mentioned above is enforced here--namely, that before a lock can be requested of any non-root object, the parent of that object (and hence all ancestors of that object) in the lock hierarchy must have been defined by means of calls to the Define Hierarchy service. 3. Unlock All This service unlocks all locks currently held by the process. It purges its lock tables of all entries, and then calls the Per-System Lock Management routines to unlock all locks held by the process. 4. Checkpoint This service notes that a Checkpoint has occurred. It is called by Recovery Management following completion of a Checkpoint. The information provided is the Checkpoint identifier. This service merely passes the information to the Per-System Lock Management Routines by calling the Per-System Checkpoint service. MTB-558 Multics Technical Bulletin DM: Lock Manager Design 5. Unlock to Checkpoint This service unlocks all locks acquired since a specified checkpoint. It calls the Per-System Lock Management routines to unlock these locks, and it uses the returned set of actions taken to adjust its tables. 7.4 Implementation Notes The Need-to-Lock Matrix and the logic which uses it are not strictly necessary, but have been included for efficiency, as employing this logic reduces calls to the Per-System Lock Manager. An alternative method would be for the Per-Process Lock Manager to do the following when a lock on an object is requested in mode M. Beginning at the root, lock each ancestor of the object in the mode Parent Transform (M), from root to the parent of the object, in that order; then lock the object in mode M. The method described above depends critically on the following attributes of the locking strategy. First, that all locks are held until the end of a transaction, when they are released as a unit. Second, when a transaction is rolled-back to a Checkpoint, all locks released are released as a unit. If these attributes are altered, the method described above will not work. The Transform described above is the weakest of several valid transforms. A stronger valid transform requires IX mode for all ancestors, under the assumption that a lock in X mode will probably be required of the object at some point. The method described above works for either transform, and, indeed, for several others. The choice of a transform is based on an intuition about likely lock scenarios. It could be tuned easily, based on experience. Indeed, different transforms could be in effect for different data bases, users, or transactions. 8 EXAMPLE The following example illustrates how the Lock Manager described above might be used to control concurrency on a simple application. Suppose the following hierarchy is established: Data Base => File => Record => Field The following assignment of lock identifiers is possible: o Each lock identifier is of the form (A, B, C), where A is the logical identifer of a file, and B and C are integers (i.e., the bit string which forms the second part of the generic Lock Identifier described above has Multics Technical Bulletin MTB-558 DM: Lock Manager Design been divided into two numeric fields). o The lock identifier associated with a Data Base is (D, 0, 0), where D is a canonical control file associated with the data base. It is assumed that this control file contains no data. o Assuming that each file is implemented as a Multics multi-segment file, the lock identifier associated with a file is (F, 0, 0), where F is the first component of the multi-segment file. o The lock identifier for a record is (F, R, 0), where F is the first component of the multi-segment file in which the record resides, and R is the index of the record in that file. o The lock identifier for a field is (F, R, B), where F is the first component of the multi-segment file in which the record resides, R is the index of the record to which the field belongs in that file, and B is the bit offset of the field within the record. If the application is such that the functional unit of operation is a field within a record, and hence the typical lock request is for a field, then the following operations are required: o When a Data Base is opened, define the Data Base lock identifier with Null Parent. o When a File is opened, define the File lock identifier with the appropriate Data Base lock identifier as a parent. o When a Record is accessed, define the Record lock identifier with the appropriate File lock identifier as a parent. o Before reading the contents of a Field, obtain a lock with mode S on the identifier representing the Field. o Before writing the contents of a Field, obtain a lock with mode X on the identifier representing the Field. An intelligently designed application could use the lock manager to greater advantage, as the following example illustrates. Suppose that in the above example, the record accessing routines knew whether the record requested was going to be modified (e.g., the semantics of the application required update to be declared when accessing the record). The record accessing routines could MTB-558 Multics Technical Bulletin DM: Lock Manager Design then lock the identifier associated with the record in IX or X mode at the time the record is accessed. Locking the record in X mode implicitly obtains X mode locks on all of the fields in the record. Locking the record in IX mode prevents the potential conflict which would occur if the field to be updated were first locked in S mode, and then in X mode. In this case, the lock on the record (and also on the file and the data base) would be upgraded from IS to IX. Acquiring the lock on the record in the mode ultimately required can prevent roll-backs due to deadlock later. This example is intentionally simple to illustrate the basic interaction with the Lock Manager. It assumes, for instance, that the information needed to access a Data Base, File, and Record never changes, and hence there are no locks required merely to find a particular Record. If this is not the case, the example could be extended with a locking hierarchy on the data structures needed to locate individual records (indices, hash tables, etc.).