Memory management and protection system for virtual memory in computer system

Abstract

A memory management and protection system for realizing a high speed execution and a proper and flexible memory access control for multiple programs sharing an identical logical address space. In the system, the memory access is permitted according to a segment identifier identifying a segment in the logical address space, and a memory protection information for a region in each segment including a target right permission to indicate assigned rights to make a memory access from the region to each of the segments, and an execution permission to indicate a type of the memory access permitted by the right permission. Alternatively, a memory access can be permitted by using an access control list to be attached to each address table entry, which stores a plurality of program numbers identifying programs which are permitted to make accesses to the logical address stored in each address table entry, among which one that matches with the current program number is to be searched. Also, it is preferable to allocate a plurality of programs within a limit of available memory protection capacity to an identical logical address space, without any overlap between adjacently allocated address regions.

Claims

What is claimed is:

1. A memory management and protection system for controlling memory accesses to a logical address space managed in terms of segments, comprising:

segment information extraction means for obtaining a target segment identifier for identifying a target segment containing a logical address to be accessed in the segments of the logical address space, according to the logical address;

memory protection information extraction means for obtaining a target memory protection information for a target region containing the logical address to be accessed in the target segment identified by the target segment identifier, according to the logical address, the memory protection information including a target right permission to indicate assigned rights to make a memory access from the target region to each of the segments of the logical address space, and a target execution permission to indicate a type of the memory access permitted by the target right permission as one of instruction access and data access; and

memory access permission means for permitting the memory access to the logical address according to the target segment identifier and the target memory protection information.

2. The system of claim 1, further comprising:

current segment identifier storage means for storing a current segment identifier for identifying a current segment in which a currently executed instruction is present in the segments of the logical address space; and

current memory protection information storage means for storing a current memory protection information for a current region in which the currently executed instruction is present in the current segment identified by the current segment identifier, the current memory protection information including a current right permission to indicate assigned rights to make a memory access from the current region to each of the segments of the logical address space, and a current execution permission to indicate a type of the memory access permitted by the current right permission as one of instruction access and data access.

3. The system of claim 2, wherein the memory access permission means permits the instruction access according to the current memory protection information, the target memory protection information, and the target segment identifier, while the memory access permission means permits the data access according to the target segment identifier and the target memory protection information, and the current segment identifier.

4. The system of claim 2, wherein the target memory protection information further includes a target transition permission to indicate the target region as a gate region accessible from all the segments in the logical address space, and the current memory protection information further includes a current transition permission to indicate the current region as the gate region.

5. The system of claim 4, wherein the memory access permission means permits the instruction access in the following three cases:

(1) the current right permission asserts the assigned right to make the memory access from the current region to the target segment identified by the target segment identifier, and the target execution permission asserts the type of the memory access permitted by the target right permission as the instruction access;

(2) the current execution permission asserts the type of the memory access permitted by the current right permission as the instruction access, and the target transition permission asserts the target region as the gate region; and

(3) the current transition permission asserts the current region as the gate region, and the target execution permission asserts the type of the memory access to be made to the logical address as the instruction access.

6. The system of claim 2, wherein the memory access permission means permits the data access when the target right permission asserts the assigned right to make the memory access from the target region to the current segment identified by the current segment identifier.

7. The system of claim 6, wherein the target memory protection information further includes a read permission to indicate the logical address to be accessed as readable, and a write permission to indicate the logical address to be accessed as writable, such that the memory access permission means permits the data access for data read when the read permission is asserted and the data access for data write when the write permission is asserted.

8. The system of claim 2, further comprising means for updating the current segment identifier stored in the current segment identifier storage means by the target segment identifier obtained by the segment information extraction means, and the current memory protection information stored in the current memory protection information storage means by the target memory protection information obtained by the memory protection information extraction means, whenever the memory access permission means permits the instruction access.

9. The system of claim 1, further comprising means for generating a segment transition notice when the target segment identified by the target segment identifier and the current segment identified by the current segment identifier are not identical in a case of the instruction access.

10. The system of claim 1, wherein the segment information extraction means obtains the target segment identifier as upper bits of the logical address to be accessed.

11. A memory management system for converting a logical address into a physical address in a computer which executes a plurality of programs allocated to a virtual space in parallel by activating a plurality of threads, comprising:

access permission memory means for storing access permissions indicating whether each thread is permitted to make accesses to the logical address;

a thread number memory for storing a thread number assigned to a currently executing thread which is currently executing the programs;

verification means for verifying whether the currently executing thread specified by the thread number stored in the thread number memory is permitted to make accesses to the logical address, according to the access permissions stored in the access permission memory means; and

means for outputting the physical address converted from the logical address when the verification means verifies that the currently executing thread is permitted to make accesses to the logical address.

12. The system of claim 11, wherein the access permissions stored in the access permission memory means indicate thread numbers assigned to those threads which are permitted to make accesses, and the verification means verifies that the currently executing thread is permitted to make accesses to the logical address when a matching of the thread number specified by the thread number memory with one of the thread numbers indicated by the access permission memory means is found.

13. The system of claim 12, wherein the verification means checks the matching of the thread number specified by the thread number memory with each one of the thread numbers indicated by the access permission memory means by masking at least a part of either one of the thread number specified by the thread number memory or said each one of the thread numbers indicated by the access permission memory means.

14. The system of claim 13, wherein the masking masks a whole of either one of the thread number specified by the thread number memory or said each one of the thread numbers indicated by the access permission memory means at most.

15. The system of claim 11, wherein the verification means verifies that the currently executing thread is permitted to make accesses to the logical address when a prescribed logical calculation for the thread number specified by the thread number memory and one of the thread numbers indicated by the access permission memory means comes up with a result indicating the prescribed logical calculation as true.

16. A memory management system for converting a logical address into a physical address in a computer which executes programs allocated to a virtual space divided into a plurality of address regions, comprising:

access permission memory means for storing access permissions indicating whether accesses from each program allocated to each address region to the logical address are permitted;

address region detection deans for detecting a current address region containing a currently executing program which makes an access to the logical address;

verification means for verifying whether accesses from the current address region detected by the address region detection means to the logical address are permitted, according to the access permissions stored in the access permission memory means; and

means for outputting the physical address converted from the logical address when the verification means verifies that the accesses from the current address region to the logical address are permitted.

17. The system of claim 16, wherein the access permissions stored in the access permission memory means indicate address region numbers assigned to those address regions from which accesses are permitted, and the verification means verifies that the accesses from the current address region to the logical address are permitted, when a matching of an address region number assigned to the current address region detected by the address region detection means with one of the address region numbers indicated by the access permission memory means is found.

18. The system of claim 17, wherein the verification means checks the matching of the address region number assigned to the current address region detected by the address region detection means with each one of the address region numbers indicated by the access permission memory means by masking at least a part of either one of the address region number assigned to the current address region detected by the address region detection means or said each one of the address region numbers indicated by the access permission memory means.

19. The system of claim 18, wherein the masking masks a whole of either one of the address region number assigned to the current address region detected by the address region detection means or said each one of the address region numbers indicated by the access permission memory means at most.

20. The system of claim 16, wherein the verification means verifies that the accesses from the current address region to the logical address are permitted, when a prescribed logical calculation for the address region number assigned to the current address region detected by the address region detection means and one of the address region numbers indicated by the access permission memory means comes up with a result indicating the prescribed logical calculation as true.

21. A memory management system for converting a logical address into a physical address, comprising:

access permission memory means for storing access permissions for accesses from each program allocated to a logical address space with respect to the logical address;

verification means for verifying whether accesses from a currently executing program with respect to the logical address are permitted, according to the access permissions stored in the access permission memory means; and

means for outputting the physical address converted from the logical address when the verification means verifies that the accesses from the currently executing program with respect to the logical address are permitted.

22. The system of claim 21, wherein the access permissions indicate whether the accesses to the logical address from a position in the logical address space at which said each program is located are permitted.

23. The system of claim 21, wherein the access permissions indicate whether the accesses to the logical address from a thread which is executing said each program are permitted.

24. The system of claim 21, further comprising:

a cache memory for storing a predetermined number of cached address table entries;

a cache access permission memory for storing a fixed number of access permissions for accesses from each program allocated to the logical address space with respect to each logical address stored in each cached address table entry of the cache memory;

cache verification means for verifying whether accessed from a currently executing program with respect to one logical address stored in one cached address table entry of the cache memory are permitted, according to the access permissions stored in the cache access permission memory; and

means for outputting a physical address stored in said one cached address table entry, when the cache verification means verifies that the accesses from the currently executing program with respect to said one logical address are permitted.

25. The system of claim 24, further comprising:

means for replacing the fixed number of access permissions for accesses from said each program by at most the fixed number of additional access permissions different from said fixed number of access permissions for accesses from said each program, when the cache verification means fails to verify said fixed number of access permissions for accesses from the currently executing program with respect to the logical address to be accessed.

26. A memory management and protection system, comprising:

program allocation means for determining an allocation of a plurality of programs to at least one of logical address spaces, where only up to a predetermined number of the programs are allocated to each logical address space, and any one address region allocated to any one of the programs does not overlap with any other address regions allocated to any other ones of the programs within said at least one of the logical address spaces;

memory protection means for detecting an occurrence of an improper access from one address region allocated to one of the programs to another address region allocated to another one of the programs, among said up to the predetermined number of the programs allocated to said each logical address space;

cache means for storing data to be accessed by the programs; and

processing means for executing the programs by making accesses to the cache means according to the allocation determined by the program allocation means, unless the memory protection means detects the occurrence of the improper access.

27. The system of claim 26, further comprising:

logical address space switching detection means for detecting an occurrence of a logical address space switching from one of the logical address spaces to another one of the logical address spaces, in conjunction with a context switching of a program to be executed from a switch requesting program to a switch target program among the plurality of programs; and

cache validation/invalidation means for invalidating those data stored in the cache means which belong to the switch requesting program when the logical address space switching detection means detects the occurrence of the logical address space switching;

wherein the processing means executes each one of the programs by making accesses to the cache means unless the memory protection means detects the occurrence of the improper access and the data to be accessed by said each one of the programs are invalidated by the cache validation/invalidation means.

28. The system of claim 27, wherein the program allocation means determines the allocation of the plurality of programs to said at least one of the logical address spaces, according to a program management table indicating a utilization state of each address region in the logical address spaces along with a logical address space number of each logical address space to which said each address region belongs.

29. The system of claim 28, wherein the logical address space switching detection means detects the occurrence of the logical address space switching by comparing the logical address space number for a switch requesting address region to which the switch requesting program is allocated and the logical address space number for a switch target address region to which the switch target program is allocated, according to the program management table.

