REGISTER  |  SIGN IN
United States Patent4025901
Bachman , ; et al.May 24, 1977
Title
Database instruction find owner
Abstract
One of a series of hardware/firmware primitives is disclosed for converting a general purpose digital computer into a database machine. The invention comprises a hardware/firmware implemented machine instruction called the find owner instruction, which fetches a set descriptor, which along with a base register BR, allows access to the owner pointer of a member record. The address of the owner record is then loaded into a register or registers.
Inventors:Bachman; Charles W. (Lexington, MA), Franklin; Benjamin S.  (Cambridge, MA)
Assignee:Honeywell Information Systems, Inc. (Waltham, MA)
Appl. No.:588434
Filed:June 19, 1975
Current U.S. Class:707/3 
Current International Class:G06F 17/30 (20060101)
Field of Search:340/172.5 445/1 444/1
U.S. Patent Documents
3389380June 1968Ashbaugh et al.
3401376September 1968Barnes et al.
3533075October 1970Johnson et al.
3614746October 1971Klinkhamer
3656123April 1972Carnevale et al.
3693165September 1972Reiley et al.
3787813January 1974Cole et al.
3821708August 1975Casey et al.
3878513April 1975Werner
3889243June 1975Drimak
3891974June 1975Coulter et al.
3909798September 1975Wallach et al.
3916385October 1975Parmar et al.
3916387October 1975Woodrum
3938096February 1976Brown et al.
3950730April 1976Bienvenu et al.
Primary Examiner: Shaw; Gareth D.
Assistant Examiner: Rhoads; Jan E.
Attorney, Agent or Firm:Prasinos; Nicholas Reiling; Ronald T.
Claims

What is claimed is:
1. In an internally programmed data processing apparatus having a memory comprised of a plurality of segments of addressable space, each segment being associated with a segment number for addressing said associated segment, each of said segments delineated by upper and lower variable bounds with predetermined ones of said segments storing a plurality of files of database records grouped in sets of database records, each set of database records having at least one owner database record and at least one member database record, each of said database records having at least one pointer for linking predetermined ones of said database records to predetermined others of said database records and also to predetermined ones of said sets, each pointer comprised of an area, page and line address, said area address for locating a predetermined file of said database records, said page address for locating a predetermined group of said database records within said file, and said line address for locating a predetermined one of said database records, each of said database records also being associated with one each of a record descriptor for describing said associated database record, said record descriptors being stored in predetermined seconds of said segments, each of said sets also being associated with one each of a set-descriptor for describing said associated set and for providing a displacement address of said pointer in a first record of said set of associated records, said set descriptors being stored in predetermined thirds of said segments; said data processing apparatus further having a system base from which absolute addresses of said segments, database records and descriptors are referenced, said data processing apparatus also having a plurality of base registers, each base register for storing first coded electrical signals indicative of the segment number of any of said segments and also storing second coded electrical signals indicative of an offset address associated with the segment number, said offset address for addressing from the beginning of an associated segment any data within said associated segment; said data processing apparatus further having at least one index register for storing third coded electrical signals indicative of the area, page and line address of said predetermined one of said database records; said data processing apparatus further having an arithmetic and logic unit (ALU) having communication channels with said base registers, index registers and system base for performing arithmetic and logic operations of any data or address of said segments, database records, and descriptors;
instruction hardware responsive to fourth coded electrical signals indicative of a find owner instruction for finding the owner record (i.e. said predetermined one of said database records) of said predetermined first of said database records, said find owner instruction having a first base register address (BR) for identifying a first of said plurality of base registers storing fifth coded electrical signals indicative of a first segmented address of said predetermined first of said database records, said first segmented address comprised of a first segment number in a first offset address of said predetermined first of said database records, and said find owner instruction further having a first address syllable for identifying a second of said base registers for providing a second segment number and second offset address of the set descriptor associated with said predetermined first of said database records, said instruction hardware comprising:
(a) first means coupled for being responsive to coded electrical signals stored in said first base register for fetching said fourth coded electrical signals indicative of said first segmented address into said arithmetic and logic unit;
(b) second means coupled to said first means for converting the fourth coded signals indicative of said first segmented address into seventh coded signals indicative of a first absolute address for locating said first of said database records relative to said system base;
(c) third means coupled to said second means for fetching eighth coded signals indicative of said first of said database records into said arithmetic and logic unit (ALU);
(d) fourth means coupled for being responsive to ninth coded signals indicative of said first address syllable for identifying said second of said base registers, said second base register storing tenth coded signals indicative of said second segment number and second offset address of said set descriptor associated with said predetermined first of said database records;
(e) fifth means coupled to said fourth means for converting said tenth coded signal indicative of said second number and second offset address into eleventh coded signals indicative of a second absolute address for locating said set descriptor associated with said predetermined first of said database records;
(f) sixth means coupled to said fifth means for fetching twelfth coded signals indicative of said set descriptor into said ALU;
(g) seventh means coupled for being responsive to thirteenth coded signals indicative of the displacement address in said set descriptor for addressing from the beginning of said first of said database records, an owner pointer of said pointers in said first of said database records; and,
(h) eighth means coupled to said seventh means for fetching fourteenth coded signals indicative of said owner pointer into said index register.

2. The apparatus as recited in claim 1 including ninth means coupled to said third coded signals in said index register for converting said third coded signals indicative of said area, page and line address of said predetermined one of said database records into fifteenth coded signals indicative of a third segmented address having a third segment number and third offset address for addressing said owner record (i.e. predetermined one of said database records).

3. The apparatus as recited in claim 2 coupled to said ninth means and said base registers and including tenth means for loading said fifteenth coded signals indicative of said third segmented address into said first base register.

4. The apparatus as recited in claim 3 wherein said group of database records are located within a page in one of said segments, said page located at a predetermined first area and first page address, and said page having at a predetermined first line-address a record-state indicator, and including eleventh means for ascertaining that said predetermined first record is located in said page.

5. The apparatus as recited in claim 4 including twelfth means responsive to sixteenth coded signals of said set descriptor associated with said predetermined first of said database records for identifying the type of pointer in said first and second database records.

6. The apparatus as recited in claim 5 wherein said pointer is of the type having an area, page and line address of said owner record.

7. The apparatus as recited in claim 6 wherein said pointer is of the type having a page and line address of said owner record.

8. The apparatus as recited in claim 7 wherein said pointer has a segmented address comprised of a segment number and an offset address of said owner record.

9. In an internally programmed data processing apparatus having a memory comprised of a plurality of segments of addressable space, each segment being associated with a segment number for addressing said associated segments, each of said segments delineated by upper and lower variable bounds with predetermined ones of said segment storing a plurality of files of database records grouped in sets of database records, each set of database records having at least one owner database record and at least one member database record, each of said database record having at least one pointer for linking predetermined ones of said database records to predetermined ones of said sets, each pointer comprised of a segment number and an offset address for locating predetermined ones of said database records, each of said database records also being associated with one each of a record descriptor for describing said associated database record, said record descriptors being stored in predetermined seconds of said segments, each of said sets also being associated with one each of a set-descriptor for describing said associated set and for providing a displacement address of said pointer in a first record of said set of associated records, said set descriptors being stored in predetermined thirds of said segments; said data processing apparatus further having a system base from which absolute addresses of said segments, database records, and descriptors are referenced, said data processing apparatus also having a plurality of base registers, each base register for storing the segment number of any of said segments and also storing an offset address associated with the segment number, said offset address for addressing from the beginning of an associated segment any data within said associated segment; said data processing apparatus further having an arithmetic and logic unit (ALU) having communication channels with said base registers, index registers and system base for performing arithmetic and logic operations on any data or address of said segments, database records and descriptors;
instruction hardware responsive to first coded signals indicative of a find-owner instruction for finding the owner record of said predetermined first of said database records, said find-owner instruction having a first base register address (BR) for identifying a first of said plurality of base registers storing a first segmented address of said predetermined first of said database records, said first segmented address comprised of a first segment number and a first offset address of said predetermined first of said database records, and said find owner instruction further having a first address syllable for identifying a second of said plurality of base registers for providing a second segment number and a second offset address of the set descriptor associated with said predetermined first of said database records, said instruction hardware comprising:
(a) first means coupled for being responsive to second coded signals stored in said first base register for fetching third coded electrical signals indicative of said first of said database records into said arithmetic and logic unit ALU;
(b) second means coupled to said first means for fetching fourth coded signals indicative of said set descriptor into said ALU;
(c) third means coupled for being responsive to fifth coded signals indicative of the displacement address in said set descriptor for addressing from the beginning of said first of said database records an owner pointer of said pointers in said first of said database records; and
(d) fourth means coupled to said third means for fetching sixth coded signals indicative of said owner pointer into said ALU.

10. The apparatus as recited in claim 9 including fifth means coupled to said ALU for placing said sixth coded signals indicative of said owner pointer into said first base register.
Description


BACKGROUND

1. Field of the Invention

This invention relates generally to computer systems and more particularly to an improved digital computer in the area of database operations.

2. Description of the Prior Art

Electronic computers have grown from first generation hardware characterized mainly by vacuum tubes, to second generation hardware characterized by transistors, to third generation hardware characterized, in the main, by integrated circuits. Along with these different generations of hardware there were different generations of software, wherein first generation software was characterized mainly by machine language, assemblers and subroutines, and second generation software was characterized by high level languages, monitors and micro-assemblers. Third generation software is characterized by operating systems, on-line real-time systems, multiprogramming systems, and database management systems.

First generation hardware in combination with first generation software, and also the second generation hardware in combination with second generation software were primarily oriented toward batch processing where jobs were executed primarily in serial fashion. Moreover, the third generation of hardware/software systems are also batch process oriented; however, because of the advent of multiprogramming, several jobs may be executed in parallel rather than serial, and permits the acceptance of input information for processing as it is generated.

The fourth generation system will typically be classified as a communication and control system capable of widely diversified processor applications, and will be stimulated primarily by transmitted data rather than by batch programs (i.e. system control will be established primarily by input rather than by operator action) wherein submission of information will generally be in real-time.

In the evolution of the above generations of computer systems, a major requirement was to develop effective methods for accessing the databases of the computer systems. In the development of system databases, the initial result was the growth of many different databases for each use. As a result of this growing number of databases, problems were encountered in excess storage requirements and in redundant data storage which aggravates the problem by having redundant data being updated at different times correctly in one spot and incorrectly in another spot. Steps were taken to correct these problems by integrating the many databases of a system into one single database. The Honeywell Integrated Data Store (IDS) was an example of a system designed to alleviate these problems. The Integrated Data Store was composed of one central database which could be used, for example, by the inventory control system, the internal auditing procedures and payroll procedures for accessing their relevant data in the database. In this central integrated database, there would be a single record describing information which was common to several functional needs. For instance, inventory control and internal auditing would access the number of a given part in the warehouse.

