 |
Claims  |
|
|
What is claimed is:
1. In a multitasking computer system having a central processing unit,
memory means for storing data and data structures, and predefined system
resources, an operating system comprising:
a multiplicity of objects comprising data structures stored in said memory
means;
a multiplicity of container means, stored in said memory means, for
referencing sets of said objects, each container means including means for
storing a multiplicity of object pointers to locations in said memory
means, stored in said memory means, where said set of objects are stored;
a multiplicity of container directory means for referencing sets of said
container means, each container directory means including a plurality of
container pointer means, each container pointer means having means for
pointing to the location in said memory means of a corresponding one of
said container means; and
container transfer means for transferring a specified one of said container
means from a first container directory means to a specified container
directory means, including
means for deleting a container pointer in said first container directory
means corresponding to said specified container means; and
means for storing a container pointer corresponding to said specified
container means in said specified container directory means;
whereby an entire set of objects referenced by a container means is
transferred to a specified container directory means.
2. An operating system as set forth in claim 1,
each said object including transfer flag means for denoting whether said
object is transferable;
said container transfer means including means for transferring a specified
container transfer only when said transfer flag of all of said objects
referenced by said specified container means is set.
3. An operating system as set forth in claim 1,
each said container means including transfer flag means for denoting
whether said container means is transferable;
said container transfer means including means for responding to a request
to transfer a specified container means to a specified container directory
means, including means for denying a request for a container transfer when
said transfer flag means of said container means is clear.
4. An operating system as set forth in claim 3,
each said object including transfer flag means for denoting whether said
object is transferable;
said container transfer means including means for denying a request for a
container transfer when said transfer flag of at least one object
referenced by said specified container means is clear.
5. An operating system as set forth in claim 1, said operating system
further including:
object identifiers, corresponding to each said object, for referencing said
objects; each said object pointer in said multiplicity of object container
means corresponding to one of said object identifiers;
each said object including count means for denoting the number of object
identifiers corresponding to said object;
identifier creating means for creating an additional object identifier for
a specified object and for incrementing the number denoted by the count
means of said specified object;
said container transfer means including means for responding to a request
to transfer a specified container means to a specified container directory
means, said responding means including means for denying a request for a
container transfer when said count means of at least one object referenced
by said specified container means denoted a value greater than one;
whereby a container means cannot be transferred if any objects referenced
by said container means have additional object identifiers.
6. In a multitasking computer system having a central processing unit,
memory means for storing data and data structures, and predefined system
resources, an operating system comprising:
a multiplicity of objects comprising data structures stored in said memory
means;
a multiplicity of container means, stored in said memory means, for
referencing sets of said objects, each container means including means for
storing a multiplicity of object pointers to locations in said memory
means for said set of objects;
a multiplicity of container directory means, stored in said memory means
for referencing sets of said container means, each container directory
means including a plurality of container pointers, each pointing to the
location in said memory means of a corresponding one of said container
means; and
process setup means for creating one of said container means, for storing
in said created container means object pointers for a multiplicity of
objects, and for storing in a first one of said container directory means
a container pointer to said created container means;
said process setup means further including container transfer means for
transferring said created container means from said first container
directory means to a specified container directory means, including
means for deleting a container pointer in said first container directory
means corresponding to said specified container means; and
means for storing a container pointer corresponding to said specified
container means in said specified container directory means;
whereby an entire set of objects referenced by a container means is
transferred to a specified container directory means.
7. An operating system as set forth in claim 6, said process setup means
including means for creating a new process in said system, said created
process having means for accessing said specified container directory
means;
whereby a created process is provided a context defined by objects in said
created container means.
8. An operating system as set forth in claim 6,
each said object including transfer flag means for denoting whether said
object is transferable;
said container transfer means including means for transferring a specified
container transfer only when said transfer flag of all of said objects
referenced by said specified container means is set.
9. An operating system as set forth in claim 6, said
each said container means including transfer flag means for denoting
whether said container means is transferable;
said container transfer means including means for responding to a request
to transfer a specified container means to a specified container directory
means, including means for denying a request for a container transfer when
said transfer flag means of said container means is clear.
10. An operating system as set forth in claim 6, said operating system
further including:
object identifiers, corresponding to each said object, for referencing said
objects; each said object pointer in said multiplicity of object container
means corresponding to one of said object identifiers;
each said object including count means for denoting the number of object
identifiers corresponding to said object;
identifier creating means for creating an additional object identifier for
a specified object and for incrementing the number denoted by the count
means of said specified object;
said container transfer means including means for responding to a request
to transfer a specified container means to a specified container directory
means, said responding means including means for denying a request for a
container transfer when said count means of at least one object referenced
by said specified container means denoted a value greater than one;
whereby a container means cannot be transferred if any objects referenced
by said container means have additional object identifiers. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
The present invention relates generally to multitasking digital computer
systems and particularly to methods and systems for managing the data
structures used by a multitasking digital computer system.
BACKGROUND OF THE INVENTION
Large computer systems generally allow many users to simultaneously use a
single computer's resources. Such systems are herein called multitasking
digitial computer systems. Such computers include virtually all mainframe
computers and most minicomputers.
One of the primary jobs of the operating system for a multitasking computer
system is to support and keep track of the operations of a multiplicity of
users who are running numerous concurrent processes. Thus the computer's
operating system must have data structures which represent the status of
each user. Such status information includes the memory and other resources
being used by each user process.
If every user process were completely independent, had its own dedicated
resources, and there were no concerns about which resources each process
could use, operating systems could be relatively simple. However in
actuality, computer resources are shared and many user processes need to
access commonly used or owned resources. In fact, each user may generate a
number of execution threads which run simultaneously and which need to be
able to share resources and to communicate with other ones of the user's
threads.
Another concern in multitasking computer systems is security and data
integrity. Ideally, the computer system should provide an access security
system which enables each user to control the extent or amount of sharing
of information that belongs to the user. Further, the system should
provide several types of protection. For example, when multiple processes
are allowed access to a resource, the identity of each process which
attempts to access the resource should be tested to determine if that
particular process is authorized to access the resource. The system of
access control should also provide limited "visibility" of computer
resources so that an unauthorized user cannot obtain information about
another user by repeated attempts to access resources with various names.
In addition, to protect data integrity, the system must protect against
simultaneous accesses by different authorized processes.
Yet another concern of multitasking operating systems is clearing the
system of "objects" (i.e., files and data structures) which are no longer
needed by any of the system users. Ideally, the system should also be able
to automatically deallocate resources, such as input/output devices, no
longer needed by a process.
SUMMARY OF THE INVENTION
In summary, the present invention is an object based operating system for a
multitasking computer system. The present invention, which is also called
an object based architecture, is "object based" because it provides
objects which represent the architecture or interrelationships of the
system's resources. The present invention provides an extensible, yet
rigorous framework for the definition and manipulation of object data
structures.
Objects, generally, are data structures which store information about the
user processes running in the system, and which act as gateways to using
the system's resources. Resources, generally, include sets of information,
physical devices such as a tape drive, and various programs or
"operations". Such resources are not available to a user unless the user
has explicit permission to use that resource. More specifically, access to
certain objects is required in order to use the corresponding resources of
the computer system.
All system objects have a consistent data structure, and a consistent
method of defining the operations which apply to each type of object. As a
result, it is relatively easy to add a new type of system object to the
operating system, or to change an existing system object.
Another feature of the present invention is a multifaceted access control
system. The object based operating system of the present invention
supports multiple levels of visibility, allowing objects to be operated on
only by processes with the object's range of visibility. This allows
objects to be made private to a process, shared by all processes within a
job, or visible to all processes within the system.
In addition to visibility control, access to each object is controlled
through an access control list which specifies the processes authorized to
access the object, and the types of access that are allowed. An object
with a restricted access control list can be associated with a "privileged
operation", thereby restricting use of the privileged operation to those
user processes authorized to access the corresponding object. An object
can furthermore be allocated to a specified job or process to protect the
object from use by others, thereby denying access by otherwise authorized
processes.
Yet another feature of the present invention concerns "waitable objects",
which are objects used to synchronize the operation of one or more
processes with one another or with specified events. The present invention
provides routines for generating new types of waitable objects without
modifying the operating system's kernel. More particularly, a set of
several different types of predefined kernel synchronization primitives
can be embedded in user defined objects, thereby enabling ordinary
programmers and system users to define and generate waitable objects.
BRIEF DESCRIPTION OF THE DRAWINGS
Additional objects and features of the invention will be more readily
apparent from the following detailed description and appended claims when
taken in conjunction with the drawings, in which:
FIG. 1 is a block diagram of a computer with a multitasking operation
system.
FIG. 2 is a block diagram of the virtual memory spaces of several
concurrently running user processes.
FIG. 3 is a block diagram showing how data structure objects in the system
are organized in a three level hierarchy.
FIG. 4 is a block diagram showing the hierarchical relationship between a
user object, a job, the processes for a job, and the execution threads for
a process.
FIG. 5 is a block diagram showing the range of objects visible to a
particular execution thread.
FIG. 6 is a block diagram of the container directory and object container
data structures at one level of the three level hierarchy shown in FIG. 3.
FIG. 6A is a more detailed diagram of the process level container
directory for a process.
FIG. 7 is a block diagram of an object ID.
FIG. 8 is a block diagram of the data structure of an object.
FIG. 9 is a block diagram an object type descriptor.
FIG. 10 is a block diagram of the process for adding a new object type to
the system by creating an object type descriptor for the new object type.
FIG. 11 is a block diagram showing the reference pointers for a specified
object.
FIG. 12 is a flow chart of the process for creating a reference ID for a
specified object.
FIG. 13 is a flow chart of the process for deleting an object ID.
FIG. 14 is a flow chart of the process for transferring an object from one
object container to another object container.
FIG. 15 is a flow chart of the process for transferring an object container
to a specified container directory.
FIG. 16 is a flow chart of the process for conditionally creating a
specified object.
FIG. 17 is a block diagram of the access control list for an object and a
execution thread which is attempting to access the object.
FIG. 18 is a block diagram of the data structures for privileged operation
objects.
FIG. 19 is a block diagram of the data structures for allocating a set of
objects to a thread, process, job or user.
FIG. 20 is a block diagram of the data structures for implementing user
defined waitable objects.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring to FIG. 1, a computer system 100 in accordance with the present
invention includes a high speed central processing unit (CPU) 102 which
concurrently runs several processes 104-110. The CPU 102 may be either a
single powerful processor or may contain multiple processors. As is
standard in multitasking computer systems, each process has its own
virtual memory space which is mapped partially into high speed primary
memory 112 and partially into lower speed secondary memory 114 by a
virtual memory manager 116. More generally, each process 104-110 is
allocated a certain portion of computer's resources, including selected
peripheral devices such as terminals 120-122 and other input/output
devices 124 and 126. Other types of resources which are allocated to
selected ones of the processes include specified sets of data and data
structures in the system's memory 112-114.
The set of software which controls the computer's operation and the
allocation of resources to the processes 104-110 running the computer is
called the operating system 130. For the purposes of the present
discussion it can be assumed that the operating system 130 is resident in
primary memory 112, although certain infrequently used portions of the
operating system may be swapped out to secondary memory by the memory
manager 116.
One feature of the present invention is that the computer system 100 can
serve as a "computer server" to one or more client computers 132. Client
computers 132, coupled to the CPU 102 by a bus interface 134, can send
tasks to the computer system 100 for execution. The computer system 100 is
a mainframe or other high performance computer system which can execute
tasks in a relatively short period of time compared to the client
computers 132. The operating system 130 of the present invention includes
a mechanism for setting up a process in the computer system 100 which
adopts the "profile" or characteristics of the process in the client
computer which is being served.
Referring to FIG. 2, there is shown a block diagram of the virtual memory
spaces of several concurrently running user processes 104-108. The virtual
memory space of every process includes a portion 140 which can be accessed
by "user mode" programs as well as "kernel mode" programs, and a portion
142-144 which can be accessed only by "kernel mode" programs. The kernel
mode portion 142-144 includes two sets of software called "the kernel" 142
and "the executive" 144.
As shown in FIG. 2, the portion of the virtual memory space which comprises
the kernel mode portion 142-144 is common to all user processes running in
the computer system. In other words, a predefined portion of the address
space of every user process is occupied by the operating system 130 and
its data structures. The user mode portion of each user process 140
occupies a distinct virtual memory space.
"Kernel mode" is a mode of operation used only by kernel and executive
software routines. Only kernel mode routines can access the data
structures used to control the operation of the computer system and to
define the system resources allocated to each user process.
When a user mode program 145 in a user process 104 creates an object, or
performs any one of a number of operations on an object, the user process
calls a kernel mode routine 146 in the kernel mode portion 142-144 of its
address space to perform the necessary operations. When the kernel mode
routine 146 completes the necessary operations on the kernel mode data
structures, it returns control to the user mode program 145.
The kernel 142 is the "lowest layer" of the operating system 130 which
interacts most directly with the computer's hardware 148. The kernel 142
synchronizes various activities, implements multiprocessing capabilities,
dispatches execution threads, and provides services to device drivers for
handling interrupts.
The executive 144, which also runs in kernel mode, implements system
services, memory management, user-level object support, the computer's
file system, network access, and device drivers. The executive defines
"system policy", such as the rules which govern the visibility of user
accessible objects. OBJECT ARCHITECTURE
The object architecture of the present invention is a set of data structure
and procedures which controls the use of user definable objects.
GLOSSARY
To clarity the following discussion, the following definitions are
provided.
"objects" are data structures used to hold information that is used by the
operating system and which must be protected from unauthorized access by
users of the system. While users cannot themselves "define" objects, they
can ask the operating system to create specified objects on their behalf.
The resultant objects are system date sturctures that are accessible by
the user through system rounties which protect the intergrity of those
objects. For instance, a "process object" is a type of object used in the
present invention to store the information needed by the operating system
to keep track of the status of a particular user process. "User accessible
objects" are objects used by user processes, and will be referred to
herein simply as "objects."
"Kernel objects" are a different set of data abstractions used by the
system's kernel and are called kernal objects in order to distinguish them
from the regular objects which are part of the object architecture of the
present invention.
A "user" is herein defined to mean a person or other entity recognized by
the computer system as being authorized to create processes and to use
resources in the computer system.
A "job"represents the current set of system resources being used by a
particular user.
A "process" is the entity to which a virtual memory address space is
assigned, and is the entity to which process-level objects are assigned.
There can be multiple processes in a job. Whenever a job is created, a
"top level" process is created for that job. Any process, including the
top level process, can cause the creation of additional processes, called
suprocesses or child processes. Any process which creates another process
is referred to as a parent process.
A "thread", also called an "execution thread", is the entity which actually
executes programs and thus provides a stream of execution (sometimes
called a context state). It is the schedulable entity which executes
program steps and consumes resources. More technically, a thread is a
system defined object that executes a program that is resident in a
process's address space. A thread contains a machine state that consists
of the computer's register contents, a program counter, and other
privileged information needed to cause the thread to execute a program.
Each process many create a number of execution threads which run
"simultaneously" and which can share resources and communicate with one
another. Multiple threads can run simultaneously when multiple CPUs are
available. On a single CPU system the operating system makes the threads
appear to run simultaneously. All resource limitation data structure for a
thread belong to the thread's process
An "object contianer" is a data structure for storing pointers to objects.
It is essentially a table which is used to keep track of a set of objects.
A "container directory" is a data structure for storing pointers to a set
of object containers. Thus a container directory is a table used to keep
track of a set of object containers.
OBJECT HIERARCHY
Referring to FIG. 3, the object architecture of the present invention
provides a hierarchical "visibility structure" for objects. When an object
is "visible"to a particular execution thread or process it means that the
execution thread may at least attempt to access that object. Objects not
visible to a process are stored in such a way that the process cannot even
attempt access.
When an object is created, it is placed at one of three level: the system
level 160, the job level 162, or the process level 164. At the system
level 160 there is a single container directory 170 which contains a set
of system level object containers 172, 174, 176. Objects 178-180 in system
level containers are visible to all threads on the system.
At the job level 162 there is a container directory 190 for every job that
is currently active in the system. Each job level container directory 190
contains a set of job level object containers 192, 194, 196. Objects as
the job level 162 are visible only to threads in that job.
At the process level 164 there is a container directory 200-206 for every
process that is currently active in the system. Each process level
container directory 200 contains a set of process level object containers
212, 214, 216. Objects at the process level 164 are visible only to
threads in that process. For example, a thread cannot access an object
that is a the process level for another process. As will be explained
below, this visibility restriction is achieved by giving each process a
pointer, called an object ID, only to its own process level container
directory. Because a process cannot have a pointer to the process level
container directory for other processes, each process is incapable of
"expressing" the object ID of objects in the containers not visible to
that process.
Each process is assigned at least two proces level object containers 212
and 214. The first object container 212 is called the public display
container for the process and the second container 214 is called the
private container. Only objects that the process wants to be accessible to
subprocesses are placed in the public display container 214, and all other
objects created by the process are put in its private container 216.
Referring to FIG. 4, there is a hierarchy of objects which represents
users, jobs, processes and threads. FIG. 4 shows the hierarchical
relationship between the objects for a user, a job, the processes for a
job, and the execution threads for a process.
As shown, there are four levels of objects in the User-Job-Process-Thread
(UJPT) hierarchy, and each type of object is stored in a corresponding
system level object container 220, 222, 224 and 226. All user objects 230
are stored in a user object container 220. Job objects 232 are stored in a
job object container 222. Process objects 234 and 236 are stored in a
process object container 224, and thread objects 240, 242 and 244 are
stored in a thread object container 226.
The four levels of objects provide a logical grouping of functionality and
control. A user object 230, which appears at the highest level of the
User-Job-Process-Thread (UJPT) hierarchy, defines the security profile and
resource quotas/limits for its underlying objects. The user object 230
also stores a pointer to the job object 232 for the user.
A job object 232 provides a job level container directory and a set of
resource limits for a collection of processes running as a job. The job
object 232 includes a reference pointer to its user object 230, and a list
head which points to the first process object 234 for the job. Thus the
process objects 324-236 for a particular job are accessed as a linked
list. Not that in FIG. 4, linked list pointers are depicted as narrow
lines with arrow heads which point either down or to the right within the
hierarchy, while reference pointers are depicted as thicker lines with
arrow heads that point upwards in the hierarchy.
A process object 234 provides a process level container directory, a
pointer to the page table for the process, and pointers to the parameters
needed to manage the address spaces of its execution threads. The process
object 234 includes a reference pointer to its job object 232, and a list
head which points to first thread object 240 for the process. The thread
objects 240-242 for a particular process are accessed as a linked list.
The process object 234 also contains a list head which points to the first
subprocess for which the object 234 is the present process (not shown in
FIG. 4).
A thread object 240 contains a thread control block which stores the
processor state as it executes the steps of a program, including the
pointers and values needed to keep track of all resources used by the
thread object. The thread object 240 includes a reference pointer to its
process object 324, and a list pointer for joining additional thread
objects into a thread list of threads for the process.
FIG. 5 is a block diagram showing the range of objects visible to a
particular execution thread. In particular, each thread object contains a
thread control block 250 which points to the software process control
block 252 for the thread's process. The software process control block 252
contains pointers which indirectly point to a container directory at each
of threee visibility levels. The container directory 170 a the process
level is the container directory belonging to the process object for the
thread. Similarly, the container directory 190 a the job level is the
container directory belonging to the job object for the thread. The system
level container directory 200 is the same for all threads.
MUTEXES
Acess to each and every container directory is governed by a corresponding
mutex. A mutex is essentially a flag used to synchronize access to a
corresponding system resource. The purpose of a mutex is to ensure that
only one thread accesses a particular resource at any one time. To use a
resource that is protected by a mutex, one must first "obtain the mutex".
Obtaining a mutex is an atomic (i.e., uninterruptable and interlocked)
operation in which the mutex is testesd. If the mutex was previously set,
the process trying to obtain the mutex is suspended until the mutex
becomes free. If the mutex is free, it is set and the requesting process
is then allowed to access the protected resources.
Mutexes are used throughout the present invention to synchronize access to
container directories, object containers, linked lists of objects, and
many other types of datea structures. For instance, to change certain
fields of an object, the thread making the change must first obtain the
mutex for the container in which the object is located. In addition, many
objects contain a mutex which protects that objects.
All mutexes used by the system are stored in an array 254 in a non-paged,
protected portion of primary memory, accessible only to kernel mode
routines, which cannot be swapped out by the memory manger. The "mutexes"
shown in many of the data structures in the Figures are actually pointers
to the corresponding mutexes in the mutex array 254. In other embodiments
the mutexes need not be stored in an array so long as they are stored in
non-paged, protected memory.
As will be explained in more detail below, in the section entitled Waitable
Objects, mutexes are a special type of kernal synchronization primitive.
As shown in FIG. 5, there is a mutex for each of the three container
directories which are visible to a particular thread.
CONTAINER DATA STRUCTURES
Referring to FIG. 6, there is shown a portion of the data structure for one
container directory 260 and one object container 262. For the purposes of
this discussion, the container directory and object container data
structures may be at any level of the three level hierarchy shown in FIG.
3.
The data structures for container directories and object containers are
virtually identical. For the sake of clarity, the data structure for an
object container will be explained first.
An object container 262 comprises a container object 270, which contains a
standard header 272, a pointer 274 to a name table 275, and a pointer 276
to an object array 280. The purpose of the name table 275 is to translate
object names into object IDs, and the purpose of the object array 280 is
to translate object IDs into pointers to objects 281. The object container
also includes a container mutex 278 which is used to synchronize access to
certain fields in the name table 275, the object array 280, and the
objects in the container.
The name table 275 has two portions, an object name array 282 and an array
of name definition blocks 284. The object name array 282 is simply an
index into the array 284 of name definition blocks and may be implemented
as either a hash table or a binary tree. In either case, each entry in the
name array 282 contains one object name and one pointer to an entry in the
array of name definition blocks 284. Each name definition block 286
contains information for one object name, including the object ID as well
as the object's type (object types are described in more detail below) and
mode (i.e., accessible by user mode or kernal mode routines).
The object array 280 contains an array size values 288 which denotes the
size of the array 280, which corresponds to the maximum number of object
points that can be stored in the object array 280. The obje | | |