30. The system of claim 27, wherein the cache validation/invalidation means also validates those data stored in the cache means which belong to the switch target program when the logical address space switching detection means detects the occurrence of the logical address space switching.

31. The system of claim 27, wherein the cache validation/invalidation means also invalidates those data stored in the cache means which belong to said one of the logical address spaces to which the switch requesting program is allocated and validates those data stored in the cache means which belong to said another one of the logical address spaces to which the switch target program is allocated, when the logical address space switching detection means detects the occurrence of the logical address space switching.

32. The system of claim 26, further comprising

logical address space switching detection means for detecting an occurrence of a logical address space switching from one of the logical address spaces to another one of the logical address spaces, in conjunction with a context switching of a program to be executed from a switch requesting program to a switch target program among the plurality of programs; and

a translation look-aside buffer (TLB) means having a plurality of TLB entries, each TLB entry storing a logical address of the data to be accessed stored in the cache means, a physical address corresponding to the logical address, and an invalidation bit for indicating a validity of said each TLB entry;

wherein the processing means makes accesses to the cache means for data to be accessed by said each one of the programs, while checking the TLB means to determine whether the data to be accessed by said each one of the programs is accessible according to the invalidation bit of the TLB entry storing the logical address of the data to be accessed by said each one of the programs.

33. The system of claim 26, wherein the program allocation means allocates the plurality of programs to said at least one of logical address spaces according to frequencies of occurrences of accesses between each two programs among the plurality of programs, such that closely related programs for which the frequencies of occurrences of accesses are higher are allocated to an identical one of the logical address spaces at higher priority.

34. The system of claim 33, wherein when a number of the closely related programs exceeds the predetermined number, the program allocation means allocates the predetermined number of the closely related programs to the identical one of the logical address spaces, while allocating each remaining one of the closely related programs in excess of the predetermined number to an additional logical address space provided in addition to said at least one of the logical address spaces, along with a duplicate of a part of the predetermined number of the closely related programs allocated to the identical one of the logical address spaces.

35. The system of claim 26, wherein the program allocation means allocates the plurality of programs to said at least one of logical address spaces such that at most one execution program, which is capable of executing an instruction for any one of reading from another program, writing to another program, and executing another program, is allocated to each logical address space.

36. The system of claim 35, further comprising access mode assignment means for indicating access modes permitted to each one of the plurality of programs with respect to other ones of the plurality of programs.

37. The system of claim 35, wherein the program allocation means allocates each execution program to said each logical address space along with other programs which are accessible from said each execution program.

38. The system of claim 26, wherein the program allocation means allocates the plurality of programs to said at least one of logical address spaces such that at most one unique access mode assigned execution program, which is capable of executing an instruction for any one of reading from another program, writing to another program, and executing another program, and which has unique access modes with respect to other ones of the plurality of programs, can be allocated to each logical address space, while any number of non-unique access mode assigned execution programs, each of which is capable of executing an instruction for any one of reading from another program, writing to another program, and executing another program, and each of which has identical access modes with respect to other ones of the plurality of programs as another non-unique execution program, can be allocated to each logical address space.

39. A method of memory management for converting a logical address into a physical address in a computer which executes a plurality of programs allocated to a virtual space in parallel by activating a plurality of threads, the method comprising the steps of:

storing, in an access permission memory means, access permissions indicating whether each thread is permitted to make accesses to the logical address;

storing a thread number assigned to a currently executing thread which is currently executing the programs;

verifying whether the currently executing thread specified by the thread number is permitted to make accesses to the logical address, according to the access permissions stored in the access permission memory means; and

outputting the physical address converted from the logical address when the verifying step verifies that the currently executing thread is permitted to make accesses to the logical address.

40. A method of memory management for converting a logical address into a physical address in a computer which executes programs allocated to a virtual space divided into a plurality of address regions, the method comprising the steps of:

storing, in an access permission memory means, access permissions indicating whether accesses from each program allocated to each address region to the logical address are permitted;

detecting a current address region containing a currently executing program which makes an access to the logical address;

verifying whether the accesses from the current address region detected at the detecting step to the logical address are permitted, according to the access permissions stored in the access permission memory means; and

outputting the physical address converted from the logical address when the verifying step verifies that the accesses from the current address region to the logical address are permitted.

41. A method of memory management for converting a logical address into a physical address, comprising the steps of:

storing, in an access permission memory means, access permissions for accesses from each program allocated to a logical address space with respect to the logical address;

verifying whether accesses from a currently executing program with respect to the logical address are permitted, according to the access permissions stored in the access permission memory means; and

outputting the physical address converted from the logical address when the verifying step verifies that the accesses from the currently executed program with respect to the logical address are permitted.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a computer system using a virtual memory, and more particularly, to the memory management and the protection for controlling memory accesses to the virtual memory in the computer system.

2. Description of the Background Art

Conventionally, in a computer system using a virtual memory, a so called MMU (Memory Management Unit) has been used in translating the logical addresses to the physical addresses and protecting the memory region specified by the physical addresses. In a usual MMU, a program number uniquely assigned to each program is utilized for distinguishing a plurality of programs which can make accesses to the memory, such that the same logical address can be translated into different physical addresses for the different programs.

In such a computer system using a virtual memory, it has become popular in recent years to employ a programming mode such as a server-client type programming in which a plurality of programs sharing the same data are executed in mutual cooperation as a result of the recent progresses made in the network technique and the parallel processing technique. In such a programming mode, a plurality of memory accesses are made from a plurality of programs to the identical physical address storing the shared data, so that it becomes necessary to provide a memory region protection in order to limit the memory accesses made from the plurality of programs to only those which are judged as proper ones.

To this end, a conventionally employed memory region protection method has been that which utilizes the program number as the identifier for indicating a program from which each memory access originates. Namely, in such a conventional memory region protection method, each data is accompanied by the program number of the program which may make accesses to this data, while the program numbers available to each program are appropriately assigned to each program as an identifier in advance. Then, the access to each data is permitted only when this access is judged as a proper one having the identifier indicating the program number which matches with the program number accompanying each data. The well known examples of this type of a conventional memory region protection method include a segmentation method and a ring protection method.

In a segmentation method, a dedicated memory region can be secured for each program by assigning a unique program number available only to that program, while a shared memory region for a plurality of programs can be secured by assigning a program number commonly available to these plurality of programs, so that the highly flexible memory region protection can be realized.

However, in order to deal with a plurality of program numbers, it becomes necessary in this segmentation method to provide a plurality of identifier storage registers and a plurality of identifier comparators. As a consequence, this segmentation method has been associated with the following problems.

Firstly, there is a case in which a number of identifier storage registers are occupied with respect to a single physical address, such that the address translation for the other physical addresses cannot be carried out efficiently. For example, in a case a number of entries in the address table is constant, when a plurality of entries are occupied by a number of identical logical and physical address pairs with different program numbers assigned, the types of the physical addresses that can be stored in the address table can be reduced considerably. Such a situation is equivalent to a case in which the address table covers only a limited range of the address space. When the covered range of the address space is limited, the probability at which the address given from the processor makes a hit at the address table becomes lower and a number of address table misses increases, such that a time required for the address table miss recovery operation increases. This time required for the address table miss recovery operation is counted as a part of the overall address translation time, so that the average overall address translation time is increased considerably in such a case.

Secondly, when the program to be executed is switched from one program to another, the entries accompanied by the program numbers used in the previously executed program are invalidated regardless of whether the program numbers are shared by the next program to be executed, so that the operation for filling the address table entries is required even for the shared program numbers. For example, in a case two programs sharing the logical address space are to be executed alternatively, when a new entry is required, the entries accompanied by the program numbers used in the previously executed program are invalidated regardless of whether these entries belong to the shared logical address space or not. In order to fill these invalidated entries anew, it becomes necessary to carry out the operations of address translation and the program number matching for each entry all over again, and the time required for these address translation and program number matching operations is counted as a part of the overall address translation time, so that in a case of the switching of the program to be executed, the average overall address translation conversion time is increased considerably. In the worst case, the time required for these address translation and program number matching can occupy the major part of the overall address translation time, as the invalidation of the entries occur every time the program to be executed is switched.

Thirdly, it becomes necessary to check the properness of the rights to make accesses for a plurality of programs simultaneously, so that the operation for checking the properness of the rights to make accesses can be quite complicated. For example, in a case a plurality of programs share the identical logical address space, an entry in the address table is set up for each of the program numbers. In such a case, when a page swapping occurred, it becomes necessary to invalidate all the entries related to the specific logical address or physical address, whereas when a plurality of entries made hits, it becomes necessary to select the valid one among the plurality of entries making hits, and the time required for these operation for invalidating all the related entries and selecting the valid entry is counted as a part of the overall address translation time. Here, the number of related entries are unknown, so that the operation can be quite complicated as a great number of different states must be accounted for.

Now, there is an alternative manner of handling a plurality of program numbers in the segmentation method in which a specialized instruction is provided in the processor side to specify the program number at a time of execution. The switching operation using such a specialized instruction is effective in reducing the number of identifier storage registers so that the time required for the exchange of the segment registers can be shortened. However, in this case, each execution of each instruction becomes quite time consuming, so that it has been difficult to improve the throughput of the program. Thus, in the segmentation method, it is easy to separate the different programs completely, but it requires a large number of additional hardware and complicated operations to share the data among the programs.

In addition, in the segmentation method, there is a problem that it is necessary to provide a flexible protection check mechanism capable of dealing with different types of accesses differently permitted to different programs and different levels of the rights to make accesses differently endowed to different programs. For example, in a case a plurality of programs share the data, very frequently, there is a case in which only one program is permitted to update the data and the other programs are only permitted to read this data.

Also, there is a case in which it is necessary to provide the hierarchical protection among the programs according to the difference of the content and the level of the programs such as Kernel, OS, and application programs. The method to achieve such a hierarchical protection is known as a ring protection method.

In order to cope with such cases, it is necessary to provide each entry of the address table with a field for specifying a data access type and a field for specifying a ring level, so as to distinguish the data in different specified levels as different entries.

In the ring protection method, the program numbers are hierarchically ordered to establish strength relationships in which the transition of the control toward the stronger region is limited to only those which are made through a proper procedure, and the data access toward the stronger region is prohibited, such that the directionality can be provided in the accesses among the protected regions. In this ring protection method, one program number can have a right to make accesses to a plurality of regions, so that the number of identifiers can be reduced and the time required for switching the identifiers can be shortened. In addition, the check of the properness of the program number can be made by comparing the sizes of the identifier of the accessing side and the identifier of the accessed side at a time of the access, so that there is no need to provide a specialized instruction to the processor side in this ring protection method.