Effective techniques using integrated databases were evolved through continually improving software techniques. The set concept is a technique which allows access to records in the integrated database on the basis of relationships between records. A typical relationship would be, say, all of the employees in a particular department, such as the manufacturing department. The manufacturing department would be described by what would be called an owner record and the employees in the department would be described by what would be called member records. The set which describes a relationship such as membership in the department could then be accessed through the owner record, which allows the software to obtain all of the member records and thus, for instance, print out all of the employees in the department.

At this state of development the integrated data store had solved some of the pure data problems mentioned above, i.e. redundant data in different databases and the problem of updating multiple copies of records. The problem had been solved by one single record which therefore allowed a reduction in data storage size and a single copy of data. Other problems in using databases still remain in the performance areas. The set concepts represented new techniques of utilizing the computer and henceforth there were no specialized hardware instructions which existed on current central processors to aid these new techniques. As a result, a set operation like find the first member of the set would be implemented in the software through a series of standard machine instructions such as add, load, stores, etc. The result was a long execution time for the rather simple set operations of find first member, insert a record in a set, and the other set operations.

What was needed was a database system which both solved the traditional data problems as had already been solved in the integrated data techniques using set operations and also an efficient database system in terms of execution time and other system performance parameters. To effect this specialized hardware/firmware supported instructions were needed to assist in the set operations. For instance, a single instruction to a database address of a member record's owner record (member and owner records described infra) in a register would allow execution in a much smaller period of time than the series of 5 to 10 extended machine instructions to perform the same operation in a traditional machine.

OBJECTS OF THE INVENTION

It is a primary object of the invention to provide an improved general purpose digital computer.

It is another object of the invention to provide an improved general purpose digital computer having improved performance of database management operations.

It is still a further object of the invention to provide a hardware/firmware instruction that loads the database address of a member record's owner record into a register or registers.

It is still a further object of the invention to reduce the number of instructions in user and operating system programs.

SUMMARY OF THE INVENTION

The foregoing objects are achieved according to one embodiment of the invention by providing one of a series of hardware/firmware implemented instructions that fetches a set descriptor, which along with a base register BR, allows access to the owner pointer of a member record. The owner pointer is converted to a segmented address according to its pointer class, and then the segmented address is loaded into the base register BR. If the pointer is a part of a database type record, the pointer is also loaded into an index register.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features which are characteristic of the invention are set forth with particularity in the appended claims. The invention itself, however, both as to organization and operation together with further objects and advantages thereof may best be understood by references to the following description taken in conjunction with the drawings in which:

FIG. 1 is a block diagram of a multiprogramming system utilizing the invention.

FIG. 2 is a schematic representation of various hardware structures utilized by the invention.

FIG. 3 is a legend of terms used for reserved areas of storage in registers depicted in FIG. 2.

FIG. 4 is a schematic diagram of a process control block of a machine utilized by the invention.

FIG. 5 is a schematic diagram of a system for addressing a process control block.

FIG. 6 is a schematic diagram of the system base of a computer system utilizing the invention.

FIGS. 7A and 7B are schematic representations of a stack segment and a stack frame of a computer system utilizing the invention.

FIG. 8 is a schematic diagram of a system for addressing G-segments and in particular the queue of processes in the G-0 segment of a computer system utilizing the invention.

FIG. 9 is an exploded schematic diagram of a G-0 segment illustrating queue of processes and process linking of a computer system utilizing the invention.

FIGS. 10A through 10L are block diagrams of structures in the PCB.

FIGS. 11A through 11R are block diagrams of structures in the system base.

FIG. 12 is a schematic diagram of addressing schemes of user and system segments utilizing the system base and PCB structures.

FIGS. 13A through 13C are schematic diagrams of the control unit of the invention.

FIGS. 14A through 14I are flow diagrams of the dispatcher unit in firmware of the computer system utilizing the invention.

FIGS. 15A through 15H are diagrams of the records and their pointers used in the set instructions.

FIGS. 16A through 16C are diagrams of the database page format and the descriptors describing those pages.

FIG. 17 is a flow chart of the firmware used to locate a database page in main memory.

FIG. 18 is a logic block diagram of a hardware mechanism to locate a database page in main memory.

FIGS. 19A and 19B are diagrams of the descriptors describing sets and records used by database instructions.

FIGS. 20A through 20F are diagrams of the instruction formats used by the database instructions.

FIGS. 21A through 21E are the flow diagrams of the find owner database instructions in firmware/hardware.

FIGS. 22A through 22D are logic block diagrams for a hardware find owner database instruction.

I. INTRODUCTION

A. Scope and Organization of the Disclosure:

The environment employed for the find owner database instruction in a large scale computer are necessarily complex and are typically found in the Honeywell Series 60 computer. Moreover, a full appreciation of the teachings of the present invention can be obtained only if the reader has some familiarity with the environment in which such instrumentalities reside. For this reason, it is desirable to at least briefly explore the general architecture of a typical large scale data processing system of the type in which the principles of the present invention may be utilized to advantage. It is also desirable to first establish and understand the basic concepts of which the present invention is based.

The database set concept unifies several techniques (table, list, chain, ring, file and field array) which have been in common usage for most of the history of the computers, primarily in programming. (This concept is a specialization of the more general mathematical set concept from which the Data Structure Set gets its name and many of its properties. In this disclosure the word "set" will always be used in the data structure and not the mathematical sense).

Many systems support the set concept, but only in software. In the database management area, the Honeywell Integrated Data Store (IDS) system pioneered broad usage of the set concept to process complex manufacturing and banking problems. IDS uses the chain (ring) form of the set implementation. These basic concepts are implemented in hardware/firmware and incorporated in existing machines to produce a new and improved digital computer.

The set is one of three complementary concepts (record, field and set) needed to build and store data structures which closely approximate their natural world counter-parts. If the natural world is considered in terms of the entities that exist, the attributes which describe them, and the relationships which associate them, then the equivalent information systems concepts are: record, field, and set, respectively. In a simple example taken from a school situation, the entities would be the teachers and the children. Some of the attributes of a teacher are "name", "grade-level," and "classroom." Some of the attributes of a child are "name," "age," "parent-name." A relationship exists between teachers and children. In an information system model of this natural world situation, two classes of records (one for teachers, one for children) would be created. In each teacher record there would be a field that stores the teacher's name, another for the grade-level and another for the classroom number. Each child's record would have a file for the child's name, another for his age and yet another for his parent's name.

The information system could tie each child's record to his teacher's record in one of several ways which have been selected to implement the set concept. This might be done by physically placing all the child's records after their teacher's record array in the file. This is called a table or record array. The present embodiment incorporates the chain (ring) implementation technique of the set concept. In this form the owner record contains a pointer to the first member record. Each member record in turn contains a pointer to the following member record. The last member record of the set contains a pointer back to the owner record. Variations are allowed which provide the owner record, or the owner and all the member records with additional pointer fields to hold the address of the prior record and possibly a pointer to the owner record for member records.

The data structure set concept thus described is a refinement on the mathematical set concept, i.e. in the data structure set the set definition is embodied in the instance of the "owner" roll. Set membership is embodied in the instance of the "member" roll. Records may concurrently have many rolls as owners and members of different sets. This property permits the creation and manipulation of complex structures which model the complexity of the real world. In this refinement of the mathematical set concept one can go reversibly either from owner as definition to members or from any member to owner to re-establish the set definition.

For data structure sets, the set definition is normally based upon the value of some field or fields within the owner record while the membership in the set is re-established in the computer by the matching value of an equivalent field or fields within a potential member record. Advantage is frequently taken of this phenomenon by removing the field from the member records which carry the matching data and depending upon the owner record for reconstruction.

In the school example above, it was said that a teacher has the role of "owner" of a teacher/children set. To extend this example, we will recognize that in most schools the relationship between teacher and child is not a simple relationship (1:n) but a rather complex relationship (m:n) as the children have different teachers for different subjects. This complex relationship of teacher:child may be transformed into a new relationship entity, "pupil," and two simple relationships; teacher:pupil and child:pupil. The teacher has many children as pupils of her class and, as a pupil, the child has many teachers. The new "pupil" entity has the attributes "subject" and "hour" which serve to describe and differentiate one relationship entity from another. A child may have the same teacher for several subjects.

The data structure set concept has four basic properties:

1. A set has one, only one, and always one record in the owner roll.

2. A set has zero, one or more records in the member roll and the number varies with time.

3. Any record may be the owner of zero, one, or more sets concurrently.

4. Any record may be a member in zero, one, or more sets concurrently and thus simultaneously owned by several owner records. Each record may appear only once as a member of a particular set. Member rolls do not interfere with the owner rolls.

The notion of "next" and "prior" are important concepts to procedural algorithms which are basic to problem solving in a storage program computer. In addition to the procedural limitation of handling one record at a time, there are more important simplifying consequences to an algorithm if the member records within the set can be delivered to it in a predefined data value ordered sequence or a time insertion ordered sequence (FIFO, First-In-First-Out or LIFO, Last-In-First-Out). The notions of "first" and "last" are vital to starting and stopping the iterative execution of data algorithms. Thus the ordering of members in a set is a prerequisite to rational manipulation of the set.

The primary motivation of associating records into sets within a file is to model the natural world relationships and to assist in the accessing of selected records within the file that represent some particular relationship. The set access methods fall in between and complement the more traditional access methods. They are listed in Table I.

TABLE I ______________________________________ ACCESS METHODS ______________________________________ Direct Access Method Retrieves one record Data Key Access Method Retrieves one record Set Owner Access Method Retrieves one record Set Member Access Method Use Iteratively; Retrieves each member of set File Sequential Access Use Iteratively; Method Retrieves each record in file ______________________________________

The first four access methods are primarily used in transaction and inquiry processing, where there is a need to determine the recorded status of a particular entity, a related group of entities, or to update their recorded status. The File Sequential Access Method is primarily used for periodic batch file updating and report generation. It is possible for the same record to be accessed by all five methods as the occassion may require. Similarly, it is possible to use these access methods in combination to achieve a particular effect.

Taking the example given above, a teacher's record might be retrieved by the Data Key Access Method and then all of her pupil's records could be retrieved by Set Member Access Method. For each pupil record, the child's record may be retrieved with the Set Owner Access Method. Alternately, retrieval might start with Data Key Access to the child's record and then access all of the child's pupil records and hence the teacher's records. The basic retrieval opportunities derived from the set are given in Table II below.

TABLE II ______________________________________ RETRIEVAL OPPORTUNITIES Given Access Method Determine ______________________________________ Owner Set First member or get empty- set notice Owner Set Ith member or get out-of set notice Owner Set Member Last member or get empty-set notice Any Member Set Member Next member or get last-of- set notice Any Member Set Member Prior member or get first-of- set notice Any Member Set Owner Owner of Set ______________________________________

