JPH03154945A - Shared memory management method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a method for managing shared memory between tasks in a multitasking system in which each task has an independent logical address space.

[Conventional technology]

In a multitasking system where multiple tasks operate in parallel, one way to transfer data between these tasks is to provide a shared memory that can be accessed by multiple tasks, and transfer data to the shared memory. A method of communicating between tasks by reading and writing is known. In order to realize such a shared memory, the system considers the possibility of access to the shared memory and
It is necessary to provide a mechanism to ensure reliable access.

Accessibility refers to the fact that the contents of shared memory can be read and written in the same way as other non-shared memory, and access certainty refers to the fact that a series of shared memory accesses is atomic and that other This means that shared memory access by tasks is not performed. Note that access reliability is not a function that is necessary only for shared memory, but is a function that is necessary when using various resources possessed by tasks.
xclusion) problem.

Now, when implementing shared memory in a multitasking system where each task has its own independent logical address space and does not have a task global address space common to all tasks, the following methods have traditionally been used. It had been.

First, accessibility is achieved by allocating shared memory, which is a logical system resource, to a part of the task-specific address space and changing the logical-physical address space. By allocating the same shared memory to multiple tasks in their own address spaces, memory can be shared among arbitrary tasks. Allocating shared memory to a part of a unique address space in this way is called attaching shared memory.

Furthermore, access reliability is achieved by using semaphores, which are general-purpose mechanisms that realize mutual exclusion between tasks, without providing a mechanism specifically for shared memory.

Examples of such systems include the UNIX operating system developed by AT&T of the United States.

[Problem to be solved by the invention]

The above conventional technology was developed with systems such as minicomputers that have a vast logical address space in mind, and in systems using microprocessors that have only a small logical address space, programs and data specific to each task are This problem occupies most of the task's logical address space, making it impossible to allocate the logical address space to attach multiple memories (shared memory).

An object of the present invention is to make it possible to use a large number of shared memories by making it possible to map a plurality of shared memories to the same logical address even in a system where the size of the logical address space is relatively small.

[Means to solve the problem]

To achieve the above object, the present invention provides a shared memory management table for managing shared memory, which is a system resource, an attached management table for managing the correspondence between tasks and shared memory, and a shared memory management table for managing shared memory, which is a system resource. The present invention is characterized in that it includes an attaching means for making the association, a locking means for starting exclusive access to the shared memory, and an unlocking means for terminating the exclusive access to the shared memory.

[For production]

The shared memory management table holds the location, size, and state of shared memory on main memory.

The attach management table holds the position of the shared memory in the task logical address space when the task attaches the shared memory.

The anti-quench means is executed when a task attaches a shared memory, and stores the position of the shared memory on the task logical address space in the attach management table. At the time when the task executes the attach means, the logical-physical address mapping is not switched.

The locking means is executed before the task starts accessing the shared memory, changes the state of the shared memory management table to locked, and also changes the logic of the task based on the values of the shared memory management table and the attachment management table.
Change physical address mapping to allow tasks to access shared memory. At this time, if the state of the shared memory to be locked is already locked, the locking process is set to fail, thereby achieving mutual exclusion of shared memory access.

The unlocking means is executed after the task finishes accessing the shared memory, and sets the state of the shared memory management table to unlocked so that it can be locked by other tasks, and also changes the logical-physical address mapping of the task. , making shared memory access impossible.

When the task accesses the shared memory after executing the attaching means, it performs exclusive access as a series of processes of executing the locking means, accessing the shared memory, and executing the unlocking means.

The attach method does not change the address mapping,
To change address mapping using locking means,
The attach means can allocate multiple shared memories to the same logical address, and the allocated addresses are stored in the attach management table, so the lock means can refer to the attach management table. It becomes possible to change the logical-physical address mapping.

[Example]

Below, a practical example of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram of hardware according to this embodiment.

The hardware of this embodiment is a CPU that performs data processing.
(Processing device) 1, main memory 2 that stores programs and data executed by the CPU 1, node disk (hereinafter referred to as El) 3, which is a secondary storage device that stores programs and data, and floppy disk 4 , a keyboard 5 for inputting characters and functions, a display 7 for displaying processing results, etc., and a printer 8 for printing processing results, etc. It is comprised of an address converter 9 that converts a logical address, which is a memory address output by the CPU 1, into a physical address, which is a memory address used when accessing the main memory 2.