However, this ring protection method has a drawback that the set up of the protection regions is not very flexible because it is predetermined that the overlapping region between the region for one identifier and the region for another identifier is to be regarded as the region for the stronger identifier.

Now, in general, in the ring protection method, a kernel program is positioned at the strongest level, and the protection levels of the other programs are determined according to the absolute strength relationship of each program with respect to the kernel program.

However, in a case of the server-client type programming in which a plurality of programs are executed in mutual cooperation, there is a case in which the hierarchical relationship among the program changes in every execution, so that it has been difficult to set up the absolute protection level for each program in advance.

The strength relationships established among the memory regions in the ring protection method is shown in FIG. 1, in which segment-1 to -4 corresponds to the different programs such as kernel, OS, library, and application programs. Here, in order for each of the kernel program and the OS program to have a dedicated data region, the segment-3 and the segment-4 corresponding to the OS program and the kernel program must be assigned to the same protection level as shown in FIG. 1, and the dedicated data regions of these two programs must be managed the method other than the ring protection method, so as to make the dedicated data region of one hidden from the dedicated data region of another.

However, in FIG. 1, there are four protection levels provided in correspondence to four programs, so that when the kernel program and the OS program are assigned to the same protection level, there will be a protection level to which no program is assigned. In other words, there are cases in which the programs having no hierarchical relationship with each other must be assigned to the same protection level, and the protection level having no program assigned exist. Such a conflict of the hierarchical relationships occurs at a higher possibility as a number of programs to be allocated into the protection space increases, and makes the management of the different protection levels difficult.

Thus, the ring protection method is suitable for a case in which the cooperative relationships among the programs are simple and fixed, but lacking in an ability to express semi-ordered hierarchical relationships among the programs.

As a consequence, in the ring protection method, it is impossible for the memory protection device to set up the strength relationships among the programs dynamically according to the progress of the programs. In addition, in the ring protection method, a region belonging to a certain protection level is accessible from the regions belong to the stronger protection levels, so that it has been impossible to provide a dedicated region for a program belonging to an intermediate protection level.

Moreover, in the ring protection method, there is a possibility for the entries of the address table to be occupied by the identical logical and physical address pairs, so that the ring protection method also has the drawback of the extended average memory access time, similar to the segmentation method. Furthermore, in the ring protection method, there is a case in which a plurality of entries make hits in an address table look up, and it becomes necessary in such a case to select the valid one among the plurality of entries making hits. Also, when a number of programs share the OS region, it is required to manage a certain group of programs collectively, but this has been impossible in the conventional ring protection method and it would have been necessary to manage each entry separately.

Now, the virtual memory to be used in a computer system is in either one of a single virtual space scheme in which a plurality of programs to be executed in parallel are loaded into one virtual space, or a multiple virtual space scheme in which each of the plurality of programs to be executed in parallel is allocated to separate one of a plurality of virtual spaces.

For example, in the UNIX system, the different processes are allocated to different virtual spaces. For this reason, when the multiple processes are executed, the virtual space must be switched when the process is switched and the hit rates for the TLB (Translation Look-aside Buffer) and cache devices can be deteriorated considerably. In other words, the TLB and cache devices which are provided for the purpose of increasing the execution speed would not operate effectively in such a multiple process environment.

Here, it is noted that, in the TLB and cache devices, the data and the physical addresses are searched by using the virtual addresses used in each program as keys, and the address positions are usually fixed regardless of the program so that the virtual address positions are common to all the programs. For this reason, when the data of the previously executed program are left in the TLB and cache devices, there is a possibility for causing an erroneous hit during the execution of the new program after the program switching.

In order to prevent the occurrence of such an erroneous hit, conventionally, a space number for identifying each virtual space has been provided in addition to the virtual addresses, and the consistency of the TLB and cache devices with respect to the main memory device are checked every time the context is switched. However, these conventional provisions require an extra amount of hardware, and also make the software operation to be used in the context switching very complicated, so that the increase of the execution speed could not have been realized without introducing considerable disadvantages in other practical aspects.

Despite of this difficulty, the performance under such a multiple process environment has become increasingly important because of the increasing use of the server-client type programming in which a plurality of programs sharing the same data are executed in mutual cooperation, due to the considerable advantages of the server-client type programming that the server program and the client program can be developed separately and flexibly such that each program can be developed to have a wider applicability and a longer lifetime.

In this regard, the size of the OS has been increased so much recently, because of the increasing number of functions to be supported by the OS, such that the OS is no longer provided as a single program as it used to be but separated into a plurality of mutually cooperating programs according to the types of the functions to be supported. Similarly, there are cases in which the application programs are also provided as a plurality of mutually hidden programs, in order to improve the software productivity. In such a case in which a plurality of programs are to be operated in mutual cooperation, the operations related to the context switching and the copying of the argument which are to be carried out by the data processing unit become quite time consuming.

In order to resolve this problem, it has been considered desirable to omit the operation related to the switching of the programs by allocating a plurality of programs to a single virtual space. Here, in a conventional scheme such as that shown in FIG. 2 in which a plurality of user programs 601 to 605 are separately allocated to separate virtual spaces under the OS 600 while these user programs 601 to 605 are using the same address region, it is impossible for one user program to make an improper access to the data of the other user program as each user program is allocated to separate virtual space. However, when the scheme to allocate a plurality of programs to a single virtual space is adopted, the data of the other programs, which have been inaccessible in the multiple virtual space scheme, become accessible as all the programs are allocated to the same virtual space, so that there is a need to provide a mechanism to control the accesses according to the properness of each access.

However, when the conventional segmentation method is utilized for this purpose, an enormous amount of hardware would be required such that the switching of the access regions would be quite complicated, while when the conventional ring protection method is utilized for this purpose, the protection ranges cannot be set up freely among the programs because the strength relationships cannot be changed dynamically in the ring protection method. Consequently, it has conventionally been difficult to realize the simple and flexible protection of the memory regions among a plurality of programs in which the protection ranges can be set up freely.

In summary, there has been the following three major problems in the conventional memory management and the protection system for controlling memory accesses to the virtual memory in the computer system adopting a server-client type programming mode in which a plurality of programs sharing the same data are executed in mutual cooperation.

First of all, as the programs are allocated to different logical address spaces separately, it becomes necessary for the programs allocated to different address spaces to exchange the data through the operating system (OS) in order to share the data among them, but this causes a considerable slow down of the processing speed due to the overhead of the OS.

Here, it is possible to devise a method in which a plurality of threads are executed on a single logical address space such that the sharing of the data among the threads can be achieved without causing any overhead to the OS.

However, such a method does not account for the protection of the data among the threads, so that in order to protect the data used by one thread from the other threads, it becomes necessary to employ a scheme requiring a large overhead to the OS. Namely, to this end, it becomes necessary to allocate each thread to different logical address space along with those data which are accessible from this thread. This scheme actually requires a considerably large overhead to the OS so that it is quite impractical to adopt this scheme.

Thus, the first major problem is that it has been impossible for each program to have the different types of accesses that are permitted to each thread.

Secondly, in order to provide a logical address space for each thread separately, it becomes necessary to provide a page table for each logical address space and allocate the same program to the same address region in the different logical address spaces. However, this in turn requires all the threads which are commonly accessible to a certain address region to have the same logical address and physical address pair in respective page tables, such that the memory capacity to be used by the page tables of all the threads must be provided redundantly to a large extent.

Here, when the types of accesses permitted to all the threads which are accessible to the commonly accessible address region are identical, it becomes possible to share a part of the page tables among a plurality of threads, but in a case of using a TLB (Table Look-aside Buffer) as a cache device for the page table, the redundancy cannot be avoided and the average processing speed for the address translation is inevitably slowed down accordingly.

The reason for this drawback is as follows. Namely, each entry of the cache of the page table has a pair of a page table information and a thread number, so that different cache entries are required for different threads even when the page table information is identical. Consequently, a number of cache entries having the same page table information but different thread numbers will occupy a large portion of the cache, such that a number of actually different physical addresses that can be stored in the cache will be reduced, and therefore the processing speed for the address translation will be slowed down.

In addition, there is also a drawback that the information related to the same page must be placed and managed on a plurality of page tables, such that the processing for the paging becomes quite complicated. For instance, in a case a plurality of threads are mapping the identical physical address to different logical address spaces, when it becomes necessary to page out a certain page, it becomes necessary to search and invalidate all the entries of the page tables which are mapped to that certain page. Similarly, in a case of page in, it becomes necessary to search and validate all the entries of the page tables which are mapped to that certain page. The additional time required for these operations will be added to the average address translation processing time, so that the processing speed for the address translation will be slowed down.

Thus, the second major problem is that the memory capacities required for the page tables and the page table caches are redundant and the management of the page tables and the page table caches becomes quite complicated and inefficient.

Thirdly, it has been considered effective in some applications to change the access rights permitted to each thread depending on which thread is executing a program on which address region in each logical address space. For example, when the data on a certain address region can be changed only by the thread executing the programs on another certain address region, the data on that certain address region can be changed while maintaining certain conditions. In a case the data of the database are allocated to that certain address region while the access routines for the data of the database are allocated to that another certain address region, it becomes possible to make accesses to the data of the database without requiring the intermediate use of the OS, while protecting the data of the database sufficiently, so that the high speed access processing becomes possible.

On the other hand, a conventionally memory management unit such as the Intel's 80486 processor has been capable only of changing the access rights by limiting the range of the programs that can be executed by each thread by using the segmentation scheme and shifting from one access level to another access level by using a call gate. In other words, such a conventional memory management unit has been lacking a flexibility in that the access rights can only be controlled among the elements related by an order relationship, such as the application programs with respect to the OS and the kernel, such that the element at a higher access level will become accessible to all the elements at lower access levels, because a number of different access levels realizable has been limited by the hardware.

Thus, the third major problem is that it has been impossible to flexibly change the permitted access rights for each address region, in a case the programs and data are allocated to a plurality of divided address regions within the single logical address space.

SUMMARY OF THE INVENTION

It is therefore an object of the present invention to provide a memory management and protection system for a virtual memory in a computer system, in which the protection ranges can be set up freely, without requiring a use of a special instruction on a processor side, an extension of the data processing time, and the considerable increase of hardware.

It is another object of the present invention to provide a memory management and protection system for a virtual memory in a computer system, capable of providing a proper and flexible control of the memory accesses made by a plurality of programs sharing an identical logical address space, without requiring an extension of the data processing time.

It is another object of the present invention to provide a memory management and protection system for a virtual memory in a computer system, capable of realizing a high speed execution of multiple programs by effectively utilizing the TLB and the cache devices.