There is a set of primitive operations which apply to sets. These are complementary to the primitive operations on records and fields which are better known. The collection of primitive operations on sets and the complementary primitive operations for records and fields compose what are known as the manipulative facilities which are a collection of hardware/firmware instructions by which a user accesses, modifies, moves, deletes, etc., the data with which he is working. This collection of primitives (i.e. hardware/firmware instructions) can be subdivided into operations with respect to fields (i.e. data items), records, sets, and procedure logic control.

The following group of hardware/firmware instructions provide for manipulation of data within fields. It is assumed the field descriptive information (e.g. size, location, recording mode) that is needed for an operation to be performed is carried as part of data descriptors associated with the operation. The operations included in this group are, for example: move, compare, hash, add, subtract, multiply and divide.

The following group of hardware/firmware instructions provide for both direct and serial access processing of data. These provide for the creation of a data record, its subsequent retrieval, modification, testing and destruction. The record firmware/hardware instructions are: create record, destroy record, find direct record, find serial record and test record type.

The following group of set hardware/firmware instructions provides the substance of conventional data processing and the building blocks for advanced database and message management systems. They provide for the creation, access to, manipulation and testing of sets. The hardware/firmware instructions are: insert record, remove record, find relative record, (find first, find last, find next, find prior, find ith), find owner record, test set for empty, test member inserted, initiate owner record, and initiate member record.

The following group of base register hardware/firmware instructions provide the determination of and modification of current process status relative to the database access. The hardware instructions are: unload base registers, nullify base registers and the previously mentioned "find" instructions which load a base register.

As well as being used to organize and provide access to records in an application database, sets can also be used in a great variety of system software areas. Tabulated below are a list of areas of system software and for each is enumerated some usages in that area of the set concept. This list is intended to be illustrative of obvious usages and there is no intent to be complete.

1. Data Base Systems

a. Index construction (index sequential and index random)

b. Data Description structures

c. Shared access control lists

d. Process responsibility structures

2. File Systems

a. Catalog construction

b. Access rights control

3. Message Systems

a. Construction of mailbox indexes

b. Queueing Messages

c. Accessing Multi Element Messages

4. Programming Systems

a. Controlling program libraries

b. Text editing

c. Program control structure

d. Symbol reference and symbol definition structures for binding

e. Intermediate program form for compilation

5. Operating Systems

a. Queues of jobs

b. Resource allocation tables

c. Deadly embrace detection

d. Queues of processes waiting on events (I/O completion, timer)

e. Dispatching queues

1. GENERAL DISCUSSION

The invention operates typically in the hardware system environment, hereinafter described, coordinated by an operating system. Referring to FIG. 1 the subsystems are the processor subsystem 101, the storage subsystem 102, and one or more --up to 32-- peripheral subsystems 103. The processor subsystem contains a central processing unit (CPU) 104 and up to four input/output control units (IOC) 105. Each peripheral subsystem consists of a peripheral control unit (PCU) 106, a number of device adapters (DA) 107, and up to 256 peripheral i/o devices 108. The storage subsystem 102 consists of one to four semiconductor memory modules of 32 to 512 kilobytes each.

In the processor subsystem 10, the CPU 104 performs the basic processing operations for the system, and interfaces with memory 102. The IOC 105 controls all information exchanges between the storage subsystem 102 and peripheral devices 106.

A. CENTRAL PROCESSING UNIT

The CPU includes a main memory synchronizer 109, a buffer store 110, various elements that comprise the computational unit 111, and optional emulation facilities 112. The main memory synchronizer 109 resolves conflicts for the use of main memory among the computational unit 111, the buffer store 110, and the IOC 109. Conflicts are resolved on a priority basis: the IOC has the highest priority followed by memory writes (from the computational unit) and then memory reads (into the buffer store). The main CPU also includes the address control unit ACU 131 which controls main memory addressing and the associative memory AS 132 used to store most recently used addresses of main memory. The buffer store 110 is a small high-speed buffer memory that reproduces a selected region of main memory and interfaces with the computational unit to decrease average memory access time. During each memory read, both the buffer store and main memory are accessed. If the information to be fetched is already in the buffer store, the main memory read is terminated and the information fetched from the buffer store. Otherwise the main memory 102 is read. Every time this is done, the CPU 104 fetches 32 bytes that contains the desired information. This information remains in the buffer store for future memory references. Since the buffer store is transparent to software, the program controlling the computer at any given moment cannot determine whether the information it is processing has been fetched from the buffer store or from main memory.

The computational unit 111 performs all data processing and address generation within the CPU. A typical control store 130 within the computational unit (see a book entitled Microprogramming: Principles and Practices, Samir S. Husson, Prentice Hall, Inc.) contains firmware which initializes the system, controls the CPU 104 and IOC 105, and decodes an instruction set. Optionally the control store may provide scientific instructions, test routines, emulation packages, or special purpose features which extend the capabilities of the processor subsystem.

As an option, the CPU provides emulation of systems other than the instant system. Emulators 112 are components of firmware, software, and in some instances hardware.

B. INPUT-OUTPUT CONTROL UNIT

The IOC 105 portion of the processor subsystem provides a data path between any peripheral subsystem 103 and the storage subsystem 102. This path allows for the initiation of peripheral commands and controls the resulting data transfers. An IOC can typically handle up to 32 channel control units (not shown).

C. PERIPHERAL SUBSYSTEMS

In a peripheral subsystem 103 on FIG. 1 the PCU 106 is a stand-alone microprogramming processor that relieves the load on the CPU 104 by controlling the i/o devices 108 during i/o operations. The PCU does this by executing instructions contained in a channel program. This program results in arithmetic, logical, transfer, shift, and branch operations being performed in the PCU. There are several kinds of PCU's according to the kind of device each controls: i.e. unit record, mass (disk) storage, magnetic tape, communications, etc.

Device adapters 107 mediate between every PCU and the devices it controls. Each contains the dedicated firmware and logic necessary to implement communication with a particular type of device. Depending on the type, a DA 107 controls one or several devices.

The major functions performed by a peripheral subsystem 103 are as follows:

1. Transforming CPU instructions into a series peripheral device.

2. Packing and unpacking data in the form needed by the CPU or the appropriate peripheral device.

3. Keeping the CPU informed of the status of the subsystem and of the devices under its control.

4. Independently initiating and processing error and recovery procedures.

5. Allowing on-line diagnosis of a device without disturbing the device-sharing capabilities of the associated peripheral processor.

The PCU resolves conflicts for main memory between devices attached to it; however, the IOC resolves conflicts between PCU's.

D. STORAGE SUBSYSTEM

Each memory module 1-4 is 4 or 8 bytes wide. The number of modules, their size, and the data path width may vary according to size of computer. Memory modules are four-way interleaved in such a way that the four modules are accessed sequentially (module 1 contains the first 8 bytes, module 2 contains the second 8 bytes, etc.). Interleaving decreases the number of conflicts for access to main memory and thereby decreases the average memory access time. Memory is reconfigurable in case of failure; i.e., blocks of memory within a module may be removed without destroying contiguous addressing.

Main memory 102 consists of a capacitive storage medium in the form of metal oxide semiconductor (MOS) chips. This medium operates on the refresh principle to maintain information. Each memory location is typically refreshed at least once every
2 milliseconds; the design ensures that few conflicts occur between refresh timing and memory accesses. (In cases of conflict, refreshing takes precedence).

An area at the beginning of main memory is reserved for hardware and firmware. The upper limit of this area is defined by the content of a boundary address register (BAR - to be later described) which is visible to the system software. The BAR content is set at system initialization time. The memory area below the address specified in the BAR can contain IOC tables which define the configuration of the peripheral subsystems, firmware to control the CPU, or microprograms and tables for emulation. The size of the area below the address specified in the BAR depends on the system configuration. Whether microprograms are in main memory or control store depends on the system configuration and the applications run on the system.

2. BASIC MACHINE STRUCTURES

There are typically three basic data structures utilized in this hardware: data formats, software visible registers, and the instruction formats.

A. DATA FORMATS

Information is transferred between memory and the CPU in multiples of 8 parallel bits. Each 8-bit unit of information is called a byte. Parity or error correction data is also transferred with data but cannot be affected by software. Therefore, in this patent specification the term data excludes the associated parity or error correction data.

B. BYTES

Bits within a byte are numbered 0 through 7 from left to right. Bytes are processed separately or in groups. Two bytes constitute a halfword, 4 bytes a word, 8 bytes a doubleword, and 16 bytes a quadword. These are the basic formats for all data, including instructions.

C. DATA REPRESENTATION

All data are in binary form, but may be interpreted as binary, decimal, or alphanumeric. Data bits are interpreted in groups of four, as binary coded decimal data; eight as alphanumeric, or 16 to 64 as binary digits. The latter are interpreted as signed, fixed, or floating-point numbers in binary notation. Any number of contiguous bits up to a doubleword may also be manipulated as a string. The alphanumeric character set is represented in EBCDIC. ASCII is supported as an alternate exchange code.

D. BYTE ADDRESSES

