JPS6112291B2 - - Google Patents

Description

[Detailed Description of the Invention] List of Items Γ Computer Semaphore Device Page 13 Γ Description of Embodiment Overview Page 27 Processor Subsystem Page 27 A Central Processing Unit Page 28 B Input/Output Control Unit Page 31 C Peripherals Subsystem page 31 Basic mechanical structure page 33 A Data format page 33 B Byte page 34 C Data display page 34 D Byte address page 35 E Visible register page 35 F General purpose register page 36 G Base register page 36 H Scientific register Page 37 I Miscellaneous Registers Page 37 J Instruction Format Page 39 System Mechanisms Page 40 A Job Steps and Tasks Page 40 B Processes Page 40 C Process Control Blocks and System Base Page 41 D Memory Segmentation Page 44 Process Management and Synchronization Synchronization page 46 A Process status page 47 B Process dispatching page 50 C Process synchronization Page 53 Structure of Γ process control block Page 57 Structure of Γ system base Page 70 Example of use of Γ system base and process control block Page 82 Γ control Unit 85 pages Γ Dispatch armwear for process control
Page 111 Main body of Γ semaphore Page 133 General explanation of ΓP and V directives Page 195 Evolution of semaphore for both ΓP and V directives
Page 206 ΓP command (command or instruction)
Page 223 A P command on a non-message semaphore Page 225 B P command on a semaphore with a message
Page 235 C Putting a running process into a standby state
Page 238 D Message forwarding without using queue
Page 269 E P instruction of semaphore with message when SCT is greater than zero Page 285 V instruction on Γ semaphore Page 293 A V of semaphore with positive SCT field
Instructions page 296 B V instruction on semaphore with message when free message link is unavailable page 311 C V instruction on semaphore with negative SCT field page 314 Γ semaphore initialization instruction page 333 Γ Control central processing unit General Description of Events External to Processes Page 349 Γ System Event Poller Mechanism Page 355 Γ I/O Event Handler Page 360 Simulated V Operations on Semaphore with Γ Positive SCT Field Page 370 Γ Free Messages Simulated V operation on semaphore when link is unavailable
Page 379 Removal of messages for Q/LC/FLS semaphores when Γ-free message links are available Page 387 Q/Removal of messages for processes that require Γ messages
Removal of messages in LC/FLS Page 399 Computer sema phores
TECHNICAL FIELD This invention relates generally to computer systems, and more particularly to data processing apparatus for computer processes in multiple programming/multiprocessing conditions.

This fourth generation system is considered to be able to satisfy the following conditions.

1 "This system is classified as a communication/control system and can be applied to a wide variety of processor applications."

2 "This system is primarily controlled by data and not by programs as in previous models; that is, the system control functions are ensured primarily by input rather than by stored instructions." ”.

3. "Hardware dominates communication and control procedures; use of system control programs can be significantly reduced."

4. "Most processing is performed in real time. Operations are performed on inputs at a rate that produces an output within the required response time."

5 “The system can be easily expanded.
The hardware and software are designed in a functional and modular manner.

Information processing in first generation hardware-software computer systems was relatively linear, and the job or program was considered to be the basic processing unit. For each job or transaction initiated by each user, typically one program ran with little or no interruption until the job or transaction was completed. FORTRAN
Many linear jobs, such as compiling and running high-level language programs, can and have been executed as a single process.
More difficult jobs required multitasking operations, and other processes were spawned as execution progressed. (Here, a process is a concept that means to perform some work; it is defined as the execution of a sequence of instructions as directed by a processor; it is a description of work, and is used by one or more processes. It should not be confused with the concept of a program that can execute a program (we can also speak of a process or processor executing a program (see the glossary section).

The concept of a process as a basic processing unit is
It has evolved to meet the needs of multi-programming/multi-processing environments of generations of computers. In an environment such as the one described above where many users request services at the same time, it is naturally recalled that multiple processes compete for resources within the computer system. Each process is a program executed by a computer that performs operations on data to perform a user's job or some stage of that job (i.e., a program that processes instructions and other data associated with the instructions). a set with a certain order)
It is composed of Given that many such processes may be requesting services from the system at the same time, the task of communicating with and between such processes, controlling such processes, and allocating resources. The task of allocating this becomes extremely complex when considering the requirements of fourth-generation systems.

No. 60 of 1969 on Operating Systems
AJ at the ACM 2nd Symposium on page 67
A paper titled "Process Control and Communication" published by Bernstein. There is.

According to this system, one system can be configured with a maximum of four parts called logical segments. These segments can be located in physically separate locations when the process is stored. Relocation and protection of these segments is accomplished by four registers.

Generally, processes are controlled by an operating system that executes primitives (i.e., pseudo-instructions) issued by the processes, using mechanisms by which the processes communicate with each other. Communication primarily consists of splitting (sharing) events in the same AIT (Arithmetic Item Table), which contains a unique entry for each open file at each point in time. With such a structure, a process can notify (by issuing a NOTIFY primitive) when its event occurs.
You can request reconciliation. As a result, the operating system creates an event queue or an entry for an event queue associated with the event or events indicating the different processes that have issued the request and are waiting for notification. At this point, the process that issued the request can continue running, or it can issue a BLOCK primitive to temporarily stop it. This event is
Occurs when some other process issues the CAUSE primitive, and can be cataloged and processed in the direction structure using the same primitive. Information is then transferred from one process to another, or several processes cooperate to perform a given task. Other primitives in the operating system create and provide primitives, or destroy them.

Such process communication and control techniques do not provide an orderly dynamic history of the program being executed, but rather introduce certain concepts of process software multiplexing and event management.

In a multi-programming/multi-processing environment, it is essential that cooperation between two or more sequential processes be achieved efficiently and quickly. Although many solutions to this problem have been proposed in the past, the process communication and control techniques required for fourth generation computers have not been fully implemented to date. However, the germination of the concepts needed for the fourth generation of computers, albeit partially, began in 1968 at the Academic
NATO, edited by F. Genuys, Paris, published by Press.
It is disclosed in EWDijkstra's paper "Cooperative Sequential Processes from Programming Languages" at the Advanced Study Intitute. In this paper
Dijkstra postulates the basic concept of signals for use in P and V instructions that operate on signals and in process synchronization. Unfortunately, Dijkstra only obtains process communication and process synchronization through the use of software, which not only results in longer system uptime, but also increases the efficiency and efficiency required for this type of system. This also reduces overall overhead. More importantly, by simply setting out the basic assumptions in process synchronization, Dijkstra does not provide the concepts needed to exploit fourth generation computers in any meaningful way. I can't say that. For example, in Dijkstra's paper there is no preparation or explanation of the transmission of messages from one process to another. Fourth generation computers need to not only increase the operating efficiency of the system, but also be flexible enough to handle the many situations that arise in transferring information from one process to another. A system that automatically incorporates process communication and control so that

The concept of P and V instructions has already been explained in the aforementioned article by Edsger W. Dijkstra. However, these concepts are presented only under general conditions, and the fourth
It does not provide the necessary system configuration for each generation of computers. Furthermore, Dijkstra simply P and V
It merely provides the basis for the software to interpret and use the instructions. Therefore, a storage facility is required for rapid process access and systematic relocation of data processors.

It is an object of the present invention to provide a new data processing apparatus for process synchronization in a multiprogramming/multiprocessing environment.

Another object of the present invention is to provide a data processing apparatus for process synchronization through guided instructions to reduce operating overhead.

Another object of the invention is to provide a data processing apparatus for process synchronization of events external to a central processing subsystem, in order to overcome the drawbacks of the prior art.

Another object of the present invention is to provide a data processing apparatus for incorporating I/O interrupts into the operation of a central processor subsystem to save circuitry and time.

Another object of the present invention is to initialize semaphores that reduce execution time and the amount of memory space required. A semaphore is defined as a data structure used to control synchronization and communication between processes.

According to one embodiment of the invention and one mode of operation of the invention, the above object is achieved by providing a data processing system with instructions that provide data for other processes. Ru. These instructions convey information by essentially two operations: a P operation that requests information (data), and a V operation that delivers information (data).

The process that executes the P instruction is
Request data to continue the operation. The P instruction addresses one semaphore data structure and decrements its count field by the number one. If the resulting number in the semaphore account field is non-negative, then the P
The process executing the instructions is
Continue executing the next instruction in the procedure segment. When the above number becomes negative, the process executing the P instruction is stopped and placed in a waiting state on the semaphore addressed by the P instruction.
Until the next notification is given (i.e., the V operation on the same semaphore as above), dynamic progress of the process executing the P instruction is logically not allowed, for which the processor is not allowed to proceed at all. Not assigned.

A process executing a V instruction transmits data. This V instruction is 1
Addresses one semaphore and increases the number in the semaphore account field by one. If the resulting value in the semaphore count field is positive, the V instruction ends at the same time as the data transfer. However, if the above value of the semaphore account field is not positive,
The V instruction also causes one of the processes in the standby state and coupled to the same accessed semaphore to transition to the ready state. That is, the dynamic progress of a process that has just been switched out of a standby state is re-enabled logically and at the appropriate time. That is, one processor is assigned to this process and enters a run state.

Variants of the P and V instructions include individual instructions for both semaphore structures with messages and semaphore structures without messages, each of which also has test instructions. have The test instruction is P
or V instructions cannot be executed, external events,
That is, outstanding I/O interrupts and certain outstanding exclusion conditions are handled. This is a system event poller that is normally entered by the central processor at the end of each instruction.
Event Poller). If the central processor is not in critical transient mode,
All I/O interrupts and some exclusion status are polled. For each external event, the System Event Poller, on behalf of the I/C subsystem or Central Exception-Mechanism, performs a simulated V operation for communication of the appropriate information. Polling then continues until all external events have been processed. All I/O
Once interrupts and exclusion conditions have been processed, a dispatcher is entered to determine the next process to be controlled by the central processor.

The semaphore initialization instruction locates a semaphore through address development of its address syllable. If the semaphore is a non-messaging semaphore, the semaphore account field receives the number N stored in the executing process's general-purpose register. If the semaphore is a message semaphore, the semaphore account field returns to the zero state. For a message semaphore, if the previous count field is greater than 0, all message links in the Q/M/S are free (free or free) message semaphore.
Returned to FLS and queued on Q/ML/FLS. If the semaphore's previous count field is zero, there is no need to migrate the message link and the instruction ends. If the semaphore's previous count field is less than zero, the instruction is not executed. In multiprograms, single processor environments, processes, and events that operate or occur asynchronously must be synchronized with each other to enable them to properly cooperate with each other.
A process is defined as the directed execution of an instruction associated with a job or user-defined word, while an event is defined as something observed by a process that affects some other process. Examples of events are the completion of a synchronization operation,
The emergence of messages, the efficient use of resources, and the emergence of processes at special stages of execution. The present invention is directed to data processing management, sometimes referred to as "housekeeping", for queuing different types of events in memory, as well as monitoring and accumulating representations of events. Also in memory, data elements called semaphores count the number of different event types, provide direct storage of events in various queues in memory, and store events in queues while preventing excessive reads of memory. Record the memory location of the display. Queues store representations of events rather than the events themselves to minimize the amount of data handled. FIG. 16a, described below, shows the structure of a semaphore indicating the availability of external disk memory containing information required by a process, such as the occurrence of a no-message event. A semaphore has a first field (SMC) that indicates the maximum number of events that can be provided in the area, a second field (SCT) that indicates the actual number of events, and a semaphore that allows processes to wait for resources, such as peripherals. depending on the environment if it is kept in a waiting state.
FIFO (first in, first out) or LIFO (last in, first out)
It includes a third field (STAG) to indicate the priority of the event in the manner of: Special instructions (P) and (V) determine the state of the semaphore. The P instruction increments the number in the second field of the semaphore if the event being responded to is the availability of a new resource, and decrements the number in the second field if a new process is requesting the resource. . Whenever a process requests a resource that is not available, such as a peripheral device, the process's display is subsequently displayed in a third state waiting to be read.
Memorized by Kyuu. If all the resources required by the process are available, the process's representation is stored in the third queue in a ready state. Synchronization is thereby provided between processes reading into the third queue while waiting for subsequent reading.

If all the resources required by the process are available, the process's representation is stored in the third queue in a ready state. Thereby, synchronization is provided between processes to determine the availability of various resources, all monitored through so-called events signaled by P and V operations or instructions.

The novelty of the invention is particularly pointed out in the claims. DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, the configuration and operating principles of the present invention, as well as other objects and features, will be explained in detail with reference to the drawings.

DESCRIPTION OF THE EMBODIMENTS Overview The present invention is generally employed in a hardware system environment, hereinafter referred to as a hardware/firmware/software operating system.

Referring to FIG. 1, a processor subsystem 101, a storage subsystem 102, and one or more (up to 32) peripheral subsystems 1
03 is drawn. The processor subsystem includes a central processing unit (CPU) 104 and up to 4
includes one input/output controller (IOC) 105. Each peripheral subsystem consists of a peripheral control unit (PCU) 10
6, a large number of device adapters (DA) 107, and a maximum of 256 peripheral I/O devices 108. The storage subsystems 102 each include 32 to 32 storage subsystems 102.
It consists of one to four semiconductor memory modules of 512 kilobytes each.

Processor subsystem In the processor subsystem 101,
CPU 104 performs basic processing operations for the system and has the ability to interface with memory 102. IOC 105 controls all information exchange between storage subsystem 102 and peripheral devices 106.

A central processing unit CPU is the main memory synchronizer 109,
It includes various elements including a buffer storage device 110, a computing device 111, and other optional emulation equipment 112. Main memory synchronizer 109 resolves conflicts for main memory usage between computing device 111 , buffer storage 110 , and IOC 105 . These conflicts are resolved by a priority scheme. That is, the IOC has the highest priority, followed by memory writes (from computing devices), and then memory reads (to buffer storage). The main CPU also includes an address control unit ACU 131 that controls addressing of the main memory and an associative memory AS 132 that is used to store the most recently used address of the main memory. Buffer storage 110 is a small, high-speed buffer memory that reclaims specific areas of main memory and interfaces with computing devices to reduce average access time. During each memory read, both buffer storage and main memory are accessed. If the information to be fetched is already in the buffer storage, the main memory read is completed and the information is fetched from the buffer storage. Otherwise, main memory 102 is read. Each time main memory is read, CPU 104 fetches 32 bytes containing the desired information. This information is maintained in buffer storage for subsequent memory reference. Because buffer storage is transparent to software, the program controlling the computer at any given time can tell whether the information it is processing was fetched from buffer storage or from main memory. cannot be determined.

Computing device 111 performs all data processing and address generation within the CPU. A typical control memory 130 in a computing device (see "Microprogramming: Principles and Practice" by Samir S. Hueson, Prentice Hall, Ine.) initializes the system and
104 and IOC 105 and decodes an instruction set (not shown). Optionally, the control storage may provide scientific instructions, test routines, emulation packages, or special purpose features such as increasing the capabilities of the processor subsystem.

Optionally, the CPU also provides emulation of systems other than instant systems. Emulator 112 is firmware,
It can be a software or even, in some instances, a hardware component.

B. I/O Controller The IOC 105 portion of the processor subsystem provides a data bus between any peripheral subsystem 103 and the storage subsystem 102. This data bus allows the initiation of peripheral commands and controls the resulting data transfer. One IOC typically handles up to 32 channel controllers (not shown).

C Peripheral subsystem In the peripheral subsystem shown in Figure 1, PCU
106 is a stand-alone microprogramming processor that relieves the load on the CPU by controlling I/O device 108 during I/O operations. The PCU performs this operation by executing instructions contained in the channel program. This program causes arithmetic, logic, transfer, shift, and branch operations to be performed within the PCU. Depending on the type of device being controlled
There are several types of PCUs: unit record, mass (disk) storage, magnetic tape, communications, etc.

A device adapter DA107 is interposed between each PCU and the device controlled thereby. Each adapter includes the given firmware and logic necessary to communicate with each particular device. Depending on each type, DA 107 controls one or several devices.

The main functions performed by peripheral subsystem 103 are as follows.

1 Translation of CPU instructions into a sequence of instructions accepted by peripheral devices.

2. Packing and unpacking of data in the form required by the CPU or appropriate peripherals.

3 Continuous supply of information to the CPU about the status of subsystems and equipment under its control.

4. Independent initiation and processing of error and recovery procedures.

5. To enable online diagnosis of one device without disrupting the device sharing capabilities of related peripheral processors.

The PCU resolves conflicts for main memory between devices attached to it. However, conflicts between PCUs are resolved by the IOC.

Basic Mechanical Structures There are generally three types of basic data structures used in this hardware: data formats, software visible registers, and instruction formats.

A. Data Format Information is transferred between memory and the CPU as multiples of eight parallel bits. Each 8-bit unit of information is called a byte. Parity or error correction data is also transferred with these data, but cannot be influenced by software. Accordingly, as used herein, the term data does not include any associated validity or error correction data.

B Byte The bits in one byte are numbered from 0 to 7 from left to right. Each byte is
Or processed in groups. 2 bytes constitute a half word, 4 bytes constitute 1 word, 8 bytes constitute 2 words, and 16 bytes constitute 4 words. The above is the basic format for all data including instructions.

C Data display All data is in binary format, but
It can also be interpreted as either decimal, decimal, or alphanumeric format. DataBits interprets the four groups as binary coded decimal data. Also, groups of 8 are interpreted as alphanumeric characters, or groups of 16 to 64 are interpreted as binary digits. These binary digits are signed numbers in binary notation, fixed point numbers,
or interpreted as a floating point number. It is also possible to treat several consecutive bits of up to two words as a string. Alphanumeric character sets are represented in EBCDIC. ASCII code can also be used as an alternative code.

D Byte Address Byte locations in main memory are numbered consecutively starting from zero, and each number is the address of the byte. A group of consecutive bytes is said to be half-word, one-word, two-word, or four-word aligned if the addresses of the left-hand bytes are each a multiple of 2, 4, 8, or 16. When half words, one word, two words, or four words are aligned in this way,
The information unit can be fetched from that address. The location of data in main memory is specified by a data descriptor that is accessed indirectly during address development.

E. Visible Registers There are 33 user visible registers within the CPU 104 of FIG. 1 whose stored information collectively sets the state of the CPU. There are four types of these registers (see Figure 2): 1 General purpose register 2 Base register 3 Scientific register (optional) 4 Miscellaneous register F General purpose register General purpose register (GR) 201 is a fixed-point register. Used for handling numbers and bitstrings. Generally, there are 16 32-bit general-purpose registers in a CPU (GR0 to GR15). General-purpose registers GR8 to GR15 can also be used as index registers. In this application, when used as an index register, they are expressed as X0 to X7. Indexing is performed using 32-bit two's complement integers contained in registers.

G Base Register The base register (BR) is the instruction counter IC and stack register 202~
It has the same format as 203. Base registers are used to define portions of memory in address calculations. Typically, eight 32-bit registers (BR0-BR7) are used.

H Scientific Register The Scientific Register (SR) is an optional device for performing calculations on floating point numbers.
Generally, four 8-byte scientific registers are used (SR0-SR3). The scientific register has the format 204-205 of FIG.

I Miscellaneous registers There are five types of other registers: ● Instruction counter (format 2)
02 to 203); ●Status register (having format 207); ●Stack register (called T register);
202-203 - Boundary address register (with format 206); - Hardware control mask register (with format 208).

The instruction counter (IC) contains the address of the instruction being executed
It is a 32-bit register. Status register (STR) 207 is an 8-bit register that records the status of the procedure currently being executed, such as whether the most recent operation caused an overflow. T
A stack register, also known as a register, is a 32-bit register that stores a pointer to the top of the pushdown stack associated with the currently active procedure. The stack described below provides a workspace, a mechanism for saving local variables, saving procedure entries, and return information.
Boundary address register (BAR) 206 is a 28-bit register that specifies the lowest absolute main memory address accessible by software.
This register is loaded during system initialization and can only be read by software. Hardware control mask register 208 is an 8-bit register that records machine status information.

J Instruction Format There are approximately 200 instructions, each of which has one of four lengths, or all of which are an even number of bytes long. These instructions are stored in consecutive memory locations. The address of the leftmost byte is a multiple of 2, and is the address of the instruction.

The eight most significant bits of an instruction (sometimes bits 8-11, or 12)
.about.15) represents an operation code, while the remaining bits represent one or more operational numbers. The operand may be a register index, a movement index, an address syllable (logical address), a literal value, an immediate literal value, etc. The type and number of operands are determined by the instruction format.

System Mechanisms A. Job Steps and Tasks The work to be performed by a computer system is controlled externally by a series of job steps using a job control language.

A job step is a unit of work to which hardware resources are allocated. Generally, a job step consists of several tasks. A task is the smallest unit of work set by the user, and consists of a flow of instructions to be executed in parallel.

B. Processes The user-visible concepts of tasks and job steps are represented in hardware by processes and process groups, respectively.
A process is defined as an ordered sequence of instructions that can be executed asynchronously by a CPU (i.e., several processes can be active and share resources). However, at any given moment, only one process is actually running). A process group is a collection of processes required to execute one job step.

C. Process Control Blocks and System Bases Because a process can relinquish control of the CPU at any point during its execution, a process can utilize storage areas in main memory to save the state of the CPU. can. This state information is used to precondition the CPU before the process regains control of the CPU.

The recording area assigned to a process is called a process control block (PCB) 400 (FIG. 4). The data contained in the PCB includes storage information of all related registers of addresses of memory areas (address spaces) allocated to the process, the state of the process, etc. Therefore,
The PCB is used as a temporary storage area for the information necessary to start or restart a process without any loss of information. Each PCB
is visible to the hardware/firmware and can be addressed by the operating system through a set of hardware/firmware tables created during system initialization and modified during system operation. Figure 5).

The absolute main memory area is called the system base (Figures 5 and 6). This area is created by the firmware and can be accessed through a base address register (BAR) 501 that is readable but not writable. System base 502 contains several system attributes, including the process name (JP) of the process that is currently running. Another system-based characteristic is a pointer 505 to a hardware-configured structure known as a J-table 503. This table contains an entry for each job step that is currently in the system. Each entry in J-table 503 specifies an attached P-table 504, which is also a hardware configuration data structure. This table defines a process group and contains an entry for each process in that process group. 50 each P table entry
7 specifies PCB400.