According to one aspect of the present invention there is provided a memory management and protection system for controlling memory accesses to a logical address space managed in terms of segments, comprising: segment information extraction means for obtaining a target segment identifier for identifying a target segment containing a logical address to be accessed in the segments of the logical address space, according to the logical address; memory protection information extraction means for obtaining a target memory protection information for a target region containing the logical address to be accessed in the target segment identified by the target segment identifier, according to the logical address, the memory protection information including a target right permission to indicate assigned rights to make a memory access from the target region to each of the segments of the logical address space, and a target execution permission to indicate a type of the memory access permitted by the target right permission as one of instruction access and data access; and memory access permission means for permitting the memory access to the logical address according to the target segment identifier and the target memory protection information.

According to another aspect of the present invention there is provided a memory management and protection system, comprising: address table means having a plurality of address table entries, each address table entry storing a logical address and a physical address corresponding to the logical address; access control list means, attached to each address table entry, for storing a plurality of program numbers for identifying programs which are permitted to make accesses to the logical address stored in said each address table entry; hit check means for detecting one of the plurality of program numbers stored in the access control list means attached to one of the address table entries storing the logical address to be accessed, which matches with a current program number identifying a currently executed program; hit notice means for generating an address table hit notice when the hit check means detects said one of the plurality of program numbers; and means for outputting the physical address stored in said one of the address table entries, when the hit notice means generates the address table hit notice.

According to another aspect of the present invention there is provided a memory management and protection system for a logical address space containing a plurality of programs to be executed by a plurality of threads, comprising: address table means having a plurality of address table entries, each address table entry storing a logical address and a physical address corresponding to the logical address; access control list means, attached to each address table entry, for storing access permissions indicating whether each thread is permitted to make accesses to the logical address stored in said each address table entry; thread number memory means for storing a thread number assigned to a currently executed thread; verification means for verifying whether the currently executed thread specified by the thread number stored in the thread number memory means is permitted to make accesses to a logical address to be accessed stored in one of the address table entries, according to the access permissions stored in the access control list means attached to said one of the address table entries; and means for outputting the physical address stored in said one of the address table entries, when the verification means verifies that the currently executed thread is permitted to make accesses to the logical address to be accessed.

According to another aspect of the present invention there is provided a memory management and protection system for a logical address space divided into a plurality of address regions, comprising: address table means having a plurality of address table entries, each address table entry storing a logical address and a physical address corresponding to the logical address; access control list means, attached to each address table entry, for storing access permissions indicating whether accesses from each address region to the logical address stored in said each address table entry are permitted; address region detection means for detecting a current address region containing a currently executed program; verification means for verifying whether the accesses from the current address region detected by the address region detection means to a logical address to be accessed stored in one of the address table entries are permitted, according to the access permissions stored in the access control list means attached to said one of the address table entries; and means for outputting the physical address stored in said one of the address table entries, when the verification means verifies that the accesses are permitted from the current address region to the logical address to be accessed.

According to another aspect of the present invention there is provided a memory management and protection system, comprising: address table means having a plurality of address table entries, each address table entry storing a logical address and a physical address corresponding to the logical address; access control list means, attached to each address table entry, for storing access permissions for accesses from each program allocated to a logical address space with respect to the logical address stored in said each address table entry; verification means for verifying the access permissions for accesses from a currently executed program with respect to a logical address to be accessed stored in one of the address table entries, according to the access permissions stored in the access control list means attached to said one of the address table entries; and means for outputting the physical address stored in said one of the address table entries, when the verification means verifies that the access permissions for the currently executed program with respect to the logical address to be accessed.

According to another aspect of the present invention there is provided a memory management and protection system, comprising: program allocation means for determining an allocation of a plurality of programs to at least one of logical address spaces, where only up to a predetermined number of the programs are allocated to each logical address space, and any one address region allocated to any one of the programs does not overlap with any other address regions allocated to any other ones of the programs within said at least one of the logical address spaces; memory protection means for detecting an occurrence of an improper access from one address region allocated to one of the programs to another address region allocated to another one of the programs, among said up to the predetermined number of the programs allocated to said each logical address space; cache means for storing data to be accessed by the programs; and processing means for executing the programs by making accesses to the cache means according to the allocation determined by the program allocation means, unless the memory protection means detects the occurrence of the improper access.

Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram representing hierarchical relationships among segments of a logical address space realized in a conventional memory management unit using a ring protection scheme.

FIG. 2 is a diagrammatic representation of a conventional manner of allocation of the multiple programs to logical address spaces.

FIG. 3 is a block diagram of one embodiment of a memory protection device to be used in a memory management unit according to the present invention.

FIG. 4A is a diagram explaining one manner of obtaining a segment identifier according to a logical address in the memory protection device of FIG. 3.

FIG. 4B is a diagram explaining another manner of obtaining a segment identifier according to a logical address in the memory protection device of FIG. 3.

FIG. 5A is a diagram of one example of a page table entry to be used in obtaining a memory protection information according to a logical address in the memory protection device of FIG. 3.

FIG. 5B is a diagram of another example of a page table entry to be used in obtaining a memory protection information according to a logical address in the memory protection device of FIG. 3.

FIG. 5C is a diagram of still another example of a page table entry to be used in obtaining a memory protection information according to a logical address in the memory protection device of FIG. 3.

FIG. 5D is a table summarizing an operation type code and its content to be used in the still another example of the page table entry shown in FIG. 5C.

FIG. 6 is a detailed block diagram of a segment transition signal generator in the memory protection device of FIG. 3.

FIG. 7 is a detailed block diagram of an instruction access permission signal generator in the memory protection device of FIG. 3.

FIG. 8 is a detailed block diagram of a data access permission signal generator in the memory protection device of FIG. 3.

FIG. 9 is a detailed block diagram of a control unit in the memory protection device of FIG. 3.

FIG. 10 is a diagram representing an example of semi-ordered hierarchical relationships among segments of a logical address space realized by the memory protection device of FIG. 3.

FIG. 11 is a diagrammatic illustration of an example of assignment of values to various permissions used in the memory protection device of FIG. 3, for realizing the semi-ordered hierarchical relationships shown in FIG. 10.

FIG. 12 is a block diagram of the memory protection device of FIG. 3 in a case of making an instruction access without a segment transition.

FIG. 13 is a block diagram of the memory protection device of FIG. 3 in a case of making an instruction access with a segment transition.

FIG. 14 is a block diagram of the memory protection device of FIG. 3 in a case of making an instruction access for a branching to a gate page.

FIG. 15 is a block diagram of the memory protection device of FIG. 3 in a case of making an instruction access for a branching from a gate page.

FIG. 16 is a block diagram of the memory protection device of FIG. 3 in a case of failing to make an instruction access with a prohibited segment transition.

FIG. 17 is a block diagram of the memory protection device of FIG. 3 in a case of making a data access with a segment transition.

FIG. 18 is a block diagram of the memory protection device of FIG. 3 in a case of failing to make a data access with a prohibited segment transition.

FIG. 19 is a diagrammatic representation of a logical address space, indicating exemplary accessible regions and three possible exemplary routes of permitted segment transitions for the instruction access in the memory protection device of FIG. 3.

FIG. 20 is a diagrammatic representation of a logical address space, indicating exemplary accessible regions for the data access in the memory protection device of FIG. 3.

FIG. 21 is a block diagram of one exemplary configuration of a memory management unit using the memory protection device of FIG. 3.

FIG. 22 is a block diagram of another exemplary configuration of a memory management unit using the memory protection device of FIG. 3.

FIG. 23 is a block diagram of another embodiment of a memory management unit according to the present invention.

FIG. 24 is a detailed block diagram of a translation look-aside buffer (TLB) check device in the memory management unit of FIG. 23.

FIG. 25 is a further detailed block diagram of a comparison unit in the translation look-aside buffer (TLB) check device of FIG. 24.

FIG. 26 is a detailed block diagram of an address translation device in the memory management unit of FIG. 23.

FIG. 27 is a further detailed block diagram of a first (or a second) stage address translation unit in the address translation device of FIG. 26.

FIG. 28 is a further detailed block diagram of a third stage address translation unit in the address translation device of FIG. 26.

FIG. 29 is a further detailed block diagram of the third stage address of FIG. 28 for a case involving access control list (ACL) switching.

FIG. 30 is a diagrammatic illustration of an example of assignment of access control list (ACL) entries used in the memory management unit of FIG. 23, for realizing the semi-ordered hierarchical relationships shown in FIG. 10.

FIG. 31 is a diagrammatic illustration of an exemplary trace of the threads in the memory management unit of FIG. 23 in a case of using the identical program number for the threads for the same program.

FIG. 32 is a diagrammatic illustration of an exemplary trace of the threads in the memory management unit of FIG. 23 in a case of using the thread identifiers as the program numbers for the threads for the same program.

FIG. 33 is a diagrammatic illustration of another example of assignment of access control list (ACL) entries used in the memory management unit of FIG. 23, for a case of realizing the control according to the size relationships among the program numbers.

FIG. 34 is a diagrammatic illustration of another example of assignment of access control list (ACL) entries used in the memory management unit of FIG. 23, for a case of realizing a not excessively tight control using a masking of a part of a program number.

FIG. 35 is a detailed block diagram of a modified configuration for a translation look-aside buffer (TLB) check device in the memory management unit of FIG. 23.

FIGS. 36A, 36B, and 36C are diagrammatic illustrations of three modified configurations for each access control list (ACL) entry that can be used in the memory management unit of FIG. 23.

FIG. 37 is a block diagram of additional embodiment of a memory management unit according to the present invention.

FIG. 38 is a block diagram of further additional embodiment of a memory management unit according to the present invention.

FIG. 39 is a block diagram of further additional embodiment of a memory management unit according to the present invention.

FIG. 40 is a block diagram of a modified configuration for the memory management unit of FIG. 39.

FIG. 41 is a block diagram of another embodiment of a memory management and protection system according to the present invention.

FIG. 42A is a diagrammatic representation of one example of allocation of the multiple programs to a single logical address space in the memory management and protection system of FIG. 41.

FIG. 42B is a diagrammatic representation of one example of allocation of the multiple programs to two logical address spaces in the memory management and protection system of FIG. 41.

FIG. 43 is an illustration of an exemplary configuration of a program management table to be used by a program allocation unit in the memory management and protection system of FIG. 41 for a case of a single virtual space scheme.

FIG. 44 is a flow chart for the operation of the program management unit in the memory management and protection system of FIG. 41 for a case of a single virtual space scheme.

FIG. 45 is an illustration of an exemplary configuration of a program management table to be used by a program allocation unit in the memory management and protection system of FIG. 41 for a case of a multiple virtual space scheme.