FIG. 3 shows an explanatory diagram of the address converter. The address converter 9 is composed of a mapping table 91 and an adder 92. The input logical address value is divided into an index part and an offset part, and the corresponding physical address value is calculated by adding the value obtained by converting the value of the index part using the mapping table 91 and the value of the offset part. Ru.

FIG. 4 shows an explanatory diagram of a method of converting a logical address to a physical address. The logical address value of the bit is divided into an index part of k bits and an offset part of (rou A) bits, and the value of the index part is stored in the mapping table 9.
The entry number is 1.

The mapping table 91 is an array having 2 entries, and each entry stores a base value of a physical address. Then, by adding this base value and the value of the offset part of the logical address, an m-bit physical address value is calculated.

FIG. 2 shows an explanatory diagram of the present invention.

Each task has an independent logical address space, and normally cannot access the address space of other tasks.

Shared memory is distinguished by a number (shared memory number).
They exist in non-overlapping positions in physical space.

A task removes shared memory from part of its logical space. In the example in Figure 1, task A has shared memory #1 and #
2. Task B has attached shared memories #2 and #6. Although each task attaches two shared memories to the same address, the logical-physical address mapping remains unchanged, so no contradiction occurs.

When actually accessing the shared memory, lock processing and unlock processing are performed before and after the access processing to ensure exclusivity of access. In lock processing, in addition to exclusive control, logical-physical address mapping switching processing is performed,
Allows tasks to access shared memory.

Next, the data structure used in this example is shown.

In this embodiment, a task control block (hereinafter abbreviated as TCB) 20. Shared memory management table (hereinafter abbreviated as SMB)
60, Attach Management Chiful (hereinafter abbreviated as ATE) 35
We use three types of data structures:

FIG. 5 shows the configuration of the TCB 20. The TCB 20 is a data structure that corresponds one-to-one with tasks, and includes a link pointer 2001, task priority 2002, and task status 20.
03, Register save 2004, ATE pointer 200
5. Each field of the lock number counter 2006 exists.

Link pointer 2001 holds addresses of other TCBs 20 and is used to create ready queues and various queues.

Task priority 2002 indicates the priority at which a task is executed.

The task status 2003 stores information necessary for scheduling a task, such as executable/waiting.

The register save 2004 stores the values of internal registers of the CPU 1 necessary for correctly suspending/resuming task processing. When switching the task to be executed, save the register 2004 in the TCE 25 of the task whose processing is interrupted.
The value of the internal register of CPU 1 at the time of interruption is saved, and the value of register 2 in TCB 25 of the restarted task is saved.
By restoring the contents of 004 to the internal register of the CPU 1, the task execution environment at the time of interruption is reproduced, and restart is performed correctly.

Since this is a widely known method of operating the time/minute side track system, which switches between a plurality of tasks one after another, a detailed explanation will be omitted.

The ATB pointer 2005 indicates the address of the ATE 35, which will be described later, and is used to manage the shared memory attachment state of the task.

A lock number counter 2006 indicates the number of shared memories locked by a task. This value is updated during lock processing and unlock processing, and is used to avoid dropouts during lock processing.

FIG. 6 shows the configuration of the SMB 30. The SMB 30 has a data configuration that corresponds one-to-one with the shared memory, including a start address 5001, shared memory length 3002, and ATB.
There are fields such as a pointer 3003 and a shared memory type Q 3004.

The start address 5001 holds the start address value in the physical space of the shared memory.

The shared memory length 3002 holds the length of the shared memory.

The ATB pointer 3003 holds the address of the ATB 35, which will be described later, and is used to manage tasks attaching to the shared memory.

A shared memory status 3004 holds the status of whether the shared memory is locked or not.

Next, FIG. 7 shows the configuration of the ATE 35. ATB 3
5 is a data structure for managing the correspondence between tasks and shared memory, and includes fields of link pointer a 3501, TCB pointer 6502, link pointer b 3503, SMB pointer 3504, and attach address 3505.

A link pointer, 3501, holds the addresses of other ATEs 35 and forms a list for the ATB 35's tasks. On the other hand, the link pointer 63503 is also A
Holds the address of TE 35 and forms a list for shared memory of ATB 35. , the head of the list for tasks in ATB 35 is ATB 35 pointing to ATE pointer 2005 in TCB 20, and the head of the list for shared memory is ATB pointer 6 in SMB 20.
006 is the ATB35 indicated.