Byte locations in main memory are consecutively numbered starting with zero; each number is the address of the byte. A group of consecutive bytes is said to be halfword-, word-, doubleword-, or quadword-aligned, if the address of the left byte in a group is a multiple of 2, 4, 8, or 16, respectively. Whenever a halfword, word, doubleword, or quadword is so aligned, that unit can be fetched from that address. The location of data in main memory is specified by a data descriptor which is accessed indirectly during address development. (See U.S. Pat. application No. 425,356 filed Dec. 17, 1973 entitled "Apparatus for Developing an Address of a Segment within Main Memory and an Absolute Address of an Operand within the Segment" and assigned to the same assignee as the instant application and issued into U.S. Pat. No. 3,938,096 on Feb. 10, 1976.

E. VISIBLE REGISTERS

There are 33 user-visible registers in the CPU 104 FIG. 1 whose contents collectively define the state of the CPU. There are four types: (See FIG. 2).

1. general registers

2. base registers

3. scientific registers (optional)

4. miscellaneous registers

F. GENERAL REGISTERS

General registers (GR) 201 FIG. 2 are used to manipulate fixed-point binary numbers and bit strings. There are typically sixteen 32-bit general registers in the CPU 104 --GR0 through GR15. General register GR8 through GR15 are also usable as index registers. When used as index registers, they are herein called X0 through X7; Indexing is performed using the 32-bit two's complement integer contained in a register.

G. BASE REGISTERS

Base registers (BR) have the same format as instruction counters IC and stack registers 202-203. Base registers are used during address computation to define a part of memory. There are typically eight 32-bit base registers, BR0 through BR7.

H. SCIENTIFIC REGISTERS

Scientific registers (SR) are optional equipment for computation with floating-point binary numbers. There are typically four 8-byte scientific registers which are referred to as SR0 through SR3. Scientific registers have the format 204-205 of FIG. 2.

I. MISCELLANEOUS REGISTERS

There are five other registers:

instruction counter -having format 202-203;

status register -having format 207;

stack register (called the T register);

boundary address register -having format 202-203; and

hardware control mask register -having format 208.

The instruction counter (IC) is a 32-bit register that contains the address of the instruction being executed. The status register (STR) 207 is an 8-bit register that records facts about the procedure currently being executed, for example, whether an underflow was caused by the most recent operation. The stack register also known as the T-register is a 32-bit register that contains a pointer to the top of a pushdown stack associated with the currently active procedure. Stacks to be described infra provide a work space, and a mechanism for saving local variables and preserving procedure entry, and return information. The boundary address register (BAR) 206 is a 28-bit register which specifies the lowest absolute main memory address accessible by software. This register is loaded during system initialization and can only be read by software. The hardware control mask register 208 is an 8-bit register which records machine condition information.

J. INSTRUCTION FORMATS

There are approximately 200 instructions although more or less may be utilized. Each instruction is one of four different lengths but always an even number of bytes long. Instructions are stored in consecutive storage locations. The address of the leftmost byte is a multiple of 2, and is the address of the instruction.

The eight most significant bits (and in some cases bits 8 through 11 or 12 through 15) of an instruction represent the operation code, while the remaining bits represent one or more operands. An operand may be a register designator, displacement designator, address syllable (logical address), literal value, immediate literal value. The type and number of operands are determined by the instruction format.

3. SYSTEM ORGANIZATION

A. JOB STEP AND TASK

Work to be performed by the computer system is defined externally by a series of job steps via a job control language. A job step is a unit of work to which hardware resources are allocated. Typically a job step consists of several tasks. A task is the smallest unit of user defined work consisting of a stream of instructions executed without parallelism.

B. PROCESS

The user-visible concepts of task and job step are represented in the hardware by a process and process group, respectively. A process is defined as an ordered sequence of instructions which can be executed asynchronously by the CPU (i.e., several processes can be active and sharing resources, but only one process is actually running at any one instant). A process group is a related set of processes necessary to perform one job step.

C. PROCESS CONTROL BLOCK AND SYSTEM BASE

Because processes can relinquish CPU control at various points during their execution, a storage area in main memory is made available to a process to save CPU status. This status information is utilized to precondition the CPU before a process regains control of the CPU.

The storage area assigned to a process is called a process control block (PCB) 400 on FIG. 4. The data contained in a PCB include the addresses of memory areas (address space) assigned to the process, the contents of all pertinent registers, and the state of the process. Thus a PCB serves as a temporary storage area for information necessary to start or restart a process without any information loss. Each PCB is visible to the hardware and can be addressed by the operating system via a set of hardware tables developed during system initialization and modified during system operation (FIG. 5).

There is an absolute main memory area which is referred to as the system base (FIGS. 5 and 6). This area is developed by firmware and is accessible via the base address register (BAR) 501 which can be read but not written. The system base 502
contains a number of system attributes which include a job step number and a process group number (J, P) respectively for the currently running process. Another attribute in the system base is a pointer to a hardware defined data structure known as the J table 503. This table contains an entry for every job step presently in the system. Each entry in the J table 503 points to an associated P table 504 which is also a hardware defined data structure. This table defines a process group and contains an entry for every process in the process group. Each P-table entry points to a PCB 400.

Referring to FIG. 5 the J-table pointer 505 indexed by the J number via the arithmetic portion 506 of computational unit 111 (FIG. 2) provides access to a J-table entry 503. This entry contains a P-table pointer which when indexed by the P number via computational unit 506 provides access to a P-table entry 504. The P-table entry contains a pointer 507 to the PCB of the current running process. Thus the operating system can access the active PCB using the contents of the BAR 501 and can access any other PCB given its associated (J, P) logic name.

D. MEMORY SEGMENTATION

In a multiprocess environment, such as herein described there are many processes in memory at any given time. These processes vary in size and demand for memory which causes a memory allocation problem. The hardware herein described in cooperation with an operating system (not shown herein) solves the problem by dynamically allocating memory space. Due to the random nature of memory requirements, memory is allocated in variable size segments and the memory allocation can be restructured during process run time. Thus, a process may be allocated a number of noncontiguous memory segments. This memory allocation method is called segmentation.

Segmentation presents an additional problem in that memory addresses have to be modified whenever part or all of a process is relocated. To alleviate this problem the system herein described provides a technique whereby addresses used by a process are logical rather than absolute main memory addresses. These logical addresses are used to develop absolute addresses.

Segmentation also allows each process to access its own or related memory segments via a system of segment descriptors. By accessing a segment descriptor, a process can obtain the address of a segment. Segment descriptors are contained in main memory and are maintained by the operating system.

Each process may have access up to 2068 memory segments. Normally, this would require an equal number of segment descriptors per process. However, since segments can be shared, the operating system groups segment descriptors into segment tables. This grouping is based on accessability by one process (task), a process group (job step), or globally (system wide). Each process may have up to 15 segment tables associated with it. This technique requires only one segment descriptor for each segment which can be accessed by a process via a segment table. Thus, the memory space required for segment descriptors is decreased; memory updating during relocation is reduced; and some program protection is provided. (The main mechanism for program protection is the ring system. See U.S. Pat. application No. 424,239, filed Dec. 12, 1973, entitled "Ring Checking Hardware" and now issued into U.S. Pat. No. 3,916,385 on Oct. 28, 1975.)

A process must be able to determine which segments it is allowed to access. Accordingly, the system provides a process with two segment table word arrays (STWA). These arrays contain the addresses of all segment tables accessible to a process. There are two segment table word arrays per process because there are two segment sizes, large and small. Large segments have a maximum size of 2.sup.22 bytes while small segments have a maximum size of 2.sup.16 bytes. All segments vary in size in
16-byte increments up to the maximum. A system can typically accommodate up to 28 large segments and 2040 small segments.

Segment table word arrays may be relocated by the operating system; therefore, a process must know the absolute address of its associated STWA's. The PCB for any process contains two words which contain this information which are known as address space words ASWO-1 on FIG. 4. Each word points to a segment table word array STWA. The operating system updates the contents of the ASW's whenever the associated STWA's are relocated. Working down the chain of pointers and decoding the segment descriptor is a firmware function and thus once initiated is not visible even to the operating system.

Segmentation defines over 200 million bytes of address space as being available for processes. This number exceeds the capacity of main memory; therefore, a secondary storage (magnetic disk or drum) is used in conjunction with main memory. The operating system creates the illusion that the system has a much larger main memory than is really available. This concept is called virtual memory.

At any given time, a defined segment may or may not be physically in main memory. The contents of a segment descriptor indicates whether or not the associated segment is in main memory. The hardware detects any attempts by a process to access a segment not in main memory and notifies the operating system. The operating system causes the desired segment to be loaded into main memory from secondary storage. Then the operating system places the segment's memory address in the segment descriptor which is the only place where the absolute address of a segment can be found. This operation is invisible to the process and thus it is not aware that the segment was not in main memory or that it may have to be relocated in main memory. (For details on memory segmentation see U.S. Pat. application No. 425,356, filed Dec. 17, 1973, referenced supra.

The computer system herein described provides data and procedure protection by preventing processes from interferring with each other or sharing each other's address space in an unauthorized manner. This protection is accomplished by restricting addressability via memory segmentation and by a ring system.

The segment tables isolate the address space of the various processes in the system. Processes always use a segmented address during execution. A segmented address consists of a segment number and a relative address within the segment (see above referenced application on Segmented Address Development). The hardware checks that the address used by a process is part of the address space assigned to the process. If the address is outside the prescribed address space, an exception occurs. A process cannot refer to data within the address space of another process because the hardware uses the segment tables of the referencing process. Thus, there is no possibility for a process or process group to reference an entity belonging to another process group.

Generally, overlap in address space in the system occurs for those segments shared by all processes. These public segments are created by system programs which check to insure against address conflicts. Thus, segmentation protects user programs against each other and protects the operating system against user programs.

Segments shared by several processes are not protected from misuse by one of these processes. To solve this problem, a ring system is utilized whereby procedure and data segments are grouped into a four-class hierarchy. The four ring classes are numbered 0 through 3. Each ring represents a level of system privilege with level 0 (the innermost ring) having the most privilege and level 3 (the outermost ring) the least. Every procedure in the system has a minimum and a maximum execute ring number assigned to it which specifies who may call the procedure. A procedure is a subroutine which is capable of calling other procedures and passing parameters to them:

The general rules of the ring system are as follows:

1. A procedure in an inner ring has free access to data in an outer ring. Conversely a procedure in an outer ring cannot access data in an inner ring.

2. A procedure in an outer ring can branch to a procedure in an inner ring, but the reverse is not allowed.

3. Each segment containing data is assigned two ring values, one for read (RD) and one for write (WR). These ring values specify the maximum ring value in which a procedure may execute when accessing the data in either the read or write mode.

Each time a procedure instruction is executed, the procedure's ring number (effective address ring, EAR) is checked against the ring numbers assigned to the segment containing the referenced data. The EAR is the maximum number of process ring numbers in the instruction counter and all ring numbers in base registers and data descriptors found in the addressing path. Access to the data will be granted or denied based on a comparison of the ring numbers. For example, if a system table exists in a segment having a maximum read ring value of 3 and a maximum write ring of 1, then a user procedure executing in ring 3 may read the table but may not update the table.

By predesign, rings 0 and 1 are reserved for the operating system and rings 2 and 3 are reserved for the user. Ring 0 contains those segments critical to total system operation. Ring 1 contains the bulk of the system segments whose failure would not be catastrophic and would allow recovery. The user may utilize ring 2 for checked-out programs and ring 3 for programs being debugged.

F. PROCEDURE CALLS

The procedure call is an important function in the system herein described. Procedure calls are used to pass from one procedure to another; to allow user procedures to employ operating system services; and to achieve a modular structure within the operating system. A procedure call is effected by instructions and a hardware recognized entity called a stack (FIG. 7A).

A stack is a mechanism that accepts, stores and allows retrieval of data on a last-in-first-out basis. Stacks reside in special segments called stack segments. A stack segment consists of a number of contiguous parts called stack frames 701
(FIGS. 7A and 7B) which are dynamically allocated to each procedure. The first stack frame is loaded into the top of the segment and succeeding frames are loaded after it. The last frame loaded is considered the top of the stack. The T-register 702
locates the top of the stack for the currently active process. A virtual T-register exists in the PCB of all other processes in the system.

A stack frame 701 of FIG. 7B consists of three areas: a work area 702 in which to store variables, a save area 703 in which to save the contents of registers, and a communications area 704 in which to pass parameters between procedures. Prior to a procedure call, the user must specify those registers he wishes saved and he must load into the communications area the parameters to be passed to the called procedure. When the call is made, the hardware saves the contents of the instruction counter IC and specified base registers to facilitate a return from the called procedure.

Each procedure call creates a stack frame within a stack segment 701 and subsequent nested calls create additional frames. Each exit from one of these called procedures causes a stack frame to be deleted from the stack. Thus, a history of calls is maintained which facilitates orderly returns.

To insure protection between procedures executing in different rings, different stack segments are used. There is one stack segment corresponding to each protection ring per process. A PCB contains three stack base words which point to the start of the stack segments for rings 0, 1 and 2 associated with the process. The ring 3 stack segment can never be entered by an inward call; therefore, its stack starting address is not required in the PCB.

4. PROCESS MANAGEMENT AND SYNCHRONIZATION

The system herein provides for multiprocessing operations which are controlled by an operating system using a combination of software, hardware and firmware. Software creates and deletes processes within the system while hardware and firmware multiplex processes on the CPU. In addition, a combination of software, hardware and firmware provide for synchronization between processes.

Processes are normally, but not always, started and stopped at the initiation and termination of i/o operations, during related job handling, and at other times for purposes deemed necessary by the operating system. Therefore, a communications system is necessary to efficiently start and stop related processes and to pass information between them. The hardware system herein provides internal messages called semaphores to provide a communications link between the processes.

A. PROCESS STATES

A process can be in one of four possible states at any time: running, ready, waiting or suspended. The hardware recognizes these four possible process states and executes various firmware procedures to effect process dispatching, state changes and to maintain data structures based on a process's state. The PCB contains a state field which defines the current state of its associated process.

A process is in the running state when it has control of the CPU. This state involves supplying the CPU with an address space (segment tables) and a starting address. The CPU then executes instructions in the procedure segments of the process. The process name J table word (logical address) of the PCB for the currently running process is retained in the running process word (BAR +60) within the system base (FIG. 6). (Note: The system base shown in FIG. 5 is the same as that shown in FIG. 6, but with some details omitted.)

The ready state is equivalent to running state except that the process does not have control of the CPU because it has not been recognized by the CPU. A process in the ready state is in contention for the CPU with other ready processes and the running process.

A process is in the wait state when it cannot continue until a specific event occurs such as a message via a semaphore. A waiting process is not in contention for the CPU but it may be in contention with other waiting processes for the required event.

A suspended process is a process which has been stopped for a time by software and may be resumed later. The decision to stop and resume the process is external to the process. Thus, a suspended process is not active and therefore cannot receive notification of event occurrences and cannot utilize the CPU.

A process is suspended under the following conditions:

(1) By executing a Terminate instruction (as a result of having completed all its functions.)

(2) By execution of a Suspend instruction by the operating system.

(3) By the occurrence of an exception condition whereby control is transferred to the operating system.

B. PROCESS DISPATCHING

Processes move from one state to another voluntarily by action of the process while running or involuntarily by the actions of other processes. CPU firmware, known as the dispatcher, controls the transaction of processes between states. The dispatcher uses a set of queues (to be later described) to manipulate processes which are in the ready or the waiting states. Suspended processes are controlled by software.

Referring to FIGS. 6, 8 and 9, a ready or waiting process is represented by a PCB and a special queue entry called a process link. FIG. 9 shows an exploded view of contents of the GO segment 802, and contains process links 803a-803b and
803c-803g of active processes, and free process links 805a-805c of suspended processes. Each process link specifies the process name (J, P), the process priority and a pointer to the next process link in the queue. There are various types of queues such as wait queue 803a- b and ready queue 803c-g.

A hardware device similar to the J table, known as the G table, (FIGS. 6 and 8) contains pointers to all general (known system wide) segments 802- 802n. The first element, GO, of the G table 801 points to that segment 802 containing the dispatcher queues. A G-table pointer to the G table 801 is found in the system base 502 on FIG. 5. Also in the system base is an entry called the internal process queue word (IPQW) which identifies the head 805 of the ready queue 803c-803g in the GO segment 802.

Thus, the dispatcher can examine all ready processes processes by consulting the ready queue 803c-803g. When the currently running process changes states, the dispatcher removes the process link at the head of the ready queue and uses the J, P name to access its PCB. The process defined by the PCB then becomes the new running process.

Since more than one process may be awaiting on the same event, a quene of waiting processes 803a-803b exists for each event. Waiting processes are also strung together via process links 805 residing in the GO segment. A pointer to the head of a wait queue exists in a semaphore 903 (to be later described). A number of events exist for which a process may wait; therefore, there are a number of wait queues each of which has an associated semaphore 903, 904.

The number of processes ready or waiting varies dynamically. Thus, the number of process links required for the ready and wait queues also varies. This fact introduces a memory management problem for the dispatcher. The problem is solved by another queue called the free process link queue 805a-c. This queue links together all process links in segment GO that are not being used by the ready or the wait queues and can be used to extend a particular queue of ready or waiting processes. A pointer 901 to the head 902 of the free process link queue 805 resides near the beginning of the GO segment 802.

C. PROCESS SYNCHRONIZATION

Process synchronization is required to coordinate the activities of two processes working on the same task. The synchronization is achieved using semaphores 903-904 which are data structures residing in the address space of communicating processes. A semaphore is used to signal event occurrence and to handle queues of messages. An event in this context is anything observed by a process which may be of interest to some other process. The event may be the completion of an asynchronous operation or the availability of a resource.

A process uses two semaphore operations to signal an event occurrence. One operation sends a signal to a semaphore; the other picks up a signal from a semaphore. (The sending operation is often called a V-operation; the receiving operation is called a P-operation). The sending operation allows a process to send data or a signal that data are ready. The semaphore stores the signal until another process is ready to pick it up. Thus, the sending process is free to proceed, since it has sent the data. The receiving operation examines a specified semaphore and picks up the signal. If a signal is present, the receiving process continues executing. However, if there is no signal at the semaphore, the receiving process enters the wait state. The semaphore then serves as a pointer to the head of a wait queue. The process remains in the wait state queued at the semaphore until another process sends a signal to that particular semaphore. Thus, a semaphore can hold a signal until a process picks it up, or a semaphore can hold a process until a signal is sent to it.

Messages can also be passed from process to process. A message has the same present or not present quality as a signal plus additional information. Part of the information is supplied by hardward and part is supplied by the procedure of the process that sent the message. A message carries the process name of the sending process. Thus, many processes can send information through a single semaphore stamped with the sender's name.

A message semaphore may have a queue of messages waiting to be picked up by processes. As with signal semaphores, requirements for memory space increases and decreases thus presenting a memory management problem. Again, the problem is solved with a queue of free message links. These links reside in a known place in a segment that can easily be found when needed to supply or absorb message links.

Because semaphores and the queues built on them are shared by different processes, the total semaphore structure is protected. This is accomplished by hardware and software conventions that restrict access to any segment containing semaphores. Thus, semaphores must be in semaphore descriptor segments, some of which may be G segments (if system communications is necessary). However, all G segments (except GO) are semaphore descriptor segments.

Each semaphore descriptor contains a pointer to a semaphore. Semaphore addresses are developed via a semaphore descriptor, thus providing added protection for the semaphore. A semaphore segment can be addressed logically using a segment number and a relative location within the segment or directly using the G, D number.

E. PROCESS CONTROL BLOCK STRUCTURES

Referring to FIG. 4 there is shown the format of the process control block (PCB). The process control block 400 is a storage area in main memory made available to a process to save the CPU status. Addressing a PCB is performed as described supra in relation with FIG. 5. The PCB pointer 507 (FIG. 5) points to the process control block PCB at memory location 0 on FIG. 4. It will be noted that proceeding in a downward direction memory locations increase by 4 bytes whereas in proceeding in an upward direction from memory location 0 they increase by 8 bytes. The downward memory locations are considered positive from 0 whereas the locations in an upward direction from 0 are considered negative directions. The upward locations are optional and may or may not be included in the process control block; also locations 148 through 176 are also optional. (Note that the numerals under memory location specify the displacement in bytes from the 0 reference location of the process control block PCB and are not to be confused with the reference numerals commonly used to identify parts in a patent drawing). Starting at byte 0 up to but not including byte 16 there are stored four process main words PMW 0 through PMW 3 with each process main word PMW being four bytes in length. Process main word 0 occupies bytes 0 through 3 and is comprised of 4 parts: a capability byte, a priority byte, a state byte and a decor extension byte DEXT. Referring to FIGS. 10a through 10d there are shown details of process main word PMW 0, with further details of the capability byte 1001 shown on FIG. 10b. Referring to FIG. 10b, the first bit 1005 is the accounting mode bit for indicating whether or not time accounting functions are being performed for the process. When the accounting mode bit 1005 is set to binary 0 no time accounting function is being performed for the process: whereas when the accounting mode 1005 is set to binary 1, time accounting is being performed. The scientific mode bit 1006, when set to zero, indicates that saving of scientific register of the machine is not performed and the scientific register saving area located at bytes 148 to 176 on FIG. 4 does not exist in the process control block PCB. When the scientific mode bit
1006, is set to binary 1, the scientific optional feature exists and is being used in the process, and the scientific registers saving area is used to save the contents of the scientific registers when necessary. The code mode bit 1007 indicates whether or not a standard code set or compatibility code set is being used by the process, with a binary 0 in that position indicating that standard code set is being used; whereas a binary 1 in the third bit position 1007 indicates a compatibility code set is being used. The remaining of the bits of the capability byte are set to zero.

Details of the priority byte 1002 are shown on FIG. 10c. Referring to FIG. 10c the first four bits 1008 of priority byte 1002 is utilized to set the priority level of the process associated with that given process control block PCB. Each process is assigned one of 16 levels of priority which is used for ordering competing processes i.e. (a) for choosing the process to be run among ready processes, (b) for putting processes is queues. Priorities decrease from 0 to 15, and for a given priority level the FIFO (first in first out) rule is applied. The next 4 bits 1009 of priority byte 1002 are zeroes.

Referring to FIG. 10d details of the state byte 1003 are shown. A state byte is utilized to provide information with regard to the process associated with the process control block PCB 400. The active field bit A 1010 is set to binary 1 when the process is activated. The suspend field S 1011 is set to binary 1 when the process is suspended. The substate field SS 1012 is a 2 bit field and defines the following substates of the process: (a) when set to binary 00 the process is inactive; (b) when set to binary 01 the process is waiting in the queue of ready process (Q/PR/RDY); (c) when set to binary 10 the process is waiting on a semaphore in a queue of semaphores (Q/PR/S); (d) when set to binary 11 the process is being executed by the processor. The mid-operation field (MOI) 1013 is set to binary 1 when an interrupt happens and is taken care of during the execution of an instruction --i.e. before the completion of the process. The extended decor mode bit EXTD 1014 is set to 1 when the process is operated in an extended decor mode which is an emulation mode of the machine. Bits 1015 and 1016 are set to 0. The fourth byte of process main word PMW 0 contains the decor extension number and is utilized when the system is in emulation mode.

Process main word PMW 1 is stored in bytes 4-7 of the process control block PCB. Details of PMW 1 is shown on FIG. 10e. The status byte 1016 is the first byte in PMW 1 and stores the status register contents. The multiprocessor byte MP 1018 is significant in a multiprocessor architecture otherwise this field is zero. The second and fourth bytes of process main word 1 are the MBZ fields 1017 and 1019 respectively which must be zero for normal operation.

Process main word PMW 2 occupies bytes 8 through 11 of the process control block and is shown in more detail on FIG. 10f. Referring to FIG. 10f the field from bit 4 through bit 31 contains the local name SEG, SRA 1021 of the semaphore to which the PCB is linked when the process is either in the waiting or suspended states. The exception class and type field 1023 contains the class and the type of the interrupt-like exception which cause the process to enter the suspended state after an exception. The field from bits 4 through 15 is meaningless 1022 when a process is in a different state than those mentioned above.

Process main word PMW 3 occupies bytes 12 through 15 in PCB 400 and points to a decor extension table. Referring to FIG. 10g for details of PMW 3 the DETSZ field 1024 defines the number of entries in the table and if this field is zero no decor extension is allowed to the process. The DETA field 1025 is the absolute address of the decor extension table in units of 16 bytes and is significant only if DETSZ is not 0. The decor extension table is made up of DETSZ entries. Each entry is one byte size. The DEXT.sup.th entry of the table defines the capability of the process to operate in the decor extension mode DEXT. When the DEXT.sup.th byte is 0 the decor extension number DEXT is not allowed, whereas if the DEXT.sup.th byte is 1 the decor extension number DEXT is allowed. Values of DEXT other than 0 and 1 are illegal. (See FIGS. 10a DEXT number 1004).

Bytes 16 through 23 of PCB 400 contains 2 address space words ASW 0 and ASW 1 respectively and each ASW contains a pointer to an array of segment table words. Both ASW 0 and ASW 1 respectively have the same format shown on FIG. 10h. The size of the array of the segment table words is defined by the number of segment table words in an array and typically comprises six for ASW 0 and eight for ASW 1. The STWSZ field 1026 indicates the size of the array of the segment table words. The segment table word array field STWA 1027 contains the absolute address STWA of the array in units of 16 bytes --i.e. the absolute address of the array is 16 times STWA in bytes.

Bytes 24 through 27 in the PCB contain an exception word EXW shown in greater detail on FIG. 10i. The exception word contains a pointer (SEG, SRA) 1029 to an exception class table which defines the action to be taken following a process exception according to its class as stored in process main word PMW 2. (See FIG. 10f). The MBZ field 1028 of exception word EXW must be 0.

The stack word SKW located in bytes 28 through 31 of the PCB contains the value of the top of the T register of the stack of the process when the process is not running and is shown in greater detail in FIG. 10j. Referring to FIG. 10j, bits 0
and 1 define the TAG field 1030. The TAG indicates the type of descriptor by its contents and must be zero for SKW. Bits 2 and 3 of the SKW word contain the RING field 1031 which contains the ring number associated with the segmented address of the stack for protection purposes and in this case must be zero. Bits 4 through 31 contain the segment number SEG, and the segment relative address SRA 1032 and is a field which identifies the segment described in a segment table and the segment relative address within the segment. The stack word SKW is updated every time the process leaves the running state. It is used to restore the T register contents every time the process becomes running. In this last case the TAG 1030 and RING 1031 are tested to be zero, otherwise an illegal PCB exception occurs.

Bytes 32 through 35 of the PCB 400 contain the instruction counter content word ICW sometimes also referred to as ICC. Referring to FIG. 10k there are shown details of the instruction counter word ICW wherein the TAG field 1033 must contain binary 00 (i.e. values other than zero are illegal in the instruction counter). The current RING field 1034 occupying bits 2 and 3 defines the current ring number of the process to be used in determination of access rights to main storage. Bits 4
through 31 define the segment number and the segment relative address (SEG, SRA) 1035 which define the address of the next instruction to be executed.

The MBZ field in bytes 36 through 39 must be zero. (Note the MBZ field always indicates a field which must be zero). The MBZ word is tested every time the PCB is accessed from the name J, P. If it is not zero an illegal PCB exception occurs.

Stack base words SBW 0-2 occupy bytes 40-51 in the process control block 400. These words have the same format which is shown in greater detail on FIG. 10l. They are utilized during stack operations and whenever used their TAG field 1036 and RING field 1037 must be zero otherwise an illegal PCB exception occurs. Bits 4 through 31 contain the segmented address (SEG, SRA) 1038 of the first bytes of the stack segments for ring zero, 1 and 2 respectively.

Bytes 52 through 83 of the process control block 400 is a space reserved for the base registers saving area (8 words). Bytes 84 through 147 is a saving area which is utilized to save the values of all general registers (16 words). Bytes 148
through 179 is a saving area which is utilized to save the scientific registers (8 words).

Five double words are provided in the PCB 400 above the PCB zero address, for time accounting purposes when the accounting mode bit in the PMW 0 word is set. These words are located from PCB address minus 8 to PCB address minus 40. Each word contains a time or a time interval expressed in microsecond units in its first 52 bits with bits 52-63 filled with zeroes. The residual time out double word RTO (first 8 bytes above 0 in the PCB) contains the quantum of time which is actually spent by the processor on behalf of the process before a time out exception occurs. The RTO word is updated in the following way: each time the process exits the running state the process timer value is stored in the RTO word. Each time the process enters the running state, the process timer value is loaded from the RTO.

The running time accounting RUA double word at bytes 7 through 15 is a time counter which specifies the total amount of processor time a process was in the running state. The time accounted for is the time actually spent by the processor on behalf of the process exclusively. The RUA word is updated in the following way: each time the process exits the running state, the value of the process timer PT is read. The difference of the contents of RTO and PT is added to RUA. (Consecutively, the PT value is stored in RTO). Note that the time during which the process is suspended is not computed. The RTO and RUA words are updated even if the accounting mode bit is set to 0. However the CET, RTA, and WTA words (to be later described) are provided in the process control block only if the accounting mode bit in the process main word PMW 0 is set to 1. They are updated only in this case.

The waiting time accounting WTA word at bytes 17 through 23 is a real time counter which specifies the total amount of real time the process was in the waiting state. The WTA word is updated in the following way: each time the process exits the waiting state the time of day clock (not shown) value TOD is read and the value of TOD minus the value of CET word is added to the WTA word.

The ready time accounting RTA word located at bytes 24 through 31 is a double word which is a real time counter which specifies the total amount of real time the process was in the ready state. The RTA is updated in the following way: each time the process exits the ready state, the time of day clock value TOD is read, and the contents of TOD minus the contents of CET is added to RTA.

The current entry time CET double word at bytes 32 through 39 contains the time of day at which the process entered one of the following states: ready, waiting, running, and suspended.

SYSTEM BASE STRUCTURES:

Referring to FIG. 6 the format of the system base 600 is shown. The system base resides in absolute main memory and is developed by firmware and is accessible via the boundary address register (BAR) which can be read but not written. The boundary address register BAR is below an area in main memory reserved for hardware and separates this area in memory reserved for hardware and the system base 600. Referring now to FIG. 6 the system base 600 contains a number of system attributes which includes a job step number and a process group number (J, P) for the currently running process. From the logical name of the process J, P, the absolute address of the corresponding process control block PCB is obtained. The size and address of the J table are defined by the contents of the J table word (JTW). This word is located at the address defined by the BAR register. The format of the JTW is shown on FIG. 11a. The size (JTSZ) 1101 or the J table 1204 on FIG. 12 defines the number of entries in the J table 1204 which may be up to 255 entries. The JTSZ 1101 is an 8 bit positive integer; an out of J table exception occurs if J is greater than JTSZ. The absolute address of the J table 1204 is obtained by multiplying the J table pointer 1102
by 16. The J table 1204 contains J table entries whose format is shown in greater detail on FIG. 11b. Each J table entry defines the absolute address of a P table 1205 which is obtained by multiplying the P table pointer 1104 by 16. The size (PTSZ)
1103 of a P table defines the number of entries in the P table. The PTSZ is an 8 bit positive integer which may typically vary from 0 to 255 to indicate the number of entries in the P table. An out of P table exception occurs if P is greater than PTSZ. Each entry of the P table 1205 defines the absolute address of a process control block (PCB) 1206 by multiplying the process control block pointer 1107 by 16. A presence indicator P 1105 indicates the absence of a PCB 1206 when set to binary 0 and indicates the presence of a PCB when set to binary 1. (When the presence indicator P 1105 is found to be 0 a vacant P table entry exception occurs). Bits 1 through 7 of the P table indicator (FIG. 11c) must be 0 (MBZ) 1106, otherwise an illegal P table entry exception occurs.

At address BAR plus 4 of the system base 600 there is the format byte of a G table word (GTW) shown in greater detail on FIG. 11d. The size and the address of a G segment-table 1212 on FIG. 1200 are defined by the contents of the G table word (GTW). The size (GTSZ) 1108 of the G table 1212 defines the number of entries in the G table which may typically be up to 255 entries. GTSZ is an 8 bit positive integer; an out of G table exception occurs if the G number is greater than the GTSZ. The absolute address of the G table 1212 is obtained by multiplying the G table pointer 1109 by 16. The format of the G segment table entry has a two word size (8 bytes) and is called a G segment descriptor. The format of the G segment descriptor is shown in detail on FIGS. 11e and 11f. All G segment descriptors are direct and therefore the indirect bit I, 1111 must be 0 otherwise an illegal segment descriptor exception occurs. The presence indicator P 1110 is a one bit field which when set to binary 1
indicates that a segment is defined in main storage for the segment number to which that descriptor corresponds; whereas if it cleared to 0 no segment is defined and a reference to the segment descriptor causes a missing segment exception. The available bit A 1112 is a one bit field which indicates whether or not the segment is available; it is only checked if this segment is defined (i.e. P equals binary 1), otherwise it is ignored. The used flag field U 1113 indicates whether or not the segment has been accessed. If the U bit is set to binary 0 the segment has not been accessed; whereas if the U field is set to binary 1 the segment has been accessed. The written flag field W 1114 indicates whether the segment has been written. If W is set to binary 0 the segment has not been written; whereas if W is set to binary 1 the segment has been written. The gating indicator GS 1115 of a G segment descriptor must be set to binary 01, otherwise an illegal segment descriptor exception occurs. The reason for this is that a G segment always contains semaphores (although the reverse is not true i.e. all semaphores are not required to be in a G segment) and instructions on semaphores require the GS code to be binary 01. The absolute address of the base of a segment 1214 is defined in the G segment descriptor of FIG. 11e by the 24 bit base field 1116; the content of this field is multiplied by 16 to obtain the absolute address. The second word of the G segment descriptor of FIG. 11f occupies bit position 32 through 63 in the G table 1212. The RSU field 1117, bits 32 through 39 is reserved for software use and is generally ignored when used as a G segment descriptor as it is in this case. The MBZ field 1118 must be 0 otherwise an illegal segment exception occurs. Since the MBZ field 1118 occupies bits 40 through 51 it sets the SIZE field 1119 which is the field for a small segment SIZE; hence all G segments must be of the small segment type. The segment SIZE 1119 is a 12 bit positive integer defining the number of bytes in the segment and the segment size is interpreted as a multiple of 16. Therefore the segment size for a G segment 1214 cannot exceed 2.sup.16 bytes (small segments). If a displacement D within a G segment is referenced where D is greater than or equal to SIZE 1119, an out of segment exception occurs. The method of accessing main memory which uses a G segment and a displacement D within that segment is called G, D accessing. The various exceptions which may occur during G, D memory operations are referred to as G, D access exceptions.

Referring once again to the system base 600 of FIG. 6 there are 9 system exception cell words located between BAR plus 8 and BAR plus 44. The format of the system exception cell words EXC is shown on FIG. 11g. Since semaphores are utilized for transmitting messages to dedicated processes when a system exception occurs the pointers to these semaphores are found in 9 locations of memory each location called a system exception cell --one per class of system exception. The MBZ field 1120 must be set to binary 0 otherwise a system check occurs. Each exception cell (EXC) contains the system name G, D 1121 and 1122 respectively.

The channel exception cell located in BAR plus 44 of the system base 600 has a format which is similar to the system exception cell previously discussed and contains the system name GD of a semaphore which is used for transmitting messages to dedicated processes when a channel exception occurs.

An internal processor queue word IPQW is located beginning at BAR plus 48 and details of its format are shown on FIG. 11h. The IPQW word points to the head of a queue of processes ready (Q/PR/RDY) as shown on FIG. 9 by reference numerals 905 and
805. The queue of processes ready (Q/PR/RDY) links all processes which are in the ready state. It is referenced by the HEAD of Q/PR/RDY-field 1124 (FIG. 11h) of the IPQW word by pointing to the top of the ready process queue. The HEAD of Q/PR/RDY-field 1124 contains a 16 bit positive integer which is the displacement from the base of the G segment number 0, referred to as the GO segment, to the first byte of Q/PR/RDY. If this Q/PR/RDY bit field is 0, the ready queue is considered to be empty. The MBZ field 1123 must be 0 otherwise a system check occurs.

At BAR plus 52 of the system base 600 there is shown the storage for the initial and current retry counts whose format is shown in detail on FIG. 11i. The NFS field 1125 is a nonfunctional storage field and is not utilized by the system base. The initial retry count field 1126 and the current retry count field 1127 are used to control the number of times automatic instruction retry is executed before a machine error is made to produce a machine failure exception condition. They are loaded with the same number by a Reset Retry Count (not shown herein).

The running process word (RPW), shown in FIG. 11j, is stored in BAR plus 56 of the system base 600 and is used to store the name of the running process with its priority in case of a monoprocessor architecture. The NFS fields 1128 and 1131
respectively are nonfunctional storage fields and may be utilized for any purpose by any facility but is generally not utilized by the system base. The priority level of a running process is stored in the PRI field 1129. An asynchronous trap bit is stored in AB field 1130; whereas an asynchronous trap ring is stored in ARN field 1132. The logical name J, P of the running process in case of a monoprocessor architecture is stored in the J, P field 1133.

An Absolutization Table Pointer word shown on FIG. 11k is located at BAR plus 60 in the system base 600 and is utilized in initial system load to initialize the absolute addresses in the initial system load (ISL) program by adding the contents of BAR to all absolute addresses in the ISL program. The Absolutization Table Pointer 1135 defines the location of an Absolutization Table (not shown). The Absolutization Table Size is shown by the ATSZ field 1134.

The CPU serial number word shown on FIG. 11l is a 4 byte word located at BAR plus 64 and contains the serial number of the CPU in the CPU serial number field 1136.

A main storage upper limit word shown on FIG. 11m is located at BAR plus 68 and indicates the main storage upper limit 1139 by providing the absolute address of the last available word in main storage.

At BAR plus 72 there is located a word shown on FIG. 11n for providing the initial system load ISL device channel number (CN) 1140 and the hardware device channel number (CN) 1141.

The type and subtype of a device used in the computer system is shown by a hardware device type word (FIG. 11o) in fields 1143 and 1144 respectively; where the RSU field 1142 is reserved for software. This word is found in the system base at BAR plus 76. A similar word having a similar type format shown on FIG. 11p contains the type and subtype of the device used in the initial system load. This word is located at BAR plus 80.

when the restart button of a computer is pressed, a simulated V-operation is preformed on a semaphore and the Ready state is entered. A pointer to this semaphore is found at BAR plus 84 of the system base 600 and is called a restart cell word, and has a format shown on FIG. 11q. The format is similar to the system exception cell described supra and contains the system name G, D of a semaphore in the G field 1149 and D field 1150 respectively. The MBZ field 1148 must be 0.

Where there is more than one processor to the computer system, a word is provided in the system base 600 at BAR plus 88 for multiprocess extension. Details of this word are shown on FIG. 11r.

EXAMPLES OF SYSTEM BASE AND PROCESS CONTROL BLOCK USE

Referring to FIG. 12 there is shown one example, how the system base may be utilized in combination with the process control block in order to address and access a user segment, a system segment, or a queue of processes ready (Q/PR/RDY) segment. Main memory 1200 has a portion 1203 reserved for hardware use. A boundary address register BAR 1202 separates the system base 1215 from the portion of memory 1203 reserved for hardware. The boundary address register BAR 1202 is utilized to address items in the system base 1215 by adding the contents of the boundary address register to the displacement in 4 byte units of the item desired in the system base. This address then points to the first byte of the item in the system base desired. In FIG.
12 the BAR 1202 is pointing at the J table word (JTW). The J table word, as previously discussed, has a pointer which points to a J table 1204. By indexing to the J number shown on FIG. 5, a J table entry 1216 is obtained. At the J table entry there is a P table pointer which points to the absolute address of the P table 1205. By indexing to the P number (see FIG. 5) within P table 1205 the absolute address of the process control block 1206 is obtained. As previously shown in process control block PCB 1206 there are two address space words ASW 0 and ASW 1. The high order bits of the segment table number field STN in the base register 1201 is used to access one of these two address space words, in this instance ASW 1 which has a segment table word array STWA pointer that points to segment table word array STWA 1208. Together with the segment table number STN of the base register 1201 one of 8 segment table words is accessed in STWA 1208, which points to one of 8 segment tables 1210. The segment table entry STE from base register 1201 is then utilized to make one of 256 entries in segment table 1210 where a segment descriptor is located. The segment descriptor is then utilized to access a user segment 1211. (For greater detail see U.S. Pat. Application No. 425,356, filed on Dec. 17, 1973, entitled "Apparatus for Developing an Address of a Segment within Main Memory and an Absolute Address of an Operand within the Segment," and issued into U.S. Pat. No. 3,938,096 on Feb. 10, 1976.

In order to access a system segment 1214 which is utilized to store semaphores a G table word CTW is utilized in the system base 1215. The address of the G table word is obtained by adding the displacement of the G table word in the system base to the boundary address register BAR 1202. (See FIG. 6). The G table word GTW includes a G table pointer which points to a G table 1212. By utilizing a G number available to the system and indexing in the G table a G segment descriptor is accessed which is utilized to address a system segment 1214.

Similarly the system base 1215 is utilized to access the queue of process ready (Q/PR/RDY) 1213 by locating an internal processor queue word IPQW which points to the Q/PR/RDY segment 1213.

G. CONTROL UNIT

Referring to FIGS. 13a-13c details of the control unit are shown. The control unit, although shown separate from the central processing unit (CPU), is in actuality a part of the CPU and is comprised of a control store unit CSU 1301, a control store interface adapter CIA 1302 and appurtenant subunits, control store loader CSL 1303 and control and load unit CLU 1304.

The control store unit CSU 1301 receives micro-instructions from the control store loader CSL 1303 via the control and load unit CLU 1304 and the control store interface adapter CIA 1302. Under normal operating conditions, microprograms are loaded from an external source during system initialization and become a permanent control function of the machine. However the control store unit CSU 1301 has the ability to be reloaded and initialized in a manner that provides for a variety of central processing units CPU 1306 operational modes. The following modes of operation of the CPU are available under control of the CSU 1301; (a) native mode; (b) emulation mode; (c) concurrent native and emulation modes; (d) diagnostic mode. This capability is possible because the micro-instructions resident in the CSU are the source of micro-operations used to control the operation of all other CPU functional units such as the emulation unit 1316, the arithmetic logic unit ALU 1317, the instruction fetch unit IFU 1318, the address control unit ACU 1319 and the data management unit DMU 1321. Also shown within the central processing unit CPU 1306 are previously described general registers 1307, base registers 1308, scientific registers 1309, T-registers
1310, status registers 1311, instruction counter IC 1312, and hardware control mask register 1313.

Typically the control store unit CSU 1301 is a 9K bipolar integrated circuit programmable read-only memory (PROM) mixed with read/write random access store (RAM). It has a typical 150 nanosecond read cycle and a 450 nanosecond write cycle. Each location of control store stores one 84-bit micro-instruction word (to be later more fully described), and each micro-instruction word controls one CPU cycle. As each location of the control store of the control store unit CSU 1301 is read, its contents are decoded by micro-operation decoders which provide micro-operation control signals each of which causes a specific operation within the CPU to take place (to be later described in detail).

By grouping locations within each micro-instruction word (to be later described in detail) control store sequences are obtained that can perform a specific CPU operation or instruction. As each instruction is initiated by the CPU, certain bits within the op-code are used to determine the control store starting sequence. Testing of certain flops (not shown) which are set or reset by instruction decode functions allows the control store memory to branch to a more specific sequence when necessary.

The control store interface adapter CIA 1302 communicates with the control store unit 1301, the data management unit DMU 1321, the address control unit ACU 1319, and the arithmetic logic unit ALU 1317 for directing the operation of the control store memory 1333 of FIG. 13b. The CIA 1302 includes logic for control store address modification, testing, error checking, and hardware address generation. Hardware address generation is utilized generally for developing the starting address of error sequences or for the initialization sequence.

The data management unit DMU 1321 provides the interface between the CPU 1306 and the main memory and/or buffer store memory shown on FIG. 1. It is the responsibility of the data management unit to recognize which unit contains the information required by other units and strobe in information into the CPU registers at the proper time. The data management unit DMU also performs the masking during partial write operations.

The instruction fetch unit IFU 1318 interfaces with the DMU 1321, the ACU 1319, the ALU 1317, and the CSU 1301, and is responsible for keeping the CPU supplied with instructions. The instruction fetch unit has the next instruction available in its registers before the completion of the present instruction. To provide this capability, the instruction fetch unit IFU 1318 contains a 12-byte instruction register (not shown) that normally contains more than one instruction. In addition, the IFU, under control of the CSU, requests information (instructions) from main memory before the instruction is actually needed, thus keeping its 12-byte instruction register constantly updated. Instructions are thus prefetched by means of normally unused memory cycles. The instruction fetch unit also decodes each instruction and informs the other units of the instruction's length and format.

The address control unit ACU 1319 communicates with the IFU, ALU, DMU, and the CSU via the CIA. The ACU 1319 is responsible for all address development in the CPU. All operations of the ACU, including transfers to, from, and within the unit, are directed by CSU micro-operation and logic in the unit. The normal cycling of the ACU depends on the types of addresses in the instruction rather than on the type of the instruction. Depending on the address types the ACU may perform different operations for each address in an instruction. The ACU also contains an associative memory 1319a that typically stores the base address of the 8 most recently used memory segments, along with their segment numbers. Each time a memory request is made, the segment number is checked against the associative memory contents to determine if the base address of the segment has already been developed and stored. If the base address is contained in the associative memory 1319a, this address is used in the absolute address development, and a considerable amount of time is saved. If the base address is not contained in the associative memory 1319a it is developed by accessing the main memory tables. However, after the base address of the segment is developed, it is stored in the associative memory, along with the segment number, for future reference.

Interfacing with the ACU, IFU, DMU, and the CSU is the arithmetic and logic unit ALU 1317. Its primary function is to perform the arithmetic operations and data manipulations required of the CPU. The operations of the arithmetic logic unit are completely dependent on micro-operation control signals from the control store unit CSU 1301.

Associated with the ALU 1317 and the CSU 1301 is the scratch pad memory unit LSU 1315, (sometimes referred to also as the local store unit). It is typically comprised of 256-location (32 bits per location) solid state memory and selection and read/write logic for that memory. The scratch pad memory 1315 is used to store CPU control information and maintainability information. In addition, the scratch pad memory 1315 contains working locations which are primarily used for temporary storage of operands and partial results during data manipulation. Also associated with the ALU 1317 is an auxiliary memory 1317a comprised typically of 64 flip-flops for storing miscellaneous states of the computer system.

The CPU also has a clocking unit 1320 and is essentially 2 clocking systems in 1: the first clocking system generates the timing for the control interface adapter CIA 1302 and the second clocking system generates the timing pulses for the operations of the functional unit within the central processing unit.

Referring now to FIG. 13c there is shown the format of the control store word 1325. The control store word is typically 84 bits wide and is divided into 6 main fields:

a. sequence type field 1326 (3 bits);

b. branching and/or micro-operations 1327 (23 bits);

c. constant generation and designation 1328 (14 bits);

d. data to bus 1329 (8 bits);

e. micro-operations 1330 (32 bits); and

f. checking 1331 (4 bits).

The 3-bit E field of the control store word 1325 is used as a sequence control field. There are typically 7 different sequence types and 1 reserved type for the instant computer system. Referring to block 1335 of FIG. 13b, when E field equals binary 0, 1, or 2, the branching field A, B, C, D and L of micro-instruction 1325 is utilized to generate the next address. The first 6 bits of KS register 1337 is utilized together with the B field, a C test results, the D test results and the L field to provide the next address of the next micro-instruction which is then placed in address register KS 1337. When the E field is set to binary 4 (see block 1335) the next address selected is taken from interrupt return register KA 1339. The address stored in the KA register is the one generated by the next address generation logic when the hardware interrupt occurs. When the E field is set to binary 5 a branch is used to initiate a subreturn from a micro-program subroutine. When used, the contents of the return register KR 1346 are used as the next control store address. The return register 1346 is loaded by issuing a control store command which will load present control store address in KS register 1337 plus 1, from incrementor 1338, into the KR register 1346. A one-level-nesting subroutine ability is provided via the KT return branch register 1347. Every time the KR register 1346 is loaded the old contents of the KR register is transferred to the KT register 1347 every time the micro-program return is called; the contents of the KT register will transfer to the KR register. Third level nesting subroutine ability is provided by the KU register 1340; and fourth level nesting subroutine ability is provided by the KV return branch register 1349. When the E field of the control store word is set to binary 6 the next control store word addressed is equal to the present address in KS register 1337 plus 1 in incrementor 1338. When the E field is set to binary 7 the CSU 1301 enters the diagnostic mode and the next address will be the present address plus 1.

In addition to the sequencing control of branching to the next control store address described above and shown in block 1335, there is hardware generated sequence control shown in block 1336 of FIG. 13b. (Note: Blocks 1335 and 1336 are in actuality hardware registers drawn so as to depict the different forms that the microinstruction words may take.) The hardware generated branches are overriding conditions (such as errors, initialize, control store scan, etc.) which suppress the E field and force a fixed address into the control store address register KS 1337. The branch is made by forcing an interrupt line high (not shown) for one clock period and storing the address which would have been generated under the control of the E field into the KA interrupt return register 1339. A hardware generated address will be placed into the control store address register. Certain hardware/firmware generated interrupts take priority when the interrupt-block flip-flop (not shown) which prevents additional interrupts in their class from being executed until the interrupting condition has been satisfied. A firmware micro-operation exists for controlling the resetting of the interrupt-block flip-flop for those sequences which are under firmware control. Those sequences under hardware control automatically generate a reset of the block-flop at the end of the sequence. The following conditions, listed by priority, exists in this category; (a) control store load; (b) control store scan; (c) hardware error; (d) software error. The remaining hardware conditions do not set the interrupt block-flop but do cause an immediate action to occur when generated. The following conditions listed by priority, exist in this category;

(a) initialize;

(b) soft-clear;

(c) enter maintenance panel;

(d) enter maintenance panel;

(e) hardware exit.

An initialize signal causes the CSU 1301 to branch to address binary 0, clear hardware resettable errors and execute a control store load operation followed by a control store scan sequence under hardware control. It will also perform system initialize. A soft-clear signal causes the CSU 1301 to branch to address binary 0, clear hardware resettable errors and reset the interrupt block-flop. An enter maintenance panel signal causes the CSU to branch to the address preset in the CSU address switches on the maintenance panel (not shown).

An enter maintenance channel signal causes the CSU to branch to an address generated via the maintenance channel (not shown). The address loaded is from maintenance bus QMB 1344, which is part of the maintenance channel, and is right-justified. A hardware exit signal causes the CSU to branch to binary address 2. This sequence is used as a maintenance facility. At the end of the sequence a return is initiated by issuing an E field branch with the E field set to binary 4.

A control store load signal causes the CSU to branch to address binary 0. It also turns off the CSU read-cycle flop (not shown), the system clock 1320, and places the CSU in the load state. In the load state the CSU can be loaded from the control store loader CSL 1303, the IOC 1305, the main memory 102, or the maintenance panel 1355. When loaded from the CSL an automatic scan is generated at the end of the load. When loaded from any other media a scan may be issued by either generating a micro-operation signal or setting the scan switch on the maintenance panel. A control store scan signal causes the CSU to branch to an address binary 0. A control store scan is under hardware control for the duration of the sequence. During the scan the system clock 1320 is off and therefore no commands or tests are executed. At the end of the scan sequence the hardware transfers the contents of the interrupt return register KA to the address register KS, the system clock is turned on and control is returned to the firmware.

A hardware error signal causes the CSU to branch to address binary 4. In the normal processing mode a hardware error detected in any CPU functional unit will activate a hardware error line (not shown). The control store sequence generated will test the system conditions to determine the action to be taken. In the diagnostic mode, error conditions which are hardware detectable are visible to microdiagnostics. The microdiagnostics control the action to be taken. A software error signal on the other hand causes the control store to branch to address binary 1. This address is the start of the software error reporting sequence which is under micro-program control.

Referring once again to FIG. 13c the E field 1326 is a 3 bit field for the branch code as previously described. The branching and/or micro-operation field 1327 is comprised of the A, B, C, D, and L fields (also shown on block 1335 of FIG. 13b) wherein the A field is the upper 6 bits of the next address, the B field is the middle 4 bits of next address of the mask field on 64-way branch, the C field is a 6 bit test field for 1 of 64 tests, the D field is another 6 bit test field for 1 of 64
tests, and the L field is the least significant bit. The K field 1328 is a 14 bit field of which 6 bits are for the constant field, 4 bits are for a constant or steering field, and 4 bits are a steering field for a constant. The data to bus field 1329
is comprised of the QA field having 4 bits for controlling information to the QA portion of the QMB bus 1344 and the QB field has 4 bits for controlling information to the QB portion of the QMB bus 1344. The F field 1330 is a 32 bit field which is coded to generate micro-operation subcommands. The P field 1331 is comprised of 4 bits reserved for checking.

In operation the micro-instruction words are stored in the control store array 1333. During a cycle of operation, the control store array is addressed by the contents of the KS address register 1337. This causes the contents of the location specified by the address to be read into the group of read latches 1357. Portions of the word contents of the read latches are distributed or transferred to storage registers within each of the functional units in the CPU. Each functional unit includes decoding logic circuits for generating the requisite subcommands specified by the control store word under control of the system clock source. In general decoding is performed within each functional unit in the CPU rather than being performed centrally in order to minimize the decoding time and to reduce the number of cables which would be normally required for transmitting command signals if decoding were performed centrally. Additionally, the decoding is done within each unit to avoid timing problems arising from differences in cable delays. Further, by decoding subcommands with each unit, those signals which are representative of certain conditions existing within the functional unit are required for the generation of certain subcommand signals do not have to be returned to the CIA unit 1302. A typical decoder unit 1359 is shown in FIG. 13b as receiving various fields from micro-instruction words and generating micro-operation signals a, b, c, d, . . . q, r. A typical micro-operation decoder 1359 receives commands from a micro-instruction word. The field from the micro-instruction word is decoded and sets one of a plurality of lines s, t, u, . . . y, z high. A matrix is formed by having predetermined control line impedance coupled to the s-z lines at points .alpha., .beta., .gamma. . . . .gamma., .omega.. Typically then when the field from a micro-instruction is decoded one of the lines s-z goes high. Since the black dots shown in the matrix by Greek letters .alpha. through .omega. represent impedance coupling between the two sets of lines, any electrical signal propagating along any horizontal wire will be coupled through to propagate along the vert