FIG. 46 is an illustration of an exemplary configuration of a logical address space management table to be used by a program allocation unit in the memory management and protection system of FIG. 41 for a case of a multiple virtual space scheme.

FIG. 47 is a flow chart for the operation of the program management unit in the memory management and protection system of FIG. 41 for a case of a multiple virtual space scheme.

FIG. 48 is a flow chart for the operation of the memory management and protection system of FIG. 41 for a case of a single virtual space scheme.

FIG. 49 is an illustration of an exemplary configuration of a TLB with invalidation bit to be used in the memory management and protection system of FIG. 41 for a case of a multiple virtual space scheme.

FIG. 50 is a flow chart for the operation of the memory management and protection system of FIG. 41 for a case of a multiple virtual space scheme.

FIG. 51A is a diagrammatic representation of another example of allocation of the multiple programs to two a logical address space in the memory management and protection system of FIG. 41.

FIG. 51B is a diagrammatic representation of one example of allocation of the multiple programs to three logical address spaces in the memory management and protection system of FIG. 41.

FIG. 52 is a diagrammatic representation of one example of allocation of the multiple programs to a plurality of logical address spaces in the memory management and protection system of FIG. 41.

FIG. 53 is an illustration of an access control list (ACL) to be used in the memory management and protection system of FIG. 41 for a case of using the allocation of FIG. 52.

FIG. 54 is a flow chart for the operation of the memory management and protection system of FIG. 41 in a case of calling up one user program from another user program in the allocation of FIG. 52.

FIG. 55A is a diagrammatic representation of one example of allocation of the multiple programs in the memory management and protection system of FIG. 41.

FIG. 55B is a diagrammatic representation of the programs allocated to one logical address space at one stage of the operation of the memory management and protection system of FIG. 41 according to the allocation of FIG. 55.

FIG. 55C is a diagrammatic representation of the programs allocated to another logical address space at another stage of the operation of the memory management and protection system of FIG. 41 according to the allocation of FIG. 55.

FIG. 56 is an illustration of an access control list (ACL) to be used in the memory management and protection system of FIG. 41 for a case of using the allocation of FIG. 55A.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring now to FIG. 3, one embodiment of a memory protection device to be used in a memory management unit according to the present invention will be described in detail. Here, for the sake of definiteness, the description will be given for the memory protection device which is utilized in managing a logical address space divided into eight segments, where the protection is provided in units of regions representing physical pages in each segment, although the applicability of the present invention is not limited to this particular case.

This memory protection device of FIG. 3 comprises: a segment information extractor (SIE) 1 for extracting a segment identifier identifying a segment to be accessed next from a logical address to be accessed next; a memory protection information extractor (MPIE) 2 for extracting a memory protection information for a region (page) to be accessed next from the logical address; a current segment identifier 3 for storing a segment identifier identifying a segment in which a currently executed instruction is present; a current memory protection information 17 for storing a memory protection information for the currently executed instruction, including a current transition permission 4, a current execution permission 5, and a current right permission 6; a target segment identifier 7 for storing the segment identifier extracted by the segment information extractor 1; a target memory protection information 18 for storing a memory protection information for the region (page) to be accessed next, including a target transition permission 8, a target execution permission 9, a target right permission 10, a read permission 11, and a write permission 12; a segment transition signal generator 13 for generating a segment transition signal indicating an occurrence of a segment transition by an access to the logical address; an instruction access permission signal generator 14 for generating an instruction access permission signal indicating a permission to make an instruction access to the logical address; a data access permission signal generator 15 for generating a data access permission signal indicating a permission to make a data access to the logical address; and a control unit 16 for updating the current memory protection information 17 by the target memory protection information 18 in a case the instruction access causing the segment transition is permitted.

The segment information extractor 1 extracts a segment identifier from a logical address to be accessed next which is supplied to the memory protection device from a data processing unit (not shown in FIG. 3). Here, the segment identifier indicates a segment in which the supplied logical address belongs to. The segment identifier obtained by the segment information extractor 1 is then temporarily stored as the target segment identifier 7.

Here, as shown in FIG. 4A, the segment identifier can be provided as upper bits of the logical address 50. In this case, the segment information extractor 1 can extract the segment identifier by selectively outputting only the upper bits of the supplied logical address 50, so that the segment identifier can be obtained very quickly solely from the supplied logical address.

Alternatively, as shown in FIG. 4B, the segment identifier can be provided as a part of an entry in a page table stored in a memory device or TLB (Translation Look-aside Buffer) 53, where each entry of the page table also stores corresponding memory protection information as will be described below. In this case, the segment information extractor 1 can extract the segment identifier by making an access to the page table on the memory device or TLB 53 by using a table access address obtained by an address calculator 52 from a table head address 51 indicating a starting address of the page table and a prescribed portion of the supplied logical address 50 indicating an offset with respect to the starting address. Consequently, the segments can be set up independently from the logical addresses, in irregular sizes if desired, and the extraction of the segment identifier can be achieved along with the extraction of the memory protection information also stored in the page table.

The memory protection information extractor 2 extracts the memory protection information also from the logical address supplied from the data processing unit. Here, the memory protection information is assigned in advance to each region (page) In each segment of the logical address space, in order to permit only a proper memory access to each region (page) in each segment. Such a memory protection information includes a transition permission indicating whether it is permitted to make an instruction access from each region (page) of each segment to another segment by making a segment transition, an execution permission indicating whether an access to the logical address is an instruction access or a data access, a right permission indicating rights assigned to each region in each segment to make an access to each of the eight segments of the logical address space, a read permission indicating whether it is permitted to make an access for a data read to each region (page) in each segment or not, and a write permission indicating whether it is permitted to make an access for a data write to each region (page) in each segment or not.

The memory protection information obtained by the memory protection information extractor 2 is then temporarily stored as the target memory protection information 18 including the target transition permission 8, the target execution permission 9, the target right permission 10, the read permission 11, and the write permission 12.

On the other hand, the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6 store the segment identifier, the transition permission, the execution permission, and the right permission, respectively, for the currently executed instruction, and these current segment identifier 3 and the current memory protection information 17 are to be updated by the control unit 16 to the target segment identifier 7 and the part of the memory protection information stored in the target transition permission 8, the target execution permission 9, and the target right permission 10, when the instruction access permission signal is asserted by the instruction access permission signal generator 14.

This memory protection information is provided either as an entry in the page table stored in the memory device or TLB, which can be obtained by making an access to the page table according to the supplied logical address. Here, in a case the segment identifier is provided as upper bits of the logical address as in a case of FIG. 4A described above, the entry in the page table can have a format as shown in FIG. 5A, containing the transition permission 88, the execution permission 89, the right permission 90, the read permission 91, and the write permission 92 to constitute the memory protection information as well as a valid bit 93 indicating the validity of this page table entry.

Alternatively, in a case the segment identifier is provided as a part of an entry in the page table as in a case of FIG. 4B described above, the entry in the page table can have a format as shown in FIG. 5B, containing the transition permission 88, the execution permission 89, the right permission 90, the read permission 91, the write permission 92, and the valid bit 93, along with the segment identifier 87.

Moreover, the entry in the page table can have a format as shown in FIG. 5C, containing the right permission 90 along with an operation type code 94 given in three bits, where the operation type code 94 encodes the transition permission 88, the execution permission 89, the read permission 91, the write permission 92, and the valid bit 93, as indicated in a table shown in FIG. 5D.

Here, it is to be noted that, in this embodiment, the memory protection information is provided in the page table on the memory device or TLB so that the set up or the change of the memory protection information can be made by using a usual data access Instruction to the memory device or TLB, in which case the protection of the memory protection information on the memory device or TLB is automatically provided by this memory protection unit. In addition, the right permission 90 expresses the relationship between the current segment and the target segment, so that the change of the relationship between certain two segments does not affect the relationship between the other segments. Consequently, the change of the right permission 90 can be made easily by the usual data access operation even during the execution of a program without affecting the relationships among the segments unrelated to the change.

Now, in this embodiment, the segment identifier, the right permission, and the execution permission plays roles of three arguments of a function to return an output indicating a permission or rejection of the access to the supplied logical address. Thus, by assigning the desired output to all the combinations of these three arguments appropriately, it becomes possible in this memory protection device to realize a control of memory accesses according to a semi-ordered hierarchical relationships among the regions (pages), without requiring a large amount of additional hardwares or special instructions on the data processing unit side.

As shown in FIG. 6, the segment transition signal generator 13 further comprises: a comparator 131 for comparing the current segment identifier 3 and the target segment identifier 7 and asserting a non-coincidence signal when the current segment identifier 3 and the target segment identifier 7 are not identical; and an AND gate 132 for receiving an instruction fetch command from the data processing unit and the non-coincidence signal from the comparator 131 and asserts the segment transition signal when both of the non-coincidence signal and the instruction fetch command are asserted. Thus, the AND gate 132 negates the segment transition signal when the current segment identifier 3 and the target segment identifier 7 are the same as well as when the access to be made is the data access.

As shown in FIG. 7, the instruction access permission signal generator 14 further comprises: a selector 141 for selecting an entry of the current right permission 6 corresponding to the target segment identifier 7; an AND gate 142 for asserting its output when both of the current transition permission 4 and the target execution permission 9 are asserted; an AND gate 143 for asserting its output when both of the current execution permission 5 and the target transition permission 8 are asserted; an AND gate 144 for asserting its output when both of the entry of the current right permission 6 selected by the selector 141 and the target execution permission 9 are asserted; and an OR gate 145 for asserting the instruction access permission signal when any one of the outputs of the AND gates 142, 143, and 144 is asserted. Thus, the OR gate 145 negates the instruction access permission signal when none of the outputs of the AND gates 142, 143, and 144 is asserted.

As shown in FIG. 8, the data access permission signal generator 15 further comprises: a comparator 151 for comparing the current segment identifier 3 and the target segment identifier 7 and asserts a non-coincidence signal output when the current segment identifier 3 and the target segment identifier 7 are not identical; a NAND gate 152 for receiving the non-coincidence signal from the comparator 151 and the target execution permission 9 and asserts its output when either one of the non-coincidence signal and the target execution permission 9 is negated; a selector 153 for selecting an entry of the target right permission 10 corresponding to the target segment identifier 7; an AND gate 154 for asserting its output when both of the read permission 11 and the data read command from the data processing unit are asserted; an AND gate 155 for asserting its output when both of the write permission 12 and the data write command from the data processing unit are asserted; an AND gate 156 for asserting its output when both of the outputs of the AND gates 154 and 155 are asserted; and an AND gate 157 for asserting the data access permission signal when both of the outputs of the NAND gate 152 and the AND gate 156 as well as the entry of the target right permission 10 selected by the selector 153 are asserted. Thus, the AND gate 157 negates the data access permission signal when any one of the outputs of the NAND gate 152 and the AND gate 156 and the entry of the target right permission 10 selected by the selector 153 is negated.