TCB pointer 5502 indicates the address of the task's TCE 20 that holds the task side list to which the ATBS 5 belongs.

Similarly, the SHE pointer 6504 points to the shared memory SM which holds the shared memory side list to which the ATB 35 belongs.
Indicates the address of E30.

The attach address 6505 holds the start address of the shared memory in the task logical space when the task indicated by the TCB pointer 35o2 attaches the shared memory indicated by the SMB pointer 3504.

The relationship between tasks and shared memory is a many-to-many relationship in which a task can attach multiple pieces of shared memory, and shared memory can be attached from multiple tasks. A many-to-many correspondence is expressed by linking through a double list structure: a side list and a shared memory side list.

The relationship between TCB 20, SMB 50, and ATB 35 is shown in FIG. In Figure 8, task A is shared memory #1.
and #2, and the relationship between each data when task B attaches shared memory #2 is shown as an example.Next, the contents of attach processing, lock processing, and unlock processing in this embodiment are explained below. explain.

FIG. 9 is a flowchart of the attach process.

The attach process uses the shared memory number to be attached,
And, it is executed using the attach address on the task logical space of the shared memory as an argument.

First, obtain one ATB 35 in step 5001,
The value of the attach address specified as an argument is stored in the attach address 5505 of the ATB 35 obtained in step 5002.

Next, in step 5003, the acquired ATB 55 is connected to the head of the ATB list held by the task to be attached.

Specifically, the address of the acquired ATE55 is stored in the ATB pointer 2005 of the TCE 20, and the acquired ATB
35 link pointer a TCE 20 A to 3501
The old stored value of the TB pointer 2005 is stored, and the address of the TCB 20 of the task performing the touch with the TCB pointer 3502 is stored.

Subsequently, the shared memory 9 attached in step 5004
Connect the acquired ATB55 to the top of the blocking ATB list. In this case as well, the ATB pointer 60 of SMB 30
Store the address of the acquired ATB 35 in 06 and send the SMB to the link pointer b 3503 of the acquired ATB 35.
The old stored value of ATB pointer 6003 of 30 is stored, and S
S of shared memory attached to MB pointer 3504
Stores the address of HE 30.

The above is the content of the attach process. Next, a flowchart of the locking process is shown in FIG.

Lock processing is executed using one or more shared memory numbers to be locked as arguments. When one task locks a certain shared memory, other tasks cannot lock the shared memory and wait. However, if two tasks each lock the same multiple pieces of shared memory. , locking one task at a time may lead to a deadlock situation where each task waits for another task to unlock it, so it is possible to lock multiple shared memories in one locking process. Also, during row lock processing, lock other shared memories until they are all unlocked.In step 6001, check the value of the lock number counter 2006 of the TCB 20. If it is 0, slap 6002
If the value is not 0, the process proceeds to step 6011, notifies the task that the lock process has failed, and ends the process.

In step 6002, it is checked whether there is any overlap in the mapping of the shared memory specified as an argument on the task logical space. The first position in the logical space is ATB
The attach address 3505 of SHE 35 and the size of the shared memory are determined from the shared memory length 3002 of SHE 30 and checked. If there is an overlap as a result of the check, the process proceeds to step 6011, where the lock processing is terminated as a failure, and if there is no overlap, the process proceeds to step 6006.

In step 6003, SMB! of the shared memory to be locked is selected. Check the value of shared memory status 3004 of 10.

Determine whether all target shared memory is unlocked. It is assumed that at least one shared memory is in the locked state and is waiting for a memory lock. This waiting state is released by unlock processing to be described later, and when the processing is restarted, the process returns to step 6003 and the determination is made again.

If all the target tasks are in the unlocked state, the process advances to step 6004, and one of the shared memories specified by the argument is selected.

Next, the SHE of the shared memory selected in step 6005 is
The shared memory status 6004 of No. 30 is set to locked, and the logical-physical address mapping is changed in step 6006 to make the target shared memory accessible to the task. Mapping change is Arn55 attach address 3505
This is done by changing the contents of the mapping table 91 so that the logical address stored in the first address 3001 of the SHE 30 indicates the physical address stored in the first address 3001 of the SHE 30.

