Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-08-26
2001-06-26
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06253225
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of executing processes in an operating system controlling a computer system and a method of accessing a resource in the computer system. More particularly, the invention is concerned with a method of executing processes by using a shared resource in an operating system providing a multiprocessor or multiprocessing environment.
In the operating system capable of providing the multiprocessing environment for executing a plurality of processes (or tasks) in parallel on a time-division basis, it is required to execute the processes while performing mutual exclusive control or management so that the resource shared among the processes is not simultaneously allocated to a plurality of processes. As a means for realizing such mutual exclusive management, there is known and widely adopted in the operating system (OS) a procedure referred to as “lock control”.
In the lock control, a flag indicating that a corresponding shared resource is being used is set for each of the shared resources. When one of the processes is going to perform a processing by using a given one of the shared resources, it is checked whether the flag corresponding to this shared resource is set by any other process. Unless the flag is set by the other process, the given one process can use exclusively the shared resource while setting the flag indicating that the resource is occupied. This operation is typically referred to as “lock or locking” of the shared resource. Upon completion of the processing for the shared resource, the process releases the shared resource while resetting the flag. This operation is referred to as “unlock or unlocking” of the shared resource. On the other hand, when the flag corresponding to the shared resource to be used is set by any other process, the operating system sets the one process requesting the use of this resource to the waiting or standby state until that shared resource has been unlocked.
At this juncture, let's assume that a process
1
of low priority and a process
2
of high priority are executed in parallel and that a shared resource A is shared availably by these two processes. On this assumption, it is further supposed that the process
1
of low priority has locked the shared resource A in the course of using a CPU (central processing unit) and that the shared resource A has entered into a suspended state with the lock being left validated. In that case, the process
2
of high priority assigned with the right for using the CPU in succession to the process
1
can not use the shared resource A, because the resource has been locked by the process
1
of low priority. As a consequence, execution in succession becomes impossible.
The problem that the process of high priority is inhibited from execution in succession because of the lock secured by the process of low priority is referred to as the priority inversion problem. Concerning this priority inversion problem, reference may be made to “PRIORITY INHERITANCE PROTOCOLS: AN APPROACH TO REAL-TIME SYNCHRONIZATION” in IEEE TRANSACTIONS ON COMPUTERS, Vol. 39, No. 9, September 1990, pp. 1175-1185. In the conventional operating system known heretofore, when the priority inversion takes place, the dormant process of low priority acquired and locked the shared resource is executed with the topmost priority in order to unlock the shared resource so that the process of high priority can be executed as early as possible.
On the other hand, the operating system providing the multiprocessing environment is imparted with a function for protecting the resource allocated to a given process against the illegal access attempted by any other process. This function is referred to as the access right control or manage function. The access right control or management now under consideration is based on the presumption that the access right can be set on a process-by-process basis and that a plurality of processes may simultaneously try to access a computer resource. An interface for allowing a user application to call the functions of the operating system is ordinarily provided and known as “system call”. In this conjunction, it is noted that when a pointer is used as an argument of the system call, designation of an illegal address by the user application may unfavorably lead to destruction of important data resident in the operating system. To avoid such unwanted situation, an identifier is used as the argument in place of the pointer in typical one of the access right control or management.
In the case of the access right control method in which the identifier is used as the argument in the system call issued by the user application, the operating system is required to translate the identifier to an address in the resource for making access to the resource. In this context, the simplest one of the translation methods is a method in which the hash function is employed. According to this method, an identifier is placed in or assigned to the hash function as a key, whereon the hash value as obtained is used as the address. The access right control method relying on the hash function will be described below.
§1. Configuration
As is shown in
FIG. 1
, the operating system assigns a resource identifier
100
to the hash function (F)
101
as a key to acquire as the hash value an index “Index”
102
contained in a resource management data table
104
. As is shown in
FIG. 2A
, resource management data
105
stored in the resource management data table
104
contains an identifier
201
, a pointer
205
to a resource
103
, a flag
202
indicating presence or absence of a succeeding or next resource management data
106
, a pointer
203
to the succeeding resource management data
106
, and a pointer
204
to process management data
107
.
There may arise such situation that the hash function returns a same index “Index” for different identifiers RID. In that case, collision between the indexes “index” will occur. Accordingly, the second resource management data
106
et seq. are stored in an overflow area with the address of the second or succeeding resource management data
106
being placed in the immediately preceding resource management data
105
.
In case the resource is a shared resource, there exist a plurality of processes having respective access rights for the same identifier RID. In that case, the pointers to the second process identifier data
108
et seq. are placed in the immediately preceding process management data
107
.
The resource management data
105
is shown in
FIG. 2A
while the process management data
107
is shown in FIG.
2
B. As can be seen in
FIG. 2B
, the process management data
107
is composed of a process identifier
207
, a flag
208
indicating presence or absence of the next process management data, and a pointer
209
to the next process management data. At the end of the user application, it becomes necessary to know the identifier of the process having the access right in order to deallocate the resource occupied by the process. Thus, the operating system is provided with a process-specific resource identifier list
109
in which a resource identifier
110
is entered every time when a corresponding resource is generated or every time the access right to the shared resource is acquired.
§2. Resource Allocation Processing
FIG. 3
is a flow chart for illustrating a resource allocation processing.
When the system call requesting the resource allocation is issued to the operating system by a user application, the operating system responds thereto by allocating the resource (step
1000
). Subsequently, the operating system acquires an identifier RIDx definite in the system (step
1001
) and places the identifier RIDx to the hash function as a key. Thus, the index “Index” contained in the resource management data table
104
, i.e., the address where the resource management data x is stored is obtained (step
1002
). In the case where the resource management data y has already been placed at the leading location of the area designa
Iwasaki Masaaki
Nakahara Masahiko
Nakano Takahiro
Serizawa Kazuyoshi
Taguchi Shihoko
Antonelli Terry Stout & Kraus LLP
Banankhah Majid A.
Hitachi , Ltd.
LandOfFree
Process executing method and resource accessing method in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process executing method and resource accessing method in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process executing method and resource accessing method in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520005