As shown in FIG. 9, the control unit 16 further comprises a gate 161 for transmitting the target segment identifier 7, the target transition permission 8, the target execution permission 9, and the target right permission 10 to the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6, respectively, so as to update the current memory protection information 17 stored in the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6, when the instruction access permission signal generated by the instruction access permission signal generator 14 is asserted.

Now, in a case of carrying out the instruction access according to the instruction fetch command from the data processing unit, this memory protection device of FIG. 3 operates as follows.

First, in a case of the instruction access, the data processing unit supplies the logical address to be accessed and the instruction fetch command to the memory protection device.

In the memory protection device, the logical address is supplied to the segment information extractor 1 and the memory protection information extractor 2.

The segment information extractor 1 then extracts the segment identifier from the supplied logical address, and the obtained segment identifier is stored into the target segment identifier 7.

On the other hand, the memory protection information extractor 2 extracts the memory protection information including the transition permission, the execution permission, the right permission, the read permission, and the write permission, also from the supplied logical address, and the obtained memory protection information is then stored in the target transition permission 8, the target execution permission 9, the target right permission 10, the read permission 11, and the write permission 12, as the target memory protection information 18.

Then, the segment transition signal generator 13 generates the segment transition signal according to the supplied Instruction fetch command, the current segment identifier 3, and the target segment identifier 7, as described above. In this embodiment, this segment transition signal is generated regardless of whether the instruction access has actually taken place or not. In a case the access is actually rejected, the segment transition signal can be utilized in Judging whether the rejected access is a branch instruction or not.

Also, the instruction access permission signal generator 14 generates the instruction access permission signal according to the current memory protection information, the target segment identifier 7, the current transition permission 8, and the current execution permission 9, as described above.

Here, when the instruction access permission signal is asserted by the instruction access permission signal generator 14, the control unit 16 updates the current memory protection information 17 by overwriting the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6, with a part of the target memory protection information 18 stored in the target segment identifier 7, the target transition permission 8, the target execution permission 9, and the target right permission 10, respectively. In this embodiment, this update of the current memory protection information 17 by the control unit 16 is carried out regardless of the occurrence of the segment transition. However, it is also possible to modify this embodiment such that the control unit 16 carries out the update of the current memory protection information 17 only when the segment transition occurred while the instruction access permission signal is asserted, by utilizing the segment transition signal generated by the segment transition signal generator 13, if desired.

Now, such an operation of the memory protection device of FIG. 3 in a case of carrying out the instruction access according to the instruction fetch command from the data processing unit will be illustrated for an exemplary case of realizing a memory access control according to semi-ordered hierarchical relationships among the segments as shown in FIG. 10, by using a more concrete assignment of the values to the transition permission, the execution permission, the right permission, the read permission, and the write permission, for each region (page) in each segment as shown in FIG. 11, where the value "1" indicates an assertion while the value "0" indicates a negation.

Here, it is to be noted that, this assignment indicated in FIG. 11 includes a gate page at the segment-7 in which the transition permission 88 is asserted such that a transition from any segment can be made to this gate page and an access to any segment can be made from this gate page in a case of the instruction access, as will be illustrated below. This gate page is provided for the following reason.

Namely, in this embodiment, the instruction access is permitted only when the logical address to be accessed belongs to one of those segments to which the access is permitted by the current right permission 6. Consequently, the range in which the segment transition can be made in conjunction with the instruction access is limited in terms of the segments, so as to prevent the improper access from a weaker program such as a user program to a stronger program such as a system program, while permitting the proper access from the stronger program to the weaker program.

However, such a memory access control according to the current right permission 6 also excludes any possibility for calling up the stronger program from the weaker program as well. In order to make it possible for the weaker program to call up the stronger program, it becomes necessary to permit an access from the weaker program to the stronger program through an appropriate entrance address, even when the current right permission 6 does not permit this access.

In order to cope with such a situation, in this embodiment, the branching of the instruction execution to those segments to which the access is not permitted by the current right permission 6 is made possible by first making a branching to the gate page to which the a transition from any segment can be made, and then making a further branching from the gate page to the desired segment, using the usual branching instructions, without requiring a large amount of additional hardwares or special instructions on the data processing unit side.

Here, it is to be noted that the appropriate entrance address is usually prescribed to the gate page by the system program and cannot be changed from the other programs, such that there is no need to check the entrance address to be accessed from the gate page.

FIG. 12 shows a case of an instruction fetch for the next instruction to be executed which is present in the same segment as the currently executed instruction. Here, the segment in which the currently executed instruction is present is the segment-2 as indicated by the current segment identifier 3 while the segment in which the next instruction to be executed next is present is also the segment-2 as indicated by the target segment identifier 7, so that there is no segment transition and consequently the segment transition signal generator 13 negates the segment transition signal. Also, the instruction access to this segment-2 is permitted by the current execution permission 5 and the current right permission 6, so that the instruction access permission signal generator 14 asserts the instruction access permission signal. In this case, the update of the current segment identifier 3 and the current memory protection information 17 by the control unit 16 makes no change in the content of the current segment identifier 3 and the current memory protection information 17 as the target segment identifier 7 and the target memory protection information 18 are identical to the current segment identifier 3 and the current memory protection information 17.

FIG. 13 shows a case of an instruction fetch for the next instruction to be executed which is located in the different segment as the currently executed instruction. Here, the segment in which the currently executed instruction is present is the segment-2 as indicated by the current segment identifier 3 while the segment in which the next instruction to be executed next is present is the segment-1 as indicated by the target segment identifier 7, so that there is a segment transition and consequently the segment transition signal generator 13 asserts the segment transition signal. Also, the instruction access by making a segment transition to this segment-1 is permitted by the current execution permission 5 and the current right permission 6, so that the instruction access permission signal generator 14 asserts the instruction access permission signal. In response, the control circuit 16 updates the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6 by overwriting their current values by the values in the target segment identifier 7, the target transition permission 8, the target execution permission 9, and the target right permission 10.

FIG. 14 shows a case of an instruction fetch in which a segment transition to the gate page is made as a branching from the segment in which the currently executed instruction is present, which is the segment-1 as indicated by the current segment identifier 3. According to the assignment of FIG. 11, the segment transition from the current segment-1 is permitted only to the segment-1 itself and the segment-7 which is the gate page. In this case, there is a segment transition so that the segment transition signal generator 13 asserts the segment transition signal. Also, this gate page has the transition permission 88 asserted as indicated by the target transition permission 8, and the current execution permission 5 is also asserted, so that the instruction access permission signal generator 14 asserts the instruction access permission signal. In response, the control circuit 16 updates the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6 by overwriting their current values by the values in the target segment identifier 7, the target transition permission 8, the target execution permission 9, and the target right permission 10.

FIG. 15 shows a case of an instruction fetch in which a segment transition from the gate page is made as a branching to a segment in which the next instruction to be executed is present, which is the segment-3 as indicated by the current segment identifier 3. In this case, there is a segment transition so that the segment transition signal generator 13 asserts the segment transition signal. Also, this gate page has the transition permission 88 asserted as indicated by the current transition permission 4, and the target execution permission 9 is also asserted, so that the instruction access permission signal generator 14 asserts the instruction access permission signal. In response, the control circuit 16 updates the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission 6 by overwriting their current values by the values in the target segment identifier 7, the target transition permission 8, the target execution permission 9, and the target right permission 10.

FIG. 16 shows a case of an instruction fetch in which a requested segment transition is a segment transition to a segment to which the segment transition is not permitted. Namely, in this case, the currently executed instruction is present in the segment-1 as indicated by the current segment identifier 3, and the current right permission 6 for the permits the access only to the segment-1, while the next instruction to be executed is present in the segment-3 as indicated by the target segment identifier 7. In this case, the current right permission 6 does not permit the access to the segment-3, so that the entry of the current right permission 6 corresponding to the target segment identifier 7 selected by the selector 141 is negated and consequently the output of the AND gate 144 is negated. Also, the target transition permission 8 is negated as the segment-3 is not the gate page, so that the output of the AND gate 142 is also negated. Moreover, the current transition permission 4 is also negated as the segment-1 is not the gate page, so that the output of the AND gate 143 is also negated. Consequently, the OR gate 145 negates the instruction access permission signal as none of the outputs of the AND gates 142, 143, and 144 is asserted. In this case, the occurrence of the improper access can be indicated by the negated instruction access permission signal from the instruction access permission signal generator 14, and whether the rejected access is a branch instruction or not can be judged according to the segment transition signal from the segment transition signal generator 13. Also, since the instruction access permission signal is not asserted, the control circuit 16 does not update the current segment identifier 3, the current transition permission 4, the current execution permission 5, and the current right permission B.

Next, in a case of carrying out the data access according to the data read command and the data write command from the data processing unit, this memory protection device of FIG. 3 operates as follows.

First, in a case of the data access, the data processing unit supplies the logical address to be accessed and the data read and the data write commands to the memory protection device.

In the memory protection device, the logical address is supplied to the segment information extractor 1 and the memory protection information extractor 2, just as in a case of the instruction access, such that the segment information extractor 1 extracts the segment identifier from the supplied logical address and the obtained segment identifier is stored into the target segment identifier 7, while the memory protection information extractor 2 extracts the memory protection information also from the supplied logical address and the obtained memory protection information is stored in the target transition permission 8, the target execution permission 9, the target right permission 10, the read permission 11, and the write permission 12, as the target memory protection information 18.

Then, the data access permission signal generator 15 generates the data access permission signal according to the current segment identifier 3, the target segment identifier 7, the target memory protection information 18, and the data read and data write commands supplied from the data processing unit, as described above. Here, it is to be noted that the checking made by the comparator 151 and the NAND gate 152 is provided in order to permit the access to the instruction region for reading or writing of the instruction by the data access operation as long as the instruction region to be accessed is in the same segment as the current segment. However, this checking made by the comparator 151 and the NAND gate 152 is not absolutely necessary, so that it can be omitted depending on the desired protection policy adopted.

Now, such an operation of the memory protection device of FIG. 3 in a case of carrying out the data access according to the data read and data write commands from the data processing unit will be illustrated for the same exemplary case of realizing hierarchical relationships among the segments shown in FIG. 10 by using the same assignment of the values to the transition permission, the execution permission, the right permission, the read permission, and the write permission, as shown in FIG. 11.