Next, in step 6007, it is determined whether the processes of steps 6005 and 6006 have been performed on all the shared memories specified as arguments.
Return to step 4 and perform processing on the next shared memory.

When all the specified shared memories have been processed, the process advances to step 6008, and the number of locked shared memories is set in the lock number counter 2006 of the TCB 20.

Then, in step 6009, the task is notified of the success of the locking process, and the locking process is ended. The above is the content of the lock processing.

Next, a flowchart of the unlocking process is shown in FIG.

The unlocking process is executed using one or more shared memory managers to be unlocked as arguments.

First, in step 7001, one of the shared memories specified by the argument is selected as a processing target.

Next, in step 7002, 5MB50 of the target shared memory is
The value of the shared memory status 3004 of the task is set to unlocked, and then, in step 7006, the logical-physical address mapping is changed to make the target shared memory inaccessible by the task. The mapping change is performed by changing the contents of the mapping table 91 so that the logical address stored in the attach address 6505 of the ATE 35 indicates an invalid address.

When processing for one shared memory is completed, step 70
The process advances to step 04, and it is determined whether or not all the specified shared memories have been processed. If there are any remaining shared memories, the process returns to step 7001 to process the next shared memory.

Steps 7002~ for all specified shared memories
After processing 7006, the process advances to step 7005, where the TC
Decrement the value of the lock number counter 2006 of B 20 by the number of unlocked shared memories.

Next, in step 7006, the shared memory lock waiting task is released from waiting, and the unlocking process is ended.

According to this embodiment, a task can attach a plurality of shared memories in a superimposed manner onto its own logical address space. Since which of the overlapping shared memories is to be accessed can be specified when the shared memories are locked, there will be no inconsistency in the processing even if the shared memories are attached overlappingly. Therefore, a large number of shared memories can be used even if the logical address space of a task is not large.

〔Effect of the invention〕

According to the present invention, since a plurality of shared memories can be attached to the same logical address, it is possible to use a large number of shared memories even if the size of the logical address space for each task is small.

Furthermore, when accessing by attaching shared memory to the same logical address, the processing performed by a task is the same as when accessing by attaching shared memory to non-overlapping addresses.
@, and the same - without causing the task to perform any special processing.
A shared memory attach function to a logical address can be realized.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of hardware according to an embodiment of the present invention, Fig. 2 is an explanatory diagram of the present invention, Fig. 3 is an explanatory diagram of an address converter, and Fig. 4 is an explanation of a logical-physical address conversion method. Figure 1i145 is an explanatory diagram of the task control block, No. 6
The figure is an explanatory diagram of the shared memory management table (SMB), the 7th stripe is an explanatory diagram of the attach management table (ArB), and the 8th
9 is a flowchart of attach processing, FIG. 10 is a flowchart of lock processing, and FIG. 11 is a flowchart of unlock processing. 1 ・・・・・・・・・・・・ CPU 2 ・・・・・・・ Main memory 9 ・・・・・・・・・ Address converter 20
...Task control block (TCB) 30...
...Shared memory management table (SMB) 35
・・・・・・・・・Attach management full (ATB) η
δ figure 4, 5 402- 〒5 figure CB? n Kankan 6 illustrations tusks 7 illustrations rhinoceros 8 illustrations

Claims (1)

[Scope of Claims] 1. In a data processing device that performs multi-task processing by providing each task with its own logical address space, a first control table that manages the position and state of a shared memory in a physical address space; , a second control table for managing the correspondence between the shared memory and the task, a first means for associating the task and the shared memory using the second control table, the first control table, and A second control table that uses the second control table to initiate exclusive access of the task to the shared memory and to change the mapping of the logical address space of the task to enable the task to access the shared memory. (2) using the first control table and the second control table to terminate the exclusive access of the task to the shared memory and to change the mapping of the logical address space of the task; and third means for disabling access to the shared memory by a task. 2. In a data processing device that performs multitask processing by giving each task its own logical address space, when accessing shared memory between the tasks, the position of the shared memory in the task logical address space is determined. Access is performed using an attaching means, a locking means and an unlocking means for performing exclusive control of access to the shared memory, the attaching means does not change the logical-physical address mapping of the task, and the locking means does not change the logical-physical address mapping of the task. A shared memory management method characterized by changing the logical-physical address mapping of the task. 5. In claim 1, the second control table is connected by two independent list structures from both the first control table and a third control table for managing the state of the task. Shared memory management method.