Referring to FIG. 5, computing device 111 (first
J table pointer 505 indexed by J number via calculation unit 506 in FIG.
gives an entry to J table entry 503. This entry includes a P table pointer that provides access to P table entry 504 when indexed by P number via computing device 506 . P table entries are for processes currently running.
Contains a pointer 507 to PCB 400. Therefore,
The operating system can access the active PCB using the information stored in BAR 501 and other PCBs given their associated logical names (JPs).

D. Memory Segmentation In a multi-process environment such as the one described in this application, there are many processes in memory at a given time. These processes have different sizes and memory requirements from each other, creating memory allocation problems. To this end, an operating system (not shown) is used in conjunction with hardware to dynamically allocate memory space to solve this problem. Due to the random nature of memory conditions, memory is allocated in variable-sized segments, allowing memory allocation to be reconfigured during process runtime. Therefore, a process may be assigned several non-contiguous memory segments. This kind of memory allocation method is called segmentation.

Segmentation poses a new problem in that memory addresses must be changed when relocating part or all of a process.
In order to solve this problem, the system of the present application:
It provides a technique for making the addresses used by processes logical addresses rather than absolute main memory addresses. These logical addresses are used to create absolute addresses.

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

Segmentation defines over 200 million bytes of addresses available to processes. The above value is greater than the capacity of the main memory, and therefore a secondary storage device (magnetic disk or drum) is used together with the main memory. This operating system creates the illusion that the system has several orders of magnitude more main memory than is actually available. This concept is called virtual memory.

Process Management and Synchronization The system of the present invention provides multi-processing operations controlled by an operating system using a combination of software, hardware and firmware. Software creates and destroys processes within the system, while hardware and firmware multiplex these processes on the CPU. Furthermore, the combination of software, hardware and firmware allows for synchronization between processes.

Processes are typically, but not always, started and stopped at the beginning and end of I/O operations, during associated job processing, and during time spent for other purposes deemed necessary by the operating system. be done. Therefore, a communication system is required to efficiently start and stop related processes and to communicate information between processes. The hardware of the present invention provides internal messages called semaphores to provide communication links between processes.

A Process State A process can be in one of the following states at any time: Running, Ready, Waiting, or Pending. The hardware recognizes these four process states and
Execute various firmware procedures, perform process dispatching, state changes,
Maintain data structures based on process state. The PCB has a status field that sets the current state of its associated process.

A process is in the run state when it is under the control of the CPU. In this state, the CPU is supplied with an address space (segment table) and a starting address. and,
The CPU executes instructions in the procedure segment of the process. PCB process name J for the process currently running.
P (logical address) is held in the running process word (BAR+56) in the system base (Figure 6). (Note: The system base in Figure 5 is the same as the system base in Figure 6, but the details have been omitted).

The ready state is the same as the running state, except that the process is not known to the CPU and therefore is not under control by the CPU. When a process is in the ready state, it competes with other ready processes and running processes for CPU.

A process becomes idle when it cannot persist until a certain event occurs, such as a message via a semaphore. Waiting processes do not compete for CPU, but they do compete with other waiting processes for necessary events.

A suspended process is a process that is stopped by the software for a period of time and can be resumed at a later time. Decisions to stop and restart the process are not included in the process.
Therefore, the pending process is not active and therefore cannot be notified of the occurrence of events and cannot use the CPU.

A process is suspended under the following conditions: (1) by execution of a Terminate instruction (as a result of having completed all its functions);

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

(3) By the occurrence of an excluded condition such that control is transferred to the operating system.

B. Process Dispatching A process can transition from one state to another when in a run state, either arbitrarily by the action of the process or forced by the action of another process. CPU firmware, called a dispatcher, controls the process's transactions between states. The dispatcher uses a set of queues (described below) to handle processes that are ready or waiting. The suspension process is controlled by software.

Referring to Figures 6, 8 and 9, a ready or waiting process is represented by a special queue entry called a PCB and process link. FIG. 9 is an exploded view of the contents of G0 segment 802, showing process links 803a-803b and 803c-803 of active processes.
g, and free process links 805a to 80
Contains 5c. Each process link specifies the process name (JP), the process's priority, and a pointer to the next process in its queue. The queue includes a standby queue 803a,
b, standby queue e~G, ready queue 803c~
There are various types such as d.

A hardware device similar to the J-table, known as the G-table (FIGS. 6 and 8), is used in all general-purpose (system-wide) segments 80.
2 to 802n. The first element G0 of G table 801 specifies the segment 802 that contains the dispatch queue. The G table pointer to G table 801 is located in the system base of FIG. Referring to FIGS. 8 and 9, there is also an entry in the system base called an internal process queue word (IPQW) that identifies the head 803 of the ready queues 803c-803s of the G0 segment.

Therefore, the dispatcher is ready
All ready processes can be examined one by one by examining 3c to 803d.
Given the state of the currently running process, the dispatcher removes the process link at the head of the ready queue and accesses the PCB using the JP name.

Since one or more processes may have the same event, there is a queue of waiting processes 803a-803b for each event. The standby process also has a process link 804 in the G0 segment.
(Fig. 8) exists in the form of a string. A pointer to the head of the waiting queue is present in signal 903 (described below). There are many events that one process waits for. for that,
There are several waiting queues, each with an associated semaphore 903,904.

The number of ready processes also changes dynamically. Therefore, the number of process links required for ready and waiting queues also changes. This fact creates memory management problems for dispatchers. This problem is solved by another queue called free process link queues 805a-c.

C. Process Synchronization Process synchronization is necessary to coordinate the activities of two processes working on the same task. This synchronization is accomplished using semaphores 903-904, which consist of data structures within the address space of the communication process. Semaphores are used to signal event occurrences and handle message queues. An event is something observed by one process that may be related to other processes. The event may be the completion of an asynchronous operation or the availability of a resource.

A process uses a semaphore to communicate the occurrence of an event.
Use operations. One operation is a semaphore or semaphore.
one picks up the signal from the semaphore. (Send operations are often referred to as V operations, and receive operations as P operations.) A send operation allows a process to send ready data or signals. The semaphore stores another process signal until it is ready to be picked up. In this way, the sending process is free to proceed as the data is being sent. The receive operation examines the predetermined semaphore and picks up the signal.
Then, if the signal is present, the receiving process continues execution. If there is no signal on the semaphore, the receiving process enters a waiting state. Then,
The semaphore acts as a pointer to the head of a waiting queue.

Messages are also sent from process to process. Messages have the same presence or absence characteristics as signals plus additional information. Some of the information is provided by the hardware, and some of the information is provided by the broker of the process sending the message. The message bears the process name of the sending process. Therefore, 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 a process. Memory management issues arise here, since memory space requirements increase and decrease with signal semaphores. Again, the problem is solved by free message links. These links exist at known locations in the segment where they can be easily located when message links need to be fed or absorbed.

Since the semaphore and the queues created on it are shared by different processes, the structure of the semaphore is globally protected. This is accomplished through hardware and software conventions that restrict access to the segment containing the semaphore. Therefore, the semaphore must be inside the semaphore descriptor, part of which is G
May be a segment (if system communication is required). However, all G segments (except G0) are semaphore descriptor segments.

Each semaphore descriptor contains a pointer to a semaphore. Since the semaphore address is created by the semaphore descriptor, the semaphore is also protected by this. Semaphores can be logically addressed using segment numbers and relative positions within the segment, or directly using G,D numbers.

Process Control Block Structure Figure 4 shows the format of the process control block (PCB). The process control block 400
A storage area in main memory that can be used to save the state of the CPU. PCB
Addressing is performed as described with reference to FIG. PCB pointer 507 (FIG. 5) specifies byte 0 of the process control block PCB of FIG. It should be noted here that in the downward progression the memory location increases by 4 bytes, but byte location 0
This means that in the upward direction from , there is an increase of 8 bytes. Memory locations downward from byte 0 are considered positive, and memory locations upward from byte 0 are considered negative. The upper positions are optional and may or may not be included in the process control block, and positions 148-176 are also optional. Part-time job 0~
16 (however, 16 is not included), four process main words PMW0 to PMW3 are stored, and each of these process main words PMW
is 4 bytes long. Process main word 0 occupies bytes 0-3 and consists of four parts: capability byte, priority byte, status byte and decall extension byte.
DEXT. In Figures 10a-10d, the process main word PMW0 is shown in detail, and in Figure 10b
shows the capability byte 1001 in more detail. Referring to Figure 10b, the first bit 10
05 is an accounting mode bit indicating whether a time accounting function is being executed for the process. If accounting mode bit 1005 is set to a binary 0, no time accounting functions are being performed for the process, and when accounting mode bit 1005 is set to a binary 1, time accounting is not performed. Function is running. When scientific mode bit 1006 is set to zero, no scientific register saving is being performed and byte 148 in FIG.
The science register saving area at ~176 is
Indicates that the process control block is not present on the PCB. science mode bit 1006
When is set to a binary 1, the scientific option feature is present and is being used in the process, and the scientific register saving area is used to save storage information in the scientific register as needed. It shows that

Details of the priority byte are shown in Figure 10c. Referring to Figure 10c, priority byte 1002
The first four bits of are used to set the priority level associated with a given process control block PCB. Each process is assigned one of 16 priority levels that are used to rank competing processes. The priorities go down from 0 to 15, and for a given priority level a FIF0 (first in, first out) rule is applied. In Figure 10d the status byte 1003 is depicted in detail. The status byte is used to obtain information about the process associated with the process control block PCB. When a process is suspended, the pending field S1011 is set to a binary one. Substate field SS
1012 is a 2-bit field that sets the substate of the process; (a) binary 00;
When set to , the process is not active; (b) When set to binary 01, the process is waiting in the queue of ready processes (Q/PR/RDY); (c )
When set to binary 10, the process is on the semaphore, waiting in the semaphore's queue (Q/PR/S); (d) When set to binary 11, the process is waiting on the semaphore in the semaphore queue (Q/PR/S); is being executed by. Bits 1015 and 10
16 is set to 0. process main word
The fourth byte of PMW0 contains the decall extension number and is used when the system is in emulation mode.

Process main word PMW1 is stored in bytes 4-7 of the process control block PCB. Details of PMW1 are shown in Figure 10e. Status byte 1016 is the first byte of PMW1 and stores information stored in the status register. The second and fourth bytes of process main word 1 are the MBZ field 101 which must be zero for normal operation.
7 and 1019.

Process main word PMW2 occupies bytes 8-11 of the process control block, which is shown in detail in Figure 10f. Figure 1
Referring to 0f, fields bits 4 to 31 are local to each SEG and SRA1 of the semaphore.
021, to which the PCB is linked when the process is in the standby or pending state. Exclusion class and type field 1023 results in process exclusion and contains bits 0 to 1023.
If field 15 is (NFS) 1022, store class and type. Process main word PMW3 is from byte 12 in PCB400.
Occupies 15 and specifies the Decor extension table.
Referring to FIG. 10g, which details PMW3, the DETSZ field 1024 sets the number of entries in the table; if this field is zero, no decall extensions are allowed for the process. DETA field 1025 is
This is the absolute address of the Decor extension table in 16-byte units, and has meaning only when DETSZ is not 0. The Decor extension table consists of DETSZ entries. Each entry is 1
It has become the size of a part-time job. DEXT of table
The second entry sets the ability of the process to operate in decall extension mode DEXT. 0
and DEXT values other than 1 are inappropriate. (See DEXT number 1004 in Figure 10a).

Bytes 16-23 of PCB 400 each contain two address space words ASW0 and ASW1, each ASW containing a pointer to a segment table word array. ASW0 and ASW1 are
Each has the same format as shown in Figure 10h. The size of the segment table word array is determined by the number of segment tables in one array, and generally ASW0 has 7 and ASW1 has 7.
There are 8. STWSZ field 1026 is
Indicates the size of the array of segment table words. Segment table word array field
STWA 1027 includes the absolute address STWA of the array in units of 16 bytes. That is, the absolute address of the array is STWA 16 in bytes.
It's double.

Bytes 24-27 of the PCB contain the exclusion word EXW, which is shown in Figure 10i. The exclusion word contains a pointer (SEG, SRA) 1029 to an exclusion class table that determines the action to be taken after process exclusion according to the class stored in the process main word PMW2. (See Figure 10f). MBZ field 1028 of excluded word EXW is 0
Must.

Stack word in bytes 28-31 of the PCB
SKW stores the value of the top of the T register of the process's stack when the process is not running. Referring to FIG. 10j, bits 0 and 1 set TAG field 1030.
TAG indicates the type of descriptor by its storage information, which must be zero for SKW. Bits 2 and 3 of the SKW word are
Includes a RING field 1031 containing the ring number associated with the stack's segmented address for protection, which must be zero in this case. Bits 4 to 31 include the segment number SEG and the segment relative address SRA1032, which is a field that specifies the segment described in the segment table and segment relative address within the segment. The stack word SKW is updated each time a process leaves the run state. This restores the stored information in the TO register each time the process goes into a run state. In this last case, TAG1
030 and RING 1031 are tested for zero, and if not zero will result in an illegal PCB exclusion.

Bytes 32-35 of PCB 400 contain the instruction counter contest word ICW, sometimes referred to as ICC. Referring to FIG. 10K, the TAG field 1033 must contain binary 00 (i.e., non-zero values are illegal in the instruction counter) in the instruction counter word.
ICW is shown in detail. bits 2 and 3
The RING field 1034, which occupies , sets the current ring number of the process to use in access right to main memory. Bits 4-31 are the segment number and segment relative address (SEG,
RRA) 1035.

The MBZ field in bytes 36-39 must be zero. The MBZ word allows the PCB to be tested every time it is accessed from the name JP. If this is not zero, it will result in an unwarranted PCB exclusion.

Stack base words SBW0-2 occupy bytes 40-51 of the process control block. These words have the same format, which is shown in detail in Figure 10l. These words are used in stack operations, but whenever they are used, TAG
Field 1036 and RING field 10
37 must be zero, otherwise it will result in an unwarranted PCB exclusion. Bits 4-31 contain the segmented address (SEG, SRA) 1038 of the first byte of the stack segment for rings zero, one and two.

Bytes 52-83 of PCB 400 are space (8 words) reserved for the base register saving area. Bytes 84-147 are a saving area (16 words) used to save the values of all general purpose registers. Bytes 148-179 are a saving area (8 words) used to save scientific registers.

PCB 400 is provided with five double words above the PCB zero address for time accounting. These words are located between (PCB address -8) and (PCB address -40). Each of these words contains within its 52 bits a time or time interval expressed in microseconds, with bits 52-63 filled with zeros. The remaining timeout double word (the first 8 bytes above the zero on the PCB) stores the amount of time actually spent by the processor before the timeout exclusion occurs. this
The RTO word is updated as follows: The process timer value is stored in the RTO word each time there is a running process. Also, each time a process enters a run state, the process timer value is
Removed from RTO.

The running time accounting RUA double word located at PCB byte address 14 is a time counter that indicates the amount of processor time that the process has been in the running state. This time is actually the time spent by the processor exclusively on the process. The RUA word is updated as follows: Each time the process is in the run state, the value of process timer PT is read. The difference in memory information between RTO and PT is added to RUA. (The PT value is then stored in the RTO). Note that the time the process is on hold is not calculated. RTO and RUA are also updated if the accounting mode bit is set to zero. However, CET, RTA, and WTA
Words (described below) are provided to the process control block only if the accounting mode bit of process main word PMW0 is set to one. These words are updated only in the above cases.

The wait time accounting WTA word at the PCB byte address is a real-time counter that indicates the amount of real-time the process has been waiting. This WTA word is updated as follows: each time the process is in a wait state, the time value TOD of the day clock is read and (value of TOD - value of CET word) is added to the WTA word.

The ready-time accounting RTA word at the PCB byte address is a doubleword of a real-time counter that indicates the amount of real-time the process has been ready. This RTA is updated as follows: each time the process is in the ready state, the time in the day clock value TOD is read, and (memory information in TCD - information stored in CET) is
Added to RTA.

The current entry time CET double word contains the time the process entered one of the following states: ready, waiting, running, and pending.

Structure of the System Base Referring to FIG. 6, the format of the system base 600 is shown. The system base resides in absolute main memory and is accessible through readable but non-writable boundary address registers (BARs) created by the firmware. This BAR is below the area in main memory reserved for hardware and separates the system base 600 from the area in memory reserved for hardware. Referring to FIG. 6, the system base 600 includes several system numbers including process names (J.P.) for the currently running processes. From the logical name J.P of the process, the absolute address of the corresponding process control block PCB can be obtained. The size and address of the J-table or J-table are determined by the stored information of the J-table word (J-table word or J-table word JTW). This word is located at the address determined by the BAR register. The format of JTW is shown in Figure 11a. The scale (JSTZ) 1101 of J table 1204 in FIG. 12 defines the number of entries in J table 1204, which is a maximum of 255 entries. JTSZ1101 is 8
A positive integer of bits, if J is greater than or equal to JTSZ, results in an out of J table exclusion. The absolute address of 1204 in the J table is obtained by multiplying the J table pointer 1102 by 16. J-table 1204 contains J-table entries, the format of which is shown in detail in Figure 11b. Each J-table entry defines the absolute address of the P-table or P-table 1205 obtained by multiplying the P-table pointer 1104 by 16. The P table size (PTSZ) 1103 determines the number of entries in the P table. PTSZ is an 8-bit positive integer that typically ranges from 0 to 255 and indicates the number of entries in the P table. If P is greater than or equal to PTSZ, an exclusion out of the P table occurs. Each entry in the P table 1205 is a PCB
By multiplying pointer 1107 by 16,
Determine the absolute address of PCB 1206. Presence indicator P1105 is set to binary 0.
It is also set to a binary 1 to indicate the absence of a PCB 1206 and the presence of a PCB. (Presence indicator P
1105 is found to be 0, resulting in an empty P table entry exclusion). Bits 1-7 of the P table indicator (Figure 11c) are 0.
(MBZ) Must be 1160. Otherwise, unwarranted P table entry exclusion will result.

System base 600 (address BAR+
In 4) there is a G table word (GTW) format type, which is shown in detail in Figure 11d. The size and address of G segment table 1212 in FIG. 12 are determined by the stored information in the G table word (GTW). Size of table 1212 (GTSZ) 110
8 defines the number of entries in the G table, which typically has a maximum of 255 entries. GTSZ is an 8-bit positive integer, and if the number of G is greater than or equal to GTSZ, it produces the number of outs excluded from the G table. G table 1212
The absolute address of G table pointer 1109
is obtained by multiplying by 16. The format of a G segment table entry has the size of a double word (8 bytes) and is called a G segment descriptor. The format of the G segment descriptor is shown in detail in Figures 11e and 11f. All G segment descriptors are directly connected, so the indirect bit I, 1111, must be zero. Otherwise, an illegal segment descriptor exclusion will result. Presence indicator P1110 is a 1-bit field and is a binary 1
is set to indicate that a segment has been established in main memory for the segment number to which the descriptor corresponds. On the other hand, if cleared to 0, no segments are defined and queries to the segment descriptor will result in the exclusion of non-existent segments. Available bit A 1112 is a 1-bit field that indicates whether the segment is available. This bit indicates that the segment is defined (i.e. P
= binary 1), otherwise it is ignored. Used flag field U1113 indicates whether the segment is being accessed. If the U bit is set to a binary 0, the segment is not being accessed; if the U field is set to a binary 1, the segment is being accessed. Written flag field W111
4 indicates whether data has changed in that segment. If W is set to a binary 0, the segment data has not changed; if W is set to a binary 1, the segment data has been changed. The gating indicator GS1115 of the G segment descriptor is binary.
Must be set to 01. Otherwise, unwarranted segment descriptor exclusion will result. The reason is that the G segment, except for the G0 segment, always contains a semaphore (however, the reverse is not true; semaphores do not all have to be in the G segment), and the instructions for the semaphore have a GS code of 2. This is because it needs to be decimal 01. The absolute address of the base of segment 1214 is defined in the G segment descriptor of FIG. 11 by the 24-bit base field 1116. This field's memory information
Multiply by 16 to get the absolute address. Figure 11f
The second word of the G segment descriptor occupies bit positions 32-63 in the G table.
Bits 32-39 of RSU field 1117
is inverted for software purposes and is generally ignored when using the G segment as a descriptor, as is the case with the present invention. MBZ field 1118 must be zero. Otherwise, it will result in unwarranted segment exclusion. Since the MBZ field 1118 occupies bits 40-51, the SIZE field, which is the field for the small segment SIZE, is set. Therefore, all G segments must be of small segment type. For that purpose, G
The segment size for segment 1214 is
2 Must be ¹⁶ bytes (small segment) or less.

Referring again to system base 600 in FIG. 6, nine system exclusion cell words are placed between BAR plus 8 and BAR plus 44. The format of this system exclusion cell word EXC is shown in Figure 11g. A semaphore is used to transmit a message to a given process, so
When a system exclusion occurs, pointers to these semaphores appear in nine locations in memory, called system exclusion cells (one per class of system exclusion).
MBZ field 1120 must be set to binary 0. Otherwise, a system check will occur. Each excluded cell (EXC) includes system names G, D1121, and 1122, respectively.

The Channel Exclude cell in BAR Plus 44 of the System Base 600 has a similar format to the System Exclude Cell described above and includes the semaphore's system name GD, which sends a message to the intended process when a channel exclude occurs. used for transmission.

The internal processor keyword IPQW is located starting at BAR plus 48 and its format is detailed in Figure 11h.
The IPQW word specifies the head of the ready process queue (Q/PR/RDY), shown in FIG. 9 by reference numerals 905 and 803c. The segment size 1119 is a 12-bit positive integer, and the number of bytes in the segment is 16 x
Equal to (size + 1). If the bit field is zero, the segment size will be 16. The ready process queue (Q/PR/RDY) links all processes in the ready state.
HEAD of Q/PR/RDY field 1124 is 16
Contains a positive integer number of bits, which represents the amount of movement from the base of G segment number 0, called the G0 segment, to the first byte of Q/PR/RDY.
If the Q/PR/RDY bit field is 0, the ready queue is considered empty.
The MBZ field must be 0. Otherwise, a system check will occur.

BAR Plus 52 of system base 600 shows storage for initial and current retory counts, the format of which is shown in detail in FIG. 11i. The first retrieval count field 1126 and the current retrieval count field 1127 are used to control the number of times automatic instruction retrieval is performed before a machine error creates a machine fail exclusion condition.

The Running Process Word (RPW) shown in FIG.
plus 56 and is used to store the name of the running process along with its priority in the case of a monoprocessor configuration. The priority level of the running process is PRI field 11.
29. AB field 1130 stores an asynchronous trap bit. In contrast, asynchronous trapping uses ARN field 1
132. The logical name JP of the running process in a monoprocessor configuration is stored in the JP field 1133.

The absolutization table pointer shown in FIG.
and on the first system load, the BAR
is used to initialize absolute addresses at the initial system load (ISL) by adding the storage information of to all absolute addresses in the ISL program. The absolutization table pointer 1135 is
Locate the absolutization table (not shown). The absolutization table size is indicated by ATSZ field 1134.

The CPU sequence number word shown in Figure 11l is a 4-byte word located in BAR plus 64,
The CPU serial number is stored in the CPU serial number field 1136.

The main memory upper limit word shown in FIG. 11m is located at BAR plus 68 and represents the main memory upper limit 1139 by giving the absolute address of the first unavailable word.

For BAR Plus 72, initial system load ISL device channel number (CN) 1140
and hardware device channel number (CN)
Words as shown in FIG. 11n to obtain 1141 are placed.

The type and subtype of equipment used in the computer system are each field 1.
These are indicated by the hardware device type words 143 and 1144 (FIG. 11o). Further, the RSU field 1142 is reserved for software use. This word is located in System Base BAR Plus 76.

When the computer's restart button is pressed, a simulated V operation is performed on the semaphore and a ready state is entered. The pointer to this semaphore is
In the BAR Plus 84, it is called a restart cell word and has a format as shown in FIG. 11g. This format is similar to the system exclusion cell described above and includes the semaphore's system name G, D in G field 1149 and D field 1150, respectively. MBZ field 1148 must be zero.

If there is more than one processor for a computer system, one word is provided in the BAR plus 88 of the system base 600 for multi-process expansion. Details of this word are shown in Figure 11r.

Example of Using the System Base and Process Control Blocks Figure 12 shows how the system base can be used with process control blocks to address or access the user segment, the system segment, or the queue (Q/PR/RDY) segment of the process register. An example of how to use it in combination is shown below. Main memory 1200 has a portion 1203 reserved for hardware use. The boundary address register BAR1202 is the system base 121
5 from the portion of memory 1203 reserved for hardware. BAR1202
is used to address an item in the system base 1215 by adding the storage information of the BAR to the amount of movement of the item in 4-byte units required by that system base. This address specifies the first byte of the item in the desired system base. In Figure 12, BAR1202 is a J table word (JTW)
is pointing to. As previously discussed, this J-table word has a pointer that specifies J-table 1204. By indexing the J number shown in FIG. 5, one J table entry is obtained. This J-table entry has a P-table pointer that specifies the absolute address of P-table 1205. Furthermore, by indexing the P number in the P table 1205 (see FIG. 5), the absolute address of the PCB 1206 can be obtained.

As previously discussed with PCB 1206, the address space words include ASW0 and ASW1. The high order bit of the segment table number field STN of base register 1201 contains a pointer to segment table word array STWA that specifies one of these two address space words, in this example segment table word array STWA 1208.
Used to access ASW1. Segment table number of base register 1201
Along with the STN, one of the eight segment table words is accessed in STWA 1208, and this word is
Specify one of 10. Next, base register 1
Segment table entry from 201
STE is segment 1 with segment descriptor
210 is used to enter one of the 256 entries. Segment descriptors are used to access user segments 1211.

To access the system segment 1214 used to store semaphores,
The G table word GTW is used in the system base 1215. The address of the G table word is obtained by adding the amount of movement of the G table word in the system base to BAR 1202. (See Figure 6). G table word GTW
contains a G table pointer that specifies G table 1212. G that can be used by the system
system segment 12 by using the number and indexing in the G table.
14 can be accessed.

Similarly, the system base 1215
Process Ready Queue (Q/PR/RDY) 121 by looking for the internal processor keyword IPQW that specifies the PR/RDY segment 1213.
3 can be used to access.

Control Unit Details of the control unit are shown in Figures 13a to 13c. Although the control unit is shown separately from the central processing unit (CPU), it actually constitutes a portion of the CPU and is connected to the control store unit CUS130.
1. Consists of a control store interface adapter CIA 1302 and attached subunits, a control store loader CSL 1303 and a control and load unit CLU 1304.

Control store unit CSU1301
is control and load unit CLU1
304 and the control store interface adapter CIA 1302, it receives microinstructions from the control store loader CSL 1303. Under normal operating conditions, the microprogram is loaded from an external source during system initialization and serves as the machine's permanent control function. However, the control store unit CSU
1301 has the ability to be reloaded and initialized for multiple central processing unit CPU 1306 operating modes. Under the control of the CSU 1301, the CPU can operate in the following modes:
(a) Native mode; (b) Emulation mode;
(c) simultaneous native and emulation modes;
(d) Diagnostic mode. This feature allows micro-instructions located within the CSU to, e.g.
316, Arithmetic logic unit ALU
1317, instruction fetish unit
IFU1318, address control unit
It is attached to the CPU because it is the source of micro-operations used to control the operation of the ACU 1319 and all other CPU functional units such as the data management unit DMU 1321. The central processing unit CPU 1306 includes the aforementioned general register 1307, base register 1308, scientific register 1309, T register 1310, status register 1311, and instruction counter.
Also included is an IC 1312, a hardware control mask register 1313, and the like.

Generally, control store unit CSU1
301 is a 9K bipolar integrated circuit capable of programming read-only memory (PROM) mixed with read/write random access store (RAM). This unit has a typical 150 nanosecond read cycle and 450 nanosecond write cycle.

Each control store location has one
84-bit micro-instruction words are stored (described in detail below), each micro-instruction word controlling one CPU cycle. control store unit
As each CSU 1301 control store location is read, its contents are decoded by a micro-operation decoder to provide micro-operation control signals, each signal instructing a particular operation within the CPU. implemented (described in detail later).

Grouping locations within each micro-instruction word (described in more detail below) provides a control store sequence that can perform a particular CPU operation or instruction. When each instruction is initiated by the CPU, certain bits in the opcode are used to determine which control store starts the sequence. Testing of certain flops (not shown) that are set or reset by the instruction decode function allows the control store memory to be branched to another specific sequence as needed.

control store interface adapter
The CIA 1302 instructs the operation of the control store memory 1333 in FIG.
Transmit information to 7. CIA 1302 includes logic for control store address modification, testing, error checking, and hardware address generation. Hardware address generation is generally used for developing the starting address of an error sequence or for the initialization sequence.

Data management unit DMU1321
constitutes an interface between the CPU 1306 shown in FIG. 1 and main memory and/or buffer store memory. The data management unit is responsible for identifying units that contain information needed by other units and storing that information in CPU registers at the appropriate time. data management unit
The DMU is also responsible for the masking function during partial write operations.

Instruction fetish unit IFU13
18 is DMU1321, ACU1319, ALU1
317 and the CSU 1301, and shares the function of holding instructions supplied to the CPU. The instruction fetch unit provides the next instruction available in its register before completing the current instruction. To enable implementation of this function, instruction fetch unit IFU 1318 typically includes a 12-byte instruction register (not shown) containing one or more instructions. Furthermore, IFU
requires information (instructions) from main memory before the instructions are actually needed, under the control of the CSU;
This allows the 12-byte instruction register to be constantly updated. In this way, instructions are prefetched by memory cycles that are generally not used. The instruction fetch unit also has the function of decoding each instruction and notifying other units of the length and format of the instruction.

Address control unit ACU1319
communicates information through the CIA to the IFU, ALU, DMU and CBU. ACU 1319 is responsible for all address development in the CPU. including transfers or transfers within, from or to the Unit;
All ACU operations are directed by unit logic and CSU micro-operations. Regular cycling of the ACU is determined by the type of instruction address rather than the type of instruction. Depending on the address type, the ACU performs different operations on each address of the instruction. The ACU also includes an associative memory 1319a whose general purpose is to store the base addresses of the eight most recently used memory segments along with segment numbers. Each time a memory request or demand is made, the segment number is checked against the contents of the associative or associative memory;
Determine whether the base address of the segment has already been developed and stored. Base address is associative memory 1319a
, this address is used for absolute address development, saving considerable time. If the base address is not included in the associative memory 1319a,
Addresses are developed by accessing the main memory table. However, after a segment's base address has been depropped, this base address is stored as a permanent reference in associative memory along with the segment number.

The interface with the ACU, IFU, DMU and CSU is configured by an arithmetic and logic unit ALU1317. The primary function of this unit is to perform the arithmetic operations and multiplications required of the CPU. The operation of the arithmetic logic unit is completely dependent on micro-operation control signals from the control store unit CSU1301.

Scratchpad memory unit LSU1315
(Sometimes called local store unit)
is used with ALU 1317 and CSU 1301. LSU 1315 generally consists of a 256 location (32 bits per location) solid state memory and selection and read/write logic for this memory. Scratchpad memory 1315 is used to store CPU control information and retainable information. Furthermore,
Scratchpad memory 1315 includes a working location whose primary function is temporary storage of partial results and operands during data manipulation. Also used in conjunction with the ALU 1317 is an auxiliary memory 1317a consisting of 64 flip-flops for storing various states of the computer system.

The CPU also comprises a clocking unit 1320, having essentially two clocking systems in one, the first clocking system being connected to the control interface adapter CIA 13.
The second clocking system generates timing pulses for the operation of functional units within the central processing unit.

FIG. 13c shown in conjunction with FIG. 14i,
The format of the control store word 1325 is shown. Control store words are typically 84 bits wide and are divided into six major fields:

a Sequence type field 1326 (3 bits).

b Blanching and/or micro-operation 1327 (23 bits).

c Constant generation and designation 1328 (14 bits).

Data 1329 (8 bits) for the d bus.

e Microoperation 1330 (32 bits).

f Checking 1331 (4 bits).

The 3-bit E field of control store word 1325 is used as a sequence control field. Generally, seven sequence types and one type reserved for instant computer systems are used. In block 1335 of FIG. 13b,
If E field is equal to binary 0, 1 or 2, branching fields A, B, C, D and L of micro-operation 1325
is used to generate the next address.
The first 6 bits of the KS register 1337 are used in conjunction with the B field, C test result, D test result and L field to provide the next address of the next microinstruction, thus provided. The next address is placed in address register KS1337. When the E field is set to binary 4 (see block 1335), the next address selected is placed in the interrupt return register KA.
Retrieved from 1339. The address stored in the KA register is the address generated by the next address generation logic in the event of a hardware interrupt. When the E field is set to binary 5, one branch is used to initiate a subreturn from the microprogram subroutine. The contents of return register KR are used as the next control store address. Return register 1346 receives KR from incrementer 1378.
Register 1346 is loaded by issuing a control store command that loads the current control store address in KS register 1337 plus one. One level nesting functionality is provided via KT return branch register 1347. Each time the KR register 1346 is loaded, the old contents of the KR register are transferred to the KT register 1347 and the contents of the KT register are moved to the KR register each time microprogram return is called. The third level nesting subroutine function is in the KU register 134.
The fourth level nesting subroutine functionality is provided by KV Return Branch Register 1
Provided by 349. When the E field of a control store word is set to binary 6, the next control store word addressed is:
Equals the current address of KS register 1337 plus one word. E field is binary 7
When set to , the CSU 1301 is in diagnostic mode and the next address is the current address plus one.

As previously discussed and illustrated, in addition to the sequencing control that branches to the next control store address, there is a hardware generated sequencing control as shown in block 1336 of Figure 13b. (Note:
Blocks 1335 and 1336 are illustrated as actual hardware registers to illustrate the various forms that a microinstruction word can take. ) A branch generated by the hardware is an overriding condition (e.g. error initialize control store scan, etc.) that suppresses the E field and forces a fixed address into the control store address register KS1337. Enter. This branch is executed by forcing the interrupt line high for one clock period (not shown) and storing the address generated under control of the E field in the KA interrupt return register 1339. configured.
The hardware generated address is placed into the control store address register. Interrupts generated by certain hardware/firmware cause an interrupt block flip-flop (not shown) to generate further interrupts in that class until the interrupting condition is satisfied. Priority is given to cases where prevention is required. The firmware microoperation has the ability to control the reset of the interrupt block flip-flops for sequences under firmware control. These sequences under hardware control are
Automatically generates a block flop reset at the end of the sequence. The conditions that exist in this category are listed below in order of priority:
(a) Control store load, (b) Control store scan, (c) Hardware error, (d) Software error. The remaining hardware requirements are that the interrupt block flop is not set, but
It has a function that activates immediately when it occurs. The conditions included in this category, in order of priority, are as follows: (a) Initialize (b) Soft clear (c) Enter maintenance panel (d) Enter maintenance panel (e) Hardware exit Initialize signal So, CSU13
01 branches to address binary 0, clears the hardware resettable error, and performs a control store load operation followed by a control store scan sequence under hardware control. The initialization signal also performs system initialization. Soft clear signal is CSU
Branch 1301 to address binary 0,
Clears hardware resettable error and resets interrupt block flop.
Enter Maintenance Panel Signal CSU
branch to the address preset of the CSU address switch in the maintenance panel (not shown).

Intermaintenance channel signals are
CSU, maintenance channel (not shown)
Branch to the address generated via . The loaded address is transferred to the maintenance bus QMB1344, which forms part of the maintenance channel.
It is supplied from and light dystiffician. The hardware exit signal causes the CSU to branch to binary address 2. This sequence is used as a maintenance facility. At the end of this sequence, a return is initiated by setting the E field to binary 4 and generating the E field branch.

The control load signal causes the CSU to branch to address binary 0. Also,
turning off the CSU read cycle flop (not shown) and system clock 1320;
Keep CSU in load state. In the load state, the CSU can be loaded from control store loader CSL 1303, IOC 1305, main memory 102, or maintenance panel 1355. When loading from a CSL, an automatic scan occurs at the end of the load. When loading from other media, a scan is issued by generating a micro-operation signal or by setting a scan switch on a maintenance panel. Control store scan signal is CSU
Branch to address binary 0. The control store scan is under hardware control for the duration of the sequence. During the scan period, system clock 1320 is turned off and therefore no commands or tests are performed. 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 normal processing mode, a hardware error detected within the CPU functional unit activates a hardware error line (not shown). The generated control store sequence tests system conditions and determines the action to take. In diagnostic mode, hardware detectable error conditions are visible to microdiagnostics. Microdiagnostics controls the actions that should be taken.
On the other hand, a software error signal causes the control store to branch to address binary 1. This address corresponds to the start of a software error reporting sequence that is under microprogram control.

Again in FIG. 13c, E field 132
As already mentioned, 6 is a bit field for the branch code. Blanching and/or micro-operation field 1
327 consists of A, B, C, D, and L fields (shown in block 1335 in Figure 13b), of which the A field contains the upper six bits of the next address, and the B field contains the mask of the 64-way branch. The middle 4 bits of the next address of the field are stored in the C field, and the D field is the 64 bit test field for 1 of the 64 test.
Another 6-bit test field for test 1, and the L field means the least significant bit. The K field 1328 is a 14-bit field, of which 6 bits are constant fields, 4 bits are constant or steering fields, and 4 bits are constant steering fields. bus field 13
Data for 29 is sent to QA on QMB bus 1344.
The QB field consists of a QA field with 4 bits to control information regarding the operation, and a QB field with 4 bits to control information regarding the QB portion of the QMB bus 1344. F field 1330 is a 32 bit field that is decoded to generate microoperation subcommands. P field 1331 consists of 4 bits held for checking.

In the operation, the microinstruction word is the control store array 1
333. During a cycle of operation, the control store array is addressed by the contents of KS address register 1337. This determines the contents of the location pointed to by the address read into the group of read latches 1357. A portion of the word content of the read latch is allocated or transferred to a storage register in each of the functional units of the CPU.
Each functional unit includes decoding logic circuitry for generating request subcommands directed by the control store word under control of the system clock source. Generally, decoding is performed in a non-centralized manner with the purpose of reducing decoding time and reducing the amount of cables required to convey command signals if decoding is performed centrally. ,
It is implemented within each functional unit of the CPU. Furthermore, decoding is performed within each unit to avoid timing problems due to different delays in the cables. Additionally, by decoding the subcommands on a per-unit basis, signals representative of certain conditions existing within the functional unit may cause certain subcommand signals to not be returned to the CIA unit 1302. required to occur. A typical decoder unit 1359 that receives various fields from a microinstruction word and generates microoperation signals a, b, c, d, . . . q, r is shown in FIG. 13b. General micro-operation decoder 1
359 receives commands from the microinstruction word. The field from the microinstruction word is decoded and sets one of the lines s, t, u...y, z to a high state. Points α, β, γ……
The matrix is constructed by predetermining the control line impedance coupled to the sz line at z, ω. Therefore,
Generally, one of the lines sz goes high when a field from a microinstruction is decoded. In the matrix, the black dots denoted by the Greek letters α through ω signify the sympedances connecting the two sets of lines, so that the electrical signal traveling along any horizontal wire is Impedance coupling (black dots) is coupled for transmission along the vertical wire a-r at the indicated points. Each vertical line a-r can be coupled such that one input corresponds to one of AND gates 1360-1365. Other input signals are also input to the AND gate 1360, including the timing signal ts from the central timing unit.
~1365. Therefore, when each timing signal ts goes high, a gate with all other input signals in a high state is enabled and directs the microinstruction signal to a predetermined fan of the CPU. supply to the functional unit. For example, if command 1341 from read latch 1357 is decoded and the horizontal line goes high, then the a, b, c, and q vertical control lines go high and AND gates 1360, 13
61, 1362 and 1364 are enabled and the ts timing signal is applied to these gates in sequence. The system, consisting of vertical control lines coupled to horizontal control lines at various points indicated by the Greek letters α through ω, is connected to the central processing A central processing unit is used to control the functional units within the unit.
A permanent switching matrix for supplying micro-operation signals to the CPU. Therefore, permanent firmware with transformative potential can be incorporated into a machine according to the invention by simply specifying the sequence of micro-operations required as one of the functions of the computer system. It is.

Under normal conditions, data is written to control store array 1333 via the CPU write data register, also referred to as local register YO 1343. A control flop (not shown) determines whether the top or bottom half of the storage array is written.
Control and load unit CLU130
Data from 4 is maintenance bus QMB134
4 to the CIA/CSU and is buffered by storage local register YO 1343 before being written to control store array 1333. Storage local register 13
43 is time-shared as a read and write local register. Multiplexer KQM
1345 is controlled by either a maintenance panel 1355 or microdiagnostics and provides a readout path from the connected resistor. Conveyor register KP13
50, the non-functional is provided for the purpose and is mainly used for the purpose of maintenance,
Used with conveyor logic 1352 and decode logic 1351.

Dispatcher armware for process control The main purpose of the dispatcher is to manage various process queues and perform switching between processes. A firmware/hardware unit whose purpose is to update queues. The dispatcher also has the ability to send messages to actually waiting processes according to a semaphore or a semaphore (simulated V operation for an IOC or for an exception handler after a V operation). The dispatcher also has the ability to make a semaphore wait for a message after a P operation that releases a message link if a process is waiting for a message on a free link semaphore.

The dispatcher unit may also be configured to: After the "contest", request native mode instructional software. In addition, request a daco extension for the following cases: (a) Temporary calls during the rolling out period of a process with a daco extension active.

(b) Temporary calls during the rolling-in period of a process with decoder extensions active.

(c) Definitive call at the end of rolling-in of the process during deco extension operation.

(d) Definitive call after a contest if the current process is active and a deco extension is active.

Additionally, the dispatcher places the system in an idle loop when there are no processes running.

The following describes how to enter or leave a dispatcher.

(1) Initialization Procedure (SIP)
provides the entry as a final step.

(2) The start and suspend instructions provide entry to the dispatcher. A start instruction starts a process, and a suspend instruction ends a process.

(3) P and V operations provide entry to the dispatcher. The P operation picks up the signal from the semaphore, and if there is no message, the process goes into a waiting state.

In summary, the dispatcher manages processes and thus the process control block PCS by deciding which processes to run, and then takes appropriate actions, e.g., rolling out currently running processes. (i.e., write all information about the currently running process to the PCB, including hardware registers, scratchpad memory, etc.) and roll in the new process (i.e., write all information necessary to run the new process) It can be said that it is the main mechanism for performing operations such as writing (from the PCB to various hardware registers, scratchpad memory, etc.).

The functions performed by the dispatcher are shown in flowchart Nos. 14a-14i. For example, block 1402 of FIG. 14a illustrates the function performed by the dispatcher when a microprogram word is issued by the control store unit, and decoder 1359.
When decoding is performed by
This part is controlled via a series of micro-operation signals 1360, 1361, etc. in the storage subsystem 102 to retrieve the IPQW from the system base,
Transfer to scratch pad memory 1315. At the same time, the dispatcher fetches 1404 the G0 segment descriptor (see FIG. 12) from the G table of segment descriptors pointed to by the system base G table word GTW. Bit 16 of the IPQW word
-31 contains a 16-bit positive integer, which is a 16-bit positive integer from the base of G segment number 0, referred to as G0 segment, to
Moved to the head (first byte) of PR/RDY. If bits 16-31 of the IPQW word are 0, then the 1403 ready queue is considered vacant. If the ready queue is empty, it means that there is no process currently waiting in Q/PR/RDY and the ready queue is empty. The next question to be determined in decision block 1405 is to determine whether there are any processes currently in progress within the machine by determining whether the vacant indicator is set. It is. If the vacant indicator is set (i.e., there are no processes currently in progress), it has been determined in advance that there are no processes in the ready queue waiting to use the processor. , the machine is in an idle state 1406. However, if there is a process currently underway in the machine but no process waiting to use the machine, the current process accesses the next instruction 140
4.

Referring again to decision block 1403 of the flowchart of FIG. 14a, a positive integer (i.e., bit 16
-31), then the head of the ready queue pointed to by the IPQW word in the G0 segment is fetched into scratchpad memory. (Note: To avoid repetition and to simplify the explanation, the intermediate functions of the control unit and the dispatcher associated with the CPU will be omitted. (It should be understood that this type of intermediate function is quite commonly performed, as described above.) By this point, it has already been determined that there is a process waiting in the ready queue. There should be. Furthermore, before any operation is performed, it is necessary to determine whether there are any processes currently in progress at the central processor. This decision is made in decision block 141 of the flowchart.
0 and there is no process currently in progress in the central processor (i.e.
If there is no CJP), the beginning of the ready-queue is executed, 1412. If there is a process in progress on the central processor, the dispatcher must decide whether the process currently in progress or the head of the ready queue has priority. Therefore, system-based
The priority byte of the ongoing process located in the ongoing process word of PCB 400 is fetched, 1413. Next, the currently ongoing process CJP
It is determined whether NJP has a lower priority than the new process NJP waiting at the head of the ready queue (1414). (See decision block 1414.) If CJP does not have lower priority than NJP, CJP remains under control of the central processor and the contest indicator is reset, 1415. (The contest indicator is always 0 except in the following cases.
is set to That is, if one or more new processes are located in the ready queue, the final instruction will be started instead of CJP, creating the possibility of a conflict.
The contest indicator is set to binary 1. ) However, before the currently ongoing process CJP is allowed to continue and any further instructions are performed, it is determined whether the CJP is operating in deco extension mode, 1415. Ru. If the CJP is operating in deco extension mode, the next instruction will be performed in emulation mode (i.e. deco extension) and will operate in deco extension mode. If not, the next instruction is executed in native mode. Referring again to decision block 1414, if the priority of the NJP at the beginning of the ready queue is higher than the priority of the CJP (i.e., if the priority number of the NJP is lower than the priority number of the CJP) ), the currently running process CJP is “rolled out” of the machine and the new process NJP is “rolled in” to the machine. Therefore, the firmware priority subroutine PRIO 1418, in accordance with the instructions of the firmware subroutine RLLO 1419, first "rolls out" the CJP, thereby placing the currently ongoing process CJP in the ready queue according to its LIFO priority and priority number. set in a given position in the column. The RLLO subroutine stores the general register, base register,
Instructs to write back the CJP information stored in the science register, T register, status register, and instruction counter to the corresponding storage area of the process control block PCB in the main memory,
Instruct RUA update. Furthermore, the DEXT number of process main word 0 (PMW0) of PCB 400 is updated to 1420.

At this point, it is possible to "roll in" the new process NJP. The boundary address register BAR is fetched 1422 and the process word in progress RPW is fetched from the system base address BAR plus 56. See block 1423. The name of the new process NJP was then written to the ongoing process word RPW, and since the name of the new process NJP was written to the process link PL of Q/PR/RDY, the name of the process link PL is Block 1
Placed at RPW of 424. Therefore, NJP from Lady Kyu becomes CJP at this point,
It is now possible to control the central processor and therefore no longer wait on Q/PR/RDY by removing its name from the process link PL of Q/PR/RDY in block 1425. removed from the waiting list. When this operation is performed, Q/PR/RDY is updated by firmware subroutine UQLK, 1425a. Therefore, the JP number of the process just removed from the machine is placed in the process link of Q/PR/RDY. The reason is that this process is no longer involved in controlling the machine and is in a waiting state 1426. At this point, the conversion to give control of the central processor to the new process and place the old process in the ready queue has been performed, and the process (new process) is now under the control of the central processor, so the vacancy The indicator is set to 0, 1427. On the other hand, if the CJP is not under the control of the central processor, the vacant indicator is set to 1. At this point, the processor assignment is complete and the old process has been placed in the ready queue, so the central processor is used for the new process. However, the new process, for example, general register 1307, base register 130
8. The central processing unit hardware shown at 1306 in Figure 13a, such as the science register 1309, the T register 1310, the status register 1311 and the instruction counter 1312, is ready for operation. It is necessary to supply control information from the process control block of the new process.

Therefore, firmware subroutine 1430
controls the CPU, and from the PCB (Figure 4), PMW3
is fetched into the scratch pad memory 1315, and then PMW0 is fetched. PMW0
The MBZ field is checked for 1433 and if it is not a binary 0 it is an illegal PCB exception. However, MBZ of PMW0
If the field is zero, PMW1 is 1434
is fucked by. MBZ field of PMW1,
Tested again to determine if it is a binary zero. If it is not a binary 0, it is an illegal PCB exception; if it is 0,
The dispatcher proceeds to C.

Therefore, address space word 0ASW0 is
Fetched from the appropriate space on the PCB, the segment table word size STWSZ is tested and
1437, and it is determined whether the result is 7 or less. If it exceeds 7, it becomes an illegal PCB.
If less than or equal to 7, ASW1 is fetched from block 1438, the PCB, and its
The STWSZ field is checked to determine if it is less than or equal to 8, 1439. The result is an illegal PCB if the field is greater than 8, and if STWSZ is less than or equal to 8, the exception word EXW is fetched, 1440, and its MBZ field is 0.
is tested to determine whether it is equal to or not.
If the MBZ field is not equal to 0 then it is an illegal PCB, if it is equal to 0 then the stack word SKW is fetched and 1442 its
The MBZ field is tested 1443 to determine whether it is equal to zero. the result
If the MBZ field is not equal to 0, it is an illegal PCB; if it is equal to 0, the instruction counter word ICW is fetched from the PCB and the instruction counter word ICW is fetched from the PCB.
and its TAG field is tested to determine whether it is equal to 0, 144
5. As a result, if the TAG field is not equal to 0, it is an illegal PCB. If the TAG field is equal to zero, the MBZ word is fetched 1446 and the MBZ field (bits 0-31) is tested against 1447 to determine if it is equal to zero. If it is not equal to 0, it is an illegal PCB and 0
, then stack basewords 0, 1 and 2BW 0, 1 and 2 are fetched, 14
48. The contents of the 8 base registers in the base register saving area of the PCB are fetched and
1449, stored in the machine's base register 1304. The contents of the 16 general registers from the PCB's general register saving area are:
Fetched and stored 1405 in the machine's general register 1307. However, before fetching the contents of the scientifc register, a check is made of the capability byte in process main word 0 (PMW0) to determine if scientifc mode is being used in the 1451. . If the scientific switch mode is used, the contents of the scientific register from the PCB's scientific register saving area are fetched 1452.
is memorized. The firmware then proceeds to check the capability byte of PMW0 to determine if accounting mode is being used at 1453. The firmware then proceeds with operations 14 to determine whether the DEXT number is set to zero.
54. If not set to 0, it means the machine can be in emulation mode (i.e. the deco extension feature is used) and therefore the DEXT number of PMW0 is ,
The DETSZ field of process main word 3 is checked to determine whether it is greater than or equal to, 1455. If the DETSZ field is exceeded, illegal PCB exception 1456 will occur. The reason is that the DEXT number is
Because the DETSZ field is less than but not equal to zero, the machine is operating in legal emulation mode and is progressing towards F. Considering again decision block 1454, if the DEXT field is a binary 0, then native mode is in effect and the machine fetches STW, 1457.
The PCB's resident timeout word RTO word is fetched 1458 and the process timer is loaded to the extent that the CJP is in the running state.

Up to this point, (a) the old CJP is in the machine;
If the new process NJP has a higher priority than the old process CJP, it will
NJP is “rolled in” or (b)
This corresponds to the case where there is no CJP under the control of the CPU and the head of the ready queue has finished operating. In summary, under condition (a):
CJP is taken from RPW and placed in the process link PL of Q/PR/RDY.
The process link PL of is placed in RPW, thus effectively switching the positions of the two processes by providing control to NJP, which is now CJP, and taking control away from the old CJP. next,
NJP's PCB is accessed and NJP (currently
The information needed to proceed (CJP) is placed into scratchpad memory or an array of registers in the ACU.

If there is no CJP under the control of the CPU (condition b), the process located at the head of the ready queue proceeds, that is, the dispatcher removes the NJP from the process link PL at the head of the ready queue, and
This means that NJP has become CJP because it is placed in the RPW word. By performing such an operation, the process link PL is left as a vacant space in Q/PR/RDY, and it is necessary to take it out.

Therefore, at this point, starting at decision block 1461, the firmware:
determine whether a CJP was under the control of the CPU;
If there is a free process link (FPLS), it will be accessed, placed in the queue, and the CJP will be written. If there is no CJP under the control of the CPU, the state byte of the NJP's PMW0 is updated, and a determination is made again 1460 as to whether there is a CJP in the machine 1463. If there is no CJP under the control of the processor, NJP (Q/
The process link for Q/PR/RDY (which was in PR/RDY but is currently under control of the machine) is Q/PR/RDY1.
466 (i.e., taken out of the queue from Q/PR/RDY), becomes a free process link, and is placed in the queue of the free process link queue of the process link semaphore (PLS) (9th Figure 805), free process link queue 1
466a. The contents of the boundary address register BAR are fetched 1464 and the NJP (currently CJP) ongoing process word RPW located in system base BAR plus 56 places the NJP identification in RPW, block 1465. Updated by The vacant indicator is set to 0 in the absence of CJP. Next, the contest indicator is set to 0 and the segment associator (AS of FIG.
132) is cleared, 1471, then process mode is entered, 1470. (Process mode indicates that the exception is handled by an ongoing process within the processor, rather than by the active system.) Next,
The firmware continues with CAB, 1480, and the asynchronous trap bit AB is checked to determine if it is set to a binary 1, 1481. If the AB bit is set to binary 1, the process ring number
A check is made to determine if PRN is greater than or equal to the asynchronous trap bit field ARN, 1482. (AB and ARN are located in the priority byte of each process's PCB and are meaningful when the process is in progress,
AB and ARU are determined from the RPW located at the system base BAR plus 56. )
AB and ARU in RPW BAR Plus 56
will be reset. The reason is the next step 148.
4 proceeds to the asynchronous trap routine which is concerned with the conditions that cause the asynchronous trap bit or the asynchronous ring number to be set in the first place. If not reset, the firmware will:
It indicates that something has happened where no real problem has occurred, so it should always proceed to the asynchronous trap routine 1484 and never be reset.
Referring again to decision blocks 1481 and 1482, either the AB bit is not set or the AB bit is set and
If the PRU is less than the ARU, the firmware continues to determine whether the processor is operating in normal mode or emulation mode. Therefore, to determine whether it is set to 0 or not,
If the DEXT number is checked and set to 0, the machine is operating in normal mode, 1487. If the DEXT number is not set to 0, you are operating in emulation mode, 148
6.

Main Theory of Semaphoo As already mentioned, processes can share process segments and can also share data segments. Because of this correlation mechanism, processes must be able to cooperate with each other, and the systems described above have a set of process synchronization facilities. To provide these functions, a data structure called a semaphore is used.

A semaphore is a shared data structure referenced by the address base of all cooperating processes. As a shared data structure, semaphores are used to connect processes and events or resources that do not occur at the same time. As previously explained, an event refers to an event observed by a process that is related to another process. The event is
It can also refer to the completion of an asynchronous operation or the availability of resources. Events can occur either by other processes reaching a certain stage of implementation or by the arrival of a message. Therefore, a semaphore must be able to remember the existence of an event or resource that a process is waiting for. On the other hand, the process
It is possible to reach certain stages of implementation before the event occurs. Under such conditions, the semaphore must be able to remember which processes are waiting for the event. Thus, Semaphore has the dual ability to remember whichever event occurs first, a process that is waiting for an event to continue, or, alternatively, a process that is waiting for an event to join. That is required.

A complete discussion of semaphore requires first detailing its relationship and location in the system already described, then detailing the various data formats, and finally its use in the system. It is necessary to explain the operation.

In FIG. 8, the physical organization of main memory is illustrated as logical groupings of segment tables. These tables, called G segments, are used to store semaphore and relationship information. More specifically, these G-tables are divided into two conceptually distinct segments, one of which is the GO segment and the other one of which is a number of SD segments.

The GO segment is used to hold a number of process links (PLs) and system process link semaphore (PLS). Each process link contains four fields.
That is, one field is the process name that represents the process, and the second field is AB and ARN.
, the third field is the connection link to the next entry,
The fourth field contains the relative address of the segment. The name field corresponds to the process control block (PCB) JP name.
It is a JP name. Therefore, each process link in the GO segment provides one two-word stand-in for the PCB, since each process link points to the PCB it represents. The priority field is a perfect imitation of the priority field in a PCB. The link field has the function of ordering process links into a queue and allowing dispatchers to view process links in order of rank. Therefore, the GO segment allows the dispatcher to see all processes that are currently active, since each process has one two-word process link that links the process to its PCB. Equipped with a simple mechanism to do so.

As previously discussed, a process can be in one of four states: progressing, preparing, waiting, or pending (not currently active). All processes other than those in the currently active progress state are positioned in the GO segment according to the process name and the queue in which the process link with the process name resides. Therefore, as well as these states dictated by the PCB, the process links of the GO segment can be configured with dispatchers to facilitate queue configuration for access and alteration. . In other words, each process currently in progress has its name in a process link, and each process link can be said to form part of one of a number of queues of GO segments. Therefore, a process name appears in only one process link, and a process link can only appear in one process link at a time.
It can only be attached to one queue. A requirement for a dispatcher that changes the state of a process is to have the ability to transfer a process link to another queue associated with the state of the process. Therefore, state transformation is easily achieved by changing the interrelationship of process links in the GO segment.

Since only one process is in progress, queue configuration for the process link is unnecessary. However, multiple processes may be in a ready or waiting state.

Furthermore, a process can be in a state of anticipation for any one of a number of types of events. Therefore, one ready queue, i.e., Q/PR/
RDY is configured and there are a number of waiting queues, i.e. Q/PR/S or Q/PR/FLS, for these processes waiting to provide events or resources to continue operations. exist. As previously discussed, queues are not configured for pending processes because they are not currently in progress.

Figure 9 shows a developed view of the GO segment. There is only one GO segment in the system. The GO segment is a two-word stand-alone segment for all process links, that is, for all processes that can be operated on by the system.
Provide inn.

Each process in the ready state is bound to other processes by its link field, ready queue, Q/PR/RDY, 803c and d.
It is incorporated into a group called Kyu. The ready key is the head and tail, i.e. the initial and final process of determining the limits by some method.
A link must be provided. This limit determination is achieved by the next field of the process link, as already mentioned. The tail of the queue, 803d, is identified by appending a zero value to the next link field. The head of Q/PR/RDY is pointed to by a field in the system base area, a word called the internal process queue word (IPOW). This IPQW
contains a pointer to the process link located at the head of the ready-queue. Therefore, the dispatcher can locate all ready queues by locating the head of the ready queue by IPQW and sequencing all process links of Q/PR/RDY by the next link field.・You can see the process. If a process currently in progress moves to another state, e.g. a waiting state, the dispatcher
Pick the process link located at the head of PR/RDY, remove it from the queue, and use the JP name to find its process control block. This causes the process to become a new, ongoing process and transition from the ready state to the progress state according to the dispatcher's instructions.

Processes that are in progress are not displayed in the GO segment's process link. Instead,
In the system base area is a word containing two fields called the Running Process Word or RPW. One of the two fields above is for the process currently in progress.
JP name and the other is a copy of the priority field held on the PCB.
If a condition arises in which the dispatcher compares the ready-queue head with the currently underway process to determine which process is controlled by the central processing unit, it compares the RPW with the process link; After that, a predetermined operation is performed.

A process in the waiting state is waiting for a signal or message that means that a particular event has occurred. This type of queue of waiting processes may be necessary since more than one process may be waiting on the same signal or message. Therefore, each process in the waiting state is also represented in the GO segment by a two-word process link, and these process links are placed in the waiting queue. Since more than one semaphore may have waiting processes, the large number of Q/s indicated by the string of process links in the GO segment
PR/S may also exist. To illustrate with a diagram, the process's two waiting queues are
03a-b and 803e-g. Each such Q/PR/S head shall be pointed to by its own semaphore, as explained below. This designation is distinct from the ready queue, which is indicated by the system-based internal processor queue word. Q/PR/
RDY and Q/PR/S are both queues of process links operated by P and V instructions and dispatcher hardware when a process changes state.
A dispatcher or P or V instruction can remove a process from one of these queues and brace it to another queue, and the dispatcher can also in progress, or
You can change from one progress state to another.

The process link for the waiting process Q/PR/S is, in terms of format, a Q/PR/RDY with the tail of the queue pointed to by the process link with a zero-value next link field. This is the same as process link. A pointer to the head of the waiting process's queue is maintained in a special data structure required by the semaphore used to dispatch the event. This semaphore contains a process queue head pointer, PHQP, which points to the head process link of the queue of the process waiting in the semaphore, that is, Q/PR/S, as will be explained in detail later. .

Abandon the process link in the GO segment when the process moves from the ready or waiting state to the proceeding or pending state. The space thus given up is therefore free for other uses. On the other hand, if a process that is in a pending or progress state is to move to a ready or waiting state, it must obtain a process link within the GO segment. Therefore, the GO segment involves memory management issues. The dispatcher must have the ability to quickly acquire and release two-word process links. To solve this problem, the GO segment includes another cue that is automatically operated by the hardware. This queue contains all free links that can be used when a new process is introduced. When a process link is decommissioned, for example when a ready or waiting process changes to a pending state, one free process link is added to the queue of free process links. When a new process link is needed to represent a process that is going into a ready or waiting state, one process link is taken from the queue of free process links. These operations are primarily performed by the dispatcher, but P and V instructions or start and hold instructions may also be used. Enough process links must be included in the GO segment to hold the names of all currently active processes at a given time.

Free process links are aligned in a manner similar to that for Q/PR/RDY and Q/PR/S, and queue tails are placed on links with zero parity next link fields. You will be given instructions. Free process links
The head of the queue is Process Link Semaphore (PLS) 901 located at the front of the GO segment.
is indicated by a field in a special data structure called . The process link semaphore is
It is located at a known location within the GO segment, so there is no problem with the dispatcher for its positioning. Therefore, all process links within a GO segment are bound in some way to either a ready queue, one of a number of waiting queues, or a free process link queue.

However, please note that the process link itself does not contain any element that identifies the queue to which it belongs. When looking at process links within a GO segment, only one process name, priority and next link link fields are allowed, so there are no backward links or other identifying information. . In this way, it is not possible to determine the current status of the system by looking at process links.

As already mentioned, semaphore also has the ability to store events that are waiting for a process to join. A number of remaining G segments are used to provide this functionality. The remaining G segments are called semaphore descriptor (SD) segments and are comprised of Gn segments 802n. The SD segment is a segment that includes a semaphore, a message link queue controlled by the semaphore, and a semaphore descriptor. A semaphore descriptor segment is referenced if an ordinary segment in the local address base of process JP has a semaphore descriptor segment containing the GS bit equal to 01. These GS bits are continuously written when accessing the semaphore descriptor segment. Furthermore, it is not possible for two G segments to start at the same absolute address. Therefore, the GO segment is the first segment with one absolute starting address, the remaining SD segments,
That is, G1 to Gn each have their own absolute starting address.

The layout of the semaphore descriptor segment (SD) is shown in FIG. The first word of the semaphore descriptor segment must have the 32-bit format that follows. The first two bits are the tag field as an 11-bit encoding that indicates a so-called tag fault. This field indication is simply a hardware mechanism to restrict access to the words of the SD segment. The next two bits, i.e. 2
and 3 is the VR ring number. (The ring number and related structure are from Japanese Patent Application Laid-Open No.
114934). The ring number, VR, specifies the maximum ring count for allowing a semaphore to perform V operations via the segment's semaphore descriptor. The next two bits, 4 and 5, are the PR ring number that defines the maximum ring count that will allow the semaphore to perform P operations through the segment's semaphore descriptor. Bits 6 and 7 are the IR ring number that defines the maximum counting ring that allows a semaphore initialized semaphore count operation via the segment's semaphore descriptor. Semaphore descriptor segment
VR, PR, and IR do not necessarily relate to the semaphore within the segment, but rather the semaphore descriptor 15 located within the segment.
02 (described in more detail below), that is, they only concern semaphores accessed through these descriptors. Therefore, a semaphore may be located in a different segment than the semaphore descriptor segment. Bit 8
-15 must be zero and is labeled MBZ. Bits 16-31 are the free link semaphore pointer, FLSP, meaning relative address transitions in the semaphore descriptor segment. Free-linked semaphore pointers serve two functions within the system.
First, it is limited as the upper limit of the address of a semaphore descriptor within a semaphore descriptor segment. In other words, the segment-relative address of any semaphore descriptor in a segment must be less than FLSP.
If the relative address of any semaphore descriptor within the segment is not less than FLSP, then the semaphore descriptor does not point to a semaphore within the segment. Second, it has a function of instructing free link semaphore (FLS), which will be explained next. In FIG. 15, number 1500 refers to the first word of the semaphore descriptor segment;
02 relates to one of a number of semaphore descriptors.

The FLSP of the first word of the semaphore descriptor segment is the free link semaphore 150 following the semaphore descriptor 1502.
Present a relative address pointing to 4. free·
The link semaphore, FLS, controls the free message link queue, Q/ML/FLS, in that segment, if the FLS is present. If the SD segment contains a semaphore along with a message, a free link semaphore must be present. In addition, all free
If message links are currently used, FLS must be used to hold the process, ie, Q/PR/FLS.

If there is no semaphore descriptor, 1
502 is invalid. If there are no free message links, the semaphore FLS indicated by 1504 is unnecessary.

In FIG. 15, 1506 indicates the position of the semaphore. Semaphores that may form part of the memory are shown in Figures 16a and 16b. Block 1508 includes message links and free message links. Each of these links is included within the SD segment in the same way as process links within the GO segment. This message area generally includes messages associated with the various semaphore within the segment, although other data may be included in other segments.

Each message link 1508 is 1508a
As shown in the figure, the message consists of four words. The first 48 bits are the message
The last 84 bits constitute the message blooper area. The message header is 1-1/2 words, or bit 0.
-47 included. The message itself occupies the remaining space in the link, 2-1/2 words or bits 48-127.

The message header format has bits 0-15 as the next link field. This format therefore contains the relative address of the queue's next message link in the semaphore descriptor segment. However, if the link is located at the end of the queue, the Next Link field will be zero, indicating the end of the queue. Bits 16-23 are the reason field that provides the reason for the message.
The reason field is only used in situations with an IO message and is meaningless in the absence of an IO message. Bits 24-27
is the message priority level (MPL). This field is used in conjunction with semaphore in conjunction with messages, with the lowest message priority level corresponding to the highest priority. Bits 28-31 are the message
It's a tag. This field contains basic information about the nature of the message. message tag 0
000 indicates that the message was generated by a P or V instruction. Message tag 1000 means that the IOC has generated a message. Bit 32-4
8 is the sender's name. Depending on the message, this field contains the name JP of the process that sent the message, or the channel number for the IOC message, and is zero everywhere else.

Messages are included in the semaphore descriptor segment and not in the GO segment. The interrelationship of message links to semaphore and free link semaphore is shown in FIG. Messages are provided to general registers 0-3 on the PCB. Thus, the process performing the V operation stores the message in general registers 1 through 3, and the system hardware configures the message header in general registers 0 through 1. By not using space in the data segment and using general registers, the hardware can easily issue messages. When a process is in the waiting state, its registers are easily addressed in the process control block, and the fields in the message are read once the process returns to the in-progress state.
Can be easily tested in a register.

Message links and free message links also constitute queues. When a message link is attached to a semaphore, the semaphore's message queue (Q/M/S) is constructed. Where message links are not currently in use, these links are coupled to FLS semaphore 1504 to form a queue of message links for free link semaphore, Q/ML/FLS. Q/When a message is not provided
Although the structure of ML/FLS is similar to Q/PR/PLS, it differs in many important respects as previously discussed.

The method described above performs basic memory allocation of where the semaphore resides.
9 and 1 as shown in Figures 17 and 18.
Before explaining the operation of the structure shown in FIG. 5, each of the data structures of the semaphore will be discussed.

With reference to FIG. 16, a data structure that enables the coupling of processes and events will be described. FIG. 16 shows five types of semaphore used in the system described above. These semaphore are semaphore 1600 without message shown in FIG. 16a, semaphore 1602 with message shown in FIG. A process link semaphore 901 used for the process link semaphore 901 and a free link semaphore 1504 used for the SD segment shown in FIG. 16d.

As already mentioned, semaphore binds a process to an event or resource. Semapho is
If the semaphore without the message data structure shown in Figure 16a is used simply to indicate the occurrence of an event without the purpose of transferring specific information about the occurrence of the event, used. For example, Semapho 16
00 is information about the availability of a disk driver that can be combined with an I/O device such as a disk drive, etc. For example, a request for a disk or an indication that a process has terminated with a disk is 1600. Other semaphore 1600 can be used to indicate other I/O devices or other quantities.
In these examples, a dedicated semaphore 1600 is used in each case. Semaphore 1600 consists of a double word, or 64 bits. Its format is shown below. The first four bits, bits 0 through 3, are the semaphore tag (STAG) field, which is used for every semaphore to indicate the particular type of semaphore. For semaphore messages that do not understand the message, the encoding of the STAG field is 0000. Bit 4 of semaphore 1600
-15 is used to indicate the Semaphore Maximum Account (SMC). The SMC field indicates the maximum number of resources that constitute or are bound to the semaphore. Bits 16-31 contain the semaphore count field (SCT), which is used to indicate the actual number of processes waiting on a semaphore, or the actual number of resources waiting on a semaphore. SMC and
There is a relationship between the SCT fields that the value of the SCT field can never be greater than the value of the SMC field, and the reason for this will be explained later.

Bits 32-47 are the process queue head pointer (PQHP). The process queue head pointer is a 16-bit relative displacement that points to the head of the process link in the GO segment associated with the semaphore. The process queue head pointer is zero if the SCT count is zero or positive. The reason is that there is no process waiting for the semaphore, so there is no process link to point to. If the SCT count is negative, field PQHP points to the first process placed in the semaphore's queue. Bit 48
-63 is the tenant process name (TEP). This field contains the JP name of the last process that caused the semaphore to perform a satisfactory P operation. As a result, the name of the last process that acquires resources from Semaphore can be known from the TEP field.
Since only a signal is given, an indication that an event has occurred, the TEP name indicates the last process that received the signal.

The count in the semaphore's SCT field is the determining factor in determining whether the semaphore remembers the existence of an event, resource, or process. If SCT is positive, the value of SCT indicates the number of resources waiting for the process. Conversely, if SCT is negative, the absolute value of SCT indicates the number of processes waiting for the resource. If the SCT field is equal to zero, there are no processes or resources waiting on the semaphore.

The SCT field is used in conjunction with the semaphore P and V operations to increment or decrement the count. Therefore, when a P operation is performed in which a process requests a resource from a predetermined semaphore, the SCT field is decremented by one. Conversely, a V operation that indicates whether a semaphore can use a resource
SCT field increases by 1. Although no message is connected to a semaphore without a message, the basic increases and decreases due to this V and P operation affect the connection between a semaphore with a message and a semaphore without a message.
Also applies to SCT fields.

A semaphore with message 1602 is used when transmission of specific information regarding the occurrence of an event is required. The situation is the same as for semahore without a message, and for semahore with a message,
Each specific event, such as the deduction of Social Security contributions from wages or federal taxes,
It is related to Therefore, each semaphore is predetermined, and its operating system is
It constitutes an address syllable for finding a specific semaphore when a specific event occurs.

Message Semaphore Tag Field (STAG)
are shown as bits 0-3. According to the encoding, the STAG field indicates whether the semaphore is one of two types: a message management semaphore or a message semaphore.
In the case of a semaphore with a message, the STAG field indicates the type of queueing of the message.
If the STAG field is 0001, the message is
The data will be queued using the FIFO (first in first out) method. If the STAG field only has the 0010 tag, only LIFO (last in first out) messages will be queued in the semaphore. If the STAG field is 0011, queueing of either FIFO or LIFO messages is allowed.

Message management semaphore is 0101
STAG field, which indicates that messages are queued according to process priority, and that the FIFO law side is applied at each level of priority. Therefore, the message
Management semaphores are distinguished from message semaphores by the use of priority levels, allowing important messages to be transmitted more quickly.

In word 1602, bits 4-15 check the semaphore maximum count SMC and bit 1
6-31 confirms the SCT count. This is the same as word 1600. Therefore, a message is another form of data like a signal, but it can be said to have the same existence-or-absence property as the signal used in a non-message semaphore. Therefore, the SCT field is generated by a message in a message semaphore in the same way as a signal in a non-message semaphore.

Bits 32-47 contain either a message queue head pointer (MQHP) or a process queue head pointer (PQHP). If the SCT count is positive, it indicates that many messages are queued on the semaphore. In this case, the message queue head pointer will point to the first message in the message queue. Bit 48-6 is
It has a message queue tail pointer, which points to the last message in the message queue when the SCT count is positive. If SCT count is negative, SCT
The absolute value of the count will represent the number of processes queued on that semaphore. In this state, PQHP points to the head of the process link queue, and the message queue tail pointer naturally points to zero since there is clearly no message. With the semaphore count equal to zero, POHP, MOHP, and MOTR are all zero because no messages or processes are acknowledged.

The semaphore of Figures 16a and 16b illustrates a signaling mechanism for process synchronization. These are found at 1506 in the SD segment. However, in this case the memory for storing either the process or the message is
A problem arises in that space is required. To alleviate this memory management problem, a free link semaphore, shown in Figure 16d, and a process link semaphore, shown in Figure 16c, are provided. These semaphore are
Controls the number of each free message link and free process link available. This will be explained below.

Figure 16c shows the process link semaphore PLS
901 shows the data structure of 901. A process link semaphore is an unused process link, i.e. a process with no process name.
Combine all links. When the process state becomes ready, the first unused link is removed from the process link semaphore. This link is given the name of the newly started process, among other fields. Conversely, when a process is interrupted or completed,
Alternatively, when it is reactivated, the name of the process entering the queue link is removed and the link field is changed so that all unused process links are preserved. Therefore, this machine allows for easy control of process link queues without the need to physically re-locate the links in the GO segment, since it is easy to change the content of the next link field for one link. can. This results in process links being transmitted from queue to queue. Since the names of all processes are stored in the GO segment, the process link semaphore is essentially a repository for process links required by new processes coming into the system. I can do it. In addition, the process links semaphore has bit position 4.
8-63 process link queue head
There is a pointer (PLQP) that points to the relative address of the queue's first process link with respect to the GO segment base. Each process link contains a next link field that points to the next process link that is bound to the process link semaphore. In this way, processes are introduced one after another,
As it completes, the process links in the GO segment are rearranged, but if you know the first process link, you can discover all the remaining process links.
All that is required is to know the first process link in advance.

The free links semaphore shown in Figure 16d is
It is similar to a process link semaphore in that it combines all free message links at the end of a segment. However, as mentioned above, the free message link is not included in the GO segment, but rather in the SD segment.
FLS has a data structure with a length of 3 words, and has the following format. Bit 0
The STAG field from 3 to 3 indicates the type of semaphore. For free message links semaphore, this STAG field is 0000. Bits 4-15 must be zero as indicated by MBZ. Bits 16-31 are the free link semaphore account, and this field indicates the number of processes waiting for a free message link. That is, Q/PR/FLS. This is a negative number and will decrease as processes are bound to free link semaphores. When the FLSCT value is zero, there are no processes waiting for a free message link. Bits 32-47 are the process queue head pointer PQHP;
-63 is the free message link queue pointer FLQP. process queue
Head pointer mentioned everything in relation to semaphore with message. The free message link queue pointer is a pointer to the first message link associated with the free link semaphore. This free message link is spliced in LIFO order using the next link field. Bit 64-71
must be zero. Also, bit 72-
79 is a free links semaphore cloval
Name (G name). Bits 81-95 are the logical channel count (CCT), which is the free
Indicates the number of logical channels waiting for message links. This occurs during IO operations, but
Here, the device via that logical channel communicates with the process via the semaphore, so
Waiting for a free message link, so there are no free message links available.

When a V operation is performed by a process on a semaphore that has a message in the SD segment of the FLS, the first message link pointed to by FLQP is used to store the message. FLQP then changes position to indicate the next free message link available. Conversely,
When a P operation is performed on a semaphore that has a message in the SD segment of the FLS, the message link with the previous information is freed and returned to the queue bound to the FLS. FLS, PQHP is used only when there are no message links available and only when a request for a message link is made. Therefore, this is
It indicates that a process tried to convey a message but was unable to do so. Like this,
Because FLS keeps track of all available free message links in a segment, it provides a memory management solution to the problem of limited memory space in SD segments. This is the translation.

Having described the form of the system in which the semaphore works and the semaphore itself, I will now discuss the operation and functions of the semaphore. FIG. 17 shows the semaphore addressing method. 17 and 18 both show various semaphores and queues that can be coupled to them. If you look at Figures 17 and 18,
The relationship of semaphore and queue structures to the overall system design becomes clear.

FIG. 17 shows the progression of semaphore positions through a segmented mechanism such as that described in connection with FIG. In particular, semaphores are addressed by process synchronization and multiplexing commands, ie P or V commands. This P or V command has a 20-bit address syllable (AS), and to solve it,
The structure of address tables 503, 504 must be searched. Furthermore, address tail 5
03,504 contains the JP number of the active process for selecting the process control block 400. Next is STN1700
Using the values of and STE1702, the segment descriptor that defines the SD segment is found. This results in an absolute address calculation that locates the semaphore descriptor in memory. The semaphore descriptor (see FIG. 15, 1505a) contains the segmented address (ie, STN, STE, and SRA) of the semaphore on which the P or V command performs its operation. A process transmits a semaphore address,
Other processes in the system that are waiting for messages to be sent back via that semaphore (IC processes) are unable to access the semaphore because the GD address applies to a wider base than the base of the narrow JP processes on the system. The address of
Given via GD address. In other words, there are two ways to give an address to a semaphore. This is a consequence of the fact that the semaphore and structures external to the semaphore are forced to share an address base with different processes and can therefore be accessed in other ways.

As discussed in connection with FIG. 16, there are two basic semaphores that receive addresses by the P and V commands. That is, there are semaphores without message 1600 and semaphores with message 1602. Here, we will first consider semaphores without messages, and then consider semaphores with messages. Also, the description here is
It concerns a point in time some time after the start of the system. In this case, the structure of the semaphore is
It has reached a certain stage of development as shown in Figures 8 and 17.

When a new process is introduced by the system, that is, when the process changes from a stopped state to a ready state, the name of the process is added to the process link 805a-c of the GO segment 802.
(The mechanism for initializing the process is the subject of Japanese Patent Application Laid-Open No. 117324/1983). This process link is Semaphore PLS90
1, ie, a free process link queue. As a result, the semaphore PLS reference will be changed to the name of the new process and the first link used for the semaphore PLS so that its PLQP points to the next free link in the queue.
For example, the displacement field of PLQP in Figure 18 is 805a
805b. Since the process has already been started and the preparations for controlling the machine's resources have been completed, the link 805a is ready.
Can be placed inside Kyu Q/PR/RDY. However, when process link 805a is placed in the ready queue, it will be placed in LIFO order based on its own priority by the dispatcher. i.e. the head of a given form of Q/PR/RDY in a ready-queue;
Or, at most, it would be number 6.

Once in the ready queue, a process waits its turn until it can take control of the central processing subsystem. Once this control is in place, the process can cause the central processing unit to execute procedure segments that include all communication signals via P or V commands. When a P command is executed on a semaphore that does not have a message, i.e. for a process that requires a signal from another process before proceeding, the system mechanism The address syllable will be used to determine the semaphore. After detecting this semaphore, the STAG field is
0000 and the STC field will be tested to determine if the count is greater than, less than, or equal to zero. If the SCT field is greater than zero, a particular semaphore that does not have a message is
Indicates that a specific related resource is available. In this case, the process obtains the requested resource and can proceed with subsequent operations. First, the process decrements the count in the SCT field by 1 to indicate that it is executing the P command. Next, write the name of the process in the TEP field that occupies the semaphore that does not have a message, indicating that the semaphore is operating as instructed.

Semaphore without message 1600
When the SCT field is less than or equal to zero, it indicates that the resource associated with the semaphore is not available. As a result, a process executing a P command on a semaphore that does not have a message enters the queue Q/PR/S. In other words, the process cannot execute the P command because the resource is not available, so the process takes itself out of service and binds to a semaphore that does not have a message. This semaphore signals the process when the resources it needs become available. Therefore, a process advances from the active state to the standby state by its own act of executing the P command. This is illustrated at 1600 in FIG. In the figure, this situation occurs twice, with two processes waiting on a semaphore with no messages. Looking at the number 1602, the process queue head pointer PQHP is semaphore 160.
Refers to the first process 1720 created from 0,
We see that it now has the next link field pointing to the second process created from the semaphore. This second process has a next link field with a value of zero, indicating that there are no more processes created on the semaphore that have no messages. When a process transmits itself to Q/PR/S, the SCT field is decremented, but since no valid operations are taking place on semaphore 1600, the process's name is not written in the TEP field.

When a process completes a V operation on a type of semaphore 1600 that has no messages, that is, when the process is done using the resource and needs to signal the semaphore that it is finished,
The SCT field is tested again to determine the state of the semaphore.

When a semaphore has an SCT count greater than zero, i.e. when there are resources available or when the count is equal to zero, the count is incremented by one and the resources used by the process are also available for use by other processes. Show that something is true. In this case, the process executing the V command will continue to run.

However, as shown in Figure 17, if the SCT count is less than zero, indicating that there is another process waiting for resources in Q/PR/S, then The abandonment of the first process 17 combined with the semaphore
Pass through 20 and enter Kyu Q/PR/RDY. And in addition to this, the SCT count increases by 1. The dispatcher takes the signal from the semaphore and the process 17 waiting on the semaphore
Place 20 PCBs in ready state. When a process becomes ready, it
Placed on PR/RDY. This queue connects all processes that are ready, or waiting for CPU to become available. Processes are Q/PR/RDY according to priority
It is queued inside. At each priority level, FIFO or LIFO rules apply. Among them, the FIFO law is applied when a process is in a waiting state before being queued, and the LIFO law is applied when a process is in a running state before being queued.
The current process in the running state is then ready.
Tested to prioritize processes at the head of the queue. In this case, you must be careful that the first process of Ready/Queue is
The process may or may not have been waiting on a semaphore that has just been placed in a ready state. Now, when a test is performed to determine which process has higher priority, the running process or the process at the head of the ready queue, the process with the higher priority will enter the running state. . Thus, in FIG. 17, if a V operation is performed on semaphore 1600, the head pointer pointing to process link 1720 will indicate that the process is the one receiving the signal. . Process link 1720 is then placed in ready queue 803, and the SCT count of semaphore 1600 increases to minus one (-1). Furthermore,
Semaphore 1600's PQHP pointer points to process link 1722, indicating that this is the next process to receive a signal when the resource becomes available.

A semaphore of type with message 1602 is
This is shown in FIG. 17 1706 and FIG. 18 1806. When a P command is executed on a semaphore that has a message, the SCT field is checked to determine the state of the semaphore itself. When the count is greater than zero, semaphore Q/M/
It shows the message queue on S. This is the result of a process previously completing a V operation on the semaphore, causing a message to bind to the semaphore and at the same time the count increases from zero to a positive number. Since messages 1708 and 1710 are combined in semaphore 1706, message 1708 is
General command of the current process performing the operation
transferred into the register. In addition to transmitting the content of the message, the message link 170
Since the information in 8 is now free, message link 1708 will be included in the message queue of the free link semaphore. The count of semaphore 1706 decreases by 1 to plus one (+1), and the message queue head pointer changes to message link 1.
710 is changed to indicate that it is the next message to be bound to semaphore 1706. Also,
Since 1710 is the last message in the message link, the message queue tail pointer remains unchanged. However, when the message was added to Q/M/S on 1706,
The SCT field is incremented by one, the message queue head pointer remains unchanged, and the message queue tail pointer now points to the message added by the message link doing FIFO queueing. When LIFO or priority queuing is indicated, the resulting queue will exhibit the appropriate ordering.

When a message link is added to Q/ML/FLS, a test is performed on the FLS semaphore corresponding to the SD segment, generally designated 802n. These tests determine whether a process was waiting on a free message link. Since a message link is freed by the currently running process, if another process is waiting for a free message link, the message held by this other process will be , will be transcribed into the now free Message Link. However, in this example, free message links were available, i.e. 1712, 1714 and 1716.
indicates that is a free message link, and therefore there are no processes waiting for a free message link. Therefore, this step has not been executed.

If the SCT count is less than zero when a P-command or P-command or P-instruction is executed in a semaphore by a message, this means that Q/PR/S has already been established. It shows. This results in the process performing the P operation becoming one of the processes waiting on the semaphore and thus binding itself to the queue. Therefore, in this example, the process is GO
Acquire a free process link from segment 802, attach itself to process link 1802 that is attached to semaphore 1800, and increase the length of the Q/PR/S queue created from semaphore 1800. become. (SCT -5
).

As shown by semaphore 1704 in FIG.
If SCT count is zero, P operation is SCT
Since the count is decreased to minus one (-1) and the semaphore 1704 is changed to point to it, a queue for process Q/PR/S is created from the semaphore. However, it should be noted that this operation depends on whether the process link is available. However, for the purpose of this invention, it is not deemed necessary to state it here.

When a process is performing a V operation on a message semaphore, the process naturally expects to remain operational. However, the process is
must be excluded from the message it contains. This message contains the process name of the process that sent the message in other fields. Therefore, many processes can send information through one semaphore. And if this information is a message rather than just a signal, it is labeled with the sender's name. These messages are therefore clearly distinguishable from each other. The SD segment's memory space 1508 can then be used to store it.

To explain in more detail, when executing the V command, the state of the semaphore 1800 in FIG.
If the SCT field is less than zero, a process 1802b is waiting for a message to be sent. As a result, the message of the process executing the V command, V command, or V instruction is transmitted to the message of the process connected to the semaphore 1800 in which the V command is executed.
It will be written into the PCB indicated by link 1802b. The process that receives the message then calls Lady Q/PR/RDY803.
The current process that went in and performed the V operation is
If it has a higher priority than the process in the ready queue's head, it will continue to run. The count of Semahore 1800 increases by 1 to minus 3 (-3), and PQHP
is changed to point to process link 1802a.

The SCT count is message 17 in Figure 17.
If equal to or greater than zero, such as the state of the semaphore with 04 and 1706, this indicates that no process is expecting the message. In other words, there are messages waiting for a process to combine them.
Therefore, a message given by a currently running process will form a Q/M/S if sent to semaphore 1704 and if sent to semaphore 1706.
If sent to , it will join the already formed Q/M/S. In either case, the first test performed is as to whether a free message link is available from the Q/ML/FLS. In this example, the available free message links are 1712,17
14,1716, a process can send messages via that operation. As a result, the first free message link, 1712, is used to route the message to the free message link. This link is for Semahore's Q/M/
Processes coupled to S, performing V operations, and sending messages will continue to run.
The semaphore that receives the address then uses its SCT
The field count increases by 1.

However, as shown in Figure 18, FLQP
=0,1504 and there are no free message links available, then the process executing the V command cannot send a message. Please note that the free message link is Q/
Even if it is queued on ML/FLS, Q/PR/
It is possible that processes are waiting on the FLS. Now, in such a case, the process must remain in a waiting state until a free message link becomes available.
In this state, process links are obtained from GO segment 802 and coupled to free links semaphore 1504 in Q/PR/FLS 1804. By binding to FLS, when a process attempts to send its message, it will be shown that there are no free message links available. Later, when a free message link becomes available, the process can send its message and is removed from the FLS semaphore. In this way, FIGS. 17 and 18 can be clearly compared. In FIG. 18, the process is bound to the free link semaphore because there are no free message links available. On the other hand, in FIG. 17, it is connected to the FLS semaphore. There are free message links available. Therefore, in Figure 17, the FLQP field points to the first free message link available, whereas in Figure 18, there are no free links available and FLQP is equal to zero. It's summery. In addition, the PQHP field is
Points to the first process bound to the FLS semaphore.

17 and 18 both show one or more semaphores of this message type. Since each semaphore can have waiting processes, there can be many Q/PR/Ss as a result. Each of these is represented by a queue of process links in the GO segment. This is illustrated in graphs 1802, 1804, and 1808 in FIG. These have process links in GO segments that are connected to semaphores. In addition, other SD
The segment (not shown here) also has a semaphore, and processes and
It is also possible that links can be combined.

As mentioned earlier, semaphores have the dual purpose of remembering that either a process waiting for an event in order to continue or an event waiting for a process to join with it has previously occurred. must have the ability to
These concepts are denoted Q/PR/S and Q/M/S, respectively. If we look at the relationship of these queues to semaphore, we can see that the queue of a message on a semaphore and the queue of a process on a semaphore are completely opposite concepts.
A data structure, ie, a semaphore, holds one of these. When a process has finished performing a P operation, and there are no events or resources available to complete the request requested by the P operation, the semaphore forms a queue for the process on the semaphore Q/PR/S. I will do it. Conversely, when an event or resource occurs and there are no processes waiting for this event or resource, a semaphore
A message queue will be formed on the semaphore Q/M/S. Each of these is a semaphore
Indicated by the SCT field. Therefore, if a semaphore's SCT count is positive, it indicates that there are messages waiting for the process and, as a result, a queue of messages has been formed on the semaphore. If a semaphore's SCT count is negative, it indicates that there is a process waiting for a message or event and that a queue of processes has been formed on the semaphore. If the semaphore count is zero, it indicates that there are no waiting processes, no messages, and no queues.

Q/ML/FLS and Q/PR/FLS are usually
Found alone on the FLS semaphore. A free link semaphore has a queue of free message links when there is a message link used by the semaphore in the SD segment. This is a non-zero inside the FLS semaphore
Denoted by FLQP. If a free link semaphore has FLQP equal to zero, indicating that there are no free message links available, then the V operation
FLS as long as message link is requested
will form the queue of process Q/PR/FLS.

Considering the limited number of message links in the semaphore descriptor segment, 1
It will be seen that some device is needed to prevent one message semaphore from using up all free message links. This is accomplished by a semaphore for each message type having a maximum count field, as shown in Figure 16b. This field, bits 4-15, serves to limit the message queue length. In a non-message type semaphore (Figure 16), this same bit 4-15 limits the number of events (V operations) that can be stored using this semaphore. As a result, an exceptional condition will occur if the value of the SCT field causes the message bound to the semaphore shown above to exceed the SMC value. These features not only help manage memory space, but also
This is provided to ensure that a single semaphore does not use up all or most of the free message links available within an SD segment.

General explanation of the P and V directives Previous information on how processes are represented in the hardware (PCB), the states in which the processes are contained, and the dispatcher units used to control the states and movements of the processes, etc. stated. Furthermore, process synchronization functions including semaphore data structures were also shown and described.

It is the operations performed on the semaphore that integrate the dispatcher unit and the semaphore to control process synchronization. When a process uses a semaphore as a signaling mechanism, two basic operations are required on the semaphore. one operation,
The V operation or V command sends a signal to the semaphore. Another operation, P operation or P
The command takes the signal from the semaphore.

The V command can also be viewed as a send operation used by a process running a process that has data and needs to send it to another process or to one of a set of processes. Dew. The V command authorizes a process to send data (ie, a signal or message) to an intermediate point, a semaphore. A semaphore stores its data until it is ready to be picked up by another process. Meanwhile, the process performing the V operation is free to proceed since the data has already been sent.

The P command could also be viewed as a receive operation used by a process that requires data from a particular process or one of many processes. The P command authorizes a process to receive data (ie, a signal or message) from a semaphore. If the data is present, the process executing the P command continues. However, if there is no data stored by Semaphore,
The process executing the P command enters a standby state. In this case, the semaphore holds processes instead of data. The process does not know the reason why the process enters the waiting state,
That is, it is kept in a standby state by the semaphore until it no longer sends data for this process via the same semaphore. This action is performed by the V command.

In this way, data (i.e. signals or messages) from other processes as they proceed
A process that requires a semaphore attempts to obtain the signal by executing a P command on a previously recognized semaphore. Conversely, a process that needs to send data to another process (i.e., a signal or message) as it progresses will attempt to send the data by executing a V command on the semaphore. Furthermore, if the process receiving the data is in a waiting state, the reason for it being in a waiting state is removed. As a result, the V command also acknowledges the process that asked the message to move to the ready state.
In this way, the data sent by the V command will be stored in the PCB of the process requesting the data, and this data will then be transferred by the dispatcher mechanism to bring the process into service. It will be considered when it becomes available.

Since there are two different types of semaphores, semaphores with messages and semaphores without messages, it follows that there are also two types of P and V commands. Each type of P and V command can only be executed on the same type of semaphore. Therefore, each command must be directed to a semaphore with the correct tag bit. That is, P and V commands that have a message must be directed only to semaphores that have a tag bit that classifies them as message semaphores, and P and V commands that are directed to semaphores that do not have a message must be directed to those semaphores that do not have a message. Messages shall be directed only to semaphores with tag bits that classify them as semaphores. In addition to these, both message type P commands and non-message type P commands are also executed as P test commands. A test command allows a running process to continue even if the command's intended action does not take place. Therefore, there are four P commands. A V command with a message requests that LIFO or FIFO queue, and is also executed by a V test command. As a result, there are four V commands with messages, and there are also V commands without messages, so there are five V commands in total.

The symbols below are shown on the flow diagram and are used to explain each of the commands above.

SEP P command on non-message semaphore. The directive picks up the signal from the semaphore or puts the running process in a waiting state and
Either create a queue on PR/S.

SEPM P command on message semaphore. The command either picks up the message from the head of the semaphore's Q/M/S or causes the running process to wait and queue on the Q/PR/S. When the message is retrieved from the Q/M/S, the message link is returned to the Q/ML/FLS and the count field in the FLS semaphore is checked. When the system detects that there are waiting IO processes (logical channels),
A free link is immediately left available for performing AV-type operations. I.O.
If there are no processes, a check is made to Q/PR/FLS for waiting processes. Also, a certain process is free with Q/PR/FLS.
Once the process is found waiting for a message link, it is returned to the ready state and is allowed to execute V commands on the FLS semaphore.

SEPT P test on non-message semaphore. This is the same directive as SEP, except that it does not put the running process into a waiting state when the signal from the semaphore is unsuccessful.

SEPTM Test directive on message semaphore.
When the signal from the semaphore was unsuccessfully acquired,
It is the same as SEPM except that running processes are not placed in a waiting state.

SEV V command on non-message semaphore. This command conveys the signals listed in the semaphore. When a semaphore has a queue of processes Q/PR/S waiting for a signal, the first process in the queue receives the signal and moves from the waiting state to the ready state.

V command on SEVF message semaphore SEVL. Each command sends a message to a semaphore. When a semaphore has a queue of waiting processes, Q/PR/S, the first process in the queue receives the message and moves from the waiting state to the ready state. if,
Without Q/PR/S, the message is Q/
FIFO (SEVP) or LIFO during M/S
(SEVL). if,
If there is no Q/PR/S and no message link can be found to queue the message, the running process enters a waiting state and the Q/PR/S
Added to PR/FLS queue. The command counter of the process executing the V command remains at its current count, allowing the V command to be attempted again when the process becomes operational again.

V test command on SEVTF message semaphore SEVTL. These directives are
Same as SEVF and SEVL, except that the process executing the V command is not put into a waiting state even if no free message link is found in the free link semaphore queue. .

All of the execution instructions described above enable control store unit 130 to perform a predetermined set of functions. Various functions are displayed in the flow charts of FIGS. 20 to 26. The execution of these functions is carried out by the dispatcher unit (14th
The same operating components as described in connection with Figure 1) and shown in Figure 13 are utilized. In order to make it easier to understand how the entire information is transmitted, only the main blocks of the operating unit are shown. In addition, to avoid repetition and make it easier to understand, we have also included the controls related to the P and V commands.
The intermediate functions of the store unit and central processing unit have been omitted. However, it must be understood that intermediate functions such as those described in connection with FIG. 14 do exist.

Furthermore, FIG. 19 shows the CPU 104 in FIG.
This is a more detailed diagram of the ALU unit 1315 shown in FIG. That is, FIG. 19a shows the 256
FIG. 19b shows some of the working positions shown in FIG. 19a that apply specifically to the functions of the P and V commands that will be considered. These detailed diagrams are part of the second section that explains the role they play in the overall functionality of the CPU system.
It seems to be easier to understand when viewed in relation to Figures 0 to 26.

Evolution of Semaphore for Both P and V Directives In further detail with reference to the drawings, FIG. Figures 26-26 illustrate various P and V commands and the functions they perform in execution.

More specifically, Fig. 20, block 200
0 illustrates the structure of the semaphore descriptor fetch routine made possible by each of the P and V commands described above. Each directive includes
Operation (op) code for bits 0-7, bit 8
Auxiliary codes from 11 to 11 and bits 12 to 3
1 20-bit address syllable. The OP code has the role of indicating to the system the type of command, ie, P, V, or a variant thereof. The auxiliary code indicates detailed information about the command. For example, whether it is queued for LIFO or FIFO, whether it is a test command, etc. Check the semaphore descriptor for the address syllable. In order to solve the address syllable, the operating process must be completed to select the PCB.
The entire structure of the address table, including the JP numbers, must be examined (see Figures 4 and 17). Next, we need to examine the STN and STE values to find the segment table. Then, to find the last segment relative address within the segment, one must perhaps examine indirect addresses and finally perform an indexing operation if necessary. In this way, the P or V command will progress into the address of the semaphore descriptor.

In addition to fetching and testing the semaphore, subroutine 2000 also fetches the addressed semaphore to allow branching to a P or V command to be executed on the semaphore. Thus, prior to execution of SF subroutine 2000, the OP code and auxiliary code will be analyzed to determine which semaphore descriptors should be fetched. step 200
1 asks if the hardware gate has been unlocked. This hardware
The gate is part of the hardware control data 1313, and when locked indicates that the system is in a critical state. When a firmware operation of a process or queue is occurring, the operating system is in a critical state because there is a risk that irrecoverable information a will be lost in the system if an interruption occurs. Therefore, when a hardware gate has a value of 1 indicating the process is moving, and the queue is moving forward, some commands, including P and V commands, may prevent the execution of these operations. It will not be executed because there is If the answer to question 2001 is yes, the hardware gate is locked and step 2002 is executed. This results in a system check, which essentially detects any exceptional conditions that would normally cause the current operation to be aborted and a central exception mechanism to be introduced. detect and initiate a model dependent diagnostic sequence to prevent the system from continuing to operate in a bad condition. Additionally, if IFHG = 1, any attempt to perform a synchronization, or any process control command that attempts to replace the currently running process, will cause a system check in step 2002 to be initiated. ing. The hardware gate check in step 2001 is also the system check in step 2002.
The check is also carried out by the command fetish unit 131.
This is done by hardware located within the 8.

Steps 2003 and 2004 are hardware tests also performed within command fetch unit 1318. In step 2003, a question is asked whether the SECIN command described below is being executed. This SECIN directive must have a process ring number equal to zero for execution. As a result,
If the answer is yes, step 2004 will test the process ring number of the command. If the ring number is not zero, privileged command exclusion 2004a occurs. However, regarding the P and V Directives, Question 2003
The answer is no, so step 2005 asks whether it is necessary to index the address syllable of the P or V command.
will be executed.

At this point, the normal evolution of the address syllable of the command is all occurring. Therefore, the segment relative address SRA and the segment number SEG mentioned above have already been determined. The question asked in step 2005 is whether one bit in the address syllable points to indexing. If the answer is yes, step 2006 adds the contents of the general register indicated by the address syllable to the SRA. In step 2007,
The first word of SD segment 1500 is transferred from main memory to scratch pad memory location WC0 in FIG. 19b. This first word contains the tag and ring fields for the P and V commands and determines whether they are executed or not. It should be noted here that the fetch operation is performed from the main memory 102 to the data management unit DMU 13.
12, and proceed to Arithmetic and Logic Unit (ALU) 1317. On the other hand, the main memory/filling operation is performed by ALU131.
7 to DMU1321, then main memory 1
Head to 02.

In step 2008, to confirm that the correct semaphore segment was accessed,
Some preliminary checks are performed by ALU 1317. To be more specific, step 200
8, the segment descriptor's own GS bit must be equal to 01. G represents a gate segment, and S represents a semaphore segment. Therefore, the semaphore segment bit must be set to access the semaphore segment. Also, STN is 8
A check is also made for greater than or equal to. This is because semaphore segments are small segments that have this restriction. (Regarding this point, please refer to Japanese Patent Application Laid-Open No. 50-42752, which is related to the development of segment addresses mentioned earlier.
(See publication number). The third check in step 2008 is whether SRA is a multiple of four. This is because the SRA is a 4-byte word-aligned descriptor. If the GB bit is set to 01 and STN is greater than or equal to 8, step 2
As shown at 008b, illegal system object subroutines are enabled. Step 20
Unless otherwise indicated, all tests are performed on ALU 1317 as shown in 01-2004.

In step 2009, the first word of the semaphore segment (SD), word 1500 in FIG. 15, is tested. This word is verified in the segment descriptor that was just tested. Specifically, bits 0 and 1 of the tag field are tested and coded to 11. Bits 8 to 15 of the MBZ field are
Tested for all zeros. And bits 16 to 30 of the FLSP field are
Tested for multiple of 8 (last 3 bits are zero). If the state of this data structure does not match well, proceed to Step 2009.
SD segment is indicated. Otherwise, the data structure is normal, and the next step 2010 is executed.

After locating the SD segment and determining whether the first word is correct, the location and contents of the semaphore descriptor in main memory are examined. That is, step 2010 verifies that the SRA developed in step 2006 is less than FLSP, bits 16-31 of word 1500. This condition is shown in Figure 15.
This is required due to the structure of the SD segment. As mentioned in that section, the semaphore descriptor addressed with the relative offset of the SRA is
It is created internally. FLSP will then point to block 1504 at a sequentially higher address in main memory than the semaphore descriptor of block 1502. As a result, the SRA developed from the address syllable of the P or V command must be checked against one of the semaphore descriptors in block 1502. This should be designed to be smaller than the relative address FLSP that matches block 1504. FLSP therefore has two purposes. One is to determine the position of the free link semaphore, and the other is to determine the upper limit of the semaphore descriptor 1502.
When these conditions are met, step 201
0a is executed. This step is an exception subroutine that indicates that an illegal system object address has evolved. step 2010
also performs a ring protection check, which, as mentioned earlier, is the subject of Japanese Patent Application Laid-open No. 114934/1983. Now, in this way, the EAR field is XR
Checked for less than or equal to field. At this time, XR confirms the first word 1500 and selects V command, P command or
Depending on which SECIN directive is being executed, it will be either VR, PR or IR. If the segment's ring number, the EAR number, is greater than the individual ring protection field, the exception condition of step 2010b is executed.

In step 2011, semaphore descriptor 1502 is inserted into SD segment 8 of main memory.
Fetched from 02n, scratched and padded.
It is transmitted to memory 1900 at location WC1. In step 2012, the semaphore descriptor 150
A series of tests for 2. These tests are substantially the same as those for segment descriptors in step 2008. These tests bits 0,1 which must be equal to 01 in the tag field. Bit 2 must be equal to 00 in the ring field,
3. Must be greater than or equal to 8
STN bits 4-7 and SRA field bits 16-3 which must be a multiple of 8
1 is carried out. Semaphore descriptor 1
The SRA field at 502 indicates the semaphore being addressed. Since the semaphore is double word size, it must be on a double word boundary, which means it must be a multiple of eight for address purposes. If any of these tests are unsuccessful, exception subroutine 2012a is executed to indicate that the format of the illegal segment descriptor has been determined. Since the exception subroutines are associated with unsuccessful tests that the system must correct, these conditions will not be discussed further.

Now, once the correct segment descriptor has been determined, the next step is to acquire the actual semaphore itself. Step 2013 asks if the semaphore segment number is in associated memory 1319a of address control unit 1319. This question is asked because the semaphore word is fetched from main memory. However, if it is not in associated memory 1319a, then the main
Memory does not need to be accessed. Therefore, if the answer to question 2013 is no, step 2014 enables subroutine SDF to place the segment descriptor into the associator. The actual mechanism of this transmission was published in Japanese Unexamined Patent Publication No. 52
This is the subject of Publication No.-85426.

In step 2015, the new segment
The test is again made to see if the GS bit is equal to 01. Under normal conditions, a semaphore descriptor matches a semaphore in its own SD segment. However, it is possible that this condition does not exist and the semaphore descriptor is
It is possible that the SD segment has been fully matched and a test is made to see if the GS bit is equal to 01.

In step 2016, a test is performed to determine whether the write permission WP bit mentioned above is equal to 1, indicating that writing into memory is permitted. In step 2017, the write bit (W bit) in the segment descriptor is tested to see if it is equal to one. If the answer to this question is yes, then step 2.
020 is executed. If the answer is no, step 2018 is executed which serves to call the subroutine WUP which writes to and updates the W bit. This is done because a write operation is performed on memory, so the W bit must be updated if it has not been done previously. All these operations are performed on the semaphore descriptor 1502 mentioned earlier.

It has already been mentioned that there are two ways in which a semaphore can be addressed, one of which is via the P and V commands. Another way to address a semaphore is step 2019
If this is used, an evolution process or flow chart is entered at this point. Another method of this is an IC or system device addressing a semaphore that provides an absolute GD address. In any case,
Whichever method is used to address the semaphore, step 2020 fetches both words of the semaphore. These words are
It is fetched from associator 1319a and transmitted to scratch pad memory locations WC4 and WC5. From these locations, ALU 1317 performs various tests on the semaphore.

However, before these tests are performed, step 2021 tests the operational code and auxiliary code of the command to determine if it is a SECIN (initiate semaphore account) command. If this is the case, a branch is executed to a subroutine that enables the SECIN directive, but we have already mentioned that this is the subject of a separate patent application. If not, ie, this is a P or V operation, step 2023 tests the semaphore's stag field.
This stag field is shown in FIG. 16, which represents the various semaphores operated by the P and V commands.

In step 2024, the SCT field at location WC4 of the semaphore is incremented by one and stored at location WC7. This is one promising step that arises from the fact that performing V operations is more critical to the operation of the system. 2
By performing the incremental step in 024,
The timing involved for V operation will receive help. If this prediction step is incorrect, the subroutine handling the P operation will correct this condition. In step 2025,
V operation will be performed, therefore,
Anticipating that the SCT needs to be checked against the SMC, the SMC field is set to ALU131.
Placed within 7. Additionally, a flop in the arithmetic and logic unit 1317a called PMO is set. This flop indicates that neither P-operation nor SCT is equal to zero. If this state does not exist, it will be changed later.

At this point, the task of setting up the P or V command is complete. Step 20
At 26, the commands in the IFU unit 1318 are tested to determine if the operating code and auxiliary code indicate a V operation. If the answer is yes, a branch is taken to V command sequence 2027; if no, P
A branch is taken to command sequence 2028.

As a result, the subroutine 2000 in FIG.
is the first word 15 of segment descriptor semaphore descriptor segment 802n
00, semaphore descriptor 1506 and the actual semaphore 150 on which the V or P operation is performed.
This means that 6 was fetched and checked. Therefore, all the necessary preliminary work to correctly execute these commands has been completed, and the firmware indicates that the commands will be executed correctly.

P Command If step 2028 of FIG. 20 were executed, the next set of functions would be as shown in FIG. Specifically, FIG. 21 shows both the overall function initially performed in accordance with the P command and the function performed in accordance with the P command on a semaphore that does not have a message.

Since the answer to the question at step 2026 was no, the new semaphore account (NSCT) at step 2101 is set equal to the old semaphore account minus one. This is a result of the P operation requesting data and therefore the semaphore account should indicate that there is one less data than is on the semaphore. Therefore, the old SCT field stored at location WC4 will be restored rather than the increased SCT stored in scratch pad memory at location WC7. This SCT is then decremented to create a new semaphore account NSCT that is written to scratch pad memory at location WC7.

A P Command on a Non-Message Semaphore At step 2102, a question is asked whether this is a P operation on a non-message semaphore. This is a result of all P operations being first analyzed by subroutine 2028. In step 2012, the operational and auxiliary codes for each of these commands are again
Tested with IFU1318, Figure 22 and PM
Determine whether a branch to subroutine 2103 should be made. This branch is taken if this is a command for a semaphore that has a message. If the test indicates that the command is for a non-message semaphore, the remainder of the PNM subroutine is performed.

Assuming the answer to the question at 2102 is yes, the data requested by this P command is a signal indicating the availability of a resource, such as a tape drive or magnetic disk. . Step 21
04 checks the SCT field of the semaphore that has no message and asks whether the SCT field has a value less than or equal to zero. If the answer is no, that is, the semaphore account is greater than zero, indicating that resources are available for the process executing the P command, then steps 2105-2
114 is on a semaphore that does not have a message,
Indicates that the P command was executed effectively. Specifically, step 2105 tests the PQHP field of the semaphore that does not have a message, ie, bits 32-47 of semaphore 1600, and determines that it is equal to zero. If this condition does not exist, an illegal semaphore exception 2105a condition results, and the control storage unit handles this exception condition.

Step 2106 asks if this is a P command. As previously explained, test directives can keep a running process running at all times. Under the current conditions, the test directive sets the condition code and then sets the non-test directive to receive the resource, since the necessary resources are available from the semaphore and the non-test directive will effectively execute. It will function as a test directive. This is illustrated in step 2107, where the SCT field is tested for a value of one. If this condition exists,
As a result, step 2108 allows a zero condition code to be transmitted to status register 1311. If the SCT field is not equal to 1, this is confirmed in step 2104.
Since we have determined that the SCT field is greater than zero, this means that the SCT field must be greater than one. In this state, step 2109 is executed where a condition code is set to 2 in status register 1311 to indicate that one or more signals are available.

In any of the above cases, whether this is a test P command on a non-message semaphore or not,
Or whether it is just a P command on a semaphore with no message, step 2
110 is executed. Since the SCT count of the P command is positive, it can be seen that the P command will be effectively executed on the semaphore because of the further steps. Therefore, this step can be said to create scratch pad memories WC4 and WC5 containing information that will eventually be written into main memory. This means that
This indicates that the process currently using the resource associated with this semaphore is the process with the JP name in the TEP field. Currently progressing in step 2101
The NSCT field has been written from the WC location as an SCT into the scratch pad memory at the WC4 location. Therefore, the updating of the two fields indicating that the P operation was successfully performed has been completed.

At step 2111, the hardware gate is locked, indicating that a critical operation of the system involving an indivisible operation has occurred. In step 2112, a valid P command is indicated and the WC
4. The updated field of the semaphore written to the scratch pad memory at location WC5 is transmitted to the SD segment in main memory 102 via DMU 1321. These fields replace the semaphore's previous fields. At step 2113, the hardware gate is unlocked, indicating that the critical condition has ended and command counter 1312 has been incremented. In this way, the next command of the execution process (CUP) is executed.

If the SCT field of a semaphore with no message indicates less than or equal to zero as the answer to step 2104, a branch to step 2115 occurs. In this state, it is addressed by the P command of the process being executed. Semaphore has no resources at all. As a result, P commands requesting resources are not effectively executed. Depending on the P command, the running process is either placed in a waiting state, where it must wait until the semaphore receives the resource, or, if it is a test P command, it is allowed to continue.

In step 2115, an inquiry is made as to whether the SCT field is equal to zero. If equal to zero, this means that there is no message or process bound to the semaphore that has the message, so step 2117 tests to ensure that the process queue head pointer is equal to zero. Do this. If the SCT count is not equal to zero, this means it is less than zero, indicating that there are processes bound to the semaphore that have no messages. In this case, step 2116
is executed and PQHP is not equal to zero. At the same time, you can check whether it is a multiple of 8. PQHP is
It is not equal to zero because it determines the first process link attached to this semaphore. Since the process link connected to a process is 8 bytes in size,
PQHP will be a multiple of 8 so that it points to the first byte of the process link that holds information about processes waiting on the semaphore.

If these tests are successful, the semaphore is known to be suitable. Step 2118 asks if it is a test P command that is being executed. If so, as indicated in step 2119,
A condition code of 1 is set. This condition code indicates that if the P command had been executed, the executing process would have entered a waiting state. In addition, the JP name of the last process is
Step 2120 is executed to determine whether a P operation was validly performed on that semaphore that does not have a message. What should be noted here is that the executing process does not write its JP name in the TEP field of the semaphore 1600 because no P operation was validly performed. However, the name of the last valid running process that performed a P operation on this semaphore is not remembered since this process holds the requested resource by the currently running process. There will be. Next, Semahore's
The J and P names in the TEP field are written into the general register O (GRO) of the currently executing process. This is indicated in step 2120 by the JP name written in the last 16 bits of the GRO of the currently executing process. The first 16 bits contain all zeros inserted. If the process running the P test directive has a higher priority than the process that has the resource and its name in the TEP field, the current process will cause the process using the resource to abort. It will be decided to. In either case, however, the command counter 131
2 increases and as shown in step 2114,
The next command of the lagging process that completed the P test command is executed.

If this is not a test command and the OP code indicates during step 2118 that this was a P command on a non-message semaphore, put the currently running process into a wait state.
Subroutine E of VP2121 is executed. As a result, the currently running process is no longer running and its process link with J,P name becomes attached to the semaphore addressed by the P command.

Step 21: Put the current process into standby state
Before considering 21, let us consider the branch subroutine PM 2103 from the question in 2102. This is because this subroutine calls the subroutine for the P operation on the semaphore with the message. The subroutine also executes VP2121 when the process that executes the P command on the message semaphore is placed in the standby state.
Branches to E. Now, E of the VP subroutine 2121 will be explained.

P command on semaphore with B message.

In step 2102, if the operation code indicates that the P command is on a semaphore with a message, then FIG. 22a and step 2
A branch to 200 is taken. In Figure 20, the semaphore has already been fetched and remains at positions WC4 and WC5 in the macrolatch pad memory. At step 2200, an inquiry is made whether the SCT field, bits 16-31, is less than zero, ie, whether the process is bound to the semaphore with the message shown at 1602 in FIG. If SCT
field is an arithmetic and logic unit 1317
, then step 2201 tests the PQHP and MQTP fields in the semaphore containing the message to determine that it is correct. More specifically, the message queue tail pointer
MQTP, bits 48-63, must be zero because it is a message, not a process, that is bound to this semaphore that has a message. Bits 32-47
is the process queue head pointer that identifies the first process bound to this semaphore, and these 16 bits are tested both for not equal to zero and for a factor of 8. . The previous test was done to ensure that the 2-word process ring was bound to the semaphore, and the latter test showed that the process link was showing the first byte of the 2-word process link. It's something. In this way, 2201
Through these tests, Semaphore Q/PR/
There is a queue of waiting processes on S.
The indication that the SCT field is less than zero is verified to be correct.

In step 2202, a question is asked whether this is a test P command on a semaphore with a message. Since the test command cannot place a running process into a waiting state, the same situation that occurred in step 2118 of FIG. 21 results. As a result, the status register 131
1 is set to a condition code of 1, and a P command on a semaphore with a message is not executed;
The command counter of the executing process is incremented by one (step 2203) to indicate that the next command of the current process may be executed (step 2204).

If the P command on the semaphore that has the message is not a test command, then the running process that initiated the P command will request the message. However, since there are no messages available, the currently executing process is required to wait for a message, and therefore subroutine E of VP 2121 places the executing process into a waiting state. This is also shown in FIG.

C. Placing a running process in a waiting state VP subroutine E is called when the current process cannot continue its execution and must be placed in a waiting state. Therefore,
The two situations described above, including a semaphore without message 1600 and a semaphore with message 1602, are treated the same because Q/PR/S is formed. Later in the discussion of the V command, it will be shown that the VP subroutine E is also called when no free message link is available. In this state, the process cannot propagate messages and therefore has no free message link Q/PR/
It is placed on a queue in the FLS semaphore 901 waiting for FLS. All of these conditions occur within firmware performing the same function, as shown in FIG.

More specifically, since the running process that is about to be placed in the standby state is currently in the running state, the process link is removed from the PLS semaphore, as shown in Figures 16C and 18. must be acquired. In Figure 18, G0
PLS semaphore 901 in segment 802 points to process link 85a, which sequentially indicates the remaining process links, so that all process links are coupled to process link semaphore 901. It is shown what is in the queue. In step 2301 of FIG. 23a, the APLS subroutine is accessing process link 805a that is coupled to PLS semaphore 901. APLS
The subroutine is shown in Figure 23C.

With reference to FIG. 23C, the first step in the APLS subroutine is PGO subroutine 2321.
access. The G0 subroutine shown in Figure 23d advances the address of the PLS semaphore 901, which is constant since the PLS semaphore is always the first word in the G0 segment. The first step in the FGO subroutine 2330 is to send the firmware to address ie G0.
Indicates that a segment number will be created that determines the location of the PLS semaphore within the segment descriptor. This is accomplished by selecting a register in the scratch pad memory at location WC9 and creating a 12-bit number as described below. The first four bits are
It is set equal to 0111 to indicate a G number, and the last 8 bits are set to zero to indicate a G number, a segment. Therefore, this segment number indicates the position of the PLS segment within the G0 segment. This segment number is then stored in federated memory 1319a at step 2331.
and the federated memory stores the segment descriptor for the segment number and, as a result,
Determines whether it contains the mogment's base address. As previously mentioned, the Associator is a fast access memory that prevents the system from having to go to main memory to fetch information. In step 2332, an inquiry is made whether the bit was created, ie, whether the federated memory 1319a contains the segment number created in step 2330. If the federated memory does not have this address, step 2333 asks if the bit written in the segment descriptor has been set. This test is performed because, in the current state, the current process is queued on the semaphore, and therefore it is necessary to write specific information, such as the point of the next link. The written bits have already been mentioned. If the written bit is not yet set, a branch is taken to the SGW subroutine, which causes the W bit to be written to both federated memory 1319a and main memory. However, if the written bit is set, there is no need to write it and therefore step 2335 is executed.

If the Associator does not contain the segment number created at step 2330, that is, no branch is taken at step 2332, then subroutine FGSG 2336 is executed and the Associator is placed with the segment number created at 2330. The next time the segment number entered is checked against the associator 1319a, a hit condition occurs. This subroutine sets the U and W bits of the segment number in both the Associator and main memory.

In all cases, step 2335 is executed;
Set up the segment base and segment limits for future use. This step transmits the segment base address and segment limit of the segment descriptor currently located in the Associator's memory to the active registers of address control unit 1319. Segment limits determine the end address of a segment in memory. Segment exception routine exclusion occurs when the address drawn is greater than the resource limit.

Upon completion of step 2335, the process shown in FIG. 23C is completed.
A return is made to the APLS subroutine. Next step 2323 is executed. However, it should be noted that step 2322 is a variation of the APLS subroutine that does not require a call to the FGO subroutine. This condition occurs when there is no need to use the FGO subroutine because the address of the PLS semaphore has been previously accessed. Using one of the APLS subroutines, step 2323
The PLS semaphore is transmitted to arithmetic logic unit 1317 where some testing is performed. In step 2324, the PLS semaphore 9 shown in FIG.
A check is made on the two words 01. Therefore, the STAG field or bit 0
The SMC field, or bits 4-15, is checked to determine that they are all zeros, and the MBZ field, or bits 16-31, is checked to determine that they are all zeros. and also points to the following process link:
The PLQP link must be a multiple of 8, since all process links are 2 words long, and it must be non-zero, since PLQP points to the first byte of the process link. is checked to determine.

If these tests are successful, step 2325 tests the access to the first process linter on the process link semaphore by performing an 8-byte memory fetch of the link. If this link is not in the correct memory, this memory fetch will result in an exception. If the test is successful, the absolute address of the link is stored in scratch pad memory at location W30. if,
When the PLQP pointer is zero, it indicates that no process link is currently available. In other words, all process links present in the system are in a waiting or ready state, and no more process links are available for new incoming processes. When this condition occurs,
Missing Process Link Exception 23
25a is executed. If this very rare event occurs, some existing processes will be suspended to allow the system to utilize the process link. However, if all of these tests are successful, the APLS subroutine is complete and it is possible to return to FIG. 23a and step 2302.

At step 2302, a question is asked as to whether this is a P command. If the answer is no, that is, if it is a V command, the subroutine writes the message header as shown in Figure 15.
MTT2303 is executed. However, in the current state, the answer is yes, so step 2304
Subroutine PRIQ is executed.

The PRIQ subroutine handles processes associated with currently running processes that are placed in a wait state.
Decide on link placement. This placement is done to queue the semaphore based on priority. Priority placement is required for all queued processes, and also for messages on Seahore that have a STAG field indicating priority queueing. PRIQ
The subroutine compares the priority of the process link message link to be placed in the priority of the link queued on Serhoa,
And depending on the type of priority queue i.e.
Check its placement depending on IIFO or LIFO.
The UQLQ subroutine then utilizes the information developed by the PQIQ register to write new links into the queue, as well as modify information for other links as requested.

For convenience of explanation, the PRIQ subroutine will be described when the P command is unsuccessful on the semaphore, that is, when the results are as shown in FIGS. 20 and 21. Additionally, because the PRIQ subroutine 2304 includes many variables, we will also discuss common symbols that do not match the notation results shown in the flow chart, such as the symbol PL in Figures 23e and 23f. Represents a queued link, which can be either a process link or a message link. symbol
QHP replaces queue head, which for semaphore is PQHP or MQHP.
The symbols in subroutine 2304(I) are:
Either FIFO is queued by priority or LIFO is queued by priority so that the auxiliary memory 13
Used to indicate that flop 17a is set for this purpose. The symbol SNL is
This is the next link field for the process link to be entered. As shown below, the acquired process link or message link is inserted somewhere within the queue. Therefore, SNL verifies the next process or the message link that immediately follows. The first link indicator determines whether the new link is placed at the head of the queue or not, i.e. if the first link indicator is still equal to 1 when the subroutine exits, the added process or message link I'll see if one of them will become Kyu's head. ULK represents the process or message link immediately preceding the new ring being added. Therefore, the next link field will need to be updated to confirm the location of the new link being added. The next link field in ULX is verified by SREL, which is the value of the next link field in ULK. As a result, when it is necessary to insert a process or message link in the middle of a queue, the link immediately preceding the newly inserted link is changed to have the value of SREL. In addition, newly inserted process or message links now point to the next link previously seen by ULK.

To clarify the actual changes made possible by the PRIQ2304 subroutine, refer to FIG.
It is necessary to refer to PR/S5. Process links 805a from the PLS semaphore are added to this queue according to priority. For convenience of explanation, process link 805a will be designated by z, and the next link field will be designated by SNL. Also, process link 1808a,
1808b and 1808c are hereafter processed.
Let us refer to links A, B, and C. Therefore, process link A has the following link field pointing to B, and process link B has the following link field pointing to B:
, and the next link field after C will be zero.
Since the priority of process link 2 is the priority of the running process to be put into standby state,
The position of the process link in this queue and other process links A, B, C and semaphore S
The changes made to 5 can be shown.

More specifically, step 2340 of FIG. 23C first indicates that SNL has been set equal to the queue head pointer, ie, the first process link in the queue. The first link indicator is set to one, and then if it is determined that it is not the first link that is being modified, the first link indicator is changed to zero. The current link LK being examined in this case becomes the next link field of process link A. As a result, the first
LK is process link A, and the applied link ULK will also be process link A.

The next question asked in step 2341 is:
The queue head pointer is equal to zero. If the answer is yes, this indicates that there is a free queue and step 2342 has been executed, i.e.
SNL is set to zero, there are no more links on the queue, and the semaphore process queue head is
The pointer indicates the process being added to the queue.
It will be written to point to the link. If the link is a message link, the message queue tail pointer will also point to the message link, which is the only link in the queue. And this is step 23
This is the end of the PRIQ subroutine indicated by 43. Therefore, in this example, link Z, i.e. 8
05a will form the only link among the queues on the semaphore.

However, in the particular situation described above with respect to semaphore S5, there are three process links coupled to this semaphore, so the answer to the question at 2341 is no. As a result, the first word of the process link, word 0, is fetched. In step 2345, a question is asked whether process link Z's priority is less than process link A's priority. If the answer to this question at 2345 is yes, that is, if process link Z has the highest priority in the queue, this means that process link Z is placed in the body of process link A. show. Now, the location for the process link has been determined. As a result, subroutine UQLK or WDB, WDC,
The semaphore will be updated by fetching the information written in the scratch hard memory to the WDD and WDE locations.

However, if process link Z's priority is less than process link A's priority, step 2346 is executed. The question asked in step 2346 is that Z's priority is
The question is whether the priority is equal to A's priority. If this condition occurs, step 2347 is followed by step 23.
Query whether the parameter set to 04 is equal to 1. If this I parameter is equal to 1, this would indicate LIFO queuing, and the same priority level means that last in first out will occur.
As a result, link Z is placed at the head of the queue, step 2343 is executed, and the subroutine ends. However, if the parameter is not equal to 1, indicating that FIFO queuing or fast-in-first-out is to be performed, then step 2348 will be executed. What should be noted is that the process link Z
If the priority of process link A is greater than the priority of process link A, then no path is indicated from step 2346 and step 2348 is automatically executed.

Thus, for both the FIFO and the low priority queuing step 2348, the question is asked is the next link equal to zero? This concerns the next link field of A. If the answer is yes, this would indicate that there are no more process links attached to the semaphore's queue, i.e. there is only one process link A attached to the semaphore. . As a result, the Z process
The link is joined to the A process link and becomes the new link end of the queue. If this condition occurs, step 2349 will write the information in scratchhat memory to the locations WDB, WDC, and WDD written by the UQLK subroutine. The information stored in this step 2349 is as follows. Z's SNL will be set to zero since there are no more links on the queue. A's next link field, SREL, links it to process link Z
receives a value pointing to. As a result, SREL
becomes PL. Additionally, the first link is changed to zero to indicate that the first link of the queue cannot be changed. First, Semaphore's MQTP will create a Z message link if this is a message link.
The link is changed to indicate that it will be the last message link. However, in this particular example being considered, Z is a process link and not a message link, and therefore MQTP
will remain at zero. This means that the federated memory 1 indicates whether the process is placed in a waiting or ready state, or whether a message is to be added to the queue.
It will be indicated by another blob in 317a. The end of PRIQ is indicated as 2343.

However, if the Next Link field is not equal to zero, which is the current state since there are process links B and C to be tested, then step 2350 is executed. To keep track of the various links currently being referenced, link A, which is LK, is currently
The next link, link B, has been changed to ULK and is now changed to LK to indicate that process link B is the one currently being examined. In step 2351, process link B
The first word of is fetched from main memory and transmitted to scratch pad memory location W32. Then, the next link field of process link B is checked and step 23
As shown in 51a and 2351b respectively,
Determine if it is a multiple of 8 or if it is within the G ₀ segment. If these conditions are met, step 2353, Figure 23f, is executed. In this step, process link Z's priority is compared to process link B's priority. If the priority of process link Z is less than the priority of process link B, step 2353
is before process link B, before process link A
Indicates that it is placed after. As a result, the information is written to scratchpad memory locations WDB through WDE, as shown at step 2349, and subroutine PRIQ is completed at step 2343. Therefore, the A next link pointer will point to process link Z, and the next link pointer of process link Z will point to process link B. This is accomplished as follows. The next link field of SNL or Z receives the value of VLK or the location of process link B. Therefore, process link Z will now become process link Z.
It will now point to link B. The link field of SERL, A, receives the value of RL, the location of process link Z. In addition,
PQHP, MQHP and MQTP remain unchanged.

If the priority of process link Z is greater than or equal to the priority of process link B, a branch to step 2354 is taken. This is the same as step 2346, just as the question of whether priority is equal to step 2355 is the same as step 2347. Therefore, if the priority of Z is equal to the priority of B in the answer to question 2354, and if the flop of ALU 1317a indicates that LIFO queueing should occur, then step 2
353 is executed and the information is written into scratch pad memory. However, if the value of I is set to zero to indicate FIFO queuing, or is less than the priority of Z, step 2348 is executed. This is a return to step 2348 leap to determine if the process link is the last link in the queue. However, if this is not the case, process link C is fetched to step 2350 and field updating occurs again as previously described. Therefore, when the priority of process link Z is determined in relation to other links in the queue as shown at 180a, 180b and 180c, the temporary register is placed in the scratchpad memory location WDB. The WDE receives the appropriate information, which is then written into main memory by the UQLK subroutine.

Thus, the PRIQ subroutine determines whether a process link has Q/PR/S or Q/PR/FLS in the queue, or a message link has Q/M/S or Q/ML/FLS. Determines whether it is placed in the queue. The PRIQ subroutine stores this information in temporary registers in scratch pad memory. These temporary registers are later used by subroutines.
Collated in UQLK, the information is then written into main memory condensing with all links in the queue, thus establishing a logical sequential order.

Upon completion of the PRIQ subroutine, a return is made to E of the VP subroutine 2121 in FIG. 23. Next, step 2305 is executed. Step 23
In 05, acquired earlier from G0 segment, JP
name, priority, and currently running processes.
Process link 805a with SRA value
is the process link 805a in main memory.
will be written to.

After acquiring a process link, the information available to the currently running process must be stored so that no loss of continuity occurs when the running state is re-entered. Therefore, the next step to take is to actually store the current information available to the running process. This is illustrated in Figure 23g in step 2360 pointing to subroutine RILO.

The RILO subroutine carries current information to the PCB shown in FIG. In accomplishing this, step 236, which is subroutine URUA,
0 is executed. This is an accounting subroutine that updates the running time of a process that is about to leave running. The URUA subroutine indicates the amount of computer time used and therefore the amount to be credited to the customer.

Steps 2361-2368 enable the contents of the general registers in central processing unit 104 to be transferred to the previously mentioned PCB. That is, step 2361
transmits the contents of status register 1311 to process control block world 4.
Step 2362 stores the contents of T register 1310 in process control address 28. Step 2363 calculates the segmented address of the next instruction and stores it in register 131.
2, and transmits this segmented address to the process control block address 32 shown in step 2364. 1 in step 2365
Base registers, shown generally at 308, are transferred to process control block addresses 52 and 80. Step 2366 is 1
The general register shown at 307 is stored at process control block addresses 84 to 144.
Transmit to. In step 2367, the PCB's movable byte is accessed and tested to determine if scientific movability was used. If so, scientific register 1309 indicates that the process
Control block address 148 to 1
76, the storage of the current information by the subroutine ends. However, if there is no scientific mobility, it means that the PLLO subroutine has already completed. Therefore, the current state of the running process, ie, the process that has been in the running state and is currently being moved to the standby state, will be transmitted to the process control block. Once the process makes available the information requested via the P directive,
The process is then placed back into service and there has been no loss of continuity.

After the transfer of information to the process control block is complete, subroutine E of VP 2121 of FIG. 23a is re-entered. The next step 2307 is to lock the previously described hardware gates to indicate that the critical state of the system has been entered. During this time, in addition to the current process entering a standby state, information in main memory is updated.

In step 2308, the process link 805a obtained from the G0 segment PLS semaphore is unkeyed and released. Step 2309
Now, the process control unit's status byte is changed to indicate that the process is not currently in the executing state, but is instead in the waiting state. This is in PMW number 0, shown as byte 3 for process control block address 0 in FIG.
In step 2310, the process control block address or PMW number 2 word contains the segment relative address and the segment number of the addressed semaphore written therein. This provides the PCB with the information it needs to find the location of the semaphore on which the process is waiting. (For other detailed explanations, please refer to the patent application regarding start and suspend commands.) After that, step 2, which is a UQLK subroutine,
311, Figure 23h is executed. Before that,
The PQIO subroutine indicates where the process link is placed in the queue on the semaphore. The UQLK subroutine performs write operations to update main memory to reflect the state of the system.

Step 2370, shown in Figure 23h as the first step of subroutine UQLK, selects the next link of process link 805a to be entered.
Field SNL is transferred from scratch pad memory location WDB to the next link field in main memory. , step 237
1, the first link indicator is checked to determine if it is 1, ie, if the link to be updated is at the head of the queue. If the answer is yes, step 23
72 is executed to ask if this head process link is the head of ready queue Q/PR/RDY. This question is based on PRIQ and
This is done by using the UQAK subroutine. If the answer is yes, the IQW word mentioned above is changed and step 2373
The location of the process link introduced in is now indicated, and the UQLK subroutine ends.

However, in the particular situation currently being considered, the answer is no, and step 2375 will ask the question, is this a message link? If the answer is yes, then the message
The head pointer is updated at step 2376, and the location of the process link is introduced at the same time, completing the subroutine. Step 2375
If the answer to the question in step 2377 is no, the process link is updated and step 2377
updates the semaphore's PQHP pointer with the location of the process link from scratch pad location W31.

If the answer to the question in step 2371 is no, indicating that the link to be inserted is not at the head of the queue, step 2378 returns the next link.
Transmit the field to main memory, so that the link field next to the link pointing to the entered link is changed to SREL, and the link field SNL next to the entered link receives the PL field. In other words, the process link Z's link added to the queue
Field will receive SNL.
The process link that confirms process link Z receives the SERL. This information includes scratch pad memory locations WDC and WDC, respectively.
Transmitted from WDE. If this is Q/M/S, MQTP will also be updated, resulting in UQLK
The subroutine is complete.

Returning to FIG. 23b, in step 2312,
The SCT field, or FLSC if it is a free link, semaphore, is written to scratch pad location WC4. NSCT
The count has already been determined in step 2101 of FIG. 21 and stored in scratch pad location WC7. In step 2313, the entire contents of the semaphore, as stored in scratch pad locations WC4 and WC5, are transferred to main memory and the semaphore is updated. After completing the modification of this information, the hardware gate in step 2314 is locked to indicate the premature end of the critical condition, and in step 2315 the free gate in ALU 1317a is locked to indicate the premature end of the critical condition.
Set to 0NE to indicate that a running process has been taken out of service. Step 23
At 16, control of the system is transferred to the dispatch unit, which determines the next process to enter service as shown in FIG.

This completes the operation of subroutine E of the VP 2121 that changes the running process to a standby state. Executing processes such as those shown in FIGS. 20 and 21 were attempting to execute a P command on a non-message semaphore or a message semaphore, respectively. Once the process is unable to continue its operation until data is provided to it, it enters a waiting state on its own behalf.

Returning to Figure 22a and block 2200, here the SCT count is tested to be less than zero, indicating that the P command on the message semaphore requested the running process to change to the waiting state; If the answer to this question is no, a branch to step 2205 is executed. Step 2205 asks if the SCT field is equal to zero. If the answer to this question is yes, a branch to subroutine PMZ 2206 shown in Figure 24a occurs.

D Transferring messages without using a queue The PMZ subroutine 2206 is a special subroutine that can be used to transfer messages without using a semaphore.
Operates on a semaphore P instruction with a message when the SCT field is equal to zero. In this case, the subroutine determines whether the previous process is currently waiting for a free or free message link to place its message on the semaphore. This can happen if all free message links have been previously used and there are no longer any free message links to run the process attempting to pass the message. In such a situation, as described below, the executing process attempting to pass the message will be placed in a waiting state because it cannot pass the message. A P-instruction executing current process requesting a message first attempts to determine whether the above situation occurs before placing itself in a wait state. If that situation had occurred, the process that attempted to pass the message would be released from the message, thereby removing the execution blockage, and the current process executing the P command (P command or P instruction) Upon receiving a message, it can continue in the running state. Thus, under this special situation, neither passing the message to the message link by the previous V instruction nor receiving the message from the semaphore by the current executing process occurs, but a hybrid situation results. and there the running process is PCB
Receive messages from waiting processes via . More specifically, in step 2400 of FIG. 24a, the message queue tail pointer MQTP and the message queue head pointer of the semaphore with
MQHP is tested to determine if it is zero. Since the SCT field of the semaphore has a zero value, both of these situations must exist, otherwise an illegal or illegal signal 2400A exhaustion situation exists. Once this is determined, step 2401 executes a subroutine for a free link semaphore fetch (FLSC, shown in Figure 24b). This subroutine takes a free link semaphore and performs a series of tests to determine its status.

More specifically, step 2420 of FIG. 24b
is the first word with a free link semaphore referenced, the semaphore descriptor segment is retrieved from main memory and moved to scratch pad memory location WD2. This first word is shown in FIG. 15 as number 1500. In step 2421, the ALU 137 performs the following tests on this first word. The tag field, bits 0 to 1, are tested to have 11 values, the MBZ field, 8 to 15 bits, is tested to be all zeros, and the FLSP
In other words, bits 16 to 31 are free link semaphore 15 shown in the SD segment layout in Figure 15.
Since it tends to point to the first byte of 04, it is tested and determined whether it is a multiple of 8. Step 2
422, directed by FLSP, FIG. 16d
The free link semaphore shown as 1504 is retrieved. These three words are then stored in scratch pad memory locations WCB, WCC, and WCD, respectively, and subjected to the next test in arithmetic and logic unit 1317. In step 2423,
STAG field, all 3 bits from 0
138 is tested for zero. In step 2424, the CCT field, bits 80 to 95, and the FLSCT field FLS1 shown in FIG.
Bits 16 through 31 of 504 are tested to determine if they are greater than zero. Neither FLSCT nor CCT may be greater than zero. These fields are typically set to zero when there are no free message links available, and can be negative when there are no free message links available.
The absolute values of these fields indicate the process number waiting to receive the process number connected to the free message link, ie, Q/PR/FLS. Therefore, the greater than zero test is to determine whether proper encoding has been achieved for the free link semaphore.

In step 2425, the FLSCT field is tested to determine if it is less than zero because if it is less than zero then there is a Q/PR/FLS connected to the free link semaphore. If the answer is yes, step 2426 checks whether the PQHP field, bits 32 through 47, are equal to zero.
Also, test to determine the multiple of 8. FLSCT
is equal to zero, then this is the only other possible
One thing is that this means that you can use free messages and links. As a result, the free link semaphore's PQHP pointer should be equal to zero, which is the test performed in step 2427. If none of these tests pass, an illegal semaphore exception situation occurs.

In step 2428, SMC field 4
The 15 bits (referred to as the MBZ field in Figure 16C) are tested to determine if they are zero. Free link semaphore cannot store message links, so this is a natural limitation. Only free message links are queued to FLS. As a result, the SMC field is set to zero since the free link semaphore does not wait for a positive value.

In step 2429 of Figure 24C, the free link queue pointer pointing to the first free message link, bits 48 through 63,
identifies the first free message link of length 4 words, so it is tested to ensure it is a multiple of 8. Step 2430 tests to determine if the CCT field, bits 80 through 95, are less than zero. Before, step 242
4, this was tested as greater than 0, but this test indicated by a negative answer that it was equal to zero, and from now on the FLS subroutine 24
The result is the end of 31. If an affirmative answer occurs to question 2430, the MMBZ field, i.e. 64
Step 2432, which tests 71 bits from , is then executed, marking the end of the FLSC subroutine. That is, the FLSC subroutine not only checks the free-link semaphore to make sure it is within the design constraints of Figure 16b, but also checks the free-link semaphore in scratch-pad memory locations WCB, WCC, and WCD. Store the three words for later use.

When the FLSC subroutine of 2421 finishes,
Step 2402 of Figure 24a is executed. Step 2402 asks if CCT is less than zero. If the answer is negative, this indicates that there are no I/O channels waiting for a free message link. In step 2403,
The question is asked whether FLSCT is equal to zero. If not, it indicates that the Q/PR/FLS process is waiting, and as a result, the SPLQ subroutine 2404 is executed.

The SPLQ subroutine is a free process link.
Q/ The current executing process searches for a queue and attempts to execute a V operation, that is, an operation that passes a message to the same semaphore that is executing a P instruction, that is, an instruction that requests a message.
Determine whether PR/FLS has a process. In other words, the message requested by the P command was previously attempted to be passed, but was unsuccessful because the free message link was not available. This situation results when a previously executing process attempts to pass a message to an SD segment that has a free link semaphore. This process is available in free messages
I couldn't do that because there was no link. As a result, this process is placed in a wait state and Q/PR/FLS is
, so that the message is transferred to the appropriate semaphore at some later time. but,
There may be cases in which the current executing process is executing P instructions that may be directed to the same message. Subroutine SPLQ 2404 will determine if this condition resulted.

More specifically, in FIG. 24d, the subroutine
SPLQ refers to each process link connected to Q/PR/FLS, and all process links, that is, each process link 48 to 63-bit field displacement field, is the current executing P instruction. Determines whether it is equal to the displacement field of the running process. If equality is found, that is, if the displacements are equal, the message from the previous executing process is transferred to this current executing process, and the current executing process executing the P instruction remains in the executing state. However, if the displacement is found to be unequal, the current executing process executing the P instruction is placed in a wait state.

In FIG. 24d, step 2440 includes Q/
The flop of the auxiliary memory 1317a, which means that the first link of PR/FLS is referenced, is initialized. This flop determines whether the free link semaphore's PQHP field is changed. If the flop states are the same, Q/PR/
The first process link in the FLB indicates that it has a displacement field equal to the P instruction, indicating that the message was retrieved from it. When the flop state is changed, the PHP of the free link semaphore remains unchanged. Also, in step 2440, the PL and UPL variables are initialized. These variables can be scratch
Padded memory locations W31 and WE8 are written to identify the process link and updated process link, respectively. Initial process to be inspected
For links, both PL and UPL have process
Identify the same process queue pointer of the link.

In steps 2441 and 2442, the first and second words of the Q/PR/FLS head process link, respectively, are brought from main memory to the ALU 1317. In step 2443, the next link field, bits 0 through 15 of the process link, is checked to determine if it is a multiple of 8 since the process link in which it exists is two words long. In step 2444, the process link,
That is, the D field of bits 48 through 63 is compared to the SRA of the current executing process to determine whether they are equal. If the answer is negative, step 2445 asks if the process link's next link field is equal to zero, that is, if there are additional processes with process links connected to the free link semaphore. If the answer is no, step 2446 is executed and the initial link indicator is set to zero, indicating that the free link semaphore does not need to be changed since the head process link remains the same. It can be done. In addition, the updated process links UPL, scratch pad location
WE8 is set to the old PL value and the PL, or process link, is changed here and the Q/PR/
Identify the next link field that will become the second process link connected to the FLS. As a result, steps 2441 to 2444 are executed again in this second process link, and the displacement field contained in the process is set to the segment relative address (SRA) of the current executing process that is executing the P instruction. Determine equality.

Once this condition is discovered, i.e. step 24
If the answer to question 44 is affirmative, step 244
7 is executed and sets the indicator in auxiliary memory 1317a to zero, a process link with the same displacement field is detected, and the updated next link, i.e. UNL, is equal to the next link in the queue. It is set as follows. The UNL field stored in scratch pad location WE9 is removed, but allows the next link field of the previous process link to be changed to match the value of the process link with the same displacement field. Thus, a queue has a series of linked pointers that match all process links connected to the free link semaphore. When this is finished,
Step 244, the end of the SPLQ subroutine
8 is executed. What you need to be careful about is step 24.
47 is to supply information to the UPLQ subroutine, as described below, in order to write new information to Q/PR/FLS.

If the D field of the process link connected to Q/PR/FLS is found not to be equal to the SRA of the current executing process executing the P instruction, step 2449 sets the flop described in step 2447 to 1. Set them together and Q/
All process links of PR/FLS are inspected and P
This would indicate that none of them had the message the command required. As a result, SPLQ
The end of subroutine is executed and the UPLQ subroutine does not write variables UPL and PL to the Q/PR/FLS queue.

Upon completion of the SPLQ subroutine 2404, step 2405 is executed to ask if the process was found. This question necessarily asks whether a process was found that attempted a V command on the same semaphore that the P command requested a message from. If the answer is yes, that is, the flop of step 2447 is zero, step 2406 asks if this was a test P instruction, and if so, returns 240
7 sets the condition code of the status register 1311 to zero, indicating that the P instruction is executed. Regardless of the question asked at step 2406, step 2408 activates the new process, subroutine RNP, which is ready. When a test P instruction or P instruction is executed in this manner, a message is passed to the current execution process that is executing the P instruction. In addition, the process attempting to execute the V instruction is set to a ready state by subroutine RNP2408. Step 2
409 is a transfer step to the dispatcher depicted in FIG.

If there is no process for the question in step 2405, step 2410 asks if this is a test P command. If the answer is yes, a condition code is set to 1 in the status register 1311 in step 2411, indicating that the instruction will not be executed, and in step 2412, the instruction counter 1312 is incremented to stop the counting execution process. Executes the next instruction.

If there is no message-attached semaphore P instruction in step 2410 and the current execution process does not receive a message, the branch to E of the VP subroutine 2121 in FIG. 23a is executed, and the current execution process is placed in a wait state. The dispatcher can then select a new process to put into running state.

In step 2403, if the answer to the question of whether the FLSCTs of the free-linked semaphores are equal is affirmative, then the free-linked semaphore has no process link, that is, no previous process attempted to execute the V instruction. If the free message link is not available, proceed to step 2.
413 is executed and asks if this is a test instruction. If the answer is yes, the condition code is again set to 1 on tap 2414. In addition,
The instruction counter 1312 of the current execution process that is executing the test P instruction is
and the next instruction step 2409 is executed. If the answer to the question of the non-test P command of the message semaphore is negative at step 2413, the current executing process is placed in a wait state as indicated by E in the VP subroutine.

In Figure 24a, the outcome of the response to question 2402 was initially assumed to be negative. However, if the answer is affirmative, thereby indicating that there is a process that wishes to have the message transferred from the I/O device, then subroutine 2416 will be executed. This necessarily means that the message is Q/
It would be the same operation as described in the negative answer, except that it would be sent directly from the I/O device rather than from the LC/FLS. If no message is to be passed, the current executing process will enter a wait state, waiting for the message requested by execution of the P instruction.

E Semaphore P instruction with message when SCT is greater than zero If it was determined in step 2205, FIG. , the message required by the executing process is found to be available. As a result, the request of the P instruction is satisfied and the execution process can continue execution. For more details, see 22
For question 05, a branch to step 2207 is made. At step 2207, a question is asked if this is a test instruction. At this point, the P instruction can be executed, but the condition code must be set for the test instruction. Therefore, if the answer is yes, the SCT field of the messaged semaphore to which the P command is directed is 1.
Another question is asked in step 220 as to whether
It will be held at 8. If the answer is yes, a condition code of zero is set in status register 1311. If the answer is negative, condition code 2 is used in step 220.
Status register 1 as shown at 9 and 2210 respectively.
It is set to 311. These condition codes indicate the message number of the Q/M/S to which the P command is directed.

If the answer to the question in step 2207 is negative, or if the condition code was otherwise set in the affirmative, step 2211 is executed. At this point, it is known that there is a semaphore (Q/M/S) message queue, and this semaphore is subjected to constant testing to determine its legitimacy. Therefore, in step 2211, the semaphore's message queue head pointer MQHP and message queue tail pointer MQTP must be unequal to zero and must be a multiple of eight. Step 22
At 12, the message link at the head of the Q/M/S is read from the queue and the message is transferred to general purpose register 1307 of central processing unit 104. The contents of the general purpose registers are transferred to scratch pad memory locations 00 through 03 in Figure 19a.

The next step executed is step 2401 of Figure 22b, which calls the FLSC subroutine depicted on Figure 24b. This subroutine retrieves the free link semaphore and checks its current state. This subroutine is executed because the message link has already been freed and is placed on the queue of free link messages directed by the FLS. Step 221
In 3, the hardware gate is locked.
indicates that a dangerous situation has occurred within the system. Memory writing of the critical situation is performed by subroutine RML, 2214, shown in FIG. 22e.

Subroutine RML is transferred to the current executing process executing the P instruction and also releases the message link with the Q/M/S previously holding the message link and the message updating the semaphore. This is step 223 in Figure 22e.
0-2234. More specifically, step 2230 dequeues the Q/M/S message link. This non-queue operation scratch pads memory location WC5.
Changes the semaphore's message queue head pointer to the next link field of the first message link on the semaphore. Step 223
1, the incremented semaphore account at scratch pad location WC7 is
It is moved to memory location WC4, indicating that one less message link is now connected to the semaphore with message Q/M/S. Step 223
2, scratch pad memory location WC4
and the contents of WC5 are transferred to main memory,
The main memory semaphore now contains the current state. Therefore, the main memory location now indicates that there is one less message link on the semaphore with a new message queue head pointer identifying the original message link. In step 2233, the free message link is now Q/ML/FLS in LIF0 manner.
It is queued above. This requires changing the free link semaphore's FLQP pointer to point to this message link. That is, the information from FLSC subroutine 2401 is now written. In addition, the previous FLQP content indicating the first link in the free link queue will be added to the link field of the next free message link to be added to the queue Q/ML/FLS.
will be relocated. Therefore, the logical structure of the free message link remains the same. At step 2234, the hardware gates are unlocked, indicating that the system is out of danger, and the RML subroutine is complete.

Returning to Figure 22b and step 2215, the instruction counter for the current executing process is incremented. Normally this would terminate the P command, but a special situation arises because the free message link is already utilized by Q/ML/FLS and this free message link can be the first free message of the queue. This situation results because the previous process may have attempted to execute a V instruction to pass the message to the SD segment of the FLS semaphore, but was unable to do so. It is now desirable to allow message transfer to occur from now on.

Therefore, in step 2216, the interrogation that is always made after the instruction counter is incremented, the instruction counter 1
A question is asked whether the new instruction counter at 312 has been filled. If the answer is yes, step 2217 indicates a segment relative address overflow and sets the instruction counter to a dummy value of zero.
Set SRA and also enable segment exception bounds deviation. This also occurs for each increment of the instruction counter. That is, step 2203 (FIG. 22a).

If the answer to question 2216 is negative, step 2218 asks if CCT is less than zero. In this case, it is desirable to look at the free link semaphore to determine if the I/O device has requested a free message link for the Q/ML/FLS. If the answer is negative, that is, if the CCT count is equal to zero, then Figure 22C and Step 2
220 is executed and the free link semaphore
I ask if FLSCT is equal to zero. If equal, this indicates that there is no process with the free message link just added to the free link signal. As a result, the next instruction 22 of the current process
21 is executed. If the answer to step 2220 is negative, that is, if there is a process waiting to pass the message, the system mode is set to 2222. Setting the system mode confirms that the instruction is complete. Furthermore,
When an error occurs, it is known that the execution of the command just executed was successful. In step 2223, FIG.
The subroutines FAR, Fetch, and Prepare Address shown below are executed. This places the previous process that attempted the V instruction on the prepare queue Q/PR/RDY, so that the dispatcher in step 2224 is notified. However, step 2218
If CCT is less than zero, that is, if there is an IO device attempting to pass the message and no free message link is available, step 2225 is executed and the instruction is fulfilled and the system mode is set. do. Step 2226 of FIG. 22d then activates the RLCM subroutine,
With the IO device now able to obtain the free message link, step 2227 resets the system mode so that the next instruction at 2228 can be executed. In this way, Figure 22b-
22d, not only does the P command succeed in obtaining the requested message, but the free message link that previously stored the passed message is either a free link semaphore or the V command's attempt is unsuccessful. It has been relocated to one of the former Semahoas.

This ends the various situations that may arise due to the P command on the messaged semaphore and the semaphore state and free link semaphore state.

V Instruction on Semaphore In FIG. 20b, if the answer to the question at step 2026 is affirmative, that is, if the V operation is executed, a transfer occurs to the VN subroutine 2027 shown in FIG. 25a. Following is a description of various permutations for V instructions executed by the current executing process.

It will be recalled that in FIG. 20, the semaphore was brought out and a preliminary decision was made that the V operation would be performed. step 2500
The question then is whether the old SCT stored at scratch pad location WC4 is less than zero, that is, is there a process connected to the semaphore that was brought out? Therefore, this question is shown in Figure 2.
0 is expected and will ignore the new semaphore stored in scratch pad location WC7. 25
If the answer to the question in 00 is negative, then V if possible.
The command adds another signal, or message, to the queue on the semaphore.

More specifically, in step 2501, the V instruction
The OP code and complementary code are tested to determine whether the Test V instruction is executed. If the answer indicates a non-test V instruction, step 2502 tests that the semaphore's semaphore maximum count (SMC) is greater than or equal to the new semaphore aligned to scratch pad memory in step 2025. If the semaphore maximum count is less than the new semaphore account, this indicates that more data has been placed on the semaphore than expected by the system, resulting in 2502
The exception status is set at a. However, if the semaphore indicates that more data can be stored, a branch to step 2503, subroutine P, or Vbondave, is made. Before describing this branch, steps 2504 to 2507 will be described.

At step 2504, it is determined that this is a test instruction. A question is now asked, as was made in the situation of step 2502, whether the semaphore's semaphore maximum count is greater than or equal to the expected new semaphore count field in step 2025. If the answer is negative, that is, SCT is greater, the V instruction cannot be completed. As a result, condition code 3 is set in the status register 1311 of step 2505, and the executing process increments its instruction counter at 2506 to execute the next instruction. If the answer to the question at 2504 is affirmative, meaning that the semaphore can store additional data, a branch to V-positive occurs at step 2503. The VPositive subroutine shown in FIG. 26 allows additional messages or signals to be added to the semaphore.

A. Semaphore V Instruction with Positive SCT Field At step 2600 (FIG. 26), the OP code and ancillary code of the V instruction in instruction fetch unit 1318 are tested to determine if this is a non-message semaphore V operation. .

If the answer to the question at 2600 is affirmative, step 2
A branch to 600A is taken. Step 260
0A tests PHQP for a value equal to zero.
If the answer is negative, an illegal semaphore exception occurs at step 2600b. If the answer to the question at step 2600 is affirmative, a branch is made to step 2601. In step 2601, the incremented SCT count expanded in step 2024 of Figure 20b is retrieved from scratch pad memory location WC7 and placed in scratch pad memory location WC4.
transmitted to. In step 2602, the hardware gate is locked, and in step 2603, an incremented SCT count is written to the semaphore in main memory, thus indicating that another signal is available from the messageless semaphore. At step 2604, the hardware gates are unlocked, indicating the end of the system's unsafe condition, and the command is completed.

However, in step 2600, the V instruction is sent from the message semaphore, and step 2605 is executed. Step 2605 asks if the SCT field is greater than zero. Since we have already determined that the semaphore account is not less than zero, it is equal to zero if it is not greater than zero. Therefore, if the answer is negative, step 2606 sets the message queue tail pointer of the message semaphore addressed by the V instruction.
MQTP message queue head pointer
The MQHP field is tested for zero since there should be no Q/M/S.

However, if the answer to step 2605 is affirmative, then
That is, if there is a message in the semaphore, step 2607 is executed and MQTP and MQHP are tested to determine that they are both equal to zero and are multiples of eight, as described above. When this condition exists, the FLSC
Subroutine step 2401 is executed.
This subroutine checks the free link semaphore and stores it in scratch pad memory locations WCB, WCC, and
Store to WCD.

When returning from the subroutine in step 2608,
Operation type is tested. If it is a semaphore V command with a message,
SEVFL, SEVTL, steps 2609 are executed. Otherwise, that is, it is an IO instruction, P
For instructions or exception handler V operations,
Step 2608a and subroutine SVP are executed. This subroutine allows messages to be passed to the semaphore.

However, if this is a V instruction by the executing process, in step 2609 the free link semaphore is
The FLQP field is tested to determine if it is equal to zero. It should be noted that both semaphore and free link semaphore are checked as legal indications. If the FLQP pointer is not equal to zero, this also indicates that free links are available. Therefore, in step 2610, this is the test V.
A question is asked as to whether this is an order. If the answer is yes, the condition code is set twice in step 2611, and in either case, whether it is a V instruction or not, step 2612, FIG. 26b, is executed.

In step 2612, the message link is
A test is performed to determine if it is within the SD segment. At this point, the free link semaphore is
Attempting to free a free message link to write a message for the executing process executing the V instruction. It is necessary to determine if the free message link is within the physical limits of the SD segment. Also, if the message link is within the segment, the priority of the executing process is transferred to the free message link in bits 24-27.
After this occurs, step 2613 calls a subroutine that tests message link access.
Run TAML and, if desired, semaphore Q/
Locate the message in the M/S queue.

The TAML subroutine is shown in Figure 26C, and more specifically, at step 2630, it also asks if this is a V instruction on a semaphore with a message if the message is queued preferentially. Therefore, this question is based on the semaphore required for scratch padded memory location WC4.
Check STAG field. If this test indicates a preferred semaphore, step 2631
The question is asked whether SCT is equal to zero. If the semaphore count is not equal to zero, indicating that there is a message link connected to the semaphore queue, Q/M/S, subroutine PRIQ 2304, shown in Figure 23e, is executed. Subroutine PRIQ locates messages within message links and performs adjacent message link validation as previously described. This information is retrieved by the PRIQ subroutine from Scratch.
The stored information is stored in memory locations WDB to WDE, so that the UQLK subroutine writes the information to main memory.

If the answer to question 2630 is negative, that is, this is not a message semaphore that is queued preferentially, or if the answer to question 2631 is affirmative, the SCT count is zero, indicating that there are no messages queued to the semaphore. message
The actual location of the link will be determined later. Step 26
32, the free link semaphore, Q/ML/
The first free message link of FLS is read into ALU 1317 from main memory.
This free message link is from FLS Semaphore
It will be the one pointed to by the FLQP pointer. In step 2633, the free message
The link's next link field is tested to be a multiple of 8, then scratch padded.
It is moved to memory location W32. This next link field is then transferred back and written as the FLQP pointer of the free link semaphore. As a result, the FLS semaphore identifies the second free message link as the queue's head free message link since the first free message link is used for the V instruction. Step 2633
Following this, the subroutine ends at step 2614.
A return to FIG. 26b is then made.

Step 2614 represents subroutine MTT, labeled 2303 in Figure 23a. The MTT subroutine is behind the move function and serves to move some of the fields in the message to a temporary scale in the working store area. The reason is,
This is because the first word and a half, 1508, must construct the message header shown in FIG. The message body, the next two and a half words after the message link, is provided by the executing process. More specifically, in FIG. 26d, step 26
40. STAG field, that is, bits 0 to 3 of the semaphore with message are tested.
If the STAG gate indicates that this is not a preferred semaphore, step 2641 is executed and the MPL field of the message header, 28 through 31
Set up to bits equal to 1111,
Indicates that this is not a priority message. but,
If the STAG field indicates a priority message, V
The priority of the process executing the instruction is read from general register #0, 1309. This priority is then written into the 27 bits from message priority field 24. At the same time, bits 28 through 31 of the message link are tested to determine if a zero value is contained in these four bits.
If not, this is step 2642a.
The data is illegal, as indicated by the exception condition that occurred.

In either case, step 2643 constructs the message tag, 20 to 23 bits.
In this particular case, the message tag is
Since it is not an IO operation, it will all be zero. Further, step 2643 sets the current process name in bits 32 to 47, thereby indicating the execution process that executed the V instruction. In step 2644, the message passed by the V instruction is transferred to temporary storage registers at storage locations WE4 through WE7. This will be the message link, the next two and a half words filled in from 48 to 127 bits. In step 2645, the message header currently in the temporary storage register is
Moved to general register 0 and the first 16 bits of the executing process's general register. Therefore, the complete message to be passed to the message link is now in general registers 0 through 3 of general register 1309. If the message link is known to be unavailable, the currently executing process will be placed in a wait state with the general registers containing the message in general registers 0 through 3 of the PCB. Therefore, subroutine MTT not only constructs the message, but also ensures that it is stored for later use.

Upon completion of the MTT subroutine, step 2616 of Figure 26b is executed. This step stores the absolute address of the message link and the relative address of the free link queue pointer.
Given the head, FLQP, the absolute address is extracted from this and then stored in temporary storage register location W30. Step 2617
, subroutine TTM is executed. This subroutine arranges and transfers the information contained in temporary storage locations WE4 to WE7 to main memory. Therefore, the TTM subroutine handles the message
Place the link at an absolute address in main memory.

The TTM subroutine is shown in Figure 26e and, in particular, it includes temporary register storage locations.
Step 2648 of reading the first double word of the message link from WE4 and WE5 and moving it to main memory, and reading the 22nd double word of the message link from scratch pad locations WE6 and WE7 and moving it to main memory. This is a writing step 2649.

Once the appropriate information has been set in the message link, step 2618 locks the hardware gate to indicate that a critical condition operation is to be performed, and step 2619 transfers the message link provided in TAML subroutine 2613. Execute a QML subroutine to The reason why two subroutines are required is that writing to main memory requires an undivided operation, which requires a hardware gate lock. Preparing information is not a dangerous operation and can be interrupted. Thus, the information check separate subroutine is executed before writing the information to main memory, and when the hardware gate is locked, the second subroutine is actually executed as shown in QML2619 in Figure 26f. Write.

More specifically, the QML subroutine is Q/ML/
Unqueue the free message link from the FLS, queue the now free message link to the semaphore with a message, and then
Add to S's message queue or form the first message link to Semaphore's queue. Therefore, in step 2650, the first free link in the free link semaphore is dequeued. This is done by moving the now free message link from scratch pad memory location W32 to the FLQP pointer of the FLS semaphore at scratch pad location WCC. In step 2651, it is determined whether the semaphore to which the V instruction is directed is open or not.
That is, a question is asked whether there is already a message link on the semaphore. If the answer is affirmative, the semaphore sends additional messages connected to the queue.
If you do not have a link, proceed to step 2652.
indicates that the semaphore's message queue head and message queue tail pointers should be changed to point to the relative address of the message link taken in step 2650. In addition, this message
The link field after the link is Q/
It is set to zero since it is the only message link connected to the M/S's semaphore. As a result, in step 2653, the semaphore's incremented SCT field is removed from scratch pad memory location WC7 and relocated to location WC4. In step 2654, the entire contents of scratch pad memory locations WC4 and WC5 are transferred to the free message memory in main memory.
Link (step 2650). In this way, not only is the message written to the message link in main memory, but the semaphore pointing to the message link is also written to the message link in step 265.
Updated via 4.

If the answer to the question at 2651 is negative, that is, there are additional message links connected to this semaphore, step 2655 asks if this is the instruction being executed in the preferred semaphore. If the answer is negative, step 2656
FIFO V instruction asks. This is determined by checking the operation code and complementary code, ie, the first 12 bits of the V instruction in instruction fetch unit 1318. If the answer is affirmative, ie, it is a FIFO queue, it indicates that the message link will be the last one in the queue. Therefore, step 2657 updates the semaphore's message queue tail pointer and queues the message link's next link field to zero on the semaphore. Because that's the last of Kyuu. Then step 2653 and step 2654
is executed, updating both the semaphore and the message link.

If the answer to the question at 2656 is negative, LIFO queuing is indicated, and step 2658 updates the semaphore's message queue head pointer;
Moves the old message queue head pointer contained in the semaphore to the link field next to the message link queued on the semaphore. This occurs because the message being passed by the V instruction of the current executing process will be the first to be passed to a P instruction that is addressed to the same semaphore. As a result, it is placed at the head of the Q/M/S. Subsequently, steps 2653 and 2654 are performed as previously described.

If the question is answered in the affirmative at step 2655 and priority queuing is required, the information necessary for queuing is provided in the TAML subroutine 2613 of FIG. 26e.
More specifically, it has already been expanded by the PRIQ subroutine referenced by the TAML subroutine. Therefore, the UQLK subroutine shown as 2311 in Figure 23b is executed to write this information to main memory for the process link. This situation arises when a message link may need to be placed somewhere in the middle of a message queue connected to a semaphore.
UQLK subroutine 2311 preferentially reorders message queues so that sequential ordering of the next link field occurs. Steps 2653 and 2654 transfer this information to the main memory location for the semaphore that has the queued message link as a priority.

Upon completion of subroutine QML, FIG. 26b shows that step 2620 is executed next, releasing the lock on the hardware gate and ending the system critical condition. After step 2620, step 2621 registers the instruction counter 13 of the executing process.
12 indicates that it will be incremented, and 2622 will sequence the next instruction.

B. V command on semaphore with message when free message link is unavailable In Figure 26a, if the answer to the question in step 2609 is affirmative, that is, the FLQP pointer of the FLS semaphore is equal to zero and there is no free link available. If so, step 2623 asks if this is a test instruction. If it is a test V instruction, step 2624
indicates that the condition code is set to 1,
Instruction counter 1312 is incremented and the next instruction is executed at step 2622. Step 2623
If the answer is negative, the process executing the V instruction has nowhere to pass the message. This is because free message links cannot be used from the free link semaphore of the SD segment shown in FIG. As a result, in step 2625, FLS
The semaphore has been modified so that it is equivalent to a semaphore with a message and can undergo processes. This is equivalent to a semaphore with a negative SCT field where the P instruction is executed. Therefore, the V instruction cannot be executed by the current executing process, and as a result, the free link semaphore holds the current executing process transferred to the wait state.
Since this is a typical P operation, step 2625 allows the free link semaphore information to be converted, and step 2121, E of the VP subroutine, processes the FLS semaphore in the same way as a message receiving a P command. Step 26
In 25, the free link semaphore pointer FLSP becomes a semaphore relative address, ie, a semaphore SRA. The FLSCT count, which was previously zero or less than zero because there may not have been a free message link available, is now decremented by one (i.e., minus one), and the free link semaphore is the FLCT for which the message could not be passed. This shows that it has an absolute number of . Also shown in the diagram is a free link semaphore that is becoming a semaphore. After step 2625, FIG.
VP subroutine 212 previously described in connection with
E of 1 is executed and the process is queued to the free link semaphore, Q/PR/FLS, by taking the process link from the G0 segment shown in Figure 17 and placing the currently executing process in the waiting state. inevitably form. This completes the semaphore V instruction with an SCT field greater than zero.

C V instruction on semaphore with negative SCT field Returning to Figure 25a, in step 2500, the old
If the answer to the question ``Is SCT greater than zero'' is positive, this indicates that the process previously requested data from the semaphore. Since the semaphore did not have the data, the process was put into a waiting state until the data was available. Since the V instruction is to be executed on the semaphore, the previous process not only receives the data and exits the waiting state, but also allows the current executing process to pass the message and continue the execution state. As a result, Figure 25
The remainder of the table depicts functions performed by both the currently executing process and processes that have been placed in a wait state because data was not available.

For more details, see steps 2508 to 2512.
Up to this point both message and non-message semaphores have been set, and step 2513 transfers information from the current executing process executing the V instruction to the semaphore that requested the data. In this way, step 2
508 is V on semaphore without message
A question is asked as to whether the operation is possible or not. If the answer is affirmative and the process queue is a non-message semaphore,
That is, Q/PR/S indicates that the semaphore's process queue head pointer is tested in step 2509 to determine whether it is a multiple of eight and not equal to zero. If the answer to the question is negative and it is a V operation on a message semaphore, step 2510 asks if this is a test V instruction on a semaphore with a message.If it is a test instruction, the condition code is returned in step 2511. Set to zero to indicate that not only is SCT negative, but executing the V instruction will place the process in a ready state. In either case, whether it is a test instruction or not, step 25
12 is executed and the message queue tale is executed.
The pointer tests to be equal to zero since this is Q/PR/S and to be a multiple of 8 for the reasons stated earlier.

If the semaphore is legal, step 2513
, the FAR subroutine, the fetch and prepare process, is executed. This subroutine passes the message to the semaphore's head process and completes the semaphore's V instruction with the message. Additionally, this subroutine changes the PCB of the process receiving the message so that the dispatcher can place the process on the ready queue.

FAR subroutine 2513 is shown in Figure 25b. More specifically, the first step (instruction) of the FAR subroutine is to access (call) the FGO subroutine 2321 described above with respect to FIG. 23d. The FG0 subroutine expands the head pointer of the G0 segment. At step 2520, the first link of the semaphore holding the process, Q/PR/S, is accessed. Therefore, the semaphore's process queue head pointer is added to the expanded address from the FG0 subroutine to provide the necessary process link. Note that if this were a free link semaphore, the process link would be
20 can be added to the G0 segment address
It would have been developed from the PQHP field. Subsequently, subroutine RNP is accessed in step 2521, and the FAR subroutine ends.

Subroutine RNP2521 is shown in Figure 25C. This serves to prepare waiting processes. This subroutine is shown in Figure 24.
a. Step 2408 is also executed when the process attached to the FLS semaphore passes the message. It will be recalled that the situation included a count execution process executing a P instruction requesting a message. There were no free message links available at that time, so the message was not passed. As a result, the message is moved and
Processes that fail to deliver the message are taken out of the waiting state and placed in the ready queue. At that time, explanation of subroutine RNP was postponed.

In addition to the above, as a result of the despatcher function,
The RNP subroutine may roll out the currently running process if the process at the head of the ready queue has a higher priority. FIG. 14 explains this in detail.

The RNP subroutine is the current
Since it is executed in a process other than the process, this other process must be found first. Therefore, step 2522 calls the PCBA subroutine shown in Figure 25h. This subroutine retrieves the absolute address of the process control block containing the waiting process. More specifically, in step 2560, the P table pointer is retrieved using the J number. Figures 5 and 17
In relation to this, this means that the J table is obtained from the system base, and then the table with the J number is indexed to expand the pointer to the P table.

In step 2561, the P table pointer is referenced and the P number is then indexed and added to the pointer to provide the address of the P table process control. The address of the process control block is then transferred from main memory to the arithmetic/logic block 1.
Taken to 317. In step 2562,
The first bit is checked, indicating that the process control block is in memory, which may have been postponed, but is not free.
In addition, bits 1 through 7 are tested and determined to be zero. As for the remaining part of the first word, these 24 bits are the absolute address for the process control block, so in Figure 19a
Step 25 in the scratch pad memory of
63.

When subroutine PCBA2522 ends, step 2523 in FIG. 25C is executed. In step 2523, the instruction's OP code and complementary code are tested. If this is an IO command, step 2
524 is executed and fetches the message data, which is the address of general register 0 of PBC.
Store at PCB address plus 84. If it is an instruction or a test V instruction, step 2525 stores the information stored in general purpose registers GR0 through GR3 of the executing process into temporary storage via subroutine MTT, shown as 2614 in FIG. 26a. Step 2524 again moves the message to PCB address +84.

In either case, subroutine TTM, step 2617, is executed to write the message to main memory. This transfer is a temporary storage location.
Process control from WE4 to WE7
It is for the block.

If, at step 2523, the operation code test indicates that there is a V instruction on a semaphore without a message, there will be no need to store the message to process control block location +84.

But in any event, step 2527 is executed and brings up an internal queue word that identifies the head of the preparation queue. What should be noted in this regard is 252
An additional entry from 8 is seen, which indicates a branch from the start instruction. This is the subject of another patent application incorporated herein by reference. The IQW word location is needed because the start command only requires transferring some of the processes to the prepare queue.

Following the internal process of bringing up the language,
Subroutine PRIQ2304, described in FIG. 23e, is executed. This subroutine prepares the process that previously performed the P operation on the semaphore, that is, the process that is currently in the waiting state.
Decide where to place it facing RP/RDY. The PRIQ subroutine checks the priority of the process in the prepare queue via the priority field in the process link and the process link's digit position (placement) in the prepare queue.
Determine. The RPIQ subroutine does not actually write to memory.

In Figure 25d, step 2529, the UACW subroutine is executed to update the accounting in the process control block. This subroutine totals the time the process spends in the wait state. At step 2530, the V instruction operation code in instruction fetch unit 1318 is tested to determine if the start instruction is being executed. If this is a start command, then in step 2532 the PCB's process priority is transferred to the process link. Following this step, if a priority byte change has occurred, the priority byte transferred from the scratch pad memory is updated.

However, if this is a non-start instruction, the process has been changed from the wait state. That is, the process link already exists. Therefore, in step 2533, the priority of the waiting process as indicated by the process link is
Scratch pad memory location NJP, Figure 19
It will be moved to a. This result occurs because the priority in the process link field of the process is the most recent version of the current priority. Therefore, if there was a priority change while the process was in a wait state, it would not be indicated by the process link field.

In Figure 25e, step 2534, the operation code is again tested to determine whether this is a semaphore P instruction with a message having an SCT field equal to zero, whether or not it is a test.
Determine. This occurs from the branch from the PNZ subroutine of FIG. 24a, which called the RNP subroutine at step 2408. If this condition exists, in step 2535, the contents of the process control block of the process in the wait state, that is, the value at address +84, are transferred from general register GR0 to GR of the process currently executing the P instruction.
It will be moved by 3. It will be recalled that the PCB of the waiting process contains a message since no free message link was available. As a result, the process was coupled to Q/PR/FLS. Now that the P instruction has been executed, the PNZ subroutine has determined that the displacement fields are equal. As a result, Q/PR/
Message transfer from processes within the FLS takes place. Next, in step 2536, the hardware gate is locked to indicate that a dangerous condition is entering, and in step 2537, the UPLQ subroutine is executed. This subroutine removes the process link and the Q/
Update PR/FLS.

Therefore, step 2580 determines whether the first link indicator is equal to zero or the process at the head of the queue being removed.
Decide whether it is a link. If so, step 2581 indicates that the process link is the head of the queue, and from now on the scratch
Process Queue Head of Patched Location WE5
The pointer is updated with the contents of UNL stored in scratch pad location WE9. However, if it is not the head of the queue, in step 2583,
The old process queue head pointer is equal to the new process head queue pointer, and the next link field of the removed process is transferred to its previous link. Therefore,
The previous link identifies the process link previously identified by the removed process link, ensuring logical connectivity of all process links within the Q/PR/FLS. This link information is provided by the SPLQ subroutine to the scratch pad location WE.
This is information stored in WE8 and WE9.

If the answer to the question at 2534 is negative, indicating that no special condition exists, a branch to step 2538 is executed. Because of the complexity of the command that can result in a negative answer, step 2538 indicates that this is the message semaphore's session start or P or P.
Test instructions ask questions. If the answer is affirmative, 2539
A branch is made. This branch is Q/PR/S
Alternatively, dequeuing from Q/PR/FLS is deferred until step 2555. However, if the answer to question 2538 is negative, as occurs with the V instruction, step 2540 locks the hardware gate and step 2541 removes the process link from semaphore Q/PR/S or Q/PL/FLS. Unqueue. In other words, the process
The link is retrieved from the queue in which it previously existed. The removed link is added to Q/PR/RDY. In step 2542, the addressed semaphore is written to a new SCT field and to both scratch pad memory and main memory. This indicates the new state of the semaphore.

If the PMZ subroutine was used, step 2542 is also executed. Subsequently, in step 2543, the hardware gate is released to indicate the end of the indivisibie unsafe state operation.

At this point, the process held in the semaphore has received the data it previously requested. but,
When a P instruction cannot be executed, the instruction count of the executing process remains the same because the process has been rolled out to the wait state. Therefore, when the process returns to the execution state, the instruction counter indicates that the P instruction is to be executed. Since the process's P instruction has now been executed, that is, since its message has been received, the contents of the instruction counter stored in the PCB should be incremented by four. By doing this, the process starts with the next instruction following the P instruction. Steps 2544-2
Up to 547, preparations are made for changing the contents of the instruction counter.

In step 2544, the instruction counter word
The MBZ field is tested for zero.
At step 2545, four is added to the segment relative address stored in the instruction counter, allowing the instruction counter to indicate that the next instruction is to be executed. In Figure 25f, step 2546, this new address for the instruction counter word is
Written to the process control block of the process that executed the P instruction, and executed in step 2547.
is tested to determine if the incremented address has spilled out of the segment. This situation can occur when the instruction counter is incremented. Therefore, a process that is removed from the waiting state can function in the running state if the desbatcher transfers it.

Step 2539 indicating message semaphore session start or P or test P command
Step 2548 is executed if a branch from is taken, or following an increment of the instruction counter of the waiting process. In step 2548,
The hardware gate indicating the critical condition is locked again and the just updated process status byte is set to the ready state at step 2549, allowing the dispatcher to place it in the ready queue.

In Figure 25g, step 2550, the question is again asked if this is a start command. If the answer is yes, in step 2551, the process link containing information about the process being initialized is retrieved from the process link queue on the Q/PL/PLS, process link semaphore, and the contest indicator is set. Set to 1. This contest indicator is set when one or more new processes are placed in the prepare queue after the beginning of the last instruction has been executed by the current executing process. The contest indicator identifies a potential conflict with the head process of the prepare queue with the current executing process for the running state. Subsequently, in step 2311, subroutine UQLK, previously described in connection with FIG. 23h, is executed to update the process links determined by the PRIQ subroutine. In step 2553, the hardware gate is unlocked since the system danger condition has ended. Therefore, regarding this branch,
It can be seen that the RNP subroutine has updated both the current executing process executing the V instruction and the processes started by the current executing process.

However, if the answer to question 2550 is negative, then the same question asked in step 2534 is asked in step 2554. This means that whether or not a test is on a message with an SCT count equal to zero, it asks whether it is a P command or a secession. For P instructions, queueing is already done by the UPLQ Qib routine. As a result, since the process has been added to the ready queue, a branch is taken to step 2552, where a priority comparison is made between the process at the head of Q/PR/RDY and the executing process. Therefore, for this branch, P of the message signal
It can be seen that the RNP subroutine has updated both the current executing process that is executing the instruction and the process that was in a waiting state and was connected to the free link semaphore because the free message link was not available.

However, if the condition of the question at 2554 is not met, that is, if the SCT current is not equal to zero, or if it is one of the instructions listed above.
If not, step 2555 is executed to retrieve the new process link, either Q/PR/ or Q/PR/FLS, from the waiting queue, and step 2556 is executed to retrieve the updated SCT link, either Q/PR/ or Q/PR/FLS.
The scratchpad memory location WC7 is queried and placed into the process link. At step 2557, a question is asked whether this is a semaphore V instruction without a message. If so, step 2558 connects the process link to the Q/
Write the name of the process link just removed from the PR/S into the tenant field of the semaphore, bits 48 through 63 as shown in FIG. In addition, step 2558 updates the semaphore with all current information stored in scratch pad memory locations WC4 and WC5, i.e., the new updated SCT as formed in 2556 and the previously occurred semaphore. All queue pointers may have changed. Once the non-message semaphore has been fully updated, step 255
The contest indicator at 2 is set to 1 to indicate that a new process has been placed in the prepare queue because the last instruction was executed by the current executing process. Before, that is, step 2311
The same steps described at 2553 are then executed, resulting in the end of the RNP subroutine. Therefore, this branch is known because the RNP subroutine has updated both the current execution process that executes the V instruction of the non-message semaphore and the waiting process connected to the non-message semaphore.

However, if the answer to the question in step 2557 is negative, indicating that the message was not a V instruction in the semaphore, then step 2559 adds a new head pointer and a new count field to the semaphore in main memory to change the Q/PR/S. Will write. and step 2552 mentioned earlier.
is executed next. Therefore, for this branch, it can be seen that the RNP subroutine updates both the current executing process executing the message semaphore's V instruction and the waiting process connected to the message semaphore.

When the RNP subroutine is finished, step 251
A return to FIG. 25a at 4 is executed, where the instruction counter of the current executing process is incremented. At step 2515, the dispatcher is called,
A previously updated process can be moved to the ready queue, and the dispatcher can determine that the process is in the running state, ie, responsive to the contest indicator being set to one.

Semaphore Initialization Instructions Previously, we explained the structure of a semaphore and each of the fields used to enable process synchronization.
Semaphore maintains an abnormally high event occurrence rate,
For example, presenting a message for a message semaphore and a resource for a non-message semaphore may create a dangerous situation within the data processor. For example, for a message semaphore, if it receives a large number of messages and therefore requires the same amount of message links, then Figure 1
The intra-SD segment free message links shown at 5, 17, and 18 cannot be fed to other message semaphores within the same SD segment. This situation may, for example, indicate a failure within the communications structure. To ensure that the semaphore is functioning properly, or alternatively to return the semaphore to its original state, the semaphore initialization instruction (SECIN) is used. This instruction sets the semaphore to its count field.
For non-message semaphores, setting the SCT to zero or to a value responsive to the originally intended number of resources transfers to the previously determined state.

It was previously shown that the negative SCT field of a semaphore indicates the number of processes connected to the semaphore.

The SECIN instruction does not initialize a semaphore that has processes attached to it. This is because this operation destroys the process itself. This result occurs because each process connected to the semaphore is in a wait state and has an event occurring. Since the SECIN instruction does not supply this event, the process cannot therefore be transferred to the prepare queue. Therefore, the process will be misdefined and will not be recognized by the processor. Thus, the job (unit of work) that a process is intended to perform is
It will not be performed and subsequent process operations will be prohibited.

More specifically, for a message semaphore, the semaphore's SCT field is gradually set to zero, freeing the Q/M/S and releasing all messages and message links connected to it. The SCT field is not initialized to the position number because it would be necessary to add an unknown message to the queue. However, this situation does not apply to non-message semaphores that may recognize resources. It is possible to use determined numbers of resources for processes. As a result, it is possible to place the numbers of available resources in the SCT fields of non-message semaphores by default, and processes can use these resources as needed.

These features may be better understood by looking at Figures 27a and 27b, which describe the functions performed in executing the SECIN instruction.

FIG. 20 shows a general-purpose subroutine for expanding semaphore descriptors. This semaphore descriptor fetch subroutine 2000 is responsive to the operation code, complement code, and address syllable of the SECIN instruction. In response to the operation complement code of the SECIN instruction, a branch is made to the SECIN subroutine at step 2022. Therefore, upon entering the SECIN subroutine of Figure 27a, the segment descriptor, semaphore descriptor, and semaphore itself are
It is brought out of memory and checked for possible errors. The SECIN subroutine works on the semaphore itself.

For more details, in step 2701 the semaphore
The SCT field is tested to determine if it is greater than or equal to zero. If less than zero, this indicates that there are no processes attached to the semaphore. The SECIN instruction does not change the process's queued semaphore. This is because it prohibits operations after these processes. Therefore, if SCT is less than zero, an illegal signal initialization exception 2702 occurs. but,
If the SCT field is greater than or equal to zero, step 2703 is executed to test the validity of the semaphore's STAG field.
The STAG field encoding is shown above in FIG. At step 2704, a question is asked if this is a non-message semaphore. STAG
If the field indicates this is a non-message semaphore, a branch is taken to step 2705.

For a non-message semaphore SECIN instruction, the general purpose register of the process executing the SECIN instruction was loaded with number N. Since a non-message semaphore may identify several resources, the number loaded into the executing process's general register may be equal to the number of the resource originally intended to be represented by the semaphore. Therefore, in step 2705, the contents of the previously set general purpose register are tested to determine if its value is less than zero. If the answer is affirmative, the illegal semaphore initialization exception 2705a occurs because negative counting is impossible, that is, it indicates a negative resource number.

However, if the answer to step 2705 is negative, then in step 2706 the value stored in the general purpose register is tested to determine if it is less than the semaphore's maximum count field SMC. Since the number of the general-purpose register should be the number of the SCT field, the requirements shown in FIG. 16 are used. It will be recalled that the SCT count needed to be less than or equal to the SMC count to aid in memory space control. Therefore, if the SCT count is higher, an illegal situation exists at the signal because there will be more resources in the semaphore than it was intended to hold. If this situation were to occur, an exception condition would be generated every time the semaphore was used. As a result, if the number in the general register is greater than the SMC field, then the illegal semaphore initialization exception 27
05a occurs.

However, assuming the value of the general purpose register is less than or equal to the semaphore maximum count field, in step 2707 the semaphore's initialized information is written to its main memory location. More specifically, the SCT field of the semaphore receives the contents of the general register and is set to either zero or the positive number indicated by the general register. In other words, the process queue head
The pointer, bits 32 through 47, are equalized to zero because there is no queue of processes connected to this non-message semaphore. And finally, since there is no process that executed the semaphore V instruction, TEP
The field, bits 48 through 63, are equalized to zero. A later result occurs because the semaphore has now been initialized, so that previously executed V commands on the semaphore are ignored. Therefore, a non-message semaphore has been initialized and now contains the information necessary for either a P or V instruction directed to it.

After initializing the semaphore, step 2708 increments the instruction counter for the process executing the SECIN instruction, and the next instruction in step 2709 is executed.

If the answer to the question in step 2709 is negative, that is, the addressed semaphore is a message semaphore, then the SECIN instruction removes all message links queued to the semaphore. More specifically, step 2710 includes:
Set the condition code in status register 1311 to a value of 3. If the semaphore counter is found to be originally zero, this condition code of 3 remains at the end of the instruction. Next, 2711 is the message semaphore.
Test the SCT field and determine if the SCT field is equal to zero, that is, the message link is connected to the semaphore; if none, that is, the answer is positive, then the message queue tail of the message semaphore Pointer field MQTP and message queue head
Pointer fields HQHP are tested to determine if they point to any message links. Both fields should contain zero since step 2711 indicated there were none. The instruction counter for the process executing the SECIN instruction is then incremented again via step 2708 and the next instruction is executed. Therefore, if the SCT field is already zero, SECIN
No message is removed by command, 3
The condition code indicates this situation.

But if the SCT count is equal to zero,
In other words, if the answer to question 2711 is negative,
The SCT count is found to be greater than zero, and the message
There are no links. As a result, FIG. 27b step 27
A branch to 13 is taken. At step 2714, the MQHP and MQTP fields of the message semaphore are tested. MQHP and MQTP because there is a message link connected to the semaphore
Both must be equal to zero and must be multiples of 8. After testing the legitimacy of the semaphore in step 2714, the subroutine shown in Figure 24b
A branch to FLSC2401 is made. This subroutine not only checks the free-link semaphore to ensure that it is within the design constraints of Figure 16D, but also scratch pads the three free-link semaphores to memory locations WDB, WDC, and WDD. Store words. This free link semaphore will receive the free message link.

Subroutine FLSC240 of step 2715
1, the semaphore count stored in the scratch pad location WC4 in Figure 20 is
The field is decremented by one and moved to scratch pad memory location WC7. This is done because it is expected that the message link from the semaphore will be released. Step 2
At 716, the message link directed by the semaphore's MQHP field is located and relocated to scratch pad location W31. This message link is semaphore, Q/
Message link released from M/S's message queue.

Once both the message link to be released and the free link semaphore to receive the freed message link are obtained, the hardware gate is locked at step 2717, indicating that a system risk operation is being performed.
This system-critical operation is a rewrite in main memory of both free-linked semaphores and semaphores with message links. Figure 2 before
RML subroutine step 2 shown in 2E
This is done by 214. subroutine
RML unqueues the message link from Q/M/S by changing the next link field of the message link, so that it is free link semaphore queued and concatenated to Q/ML/FLS. be done. Additionally, the RML updates the fields of the message semaphore so that the released message link is no longer connected to the Q/M/S. This includes writing the NSCT expanded in the new semaphore account step 2715 to the scratch pad location WC4;
The purpose is to update MQHP to indicate the next message link on Q/M/S. At this point,
The initial message link on the Q/M/S is free.

Since the free message link is fed to the free link semaphore at 2718, the channel count of the free link semaphore is 80 to 95.
A question is then asked whether up to bits is less than zero. This question in step 2718 determines whether the I/O process is waiting for the free message that was just retrieved. If the CCT count is less than zero, then step 2719 indicates that the I/O process was waiting for a free message link.
The steps from 2721 to 2721 are executed. Step 2719
Then, the condition code in the status register 1311 is 2.
is set to indicate that the IO operation has received a free message link. Step 27
At 20, the RLCM subroutine is executed.
The RLCM subroutine transfers the message link to the IO process by executing a simulated V command.

Upon completion of the RLCM subroutine, branch 2721 is taken and the new state of the semaphore can be re-examined. Therefore, step 2722
The question is then asked whether the semaphore's SCT count is now equal to zero. If so, and the semaphore has no additional message links attached to it, step 2712 tests the legitimacy of the semaphore and executes the next instruction for the executing process. If not equal, another message link from the semaphore is returned in step 2713.
is released as indicated by the branch at .

However, if the answer to the question in step 2713 is negative, a condition code is set indicating that the message link has been transferred to Q/ML/FLS. Next, in step 2725, a question is asked whether the free link semaphore account, FLSCT field, is less than zero. This question determines whether there is a process queue on the free link semaphore, Q/PR/FLS, that is, the process attempted a V instruction, failed, and was placed in a wait state connected to Q/PR/FLS. . At this point, you can see that the message link has been released. Therefore, a process that attempts to execute a V instruction and fails may be able to do so after a free message link is added to the free link semaphore. Therefore, if the answer to the question at step 2727 is affirmative, subroutine FAR2513
is executed. This fetch and prepare subroutine, previously described in Figure 25b, essentially puts the wait state into the prepare state and Q/PR/RDY so that it is a semaphore with a message that retries its V command. You will be able to do it. Therefore,
The free message link just released by the SECIN command can now be used to carry out the previously attempted V command.

However, if the answer to the question in step 2725 is negative, indicating that there are no processes waiting for the free message link, then the freed message link Will be added to ML/FLS. Step 2726 then allows the condition code to be set to zero in the status register. Next, step 2722 asks if any additional message links are connected to the semaphore. Again, if the answer is yes,
That is, if there are no more message links connected to the semaphore, the legitimacy of the semaphore is tested and the next instruction is executed as shown in Figure 27a. The same steps, steps 2714 through 2725, are executed until there are no more messages linked to the message semaphore.

Therefore, regarding the message semaphore,
The SECIN command allows a message link connected to a semaphore, Q/M/S, to be released to a free message link queue Q/ML/FLS. In addition, each message link released displays a potential link for a previously unsuccessful V command, so the information is Q/PR/
Place the same number of processes connected to FLS into the preparation queue Q/PR/RDY. Furthermore, SCT, MQHP,
MQTP fields are all set to zero.
For non-message semaphores, the SECIN instruction sets the SCT field to either zero or a positive value and the TEP field to zero. A process is a general description of an event external to a process that controls the central processing unit. It was shown earlier that a task is a unit of work at the level to which it is assigned. While there are many processes involved in the activity status,
Only one controller controls the central processing unit at a given time
There are two processes. If this process requires additional resources to continue processing its steps,
A request for a resource is made by using a P command on the semaphore associated with the resource. The semaphore then displays resource availability. In addition, resource availability is provided by a corresponding semaphore, the semaphore V instruction, which indicates whether the process is waiting for the resource. P and V instructions can also be used to transfer information related to certain so-called internal events between processes.・This is an event depicted by control blocks (PCBs).

Previously, it was stated that internal events are communicated by processes controlling the central processing unit via V-instruction execution. However, there is another method in which external events are communicated to the central processing unit subsystem. When this communication is required, it is done through a mechanism called the system event poller.
The request is made by the data processing machine hardware/firmware. This requirement is considered between the processing of instructions of the active process that controls the central processing unit and the results of the simulated V instructions that communicate information of external events to the active process.

These external events processed between instructions are directly related to the active processes controlling the central processing unit.
More specifically, these events are typically I/O interrupts or certain exceptional conditions. A central exception facility communicates about this exception condition. When an interrupt-like or system exception condition occurs, a simulated V operation is provided to route the communication to the appropriate process on the central processing unit. This communication reports to the appropriate process the nature and cause of the exceptional condition so that the data processing system can continue its operation, and also reports the relative importance of the exceptional condition and the central processing unit subsystem. Take appropriate action regarding the exception at a time determined by both states.

In addition to handling communication about exceptional events, the system event poller also allows communication about I/O interrupts. I/O interrupt refers to all communications that occur from the I/O subsystem. This includes communications from input/output controllers (IOCs) and all peripherals.

The I/O subsystem supports asynchronous I/O operations and provides a high degree of overlap to central processing unit execution. Accordingly, the I/O subsystem includes the entire set of facilities necessary for transferring information between the central processing unit main memory and any of the peripheral devices included in the peripheral subsystem. I/
A detailed description of the O subsystem will not be given as it may utilize various implementations known in the prior art. However, the operation of the I/O subsystem will be briefly introduced to illustrate the reporting of messages to the central processing unit.

More specifically, the I/O subsystem works asynchronously with the central processing unit. As a result, the I/O subsystem has its own underlying program called a channel program, which contains a complete set of commands and address information to perform the desired I/O operation. It consists of a set. The channel program is
the channel number of the logical channel consisting of the program header and to which the program is directed;
Contains channel command entries, which are the basic building blocks of channel programs. Logical channels are used to communicate from the IOC's I/O devices to the central processing unit. A logical channel is a conceptual communication path between main memory and a single peripheral of an I/O subsystem. As used herein, a logical channel is used to perform one or more operations on a peripheral device.

Because the I/O subsystem and central processing subsystem work independently, during channel program execution several events may occur that need to be communicated to the central processing unit. These events may occur during or at the end of channel program execution, so
The program is interrupted and the I/O subsystem provides an event notification message containing the LC number corresponding to the channel program.

These I/O report messages can recognize the following events: first, events related to channel program execution, hereinafter referred to as intermediate or termination events; second, related to specific peripheral devices; Third, events not directly related to the channel program, hereinafter referred to as attention events; third, hereinafter referred to as physical channel exceptions, or I/O malfunction exceptions. An event that implies a change in the operational status of any I/O hardware. The latter exceptional circumstances are outside the scope of this application.

Message notifications of I/O events are provided to processes within the central processing unit as follows. When an I/O message is acknowledged, a mechanism called a system event poller is employed to act as a pseudo process. This mechanism then prepares a simulated V operation of the message semaphore that allows the message to be communicated to a process within the central processing unit. Therefore, I/O interrupts may be viewed as a process equivalent to a process within a central processing unit. That is, they communicate with central processing unit processes through message semaphores and simulated synchronization primitives. In addition, the simulated V operations transfer messages on behalf of logical channels, just as V instructions transfer messages on behalf of processes controlling a central processing unit.

For I/O interrupts, the I/O subsystem provides a signal that sets a flop indicating that a message was generated by some I/O event. This special signal is recognized by the central processing unit as an indication that an event notification message is waiting to be queued to a signal. This flop, which is set up and is the interface between the I/O subsystem and the central processing unit, will be referred to below as the interface flop.
Once this interface flop is set, the central processing unit recognizes that a simulated V operation is being executed. At the end of the current instruction, the system event poller shown in FIG. 27 is entered by the central processing unit.

System Event Poller Mechanism The System Event Poller is a hardware mechanism that prepares the set of operations shown in FIG. The system event poller can be either hardware or firmware implemented in a manner well known to those skilled in the art. system event
A functional description of Polar's operation is as follows.

At step 2700, at the end of the current instruction being executed by the active process,
The system event poller is populated by the central processing unit. The first question asked by the system event poller is whether external events that may have occurred during the execution of the final instruction are polled. Step 2702, which checks if the hardware gate is locked, does this. As stated above, locked hardware indicates that an unsafe operation is occurring. By setting the hardware gate, 1
Two indivisible operations are provided. This indivisible operation may, for example, transfer information to main memory or a message to a semaphore. If the hardware gate is locked, that is, it is set to a binary 1, then step 270
A branch to 4 is taken, where the next instruction of the currently active process is executed. Therefore, when the hardware gate is locked, a determination is made by the data processing system that the action currently being performed is more important than the communication of I/O events.

However, if the hardware gate is not locked, a branch is made to step 2706;
System mode is entered. This step 2
706 initializes the flop of auxiliary memory 1317a, indicating that a system control operation is to be performed. The system event poller is the mechanism that performs this system control operation. More specifically, the system event poller polls all I/O interrupts and exception conditions and enables processing of these events.

In the system 2708, the system event
Paula checks the flop to the I/O subsystem to see if it is set.
If set, an I/O interrupt is pending and
A branch to step 2710 is taken. This step activates the I/O event handler mechanism shown and described in FIG.

However, if the interface flop is not set, a test is performed at step 2712 to determine if an exceptional condition has been detected. If that has occurred, the branch to the center-lateral mechanism of step 2714 is taken. A central exception facility allows exceptional conditions to be handled and sends reports to exception handlers.

For both the I/O event handler and the central exception facility, once they have completed the particular event that was polled, a branch is taken back to the system event poller and, more particularly, to step 2708. Because of this operation, all I/O interrupts and all exception conditions are handled before the next instruction of the currently active process within the central processing unit is executed.

The I/O event handler and central exception facility prepare for simulated V operations as part of its external event handling tasks so that one or more messages are sent to the appropriate process within the central processing unit. It may have been moved. Depending on the configuration of each semaphore that may have received a message via this simulated V operation, one or more processes within the central processing unit may queue the semaphore message (Q/
M/S) may have been transferred to the preparation queue (Q/PR/RDY). As a result, step 27
At 16, Despatches are added. This dispatcher, shown in FIG. 14, determines which processes should be subject to central processing unit control. Therefore, messages from external events are integrated with the central processing unit's internal messages. Depending on the priority of the processes in the preparation queue, more important communications are handled first. Obviously, all messages are conditionally fed to the central processing unit. Messages of greater importance are then handled depending on what is present within the central processing subsystem at the time.

I/O Event Handler Referring now to FIG. 28, an I/O event handler 2710 is entered when the system event poller detects the presence of a pending I/O event message. trying to be set,
The queue of logical channels for events, i.e., Figure 29b
This will be illustrated by the alternating interrupt flops that cause entries to be placed in the Q/LC/EVQ shown in FIG. These event messages are queued onto message signals located in the main memory of the central processing subsystem. I/O event・
Before discussing the functions performed by handler 2710, we will discuss the tables used by the I/O subsystem for simulated V operations.

After event notification messages are generated by the I/O subsystem, they are stored in the appropriate logical channel table with a plurality of logical channel table entries (LCTEs). Each LCTE includes an event notification message that is communicated to a process within the central processing unit by a simulated V operation. Each LCTE has an event notification queue Q/LC/
You can have two items in EVQ. The I/O subsystem has one Q/O for all logical channels.
There is LC/EVQ queue. If at least one message is presented, a queue is formed and one is generated that sets an interrupt flop to recognize the occurrence of an I/O event. If the queue is empty, no signal is asserted and the interrupt flop is set to logic zero. If the interrupt flop is logic 1, the system
The event poller allows a simulated V operation similar to that required by the interrupt flop to empty Q/LC/EVQ to be set to logic zero.

Messages transmitted by the I/O subsystem to the LCTE are queued in the order of arrival, that is, first in, first out (F1F0).
Placed in EVQ. Each simulated V operation performs some function on the queued message. First, remove the first event notification message from Q/LC/EVQ. Second, the simulated V operation attempts to assign this to the associated semaphore as given by the semaphore system name, Gi, Di for intermediate or terminal messages, and Ga, Da for the attention message. Either queuing the message or sending the message to the waiting process specified by the semaphore. Third, if a message can be queued to a semaphore or sent to a waiting process, the message corresponds to Q/LC/EVQ.
Removed from LOTE's appropriate storage area. Fourth, if a lack of free message links in the associated SD segment prevents a message from being queued to the appropriate semaphore, the message is removed from the Q/LC/EVQ and the message was originally associated with the message. Semaphore (Gi, Di) or (Ga, Da)
is linked to the free message link semaphore of the corresponding SD segment. The message is
remain in the LCTE's storage, but the message concatenation is modified, i.e., it relates to a free link semaphore
LCTE is queued to a new queue, Q/LC/ELS, a logical channel queue on a free link semaphore. Both Q/LC/
EVQ and Q/LC/FLS will be more easily understood when Figure 29a showing LCTE is explained.

The I/O system uses special tables, one of which corresponds to the various logical channels that provide communication paths to main memory. I/O table has absolute address 0
, but before the base address register (BAR) previously shown in FIG.
The LCTE shown in Figure 29a is the only entry in the logical channel table, as seen in Figure 29b.

Each logical channel table entry consists of 16 words,
It is used to store information about logical channels, as well as information identifying channel programs, intermediate or end-of-event messages, and messages of interest.

Only those areas of LCTE within the scope of the present invention are discussed below. Therefore, information other than the program is stored in word 1, the first byte contains the LC status, and bytes 1 to 3 of word 1 contain the semaphore of interest.

Words 8-11 indicate intermediate or event termination messages that are communicated. More specifically, the last two bytes of word 8 are the next link (NL) pointer that identifies the queue on which the logical channel table entry resides. As mentioned earlier, this is either an event reporting queue Q/LC/EVQ that occurs when a message is first transferred to the table, or a free link semaphore, which is the result of not being able to store the message in the appropriate semaphore. Maybe. Byte 2 of word 8 defines the event type corresponding to the reason (reascn) field for I/O operations discussed in FIG. The reason field recognizes the manner in which the I/O operation is terminated and may contain information for normal or abnormal termination.
In the fourth byte of word 8, the first half of this byte is the message priority corresponding to the channel program priority stated in the I/O operation. When this message is passed to the message semaphore with the priority determined queue,
Field recognizes message position of Q/M/S. The next half byte is a semaphore tag that recognizes that this message is the result of an I/O operation. LCTE word 9 contains specific information that recognizes the logical channel number (LC) and other information outside the scope of the present invention. Word 10 contains the channel command, entry pointer that generated the intermediate or terminal event notification message. Word 11 may include the status of both the I/O device and the IOC.

Words 8-11 consist of messages that would be transferred via a simulated V operation to a semaphore with system addresses Gi, Di. Words 12-15 consist of the attention message passed to the semaphore indicating the system address Gi, Di recognized in word 1 of the LCTE table.

In the first half-word attention message, its location in LCTE and Q/LC/EVQ or Q/LC/
Next link field, which recognizes what is in the FS
The reason field has a determined termination message, indicated by the encoding /000/101, ie by the word 12 of 3. This field recognizes that this semaphore message is an attention type message. The priority field, the first four bits of the fourth byte, is set to the coding /111, indicating highest priority. A message tag is the same as an intermediate or terminal message. This is because it indicates an I/O message. Word 13
Now, the first two bytes are the same as the message described previously, but the last two bytes recognize the name of the device supplying the message of interest. Since the attention message describes an event that is not attributable to channel program execution associated with a particular peripheral, the resident count and current LCTE address fields supplied with intermediate or terminal events are not required. However, a device name is required and word 13 recognizes the device.
Word 15 is the same as word 11 described above. For the message of interest, all the necessary information is provided in only three words (words 12, 13, and 15 shown here). Therefore, word 14 is used to store the semaphore associated with the intermediate or terminal event found in the last three bytes.

Each LCTE entry thus indicated initially creates one or more items in the event notification queue, ie of interest and/or intermediate termination type. Each entry represents the occurrence of an I/O event requiring communication to one process within the central processing unit. This communication will be sent in words 8-11 or 12-15 depending on the type of event being notified.
May be supplied by. For intermediate or terminal messages, simulated V operations are performed on semaphore Ga, Da. Therefore, the system names Gi and Di are channel
Recognize the semaphore, where all messages related to the program are passed. System name Ga,
Da recognizes a semaphore, where all messages related to a particular peripheral are passed.

A plurality of logical channel table entries are shown in Figure 29b. Since LCT includes all LCTE, Q/
LC/EVQ and Q/LC/FLS are shown. Queue Q/LC/EVQ, as previously described, contains entries for event notification messages and Q/LC/EVQ.
LC/EVQ is brought up. As shown in Figure 19a, there is an entry in scratch pad memory location 2F that recognizes the head of Q/LC/EVQ. In this way, this entry is the first entry in the queue.
A pointer to an LCTE entry. This absolute address is retrieved from location 2E and that address is used to call the first logical channel table entry. The pointer was written to scratch pad memory when the asynchronous I/O subsystem placed the message in the queue.

In FIG. 28, step 2802, a question is asked whether this is an event of interest. If it is a noteworthy event,
At step 2804, the Ga, Da address of the semaphore to which the message is directed is retrieved from the LCTE. If it is not an attention message, proceed to step 28.
06, the semaphore to which the message is directed.
The names Gi and Di are brought up from word 14 of the LCTE.

In step 2808, the initial LCTE from the queue Q/LC/EVQ is dequeued by changing the scratch pad memory location in the LE and to point to the new head of the LCTE table; The next link field in the LCTE is brought out. Therefore, the LCTE entry is removed and
The message is placed on the message semaphore indicated by the system GD name. At step 2810, the message is placed in scratch pad memory locations WC4 through WC7.
If it is an intermediate message, words 8-11 are moved to these locations, but if it is a message of interest, words 12-15 are placed there.

In step 2812, the message is then transferred via a simulated V operation to the appropriate semaphore indicated by the system name. When the V operation finishes, the system event poller is re-entered and there
The next LCTE entry, if any, is transferred.

Thus, FIG. 28 is a list of steps that are performed on an event notification message when communication with a process within the central processing unit is required. The steps shown in FIG. 28 will be explained in more detail in FIGS. 30-32 in conjunction with FIGS. 20-26 to identify the operations necessary to convert the message into the appropriate process. .

Simulated V-Operation on a Semaphore with a Positive SCT Field It will be recalled that a V-operation is a forwarding operation that allows a message to be transferred to an intermediary point called a semaphore. This semaphore stores data until picked up by another process. The V instruction was previously executed by the process controlling the central processing unit. The simulated V instructions are nearly identical in that they send information to either another process or set of processes within the central processing unit. The V
Different from the command. While there is only one target instruction between a V operation and a V instruction, if this mechanism attempts to transfer a message, for simplicity it is
called a command.

The major features of simulated V operations provided by the system event poller mechanism are: (1) Updates to process state performed by processes controlling the central processing unit; (2) free link semaphore in the associated SD segment, as opposed to updating the logical channel state when a message passes successfully, and (2) queuing the process to Q/PR/FLS when a free message link is found unavailable. (3) logical channel queueing to Q/LC/FLS when finding a free message link connected to (Q/FL/FLS) unavailable and no process waiting on the appropriate semaphore; Testing the G field of a free link semaphore within the associated SD segment when the count (CCT) field is less than zero. Previously, in Figures 20 to 26,
The field indicated that it had been tested but no explanation of the operation was given.

In addition, regarding I/O events and exception conditions, 2.
Two additional differences were given. The first difference is supplied by a simulated V operation,
This is the content of the message being passed. The message content for I/O interrupts was described in conjunction with FIG. 29 and the LCTE table description. Second, the address of the semaphore is different from that described for the P and V instructions. Each semaphore can have two names: the local SEG, SRA name and the system G,0 name. For processes controlling central processing units, it is recalled that local SEG and SRA names were used to recognize signals. For intermediate, terminal, and attention name messages,
The system name GD is given.

The system name of a semaphore is the address GD of the semahore in the corresponding SD segment. Figure 4, 1
1, 17, the G segment table (G
Table) contains a G segment descriptor, so this is the result. The G segment descriptor describes a general purpose system segment. Since there is only one G segment table in the data processing system, the size and address of the G segment table are defined in terms of the contents of the G word (GTW). This word is located at system base address BAR+4. The G table pointer, also at the system base, gives the absolute address of the G table. When calling this G segment, the G number provides a displacement into the G segment table, allowing selection of the appropriate semaphore to which the message is directed.

As shown in Figure 17, the system G and D names are expanded differently from the local EG and SRA names, so the start of the simulated V instruction is different from the semaphore address expansion from the JP name in the entry shown in Figure 20.・
It is done in points.

More specifically, FIG. 20 depicts the semaphore descriptor fetch routines enabled by each of the P and V instructions. When this subroutine is invoked, the operation code has been placed in the instruction fetch unit 1318 which represents the simulated V instruction. Since the I/O interrupt or exception condition is given a system name, there is no need to test and bring up the semaphore descriptor. As a result, the semaphore fetching routine determines the absolute address of the semaphore to which the message is expanded and step 201 of FIG. 20b.
Can be entered at 9. This absolute address is the G,D system name. At step 2020, both words of the message semaphore as shown in FIG. 16b are brought out of main memory and moved to scratch pad memory locations WC4 and WC5. V
Same system as for orders 2021-20
26 are carried out, and the answer to the question in system 2026 is affirmative, so system 25 in FIG.
00 is executed.

less than 0, i.e. the process previously requested by the semaphore when the data was not available;
Assuming the message semaphore has an SCT count, a branch to step 2508 is taken. Since the simulated V instruction is message semaphore directed, the answer to system 2508 will be negative. As a result, step 2510 will be executed and will receive a negative response since the simulated V instruction is not a test instruction. Since the simulated V instruction may not be rejected when the semaphore's SCT field is positive, it may not be a test instruction.

Subroutine FAR, step 2513, scratch pads memory locations WE4 to WE7.
Messages that have already been transferred to the process's queue head waiting on the semaphore (Q/PR/S) are stored in the process' general registers GF0-GR.
Passed to 3. In addition, subroutine FAR changes the process control block that receives the message so that the dispatcher in step 2515 sends the process to the prepare queue Q/PR/
It can be placed in RDY. This process priority will become decisive for the purpose of the process controlling the central processing unit.

After the FAR subroutine completes in step 2513, a test will be performed before step 2514 is executed. This step will test the flop in auxiliary memory 1317 to determine if the simulated V instruction is an I/O simulated V operation. If the flop is set, a branch is taken back to Q/LC/EVQ and the next logical channel table pointed to by the head pointer in the scratch pad memory location LE is brought there.

Simulated V Operation on a Semaphore with a Non-Positive SCT Field In step 2500 of Figure 25a, if the answer is negative,
If the semaphore's SCT field is greater than or equal to zero, a branch to the V-positive subroutine shown in FIG. 26a is executed. At this point, the semaphore does not have a queue of processes waiting for messages, i.e., Q/PR/S, and may have a queue of messages, Q/M/S, if its SCT field count is greater than zero. I understand.

In Figure 26a, the first question in step 2600 will receive a negative response since this is a V command on the message semaphore. As a result, steps 2605 and 2608 are executed. At step 2608,
The flop in auxiliary memory 1317 is tested to determine if this is a simulated V instruction. If so, step 2608
a, a branch to the subroutine SVP shown in FIG. 30 is made. This subroutine allows messages to be passed on semaphore and queue Q/M/S.

For the simulated V-positive subroutine shown in FIG.
Stepping through the question of whether the link is available, i.e. whether the FLQP of a free link semaphore is equal to 0.
3000 do. Already, the SD segment's free link semaphore has been brought up by the FLSC subroutine shown in step 2401 of Figure 26a. FLQP field is a scratch pad location
It has been stored in WCC and will now be tested by step 3000. If there is a free message link available, that is, the answer is negative, then the simulated V operation is performed exactly like a V command, i.e., to B of VP, shown as step 2612 in Figure 26b. Branching is performed. This branch transfers messages created at either the LCTE or the central exception facility from scratch pad locations WE4 to WE7 to available free message links. This message link is then transferred to the semaphore Q/M/S where it awaits the process requesting the information. Therefore, this branch causes the simulated V-regular subroutine to transfer the message to the semaphore.

At step 2622, shown in Figure 26b, the next instruction will be a return to the system event poller which will perform the next simulated V operation, if any. If there are no more simulated V instructions, execution of the next instruction of the process controlling the central processing unit takes place.

Simulated V Operation on Semaphore When Free Message Link is Unavailable However, if the answer to the question in Figure 30a is affirmative, indicating that there is no free message link available, then step 3004 is executed next. be done.
Step 3004 asks if this is an I/O operation. If negative, it should be a central exception mechanism operation. Since there are no free message links to queue the messages provided by the central exception facility, a missing message link exception in step 3006 occurs. Since this is a system exception as a result of the system mode being entered in step 2706 of FIG. 27, step 3006 performs model dependent diagnostics.
The system enters a system check state to prepare the system. Therefore, step 3006 terminates the simulated V instruction for the exception condition. The remaining publications discussed below are directed only to I/O simulated V operations.

If the answer to step 3004 is affirmative, that is, the flop in auxiliary memory is set to indicate an I/O operation, step 3008 returns
The system name is brought out of main memory and moved to the scratch pad location WC0. FLS
The semaphore is bit 7 as shown in Figure 16b.
G field bits 80 to 9 from 2 to 79
Word number 2 with CCT field up to 5 (Word
No. 2) is included. For the P and V instructions previously mentioned, these fields were not used because no I/O operations were involved and therefore no logical channel or system name was initialized. However, it will now be used to queue a logical channel into a free link semaphore. As a result, when a free message link is obtained by a free link semaphore for this SD (or G segment), the message indicated by the G name is transferred to the free message link of the free link semaphore.

In step 3010, the channel count (CCT) of the free link semaphore stored in the scratch pad location WDO is tested.
If the CCT field is equal to zero, that is, the question is answered in the affirmative, then in step 3012 the G system name retrieved in step 3008, bits 72 through 79 of word 2, is written to the G field of the free link semaphore. this is,
Recognize the G segment number of the logical channel that requested the free message link. but,
CCT field is less than zero and already I/O
If a previously simulated V operation indicates that it was performed on the same SD segment, and there were no free message links available at the time, then in step 3014 the G system name retrieved in step 3008 is stored in the free link semaphore. G system name. Since each SD segment has its own unique G-address, the 300
The G-system name brought out in step 8 must be the same as the G-system name in the free link semaphore. While this semaphore in the SD segment may simulate a V operation performed on a semaphore, this would be indicated by a different displacement field, i.e., but the same G system name would be superior. Therefore, if the G system name is not equal to the system name in the free link semaphore, an illegal semaphore exception occurs in step 3014a.

However, assuming there is no problem with the G system name, the hardware gate is locked at step 3016, indicating that an unsafe system operation is to occur. In step 3018, the CCT field of the free link semaphore stored in the scratch pad memory location WCD is 1.
is decremented by one. The absolute value of the CCT field indicates that number of logical channels with free messaged links. In step 3020, the contents of scratch pad memory locations WCB to WCD are then transferred to main memory and the free-link semaphore address expanded via the FLSC subroutine, so that the current state of the free-link semaphore is will be shown. Step 302
In step 2, subroutine EWLC is executed. this
The EWLC subroutine, which queues messages on logical channels to queues Q/LC/FLS, is shown in Figure 30b.

At this time, the message taken out from Q/LC/EVQ is not available in related semaphore, Gi, Di due to lack of free message link in SD segment.
Or, it can be seen that it could not be queued to either Ga or Da. In addition, the steps for temporarily associating a message to this SD segment's free link semaphore are to change the G system name to FLS
This is accomplished by feeding the semaphore and decrementing the CCT count as shown in steps 3010 through 3020. Here, the message must be stored so that the P command makes available the message link within the SD segment, and the stored message can be transferred to the newly available free message link.

For this feature, a queue Q/LC/FLS is formed to store messages in a pending state until a free message link within the G segment becomes available. This queue Q/LC/FLS performs the same function as the Q/PR/FLS for V instructions. Since the queue Q/LC/FLS links all logical channels waiting for a free message link on any SD segment, there is only one Q/LC/FLS for all free link semaphores in main memory. This Q/LC/FLS has several different system names that recognize the various free link semaphores within the SD segment.

Queue Q/LC/FLS has a pointer and absolute address provided in the scratch pad memory at location 2F as shown in Figure 19a.
This word recognizes both the head and tail of Kyu. When determining which link in the queue is associated with a free link semaphore, the G name stored in the free link semaphore is compared to the G name in the Q/LC/FLS. When a link is removed from a Q/LC/FLS, the previous LCTE intra-next link field is modified so that it recognizes the link pointed to by the removed link. If LCTE happens to be the first link, location F
The head pointer of is changed.

In FIG. 30b, step 3030, Q/LC/
Logical channel table entries retrieved from EVQ are queued to Q/LC/FLS. If this queue already has an entry, this queue is
It will be added to the previous LCTE entry in FIFC fashion. If there was no previous LCTE entry, this queue would be started.
Therefore, in step 3030, the tail pointer of the absolute address in main memory is set to Q/
It seems to be new and has just been made into a queue in LC/FLS.
The LCTE will now be changed to indicate that it is Kyuu's tail.

At step 3032, the logical channel status byte is updated. Even though the message has not been passed to the appropriate process, this status byte is modified to indicate that the simulated V instruction was actually executed. The message is Q/
This is the result because it is not queued in LC/FLS. However, since the message did not reach the appropriate process, the status byte will indicate that the simulated V instruction execution was unsuccessful.

This will terminate the EWLC, so step 3
A branch back to 024 is taken. Step 302
4 indicates that the hardware gate is unlocked and an indivisible operation of writing and transferring data has been performed. In step 3026, if any,
The next simulated V operation is performed.

If a free message link is available,
Removing Messages from a Q/LC/FLS Semaphore Once a Q/LC/FLS is given or created, it must be explained how to move the message associated with the queue to the appropriate semaphore or semaphore. . For this state to occur, it is necessary to give a P command to the message semaphore to break the message link. This now free message link is returned to the SD segment's free link semaphore where it is used to store the message contained in the Q/LC/FLS. This can be done if the free link semaphore has a value less than or equal to 0.
This is the case with an OCT field.

As a more specific example, the P command for a semaphore accompanied by a message will be explained with reference to FIG. 22a. Since we want a situation where the message link is free, we consider branches from step 2200 to step 2205 and step 2207 where the SCT count of the message semaphore is greater than one. The P command is executed in this semaphore, receives a message from the semaphore, and frees the message link. In step 2205, if
If the SCT field count is equal to 0, then
It must be noted that free message links cannot be used. But let's consider this situation later.

For simplicity, let us assume that step 2218 of Figure 22b has been reached. This results in Word No.2
This is because we now have a situation where we test the free link semaphore channel, count, in to determine if it is less than or equal to zero. If the count is less than or equal to 0, it means that there is a conceptual Q/LC/FLS for this free link semaphore. As a result, in step 2225, the system mode is set and a branch is made to FIG. 22d and step 2226. This is the RLCM subroutine shown in Figure 31a. The RLCM subroutine represents a release message link to a logical channel. This subroutine specifies the LCTE entry, the message destination semaphore, and moves the message to that semaphore.

In this way, step 3100 (FIG. 31
In A), subroutine FLC, which is a fetch logical channel, is executed as shown in FIG. 31b. In step 3120, Q/
Looks for LO/FLS and specifies a semaphore with the same name as given by the SD segment's free link semaphore. thus,
Using the head pointer to Q/LC/FLS, check the first LCTE entry and appropriate G name. If the Gname of the first LCTE entry does not match the Gname of the SD segment's free link semaphore, then
Take the LCTE entry and do the same comparison. Even after testing all Q/LC/FLS, the same G
If the name is not found, step 312
Illegal semaphore exclusion of 0a is performed. However, once the first G name is identified, step 3
122 is executed.

What should be noted here is that Q/LC/FLS is
Depending on the absolute value of the FLS semaphore channel count, it is possible to have several identical G-names. For example, if the channel count of the semaphore is 2, the Q/Q to be placed in the free message link for the free link semaphore in the SD segment is
There should be two LCTE entries in the LC/FLS. However, in this case, only one free message link is available due to the currently executing P instruction, so only the first one with the G name is added to the queue.

In step 3122, the system name is
Removed from LCTE and moved to scratch pad memory location WD4. Step 3124 indicates that the hardware gates are locked and a system critical operation associated with one individual action is performed. In step 3126, the free link semaphore channel count (CCT) in the scratch pad location WCD is increased by one, indicating that the number of logical channels LC waiting for a free message link has been decreased by one. In step 3128, Q/LC/
Logical channel table entries from FLS are removed. This step involves adding the next link field of the previous LCTE in the same way as removing a message link or process link from the Q/M/S or Q/PL/PLS, as described previously. This includes creating queues sequentially by changing the .

Critical against Q/LC/FLS
After performing the operation, step 3130
unlocks the hardware gate. In step 3132, the absolute address of the semaphore discussed above is expanded. Step 3132 is necessary because the P instruction that freed the message link may be on a different semaphore than the one identified by the system name.

In step 3134, the removed from the queue
The message in LCTE is moved to scratch pad memory locations WE4-WE7, completing subroutine FLC.

When the FLC subroutine ends, the process returns to FIG. 31a and executes step 3102 which calls the PSEM subroutine. This subroutine checks the semaphore since the semaphore count is greater than zero. The PSEM subroutine is also shown in more detail in Figure 31c.

More specifically, in step 3140, it is checked whether the D number of the GD system name is a multiple of eight. What is D number?
The registration number of the appropriate semaphore within the SD segment, which by definition must be a multiple of 8. In steps 3142 and 3144, the two words of the semaphore are
Scratch pad memory location
Moved to WC4 and WC5.

Once the semaphore is obtained, a similar check is made for the semaphore fetch routine.
This step 3146 checks the semaphore's stag field to determine that the semaphore is a message semaphore.
In step 3148, the semaphore's SCT field is checked to ensure that it is less than the SMC field. Thus, steps 3146 and 3148 test the validity of the retrieved semaphore.

In step 3150, the SCT field is tested. SCT field count is 0
If the following occurs, an illegal semaphore exception or illegal semaphore exception 3150a occurs. If the count in the SCT field is less than or equal to 0, it means that the process was queued for the semaphore, resulting in this result. However, as described later, the Q/LC/
If there is a message in the FLS, the process will not enter a wait state. Under the circumstances of the P command, the message would have been moved to the process when the Q/LC/EVQ was dequeued. If the SCT field count is greater than zero, a branch is taken to step 3152, where the semaphore pointer field is tested. More specifically, these fields are the Message Queue Head Pointer (MQHP) and the Message Queue Tail Pointer (MQTP).
and must not be equal to 0 and must be a multiple of 8, since the semaphore must be double word (8 bytes) aligned.
If the SCT field of step 3150 is equal to 0, steps 31-54 are executed.
Since the SCT field is equal to 0, there is no queue, so the MQHP and MQPT fields must also be 0. If any of these conditions are not met, step 31
50a illegal semaphore exception is performed. This ends the checks provided by the PSEM subroutine.

When the PSEM subroutine ends, the process returns to FIG. 31a and the subroutine TAML26 shown in FIG. 26c
13 is executed. A free message link has just been added to the queue of free link semaphore, i.e. Q/ML/FLS
This subroutine tests access to a message link since it is known that it has been created or added. The relative address of this message is determined by step 3104 in the scratchpad memory location W35.
Stored in This address is the free link queue pointer PLQP of the free link semaphore that identifies the location of the free message link. In step 2617, illustrated in FIG. 26c, the result of step 2134 is the scratch pad location WE4-WE
The message entered in 7 has been newly developed. Written to the main memory location of the free message link.

Step 3106 locks the hardware gate. Step 2619 creates a subroutine QML which is a queue of messages for the semaphore Q/M/S. The newly free message link that stores the LCTE message must now be attached to the semaphore. Entering Figure 31, SCT of semaphore
There is no need to check the message link since it is already guaranteed that the field is greater than or equal to zero. The QML subroutine is the main
Writes the new semaphore to memory and rewrites the pointer field (if necessary) in the message semaphore to indicate that the new message has been added to the semaphore queue Q/M/S.

In step 3108, the logical channel state is revised to indicate that the now successfully simulated V instruction has been executed, and in step 3110, the hardware gate is updated as the information has been moved to main memory. is unlocked.

This allows step 3 of the RLCM subroutine to
112 is completed and it is possible to return to step 2227 of FIG. 22d. The system mode is now reset. The system control operation controls the execution of the simulated V instruction, and now that the simulated V instruction has finished, the process mode can be re-entered. In step 2228 of Figure 22d, the P operation ends and at this point a system event flag is entered to determine if another logical channel should be used.

In this way, a logical channel table entry from the Q/LC/FLS is sent to the appropriate semaphore such that a message being supplied by an I/O interrupt is given to the appropriate process. FIG. 31 shows the actual dequeuing of . This is LCTE
This is the situation for intermediate or terminal messages in words 8-11 of the LCTE, or attention messages in words 12-15 of the LCTE.

Q/ for processes that require messages
Removing Messages in LC/FLS There is another way to access Q/LC/FLS. In this situation, a process controlled by a central processor is executing a P instruction for a certain message semaphore.
Occurs when the semaphore's SCT field is equal to 0. This situation is illustrated in Figure 24a and the subroutine
Previously described in connection with PMZ2206. In this case, the message is Q/PR/
Moved from one process in the FLS, the message is never bound to a semaphore queue Q/M/S.

To be more specific, in the following explanation, V
instructions, i.e. the resulting Q/PR/
FLS or simulated V instructions, i.e. the resulting Q/LC/FLS
as provided by and not in the actual P command described solely for the purpose of giving context.
Focus your attention on the concept of getting the previously intended message. The PME subroutine indicates that the previous process currently has a free message link to put the message in the message semaphore, i.e. the previous process cannot deliver the message, and therefore the process still has the message semaphore. Recall that we need to determine whether or not we have . Thus, a situation has arisen in which all free message links in the SD segment have been used and a process has attempted to perform a V operation without success. Because of this situation, the process is put into queue Q/PR/FLS and waits for the message link in the SD segment to become free.
Once the free messages in the SD segment are available, the process can be Q/PR/FLS
It is possible to remove the command from the V command and execute the V command. However, before this situation occurs, the process is running on the same SD
Execute the P instruction on the segment. The message that was intended to be delivered but could not be delivered because there is no free message link is the message that the process controlled by the central processor is currently requesting by its P command, so Q/ Explore PR/FLS. Once the message is identified, the process executing the P instruction obtains the message directly from the process in Q/PR/FLS and links this process to the free link semaphore, i.e., Q/PR/FLS.
This same situation of dequeuing FLS occurs for messages from simulated V instructions, so queue Q/LC/FLS
This queue will also be searched since it may have a message requested by the process via its P command. Free link semaphore is less than 0. If it has a CCT field, this is determined. Under such conditions, it is known that a queue Q/LC/FLS exists and that the Q/LC/FLS has the possibility to store the requested message. This possibility is LCTE in Q/LC/FLS
The entry's GD number is checked by comparing it with the SEG. The SRA of the process executes the P instruction.

More specifically, step 24 in FIG. 24a
In step 01, the free link semaphore is retrieved, and in step 2402, the free link semaphore is retrieved.
The channel count field of the semaphore is tested to see if it is less than or equal to zero. If the CCT field is less than or equal to 0, this means that the simulated V instruction attempted to pass the message and was not successful, so there is no free link.
Logical analysis for semaphore Q/LC/FLS
Indicates that an entry has been made in the channel's queue. Thus, if the answer during step 2402 is YES, step 2416 of FIG. 27a is executed in which the queue Q/LC/
Search the FLS to see if the message requested by the P command exists.

The first step in FIG. 32a is subroutine 3.
200. The SLCQ subroutine searches for logical channel queues and
Returns LC number message and count. More specifically, as shown in FIG. 32b, in step 3230, search for Q/LC/FLS,
Find a semaphore with the same G name as the G number of FLS word No. 2, and a semaphore with the same D as SRA in the semaphore name of the D instruction. This is Clutch Pad Location 2
This is done by accessing the queue linkage which retrieves the absolute address of F and checks the system name. If the G names are equal, ie, the semaphore is in the SD segment, then the D numbers are compared. This is Q/
This is the D number of the system name stored in the LCTE of the LC/FLS, and is the SRA name of the semaphore given by the P command. If they are equal, it indicates that the P instruction attempted to supply the message to the appropriate semaphore being executed. When such a situation occurs, the process executing the P instruction receives the message and therefore continues its execution. Besides, Kyu Q/LC/
The LCTE entry in the FLS is removed as it has passed the message to the appropriate process. In this situation, matching the semaphore name will cause the waiting process and the free
This explains why there are no Q/LC/FLS messages waiting for a link.

Thus, in step 3232, the question is asked whether a logical channel LC with the same system name as the semaphore was found. This results from a similar search as in the SPLQ subroutine of Figure 24d. Note that the FLS semaphore indicates by the CCT field that a simulated V operation was attempted and was not successful, so the G number of the system name must be determined. . If this G number is not found, an illegal semaphore exception is performed in step 3230a.

However, even if the G names are equal, the displacement number is not equal to SRA, so if this condition occurs, step 3234 is executed to set the indicator in auxiliary memory 1317a to zero. This ends the SLCQ subroutine since there is no message to be passed to the message semaphore where the P instruction is being executed. However, if the system name's G and D numbers are equal to the semaphore's SEG and SRA numbers, then the answer to step 3232 is yes.
Then, step 3238 is executed. This sets the flop indicator in auxiliary memory 1317a to 1, indicating that the message has been found and can be moved to the process that executes the P instruction. In step 3240,
The logical channel table address is stored in scratch pad location WD4 and in step 3242 the message is moved to scratch pad locations WE4-WE7.

Once this address has been stored, Figure 32a
Return to You will be asked again if the LCTE entry was found. If the answer is no, branch 2403 is taken which returns to Figure 24a;
Kyu Q/PR/FLS is searched here. The answer is
If YES, this indicates that the message can be used, so step 3204 is executed. Next, in step 3204, a question is asked whether the P instruction being executed is a test instruction. If so, the condition code is set to 0 in step 3206 to indicate that the instruction is completed, and the condition code is set to 0 in step 3206 to indicate that the instruction is completed.
08 is executed. If the answer is no, this is P
Indicates that the instruction is not tentative, so step 3208 is executed.

Step 3208 is the subroutine TMGR,
It transfers messages to the general register. This subroutine is shown in FIG. 32c and includes a step 325 that reads messages stored in scratch pad locations WE4-WE7 and moves them to general registers GR0-GR3 of the process executing the P instruction in step 3252.
Contains 0. In this way, a message was moved from the Q/LC/FLS to the general register of the process executing the P instruction without queuing the message semaphore P/M/S.

Upon completion of subroutine TMGR, step 321 locks the hardware gate.
0 is executed. The indication that the simulated V operation was unsuccessful is negated because the message in the logical channel table entry has been passed to the appropriate process. These actions that revise the status of various queues must be performed. Step 32
At 12, the channel count field of the SD segment's free link semaphore is incremented by one. This means that the number of pending unsuccessful message passes is reduced by one.
The revised channel count is set in step 3.
At 214, the free link semaphore is written to main memory. In step 3216, the logical channel table entry is removed from queue Q/LC/FLS and the queue is reordered to prevent removal of this link. The address of this LCTE is the subroutine
Stored in scratch pad location WD4 by SLCQ. At step 3218, the logical channel state is revised to indicate that a successful simulated V operation has been executed because the message has been moved to the appropriate process. Step 3220 unlocks the hardware gate, indicating that an atomic operation has been performed. Step 3222 increments the instruction count and the next instruction is executed as shown in step 3224.

If the process searching Q/LC/FLS does not find a segment relative address SRA equal to the displacement D number of the system name, the process executing the P instruction
It is placed in a waiting state as shown in the figure below. Furthermore, Q/LC/FLS cannot be changed because no LCTE entry to store the message is provided to the P instruction.

Thus, it has been shown that both the central exception mechanism and the system event poller are simulated processes, allowing simulated V operations to communicate data to the central processor process.
Access to semaphore is by processing
For SEG, SRA names, simulated V operations have system names C, D.
However, a basic test of the semaphore count field with the V operation is performed in each situation. This test controls the final transference of the message. Thus, if the SCT field is negative, the process's queue is
Should be linked to PR/S. When a simulated V operation gives a message to a semaphore, the first process in the queue is removed and the ready state Q/PR/
Set to RDY. The messages provided by the simulated V operation are for scratch pad locations WE4 to WE7.
by copying the contents of the semaphore into general registers GR0-GR3 of the process control block of the process associated with the semaphore. Furthermore, a semaphore whose number of associated processes is reduced by one increases its SCT field by one.

If the SCT field is not positive, there are no processes waiting on the semaphore to which this message is directed. The message is then copied to the SD segment containing the semaphore, and the semaphore Q/
Connected to M/S. If the message cannot be moved to a free message link, a Q/LC/FLS is provided for I/O interrupts. The central exception mechanism provides another exception condition, which causes a system check condition, so the Q/
Do not call LC/FLS.

Therefore, it has been shown that conditional operations can be obtained by I/O interrupts.
The first condition is that the hardware gate is locked. In this case, it is determined that the execution of the procedure at hand is more important than the transfer of messages from the I/O subsystem. The second condition occurs after the I/O message is transferred to the central processor.
Messages initially depend on the existence of the central processor at the time, ie, whether a process has already requested the message or whether the message can be delivered to the appropriate semaphore. But eventually the message is passed to the appropriate process. This delivery is accelerated by the message's priority. Even in that case, the priority of the process is important because if the process is not under the control of the central processor, the process will be placed in Q/PR/RDY depending on its priority. Messages are therefore integrated with internal messages and are dependent on the state of the entire data processing system. Thus, message transport depends on the conditions of the semaphore on which the simulated V operation occurs, and on the state of the system, ie, the priorities of the running process and other processes in the queues Q/PR/RDY.

Although the invention has been described with respect to particular embodiments, many modifications will be apparent to those skilled in the art. It is therefore intended that the invention be broadly covered within the spirit and scope of the appended claims.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a multiple programming system utilizing the present invention. FIG. 2 is a schematic diagram of various hardware structures used in the present invention. FIG. 3 is a legend of terms and symbols used in the saved area of the register shown in FIG. FIG. 4 is a schematic diagram of the process control block. FIG. 5 is a schematic diagram of a system for addressing process control blocks. FIG. 6 is a system-based block diagram of the present invention. Figures 7A and 7B are schematic diagrams of a stack segment and stack frame, respectively. FIG. 8 is a block diagram of a system for addressing the queue of processes in the G-segment, specifically the G0 segment. FIG. 9 is a schematic exploded view of the G0 segment showing process queuing and process linking. Figures 10a-10l are block diagrams of structures within the PCB. Figures 11a-11r are
This is a block diagram of the structure within the system base. FIG. 12 is a schematic diagram of the user addressing table and system segments using the system base and PCB structure. Figures 13a, 13b and 13c are schematic diagrams of the control device. 14a-14i are flowcharts of the dispatcher device in firmware. 1st
Figure 5 shows the semaphore descriptor (semaphore
2 is an exploded view of the descriptor segment and its configuration; FIG. Figures 16a-16d are block diagrams of the semaphore structure used in this system. FIG. 17 is a schematic diagram of an address development mechanism for a semaphore. FIG. 18 is a schematic diagram showing the relationship between semaphore descriptor segments and G0 segments. 19a and 19b show the first
3 is an exploded view of the scratch pad memory of the logical storage device of FIG. 3, showing the overall word structure thereof; FIG. Figures 20a and 20b are flow diagrams of the semaphore descriptor fetch subroutine used for all P and V instructions. Second
FIG. 1 is a flowchart of the P instruction for a semaphore without a message. Figure 22
a-22e are flow diagrams of P instructions for semaphores with messages. Figure 2
3a-23h are a flowchart of the EVP subroutine called by the P and V instructions to transition a running process to a standby state. Figures 24a-24d are a flowchart of a PMZ subroutine for forwarding messages without queuing on a semaphore. Figures 25a-25i show the semaphore
V for semaphore when SCT field is negative
2 is a flowchart of instructions. Figure 26a~
26b is a flow diagram of a V instruction for a semaphore when the SCT field of the semaphore is positive. Figures 27 and 27a show the System Event called at the end of the latest instruction.
2 is a flowchart of Poller (system event poller).
Figure 28 is populated by the System Event Poller. I/O Event Handler
This is a flowchart. Figures 29a and 29b are schematic diagrams of logical channel table entries and queues using logical channel table entries. Figures 30a and 30b are flow diagrams of simulated V instructions for a message semaphore when the message semaphore's SCT field is positive and no free message links are available. 31a, 31b, 31c can utilize free message links,
and is a flowchart of a simulated V instruction for a message semaphore given a logical channel queue (Q/LC/FLS) on a free links semaphore. Figures 32a and 32b are
FIG. 3 is a flowchart of a simulated instruction for a message when the SCT field of the message semaphore is zero and Q/LC/FLS is present. FIG.
Important symbols in the drawings are as follows. 101...processor subsystem, 102
... Storage subsystem, 103 ... Peripheral subsystem, 10 ... Central processing unit, 105 ... Output control device, 106 ... Peripheral control device, 107 ... Adapter, 108 ... Peripheral I/O device.

Claims (1)

[Scope of Claims] 1. A central processing unit (101, FIG. 1) that processes data under the control of a selected one of a plurality of processes each consisting of a plurality of instructions.
and a plurality of data structures called semaphores (Figures 15, 16A-16D) used to exchange information (messages or events) between processes, each semaphore being A process for storing references (J, P) of processes waiting for information to be generated by other processes.
Kyu (Q/PR/S; Figure 9, 803a, 80
3b, 803c, 803f, 803g; 17th
Figure, 802; Figure 18, 1802a-1802
d, 1804a, 1084b, 1808a, 18
08b) and is associated with a memory location called
Furthermore, each semaphore has a message queue (Q/M/S; FIG. ; FIG. 17, 1708, 1710)) (1602, FIG. 15, FIG. 16B), said central processing unit stores a corresponding memory location of a running process, called a "running process". Program instructions (P instructions: SEP, SEPM; V instructions: SEV,
SEVF, SEVL) initiates a process synchronization operation (P or V operation), the first type of this operation (V operation) allows information to be transferred from the running process to the semaphore; The second type of operation (P operation) transfers the information requested by the running process to the running process immediately if it is available in the addressed semaphore; If not found in the specified semaphore, the running process was placed in a standby state, allowing a reference to that process to be stored in the semaphore's process queue (Q/PR/S). multiprogramming,
In a data processing device operating in a multiprocessing environment, a first field (SCT) provided in each semaphore (see FIGS. 16a and 16b) indicating a count that is positive, negative, or zero; Queu related to semaphore (Q/PR/
a second field (PQHP, PQHP/MQHP) provided in each semaphore (see Figures 16a and 16b) indicating the first location (PQHP or MQHP) of the S or Q/M/S); means for, in response to a P or V instruction, addressing a particular semaphore identified in said P or V instruction (2020; FIGS. 20a, 20b);
) and means for changing the value of said count (SCT) in response to the type of instruction (P or V), wherein this change caused by a V operation is the opposite of the change caused by a P operation. , such that the count is initially zero and the sign of the count (SCT) at any moment is the same as the queue (Q/PR/S or Q/M/S) associated with the semaphore. ) indicates whether it contains a process (Q/PR/S) or a message (Q/M/S),
means in which the absolute value of said count represents the number of processes or messages waiting in said queue; and means responsive to the sign of said count (SCT) and dependent on the type of instruction P or V. If it is a V instruction and the code indicates a process queue (Q/PR/S), then the information is sent to the process in the first location (PQHP) of the queue (Q/PR/S). Transferred, if counting (SCT), message queue (Q/M/S)
If it has an opposite sign indicating that it is a P instruction and the sign of the count (SCT) is If the process queue (Q/PR/S) is indicated, the running process that executed this P command is placed in a standby state and the process queue (Q/PR/S) is
PR/S) and if the count (SCT) has an opposite sign indicating that it is a message queue (Q/M/S), then the first of that message queue (Q/M/S). A data processing device operating in such a way that a message located at a location is forwarded to the running process. 2. A third field (STAG) provided in each semaphore that indicates the type of semaphore (with message or without message), and a fourth field provided in each semaphore that indicates the maximum value of the count (SCT). (SMC)
2. A data processing device according to claim 1, comprising: means for comparing the count (SCT) with the maximum value (SMC) during each synchronization operation (V or P). 3 Free link semaphore (FLS, 1504,
Another type of semaphore called a semaphore (Figs. 15, 16D) is associated with each messaged semaphore (1602, Figs. 15, 16B), and said free link semaphore is defined as a process related to a free link semaphore.・
Q/PR/FLS (Fig. 18, 1804
a, 1804b) and a fifth field (PQHP) indicating the initial location of the associated process queue called “Queue of Free Message Links” (Q/
a sixth field (FLQP) indicating the beginning of a free message location forming another queue called ML/FLS); ) for determining a free message location by checking the sixth field (FLQP) when the symbol indicates a message queue (Q/M/S), and when this free message location is not available; The running process and the idle link semaphore (Q/
In the case of execution of a P instruction with a message (SEPM), when the sign of the count (SCT) indicates a process queue (Q/PR/S), 2. A data processing device according to claim 1, further comprising means for incorporating message locations freed by an instruction into the queue of free message links (Q/ML/FLS). 4 Free link semaphore (FLS, 1504,
Another type of semaphore called a semaphore (Figs. 15, 16D) is associated with each messaged semaphore (1602, Figs. 15, 16B), and said free link semaphore is defined as a process related to a free link semaphore.・
Q/PR/FLS (Fig. 18, 1804
a, 1804b) and a fifth field (PQHP) indicating the initial location of the associated process queue called “Queue of Free Message Links” (Q/
a sixth field (FLQP) indicating the beginning of a free message location forming another queue called ML/FLS); ) for determining a free message location by checking the sixth field (FLQP) when the symbol indicates a message queue (Q/M/S), and when this free message location is not available; The running process is placed in a standby state and the free link semaphore (Q/
In the case of execution of a P instruction with a message (SEPM), when the sign of the count (SCT) indicates a process queue (Q/PR/S), 3. A data processing device according to claim 2, further comprising means for incorporating message locations freed by an instruction into the queue of free message links (Q/ML/FLS).