Here, it is to be noted that, in this case, the target execution permission 9 indicates that the access to be made next is the data access, so that the target right permission 10 can be regarded as indicating the right to be accessed for the data at the logical address to be accessed next. Consequently, the regions to which the instruction access is permitted from the supplied logical address is independent of the regions to which the data access is permitted from the supplied logical address, such that it becomes possible to set up the regions that can be accessed only from the regions in the same segment, and the regions that can be shared with the other segments. Thus, it is possible in this embodiment to hide the data which are effective in protecting the programs.

FIG. 17 shows a case of a data fetch for the data write operation to the segment to which the data access is permitted. Here, the segment in which the currently executed instruction is present is the segment-2 as indicated by the current segment identifier 3 while the segment to be accessed for the data write operation is the segment-1 as indicated by the target segment identifier 7. In this case, the target execution permission 9 is negated to indicate the data access so that the NAND gate 152 asserts its output, while the access from the segment-2 to the segment-1 is permitted by the target right permission 10 so that the entry of the target right permission 10 corresponding to the current segment identifier 3 selected by the selector 153 is asserted, and the write permission 12 permits the data write, so that the OR gate 156 asserts its output. Consequently, the data access permission signal generator 15 asserts the data access permission signal.

FIG. 18 shows a case of a data fetch for the data read operation from the segment to which the data access is not permitted. Here, the segment in which the currently executed instruction is present is the segment-2 as indicated by the current segment identifier 3 while the segment to be accessed for the data read operation is the segment-4 as indicated by the target segment identifier 7. In this case, the target execution permission 9 is negated to indicate the data access so that the NAND gate 152 asserts its output, and the read permission 11 permits the data read so that the OR gate 156 asserts its output, but the access from the segment-2 to the segment-4 is not permitted by the target right permission 10, so that the entry of the target right permission 10 corresponding to the current segment identifier 3 selected by the selector 153 is negated. Consequently, the data access permission signal generator 15 negates the data access permission signal. In this case, the occurrence of the improper access can be indicated by the negated data access permission signal from the data access permission signal generator 15.

Thus, in this memory protection device of FIG. 3, the rights to make accesses to the segments in the virtual memory can be set up separately for the case of the instruction access and the case of the data access, according to semi-ordered hierarchical relationships among the segments such as that shown in FIG. 10.

Namely, when the assignment shown in FIG. 11 realizing the semi-ordered hierarchical relationships shown in FIG. 10 is used, the regions in the logical address space 80 to which the direct branching can be made from the segment-2 in a case of the instruction fetch can be limited, as indicated in FIG. 19, to the branching to the segment-1 excluding a data region 81 indicated by an arrow (1) which is permitted by the right permission, the branching to the gate page 82 indicated by an arrow (2), and the branching from the gate page 82 indicated by an arrow (3) to a prescribed entrance address 83.

As for the case of the data fetch, the regions in the logical address space 80 to which the data access can be made from the segment-2 can be set up differently from the case of the instruction access, as indicated in FIG. 20, to the same segment-2, the argument region 84 in the segment-1 and the buffer region 85 in the segment-3.

As a consequence of realizing such a limited transition range for the instruction execution and a page accessible only from one segment, it becomes possible to realize a segment which is hidden from the other segment in a case of allocating a plurality of programs to a single virtual space, such that the hidden segment can be protected against the improper accesses from the other segments.

Now, the memory protection device of FIG. 3 described above can be utilized as a component of a memory management unit having exemplary configurations as shown in FIG. 21 and FIG. 22.

FIG. 21 shows one exemplary configuration of a memory management unit, in which a memory management unit 70A generally comprises a memory protection device 71A of the type similar to that shown in FIG. 3, and an address translation device 72 for translating the logical address supplied from the data processing unit 60A into the physical address.

In this memory management unit 70A, the logical address and the instruction fetch command are supplied to the memory protection device 71A directly from the data processing unit 60A, while the data read and data write commands are supplied to the memory protection device 71A from AND gate 73A and NAND gate 74A which obtain the data read and data write commands from the read/write signal and the instruction/data signal supplied from the data processing unit 60A.

The segment transition signal, instruction access permission signal, and data access permission signal obtained by the memory protection device 71A are supplied to the data processing unit 60A. On the other hand, the address translation operation of the address translation device 72 is controlled by an address translation permission signal obtained by an OR gate 75 which outputs the address translation permission signal when either one of the instruction access permission signal and the data access permission signal obtained by the memory protection device 71A is asserted.

FIG. 22 shows another exemplary configuration of a memory management unit suitable for a case in which the data processing unit 60B supplies the logical instruction address and the logical data address separately. In this configuration of FIG. 22, a memory management unit 70B generally comprises: a memory protection device 71B of the type similar to that shown in FIG. 3 in which the segment information extractor, the memory protection information extractor, the target segment identifier, and the target memory protection information are provided in duplicate with respect to the separately supplied logical instruction address and logical data address; an instruction address translation device 72A for translating the logical instruction address supplied from the data processing unit 60A into the physical instruction address; and a data address translation device 72B for translating the logical data address supplied from the data processing unit 60A into the physical data address.

In this memory management unit 70B, the logical instruction address, the instruction fetch command, and the logical data address are supplied to the memory protection device 71B directly from the data processing unit 60B, while the data read and data write commands are supplied to the memory protection device 71B from an AND gates 73B and 74B which obtain the data read and data write commands from the read/write signal and the data access signal supplied from the data processing unit 60B.

The segment transition signal, instruction access permission signal, and data access permission signal obtained by the memory protection device 71B are supplied to the data processing unit 60B. On the other hand, the address translation operation of the instruction address translation device 72A is controlled by the instruction access permission signal obtained by the memory protection device 71B while the address translation operation of the data address translation device 72B is controlled by the data access permission signal obtained by the memory protection unit 71B.

Referring now to FIG. 23, another embodiment of a memory management unit according to the present invention will be described in detail. This memory management unit utilizes an ACL (Access Control List) type controlling in which the access is controlled according to an ACL indicating where each page can be accessed from, instead of a capability type controlling used in the previous embodiment in which the access is controlled according to various permissions given in terms of bit patterns indicating where each page can make access to. Here, as in the above, for the sake of definiteness, the description will be given for a case in which the protection is provided in units of regions representing physical pages in each segment, where each page is identified by a page number defined by upper 20 bits of full address, although the applicability of the present invention is not limited to this particular case.

In this configuration of FIG. 23, the memory management unit 101 comprises: an address translation device 102 for translating a logical page number supplied from a data processing unit (not shown in FIG. 23) into a corresponding physical page number; a TLB (Translation Look-aside Buffer) check device 103 for checking a TLB storing a selected number of the logical and physical page number pairs along with the memory protection information for each logical address; a thread number memory 104 for storing thread numbers assigned in advance to threads to be executed in the data processing unit; and an OR gate for outputting a protection fault signal 119 indicating an occurrence of a protection fault.

In this embodiment, the memory management unit 101 is supplied with a logical page number 111 defined by upper 20 bits of the logical address to be accessed, an LPC (Last Program Counter) upper 20 bits value 112 defined by upper 20 bits of an Immediately previous value indicated by a program counter in the data processing unit which indicates an address at which the currently executed instruction is present, and 3 bits memory access mode (RWX) 113 indicating a type of access to be made including read, write and execution, from the data processing unit. Then, the memory management unit 101 basically operates to obtain a physical page number 114 defined by upper 20 bits of the physical address corresponding to the supplied logical page number 111.

In the memory management unit 101, the supplied logical page number 111, LPC upper 20 bits value 112, and memory access mode 113 are supplied to the address translation device 102 and the TLB check device 103 simultaneously, along with a current thread 115 specifying a thread number of the currently executed thread stored in the thread number memory 104, such that the address translation operation to obtain the desired physical page number 114 for the physical address to be accessed is carried out in parallel at the address translation device 102 and the TLB check device 103.

Here, the address translation device 102 translates the supplied logical page number into the desired physical page number by using a page table enlisting all corresponding logical and physical page number pairs along with their associated memory protection information in forms of page table entries (PTE), while the TLB check device 103 obtains the desired physical page number corresponding to the supplied logical page number by using the TLB enlisting a selected number of the page table entries of the page table cached from the address translation device 102.

When the TLB check device 103 finds the desired physical page number in the TLB, the TLB check device 103 outputs this physical page number as the desired physical page number 114 and supplies a TLB hit signal 116 to the address translation device 102 in order to abort the address translation operation in the address translation device 102.

When the TLB check device 103 fails to find the desired physical page number in the TLB, the TLB check device 103 asserts a TLB miss signal 117. In this case, the address translation device 102 continues its address translation operation. In a case the address translation device 102 obtains the desired physical page number from the page table successfully, the address translation device 102 caches the page table entry (PTE) 24 for the obtained physical page number into the TLB in the TLB check device 103, and the TLB check device outputs this physical page number indicated by the supplied page table entry (PTE) 24 as the desired physical page number 114. On the other hand, in a case the address translation device 102 also fails to obtain the desired physical page number corresponding to the supplied logical page number, the address translation device 102 generates a page fault signal 118 to interrupt the operation of the data processing unit.

In addition, in a case the desired physical page number is found to be associated with the memory protection information indicating a prohibition to make an access to the physical address corresponding to this physical page number in either one of the address translation device 102 or the TLB check device 103, that one of the address translation device 102 or the TLB check device 103 which found the desired physical page number supplies the protection fault signal 122 or 121 to the OR gate 105 such that the protection fault signal 119 to interrupt the operation of the data processing unit is outputted from the OR gate 105.

Furthermore, when the TLB check device 103 finds the desired physical page number in the TLB, but fails to hit any ACL entries, the TLB check device 103 asserts an ACL miss signal 120. In this case, the address translation device 102 checks the ACL entries.

FIG. 24 shows a further detail configuration of the TLB check device 103 in this memory management unit 101.

In this configuration of FIG. 24, the TLB check device 103 has the TLB 31 storing a plurality of entries, of which only one is shown in FIG. 24. Each entry of this TLB 31 includes: the logical page number 311; the physical page number 312 corresponding to the logical page number 311; five flags (V, D, R, M, and E) 313 to 317 for indicating the attributes of the page represented by the logical page number 311 and the physical page number 312; a plurality (three in FIG. 24) of thread numbers 318 for the threads which are permitted to make an access to the logical address corresponding to the logical page number 311; the LPC upper 20 bits value 319 corresponding to each of the thread numbers 318; three flags (PE, TE, and B) 320 to 322 associated with each of the thread numbers 318; and memory access mode permission (rwx) 323 associated with each of the thread numbers 318. In this TLB 31, an area U next to the flag E is unused.

In this embodiment, three sets of the thread number 318, the LPC upper 20 bits value 319, the flags 320 to 322, and the memory access mode permission 323 form the ACL (Access Control List) for indicating which thread that is executing codes of which logical page is permitted to make what kind of access to that logical page.

In this TLB 31, the five flags (V, D, R, M, and E) 313 to 317 indicate the following attributes of the page. The flag (V) 313 is a valid flag indicating whether this TLB entry is valid or not. The flag (D) 314 is a dirty flag indicating whether the page represented by this TLB entry has been changed or not. The flag (R) 315 is a referenced flag indicating whether the page represented by this TLB entry has been accessed. The flag (M) 316 is a more flag indicating whether the additional ACL entries for the page represented by this TLB entry other than the three ACL entries enlisted in the TLB 31 exist or not. The flag (E) 317 is an enable flag indicating whether the ACL for the page represented by this TLB entry is to be checked or not.

Also, in each ACL entry in this TLB 31, the memory access mode permission (rwx) 323 indicates whether the page represented by this TLB entry is readable, writable, and executable in the thread represented by the thread number 318 of this ACL entry.

Moreover, in each ACL entry in this TLB 31, the three flags (PE, TE, and B) 320 to 322 given in the ACL indicate the following attributes of each ACL entry.

The flag (PE) 320 indicates whether a comparison of the thread number 318 of this ACL entry with the thread number specified by the current thread 115 is to be made or not. When this flag (PE) 320 is set to 0, the check of the access condition regarding the thread number can be omitted, such that the access permission can be given to all the threads uniformly.

The flag (TE) 321 indicates whether a comparison of the LPC upper 20 bits value 219 of this ACL entry with the LPC upper 20 bits value 112 is to be made or not. When this flag (TE) 321 is set to 0, the access permission can be given to any ACL entry regardless of the LPC upper 20 bits value, as long as the thread number of the thread is the same as the thread number 318 of this ACL entry,

The flag (B) 322 indicates whether the coincidence of the thread numbers is to be checked or the size relationship between the thread numbers is to be checked in the comparison of the thread numbers. When this flag (B) 322 is set to 0, the access permission is given only when the thread number specified by the current thread 115 is equal to the thread number 318 of this ACL entry. On the other hand, when this flag (B) 322 is set to 1, the access permission is given when the thread number specified by the current thread 115 is greater than or equal to the thread number 318 of this ACL entry. Thus, in this case of setting the flag (B) 322 to 1, the thread numbers are utilized to indicate the protection levels in the ring protection, where the larger thread number is given the stronger right.

Now, in this TLB check device 103 of FIG. 24, the logical page number 111 supplied from the data processing unit specifies the corresponding TLB entry having the identical logical page number 318 in the TLB 31. Then, the thread number specified by the current thread 115 and the LPC upper 20 bits value 112 and the 3 bits memory access mode (RWX) 113 supplied from the data processing unit are combined together at combiners 32 and 33 to obtain 43 bits output 331, which is to be compared with each of the three ACL entries of this TLB entry by three identical comparison units 34, 35, and 36.

Each of the comparison units 34, 35, and 36 has a configuration as shown in FIG. 25, which comprises: a comparator 341 for comparing the thread number specified by the current thread 115 with the thread number 318 of each ACL entry and asserting its output when they are identical; a comparator 342 for comparing the supplied LPC upper 20 bits value 112 with the LPC upper 20 bits value 319 of each ACL entry and asserting its output when they are identical; an AND gate 343 for asserting its output when the output of the comparator 341 and the flag (B) 322 are both asserted; an OR gate 347 for asserting its output when either one of the outputs of the comparator 341 and the AND gate 343 is asserted; an OR gate 349 for asserting its output when the output of the OR gate 347 is asserted while the flag (PE) 320 is negated; an OR gate 350 for asserting its output when the output of the comparator 342 is asserted while the flag (TE) 321 is negated; an AND gate 344 for asserting its output 352 when the outputs of the OR gates 349 and 350 are both asserted; an AND gate 345 for asserting each bit of its 3 bits output when each of the memory access mode (RWX) 113 is identical to each of the memory access mode permission (rwx) 323 of each ACL entry; an OR gate 348 for asserting its output when any one of the 3 bits output of the AND gate 345 is asserted; and an AND gate 346 for asserting its output 351 when the outputs of the OR gate 348 and the AND gate 344 are both asserted.

Thus, the AND gate 344 asserts the output 352 when the thread number specified by the current thread 115 is identical to the thread number 318 of each ACL entry and the supplied LPC upper 20 bits value 112 is identical to the LPC upper 20 bits value 319 of each ACL entry, i.e., when the memory access conditions are satisfied. Then, the AND gate 346 asserts the output 351 when the memory access conditions are satisfied and the type of the memory access to be made is permitted. In other words, when the output 351 is asserted, the memory access is permitted.

Then, the TLB check device 103 of FIG. 24 further comprises: a NOT gate 42 for asserting its output when the enable flag (E) 317 is negated; an OR gate 37A for asserting the TLB hit 116 when any one of the outputs 351 of the three comparison units 34, 35, and 36 and the output of the NOT gate 42 is asserted; an OR gate 37B for asserting its output when any one of the outputs 352 of the three comparison units 34, 35, and 36 and the output of the NOT gate 42 is asserted; an AND gate 38A for asserting its output when the output of the OR gate 37A is negated while the output of the OR gate 37B is asserted; an AND gate 38B for asserting its output when the outputs of the OR gate 37B and the more flag (M) 316 are both negated; an OR gate 39 for asserting the protection default 121 when either one of the outputs of the AND gate 38A and the AND gate 38B is asserted; an AND gate 38C for asserting the ACL miss 120 when the output of the OR gate 37B is negated while the more flag (M) 316 is asserted; a gate 40 for outputting the physical page number 312 of this TLB entry when the TLB hit 116 is asserted by the OR gate 37A; and a NOT gate 41 for asserting the TLB miss 117 when the valid flag (V) 313 is negated.

Thus, when the memory access conditions are satisfied and the type of the memory access to be made is permitted for any one of the ACL entries on this TLB entry, the TLB hit is asserted and the physical page number of this TLB entry is outputted as the desired physical page number corresponding to the supplied logical page number. On the other hand, the protection fault 121 is asserted when the memory access conditions are satisfied but the type of the memory access to be made is not permitted, or when the memory access conditions are not satisfied and there is no other ACL entries for the page represented by this TLB entry.

Also, when the enable flag (E) 317 is negated, the physical page number 312 of this TLB entry is outputted without carrying out the check of the ACL entries.

When neither the TLB hit 116 nor the protection fault 121 is asserted, the address translation operation of the TLB check device 103 is terminated and the result of the address translation operation by the address translation device 102 is waited while the ACL entries are checked.

When the memory access conditions are satisfied but no corresponding ACL entry can be found in this TLB entry, the TLB check device 103 asserts an ACL miss signal 120 and the address translation device 102 checks the ACL entries.

FIG. 26 shows a further detail configuration of the address translation device 102 in this memory management unit 101.

In this configuration of FIG. 26, the address translation device 102 comprises: a first stage address translation unit 21 for translating a first 7 bits 1111 of the supplied logical page number 111; a second stage address translation unit 22 for translating next 7 bits 1112 of the supplied logical page number 111; a third stage address translation unit 23 for translating last 6 bits 1113 of the supplied logical page number 111; a root pointer for indicating a start address of a first stage address table in the first stage address translation unit 21; an OR gate 28 for outputting the page fault signal 118 according to the results of the address translation by the first, second, and third stage address translation units 21, 22, and 23; and an OR gate 29 for outputting the protection fault signal 122 according to the results of the address translation by the first, second, and third stage address translation units 21, 22, and 23.

In this address translation device 102 of FIG. 26, the thread number specified by the current thread 115, the supplied LPC upper 20 bits value 112, and the 3 bits memory access mode (RWX) 113 are supplied to each of the first, second, and third stage address translation units 21, 22, and 23 as an input 211, and the first stage address table in the first stage address translation unit 21 is accessed by using the start address indicated by the root pointer 25 and the first 7 bits 1111 of the logical page number 111.

Then, the first stage address translation unit 21 determines an entry in the first stage address table corresponding to the first 7 bits 1111 of the logical page number 111 and outputs the obtained entry as a start address 26 of an address table in the second stage address translation unit 22 such that the second stage address table in the second stage address translation unit 22 is accessed by using the start address 26 and the next 7 bits 1112 of the logical page number 111.

Then, the second stage address translation unit 22 determines an entry in the second stage address table corresponding to the next 7 bits 1112 of the logical page number 111 and outputs the obtained entry as a start address 27 of an address table in the third stage address translation unit 23 such that the third stage address table in the third stage address translation unit 23 is accessed by using the start address 27 and the last 6 bits 1113 of the logical page number 111.

Then, the third stage address translation unit 23 determines an entry in the third stage address table corresponding to the last 6 bits 1113 of the logical page number 111 and outputs the obtained entry as the page table entry (PTE) 24 to be supplied to the TLB check device 103.

Here, the address translation operation carried out in any one of the first, second, and third stage address translation units 21, 22, and 23 is aborted when the TLB hit 116 or the protection fault 121 is supplied from the TLB check device 103.

Also, when the desired physical page number is found to be non-existent by any one of the first, second, and third stage address translation units 21, 22, and 23, that one of the first, second, and third address translation unit 21, 22, and 23 which found the non-existence of the desired physical page number supplies the page fault signal to the OR gate 28 such that the page fault signal 118 is outputted to the OR gate 105.

Also, when the desired physical page number is found to be associated with the memory protection information indicating a prohibition to make an access to the logical address corresponding to this physical page number by any one of the first, second, and third stage address translation units 21, 22, and 23, that one of the first, second, and third address translation unit 21, 22, and 23 which found the access prohibition supplies the protection fault signal to the OR gate 29 such that the protection fault signal 122 is outputted to the OR gate 105.

FIG. 27 shows a further detail configuration of the first stage address translation unit 21 in the address translation device of FIG. 26. It is to be noted that the second stage address translation unit 22 also has a similar further detail configuration for which the reference numerals given in parentheses should be used.

In this configuration of FIG. 27, the first (second) stage address translation unit 21 (22) is supplied with the 43 bits of the input 211, the TLB hit 116, the first (next) 7 bits 1111 (1112) of the logical page number 111, and the address table start address 25 (26). The first (next) 7 bits 1111 (1112) and the address table start address 25 (26) are combined together by an address composition unit 212 to obtain an address table access address which specify the particular address table entry 213 corresponding to the first (next) 7 bits of the logical page number 111.

Each address table entry 213 contains: a pointer 2131 to next stage address table indicating the address table start address 26 (27) of the second (third) stage address table; three flags (V, M, and E) 2132, 2133, and 2134 similar to the flags (V, M, and E) used In the T